WHIR多项式承诺方案的Gas效率

关于 WHIR 多项式承诺方案的 Gas 效率

与 @WizardOfMenlo 联合发布

TLDR; 我们为 WHIR 多项式承诺方案 (PCS) 开发了一个 开源且 MIT 许可的 原型 EVM 验证器。对于具有 22 个变量和 100 位安全性的多元多项式，验证成本为 190 万 Gas。通过更激进的参数设置，我们甚至可以达到更低的成本，低于 150 万 Gas 的水平。这使得 WHIR 成为了一个严肃的后量子 PCS 候选方案，适用于在生产中使用或希望利用 STARK 的团队。

WHIR

WHIR 是一种多线性 PCS，仅需要透明设置并保证后量子安全性，同时实现高验证速度。我们想估计一下当在 EVM 上验证 WHIR 证明时，高度验证速度将如何转化为 Gas 使用量。为此，我们开发了一个原型 WHIR 验证器，并以各种参数级别对其进行了基准测试。

我们的原型实现支持各种设置，折叠因子最大为 4 - 这是源于 Gas 优化的一种实现特性，可以很容易地修改。虽然我们展示了一组特定参数的结果，但我们的验证器是 开源且 MIT 许可的，允许任何人使用不同的配置要求对其进行测试。

节省 Gas 的策略

WHIR 配备了各种参数，并允许用户选择 Prover 应该执行多少工作以使 Verifier 受益。我们在此快速回顾一下四个重要的参数：

1. 所选的代码速率 \rho 将影响参数大小，从而影响 Verifier 的时间，但会增加 Prover 的时间。具体来说，使用 WHIR，Verifier 发出的查询（即对多项式求值的请求）的数量会随着 \rho 接近 0 而趋于 0。这意味着每次保存的查询都会转化为节省的 Gas 成本。
2. 折叠因子 k 决定了 Prover 和 Verifier 之间的轮数。更高的 k 意味着更少的轮数，但会增加 Prover 的工作量。
3. 工作量证明研磨的数量[1] 让 Verifier 减少它将从 Prover 那里索取的认证路径的数量。更高的研磨水平转化为降低 calldata 和 Verifier 的执行成本。
4. 我们还可以直接调整 WHIR 的安全参数 \lambda。实际上，这意味着更高的 \lambda 值将导致增加 Verifier 的查询和 Gas 成本。

独立于 WHIR，我们可以利用的最后一个技术是 masking。它允许通过 masking Merkle 树哈希函数的最后几个字节的输出来节省 calldata[2]。为了完整起见，我们包含了一个使用（naive）版本的这种行业标准技术的 Verifier 实现。我们回顾一下，masking 在实现 \lambda \le 128 时特别有利，因为为了达到 \lambda 安全级别，我们需要哈希函数摘要大小最多为 2*\lambda。

结果

在这项工作中，我们展示了 WHIR 验证器在不同的起始速率 \rho、折叠因子 k 和 \lambda 安全位下，对于随机采样的 16、20 和 22 个变量的多项式以及使用容量约束猜想实例化的多项式的性能。我们将绘制每个参数如何影响相对于所选 pow 研磨级别的 Gas 成本，并展示如何在使用 WHIR 时达到低 Gas 成本。

我们选择的实验参数与我们认为有用的实用性和安全性水平相符。我们的 Gas 结果是通过使用 foundry forge 和 anvil 在 0.2.0 版本 - commit e10ab3d 下计算平均交易 Gas 成本而获得的。

设置 \rho

我们首先调整代码速率，并绘制所选速率对验证器 Gas 使用量的影响。我们可以看到选择正确的起始代码速率 \rho 的影响非常大。对于 20 个变量和 30 位的 pow 研磨，当从 \rho=2^{-1} 变为 \rho=2^{-6} 时，我们可以将 Gas 成本降低一半。因此，对于我们其余的实验，我们将代码速率设置为 \rho=2^{-6}。此外，为了清楚起见，我们省略了 22 个变量的多项式的结果。我们现在也将开始绘制它的结果。

