以更快的承诺方案助力Lasso/Jolt

本文主要是介绍以更快的承诺方案助力Lasso/Jolt，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 引言

前序博客有：

基于Towers of Binary Fields的succinct arguments
multilinear多项式承诺方案benchmark对比
关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答
Lasso、Jolt 以及 Lookup Singularity——Part 1
Lasso、Jolt 以及 Lookup Singularity——Part 2
深入了解Lasso+Jolt

之前已介绍过Lasso和Jolt所实现的SNARKs，不仅具有更好的性能，还更易于构建和审计。

Lasso为新的lookup argument，具有快得多的prover。
Jolt，基于Lasso，构建了zkVM-SNARKs的全新设计范式，支持prover证明某计算机程序正确运行。在某些特定虚拟机中，该计算机程序是以汇编语言编写的。
Lasso和Jolt的核心技术工具为sum-check protocol——用于将prover所需承诺的数据量（和每个数据片段的“size”）最小化。数据承诺的开销，是SNARK prover性能的关键瓶颈之一。

近期，Ulvetanna团队Benjamin E. Diamond和Jim Posen（以下简称D&P）近期发布了论文《Succinct Arguments over Towers of Binary Fields》，进一步改变了游戏：

改进了Ligero/Brakedown多项式承诺方案：支持prover对每个committed value的开销为roughly “pay by the bit”。
- 当将其与Lasso结合，可获得快得多的SNARKs，D&P称该实现为Binius。
并将其与基于sum-check的SNARK方案（如Lasso）结合。
开源代码见：
- https://github.com/recmo/binius（Rust + Sage）【基于plonky3等库】【Binius：针对硬件优化的SNARK】

这些开发不仅具有更好的性能，还表明，我们对SNARK设计的关键方面概念化不正确。如，Jolt已经表明，当手工设计“SNARK-friendly”虚拟机时，实际上已根据当今流行SNARK的人为限制对其进行了定制。D&P显示，对SNARK-friendly的哈希也是如此。在这篇文章的最后，还将解释SNARK设计需要改变的地方，包括如何看待它和构建什么。

并在如下文章中，补充了D&P的贡献：

BabySpartan: Lasso-based SNARK for non-uniform computation
The Sum-Check Protocol over Fields of Small Characteristic

2. 通过Lasso，为Circuit-SAT实现更好的SNARKs

Jolt，可看成是将Lasso用于VM执行，其包含了一次又一次简单地fetch-decode-execute该VM cycle。然后，Lasso更具备普遍适用性。

首先D&P使用Lasso来给circuit satisfiability更好的SNARKs。此处“circuit”支持Plonkish约束系统。可将其看成是将Lasso用于（潜在）non-uniform computations。与VM执行不同，VM执行本质上是一致的，因为VM重复执行相同的fetch-decode-execute周期。将Lasso用于non-uniform computations，在于Lasso比lookup argument更强大：

Lasso为对通用稀疏linear relations的argument，即意味着，对于 $M\cdot t=a$ ，其中 $M$ 为系数矩阵，其大多数元素为0， $t$ 和 $a$ 为（可能被承诺的）向量。

与Jolt类似，将Lasso用于non-uniform computations，其具有的重要属性为：

prover所需密码学承诺的values都是small的，即意味着对于不是很大的 $b$ 值，所承诺的值为 $0$ 到 $2^b$ 。称 $b$ 为每个committed value的bit-complexity。如，Jolt内，大多数的committed values有 $b\leq 25$ 。

在BabySpartan: Lasso-based SNARK for non-uniform computation中，展示了一种通用Plonkish SNARK，其原理更简单，但可能并不易于与D&P的后续贡献结合。

对Plonkish约束系统的新的Lasso-based SNARKs，更易于将Lasso底层技术，与现有明确支持Plonkish的工具（如Halo2）集成。

3. 对small values的更快的多项式承诺方案

之前已提到，大多数SNARKs包含两大要素：

1）Polynomial IOP
2）多项式承诺方案

Prover关键瓶颈通常在多项式承诺方案。

当今流行的两大多项式承诺方案为：

1）基于椭圆曲线的多项式承诺方案，典型代表有KZG承诺方案和Bulletproofs/IPA承诺方案。
2）基于哈希的多项式承诺方案，典型代表有FRI承诺方案。

这两大类承诺方案，对small values承诺，都比对big values承诺，要更快。但prover开销，为values size的step函数：

随着values size增加，开销大多数都是平缓的，偶然会有大幅跳跃。

在基于椭圆曲线的多项式承诺方案中，通过Pippenger’s algorithm：

