探究零知識證明歷久彌新創新湧現的真正原因

撰寫：LambdaClass

#編譯：mutourend；Yiping，IOSG Ventures

### ######1. 引言######零知識、簡潔、非互動知識證明（zk-SNARKs），是一種強大的密碼學原語，允許證明者說服驗證者某個陳述的正確性，而無需透露陳述以外的任何資訊。由於其在可驗證私人計算、電腦程式執行正確性證明和區塊鏈擴展方面的應用，zk-SNARKs 受到廣泛關注。我們相信，正如我們在文章中所描述的那樣，zk-SNARKs 將對塑造世界產生重大影響。 zk-SNARKs 涵蓋了不同類型的證明系統，使用不同的多項式承諾方案、算術化方案、互動式預言機證明或機率可檢驗證明。但這些基本想法和概念可追溯至 20 世紀 80 年代中期。 ######自從比特幣和以太坊推出以來，zk-SNARKs 的發展大大加速，因為它們能夠透過使用零知識證明（通常稱為此特定用例的有效性證明）來擴展。 zk-SNARKs 在區塊鏈可擴展性方面起著至關重要的作用。正如 Ben-Sasson 所述，近年來看到了加密證明的寒武紀爆發。每種證明系統都有優勢和劣勢，並且在設計時都考慮到了特定的權衡。硬體、演算法、新證明和工具的進步不斷提高效能，也催生了新系統的誕生。這些系統中許多已投入使用，我們不斷突破界限。我們是否會擁有適用於所有應用的通用證明系統，或者會有幾種適用於不同需求的系統？我們認為一個證明系統能夠統治所有其他系統的可能性很小，原因包括：#######1）應用的多樣性。 ######2）不同的限制類型（關於記憶體、驗證時長、證明時長）。 ######3）對魯棒性的需求（如果一個證明系統被破壞，還有其他證明系統）。 ######儘管證明系統可能發生重大變化，但它們仍然具有一個重要特性：證明的快速驗證性。在一個能夠驗證證明並輕鬆適應新證明系統的層面的情況下，解決了與更改基礎層（如以太坊）相關的困難。本文將簡要概述 SNARKs 的各種特徵。 ######1）密碼學假設：抗碰撞雜湊函數、橢圓曲線上的離散對數難題、knowledge of exponent。 ######2）透明 vs 可信任設定。 ###

3）證明長度：線性 vs 超線性。

4）驗證器時間：恆定時間、對數、次線性、線性。

5）proof size。

6）易於遞歸。

7）算術化方案。

8）單變數多項式 vs 多變數多項式。

本文將探討 SNARKs 的起源、一些基本建置模組以及不同證明系統的興起（和衰退）。本文無意對證明系統進行詳盡的分析。相反，只關注那些對我們有影響的人。當然，這些發展只有透過該領域先驅者的偉大工作和想法才有可能實現。

2. 基礎問題

零知識證明並不新鮮。定義、基礎、重要定理、甚至重要協議都是從 1980 年代中期開始製定的。用來建構現代 SNARKs 的一些關鍵思想和協議是在 20 世紀 90 年代提出的（sumcheck 協議），甚至是在比特幣出現之前（2007 年的 GKR）。使用它的主要問題與缺乏強大的用例（互聯網在 20 世紀 90 年代並不發達）以及所需的計算能力有關。

1）零知識證明：起源 (1985/1989)。

零知識證明領域隨著 Goldwasser、Micali 和 Rackoff 《The knowledge complexity of interactive proof systems》 論文出現在學術文獻中。有關起源的討論，可觀看 2023 年 1 月視頻 ZKP MOOC Lecture 1: Introduction and History of ZKP。論文引入了完倍性、可靠性和零知識性的概念，提供了 quadratic residuosity 和 quadratic non-residuosity 的構造。

2）Sumcheck 協定 (1992)。

sumcheck 協議由 Lund、Fortnow、Karloff 和 Nisan 於 1992 年 Algebraic Methods for Interactive Proof Systems 論文提出。它是簡潔互動式證明最重要的建置模組之一。它幫助我們將多變量多項式 evaluate 求和的要求減少到隨機選擇點的單一 evaluation。

3）Goldwasser-Kalai-Rothblum (GKR) (2007)。

