zk-SNARK的構建及案例

TL;DR

• SNARK 的構建流程是什麼樣的？

  待證明的問題-算術電路-R1CS-多項式

• 為什麼最終要轉換成多項式？

  因為多項式的特性有效的縮短了驗證時間，實現了簡潔性。

• 是如何實現零知識的？

  簡單來說，就是在推導多項式的過程中，多選取兩個隨機數，以此推導出的多項式能讓驗證者無法從中獲取原多項式的係數，即證明者的秘密輸入，以此實現ZK。

• 怎麼實現非交互？

  在證明開始前，引入了一個第三方，即可信設置，將原本驗證者挑選隨機數的任務交給了可信設置，從而實現驗證者和證明者之間的非交互。

ZK 技術近兩年在Web3 領域備受關注。從Rollup 開始，越來越多不同賽道的項目都開始嘗試使用ZK 技術。在這之中，SNARK 和STARK 是大家最常聽到的兩個名詞，為了後期更好地理解ZK技術的應用，本文將從非技術的角度簡化闡述SNARK 的證明邏輯，然後會以 Scroll 的zk Rollup 為例來說明zk 證明系統的運行。

文章旨在闡述基本邏輯，便於閱讀，會盡量避免術語使用，且不會深入探討數學轉換等細節，如有疏漏，敬請諒解。

2012年1月，加州大學伯克利分校教授Alessandro Chiesa 與人合作撰寫了SNARK 的論文，提出了術語zk-SNARK。

zk-SNARK，全稱Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge，是使用了ZK技術的一種證明系統。需要注意的是，SNARK 是一類方案的名稱，有很多不同的組合方法都可以實現SNARK。

• 零知識（Zero-Knowledge）：只有證明者知道的內容將會被隱藏，除了證明者，其他任何人都無法看到。

• 簡短（Succinct）：生成的證明小，驗證時間快。

• 非交互性（Non-Interactive）：證明者和驗證者之間交互很少，甚至沒有。

• 論證（Argument）：驗證者的驗證只對計算能力受限的證明者有效，因為擁有超強計算能力的證明者可以偽造證明，也就是說，系統具備計算可靠性。

• 知識（Knowledge）：證明者只有知道一些驗證者不知道的信息才能計算出證明。

zk-SNARK 要解決的是“計算驗證問題”，即驗證者能否在不知道證明者隱私的情況下，高效地驗證計算結果。

下面將以zk-SNARK 的簡化版構建流程來說明該系統是如何結合零知識達到高效驗證的。

zk-SNARK 的構建

將待證明問題轉化為多項式

簡單來說，SNARK 的思路是將證明陳述是否成立轉換成證明多項式等式是否成立。

整個轉換過程：待求證的問題➡算術電路➡R1CS➡多項式➡多項式之間的轉換

待求證的問題➡算術電路

要通過計算證明一個問題是否為真，首先就要將待證明的問題轉化成一個計算問題，而任何計算都可以描述為一個算術電路。

算術電路通常由常數、“加法門”、“乘法門”組成，通過門的疊加，我們可以構建出複雜的多項式。

上圖中的算術電路構建的多項式為：（Inp1+Inp2）*（-1）= Output

現實中的問題要轉為算術電路極其複雜，我們可以將之簡單理解為：輸入一些內容，內容經過電路轉化，最終輸出一個結果。即：

基於算術電路的概念，我們構造一個用於生成證明的算術電路，即：

該電路中包含了兩組輸入，公開輸入x 和秘密輸入w。公開輸入x意味該內容是待證明問題的固定值，驗證者和證明者都知曉，秘密輸入w 則意味著該內容只有證明者知曉。

我們構建的算術電路為C( x, w ) = 0，即通過電路輸入x與w，最終的輸出結果為0。證明者和驗證者知道電路輸出為0，且公有輸入為x的情況下，證明者需要證明自己知道秘密輸入w。

算術電路➡R1CS

我們最終需要一個多項式，但算術電路不能直接轉化為多項式，需要R1CS 作為二者間的媒介，故先將算術電路轉換為R1CS。

R1CS，全名為Rank-1 Constraints System（一階約束系統），是一種描述電路的語言，本質上是一種矩陣向量方程。具體來說，R1CS 是由三個向量(a,b,c) 組成的序列，R1CS 的解是一個向量s，其中s 必須滿足方程：

其中. 代表內積運算。

此間具體的數學轉換可以參見Vatalik：Quadratic Arithmetic Programs: from Zero to Hero

我們只需要知道，R1CS 的作用是對算術電路中的每個門的描述進行限定，使得每個門之間的向量滿足以上關係。

R1CS➡多項式

