关于Lasso、Jolt和最近SNARK设计进展的技术常见问题解答

今天，Ben Diamond 和 Jim Posen 来自 Ulvetanna（D&P）发布了 一篇论文，改进了 Ligero/ Brakedown 多项式承诺方案，并将其与基于 sum-check 的 SNARK 集成，如 Lasso。你可以 阅读我对他们工作的介绍及其影响，并查阅 Ben 和 Jim 的 github 代码库（称为 Binius）和 博客文章。此 FAQ 回答了我在讨论 Lasso、Jolt 和 Binius 时被问到的问题。

1. 相对于 RISC-V 程序的原生执行，你认为 Jolt 证明者的速度可以有多快，一旦 Jolt 被重新实现以使用 D&P 的承诺？

这是一个粗略和推测的估计。Jolt 证明者在 RISC-V CPU 的每一步中承诺大约 800 位的数据，使用 32 位数据类型和乘法扩展（有两个警告：首先，一些 RISC-V 指令通过多个伪指令处理，例如，除法指令通过让证明者提供商和余数来处理，并通过乘法、加法和不等式检查来检查这两者。第二，这个数字在我们对 GF[2128] 的查找表分解进行处理后可能会有所变化）。

使用 D&P 的承诺方案，假设递归不会成为瓶颈，对于一个 T-步计算，主要承诺成本如下。

首先，对大约 200 T 字节的数据应用加法 FFT。更精确地说，Ligero/Brakedown 证明者执行 O(√TT) 个独立 FFT，每个大小为 O(√TT)。 （这比执行一个长度为 O( T) 的单个 FFT 所需的总工作更少，且更具优越的并行性。）其次，使用标准哈希函数（如 Keccak 或 SHA2）哈希大约 200 T 字节。

根据实证数据，D&P 发现 FFT 和哈希大致是证明时间的相等贡献者。

使用大约 70 个 RISC-V 周期每字节 用 Keccak 哈希的估计，我们可以预期这些操作大约比简单运行 RISC-V 程序慢 30,000 倍。也就是说，为了证明 Jolt 证明者正确执行了 RISC-V 程序 Ψ，证明者（自身实现为 RISC-V 时）将花费至少 30,000 倍于 Ψ 本身的周期。

这些承诺成本是“足够快”的，以至于证明者的瓶颈可能是其在 sum-check 协议中执行的域操作（即使合并了 针对小特征场的优化）。因此，作为一个粗略和推测的估计，我想 Jolt 证明者（当自身实现为 RISC-V 时）将比简单运行 RISC-V 程序慢大约 50,000 倍。

整个计算有点傻：当 Jolt 部署时，证明者自身不太可能在 RISC-V 中实现。但它确实给了我们一个大致的方向，说明人们可能会如何考虑估计 zkVM 的证明者开销。

虽然 50,000 倍的减速看起来很大，但它比我 乐观估计 一年前可以实现的 1,000,000 倍的开销快 20 倍。这个改善的主要原因是由于 Lasso 和 Jolt 解锁了较少的承诺数据量（每个承诺值的大小也较小）。其余的则是由于更好的承诺方案（例如，提高了使用快速哈希函数并在基于哈希的 SNARK 中利用承诺值小巧的能力）。

2. D&P 为 Keccak 和 Grøstl 提供了快速 SNARK。为什么选择这些哈希函数？还有哪些其他哈希函数适合这些技术？

Keccak/SHA3 是一个显而易见的选择，因为它是 NIST 标准，Ethereum 的预编译，且是 Type-1 zkEVMs 的关键瓶颈。（SHA3 是正式的 NIST 标准，Keccak 是以太坊的预编译，它们在 SNARK 成本无关的小方面上只有细微差别。）

