The historical development of ZK technology

Written by:Lambda Class

编译：白丁、Faust、Nickqiao

英文原文发布于 2024 年 2 月 17 日

Zero knowledge proof (ZK Proofs) 是功能强大的密码学原语，允许一方（证明者）在不透露任何私密信息的情况下，使另一方（验证者）相信某个给定的声明是真实有效的。近年来 ZK 在可验证私密计算、为计算机程序提供有效性证明以及Blockchain领域获得了广泛关注，并且对世界的发展产生了重大的积极作用。

虽然 ZK 是新兴技术，但其基本思想和概念可以追溯到上世纪 80 年代。在与比特币和以太坊等Blockchain结合后，ZK 技术的发展显著加速，becauseBlockchain可以通过 SNARK 和 STARK 进行有效性证明，极大程度的增强可扩展性，这使 ZK 在Blockchain领域中炙手可热。

正如 Starkware 创始人 Eli Ben-Sasson 所言，近年来我们见证了密码学证明系统的「寒武纪大爆发」，每种证明系统各有独特的优势和劣势，并且在设计时进行了权衡。硬件的进步、更好的算法、新的论点和周边工具，都刺激了 ZK 系统的性能提升及新式系统的诞生。许多证明系已经在实际应用中被采用，而人们仍在不断扩展 ZK 的边界。

这也促使人们深入思考一个问题：是否有一个适用于所有应用的通用 ZK 证明系统？对此我们认为这种可能性不大，原因有三点：

1. 应用程序的多样性；

2. 不同的约束类型（包括内存、验证时间、证明时间）；

3. 对鲁棒性的需求（如果一种证明系统被黑客攻破，我们仍然可以切换到其他系统作为保险）。

基于上述理由，ZK 证明系统理应是多样性的。但即使证明系统的种类很多，也一定有一个显著的共性：ZK 证明可以被快速的验证，并且拥有一个验证层，可以很容易地适应新的证明系统，以解决其依附的基础层（如以太坊）的相关困难。

在 ZK 领域中，zk-SNARK 被频繁提及。它是实现Zero knowledge proof的一种形式，通过使用复杂的数学工具，如双线性配对和算术电路，来实现高效的Zero knowledge proof。zk-SNARK 的特点是证明过程简洁化、非交互式，证明者和验证者之间只需要单次通讯不需要多次交互。此外，zk-SNARK 的证明尺寸非常短小，验证效率高，适合在资源有限的环境中使用。

而 zk-STARK 是另一种常见的形式，旨在克服 zk-SNARK 的某些局限性。zk-STARK 不依赖于可信设置，使用更透明的数学构造系统，如多项式承诺和有限域运算、哈希碰撞等，来生成和验证证明。zk-STARK 比 zk-SNARK 更具可扩展性，适用于更大规模的计算，证明生成速度更快，但是 Proof 本身的尺寸通常较大。

可以说，zk-SNARK 和 zk-STARK 都是零知识证明中常用的形式，但它们在透明度、可扩展性、证明大小等方面有所不同。

总体来看，一个 ZK 证明系统通常包括 PIOP（多项式交互式预言机）和 PCS（多项式承诺方案）两大部分。常见的 PIOP 方案包括 PLONKish、GKR 等，而常见的 PCS 方案包括 FRI，KZG，IPA 等，比如 Zcash 版本的 Halo2 使用了 Plonkish+IPA 的实现方式，至于 zk-STARK 其实可以当成是一种基于 FRI 的特殊的 zk-SNARK。

如果更详细的说，不同类型的证明系统会使用不同的多项式承诺方案 (PCS)、算术化方案、交互式预言机证明 (IOP) 或概率可检查证明 (PCP)。

进一步说，不同的 ZK 证明系统往往在如下指标上有所不同：

• 密码学假设：抗碰撞哈希函数、椭圆曲线上的离散对数问题、指数知识

• 透明设置 vs 可信设置

• 生成证明的耗时：线性 vs 超线性

• 验证证明的耗时：常数时间、对数时间、次线性、线性

• 证明尺寸的大小

• 递归的简易性

• 算术化方案

• 单变量 vs 多变量多项式

下文中我们将简要谈及 ZK 技术的起源，探索其基本的构建模块，概述不同 ZK 证明系统的兴起和衰落过程。同时，本文并不对证明系统本身进行详尽分析，而是着重介绍那些对该领域产生深远影响的人，毕竟任何行业的发展只有通过先驱者的伟大想法并诉诸实践，才有可能实现。

zk-SNARK 的历史发展脉络

起源：20 世纪 80~90 年代

