优化Sumcheck协议

介绍

在本文中，我们将回顾对 SUMCHECK 协议的一些优化，正如 Bagad、Dao、Domb 和 Thaler 最近的文章中所讨论的那样。作者解决了 字段乘法成本不成比例 的问题。在许多 SNARK 应用中，sum-check 协议在 扩张域 上运行，这些扩张域比它们的 基域 大得多。虽然被求和或计算的实际值通常是“小的”（例如，32 位整数或较小基域的元素），但涉及来自较大扩张域的元素的乘法（large-large (ll) 乘法）比那些在较小基域内的乘法（small-small (ss) 乘法）昂贵得多。这种成本差异可能非常大，有时甚至数量级。

SUMCHECK 协议快速回顾

读者可能已经知道，SUMCHECK 协议是一种可验证计算和密码学中的基本交互式证明系统，最早由 Lund、Fortnow、Karloff 和 Nisan 在 1990-1991 年左右提出。我们将首先广泛地描述其目的和典型用法，然后我们将开始研究实现的细节，其中一些巧妙的观察可以带来性能的提升。熟悉该协议的读者可以安全地跳过第一节；那些想要快速复习的读者可以阅读。

SUMCHECK 协议的主要目的是让 证明者 (P) 说服 验证者 (V)，多项式求值的大量和 等于一个特定的值，而无需验证者自己计算整个和。该和通常是针对 布尔超立方体 ${0,1}^l$ 中的所有输入，对于一个 $l$ 变量多项式 $g$。

验证者的核心好处是计算工作量的大幅减少：验证者可以通过在所有 $2^n$ 个可能的输入处评估多项式来计算和。然而，使用 SUMCHECK 协议，验证者最终只需要在较大的有限域中一个随机选择的点上评估多项式。这个随机点是从一个比 $\{0,1\}^l$ “大得多的空间”中选择的。

协议通过证明者和验证者之间的一系列交互轮次进行：

1. 初始声明： 在开始时，证明者发送一个值 $C_1$，声称它等于期望的和 $H$。

2. 迭代缩减： 该协议涉及 $n$ 轮（其中 $n$ 是多项式中的变量数）。在每一轮 $j$（从 1 到 $l$）中：

- 证明者发送一个单变量多项式 $g_j(X_j)$，声称它代表原始多项式的部分和，其中前 $j-1$ 个变量已被“绑定”到验证者在先前轮次中选择的随机值，而第 $j$ 个变量是自由的。这个过程在每一轮中“消除了求和中的一个变量”。

- 验证者对接收到的多项式执行一致性检查，特别检查当前多项式是否与前一轮中建立的值一致（例如，第一轮中的 $C_1=g_1(0)+g1(1)$，以及后续轮次中的 $g{j-1}(r_{j-1})=g_j(0)+g_j(1)$）。验证者还会检查 $g_j(X_j)$ 的度数是否过高。

- 如果检查通过，验证者选择一个新的随机域元素 $r_j$，并将其发送给证明者。这个随机选择用于概率性地验证证明者发送的多项式。

3. 最终检查： 在最后一轮 ($l$) 中，证明者发送一个单变量多项式 $g_l(X_l)$，它应该是原始多项式 $g$，在到目前为止为前 $l-1$ 个变量选择的所有随机 $r$ 值处进行求值。然后，验证者选择一个最终的随机 $r_l$，并直接在完整的随机点 $(r_1,…,r_l)$ 处评估原始多项式 $g$，并将此结果与 $g_l(r_l)$ 进行比较。如果所有检查都通过，则验证者接受初始和。

该协议的一个重要特征是 验证者的消息仅仅是随机域元素，独立于输入多项式 $g$（除了需要其每个变量的度数的上限以及能够在随机点评估它）。

在深入了解内部机制之前，让我们谈谈符号。为了简洁起见，并使我们的生活更轻松，当变量的数量和涉及的维度从上下文中清楚时，我们将简化符号。在本文中，我们专注于 $\ell$ 个变量 $X_1,X2,…X\ell$ 的多项式，但为了简单起见，我们采用

$f(X_1,X2,…X\ell)=f(X)$

作为标准符号。当这些 $\ell$ 个变量被分割时，我们也使用单个字母来表示它的肢，例如我们将 $X$ 分割成三个部分

$(X_1,X2,…X\ell)=(Y_1,Y2,…Y{i-1},Xi,x'{i+1},…x'_\ell)$

