需证明： h i n 1 ( X ) h i n 2 ( X ) = h i n 3 ( X ) h_{in1}(X)h_{in2}(X)=h_{in3}(X) hin1(X)hin2(X)=hin3(X)
首先，Prover需添加zero-knowledge souce，引入随机数 r 0 , r 1 , r 2 r_0, r_1,r_2 r0,r1,r2： h 1 ( X ) = r 0 ∗ Z H ( X ) + h i n 1 ( X ) h_1(X)=r_0*Z_H(X)+h_{in1}(X) h1(X)=r0∗ZH(X)+hin1(X) h 2 ( X ) = r 1 ∗ Z H ( X ) + h i n 2 ( X ) h_2(X)=r_1*Z_H(X)+h_{in2}(X) h2(X)=r1∗ZH(X)+hin2(X) h 3 ( X ) = r 2 ∗ Z H ( X ) + h i n 3 ( X ) h_3(X)=r_2*Z_H(X)+h_{in3}(X) h3(X)=r2∗ZH(X)+hin3(X) 其中 Z H ( X ) Z_H(X) ZH(X)为vanishing polynomial， Z H ( X ) Z_H(X) ZH(X)对Prover和Verifier均已知。
2. 直观证明方案 2.1 Prover对多项式进行commit： H 1 = c o m ( h 1 ( X ) ) H_1=com(h_1(X)) H1=com(h1(X)) H 2 = c o m ( h 2 ( X ) ) H_2=com(h_2(X)) H2=com(h2(X)) H 3 = c o m ( h 3 ( X ) ) H_3=com(h_3(X)) H3=com(h3(X))
计算quotient polynomial并commit： t ( X ) = h 1 ( X ) h 2 ( X ) − h 3 ( X ) Z H ( X ) t(X)=\frac{h_1(X)h_2(X)-h_3(X)}{Z_H(X)} t(X)=ZH(X)h1(X)h2(X)−h3(X) T = c o m ( t ( X ) ) T=com(t(X)) T=com(t(X))
Prover计算challenge z z z，及相应各多项式的evaluation值为： h 1 = h 1 ( z ) h_1=h_1(z) h1=h1(z) h 2 = h 2 ( z ) h_2=h_2(z) h2=h2(z) h 3 = h 3 ( z ) h_3=h_3(z) h3=h3(z) t = t ( z ) t=t(z) t=t(z)
Prover计算challenge v v v，witness并commit： w ( X ) = ( t ( X ) − z ) + v ( h 1 ( X ) − h 1 ) + v 2 ( h 2 ( X ) − h 2 ) + v 3 ( h 3 ( X ) − h 3 ) X − z w(X)=\frac{(t(X)-z)+v(h_1(X)-h_1)+v^2(h_2(X)-h_2)+v^3(h_3(X)-h_3)}{X-z} w(X)=X−z(t(X)−z)+v(h1(X)−h1)+v2(h2(X)−h2)+v3(h3(X)−h3) W = c o m ( w ( X ) ) W=com(w(X)) W=com(w(X))
Prover给Verifier发送的proof内容有： π = ( H 1 , H 2 , H 3 , h 1 , h 2 , h 3 , W , T ) \pi=(H_1,H_2,H_3,h_1,h_2,h_3,W,T) π=(H1,H2,H3,h1,h2,h3,W,T)
2.2 VerifierVerifier计算quotient evaluation： t = h 1 h 2 − h 3 Z H ( z ) t=\frac{h_1h_2-h_3}{Z_H(z)} t=ZH(z)h1h2−h3
Verifier计算batch commitment： F = T + v ∗ H 1 + v 2 ∗ H 2 + v 3 ∗ H 3 F=T+v*H_1+v^2*H_2+v^3*H_3 F=T+v∗H1+v2∗H2+v3∗H3
Verifier计算batch evaluation point： E = ( t + v h 1 + v 2 h 2 + v 3 h 3 ) ∗ G E=(t+vh_1+v^2h_2+v^3h_3)*G E=(t+vh1+v2h2+v3h3)∗G
Verifier验证如下等式是否成立： e ( W , c o m ( X ) ) = e ( z ∗ W + F − E , G ) e(W,com(X))=e(z*W+F-E,G) e(W,com(X))=e(z∗W+F−E,G)
3. 优化证明方案 3.1 Prover对多项式进行commit： H 1 = c o m ( h 1 ( X ) ) H_1=com(h_1(X)) H1=com(h1(X)) H 2 = c o m ( h 2 ( X ) ) H_2=com(h_2(X)) H2=com(h2(X)) H 3 = c o m ( h 3 ( X ) ) H_3=com(h_3(X)) H3=com(h3(X))
Prover计算challenge z z z，仅对 h 1 h_1 h1的evaluation值为： h 1 = h 1 ( z ) h_1=h_1(z) h1=h1(z)
Prover计算quotient polynomial并commit： t ( X ) = h 1 ( X ) h 2 ( X ) − h 3 ( X ) Z H ( X ) t(X)=\frac{h_1(X)h_2(X)-h_3(X)}{Z_H(X)} t(X)=ZH(X)h1(X)h2(X)−h3(X) T = c o m ( t ( X ) ) T=com(t(X)) T=com(t(X))
Prover计算linearisation polynomial： r ( X ) = h 1 ∗ h 2 ( X ) − h 3 ( X ) r(X)=h_1*h_2(X)-h_3(X) r(X)=h1∗h2(X)−h3(X) r = r ( z ) r=r(z) r=r(z)
Prover计算challenge v v v，witness并commit： w ( X ) = ( t ( X ) − t ) + v ( r ( X ) − r ) + v 2 ( h 1 ( X ) − h 1 ) X − z w(X)=\frac{(t(X)-t)+v(r(X)-r)+v^2(h_1(X)-h_1)}{X-z} w(X)=X−z(t(X)−t)+v(r(X)−r)+v2(h1(X)−h1) W = c o m ( w ( X ) ) W=com(w(X)) W=com(w(X))
Prover给Verifier发送的proof内容为：【相比于直观方案，优化方案的proof size减少了1个field element。】 π = ( H 1 , H 2 , H 3 , h 1 , r , W , T ) \pi=(H_1,H_2,H_3,h_1,r,W,T) π=(H1,H2,H3,h1,r,W,T)
3.2 VerifierVerifier计算quotient evaluation： t = r / Z H ( z ) t=r/Z_H(z) t=r/ZH(z)
Verifier计算batch commitment： R = h 1 ∗ H 2 + H 3 R=h_1*H_2+H_3 R=h1∗H2+H3 F = T + v ∗ R + v 2 ∗ H 1 F=T+v*R+v^2*H_1 F=T+v∗R+v2∗H1
Verifier计算batch evaluation point：【相比于直观方案，优化方案中减少了1次group addition】 E = ( t + v r + v 2 h 1 ) ∗ G E=(t+vr+v^2h_1)*G E=(t+vr+v2h1)∗G
Verifier验证如下等式是否成立： e ( W , c o m ( X ) ) = e ( z ∗ W + F − E , G ) e(W,com(X))=e(z*W+F-E,G) e(W,com(X))=e(z∗W+F−E,G)
参考资料[1] Hackmd笔记 Linearisation Polynomial Example