正如我们所提到的，零知识证明并不是新概念，其定义、基础、重要定理，甚至相关的重要协议，早在上世纪 80 年代中期就已经出现，首次出现是在是在 Goldwasser、Micali(Algorand 创始人 ) 和 Rackoff 的论文《The Knowledge Complexity of Interactive Proof Systems》中。

and如今我们用来构建 ZK-SNARK 技术的关键思想和协议，在 20 世纪 90 年代就被出，比如 Sumcheck 协议，将对多元多项式求值总和的声明，简化为在椭圆曲线上随机选择的点进行单一求值，该协议为 ZK 技术奠定了重要基础。

所以，ZK 思想的萌芽实际上远远早于比特币的出现，但在当时普遍缺乏 ZK 的合适用例，人们也无法提供满足 ZK 证明系统所需的强大算力，毕竟互联网和硬件设备在上世纪 90 年代并不发达。

GKR 协议（2007)

GKR（Goldwasser-Kalai-Rothblum）是一种交互式协议，证明者的运行时间与电路中逻辑门的数量呈线性相关，而验证者的耗时则与电路大小呈次线性关系。在 GKR 协议中，证明者和验证者需要对一个有限域上的双输入算术电路运行结果达成一致，该电路的深度为 d，第 d 层为输入层，第 0 层为输出层。协议从关于电路输出的声明开始，通过递归将其简化为对上一层的声明。最后，我们可以将对输出的声明转换为对电路输入参数的声明，这很容易被验证。可以说，GKR 协议是在前面提及的 Sumcheck 协议基础上进行了高度简化的。

KZG 多项式承诺方案 (2010)

2010 年，三名 ZK 领域的专家——来自德国研究机构 MPI-SWS 的 Kate，来自加拿大密码学公司 Certicom Research 的 Zaverucha，以及来自滑铁卢大学的 Goldberg 联合发表了一篇论文《Constant-Size Commitments to Polynomialsand Their Applications》。该论文提出了一种使用双线性对群的多项式承诺方案，名为 KZG。

该承诺由一个单独的群元素组成，提交者可以高效地揭示多项式的任何正确求值，借助批处理技术，可以对多个多项式的求值进行揭示。KZG 承诺成为了一些知名 ZK 证明系统的基本构建模块之一（比如以太坊 PES 小组用的 halo2），更是在以太坊的 EIP-4844 中起到了核心作用。若要更直观地了解批处理技术的概念，可以参考关于 Mina-Ethereum 桥的文章 Mina-Ethereum bridge。

参考资料：https://blog.lambdaclass.com/mina-to-ethereum-bridge/

基于椭圆曲线的实用 ZK-SNARK 系统（2013）

ZK-SNARK 的第一个实用结构出现在 2013 年，需要一个预处理步骤来生成证明密钥和验证密钥，并且是随程序或电路特定的，没有泛用化。这些密钥的尺寸可能非常大，并取决于秘密参数本身；若这种保密性被破坏，攻击者就可以伪造出证明。在这种实用的 ZK-SNARK 系统中，要将代码转换为可以被证明的形式，需要将代码编译为一组数学形式的多项式约束。

起初，上述过程必须手动完成，既耗时又容易出错。后来针对该方向的技术更迭，主要试图解决下述核心问题：

1. 提供更高效的证明

2. 减少预处理的次数

3. 实现通用的而非电路特定的设置

4. 避免可信设置

5. 开发使用高级语言描述电路的方法，而不是手动编写多项式约束

Pinocchio 协议（2013）

Pinocchio 协议是第一个实际可用的 zk-SNARK 系统，基于二次算术程序（QAP），最初的证明大小为 288 字节。Pinocchio 的工具链提供了一个将 C 语言编译为算术电路的编译器，它可以进一步转换为 QAP。Pinocchio 协议要求验证者生成密钥，这些密钥并不通用，而是由电路特定的。该证明系统生成和密钥设置的渐进时间复杂度与计算规模呈线性关系，验证时间与公共输入和输出的大小呈线性关系。

Groth16(2016)

Groth 引入了一种新的 ZK 明算法，在处理 R1CS 上具有更高的性能。R1CS 即 Rank-1 Constraint System，一阶约束系统，是 zk-SNARK 中的一种多项式约束形式。Gorth 的证明是数据规模最小的（仅包含三个群元素），且验证速度很快，只需进行三个配对运算，以及一个使参考字符串结构化的预处理步骤。但 Gorth 主要的缺点是每个需要证明的程序都需要进行不同的可信设置，这在实际应用中相当不便。

