我们对零知识证明历史的高度主观看法

零知识、简洁、非交互式知识论证 (zk-SNARKs) 是一种强大的密码学原语，允许一方（证明者）说服另一方（验证者）某个给定的陈述是成立的，而除了该陈述的有效性之外不泄露任何其他信息。由于它们在可验证的私有计算中的应用，为计算机程序的执行提供正确性证明，并帮助扩展区块链，它们受到了广泛的关注。我们认为 SNARKs 将对塑造我们的世界产生重大影响，正如我们在文章中描述的那样。SNARKs 充当不同类型证明系统的保护伞，使用不同的多项式承诺方案 (PCS)、算术化方案、交互式预言证明 (IOP) 或概率可验证证明 (PCP)。然而，基本的思想和概念可以追溯到 20 世纪 80 年代中期。在比特币和以太坊推出后，其发展显著加速，事实证明这是一个令人兴奋且强大的用例，因为你可以通过使用零知识证明（通常对于这种特定用例称为有效性证明）来扩展它们。SNARKs 是区块链可扩展性的重要工具。正如 Ben-Sasson 所描述的，近年来见证了密码学证明的寒武纪爆发。每个证明系统都有其优点和缺点，并且在设计时考虑了某些权衡。硬件的进步、更好的算法、新的论证和小工具可以提高性能并催生新的系统。其中许多已在生产中使用，并且我们不断突破界限。我们是否会有一个适用于所有应用程序的通用证明系统，还是有几个适用于不同需求的系统？我们认为不太可能有一个证明系统可以统治一切，因为：

1. 应用的多样性。
2. 我们拥有的约束类型（关于内存、验证时间、证明时间）。
3. 对鲁棒性的需求（如果一个证明系统被破坏，我们仍然有其他的）。

即使证明系统发生很大变化，它们都提供了一个重要的属性：证明可以快速验证。拥有一个可以验证证明并且可以轻松适应处理新证明系统的层，可以解决与更改基础层（例如以太坊）相关的困难。为了概述 SNARKs 的不同特征：

• 密码学假设：抗碰撞哈希函数、椭圆曲线上的离散对数问题、指数知识。
• 透明设置 vs 可信设置。
• 证明者时间：线性 vs 超线性。
• 验证者时间：恒定时间、对数时间、亚线性时间、线性时间。
• 证明大小。
• 递归的难易程度。
• 算术化方案。
• 单变量 vs 多变量多项式。

这篇文章将探讨 SNARKs 的起源、一些基本构建模块以及不同证明系统的兴起（和衰落）。这篇文章的目的不是对证明系统进行详尽的分析。相反，我们专注于那些对我们产生影响的系统。当然，这些发展只有在这一领域先驱者的伟大工作和思想的基础上才有可能实现。

基础知识

正如我们提到的，零知识证明并不是什么新鲜事物。定义、基础、重要定理，甚至重要协议都是从 20 世纪 80 年代中期建立起来的。我们用来构建现代 SNARKs 的一些关键思想和协议是在 20 世纪 90 年代（sumcheck 协议）甚至在比特币出现之前（2007 年的 GKR）提出的。其采用的主要问题与缺乏强大的用例（20 世纪 90 年代的互联网不如现在发达）以及所需的计算能力有关。

零知识证明：起源 (1985/1989)

零知识证明领域在学术文献中首次出现是在 Goldwasser、Micali 和 Rackoff 的论文中。有关起源的讨论，你可以观看以下视频。该论文介绍了完备性、可靠性和零知识的概念，并为二次剩余和二次非剩余提供了构造。

Sumcheck 协议 (1992)

sumcheck 协议 由 Lund、Fortnow、Karloff 和 Nisan 于 1992 年提出。它是简洁交互式证明的最重要构建块之一。它帮助我们将对多元多项式求和的声明简化为在随机选择的点上的单个求值。

Goldwasser-Kalai-Rothblum (GKR) (2007)

GKR 协议 是一种交互式协议，其证明者的运行时间与电路的门数呈线性关系，而验证者的运行时间与电路的大小呈亚线性关系。在该协议中，证明者和验证者在深度为 dd 的有限域上的扇入为 2 的算术电路达成一致，其中第 dd 层对应于输入层，第 00 层是输出层。该协议从关于电路输出的主张开始，该主张被简化为对上一层值的声明。使用递归，我们可以将其转换为对电路输入的声明，该声明可以很容易地检查。这些简化是通过 sumcheck 协议实现的。

KZG 多项式承诺方案 (2010)

Kate、Zaverucha 和 Goldberg 在 2010 年引入了一种使用双线性配对群的多项式承诺方案。该承诺由单个群元素组成，并且承诺者可以有效地将承诺开放给多项式的任何正确求值。此外，由于批处理技术，可以对多个求值进行开放。KZG 承诺为几个高效的 SNARKs 提供了基本构建块，例如 Pinocchio、Groth16 和 Plonk。它也是 EIP-4844 的核心。要获得有关批处理技术的直觉，你可以查看我们关于 Mina-Ethereum 桥 的文章。

