测量SNARK性能：前端与后端

A SNARK (简洁非交互式知识证明) 是一种重要的加密原语，应用于区块链的可伸缩性（例如，L2 rollups）和隐私中。SNARKs 允许某人向一个不可信的验证器 V（例如，以太坊区块链）证明他们知道某些数据（例如，一批有效的交易）。一种简单的证明方法是将数据发送给 V，V 然后可以直接验证其有效性。SNARK 达到同样的目的，但具有更好的成本效益。具体来说，SNARK 证明的长度应该短于简单方法中的数据本身。（有关更多细节，请参见我的教科书草稿，Proofs, Arguments, and Zero Knowledge link。有关 SNARK 的介绍，请查看 Sarah Meicklejohn 在 a16z crypto 夏季研究系列 中的演讲 link）。

SNARK 的验证成本可以变化，但通常被很好理解，并且通常相当好。例如，PlonK 证明在以太坊上的验证成本约为 290,000 gas，而 StarkWare 的证明成本约为 500 万 gas。尽管 SNARK 可能应用于多种场景，即使在区块链之外，例如，启用快速但不可信的 服务器 和 硬件。

但是，由于 SNARK 验证通常是廉价的，适用性的主要决定因素是 SNARK 证明者 P 的成本。在这篇文章中，我解释了如何估算这些成本，以确定何时合理使用 SNARK，以及 SNARK 将如何在未来改善。值得注意的是，这是一个快速发展的领域，本文中讨论的多个项目正在积极改善其性能。

首先：SNARK 如何部署

在 SNARK 部署中，开发者通常编写一个计算机程序 ψ，该程序将证明者声称知道的数据 w 作为输入，并检查 w 是否有效。例如，在 rollups 中，程序将检查 w 中的所有交易是否已数字签名、不会导致任何账户余额低于零等。然后将程序 ψ 输入到一个 SNARK 前端 ，将其编译成更适合应用 SNARK 技术的格式。这个 SNARK 友好的格式被称为 中间表示 (IR)。

通常，IR 是某种等价于 ψ 的电路可满足性实例。这意味着电路 C 将数据 w 作为输入，以及一些通常称为“非确定性建议”的额外输入，并在 w 上运行 ψ。建议输入用于帮助 C 运行 ψ，同时保持 C 小。例如，每当 ψ 将两个数字 x 和 y 相除时，商 q 和余数 r 可以作为建议提供给 C ，而 C 仅需检查 x = qy + r 。这个检查的成本低于让 C 执行完整的除法算法来从头计算 q 和 r。

最后，将 SNARK 应用于电路可满足性 C 。这称为 SNARK 后端。对于一些高结构性问题，例如 矩阵乘法、Rollup 和 几个图问题，已知的 SNARK 可以避免这种前端/后端范式，从而实现更快的证明者。但是，本文的重点是通用 SNARK。

正如我们将看到的，SNARK 后端的证明者成本随着 C 的大小而增长。保持 C 小可能具有挑战性，因为电路是在表达计算时的极有限格式。电路由 门 通过 线 连接而成。每个门 g 需要一些值并对这些值应用一个 非常 简单的函数。结果随后通过来自 g 的线馈送到“下游”门。

SNARK 可扩展性：真正需要多少时间？

关键问题是，SNARK 证明者所需的时间与直接对数据重新执行 ψ 相比，增加了多少？答案是 SNARK 的 证明者开销，相对于 直接见证检查。后者指的是在简单证明中，P 将 w 发送给 V，V 通过对其执行 ψ 来检查 w 的有效性。

将证明者开销分解为“前端开销”和“后端开销”是有帮助的。如果逐门评估电路 C 的费用是运行 ψ 的 F 倍，我们称前端开销为 F。如果将后端证明者应用于 C 的费用是逐门评估 C 费用的 B 倍，我们称之为后端开销 B。总的证明者开销是 F·B 的乘积。即使 F 和 B 各自较小，这种乘积开销可能是相当可观的。

在实践中，F 和 B 都可以粗略地都在 1000 或更大。这意味着证明者相对于直接见证检查的总开销可能在 100 万至 1000 万或更多。一个在笔记本电脑上运行仅一秒的程序，可以轻松导致 SNARK 证明者需要几十或几百天的计算时间（单线程）。幸运的是，这项工作通常在不同程度上可以并行化（具体取决于 SNARK）。

