因式分解等式多项式如何优化SUMCHECK协议

介绍

在本文中，我们将继续研究和分析 Bagad、Dao、Domb 和 Thaler 的著作“加速 SUMCHECK”，该著作涉及应用于多线性多项式乘积的多项式的 SUMCHECK 协议的优化。现在是深入研究细节的时候了：由于等式多项式在密码学环境中被广泛使用，因此人们对它们的兴趣非常浓厚。

从前...

本文的读者肯定遇到过等式多项式（也称为“eq 多项式”）——这些多项式在其定义域内的所有点上都计算为零，但在一个点上计算为 1。在通常的实分析术语中，它们也称为笛卡尔空间中点的指示函数。回顾在单个和多个变量中多线性多项式的作用，可以通过将“较小的多项式”相乘来获得等式多项式。具体来说，假设 FF 是一个域，并且令 ω∈Fℓω∈Fℓ：它是

ω=(ω1,ω2,…,ωℓ)ω=(ω1,ω2,…,ωℓ)

对于 ωi∈Fωi∈F。现在假设我们将 ωω 分成块；例如，假设我们想将它分成三个块，比如

ω=(ωL,ωC,ωR)ω=(ωL,ωC,ωR)

其中 L,C,RL,C,R 是 [ℓ]={1,2,…ℓ}[ℓ]={1,2,…ℓ} 的一个划分，使得 l<c<r∀l∈L,c∈C,r∈Rl<c<r∀l∈L,c∈C,r∈R。这些子集表示每个“块”中涉及的索引。如果读者需要一些帮助来想象这一点，只需考虑

ω=(2,3,4,2,5,5)=((2,3),(4,2),(5,5))ω=(2,3,4,2,5,5)=((2,3),(4,2),(5,5))

对于 L = \{1,2\}, C = \{3,4}, R = \{5,6\}L = \{1,2\}, C = \{3,4}, R = \{5,6\}。

分块分割点的好处在于它与等式多项式的因式分解兼容：ω=(ωL,ωR)⟹eqω(x)=eqωL(xL)eqωR(xR)ω=(ωL,ωR)⟹eqω(x)=eqωL(xL)eqωR(xR)，对于 x=(xL,xR)x=(xL,xR)，变量 xx 的一个分块。

这当然与多线性多项式的插值基的张量性质完全兼容，并且不足为奇。一个额外的观察结果很方便，并且将发挥关键作用，尤其是在求和有限域上定义的多项式的评估时。每当多项式 ff 可以如上所示进行分块分解时，它的积分（即其评估的总和）可以按顺序完成，或者换句话说：有一种巧妙的方法可以重新排序我们可以利用的评估域。具体来说，假设 x∈Fℓx∈Fℓ 并且

f(x)=fL(xL)fR(xR)f(x)=fL(xL)fR(xR)

那么所有 xx 上的总和可以根据它的任何块来索引：

∑x∈Fℓf(x)=∑x∈FℓfL(xL)fR(xR)=∑xR∈FR∑xL∈FLfL(xL)fR(xR)∑x∈Fℓf(x)=∑x∈FℓfL(xL)fR(xR)=∑xR∈FR∑xL∈FLfL(xL)fR(xR)

通过固定外层求和中的索引，涉及该索引的因子可以从内层求和中取出（即反向分配律），因此

∑x∈Fℓf(x)=∑xR∈FRfR(xR)∑xL∈FLfL(xL)∑x∈Fℓf(x)=∑xR∈FRfR(xR)∑xL∈FLfL(xL)

这种想法将是我们讨论和利用的：固定 XRXR 将允许预先计算 XLXL 上的和，其中 XRXR 被视为参数：从这个意义上说，后一个和是预先计算的，然后在调用参数 XRXR 时重新使用。

如果读者想知道游戏的名字是什么：游戏的名字是积累，积累，积累（但要巧妙地积累）。

想法 (ideas)

我们现在准备深入研究 BDDT 提出的优化。起点是一个在形如 g(X)=~eq(w,X)⋅p(X)g(X)=eq~(w,X)⋅p(X) 的多项式上的 sum-check 协议，其中 p(X)p(X) 本身就是 dd 个多线性多项式的乘积。这使得 g(X)g(X) 成为一个 d+1d+1 次的多项式。在 sum-check 协议的每一轮 ii 中，证明者必须发送一个单变量多项式 si(X)si(X)，它是 g(X)g(X) 在剩余变量上的和。为了定义这个多项式，证明者需要计算它的 d+2d+2 个评估值。

