详解 a16z crypto 新推出的两个 SNARK 工具

原文标题：Approaching the 'lookup singularity': Introducing Lasso and Jolt
编译：倩雯，ChainCatcher

SNARK 是一种加密协议，它允许任何人向不信任的验证者证明自己认识满足某些属性的“见证”（witness）。SNARK 在 Web3 中的一个突出应用是 L2 rollup 向 L1 的区块链证明他们认识授权一系列交易的数字签名，这样签名本身就不必由 L1 存储和验证，从而提升可扩展性。

SNARK 在区块链以外的应用包括：速度高但不受信的硬件设备证明它们产生的所有输出的有效性，确保用户可以信任它们。个人可以以零知识的方式证明受信机构向他们颁发了凭证。例如，证明他们的年龄足以访问受年龄限制的内容，而无需透露他们的出生日期。任何人通过网络发送加密数据，都可以向管理员证明该数据符合网络政策，而无需透露更多细节。

虽然很多 SNARK 对证明者（prover）来说成本很低，但 SNARK 一般仍会在验证计算中带来约六个数量级的开销。验证者被迫承担的额外工作是高度可并行化的，但一百万倍的系数开销严重限制了 SNARK 的应用。

性能更强的 SNARK 可以加快 L2 的速度，还能让构建者解锁尚未实现的应用。因此，我们推出了两项相关的新技术：Lasso 是一种新的查找参数，可显著降低证明者成本；Jolt 使用 Lasso 技术，为 zkVM 和其他前端设计提供了设计 SNARK 的新框架。它们共同提高了 SNARK 设计的性能、开发者体验和可审计性，促进 web3 的建设。

与流行的 SNARK 工具链 halo2 中的查找参数相比，Lasso 初步实现已经证明速度提高 10 倍以上。我们预计，当 Lasso 代码库完全优化后，速度将提高约 40 倍。Jolt 包含基于 Lasso 的更多创新，我们希望它能实现与现有 zkVM 类似或更高的速度。

查找参数、Lasso和Jolt

SNARK 前端（SNARK frontend）是一种编译器，可将计算机程序转化为电路，并由 SNARK 后端摄取。电路是一种极其有限的计算模型，其中的原始运算仅仅是加法和乘法。

现代 SNARK 设计中的一个关键工具是查找参数（lookup argument），它是一种协议，允许不受信证明者以加密方式提交一个大型向量，然后证明该向量的每个条目都包含在某个预定表中。查找参数可以有效地处理那些无法通过少量加法和乘法自然计算的运算，从而有助于保持电路维持小型规模。

以太坊基金会的 Barry 就提出了一种设想，他认为如果我们可以实现“只使用查找参数就能高效地定义电路，就可以带来更简化的工具和电路”，也就是实现“查找奇点”，此时我们已经可以“设计出只执行查找的电路时”，这种方式在几乎所有方面这优于比多项式约束。

这一愿景与当今的工作方式形成了鲜明对比，在当今的工作方式中，开发人员部署 SNARK 的方法是使用特异性领域特定语言（将程序编译为多项式约束）编写程序，或者直接手动编码约束。这种工具链耗费大量人力物力，导致安全关键漏洞的概率很高。即使用复杂的工具和电路，SNARK 仍然很慢，这限制了它的应用。

Lasso 和 Jolt 解决了所有三个关键问题：性能、开发人员体验和可审计性。我相信，它们将共同实现查找奇点的愿景。Lasso 和 Jolt 还让我们对 SNARK 设计中的许多公认真题进行反思。在介绍了一些必要的背景知识后，本篇文章将重新审视有关 SNARK 性能的一些常见观点，并解释如何根据 Lasso 和 Jolt 等创新技术更新这些观点。

SNARK设计背景：为什么这么慢？

大多数 SNARK 后端都让验证者对电路中每个门的值进行加密承诺，使用的方法称为多项式承诺方案。然后，证明者证明所承诺的值符合见证检查程序的正确执行。

我将来自多项式承诺方案的证明者工作称为承诺成本（commitment cost）。SNARK 还有额外的证明者成本，这些成本来自多项式承诺方案之外。但承诺成本往往是瓶颈所在。Lasso 和 Jolt 的情况也是如此。在设计 SNARK 时，如果承诺成本不构成主要的证明者成本，这不意味着多项式承诺方案的成本低，反而意味着其他费用高于它们应有的水平。

直观地说，承诺的目的是通过加密方法安全地增加证明系统的简洁性。当证明者对一个大的值向量做出承诺时，这就类似于证明者把整个向量发送给验证者，就像微小证明系统（trivial proof system）把整个见证发送给验证者一样。承诺方案无需强制验证者实际接收整个见证就能实现这一点，这意味着在 SNARK 设计中，承诺方案的目的是控制验证者成本。

但这些加密方法对证明者来说非常昂贵，尤其是与 SNARK 在多项式承诺方案之外使用的信息论方法相比。信息论方法只依赖于有限域运算。而一次字段运算的速度要比对任意字段元素进行承诺所需的时间快上几个数量级。

