介绍 Lasso 和 Jolt

编辑注：在本系列中，我们将分享两个可以显著加快在 web3 中扩展和构建应用程序的创新：Lasso 和 Jolt。它们代表了一种从根本上新的 SNARK 设计方法，在性能上超过了广泛部署的工具链一个数量级或更多；提供了更好的、更易于接入的开发者体验；并使审计更加容易。

有关为什么 SNARKs 重要、它们设计的现状、需要理解的关键概念以及开发者和工程师的实现细节，请阅读 Building on Lasso and Jolt（其中还包含开放源代码实现）。研究论文可在这里找到（ Lasso， Jolt）。你还可以观看介绍 Lasso 和 Jolt、查找奇点以及思考 SNARK 设计的新方法的完整或简短视频，链接在此 YouTube 播放列表。

一个 SNARK (简洁 非互动 知识 论证) 是一种加密协议，允许任何人向不信任的验证者证明其知道满足某些属性的“见证”。在 web3 中，一个突出的应用是层级-2 （L2）rollup 向层级-1 （L1）区块链证明他们知道数字签名，授权一系列交易，因此签名本身不必由 L1 存储和验证，从而促进可扩展性。

超出区块链的应用包括快速但 不受信任 硬件 设备，证明它们产生的所有输出的有效性，以确保用户可以信任它们。个人可以 零知识 的方式证明受信单位向他们颁发了 凭证，例如证明他们足够大以访问年龄限制内容，而无需透露他们的出生日期。任何在网络上发送加密数据的人都可以向管理员证明这些数据 遵循 网络政策，而无需透露更多细节。

虽然许多 SNARK 对验证者的成本具有吸引力，但一般来说，SNARK 仍然在 证明者 计算中引入约六个数量级的开销。迫使证明者进行的额外工作高度可并行化，但百万倍的开销极大地限制了 SNARK 的应用。 （有关更多细节，请参阅我之前关于 SNARK 证明者性能、安全性 和开发 历史 的帖子，以及关于这种强大但复杂技术的 常见误解）。

更高性能的 SNARK 将加速 L2，并且可能使构建者能够解锁尚未构想的应用。因此我们引入两种新的相关技术：Lasso，一种新的查找论证，大幅降低证明者成本；以及 Jolt，利用 Lasso 提供一种用于设计所谓的 zkVM 和更通用前端设计的新框架。它们共同提高了 SNARK 设计的性能、开发者体验和可审计性，从而推动 web3 的建设。

我们对 Lasso 的初步实施已经展示了超过 10 倍的速度提升，相比流行的 SNARK 工具链 halo2 的查找论证。当 Lasso 代码库完全优化时，我们预计速度提升约为 40 倍。Jolt 在 Lasso 的基础上包含更多创新，我们预计它能达到相对现有 zkVM 遇到的类似或更好的速度提升。

查找论证、Lasso 和 Jolt

SNARK 前端 是将计算机程序转化为可以被 SNARK 后端接收的电路的编译器。电路是一种极为有限的计算模型，其“基本操作”仅为加法和乘法。

现代 SNARK 设计中的一个关键工具称作查找论证，与不受信任的证明者可加密 承诺 一large_vector，随后证明向量的每个条目都包含在某个预先确定的表中。查找论证能够通过有效处理不是通过少量加法和乘法自然计算的操作，有助于保持电路小（详见我们相关文档中讨论的位运算例子 our companion post）。

然而，“如果我们能够仅使用查找论证高效定义电路，那么这将导致更简单的工具和电路”，正如以太坊基金会的 Barry Whitehat 去年概述的愿景，他称之为 查找奇点，即我们设计的电路仅执行查找的那一刻。正如巴里所写，查找论证“在一切方面将会随着时间变得更加高效”。

此愿景与今天的运作方式形成鲜明对比，开发者通过在特定的领域特定语言中编写程序（这些程序将程序编译为多项式约束）或通过直接手工编写约束来部署 SNARKs。该工具链投入大量精力，并为安全关键的错误潜入提供了大量表面区域。即使在复杂的工具和电路下，SNARK 性能 仍然缓慢，这限制了它们的适用性。

Lasso 和 Jolt 解决了这三大关键问题：性能、开发者体验和可审计性。我相信它们实现了查找奇点的愿景。Lasso 和 Jolt 还迫使我们重新思考 SNARK 设计中许多接受的观点。本篇文章在介绍一些必要的背景之后，从新的视角审视了一些关于 SNARK 性能的共识观点，解释了在 Lasso 和 Jolt 等创新出现后，这些观点应如何更新。

