一文了解最熱門的 zkSNARK 方案：Groth16 方案
原文標題：一文了解最熱門zkSNARK方案：零知識證明引論（三）
在之前的文章中，我們介紹了零知識證明的 基礎概念 以及構造 zkSNARK 的 基本思想和方法。從本文開始，我們將逐一介紹目前最熱門的 zkSNARK 方案。文章旨在讓讀者理解這些方案的基本原理。為了方便敍述並容易理解，在敍述方案時，我們會做一些簡化處理，重在傳達方案的核心思想。
本文介紹的是 Groth16 方案。Groth16 方案，顧名思義，就是 Groth 在 2016 年發表的一篇論文 [Gro16] 中提出的方案。目前為止，Groth16 是在實踐中使用最廣泛的 zkSNARK (沒有之一)。特別一提的，Zcash 目前使用的 zkSNARK 方案就是 Groth16。從性能上，Groth16 的 Verifier 性能是所有 zkSNARK 中最快的，其證明字符串也是最短的。
而 Groth16 的最大缺點就是它需要對每個電路都執行一次可信初始化。
在介紹 Groth16 之前，簡單回顧一下 zkSNARK 所要解決的問題。我們稱這個問題為「計算驗證問題」。
任何計算都可以描述為一個算術電路。一個算術電路可以對數字進行算術運算。電路由加法門、乘法門以及一些常數門組成，如下圖所示：
這個例子中的電路包含了 15 個門。這個電路所描述的計算過程需要輸入五個數字 x1 到 x5，輸出四個數字。
給定一組輸入的數字，需要把這個電路中的每個門都計算一遍，才能計算出這個電路的輸出。在這個例子中，如果輸入是 (1,2,3,4,5) ，則電路的輸出為 (-27,14,80,171)，如下圖所示：
計算驗證問題是指，如果一個驗證者——不妨叫做 Verifier——只拿到了電路的一組輸入和輸出，如這個例子中的 (1,2,3,4,5) 和 (-27,14,80,171) ，它該如何驗證這是一對合法的輸入和輸出呢？最簡單粗暴的方法就是把這個輸入重新扔進電路算一遍。如果電路很大的話，這個驗證方法最大的缺點就是效率問題。
有些場景下，效率還不是唯一的問題。例如，輸入可能包含 Verifier 不能知道的秘密信息。假設上例中的 (3,4,5) 是秘密輸入，Verifier 只能看到 (1,2) ，如下圖所示。此時 Verifier 要驗證的問題就變成了「是否存在 (?,?,?) 使得電路在輸入 (1,2,?,?,?) 的時候的輸出是 (-27,14,80,171) 」。這個場景下，即使是簡單粗暴的重新計算也不再可行。
一句話概括計算驗證問題：Verifier 能否在不知道秘密輸入的情況下，高效地驗證計算結果？
一個 zkSNARK 就是對上述問題的一個解決方案。使用 zkSNARK，一個證明者，叫做 Prover，可以為計算過程生成一個簡短的證明字符串。Verifier 讀取這個字符串，就可以判斷給定的公開輸入和輸出是否合法。
Groth16 是眾多 zkSNARK 構造方案中的一種。接下來，我們介紹 Groth16 是怎麼解決計算驗證問題的。
首先，我們重新審視一下 Verifier 的任務：我們只知道電路的前兩個輸入是 (1,2)，我們的目標是要判斷是否存在一組合法的秘密輸入，使得電路的輸出是 (-27,14,80,171)。如果我們換個角度看這個問題，它其實可以描述為：給一個電路，上面有些空格可以填數字，有些空格已經填上了數字，請問是否存在一種填法，能夠同時滿足每個門的邏輯？
從這個新的角度，計算驗證問題被轉換成了一個類似於數獨那樣的填數字遊戲：有一些空格，一部分已經填上，請你填上另外一些空格，滿足一些限制條件。
然後，我們為每一個要滿足的條件列一個方程。這裏，每個要滿足的條件其實就是一個門的邏輯：加法門的輸出等於兩個輸入之和，乘法門的輸出等於兩個輸入之積。於是，原來的填空遊戲就變成了一個多元方程組。上述例子轉化得到的方程組如下：
最後，我們對這個方程做一些整理，使得它能夠寫成矩陣和向量的形式，更加整齊和簡潔。我們把每個方程都寫成 * = * x * 的模式。儘管並不是所有方程中都有乘法，但我們可以給沒有乘法的式子乘上一個 。於是方程組變成了下面這個樣子：
把所有方程合到一起，就得到了原方程組的矩陣表示
我們把最終得到的這個矩陣向量方程叫做一個Rank-1 Constraint System (R1CS)。
總結一下，這一節中我們把計算驗證問題轉化成了數學問題 R1CS。
在計算驗證問題中，Verifier 知道一個電路，拿到公開部分的輸入，以及電路的輸出，判斷它們是否合法。
在零知識證明領域，R1CS 基本上就是電路的代名詞。許多 zkSNARK 把 R1CS 問題作為目標問題。不過，大部分 zkSNARK 不會直接對 R1CS 下手，而是把 R1CS 問題繼續轉化，得到一個等價的多項式問題，再對這個多項式問題設計證明方案。Groth16 也不例外。不同的 zkSNARK 選擇的多項式問題各不相同，Groth16 選擇的是一個叫做Quadratic Arithmetic Programming (QAP)的問題。
這一節中介紹一下怎樣把 R1CS 問題轉化為等價的 QAP 問題。
然後，我們把這些列向量換成多項式，使得多項式方程和原先的向量方程等價。
把向量轉化成多項式的一種方式是使用多項式插值。
多項式插值
QAP 問題
現在，我們直接把 R1CS 矩陣中的列向量換成它們的多項式插值，得到的結果如下圖所示。
我們用一個表格總結一下上文中提到的所有問題。
為什麼要越搞越複雜，把電路問題轉化為 QAP 問題呢？一個簡單的回答：就是為了引入多項式！多項式是一個強大的工具。多項式的作用，可以理解為一個「槓桿」，或者叫「誤差放大器」。如果我們要檢查兩個長度為 10000 的向量是否相等，一定需要檢查 10000 次，哪怕檢查過了 9999 個點都是一樣的，也不能保證最後一點是相同的。而兩個 10000 次的多項式，哪怕非常接近，比如説它們的係數有 9999 個都相同，或者它們在 這些點上的取值都相等，但只要有一個點不同，這兩個多項式就截然不同。這意味着，如果在一個很大的範圍內，例如 到 當中均勻隨機選一個點，兩個不同的多項式在這個點上相等的機會只有 。檢查兩個多項式是否相等，比檢查同樣規模的向量要快得多，這幾乎是所有 zkSNARK 提高 Verifier 效率的根本原理。
QAP 問題就是 Groth16 要用來構造 zkSNARK 的最終問題了。不過，在解釋 Groth16 的構造細節之前，我們先準備一些工具。
準備工具
我們假設讀者對橢圓曲線羣的基本特性和應用有所瞭解，並採用加法羣的記號來描述橢圓曲線羣中的點和運算。橢圓曲線羣中的元素可以用來表示多項式，並限制 Prover 必須使用給定的多項式來進行線性組合。這正是 QAP 所需要用到的特性。
我們看一下橢圓曲線是怎麼用來表示多項式的。
KoE 假設
然而，上述直覺並不能從離散對數假設嚴格地證明而來。所以，只能把它作為一個新的安全性假設來用。這個假設就叫做 Knowledge-of-Exponent (KoE) 假設。
KoE 假設怎樣應用到 QAP 問題上呢？那就是，KoE 允許我們使用橢圓曲線點來表示多項式，並且迫使 Prover 只能從已知的多項式線性組合產生新的多項式。
不過，到目前為止，我們忽略了兩個關鍵問題：
關於第二個問題，一個解決方法就是雙線性配對。
雙線性配對
現在，我們已經準備好了工具：KoE 假設和雙線性配對。接下來，我們就介紹 Groth16 是如何為 QAP 問題構造 zkSNARK 的。
Groth16 方案
Setup
Prove
Verify
解析
我們簡單解釋一下上述構造為什麼能夠工作。至於它為什麼是安全的，請感興趣的讀者參閲 [Gro16] 原文。
當然，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