作者采用了 Angus Gruen 的工作，并将其进一步发展。**简而言之，Gruen 的关键思想是利用等式多项式 ~eqeq~ 的特殊结构。这个多项式可以分解成一个乘积：

~eq(w,(r1,...,ri−1,Xi,xi+1,...,xl))=~eq(w[<i],r[<i])⋅~eq(wi,Xi) 线性部分 l_i(X) ⋅~eq(w[>i],x′)剩余部分eq~(w,(r1,...,ri−1,Xi,xi+1,...,xl))=eq~(w[<i],r[<i])⋅eq~(wi,Xi)⏟ 线性部分 l_i(X) ⋅eq~(w[>i],x′)⏟剩余部分

这种分解的效果是，最初定义为在 x′x′ 上的和的轮多项式 si(Xi)si(Xi) 现在看起来像一个乘积：

si(Xi)=∑x′g(r,Xi,x′)=∑x′eq(r,Xi,x′)p(r,Xi,x′)=∑x′eqw<i(r)eqwi(Xi)eqw>i(x′)p(r,Xi,x′)=eqw<i(r)eqwi(Xi)(∑x′eqw>i(x′)p(r,Xi,x′))si(Xi)=∑x′g(r,Xi,x′)=∑x′eq(r,Xi,x′)p(r,Xi,x′)=∑x′eqw<i(r)eqwi(Xi)eqw>i(x′)p(r,Xi,x′)=eqw<i(r)eqwi(Xi)(∑x′eqw>i(x′)p(r,Xi,x′))

现在，轮多项式是一个线性因子 li(Xi)li(Xi)} 的乘积，即

li(Xi)=eqw<i(r)eqwi(Xi)li(Xi)=eqw<i(r)eqwi(Xi)

它取决于前几轮的挑战 (r[<i]r[<i]) 和当前的变量 (XiXi)，以及一个 dd 次因子，ti(Xi)ti(Xi)：

ti(Xi)=∑x′eqw>i(x′)p(r,Xi,x′)ti(Xi)=∑x′eqw>i(x′)p(r,Xi,x′)

它包含实际的求和，包括 pkpk 多项式的乘积和 ~eqeq~ 多项式的剩余部分。因此，证明者在第 i−thi−th 轮计算的多项式是

si(Xi)=li(Xi)⋅ti(Xi)si(Xi)=li(Xi)⋅ti(Xi)

读者可能会问，以这种方式思考 sisi 有什么好处。

证明者现在只需要计算更简单的多项式 ti(X)ti(X) (dd 次) 的 d+1d+1 个评估值，而不是计算复杂多项式 si(X)si(X) (d+1d+1 次) 的 d+2d+2 个评估值。其中一个评估值，ti(1)ti(1)，可以从协议的一致性检查中推导出来 (si(0)+si(1)=Ci−1si(0)+si(1)=Ci−1)，因此在实践中，只需要显式计算 dd 个和。

总而言之，Gruen 降低了证明者必须执行最多工作的多项式的次数，从而节省了协议每一轮中一次完整评估的成本。BDDT 的关键思想是重新应用 ~eqeq~ 多项式的可分离性，但这次是在被求和的剩余变量 (x′x′) 上，并结合他们之前提出的将 pp 在随机挑战处的评估转移到拉格朗日插值多项式的评估上。概括地说，这项新颖的工作如下：

1. 变量拆分： 他们将剩余变量 x′x′ 的集合分成两个适当长度的部分，我们现在称之为 xLxL（左）和 xRxR（右）。
2. 嵌套求和： 由于这种拆分，计算 ti(u)ti(u) 的和可以改写为嵌套求和：ti(u)=∑xR~eq(wR,xR)⋅(∑xL~eq(wL,xL)⋅d∏k=1pk(r,u,xL,xR))ti(u)=∑xReq~(wR,xR)⋅(∑xLeq~(wL,xL)⋅∏k=1dpk(r,u,xL,xR))

这种重写是优化的核心。证明者现在可以首先计算内和（在 xLxL 上），然后将这些结果用于外和（在 xRxR 上）。

这种“和拆分”技术在时间和内存方面都产生了非常显著的好处。