SNARK 设计的背景：为什么如此缓慢？

大多数 SNARK 后端要求证明者对电路中每个门的值进行加密承诺，使用一种称为 多项式承诺方案。然后，证明者证明承诺的值确实对应于见证检查过程的正确执行。

我将来自多项式承诺方案的证明者工作称为 承诺成本。SNARK 还有其他来自多项式承诺方案之外的证明者成本。但承诺成本常常是瓶颈。对于 Lasso 和 Jolt 仍是如此。如果设计的 SNARK 中承诺成本 不是 主导的证明者成本，那并不意味着多项式承诺方案是廉价的。而是意味着其他成本比它们应该更高。

直观来说，承诺的目的是通过加密方法安全地为证明系统添加简洁性。当证明者承诺一个大向量时，大致上是将整个向量发送给验证者，如同简单的证明系统将整个见证发送给验证者一样。承诺方案的目的在于 控制 验证者成本，而不强迫验证者实际上接收整个见证。

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

Depending on which polynomial commitment scheme is used, computing a commitment involves multi-exponentiations (也称为多标量乘法，或 MSMs) ，或 FFT 和 Merkle 哈希。Lasso 和 Jolt 可以使用任何多项式承诺方案，但在通过 MSM 基础方案实例化时成本特别具有吸引力，例如 IPA/ Bulletproofs、KZG/ PST、Hyrax、Dory 或 Zeromorph。

为什么 Lasso 和 Jolt 重要

Lasso 是一种新的查找论证，其中证明者承诺的值比之前的工作少且小。根据上下文，这可以带来 20 倍或更高的加速，其中 2x 到 4x 作为较少的承诺值来源，另一 10x 的因子来源于 Lasso 中所有承诺值都是小的。与许多先前的查找论证不同，Lasso（和 Jolt）还避免了占空间且可能在大实例中成为瓶颈的 FFT。

此外，Lasso 适用于巨大表格（例如大小为 2128），只要表格是“结构化的”（在精确的技术含义上）。这些表格大到任何人都无法明确物化，但 Lasso 仅为它实际访问的表元素付费。特别是 – 与之前的查找论证对比 – 如果表是结构化的，那么没有任何一方需要对表中的所有值进行加密承诺。

Lasso 利用结构的两个不同概念：可分解性 和 LDE 结构（LDE 是指一种称为 低阶扩展 多项式 的技术概念）。可分解性大致意味着，表中的单个查找可以通过对许多较小表进行一些查找来回答。这是一个比 LDE 结构更严格的要求，但 Lasso 在应用于可分解表时特别高效。

Jolt

Jolt (J ust O ne L ookup T able) 是通过 Lasso 对能够使用巨大的查找表解锁的新前端。Jolt 针对的是虚拟机/CPU 抽象，亦可称为 指令集架构（ISA）。支持此类抽象的 SNARK 被称为 zkVM。例如，考虑 RISC-V 指令集（包括 乘法扩展），同时 RISC-Zero 项目 也以此为目标。这是计算机架构社区开发的一种流行开源 ISA，未考虑 SNARKs。

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

对于几乎每条 RISC-V 指令，生成的查找表都是可分解的，Lasso 可以应用（处理少数指令通过应用其他指令的短序列。比如，除法通过让证明者承诺一个商和余数，并检查通过一次乘法和一次加法提供它们来处理）。

然后，可以生成一个在 T 步骤内运行 RISC-V CPU 的“电路”。对于每个 T 步骤，电路包括一些简单的逻辑，以确定在该步骤执行的原始 RISC-V 指令 f i，以及该指令的输入（ x , y）。然后，电路通过执行查找简单地执行 f i，此查找会显示与该表相关联的条目的 ( x , y )'。在更确切的说法中，Jolt 考虑的是由每条指令的表的连接组成的单个表 – 因此称为“仅一个查找表”。

重审 SNARK 设计中的公认智慧

Lasso 和 Jolt 还颠覆了 SNARK 设计中的几条公认智慧。每条公认的智慧用加粗表示，后面是 Lasso 和 Jolt 如何改变它。

#1. SNARKs 在大 字段 上是浪费的。每个人都应该使用 FRI、Ligero](https://eprint.iacr.org/2022/1608)**、**[**Brakedown**](https://eprint.iacr.org/2021/1043) 或变体，因为它们避免了通常在大字段上工作的椭圆曲线技术。

