a16z：Lasso+Jolt，快速承诺的崭新前景

编者按：

a16z Crypto 推出了两项与 SN ARK 相关的技术：Lasso 和 Jolt。它们解决了三个关键问题：性能、开发人员体验和可审核性。

其中 Lasso 是一种新的查找参数，可以显著提高证明者成本；Jolt（Just One Lookup Table）是一个专为与以太坊虚拟机兼容的 Rollups 设计的框架，一种利用 Lasso 构建 SNARK VM 的新颖方法。Lasso 和 Jolt 可以显著加快 Web3 中的扩展和构建应用程序，它们共同代表了一种全新的 SNARK 设计方法，可将广泛部署的工具链的性能提高一个数量级甚至更多级。

a16z 的研究合伙人、乔治城大学计算机科学系的副教授 Justin Thaler 深入探讨了最新的 SNARK 技术发展，强调了通过改变现有部署的各个组件，包括多项关键技术，以获取具有高性能证明者的 SNARKs 的必要性。Justin 建议使用基于求和检查的多项式 IOPs 和结合更快的证明者、更大证明的方案，如 Ligero/Brakedown，再加上递归，以实现更高效的 SNARK 系统。此外，他强调了对于更简单、易于开发的 SNARK 系统的迫切需求，以提高可审计性和安全性。

今年初，我们推出了 Lasso 和 Jolt，它们不仅性能更强大，而且更易于构建和审计的 SNARK。

Lasso 是一种具有明显更快证明者的新型查找参数。Jolt 基于 Lasso，提供了一种根本上新的设计范例，用于设计所谓的 zkVMs - SNARKs，使证明者能够证明它正确地运行了计算机程序（以某个特定虚拟机的汇编语言指定）。

Lasso 和 Jolt 的核心都是一种称为 sum-check 协议的技术工具，它们使用该协议来最小化证明者必须承诺的数据量（以及每个数据片的「大小」）。承诺数据的成本是 SNARK 证明者性能的关键瓶颈。

今天，Ulvetanna 的 Ben Diamond 和 Jim Posen（以下简称 DP）发布了一篇改变游戏规则的论文。DP 的核心贡献是修改了 Ligero/Brakedown 承诺方案，使证明者可以对每个承诺的值「按位」付费。我将解释他们是如何实现这一点的，以及为什么与 Lasso 结合使用，这导致 SNARK 性能大幅提升。DP 将他们的实现称为 Binius。

这些发展不仅提高了性能，也表明我们一直在错误地构思 SNARK 设计的关键方面。例如，Jolt 已经表明，当我们手工设计「SNARK-friendly」VMs 时，实际上我们一直在为今天流行的 SNARKs 的人工限制进行定制。DP 表明，SNARK-friendly 哈希也是如此。在本文末尾，我还将详细说明关于 SNARK 设计需要发生哪些变化，无论是我们如何思考它还是我们构建什么。

通过 Lasso 实现更好的 Circuit-SAT SNARK

Jolt 可以看作是将 Lasso 应用于 VM 执行的一种应用，其定义包括一遍又一遍地执行 VM 的简单取指-解码-执行循环。然而，Lasso 本身具有更广泛的适用性。

DP 的第一步是使用 Lasso 为电路可满足性提供更好的 SNARK（更准确地说，支持的「电路」是 Plonkish 约束系统）。这可以看作是将 Lasso 应用于（潜在的）非均匀计算（与 VM 执行不同，后者在本质上是均匀的，因为 VM 反复执行相同的取指、解码和执行循环）。这种应用利用了 Lasso 实际上比查找参数更强大：它是一种用于一般稀疏线性关系的参数，用于建立 M⋅t = a 的关系，其中 M 是一个稀疏矩阵（即，其大多数条目为零），而 t 和 a 是（可能已提交的）向量。

与 Jolt 一样，对 Lasso 的这种应用具有重要的特性，即证明者几乎需要进行密码学承诺的所有值都很小，意味着它们在 0 到 2b 之间，其中 b 是一个不是很大的数字（我们将 b 称为每个承诺值的比特复杂度）。例如，在 Jolt 中，对于大多数承诺的值，b ≤ 25。

在另一篇文章中，Srinath Setty 和我提出了一种 Plonkish 泛化的替代 SNARK，我们认为这种替代方法在概念上更简单，但可能不太容易与 DP 随后的贡献整合。

这些基于 Lasso 的新的 Plonkish 约束系统 SNARK 将使 Lasso 基础技术更容易整合到现有的工具（如 Halo2）中，其中许多工具专门支持 Plonkish。

更快速的小值多项式承诺方案

首先，正如我在之前的文章中解释的那样，大多数 SNARKs 由两个组件组成：一个所谓的多项式 IOP 和一个称为多项式承诺方案的密码原语。关键的证明者瓶颈通常是多项式承诺方案。

