我们对零知识证明历史的深度主观解读

零知识证明、简洁非交互式知识论证（zk-SNARKs）作为一种强大的密码学工具，使得一方（证明者）能向另一方（验证者）证明某一声明的真实性，同时不泄露任何超出声明有效性之外的信息。zk-SNARKs因其在可验证隐私计算、确保计算机程序执行的正确性以及促进区块链扩容等领域的应用而受到广泛关注。我们相信，正如文章所述，SNARKs将在重塑我们世界的过程中发挥巨大作用。SNARKs作为一类证明系统，涵盖了多种多项式承诺方案（PCS）、算术化方案、交互式Oracle证明（IOP）及概率可检查证明（PCP）。尽管如此，它们的基本理念和概念可以追溯至20世纪80年代中期。随着比特币和以太坊的出现，这一领域的发展加速，证明了零知识证明在区块链扩容方面的强大潜力。SNARKs成为了区块链可扩展性的关键工具。正如Ben-Sasson所阐述，近年来，密码学证明经历了快速增长，每种证明系统都有其优缺点，并在权衡考量下设计。硬件进步、算法优化、新论证及小工具的出现推动了性能提升和新系统的诞生，许多已被投入生产使用，我们也在不断推进技术边界。面对应用的多样性、我们所面临的各种限制（内存、验证时间、证明时间）以及对鲁棒性的需求（若一证明系统被破解，我们还有备选方案），是否有一个万能的证明系统，或者存在几个针对不同需求的系统？我们认为，一个单一的证明系统统治全部是不太可能的，因为：

1. 应用的多样化。
2. 我们所面临的约束类型（内存、验证时间、证明时间）。
3. 对鲁棒性的需求（如果一个证明系统被破解，我们还有其他选择）。

尽管证明系统经历了巨大变革，它们都提供了一个共同特性：证明可以快速验证。存在一个验证证明的层次，它可以轻松适应新的证明系统，解决更改底层技术（如以太坊）相关的挑战。为了概述SNARKs的不同特性，我们关注以下方面：

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

本文旨在探讨SNARKs的起源、一些基础构建块及不同证明系统的发展历程。我们并不打算进行详尽的分析，而是关注那些对我们产生重大影响的发展。显然，这些进步都得益于该领域先驱们的杰出工作和思想。

基础

正如前文提及，零知识证明的概念并非新鲜事物。自20世纪80年代中期以来，定义、基础理论、重要定理乃至关键协议均已建立。构建现代SNARKs的关键思想和协议，部分在1990年代提出（例如sumcheck协议），或甚至早于比特币的出现（2007年的GKR协议）。其采纳面临的主要挑战与缺乏强大应用场景（1990年代的互联网并不像今天这样发达）以及所需的计算能力有关。

零知识证明：起源（1985/1989）

零知识证明领域是随着Goldwasser、Micali和Rackoff的论文而跻身学术圈的。关于其起源的讨论可以参见相关视频。该论文首次提出了完备性、健全性和零知识的概念，并为二次剩余性和非剩余性问题提供了构造方法。

Sumcheck协议（1992）

Sumcheck协议由Lund、Fortnow、Karloff和Nisan在1992年提出，它是简洁交互式证明中最关键的构建块之一。该协议能够将对多变量多项式求和的声明简化为在随机选择的点上的单一评估。

Goldwasser-Kalai-Rothblum（GKR）（2007）

GKR协议是一个交互式协议，证明者的运行时间与电路门数线性相关，而验证者的运行时间则与电路大小亚线性相关。协议围绕一个有限域上的双输入算术电路展开，从电路输出的声明开始逐层简化至电路输入的声明，这一过程通过sumcheck协议实现。

KZG多项式承诺方案（2010）

2010年，Kate、Zaverucha和Goldberg引入了基于双线性配对群的多项式承诺方案。该方案的承诺由单个群元素组成，提交者可以高效地验证多项式的任何正确评估。此外，得益于批处理技术，可以同时验证多个评估。KZG承诺为几种高效的SNARKs（如Pinocchio、Groth16和Plonk）提供了基础构建块，并成为EIP-4844的核心。关于批处理技术的直观理解，可参考我们关于Mina-Ethereum桥的文章。

实用的SNARKs和椭圆曲线（2013）

2013年，首批实用的SNARK构造出现，它们需要预处理步骤来生成证明和验证密钥，这些密钥依赖于应保密的参数；否则，可能伪造证明。将代码转换为可证明形式需要将代码编译成一套多项式约束系统，最初这一过程需手动完成，既耗时又易错。该领域的进步在于解决了以下主要问题：

• 提高证明者效率。
• 减少预处理量。
• 实现通用而非特定于电路的设置。
• 避免信任设置。
• 使用高级语言描述电路，简化多项式约束的编写。

接下来的部分将继续概述从Pinocchio到HyperPlonk等证明系统的发展，展示了如何通过不断的技术创新和优化，推动了零知识证明技术的进步和应用的扩展。每一步进展不仅解锁了之前系统的局限性，还为未来的创新奠定了基础，这些进步涵盖了证明生成、验证效率和应用适用性的全方位提升。

Pinocchio（2013）

Pinocchio是首个实用且高效的zk-SNARK，基于二次算术程序（QAP）。它的证明大小最初为288字节，提供了从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引入了新的算术化方案和大乘积检查用于复制约束，允许使用自定义门。这些特性使Plonk成为包括Aztec、ZK-Sync、Polygon ZKEVM等多个项目选择的基础。

Lookups（2018/2020）

