一文了解最熱門的 zkSNARK 方案:Groth16 方案

原文標題:一文了解最熱門zkSNARK方案:零知識證明引論(三)

在之前的文章中,我們介紹了零知識證明的 基礎概念 以及構造 zkSNARK 的 基本思想和方法。從本文開始,我們將逐一介紹目前最熱門的 zkSNARK 方案。文章旨在讓讀者理解這些方案的基本原理。為了方便敍述並容易理解,在敍述方案時,我們會做一些簡化處理,重在傳達方案的核心思想。

本文介紹的是 Groth16 方案。Groth16 方案,顧名思義,就是 Groth 在 2016 年發表的一篇論文 [Gro16] 中提出的方案。目前為止,Groth16 是在實踐中使用最廣泛的 zkSNARK (沒有之一)。特別一提的,Zcash 目前使用的 zkSNARK 方案就是 Groth16。從性能上,Groth16 的 Verifier 性能是所有 zkSNARK 中最快的,其證明字符串也是最短的。

而 Groth16 的最大缺點就是它需要對每個電路都執行一次可信初始化。

在介紹 Groth16 之前,簡單回顧一下 zkSNARK 所要解決的問題。我們稱這個問題為「計算驗證問題」。

計算驗證問題

任何計算都可以描述為一個算術電路。一個算術電路可以對數字進行算術運算。電路由加法門、乘法門以及一些常數門組成,如下圖所示:

一文了解最熱門的 zkSNARK 方案:Groth16 方案

這個例子中的電路包含了 15 個門。這個電路所描述的計算過程需要輸入五個數字 x1 到 x5,輸出四個數字。

給定一組輸入的數字,需要把這個電路中的每個門都計算一遍,才能計算出這個電路的輸出。在這個例子中,如果輸入是 (1,2,3,4,5) ,則電路的輸出為 (-27,14,80,171),如下圖所示:

一文了解最熱門的 zkSNARK 方案:Groth16 方案

計算驗證問題是指,如果一個驗證者——不妨叫做 Verifier——只拿到了電路的一組輸入和輸出,如這個例子中的 (1,2,3,4,5) 和 (-27,14,80,171) ,它該如何驗證這是一對合法的輸入和輸出呢?最簡單粗暴的方法就是把這個輸入重新扔進電路算一遍。如果電路很大的話,這個驗證方法最大的缺點就是效率問題。

一文了解最熱門的 zkSNARK 方案:Groth16 方案

有些場景下,效率還不是唯一的問題。例如,輸入可能包含 Verifier 不能知道的秘密信息。假設上例中的 (3,4,5) 是秘密輸入,Verifier 只能看到 (1,2) ,如下圖所示。此時 Verifier 要驗證的問題就變成了「是否存在 (?,?,?) 使得電路在輸入 (1,2,?,?,?) 的時候的輸出是 (-27,14,80,171) 」。這個場景下,即使是簡單粗暴的重新計算也不再可行。

一文了解最熱門的 zkSNARK 方案:Groth16 方案

一句話概括計算驗證問題:Verifier 能否在不知道秘密輸入的情況下,高效地驗證計算結果?

從電路到 R1CS 問題

一個 zkSNARK 就是對上述問題的一個解決方案。使用 zkSNARK,一個證明者,叫做 Prover,可以為計算過程生成一個簡短的證明字符串。Verifier 讀取這個字符串,就可以判斷給定的公開輸入和輸出是否合法。

Groth16 是眾多 zkSNARK 構造方案中的一種。接下來,我們介紹 Groth16 是怎麼解決計算驗證問題的。

首先,我們重新審視一下 Verifier 的任務:我們只知道電路的前兩個輸入是 (1,2),我們的目標是要判斷是否存在一組合法的秘密輸入,使得電路的輸出是 (-27,14,80,171)。如果我們換個角度看這個問題,它其實可以描述為:給一個電路,上面有些空格可以填數字,有些空格已經填上了數字,請問是否存在一種填法,能夠同時滿足每個門的邏輯?

從這個新的角度,計算驗證問題被轉換成了一個類似於數獨那樣的填數字遊戲:有一些空格,一部分已經填上,請你填上另外一些空格,滿足一些限制條件。

一文了解最熱門的 zkSNARK 方案:Groth16 方案
一文了解最熱門的 zkSNARK 方案:Groth16 方案

然後,我們為每一個要滿足的條件列一個方程。這裏,每個要滿足的條件其實就是一個門的邏輯:加法門的輸出等於兩個輸入之和,乘法門的輸出等於兩個輸入之積。於是,原來的填空遊戲就變成了一個多元方程組。上述例子轉化得到的方程組如下:

一文了解最熱門的 zkSNARK 方案:Groth16 方案

最後,我們對這個方程做一些整理,使得它能夠寫成矩陣和向量的形式,更加整齊和簡潔。我們把每個方程都寫成 * = * x * 的模式。儘管並不是所有方程中都有乘法,但我們可以給沒有乘法的式子乘上一個 。於是方程組變成了下面這個樣子:

一文了解最熱門的 zkSNARK 方案:Groth16 方案
一文了解最熱門的 zkSNARK 方案:Groth16 方案

把所有方程合到一起,就得到了原方程組的矩陣表示

一文了解最熱門的 zkSNARK 方案:Groth16 方案

我們把最終得到的這個矩陣向量方程叫做一個Rank-1 Constraint System (R1CS)。

一文了解最熱門的 zkSNARK 方案:Groth16 方案

總結一下,這一節中我們把計算驗證問題轉化成了數學問題 R1CS。

在計算驗證問題中,Verifier 知道一個電路,拿到公開部分的輸入,以及電路的輸出,判斷它們是否合法。

一文了解最熱門的 zkSNARK 方案:Groth16 方案
從 R1CS 問題到 QAP 問題

