我们对Jagged多项式承诺的Succinct解释

介绍

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

Jagged函数

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

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

这导致了大量的开销，因为我们需要将所有列填充到相同的长度，并在表格中存储大量的虚拟条目（例如，零值）。我们希望使用数据的某种稀疏表示，即仅存储所有非虚拟值。此外，我们希望将所有内容压缩为单个列，以便仅提交到一个编码。这正是本文的要点之一，该论文找到了一种获得表格密集表示的方法，而无需所有填充（请注意，我们需要该列的长度等于 2 的幂，并且可能需要一些填充）。

我们将使用一个表格解释密集表示背后的思想，但该思想可以扩展到多个表格，添加一个额外的变量来跟踪表格的数量以及每个表格拥有的列数。假设我们有一个包含 32 列的表格 ($32 = 2^5$)。对于每一列，我们保留每一列的长度 $l_k$，包括非虚拟条目。例如，$l_0 = 220$, $l_1 = 2^{18} + 15$, $l_2 = 2^{16} + 1475$，等等。证明者可以构造一个向量，其条目是列的添加长度，$t$。因此，$t_0 = l_0$, $t_1 = l_0 + l_1$, $t_2 = l_0 + l_1 + l_2$。总之，

$t_0 = l_0$

$t_{k+1} = tk + l{k+1}$

请注意，由于 $l_k$ 都是正数，因此向量 $t$ 具有非递减的条目。我们可以将所有列合并为一列，方法是将它们一个堆叠在另一个之下。给定堆叠列向量的索引 $j$，我们可以找到原始元素的位置。首先，我们寻找最小的 $k$，使得 $j < tk$。这个 $k$ 给出了元素所属的列。然后，我们可以通过执行 $i = j - t{k-1}$ 来计算行（如果 $k=0$，则 $i=j$）。这产生了原始表格和堆叠列之间的一一对应关系（我们现在将称之为密集表示形式）。密集表示的长度等于 $2^m$，其中 $m = \lceil \log_2 \max t \rceil$。给定查找行和列的过程，我们可以定义两个函数，

$\text{col}(j) = \min_k { t_k > j }$

$\text{row}(j) = j - t_{k-1}$

使用字母 $q$ 来表示密集表示的多线性编码，我们看到每个条目对应于整个表格 $p$ 的多线性扩展的非虚拟部分。

$p(\text{row}(j), \text{col}(j)) = q(j)$.

这节省了大量空间来表示整个表格，但代价是证明者需要发送向量 $t$。然后我们可以证明，如果我们想要评估 $p(z_r, z_c)$，这相当于，

$p(z_r, z_c) = \sum p(x, y) \text{eq}(x, z_r) \text{eq}(y, z_c) = \sum q(i) \text{eq}(\text{row}(i), z_r) \text{eq}(\text{col}(i), z_c)$

因为 $p(x,y)$ 的任何零条目都不会对总和做出贡献。

为什么这适用于多线性多项式？

多变量多项式使用 sumcheck 协议将语句简化为在随机点评估多项式。例如，我们可以使用 sumcheck 协议来证明多变量多项式 $g$ 在超立方体上的值为零，使用零校验，

$\sum \text{eq}(r, x) g(x) = 0$

并且，通过与证明者交互，验证者只需对 $\text{eq}(r, z) g(z)$ 执行一次评估，以及一些涉及单变量多项式的简单检查。使用 PCS，证明者可以让验证者访问 $g$，并使用 PCS 的评估协议查询 $z$ 处的评估。

在单变量多项式的情况下，我们通过对 $D$ 上的 zerofier/vanishing 多项式 $Z_D(x)$ 进行商数运算，来证明 $g(x)$ 在域 $D$ 上有零点。一般来说，如果 $D$ 具有良好的结构（例如，$D$ 由 unity 的 $n$ 次根组成），则可以非常有效地评估 vanishing 多项式（在我们的例子中，$Z_D(x) = x^n - 1$。在稀疏多项式的情况下，$Z_D(x)$ 的表示可能很复杂，因此无法有效计算。

因此，多线性多项式不需要计算商，并且你可以先验地在更一般的域上工作（另一方面，FFT 需要平滑域，其中 $|F| - 1 = 2^n c$，其中 $n$ 通常至少为 $24$）。

如何处理大量的列

该论文提供了两个优化来处理大量的列：

1. Fancy jagged：如果表格中的所有列具有相同的高度，我们可以减少需要传递的信息量来计算 $t$。
2. 提交到列的高度。证明者可以将列的高度（将它们添加到表格的前面）包含在表格中并提交它们。

Jagged PCS

该论文的另一个核心部分是为稀疏/jagged多项式开发 PCS。请记住，从上面的讨论中，

$p(z_r, z_c) = \sum p(x, y) \text{eq}(x, z_r) \text{eq}(y, z_c) = \sum q(i) \text{eq}(\text{row}(i), z_r) \text{eq}(\text{col}(i), z_c)$

我们可以找到函数 $f_t$ 的多线性扩展，由下式给出

$f_t(x) = \text{eq}(\text{row}(x), z_r) \text{eq}(\text{col}(x), z_c)$

使用多线性乘积的 sumcheck 协议，验证者只需证明 $v = q(\alpha) f_t(\alpha)$，这反过来又相当于 $q(\alpha) = \beta_1$ 和 $f_t(\alpha) = \beta_2$。关键在于验证者可以有效地评估 $f_t$。这在 claim 3.2.1 中得到了证明。

