zk-SNARK 是如何實現零知識證明的?從技術角度詳細解讀。

原文標題:《徹底讀懂零知識證明及其實現方法:解析 zk-SNARK》
撰文:李畫
致謝:東澤、even
參考:Maksym Petkus,Why and How zk-SNARK Works: Definitive Explanation

我們已經越來越頻繁地見到 zk-SNARK,我們還會更多地遇到它。

大家都知道它是一種實現零知識證明的方法,也知道它是擴容和隱私方向的利器,但究竟什麼是零知識證明,zk-SNARK 是如何實現零知識證明的?這便是本文試着去回答的問題。

閱讀這篇文章需要保持較高的專注度,以及適當思考;但本文盡力做到沒有含混和晦澀之處,所以如果你保持專注,看完就能理解零知識證明究竟是如何通過 zk-SNARK 做到的,而不是停留在只知道概念的階段。

那麼現在,開始吧。

技術詳解零知識證明實現方法:以 zk-SNARK 爲例

第一階段:爲使用 zk-SNARK 做準備工作

把零知識證明的需求轉換爲數學運算電路

保險機構需要知道用戶的一個體檢數據是否達標,用戶只想讓保險機構知道數據是否達標,但不透露具體的數據給他們。怎麼去做?

假設這個體檢的隱私數據是 x,x 的值在 0~7 之間(包含 0 和 7)爲達標,否則爲不達標。那要做首先是把這個需求轉換爲一個可計算的問題,即有一個程序,其輸入爲 x,當 x 在 0~7 之間時,輸出「真」,當 x 不在該區間時,輸出「假」。

該程序的計算過程可以被表達爲如下一組方程的驗證過程。當輸入 x 後,如果這 4 個方程都能被滿足,也就是方程左邊的計算結果都爲 0,就能證明 x 在 0~7 之間,那麼就輸出「真」,否則輸出「假」。這 4 個方程爲:

b0 * (b0-1)= 0 

b1 * (b1-1)= 0

b2 * (b2-1)= 0

2^0 * b0 + 2^1 * b1+2^2 * b2 – x = 0

注:b0、b1、b2 的值由 x 確定,它們也是輸入;前 3 個方程約束 b0、b1、b2 的值爲 0 或 1;最後 1 個方程驗證 x 的取值在 0~7 之間。

可以把這樣的一組方程表達爲一個數學運算電路。以 b0 * (b0-1) 爲例,它這一部分的電路如下圖所示。

技術詳解零知識證明實現方法:以 zk-SNARK 爲例

而整個程序的計算過程可以抽象表達爲下圖:

技術詳解零知識證明實現方法:以 zk-SNARK 爲例

如此一來,零知識證明的問題就被轉化爲「輸入+用作證明的數學運算電路+輸出」;如果輸出爲真,就可以相信輸入爲真。在本文的例子中,如果輸出爲 0,就可以相信用戶的體檢數據達標。

把數學運算電路轉換爲多項式

在把零知識證明的需求轉換爲數學運算電路後,我們能夠把驗證者和證明者這兩個角色分開。而當驗證者不是證明者時,就創造了一個可以隱藏輸入(原始數據)的機會。

隨之而來問題只有一個:驗證者憑什麼相信這個「輸出」是「輸入」通過「用作證明的數學運算電路」計算出來的?最簡單的辦法就是驗證者看着證明者輸入和計算,但這樣就無法隱藏輸入了。

所以我們要在數學運算電路的基礎上接着做轉換,把輸入、用作證明的數學運算電路、輸出這三者綁定到一起,也就是說,能夠通過某種方式驗證「輸出」是否爲「輸入」通過「用作證明的數學運算電路」計算出來的。

這樣一來,在輸出爲真的前提下,只要該驗證通過,證明者就可以相信輸入爲真。

爲了完成這種綁定,需要把數學運算電路轉換爲多項式。

(以下爲數學轉換過程,若無興趣可跳至下一張圖片下方的段落)

首先要把數學運算電路轉換爲一階約束系統(RICS)。

Vitalik 在《Quadratic Arithmetic Programs: from Zero to Hero》一文中詳細介紹了這個轉換過程,本文爲省略細節描述,將直接引用 Vitalik 使用的例子。

