哥布林Plonk：惰性递归证明组合

作者：Zac (Aztec)

####### 标签：递归

此处有带图表的类似文档

本书是关于在 Plonk/Honk/PlonkISH 证明系统中执行高效递归证明组合的方法规范。

核心技术包括使用曲线循环，以避免执行类似 Halo2 的昂贵的非原生群运算。

我们通过引入指令机来委派昂贵的非原生群操作，从而扩展了这个概念。

我们使用聚合技术将来自多个证明的非原生群操作指令组合成一个指令集。

我们利用曲线转置电路将非原生群操作指令有效地转换为原生群操作指令。

我们定义了一个椭圆曲线 VM 电路来证明指令记录的正确性。

最后，我们定义了一个非原生域 VM 电路来执行曲线转置电路所需的非原生域运算。

主要目标是消除在递归的每一层在曲线循环之间跳转的需要，并显著降低证明者的成本。

Goblin Plonk 有什么用？

1. 资源受限的 Prover 需要构建一个包含多层递归的 ZK SNARK 证明
2. Verifier 对最终证明大小不太敏感（例如，输出证明将被另一层递归吞噬）
3. Verifier 对最终（非递归）验证成本不太敏感

上述条件非常适合 ZK rollup 架构。例如，对于一个保护隐私的 ZK rollup，每个“交易”都是用户生成的关于私有交易正确性的证明。

Goblin Plonk 可用于启用多层用户端递归。生成的证明被传递给 rollup Prover，后者具有足够的计算资源来递归验证（相对较大的）Goblin Plonk 证明。

估计成本

对于 Plonk/Honk（类似 Hyperplonk 的多线性 Plonk。论文即将发布™）验证算法，我们可以将每个非原生标量乘法转换为 5 个非原生域乘法和 1 个原生（可变基）标量乘法。

保守估计是我们的 ECC VM 可以在 64 个 width-4-UltraPlonk 等效约束中执行原生标量乘法。

NNF VM 的保守估计是每个非原生乘法需要 10 个 width-4-UltraPlonk 等效约束。

对于需要（保守地）64 个标量乘法进行验证的 Honk 证明，这相当于 7,296 个约束。

希望我们可以做得更好。使用 UltraPlonk 约束来蛮力计算 64 个标量乘法的等效成本接近 300,000 - 400,000。

符号

本文档假定所讨论的曲线循环是半配对 BN254/grumpkin 曲线循环。使用显式曲线/参数来解释协议会更容易一些。将本文档中的技术应用于任何曲线循环（例如 pasta/vella 曲线）都很简单。

我们使用加法符号表示椭圆曲线群运算，例如

[A]+x⋅[B]=[C]。

核心技术

曲线循环

椭圆曲线

A 定义在域

Fq 上。由此产生的椭圆曲线子群的阶数为

p。

如果

A 的 cofactor 为

1，则总是存在一个对应的定义在

Fp 上的曲线

B，其子群的阶数为

q。

一个定义在曲线

A 上的 SNARK 电路可以有效地评估曲线

B 上的群运算，反之亦然。

对于我们计划实现的 Honk，BN254 和 Grumpkin 曲线构成了这个曲线循环。

参见这篇 halo2 文章以获取更多信息。

曲线循环的缺点

在 BN254 电路中验证 BN254 证明需要非原生群运算。

一种解决方案是定义一个 Grumpkin 电路来执行 BN254 标量乘法。

现在，BN254 电路可以验证这个 Grumpkin 证明的正确性，而不是直接执行非原生群运算。

然而，这种方法并不完美。现在必须验证 2 个证明而不是 1 个（假设一个在 1 个曲线上评估核心协议逻辑，并纯粹使用循环曲线进行递归验证）。每个证明都需要大量的哈希运算，特别是当证明系统的 IPA 使用 sumcheck 协议时。

此外，验证 Grumpkin 证明所需的域运算是 BN254 电路中的非原生运算。

将这些域运算委派给递归栈中的未来 Grumpkin 电路是一项非同小可的任务。在某些时候，我们必须将曲线 A 电路 witnesses 链接到循环曲线上 SNARK 的公共输入。这总是需要（许多）非原生域运算。

计算委托

考虑原始问题；我们需要在 BN254 电路中验证 BN254 证明。

除了执行非原生群运算（或验证 Grumpkin 证明的正确性）之外，还有第三种解决方案。

我们使用修改后的查找表协议（例如 plookup）从查找表中读取。

查找表包含我们需要的精确非原生群运算的输入/输出。

我们将“预计算”查找表 commitments 定义为

[Y0]IM,[Y1]IM,[Y2]IM,[Y3]IM。这些代表独立于我们现有 Plookup 协议 commitments 的 commitments。假设是查找表 commitments 的数量跟踪底层证明系统的“宽度”（我们的 UltraPlonk/Honk 实现的宽度为 4）

