來源：登鏈社區
零知識、簡潔、非互動知識證明（zk-SNARKs）是一種強大的加密原語，允許一方，即證明者，說服另一方，即驗證者，某個陳述是真實的，而不透露除了該陳述的有效性之外的任何其他資訊。由於它們在可驗證的私人計算、提供電腦程式執行正確性的證明以及幫助擴展區塊鏈方面的應用，它們引起了廣泛關注。我們認為SNARKs 將對塑造我們的世界產生重大影響，正如我們在我們的文章[6]中所描述的。 SNARKs 作為不同類型的證明系統的總稱，使用不同的多項式承諾方案（PCS）、算術化方案、互動式Oracle 證明（IOP）或機率可檢查證明（PCP）。然而，這些基本思想和概念可以追溯到20 世紀80 年代中期。在比特幣和以太坊的引入後，開發工作顯著加快，這證明了它們是一個令人興奮且強大的用例，因為你可以透過使用零知識證明（通常稱為此特定用例的有效性證明）來擴展它們。 SNARKs 是區塊鏈可擴展性的重要工具。正如Ben-Sasson 所描述的，過去幾年見證了加密證明的寒武紀爆發[7] 。每個證明系統都有優點和缺點，並且在設計時考慮了某些權衡。硬體的進步、更好的演算法、新的論證和小工具導致了性能的提升和新系統的誕生。其中許多系統正在生產中使用，我們不斷推動界限。我們是否會有一個適用於所有應用的通用證明系統，還是適用於不同需求的幾個系統？我們認為一個證明系統將統治所有應用的可能性不大，因為：
-
應用的多樣性。
-
我們有不同的約束類型（關於記憶體、驗證時間、證明時間）。
-
對魯棒性的需求（如果一個證明系統被破解，我們仍然有其他系統）。
即使證明系統發生了很大變化，它們都具有一個重要特性：證明可以快速驗證。透過具有驗證證明並且可以輕鬆適應處理新的證明系統的層， 也解決了與更改基礎層（如以太坊）相關的困難。
為了概述SNARKs 的不同特徵：
-
密碼假設：抗碰撞雜湊函數、橢圓曲線上的離散對數問題、指數知識。
-
透明vs 可信任設定。
-
證明者時間：線性vs 超線性。
-
驗證者時間：常數時間、對數、次線性、線性。
-
證明大小。
-
遞歸的便利性。
-
算術化方案。
-
一元vs 多元多項式。
本文將探討SNARKs 的起源、一些基本建構模組以及不同證明系統的興起（和衰落）。本文並不打算對證明系統進行詳盡的分析。相反，我們專注於對我們當前產生影響的那些。當然，這些發展只有在這一領域的先驅們的偉大工作和思想的基礎上才得以實現。
基礎知識
正如我們所提到的，零知識證明並不是新鮮事。定義、基礎、重要定理甚至重要協定都是從20 世紀80 年代中期確立的。一些用於構建現代SNARKs 的關鍵思想和協議是在1990 年代提出的（sumcheck 協議），甚至在比特幣出現之前（2007 年的GKR）。當時採用的主要問題，主要是缺乏強大的用例（1990 年代互聯網發展不如今日）以及所需的運算能力有關。
零知識證明：起源（1985/1989）
零知識證明領域在學術文獻中首次出現是在 [Goldwasser, Micali and Rackoff](https://people.csail.mit.edu/silvio/Selected Scientific Papers/Proof Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf?ref=blog.lambdaclass.com “Goldwasser, Micali and Rackoff”) 的論文中。有關起源的討論，你可以參見以下視頻[8] 。論文引入了完備性、正確性和零知識的概念，並提供了二次剩餘（quadratic residuosity）和二次非剩餘（quadratic non-residuosity）的構造。
Sumcheck 協議（1992）
sumcheck 協議[9]是由Lund, Fortnow, Karloff, and Nisan[10] 於1992 年提出的。它是簡潔互動證明的最重要的建構模組之一。它幫助我們將多元多項式的求值總和的聲明減少到在隨機選擇的點上的單一求值。
Goldwasser-Kalai-Rothblum（GKR）（2007）
GKR 協議[11]是一種互動式協議，其證明者的運行時間與電路的閘數成線性關係，而驗證者的運行時間與電路的大小成次線性關係。在該協議中，證明者和驗證者就深度為d 的有限域上的扇形二通算術（an arithmetic circuit of fan-in-two）電路達成一致，其中層d 對應於輸入層，層0 對應於輸出層。協定從對電路輸出的聲明開始，將其減少為對前一層值的聲明。透過遞歸，我們可以將其轉換為對電路輸入的聲明，這可以輕鬆地進行檢查。這些減少是透過sumcheck 協議實現的。
KZG 多項式承諾方案（2010）
KZG 多項式承諾方案（KZG polynomial commitment scheme 簡稱PCS ）Kate, Zaverucha, and Goldberg[12]於2010 年引入了使用雙線性配對群的多項式承諾方案。該承諾由單一群體元素組成，提交者可以有效地打開對多項式的任何正確評估的承諾。此外，由於批次技術，可以對多個評估進行開啟。 KZG 承諾是Pinocchio、Groth16 和Plonk 等幾種高效能SNARKs 提供了基本構建模組。它也是EIP-4844[13] 的核心。有關批次技術的直觀理解，你可以參見我們關於Mina-Ethereum 橋[14]的文章。
使用橢圓曲線的實用SNARKs
2013 年出現了第一個實用的SNARKs 構造。這些構造需要預處理步驟來產生證明和驗證金鑰，並且是程式/電路特定的。這些密鑰可能相當大，並且取決於應保持未知的秘密參數；否則，它們可以偽造證明。將程式碼轉換為可證明的內容需要將程式碼編譯成一系列多項式約束系統。起初，這必須以手動編碼方式完成，這是耗時且容易出錯的。該領域的進展試圖消除一些主要問題：
-
有更有效率的證明者。
-
減少預處理的數量。
-
具有通用而不是特定電路的設定。
-
避免信任設定。
-
發展使用高階語言描述電路的方法，而不是手動編寫多項式約束。
Pinocchio (2013)
Pinocchio[15] 是第一個實用的、可用的zk-SNARK。 SNARK 基於二次算術程序（QAP）。證明大小最初為288 位元組。 Pinocchio 的工具鏈提供了從C 程式碼到算術電路的編譯器，進一步轉換為QAP。該協定要求驗證者產生金鑰，這些金鑰是特定於電路的。它使用橢圓曲線配對來檢查方程式。證明產生和金鑰設定的漸近性與計算大小成線性關係，驗證時間與公共輸入和輸出的大小成線性關係。
Groth 16 (2016)
Groth[16] 引入了一個具有增強性能的新知識論證[17] ，用於描述R1CS 的問題。它具有最小的證明大小（僅三個群元素）和快速驗證，涉及三個配對。它還涉及一個預處理步驟，以獲得結構化參考字串。其主要缺點是，它需要針對我們想要證明的每個程式進行不同的信任設置，這很不方便。 Groth16 被ZCash 使用。
Bulletproofs & IPA (2016)
KZG PCS 的一個弱點是它需要一個信任設定。 Bootle 等人[18] 引入了滿足內積關係的Pedersen 承諾開局的有效零知識論證系統。內積論證具有線性證明者，對數通信和交互，但具有線性時間驗證。他們也發展了一個不需要信任設定的多項式承諾方案。使用這些想法的多項式承諾方案（PCS） 被Halo 2 和Kimchi 使用。
Sonic、Marlin 與Plonk (2019)
Sonic[19]、Plonk[20] 和Marlin[21] 解決了Groth16 中我們所遇到的每個程式都需要信任設定的問題，透過引入通用和可更新的結構化參考字串。 Marlin 提供了基於R1CS (Rank-1 Constraint System) 的證明系統，是Aleo 的核心。
Plonk[22] 引入了一種新的算術方案（後來稱為Plonkish）和使用宏積（grand-product）檢查來檢查複製約束。 Plonkish 還允許為某些操作引入專門的門，即所謂的定制門。幾個項目都有Plonk 的定製版本，包括Aztec、ZK-Sync、Polygon ZKEVM、Mina 的Kimchi、Plonky2、Halo 2 和Scroll 等。
Lookups (2018/2020)
Gabizon 和Williamson 在2020 年引進了plookup[23]，使用宏積檢定來證明一個值包含在預先計算的值表中。儘管查找參數先前在Arya[24] 中提出，但該構造需要確定查找的多重性，這使得構造不夠有效率。 PlonkUp[25] 論文展示如何將plookup 參數引入Plonk。這些查找參數的問題在於，它們迫使證明者為整個表格支付費用，而與他的查找次數無關。這意味著大型錶的成本相當大，人們已經付出了大量努力來減少證明者僅支付他使用的查找次數的成本。 Haböck 引進了LogUp[26]，它使用對數導數將宏積（grand-product）檢查轉換為倒數的和。 LogUp 對於Polygon ZKEVM[27] 中的效能至關重要，他們需要將整個表拆分為幾個STARK 模組。這些模組必須正確鏈接，跨表查找強制執行這一點。引進LogUp-GKR[28] 使用GKR 協定來提高LogUp 的效能。 Caulk[29] 是第一個證明者時間與表格大小亞線性的方案，使用預處理時間O(NlogN) 和儲存O(N)，其中N 是表格大小。隨後出現了幾種其他方案，如Baloo[30]、flookup[31]、cq[32] 和caulk+[33]。 Lasso[34] 提出了幾項改進，避免在表具有給定結構時對其進行提交。此外，Lasso 的證明者只為lookup 操作存取的表格條目付費。 Jolt[35] 利用Lasso 透過lookups 證明虛擬機器的執行情況。
Spartan (2019)
Spartan[36] 為使用R1CS 描述的電路提供了一個IOP (“Interactive Oracle Proof.”)，利用多變量多項式的性質和sumcheck 協定。使用合適的多項式承諾方案，它產生了一個線性時間證明的透明SNARK。
HyperPlonk (2022)
HyperPlonk[37] 基於Plonk 的思想，使用多變量多項式(multivariate polynomials)。它依賴sumcheck 協定而不是商來檢查約束的執行。它還支援高次約束，而不會影響證明者的運行時間。由於它依賴多變量多項式，因此無需進行FFT，證明者的運行時間與電路大小成線性關係。 HyperPlonk 引入了一種適用於較小欄位的新置換IOP，以及基於sumcheck 的批量開啟協議，這減少了證明者的工作、證明大小和驗證者的時間。
Folding schemes (2008/2021)
Nova[38] 引入了折疊（Folding）方案的概念，這是實現增量可驗證計算（IVC：incrementally verifiable computation）的新方法。 IVC 的概念可以追溯到Valiant[39]，他展示瞭如何將長度為k 的兩個證明合併為長度為k 的單一證明。這個想法是，我們可以透過遞歸地證明從第i 步到第I +1 步的執行是正確的，並驗證一個證明，證明從第i−1 步到第i 步的轉換是正確的，來證明任何長時間運行的計算。 Nova 很好地處理統一計算；隨後它被擴展以處理不同類型的電路，引入了Supernova[40]。 Nova 使用R1CS 的一種放鬆版本，並在友善的橢圓曲線上工作。使用曲線的友善循環（例如Pasta 曲線）來實現IVC，也被用於Pickles，Mina 的實現簡潔狀態的主要構建塊。然而，折疊的概念與遞歸SNARK 驗證不同。
累加器的想法與批量證明的概念更深入地聯繫在一起。 Halo[41] 引入了累加的概念作為遞歸證明組合的替代方案。 Protostar[42] 為Plonk 提供了一個非統一的IVC 方案，支援高次閘和向量lookups。
使用抗碰撞哈希函數
在Pinocchio 開發的同時，有一些想法是產生電路/算術方案，可以證明虛擬機器的執行正確性。即使開發虛擬機器的算術化可能比為一些程式編寫專用電路更複雜或不太高效，但它的優勢在於可以透過展示在虛擬機器中正確執行程式來證明任何複雜的程式。 TinyRAM 中的想法隨後透過Cairo vm 的設計得到改進，並且隨後的虛擬機器（如zk-evms 或通用目的zkvms）也得到了改進。使用抗碰撞雜湊函數消除了對可信設定或橢圓曲線操作的需求，但代價是證明變得更長。
TinyRAM（2013）
在SNARKs for C[43] 中，他們開發了基於PCP 的SNARK，用於證明C 程式的執行正確性，該程式被編譯為TinyRAM，即精簡指令集電腦。
備註：PCP， Probabilistically Checkable Proof 機率可檢查證明， 驗證者只需閱讀證明中隨機選擇的一小部分內容，就能以很高的置信度檢查證明的有效性。與驗證者需要檢查整個證明的傳統證明系統不同，PCP 只需有限的隨機性即可實現高效驗證。
該計算機採用哈佛結構，具有位元組級可尋址的隨機記憶體。利用非確定性，電路的大小與計算的大小幾乎成線性關係，可以高效處理任意和資料相關的循環、控制流和記憶體存取。
STARKs（2018）
STARKs[44] 由Ben Sasson 等人於2018 年提出。它們實現了0（log^2 n）的證明大小，具有快速的證明者和驗證者，不需要可信設置，並且被推測為後量子安全。它們首次被Starkware/Starknet 使用，與Cairo vm 一起。它的關鍵引入包括代數中間表示（AIR）和FRI 協議[45]（快速Reed-Solomon 互動式Oracle 接近證明Fast Reed-Solomon Interactive Oracle Proof of Proximity ）。它也被其他項目使用（Polygon Miden、Risc0、Winterfell、Neptune），或看到了一些組件的改編（ZK-Sync 的Boojum、Plonky2、Starky）。
Ligero（2017）
Ligero[46] 提出了一種證明系統，實現了證明大小為O(√n) ，其中n 是電路的大小。它將多項式係數排列成矩陣形式，並使用線性碼。 Brakedown[47] 建立在Ligero 的基礎上，引入了領域無關多項式承諾方案的概念。
一些新的發展
在生產中使用不同的證明系統展示了每種方法的優點，並帶動新的發展。例如，plonkish 算術化提供了一種簡單的方法來包含自訂門和lookup arguments；FRI 已經顯示出作為PCS 的出色性能，通往了Plonky。同樣，在AIR 中使用宏積檢查（帶來了預處理的隨機化AIR）改進了其性能並簡化了記憶體存取參數。基於雜湊函數的承諾因其在硬體中的速度或新的適用於SNARK 的雜湊函數的引入而變得流行。
新的多項式承諾方案（2023）
隨著基於多變量多項式的高效SNARKs 的出現，例如Spartan 或HyperPlonk，人們對適用於這種多項式的新承諾方案產生了更大的興趣。 Binius[48]、Zeromorph[49] 和Basefold[50] 都提出了對多線性多項式進行承諾的新形式。 Binius 的優點在於表示資料類型時沒有額外開銷（而許多證明系統至少使用32 位元欄位元素來表示單一位元），並且可以在二進位域上工作。此承諾方案採用了為領域無關而設計的brakedown。 Basefold 將FRI 推廣到Reed-Solomon 之外的碼，帶來了一個領域無關的PCS。
註領域無關：在領域無關的多項式承諾方案中，承諾過程不依賴任何特定領域的特定屬性。這意味著可以對任何代數結構的多項式做出承諾，例如有限域、橢圓曲線，甚至整數環。
可自訂的約束系統（2023）
CCS[51] 泛化了R1CS，同時捕捉了R1CS、Plonkish 和AIR 算術化，沒有額外開銷。使用CCS 與Spartan IOP 結合產生了SuperSpartan，它支援高維度約束，證明者不需要承擔隨著約束度量增加而擴展的加密成本。特別是，SuperSpartan 為AIR 提供了一個線性時間證明的SNARK。
結論
本文描述了自20 世紀80 年代中期以來SNARKs 的進展。電腦科學、數學和硬體的進步，以及區塊鏈的引入，導致了新的更有效率的SNARKs 的出現，為許多可能改變我們社會的應用打開了大門。研究人員和工程師根據他們的需求提出了對SNARKs 的改進和適應，專注於證明大小、記憶體使用、透明設定、後量子安全、證明時間和驗證時間。雖然最初有兩條主要線路（SNARKs vs STARKs），但兩者之間的界限已經開始消失，試圖結合不同證明係統的優勢。例如，結合不同的算術化方案與新的多項式承諾方案。我們可以預期，新的證明系統將繼續湧現，性能將會提高，對於一些需要一些時間來適應的系統來說，要跟上這些發展將會很困難，除非我們可以輕鬆地使用這些工具而無需改變一些核心基礎設施。
參考資料
[1]連結: https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/
[2]登鏈翻譯計畫: https://github.com/lbc-team/Pioneer
[3]翻譯小組: https://learnblockchain.cn/people/412
[4]Tiny 熊: https://learnblockchain.cn/people/15
[5]learnblockchain.cn/article…: https://learnblockchain.cn/article/7422
[6]文章: https://blog.lambdaclass.com/transforming-the-future-with-zero-knowledge-proofs-fully-homomorphic-encryption-and-new-distributed-systems-algorithms/
[7]加密證明的寒武紀爆發: https://medium.com/starkware/cambrian-explosion-of-cryptographic-proofs-5740a41cdbd2?ref=blog.lambdaclass.com
[8]以下影片: https://www.youtube.com/watch?v=uchjTIlPzFo&ref=blog.lambdaclass.com
[9]sumcheck 協議: https://blog.lambdaclass.com/have-you-checked-your-sums/
[10]Lund, Fortnow, Karloff, and Nisan: https://dl.acm.org/doi/pdf/10.1145/146585.146605?ref=blog.lambdaclass.com
[11]GKR 協定: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/2008-DelegatingComputation.pdf?ref=blog.lambdaclass.com
[12]Kate, Zaverucha, and Goldberg: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf?ref=blog.lambdaclass.com
[13]EIP-4844: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-4844.md?ref=blog.lambdaclass.com
[14]Mina-Ethereum 橋: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
[15]Pinocchio: https://eprint.iacr.org/2013/279?ref=blog.lambdaclass.com
[16]Groth: https://eprint.iacr.org/2016/260.pdf?ref=blog.lambdaclass.com
[17]具有增強效能的新知識論證: https://blog.lambdaclass.com/groth16/
[18]Bootle 等： https://eprint.iacr.org/2016/263?ref=blog.lambdaclass.com
[19]Sonic: https://eprint.iacr.org/2019/099?ref=blog.lambdaclass.com
[20]Plonk: https://eprint.iacr.org/2019/953?ref=blog.lambdaclass.com
[21]Marlin: https://eprint.iacr.org/2019/1047?ref=blog.lambdaclass.com
[22]Plonk: https://blog.lambdaclass.com/all-you-wanted-to-know-about-plonk/
[23]plookup: https://eprint.iacr.org/2020/315?ref=blog.lambdaclass.com
[24]Arya: https://eprint.iacr.org/2018/380?ref=blog.lambdaclass.com
[25]PlonkUp: https://eprint.iacr.org/2022/086?ref=blog.lambdaclass.com
[26]LogUp: https://eprint.iacr.org/2022/1530?ref=blog.lambdaclass.com
[27]Polygon ZKEVM: https://toposware.medium.com/beyond-limits-pushing-the-boundaries-of-zk-evm-9dd0c5ec9fca?ref=blog.lambdaclass.com
[28]LogUp-GKR: https://eprint.iacr.org/2023/1284?ref=blog.lambdaclass.com
[29]Caulk: https://eprint.iacr.org/2022/621?ref=blog.lambdaclass.com
[30]Baloo: https://eprint.iacr.org/2022/1565?ref=blog.lambdaclass.com
[31]flookup: https://eprint.iacr.org/2022/1447?ref=blog.lambdaclass.com
[32]cq: https://eprint.iacr.org/2022/1763?ref=blog.lambdaclass.com
[33]caulk+: https://eprint.iacr.org/2022/957?ref=blog.lambdaclass.com
[34]Lasso: https://eprint.iacr.org/2023/1216?ref=blog.lambdaclass.com
[35]Jolt: https://eprint.iacr.org/2023/1217?ref=blog.lambdaclass.com
[36]Spartan: https://eprint.iacr.org/2019/550?ref=blog.lambdaclass.com
[37]HyperPlonk: https://eprint.iacr.org/2022/1355.pdf?ref=blog.lambdaclass.com
[38]Nova: https://eprint.iacr.org/2021/370?ref=blog.lambdaclass.com
[39]Valiant: https://https//iacr.org/archive/tcc2008/49480001/49480001.pdf?ref=blog.lambdaclass.com
[40]Supernova: https://eprint.iacr.org/2022/1758?ref=blog.lambdaclass.com
[41]Halo: https://eprint.iacr.org/2019/1021.pdf?ref=blog.lambdaclass.com
[42]Protostar: https://eprint.iacr.org/2023/620?ref=blog.lambdaclass.com
[43]SNARKs for C: https://eprint.iacr.org/2013/507?ref=blog.lambdaclass.com
[44]STARKs: https://eprint.iacr.org/2018/046?ref=blog.lambdaclass.com
[45]FRI 協定: https://blog.lambdaclass.com/how-to-code-fri-from-scratch/
[46]Ligero: https://eprint.iacr.org/2022/1608?ref=blog.lambdaclass.com
[47]Brakedown: https://eprint.iacr.org/2021/1043?ref=blog.lambdaclass.com
[48]Binius: https://blog.lambdaclass.com/snarks-on-binary-fields-binius/
[49]Zeromorph: https://eprint.iacr.org/2023/917?ref=blog.lambdaclass.com
[50]Basefold: https://blog.lambdaclass.com/how-does-basefold-polynomial-commitment-scheme-generalize-fri/
[51]CCS: https://eprint.iacr.org/2023/552?ref=blog.lambdaclass.com
[52]DeCert.me: https://decert.me/