如今，有两类广泛使用的多项式承诺方案。一类基于椭圆曲线密码学，其中最流行的例子是 KZG 承诺和 Bulletproofs/IPA。另一类基于哈希，当前最流行的例子是 FRI。

对于基于曲线和基于哈希的承诺方案，承诺小值比大值更快。但是，就证明者的成本而言，它是一个关于值大小的阶跃函数：随着值的大小增长，成本基本保持不变，偶尔会有显著的跳跃。

在基于曲线的情况下，这是由于 Pippenger 的算法，它大致允许证明者使用单个群操作对 1 到 20 位值进行承诺，使用两个群操作对 20 到 40 位值进行承诺，使用三个群操作对 40 到 60 位值进行承诺，依此类推。（在这里，20 是「承诺向量长度的对数」的替代，这个长度通常在 20 到 30 之间，并且前述的承诺成本是摊销的。）对于基于哈希的承诺方案，许多项目今天在扩展域上工作，这些域具有其中一个更小的基础域。如果所有承诺的值都驻留在基础域中，则计算承诺的速度更快，目前常见的基础域大小在 31 到 64 位之间。

然而，当前的承诺方案在受益于小值方面的程度是有限的。在基于曲线的情况下，承诺一个 2 位值（即 {1, 2, 3, 4} 中的值）的速度不比承诺一个 20 位值（即介于 0 和 2^20≈100 万之间的数字）快：两者都需要通过 Pippenger 的算法进行大致一次群操作。今天流行的基于哈希的方案也是如此，它们对待所有基础域元素都差不多。

DP 通过两种技术的组合，使 Ligero/Brakedown 基于哈希的多项式承诺方案的这种阶跃函数变得更加平滑，允许证明者大致按比特「支付」每个承诺的值。他们通过两种技术的组合实现了这一点。首先，他们在 GF[2^128] 域上工作，这个域的特征是二（这与今天流行的 SNARKs 有很大的不同，后者的特征至少为 2^31）。他们将这个域构造为一个塔，意味着 GF[2^128] 被构造为 GF[2^64] 的扩展，GF[2^64] 被构造为 GF[2^32] 的扩展，以此类推。其次，他们使用与代码串联相关的技术，以确保承诺一个 1 位值的成本真的比承诺一个 2 位值便宜约 2 倍，承诺一个 2 位值的成本大约比承诺一个 4 位值便宜 2 倍，依此类推。（有关这些技术的概述，请参阅我更详细的技术伴随 FAQ。）

这一效果可能是巨大的。在 DP 目前针对 Keccak 的 SNARK 中，所有的承诺值都是单独的位，他们的改进使得承诺这些一位值的时间缩短了一个数量级以上。举个例子，在 Jolt 中，三分之一到三分之二的承诺值只是一个单一的位。

戏剧性改进的哈希 SNARKs

前两个贡献在应用于特征为二的场域上的电路满足性方面，产生了一个更快的 SNARK，可能比以前的工作快一个甚至两个数量级。

然后，DP 将这个 SNARK 应用于实现哈希函数 Keccak（以及另一个称为 Grøstl 的函数），为这些哈希函数产生比以前任何东西都要快得多的 SNARKs。一旦完全优化，我预计他们的 SNARKs 在单线程情况下每秒可以证明超过 5,000 个 Keccak-f 排列（在基准测试中使用的机器是 AWS c7i.16xlarge 实例，配备 Intel Sapphire Rapids 8488C 处理器），并且有充足的并行性可用。这意味着 20-25 MiB 的数据可以在约 30 秒的单线程处理中进行哈希。

影响

更好的用于哈希的 SNARKs 本身就是强大的，因为 SNARKs 应用于许多密码学语句（如 Merkle 身份验证路径的知识）最终都归结为哈希。事实上，这是 Type-1 zkEVMs 以及递归哈希基础的 SNARKs 的关键瓶颈。

因此，尽管 Lasso 使哈希的 SNARKs 更好，它和 Jolt 也从中受益：对哈希更好的 SNARKs 使 Lasso 和 Jolt 能够与（递归版本的）基于 Ligero/Brakedown 哈希的多项式承诺方案结合使用。这些方案的证明者非常快速，但需要验证者执行相当多的哈希操作（在承诺的多项式大小的平方根）。这使得使用 Ligero/Brakedown 递归应用 SNARKs 变得困难，因为证明者很难证明它正确执行了验证者的哈希操作。在使用更快的哈希 SNARKs 后，这个困难应该会消失。

具体而言，对于拥有数十亿门的电路，Ligero/Brakedown 证明的大小在 MB 级别，验证者 V 主要执行字段操作（对于递归而言很便宜）和哈希操作。考虑到 SNARKs 可以在 30 秒的单线程处理时间内对 20 MB 的数据进行哈希（并且具有充分的可并行性），证明者应该需要不到 10 秒的单线程处理时间来对该证明系统应用递归。

