cover_image

对Jagged多项式承诺的简洁解释

Kurt Pan XPTY
2025年06月07日 14:15

原文：https://blog.lambdaclass.com/our-succinct-explanation-of-jagged-polynomial-commitments/

作者：LambdaClass

译者：Kurt Pan

几周前，Succinct 发布了他们的论文 《Jagged Polynomial Commitments》 和使用其中描述的技术的验证者，能够在大约 12 秒内证明以太坊区块，表明链的实时证明是可能的。虽然这只代表平均情况且能耗仍然很高 ，但这是使用 ZK 扩展以太坊迈出的重要一步。该论文大量使用了多线性多项式和 sumcheck 协议，因此如果你不熟悉 sumcheck 、 GKR 和 Basefold， 建议阅读我们关于 sumcheck、GKR 和 Basefold 的帖子。有关稀疏承诺及其用途的更多背景信息，请参阅 twist and shout 和 Lasso 。有关一次读取分支程序及其在求值多线性扩展中的用途的更多背景信息，请参见此处 。

  • https://github.com/succinctlabs/hypercube-verifier/blob/main/jagged-polynomial-commitments.pdf
  • https://eprint.iacr.org/2018/861.pdf

锯齿（Jagged）函数

典型的算术化方案由多个表（例如，一个用于 CPU，一个用于 ALU，另一个用于内存等）以及一组必须在表上强制实现的代数约束组成。表的每一列都使用单变量或多变量多项式进行编码，然后证明者对这些编码进行承诺（使用多项式承诺方案，PCS）。在这两种情况下，我们都要求列的长度为 2 的幂，因为这可以通过快速傅里叶变换 (FFT) 或多线性拉格朗日基多项式实现高效编码。这施加了几个约束：

  1. 表中的所有列必须具有相同的长度
  2. 我们需要填充列以确保它们的长度等于 2 的幂。

这会导致大量的开销，因为我们需要将所有列填充到相同的长度，并在表中存储大量的哑条目（例如零值）。我们希望使用某种稀疏的数据表示，也就是说，只存储所有非哑值。此外，我们希望将所有内容压缩到一列中，以便只采用一种编码。这正是本文的重点之一，它找到了一种无需任何填充即可获得表的稠密表示的方法（我们需要列的长度等于 2 的幂，因此可能还需要一些填充）。

我们将使用一个表来解释稠密表示背后的思想，但这个想法可以扩展到多个表，只需添加一个额外的变量来跟踪表的数量以及每个表的列数。假设我们有一个包含 32 列（）的表。对于每一列，我们保留其长度 ，由非哑条目组成。例如，、、，依此类推。证明者可以构造一个向量，其条目是各列长度的累加 。因此，、、。总而言之，

请注意，由于所有  都为正数，向量  的元素是非递减的。我们可以通过将所有列依次堆叠来将它们合并为一列。给定堆叠列向量的索引 ，我们可以找到原始元素的位置。首先，寻找最小的  使得 。该  即为元素所属的列索引。然后，通过计算 （若 ，则 ）来得出行索引。这便在原始表与堆叠列之间建立了一一对应关系（下文称为稠密表示）。稠密表示的长度为 ，其中 。由此，我们可以定义两个函数：

使用字母  表示稠密表示的多线性编码，可以看到每个条目都对应于整个表多线性扩展的非哑部分 ：

这节省了大量空间来表示整个表格，但代价是需要证明者发送向量 。然后我们可以证明，如果我们要求值 ，这等价于

因为  中的任何零项都不会对求和结果产生贡献。

为什么这对多线性多项式有效？

多元多项式使用sumcheck协议将陈述归约到在随机点对多项式的求值。例如，我们可以使用sumcheck协议来证明多元多项式  在超立方体上通过zero-check求值为零：

通过与证明者交互，验证者只需在随机点  处对  执行一次求值，并进行一些涉及一元多项式的简单检查。使用多项式承诺（PCS），证明者可以为验证者提供对多项式  的访问，并使用 PCS 的求值协议查询其在  处的值。

