作者：LambdaClass
翻譯：mutourend；Yiping，IOSG Ventures
1. 引言
零知識、簡潔、非互動知識證明（zk-SNARKs），是一種強大的密碼學原語，允許證明者說服驗證者某個陳述的正確性，而無需透露陳述以外的任何資訊。由於其在可驗證私人計算、電腦程式執行正確性證明和區塊鏈擴展方面的應用，zk-SNARKs受到廣泛關注。我們相信，正如我們在文章中所描述的那樣，zk-SNARKs將對塑造世界產生重大影響。 zk-SNARKs涵蓋了不同類型的證明系統，使用不同的多項式承諾方案、算術化方案、互動式預言機證明或機率可檢驗證明。但這些基本思想和概念可追溯至1980年代中期。自從比特幣和以太坊推出以來，zk-SNARKs的發展大大加速，因為它們能夠透過使用零知識證明（通常被稱為此特定用例的有效性證明）進行擴展。 zk-SNARKs在區塊鏈可擴展性方面起著至關重要的作用。正如Ben-Sasson所述，近年來看到了加密證明的寒武紀爆發。每種證明系統都有優勢和劣勢，並且在設計時都考慮到了特定的權衡。硬體、演算法、新證明和工具的進步不斷提高效能，也催生了新系統的誕生。這些系統中許多已投入使用，我們不斷突破界限。我們是否會擁有適用於所有應用的通用證明系統，或者會有幾種適用於不同需求的系統？我們認為一個證明系統能夠統治所有其他系統的可能性很小，原因包括：
1）應用的多樣性。
2）不同的限制類型（關於記憶體、驗證時長、證明時長）。
3）對魯棒性的需求（如果一個證明系統被破壞，還有其他證明系統）。
即使證明系統發生了很大變化，它們都提供了一個重要的特性：證明可快速驗證。擁有一個驗證證明並且可以輕鬆適應新證明系統的layer，解決了與更改base layer（如以太坊）相關的困難。本文將概述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)
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），但兩者之間的界限已經開始淡化，試圖結合不同證明系統的優點。如，將不同的算術方案與新的多項式承諾方案結合。可預期，新的證明系統將繼續興起，性能也隨之提高，而對於一些需要一些時間適應的系統來說，將很難跟上這些發展，除非可輕鬆地使用這些工具，而無需更改一些核心基礎設施。