這是一個數學的過程,我們只需要知道這種轉換是等價的即可,若希望知曉細節,可閱讀 Vitalik 的文章。

Vitalik 的那組方程爲:




x * x - sym_1 = 0  


sym_1 * x – y = 0

(y + x) * 1 - sym_2 = 0

(sym_2 + 5) * 1 - ~out = 0

以其中的第一個方程 x * x - sym_1 = 0 爲例,它被轉換爲 R1CS 後的形式如下所示:

a = [0, 1, 0, 0, 0, 0]  


b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 1, 0, 0]

s = [~one,x,~out,sym_1,y,sym_2]

R1CS 是由上方 3 個向量(a, b, c)組成的序列,解向量爲 s,且滿足 s. a * s.b - s.c = 0,這也被稱作一個約束。可以試着計算一下,你會發現 s.a * s.b - s.c = x * x - sym_1,它們是等價的。

Vitalik 的例子包含 4 個拍平後的方程,每個方程對應一個 RICS 約束,因此一共有 4 個約束。

接下來是把 R1CS 轉換爲多項式。依然不需要深入理解如何轉換,只需要知道轉換是等價的。轉換過程如下:

一共有 4 個 RICS 約束,每個約束中都包含一個向量 a,因此一共有 4 個向量 a,它們分別是:

a = [0, 1, 0, 0, 0, 0]  


a = [0, 0, 0, 1, 0, 0]

a = [0, 1, 0, 0, 1, 0]

a = [5, 0, 0, 0, 0, 1]

通過拉格朗日插值法,可以把這 4 個向量轉換爲 6 個多項式(因爲每個向量包含 6 個值),它們分別是:

–5+ 9.166* x- 5* x^2+0.833* x^3  


8- 11.333 * x + 5 * x^2-0.666 * x^3

0 + 0 * x + 0 * x^2 + 0 * x^3

–6 + 9.5 * x - 4 * x^2 + 0.5 * x^3

4 - 7 * x + 3.5 * x^2 - 0.5 * x^3

–1+ 1.833 * x- 1 * x^2+ 0.166 * x^3

可以試着把 x= 1 代入這 6 個多項式計算,將得到 [0、1、0、0、0、0] 這 6 個值,你會發現它們正是第一個約束下的向量 a;把 x 等於 2、3、4 分別帶入這 6 個多項式,將得到其他 3 個約束下的向量 a。

向量 a 對應 6 個多項式,向量 b 和向量 c 也是如此,因此一共會有 18 個多項式。當 x=1 時,這 18 個多項式的 18 個解正是第一個約束;當 x 等於 2、3、4 時,分別得到第 2、3、4 個約束。多項式與 RICS 是等價的。

到此就完成了從數學運算電路到多項式的轉換:

  • 通過 RICS 轉換,把證明多個原方程轉換爲證明多個 s.a * s.b - s.c = 0 ;

  • 通過多項式轉換,把證明多個 s.a * s.b - s.c = 0 轉換爲證明在 x=1、x=2、x=3、x=4 時,A(x) * B(x) – C(x) = 0,其中 A(x) = s.a,B(x) = s.b,C(x) = s.c。如下圖所示。

圖中最左邊一行數字 [1, 3, 35, 9, 27, 30] 爲 Vitalik 例子中的解向量 s。A1(x) 爲 a 的第 1 個多項式在 x 處的取值,比如 A1(1)=0;A1(x)~A6(x) 構成第 x 個約束的向量 a,比如 x=1 時,a=[0、1、0、0、0、0];其他同理。

技術詳解零知識證明實現方法:以 zk-SNARK 爲例

(若跳過轉換,可從此處接着閱讀)

我們似乎是在通過一個繁瑣的步驟,把本來簡單的證明變成了複雜的證明,爲什麼?如果你仔細觀察,就會發現一件神奇的事情發生了:

本來驗證者需要驗證的是:輸入通過用作證明的數學運算電路,輸出爲真;但現在驗證者需要驗證的是,當 x=1、x=2、x=3、x=4 時,A(x) * B(x)–C(x) = 0。

A(x) * B(x)–C(x) 中包含了解向量 s,它是把輸入、輸出、電路綁定在一起的;驗證 A(x) * B(x)–C(x) = 0,就是在驗證輸入和輸出是否滿足用作證明的數學運算電路。