Prover以单个group运算来对1-to-20 bit values进行承诺
Prover以2个group运算来对20-to-40 bit values进行承诺
Prover以3个group运算来对40-to-60 bit values进行承诺
等等以此类推。
此处，20表示，所承诺向量长度的对数，其取值通常为20到30。且上面提及的承诺开销是已摊销的。

在基于哈希的多项式承诺方案中，当今很多项目采用扩域——为large field，其内部有小得多的base field：

若所有committed values位于base field内，则承诺要更快。
当今流行的base field为31到64 bits。

尽管如此，当今现有的承诺方案从small values中受益的程度是有限的。在基于曲线的情况下，对2-bit values（即｛1，2，3，4｝中的值）承诺，并不比对20-bit values（如， $0$ 到 $2^{20}≈100万$ 之间的数字）承诺，要更快：两者都需要通过Pippenger算法进行大约一个group运算。当今流行的基于哈希的方案也有类似的情况，它们对所有base field元素的处理或多或少相同。（详情见关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答中的问题14。）

D&P为Ligero/Brakedown hash-based多项式承诺方案平滑了这一step函数，允许prover对每个committed value的开销为大致“pay by the bit”。D&P通过两种技术的结合来实现这一点：

1）首先，其使用 $GF[2^{128}]$ 域，该域具有characteristic two（与当今流行的SNARK有很大不同，SNARK的characteristic至少为 $2^{31}$ ）。其专门构造该域为tower，即意味着 $GF[2^{128}]$ 构造为 $GF[2^{64}]$ 的扩域，进而为 $GF[2^{32}]$ 的扩域，再进而为 $GF[2^{16}]$ 的扩域等等。
2）其次，其使用与code concatenation相关的技术来确保承诺1-bit value实际上比承诺2-bit value便宜约2倍，进而比承诺4-bit value便宜大约2倍等等。（详情见关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答）

效果可能是巨大的。在D&P目前针对Keccak的SNARK中，所有承诺的值都是单个bit的，且将对单个bit进行承诺的速度，提升了一个量级。另一个例子是，在Jolt中，三分之一到三分之二的committed values是单个bit的。具体将Jolt论文图4：
在这里插入图片描述

4. 对hash的更好的SNARKs

Better SNARKs for Circuit-SAT via Lasso
A faster polynomial commitment scheme for small values

这两大贡献，从而有对 Circuit-SAT快得多的SNARK——当使用characteristic two field时，比之前成果快1到2个数量级。（详情见关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答中的问题10。）

然后D&P将该SNARK用于实现Keccak（和Grøstl）哈希函数的电路，针对这些哈希函数所生成的SANRKs，要比之前的快得多。一旦彻底优化，有望每秒单线程，证明超过5000个Keccak-f permutation，并具备重组的可用并行化，使用AWS c7i.16xlarge instance with an Intel Sapphire Rapids 8488C processor。即意味着，在单线程处理情况下，对20-25MB数据哈希，仅需约30秒。

5. 结论

用于哈希的更好的SNARK本身就很强大，因为应用SNARK的许多密码学statements（如knowledge of Merkle-authentication paths）都可归结为哈希。事实上，这是Type-1 zkeVM以及基于哈希的递归SNARK中的关键瓶颈。

因此，虽然Lasso能够为哈希提供更好的SNARK，但它（以及Jolt）也从中受益：

更好的哈希SNARK使Lasso和Jolt能够与Ligero/Brakedown基于哈希的多项式承诺方案（的递归版本）相结合。这些方案有非常快的prover，但需要verifier进行大量的哈希运算（ $O(\sqrt{N})$ ，其中 $N$ 为所承诺多项式大小）。这使得使用Ligero/Brakedown的SNARK的递归应用变得困难，因为prover证明其正确执行了verifier的哈希运算是昂贵的。都有更快的用于哈希的SNARK，这种困难应该会消失。

具体来说，对于具有几十亿个门的电路，Ligero/Brakedown proof size的数量级为MB，Verifier V主要执行域运算（这对于递归来说很便宜）和哈希。对于可单线程（且具备充足的并行性）处理以30秒对20MB数据哈希的SNARKs，prover将递归应用于该证明系统，单线程处理时长小于10秒。

最重要的是，当使用递归时，优化Ligero/Brakedown的proof size是没有意义的，而应优化递归prover的runtime。由于与域运算相比，哈希运算的证明成本要高得多，因此应该将Ligero/Brakedown配置为让Verifier V进行更少的哈希运算，尽管这意味着更大的proof和更多的域运算。这将加速递归证明，超过上述10秒的评估。

