作者：LambdaClass
翻譯：mutourend；Yiping，IOSG Ventures
零知識、簡潔、非互動式知識證明（zk-SNARKs） ，是一種強大的密碼學原語，允許證明者說服驗證者某個陳述的正確性，而無需透露陳述以外的任何資訊。由於其在可驗證私人計算、電腦程式執行正確性證明和區塊鏈擴展方面的應用，zk-SNARKs受到廣泛關注。我們相信，正如我們在文章中所描述的那樣，zk-SNARKs將對塑造世界產生重大影響。 zk-SNARKs涵蓋了不同類型的證明系統，使用不同的多項式承諾方案、算術化方案、互動式預言機證明或機率可檢驗證明。但這些基本思想和概念可追溯至1980年代中期。自從比特幣和以太坊推出以來，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 的起源、一些基本建置模組以及不同證明系統的興起（和衰退）。本文無意對證明系統進行詳盡的分析。相反，只關注那些對我們有影響的人。當然，這些發展只有透過該領域先驅者的偉大工作和想法才有可能實現。
零知識證明並不新鮮。定義、基礎、重要定理、甚至重要協議都是從 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。
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 透過尋找來證明虛擬機器的執行情況。
Spartan為使用 R1CS 描述的電路提供了 IOP，利用多變量多項式和sumcheck協定的屬性。使用合適的多項式承諾方案，它會產生具有線性時長prover的透明 SNARK。
HyperPlonk是基於使用多變量多項式的 Plonk 想法而建構。它不依賴商來檢查約束的執行情況，而是依賴sumcheck協定。它還支援high degree約束，而不會損害證明者的運行時間。由於它依賴多變量多項式，因此無需執行 FFT，且證明者的運行時間與電路尺寸呈線性關係。 HyperPlonk 引入了適合較小網域的新permutation IOP 和基於sumcheck的batch opening協議，這減少了prover的工作量、證明大小和驗證者的時間。
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。
大約在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 的基礎上，並引入了與領域無關的多項式承諾方案的想法。
在生產中使用不同的證明系統顯示了每種方法的優點，並帶來了新的發展。如，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。
本文描述了 SNARK 自 20 世紀 80 年代中期推出以來的進步。電腦科學、數學和硬體的進步，加上區塊鏈的引入，催生了新的、更有效率的 SNARK，為許多可以改變我們社會的應用程式打開了大門。研究人員和工程師根據自己的需求提出了對 SNARKs 的改進和調整，重點關注證明大小、記憶體使用、透明設定、後量子安全、證明者時間和驗證者時間。
雖然最初有兩條主線（SNARK 與 STARK），但兩者之間的界限已經開始淡化，試圖結合不同證明系統的優點。如，將不同的算術方案與新的多項式承諾方案結合。可預期，新的證明系統將繼續興起，性能也隨之提高，而對於一些需要一些時間適應的系統來說，將很難跟上這些發展，除非可輕鬆地使用這些工具，而無需更改一些核心基礎設施。
以上是IOSG：零知識證明不斷創新的動力是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
