Almost Optimal Short Adaptive Non-Interactive Zero Knowledge学习笔记

1. 背景知识

Helger Lipmaa 2014年eprint 论文《Almost Optimal Short Adaptive Non-Interactive Zero Knowledge》：

• 提出新的Hadamard product argument。借助Gennaro等人2013年论文《Quadratic Span Programs and Succinct NIZKs without PCPs》的QAP机制，将Hadamard product argument理解为：The product argument is enssentially a polynomial quadratic arithmetic program (QAP) for the circuit that computes n n n multiplications in paralle, with additional elements to guarantee security in our setting。且在本文中的新的Hadamard product argument，Prover对应的计算有：3个polynomial interpolation（over Z p \mathbb{Z}_p Zp​），1个polynomial multiplication（over Z p \mathbb{Z}_p Zp​）、1个polynomial division（over Z p \mathbb{Z}_p Zp​）和2个 n − n- n−wide multi-exponentiations。Prover的计算时间为 Θ ( n log ⁡ n ) \Theta(n\log n) Θ(nlogn)，assuming that p p p satisfies a mild criterion。
• 采用了新的同态trapdoor commitment scheme——interpolating commitment scheme。【其实就是将2.1节中的 x x x替换为多项式 P i ( σ ) P_i(\sigma ) Pi​(σ)来构建CRS。Groth 2010年论文《Short Pairing-based Non-interactive Zero-Knowledge Arguments》中的CRS特例化为： P 0 ( X ) = Z ( X ) = 1 , P i ( X ) = X i P_0(X)=Z(X)=1,P_i(X)=X^i P0​(X)=Z(X)=1,Pi​(X)=Xi。】
• 新的shift argument。
• 新的restriction argument。
• 新的range argument。The new range argument can be seen as a short program in the scan vector parallel computation model [Ble90] that operates on committed vectors of length n n n。（可由1个restriction argument，1个shift argument，2个product argument组成。）

2. trapdoor commitment scheme 2.1 何为trapdoor commitment scheme？

trapdoor commitment scheme主要针对的是CRS场景，如上图中的 x x x为trapdoor key，该key值应对Prover和Verifier均不可知（传说中的有毒垃圾？），否则，如对向量 0 ⃗ \vec{0} 0 的knowledge commitment ( c , c ^ ) , c = g t , c ^ = g ^ t (c,\hat{c}),c=g^t,\hat{c}=\hat{g}^t (c,c^),c=gt,c^=g^​t，若Prover若知道x值，可将 c c copen为任意的消息 a 1 , ⋯   , a n ; r = t − ∑ i = 1 n a i x i a_1,\cdots,a_n;r=t-\sum_{i=1}^{n}a_ix^i a1​,⋯,an​;r=t−∑i=1n​ai​xi，使得Verifier验证 c = g r ∏ i = 1 n g i a i c=g^r\prod_{i=1}^{n}g_i^{a_i} c=gr∏i=1n​giai​​、 c ^ = g ^ r ∏ i = 1 n g i ^ a i \hat{c}=\hat{g}^r\prod_{i=1}^{n}\hat{g_i}^{a_i} c^=g^​r∏i=1n​gi​^​ai​以及 e ( g , c ^ ) = e ( g ^ , c ) e(g,\hat{c})=e(\hat{g},c) e(g,c^)=e(g^​,c)均成立，从而破坏了commitment的binding属性要求。

2.2 pairing-based polynomial (trapdoor) commitment scheme

其实就是将2.1节中的 x x x替换为多项式 P i ( σ ) P_i(\sigma ) Pi​(σ)来构建CRS。Groth 2010年论文《Short Pairing-based Non-interactive Zero-Knowledge Arguments》中的CRS特例化为： P 0 ( X ) = Z ( X ) = 1 , P i ( X ) = X i P_0(X)=Z(X)=1,P_i(X)=X^i P0​(X)=Z(X)=1,Pi​(X)=Xi。

2.2.1 { P i } \{P_i\} {Pi​}-Commitment Scheme