对于单变量多项式，我们通过与求值域  上的消失多项式  相除来证明  在  上的零点性质。一般而言，如果  具有良好的结构（例如由  次单位根组成），消失多项式的求值可以非常高效（在我们的示例中，）。而对于稀疏多项式， 的表示可能非常复杂，从而无法高效计算。

因此，多线性多项式无需计算商，并且可以在更通用的域上先验运算（而快速傅里叶变换（FFT）则需要平滑域，即满足 ，且通常 ）。

如何处理大量列

本文提出了两种优化方法来处理大量的列：

  1. Fancy jagged：若表中所有列的高度相同，可减少计算  所需的信息量。
  2. 对列高度进行承诺：证明者可以将列高度附加到表格前部，并对其进行承诺。

锯齿 PCS

本文的另一个核心部分是开发一个用于稀疏/锯齿多项式的 PCS。从上面的讨论中有，

我们可以找到函数  的多线性扩展，如下所示：

使用多线性乘积的sumcheck协议，只需向验证者展示：

这又等价于

关键在于验证者可以高效计算 ，这在论文的命题 3.2.1 中得到证明。

为了高效计算该函数，论文引入了函数 ，当且仅当 $x<z$ 4="" 且="" $x="w+y$" 时，$g(w,x,y,z)="1$。该函数可与" $f_t$="" 直接关联，并可通过宽度为="" 的一次读取分支程序高效计算：<="" p="">

该证明依赖多线性扩展的唯一性，因此只需对二进制串形式的  验证相等性。如果 ，则 $i<t_y$ 且="" $i="z_r+t_{y-1}$。由于" $z_r\ge0$，可得="" $t_{y-1}\le="" i

由此我们可见，通过对  执行  次求值，便能计算 。根据命题 3.2.2，宽度为 4 的一次读取分支程序能够以流式方式逐位检查  并高效计算 。对于非消失的 ，条件 $i<t_y$ 4="" 和="" $z_r="i-t_{y-1}$" 可通过每次查看="" 位并维护两个额外变量来判断。<="" p="">

论文随后讨论了如何使用只读一次的矩阵分支程序生成符号化求值，这对于批量证明多个求值十分必要。该程序由一系列矩阵  及其输入 （）和一个汇向量  构成。给定输入 ，程序输出向量  的第一个分量，即 ，其中 。

如果矩阵是布尔矩阵（条目为  或 ），则矩阵乘法仅涉及加法（若矩阵乘法的计算仅需线性数量的加法而无需乘法，论文称之为乘法友好）。

当汇向量  未给定时，可先以符号方式执行求值；待汇向量给出后，再获得程序的最终输出。具体而言，我们可以得到一个向量 ，使得 ，其中  是由矩阵分支程序  和向量  定义的多线性扩展。向量  定义为：

批量验证多个求值

我们面临的问题是，验证者需要计算  次求值，这可能代价高昂。但通过与证明者交互，可将所有工作归约为一次求值。这遵循一种常用技巧：验证者随机选择权重 ，证明者执行随机线性组合。更具体地，假设我们要证明：

证明者随后对权重  执行线性组合：

证明者希望说服验证者每个  都满足 ，因此将  发送给验证者。验证者可自行计算右侧 。

左侧可由证明者高效计算。首先，注意到

其中  且 。换句话说， 的计算可表示为向量 （其中 ）与拉格朗日基多项式向量  的内积。由于内积是双线性的，我们可以将线性组合写成：

证明者和验证者可以对  运行sumcheck协议，最终验证者必须在随机点  处计算：

这实际上相当于对  的一次预言查询，并计算线性组合 。sumcheck协议中使用的一些优化方法可在 improvements on zerocheck 中找到。

  • https://eprint.iacr.org/2024/108.pdf

这一切将如何发展以及未来的工作

jagged方法使我们能够承诺表格的非零部分，从而节省大量工作，无论是在内存需求还是承诺时间方面。如果将此思路与 M3 算术化） 结合，即利用虚拟多项式（由迹多项式通过某些运算生成的多项式）免于承诺，我们将看到工作量大幅减少。反过来，这可降低证明时间、成本和内存占用，使我们能证明更大规模的以太坊和 L2 区块，从而有效扩展，引入更多用户并支持更多应用场景。

  • https://www.binius.xyz/basics/arithmetization/m3