D&P 考虑 Grøstl，因为它在维持 Keccak 许多优点的同时，应该能导致更快的证明者。特别是，Grøstl 在 NIST 的 SHA-3 竞赛中进入了最后一轮，因此受到严格的密码分析审查（即使最后没有被选中），并且它使用 AES S-box。由于具有 AES 加速指令，Grøstl 在 Intel 芯片上的运行比 Keccak 更快。

D&P 的证明者对于 Grøstl 应该比 Keccak 更快，因为 Grøstl 本质上是在 GF[28] 上原生定义的，这意味着 D&P 的证明者可以承诺比使用 Keccak 更少的场元素。（有关这如何使证明者受益的详细信息，请参见第 #9 项下的内容。）结果是，Grøstl 应更适合于（递归）SNARK，因为它对证明者和芯片都更快。

D&P 的 SNARK 根本不是专门针对 Keccak 和 Grøstl 的。这些技术应该适用于很多其他哈希函数。例如，D&P 预计 SHA2 也会像 Keccak 一样好，但尚未完成详细工作。

3. 我以为 Lasso/Jolt 针对的是椭圆曲线基的承诺方案？

不，Lasso 和 Jolt 并不特定于基于曲线的承诺。但它们相较于以往工作的优势，在几个月前最明显，当时与基于曲线的承诺结合使用。这是因为基于曲线的承诺在证明者必须向随机域元素承诺时要付出特别高的代价，因此 Lasso/Jolt 避免这一点的创新能力在使用这些承诺时表现得尤为显著。

简言之，尽管之前没有人设计基于曲线的 SNARK 以利用小值的承诺，但是通过针对小场工作的基于哈希的承诺在某种程度上已经为此进行了探讨。

但是 Lasso 和 Jolt 在使用基于哈希的承诺时甚至还有两种方法大大改进了以往工作。首先，D&P 证明基于哈希的承诺可以从仅承诺小场元素中获得比以往所知更强的好处。例如，目前的承诺方案承诺 1 位值的证明者成本与承诺 32 位值的成本相同，而 D&P 的方案中，承诺 1 位值的成本几乎便宜了 32 倍。（ 查看我其他帖子以获取详细信息。）其次，Lasso 和 Jolt 不仅确保证明者只承诺小范围元素，他们还确保证明者承诺的域元素数量比非 sum-check 基础的 SNARKs 要 少。事实上，在 Jolt 中，我们仔细统计了所有承诺的场元素的总位复杂性，并确认它远低于现有 zkVM 所需的。

最近一个技术问题促使我们在 Lasso/Jolt 发布几个月时强调基于曲线的承诺：唯一具有多对数证明大小的基于哈希的承诺方案 FRI，针对的是单变量多项式，而 Lasso/Jolt 使用的是多线性多项式。（请参阅最近的 博客文章 进行阐述。）几篇 已知 转换 将 FRI 转换为多线性多项式的承诺方案，但这些增加的开销（在证明者时间、证明大小或两者中）我们认为极其不具吸引力。BaseFold 则新允许在必需的多对数证明大小下进行“直接”的多线性承诺，尽管生成的证明者比 Brakedown 的慢，且证明比 FRI 的大。

与 FRI 相比，Ligero/Brakedown 承诺方案直接适用于多线性多项式，并且具有非常快的证明者。但以往在使用递归降低其证明大小时是困难的，因为验证者需要进行大量哈希操作，使递归的开销很高。通过为哈希提供更快的 SNARK，D&P 的工作将大大降低这种递归的成本。

4. 你不是说过基于曲线的承诺方案比基于哈希的承诺方案更快（当仅承诺小值时，如在 Lasso/Jolt 中）吗？这与你对 D&P 的 SNARK 的认可有何矛盾？

首先，正如我之前 所说的 之前，在某些重要的 SNARK 应用中，基于哈希的 SNARK 绝对不是最具性能的，因为在椭圆曲线组的基础场上工作是合理的。在这些场上，基于曲线的承诺更快。证明有关椭圆曲线密码系统的任何声明（包括知识 ECDSA 数字签名以授权区块链交易）都属于此类。