GKR 協議（見論文 Delegating Computation: interactive Proofs for Muggles）是一種互動式協議，其證明者根據電路的閘數線性運行，而驗證者則根據電路的大小亞線性運行。在協議中，證明者和驗證者就 depth 為 d dd 的有限域的 fan-in-two 運算電路達成一致，其中 layer d dd 對應 input layer，layer 0 00 對應 output layer。該協議從有關電路輸出的聲明開始，該聲明被簡化為對前一層值的聲明。使用遞歸，可將其轉換為對電路輸入的聲明，從而可輕鬆檢查。這些 reductions 是透過 sumcheck 協議實現的。

4）KZG polynomial commitment scheme (2010)。

Kate、Zaverucha 和 Goldberg 在 2010 年 Constant-Size Commitments to Polynomials and Their Applications 引入了使用雙線性配對群的多項式承諾方案。承諾由單一群體元素組成，承諾者可有效地開啟對多項式的任何正確 evaluation 的承諾。此外，由於 batching 技術，可以對多個 evaluations 進行開啟。 KZG 承諾為幾個高效的 SNARKs 提供了基本構建模組之一，如 Pinocchio、Groth16 和 Plonk。它也是 EIP-4844 的核心。若要直觀地了解 batching 技術，可參考 Mina to Ethereum ZK bridge。

3. 使用橢圓曲線的實用 SNARKs

SNARKs 的第一個實用構造出現於 2013 年。這些構造需要預處理步驟來產生證明和驗證金鑰，並且是特定於程式 / 電路的。這些密鑰可能非常大，並且取決於各方不知道的秘密參數；否則，可偽造 proofs。將程式碼轉換為可證明的程式碼需要將程式碼編譯為多項式約束系統。起初，這必須以手動方式完成，既耗時又容易出錯。該領域的進步試圖消除一些主要問題：

1）擁有更有效率的證明者。

2）減少預處理量。

3）具有通用而不是電路特定的 setups。

4）避免採用可信任設定。

5）發展使用高階語言描述電路的方法，而不是手動編寫多項式約束。

目前，使用橢圓曲線的實用 SNARKs 方案有：

1）Pinocchio (2013)

2）Groth 16 (2016)

3）Bulletproofs & IPA (2016)

4）Sonic, Marlin, and Plonk (2019)

5）Lookups (2018/2020)

6） Spartan (2019)

7）HyperPlonk (2022)

8）Folding schemes (2008/2021)

3.1 Pinocchio (2013)

##3.1 Pinocchio (2013)

Pinocchio（見論文Pinocchio: Nearly Practical Verifiable Computation）是第一個實用、可用的zk-SNARK。 SNARK 基於二次算術程序 (quadratic arithmetic programs，QAP)。證明大小最初為 288 位元組。 Pinocchio 的工具鏈提供了從 C 程式碼到算術電路的編譯器，並進一步轉換為 QAP。該協定要求驗證者產生特定於電路的金鑰。它使用橢圓曲線配對來檢查方程式。證明產生和金鑰設定的 asymptotics 漸近與計算大小呈線性關係，驗證時長與公用輸入和輸出的大小呈線性關係。

3.2 Groth 16 (2016)

Groth 2016 年論文On the Size of Pairing-based Non-interactive Arguments 引入了一種新的知識論證，提高了由R1CS 描述問題的性能。它具有最小的證明大小（僅三個群元素）和涉及三個 pairings 的快速驗證。它還涉及獲取結構化 references 字串的預處理步驟。主要缺點是，待證明的每個程序都需要不同的可信設置，這很不方便。 Groth16 曾用於 ZCash。詳情也可參考部落格 An overview of the Groth 16 proof system。

3.3 Bulletproofs & IPA (2016)

KZG PCS 的弱點之一是它需要可信任設定。 Bootle 等人 2016 年 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting 論文中引入了滿足內積（inner product）關係的 Pedersen 承諾 openings 的有效零知識論證系統。內積證明系統有一個線性證明者，具有對數通信和交互，但具有線性時長驗證。其也發展了一種不需要可信任設定的多項式承諾方案。 Halo 2 和 Kimchi 都採用了採用 IPA PCS 想法。

3.4 Sonic, Marlin, and Plonk (2019)

Sonic、Plonk 和Marlin 透過引入通用且可更新的結構化reference 字串，解決了Groth16 中每個程序的可信任設定問題。 Marlin 提供了基於 R1CS 的證明系統，是 Aleo 的核心。 Plonk 引入了一種新的算術化方案（後來稱為 Plonkish），並對 copy constraints 使用 grand-product check。 Plonkish 還允許為某些操作引入專門的門，即所謂的定制門。多個專案都有 Plonk 的定製版本，包括 Aztec、ZK-Sync、Polygon ZKEVM、Mina’s Kimchi、Plonky2、Halo 2 和 Scroll 等。可參考部落格 All you wanted to know about Plonk。

