Sum-check 协议 | Codeboy's Blog

形式陈述

设 $\mathbb F$ 是有限域，且 $g$ 是多项式环 $\mathbb F[X_1,\ldots,X_m]$ 中每个变量次数至多 $d\ge0$ 的多项式，先设 $m\ge1$ 。Prover 声称

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

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

G_1(X_1)=\sum_{b_2,\ldots,b_m\in\{0,1\}} g(X_1,b_2,\ldots,b_m),

各轮都以至多 $d+1$ 个系数描述多项式，验证者先拒绝格式或次数越界的消息；第一轮再检查 $H=G_1(0)+G_1(1)$ ，通过后才随机取 $r_1\in\mathbb F$ 。第 $i$ 轮发送

G_i(X_i)=\sum_{b_{i+1},\ldots,b_m} g(r_1,\ldots,r_{i-1},X_i,b_{i+1},\ldots,b_m),

并检查 $G_{i-1}(r_{i-1})=G_i(0)+G_i(1)$ 。末轮随机取 $r_m$ 后，验证者直接计算或通过可信求值 oracle 得到 $g(r_1,\ldots,r_m)$ ，检查其等于 $G_m(r_m)$ 。

诚实 prover 使所有等式恒成立，故 perfect completeness 为 $1$ 。若初始声明错误，只要某轮开始时的声明仍错、且通过了端点一致性检查，所发多项式就必与真实部分和不同；二者之差非零、次数至多 $d$ 。只有随机 $r_i$ 落在这个差的根上，错误声明才可能首次变成正确声明，其条件概率至多 $d/|\mathbb F|$ 。若始终未发生这种事件，最后的可信求值会拒绝。对至多 $m$ 轮应用并合界，soundness error 至多 $\min\{1,md/|\mathbb F|\}$ 。

协议有 $m$ 轮，通信 $O(m(d+1))$ 个域元素； $d=0$ 时仍要传常数系数和挑战。验证者还必须承担一次 $g$ 的随机点求值成本。若 $m=0$ ，立方体只有唯一空元组，直接比较 $H=g()$ ，不需交互。

直觉

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

交互顺序是 soundness 的核心。例如在 $\mathbb F_5$ 上取 $m=1,d=2,g(X)=0$ ，却声称 $H=1$ 。若先公开挑战 $r$ ，prover 在 $r=0,1,2,3,4$ 时依次选择 $q(X)=X,1-X,3X-1,2(X-3)^2,2X+2$ 。这些多项式都满足次数至多 $2$ 、 $q(0)+q(1)=1$ 及 $q(r)=0=g(r)$ ，使假声明以概率 $1$ 通过；先承诺再挑战则仍受上述根数界约束。

Sum-check 协议 m 等于 2 的 prover-verifier 时序，展示先承诺多项式、再产生随机挑战和最终随机点检查 — Sum-check：先承诺，再挑战

例子与边界

当 $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|$ 时，上界可能没有信息，应先选择适当扩域或另证非平凡可靠性界；只有已有严格小于1的错误上界时，重复才能进一步放大。

上面先把均匀域元素作为随机原语。若用公平随机 bit 实现，可取 $|\mathbb F|=2^\ell$ 并用 $\ell$ 位系数直接均匀抽样。对其他域，拒绝采样的无限重试只有期望时间界；若截断后失败就拒绝，还要报告抽样失败对完备性的损失。不能一边要求每条执行最坏多项式时间，一边把无限重试当成免费步骤。

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

推论与应用

Sum-check 把算术化后的指数求和声明压缩成线性轮数交互，是 $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.

形式陈述 ​

反向链接

形式陈述