使用椭圆曲线的实用 SNARKs

第一个实用的 SNARKs 构造出现在 2013 年。这些需要一个预处理步骤来生成证明和验证密钥，并且是特定于程序/电路的。这些密钥可能非常大，并且依赖于应该对各方保持未知的秘密参数；否则，他们可能会伪造证明。将代码转换为可以证明的内容需要将代码编译为多项式约束系统。起初，这必须以手动方式完成，这既耗时又容易出错。该领域的进展试图消除一些主要问题：

1. 拥有更高效的证明者。
2. 减少预处理量。
3. 拥有通用的而不是电路特定的设置。
4. 避免拥有可信设置。
5. 开发使用高级语言描述电路的方法，而不是手动编写多项式约束。

Pinocchio (2013)

Pinocchio 是第一个实用的、可用的 zk-SNARK。该 SNARK 基于二次算术程序 (QAP)。证明大小最初为 288 字节。Pinocchio 的工具链提供了一个从 C 代码到算术电路的编译器，该电路进一步转换为 QAP。该协议要求验证者生成密钥，这些密钥是特定于电路的。它使用椭圆曲线配对来检查方程式。证明生成和密钥设置的渐进复杂度与计算大小呈线性关系，并且验证时间与公共输入和输出的大小呈线性关系。

Groth 16 (2016)

Groth 介绍了一种新的知识论证，并提高了性能 ，用于由 R1CS 描述的问题。它具有最小的证明大小（仅三个群元素）和快速验证，涉及三个配对。它还涉及一个预处理步骤来获得结构化参考字符串。主要的缺点是，对于我们要证明的每个程序，它都需要不同的可信设置，这很不方便。Groth16 在 ZCash 中使用。

Bulletproofs & IPA (2016)

KZG PCS 的弱点之一是它需要可信设置。Bootle 等人 介绍了一种高效的零知识论证系统，该系统可以开放满足内积关系的 Pedersen 承诺。内积论证具有线性证明者、对数通信和交互，但具有线性时间验证。他们还开发了一种不需要可信设置的多项式承诺方案。使用这些思想的 PCS 被 Halo 2 和 Kimchi 使用。

Sonic、Marlin 和 Plonk (2019)

Sonic、Plonk 和 Marlin 通过引入通用且可更新的结构化参考字符串，解决了 Groth16 中每个程序都需要可信设置的问题。Marlin 提供了一种基于 R1CS 的证明系统，并且是 Aleo 的核心。

Plonk 介绍了一种新的算术化方案（后来称为 Plonkish）和用于复制约束的大乘积检查。Plonkish 还允许为某些操作引入专用门，即所谓的自定义门。多个项目都有 Plonk 的自定义版本，包括 Aztec、zkSync、Polygon ZKEVM、Mina 的 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(Nlog⁡N) 和存储 O(N)O(N)，其中 NN 是表大小。随后出现了其他几个方案，例如 Baloo、flookup、cq 和 caulk+。Lasso 提出了几项改进，避免在表具有给定结构时提交到该表。此外，Lasso 的证明者仅为其查找操作访问的表条目付费。Jolt 利用 Lasso 通过查找来证明虚拟机的执行。

Spartan (2019)

Spartan 为使用 R1CS 描述的电路提供了一个 IOP，利用了多元多项式的属性和 sumcheck 协议。使用合适的多项式承诺方案，它会产生一个具有线性时间证明者的透明 SNARK。

HyperPlonk (2022)

HyperPlonk 基于使用多元多项式的 Plonk 的思想构建。它不使用商来检查约束的执行情况，而是依赖于 sumcheck 协议。它还支持高度约束，而不会损害证明者的运行时间。由于它依赖于多元多项式，因此无需执行 FFT，并且证明者的运行时间与电路大小呈线性关系。HyperPlonk 引入了一种适用于较小字段的新排列 IOP 和一个基于 sumcheck 的批量开放协议，这减少了证明者的工作、证明大小和验证者的时间。

Folding 方案 (2008/2021)

Nova 引入了 folding 方案的思想，这是一种实现增量可验证计算 (IVC) 的新方法。IVC 的概念可以追溯到 Valiant，他展示了如何将两个长度为 kk 的证明合并为单个长度为 kk 的证明。这个想法是，我们可以通过递归证明从步骤 ii 到步骤 I+1I+1 的执行是正确的，并验证证明从步骤 i−1i−1 到步骤 ii 的转换是正确的证明来证明任何长时间运行的计算。Nova 可以很好地处理统一计算；后来通过引入 Supernova 将其扩展到处理不同类型的电路。Nova 使用 R1CS 的松弛版本，并在友好的椭圆曲线上工作。使用友好的曲线循环（例如，Pasta 曲线）来实现 IVC 也在 Pickles 中使用，这是 Mina 实现简洁状态的主要构建块。但是，folding 的思想不同于递归 SNARK 验证。累加器的思想与批量证明的概念联系更紧密。Halo 引入了累积的概念，作为递归证明组合的替代方案。Protostar 为 Plonk 提供了一种非统一 IVC 方案，该方案支持高度门和向量查找。