在零知識證明領域,R1CS 基本上就是電路的代名詞。許多 zkSNARK 把 R1CS 問題作為目標問題。不過,大部分 zkSNARK 不會直接對 R1CS 下手,而是把 R1CS 問題繼續轉化,得到一個等價的多項式問題,再對這個多項式問題設計證明方案。Groth16 也不例外。不同的 zkSNARK 選擇的多項式問題各不相同,Groth16 選擇的是一個叫做Quadratic Arithmetic Programming (QAP)的問題。

這一節中介紹一下怎樣把 R1CS 問題轉化為等價的 QAP 問題。

一文了解最熱門的 zkSNARK 方案:Groth16 方案
一文了解最熱門的 zkSNARK 方案:Groth16 方案

然後,我們把這些列向量換成多項式,使得多項式方程和原先的向量方程等價。

把向量轉化成多項式的一種方式是使用多項式插值。

多項式插值

一文了解最熱門的 zkSNARK 方案:Groth16 方案
一文了解最熱門的 zkSNARK 方案:Groth16 方案

QAP 問題

現在,我們直接把 R1CS 矩陣中的列向量換成它們的多項式插值,得到的結果如下圖所示。

一文了解最熱門的 zkSNARK 方案:Groth16 方案
一文了解最熱門的 zkSNARK 方案:Groth16 方案

我們用一個表格總結一下上文中提到的所有問題。

一文了解最熱門的 zkSNARK 方案:Groth16 方案

為什麼要越搞越複雜,把電路問題轉化為 QAP 問題呢?一個簡單的回答:就是為了引入多項式!多項式是一個強大的工具。多項式的作用,可以理解為一個「槓桿」,或者叫「誤差放大器」。如果我們要檢查兩個長度為 10000 的向量是否相等,一定需要檢查 10000 次,哪怕檢查過了 9999 個點都是一樣的,也不能保證最後一點是相同的。而兩個 10000 次的多項式,哪怕非常接近,比如説它們的係數有 9999 個都相同,或者它們在 這些點上的取值都相等,但只要有一個點不同,這兩個多項式就截然不同。這意味着,如果在一個很大的範圍內,例如 到 當中均勻隨機選一個點,兩個不同的多項式在這個點上相等的機會只有 。檢查兩個多項式是否相等,比檢查同樣規模的向量要快得多,這幾乎是所有 zkSNARK 提高 Verifier 效率的根本原理。

為 QAP 問題構造 zkSNARK

QAP 問題就是 Groth16 要用來構造 zkSNARK 的最終問題了。不過,在解釋 Groth16 的構造細節之前,我們先準備一些工具。

準備工具

我們假設讀者對橢圓曲線羣的基本特性和應用有所瞭解,並採用加法羣的記號來描述橢圓曲線羣中的點和運算。橢圓曲線羣中的元素可以用來表示多項式,並限制 Prover 必須使用給定的多項式來進行線性組合。這正是 QAP 所需要用到的特性。

我們看一下橢圓曲線是怎麼用來表示多項式的。

KoE 假設

一文了解最熱門的 zkSNARK 方案:Groth16 方案

然而,上述直覺並不能從離散對數假設嚴格地證明而來。所以,只能把它作為一個新的安全性假設來用。這個假設就叫做 Knowledge-of-Exponent (KoE) 假設。

KoE 假設怎樣應用到 QAP 問題上呢?那就是,KoE 允許我們使用橢圓曲線點來表示多項式,並且迫使 Prover 只能從已知的多項式線性組合產生新的多項式。

一文了解最熱門的 zkSNARK 方案:Groth16 方案

不過,到目前為止,我們忽略了兩個關鍵問題:

一文了解最熱門的 zkSNARK 方案:Groth16 方案

關於第二個問題,一個解決方法就是雙線性配對。

雙線性配對

一文了解最熱門的 zkSNARK 方案:Groth16 方案

現在,我們已經準備好了工具:KoE 假設和雙線性配對。接下來,我們就介紹 Groth16 是如何為 QAP 問題構造 zkSNARK 的。

Groth16 方案

一文了解最熱門的 zkSNARK 方案:Groth16 方案

Setup

一文了解最熱門的 zkSNARK 方案:Groth16 方案

Prove

一文了解最熱門的 zkSNARK 方案:Groth16 方案

Verify

一文了解最熱門的 zkSNARK 方案:Groth16 方案

解析

我們簡單解釋一下上述構造為什麼能夠工作。至於它為什麼是安全的,請感興趣的讀者參閲 [Gro16] 原文。

一文了解最熱門的 zkSNARK 方案:Groth16 方案

當然,Verifier 的驗證式中還包含了許多其他項,但在 Groth 的精心設計下,它們都消掉了。感興趣的可以自行驗證。

小結

本文中,我們解釋了 Groth16 這個 zkSNARK 方案的構造原理。我們從算術電路開始,介紹了怎樣將計算驗證問題轉化為 R1CS 問題以及 QAP 問題。然後我們解釋了怎樣使用 Groth16 方案來證明知道一個 QAP 問題的解。Groth16 方案使用了 KoE 假設以及雙線性配對。它的缺點是需要可信第三方進行初始化,而且初始化過程需要對每個電路進行一次。與此同時,Groth16 享有最高效的 Verifier 算法以及最短的證明字符串,使得 Groth16 成為至今仍然應用最廣的 zkSNARK 方案。

參考資料

[Gro16] Jen Groth. On the Size of Pairing-based Non-interactive Argument. 2016.

撰文:Cyte

版權聲明:本文源自 網絡, 於,由 楠木軒 整理發佈,共 3829 字。

轉載請註明: 一文了解最熱門的 zkSNARK 方案:Groth16 方案 - 楠木軒