总之，如果你想在今天的应用程序中使用 SNARK，则必须符合以下三种情况之一：

1. 直接见证检查在笔记本电脑上需要的时间远少于一秒。
2. 直接见证检查特别便于在电路中表示，因此前端开销很小。
3. 你愿意等待几天以完成 SNARK 证明者，并/或支付巨额并行计算资源。

本文的其余部分解释了前端和后端开销的来源，以及我如何估算不同 SNARK 的这些开销。然后我们将转向改善的前景。

分离前端和后端

完全将前端与后端分开可能会很有挑战性，因为不同的后端支持不同类型的电路。因此，前端可能会根据它们期望接口的后端而有所不同。

SNARK 后端通常支持所谓的算术电路，这意味着电路的输入是某个有限域的元素，而且电路的门执行两个域元素的加法和乘法。这些电路大致对应于直线计算机程序（没有分支、条件语句等），这些程序在性质上是代数的——即，其基本数据类型是领域元素。

大多数后端实际上支持算术电路的广义，通常称为 Rank-1 Constraint Satisfaction (R1CS) 实例。唯一的例外是 Groth16 及其前身，这些 SNARK 可以使其支持其他 IR。例如，StarkWare 使用名为代数中间表示 (AIR) 的东西，这和一个概念非常相似，称为 PlonKish 代数化，可以由 PlonK 和其他后端支持。一些后端支持更一般的 IR 的能力可以减少产生这些 IR 的前端的开销。

后端在本地支持的有限域方面也有所不同。在下一部分中我将进一步讨论这个问题。

各种前端方法

一些（非常特殊的）计算机程序自然对应于算术电路。一个例子是执行在某个字段上进行的朴素矩阵乘法的计算机程序。但是大多数计算机程序既不是直线的也不是代数的。它们通常涉及条件语句、整数除法或浮点算术等操作，这些操作自然对应于有限领域算术，并且更多。在这些情况下，前端开销将是相当大的。

一种流行的前端方法是生成电路，该电路本质上逐步执行某个简单 CPU，也称为虚拟机（VM）。前端设计者指定一组“基本操作”，类似于真实计算机处理器的汇编指令。希望使用前端的开发者将直接在汇编语言中编写“见证检查程序”，或者使用某些高级语言（例如 Solidity），并将其程序自动编译为汇编代码。

例如，StarkWare 的 Cairo 是一种非常有限的汇编语言，其中的汇编指令大致允许对有限域进行加法和乘法，函数调用以及对不可更改的（即，一次写入）内存的读取和写入。Cairo VM 是一种冯·诺依曼架构，这意味着前端生成的电路本质上将 Cairo 程序作为公共输入，并在见证上“运行”该程序。Cairo 语言是图灵完备的——尽管其指令集有限，但它可以模拟更标准的架构，尽管这样做可能很昂贵。Cairo 前端将执行 T 个基本指令的 Cairo 程序转化为所谓的“具有 T 行和约 50 列的二次 AIR”。对此 确切含义 并不重要，但就 SNARK 证明者而言，这对应于每个 T 步骤之间有 50 到 100 个门的电路。

RISC Zero 采取了与 Cairo 相似的方法，但虚拟机是所谓的 RISC-V 架构，一种开源架构，拥有丰富的软件生态系统并日益受欢迎。由于指令集非常简单，设计一个有效的 SNARK 前端来支持它可能相对可行（至少相对于像 x86 或 ARM 这样的复杂架构）。截至 5 月，RISC Zero 正在将执行 T 个基本 RISC-V 指令的程序转化为具有 3 T 行和 160 列的五次 AIR。这对应于每个 RISC-V CPU 步骤的电路至少有 500 个门。预计在不久的将来会有更多改进。

各种 zkEVM 项目（例如，zkSync 2.0、Scroll、Polygon 的 zkEVM）将虚拟机（显而易见）视为以太坊虚拟机。将每个 EVM 指令转换为等效的“工具”（即实现该指令的优化电路）的过程比对于更简单的 Cairo 和 RISC-V 架构要复杂得多。由于这个和其他原因，一些 zkEVM 项目 并未直接实现 EVM 指令集，而是将高级 Solidity 程序编译为其他汇编语言，然后再将其转换为电路。这些项目的性能结果尚待公布。