使用抗碰撞哈希函数

在 Pinocchio 开发的同时，还有一些想法是生成可以证明虚拟机执行正确性的电路/算术化方案。即使开发虚拟机的算术化可能比为某些程序编写专用电路更复杂或效率更低，但它提供了一个优势，即任何程序，无论多么复杂，都可以通过证明它在虚拟机中正确执行来证明。TinyRAM 中的思想后来通过 Cairo vm 的设计以及随后的虚拟机（例如 zk-evms 或通用 zkvms）得到改进。使用抗碰撞哈希函数消除了对可信设置或使用椭圆曲线运算的需求，但代价是更长的证明。

TinyRAM (2013)

在 SNARKs for C 中，他们开发了一种基于 PCP 的 SNARK，用于证明 C 程序执行的正确性，该程序被编译为 TinyRAM，这是一种精简指令集计算机。该计算机使用哈佛架构，具有字节级可寻址随机存取存储器。利用非确定性，电路的大小与计算的大小呈准线性关系，可以有效地处理任意的和数据相关的循环、控制流和内存访问。

STARKs (2018)

STARKs 由 Ben Sasson 等人于 2018 年推出。它们实现了 O(log2n)O(log2⁡n) 证明大小，具有快速的证明者和验证者，不需要可信设置，并且据推测是后量子安全的。它们首先被 Starkware/Starknet 与 Cairo vm 一起使用。其关键介绍包括代数中间表示 (AIR) 和 FRI 协议（快速 Reed-Solomon 交互式 Proximity 预言证明）。它也被其他项目（Polygon Miden、Risc0、Winterfell、Neptune）使用，或者已经看到了某些组件的改编（zkSync 的 Boojum、Plonky2、Starky）。

Ligero (2017)

Ligero 引入了一种证明系统，该系统实现了大小为 O(√n)O(n) 的证明，其中 nn 是电路的大小。它以矩阵形式排列多项式系数，并使用线性码。

Brakedown 基于 Ligero 构建，并引入了与字段无关的多项式承诺方案的思想。

一些新的发展

在生产中使用不同的证明系统显示了每种方法的优点，并促成了新的发展。例如，plonkish 算术化提供了一种简单的方法来包含自定义门和查找参数；FRI 作为 PCS 已经显示出强大的性能，从而产生了 Plonky。类似地，在 AIR 中使用大乘积检查（导致具有预处理的随机 AIR）提高了其性能并简化了内存访问参数。基于哈希函数的承诺越来越受欢迎，这基于硬件中哈希函数的速度或引入新的 SNARK 友好的哈希函数。

新的多项式承诺方案 (2023)

随着基于多元多项式的高效 SNARKs 的出现，例如 Spartan 或 HyperPlonk，人们对适用于此类多项式的新承诺方案越来越感兴趣。Binius、Zeromorph 和 Basefold 都提出了新的形式来承诺多线性多项式。Binius 提供了零开销表示数据类型的优势（而许多证明系统使用至少 32 位字段元素来表示单个位），并且适用于二进制字段。该承诺改编了 brakedown，该 brakedown 旨在与字段无关。Basefold 将 FRI 推广到 Reed-Solomon 以外的代码，从而形成了与字段无关的 PCS。

可定制的约束系统 (2023)

CCS 推广了 R1CS，同时捕获了 R1CS、Plonkish 和 AIR 算术化，而没有开销。将 CCS 与 Spartan IOP 结合使用会产生 SuperSpartan，它支持高度约束，而无需证明者承担随约束度数缩放的密码学成本。特别是，SuperSpartan 会产生一个 AIR 的 SNARK，并具有线性时间证明者。

结论

这篇文章描述了自 20 世纪 80 年代中期 SNARKs 推出以来的进展。计算机科学、数学和硬件的进步，以及区块链的引入，已经产生了新的和更高效的 SNARKs，为许多可以改变我们社会的应用程序打开了大门。研究人员和工程师根据他们的需求提出了对 SNARKs 的改进和改编，重点是证明大小、内存使用、透明设置、后量子安全性、证明者时间和验证者时间。虽然最初有两条主要线路（SNARKs vs STARKs），但两者之间的界限已经开始消失，试图结合不同证明系统的优点。例如，将不同的算术化方案与新的多项式承诺方案相结合。我们可以预期新的证明系统将继续兴起，性能会提高，并且对于某些需要一些时间才能适应这些发展的系统来说，很难跟上这些发展，除非我们可以轻松地使用这些工具，而无需更改一些核心基础设施。

• 原文链接： blog.lambdaclass.com/our...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～