零知识证明的历史发展及其重要影响深度解析

零知识、简洁、非交互式知识论证（zk-SNARKs）作为一种强大的密码学原语，正在重塑我们对隐私保护和可验证计算的认知。这种技术允许证明者在不泄露任何额外信息的情况下，向验证者证实某个陈述的真实性。随着区块链技术的蓬勃发展，zk-SNARKs在可验证私有计算领域的应用价值日益凸显，不仅能够验证程序执行的正确性，还能显著提升区块链的可扩展性。正如我们在相关文章中所探讨的，这项技术正在对世界产生深远影响。

zk-SNARKs实际上是一个涵盖多种证明系统的总称，这些系统采用不同的多项式承诺方案、算术化方案以及交互式预言证明或概率可检查证明等技术。虽然这些概念可以追溯到20世纪80年代中期，但直到比特币和以太坊的出现才真正加速了其发展进程。特别值得一提的是，零知识证明（在这个特定应用场景中常被称为有效性证明）为区块链扩展提供了创新解决方案。正如本-萨森(Ben-Sasson)在相关文章中所描述的，过去几年见证了密码学证明技术的”寒武纪大爆发”。

每个证明系统都有其独特的优势和局限性，设计时都需要权衡各种因素。随着硬件技术的进步、算法的优化以及新论证方法的出现，性能不断提升，新型系统不断涌现。许多系统已经投入实际应用，我们正在不断突破技术边界。关于未来是会出现一个通用证明系统还是多个针对不同需求的专用系统，我们认为单一系统统治所有场景的可能性不大，这主要基于三个原因：应用场景的多样性、各类资源约束（如内存、验证时间、证明时间）的差异，以及对系统稳健性的需求（当一个系统被攻破时需要有替代方案）。

尽管证明系统经历了巨大变革，但它们都保留了一个关键特性：快速验证能力。建立一个能够验证证明并轻松适应新系统的中间层，可以有效解决修改底层基础设施（如以太坊）带来的挑战。zk-SNARKs具有多方面的特征，包括密码学假设（抗碰撞哈希函数、椭圆曲线离散对数问题等）、透明度与可信设置的平衡、证明者和验证者的时间效率、证明大小、递归能力、算术方案选择，以及单变量与多元多项式的应用等。

本文将追溯SNARK技术的发展历程，探讨其基础构建模块，并分析不同证明系统的兴衰演变。需要说明的是，本文并非对证明系统的全面分析，而是聚焦于那些对我们产生重要影响的技术突破。当然，所有这些进步都建立在领域先驱者的杰出工作和创新思想之上。

技术溯源

正如前文所述，零知识证明并非新生事物。其定义、基础理论、重要定理乃至关键协议都可以追溯到20世纪80年代中期。我们构建现代SNARK所依赖的一些核心思想和协议，如sumcheck协议，早在90年代就已提出，甚至GKR协议在比特币诞生前（2007年）就已出现。早期采用面临的主要障碍是缺乏强有力的应用场景（90年代互联网尚未普及）以及所需的计算能力不足。

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

零知识证明领域正式进入学术视野始于戈德瓦瑟、米卡利和拉科夫的开创性论文。该研究首次提出了完备性、健全性和零知识的概念，并为二次剩余性和非剩余性问题提供了具体构造方法。关于这段历史的更多讨论，可以参考相关视频。

Sumcheck协议(1992)

由Lund、Fortnow、Karloff和Nisan在1992年提出的Sumcheck协议成为简洁交互式证明中最关键的构建模块之一。该协议能够将对多变量多项式求和的声明简化为在随机选择点上的单一评估，这一创新为后续发展奠定了基础。更多细节可参考我们关于Sumcheck协议的专门文章。

GKR协议(2007)

GKR协议作为一种交互协议，其证明者运行时间与电路门数呈线性关系，而验证者运行时间则是电路大小的亚线性。该协议中，证明者和验证者就有限域上的二叉输入算术电路达成一致，通过递归将从电路输出层开始的声明逐步转化为对输入的声明，这些转化过程都借助sumcheck协议实现。

KZG多项式承诺方案(2010)

凯特、扎韦鲁查和戈德堡在2010年提出的基于双线性配对群的多项式承诺方案成为多项技术突破的基础。该方案的承诺仅需单个群元素，却能高效验证多项式的任意正确评估，并支持批处理验证。KZG承诺为Pinocchio、Groth16和Plonk等高效SNARK提供了核心构建模块，也是EIP-4844的核心技术。关于批处理技术的直观解释，可以参考我们关于Mina-Ethereum桥的文章。

