從頭複習 zk-SNARK (Groth16)

聲明：想瞭解 zk-SNARK 的話，推薦大家去閱讀《读懂区块链之零知识证明（zk-SNARK）》，裡面先解釋了 ZKP 的基本特性，然後帶到 ZCash 上面的應用，最後花很多篇幅講解 zk-SNARK 的數學原理與技術細節，由淺入深、生動又細緻。這篇只是作為個人筆記，給已經瞭解過原理的人複習用的，不會講解複雜的細節，且圖片都是從該篇文章複製過來。

在原文裡的名詞有點混用。嚴格來說，zk-SNARK 指的是「零知識簡潔非交互式知識論證」(Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) 這一類技術，實作則有 Groth16、Plonk、Marlin 等等。作者講解的都是 Groth16 的原理，但由於當時 (2018年) zk-SNARK 幾乎沒有其他實作，所以才會把 Groth16 跟 zk-SNARK 混用。

首先要知道，Grth16 只處理特定形式的計算問題，即 QAP (Quadratic Arithmetic Programs)。所以一般的計算會需要先經過轉換才能交給 Groth16 處理。轉換過程相當複雜，為了教學目的通常會找一個簡單的數學式示範，比如作者使用x**3 + x + 5 = 35：

中間的轉換作者稱為 L1CS，但我自己在學的時候看到的都是 R1CS (Rank-1 Constraint System)，概念差不多。

圖中的向量解 s = [~one, x, ~out, sym_1, sym_2, sym_3] 由常數、Public Inputs 和 Witness / Private Inputs 組成。.則是內積的意思 (兩個相量相乘以後結果累加)。

完成以上轉換以後，底下就可以進入 Groth16。Prover (Anna) 可以透過以下方式向 Verfiier (Carl) 證明自己知道 s，且不洩露具體 s：

• P(n) = s.C(n) - s.A(n) * s.B(n)
• H(n) = P(n)/Z(n)

但對實際應用而言，多項式的 degree 很大，這樣做會導致每次驗證都需要傳輸大量資料。所以改用取樣的方式，先求單點的值以後再去作比較：

雖然如果 Prover 用假的 witness s' 也可能計算出 P’(n) 使得 P’(n) = H(n)Z(n) 成立，但機率極小可忽略。

系統設計到目前有兩個顯而易見的漏洞：

1. Prover 可以偽造證明：使用假 witness s’ 建構多項式 P'(n)，並構造一個H'(n)使得至少在抽樣點 t 上 H’(t) = P’(t)/Z(t)。
2. Verifer 無法識別不同的證明：Prover 雖然不知道 s.C(n) - s.A(n) * s.B(n) = P(n) = H(n) * Z(n)中的解 s，但知道 s'.C'(n) - s'.A'(n) * s'.B'(n) = P'(n) = H'(n) * Z(n)中的解 s’，如果丟 P'(n)與H’(n)給 Verifier 一樣會通過。

漏洞 1. 可以用「同態加法」解決。假設我們可以找到一種映射E，使得我們可以直接從E(x), E(y)算出E(x+y) = E(x) + E(y)，那就可以將流程轉換如下：

• N 是一個比任何涉及多項式的 degree 都大的整數
• Prover 不知道 t， 如果他不知道真正的解 s，雖然仍然能用假的解 s’構造出 P'(n)，但無法透過偽造H'(t)使得 P’(t)通過驗證 如果他知道真正的解 s，則仍然可以透過同態加法計算E(P(t))和E(H(t))
• Verifier 知道 t，可以算出 Z(t) = ⍺，進而判斷E(P(t)) = E(⍺H(t))是否成立

漏洞 2. 中，我們想要避免 Prover 所給的 P(n)是來自 A’(n), B’(n), C’(n) 而非 A(n), B(n), C(n)。既然如此，Verifier 只提供 A(t), B(t), C(t)，使得 Prover 只能基於這三個點來構建回答。

這裡需要使用 “Knowledge of Coefficient Test and Assumption” (KCA) 來強迫 Prover 做到這件事。KCA 主要解決一個問題：如何確保證明者送出的數據，是透過對已知數據進行「線性組合」得到的，而不是憑空捏造的？

細節可以看原文，總之我們會需要引入一些隨機數、產生多項式 pairs、並加入對於 pairs 的驗證：

• 此處的 A(n), B(n), C(n) 其實是前面的 s.A(n), s.B(n), s.C(n)
• 引入L(n) = A(n) + B(n) + C(n) 是為了檢驗 A(t)、B(t)、C(t)都對應到相同的係數，即解向量 s 如果L(t)、A(t)、B(t)、C(t)都對應到s，Prover 就可以用 Verifier 給的E(βLi(t))與s算出正確的E(βL(t))並通過以下檢驗：E(βL(t)) = βE(A(t) + B(t) + C(t)) = β*E(A(t)) + E(B(t)) + E(C(t)) 但如果係數不同，則根據 KCA，Prover 在無法在β未知情況下算出能通過檢驗的 E(βL(t))

目前做法仍有兩個漏洞：

1. 不夠簡潔
2. 綠色部份：如何用 E(A(t))、E(B(t))和E(C(t))求E(C(t)-A(t)*B(t))？

為了做到簡潔，可以通過 Trusted Setup 將 Verifier 發給 Prover 的那一大串資料變成 CRS (Common Reference String)：

但這樣⍺,β對於 Verifier 而言也變成未知了，這使得以上綠色部份目前都無法計算。

為了完成綠色部份的計算，我們需要利用「同態乘法」。而想要找到滿足「同態乘法」的映射E，就需要先找到滿足同態加法的映射E1, E2以及 bilinear map e，使得E(xy) = e(E1(x), E2(y))。當我們找到了這樣的映射，就可以根據下圖完成整個 Groth16 流程：

以下幾點是這張圖與前一張圖的主要區別：

• CRS 包含了兩種同態加法E1和E2，並新增幾個α, β的映射值，會在後續驗證過程中用到。
• Verifier 的驗證方式有所調整，其中e是 bilinear map

換句話說，想要讓整套流程成立，就需要滿足上述的各種假設，比如同態加法、KCA、同態乘法… 那這些假設可以被滿足嗎？

答案當然是可以的，橢圓曲線就提供了以上條件：

• 定義了安全的加法群結構來實現同態加法
• 特定的「配對友好」曲線內建 bilinear map

細節這邊就不多提了，可以參考原文，底下也附上 Vitalik 本人關於 zk-SANRK 的講解：

• Part 1: Quadratic Arithmetic Programs: from Zero to Hero
• Part 2: Exploring Elliptic Curve Pairings
• Part 3: Zk-SNARKs: Under the Hood

恭喜你學完一大長串這輩子可能沒什麼機會派上用場的知識，keep going!