SNARK（简洁的非交互式知识论证）是一种重要的密码学原语，用于发现区块链可扩展性（例如 L2 汇总）和隐私的应用。 SNARK 让某人向不信任的验证者证明 V （例如，以太坊区块链）他们知道一些数据（例如，一批有效交易）。 证明这一点的一种天真的方法是将数据发送到 V，然后谁可以直接检查其有效性。 SNARK 可以达到相同的效果，但成本更高 V. 特别是，SNARK 证明应该比包含数据本身的简单证明更短。 （更多细节见我的教科书草稿， 证明、论证和零知识. 有关 SNARK 的介绍，请参阅 Sarah Meicklejohn 的 在 a16z 加密货币 夏季研究系列.)
SNARK 的验证成本可能会有所不同，但都很好理解，而且通常相当不错。 例如， 普朗克 样张费用约为 290,000汽油 在以太坊上进行验证，而 StarkWare 的证明花费了大约 5 万 gas。 SNARK 可能适用于区块链之外的各种环境——例如，可以使用快速但不受信任的 服务器 和 硬件.
但是因为 SNARK 验证通常很便宜，所以适用性的主要决定因素是 SNARK 证明者的成本 P. 在这篇文章中，我将解释如何估算这些成本以确定何时使用 SNARK 是合理的，以及 SNARK 在未来如何改进。 值得注意的是，这是一个快速发展的领域，本文中讨论的几个项目正在积极提高其性能。
但首先：如何部署 SNARK
在 SNARK 部署中，开发人员通常编写计算机程序 ψ 将数据作为输入 w 证明者声称知道（w 代表 见证)，并检查 w 已验证。 例如，在汇总中，程序将检查所有事务 w 数字签名，不要导致任何账户余额低于零，等等。 该程序 ψ 然后通过一个馈 SNARK 前端 将其编译成更适合 SNARK 技术应用的格式。 这种对 SNARK 友好的格式称为 中间表示 （红外）。
通常，IR 是某种电路可满足性实例，它等价于 ψ。 这意味着电路 C 将数据作为输入 w，以及一些通常称为“非确定性建议”的额外输入，并运行 ψ on w. 建议输入用于帮助 C 运行 ψ，同时保持 C 小的。 例如，每次 ψ 两个数相除 x 和 y, 商 q 和剩余的 r 可以作为建议提供给 C及 C 可以简单地检查一下 x = qy + r. 这张支票比制作便宜 C 运行除法算法来计算 q 和 r 从头开始。
最后，将用于电路可满足性的 SNARK 应用于 C。 这称为 SNARK 后端. 对于少数高度结构化的问题，例如 矩阵乘法, 卷积及 几个图形问题，存在已知的 SNARK，它们避免了这种前端/后端范式，从而实现了更快的证明者。 但这篇文章的重点是通用 SNARK。
正如我们将看到的，SNARK 后端的证明者成本随着 C的 尺寸。 保持 C 小可能具有挑战性，因为电路是表达计算的极其有限的格式。 它们包括 大门， 通过连接 电线. 每个门 g 输入一些值并应用 非常 这些值的简单函数。 然后将结果通过来自的电线馈送到“下游”门 g.
SNARK 可扩展性：真正需要多少时间？
关键问题是，相对于简单地重新执行，SNARK 证明者需要多长时间 ψ 在数据上？ 答案是 证明者开销 SNARK 的，相对于 直接证人检查. 后一种表达是指这样一个事实，即在朴素证明中 P 发送 w 至 V, V 检查 w的有效性通过执行 ψ 就可以了。
将证明者开销分解为“前端开销”和“后端开销”会很有帮助。 如果评估电路 C 门接门是 F 比跑步贵几倍 ψ，那么我们说前端开销是 F. 如果将后端证明器应用于 C is B 比评估贵几倍 C 门接门，那么我们说后端开销是 B. 证明者的总开销是 产品， F·B. 这种乘法开销可能很大，即使 F 和 B 个人谦虚。
在实践中， F 和 B 两者都可以大约为 1000 或更大。 这意味着相对于直接证人检查的总证明者开销可能是 1 万到 10 万或更多。 在笔记本电脑上运行一秒钟的程序很容易导致 SNARK 证明者需要数十或数百天的计算时间（单线程）。 幸运的是，这项工作通常可以在不同程度上并行化（取决于 SNARK）。
总而言之，如果您想在今天的应用程序中使用 SNARK，则需要满足以下三件事之一：
- 在笔记本电脑上，直接证人检查所需的时间不到一秒钟。
- 直接见证检查特别适合电路中的表示，因此前端开销很小。
- 您愿意等待数天等待 SNARK 证明器完成，和/或支付大量并行计算资源。
T他在这篇文章的其余部分解释了前端和后端开销的来源，以及我如何为不同的 SNARK 估计它们。 然后我们将转向改进的前景。
分离前端和后端
将前端与后端完全分离可能具有挑战性，因为不同的后端支持不同类型的电路。 因此，前端可能会根据他们期望与之交互的后端而有所不同。
SNARK 后端通常支持所谓的算术电路，这意味着电路的输入是某个有限域的元素，并且电路的门执行两个域元素的加法和乘法。 这些电路大致对应于本质上是代数的直线计算机程序（没有分支、条件语句等）——也就是说，它们的原始数据类型是字段元素。
大多数后端实际上支持算术电路的泛化，通常称为 Rank-1 约束满足 (R1CS) 实例。 除了值得注意的例外 格罗斯16 及其前身，这些 SNARK 也可以用来支持其他 IR。 例如，StarkWare 使用称为代数中间表示 (AIR) 的东西，它也类似于称为 PlonKish 算术化 PlonK 和其他后端可以支持。 一些后端支持更通用的 IR 的能力可以减少产生这些 IR 的前端的开销。
后端在它们本机支持的有限字段方面也有所不同。 我将在下一节进一步讨论这个问题。
各种前端方法
一些（非常特殊的）计算机程序自然对应于算术电路。 一个例子是在某个域上执行矩阵乘法的计算机程序。 但是大多数计算机程序既不是直线也不是代数。 它们通常涉及条件语句、整数除法或浮点算术等与有限域算术自然不对应的操作等等。 在这些情况下，前端开销将是巨大的。
一种流行的前端方法是生成基本上逐步执行一些简单 CPU 的电路，也称为虚拟机 (VM)。 前端设计人员指定了一组类似于真实计算机处理器的汇编指令的“原始操作”。 想要使用前端的开发人员要么直接用汇编语言编写“见证检查程序”，要么用 Solidity 等高级语言编写，然后将他们的程序自动编译成汇编代码。
例如，StarkWare 的 开罗 是一种非常有限的汇编语言，其中汇编指令大致允许在有限域上进行加法和乘法运算、函数调用以及对不可变（即一次写入）内存的读取和写入。 Cairo VM 是 von Neumann 架构，这意味着前端生成的电路本质上将 Cairo 程序作为公共输入，并在见证服务器上“运行”程序。 Cairo 语言是图灵完备的——尽管指令集有限，但它可以模拟更多标准架构，尽管这样做可能很昂贵。 Cairo 前端让 Cairo 程序执行 T 原始指令转化为所谓的“度2 空气与 T 行和大约 50 列。” 什么 正是这意味着 对于这篇文章并不重要，但就 SNARK 证明者而言，这对应于每个电路有 50 到 100 个门的电路 T Cairo CPU 的步骤。
RISC 零 采用与开罗类似的方法，但虚拟机是所谓的 RISC-V架构，一种具有丰富软件生态系统的开源架构，越来越受欢迎。 作为一个非常简单的指令集，设计一个支持它的高效 SNARK 前端可能相对容易处理（至少相对于 x86 或 ARM 等复杂架构而言）。 截至 XNUMX 月，RISC 零 正在转动程序 执行 T 将原始 RISC-V 指令转换为 5 级 AIR 3T 行和 160 列。 这对应于至少具有 500 RISC-V CPU 的每步门数。 预计在不久的将来会有进一步的改进。
各种 zkEVM 项目（例如，zkSync 2.0、Scroll、Polygon 的 zkEVM）将虚拟机视为（duh）以太坊虚拟机。 与更简单的 Cairo 和 RISC-V 架构相比，将每条 EVM 指令转换为等效“小工具”（即实现指令的优化电路）的过程要复杂得多。 由于这个和其他原因, 一些 zkEVM 项目 不是直接实现 EVM 指令集，而是将高级 Solidity 程序编译成其他汇编语言，然后再将它们变成电路。 这些项目的绩效结果正在等待中。
诸如 RISC-V 和 Cairo 之类的“CPU 仿真器”项目产生了一个可以处理相关汇编语言中的所有程序的单一电路。 替代方法是“类 ASIC”，为不同的程序生成不同的电路。 这种类似 ASIC 的方法可以为某些程序产生更小的电路，尤其是当程序在每个时间步执行的汇编指令不依赖于程序的输入时。 例如，对于简单的矩阵乘法等直线程序，它可以完全避免前端开销。 但是 ASIC 方法似乎也非常有限。 据我所知，不知道如何使用它来支持没有预定迭代界限的循环。
前端开销的最后一个组成部分来自所有 SNARK 都使用在有限域上运行的电路这一事实。 笔记本电脑上的 CPU 可以使用一条机器指令将两个整数相乘或相加。 如果前端在足够大的特性场上输出电路，它基本上可以通过相应的场操作模拟乘法或加法。 然而，在真正的 CPU 上实现字段操作通常需要许多机器指令（尽管一些现代处理器确实对某些字段具有原生支持）。
一些 SNARK 后端比其他后端支持更灵活的字段选择。 例如，如果后端使用加密组 G，电路的场必须与元素的数量相匹配 G，这可能是限制性的。 此外，并非所有领域都支持实用的 FFT 算法。
只有一个实现的 SNARK， 分裂，它本机支持对任意（足够大）字段的计算。 连同它的 后代，即使在其他 SNARK 支持的领域中，它也具有已知最快的具体证明者性能，但它的证明目前对于许多区块链应用来说太大了。 最近的工作 试图提高证明的大小，但证明者渐近地变慢并且存在 看起来是 障碍 到实用性。
一些项目选择在运算速度特别快的领域工作。 例如， 笨笨2 和其他人使用特征 2 的字段64 - 232 + 1，因为该领域的算术执行速度比结构化程度较低的领域快几倍。然而，使用如此小的特征可能会导致通过字段运算有效表示整数算术的挑战（例如，将两个 32 位无符号整数相乘可能会产生大于字段特征的结果）。
但无论如何，对于当今所有流行的 SNARK，要实现 128 位的安全性（不显着增加验证成本），它们必须在大于 2 的域上工作128. 据我所知，这意味着每个字段运算将需要至少大约 64 次 XNUMX 位机器乘法，以及更多的加法和按位运算。 因此，由于需要在有限域上运行的电路，因此应该考虑至少一个数量级的前端开销。
总而言之，使用虚拟机抽象的现有前端在虚拟机的每一步中产生的电路具有 100 倍到 1000 倍的门，对于更复杂的虚拟机可能更多。 最重要的是，有限域算术至少比现代处理器上的类似指令慢 10 倍（如果处理器具有对某些域的内置支持，则可能存在例外）。 “ASIC 前端方法”可能会减少其中一些开销，但目前它可以支持的程序种类有限。
后端瓶颈是什么？
用于电路可满足性的 SNARK 通常是通过结合称为“多项式眼压” 使用称为“多项式承诺方案。” 在大多数情况下，证明者的具体瓶颈是多项式承诺方案。 特别是，这些 SNARK 让证明者以密码方式承诺一个或多个多项式，其次数为（至少） |C|, 电路中的门数 C.
反过来，多项式承诺方案中的具体瓶颈将取决于所使用的方案和电路尺寸。 但它始终是以下三种操作之一：计算 FFT、加密组中的求幂，或 默克尔散列. Merkle 散列通常仅在电路很小的情况下才会成为瓶颈，因此我们将不再进一步讨论。
基于离散对数的多项式承诺
在基于密码组中离散对数问题硬度的多项式承诺中 G (克孜格, Bulletproofs, 海鲂及 Hyrax-提交)，证明者必须计算一个 Pedersen 向量承诺 为多项式的系数。 这涉及到多次幂运算，其大小等于多项式的次数。 在 SNARK 中，这个度数通常是大小 |C| 该电路的 C.
天真地完成，大小的多次幂 |C| 需要大约1.5·|C|·日志 |G| ≈ 400·|C| 组操作，其中 |G| 表示组中元素的数量 G. 但是，有一种方法，称为 Pippenger 算法，可以将其减少大约 log |C|. 对于大型电路（例如， |C| ≥ 225)，这个日志 |C| 因子具体可以是 25 或更大，也就是说，对于大电路，我们预计 Pedersen 向量承诺可能可以计算 10 多一点·|C| 组操作。 反过来，每个组操作往往（作为一个非常粗略的球场）比有限域操作慢约 10 倍。 使用这些多项式承诺的 SNARK P 大约 100·|C| 现场操作。
不幸的是，现有的 SNARK 在上述 100 倍因素之上还有额外的开销。 例如：
- 斯巴达的证明者，它使用 Hyrax 多项式承诺，必须做 |C|½ 许多多重指数，每个大小 |C|½，将 Pippenger 算法的加速性能降低了大约两倍。
- In 格罗斯16, P 必须在一个配对友好的组上工作，其操作通常比不配对的组慢至少 2 倍。 P 还必须执行 3 次乘幂运算而不是 1 次。结合起来，这会导致相对于 6 次的至少额外的 100 倍减速·|C| 以上估计。
- 马林 和 普朗克 还需要配对，并且它们的证明者承诺远远超过 3 个多项式。
- 对于任何使用 SNARK Bulletproofs （例如， Halo2，大致是 PlonK，但使用 Bulletproofs 而不是 KZG 多项式承诺），证明者必须在承诺方案的“开放”阶段以对数方式计算许多多重指数，这在很大程度上消除了任何 Pippenger 加速。
总之，使用 Pedersen 向量承诺的已知 SNARK 似乎具有至少 200 倍和高达 1000 倍或更多的后端开销。
其他多项式承诺
对于使用其他多项式承诺的 SNARK（例如 星期五 和 Ligero-提交)，瓶颈在于证明者需要执行大型 FFT。 例如，在 Cairo 制作的 2 级 AIR（有 51 列和 T 行，Cairo CPU 的每步一个），StarkWare 部署的证明器每列至少执行 2 次 FFT，长度介于 16·T 和 32·T. 常数 16 和 32 取决于 StarkWare 设置的 FRI 的内部参数，并且可以减少 - 但以增加验证成本为代价。
乐观地，长度为 32 的 FFT·T 大约需要 64·T·日志（32T) 场乘法。 这意味着即使对于相对较小的值 T （例如， T ≥ 220)，每列的字段操作数至少为 64·25·T= 1600·T. 因此，后端开销似乎至少为数千。 此外，与现场操作相比，内存带宽可能对大型 FFT 造成更大的瓶颈。
在某些情况下，执行大型 FFT 的 SNARK 的后端开销可以通过一种称为证明聚合的技术来减轻。 对于汇总，这意味着 P （汇总服务）将一大批事务分成 10 个较小的批次。 对于每个小批量 i, P 产生一个 SNARK 证明 πi 批次的有效性。 但 P 不会将这些证明发布到以太坊，因为这会导致 gas 成本增加近 10 倍。 相反，SNARK 再次被应用，这一次是为了产生一个证明 π 确立 P 知道 π1 ，...，π10. 也就是说，证人 P 声称知道是十个证明 π1,…,π10，并且直接见证检查将 SNARK 验证程序应用于每个证明。 这个单证 π 发布到以太坊。
在 FRI 和 Ligero-commit 等多项式承诺中， P 时间和 V 成本，内部参数充当一个旋钮，可以在一个与另一个之间进行权衡。 自从 π1 ,…,π10 没有发布到以太坊，可以调整旋钮以便这些证明 很大，而且生产速度更快。 只有在 SNARK 的最终应用中，才能聚合 π1 ,…,π10 成一个单一的证明 π, 是否需要配置承诺方案以确保小证明。
StarkWare 计划部署证明聚合 迫在眉睫. 这也是项目的重点，例如 笨笨2.
SNARK 可扩展性的其他瓶颈是什么？
这篇文章的重点是证明者 次，但其他证明者成本也可能成为可扩展性瓶颈。 例如，对于许多 SNARK 后端，证明者需要为每个门存储几个字段元素 C，而这个空间成本可能是巨大的。 例如，一个程序 ψ 在笔记本电脑上运行一秒钟可以在现代处理器上执行十亿个原始操作。 正如我们所看到的，一般来说，人们应该期望 C 每次这样的操作需要超过 100 个门。 这意味着 100 亿个门，根据 SNARK，这可能意味着数十或数百 TB 的空间 P.
另一个例子：许多流行的 SNARK（例如， 普朗克, 马林, 格罗斯16) 需要复杂的“可信设置仪式”来生成结构化的“证明密钥”， 必须由证明者存储。 据我所知， 最大的此类仪式 生成了一个能够支持大约 2 个电路的证明密钥28≈250亿门。 证明密钥的大小为几十 GB。
在可以进行证明聚合的情况下，可以大大缓解这些瓶颈。
展望未来：更具可扩展性的 SNARK 的前景
前端和后端开销都可以是三个数量级或更多。 我们可以期待这些在不久的将来大幅下降吗？
我想我们会——在一定程度上。 首先，当今最快的后端（例如， 斯巴达 和 分裂，以及其他结合了 和校验协议 多项式承诺）有很大的证明——通常是电路大小的平方根——所以人们并没有真正使用它们。 我预计在不久的将来，通过使用小证明 SNARK 的深度一组合，证明大小和验证者时间会显着减少。 与证明聚合类似，这意味着证明者将首先生成 SNARK 证明 π 使用“快速证明，大证明”的 SNARK，但不发送 π 至 V。 相反， P 将使用小型证明 SNARK 来生成证明 π和 它知道 π, 并且寄出 π“ 至 V. 这可以将当今流行的 SNARK 的后端开销减少一个数量级。
其次，硬件加速可以提供帮助。 一个非常粗略的一般规则是，GPU 可以比 CPU 获得 10 倍的加速，而 ASIC 可以比 GPU 获得 10 倍的加速。 但是，我在这方面有三个担忧。 首先，大型 FFT 可能会受到内存带宽而非现场操作的瓶颈，因此执行此类 FFT 的 SNARK 可能会看到专用硬件的加速速度有限。 其次，虽然这篇文章专注于多项式承诺瓶颈，但许多 SNARK 要求证明者执行其他操作，这些操作只是稍微便宜一些。 所以打破多项式承诺瓶颈（例如， 加速多幂运算 在基于离散对数的 SNARK 中）可能会留下一个新的瓶颈操作，它并不比旧的好很多。 （例如，包括 Groth16、Marlin 和 PlonK 在内的 SNARK 除了多幂运算外，还让证明者进行 FFT。) 最后，导致最有效 SNARK 的场和椭圆曲线可能会继续发展一段时间，这可能会给基于 ASIC 的证明者加速带来挑战。
在前端，我们可能会越来越多地发现 Cairo、RISC Zero、zkEVM 等项目的“CPU 仿真器”方法实际上可以很好地扩展（在性能方面）与 CPU 指令集的复杂性。 的确，这正是各种 zkEVM 项目的希望所在。 这可能意味着，虽然前端开销仍然是三个数量级或更多，但前端设法支持越来越匹配真实 CPU 架构的 VM。 一个相反的问题是前端可能会变得复杂且难以审计，因为手动编码的小工具执行越来越复杂的指令会激增。 形式验证方法可能会在解决这一问题方面发挥重要作用。
最后，至少在区块链应用中，我们可能会发现大多数出现在野外的智能合约主要使用简单的、对 SNARK 友好的指令。 这可以在实践中实现较低的前端开销，同时保留支持高级编程语言（如 Solidity）和丰富的指令集（包括 EVM 的指令集）所带来的通用性和改进的开发人员体验。
***
贾斯汀·泰勒 is 乔治城大学副教授。 在加入乔治城大学之前，他在纽约雅虎实验室担任了两年的研究科学家，在此之前，他是纽约大学的研究员。 西蒙斯计算理论研究所 在加州大学伯克利分校。
***
致谢：我很感激 埃琳娜汉堡 提出这篇文章的主题，并 阿拉苏·阿伦， 约瑟夫·波诺（Joseph Bonneau）及 山姆·拉格斯代尔 有见地的评论。 还要特别感谢我的编辑， 蒂姆·沙利文.
***
此处表达的观点是引用的个人 AH Capital Management, LLC (“a16z”) 人员的观点，而不是 a16z 或其关联公司的观点。 此处包含的某些信息是从第三方来源获得的，包括来自 a16z 管理的基金的投资组合公司。 虽然取自被认为可靠的来源，但 a16z 并未独立验证此类信息，也不对信息的持久准确性或其对特定情况的适用性做出任何陈述。 此外，该内容可能包含第三方广告； a16z 未审查此类广告，也不认可其中包含的任何广告内容。
此内容仅供参考，不应被视为法律、商业、投资或税务建议。 您应该就这些事项咨询您自己的顾问。 对任何证券或数字资产的引用仅用于说明目的，并不构成投资建议或提供投资咨询服务的要约。 此外，本内容并非针对也不打算供任何投资者或潜在投资者使用，并且在任何情况下都不得在决定投资于 a16z 管理的任何基金时作为依据。 （投资 a16z 基金的要约仅通过私募备忘录、认购协议和任何此类基金的其他相关文件提出，并应完整阅读。）任何提及、提及或提及的投资或投资组合公司所描述的并不代表对 a16z 管理的车辆的所有投资，并且不能保证这些投资将是有利可图的，或者将来进行的其他投资将具有类似的特征或结果。 由 Andreessen Horowitz 管理的基金进行的投资清单（不包括发行人未允许 a16z 公开披露的投资以及对公开交易的数字资产的未宣布投资）可在 https://a16z.com/investments 获得/。
其中提供的图表仅供参考，在做出任何投资决定时不应依赖。 过去的表现并不预示未来的结果。 内容仅在所示日期生效。 这些材料中表达的任何预测、估计、预测、目标、前景和/或意见如有更改，恕不另行通知，并且可能与他人表达的意见不同或相反。 有关其他重要信息，请参阅 https://a16z.com/disclosures。
