了解零知識證明歷史

來源：登鏈社區

零知識、簡潔、非交互式知識證明（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/

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。

標題：了解零知識證明歷史

地址：https://www.100economy.com/article/112910.html