3.5 Lookups (2018/2020)#########Gabizon 和Williamson 在2020 年引入了plookup，使用grand product check 來證明某個值包含在預先計算的值表中。儘管先前在 Arya 提出了 lookup arguments，但其構造需要確定 lookups 的 multiplicities，效率較低。 PlonkUp 論文展示如何將 plookup argument 引入 Plonk。這些 lookup arguments 的問題在於，它們迫使證明者為整個表支付費用，而與其查找次數無關。這意味著大型表的成本相當大，並且已投入了大量的精力來將證明者的成本降低到其使用的查找數量。 ###

Haböck 引入了 LogUp，它使用對數導數將乘積檢查轉換為倒數總和。 LogUp 對於 Polygon plonky2 ZKEVM（Beyond Limits: Pushing the Boundaries of ZK-EVM） 的效能至關重要，其需要將整個表拆分為多個 STARK 模組。這些模組必須正確鏈接，並跨表查找來強化此操作。 LogUp-GKR 的推出利用 GKR 協定來提升 LogUp 的效能。 Caulk 是第一個 prover time 與 table size 呈亞線性關係的 lookup argument，其預處理時長為‍O ( N log ⁡ N ) 且 storage 為 O ( N ) ，其中 N 為 table size。隨後出現了其他幾個方案，如 Baloo、flookup、cq 和 caulk 。 Lasso 提出了多項改進，避免在表具有給定結構時對其進行 commit。此外，Lasso 的證明者只為查找操作存取的表格條目付費。 Jolt 利用 Lasso 透過尋找來證明虛擬機器的執行情況。

3.6 Spartan (2019)

Spartan 為使用 R1CS 描述的電路提供了 IOP，利用多變量多項式和 sumcheck 協定的屬性。使用合適的多項式承諾方案，它會產生具有線性時長 prover 的透明 SNARK。

3.7 HyperPlonk (2022)

HyperPlonk 是基於使用多變量多項式的 Plonk 想法而建構。它不依賴商來檢查約束的執行情況，而是依賴 sumcheck 協定。它還支援 high degree 約束，而不會損害證明者的運行時間。由於它依賴多變量多項式，因此無需執行 FFT，且證明者的運行時間與電路尺寸呈線性關係。 HyperPlonk 引入了適合較小網域的新 permutation IOP 和基於 sumcheck 的 batch opening 協議，這減少了 prover 的工作量、證明大小和驗證者的時間。

3.8 Folding schemes (2008/2021)

Nova 引入了folding 方案的思想，這是一種實現增量可驗證計算（IVC）的新方法。 IVC 的概念可以追溯到 Valiant，其展示瞭如何將 2 個長度為 k kk 證明，合併為，一個長度為 k kk 的證明。其想法為，可透過遞歸證明，來證明由step i ii 到step i 1 i 1i 1 的執行是正確的，且驗證由step i − 1 i-1i−1 到step i ii 的過渡proof 是正確的，從而證明任何長時間運行的計算。

Nova 可以很好地處理 uniform computations；後來隨著 Supernova 的引入，擴展到處理不同類型的電路。 Nova 使用 R1CS 的寬鬆版本，並在友善的橢圓曲線上工作。使用友善的曲線 cycles（如，Pasta 曲線）來實現 IVC 也被用在 Pickles 中，Pickles 是 Mina 的主要基礎模組，以實現簡潔的狀態。然而，folding 的想法與遞歸 SNARK 驗證不同。累加器的想法與 batching proofs 的概念有更深入的連結。 Halo 引入了累加的概念作為遞歸證明組合的替代方案。 Protostar 為 Plonk 提供了 non-uniform IVC 方案，支援 high-degree gates 和 vector lookups。

4. 使用抗碰撞雜湊函數的 SNARKs

大約在 Pinocchio 開發的同時，出現了一些生成電路 / 算術方案的想法，可以證明虛擬機器執行的正確性。儘管開發虛擬機器的算術可能比為某些程式編寫專用電路更複雜或效率更低，但它提供了一個優點，即任何程序，無論多麼複雜，都可以透過證明它在虛擬機器中正確執行來證明。 TinyRAM 中的想法後來隨著 Cairo vm 和後續虛擬機器（如 zk-evms 或通用 zkvms）的設計而得到改進。使用抗碰撞雜湊函數消除了對可信設定或使用橢圓曲線運算的需要，但代價是更長的 proofs。

