Zero-knowledge， Succinct， Non-interactive ARguments of Knowledge（zk-SNARKs）是強大的密碼學原語
原文：Our highly subjective view on the history of Zero-Knowledge Proofs（LambdaClass）
作者：LambdaClass
翻譯：mutourend，Yiping，IOSG Ventures
原用標題：IOSG Weekly Brief |零知識證明歷久彌新創新湧現的原因是什麼？ #213
原文來源於 https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/
引言
零知識、簡潔、非互動式知識證明（zk-SNARKs），是一種強大的密碼學原語，允許證明者說服驗證者某個陳述的正確性，而無需透露陳述以外的任何資訊。 由於其在可驗證私人計算、計算機程序執行正確性證明和區塊鏈擴展方面的應用，zk-SNARKs 受到廣泛關注。 我們相信，正如我們在文章中描述的那樣，zk-SNARKs 將對塑造世界產生重大影響。 zk-SNARKs 涵蓋了不同類型的證明系統，使用不同的多項式承諾方案、算術化方案、互動式預言機證明或概率可檢驗證明。 但這些基本思想和概念可追溯至 20 世紀 80 年代中期。 自比特幣和乙太坊推出以來，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 的起源、一些基本構建模組以及不同證明系統的興起（和衰落）。 本文無意對證明系統進行詳盡的分析。 相反，只關注那些對我們有影響的人。 當然，這些發展只有通過該領域先驅者的偉大工作和想法才有可能實現。
基礎知識
零知識證明並不新鮮。 定義、基礎、重要定理、甚至重要協定都是從 20 世紀 80 年代中期開始制定的。 用來構建現代 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
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。 這些 lookuparguments 的問題在於，它們迫使證明者為整個表支付費用，而與其查找次數無關。 這意味著大型表的成本相當大，並且已投入了大量的精力來將證明者的成本降低到其使用的查找數量。
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。
使用抗碰撞哈希函数的 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 的基础上，并引入了与域无关的多项式承诺方案的思想。
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。
結論
本文描述了 SNARK 自 20 世紀 80 年代中期推出以來的進步。 計算機科學、數學和硬體的進步，加上區塊鏈的引入，催生了新的、更高效的 SNARK，為許多可以改變我們社會的應用程式打開了大門。 研究人員和工程師根據自己的需求提出了對 SNARKs 的改進和調整，重點關注證明大小、記憶體使用、透明設置、后量子安全、證明者時間和驗證者時間。
雖然最初有兩條主線（SNARK 與 STARK），但兩者之間的界限已經開始淡化，試圖結合不同證明系統的優點。 如，將不同的算術方案與新的多項式承諾方案相結合。 可預期，新的證明系統將繼續興起，性能也隨之提高，而對於一些需要一些時間適應的系統來說，將很難跟上這些發展，除非可輕鬆地使用這些工具，而無需更改一些核心基礎設施。
免責聲明：作為區塊鏈資訊平臺，本站所發佈文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。 文章內的資訊僅供參考，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