根据所使用的多项式承诺方案，计算承诺涉及多幂乘（也称为多标量乘法或 MSM），或 FFT 和梅克尔散列。Lasso 和 Jolt 可以使用任何多项式承诺方案，但在使用基于 MSM 的方案，比如  IPA/Bulletproofs、KZG/PST、Hyrax,、Dory 或 Zeromorph 时会产生额外的成本。

Lasso和Jolt为何重要？

Lasso 是一种新的查找参数方法，与之前的方法相比，证明者承诺的值更少、更小。根据具体情况，这可以将速度提高20倍或更多，其中2倍到4倍来自于更少的承诺值，另外10倍是因为在 Lasso 中，所有承诺值都很小。与之前的许多查找参数不同，Lasso（和Jolt）还避免了 FFT，因为 FFT 需要大量空间，在大型实例中可能会导致瓶颈。

此外，只要表格是“结构化”的（从精确的技术意义上来说），Lasso 甚至可以应用于巨大的表格（比如规模达到2128）。表格规模太大时，任何人都无法明确地将其具体化，但 Lasso 只对它实际访问的表格元素付出成本。值得关注的另一点是，如果表是结构化的，那么任何一方都不需要对表中的所有值进行加密承诺。

Lasso 利用了两种不同的结构概念：可分解性和 LDE 结构。可分解性大致是指，通过对非常小规模的表少量查找，就能完成对表的一次查找。这是比 LDE 结构更严格的要求，但Lasso在应用于可分解的表时十分高效。

Jolt

Jolt（Just One Lookup Table“只需一个查找表”）是一个新的前端，基于 Lasso 使用巨型查找表的功能。Jolt 针对虚拟机/CPU 抽象，也称为指令集架构（ISA）。支持这种抽象 SNARK 被称为 zkVM。例如受 RISC-Zero 项目支持的RISC-V指令集（包括乘法扩展的指令集）。这是一种流行的开放源码 ISA，由计算机体系结构社区开发，在开发时没有考虑 SNARK。

对于每一条 RISC-V 指令 fi，Jolt 的主要想法是创建一个查找表，其中包含 fi 的整个评估表。因此，如果 fi 接收两个 32 位输入，该表将有 264 个条目，其中(x,y)'th的条目为 fi(x,y)。如果我们考虑的是 64 位而不是 32 位数据类型的指令，那么每条指令的表的大小将是 2128 而不是 264。

基本上每一条 RISC-V 指令的查找表都是可分解的，并适用 Lasso。少数指令是通过应用其他指令的简短序列来处理的。例如，除法指令的处理方法是让证明者提交商和余数，并检查是否通过一次乘法和一次加法正确提供了商和余数。

运行 T 步RISC-VCPU 的电路可按如下方式生成。对于 T 步中的每一步，电路都包含一些简单的逻辑，以确定该步要执行的原始 RISC-V 指令fi，以及该指令的输入 (x，y)。然后，电路只需执行一次查找，揭示相关表中的第 (x,y) 项，即可执行 fi。更准确地说，Jolt 只考虑了一个表，它由每条指令的表连接而成，因此被称为“只需一个查找表”。

重新审视SNARK设计中的公认真理

Lasso 和 Jolt 还颠覆了 SNARK 设计中几项公认真理。

1.SNARK 过度域（over large field）是一种浪费。每个人都应该使用 FRI、Ligero、Brakedown或其变体，因为这些技术避免了椭圆曲线技术，而椭圆曲线技术通常适用于较大的字段。

这里的字段大小大致可以理解为 SNARK 证明中出现数字的大小。由于大数的加法和乘法开销很大，因此大字段上的 SNARK 会造成浪费，这意味着我们应尽可能设计永远不会出现大数的协议。基于 MSM 的承诺使用椭圆曲线，而椭圆曲线通常定义在大字段上（大小约为 2256），因此椭圆曲线的性能较差。

我之前有讨论过使用小字段是否合理在很大程度上取决于应用。Lasso 和 Jolt 表明，即使使用基于 MSM 的承诺方案，证明者的工作也几乎不受字段大小的影响。这是因为，对于基于 MSM 的承诺，承诺值的大小比这些值所在字段的大小更重要。

现有的 SNARK 会让证明者提交许多随机字段元素。例如，一个名为 Plonk 的证明者会对每个电路门提交约7个随机字段元素（以及额外的非随机字段元素）。即使被证明的计算中出现的所有值都很小，这些随机字段元素也会很大。

相比之下，Lasso和Jolt只要求证明者提交较小的数值（Lasso 的证明者提交的数值也少于先前的查找参数）。这大大提高了基于 MSM 方案的性能。至少，Lasso 和 Jolt 应该摒弃这样的观念，即在证明者性能很重要的情况下，社区应该放弃基于 MSM 的承诺。

2.指令集更简单，zkVM速度更快。

