title
tags
Milestones 08. Sumcheck Protocol
zk
computation theory
interactive proof
sumcheck protocol
WTF zk 教程 里程碑 08：Sumcheck Protocol 在本讲中，我们将介绍 Sumcheck 协议（Sumcheck Protocol），一个非常经典的交互式证明系统的协议。在这个协议中，验证者通过与证明者的交互，以很小的开销验证一个非常复杂的多项式求和结果。
给定一个定义在有限域 $F$ 上的 $n$ 元多项式 $P(x_1, x_2, \dots, x_n)$ ，我们想要求解：
$$
S = \sum_{x_1, x_2, ..., x_n \in {0,1}^n} P(x_1, x_2, \dots, x_n)
$$
即这些多项式在所有可能的 $\set{0, 1}$ 输入上求和的结果。
这个问题看起来简单，但是却包含 $2^n$ 项的求和。当 $n$ 很大的时候，计算这个求和的值是及其困难的。
举个例子，对于一个 3 元多项式：
$$
P(x_1, x_2, x_3) = x_1 x_2 x_3 + 3 x_1 x_2 + x_3^2
$$
求和时需要计算 $2^3 = 8$ 项的和，即：
$$
S = P(0,0,0) + P(0,0,1) + P(0,1,0) + P(0,1,1) + P(1,0,0) + P(1,0,1) + P(1,1,0) + P(1,1,1)
$$
最终的结果为 $S = 0 + 1 + 0 + 1 + 0 + 1 + 3 + 5 = 11$ 。
假设 Bob 是一个可怜的多项式时间图灵机，他没法在多项式时间内算出这个结果。他有一个朋友 Alice， 是个有无限计算资源的恶魔，可以轻松的算出 $S$ 。但是恶魔喜欢骗人， Bob 需要一种方法来验证 Alice 的结果。
所以它们决定使用一种交互式的证明协议 Sumcheck Protocol，让 Bob 仅花费常数次计算来验证 Alice 的结果。具体协议如下：
证明者 Alice 声称
$$
S = \sum_{x_1, x_2, ..., x_n \in {0,1}^n} P(x_1, x_2, \dots, x_n)
$$
一共需要 $n$ 轮交互。
证明者 Alice 将除了第一个变量 $x_1$ 之外的 $n-1$ 个变量固定，将多项式 $P(x_1, x_2, \dots, x_n)$ 转化为一个新的一元多项式 $q_1(X_1)$ ：
$$
q_1(X_1) = \sum_{x_2, \dots, x_n \in {0,1}^{n-1}} P(X_1, x_2, \dots, x_n)
$$
然后，Alice 将 $q_1(X_1)$ 发送给验证者 Bob。Bob 验证 $q_1(0) + q_1(1)$ 是否等于 $S$ 。如果等于，则继续进行验证：随机选择一个值 $r_1 \in \mathbb{F}$ ，发送给 Alice；否则，拒绝。
Alice 将除了第二个变量 $x_2$ 之外的 $n-1$ 个变量固定，将多项式 $P(r_1, x_2, \dots, x_n)$ 转化为一个新的一元多项式 $q_2(X_2)$ ：
$$
q_2(X_2) = \sum_{x_3, \dots, x_n \in {0,1}^{n-2}} P(r_1, X_2, x_3, \dots, x_n)
$$
然后，Alice 将 $q_2(X_2)$ 发送给 Bob。Bob 验证 $q_2(0) + q_2(1)$ 是否等于 $q_1(r_1)$ 。如果等于，则继续进行验证：随机选择一个值 $r_2 \in \mathbb{F}$ ，发送给 Alice；否则，拒绝。
Alice 将除了第 $j$ 个变量 $x_j$ 之外的 $n-j$ 个变量固定，将多项式 $P(r_1, \dots, r_{j-1}, X_j, x_{j+1}, \dots, x_n)$ 转化为一个新的一元多项式 $q_j(X_j)$ ：
$$
q_j(X_j) = \sum_{x_{j+1}, \dots, x_n \in {0,1}^{n-j}} P(r_1, \dots, r_{j-1}, X_j, x_{j+1}, \dots, x_n)
$$
然后，Alice 将 $q_j(X_j)$ 发送给 Bob。Bob 验证 $q_j(0) + q_j(1)$ 是否等于 $q_{j-1}(r_{j-1})$ 。如果等于，则继续进行验证：随机选择一个值 $r_j \in \mathbb{F}$ ，发送给 Alice；否则，拒绝。
Alice 将除了最后一个变量 $x_n$ 之外的 $n-1$ 个变量固定，将多项式 $P(r_1, \dots, r_{n-1}, X_n)$ 转化为一个新的一元多项式 $q_n(X_n)$ ：
$$
q_n(X_n) = P(r_1, \dots, r_{n-1}, X_n)
$$
然后，Alice 将 $q_n(X_n)$ 发送给 Bob。Bob 验证 $q_n(0) + q_n(1)$ 是否等于 $q_{n-1}(r_{n-1})$ 。如果等于，则继续进行验证：随机选择一个值 $r_n \in \mathbb{F}$ ，发送给 Alice；否则，拒绝。
最后，验证者 Bob 检查 $P(r_1, \dots, r_n)$ 是否等于 $q_n(r_n)$ 。如果等于，则接受证明者 Alice 的证明，否则拒绝。
我们还是以之前的 3 元多项式为例演示 Sumcheck Protocol，其中 $\mathbb{F} = \mathbb{F_{31}}$ 。
$$
P(x_1, x_2, x_3) = x_1 x_2 x_3 + 3 x_1 x_2 + x_3^2
$$
证明者 Alice 声称 $S$ 的值为 10。验证一共需要 3 轮。
证明者 Alice 将除了第一个变量 $x_1$ 之外的 $2$ 个变量固定，将多项式 $P(x_1, x_2, x_3)$ 转化为一个新的一元多项式 $q_1(X_1)$ ：
$$
q_1(X_1) = P(X_1, 0, 0) + P(X_1, 0, 1) + P(X_1, 1, 0) + P(X_1, 1, 1)
$$
带入 $P(x_1, x_2, x_3)$ 得到，得到
$$
q_1(X_1) = 7 X_1 + 2
$$
Alice 将 $q_1(X_1)$ 发送给验证者 Bob。Bob 验证 $q_1(0) + q_1(1) = 2+ 9 = 11$ ，等于 $S$ ，验证通过。Bob 随机选择一个值 $r_1 = 2 \in \mathbb{F}$ 返回给 Alice，继续下一轮。
Alice 将除了第二个变量 $x_2$ 之外的 $2$ 个变量固定，将多项式 $P(r_1, x_2, x_3)$ 转化为一个新的一元多项式 $q_2(X_2)$ ：
$$
q_2(X_2) = P(r_1, X_2, 0) + P(r_1, X_2, 1)
$$
带入 $P(x_1, x_2, x_3)$ （其中 $r_1 = 2$ ）得到
$$
q_2(X_2) = 14 X_2 + 1
$$
Alice 将 $q_2(X_2)$ 发送给验证者 Bob。Bob 验证 $q_2(0) + q_2(1) = 1 + 15 = 16$ ，等于 $q_1(2) = 16$ ，验证通过。Bob 随机选择一个值 $r_2 = 1 \in \mathbb{F}$ 返回给 Alice，继续下一轮。
Alice 将除了第三个变量 $x_3$ 之外的 $2$ 个变量固定，将多项式 $P(r_1, r_2, x_3)$ 转化为一个新的一元多项式 $q_3(X_3)$ ：
$$
q_3(X_3) = X_3^2 + 2X_3 +6
$$
Alice 将 $q_3(X_3)$ 发送给验证者 Bob。Bob 验证 $q_3(0) + q_3(1) = 6 + 9 = 15$ ，等于 $q_2(1) = 15$ ，验证通过。Bob 随机选择一个值 $r_3 = 3 \in \mathbb{F}$ 返回给 Alice。
最后，Bob 计算 $P(2,1,3) = 6 + 6 + 9 = 21$ ，然后计算 $q_3(r_3) = 21$ ，两者相等。因此，Bob 接受 Alice 的证明： $S = 11$ ，协议结束。
完备性（Completeness） ：对于正确的求和，证明者总是能够通过验证。
可靠性（Soundness） ：对于错误的求和，验证者接受的概率小于 $\epsilon= \frac{nv}{|\mathbb{F}|}$ ，其中 $n$ 是多项式的变量数，$v$ 是多项式的度数。如果我们选择的域 $\mathbb{F}$ 足够大，那么可靠性误差会非常小。
对于验证者 Bob 来说，每一轮的计算一元多项式的成本为 $O(v)$ ，其中 $v$ 是多项式的度数，总共 $n$ 轮。因此，验证者的总计算成本为 $O(nv)$ （外加最后计算 $P(r_1, \dots, r_n)$ 的成本），非常低。
对于证明者 Alice 来说，每一轮的计算 $n$ 元多项式的成本约为 $O(2^n)$ ，总共 $n$ 轮。因此，证明者的总计算成本为 $O(2^n)$ ，与直接计算 $S$ 的成本相当。
这一讲，我们介绍了经典的交互式验证协议 Sumcheck Protocol，包括它的基本步骤、完备性和可靠性。Sumcheck Protocol 允许我们花费非常少的计算成本验证一个非常复杂的多项式求和结果，体现了交互式证明系统的魅力。