Sum-check 协议

形式陈述 ​

设 $g\in \mathbb{F}[X_1,\dots ,X_m]$，每个变量次数至多 $d$。Prover 声称

$$H=\sum _{b\in \{0,1{\}}^m}g(b).$$

第 $1$ 轮 prover 发送次数至多 $d$ 的单变量多项式

$$G_1(X_1)=\sum _{b_2,\dots ,b_m\in \{0,1\}}g(X_1,b_2,\dots ,b_m),$$

验证者检查 $H=G_1(0)+G_1(1)$，通过后才随机取 $r_1\in \mathbb{F}$。第 $i$ 轮发送

$$G_i(X_i)=\sum _{b_{i+1},\dots ,b_m}g(r_1,\dots ,r_{i-1},X_i,b_{i+1},\dots ,b_m),$$

并检查 $G_{i-1}(r_{i-1})=G_i(0)+G_i(1)$。末轮随机取 $r_m$ 后，验证者直接计算或查询 $g(r_1,\dots ,r_m)$，检查其等于 $G_m(r_m)$。

诚实 prover 使所有等式恒成立，故 perfect completeness 为 $1$。若初始声明错误，任一轮伪多项式与诚实多项式之差非零、次数至多 $d$，在随机 $r_i$ 上碰巧相等的概率至多 $d/|\mathbb{F}|$；对 $m$ 轮作 union bound，soundness error 至多 $md/|\mathbb{F}|$。协议有 $m$ 轮，通信 $O(md)$ 个域元素；验证者还必须承担一次 $g$ 的随机点求值成本。

直觉 ​

指数多个求和项被逐变量折叠：每轮只留下一个低次单变量多项式，再用随机点把当前承诺绑定到下一轮。撒谎者必须先提交多项式，之后才看到挑战；一旦承诺偏离真实部分和，只有少数域点能让谎言继续伪装。

交互顺序公理库交互式证明系统Interactive proof system · IP由计算受限的概率验证者与计算无界证明者多轮交互定义的证明模型。是 soundness 的核心。若 prover 先知道 $r_i$ 再选择 $G_i$，总能构造一个只在该点过关的伪多项式。

例子与边界 ​

当 $m=2$ 时，目标是 $H=\sum _{b_1,b_2}g(b_1,b_2)$。第一轮把第二变量求和得到 $G_1(X)$；随机固定 $r_1$ 后，第二轮只需证明 $G_1(r_1)=G_2(0)+G_2(1)$，最后检查 $G_2(r_2)=g(r_1,r_2)$。四项总和由两次单变量承诺和一个随机点求值锁定。

验证者必须检查每个 $G_i$ 的 degree bound。若允许 prover 发送任意高次多项式，它可在许多指定点插值通过检查，根数概率界不再给出小 soundness。域也需足够大；当 $md\ge |\mathbb{F}|$ 时，上界可能没有信息，应扩域或重复协议。

Sum-check 不会免费验证任意黑盒 $g$。最后一步要求验证者能高效得到 $g$ 在随机点的值，或由外层协议把该值归约成另一个可检查声明。Prover 的诚实计算仍可能需要枚举 $2^m$ 项；协议节省的是验证成本，不是总计算量。

推论与应用 ​

Sum-check 把算术化公理库算术化Arithmetization把布尔关系嵌入有限域低次多项式，使离散正确性声明可由随机代数恒等式检查。后的指数求和声明压缩成线性轮数交互，是 $IP=PSPACE$、GKR 协议和可验证计算的基本组件。外层协议负责构造低次 $g$ 与最终求值 oracle，本协议负责逐变量折叠和错误概率。

Soundness 参数必须与“每变量 degree”版本一致；若来源只给总次数界，应按其定理重算根数上界，不能拼接不同 convention 的常数。

参考资料

• Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan, “Algebraic Methods for Interactive Proof Systems,” Journal of the ACM 39(4), 1992, pp. 859–868.
• Justin Thaler, Proofs, Arguments, and Zero-Knowledge, 2023, Ch. 4, the sum-check protocol.