除此之外，当使用递归时，优化 Ligero/Brakedown 的证明大小并不合理，而应该优化递归证明器的运行时间。由于相比于字段操作，哈希操作更昂贵，因此应配置 Ligero/Brakedown 让验证者 V 执行更少的哈希操作，即使这意味着更大的证明和更多的字段操作。这将加速递归证明，超出了前述 10 秒的估计。

总的来说，将 Lasso 和 Jolt 与 DP 的承诺方案（递归应用）相结合将进一步提高 Lasso 和 Jolt 的性能。这既因为 Keccak 和 Grøstl 比今天流行的 SNARK 友好的哈希函数更快，而且无论使用哪种哈希函数，Ligero/Brakedown 的证明速度都比 FRI 快。

重新审视 SNARK 友好哈希的观点

Jolt 表明，大多数 zkVM 项目对于什么是「SNARK-friendly」虚拟机存在误解。使一条指令「SNARK-friendly」的关键属性是一种被称为可分解性的东西。实际的指令集，而不是为了所谓的 SNARK 友好而手工设计的指令集，自然满足这种属性。我们一直在手工设计虚拟机，使其适应当今流行的 SNARK 的限制，但这些限制是人为的。DP 表明 SNARK 友好哈希也是如此。近期，未来的工作是完全优化 DP 的 SNARKs 以适应标准哈希函数，并在应用于表面上是 SNARK-friendly 哈希时将其性能与当今流行的哈希函数进行比较。

更快的小域求和检查证明程序

DP 目前的承诺成本已经降低到这样一个程度，在他们目前的 Keccak SNARK 实现中，证明者的瓶颈不再是多项式承诺方案，而是求和检查协议（Lasso 和 Jolt 基础多项式 IOP 的技术核心）。

然而，包括 DP 在内的现有求和检查证明程序实现并没有被优化，以充分利用被求和的值都是「小」的这一事实。也就是说，现有的求和检查证明程序执行很少的有限域操作，但是大多数这些操作发生在「整个域」GF[2^128] 中，即使大多数被求和的值存在于一个更小的子域中，比如 GF[2]，GF[2^8] 或 GF[2^16]。

在我的另一篇文章中，我已经优化了求和检查证明程序以利用小的值。取决于值的大小，这可以将求和检查证明程序的工作改进大约 2 倍，甚至是多个数量级。

将这些优化纳入 DP 的实现是短期未来的工作。

在 SNARK 设计中交互的作用

当今被广泛认为具有领先证明性能的 SNARKs 使用最小交互（即常数轮）的多项式 IOP，结合高度交互的多项式承诺方案，即 FRI。（Bulletproofs/IPA 也是高度交互的，尽管不太常与快速证明器联系在一起。）这与设计快速证明器 SNARKs 的方式相反。多项式 IOP 中的交互可以被利用以减少证明器成本，而多项式承诺方案中的交互则被利用以减少验证器成本，通常是以证明器成本为代价。

由于证明器成本是 SNARK 的关键可扩展性瓶颈，多项式 IOP 中的交互是实现更可扩展 SNARK 的关键，而在多项式承诺方案中大量的交互实际上可能会损害可扩展性。

更详细地说，FRI（和 Bulletproofs/IPA）利用交互来最小化证明大小，但这是以证明时间为代价的。相反，我们应该追求可能最快的证明器，即使这意味着仅获得略微次线性大小的证明。然后，我们可以应用递归来减小证明的大小。这正是 Ligero/Brakedown 多项式承诺中所做的，它仅涉及一轮交互，并且具有非常快速的证明器，但具有平方根大小的证明。在 DP 的工作之前，使用这些承诺方案递归 SNARKs 是困难的，因为 Ligero/Brakedown 验证器必须执行大量哈希评估。实际上，一些作品，如 Orion，简单地「在递归中留出验证器的哈希」，限制了证明大小和验证器工作的减少。但是，由于用于证明哈希评估的 SNARKs 速度更快，这个问题就消失了。

多轮的多项式 IOP 内的交互确实在很大程度上帮助了证明者。具体而言，求和检查协议利用多轮的交互来最小化证明者的承诺成本。在更低的层次上，求和检查协议使用多变量多项式和多轮的交互，而当今最流行的多项式 IOPs 使用单变量多项式和少量轮次的交互。单变量方法实现了与多变量方法相同的功能，但在关键时刻以要求证明者承诺大量额外数据为代价。