我们简单地使用 $(Y,X_i,x')$ 来减少繁琐的索引。

设置

作者关注 SUMCHECK 的一个特定设置，在各种上下文中很有用：他们将注意力缩小到多项式 $g$ (SUMCHECK 声明的对象) 可以写成 $d$ 个多重线性多项式的乘积的情况

$g(X)=\prod_{k=1}^{d}p_k(X)$

其中，多重线性多项式是指一个 $\ell$ 变量多项式，使得它的每个单项式具有以下特征：每个变量的幂要么是 0，要么是 1。这些多项式非常有用，并且以不同的形式出现在整个域理论文献中，最近又重新出现在 Ben Diamond 和 Jim Posen 的 BINIUS 工作中，成为有用的对象。对于不熟悉的读者，我们建议快速阅读我们关于这些对象的自成一体的入门指南多重线性多项式：基本生存指南。

仔细观察

所考虑的优化的关键观察在于认识到证明者在第 $i$ 轮中发送的多项式：

$s_i(Xi)=\sum{x' \in {0,1}^{\ell-i}}\prod_{k=1}^{d}p(r,X_i,x')$

实际上是变量 $X_i$ 上单变量多项式的和。多项式在证明者和验证者之间传递的方式通常是通过传递它们在一组适当的集合上的求值。从 $s_i$ 在足够大的集合上的求值中，验证者能够从接收到的数据中重构多项式。

求值集应该有多大？嗯，这个问题在很多年前就被代数基本定理回答了：对于一个度为 $\text{deg}(f)$ 的多项式 $f$，有 $\text{deg}(f)+1$ 个求值来完全重构其系数就足够了。因此，证明者需要向验证者发送 $\text{deg}(s_i)+1$ 个求值，现在问题变成了发送元素

$si(u)=\sum{x' \in {0,1}^{\ell-i}}\prod_{k=1}^{d}p(r,u,x')$

对于至少 $\text{deg}(s_i)+1$ 大小的集合中的所有 $u$。

关键见解

关键的见解是，对于每个 $s_i(u)$ 求和的元素，即

$\prod_{k=1}^{d}p_k(r,u,x')$

不仅是多重线性因子求值的乘积，而且：在每个被加数中都存在 不同类型的求值：

i. 一方面，因子 $p_k$ 在其前 $i-1$ 个变量中，于 $r=(r_1,r2,…r{i-1})$ 处求值 - 这些求值涉及与验证者的交互，因为它们使用来自比布尔立方体大得多的空间的随机元素（通常是基域的域扩展），由验证者选择。这些挑战的表示和代数操作比基域要求的占用更多的内存和时间。在 BDDT 的上下文中，它们涉及 $ll$ 和 $ls$（large-large 和 large-small）乘法。

ii. 另一方面，我们有 $u$，它仅仅是一个基域元素，并且因子 $p_k$ 在布尔超立方体 ${0,1}^{\ell-i}$ 中的点处的求值，对应于最后的 $\ell-i$ 个变量：这些求值不需要与验证者的交互，并且至关重要的是，不涉及基域的扩展中的元素。这些被认为是 $ss$ 乘法，因为它们被认为是基域元素。

这个观察给出了以下想法：如果可以将这些求值解耦，那么可能会有一些改进性能的空间：不依赖于与验证者交互的求值可以作为预处理阶段的一部分离线完成，然后可以在线处理涉及随机挑战的求值......

好消息是，Bagad、Dao Domb 和 Thaler 通过巧妙地使用（再次）内插的概念成功地追求了这一系列想法：可以将多项式表示为 基内插多项式 的和，这些多项式可以 预先计算，更重要的是，可以在 基域 的任意大的子集上定义；然后，可以通过评估这些辅助多项式而不是原始多项式来计算对任何所需挑战的求值。

为了了解如何进行这种解耦，让我们举一个非常简单的例子。假设验证者要求我们在一个随机挑战 $r$ 处评估一个多项式 $f$。为了具体起见，设

$f(x)=2x^2-3x+1$

以下是我们如何使用内插来执行此任务：由于 $f$ 的次数为 2，我们需要至少 3 个点来评估 $f$。让我们选择集合

$\{0,1,2\}$

首先，我们需要找到多项式 $f(x)$ 中每个点的值

• $f(0)=2(0)^2-3(0)+1=1$
• $f(1)=2(1)^2-3(1)+1=0$
• $f(2)=2(2)^2-3(2)+1=8-6+1=3$

其次，我们为集合 $\{0,1,2\}$ 构建 Lagrange 基：它有三个度为 2 的多项式

$\{L_0,L_1,L_2\}$

就像规范基一样工作：每个基多项式 $L_j(x)$ 具有特殊属性

$L_i(j)=1 \text{ if } j=i, L_i(j)=0 \text{ if } j \neq i,$

众所周知，用于生成此类多项式的 Lagrange 公式产生

• $L_0(x)$：（与 $x_0=0$ 关联）：$L_0(x)=0.5x^2-1.5x+1$
• $L_1(x)$：（与 $x_1=1$ 关联）：$L_1(x)=-x^2+2x$
• $L_2(x)$：（与 $x_2=2$ 关联）：$L_2(x)=0.5x^2-0.5x$

这三个多项式构成了集合 $\{0,1,2\}$ 的 拉格朗日基。

最后，Lagrange 多项式被构造为这些基多项式的加权和，其中每个权重是该函数在对应点的值。我们有

$f(x)=f(0) \cdot L_0(x)+f(1) \cdot L_1(x)+f(2) \cdot L_2(x)$

这是

$f(x)=1 \cdot (0.5x^2-1.5x+1)+0 \cdot (-x^2+2x)+3 \cdot (0.5x^2-0.5x)$

现在我们准备观察 $f$ 可以表示为多项式组合（独立于 $r$ 的选择 并且相对于 $f$ 是辅助的），权重是 $f$ 在由证明者选择的基域点的求值。从这个意义上讲，这些标量的计算也独立于与验证者的交互，并且可以在预处理阶段完成。

只有在这个阶段，验证者才会移交随机挑战 $r$，证明者不是通过评估 $f$ 本身而是通过评估基多项式 $L_i$ 在 $r$ 处 来计算 $f(r)$：

$f(r)=f(0)L_0(r)+f(1)L_1(r)+f(2)L_2(2)$

关键点是：$F$ 在随机挑战上的求值将被转移到辅助多项式的求值，这些辅助多项式可以被预先计算，并将集中更多的计算负担。

当然，通过使用单变量 Lagrange 基的张量积，可以将此想法推广到多元多项式。例如，假设我们需要计算多项式

$f(Y_1,Y_2)=Y_1(2+Y_2)^2$

作为 $Y_1$ 中的多项式，它的次数为 1，作为 $Y_2$ 中的多项式，它的次数为 2。我们现在将考虑在网格 $\{0,1,2\}^2$ 上内插 $f$；下一步是找到与单变量 Lagrange 多项式起相同作用的二元多项式。毫不奇怪，如果我们考虑单变量基

$\{L_0,L_1,L_2\}$

并定义 $L_{i,j}(Y_1,Y_2)=L_i(Y_1)L_j(Y_2)$，然后集合

$L=\{L_{i,j}:(i,j) \in {0,1,2}^2\}$

将验证

$L{i,j}(a,b)=1 \text{ if } (a,b)=(i,j), L{i,j}(a,b)=0 \text{ if } (a,b) \neq (i,j)$

所以

$f(Y_1,Y2)=\sum{(i,j) \in {0,1,2}^2}f(i,j)L_{i,j}(Y_1,Y_2)$

向前推进

因此，在解释以下内容时，先前的讨论将在 SUMCHECK 协议中实现

$\prod_{k=1}^{d}p_k(r,X_i,x')$

对于固定在布尔超立方体 ${0,1}^{\ell-i}$ 和 $u$ 在基域的方便子集中的 $x'$ ，作为多项式的求值

$F_{u,x'}(Y_1,Y2,…,Y{i-1})=\prod_{k=1}^{d}p_k(Y,u,x')$

在随机挑战 $r=(r_1,r2,…r{i-1})$ 处。同样，为了简单起见，我们将采用更合理的表示法

$F(Y)=\prod_{k=1}^{d}p_k(Y,u,x')$

同样在这一点上，我们将一般地假设每个因子 $p_k$ 实际上都包含 $X_i$ 作为一个变量；在这种情况下，证明者需要评估的多项式 $s_i(X_i)$ 的次数为 $d$，因此我们需要至少 $d+1$ 个元素的子集来评估这样一个多项式。

为具体起见，假设我们选择基域中具有 $d+1$ 个点的子集 $U_d$。然后我们将考虑网格

$G_g=U_d \times \cdots \times U_d=U_d^i$

来构建我们的拉格朗日多元多项式 $L_v(Y)$ 与 $v \in G_d$。为简单起见，我们从网格的表示法中省略了 $i$。

现在使用多元 Lagrange 基内插 $F$ 会将此 $F$ 转换为由具有小坐标的网格点 $v \in G_d$ 索引的和，并用在基域元素处 $F$ 的求值加权

$F(Y)=\sum_{v \in G_d}F(v)L_v(Y)$

现在在查看 $s_i(u)$ 的时候，请记住我们需要在最后 $\ell-1$ 个坐标的超立方体上求和，并且 $u$ 现在是 $X_i$ 变量的求值。这里的关键是，我们意识到 超立方体上的求和与来自内插的求和很好地相互作用：我们现在将明确 $F$ 与 $u$ 和 $x'$ 的依赖关系

$si(u)=\sum{x' \in {0,1}^{\ell-i}}F{u,x'}(r)=\sum{x' \in {0,1}^{\ell-i}}\sum_{v \in Gd}F{u,x'}(v)Lv(r)=\sum{v \in Gd}\left(\sum{x' \in {0,1}^{\ell-i}}F_{u,x'}(v)\right)L_v(r)$

从这个表达式中，我们能够看到为什么这种策略有效：要发送给验证者的期望值 $s_i(u)$ 仅仅是预先计算的插值多项式的线性组合，涉及大的乘法（因为它们依赖于随机挑战），这些多项式由超立方体索引的总和加权，是预先计算的在基域网格向量上的取值，也就是 小 系数。

此线性组合中的系数称为 累加器，主要是因为它们是一个总和。对于每个固定的 $v \in G_d$ 和 $u$，则

$\sum{x' \in {0,1}^{\ell-i}}F(v)=\sum{x' \in {0,1}^{\ell-1}}\prod_{k=1}^{d}p_k(v,u,x')=A_i(v,u)$

这些都不依赖于与验证者的交互，因此可以方便地离线处理。要计算的累加器的数量取决于多项式 $s_i(X_i)$ 的次数度数，并且可以通过假设它是度度为 $d$ 的多项式来通用地解决该问题，或通过在每一轮中细化来决定有多少个因子确实包含感兴趣的变量。

优化预计算阶段

现在由于网格中元素的索引性质和系数的结构，仍然可以在预计算阶段完成大量工作。作者提出了一种称为 idx4 的算法 - 简而言之，它是一种选择规则。它的功能是确定乘积项对哪些累加器 $A_i(v,u)$ 有贡献，从而使该项只需计算一次，然后有效地重复使用。

目标：重用计算。 优化不是为每个累加器重新计算所有乘积，而是让每个 PP 只计算一次，然后将其分发给所有相应的累加器。idx4 函数是决定“每个产品 PP 去哪里”的机制。

你可以将 idx4 视为模式匹配或解构函数。它的工作是获取评估前缀 $\beta$，并查看它适合多少个有效的累加器模式。

• 输入： 前缀 $\beta=(\beta_1,…,\beta_l)$，其中每个 $\beta_j$ 属于评估点集 $U_d$。
• 过程： 对于每一轮 $i$（从 1 到 $l$），idx4 尝试将 $\beta$ 分解为三个部分，这些部分与累加器 $A_i(v,u)$ 的结构匹配：

1. $v=(\beta1,…,\beta{i-1})$：对应于先前几轮挑战的前缀。
2. $u=\beta_i$：当前轮 $i$ 的评估点。
3. $y=(\beta_{i+1},…,,\beta_l)$：前缀的后缀。
   • 关键选择条件： 选择规则很简单：仅当后缀 $y$ 仅由 二进制值（0 和 1） 组成时，给定轮 $i$ 的解构才有效。如果 $y$ 中的任何元素是非二进制的，则前缀 $\beta$ 不会贡献给任何轮 $i$ 的累加器。
   • 输出： 该函数返回可以从输入 $\beta$ 形成的所有有效元组 $(i,v,u,y)$ 的集合。

此选择过程在预计算阶段进行，典型的流程如下：

1. 该算法遍历每个可能的评估前缀 $\beta \in (U_d)^l$。
2. 对于给定的 $\beta$，它计算乘积项 $P=\prod_{k=1}^{d}p_k(\beta,x'')$。
3. 它调用函数 idx4$(\beta)$ 以获取目标索引集 $I$。
4. 最后，它遍历 $I$ 中的每个元组 $(i,v,u,y)$ 并将 $P$ 的值添加到相应的累加器 $A_i(v,u)$。

内插的选择

我们的文章扩展了通过 Lagrange 插值分离不同类型的评估的一般原理。但是，BDDT 更深入地研究了细节并稍微修改了所涉及的插值基础，以利用 $g$ 的因子实际上是 多重线性 多项式这一事实。

作者提出的 Lagrange 内插的变体使用其在 $d$ 个不同点的评估加上其前导（最高度）系数来重构一个度为 $d$ 的多项式，而不是典型的 $d+1$ 个评估。该前导系数被称为 无穷大处的评估，并表示为 $s(\infty)$。

然后用于内插的公式变为：

$s(X)=a \cdot \prod_{k=1}^{d}(X-xk)+\sum{k=1}^{d}s(xk) \cdot L{\{x_i\},k}(X)$

其中：

• $a$ 是 $s(X)$ 的前导系数，也表示为 $s(\infty)$。
• $x_1,…,x_d$ 是 $d$ 个不同的评估点。
• $s(x_k)$ 是 $s(X)$ 在点 $x_k$ 处的评估。
• $L_{\{x_i\},k}(X)$ 是点集 $\{x_1,…,x_d\}$ 的第 $k$ 个 Lagrange 基多项式。

让我们举一个例子，并表明这实际上成立。

玩具示例：2 次多项式

让我们取多项式 $s(X)=3X^2-5X+2$。在 BDDT 方法中，要完全编码该多项式，我们只需要 只有 2 个评估和前导系数。

1. 我们首先收集必要的信息：

   • 无穷大处的评估： 前导系数为 $a=3$。因此， $s(\infty)=3$。
   • 评估点： 我们选择两个不同的点，例如， $x_1=0$ 和 $x_2=1$。

   • 评估：

     a. $s(0)=3(0)^2-5(0)+2=2$

     b. $s(1)=3(1)^2-5(1)+2=0$

2. 现在我们构造内插基：

   • 点 0,1 的 Lagrange 基多项式为：

     a. $L_1(X)=\frac{X-1}{0-1}=1-X$

     b. $L_2(X)=\frac{X-0}{1-0}=X$

   • 对于 $d=2$ 的内插公式为：$s(X)=s(\infty) \cdot (X-x_1)(X-x_2)+s(x_1)L_1(X)+s(x_2)L_2(X)$

   • 代入值：

     $s(X)=3 \cdot (X-0)(X-1)+2 \cdot (1-X)+0 \cdot (X)$

   • 简化：

     $s(X)=3(X^2-X)+2-2X$

     $s(X)=3X^2-3X+2-2X$

     $s(X)=3X^2-5X+2$

     结果与原始多项式匹配。

出于实际目的，BDDT 专注于形式为 $U_d=\{\infty,0,1,2,…d-1\}$ 的评估集来内插度为 $d$ 的多项式。

多项式乘积的 $s(\infty)$ 计算

进行此修改的原因是多项式乘积的前导系数始终易于计算：分配律确保

$s(X)=p(X)q(X) \Longrightarrow s(\infty)=p(\infty)q(\infty)$

也就是说——乘积的前导系数是前导系数的乘积。此外，对于线性多项式 $p_i(X)$，其前导系数可以计算为其在 1 和 0 处的评估之差：$p_i(1)-p_i(0)$。

因此，公式为：

$s(\infty)=\prod_{i=1}^{d}pi(\infty)=\prod{i=1}^{d}(p_i(1)-p_i(0))$

示例：

设 $s(X)=p_1(X) \cdot p_2(X)$，其中：

- $p_1(X)=2X+3$

- $p_2(X)=5X-4$1. 计算每个因子的 $p_i(\infty)$：

• $p_1(\infty) = p_1(1) - p_1(0) = (2(1)+3) - (2(0)+3) = 5 - 3 = 2$。(p1 的前导系数是 2)。
• $p_2(\infty) = p_2(1) - p_2(0) = (5(1)-4) - (5(0)-4) = 1 - (-4) = 5$。(p2 的前导系数是 5)。
  2. 计算 $s(\infty)$： $s(\infty) = p_1(\infty) \cdot p_2(\infty) = 2 \cdot 5 = 10$
  3. 验证：

让我们将多项式相乘来明确地找到 $s(X)$：$s(X) = (2X+3)(5X-4) = 10X^2 - 8X + 15X - 12 = 10X^2 + 7X - 12$

$s(X)$ 的前导系数是 10，这证实了该规则完美运行。

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