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。这些 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 通过查找来证明虚拟机的执行情况。
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 立场无关。文章内的信息仅供参考，均不构成任何投资建议及要约，并请您遵守所在国家或地区的相关法律法规。