相应的trapdoor key为 ( σ , α ) (\sigma,\alpha) (σ,α)，其security依赖于 q − q- q−type假设：

2.2.2 Interpolating Commitment Scheme

Interpolating Commitment Scheme的核心思想为：将要commit的向量 a ⃗ = ( a 1 , ⋯   , a n ) \vec{a}=(a_1,\cdots,a_n) a =(a1​,⋯,an​)以 n − 1 n-1 n−1阶多项式系数表示 L a ( X ) = a 1 + a 2 X + ⋯ + a n X n − 1 L_a(X)=a_1+a_2X+\cdots+a_nX^{n-1} La​(X)=a1​+a2​X+⋯+an​Xn−1，该多项式再用 w i w_i wi​【其中 Z ( X ) = X n − 1 ， Z ( w i ) = 0 ， w i = w i − 1 Z(X)=X^n-1，Z(w_i)=0，w_i=w^{i-1} Z(X)=Xn−1，Z(wi​)=0，wi​=wi−1，其中 w w w为n-th of root】进行Lagrange插值，对应的 n − 1 n-1 n−1阶Lagrange basis polynomial为： l i ( X ) = ∏ j ≠ i X − w j w i − w j ， 相 应 地 有 ： l i ( w i ) = 1   a n d   l i ( w j ) = 0   f o r   j ≠ i l_i(X)=\prod_{j\neq i}^{}\frac{X-w_j}{w_i-w_j}，相应地有：l_i(w_i)=1\ and\ l_i(w_j)=0\ for\ j\neq i li​(X)=∏j​=i​wi​−wj​X−wj​​，相应地有：li​(wi​)=1 and li​(wj​)=0 for j​=i。 对应地： L a ( X ) = ∑ i = 1 n a i l i ( X ) L_a(X)=\sum_{i=1}^{n}a_il_i(X) La​(X)=∑i=1n​ai​li​(X) is the interpolating (Lagrange) polynomial of a ⃗ \vec{a} a at points w i w_i wi​， L a ( w i ) = a i L_a(w_i)=a_i La​(wi​)=ai​。

3. 零知识 Zero Knowledge

4. Hadamard Product Argument