总之，将Lasso和Jolt与（递归应用）D&P的承诺方案相结合将进一步提高Lasso和Joelt的性能。这既是因为Keccak和Grøstl是比今天流行的SNARK-friendly更快的哈希函数，也是因为，无论使用什么哈希函数，Ligero/Brakedown都有比FRI更快的prover（详情见关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答中的问题7。）

6. 重新审视对SNARK-friendly哈希函数的看法

Jolt表明，大多数zkVM项目的“SNARK-friendly” VM考量都是错误的。使指令“SNARK-friendly”的关键属性是所谓的可分解性。真正的指令集，不是为所谓的SNARK友好性而手工设计的，自然满足了这一特性。我们一直在手工设计虚拟机，以友好地应对当今流行的SNARK的限制，但这些限制是人为的。D&P显示，对SNARK友好的哈希也是如此。（为标准哈希函数充分优化D&P的SNARK，并将其性能与当今流行的应用于表面上对SNARK友好的哈希时的性能进行比较，这是近期的未来工作）。

7. 基于small fields的更快的sum-check prover

D&P所实现的SNARK for Keccak，其承诺开销如此之低，使得prover瓶颈不再是多项式承诺方案，瓶颈在于sum-check协议。sum-check协议为Lasso/Jolt底层的polynomial IOP技术核心。

但是，现有包括D&P的sum-check prover实现，都未充分优化利用values 为small的优势。即，现有的sum-check prover实现，执行少量域运算，但大多数域运算都是在“whole field” $GF[2^{128}]$ 域内的，即使实际所commit的value在小得多的subfield中——如 $GF[2],GF[2^8],或GF[2^{16}]$ 。

在The Sum-Check Protocol over Fields of Small Characteristic，利用了small values优势来优化sum-check prover。仅取决于values有多small，可将sum-check prover工作性能提升2倍或多个数量级。

未来会将这些优化嵌入到D&P实现中。

8. SNARK设计中的交互角色

如今被广泛描述为具有最先进Prover性能的SNARK使用最小交互（即，constant-round）polynomial IOP，并结合高度交互的多项式承诺方案，即FRI。（Bulletproof/IPA也是高度交互的，尽管与fast prover的关联度不高。）这与fast-prover SNARKs的设计方式相反。polynomial IOP中的交互可用来降低prover开销，而多项式承诺方案中的交互可用来降低verifier开销，通常是以prover开销为代价的。

由于prover开销是SNARK的关键可扩展性瓶颈，polynomial IOP中的交互是更具可扩展性SNARK的关键，而多项式承诺方案中的大量交互实际上会损害可扩展性。

更详细地说，FRI（和Bulletproofs/IPA）利用交互来使proof size最小化，但这是以牺牲prover time为代价的（详情见关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答中的问题7。）
。相反，应以尽可能快的prover为目标，即使这意味着proof size为slightly sublinear的。然后，可应用递归来降低proof size。这正是Ligero/Brakedown多项式承诺中所做的，它只涉及一轮交互，并且具有非常快的prover（但proof size为平方根大小）。在D&P工作之前，很难使用这些承诺方案递归SNARK，因为Ligero/Brakedown verifier必须执行如此多的哈希evaluations。事实上，像Orion这样的一些工作只是“将verifier的哈希排除在递归之外”，限制了proof size的减小和verifier工作的减少。但随着用于证明哈希evaluations的SNARK速度更快，这个问题就消失了。

polynomial IOP内的多轮交互确实对prover有很大帮助。具体来说，sum-check协议利用多轮交互来最大限度地减少prover的承诺开销。

在较低级别上，sum-check协议使用多变量多项式和多轮交互，而当今最流行的polynomial IOP使用单变量多项式和少数轮的交互。单变量方法实现了与多变量方法相同的功能，但以要求prover commit大量额外数据为关键代价。

这里发生的事情是，sum-check协议让prover（快速）进行额外的域运算，以减少prover在承诺方案中使用的（慢速）密码学运算量。这是prover time的胜利。相比之下，高度交互的承诺方案让prover做额外的密码学运算（相对于最小交互），不是为了减少prover的工作，而是为了减少verifier的开销，如proof size和verifier的工作。最好使用递归而不是交互将这些verifier开销推到prover上，只需少量增加prover time（现在有足够快的SNARKs for hash）。

概要：

应利用polynomial IOP中的交互来最大限度地减少prover必须承诺的数据量。用于承诺数据的多项式承诺方案对于prover来说应该尽可能快，但要有sublinear verification cost。多项式承诺方案只需一轮交互就足够了。然后可以通过递归降低验证开销，而不会引入新的prover瓶颈。