此处的字段大小大致对应于 SNARK 证明中出现的数字的大小。由于非常大的数字在加法和乘法中昂贵，因此 SNARKs 在大字段上的浪费观念意味着我们应努力设计在其中不出现大数字的协议。基于 MSM 的承诺（如下所定义）使用椭圆曲线，而椭圆曲线通常在较大的字段（约 2256 的大小）上定义，因此这些已经因性能较低而声名在外。

我之前的帖子 解释过，是否明智使用小字段（即使它们是可选项）在很大程度上依赖于应用。Lasso 和 Jolt 走得更远。它们表明，即便使用基于 MSM 的承诺方案，证明者的工作几乎可以独立于字段大小。这是因为，对于基于 MSM 的承诺，承诺值的大小远比它们所处的字段大小重要。

关于 MSM 的细节。 一次规模为 n 的多重指数化（也称 MSM）计算形式为 ∏ni=1gxii∏i=1ngixi，其中每个 g i 是 群体 的一个元素。朴素的多重指数算法进行 n 次群体指数运算和 n 次群体乘法。每次指数运算的速度可以是 ~400x 更慢 相比乘法。

Pippenger 的 多重指数算法 相比于朴素算法节省了大约 log( n ) 的数量级。这在实践中可能超过 10 倍。此外，如果所有指数都是“小”的（例如，在 0 到 220 之间），则在多项式指数时间上还节省了“另一个” 10 倍。这类似于计算 g216igi216 是 g2160igi2160 的 10 倍快。前者涉及 16 次平方，而后者涉及 160 次。

如果所有承诺值都很小，Pippenger 的算法仅需 (关于) 一次群体乘法 进行价值承诺（请参阅 此论文 的第 4 节中的精彩阐述）。

Lasso 和 Jolt 的新属性。 现有 SNARK 要求证明者承诺许多 随机 字段元素。例如，在一个流行的 SNARK 后端 Plonk 中，证明者对每个电路门承诺约 7 个随机字段元素（和其他非随机元素）。这些随机字段元素将是巨大的，即使计算中产生的所有值都很小。

相比之下，Lasso 和 Jolt 仅要求证明者承诺小值（Lasso 的证明者还承诺比以前的查找论证要 少 的值）。这显著提高了基于 MSM 的方案的性能。至少，Lasso 和 Jolt 应该摒弃社区应该在证明者性能重要的背景下放弃基于 MSM 的承诺的观念。

#2：更简单的指令集导致更快的 zkVM。

只要每个指令的评估表是可分解的，Jolt 的（每个指令的）复杂性仅依赖于指令的输入大小。Jolt 证明意外复杂的指令是可分解的，尤其是 RISC-V 的所有指令。

这反驳了广泛认为更简单的虚拟机（zkVM）自然会导致更小的电路及其相关的更快证明者（每 VM 步）。这一直是特别简单的 zkVM，比如 Cairo VM 的驱动动力，这种设计目的之一就是让其对 SNARK 友好。

确实，Jolt 为更简单的 VM 的证明者比早期的 SNARK 取得了更低的承诺成本。例如，对于 Cairo VM 执行， SNARK 证明者 每个 VM 步伐承诺 51 个字段元素。Cairo 部署的 SNARK 当前工作于 251 位字段（ 63 位 是 SNARK 可以使用的字段大小的严格下限）。Jolt 的证明者每个 RISC-V CPU 的步骤承诺大约 60 个字段元素（定义于 64 位数据类型之上）。在考虑到承诺字段元素较小后，Jolt 证明者的成本大致相当于承诺 6 个随机 256 位字段元素的成本。

#3. 将大计算分解为小片段而没有性能损失。

根据这种看法，今天的项目将任何大型电路分解为小片段，单独证明每个片段，并通过 SNARK 递归地聚合结果。他们使用这种方法来缓解绩效瓶颈。

例如，今天已部署的 SNARKs 是空间密集的。作为一个代表性例子，Polygon 的 zkEVM 需要 250+ GB 的空间。这是由于将 SNARK 应用到一个具有 223 行、1164 列和“FRI 扩展因子”为 2 的“电路轨迹”。该电路处理一批消耗大约 1000 万 gas 的交易。其他项目则 使用参数（例如，字段大小和 FRI 扩展因子）进一步提高空间成本。今天已部署的 SNARKs 还需要 FFT，这是一种可能在对大电路“全盘”应用 SNARK 时形成瓶颈的超线性操作。