這便解決了本節開始時提出的問題:驗證者憑什麼相信「輸出」是「輸入」通過「用作證明的數學運算電路」計算出來的。

如此一來,驗證者就不需要關注具體的輸入和計算過程,只需要驗證 A(x) * B(x) – C(x) = 0 本身是否成立。這讓我們真正有了機會去隱藏輸入。

到此處可以長舒一口氣了,雖然還沒開始進入 zk-SNARK,但我們已經完成了最艱難的部分。如果轉換部分沒有理解清楚也沒關係,你只需要知道:

通過 zk-SNARK 實現零知識證明,實際上是要在 zk-SNARK 的幫助下,驗證當 x= 1、2、3、……、n 時,A(x) * B(x)–C(x) = 0,其中 n 是 RICS 約束的個數;而不同的零知識證明問題,區別只在於它們的 A(x)、B(x)、C(x) 不同。

把多次驗證轉換爲一次驗證

對於包含 n 個約束的零知識證明問題,需要進行 n 次 A(x) * B(x)–C(x) 是否爲零的驗證。可不可以把 n 次驗證變爲一次驗證?可以。

  • 定義 t(x) = (x-1) * (x-2) * …… * ( x-n),t(x) 在 x=1、x=2、…… 、x=n 處必然等於零;

  • 那麼如果有一個多項式 h(x),使得 A(x) * B(x)–C(x) = t(x) * h(x) 成立,便意味着 A(x) * B(x)–C(x) 這個多項式可以被 t(x) 整除,那麼這個多項式在 x=1、x=2、…… 、x=n 處也必然等於零。

也就是說,驗證 A(x) * B(x)–C(x) = t(x) * h(x) ,就能夠一次完成全部 RICS 約束的驗證;而一旦這個驗證通過,就可以相信輸入爲真。

現在終於可以把接力棒交給 zk-SNARK 了,它要做的工作就是幫助驗證 A(x) * B(x)–C(x) = t(x) * h(x)。

驗證的過程是怎樣的?很簡單。verifier (驗證者)選擇一個隨機數 x 發起挑戰,prover (證明者)證明在這個 x 處, A(x) * B(x)–C(x) = t(x) * h(x)。

在不知不覺中,一件關鍵又有趣的事情發生了:

證明者本來需要證明在 x=1、x=2、…… 、x=n 時,A(x) * B(x)–C(x) = 0,這是一種推理式證明,就像我們解數學題,需要一步步地推導和計算,在這種證明過程中,要隱藏解題的知識是困難的。

但現在,推理式證明變成了交互式證明:verifier 在一個隨機點上提出挑戰,prover 給出這個點上的解響應挑戰;prover 需要有「知識」才能計算出隨機點上的解,但這個解本身不會泄露「知識」。

而這,就是零知識證明得以成立的前提,或者說,如果沒有交互式證明這種證明方法,零知識證明這個領域便不會存在。

接下來只剩下一個問題:爲什麼能通過驗證多項式上的一個點來確定兩個多項式 A(x) * B(x)–C(x) 與 t(x) * h(x) 是否相等?

這是由多項式的特性決定的,「一個多項式在任意點的計算結果都可以看做是其唯一身份的表示」。(引自 Maksym)

用圖形說明更爲直觀。下圖是兩個多項式,藍色曲線是 f(x) = x^3– 6 * x^2+ 11 * x– 6,綠色曲線是 f(x) = x^3– 6 * x^2+ 10 * x– 5,不難發現,兩個多項式只有微小的不同,但它們的曲線卻是迥異的。

技術詳解零知識證明實現方法:以 zk-SNARK 爲例

就像世界上沒有兩片相同的樹葉,世界上也沒有會在某個區域重合的兩條不同曲線,它們只會在有限的點上相交。對於兩個階數爲 d (x 的最大指數)的多項式,它們相交的點數不會超過 d。

在本文的應用中,有一個多項式 A(x) * B(x)–C(x),一個多項式 t(x) * h(x),如果它們不相等,它們只會在最多 d 個點上相交,也就是在 d 個點上的解相同。

這意味着只有當驗證者選擇的隨機挑戰點 x 恰好是這 d 個點中的一個時,纔有可能發生誤判,即在 A(x) * B(x)–C(x) 與 t(x) * h(x) 不相同的情況下誤以爲它們相同。