后来 Groth16 被用于 ZCash，后者是一个比较有名的隐私区块链项目（Starkware 创始人 Eli 参与做的）。

Bulletproofs 与 IPA（2016）

前面提到的 KZG 多项式承诺方案，其一大弱点是需要可信设置。Bootle 等人提出了一种有效的零知识证明系统，该系统对满足内在乘积关系的 Pedersen 承诺的开启进行了分析。内积证明具有线性复杂度的证明耗时，证明者和验证者之间的交互次数是对数级的，但验证时间是线性的。此外 Bootle 等人还开发了一种不需要可信设置的多项式承诺方案。这些思想后来被 Halo2 和 Kimchi 等采用。

Sonic、Marlin 和 Plonk（2019）

Sonic、Plonk 和 Marlin 解决了 Groth16 算法中每个程序都需要可信设置的问题，引入了通用且可更新的结构化参考字符串（用来实现仅需一次的可信设置）。其中，Marlin 提供了一个基于 R1CS 的证明系统，并且成为了 Aleo 的核心技术。

而 Plonk 引入了一种新的算术方案（后来被称为 Plonkish）以及使用 grand-product 来检查复制约束。Plonkish 还允许引入用于特定操作的专用电路逻辑门，即所谓的「自定义门」。许多知名的区块链项目方都用到了 Plonk 的定制化版本，包括 Aztec、zkXiaobai NavigationSync、Polygon zkEVM、Mina、以太坊 PSE 小组和 Scroll 等。

Spartan（2019）

Spartan 为使用 R1CS 描述的电路提供了一个 IOP，利用了多变量多项式和求和检验协议的特性。通过使用合适的多项式承诺方案，它实现了一套具有透明性的 zk-SNARK 系统，并且生成证明的时间复杂度是线性的。

Lookups(2020)

Gabizon 和 Williamson 于 2020 年在论文中提出了 plookup，利用 grand-product 证明某个值包含在预先计算出的真值表中，展示了如何将 plookup 参数引入 Plonk 算法。

然而，这些 lookup arguments 有一个共同的问题，证明者需要耗费巨大成本建立完整的真值表，因此之前围绕着 Lookups 的工作都致力于将证明成本减少。

后来 Habck 在论文中引入了 LogUp，它使用对数导数将 grand-product 检查转化为倒数之和。LogUp 对于 Polygon zkEVM 的性能提升至关重要，因为他们需要将整个真值表拆分为多个 STARK 模块。这些模块必须正确链接，而跨表查找可以强制实现这一点。此后 LogUp-GKR 的引入又通过 GKR 协议提高了 LogUp 的性能。

Caulk 是第一个使证明时间与真值表大小呈亚线性关系的方案，它的预处理时间复杂度为 O(NlogN)，存储占用的空间复杂度为 O(N)，其中 N 是真值表大小。随后又出现了其他方案，如 Baloo、flookup、cq 和 caulk+。此外，Lasso 提出了若干改进方案，避免在真值表具有特定结构时对其进行承诺。

HyperPlonk（2022）

HyperPlonk 在论文《HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates》中被提出。HyperPlonk 基于 Plonk 的理念，采用多变量多项式。它不使用除法来检查约束的执行，而是依赖于求和检验协议。同时，它还支持高阶约束，而不会影响证明生成的时间。

由于使用了多变量多项式，无需执行快速傅里叶变换（FFT），证明生成的时间与电路规模成线性关系。HyperPlonk 还引入了一种适用于小字段的新置换 IOP，并且采用基于求和检验的协议，减少了证明者的工作量、证明大小，以及验证时间。

使用防碰撞哈希函数的 ZK 证明系统

在 2013 年 Pinocchio 被提出的同时，有一些关于生成电路 / 算术化方案的方案，这些方案可以证明虚拟机对指令的执行结果正确。尽管为虚拟机开发算术化方案比为某些程序编写专用电路更复杂或效率更低，但它却有一个重要优势：无论程序多复杂，只需证明其在虚拟机中是正确执行的即可。

TinyRAM 中的一些想法后来在 Cairo 虚拟机的设计中得到了改进，随后又有了 zk-evm 和通用 zkvm 等。在证明系统中使用抗碰撞的哈希函数消除了对可信设置或椭圆曲线操作的需求，但代价是证明时间更长。

TinyRAM（2013）

在「SNARKs for C」中，他们基于 PCP 开发了一种证明系统，用于证明 C 语言编写的程序的执行结果正确。该程序被编译为 TinyRAM，一种简化的 VM。该 VM 具有字节级可寻址的随机存储器，电路大小在计算规模上呈准线性增长，可以高效地处理循环、控制流和内存访问等操作。