“CPU 模拟器”项目，如 RISC-V 和 Cairo，生成一个可以处理其关联汇编语言中所有程序的单一电路。另一种替代方法是“ASIC 方式”，为不同程序生成不同的电路。该 ASIC 方式可以为某些程序产生较小的电路，特别是当程序在每个时间步骤上执行的汇编指令不依赖于程序的输入时。例如，它可能完全避免直线程序如简单矩阵乘法的前端开销。但 ASIC 方法似乎也高度有限；据我所知，尚不清楚如何在没有预定迭代界限的情况下支持循环。

前端开销的最后一个组成部分来自于所有的 SNARK 都使用在有限域上运作的电路。你笔记本电脑上的 CPU 可以通过单个机器指令乘以或加上两个整数。如果前端输出一个足够大特征的领域电路，它可以基本上通过相应的域运算来模拟那次乘法或加法。然而，在实际 CPU 上实现该域运算通常会需要多个机器指令（尽管一些现代处理器确实对某些字段具有原生支持）。

一些 SNARK 后端能够支持比其他后端更灵活的领域选择。例如，如果后端利用一个加密组 G，那么电路的字段必须与 G 中的元素数量匹配，可能会有限制。此外，并非所有的字段都支持实用的 FFT 算法。

当前实现的唯一一个 SNARK，Brakedown，原生支持在任意（足够大）字段上的计算。连同其 后裔，它在已知的具体证明者性能中即使在其他 SNARK 支持的字段上也是最快速的，但其证明目前对于许多区块链应用来说过大。最近的工作寻求改善证明大小，但证明者是渐进地较慢的，并且似乎存在 实用性上的障碍 link。

一些项目选择在计算速度特别快的字段上工作。例如，Plonky2 和其他项目使用一种特征为 264 - 232 + 1 的字段，因为该字段中的运算可以比在结构较差的其他字段中实现得快好几倍。然而，使用如此小的特征可能在通过字段运算有效地表示整数算术方面带来挑战。（例如，将一个 32 位无符号整数乘以任何大于 232 的数字可能导致结果大于字段特征。因此，字段选择自然仅支持 32 位数字的算术运算。）

但是，无论如何，目前所有流行的 SNARK 要实现 128 位的安全性（不会显著增加验证成本），都必须在大小超过 2^128 的字段上工作。据我所知，这意味着每个字段操作至少需要大约十次 64 位机器乘法，以及更多的加法和按位操作。因此，由于需要在有限字段上运作的电路，前端开销至少应考虑增加一个数量级。

总之，现有的使用虚拟机抽象的前端生成的电路在每个虚拟机步骤上有 100 倍到 1000 倍的门，以及对于更复杂的虚拟机可能更多。再加上，有限域运算的速度至少比现代处理器上的类似指令慢 10 倍（如果处理器确实对某些字段有内置支持，则可能会有所例外）。“ASIC 前端方法”可能会降低一些开销，但目前受限于可以支持的程序类型。

后端瓶颈是什么？

用于电路可满足性的 SNARK 通常通过结合一种称为“多项式 IOP”的信息论安全协议与一种称为“多项式承诺方案”的加密协议来设计。在大多数情况下，证明者的具体瓶颈是多项式承诺方案。特别是，这些 SNARK 使证明者必须对一个或多个多项式进行加密承诺，其程度为（至少）| C |，即电路 C 中的门的数量。接着，多项式承诺方案内的具体瓶颈将取决于使用的方案和电路大小。但它总是将是以下三种操作之一：计算 FFT、在加密组中进行指数运算或 Merkle 哈希。Merkle 哈希通常仅在电路较小时才会成为瓶颈，因此我们将不再讨论它。

基于离散对数的多项式承诺

在基于加密组 G 中离散对数问题困难性的多项式承诺（KZG、Bulletproofs、Dory 和 Hyrax-commit）中，证明者必须计算对多项式系数的 Pedersen 矢量承诺。这涉及多项式的次数相等的多次指数运算。在 SNARK 中， 该次数通常是电路 C 的大小 | C |。