Gabizon和Williamson于2020年推出了plookup技术，利用大乘积检验来验证某个值是否存在于预先计算的表中。尽管Arya项目先前已经探索了查找机制，但其效率因需确定查找的多重性而受限。PlonkUp论文成功展示了plookup机制在Plonk中的应用，解决了证明者不论实际查找次数，均需为整个表的查找支付成本的问题。特别对于大型表格，这一问题导致成本显著增加，促使研究者努力仅让证明者根据实际查找次数承担费用。

Haböck提出的LogUp通过对数导数将大乘积检查简化为倒数之和，对Polygon ZKEVM中将表格分割为多个STARK模块的性能优化至关重要。引入LogUp-GKR，利用GKR协议进一步提升了LogUp的效率。Caulk首次实现了预处理时间O(NlogN)和存储O(N)的方案，使证明者的时间成本达到亚线性，N代表表格大小。继Caulk之后，新的方案如Baloo、flookup、cq和caulk+相继推出。Lasso引入的改进允许在表格具有特定结构时避免全表提交，并确保证明者只为查找操作访问的表格条目支付

HyperPlonk（2022）

HyperPlonk基于Plonk思想，使用多变量多项式和sumcheck协议检查约束执行，支持高度约束而不牺牲证明者运行时间。它避免了FFT的需要，使证明者时间与电路大小线性相关，为小型字段引入了新的排列IOP，并通过基于sumcheck的批量开放协议降低了证明者的负担。

折叠方案（2008/2021）

Nova引入了折叠方案的概念，这是实现增量可验证计算（IVC）的新方法。IVC的概念最早由Valiant提出，展示了如何将两个长度为k的证明合并为一个长度为k的单一证明。其核心思想是，可以通过递归证明，证明从步骤i到步骤i+1的执行是正确的，并验证一个证明，以显示从步骤i-1到步骤i的转换是正确的。Nova巧妙地处理了统一计算问题，并通过引入Supernova来扩展以处理不同类型的电路。Nova采用了R1CS的放宽版本，并在友好的椭圆曲线上实现。使用友好曲线循环（如Pasta曲线）实现IVC也被用于Pickles，这是Mina实现简洁状态的关键组件。然而，折叠概念与递归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(log^2n)的证明大小，具有快速的证明者和验证者，不需要信任设置，并被认为是后量子安全的。它们首次被Starkware/Starknet采用，结合Cairo vm使用。STARKs的关键引入包括代数中间表示（AIR）和FRI协议（快速Reed-Solomon交互式Oracle证明的接近性），也被其他项目（如Polygon Miden, Risc0, Winterfell, Neptune）采用，或见到了一些组件的适应（如ZK-Sync的Boojum, Plonky2, Starky）。

Ligero（2017）

Ligero引入了一个证明系统，其证明大小为O(√n)，其中n是电路的大小。通过将多项式系数以矩阵形式排列，并使用线性编码，Ligero实现了较小的证明大小和较高的效率。基于Ligero的进一步发展，如Brakedown，引入了与字段无关的多项式承诺方案的概念，为零知识证明技术的通用性和适用性提供了新的可能。

一些新的发展

随着不同证明系统在实践中的应用，每种方法的优点逐渐显现，促进了新的技术发展。例如，plonkish算术化提供了一种简单的方法来包含自定义门和查找证明；FRI作为多项式承诺方案（PCS）展现了出色的性能，促进了Plonky等新系统的出现。同样地，AIR中使用的大乘积检查改进了性能并简化了内存访问证明。基于哈希函数的承诺方案因为其在硬件中的速度或是新的SNARK友好哈希函数的引入而变得流行。

新的多项式承诺方案（2023）

随着基于多变量多项式的高效SNARKs（如Spartan或HyperPlonk）的出现，对这类多项式适用的新承诺方案兴趣增加。新提出的承诺方案，如Binius、Zeromorph和Basefold，为多线性多项式提供了新的形式，展现了在效率和表示数据类型上的优势，同时在二进制字段上工作，减少了与字段无关的开销。

可定制约束系统（2023）

CCS（可定制约束系统）在捕获R1CS、Plonkish和AIR算术化的同时，推广了R1CS，而没有引入额外开销。结合Spartan IOP使用CCS产生了SuperSpartan，支持高度约束而不增加证明者的加密成本。特别是，SuperSpartan为AIR提供了一个具有线性时间证明者的SNARK，进一步推动了零知识证明技术的发展和应用。

结论

本文综述了自20世纪80年代中期以来，零知识简洁非交互式证明（SNARKs）的重要发展历程。得益于计算机科学、数学及硬件技术的进步，结合区块链技术的兴起，我们见证了更高效的SNARKs技术的诞生，这为社会带来可能的变革性应用开辟了新的道路。研究人员和工程师针对实际需求，不断对SNARKs进行优化和调整，聚焦于缩减证明尺寸、减少内存消耗、实现透明配置、保障后量子安全性、以及优化证明者与验证者的时间效率。尽管SNARKs和STARKs最初被视为两条独立的发展路径，但随着时间的推进，这两者之间的界限正逐渐模糊，展现出一种趋势，即尝试融合两种系统各自的优势，比如将不同的算术化方案与新兴的多项式承诺方案结合起来。我们期待未来将会有更多新型的证明系统问世，它们的性能将持续提升。然而，要让一些现有系统跟上这些快速的发展步伐，可能需要时间去适应，除非我们能够便捷地采用这些新工具，而无需对现有的核心基础设施进行重大修改。