设置 k

我们下一个感兴趣的参数是折叠因子 k。如果我们有一个由 22 个变量组成的多项式，并且 pow 研磨设置为 30 位，那么当使用较低的折叠因子 k=2 而不是 k=4 时，Gas 成本最终会增加 x1.75。因此，我们现在将设置 k=4。

设置 \lambda

接下来，我们将 \lambda 参数调整到一个更激进的安全级别。我们绘制了设置 \lambda=80 如何进一步降低我们的 Gas 成本。显然，移除 20 位的安全性会导致大量的额外节省。在 22 个变量和 30 位研磨的情况下，移除的每个安全位转化为节省超过 1 万 Gas。

Masking

最后，我们为 calldata 应用了一种 naive 的 masking 策略。由于我们设置了 \lambda = 80，因此我们将承诺 masking 为 160 位 - 与 starkware 运行（或一直在运行）其验证器的级别相似。结合 \rho=6、k=4，我们得到的 WHIR 验证器的最终 Gas 成本相当具有竞争力：

• 对于 16 个变量，我们这种策略的 naive 实现平均额外节省了 2.5 万 Gas。我们最终得到的平均总 Gas 成本为 1091720 Gas，略高于 100 万 Gas 的水平。
• 如果我们的多元多项式的大小为 20 和 22，我们可以额外节省约 3.5 万 Gas。我们最终得到的平均总 Gas 成本分别为 1388230 和 1493552 Gas，低于 150 万 Gas 的水平。

相比之下，今天验证 groth16 和 fflonk 证明的成本约为 30 万 Gas。但是，WHIR 是透明的并且是后量子的。这些 Gas 成本说明了为什么我们认为 WHIR 是一个相当不错的选择，不仅与具有类似假设的协议（如 FRI）相比，而且与基于可信设置的协议相比也是如此。

未来的方向

首先，我们开发了一个原型验证器。我们相信未来会有更多的优化。其中一个唾手可得的成果是，我们代码的某些部分仍然可以从汇编重写中受益。

对于 22 个变量，使用 \lambda=80、\rho=1/2^6、k=4、30 位研磨和 masking，我们的平均 Gas 成本几乎为 150 万 Gas。但是，我们预计总优化 Gas 成本平均约为 120 万-130 万 Gas。实际上，我们当前的（平均）成本细分大致包括：calldata 为 70 万 Gas，Merkle 证明为 25 万 Gas，计算 STIR 挑战为 8 万 Gas，sumcheck 迭代为 6.5 万 Gas，Fiat-Shamir 实用程序（从 transcript 中弹出、pow 检查等）为 6 万 Gas，各种单变量/多变量求值为 2.5 万 Gas。因此，我们估计剩余的粘合代码（以内存扩展、使用抽象的开销等形式支付）大约需要 30 万 - 25 万 Gas，汇编重写将有助于减少这些 Gas。

此外，我们 masking 的实现有些 naive，因为它只是简单地将 Merkle 解压缩的最后 12 个字节清零。我们很乐意集成此 masking 策略的改进版本，以便不为 masking 值支付任何费用。在相关方面，我们执行了一个定制的多 Merkle 证明汇编实现，该实现来自 Recmo 的初始 solidity 版本。多 Merkle 证明占验证器 Gas 成本的约 20%。我们很乐意看到这里的进一步算法改进，因为我们怀疑我们的版本远非完美。

最后，WHIR 不限于特定的字段。我们很想看看这些数字在不同的较小字段中的表现如何。特别是，我们预计与使用 BN254 标量字段相比，我们的字段运算 Gas 成本会更低。

致谢

感谢 @alxkzmn 在这项工作的早期版本中帮助完成了 Merkle 和 pow 模块。

1. 有关研磨的入门知识，请参见 ethSTARK 论文 的第 3.11.3 节。 ↩︎

2. 从这种方法获得的 Gas 节省可能会在未来发生变化，请参见 EIP 7623。 ↩︎

• 以太坊的 WHIR

• 原文链接： ethresear.ch/t/on-the-ga...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～