通过更快的承诺来增强Lasso+Jolt

在今年早些时候，我们介绍了Lasso和Jolt，它们承诺能够产生不仅性能大幅提升，而且更易于构建和审计的SNARK。

Lasso是一种新的查找论证，提供了显著更快的证明者。Jolt在Lasso的基础上提供了一种根本性的新范式，用于设计所谓的zkVM——SNARK使证明者能够证明其正确运行了一个（在某些特定虚拟机的汇编语言中指定的）计算机程序。

Lasso和Jolt的核心是一种称为sum-check protocol的技术工具，利用它们来最小化证明者需要提交的数据量（以及“每个数据片段的大小”）。提交数据的成本是SNARK证明者性能的一个关键瓶颈。

今天，Ben Diamond和Jim Posen来自Ulvetanna（以下简称D&P）发布了一篇论文，进一步改变了游戏。D&P的核心贡献是对Ligero/Brakedown承诺方案的修改，使得证明者可以大致“按位支付”每个提交值。我将解释他们如何实现这一点，以及为什么结合Lasso，这将导致显著更快的SNARK。D&P称他们的实现为Binius。

这些发展不仅能够提升性能。它们还显示出我们在SNARK设计的关键方面的概念是错误的。例如，Jolt已经表明，当我们手动设计“SNARK友好”的虚拟机时，我们实际上是根据今天流行的SNARK的人工限制来调整它们。D&P表明，同样的情况也适用于SNARK友好的哈希函。本文的最后，我还将解释SNARK设计方面需要改变的内容，包括我们如何看待它以及构建什么。

（我已经发布了两篇独立且较为温和的补充笔记，以补充D&P的贡献。我还写了一篇更技术性的问答，回答了在讨论这些工作时遇到的问题。）

通过Lasso为Circuit-SAT提供更好的SNARK

Jolt可以被视为将Lasso应用于虚拟机执行的一种方式，虚拟机执行的定义是不断执行虚拟机的简单取指-解码-执行周期。然而，Lasso本身更具普遍适用性。

D&P所做的第一件事是使用Lasso为电路可满足性问题提供更好的SNARK（更准确地说，支持的“电路”是Plonkish约束系统）。这可以被视为将Lasso应用于（潜在）非统一计算（与虚拟机执行的方法不同，后者本质上是统一的，因为虚拟机重复执行相同的取指-解码-执行周期）。这一应用利用了Lasso实际上是比一个查找论证更强大的工具：它是用于一般稀疏线性关系的论证，这意味着用于建立的形式是M ⋅ t = a，其中M是一个稀疏矩阵（即大多数条目为零），而t和a是（可能被提交的）向量。

与Jolt一样，Lasso的这一应用具有重要的特性，即几乎所有证明者需要在加密上提交的值都是小的，这意味着它们的值介于0和2b之间，其中b是一个不是很大的数（我们称b为每个提交值的位复杂度）。例如，在Jolt中，绝大多数提交值的b ≤ 25。

在一篇单独的笔记中，Srinath Setty和我介绍了一种我们认为在概念上更简单但可能与D&P之后的贡献不太容易整合的 alternative SNARK（针对Plonkish的概念化）。

这些基于Lasso的新的SNARK对于Plonkish约束系统将简化将Lasso背后的技术整合到现有工具（如Halo2）中，大部分技术正尤其支持Plonkish。

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

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

当今流行的多项式承诺方案可以分为两大类。一类是基于椭圆曲线密码学，最流行的例子是KZG承诺和Bulletproofs/IPA 。另一类是基于哈希，当前最流行的例子是FRI。

对于基于曲线和基于哈希的承诺方案，提交小值所需的时间比提交大值要快。但根据所提交值的大小，证明者的成本是一个阶跃函数：随着值的大小增长，成本大致保持平稳，偶尔有剧烈的跃升。

在基于曲线的情况下，这是因为Pippenger算法，它大致允许证明者通过一次群操作提交1到20位的值，通过两次群操作提交20到40位的值，通过三次群操作提交40到60位的值，依此类推。（这里，20是提交向量长度的对数的一个替代值，通常在20到30之间，上述承诺的成本是摊销的。）在基于哈希的承诺方案中，今天的许多项目在扩展域上工作——拥有一个基域的较大场。若所有提交值都位于基域中，则计算承诺的速度更快。当前流行的基域通常是31到64位之间。

尽管如此，今天的承诺方案从小值中受益的程度是有限的。在基于曲线的情况下，提交一个2位值（即值在{1, 2, 3, 4}中）的速度并不比提交一个20位值（即介于0和220 ≈ 100万之间的数）快：这两者大约都需要通过Pippenger的算法进行一次群操作。类似的情况在今天流行的基于哈希的方案中也是如此，它们对所有基域元素的处理大致相同。（关于具体细节，请参见我伴随的技术问答中的项目14。）