只要每条指令的评估表都是可分解的，Jolt（每条指令）的复杂度就只取决于指令的输入大小。Jolt 证明了巨大的复杂指令都是可分解的，尤其是所有 RISC-V 指令。

这与人们普遍认为更简单的虚拟机（zkVM）必然导致更小的电路和相关的更快证明器（虚拟机的每一步）的看法相反。这一观点一直指导着极简zkVM（如 Cairo VM）的设计。

事实上，对于较简单的虚拟机，Jolt 比之前的 SNARK 更能降低证明者的承诺成本。例如，对于 Cairo VM 执行的证明者在虚拟机的每一步都要提交 51 个字段元素。Cairo VM 部署的 SNARK 目前处于 251 位的字段（63 位是 SNARK 可以使用字段大小的硬下限）。Jolt 的验证者在 RISC-VCPU 上每步提交约 60 个字段元素（定义为 64 位数据类型）。考虑到提交的字段元素较少，Jolt 验证者的成本大约相当于提交 6 个 256 位随机字段元素的成本。

3.将大型计算分解成小块不会造成性能损失。

基于这种观点，如今的项目会将大电路分解成小块，分别证明每一块，并通过 SNARK 递归将结果汇总。这些部署使用这种方法来缓解多数 SNARK 的性能瓶颈。例如，基于 FRI 的 SNARK 即使对小型电路也需要近 100 GB的证明器空间。它们还需要 FFT，这是一种超线性操作，如果 SNARK 一次性应用于大型电路，这种操作就会成为瓶颈。

现实情况是，一些 SNARK（如 Lasso和Jolt）表现出规模经济性（而目前部署的SNARK不具有规模经济性）。这意味着被证明的语句越大，证明者的开销相对见证检查（witness checking，即在不保证正确性的情况下评估见证电路所需的工作）就越小。在技术层面上，规模经济来自两个方面：

1）大小为n的MSM的皮彭格加速度（Pippenger speedup）比原始算法提高了log(n)倍。n越大，提升越大。

2）在Lasso等查找参数中，证明者需要支付一次性成本，该成本取决于查找表的大小，但与查找值的数量无关。证明者的一次性成本在对表的所有查询中摊销。更大的数据块意味着更多的查找次数，也就意味着更好的摊销。

如今，处理大型电路的主流方法是将电路分成尽可能小的块。对每块电路大小的主要限制是，它们不能太小，否则递归聚合证明会成为证明者的瓶颈。

Lasso和Jolt提出了一种基本相反的方法。我们应该使用具有规模经济性的SNARK。然后将大型计算分成尽可能大的部分，并对结果进行递归。每个计算片段大小的主要限制因素是证明者空间，随着计算片段的增大，证明者空间也会随之增大。

4.高阶约束是高效 SNARK 的必要条件。

Jolt 使用 R1CS 作为中间表示。在 Jolt 中，使用“高阶”或“自定义”约束没有任何好处。在 Jolt 中，证明者的大部分成本都在查找参数 Lasso 上，而不是在证明约束系统的可满足性上（这一系统将查找选项视为理所应当）。

Jolt 是通用型的，因此不会丧失通用性。因此，开发人员在设计高度约束（通常是手动定制）时，为了从当今流行的 SNARK 中榨取更高的性能，把重点放在了设计高度约束上，Jolt正好与之相反。

当然，在某些情况下，高程度或自定义约束条件仍会有所助益。一个重要的例子是 Minroot VDF ，对它来说，5 级约束可以将承诺成本降低约3倍。

5.稀疏多项式承诺方案（Sparse polynomial commitment ）耗资巨大，应尽可能避免。

真一批评主要针对最近推出的名为 CCS 和支持该系统的 SNARK： (Super-)Spartan 和 (Super-)Marlin。CCS 是对当今实践中流行的所有约束系统的简洁概括。

这种批评是没有根据的。事实上，Lasso 和 Jolt 的技术核心是 Spartan 中的稀疏多项式承诺方案，称为 Spark。Spark 本身就是将任何（非稀疏）多项式承诺方案转换为支持稀疏多项式的方案。

Lasso 对 Spark 进行了优化和扩展，以确保证明者只提交“小”值，但即使没有这些优化，这种批评也是没有道理的。事实上，Spartan 的证明者比 SNARK（如 Plonk 等避免稀疏多项式承诺的SNARK）相比，Spartan 的证明者承诺的（随机）字段元素更少。

Spartan 的方法具有额外的性能优势，特别是对于具有重复结构的电路。对于这些电路，添加门并不会增加 Spartan 验证者的加密工作量。这种工作量只会随着给定约束系统中变量数量的增加而增加，而不会随着约束数量的增加而增加。而且与 Plonk 不同的是，Spartan 验证者无需对同一变量的多个不同“副本”做出承诺。

结语

我们相信，Lasso 和 Jolt 将大大改变 SNARK 的设计方式，从而提高性能和可审计性。本系列的后续文章将深入探讨 Lasso 和 Jolt 的工作原理。