• 大幅减少内存： 标准方法将需要预先计算并存储一个包含所有 xx 的 ~eq(w,x)eq~(w,x) 评估值的表——一个大小为 2l2l 的表。BDDT 的优化消除了对这个巨大表的需求。相反，证明者只需要预先计算变量的一半（xLxL 和 xRxR）上的 ~eqeq~ 评估值的表，其大小约为 ≈2l/2≈2l/2。从 O(2l)O(2l) 到 O(2l/2)O(2l/2) 的内存需求的转变是一个指数级的改进，并使更大的问题成为可能。
• 降低计算成本（时间）： 通过避免与大型 ~eqeq~ 表相乘，证明者节省了大量操作。该论文估计，这种优化将成本降低了大约 NN 个大型域元素之间的乘法运算，其中 N=2lN=2l 是求和域的大小。这些和会通过较小的域迭代处理，从而提高内存局部性和计算效率。

这种优化是在协议的前 l/2l/2 轮中应用的。对于剩余的轮次，好处会减少，并且算法会切换回标准方法。

组织胜过时间

作者提出将 Gruen 的策略与他们自己来自 SmallValues 优化的想法相结合，这意味着在评估多项式 lili 和 titi 时需要特别注意。在第 ii 轮中，发送给验证者的数据

si(u)=li(u)ti(u)si(u)=li(u)ti(u)

有一个计算量更大的部分：计算一个足够大的集合中的 uu 的 ti(u)ti(u)。到目前为止，这个多项式的唯一可用定义由下式给出

ti(u)=∑xR~eq(wR,xR)⋅(∑xL~eq(wL,xL)⋅d∏k=1pk(r,u,xL,xR))ti(u)=∑xReq~(wR,xR)⋅(∑xLeq~(wL,xL)⋅∏k=1dpk(r,u,xL,xR))

并且仍然需要一些澄清。x′x′ 的各个部分是如何定义的？如何执行此总和？它与作者先前提出的 SmallValues 优化有什么关系？

需要强调的是，这个描述在概念上是合理的，并且包含了这个优化中涉及的关键思想。此外，必须提到的是，在这个层面上，剩余向量 x′x′ 的分块划分和等式多项式的因式分解是一个动态因素：x′x′ 的长度在第 ii 轮为 ℓ−iℓ−i，因此在绝对意义上，xLxL 和 xRxR 的长度将逐轮变化。

虽然这足以进行咖啡桌上的谈话，但从算法的角度来看，它留下了一些不足之处，尤其是如果期望获得一些收益的话。

对最优性参数的需求

为了在概念清晰性和高效计算之间进行转换，作者定义了一个称为 l0l0 的最优性参数 - 仔细选择以最小化证明者的总时间。它的选择基于成本权衡：

• 优化轮次 (i≤l0i≤l0) 的成本：此成本（主要是 sl 乘法）随 l0l0 呈指数增长，因为累加器的大小约为 O((d+1)l0)O((d+1)l0)。
• 标准轮次 (i>l0i>l0) 的成本：此成本（主要是 ll 乘法）随着 l0l0 的增加而降低，因为要执行的“昂贵”轮次更少。

l0l0 的最佳值是这两个成本平衡的值。该论文提供了一个公式来估计算法 4 的最佳点，该公式取决于多项式的结构（因子数，dd）和硬件操作的相对成本（ll 和 ss 乘法的成本之间的比率 κκ）。最佳切换点 l0l0 可以通过以下公式估算：

l0=log(κ⋅d22(d−1))log(d+1)l0=log⁡(κ⋅d22(d−1))log⁡(d+1)

其中：

• dd 是多线性因子的数量。
• κκ 是大-大（ll）和小-小（ss）乘法之间成本的因子差异。作者对他们的估计使用 κ=30κ=30，并为该选择提供了更深层次的背景（鼓励读者在原始文章中寻找详细信息！）

此参数严格控制 SUMCHECK 协议在任何给定阶段的工作方式：

• 如果 i≤l0i≤l0：你处于“优化阶段”。该协议使用预先计算的累加器来非常快速地计算证明者的消息。
• 如果 i>l0i>l0：你已越过阈值。该协议切换到更标准的算法（如算法 5）以进行剩余的轮次，因为预计算的好处已经结束。

现在我们能够进一步了解 x′x′ 的分块划分。作者的优化实现基于这些点在优化参数 ℓ0ℓ0 和变量数 ℓℓ 方面的静态划分。此划分名为

x′=(xin,xout)x′=(xin,xout)

以与动态划分相同的方式工作，但允许进行有效的计算，因为长度现在是恒定的。它们表示对不在 l0l0 轮前缀中的变量的固定拆分。