第二，即使在合理使用小特征场工作的应用中，基于哈希的方案与基于曲线的方案的性能比较也很复杂。例如，这在很大程度上取决于在基于哈希的方案中使用的哈希函数的速度。目前，许多（但 不是 所有）项目使用更慢的哈希函数，如 Poseidon，以便实现递归。在这种情况下，基于哈希的方案 显然比 基于曲线的方案慢（当承诺的小值，如在 Lasso/Jolt 中）。即使使用快速哈希函数，它们也显然不一定更快（根据我 之前 的评论）。

但是 D&P 通过在小特征场上工作时加快基于哈希的承诺，并允许证明者更好地利用小价值的承诺，来加强基于哈希的方案，相对于现有的基于哈希的方案，如 FRI。因此，我目前的预期是，Ligero/Brakedown 在小特征场上将是前进的方向，除非 证明声明在其他有限场上原生定义。

总之，直到今天，人们相信基于哈希的承诺方案比基于曲线的方案更快的主要原因是流行的 SNARK（如 Plonk）要求证明者向随机场元素承诺，而不是小场元素，并且在这种情况下，基于曲线的承诺方案非常慢。Lasso 和 Jolt 显示，证明者不必承诺随机领域元素。在这种情况下，比较至少更加细致。到今天为止，基于曲线的方案实际上更快，但随着 D&P 的改进，现在情况反转（除非是在大型场上原生定义的声明）。

5. 你不是说过基于哈希的承诺方案安全性低吗？

并没有任何关于基于哈希的承诺方案（如 FRI 或 Ligero/Brakedown）不安全的本质。然而，项目在实际中普遍优先考虑性能而非安全性，因为在已知攻击接近可行的配置下部署 FRI，并假设这些已知攻击对 FRI 是完全最优的。

Ligero/Brakedown 承诺的一个好处是，关于 FRI 的主要猜测（即，关于其在接近参数上的安全性，超出 Johnson 上限）并不相关，因此没有 SNARK 设计者基于这些猜测的诱惑。

同样，我对在 SNARK 部署中使用表面上“对 SNARK 友好的”哈希（如 Poseidon）的做法也一直心存疑虑。这些哈希的安全性（即使是那些存在时间最长的）并没有受到与标准哈希（如 Keccak）同样的审视。

在上述两种情况下，我的观点是，项目一直在危害安全性，以弥补当今 SNARK 的性能缺陷。消除这些做法的最简单方法就是简单地开发性能更好的 SNARK。

相关的是，我认为当前设计“对 SNARK 友好的”虚拟机以及实现这些虚拟机的约束系统的做法是一个主要的安全问题（也是开发资源的巨大消耗），因为设计约束系统和从高级语言开发新编译器到定制虚拟机的汇编代码的过程容易出错。我希望 Jolt 使这一做法不再必要，证明标准指令集实际上也是一样对 SNARK 友好，从而消除手动设计实现这些指令集的约束系统的需要或动机。

消除具有负面安全影响做法的办法是设计出更具性能的 SNARK，使该做法变得无关紧要。

6. D&P 在他们实现的多项式承诺方案中使用 Reed-Solomon 码，但 Brakedown 可以使用任何代码。探索其他代码是否值得以获得性能提升？

是的。

7. 在哪些方面 Ligero/Brakedown 更优于 FRI？

D&P 在承诺非常小值时显著改善的证明时间在 Ligero/Brakedown 中是独一无二的，至少在目前是这样。此外：

• D&P 不仅在承诺小值时改善证明时间，还改善证明空间。这是一个主要的瓶颈，尤其是对于基于哈希的 SNARK。例如，Polygon 的 zkEVM 证明者今天需要 250+ GB 的空间，以证明处理约 1000 万 gas 的交易批次的电路。
• Ligero/Brakedown 在使用的纠错代码方面有更大的灵活性。事实上，D&P 针对小值的许多改进可以通过在 Ligero/Brakedown 中使用串联编码获得。
• 使用 Reed-Solomon 码时，Ligero/Brakedown 证明者执行许多小的 FFT 而不是一个大的 FFT。这节省了 FFT 运行时间的两倍，并且更适合并行化。

