多变量Sumcheck协议是零知识证明中 PIOP（Polynomial IOP）框架的重要组成部分，主要用于证明如下等式的正确性： $$ c = \sum_{\vec{X} \in {0,1}^n} f(X_1, \ldots, X_n) $$ 其中，$c$ 是求和结果，$X_1, \dots, X_n$ 是 $d$ 个变量，每个取值为 0 或 1。与传统单变量多项式运算不同，多变量多项式相乘无需复杂的 FFT 运算——只需逐点相乘即可。 下面将介绍多变量多项式的基本知识，包括其表示方法与运算方式。

1. 预备知识

1.1 从单变量到多变量多项式（取值形式）

设 $\vec{g} = {g^0, g^1, \ldots, g^7}$ 为大素数域中的一个 8 阶乘法子群，其中： $$ g^8 = 1 $$ 我们可将布尔域中的位置 $i$ 用 $g^i$ 编码为二进制形式 ${000, 001, \ldots, 111}$，以构造多变量布尔函数的所有取值点。 单变量多项式 $f(X)$ 可表示为多变量多项式 $f(\vec{X}) = f(X_0, X_1, \dots, X_7)$： $$ (f(g^0), f(g^1), \ldots, f(g^7)) = (f(0,0,0), f(0,0,1), \ldots, f(1,1,1)) $$ 每个值一一对应，实现了将高维布尔函数“扁平化”为一个向量。

1.2 向量存储形式（取值形式）

多线性扩展可用小端序向量存储： $$ E[1] = \tilde{f}(0,0,0,1), \quad E[5] = \tilde{f}(0,1,0,1), \quad E[8] = \tilde{f}(1,0,0,0) $$ 这类似于用二进制表示的十进制索引来存储各点的取值。

1.3 低阶扩展（系数形式）

我们希望将 $f$ 从布尔点扩展为 $\mathbb{F}^n$ 上的函数 $\tilde{f}$。

定义： $$ \chi_w(x) = \begin{cases} 1 & w = x \ 0 & \text{otherwise} \end{cases} $$ 多变量多项式 $$ \chiw(x) = \prod{i=1}^n [(1 - x_i)(1 - w_i) + x_i w_i] $$ 类似于单变量多项式的拉格朗日基底，并常在系统初始化时预计算。

更一般地，从取值形式到系数形式的转换为： $$ \tilde{f}(x_1, \ldots, xn) = \sum{w \in {0,1}^n} f(w) \cdot \chi_w(x_1, \ldots, x_n) $$ 这里 $\tilde{f}$ 也称为 多线性扩展（MLE）。

1.4 向量存储形式（系数形式）

多线性扩展也可用小端序存储，例如： $$ E[1] = \tilde{f}(0,0,0,1), \quad E[5] = \tilde{f}(0,1,0,1), \quad E[8] = \tilde{f}(1,0,0,0) $$

若多项式为 $f(X_3, X_2, X_1, X_0)$，则 $E[1], E[5], E[8]$ 分别存储 $X_0$、$X_2 \cdot X_0$ 和 $X_3$ 项的系数。

1.5 在特定点上用取值形式计算

假设要计算 $x_1 = r$，令： $$ \tilde{f}'(x_2, \ldots, x_n) = \tilde{f}(r, x_2, \ldots, x_n) $$

let n = 2^v;
let half = n / 2;
for i in 0..half {
    let low = E[i];
    let high = E[half + i];
    E[i] = low + r * (high - low);
}

原理为： $$ \tilde{f}(r, x_2, \ldots, x_n) = (1 - r) \cdot \tilde{f}(0, x_2, \ldots, x_n) + r \cdot \tilde{f}(1, x_2, \ldots, x_n) $$ 此方法可直接在取值形式下计算，无需转换为系数形式，时间与空间复杂度均为 $O(n)$。

1.6 在特定点上用系数形式计算

1. 按第 3 节方法从取值形式转为系数形式。
2. 将特定点代入相应变量即可。

1.7 多变量多项式乘法

在基于多变量Sumcheck的 zkSNARK 协议中，MLE × MLE（多线性扩展 × 多线性扩展）运算非常常见。

设 $f, g$ 为定义在布尔超立方体 ${0,1}^v$ 上的两个 MLE（每个变量均为一次项），可用其在 $2^v$ 个点的取值向量表示。

利用取值形式，可高效计算： $$ f(r_1, \ldots, r_v) \cdot g(r_1, \ldots, r_v) $$ 即在同一点逐值相乘。

若取值向量长度不足（如未达到所需次数 $d$），需先补齐至长度 $d$，因为相乘会使次数最高加倍，保持长度 $d$ 可确保后续 IFFT 或拉格朗日插值的正确性。

这与单变量多项式在 FFT 中的处理类似：FFT 后逐点相乘，再 IFFT 返回系数形式。多变量 MLE 逐点相乘遵循相同原则，只是作用在高维布尔超立方体上。

2. 求和检验协议

目标是证明：

$$ \sum_{x \in {0,1}^n} f(x_1, \ldots, x_n) = c $$

协议步骤：

1. 证明者 构造一元多项式： $$ g_1(X1) = \sum{(x_2,\dots,x_n) \in {0,1}^{n-1}} f(X_1, x_2, \dots, x_n) $$ 并发送给 验证者（用系数形式计算）。

2. 验证者 检查 $g_1(0) + g_1(1) = c$，然后发送随机数 $r_1$。

3. 证明者 构造： $$ g_2(X2) = \sum{(x_3,\dots,x_n) \in {0,1}^{n-2}} f(r_1, X_2, \dots, x_n) $$ 验证者 检查 $g_1(r_1) = g_2(0) + g_2(1)$。

4. 重复：每轮中，证明者 发送 $gi(X)$，验证者 检查 $g{i-1}(r_{i-1}) = g_i(0) + g_i(1)$。

5. 最后一轮：验证者 检查 $g_n(0) + gn(1) = g{n-1}(r_{n-1})$，并额外计算 $f(r_1, r_2, \ldots, r_n)$ 进行最终验证。

最后一轮验证可通过查询多项式预言机完成，或由 证明者 直接在取值形式下计算。

3. 结论

多变量求和检验协议在不显式计算所有 $2^n$ 点函数值的情况下，提供了一种高效且模块化的方法来验证布尔超立方体上的大规模多线性多项式求和。通过逐步将 $n$ 元求和化简为一系列一元检验，它显著减少了证明者与验证者的通信与计算开销。该协议依赖于多线性扩展与取值形式运算，避免了高维下的复杂 FFT，使其非常适合用于 zkSNARK 和 GKR 等零知识证明系统。同时，其结构不仅通过随机挑战确保了完备性，还能与其他 PIOP 组件无缝结合，实现现代密码协议中的可扩展验证。