• xinxin 是计算“内和”的变量集合。
• xoutxout 是“外和”迭代的变量集合。

多项式的总共 ll 个变量被划分为三个不相交的组，其并集形成完整的变量集合：

1. 预计算前缀 ββ：前 l0l0 个变量。
2. 集合 xinxin：接下来的 ⌊l/2⌋⌊l/2⌋ 个变量
3. 集合 xoutxout：最后的 ⌊l/2⌋−l0⌊l/2⌋−l0 个变量

因此，xinxin 和 xoutxout 一起形成不属于预计算前缀的变量集合的划分（即预计算后缀）。它们大小之和为 (⌊l/2⌋)+(⌊l/2⌋−l0)(⌊l/2⌋)+(⌊l/2⌋−l0)，这大约是 l−l0l−l0，即预计算后缀的总大小。

现在我们已经解决了所涉及的符号和参数，让我们看看他们的算法实际上如何在第 ii 轮中计算所需的值。

预计算阶段中分块描述的效果

为了计算 ti(u)ti(u) - 作者利用 SmallValue 优化 - 它允许计算多个线性多项式的乘积在验证者发送的随机挑战处的评估。正如我们在之前的帖子中提到的，这是通过将评估的负担转移到在基域中具有系数的点网格上定义的多变量拉格朗日多项式来完成的 - 并评估这些多项式。所需的评估现在是由预先计算的系数（称为累加器）加权的求和，这些系数取决于网格和乘积。

为了具体起见，请回顾一下 titi 的定义

ti(u)=∑x′~eq(w>i,x′)⋅d∏k=1pk(r,u,x′)ti(u)=∑x′eq~(w>i,x′)⋅∏k=1dpk(r,u,x′)

SmallValues 优化允许将其重写为

ti(u)=∑v∈Gi(∑x′~eq(w>i,x′)⋅d∏k=1pk(v,u,x′))⋅Lv(r)ti(u)=∑v∈Gi(∑x′eq~(w>i,x′)⋅∏k=1dpk(v,u,x′))⋅Lv(r)

其中

1. GiGi 是基域中点的充分插值网格。具体来说，如果 gg 是 dd 个多线性多项式的乘积，不包括 eq 因子，设置 Ud=∞,0,1,…,d−1Ud=∞,0,1,…,d−1，然后 Gi=Ui−1di≥2andG1=∅Gi=Udi−1i≥2andG1=∅
2. 多项式 LvLv 是与网格 GiGi 关联的 i−1i−1 变元拉格朗日插值多项式 - 最终在挑战 r1,…ri−1r1,…ri−1 处评估的正是那些多项式。对于 i=1i=1，我们设置 L1=1L1=1。
3. 作者喜欢收集 |Gi||Gi| 个多项式 Lv(r)Lv(r) 的值，在一个以网格中的点索引的 |Gi||Gi| 长的向量中，在一个挑战向量 RiRi 中。
4. 上一行的括号之间的总和是累加器 Ai(v,u)Ai(v,u) 的定义 - 简单地说，就是用拉格朗日插值多项式表达 ti(u)ti(u) 值的所需系数。作者将其表示为挑战向量和累加器向量之间的“内积”，也以 vv 索引：ti(u)=∑v∈GiRi(v)Ai(v,u)ti(u)=∑v∈GiRi(v)Ai(v,u)。

现在是让分块划分的力量闪耀并发挥其魔力的时候了：现在可以分两步进行 x′x′ 上的总和：

Ai(v,u)=∑xout~eq(wout,xout)∑xin~eq(win,xin)d∏k=1pk(v,u,xin,xout)Ai(v,u)=∑xouteq~(wout,xout)∑xineq~(win,xin)∏k=1dpk(v,u,xin,xout)

