江苏企业网站建设公司,北京果木烤鸭制作方法,南宁手机网站开发策划,网站内连接sumcheck是一个交互式证明协议#xff0c;给定域F上的多元多项式g(x1,...,xv)g(x_1,...,x_v)g(x1,...,xv)#xff0c;证明者Prover可以向验证者Verifier证明该多项式ggg的遍历求和值等于公开值HHH#xff0c;即 H∑b1,b2,...,bv∈{0,1}vg(b1,b2,...,bv)H \sum_{b_1,b_2,…sumcheck是一个交互式证明协议给定域F上的多元多项式g(x1,...,xv)g(x_1,...,x_v)g(x1,...,xv)证明者Prover可以向验证者Verifier证明该多项式ggg的遍历求和值等于公开值HHH即 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) Hb1,b2,...,bv∈{0,1}v∑g(b1,b2,...,bv) 法一 Verifier可以直接通过上述等式计算验证但直接计算需要2v2^v2v次求和
法二Verifier将计算转移到计算能力更强的Prover即本文所述的sum-check协议通过sum-check协议Prover使得Verifier相信其遍历求和值等于HHH
sumcheck
sumcheck一共需要进行vvv轮交互其过程如下
第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) g1(X1)b2,...,bv∈0,1v∑g(X1,b2,...,bv) Verifier: 检查Hg1(0)g1(1)Hg_1(0) g_1(1)Hg1(0)g1(1)是否成立如果成立则随机选取r1∈Fr_1 \in Fr1∈F发送给Prover
第j轮 Prover向Verifier发送一个单变量多项式 gj(Xj)∑bj1,...,bv∈{0,1}vg(r1,...,rj−1,Xj,bj1,...,bv)g_j(X_j)\sum_{b_{j1},...,b_v \in \{0,1\}^v}g(r_1,...,r_{j-1},X_j,b_{j1},...,b_v) gj(Xj)bj1,...,bv∈{0,1}v∑g(r1,...,rj−1,Xj,bj1,...,bv) Verifier: 检查gj−1(rj−1)gj(0)gj(1)g_{j-1}(r_{j-1})g_j(0) g_j(1)gj−1(rj−1)gj(0)gj(1)是否成立如果成立则随机选取rj∈Fr_j \in Frj∈F发送给Prover
第v轮 Prover向Verifier发送一个单变量多项式 gv(Xv)g(r1,r2...,rv−1,Xv)g_v(X_v)g(r_1,r_2...,r_{v-1},Xv) gv(Xv)g(r1,r2...,rv−1,Xv) Verifier: 检查gv−1(rv−1)gv(0)gv(1)g_{v-1}(r_{v-1})g_v(0) g_v(1)gv−1(rv−1)gv(0)gv(1)是否成立如果成立则计算g(r1,r2,...,rv)g(r_1,r_2,...,r_v)g(r1,r2,...,rv) 并验证g(r1,r2,...,rv)gv(rv)g(r_1,r_2,...,r_v) g_v(r_v)g(r1,r2,...,rv)gv(rv)是否成立
例如 g(X1,X2,X3)2X13X1X3X2X3g(X_1,X_2,X_3) 2X_1^3 X_1X_3X_2X_3g(X1,X2,X3)2X13X1X3X2X3 ,其遍历求和值H12H 12H12
第1轮 Prover向Verifier发送一个单变量多项式( univariate polynomial) g1(X1)8X132X11g_1(X_1)8X_1^32X_11 g1(X1)8X132X11 Verifier: 验证Hg1(0)g1(1)12Hg_1(0) g_1(1) 12Hg1(0)g1(1)12并随机选取r12r_1 2r12发送给Prover
第2轮 Prover向Verifier发送一个单变量多项式 g2(X2)34X2g_2(X_2)34 X_2 g2(X2)34X2 Verifier: 验证g1(2)g2(0)g2(1)69g_{1}(2)g_2(0) g_2(1) 69g1(2)g2(0)g2(1)69并随机选取r23r_2 3r23发送给Prover
第3轮 Prover向Verifier发送一个单变量多项式 g3(X3)165X3g_3(X_3)165X_3 g3(X3)165X3 Verifier: 验证g2(r2)g3(0)g3(1)37g_{2}(r_{2})g_3(0) g_3(1) 37g2(r2)g3(0)g3(1)37并随机选取r36r_3 6r36计算并验证g(r1,r2,...,rv)46g3(6)g(r_1,r_2,...,r_v) 46 g_3(6)g(r1,r2,...,rv)46g3(6)
