零知识、简洁、非交互式知识论证（zk-SNARKs，Zero-knowledge, Succinct, Non-interactive ARguments of Knowledge）是强大的密码学原语，允许一方（证明者）说服另一方（验证者）给定的陈述是真实的，同时不泄露任何超出声明有效性之外的信息。它们由于在可验证的私有计算中的应用而受到广泛关注，提供计算机程序执行正确性的证明并帮助扩展区块链。我们认为 SNARK 将对塑造我们的世界产生重大影响，正如我们在我们的文章中所描述的那样。 SNARK 充当不同类型证明系统的保护伞，使用不同的多项式承诺方案 (PCS)、算术化方案、交互式预言证明 (IOP) 或概率可检查证明 (PCP)。然而，基本思想和概念可以追溯到 20 世纪 80 年代中期。引入比特币和以太坊后，开发速度显着加快，这被证明是一个令人兴奋且强大的用例，因为您可以通过使用零知识证明（通常称为此特定用例的有效性证明）来扩展它们。 SNARK 是区块链可扩展性的重要工具。正如本-萨森 (Ben-Sasson) 所描述的那样，过去几年出现了密码学证明的寒武纪大爆发。每个证明系统都有优点和缺点，并且在设计时考虑到了某些权衡。硬件的进步、更好的算法、新的论点和小工具的出現，推动了性能提升和新系统的诞生。其中许多已用于生产，我们在不断突破界限。我们是否会有一个适用于所有应用程序的通用证明系统或适合不同需求的多个系统？我们认为一个证明系统不太可能统治所有这些，因为：
- 应用的多样性。
- 我们所拥有的约束类型（内存、验证时间、证明时间）。
- 对稳健性的需求（如果一个证明系统被破解，我们还有其他选择）。
即使证明系统发生了很大变化，它们都提供了一个重要的特性：证明可以快速验证。拥有一个验证证明并可以轻松适应新证明系统的层解决了与更改基础层（例如以太坊）相关的困难。以下概述 SNARK 的不同特征：
- 密码学假设：抗碰撞哈希函数、椭圆曲线上的离散对数问题、指数知识。
- 透明度与可信设置。
- 证明者时间：线性与超线性。
- 验证器时间：恒定时间、对数、次线性、线性。
- 证明大小。
- 易于递归。
- 算术方案。
- 单变量与多元多项式。
这篇文章将探讨 SNARK 的起源、一些基本构建模块以及不同证明系统的兴起（和衰落）。这篇文章无意对证明系统进行详尽的分析。相反，我们关注那些对我们有影响的人。当然，这些发展只有通过该领域先驱者的伟大工作和想法才有可能实现。
基础知识
正如我们提到的，零知识证明并不新鲜。定义、基础、重要定理、甚至重要协议都是从 20 世纪 80 年代中期开始制定的。我们用来构建现代 SNARK 的一些关键思想和协议是在 20 世纪 90 年代提出的（sumcheck 协议），甚至是在比特币出现之前（2007 年的 GKR）。采用它的主要问题与缺乏强大的用例（互联网在 20 世纪 90 年代并不发达）以及所需的计算能力有关。
零知识证明：起源 (1985/1989)
零知识证明领域随着以下论文出现在学术文献中：戈德瓦瑟、米卡利和拉科夫。有关起源的讨论，您可以参见相关视频。该论文首次提出了完备性、健全性和零知识的概念，并为二次剩余性和非剩余性问题提供了构造方法。
Sumcheck 协议 (1992)
Sumcheck协议由Lund、Fortnow、Karloff和Nisan在1992年提出，它是简洁交互式证明中最关键的构建块之一。该协议能够将对多变量多项式求和的声明简化为在随机选择的点上的单一评估。
戈德瓦塞尔-卡莱-罗斯布鲁姆 (GKR) (2007)
GKR 协议 是一个交互协议，它的证明者在电路门数的线性运行，而验证者在电路大小的亚线性运行。在协议中，证明者和验证者同意在有限域上的二叉输入算术电路的深度d，其中第d层对应于输入层，第0层是输出层。该协议从关于电路输出的声明开始，这被减少到前一层的值的声明。使用递归，我们可以将此转化为对电路输入的声明，这可以轻松检查。这些减少是通过 sumcheck 协议实现的。
KZG多项式承诺方案（2010）
凯特、扎韦鲁查和戈德堡 2010 年引入了基于双线性配对群的多项式承诺方案。该方案的承诺由单个群元素组成，提交者可以高效地验证多项式的任何正确评估。此外，得益于批处理技术，可以同时验证多个评估。KZG承诺为几种高效的SNARKs（如Pinocchio、Groth16和Plonk）提供了基础构建块，并成为EIP-4844的核心。关于批处理技术的直观理解，可参考我们关于Mina-Ethereum桥的文章。
使用椭圆曲线的实用 SNARK
SNARK 的第一个实用结构出现于 2013 年。这些结构需要预处理步骤来生成证明和验证密钥，并且是特定于程序/电路的。这些密钥可能非常大，并且取决于各方不知道的秘密参数；否则，他们可以伪造证据。将代码转换为可证明的代码需要将代码编译为多项式约束系统。起初，这必须以手动方式完成，既耗时又容易出错。该领域的进步试图消除一些主要问题：
- 拥有更高效的证明者。
- 减少预处理量。
- 具有通用而不是电路特定的设置。
- 避免采用可信设置。
- 开发使用高级语言描述电路的方法，而不是手动编写多项式约束。
Pinocchio (2013)
Pinocchio 是第一个实用、可用的 zk-SNARK。 SNARK 基于二次算术程序 (QAP)。证明大小最初为 288 字节。 Pinocchio的工具链提供了从C代码到算术电路的编译器，并进一步转化为QAP。该协议要求验证者生成特定于电路的密钥。它使用椭圆曲线配对来检查方程。证明生成和密钥设置的渐近与计算大小呈线性关系，验证时间与公共输入和输出的大小呈线性关系。
Groth16 (2016)
Groth16 介绍了一个知识的新论证 对于 R1CS 描述的问题表现出更高的效率。它具有最小的证明大小（仅三个组元素）和涉及三个配对的快速验证。它还涉及获取结构化参考字符串的预处理步骤。主要缺点是，我们想要证明的每个程序都需要不同的可信设置，这很不方便。 Groth16 被广泛应用于ZCash等项目中。
Bulletproofs & IPA (2016)
Bulletproofs 介绍了一个无需信任设置的高效零知识论证系统，用于证明满足内积关系的Pedersen承诺的开放。内积论证具备线性证明者、对数通信量和交互次数，但验证时间为线性。该研究还开发了一个不需要信任设置的多项式承诺方案，这些创新被Halo 2和Kimchi等项目采用。
Sonic、Marlin和Plonk (2019)
Sonic, Plonk， 和Marlin 通过引入通用且可更新的结构化参考字符串，解决了 Groth16 中每个程序的可信设置问题。 Marlin 提供了基于 R1CS 的证明系统，是 Aleo 的核心。
Plonk 引入了一种新的算术方案（后来称为 Plonkish）以及对复制约束的宏积检查的使用。 Plonkish 还允许为某些操作引入专门的门，即所谓的定制门。多个项目都有 Plonk 的定制版本，包括 Aztec、zkSync、Polygon ZKEVM、Mina’s Kimchi、Plonky2、Halo 2 和 Scroll 等。
Lookups（2018/2020）
Gabizon和Williamson在2020年引入了plookup，使用大乘积检查来证明一个值包含在预先计算的值表中。虽然查找参数已经在Arya中被提出，但该构造需要确定查找的多重性，这使得构造效率降低。PlonkUp的论文展示了如何将plookup参数引入到Plonk中。这些查找参数的问题在于，它们强迫证明者为整个表格付出代价，而不考虑他的查找次数。这意味着大表格的代价很大，大量的努力已经投入到降低证明者的代价，只计算他使用的查找次数。 \
Haböck引入了LogUp，它使用对数导数将大乘积检查转化为倒数之和。LogUp在Polygon ZKEVM的性能中至关重要，他们需要将整个表格分割成几个STARK模块。这些模块必须被正确的链接，跨表格查找强制执行这一点。LogUp-GKR的引入使用GKR协议来提高LogUp的性能。Caulk是第一个使用预处理时间O(NlogN)和存储O(N)，其中N是表格大小，使证明时间在表格大小下非线性的方案。其他几个方案如Baloo、flookup、cq和caulk+也相继出现。Lasso提出了几个改进，避免了对具有给定结构的表格的提交。此外，Lasso的证明者只为查找操作访问的表格条目付费。Jolt利用Lasso来通过查找证明虚拟机的执行。
Spartan (2019)
Spartan 利用多元多项式和求和协议的属性，为使用 R1CS 描述的电路提供 IOP。使用合适的多项式承诺方案，它会产生带有线性时间证明器的透明 SNARK。
HyperPlonk (2022)
HyperPlonk 建立在使用多元多项式的 Plonk 思想之上。它不依赖于商来检查约束的执行情况，而是依赖于和检查协议。它还支持高度的约束，而不会损害证明者的运行时间。由于它依赖于多元多项式，因此无需执行 FFT，并且证明器的运行时间与电路尺寸呈线性关系。 HyperPlonk 引入了适合较小字段的新排列 IOP 和基于和检查的批量打开协议，这减少了证明者的工作、证明大小和验证者的时间。
折叠方案（2008/2021）
Nova 引入了折叠方案的思想，这是一种实现增量可验证计算（IVC）的新方法。 IVC的概念可以追溯到Valiant 展示了如何将两个长度为 k 的证明合并为一个长度为 k 的证明。其核心思想是，可以通过递归证明，证明从步骤i到步骤i+1的执行是正确的，并验证一个证明，以显示从步骤i-1到步骤i的转换是正确的。Nova 巧妙地处理统一计算問題，后来通过引入将其扩展到处理不同类型的电路Supernova。 Nova 使用 R1CS 的宽松版本，并在友好的椭圆曲线上工作。使用友好的曲线循环（例如，Pasta曲线）来实现 IVC 也被用在 Pickles 中，Pickles 是 Mina 的主要构建块，以实现简洁的状态。然而，折叠概念与递归 SNARK 验证不同，累加器的想法与批处理证明的更为紧密相关。Halo 引入了累加器作为递归证明组合的替代。Protostar 为 Plonk 提供非均匀 IVC 方案，支持高度门和向量查找。
使用抗冲突哈希函数
大约在Pinocchio开发的同时，出现了一些生成电路/算术方案的想法，可以证明虚拟机执行的正确性。尽管开发虚拟机的算术可能比为某些程序编写专用电路更复杂或效率更低，但它提供了一个优点，即任何程序，无论多么复杂，都可以通过证明它在虚拟机中正确执行来证明。机器。 TinyRAM 中的想法后来随着 Cairo vm 和后续虚拟机（例如 zk-evms 或通用 zkvms）的设计而得到改进。使用抗冲突散列函数消除了对可信设置或使用椭圆曲线运算的需要，但代价是更长的证明。
TinyRAM (2013)
在SNARK for C之后，他们开发了一个基于PCP的SNARK，用于证明C程序执行的正确性，该程序被编译为TinyRAM，一种精简指令集计算机。该计算机采用哈佛架构，具有字节级可寻址随机存取存储器。利用非确定性，电路的大小与计算大小呈拟线性关系，从而有效地处理任意和数据相关的循环、控制流和内存访问。
STARKS (2018)
STARKS 由 Ben Sasson 等人介绍。 2018 年。他们实现了 O(log^2n) 的证明大小，具有快速证明者和验证者，不需要可信设置，并且被认为是后量子安全的。它们首先由 Starkware/Starknet 与 Cairo 虚拟机一起使用。其主要介绍包括代数中间表示（AIR）和FRI协议 （快速Reed-Solomon交互式预言机邻近证明）。它也被其他项目（Polygon Miden、Risc0、Winterfell、Neptune）使用，或者已经看到了一些组件的改编（zkSync 的 Boojum、Plonky2、Starky）。
Ligero (2017)
Ligero 引入了一个证明系统，该证明系统的大小为 O(√n)，其中 n 是电路的大小。它将多项式系数排列成矩阵形式并使用线性码。Brakedown 建立在 Ligero 的基础上，并引入了与场无关的多项式承诺方案的思想。
一些新进展
在生产中使用不同的证明系统显示了每种方法的优点，并带来了新的发展。例如，笨拙的算术化提供了一种简单的方法来包含自定义门和查找参数； FRI 作为 PCS 表现出了出色的性能，领先于 Plonky。同样，在 AIR 中使用大乘积检查（导致带有预处理的随机 AIR）提高了其性能并简化了内存访问参数。基于哈希函数的承诺已经流行起来，基于硬件中哈希函数的速度或引入新的 SNARK 友好哈希函数。
新的多项式承诺方案（2023）
随着基于多元多项式的高效 SNARK（例如 Spartan 或 HyperPlonk）的出现，人们对适合此类多项式的新承诺方案越来越感兴趣。如 Binius, Zeromorph， 和Basefold 等所有人都提出了新的形式来致力于多线性多项式。 Binius 具有零开销来表示数据类型的优点（而许多证明系统使用至少 32 位字段元素来表示单个位）并在二进制字段上工作。该承诺采用了制动功能，其设计目的是与现场无关。 Basefold 将 FRI 推广到 Reed-Solomon 以外的代码，从而形成与字段无关的 PCS。
可定制的约束系统 (2023)
CCS 概括 R1CS，同时捕获 R1CS、Plonkish 和 AIR 算术，无需任何开销。将 CCS 与 Spartan IOP 结合使用会产生 SuperSpartan，它支持高度约束，而无需证明者承担随约束程度而扩展的加密成本。特别是，SuperSpartan 为带有线性时间证明器的 AIR 生成 SNARK。
结论
这篇文章描述了 SNARK 自 20 世纪 80 年代中期推出以来的进步。计算机科学、数学和硬件的进步，加上区块链的引入，催生了新的、更高效的 SNARK，为许多可以改变我们社会的应用程序打开了大门。研究人员和工程师根据自己的需求提出了对 SNARK 的改进和调整，重点关注证明大小、内存使用、透明设置、后量子安全、证明者时间和验证者时间。虽然最初有两条主线（SNARK 与 STARK），但两者之间的界限已经开始淡化，试图结合不同证明系统的优点。例如，将不同的算术方案与新的多项式承诺方案相结合。我们可以预期，新的证明系统将继续兴起，性能也随之提高，而对于一些需要一些时间适应的系统来说，将很难跟上这些发展，除非我们可以轻松地使用这些工具，而无需更改一些核心基础设施。
声明：
- 本文转载自[lambdaclass]，著作权归属原作者[LambdaClass]，如对转载有异议，请联系Gate Learn团队，团队会根据相关流程尽速处理。
- 免责声明：本文所表达的观点和意见仅代表作者个人观点，不构成任何投资建议。
- 文章其他语言版本由Gate Learn团队翻译， 在未提及Gate.io的情况下不得复制、传播或抄袭经翻译文章。
Статті на тему