基于椭圆曲线的实用SNARK

2013年见证了第一个实用SNARK结构的诞生。这些早期结构需要进行预处理来生成证明和验证密钥，且针对特定程序/电路设计。密钥规模可能很大，且依赖于各方不知晓的秘密参数，否则可能导致证明伪造。将代码转换为可证明代码需要先将其编译为多项式约束系统，这一过程最初需要人工完成，既耗时又容易出错。后续发展主要致力于解决以下关键问题：提升证明者效率、减少预处理、实现通用设置而非电路特定设置、避免可信设置，以及开发高级电路描述方法。

Pinocchio(2013)

作为首个实用化的zk-SNARK，Pinocchio基于二次算术程序(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创新性地提出了Plonkish算术方案和复制约束的宏积检查方法。Plonkish还支持为特定操作设计专门门电路（定制门）。Aztec、zkSync、Polygon ZKEVM、Mina’s Kimchi、Plonky2、Halo 2和Scroll等多个项目都采用了Plonk的定制版本。

查找参数(2018/2020)

Gabizon和Williamson在2020年提出的plookup利用大乘积检查来证明值包含在预计算表中。虽然查找参数的概念在Arya中已有提及，但其构造需要确定查找多重性，影响了效率。PlonkUp展示了如何将plookup参数整合到Plonk中。

这些查找参数的主要问题是证明者需要为整个表格付出代价，而不论实际查找次数。Haböck提出的LogUp使用对数导数将大乘积检查转化为倒数之和，在Polygon ZKEVM的性能优化中发挥了关键作用。LogUp-GKR则结合GKR协议进一步提升了LogUp性能。

Caulk是首个实现预处理时间O(NlogN)和存储O(N)的方案，使证明时间在表格规模下呈非线性。后续出现的Baloo、flookup、cq和caulk+等方案持续优化这一领域。Lasso通过避免对具有特定结构表格的承诺，使证明者仅需为实际查找的表格条目付费。Jolt则利用Lasso通过查找证明虚拟机执行。

Spartan(2019)

Spartan利用多元多项式和求和协议的特性，为R1CS描述的电路提供交互式预言证明(IOP)。配合适当的多项式承诺方案，它能产生具有线性时间证明器的透明SNARK。

HyperPlonk(2022)

HyperPlonk将Plonk思想扩展到多元多项式领域。它不依赖商来检查约束执行，而是基于和检查协议，支持高度约束而不影响证明者运行时间。由于采用多元多项式，无需执行FFT，证明者运行时间与电路规模呈线性关系。HyperPlonk引入了适合小字段的新排列IOP和基于和检查的批量打开协议，减少了证明者工作量和证明大小，同时提升了验证效率。

折叠方案(2008/2021)

Nova提出的折叠方案为实现增量可验证计算(IVC)提供了新方法。IVC概念最早由Valiant提出，展示了如何将两个长度为k的证明合并为一个长度相同的证明。Nova通过递归证明处理步骤间转换的正确性，后来通过Supernova扩展到处理不同类型电路。

Nova使用R1CS的宽松版本，在友好椭圆曲线上工作。类似Pickles等项目利用友好曲线循环（如Pasta曲线）实现简洁状态。值得注意的是，折叠概念不同于递归SNARK验证，更接近于批处理证明的累加器思想。Halo引入累加器作为递归证明组合的替代方案。Protostar则为Plonk提供支持高度门和向量查找的非均匀IVC方案。

基于抗碰撞哈希函数的方案

与Pinocchio同期，一些关于生成电路/算术方案的新思路开始出现，这些方案能够验证虚拟机执行的正确性。虽然为虚拟机设计算术可能比为特定程序编写专用电路更复杂或效率更低，但其优势在于能够通过证明程序在虚拟机中的正确执行来验证任意复杂度的程序。TinyRAM的创新思想后来在Cairo虚拟机及后续zk-evms或通用zkvms的设计中得到继承和发展。使用抗碰撞哈希函数消除了对可信设置或椭圆曲线运算的需求，但代价是更长的证明。

TinyRAM(2013)

在SNARK for C之后，研究人员开发了基于PCP的SNARK来验证C程序的正确执行，这些程序被编译为精简指令集计算机TinyRAM。该计算机采用哈佛架构，具有字节级可寻址随机存取存储器。通过利用非确定性，电路规模与计算规模呈拟线性关系，有效处理任意和数据相关的循环、控制流和内存访问。

STARKS(2018)

Ben Sasson等人2018年提出的<a href="https://eprint.iacr.org/2018/046?ref=blog.lambdaclass.com" target="_