为了证明该函数可以有效地计算，该论文介绍了一个函数 $g(w, x, y, z)$，它满足 $g(w, x, y, z) = 1$ 仅当 $x < z$ 且 $x = w + y$ 时。该函数可以直接与 $f_t$ 相关，并且可以使用宽度为 4 的分支程序有效地计算 $g$：

$f_t(z_r, z_c, i) = \sum_y \text{eq}(z_r, y) g(zc, y, t{y-1}, t_y)$

该证明依赖于多线性扩展的唯一性，因此只需检查 $z_r, z_c, i$ 作为二进制字符串的相等性即可。如果 $g(zr, i, t{y-1}, t_y) = 1$，则 $i < t_y$ 且 $i = zr + t{y-1}$。由于 $zr \geq 0$，因此 $t{y-1} \leq i < t_y$ 且 $zr = i - t{y-1}$。由于我们有 $\text{col}_t(i) = z_c$ 且 $\text{row}_t(i) = z_r$，因此 $f_t(z_r, z_c, i) = 1$。类似地，如果 $f_t(z_r, z_c, i) = 1$，则变量 $w, x, y, z$ 自动满足 $g(w, x, y, z) = 1$ 的条件。

从上面可以看出，我们可以通过计算 $g$ 的 $2^k$ 个评估来计算 $f_t$。通过 claim 3.2.2，一个宽度为 4 的只读分支程序可以通过以流式方式检查 $w, x, y, z$ 的每一位来有效地计算 $g$。可以通过一次查看 4 位并跟踪两个额外的变量来检查非消失 $g$ 的条件 $i < t_y$ 和 $zr = i - t{y-1}$。

然后，该论文讨论了如何使用只读矩阵分支程序生成符号评估，我们将需要它来进行批量证明多次评估。该程序由一系列矩阵 $M = M_{\sigma}^j$ 定义，其中 $\sigma \in {0, 1}^b$ 且 $j = 1, 2, ..., n$ 和一个 sink 向量 $u$。给定一个输入 $x \in {0, 1}^n$，程序的输出是由 $(\prod M_j^{x_j}) u$ 给出的向量的第一个分量，即 $e_1^t (\prod M_j^{xj}) u$，其中 $e{1j} = \delta_{1j}$（当且仅当 $j=1$ 时为 1，否则为零）。

如果矩阵是布尔矩阵（条目为 0 或 1），则矩阵乘法仅涉及加法（如果计算矩阵的乘积涉及线性数量的加法而没有乘法，则该论文称矩阵乘法友好）。

当没有给出 sink 向量 $u$ 时，可以以符号形式完成评估，并且当最终给出向量时，获得矩阵分支程序的最终值。我们的想法是，我们可以得到一个向量 $res$，使得 $res \cdot u = f_{M, u}(z)$，其中 $f$ 是由 $M$ 和 $u$ 给出的矩阵分支程序的多线性扩展。向量 $res$ 由下式给出

$res = e_1^t \prodj (\sum{\sigma} \text{eq}(zj, \sigma) M{\sigma}^j)$

批量证明多次评估

我们面临的问题是验证者应该计算 $k$ 次评估，这可能会非常昂贵。但是，通过与证明者交互，我们可以将所有内容简化为仅一次评估。这遵循一个标准技术，其中验证者选择随机权重 $\alpha_0, \alpha1, ... \alpha{k-1}$，并且证明者执行随机线性组合。更准确地说，假设我们要证明

$h(z_0) = v_0$

$h(z_1) = v_1$

$\vdots$

$h(z{k-1}) = v{k-1}$

然后证明者使用 $\alpha_j$ 进行以下线性组合，

$\sum_j \alpha_j h(z_j) = \sum_j \alpha_j v_j$

证明者想要说服验证者 $h(z_j) = v_j$ 对于每个 $j$ 都成立，因此将 $v_j$ 发送给验证者。验证者可以自己计算右侧的总和，$\sum \alpha_j v_j$。

左侧可以由证明者有效地计算。首先，请注意

$h(z_j) = \sum h(b) \text{eq}(b, z_j) = \sum h_k \text{eq}(b, z_j)$

其中 $k = \sum_j b_j 2^j$，其中 $b = b_0 b_1 b2 ... b{k-1}$。换句话说，评估 $h(z_j)$ 可以计算为向量 $h$（使得 $h_k = h(b)$）和拉格朗日基多项式 $\text{eq}(b, z_j)$ 的向量之间的内积。由于内积是（双）线性的，我们可以将线性组合写为

$\sum \alpha_j h(z_j) = \sum h(b) (\sum \alpha_j \text{eq}(b, z_j))$

证明者和验证者可以在 $(h(b) \sum \alpha_j \text{eq}(b, z_j))$ 上运行 sumcheck 协议，最后验证者必须在随机点 $\rho$ 计算 $h(\rho) \sum \alpha_j \text{eq}(\rho, z_j)$，这实际上是对 $h$ 的 oracle 查询，再加上计算线性组合 $\sum \alpha_j \text{eq}(\rho, z_j)$。zerocheck 的改进 中介绍了一些在 sumcheck 协议中使用的优化。

这都适用于哪里以及未来的工作

jagged方法允许我们提交到表格的非零部分，并节省大量工作，包括内存需求和提交时间。如果我们将这个想法与 M3 算术化 结合起来，在 M3 算术化中，我们不需要提交可以使用某些操作从 trace 多项式（虚拟多项式）计算的多项式，我们可以看到我们必须完成的工作量大大减少。反过来，这可以降低证明时间、证明成本和内存占用，从而允许我们证明更大的以太坊和 L2 区块，从而有效地扩展它以带来更多的用户并支持更多的用例。

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