1. 引言

需证明：
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 Verifier

Verifier计算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)h1​h2​−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 Verifier

Verifier计算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