其中，PCP 指 Probabilistically Checkable Proof，即概率可检查证明，验证者只需阅读证明中随机选择的一小部分内容，就能以很高的置信度检查证明的有效性。与验证者需要检查整个证明的传统证明系统不同，PCP 只需有限的随机性即可实现高效验证。

Ligero（2017）

Ligero 引入了一套证明系统，该系统可实现大小为 O(√￣n) 的证明，其中 n 是电路的大小。它以矩阵形式排列多项式系数。Brakedown 基于 Ligero 构建，并引入了领域无关的多项式承诺方案的概念。

STARKs（2018）

STARKs（Scalable Transparent ARguments of Knowledge）由 Eli Ben-Sasson 等人于 2018 年提出。它们实现了(log⁡) 的证明复杂度，具有快速的验证速度，不需要可信设置，并且被推测为后量子Safety。它们被 Starkware/Starknet 与 Cairo 虚拟机一起投入采用。其关键创新包括代数中间表示（AIR）和快速 Reed-Solomon 交互式 Oracle 接近证明（FRI）协议。另外，STARKs 也被许多知名的区块链项目所使用（如 Polygon Miden、RiscZero、Winterfell、Neptune 以及 ZeroSync、zkSync 等）。

新的发展方向

不同的证明系统在实际应用中的使用展示了不同方法的优点，并推动了 ZK 的发展。例如，Plonkish 的算术化方案提供了一种简单的方法，来包含自定义逻辑门和 lookup arguments；FRI 已经显示出作为 PCS 的出色性能，促成了 Plonky 的诞生。同时，在 AIR 中使用 grand-products 检查（带来了预处理的随机化 AIR）提高了其性能并简化了内存访问参数。zk-STARK 由于在生成效率上更好，且有越来越多的 ZK 友好型哈希函数被引入，而越来越受欢迎。

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

随着基于多变量多项式的高效 SNARK（如 Spartan 或 HyperPlonk）的出现，人们对适用于此类多项式的新承诺方案的兴趣日益增加。Binius、Zeromorph 和 Basefold 都提出了新的方式来承诺多线性多项式。Binius 的优势在于表示数据类型时没有额外开销（而许多其他证明系统至少使用 32 位字段元素来表示单个位），并且在二进制域上工作。该承诺方案采用了为领域无关而设计的 brakedown。Basefold 将 FRI 推广到除 Reed-Solomon 之外，从而实现了领域无关的多项式承诺方案（PCS）。

领域无关是多项式承诺方案的一个性质，指多项式承诺方案中，承诺过程不依赖于任何特定领域的特定属性。这意味着可以对任何代数结构的多项式做出承诺，如有限域、椭圆曲线，甚至整数环。

可定制约束系统（2023）

CCS 泛化了 R1CS，同时捕捉了 R1CS、Plonkish 和 AIR 的算术化，而没有额外开销。使用 CCS 与 Spartan IOP 结合可以产生 SuperSpartan，它支持高维度约束，而证明者无需承担与约束阶数成比例的加密成本。特别地，SuperSpartan 为 AIR 提供了一个具有线性时间证明的 SNARK。

Summarize

这篇文章综述了自上世纪 80 年代中期以来 ZK 技术的进展。计算机科学、数学和硬件的进步，加上区块链的引入，催生了新的、更高效的 ZK 证明系统出现，为许多可能改变社会的应用开辟了道路。

研究人员和工程师们根据需求提出了 ZK 系统的改进方案，重点围绕在证明尺寸大小、内存使用程度、透明度、抗量子Safety性、证明时间和验证时间等方面。虽然一直以来，ZK 的主流实现方案有两大类（SNARK 与 STARKs），但这两者之间的界限已经逐渐模糊，不同证明系统的优势正被结合起来，例如结合不同的算术化方案与新的多项式承诺方案。

我们可以预期，新的 ZK 证明系统将继续涌现，且性能会不断提升。对于使用这些证明系统的应用来说，如果不能跟随最新技术的迭代发展，不断重构并应用最新的算法，现在的领先地位也只是暂时的。

The article comes from the Internet:The historical development of ZK technology

相关推荐: OpenAI CTO 剧透 AGI 关键词：十年内出现、极其先进、智能系统

资深记者尖锐追问 OpenAI 训练数据来源。 编译：木沐 编辑：文刀 7 月初，在约翰霍普金斯大学，资深科技记者、播客 Pivot 的联合主持人 Kara Swisher 与 OpenAI CTO Mira Murati 展开了一场火药味十足的对话，计算机科…