乍一看，对于 | C | 大小的多个指数运算需要约 1.5·| C |·log | G |≈ 400·| C | 的组运算，其中 | G | 表示组 G 中的元素数量。然而，有一种被称为 Pippenger 算法的方法，可以减少这类计算，大约减少一个 log | C | 的因子。对于较大的电路（例如，| C | ≥ 225），这个 log | C | 因子可以具体地是 25 或更多，对于大电路，我们期望 Pedersen 矢量承诺可能只需略微超过 10·| C | 次组运算即可完成。每次组运算的耗时往往为（非常粗略地估算）约是有限域运算的 10 倍。因此，使用这些多项式承诺的 SNARKs 对 P 的开销是大约 100·| C | 的有限域运算。

不幸的是，现有的 SNARK 在上述 100 倍因子之上还有额外的开销。例如：

• 使用 Hyrax 多项式承诺的 Spartan 的证明者必须执行 | C |½ 次多次指数运算，每次大小为 | C |½，约十分抵消了 Pippenger 算法带来的加速。

• 在 Groth16 中，P 必须在对称友好的组中工作，该操作的速度通常至少比非对称友好的组慢 2 倍。P 还必须执行 3 次多次指数运算，而不是 1 次。因此，总体而言，相对于上述 100·| C | 的估计，还有至少 6 倍的减速。

• Marlin 和 PlonK 也要求执行配对运算，且它们的证明者承诺的多项式可能比 3 个更多。

• 对于任何使用 Bulletproofs 的 SNARK（如 Halo2，该方案与 PlonK 类似但使用 Bulletproof 而非 KZG 多项式承诺），证明者在承诺方案的“开口”阶段必须执行对数次多次指数运算，这在很大程度上消除了任何 Pippenger 的加速。

总的来说，使用 Pedersen 矢量承诺的已知 SNARK 似乎具有至少 200 倍，甚至 1000 倍以上的后端开销。

其他多项式承诺

对于使用其他多项式承诺的 SNARK（如 FRI 和 Ligero-commit），瓶颈在于证明者需要执行大规模的 FFT。例如，在由 Cairo 产生的二次 AIR 中（具有 51 列和 T 行，每个行对应一个 Cairo CPU 的步骤），StarkWare 部署的证明者每列至少执行 2 次 FFT，每次的长度在 16·T 与 32·T 之间。常数 16 和 32 取决于 StarkWare 设置的 FRI 的内部参数，并且可以减少——但代价是增加验证成本。

乐观地说，对长度为 32·T 的 FFT，因此需要的有限域乘法次数大约为 64·T·log(32·T)。这意味着，即使对比较小的 T 值（例如，T ≥ 220），每列的有限域运算每次至少也是 64·25·T=1600·T。因此，后端开销似乎至少在几千的数量级。此外，可能大规模的 FFT 受内存带宽的瓶颈更大于字段操作的瓶颈。

在某些情况下，执行大规模 FFT 的 SNARK 的后端开销可以通过一种称为证明聚合的技术来减轻。对于 rollups，这意味着 P（rollup 服务）将一大批交易分解为例如 10 个小批次。对于每个小批次 i，P 产生该批次有效性的 SNARK 证明 πi。但 P 并不将这些证明提交到以太坊，因为这将导致 gas 成本几乎增加 10 倍。相反，SNARK 将再次应用，这次产生一个证明 π，证明确保 P 知道 π1,…,π10。即，P 声称知道的见证是这十个证明 π1,…,π10，直接见证检查应用 SNARK 验证过程到每个证明上。这个单一证明 π 被提交到以太坊上。

在像 FRI 和 Ligero 这样的多项式承诺中，存在 P 时间和 V 成本之间的强烈紧张关系，内部参数作用为一个可以互换的调整参数。由于 π1,…,π10 未被提交到以太坊，因此该参数可以调整，以使这些证明变得较大，并且生产它们的速度更快。仅在 SNARK 的最终应用中，对 π1,…,π10 进行聚合成一个小证明时，需配置承诺方案以确保证明较小。

StarkWare 计划 立即 部署证明聚合。这也是 Plonky2 等项目的重点。

SNARK 可扩展性的其他瓶颈是什么？

