sum-check protocol

sumcheck是一个交互式证明协议，给定域F上的多元多项式$g(x_1,...,x_v)$，证明者Prover可以向验证者Verifier证明该多项式$g$的遍历求和值等于公开值$H$，即
H=∑b1,b2,...,bv∈{0,1}vg(b1,b2,...,bv)H= \sum_{b_1,b_2,...,b_v \in \{0,1\}^v}g(b_1,b_2,...,b_v) H=b1​,b2​,...,bv​∈{0,1}v∑​g(b1​,b2​,...,bv​)
法一： Verifier可以直接通过上述等式计算验证，但直接计算需要$2^v$次求和

法二：Verifier将计算转移到计算能力更强的Prover，即本文所述的sum-check协议，通过sum-check协议，Prover使得Verifier相信其遍历求和值等于$H$

sumcheck

sumcheck一共需要进行$v$轮交互，其过程如下：

第1轮：

• Prover：向Verifier发送一个单变量多项式( univariate polynomial)
  $$g_1(X_1)=\sum _{b_2,...,b_v\in {0,1}^v}g(X_1,b_2,...,b_v)$$

• Verifier: 检查$H=g_1(0)+g_1(1)$是否成立，如果成立则随机选取$r_1\in F$发送给Prover

第j轮：

• Prover：向Verifier发送一个单变量多项式
  gj(Xj)=∑bj+1,...,bv∈{0,1}vg(r1,...,rj−1,Xj,bj+1,...,bv)g_j(X_j)=\sum_{b_{j+1},...,b_v \in \{0,1\}^v}g(r_1,...,r_{j-1},X_j,b_{j+1},...,b_v) gj​(Xj​)=bj+1​,...,bv​∈{0,1}v∑​g(r1​,...,rj−1​,Xj​,bj+1​,...,bv​)

• Verifier: 检查$g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$是否成立，如果成立则随机选取$r_j\in F$发送给Prover

第v轮：

• Prover：向Verifier发送一个单变量多项式
  $$g_v(X_v)=g(r_1,r_2...,r_{v-1},Xv)$$

• Verifier: 检查$g_{v-1}(r_{v-1})=g_v(0)+g_v(1)$是否成立，如果成立则计算$g(r_1,r_2,...,r_v)$ ，并验证$g(r_1,r_2,...,r_v)=g_v(r_v)$是否成立

例如 $g(X_1,X_2,X_3)=2X_1^3+X_1{X}_3+X_2{X}_3$ ,其遍历求和值$H=12$

第1轮：

• Prover：向Verifier发送一个单变量多项式( univariate polynomial)
  $$g_1(X_1)=8X_1^3+2X_1+1$$

• Verifier: 验证$H=g_1(0)+g_1(1)=12$，并随机选取$r_1=2$发送给Prover

第2轮：

• Prover：向Verifier发送一个单变量多项式
  $$g_2(X_2)=34+X_2$$

• Verifier: 验证$g_1(2)=g_2(0)+g_2(1)=69$，并随机选取$r_2=3$发送给Prover

第3轮：

• Prover：向Verifier发送一个单变量多项式
  $$g_3(X_3)=16+5X_3$$

• Verifier: 验证$g_2(r_2)=g_3(0)+g_3(1)=37$，并随机选取$r_3=6$，计算并验证$g(r_1,r_2,...,r_v)=46=g_3(6)$