FRI 还需要同时执行 FFT 和 IFFT（在技术层面上，这是因为 FRI 需要实际在多个点评估承诺的多项式）。Ligero/Brakedown 证明者可以跳过 IFFT（在技术层面上，跳过 IFFT 源于 Ligero/Brakedown 在选择纠错代码时的优越灵活性）。如果使用“Reed-Solomon 放大因子”2，这将另外节省 33% 的证明时间（这是优化证明时间的放大因子）。

• Ligero/Brakedown 的评估证明不需要证明者进行额外的 Merkle 哈希。FRI 需要（尽管大多数 FRI 的调用将评估证明的开销分摊到多个承诺的多项式中）。

8. 你能简要说明 D&P 如何确保对 GF[2] 元素的承诺比对 GF[2^2] 元素的承诺更便宜，而后者又比 GF[2^4] 元素的承诺更便宜吗？

使用 D&P 的承诺方案，证明者承诺一堆值所需的时间大致仅依赖于对这些值的指示所需的总位数，其中 b 位用于指出介于 0 和 2b 的值。D&P 的 SNARK 中的其他证明者成本确实会随着用于编码这些位的 场元素 数量而增长（请参阅 #9 中的详细信息）。D&P 是这样实现的。

Brakedown 多项式承诺方案通过任何所需的纠错码对要承诺的值向量（子向量）进行编码。假设要承诺的一堆值在 GF[2] 中，但我们希望代码本身在更大域 GF[216] 中运行。（我们有许多技术原因希望这样做，实际上，这是必需的，如果我们想应用某些代码到长度高达 216 的向量。）

为此，我们可以简单地使用代码串联，这意味着将所有的 GF[2] 值分割成大小为 16 的块，并将每个大小为 16 的 GF[2] 值块“打包”到一个 GF[216] 场元素中。这减少了要承诺的场元素数量，缩小了一个 16 倍的比例。我们然后可以应用任何在 GF[216] 上有效的纠错代码（这称为“外部码”）。结果编码的每个符号可以“解包”为十六个 GF[2] 元素，结果编码成定义在 GF[2] 上的“内部代码”。

有效地说，串联办法通过将承诺向量（按照场元素数度量）降低了 16 倍的长度，但要求证明者执行打包和解包操作，并对外部代码字的每个（解包）符号应用内部代码。

这一简单方法，通过在 Brakedown 中应用串联代码，已经实现了 D&P 工作的许多好处。但 D&P 采取了一种不同的方法，导致证明者速度更快（虽然证明稍大）。例如，D&P 的实际方法避免了对每个解包外部码符号施加内部代码的成本。

9. 既然 D&P 的承诺方案使承诺在 {0, 1} 中的值变得如此廉价，为什么不让证明者承诺计算中所有产生值的比特分解？也就是说，为什么不采用布尔电路实现整个计算，并让 SNARK 为电路中的每个输入位和门分配一个“完整”的场元素？

在他们的 Keccak SNARK 中，D&P 确实让证明者仅承诺 {0, 1} 中的值，但这并不一定是一种好的普遍做法。

确实，D&P 的承诺时间大致会随着所有被承诺值的位复杂度的总和增长，而与这些值分割成多少个场元素无关（这就是为什么在 Keccak 的 SNARK 中仅承诺值为 1 位是一个合理的做法）。

然而，这并不意味着 所有 成本都与被交付的场元素数量无关。特别是，承诺方案评估证明的大小随承诺的场元素数量的平方根增长。