别慌，我们已经到了。现在考虑前缀 β=(v,u)β=(v,u> 和调用 Ein[xin]=eq(win,xin)Ein[xin]=eq(win,xin)。最后一个内和由 ββ 和 xoutxout 参数化，应称为临时累加器 tA[β]tA[β]。

tA[β]=∑xin∈{0,1}l/2Ein[xin]⋅d∏k=1pk(β,xin,xout)tA[β]=∑xin∈{0,1}l/2Ein[xin]⋅∏k=1dpk(β,xin,xout)

现在我们已经命名了适当的对象，我们可以描述该算法的工作方式。

逻辑和算法步骤：

核心思想是一种记忆化形式。该算法并非为每个累加器计算整个和，而是计算一次最内层的和并重复使用结果：确实，是分块划分的效果。

1. 在 xoutxout 上的外部迭代：该算法有一个主循环，该循环对 xoutxout 段中变量的所有可能赋值进行迭代。
2. 内和计算：在该循环内部，对于 xoutxout 的固定值，该算法计算最内层的和。该和在 xinxin 的所有赋值上进行，并且取决于前缀 ββ（它概括了（v,u,y）（v,u,y>）和当前的 xoutxout。

a. 对于每个前缀 ββ，计算 ∑xinEin[xin]⋅∏pk(β,xin,xout)∑xinEin[xin]⋅∏pk(β,xin,xout)。

b. 每个 ββ 的内和的结果存储在称为 tA[β]tA[β] 的临时累加器中。

3. 分发给最终累加器：一旦计算出当前 xoutxout 的所有 tAtA 值，该算法会将它们分发给最终累加器 Ai(v,u)Ai(v,u)。这是通过以下方式完成的：

a. 它对每个前缀 ββ 及其在 tA[β]tA[β] 中的对应值进行迭代。

b. 使用映射函数 idx4（在 A.5 中定义），它确定此前缀 ββ 对哪个最终累加器 (i,v,u)(i,v,u) 有贡献。

c. 它将 tA[β]tA[β] 的值添加到适当的最终累加器中，并由外部 eq-poly 因子 Eout,iEout,i 加权。

分类和分发机制

当我们在研究 BDDT 的 SmallValue 优化时，我们讨论了这种方法，但是很高兴让读者了解这是如何执行的。idx4 分类算法的作用是在预计算阶段充当智能“调度器”或“路由器”。它的功能是确定应该用刚刚计算出的中间结果来更新哪些最终累加器 Ai(v,u)Ai(v,u)，可能来自不同的轮次。

_过程 9_（算法 6 的预计算引擎）旨在实现高效率。该算法不是单独计算每个累加器 Ai(v,u)Ai(v,u)，而是对长度为l0l0 的所有可能前缀 ββ 进行迭代，并为每个前缀计算一个值：临时累加器tA[β]tA[β]。

问题在于，单个值 tA[β]tA[β]（例如，针对前缀 β=(0,1,0)β=(0,1,0) 计算得出的）可能是以下计算的一部分：

• 第 1 轮 的累加器：A1(u=0)A1(u=0)。
• 第 2 轮 的累加器：A2(v=(0),u=1)A2(v=(0),u=1)。
• 第 3 轮 的累加器：A3(v=(0,1),u=0)A3(v=(0,1),u=0)。

_idx4_ 要回答的问题是：给定一个 ββ，必须将此 tA[β]tA[β] 发送到哪个最终累加器的所有“地址”（i,v,u>？

它的逻辑包括为每一轮 ii（从 1 到 l0l0）“分解”前缀 ββ，并检查它是否满足所需的结构。对于与第 ii 轮的累加器有效的前缀 ββ，对应于未来变量（向量 yy）的部分 必须是二进制的（仅包含 0 和 1）。多项式 gg 具有 eqeq 因子这一事实最终极大地简化了此分发步骤，因为预先计算的乘积/和的数量很少参与累加器的构造。

直观示例

假设 l0=3l0=3 并且计算的前缀为 β=(0,1,0)β=(0,1,0)。_idx4_ 将执行以下操作：

1. 它是否对第 1 轮 (i=1i=1) 有贡献？

a. u=β1=0u=β1=0。

b. 剩余的是 y=(β2,β3)=(1,0)y=(β2,β3)=(1,0)。

c. 由于 yy 是二进制的，因此 是的。_idx4 生成元组 _(i=1,v=(),u=0,y=(1,0))(i=1,v=(),u=0,y=(1,0))\。

2. 它是否对第 2 轮 (i=2i=2) 有贡献？

a. v=(β1)=(0)v=(β1)=(0)。

b. u=β2=1u=β2=1。

c. 剩余的是 y=(β3)=(0)y=(β3)=(0)。

d. 由于 yy 是二进制的，因此 是的。_idx4_ 生成元组 (i=2,v=(0),u=1,y=(0))(i=2,v=(0),u=1,y=(0))。

3. 它是否对第 3 轮 (i=3i=3) 有贡献？

a. v=(β1,β2)=(0,1)v=(β1,β2)=(0,1)。

b. u=β3=0u=β3=0。

c. 剩余的 yy 为空。

d. 是的。_idx4_ 生成元组 (i=3,v=(0,1),u=0,y=())(i=3,v=(0,1),u=0,y=())。

相比之下，如果 β=(2,1,0)β=(2,1,0)，它将只对第 1 轮有贡献。对于第 2 轮和第 3 轮，前缀的 vv 部分将包含一个 2，这不是二进制值，因此不属于定义这些轮次的累加器的布尔超立方体上的总和。

在你从椅子上摔下来之前的一个小例子

为了固定想法，我们现在将通过一个包含小的具体数字的示例进行讲解。如果你愿意，拿一张纸和一些咖啡，并在我们进行初始几轮计算时仔细检查计算。

设置

我们将使用一个 6 变量 的多项式，同时将优化轮次保持在 l0=2l0=2。此更改使我们可以在第 2 轮中有一个非空的 xoutxout，从而显示临时累加器和最终累加器之间的完整交互。

考虑多项式

g(X)=~eq(w,X)⋅(X1+X3+X5+1)⋅(X2+X4+X6+2)g(X)=eq~(w,X)⋅(X1+X3+X5+1)⋅(X2+X4+X6+2)

而 eqeq 是向量 w=(1,0,1,1,0,1)w=(1,0,1,1,0,1) 的等式多项式。考虑到 l0=2l0=2，则只有第 1 轮和第 2 轮被优化。作为作者对插值集合的选择，我们将坚持使用 U2={∞,0,1}U2={∞,0,1}。证明者需要计算 u∈^U2={∞,0}u∈U2^={∞,0} 的 t2(u)t2(u)。

正确进行划分

由于 ℓ0=2ℓ0=2，因此 6 个变量的划分如下：

• 预计算前缀 β=(X1,X2)β=(X1,X2) 及其“eq”同伴 wL=(w1,w2)=(1,0)wL=(w1,w2)=(1,0)
• 预计算后缀(X3,X4,X5,X6)(X3,X4,X5,X6) 随后拆分为

a. xinxin (大小 l/2=3l/2=3): (X3,X4,X5)(X3,X4,X5)。其 eq 向量为 win=(w3,w4,w5)=(1,1,0)win=(w3,w4,w5)=(1,1,0)。

b. xoutxout (大小 l/2−l0=1l/2−l0=1): (X6)(X6)。其 eq 向量为 wout=(w6)=(1)wout=(w6)=(1)。

第一轮

证明者需要计算以下各项的值 s1(X1)=l1(X1)t1(X1)s1(X1)=l1(X1)t1(X1)

在 ∞∞ 和 00 处。请记住，线性因子 li(Xi)li(Xi) 定义为：

li(Xi)=~eq(w[<i],r[<i])过去挑战⋅~eq(wi,Xi)当前变量li(Xi)=eq~(w[<i],r[<i])⏟过去挑战⋅eq~(wi,Xi)⏟当前变量

因此，在第 1 轮 i=1i=1 中，过去挑战 r[<1]r[<1] 的集合为空。按照惯例，空集上的乘积为 1。因此，公式的第一个因子就是 1。这意味着

l1(X1)=1⋅~eq(w1,X1)=~eq(1,X1)=X1l1(X1)=1⋅eq~(w1,X1)=eq~(1,X1)=X1

这意味着 l1(∞)=1l1(∞)=1 并且 l1(0)=0l1(0)=0，所以好消息是我们不需要计算 t1(0)t1(0)。让我们开始工作，看看 t1t1 的前导系数是如何计算的。

根据算法 6，

t1(u)=⟨R1,A1(u)⟩=A1(u)(因为 R1=[1])t1(u)=⟨R1,A1(u)⟩=A1(u)(因为 R1=[1])

因此，任务简化为计算最终累加器 A1(∞)A1(∞)，这就是临时累加器发挥作用的地方。由于优化参数是 ℓ0=2ℓ0=2，那么

• 对于第一轮，我们将感兴趣考虑的前缀 ββ 是 β=(∞,0) 和 β=(∞,1)β=(∞,0) 和 β=(∞,1)
• 然后，后缀 分为 xin=(X3,X4,X5)xin=(X3,X4,X5) 和 xout=(X6)xout=(X6)，并且由于 eq 向量 是 win=(1,1,0)win=(1,1,0) 和 wout=(1)wout=(1)，我们有 Eout,1(1,0)=0 和 Eout,1(1,1)=1Eout,1(1,0)=0 和 Eout,1(1,1)=1，所以我们不会计算 x6=0x6=0 的临时累加器（它乘以零）。

为了完整起见，我们在此处包含一个包含此案例中的预计算的小表格：

x6=1x6=1 的临时累加器

uu	y2y2	p1=u+2p1=u+2	p2=y2+4p2=y2+4	tA[u,y2]tA[u,y2]
∞∞	0	1	4	1⋅4=41⋅4=4
∞∞	1	1	5	1⋅5=51⋅5=5
0	0	2	4	2⋅4=82⋅4=8
0	1	2	5	2⋅5=102⋅5=10

因此，让我们计算 x6=1x6=1 的外部循环。现在，乘积的内部权重由 Ein(win,xin)Ein(win,xin) 给出，因此内部总和中唯一的项是对应于 xin=(1,1,0)xin=(1,1,0) 的项，因此

tA[∞,0]=p1(∞,0,1,1,0,1)⋅p2(∞,0,1,1,0,1)=1⋅4=4tA[∞,0]=p1(∞,0,1,1,0,1)⋅p2(∞,0,1,1,0,1)=1⋅4=4

和

tA[∞,1]=p1(∞,1,1,1,0,1)⋅p2(∞,1,1,1,0,1)=1⋅5=5tA[∞,1]=p1(∞,1,1,1,0,1)⋅p2(∞,1,1,1,0,1)=1⋅5=5

这意味着

A1(∞)=1⋅tA[∞,0]+1⋅tA[∞,1]=4+5=9A1(∞)=1⋅tA[∞,0]+1⋅tA[∞,1]=4+5=9

因此，证明者发送

s1(∞)=1⋅9=9and s1(0)=0s1(∞)=1⋅9=9and s1(0)=0

第二轮

首先，我们处理线性因子 l2(X2)l2(X2)。该因子来自 (r1,X2)(r1,X2) 处计算的 eq (X1,X2)(X1,X2) 上关于前缀变量的 ：

l2(X2)=~eq((w1,w2),(r1,X2))=~eq(1,r1)⋅~eq(0,X2)=r1⋅(1−X2)l2(X2)=eq~((w1,w2),(r1,X2))=eq~(1,r1)⋅eq~(0,X2)=r1⋅(1−X2)

很明显

l2(∞)=−r1andl2(0)=r1l2(∞)=−r1andl2(0)=r1

现在到了计算 t2(X2)t2(X2) 的艰难部分。由于这是通过 SmallValue 优化计算的，因此它涉及使用预先计算的累加器组合拉格朗日插值多项式在随机挑战 r1r1 处的求值：最终结果是乘积之和，作者通常将其显示为内积 t2(u)=⟨R2,A2(u)⟩t2(u)=⟨R2,A2(u)⟩，其中挑战向量 R2R2 取决于 r1r1 和 U2={∞,0,1}U2={∞,0,1}，并计算为：

• R2[∞]=(r1−0)(r1−1)=r1(r1−1)R2[∞]=(r1−0)(r1−1)=r1(r1−1)
• R2[0]=r1−10−1=1−r1R2[0]=r1−10−1=1−r1
• R2[1]=r1−01−0=r1R2[1]=r1−01−0=r1

那么挑战向量是 R2=(r1(r1−1),1−r1,r1)R2=(r1(r1−1),1−r1,r1)。

现在，我们将按照过程 9 的逻辑计算 v,u∈U2v,u∈U2 的值 A2(v,u)A2(v,u)，该过程迭代 xout=(X6)xout=(X6)；同样，由于

Eout,2(1,X6)=X6Eout,2(1,X6)=X6

我们只需要考虑 x6=1x6=1 的情况。此外，在这种情况下，临时累加器 tAtA 的计算得益于我们在第一轮中已经学到的知识：对于 xin=(1,1,0)xin=(1,1,0)，总和仍然会折叠。为了完整起见，我们包括

x6=1x6=1 的临时累加器

vv	uu	p1=v+2p1=v+2	p2=u+4p2=u+4	tA[v,u]tA[v,u]
∞∞	∞∞	1	1	1⋅1=11⋅1=1
∞∞	0	1	4	1⋅4=41⋅4=4
0	∞∞	2	1	2⋅1=22⋅1=2
0	0	2	4	2⋅4=82⋅4=8
1	∞∞	3	1	3⋅1=33⋅1=3
1	0	3	4	3⋅4=123⋅4=12

我们现在可以构建一个包含此轮中涉及的最终累加器的表格。由于证明者需要发送在 ∞∞ 和 00 处的求值，因此我们仅计算累加器

A2(∞,∞),,A2(0,∞),,A2(1,∞),,A2(∞,0),,A2(0,0),and,A2(1,0)A2(∞,∞),,A2(0,∞),,A2(1,∞),,A2(∞,0),,A2(0,0),and,A2(1,0)

请记住：Eout,2Eout,2 和 EinEin 的权重消除了定义中的大多数总和

A2(v,u)=∑xoutEout,2∑xinEin[xin]p1(v,u,xin,xout)p2(v,u,xin,xout)A2(v,u)=∑xoutEout,2∑xinEin[xin]p1(v,u,xin,xout)p2(v,u,xin,xout)

简化为

A2(v,u)=p1(v,u,1,1,0,1)p2(v,u,1,1,0,1)A2(v,u)=p1(v,u,1,1,0,1)p2(v,u,1,1,0,1)

这种情况的急剧减少清楚地表明了这种计算循环多项式的方法的工作原理：通过 titi 收集的 eq 因子进行块分区会导致大部分总和消失，并产生很少的对累加器有贡献的非平凡的加数。

为了完整起见，这是一个显示最终累加器的表格

第 2 轮最终累加器值

A2(v,u)A2(v,u)	u=∞u=∞	u=0u=0	u=1u=1
v=∞v=∞	1	4	（不需要）
v=0v=0	2	8	（不需要）
v=1v=1	3	12	（不需要）

在本轮中，我们结合挑战向量，使用累加器作为权重来生成 t2(u)t2(u) 的求值：

\begin{itemize}

• t2(0)t2(0) 的计算：

t2(0)=∑v∈U2R2[v]⋅A2(v,0)=r1(r1−1)⋅A2(∞,0))+(1−r1)⋅A2(0,0)+r1⋅A2(1,0)=r1(r1−1)⋅4+(1−r1)⋅8+r1⋅12t2(0)=∑v∈U2R2[v]⋅A2(v,0)=r1(r1−1)⋅A2(∞,0))+(1−r1)⋅A2(0,0)+r1⋅A2(1,0)=r1(r1−1)⋅4+(1−r1)⋅8+r1⋅12