誤判的概率存在,但我們不用爲此擔心,比較 d 個點和 x 的取值範圍,這件事發生的概率極低;結合後續在 zk-SNARK 協議中使用的密碼學方法,這件事可以被認爲幾乎不可能發生。

那麼現在,在全部的準備工作完成後,本文進入下一個階段。對第一階段的抽象總結就是:零知識證明的問題就是驗證計算滿足多個約束的問題,而多項式可以一個點驗證多個約束。

第二階段:使用 zk-SNARK 完成零知識證明

得益於交互式證明和多項式的特性,我們可以通過驗證挑戰點 x 上多項式 A(x) * B(x)–C(x) 的解與 t(x) * h(x) 的解是否相等來驗證 A(x) * B(x)–C(x) = t(x) * h(x) 是否成立,這種方式是可以隱藏 A(x) * B(x)–C(x) 這個多項式的係數的。

多項式的係數就是零知識證明中的「知識 」,最明顯的,這個係數裏是包含了想要隱藏的祕密輸入(解向量 s)的。

使用 zk-SNARK 完成零知識證明,就是完成 verifier 給出隨機點進行挑戰的工作和 prover 給出隨機點上的解完成證明的工作,這實際上是_互不信任的 verifier 和 prover 之間的一場攻防戰,他們使用的武器是密碼學_。

verifier 加密挑戰點

分析需要被驗證的 A(x) * B(x)–C(x) = t(x) * h(x):

  • t(x) 是 verifier 和 prover 雙方都知道的一個多項式,t(x) = (x-1) * (x-2) * …… * ( x-n);

  • A(x) * B(x) – C(x) 只有 prover 知道,它的係數包含着知識;

  • h(x) 也只有 prover 知道,是用 A(x) * B(x) – C(x) 除以 t(x) 計算出來的,h(x) 不能被 verifier 知道,因爲可以通過 t(x) 和 h(x) 計算出 A(x) * B(x) – C(x)。

爲了清晰起見,先把 A(x) * B(x)–C(x) 寫爲 p(x),把要證明的問題簡化爲證明 p(x) = t(x) * h(x)。

其證明過程包含如下 3 步:

  • verifier 選擇隨機挑戰點 x,假設 x= r;

  • prover 收到 r 後,計算 p(r) 和 h(r),並把這兩個值給 verifier;

  • verifier 計算 t(r),然後計算 t(r) * h(r),並判斷 t(r) * h(r) = p(r) 是否成立,若成立,則驗證通過。

這實際上就是 zk-SNARK 的基礎工作流程,但直接這樣做會有一個問題:

prover 是知道 t(x) 的,如果把 r 給他,他就能夠計算出 t(r),那麼他完全可以構造出一對假的 p(x) 和 h(x),使得 p(r)= t(r) * h(r),結果就是他雖然不知道真正的 p(x),卻能騙過 verifier。

解決這一問題的辦法就是對 r 加密,使得 prover 可以計算某種形式下 p(r) 和 h(r),但卻不能通過該形式下的 t(r) 構造假的滿足驗證要求的 p(x) 和 h(x)。

觀察 prover 的證明過程,他需要計算 p(x) 和 h(x) 這兩個多項式,但不管哪一個,其形式均爲:c0+ c1*x^1+ ……+ cn*x^n;prover 本身知道 c0、c1 等等全部係數。

如果 verifier 把 x 給 prover,假設 x= s,prover 就能完成全部計算;但如果 verifier 把加密後的 s 給 prover,prover 是不能完成計算的,因爲他無法用加密後的 s 計算出 s^2、……、s^n。

所以當 verifier 確定隨機點 s 後,需要把加密後的 s、s^2、……、s^n 全部給 prover,這樣 prover 才能完成計算。

在實際應用中,verifier 是把 E(s)、E(s^2)、……、E(s^n) 給到 prover,其中 E(s) 是 s 的加密值,E(s) = g^s (mod n),這是一種同態加密方法。

