zk-SNARK的構建及案例_ROL

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）：證明者和驗證者之間交互很少，甚至沒有。

Opside已在測試網上線ZK-Rollup LaunchBase:8月14日消息，去中心化ZK-RaaS平臺Opside已在測試網上線ZK-Rollup LaunchBase，支持開發者構建專用應用程序Rollup，包括Layer1、zkEVM、Gas、Data Availability與Sequencer各個組件。LaunchBase現允許開發者從Opside、Goerli、Mumbai與BNB測試網等EVM兼容的Layer1中選擇以構建其應用程序的特定rollup，支持Polygon zkEVM、zkSync、Scroll與Starknet四個zkEVM。[2023/8/14 16:24:39]

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

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

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

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

zk-SNARK 的構建

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

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

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

待求證的問題?算術電路

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

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

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

ZK-RaaS網絡Opside將于8月份集成ZK Stack:6月28日消息，Opside官方表示，將大力支持zkEVM的推廣，其中包括zkSync最新公布的ZK Stack。目前，Opside測試網已集成Polygon zkEVM（Hermez），用戶可以一鍵在ETH、BSC和Polygon等L1公鏈上發行一條屬于自己的zkEVM鏈。

據路線圖顯示，Opside測試網預計在8月份集成zkSync的ZK Stack。未來還將提供Scroll、Linea等zkEVM解決方案。Opside的多鏈ZK-PoW算法將為各個公鏈上的ZK-Rollup提供海量算力支撐。

Opside是一個提供ZK-RaaS（ZK-Rollup as a service）的平臺，支持用戶一鍵發布zkEVM。同時支持ZKP挖礦，包括CPU、顯卡、FPGA等機器類型。[2023/6/28 22:05:47]

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

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

該電路中包含了兩組輸入，公開輸入 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 必須滿足方程：

幣安升級資產儲備證明系統，部署zk-SNARKs:2月10日消息，幣安宣布將在其資產儲備證明系統（PoR）中部署零知識證明驗證方法zk-SNARKs，提升敏感信息的隱私性和安全性，除升級之外，該系統還新增支持四個代幣：SHIB、DOT、CHZ、SOL。未來幾周，幣安將在資產儲備證明系統（PoR）逐步支持更多代幣資產。[2023/2/10 11:59:22]

其中 . 代表內積運算。

此間具體的數學轉換可以參見 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) 成立，如果成立，說明證明者的秘密輸入正確。

Suterusu CTO：Suterusu在ZK-ConSNARK上的突破性進展將為DeFi生態提供隱私保護:12月21日晚，在由Gate.io主辦的直播專訪節目《酒局幣赴》中，Suterusu CTO林煌介紹，Suterusu項目在ZK-ConSNARK上取得了新的突破性進展，他與國際頂尖密碼學專家合著并提交了一篇范圍證明方案的學術論文，該設計基于有界整數承諾來設計透明設置的范圍證明方案。此外，Suterusu的協議和Suter Shield開發上都有新發展，這兩個項目的開發都已初步完成。Suterusu還實現了和波場（Tron）網絡嫁接的Suter Bridge，這意味著Suterusu針對智能合約平臺的隱私交易功能可以同時轉移到波場網絡上。另外，Suterusu在方案設計方面也考慮了反洗錢等要求，采用了一些比較先進的技術如recursive blacklist等。林煌表示，Suterusu的產品進展已經初步實現了Suterusu作為DeFi協議隱私插槽的階段性目標，將為整個DeFi生態提供隱私保護。[2020/12/22 16:01:50]

多項式之間的轉換

復雜的算術電路中，有成千上萬個門，我們需要對每個門驗證其是否滿足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) ，從而我們要驗證的多項式最終轉變為 ：

以太坊側鏈SKALE CTO：zk-STARKs技術還不足以實現規模化:6月10日消息，以太坊側鏈平臺SKALE Network首席技術官Konstantin Kladko在接受采訪時表示，以太坊Layer 2擴容方案zkRollup的基礎技術，即零知識技術zk-STARKs還不足以實現規模化。他稱，SKALE對zk-STARKs做了很多研究，并得出的結論，zk-STARKs是一項很有前途的基礎技術，但可能需要5年時間才能成熟。從這個意義上說，它的發展速度很慢。（Cointelegraph）[2020/6/10]

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 s.t. 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 合約就會直接采納提交的狀態根作為自己新狀態根。

金色早8點

Odaily星球日報

金色財經

Block unicorn

DAOrayaki

曼昆區塊鏈法律

Tags：ROLROLLARKNARTROLLER價格TROLLBNB幣MARKETING價格NAR價格

SOL