我们对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=2532=25)。对于每一列，我们保留每一列的长度 lklk，包括非虚拟条目。例如，l0=220l0=220, l1=218+15l1=218+15, l2=216+1475l2=216+1475，等等。证明者可以构造一个向量，其条目是列的添加长度，tt。因此，t0=l0t0=l0, t1=l0+l1t1=l0+l1, t2=l0+l1+l2t2=l0+l1+l2。总之，

t0=l0t0=l0

tk+1=tk+lk+1tk+1=tk+lk+1

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

col(j)=mink{tk>j}col(j)=mink{tk>j}

row(j)=j−tk−1row(j)=j−tk−1

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

p(row(j),col(j))=q(j)p(row(j),col(j))=q(j).

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

p(zr,zc)=∑p(x,y)eq(x,zr)eq(y,zc)=∑q(i)eq(row(i),zr)eq(col(i),zc)p(zr,zc)=∑p(x,y)eq(x,zr)eq(y,zc)=∑q(i)eq(row(i),zr)eq(col(i),zc)

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

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

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

∑eq(r,x)g(x)=0∑eq(r,x)g(x)=0

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

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

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

如何处理大量的列

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

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

Jagged PCS

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

p(zr,zc)=∑p(x,y)eq(x,zr)eq(y,zc)=∑q(i)eq(row(i),zr)eq(col(i),zc)p(zr,zc)=∑p(x,y)eq(x,zr)eq(y,zc)=∑q(i)eq(row(i),zr)eq(col(i),zc)

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

ft(x)=eq(row(x),zr)eq(col(x),zc)ft(x)=eq(row(x),zr)eq(col(x),zc)

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

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

ft(zr,zc,i)=∑yeq(zr,y)g(zc,y,ty−1,ty)ft(zr,zc,i)=∑yeq(zr,y)g(zc,y,ty−1,ty)

该证明依赖于多线性扩展的唯一性，因此只需检查 zr,zc,izr,zc,i 作为二进制字符串的相等性即可。如果 g(zr,i,ty−1,ty)=1g(zr,i,ty−1,ty)=1，则 i<tyi<ty 且 i=zr+ty−1i=zr+ty−1。由于 zr≥0zr≥0，因此 ty−1≤i<tyty−1≤i<ty 且 zr=i−ty−1zr=i−ty−1。由于我们有 colt(i)=zccolt(i)=zc 且 rowt(i)=zrrowt(i)=zr，因此 ft(zr,zc,i)=1ft(zr,zc,i)=1。类似地，如果 ft(zr,zc,i)=1ft(zr,zc,i)=1，则变量 w,x,y,zw,x,y,z 自动满足 g(w,x,y,z)=1g(w,x,y,z)=1 的条件。

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

然后，该论文讨论了如何使用只读矩阵分支程序生成符号评估，我们将需要它来进行批量证明多次评估。该程序由一系列矩阵 M=MσjM=Mjσ 定义，其中 σ∈0,1bσ∈0,1b 且 j=1,2,...,nj=1,2,...,n 和一个 sink 向量 uu。给定一个输入 x∈0,1nx∈0,1n，程序的输出是由 (∏Mxjj)u(∏Mjxj)u 给出的向量的第一个分量，即 et1(∏Mxjj)ue1t(∏Mjxj)u，其中 e1j=δ1je1j=δ1j（当且仅当 j=1j=1 时为 1，否则为零）。

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

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

res=et1∏j(∑σeq(zj,σ)Mσj)res=e1t∏j(∑σeq(zj,σ)Mjσ)

批量证明多次评估

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

h(z0)=v0h(z0)=v0

h(z1)=v1h(z1)=v1

⋮⋮

h(zk−1)=vk−1h(zk−1)=vk−1

然后证明者使用 αjαj 进行以下线性组合，

∑jαjh(zj)=∑jαjvj∑jαjh(zj)=∑jαjvj

证明者想要说服验证者 h(zj)=vjh(zj)=vj 对于每个 jj 都成立，因此将 vjvj 发送给验证者。验证者可以自己计算右侧的总和，∑αjvj∑αjvj。

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

h(zj)=∑h(b)eq(b,zj)=∑hkeq(b,zj)h(zj)=∑h(b)eq(b,zj)=∑hkeq(b,zj)

其中 k=∑jbj2jk=∑jbj2j，其中 b=b0b1b2...bk−1b=b0b1b2...bk−1。换句话说，评估 h(zj)h(zj) 可以计算为向量 h（使得 hk=h(b)hk=h(b)）和拉格朗日基多项式 eq(b,zj)eq(b,zj) 的向量之间的内积。由于内积是（双）线性的，我们可以将线性组合写为

∑αjh(zj)=∑h(b)(∑αjeq(b,zj))∑αjh(zj)=∑h(b)(∑αjeq(b,zj))

证明者和验证者可以在 (h(b)∑αjeq(b,zj))(h(b)∑αjeq(b,zj)) 上运行 sumcheck 协议，最后验证者必须在随机点 ρρ 计算 h(ρ)∑αjeq(ρ,zj)h(ρ)∑αjeq(ρ,zj)，这实际上是对 hh 的 oracle 查询，再加上计算线性组合 ∑αjeq(ρ,zj)∑αjeq(ρ,zj)。zerocheck 的改进 中介绍了一些在 sumcheck 协议中使用的优化。

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

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

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