现实是某些 SNARKs（如 Lasso 和 Jolt）体现了规模经济（而不是今天已部署的 SNARKs 中出现的规模不经济）。这意味着，被证明的声明越大，证明者的开销相对直接见证检查（即计算电路所需的工作， لم有证明正确性）。在技术层面上，规模经济来自两个方面。

1. Pippenger 对于 n 大小的 MSM 的加速提升： 相比于朴素算法获得的 log( n ) 的因素改进。n 越大，改进量越大的。
2. 在像 Lasso 这样的查找论证中，证明者支付一次性成本，依赖于查找表的大小，但与查找的值数量无关。一次性证明者成本在对表的所有查找中平均分摊。越大的片段意味着更多的查找，意味着更好的攤提。

当今处理大电路的主要方法是将事情分解为尽可能小的部分。每个片段的大小的主要约束是，它们不能小到递归聚合证明成为证明者瓶颈。

Lasso 和 Jolt 提议了一种基本相反的方法。应该使用体现规模经济的 SNARKs。然后将大的计算分解为 最大的 片段，然后对结果进行递归。每个片段大小的主要约束是证明者可用空间，随着片段变大而增长。

#4：高阶约束对高效的 SNARK 是必要的。

Jolt 使用 R1CS 作为其中间表示。在 Jolt 中没有使用“高阶”或“自定义”约束的好处。Jolt 中所涉及的大部分证明者成本都位于查找论证 Lasso 中，而不在证明满足性所需考虑的约束系统中。

Jolt 是通用的，因此没有任何通用性损失。以此反驳开发者在设计高阶约束方面投入的剧烈关注（通常是手动指定），以努力从今天流行的 SNARKs 中挤出性能提升。

当然，有些情况下仍可能受益于高阶或自定义约束。一个重要的例子是 Minroot VDF，对于这种情况，度为5的约束可以将承诺成本削减约 3 倍。

#5. 稀疏多项式承诺方案昂贵且应尽量避免。

这是对最近引入的约束系统 CCS 和支持它的 SNARK（Super-）Spartan 和 (Super-) Marlin 的主要批评。正如我在 之前的帖子 中讨论的，CCS 是对当前流行的所有约束系统的清晰推广。

这一批评是没有根据的。实际上，Lasso 和 Jolt 的技术核心是 Spartan 中的稀疏多项式承诺方案（参见第七节），称为 Spark。Spark 本身是对任何（非稀疏）多项式承诺方案应用的通用转换，以支持稀疏多项式。

Lasso 优化并扩展了 Spark，以确保证明者仅承诺“小”值，但即使没有这些优化，批评也是不公正的。实际上，Spartan 的证明者承诺的随机字段元素比那些避免稀疏多项式承诺方案的 SNARK（如 Plonk) 更少。

此外，正如我在 之前的帖子 中讨论的，Spartan 的方法在处理重复结构的电路中特别在性能上具有额外的好处，对于这些电路，导入门不会增加 Spartan 证明者的加密工作。这个成本仅随着给定约束系统中的变量数量增长，而不是随着约束数的变化。 与 Plonk 不同的是，Spartan 的证明者不需要承诺多个“副本”同一变量。

\\\*

我们对 Lasso 和 Jolt 将实质上改变 SNARK 的设计方式的前景感到乐观，从而提升性能和可审计性。本系列中后续的帖子将更深入探讨 Lasso 和 Jolt 的工作原理。特别是，我将解释它们如何使用 sum-check protocol，这是一个在证明者承诺成本方面具有边缘奇迹般能力的关键工具。在我们继续优化 Lasso 并建立 Jolt 的过程中，我们欢迎社区的反馈。你可以通过 此处 与我联系，我还将在那里宣布未来的工作。

\\\*

感谢：Justin Thaler 与他的同事们一起开发了 Lasso 和 Jolt， Srinath Setty (微软研究) ， Riad Wahby(卡内基梅隆大学)，以及 _ Arasu Arun _(纽约大学); Lasso 的实施由 a16z crypto 工程师 _Sam Ragsdale 和 Michael Zhu _ 完成。

\\\*

Justin Thaler 是 a16z 的研究合伙人，也是乔治城大学计算机科学系的副教授。他的研究兴趣包括可验证计算、复杂性理论和大规模数据集的算法。

\\\*

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