• t2(∞)t2(∞) 的计算

t2(∞)=∑v∈U2R2[v]⋅A2(v,∞)=(r1(r1−1)⋅A2(∞,∞))+((1−r1)⋅A2(0,∞))+(r1⋅A2(1,∞))=(r1(r1−1)⋅1)+((1−r1)⋅2)+(r1⋅3)t2(∞)=∑v∈U2R2[v]⋅A2(v,∞)=(r1(r1−1)⋅A2(∞,∞))+((1−r1)⋅A2(0,∞))+(r1⋅A2(1,∞))=(r1(r1−1)⋅1)+((1−r1)⋅2)+(r1⋅3)

最后，prover 将以下值发送给验证者

s2(∞)=l2(∞)⋅t2(∞)ands2(∞)=l2(∞)⋅t2(∞)s2(∞)=l2(∞)⋅t2(∞)ands2(∞)=l2(∞)⋅t2(∞)

（实际的证明者替换挑战 r1r1 并生成一个数值输出交给验证者，这就是前两轮的内容）

l0l0 之后的轮次

一旦使用预计算进行优化后的轮次完成，算法将切换其策略以用于协议的其余部分。

• 过渡阶段（第 l0+1l0+1 轮）

这一单轮的目标是从预计算的“快速模式”切换到“标准”线性模式。prover 计算多项式 pkpk 的求值，其中前 l0l0 个变量已固定为挑战 (r1,…,rl0)(r1,…,rl0)。此阶段的结果是创建将在最后几轮中使用的数据数组（称为 PkPk）。

• 最后阶段（第 l0+2l0+2 轮到第 ll 轮）

从这一点开始，协议遵循标准的线性 sum-check 算法（类似于算法 1 或 5）。在这些轮次的每一轮中：

i. 证明者使用当前的数组 PkPk 来计算并发送其消息。

ii. 它收到一个新的挑战 riri。

iii. 它使用该挑战来组合数组中的成对条目，将其大小减半 并为下一轮做好一切准备。

这种减半过程一直持续到最后一轮，在最后一轮中，数组非常小，以至于问题简化为单个最终检查。

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