Inner Product点积的零知识证明

1 引言

Inner product具有如下特征： 例子一：Prover声称其有某公钥 P X P_X PX​的私钥 x x x， P X = x G P_X=xG PX​=xG。典型的Schnoor’s身份协议。 Prover以零知识证明方式来证明他知道 x x x，证明过程如下： a) P → V : R P \rightarrow V:R P→V:R (P选择随机数k，该值对V保密， R = k G R=kG R=kG。R为a new random curve point。) b) V → P : e V \rightarrow P: e V→P:e (a random scalar，也可称为challenge值。) c) P → V : s P \rightarrow V: s P→V:s， 其中 s = k + e x s=k+ex s=k+ex。

对于Verifier，只需验证： s G = ? R + e P X sG=?R+eP_X sG=?R+ePX​

例子二： a) P → V : C 0 P \rightarrow V: C_0 P→V:C0​ (a new commitment to a newly chosen random vector of dimension N) b) V → P : e V \rightarrow P: e V→P:e (a random scalar，也可称为challenge值。) c) P → V : ( z ⃗ , s ) P \rightarrow V: (\vec z, s) P→V:(z ,s) (a single vector of dimension N, and another scalar) 其中： z ⃗ = ∑ i = 0 m e i x ⃗ i , s = ∑ i = 0 m e i r i \vec z=\sum_{i=0}^{m}e^i\vec x_i, \quad s=\sum_{i=0}^{m}e^ir_i z =∑i=0m​eix i​,s=∑i=0m​eiri​** 对于Verifier，只需验证： ∑ i = 0 m e i C i = ? s H + z ⃗ G ⃗ \sum_{i=0}^{m}e^iC_i=?sH+\vec z\vec G ∑i=0m​eiCi​=?sH+z G

根据以上两个例子，都满足Sigma protocol。整个流程可抽象为： a) P → V : c o m m i t m e n t P \rightarrow V: commitment P→V:commitment b) V → P : c h a l l e n g e V \rightarrow P: challenge V→P:challenge c) P → V : r e s p o n s e ( p r o o f ) P \rightarrow V: response(proof) P→V:response(proof)

2. Inner Product的零知识证明

Inner Product点积表示为： < x ⃗ , y ⃗ > = ∑ i = 1 n x i y i <\vec x, \vec y>=\sum_{i=1}^{n}x_iy_i =∑i=1n​xi​yi​。 如需零知识证明 z = < x ⃗ , y ⃗ > z=<\vec x, \vec y> z=，则在a)b)c)步骤前，以下三个commitment C x , C y , C z C_x, C_y,C_z Cx​,Cy​,Cz​为已知： C z = t H + z G C_z=tH+zG Cz​=tH+zG C x = r H + x ⃗ G ⃗ = r H + ( x 1 G 1 + x 2 G 2 + . . . + x n G n ) C_x=rH+\vec x\vec G=rH+(x_1G_1+x_2G_2+...+x_nG_n) Cx​=rH+x G =rH+(x1​G1​+x2​G2​+...+xn​Gn​) C y = s H + y ⃗ G ⃗ = s H + ( y 1 G 1 + y 2 G 2 + . . . + y n G n ) C_y=sH+\vec y\vec G=sH+(y_1G_1+y_2G_2+...+y_nG_n) Cy​=sH+y ​G =sH+(y1​G1​+y2​G2​+...+yn​Gn​)

以下将类比例子一来构建相应的a)b)c)step。

2.1 a)step P → V : c o m m i t m e n t P \rightarrow V: commitment P→V:commitment

在本阶段，分别为 x ⃗ , y ⃗ \vec x, \vec y x ,y ​选择相应的随机向量 d ⃗ x , d ⃗ y \vec d_x, \vec d_y d x​,d y​和随机值 r d , s d r_d,s_d rd​,sd​，计算： A d = r d H + d ⃗ x G ⃗ A_d=r_dH+\vec d_x\vec G Ad​=rd​H+d x​G B d = s d H + d ⃗ y G ⃗ B_d=s_dH+\vec d_y\vec G Bd​=sd​H+d y​G

同时参考例子中c)步骤中计算 e x + k ex+k ex+k的方式来构建 < e x ⃗ + d ⃗ x , e y ⃗ + d ⃗ y > = < x ⃗ , y ⃗ > e 2 + ( < x ⃗ , d ⃗ y > + < d ⃗ x , y ⃗ > ) e + < d ⃗ x , d ⃗ y > <e\vec x+\vec d_x,e\vec y+\vec d_y>=<\vec x,\vec y>e^2+(<\vec x,\vec d_y>+<\vec d_x,\vec y>)e+<\vec d_x, \vec d_y> =e2+(+)e+，对该多项式的三个系数提供相应的commitment，其中 < x ⃗ , y ⃗ > <\vec x,\vec y> 的commitment即为 C z C_z Cz​。另外两个系数的commitment为：【注意此处的三个系数均为scalars，而不是vectors。所以用的是G而不是 G ⃗ \vec G G 】 C 1 = t 1 H + ( < x ⃗ , d ⃗ y > + < d ⃗ x , y ⃗ > ) G C_1=t_1H+(<\vec x,\vec d_y>+<\vec d_x,\vec y>)G C1​=t1​H+(+)G C 0 = t 0 H + ( < d ⃗ x , d ⃗ y > ) G C_0=t_0H+(<\vec d_x, \vec d_y>)G C0​=t0​H+()G