在 D&P 的 SNARK 中，承诺许多场元素所需的另一项成本是，在某些应用的 sum-check 协议中需要求和的项数。大致而言，承诺 x 倍更多的场元素意味着 sum-check 证明者需要求和 x 倍多的项。有 优化 可以减轻这种开销，但缓解并不完善。也就是说，当承诺 x 个一位值时，sum-check 证明者仍然可能会比将这些值以单个 x-位场元素打包后再进行承诺要慢。

D&P 通过提供基于 sum-check 的协议，在关注的许多一位值被承诺后，将许多一位值打包成单个场元素来缓解最后这一承诺多个一位值的成本。这使他们在承诺值之后，还可避免在 sum-check 中为许多被承诺的值支付过多的 sum-check 证明者时间，同时仍然获得它们的好处（尤其是，一旦承诺比特分解，使用 sum-check 证明的某些操作，如按位与，不会额外增加承诺费用）。

10. D&P 在特征为二的场上工作的具体好处有哪些？

有许多。以下是部分列表。

• D&P 大量利用塔场构造。在特征为二的场上下，这指的是构造 GF[22] 作为 GF[2] 的 2 次扩展，再构造 GF[24] 作为 GF[4] 的 2 次扩展，然后构造 GF[28] 作为 GF[24] 的 2 次扩展，依此类推。尤其有效的 塔构造 在特征为二的场上是众所周知的。

• sum-check 协议计算 ∑x∈0,1ng(x)∑x∈0,1ng(x)，其中 g 是一个多变量多项式。布尔超方体 {0, 1}n（及其子立方体）的大小为二的幂，因此子场与子立方体对称对齐。D&P 利用这一点，使其能够轻松将许多小场元素打包到更大扩展域的单个元素中。

• D&P 当前在 Ligero/Brakedown 多项式承诺方案中使用 Reed-Solomon 码。高效的 Reed-Solomon 编码需要加法 FFT，这在特征为二的场上效果良好，但在其他场上则不然。然而，使用 其他 代码 完全可以避免对 FFT 的需求。

• 特征为二的场可以很好地由真实硬件处理。现实世界的计算机基于大小为二的幂的数据类型。在寄存器、缓存行等中，可以完美地适配最大信息，没有填充。Intel 提供将 GF[28] 的算术运算加速的原生指令（ Galois Field New Instructions [GFNI]）。通过使用塔构造，即使对于 k > 8，也可实现 GF[2k] 算术运算的极高速度。

11. 使用 D&P 的承诺方案递归合成 SNARK 时，SNARK 证明可缩溯至何种极限？

是的，使用 Ligero/Brakedown 承诺的 SNARK 的“递归阈值”略高。递归阈值是指证明的大小，使得针对验证者进行递归应用基于 Brakedown/Ligero 的 SNARK 不再产生更短的证明。我预计递归阈值大约是在几 MB 的数量级。

如果需要更小的证明，我预计这可以通过与其他小证明的 SNARK 进行组合来实现，如 #12 中所述。（如果这被证明是错误的，那不应视为 Binius 的失败，而应看作对当今流行的 SNARK 可扩展性的指责。如果它们无法在合理时间内证明数 MB 的数据已被哈希，那我们怎么能称其为可扩展呢？）

无论如何，还有其他原因证明快速递归组合是重要的。最值得注意的是，它是控制证明者空间需求的重要工具。因为（非递归）SNARK 对于证明者的空间需求非常高，人们会将大计算分解为小块，分别证明每个部分，并使用递归证明将各部分“链接”在一起（参见这篇 博客文章 来进行说明）。D&P 对标准哈希函数，如 Keccak，的快速 SNARK 使得这个递归证明能够迅速完成，即使证明大小有所增加。

12. 假设你想使用 D&P 的承诺方案与基于椭圆曲线的 SNARK（如 Plonk 或 Groth16）进行组合，以减少验证者在上链上提交证明的成本。难道这不会让证明涉及“非原生”场算术，因为 D&P 的验证者在 GF[2^{128}] 上工作，而基于曲线的 SNARK 使用大型素数场？