这里发生的情况是，求和检查协议让证明者执行额外的字段操作（这是快速的），以减少证明者在承诺方案中使用的加密操作的数量（这是慢的）。这对于证明者的时间是一种胜利。相比之下，高度交互的承诺方案让证明者执行额外的加密操作（相对于最小交互方案），并不是为了减少证明者的工作，而是为了降低验证者的成本，比如证明大小和验证者工作。最好使用递归而不是交互，将这些验证者成本转嫁给证明者，而证明者的时间只会略微增加（现在我们有了足够快速的用于散列的 SNARKs）。

我们应该利用多项式 IOP 内的交互来最小化证明者需要承诺的数据量。用于承诺数据的多项式承诺方案应该对证明者来说尽可能快，前提是具有次线性的验证成本。只需要一轮交互就足够了。然后，可以通过递归减少验证成本，而不引入新的证明者瓶颈。

新发展概要

DP 使用 Lasso 提供了更好的电路可满足性（circuit-SAT）SNARK。

这个 SNARK 可以使用任何多线性多项式的承诺方案。另外，他们提供了一个更快的多项式承诺方案（在特征为二的域上实例化的 Ligero/Brakedown）。简而言之，通过使用二进制塔场和代码级联，他们确保对非常小的值进行承诺非常快（至少比以前的工作快一个数量级）。这个方案对于证明者来说非常快，但验证成本相对较高（验证者需要进行大量哈希运算）。

这两个进展共同为标准哈希函数（如 Keccak）提供了极快的 SNARKs。再次强调，这一验证成本相对较高。

更快的哈希 SNARKs 使这些 SNARKs 可以进行递归，尽管它们的验证成本相对较高。

递归反过来解决了大量验证成本的问题。

加密学术文章对 SNARK 生态系统的影响

这些新的研究成果意味着，为了获得性能卓越的 SNARK 证明者，我们应该基本上改变今天部署的每个组件，包括：

多项式 IOPs（交互式证明）：它们应该基于总检查以最小化证明者需要提交的数据量。

多项式承诺方案：我们应该将更快的证明者、更大的证明方案，如 Ligero/Brakedown，与递归相结合。Ligero/Brakedown 具有与 FRI 完全相同的安全属性。它们是透明的，有可能在量子计算后期是安全的，仅基于哈希等。

哈希函数：我主张使用诸如 Keccak 和 Grøstl 之类的哈希函数，它们可以至少与今天所谓的「SNARK 友好」哈希函数一样快速地进行证明。如果我们确实想要设计出更加友好于 SNARK 的哈希函数，我们将不得不从头开始，考虑到我们对高性能 SNARK 实际能力和局限性的改进理解。

zkVM 的指令集：我们应该使用 RISC-V 的标准指令集，而不是设计在先前证明系统的限制周围的指令集。我们也不应该手动设计实现每个指令的电路。相反，zkVM 的设计者应该简单地指定每个指令的评估表，并使用像 Lasso 这样基于总检查的查找参数。

它们所涉及的领域：由于各种技术原因，今天流行的 SNARK 通常需要具有相对大特征的领域（部署通常使用至少 231 的特征）。基于总检查协议的 SNARK 没有这个限制，而 D＆P 展示了如何利用具有非常小特征的领域，比如 GF[2128]，以获得性能的显著提升。

幸运的是，导致这些变化的同一发展也使 SNARK 变得更简单、更易于构建，尽管仍有进一步改进的空间。特别是，Jolt 消除了为 zkVM 手动设计指令集或手动优化实现这些指令集的电路的需要，因为它用每个原始指令的评估表的简单规范替代了这些电路。这种模块化和通用的架构使得更容易替换领域和多项式承诺方案，实现递归，并且通常减少了错误的表面积和需要维护和审核的代码量。

这种简单性不仅对可用性和开发速度至关重要。它有助于解决一个重要的安全问题。基于 SNARK 的系统由成千上万行代码组成，需要理解多个定制的约束系统或 DSL，将永远无法足够可审计，以确保数十亿美元的价值的安全。

我希望这篇文章能够说服更多的项目投资于开发符合这一设计范例的 SNARKs。

在不久的将来，我所提出的一些观点仍然需要通过实施进行全面验证（例如，比较 DP 的 Keccak SNARK 与那些表面上友好的 SNARK 哈希函数的比较，以及充分实施递归以减小证明大小）。与此同时，我们的初步 Jolt 实现（采用基于曲线的承诺方案）已经接近完成。一旦完成，重新实现 Jolt 以使用 DP 的基于哈希的承诺方案将是值得的。这有些复杂，主要是因为从大素数域切换到二特征域需要重新定义所有 Lasso 应用的查找表。我还希望基于新的 Lasso 的 Plonkish 电路的 SNARK 能够简化将 Lasso 集成到现有工具中的过程，因为它可以将人们已经编写的电路馈送到其中。

这些是明显的下一步。我很期待看到社区完全吸收求和检查协议以最小化承诺成本的能力后会发生什么。