综上，在a)commitment 阶段： a) P → V : ( r d , s d , t 1 , t 0 ) P \rightarrow V:(r_d,s_d,t_1,t_0) P→V:(rd​,sd​,t1​,t0​) (为4个salar随机数，对V保密)， ( d ⃗ x , d ⃗ y ) (\vec d_x, \vec d_y) (d x​,d y​) (为2个随机数向量，对V保密)，以及4个Pedersen commitments ( A d , B d , C 1 , C 0 ) (A_d,B_d,C_1,C_0) (Ad​,Bd​,C1​,C0​)（对V公开）。

2.2 b)step V → P : c h a l l e n g e V \rightarrow P: challenge V→P:challenge

V → P : e V \rightarrow P: e V→P:e (单个的scalar随机数)

2.3 c)step P → V : r e s p o n s e ( p r o o f ) P \rightarrow V: response(proof) P→V:response(proof)

在本阶段，Prover需提供如下值： f ⃗ x = e x ⃗ + d ⃗ x \vec f_x =e\vec x+\vec d_x f ​x​=ex +d x​ f ⃗ y = e y ⃗ + d ⃗ y \vec f_y =e\vec y+\vec d_y f ​y​=ey ​+d y​ r x = e r + r d r_x=er+r_d rx​=er+rd​ s y = e s + s d s_y=es+s_d sy​=es+sd​ t z = e 2 t + e t 1 + t 0 t_z=e^2t+et_1+t_0 tz​=e2t+et1​+t0​

对于Verifier来说，仅需做如下三个验证：

1. e C x + A d = ? r x H + f ⃗ x G ⃗ eC_x+A_d=?r_xH+\vec f_x\vec G eCx​+Ad​=?rx​H+f ​x​G
2. e C y + B d = ? s y H + f ⃗ y G ⃗ eC_y+B_d=?s_yH+\vec f_y\vec G eCy​+Bd​=?sy​H+f ​y​G
3. t z H + ( < f ⃗ x , f ⃗ y > ) G = ? e 2 C z + e C 1 + C 0 t_zH+(<\vec f_x,\vec f_y>)G=?e^2C_z+eC_1+C_0 tz​H+()G=?e2Cz​+eC1​+C0​

证明过程如下：

1. e C x + A d = e ( r H + x ⃗ G ⃗ ) + ( r d H + d ⃗ x G ⃗ ) = ( e r + r d ) H + ( e x ⃗ + d ⃗ x ) G ⃗ = r x H + f ⃗ x G ⃗ eC_x+A_d=e(rH+\vec x\vec G)+(r_dH+\vec d_x\vec G)=(er+r_d)H+(e\vec x+\vec d_x)\vec G=r_xH+\vec f_x\vec G eCx​+Ad​=e(rH+x G )+(rd​H+d x​G )=(er+rd​)H+(ex +d x​)G =rx​H+f ​x​G
2. 同理有 e C y + B d = s y H + f ⃗ y G ⃗ eC_y+B_d=s_yH+\vec f_y\vec G eCy​+Bd​=sy​H+f ​y​G
3. t z H + ( < f ⃗ x , f ⃗ y > ) G = ( e 2 t + e t 1 + t 0 ) H + ( < e x ⃗ + d ⃗ x , e y ⃗ + d ⃗ y > ) G = e 2 C z + e C 1 + C 0 t_zH+(<\vec f_x,\vec f_y>)G=(e^2t+et_1+t_0)H+(<e\vec x+\vec d_x,e\vec y+\vec d_y>)G=e^2C_z+eC_1+C_0 tz​H+()G=(e2t+et1​+t0​)H+()G=e2Cz​+eC1​+C0​

由此完成整个Inner Product的零知识证明。 完整的proof信息为 ( ( A d , B d , C 1 , C 0 ) , e , ( f ⃗ x , f ⃗ y , r x , s y , t z ) ) ((A_d,B_d,C_1,C_0),e,(\vec f_x, \vec f_y, r_x,s_y,t_z)) ((Ad​,Bd​,C1​,C0​),e,(f ​x​,f ​y​,rx​,sy​,tz​))

同样地，对于不honest的prover，他仍然可以伪造proof信息，使得以上的三个验证均能通过，如： ( ( A d = ( x x H + f ⃗ x G ⃗ ) − e C x , B d = ( s y H + f ⃗ y G ⃗ ) − e C y , C 1 = t 1 H + 0 G , C 0 = t z H + ( < f ⃗ x , f ⃗ y > ) G − e C 1 − e 2 C z ) , e , ( f ⃗ x , f ⃗ y , r x , s y , t z ) ) ((A_d=(x_xH+\vec f_x\vec G)-eC_x,B_d=(s_yH+\vec f_y\vec G)-eC_y,C_1=t_1H+0G,C_0=t_zH+(<\vec f_x,\vec f_y>)G-eC_1-e^2C_z),e,(\vec f_x, \vec f_y, r_x,s_y,t_z)) ((Ad​=(xx​H+f ​x​G )−eCx​,Bd​=(sy​H+f ​y​G )−eCy​,C1​=t1​H+0G,C0​=tz​H+()G−eC1​−e2Cz​),e,(f ​x​,f ​y​,rx​,sy​,tz​))。

3. 更紧凑的Inner Product零知识证明

完整的proof信息为 ( ( A d , B d , C 1 , C 0 ) , e , ( f ⃗ x , f ⃗ y , r x , s y , t z ) ) ((A_d,B_d,C_1,C_0),e,(\vec f_x, \vec f_y, r_x,s_y,t_z)) ((Ad​,Bd​,C1​,C0​),e,(f ​x​,f ​y​,rx​,sy​,tz​))，如何进一步减小proof呢？ 答案是：使用递归！！！

使用递归可减少proof的大小，同时若基于Fiat Shamir heuristic可切换为非交互式零知识证明，可生成更紧凑的proof。

参考资料： [1] https://joinmarket.me/static/FromZK2BPs_v1.pdf