是的，这是一个潜在的挑战。尽管如此，我希望会找到解决方法。

一种可能性是在与基于哈希的多项式承诺方案的 SNARK（例如 FRI，转换为多线性多项式承诺方案，或者 BaseFold）组合之前，先与一种证明有更短证明的 SNARK 进行组合。注意，FRI 在特征为二的场上可以原生工作，这一设置已在最初 FRI 论文 中考虑。当前流行的 SNARKs 在使用该场上的限制来源于其使用非 sum-check 基础的多项式 IOP，而不是 FRI 本身。

这并不消除非原生场算术的问题，但大大缓解了这个问题，因为 FRI 验证者的总操作（对于 大型 多项式）的数量较少，尤其是在场操作方面，相较于 Ligero/Brakedown 验证者。

13. D&P 的承诺方案是否可以与像 Nova 这样的折叠方案组合？

这将面临与 #12 相同的问题，即折叠方案使用椭圆曲线，通常在大型素数场上定义，而 D&P 的承诺方案使用大小为二的场。

我期待在折叠方案中获得显著进一步进展，并且我认为它们将在未来的 SNARK 设计中扮演重要角色。然而，它们可能根本无法与許多特征非常小的基于哈希的 SNARK 进行良好结合。

目前，基于椭圆曲线的承诺和折叠方案应基于在大型场中原生定义的声明使用，或者在证明者空间极为重要时使用（像 Nova 这样的折叠方案在证明者空间方面远远优于其他 SNARK，因为它们可以将大型计算拆分成比其他 SNARK 更小的块）。而对于其他情况，应使用基于小特征场的基于哈希的方案。

此外，未来针对折叠 Schemes 的进展也有可能使其超越基于哈希的方案。实际上，Nova 已经在某些基准测试中比当前一代基于哈希的 SNARK 更快 测试（尽管许多声称当今基于哈希的 SNARK 比基于曲线的 SNARK 更快）。

14. 使用基于哈希的多项式承诺方案是否可以通过在哈希所有值之前先将许多小场元素串联在一起，从而实现“按位付费”？也就是说，为什么 D&P 的结果不显而易见？

基于哈希的承诺方案有两个操作，两个操作在实际中均可能成为瓶颈：FFT（或更一般，这是一种纠错代码的编码操作）以及哈希。

即使在向量中所有经过 FFT 的值都较小（例如几位），然而，转换中的 twiddle 因素 将仍然更大，因此在进行更大值的算术时仍需支付费用。而且，由 FFT 产生的向量与输入 FFT 的向量相比将有“额外”的场元素，这些额外的场元素并不小（更糟糕的是，如果使用非系统性代码，如 D&P 的情况，那么整个编码向量就不会再小，而不仅仅是“额外”元素）。在计算承诺时必须哈希的是 FFT 的结果。因此，FFT 中对场算术成本的利用并未充分改善小值的承诺，哈希成本同样如此。

确保小值更快地转化为更快的 FFT 和更快的 Merkle 哈希的合理方式是，将多个小值打包到单个场元素，以便将其转换为较大值的短向量，而不是将小值逐一处理。特征为二的塔场设计使得此打包操作在字面上对应于将小值的二进制表示串联起来，以获取（串联的）场元素的二进制表示。这正是 D&P 所做的。

然而，事情并不像前面段落所示的那样简单。大多数复杂性不是由于承诺过程本身（其中只涉及对一个或多个 FFT 转换向量的 Merkle 哈希），而是由于多项式评估证明过程中的情况。在此时，在多项式承诺方案中存在多个（子）场，例如与 Reed-Solomon 编码相同的字母的扩展字段，评估过程中提取到的随机值等。这些不同字段的交互是复杂而难以定义和分析的。

阅读 原始博客文章。

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

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