单位矩阵 I n = ( 1 0 ⋯ 0 0 1 ⋯ 0 ⋱ ⋱ ⋱ 0 0 0 ⋯ 1 ) = ( e ⃗ 1 e ⃗ 2 ⋯ e ⃗ n ) I_n=\begin{pmatrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & 0\\ \ddots & \ddots & \ddots & 0\\ 0 & 0 & \cdots & 1 \end{pmatrix}=\begin{pmatrix} \vec{e}_1 \\ \vec{e}_2 \\ \cdots \\ \vec{e}_n \end{pmatrix} In​=⎝⎜⎜⎛​10⋱0​01⋱0​⋯⋯⋱⋯​0001​⎠⎟⎟⎞​=⎝⎜⎜⎛​e 1​e 2​⋯e n​​⎠⎟⎟⎞​ 全1向量为 1 ⃗ n = ( 1 , ⋯   , 1 ) \vec{1}_n=(1,\cdots,1) 1 n​=(1,⋯,1)

需证明： a ⃗ ∘ b ⃗ = ( a 1 b 1 , ⋯   , a n b n ) = c ⃗ = ( c 1 , ⋯   , c n ) \vec{a}\circ \vec{b}=(a_1b_1,\cdots,a_nb_n)=\vec{c}=(c_1,\cdots,c_n) a ∘b =(a1​b1​,⋯,an​bn​)=c =(c1​,⋯,cn​) 当且仅当： ( a ⃗ T I n ) ∘ ( b ⃗ T I n ) = ( c ⃗ T I n ) ∘ ( 1 ⃗ n T I n ) (\vec{a}^TI_n)\circ(\vec{b}^TI_n)=(\vec{c}^TI_n)\circ(\vec{1}_n^TI_n) (a TIn​)∘(b TIn​)=(c TIn​)∘(1 nT​In​) ⇒ \Rightarrow ⇒ ( ∑ a i e ⃗ i ) ∘ ( ∑ b i e ⃗ i ) = ( ∑ c i e ⃗ i ) ∘ ( ∑ e ⃗ i ) (\sum a_i\vec{e}_i)\circ(\sum b_i\vec{e}_i)=(\sum c_i\vec{e}_i)\circ(\sum \vec{e}_i) (∑ai​e i​)∘(∑bi​e i​)=(∑ci​e i​)∘(∑e i​)

上述公式可理解为：有一个arithmetic circuit C C C，具有 n n n个parallel multiplication gates, that on given inputs a ⃗ \vec{a} a and b ⃗ \vec{b} b returns c ⃗ \vec{c} c as the output。

构建多项式： Q a ⃗ , b ⃗ , c ⃗ ( X ) = L a ( X ) L b ( X ) − L c ( X ) L 1 n ( X ) Q^{\vec{a},\vec{b},\vec{c}}(X)=L_a(X)L_b(X)-L_c(X)L_{1_n}(X) Qa ,b ,c (X)=La​(X)Lb​(X)−Lc​(X)L1n​​(X) 借助2.2.2节的Interpolating Commitment Scheme概念，取 n n n个不同值 w 1 , ⋯   , w n w_1,\cdots,w_n w1​,⋯,wn​，满足 Z ( X ) = X n − 1 ， Z ( w i ) = 0 Z(X)=X^n-1，Z(w_i)=0 Z(X)=Xn−1，Z(wi​)=0。同时 L a ( X ) = ∑ i = 1 n a i l i ( X ) ， L b ( X ) = ∑ i = 1 n b i l i ( X ) ， L c ( X ) = ∑ i = 1 n c i l i ( X ) ， L 1 n ( X ) = ∑ i = 1 n l i ( X ) L_a(X)=\sum_{i=1}^{n}a_il_i(X)，L_b(X)=\sum_{i=1}^{n}b_il_i(X)，L_c(X)=\sum_{i=1}^{n}c_il_i(X)，L_{1_n}(X)=\sum_{i=1}^{n}l_i(X) La​(X)=∑i=1n​ai​li​(X)，Lb​(X)=∑i=1n​bi​li​(X)，Lc​(X)=∑i=1n​ci​li​(X)，L1n​​(X)=∑i=1n​li​(X)【 n − 1 n-1 n−1阶Lagrange basis polynomial l i ( X ) = ∏ j ≠ i X − w j w i − w j ， 相 应 地 有 ： l i ( w i ) = 1   a n d   l i ( w j ) = 0   f o r   j ≠ i l_i(X)=\prod_{j\neq i}^{}\frac{X-w_j}{w_i-w_j}，相应地有：l_i(w_i)=1\ and\ l_i(w_j)=0\ for\ j\neq i li​(X)=∏j​=i​wi​−wj​X−wj​​，相应地有：li​(wi​)=1 and li​(wj​)=0 for j​=i。】，从而有 Q a ⃗ , b ⃗ , c ⃗ ( X ) Q^{\vec{a},\vec{b},\vec{c}}(X) Qa ,b ,c (X)为 ( n − 1 ) + ( n − 1 ) = 2 n − 2 (n-1)+(n-1)=2n-2 (n−1)+(n−1)=2n−2阶。 若 a i b i = c i a_ib_i=c_i ai​bi​=ci​成立，则有： Q a ⃗ , b ⃗ , c ⃗ ( w i ) = a i b i − c i = 0 Q^{\vec{a},\vec{b},\vec{c}}(w_i)=a_ib_i-c_i=0 Qa ,b ,c (wi​)=ai​bi​−ci​=0，即 Q a ⃗ , b ⃗ , c ⃗ ( X ) Q^{\vec{a},\vec{b},\vec{c}}(X) Qa ,b ,c (X)在 n n n个不同的 ( w 1 , ⋯   , w n ) (w_1,\cdots,w_n) (w1​,⋯,wn​)均evaluate为0。 而 n n n阶多项式 Z ( X ) Z(X) Z(X)亦在 n n n个不同的 ( w 1 , ⋯   , w n ) (w_1,\cdots,w_n) (w1​,⋯,wn​)均evaluate为0。

因此： 存在 ( 2 n − 2 ) − n = n − 2 (2n-2)-n=n-2 (2n−2)−n=n−2 阶多项式 π ( X ) \pi(X) π(X)，使得： π ( X ) ⋅ Z ( X ) = Q a ⃗ , b ⃗ , c ⃗ ( X ) \pi(X)\cdot Z(X)=Q^{\vec{a},\vec{b},\vec{c}}(X) π(X)⋅Z(X)=Qa ,b ,c (X)成立。

Witness： a ⃗ , b ⃗ , c ⃗ \vec{a},\vec{b},\vec{c} a ,b ,c 1）即证明Prover知道相应的 a ⃗ , b ⃗ , c ⃗ \vec{a},\vec{b},\vec{c} a ,b ,c 满足 a ⃗ ∘ b ⃗ = c ⃗ \vec{a}\circ\vec{b}=\vec{c} a ∘b =c

2）改为证明Prover知道相应的 n − 2 n-2 n−2 阶多项式 π ( X ) \pi(X) π(X)，满足 π ( X ) ⋅ Z ( X ) = Q a ⃗ , b ⃗ , c ⃗ ( X ) \pi(X)\cdot Z(X)=Q^{\vec{a},\vec{b},\vec{c}}(X) π(X)⋅Z(X)=Qa ,b ,c (X)

3）为了保证zero knowledge，引入随机变量 r a , r b , r c ← r Z p r_a,r_b,r_c\leftarrow _r \mathbb{Z}_p ra​,rb​,rc​←r​Zp​，构建具有zero knowledge的多项式： Q z k a ⃗ , b ⃗ , c ⃗ ( X ) = ( L a ( X ) + r a Z ( X ) ) ( L b ( X ) + r b Z ( X ) ) − ( L c ( X ) + r c Z ( X ) ) L 1 n ( X ) Q^{\vec{a},\vec{b},\vec{c}}_{zk}(X)=(L_a(X)+r_aZ(X))(L_b(X)+r_bZ(X))-(L_c(X)+r_cZ(X))L_{1_n}(X) Qzka ,b ,c ​(X)=(La​(X)+ra​Z(X))(Lb​(X)+rb​Z(X))−(Lc​(X)+rc​Z(X))L1n​​(X) 证明Prover知道相应的 n − 2 n-2 n−2 阶多项式 π z k ( X ) \pi_{zk}(X) πzk​(X)，满足 π z k ( X ) ⋅ Z ( X ) = Q z k a ⃗ , b ⃗ , c ⃗ ( X ) \pi_{zk}(X)\cdot Z(X)=Q^{\vec{a},\vec{b},\vec{c}}_{zk}(X) πzk​(X)⋅Z(X)=Qzka ,b ,c ​(X)。

n − 2 n-2 n−2 阶多项式 π z k ( X ) = Q z k a ⃗ , b ⃗ , c ⃗ ( X ) / Z ( X ) = ∑ i = 0 n − 2 π i X i \pi_{zk}(X)=Q^{\vec{a},\vec{b},\vec{c}}_{zk}(X)/Z(X)=\sum_{i=0}^{n-2}\pi_iX^i πzk​(X)=Qzka ,b ,c ​(X)/Z(X)=∑i=0n−2​πi​Xi 并不会reveal any information about the witness。

4）由于 π z k ( X ) \pi_{zk}(X) πzk​(X) is not of sublinear length in n n n，Prover改为传输 the evaluation of π z k ( X ) \pi_{zk}(X) πzk​(X) at a random secret point σ \sigma σ，同时借助2.2.2节的interpolating commitment scheme对应有： c o m 1 ( c k 1 ; a ⃗ ; r a ) = g 1 r a Z ( σ ) + ∑ i = 1 n a i P i ( σ ) = g 1 r a Z ( σ ) + L a ( σ ) com_1(ck_1;\vec{a};r_a)=g_1^{r_aZ(\sigma)+\sum_{i=1}^{n}a_iP_i(\sigma)}=g_1^{r_aZ(\sigma)+L_a(\sigma)} com1​(ck1​;a ;ra​)=g1ra​Z(σ)+∑i=1n​ai​Pi​(σ)​=g1ra​Z(σ)+La​(σ)​ 从而有： e ( g 1 π z k ( σ ) , g 2 Z ( σ ) ) = e ( g 2 , g 1 Q z k a ⃗ , b ⃗ , c ⃗ ( σ ) ) = e ( c o m 1 ( c k 1 ; a ⃗ ; r a ) , c o m 1 ( c k 2 ; b ⃗ ; r b ) ) / e ( c o m 1 ( c k 1 ; c ⃗ ; r c ) , c o m 1 ( c k 2 ; 1 ⃗ ; 0 ) ) e(g_1^{\pi_{zk}(\sigma),g_2^{Z(\sigma)}})=e(g_2,g_1^{Q^{\vec{a},\vec{b},\vec{c}}_{zk}(\sigma)})=e(com_1(ck_1;\vec{a};r_a),com_1(ck_2;\vec{b};r_b))/e(com_1(ck_1;\vec{c};r_c),com_1(ck_2;\vec{1};0)) e(g1πzk​(σ),g2Z(σ)​​)=e(g2​,g1Qzka ,b ,c ​(σ)​)=e(com1​(ck1​;a ;ra​),com1​(ck2​;b ;rb​))/e(com1​(ck1​;c ;rc​),com1​(ck2​;1 ;0)) 成立。

由于Prover 亦未知 random secret point σ \sigma σ，Prover需证明其知道 n − 2 n-2 n−2 阶多项式 π z k ( X ) \pi_{zk}(X) πzk​(X) 的系数 π 0 , π 1 , ⋯   , π n − 2 \pi_0,\pi_1,\cdots,\pi_{n-2} π0​,π1​,⋯,πn−2​。同时需在CRS中包含相应的 ( g 1 σ , g 1 σ 2 , ⋯   , g 1 σ n − 2 ) (g_1^{\sigma},g_1^{\sigma^2},\cdots,g_1^{\sigma^{n-2}}) (g1σ​,g1σ2​,⋯,g1σn−2​)。同时，为了实现knowledge commitment of π 0 , π 1 , ⋯   , π n − 2 \pi_0,\pi_1,\cdots,\pi_{n-2} π0​,π1​,⋯,πn−2​，引入secret key β \beta β，构建CRS ( g 1 β σ , g 1 β σ 2 , ⋯   , g 1 β σ n − 2 ) (g_1^{\beta\sigma},g_1^{\beta\sigma^2},\cdots,g_1^{\beta\sigma^{n-2}}) (g1βσ​,g1βσ2​,⋯,g1βσn−2​)。 Prover计算： ( π , π β ) = ( g 1 , g 1 β ) ← ∏ i = 0 n − 2 ( g 1 σ i , g 1 β σ i ) π i (\pi,\pi^{\beta})=(g_1,g_1^{\beta})\leftarrow\prod_{i=0}^{n-2}(g_1^{\sigma^{i}},g_1^{\beta\sigma^{i}})^{\pi_i} (π,πβ)=(g1​,g1β​)←∏i=0n−2​(g1σi​,g1βσi​)πi​。其中 π \pi π即为 g 1 π z k ( σ ) = g 1 ∑ i = 0 n − 2 π i σ i = ∏ i = 0 n − 2 g 1 σ i g_1^{\pi_{zk}(\sigma)}=g_1^{\sum_{i=0}^{n-2}\pi_i\sigma^i}=\prod_{i=0}^{n-2}g_1^{\sigma^{i}} g1πzk​(σ)​=g1∑i=0n−2​πi​σi​=∏i=0n−2​g1σi​。

详细的Hadamard Product Argument证明思路如下图所示：

Prover和Verifier相应的计算量为：

5. right-shift-by- ξ \xi ξ argument

6. Restriction Argument

7. Range Argument