在得到R1CS 這個媒介後，我們就可以將其等價轉換成多項式。

矩陣和多項式之間可以進行如下圖所示的等價轉換：

多項式

轉化為矩陣

根據上述等價轉換的性質，對於滿足R1CS 的矩陣，我們可以使用拉格朗日插值法，還原出多項式每一項係數，基於這個關係，我們可以將R1CS 矩陣推導為多項式關係，即：

注：A, B, C分別代表一個多項式

一個多項式對應我們想要證明的問題所對應的一個R1CS矩陣約束，通過以上轉化，我們可以知道，多項式之間滿足以上關係，就說明我們的R1CS矩陣是正確的，從而說明證明者在算術電路中的秘密輸入也是正確的。

到這我們的問題就簡化為：驗證者隨機挑選一個數x，讓證明者證明A(x) * B(x)=C(x) 成立，如果成立，說明證明者的秘密輸入正確。

多項式之間的轉換

複雜的算術電路中，有成千上萬個門，我們需要對每個門驗證其是否滿足R1CS約束。換句話說，我們需要驗證數次A(x) * B(x)=C(x) 等式成立，但是逐次單獨驗證的效率太低，如何能做到一次性驗證所有門的約束的正確性？

為了方便理解，我們引入一個P(x)，令P(x) = A(x) * B(x) – C(x)

我們知道，任意的一個多項式只要它有解，就可以將它分解成線性多項式。故我們將P(x) 拆分為F(x) 和H(x)，即：

然後將F(x) 公開，這就意味著存在一個H(x) = P(x)/F(x) ，從而我們要驗證的多項式最終轉變為：

A(x) * B(x) – C(x)：包含多項式的係數，只有證明者知，即秘密輸入。

F(x) ：一個公開的多項式，驗證者和證明者皆知，即公開輸入。

H(x) ：證明者通過計算得知，驗證者不可知。

而最終要證明的問題為：多項式等式A(x) * B(x) – C(x) = F(x) * H(x)，在所有x上都成立。

現在只需要驗證一次多項式就可以驗證所有約束是否滿足矩陣關係。

到這裡我們就完成了將待證明的問題轉化成只需要驗證一次的多項式，實現了系統的簡潔性。

但是這個實現的簡潔性是讓驗證者的驗證時間縮短，那證明大小呢？

簡單來說，在證明協議中，使用的是Merkle 樹的結構，這有效的降低了證明的大小。

整個轉換過程完成以後，自然而然的會產生兩個問題：

• 為什麼要轉換成多項式？

  因為多項式實現了證明的簡潔性。零知識證明的問題就是驗證計算滿足多個約束的問題，而多項式可以一個點驗證多個約束。換句話說，驗證者本來要驗證n 次才能確認的問題，現在只需要驗證一次就能極大概率地確認證明的正確性。

• 為什麼驗證多項式上的一個點，就能確定兩個多項式A(x) * B(x) – C(x )= F(x) * H(x) 成立？

  這是由多項式的特性決定的，即：一個多項式在任意點的計算結果都可以看做是其唯一身份的表示。對於兩個多項式，它們只會在有限的點上相交。

對於上述的兩個d 階多項式：A(x) * B(x) – C(x) 和F(x) * H(x)，如果它們不相等，它們最多只會在d 個點上相交，也就是在d 個點上的解相同。

完成了多項式的轉換，我們就要進入多項式證明階段。

證明多項式成立

為了便於闡述，我們採用多項式P(x) = F(x) * H(x)。

現在，證明者要證明的問題是：在所有x 上，P(x) = F(x) * H(x)。

證明者和驗證者對以上多項式的驗證過程如下：

• 驗證者選擇隨機挑戰點x，假設x = s；

• 證明者收到s 後，計算P(s) 和H(s)，並把這兩個值給驗證者；

• 驗證者先計算F(s)，再計算F(s) * H(s)，並判斷F(s) * H(s) = P(s) 是否成立，若成立則驗證通過。

但是我們仔細思考就會發現以上流程存在一些問題：

• 證明者能夠知道整個等式的信息，如果收到隨機點s，他能計算出F(s)，然後構造出一對假的P(x) 和H(x)，使得P(s) = F(s) * H(s) ，以此欺騙驗證者。

• 證明者不使用驗證者給出的s 計算F(s) 和H(s)，而是用其他值計算，以此欺騙驗證者。

• 驗證者收到的值是由公共輸入和證明者的隱私輸入一起計算出來的，如果驗證者算力極大，可以破解證明者的隱私輸入。

針對上述問題，我們進行以下優化：