同態加密有一個性質,就是先加密後計算的解與先計算後加密的解與是相同的。也就是說:

  • c0+ c1*E(s)+ ……+ cnE(s^n) = g^(c0+ c1s^1+ ……+ cn*s^n);

  • 即,p(E(s)) = E(p(s)) = g^p(s),h(E(s)) = E(h(s)) =g^h(s);

  • 那麼,prover 就能通過計算 p(E(s)) 和 h(E(s)),得到 g^p(s) 和 g^h(s)。

此處只需要知道這種計算確實可行即可,如果想了解密碼學部分的工作原理,可看我之前的一篇文章,《一文讀懂零知識證明背後的簡單邏輯》。

所以現在,證明過程變成了如下 3 步:

  • verifier 選擇隨機挑戰點 x,假設 x= s,然後把一整套 s 的加密值給 prover;

  • prover 收到後,計算 g^p(s) 和 g^h(s),並把這兩個值給 verifier;

  • verifier 計算 t(s),然後計算 (g^h(s))^ t(s),並判斷 (g^h(s))^t(s) = g^p(s) 是否成立,若成立,則驗證通過,因爲這意味着 h(s) * t(s) = p(s)。

通過對隨機點 s 加密,可以避免 prover 作弊,但 prover 還有一個漏洞可鑽,即他不使用 verifier 給出的挑戰點 s 計算 h(s) 和 t(s),而是用其他值計算並欺騙 verifier。

所以 verifier 還需要一個方法,該方法能夠證明 prover 給出的值確實是用 s 計算出來的。

本文將不具體展開這一部分,簡單而言就是 verifier 除了選擇隨機數 s 外,還要選擇一個隨機數α,prover 給出的解需要維持 s 和α 之間的關係,如果這個關係被破壞了,則證明他沒有用 s 在計算。

該方法被稱作指數知識假設,若想了解具體內容,可閱讀 Maksym 的文章。

在 verifier 完成了他的防守戰後,輪到 prover 了。

prover 加密計算結果

雖然 prover 只把多項式在挑戰點 x 上的解給了 verifier,但如果多項式係數的取值範圍較小,verifier 是有可能通過暴力破解從解計算出多項式係數,即知識的。因此,prover 需要對解加密。

證明過程變成如下 3 步:

  • verifier 選擇隨機挑戰點 x,假設 x= s,以及隨機數α,然後把一整套 s 的加密值、以及一整套α * s 的加密值給 prover;

  • prover 收到後,計算 g^p(s)、g^h(s)、g^(α*p(s));選擇隨機數δ 對解加密,變爲 (g^p(s))^δ、(g^h(s))^δ、(g^(α*p(s)))^δ;然後把這 3 個加密值給 verifier;

  • verifier 計算 t(s),然後計算 ((g^h(s))^δ)^t(s),並判斷 ((g^h(s))^δ)^t(s) = (g^p(s))^δ是否成立,若成立,則意味着 h(s) * t(s) = p(s);

  • 與此同時,verifier 還需要驗證 ((g^p(s))^δ)^α = (g^(α*p(s)))^δ是否成立,若成立,則證明 prover 給出的解是用 s 計算出來的。

如此一來,prover 也就完成了自己的攻防戰。

從交互變爲非交互

zk-SNARK 的 N 是指 Non-Interactive,即非交互,但不難發現在上述的證明過程中,是需要 verifier 和 prover 交互的,而且我們都知道,交互式證明本身是零知識證明得以成立的前提。那非交互是指什麼?

很簡單,所謂的非交互只不過是把 verifier 選擇隨機數的工作交給了「可信設置」來完成,也就是由一個可信任的第三方在證明開始前選擇隨機挑戰點 x。

這種改變對 prover 沒什麼影響,因爲他需要的始終是一組與 x 相關的加密值,而不用管這些加密值來自 verifier,還是來自可信第三方。但這種改變對 verifier 有影響,因爲他本來知道 x,可以用 x 計算 t(x),但現在他不知道了。

所以從交互到非交互,最主要的改變就是要在可信設置中把 t(x) 給到 verifier,以便他能完成驗證工作。

t(x) 需要被加密,因爲 prover 可以利用 t(x) 的值做弊;但加密後的 t(x) 又要能被用於計算,因爲 verifier 需要計算 h(x) * t(x)。這便是這一部分的難點所在:h(x) 和 t(x) 都是加密值,但之前使用的同態加密方法不支持兩個加密值的乘法。