1）TinyRAM (2013)

在 SNARKs for C 中，開發了一個基於 PCP 的 SNARK，用於證明 C 程式執行的正確性，該程式被編譯為 TinyRAM（精簡指令集電腦）。該電腦採用哈佛架構，具有位元組級可尋址隨機存取記憶體。利用非確定性，電路的大小與計算大小呈擬線性 quasilinear 關係，從而有效地處理任意和資料相關的循環、控制流和記憶體存取。

2）STARKs (2018)

STARKs 是由 Ben Sasson 等人於 2018 年提出。其實現的 proof size 為 O(log2n)，且具有快速證明者和驗證者，不需要可信設置，並且被認為是後量子安全的。其首先由 Starkware/Starknet 與 Cairo 虛擬機器一起使用。其關鍵元件包括：

代數中間表示 (AIR)

和 FRI 協定（Fast Reed-Solomon Interactive Oracle Proof of Proximity）。

STARKs 也被其他項目（Polygon Miden、Risc0、Winterfell、Neptune）使用，或對其的一些改編（ZK-Sync 的 Boojum、Plonky2、Starky）。

3）Ligero (2017)

Ligero 引入了一個證明系統，其 proof size 為 O( 根號 n），其中 n 為 circuit size。它將多項式係數排列成矩陣形式並使用線性碼 linear codes。

Brakedown 建立在 Ligero 的基礎上，並引入了與域無關的多項式承諾方案的想法。

5. ZKP 的一些新進展

在生產中使用不同的證明系統顯示了每種方法的優點，並帶來了新的發展。如，plonkish 算術化提供了一種簡單的方法來包含自訂門和 lookup arguments；FRI 作為 PCS 表現出了出色的性能，領先於 Plonky。同樣，在 AIR 中使用 grand product check（導致帶有預處理的隨機化 AIR）提高了其性能並簡化了記憶體存取 arguments。基於哈希函數的承諾已經流行起來——基於硬體中哈希函數的速度或引入新的 SNARK 友好哈希函數。

1）新的多項式承諾方案（2023）

隨著基於多變量多項式的高效 SNARK（如 Spartan 或 HyperPlonk）的出現，人們對適合此類多項式的新承諾方案越來越感興趣。 Binius、Zeromorph 和 Basefold 都提出了新的形式來致力於多線性多項式。 Binius 具有零開銷來表示資料類型的優點（而許多證明系統使用至少 32 位元域元素來表示單一 bit）並在 binary 域上運作。 Binius 承諾基於 Brakedown，其設計目的是與域無關。 Basefold 將 FRI 推廣到 Reed-Solomon 以外的程式碼，從而形成與域無關的 PCS。

2）Customizable Constraint Systems（CCS） (2023)

CCS 概括了 R1CS，同時捕捉 R1CS、Plonkish 和 AIR 算術，無需任何開銷。將 CCS 與 Spartan IOP 結合使用會產生 SuperSpartan，它支援 high-degree 約束，而無需證明者承擔隨約束 degree 而擴展的加密成本。特別是，SuperSpartan 為帶有線性時間 prover 的 AIR 產生 SNARK。

6. 結論

本文描述了 SNARK 自 20 世紀 80 年代中期推出以來的進步。電腦科學、數學和硬體的進步，加上區塊鏈的引入，催生了新的、更有效率的 SNARK，為許多可以改變我們社會的應用程式打開了大門。研究人員和工程師根據自己的需求提出了對 SNARKs 的改進和調整，重點關注證明大小、記憶體使用、透明設定、後量子安全、證明者時間和驗證者時間。

雖然最初有兩條主線（SNARK 與 STARK），但兩者之間的界限已經開始淡化，試圖結合不同證明系統的優點。如，將不同的算術方案與新的多項式承諾方案結合。可預期，新的證明系統將繼續興起，性能也隨之提高，而對於一些需要一些時間適應的系統來說，將很難跟上這些發展，除非可輕鬆地使用這些工具，而無需更改一些核心基礎設施。

以上是探究零知識證明歷久彌新創新湧現的真正原因的詳細內容。更多資訊請關注PHP中文網其他相關文章！