• 驗證者在選取了隨機點s 後，對s 進行同態加密，同態加密意味著加密後計算的解=計算後加密的解；在這種加密形式下，證明者能夠計算出解，但不能構造假的P(x) 和H(x)。

• 在驗證者選擇挑戰點s 時，再選取一個隨機參數λ，額外生成一個s 和λ 之間的線性關係。驗證者把同態加密後的 s 和λ 都發給證明者。待證明者將證明發回，驗證者除了驗證證明是否為真，還需要驗證隨機參數λ 與s 之間的關係。

• 針對驗證者可破解秘密輸入的問題，我們就可以引入ZK。縱覽整個證明，我們可以發現在驗證過程中，證明者發給驗證者的只有計算出的多項式的值，驗證者可以通過值倒推出多項式的係數，即證明者的秘密輸入。為了防止驗證者倒推，我們可以從R1CS 推出多項式A、B、C 的時候，多選取兩個隨機數並增加一組取值，這樣還原出來的多項式比原來的多項式多1階，從而讓驗證者無法從加密後的多項式中獲取原多項式的信息，以此實現ZK。

優化以後我們發現證明系統依舊需要驗證者和證明者之間進行交互，如何才能實現非交互？

實現非交互

為了實現非交互，SNARK 引入了可信設置（Setup）。

換句話說，在證明開始前，將原本屬於驗證者的選擇隨機挑戰點的權力交給一個可信的第三方，第三方選擇了隨機參數λ 後，將加密後的λ 放在R1CS 電路中，以此生成CRS（Common Reference String，公共參考字串）。驗證方能從CRS 中獲取屬於自己的Sv，證明方能從CRS 中獲取屬於自己的Sp。

需要注意的是，λ 在生成Sv 和Sp 後，需要被銷毀，若λ 被洩露，可能被用來通過虛假驗證偽造交易。

zk-SNARK 工作流程

在明白SNARK 的構建流程後，基於我們構造的可生成證明的算術電路，zk-SNARK 的證明流程如下：

• Setup:(C circuit, λ)= (Sv, Sp)

  通過電路C 和隨機參數λ ，生成後續證明者和驗證者使用的隨機參數Sv、Sp。

• Prove(Sp,x,w) = Π

  證明者通過隨機參數Sp，公共輸入x，秘密輸入w，計算出證明Π。

• Verify(Sv,x,Π) == (∃ w st C(x,w))

  驗證者通過隨機參數Sv，公共輸入x 和證明Π 來驗證是否存在C（x,w）=0。同時，驗證證明是否是通過電路C 計算得出。

到此，我們就完成了整個zk-SNARK 的講解，下面來看看實際運用的案例。

案例：以Scroll 的zk Rollup 為例

證明系統的作用是讓證明者說服驗證者相信一件事；

對於zk 證明系統而言，是要讓驗證者相信由zk 算法計算出的Zero-Knowledge Proof（零知識證明）為真。

我們以Scroll 的zk Rollup 為例來說明zk 證明系統的運行。

Rollup 是指鏈下計算，鏈上驗證。對zk Rollup 而言，交易在鏈下執行後，證明者需要對交易執行後產生的新的狀態根生成zk 證明，再將證明傳到L1 Rollup 合約進行鏈上驗證。

需要注意的是，在zk Rollup 中存在兩類區塊：

• L1 Rollup 區塊：提交到以太坊的區塊

• L2 區塊：用戶在L2 上提交的交易打包而成的區塊

以下是Scroll 的zk Rollup 的工作流程：

• 用戶在L2 發起交易，Sequencer 檢索到交易，在鏈下執行交易並生成L2 區塊和新的狀態根；同時將交易數據和新的狀態根提交給以太坊上的Rollup 合約（提交交易數據是為了實現數據可用性）；

• 當L2區塊生成時，Coordinator 會從Sequencer 那收到該區塊的執行軌跡，然後將該軌跡隨機分配給任意一個Roller；

• Roller 將接收到的執行軌跡轉換為電路，且為每個電路生成有效性證明，然後將該證明發回給Coordinator；

• 每生成k 個L2塊，Coordinator 就會發送一個聚合任務給另一個Roller，以將k 個塊的證明聚合為單個聚合證明；

• Coordinator 將單個聚合證明提交給Rollup 合約，Rollup 合約結合之前提交的狀態根和交易數據一起驗證聚合證明，驗證通過則相應的區塊就被視為在Scroll 上最終確定。

從以上流程可以看到，Roller 是該系統中的證明者，Rollup 合約是驗證者。 Roller 對在鏈下執行的交易生成一個zk 證明；Rollup 合約驗證該證明，若驗證通過，Rollup 合約就會直接採納提交的狀態根作為自己新狀態根。