D&P平滑了基于Ligero/Brakedown基于哈希的多项式承诺方案的阶跃函数，使得证明者可以大致“按位支付”每个提交值。它们通过组合两种技术来实现这一点。首先，它们在GF[2128]上工作，该域具有特征为2（与当前流行的SNARK相比，这一特征至少为231）。它们将该域专门构造为一个塔，这意味着GF[2128]是GF[264]的扩展，GF[264]是GF[232]的扩展，GF[232]是GF[216]的扩展，依此类推。其次，它们使用与编码串联相关的技术，以确保提交1位值的成本实际上比提交2位值低大约2倍，而提交2位值的成本又比提交4位值低约2倍，依此类推。（获取这一技术的概述，请参见我更技术性的伴随问答）。

这一效果可以是显著的。D&P目前针对Keccak的SNARK中，所有提交的值都是单独的位，他们的改进将提交这1位值的时间提高了一个数量级。作为另一个例子，在Jolt中，提交的值中有三分之一到三分之二只是一位值。（请参见Jolt论文中的图4，了解提交值的大小分布。）

对哈希的SNARK显著提升

这前两项贡献为电路可满足性问题提供了显著更快的SNARK——在特征为2的域上，这一速度相较于先前的工作可能快一到两整个数量级。（关于在特征为2的域上计算的技术好处，请参见我的技术伴随问答）。

D&P随后将这一SNARK应用于实现哈希函数Keccak（还有另一种叫做Grøstl的函数），为这些哈希函数提供了比之前的任何方法都要快得多的SNARK。一旦完全优化，我预计他们的SNARK每秒可证明超过5000个Keccak-f置换，单线程（在使用的测试机器上为AWS c7i.16xlarge实例，具有Intel Sapphire Rapids 8488C处理器），并且有大量的并行性可用。这意味着20-25 MiB的数据可以在大约30秒的单线程处理下快速哈希。

后果

更好的哈希SNARK本身是强大的，因为许多应用SNARK的加密声明（例如对Merkle认证路径的知识）归结为哈希。事实上，这是Type-1 zkEVMs以及回归哈希基SNARK的关键瓶颈。

因此，尽管Lasso 使得 更好的哈希SNARK成为可能，但它（以及Jolt）也 _受益_于此：更好的哈希SNARK使得Lasso和Jolt可以与（递归版本的）Ligero/Brakedown基于哈希的多项式承诺方案结合。这些方案有一个极快的证明者，但需要验证者执行相对较大的哈希操作（是提交多项式大小的平方根）。由于让证明者证明其正确执行验证者的哈希操作成本昂贵，使用Ligero/Brakedown难以进行SNARK的递归应用。考虑到哈希SNARK的显著提升，这一困难将不复存在。

具体来说，对于拥有数十亿个门的电路，Ligero/Brakedown的证明在MB级量级，验证者_V_主要执行域内操作（这对于递归过程相对便宜）和哈希操作。由于可以在30秒内通过单线程处理哈希20 MB数据（并具有良好的并行性），则证明者应只需不到10秒的单线程处理时间即可在该证明系统中应用递归。

更重要的是，在使用递归时，没必要为_证明大小_优化Ligero/Brakedown，而是应优化递归证明者的运行时间。由于与域操作相比，哈希操作的证明时间更ส昂贵，因此应配置Ligero/Brakedown，使得_V_执行更少的哈希操作，尽管这会意味着更大的证明和更多的域操作。这将使得递归证明的速度超出之前估计的10秒。

总之，将Lasso和Jolt与（递归应用）D&P的承诺方案结合将进一步提升Lasso和Jolt的性能。这不仅因为Keccak和Grøstl是比今天流行的SNARK友好的哈希函数更快的哈希函数，还因为，不管使用什么哈希函数，Ligero/Brakedown的证明者的速度比FRI更快（请见我技术问答中的#7）。

修正我们对SNARK友好哈希的看法

Jolt表明，大多数zkVM项目在认为何为“SNARK友好”的虚拟机方面是错误的。使一条指令“SNARK友好”的关键属性被称为可分解性。真正的指令集，而不是为了所谓的SNARK友好手动设计的，天然满足这一属性。我们已经根据今天流行的SNARK的限制来手动设计虚拟机，但这些限制是人造的。D&P展示了SNARK友好的哈希也同样如此。（全面优化D&P的标准哈希函数SNARK，并将其性能与目前流行的似乎是SNARK友好的哈希进行比较，是短期内的未来工作）。

针对小域的更快求和检查证明者

D&P的承诺成本现在低到在他们目前针对Keccak的SNARK实现中，证明者瓶颈不再是多项式承诺方案，而是求和检查协议（Lasso和Jolt下的多项式IOP的技术核心）。