zk-SNARK 使用配對操作解決這一問題,用公式表達就是 e(g^a, g^b)= a^g * b^g=(a * b)^g,其中 g^a 和 g^b 是加密值。配對操作可以把兩個加密值映射爲它們的乘積。

可信設置通過該方法把 t(x) 給到 verifier。於是,證明過程變爲如下 3 步:

  • 可信設置:可信第三方選擇隨機挑戰點 x,假設 x= s,以及隨機數α,然後把一整套 s 的加密值、以及一整套α * s 的加密值給 prover;再把 t(s) 的加密值 g^t(s) 和α 的加密值 g^α 給 verifier;

  • prover 收到後,計算 g^p(s)、g^h(s)、g^(α*p(s));選擇隨機數δ 對解加密,變爲 (g^p(s))^δ、(g^h(s))^δ、(g^(α*p(s)))^δ;然後把這 3 個加密值給 verifier;

  • verifier 計算並判斷 e(g^p, g) = e(g^t(s), g^h) 是否成立,若成立,則意味着 h(s) * t(s) = p(s);g^p、g^h、g^p′ 爲 prover 提供的 3 個加密值的簡寫。

  • 與此同時,verifier 還需要驗證 e(g^p′ , g) = e(g^p, g^α) 是否成立,若成立,則證明 prover 給出的解是用 s 計算出來的。

到這一步,我們就基本完成了 zk-SNARK 協議的構造工作,它可以在不泄露多項式係數的情況下證明多項式,即實現零知識證明。

額外一提,在可信設置階段爲 prover 和 verifier 準備的加密值被稱作 CRS (common reference string),用以生成 CRS 的隨機數是要被銷燬的,它們可用於作弊;可信設置需要可信第三方,通過什麼機制選擇可信第三方是一個議題。

可信設置影響 zk-SNARK 的通用性,因此也發展出了不需要可信設置的 zk-SNARK,其意義重大但理解起來並不難:只不過是換了一種方式提供隨機挑戰點 x。

不管有多少種 zk-SNARK,我們需要知道的是:零知識證明是一種交互式的證明系統,對它而言重要的、也是與安全和資源相關的一個工作就是,以什麼樣的方式提供隨機挑戰點。

把 p(x) 還原爲 A(x) * B(x)–C(x)

zk-SNARK 協議需要證明的多項式是 A(x) * B(x)–C(x),如果把 p(x) 還原爲 A(x) * B(x)–C(x),相較於 p(x) 時的協議,主要區別在於:

  • prover 需要分別提供 A(s)、B(s)、C(s) 的加密值;

  • verifier 需要驗證 A(s) * B(s) = h(s) * t(s)+ C(s);

  • 在對 prover 的計算進行約束時(比如必須用 s 計算),需要有 3 個不同的α 分別對應於 A(s)、B(s)、C(s);當 prover 對計算結果加密時,需要有 3 個不同的δ分別加密 A(s)、B(s)、C(s)。

在具體的 zk-SNARK 協議中,還會通過一些設計來改進協議,本文不再一一論述,zk-SNARK 的探祕之旅到這裏就全部結束啦。

在旅程結束之際,有幾點說明:

1.zk-SNARK 有不同的組合實現方法,本文主要是以 Pinocchio 協議爲線索;密碼學所涉甚廣,文章難免會有疏漏和理解不當之處,請不要盡信,深入研究需以論文爲參考。
2. 本文在構建 zk-SNARK 協議部分(第二部分)採用了 Maksym 文章的框架;Maksym 的文章極有條理地介紹了 zk-SNARK,但可能對於不太具備相關背景知識的讀者來說仍有一定的理解難度,這也是我寫這篇文章的原因所在。

那麼,如果你讀到了這裏,謝謝你;如果你在知曉零知識證明的整個實現過程後,被其中的數學之美打動,那我太開心了。

參考:

1. 東澤;

2. Vitalik Buterin;《Quadratic Arithmetic Programs: from Zero to Hero》,

3. Maksym Petkus;《Why and How zk-SNARK Works: Definitive Explanation》,https://arxiv.org/pdf/1906.07221.pdf

中文版本:,翻譯:even@ 安比實驗室,校對:valuka@ 安比實驗室

4. 李畫;