sumcheck是一個(gè)交互式證明協(xié)議，給定域F上的多元多項(xiàng)式$g(x_1,...,x_v)$，證明者Prover可以向驗(yàn)證者Verifier證明該多項(xiàng)式$g$的遍歷求和值等于公開(kāi)值$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可以直接通過(guò)上述等式計(jì)算驗(yàn)證，但直接計(jì)算需要$2^v$次求和

法二：Verifier將計(jì)算轉(zhuǎn)移到計(jì)算能力更強(qiáng)的Prover，即本文所述的sum-check協(xié)議，通過(guò)sum-check協(xié)議，Prover使得Verifier相信其遍歷求和值等于$H$

sumcheck

sumcheck一共需要進(jìn)行$v$輪交互，其過(guò)程如下：

第1輪：

• Prover：向Verifier發(fā)送一個(gè)單變量多項(xiàng)式( 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)$是否成立，如果成立則隨機(jī)選取$r_1\in F$發(fā)送給Prover

第j輪：

• Prover：向Verifier發(fā)送一個(gè)單變量多項(xiàng)式
  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)$是否成立，如果成立則隨機(jī)選取$r_j\in F$發(fā)送給Prover

第v輪：

• Prover：向Verifier發(fā)送一個(gè)單變量多項(xiàng)式
  $$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)$是否成立，如果成立則計(jì)算$g(r_1,r_2,...,r_v)$ ，并驗(yàn)證$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發(fā)送一個(gè)單變量多項(xiàng)式( univariate polynomial)
  $$g_1(X_1)=8X_1^3+2X_1+1$$

• Verifier: 驗(yàn)證$H=g_1(0)+g_1(1)=12$，并隨機(jī)選取$r_1=2$發(fā)送給Prover

第2輪：

• Prover：向Verifier發(fā)送一個(gè)單變量多項(xiàng)式
  $$g_2(X_2)=34+X_2$$

• Verifier: 驗(yàn)證$g_1(2)=g_2(0)+g_2(1)=69$，并隨機(jī)選取$r_2=3$發(fā)送給Prover

第3輪：

• Prover：向Verifier發(fā)送一個(gè)單變量多項(xiàng)式
  $$g_3(X_3)=16+5X_3$$

• Verifier: 驗(yàn)證$g_2(r_2)=g_3(0)+g_3(1)=37$，并隨機(jī)選取$r_3=6$，計(jì)算并驗(yàn)證$g(r_1,r_2,...,r_v)=46=g_3(6)$