这篇文章专注于证明者 时间，但其他证明者成本也可能构成可扩展性瓶颈。例如，对于许多 SNARK 后端，证明者需要为 C 中的每个门存储多个有限域元素，而这种空间成本可能是巨大的。例如，一个在笔记本电脑上运转一秒的程序 ψ 可能在现代处理器上执行大约十亿次基本操作。正如我们所见，通常人们应该预期 C 每种操作需要超过 100 个门。这意味着 1000 亿门，这可能取决于具体的 SNARK 会可能产生数十或数百 TB 的 P 的存储需求。

另一个例子：许多流行的 SNARK（例如，PlonK、Marlin、Groth16）需要一个复杂的“可信设置仪式”来生成一个结构化的“证明密钥”，该密钥必须由证明者存储。 最大的 仪式 生成的证明密钥能够支持约 2^28 ≈ 2.5 亿门的电路。该密钥大小数十 GB。

在能够进行证明聚合的上下文中，这些瓶颈可以大大减轻。

展望未来：更可扩展的 SNARK 前景

前端和后端开销都可能是三个数量级或更多。我们可以指望这些在不久的将来大幅下降吗？

我认为我们会——达到一定程度。首先，今天最快的后端（例如，Spartan 和 Brakedown，还有将 求和检查协议 与多项式承诺结合的其他 SNARK）具有较大的证明——通常是电路规模的平方根，因此人们实际上并未广泛使用它们。我预计未来，通过与小证明 SNARK 的深度一种组合，证明大小和验证者时间将显著降低。类似于证明聚合，这意味着证明者将首先使用“快速证明、巨大证明”的 SNARK 生成 SA 证明 π，但并不将 π 发送给 V。相反，P 还将使用小证明 SNARK 生成一个证明 π‘，证明其知道 π，并将 π‘_ 发送给 V。这可以减少当前流行的 SNARK 的后端开销一个数量级。

其次，硬件加速可以有所帮助。一个非常粗略的一般规则是，GPU 可以为 CPU 提供 10 倍的加速，而 ASIC 可以提供 10 倍的 GPU 加速。然而，我对此有三点担忧。首先，大规模 FFT 可能受限于内存带宽而非领域操作，因此执行此类 FFT 的 SNARK 可能从专用硬件中获得有限加速。第二，尽管此文集中在多项式承诺瓶颈上，但许多 SNARK 还需证明者执行的其他操作仅稍微少些费力。因此突破多项式承诺瓶颈（例如，加速多次指数运算）可能会留下一个新瓶颈，这并没有显著改善。而且，许多包含 Groth16、Marlin 及 PlonK 的 SNARK 额外还必须对 FFT进行操作。此外，可能导致最有效的 SNARK 的领域及椭圆曲线也可能在一定时间内继续发展，并可能对基于 ASIC 的证明者加速构成挑战。

在前端方面，我们可能越来越发现，像 Cairo、RISC Zero、zkEVM 等项目的“CPU 模拟器”方法，实际上在性能上与 CPU 指令集的复杂性扩展良好。确实，这是各种 zkEVM 项目的正希望。这可能意味着，尽管前端开销仍保持在三个数量级或更高，但前端能够支持的 VM 与真实的 CPU 架构相见增长互吻合。有一个相反的担忧是，随着实现越来越复杂的指令的手写工具不断增多，前端可能变得复杂且难以审计。正式验证方法可能在解决这一问题中发挥重要作用。

最后，至少在区块链应用中，我们可能会发现，现实中出现的大多数智能合约主要使用简单、适合 SNARK 的指令。这可能实现在实践中保持低前端开销，同时保留支持高层编程语言（如 Solidity）和丰富指令集（包括 EVM 的指令集）所带来的通用性和改进的开发者体验。

Justin Thaler 是乔治城大学的助理教授。在加入乔治城大学之前，他在纽约的雅虎实验室担任了两年的研究科学家，此前他在加州大学伯克利分校的 Simons Institute for the Theory of Computing 中担任研究员。

感谢 Elena Burger 提出该文主题的建议，感谢 Arasu Arun, Joseph Bonneau、Sam Ragsdale 和 _Daniel Lubarov，以及 Brendan Farmer 的深刻评论。特别感谢我的编辑，Tim Sullivan。

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