然而，现有的求和检查证明者实现，包括D&P的，并未得到优化，以充分利用所求和的值都是“小”的这一事实。也就是说，现有的求和检查证明者实现执行很少的域操作，但大多数操作发生在“整个域”GF[2128]中，即便所求和的大多数值存在于一个较小的子域中，如GF[2]、GF[28]或GF[216]。

在我单独的笔记中，我优化了求和检查证明者，以充分利用小值。根据值的大小不同，这可以将求和检查证明者的工作量改善2倍到几个数量级。

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

互动在SNARK设计中的角色

今天广泛被认为具有先进证明者性能的SNARK使用了最小交互（即常数回合）多项式IOP，结合高度交互的多项式承诺方案，例如FRI。（Bulletproofs/IPA虽然也是高度交互的，但不常与快速证明者关联）。这与快速证明者SNARK的设计方式恰恰相反。多项式IOP中的交互可以利用来降低证明者成本，而多项式承诺方案中的交互则用于降低验证者成本，这往往是以牺牲证明者成本为代价的。

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

更具体来说，FRI（和Bulletproofs/IPA）利用交互来最小化证明大小，但这以牺牲证明者时间为代价（请见我技术问答中的#7）。相反，我们应该追求尽可能最快的证明者，即使这意味着得到略微次线性的大小证明。我们可以随后运用递归来降低证明大小。这正是Ligero/Brakedown多项式承诺所做的，它只涉及一次交互回合，并且具有极快的证明者（但证明的大小是平方根）。在D&P工作之前，使用这些承诺方案递归应用SNARK很困难，因为Ligero/Brakedown的验证者必须执行大量的哈希评估。事实上，一些作品如Orion仅仅“将验证者的哈希排除在递归之外”，限制了证明大小和验证者工作的减少。但随着哈希评估的证明速度显著提升，这一问题将不复存在。

多回合的交互配合多项式IOP确实帮助了证明者。具体来说，求和检查协议利用多轮交互以减少证明者的承诺成本。

在更低的层面上，求和检查协议使用多维多项式和多轮交互，而今天流行的多项式IOP使用单变量多项式和少量回合交互。单变量方法实现了与多维方法相同的功能，但在至关重要的方面牺牲了要证明者提交大量额外数据的便利。

这里发生的事情是，要求检查协议让证明者执行额外的域操作（快速），以减少证明者在承诺方案中使用字符串加密操作（缓慢）的数量。这对证明者时间是有利的。相反，高度交互的承诺方案让证明者执行额外的加密操作（相对于最小交互的情况），并不是为了减少证明者的工作，而是为了减少验证者成本如证明大小和验证者工作。使用递归并不是交互中更有利于降低验证者成本，而是在证明者时间上引入低阶增长（现在我们有了足够快速的哈希SNARK）。

摘要。 我们应在多项式IOP中利用交互，以最小化证明者需要承诺的数据量。用于承诺该数据的多项式承诺方案应该是尽可能快，这样可以确保具有次线性验证成本。这只需要一轮的交互即可。然后，通过递归减少验证成本，而不会引入新的证明者瓶颈。

新发展摘要

• D&P使用Lasso为电路可满足性提供更好的SNARK。该SNARK可以使用任何多线性多项式的承诺方案。
• 他们还提出一个更快的多项式承 诺方案（在特征为2的域上实设的Ligero/Brakedown）。简单来说，通过使用二进制塔域和编码串联，他们确保对非常小值的承诺速度极快（至少比先前的工作快一个数量级）。该方案对证明者来说非常快速，但有相对较大的验证成本（验证者做了大量哈希）。
• 这两项发展结合为标准哈希函数如Keccak提供了极快的SNARK（同样具有相对较大的验证成本）。
• 更快的哈希SNARK实现递归，而尽管 它们的验证成本仍较大。
• 最终，递归解决了验证成本大这一问题。

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。我们还有很多建设的工作。

在不久的将来，我所提出的一些论点仍需通过实施完全验证（例如，比较D&P针对Keccak的SNARK与针对表面上是SNARK友好的哈希的SNARK，并完全实现递归，以降低证明大小）。与此同时，我们的初步Jolt实现（基于曲线的承诺方案）几乎完成。一旦完成，为了使用D&P的基于哈希的承诺方案，重新实现Jolt将是值得的。这涉及一定程度的复杂性，主要因为从一个大质数域切换到特征为二的域需要重新定义所有应用了Lasso的查找表。我还希望新的基于Lasso的SNARK在Plonkish电路中能够简化Lasso与现有工具的整合，因为它使得人们已经编写的电路可以被输入到其当中。

这些是显而易见的后续步骤。我期待看到一旦社区完全吸收求和检查协议在最小承诺成本方面的能力会发生什么。

\\*\

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

\\*\

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