commitments

[Y0]IM,[Y1]IM,[Y2]IM,[Y3]IM 代表对指令机记录的 commitments。Prover 最终必须生成一个记录正确性的证明。

我们将使用曲线转置协议将这些 commitments 转换为Grumpkin曲线上的 commitments。

由此产生的证明记录结果的电路（并评估所需的群运算）随后将在 Grumpkin 曲线之上定义，并且只需要原生（可变基）群运算。

记录聚合

为了最大化 Prover 的效率，我们希望对一组递归证明执行一次曲线转置协议。

此外，我们只想计算一次记录正确性的证明。

即，递归不应需要递归验证记录证明

为了实现这一点，我们的递归步骤必须有效地聚合两个记录 commitments。

为了更好地构建问题，考虑递归验证场景。我们有一个证明

πi 代表递归栈的步骤

i。我们假设

πi 包含对记录的前一个和当前版本的 commitments：

[Y→]IM,i−1,[Y→]IM,i。我们还有步骤

i−1 时记录的度数（

ci−1）和步骤

i 时的记录条目数（

ccurrent）（例如，它是验证密钥的一部分）。

假设我们通过归纳法知道步骤

i−1 时的记录是正确的，我们可以为证明

πi 推导出记录 commitment。

具体如何做到这一点取决于记录多项式的表示。为了举例说明，我们假设单变量 commitment 在系数基上（即 Honk 和 HyperPlonok 中发生的情况）。

假设两个记录多项式集合的前

ci−1 个系数相同，则两个记录多项式集合的描述如下：

对于 j∈[0,…,3]:Yi−1,j(X)=∑j=0ci−1−1yjXj对于 j∈[0,…,3]:Yi,j(X)=∑j=0ci−1+ccurrent−1yjXj

即

对于 j∈[0,…,3]:Ycurrent,j(X)=Yi,j−Yi−1,jXci−1

此外，必须证明

Ycurrent,j(X) 的度数为

ccurrent−1（或者，通过 SNARK IOP，证明过去

ccurrent 的行值为零）。

当使用多线性证明系统时，聚合章节中描述了一个示例聚合方案。

曲线转置

一旦计算出一组递归证明，我们将剩下在 BN254 曲线上聚合的记录 commitments

[Y1]IM,[Y2]IM,[Y3]IM,[Y4]IM。

这些 commitments 将表示执行 BN254 椭圆曲线运算的指令。

我们希望提供Grumpkin曲线上的记录 commitments，并证明两条曲线上 commitments 的等价性。

我们可以使用相对少量的非原生域运算来实现这一点。

首先，我们获取一组 Grumpkin 多项式 commitments

[z0],...,[z4]（Grumpkin 记录使用 5 列，有关更多详细信息，请参见椭圆曲线 VM规范）。

我们在一个随机 challenge

ζ 处评估 Grumpkin 多项式，并获得多项式评估

z0(ζ),z1(ζ),z2(ζ),z3(ζ),z4(ζ)。

原始记录 commitments

[Y1]IM,[Y2]IM,[Y3]IM,[Y4]IM) 中编码的 witness 和 Grumpkin commitments 中编码的 witness 之间会有一个简单的映射。这要求所有 witness 都小于两条曲线的子群阶数。这将需要范围检查。

我们可以使用 BN254 SNARK 电路从 BN254 记录 commitments 中推导出 Grumpkin 多项式系数。然后，我们在 BN254 SNARK 电路中直接评估 Grumpkin 域中声明的 Grumpkin 多项式。这需要非原生域运算。

注意：将 witness 限制为小于群阶的范围检查可以“免费”获得，因为非原生域运算组件将对输入应用适当的范围约束。

指令机

我们需要两个定制的电路，分别执行非原生域运算和椭圆曲线群运算。

前者将在 BN254 曲线之上构建/证明。后者将在 Grumpkin 曲线之上构建/证明。

出于效率原因，我们希望将这些电路设计为虚拟机。

与其定义必须为真的简单条件（例如“

a∗b==c mod p ”或“

[P]==s∗[Q]”），不如使用具有可更新内部状态的电路，Prover 的效率更高。

例如，“计算

a∗b mod p 并将结果添加到累加器中”，或“计算

s∗[Q] 并将结果添加到累加器中”。

这种方法减少了记录中需要的信息量。这很有价值，因为每个记录多项式度数都需要一个非原生域乘法来评估。

对于 Goblin 递归，此“指令机”唯一需要的指令是 BN254 群运算（包括标量乘法运算）。但是，我们可以扩展这个概念，在 IM 中添加其他有用的指令，这将提高 Prover 的效率（例如 SHA256，与 BN254 群运算无关的非原生域运算）。然后，每种指令类型都可以在递归栈的末尾由一个专门构建的定制电路进行评估。

• 原文链接： hackmd.io/@aztec-network...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～