本文描述了 SNARK 自 20 世紀 80 年代中期推出以來的進步，探討零知識證明如何不斷創新？源自作者 LambdaClass 所著文章，由 IOSG Ventures 翻譯，PANews 整理及撰稿。
（前情提要： 零知識證明是什麼？一文探討 ZK 程式語言）
（背景補充： 科普｜zk-SNARKs是什麼？V神定調零知識證明未來十年「非常重要」）
零知識、簡潔、非互動式知識證明（zk-SNARKs），是一種強大的密碼學原語，允許證明者說服驗證者某個陳述的正確性，而無需透露陳述以外的任何資訊。
由於其在可驗證私人計算、電腦程式執行正確性證明和區塊鏈擴展套件方面的應用，zk-SNARKs 受到廣泛關注。我們相信，正如我們在文章中描述的那樣，zk-SNARKs 將對塑造世界產生重大影響。
zk-SNARKs 涵蓋了不同型別的證明系統，使用不同的多項式承諾方案、算術化方案、互動式預言機證明或概率可檢驗證明。但這些基本思想和概念可追溯至 20 世紀 80 年代中期。
自比特幣和以太坊推出以來，zk-SNARKs 的發展大大加速，因為它們能夠通過使用零知識證明（通常被稱為此特定用例的有效性證明）進行擴展套件。zk-SNARKs 在區塊鏈可擴展套件性方面起著至關重要的作用。
正如 Ben-Sasson 所述，近年來看到了加密證明的寒武紀爆發。每種證明系統都有優勢和劣勢，並且設計時都考慮到了特定的權衡。硬體、演算法、新證明和工具的進步不斷提高效能，也催生了新系統的誕生。這些系統中許多已投入使用，並且我們不斷突破界限。我們是否會擁有適用於所有應用的通用證明系統，或者會有幾種適用於不同需求的系統呢？我們認為一個證明系統能夠統治所有其他系統的可能性很小，原因包括：
1）應用的多樣性。
2）不同的限制類型（關於記憶體、驗證時長、證明時長）。
3）對魯棒性的需求（如果一個證明系統被破壞，還有其他證明系統）。
即使證明系統發生了很大變化，它們都提供了一個重要的特性：證明可被快速驗證。擁有一個驗證證明並可以輕鬆適應新證明系統的 layer，解決了與更改 base layer（如以太坊）相關的困難。本文將概述 SNARKs 的不同特徵：
1）密碼學假設：抗碰撞 hash 函式、橢圓曲線上的離散對數難題、knowledge of exponent。
2）透明 vs 可信設定。
3）證明時長：線性 vs 超線性。
4）驗證器時間：恆定時間、對數、次線性、線性。
5）proof size。
6）易於遞迴。
7）算術化方案。
8）單變數多項式 vs 多變數多項式。
本文將探討 SNARKs 的起源、一些基本構建模組以及不同證明系統的興起（和衰落）。本文無意對證明系統進行詳盡的分析。相反，只關注那些對我們有影響的人。當然，這些發展只有通過該領域先驅者的偉大工作和想法才有可能實現。
基礎知識
零知識證明並不新鮮。定義、基礎、重要定理、甚至重要協議都是從 20 世紀 80 年代中期開始制定的。用來構建現代 SNARKs 的一些關鍵思想和協議是在 20 世紀 90 年代提出的（sumcheck 協議），甚至是在比特幣出現之前（2007 年的 GKR）。使用它的主要問題與缺乏強大的用例（網際網路在 20 世紀 90 年代並不發達）以及所需的計算能力有關。
零知識證明：起源 (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 的構造。
Sumcheck 協議 (1992)
sumcheck 協議由 Lund、Fortnow、Karloff 和 Nisan 於 1992 年 Algebraic Methods for Interactive Proof Systems 論文提出。它是簡潔互動式證明最重要的構建模組之一。它幫助我們將多變數多項式 evaluate 求和的要求減少到隨機選擇點的單個 evaluation。
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 協議實現的。
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
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)
Pinocchio (2013)
Pinocchio（見論文 Pinocchio: Nearly Practical Verifiable Computation）是第一個實用、可用的 zk-SNARK。SNARK 基於二次算術程式 (quadratic arithmetic programs，QAP)。證明大小最初為 288 位元組。Pinocchio 的工具鏈提供了從 C 程式碼到算術電路的編譯器，並進一步轉化為 QAP。該協議要求驗證者生成特定於電路的金鑰。它使用橢圓曲線配對來檢查方程。證明生成和金鑰設定的 asymptotics 漸近與計算大小呈線性關係，驗證時長與公共輸入和輸出的大小呈線性關係。
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。
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 思想。
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。
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 (2019)
Spartan 為使用 R1CS 描述的電路提供了 IOP，利用多變數多項式和 sumcheck 協議的屬性。使用合適的多項式承諾方案，它會產生帶有線性時長 prover 的透明 SNARK。
HyperPlonk (2022)
HyperPlonk 基於使用多變數多項式的 Plonk 思想而構建。它不依賴於商來檢查約束的執行情況，而是依賴於 sumcheck 協議。它還支援 high degree 約束，而不會損害證明者的執行時間。由於它依賴於多變數多項式，因此無需執行 FFT，且證明者的執行時間與電路尺寸呈線性關係。HyperPlonk 引入了適合較小域的新 permutation IOP 和基於 sumcheck 的 batch opening 協議，這減少了 prover 的工作量、證明大小和驗證者的時間。
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。
使用抗碰撞 hash 函式的 SNARKs
大約在 Pinocchio 開發的同時，出現了一些生成電路 / 算術方案的想法，可以證明虛擬機器執行的正確性。儘管開發虛擬機器的算術可能比為某些程式編寫專用電路更復雜或效率更低，但它提供了一個優點，即任何程式，無論多麼複雜，都可以通過證明它在虛擬機器中正確執行來證明。TinyRAM 中的想法後來隨著 Cairo vm 和後續虛擬機器（如 zk-evms 或通用 zkvms）的設計而得到改進。使用抗碰撞hash函式消除了對可信設定或使用橢圓曲線運算的需要，但代價是更長的 proofs。
TinyRAM (2013)
在 SNARKs for C 中，開發了一個基於 PCP 的 SNARK，用於證明 C 程式執行的正確性，該程式被編譯為 TinyRAM（精簡指令集電腦）。該電腦採用哈佛架構，具有位元組級可定址隨機存取儲存器。利用非確定性，電路的大小與計算大小呈擬線性 quasilinear 關係，從而有效地處理任意和資料相關的迴圈、控制流和記憶體訪問。
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）。
Ligero (2017)
Ligero 引入了一個證明系統，其 proof size 為 O (根號 n），其中 n 為 circuit size。它將多項式係數排列成矩陣形式並使用線性碼 linear codes。
Brakedown 建立在 Ligero 的基礎上，並引入了與域無關的多項式承諾方案的思想。
ZKP 的一些新進展
在生產中使用不同的證明系統顯示了每種方法的優點，並帶來了新的發展。如，plonkish 算術化提供了一種簡單的方法來包含自定義門和 lookup arguments；FRI 作為 PCS 表現出了出色的效能，領先於 Plonky。同樣，在 AIR 中使用 grand product check（導致帶有預處理的隨機化 AIR）提高了其效能並簡化了記憶體訪問 arguments。基於hash函式的承諾已經流行起來 —— 基於硬體中hash函式的速度或引入新的 SNARK 友好hash函式。
新的多項式承諾方案（2023）
隨著基於多變數多項式的高效 SNARK（如 Spartan 或 HyperPlonk）的出現，人們對適合此類多項式的新承諾方案越來越感興趣。Binius、Zeromorph 和 Basefold 都提出了新的形式來致力於多線性多項式。Binius 具有零開銷來表示資料型別的優點（而許多證明系統使用至少 32 位域元素來表示單個 bit）並在 binary 域上工作。Binius 承諾基於 Brakedown，其設計目的是與域無關。Basefold 將 FRI 推廣到 Reed-Solomon 以外的程式碼，從而形成與域無關的 PCS。
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），但兩者之間的界限已經開始淡化，試圖結合不同證明系統的優點。如，將不同的算術方案與新的多項式承諾方案相結合。可預期，新的證明系統將繼續興起，效能也隨之提高，而對於一些需要一些時間適應的系統來說，將很難跟上這些發展，除非可輕鬆地使用這些工具，而無需更改一些核心基礎設施。