9. 最新开发总结

10. 对SNARK生态系统的影响

这些新成果，意味着为实现具有高性能prover的SNARKs，应改变当今deployments的每个元素，包括：

1）Polynomial IOPs：应为sum-check-based，以使prover所需commit的数据量最小化。
2）多项式承诺方案：应将，像Ligero/Brakedown这样的faster-prover、bigger-proof方案，与，递归，结合。Ligero/Brakedown具有与FRI相同的安全属性：
- 为transparent的
- 为plausibly post-quantum secure的
- 仅基于hash的
- 等等
3）哈希函数：提倡使用像Keccak和Grøstl这样的哈希函数，其证明速度至少和当今所提倡的“SNARK-friendly” 哈希函数的证明速度，是一样快的。若想要编造对SNARKs更友好的哈希函数，鉴于对高性能SNARK的实际功能和局限性的理解有所提高，必须从头开始设计新的SNARK-friendly哈希函数。
4）zkVM指令集：应使用类似RISC-V这样的标准指令集，而不是基于之前证明系统的限制来设计。同时，不行对每个指令手写设计电路。zkVM设计者应简单指定每个指令的evaluation table，并使用像Lasso这样的sum-check-based lookup argument。
5）所基于的域fields：由于各种技术原因，当今流行的SNARK需要具有相对较大characteristic的域（deployments通常使用的characteristic至少为 $2^{31}$ ）。基于sum-check协议的SNARK没有这一限制，D&P展示了如何利用像 $GF[2^{128}]$ 这样的非常小characteristic 域来获得性能上的提升。

幸运的是，需要这些更改的相同开发也导致SNARK更简单、更容易构建（尽管仍有进一步改进的空间）。特别地，Jolt 消除了手工设计zkVM的指令集或手工优化实现这些指令集的电路的需要，因为它用每个原语指令的evaluation table的简单规范来替换这些电路。这种模块化和通用的架构使得更易于swap out field和多项式承诺方案以及实现递归，并且通常减少了bug的表面积以及需要维护和审计的代码量。

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

希望本文能说服更多的项目投资开发遵循这种设计范式的SNARK。有很多需要构建。

在不久的将来，本文所提出的一些主张仍然需要通过实现来完全验证（如，将D&P针对Keccak的SNARK与表面上对SNARK友好的哈希进行比较，并完全实现递归以降低proof size）。与此同时，Jolt初步实现（采用基于曲线的承诺方案）已接近完成。一旦完成，将值得重新实现Jolt，以使用D&P的基于哈希的承诺方案。这在一定程度上涉及到这一点，主要是因为从大素数域切换到characteristic two域需要重新定义Lasso所应用的所有查找表。还希望，用于Plonkish电路的新的基于Lasso的SNARK可以简化Lasso与现有工具的集成，因为它可以将人们已经编写的电路输入到其中。

这些是显而易见的下一步行动。很高兴看到，一旦社区完全吸收sum-check协议的力量，将承诺开销降至最低，将会发生什么。

参考资料

[1] Justin Thaler 2023年11月博客 Boosting Lasso+Jolt through faster commitments – with far-reaching consequences

Justin Thaler系列博客

SNARK Design
Rollup项目的SNARK景观
SNARK原理示例
SNARK性能及安全——Prover篇
SNARK性能及安全——Verifier篇
sum-check protocol in zkproof
sum-check protocol深入研究
Lasso、Jolt 以及 Lookup Singularity——Part 1
Lasso、Jolt 以及 Lookup Singularity——Part 2
深入了解Lasso+Jolt
关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答

lookup系列博客

PLOOKUP
PLOOKUP代码解析
Efficient polynomial commitment schemes for multiple points and polynomials学习笔记
PLONK + PLOOKUP
PlonKup: Reconciling PlonK with plookup
PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge 学习笔记
Plonk代码解析
RapidUp: Multi-Domain Permutation Protocol for Lookup Tables学习笔记
Lookup argument总览
Halo2 学习笔记——设计之Proving system之Lookup argument（1）
logUp-Multivariate lookups based on logarithmic derivatives
cq：fast lookup argument
Lookup Argument性能优化——Caulk
2023年 ZK Hack以及ZK Summit 亮点记
Research Day 2023：Succinct ZKP最新进展
Lasso、Jolt 以及 Lookup Singularity——Part 1
Lasso、Jolt 以及 Lookup Singularity——Part 2
深入了解Lasso+Jolt
Lookup Singularity
Halo2、Caulk+、Baloo、Cq Lookup argument细览
Lookup Argument简史