sum-check protocol

文章列表

sum-check protocol

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

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

sumcheck

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

第1轮：

Prover：向Verifier发送一个单变量多项式( univariate polynomial)
$g1(X1)=∑b2,...,bv∈0,1vg(X1,b2,...,bv)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)$ 是否成立，如果成立则随机选取 $r1∈Fr_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)$
Verifier: 检查 $g_{j-1}(r_{j-1})=g_j(0) + g_j(1)$ 是否成立，如果成立则随机选取 $rj∈Fr_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_1X_3+X_2X_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)$

sum-check protocol

sumcheck

第1轮：

第j轮：

第v轮：

例如 g(X1,X2,X3)=2X13+X1X3+X2X3g(X_1,X_2,X_3)= 2X_1^3 + X_1X_3+X_2X_3g(X1​,X2​,X3​)=2X13​+X1​X3​+X2​X3​ ,其遍历求和值H=12H =12H=12

第1轮：

第2轮：

第3轮：

相关问题

公告

例如 $g(X_1,X_2,X_3)= 2X_1^3 + X_1X_3+X_2X_3$ ,其遍历求和值 $H = 12$