Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》中提出了shuffle argument算法，该算法主要由Multi-exponentiation Argument和product argument两部分组成。 在博客 Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1）中介绍了Shuffle argument总体算法以及Multi-exponentiation Argument算法，在本博客中，将重点介绍product argument算法。
1. 背景知识Witness 向量 A = { a i j } i , j = 1 n , m A=\{a_{ij}\}_{i,j=1}^{n,m} A={aij}i,j=1n,m，以矩阵方式表示： A = ( a 11 a 12 ⋯ a 1 m a 21 a 22 ⋯ a 2 m ⋯ ⋯ ⋯ ⋯ a n 1 a n 2 ⋯ a n m ) = ( a ⃗ 1 , a ⃗ 2 , ⋯ , a ⃗ m ) A=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1m} \\ a_{21} & a_{22} & \cdots & a_{2m} \\ \cdots & \cdots & \cdots & \cdots \\ a_{n1} & a_{n2} & \cdots & a_{nm} \end{pmatrix}=(\vec{a}_1,\vec{a}_2,\cdots,\vec{a}_m) A=⎝⎜⎜⎛a11a21⋯an1a12a22⋯an2⋯⋯⋯⋯a1ma2m⋯anm⎠⎟⎟⎞=(a 1,a 2,⋯,a m)
Public info for both Prover AND Verifier，对 A A A的每列向量 a i ⃗ \vec{a_i} ai 分别进行commit： c ⃗ A = c o m c k ( A ; r ⃗ ) = ( c o m c k ( a ⃗ 1 ; r 1 ) , ⋯ , c o m c k ( a ⃗ m ; r m ) ) \vec{c}_A=com_{ck}(A;\vec{r})=(com_{ck}(\vec{a}_1;r_1),\cdots,com_{ck}(\vec{a}_m;r_m)) c A=comck(A;r )=(comck(a 1;r1),⋯,comck(a m;rm)) 需证明 b = ∏ i = 1 n ∏ j = 1 m a i j = ∏ i = 1 n ( ∏ j = 1 m a i j ) b=\prod_{i=1}^{n}\prod_{j=1}^{m}a_{ij}=\prod_{i=1}^{n}(\prod_{j=1}^{m}a_{ij}) b=∏i=1n∏j=1maij=∏i=1n(∏j=1maij)。
思路如下： 构建新的向量 b ⃗ = ( ∏ j = 1 m a 1 j , ⋯ , ∏ j = 1 m a n j ) = ( b 1 , ⋯ , b n ) \vec{b}=(\prod_{j=1}^{m}a_{1j},\cdots,\prod_{j=1}^{m}a_{nj})=(b_1,\cdots,b_n) b =(∏j=1ma1j,⋯,∏j=1manj)=(b1,⋯,bn)，对该向量进行commit： c b = c o m c k ( b 1 , ⋯ , b n ; s ) c_b=com_{ck}(b_1,\cdots,b_n;s) cb=comck(b1,⋯,bn;s)。从而将证明 b = ∏ i = 1 n ∏ j = 1 m a i j = ∏ i = 1 n ( ∏ j = 1 m a i j ) b=\prod_{i=1}^{n}\prod_{j=1}^{m}a_{ij}=\prod_{i=1}^{n}(\prod_{j=1}^{m}a_{ij}) b=∏i=1n∏j=1maij=∏i=1n(∏j=1maij)拆分为了两组证明： 1）证明Prover知道相应的witness a 11 , ⋯ , a n m a_{11},\cdots,a_{nm} a11,⋯,anm，使得 c b = c o m c k ( b 1 , ⋯ , b n ; s ) = c o m c k ( ∏ j = 1 m a 1 j , ⋯ , ∏ j = 1 m a n j ; s ) c_b=com_{ck}(b_1,\cdots,b_n;s)=com_{ck}(\prod_{j=1}^{m}a_{1j},\cdots,\prod_{j=1}^{m}a_{nj};s) cb=comck(b1,⋯,bn;s)=comck(∏j=1ma1j,⋯,∏j=1manj;s)成立。【使用后续要介绍的Hadamard product argument及zero argument实现】 2）当 c b = c o m c k ( b 1 , ⋯ , b n ; s ) c_b=com_{ck}(b_1,\cdots,b_n;s) cb=comck(b1,⋯,bn;s)，证明 b = ∏ i = 1 n b i b=\prod_{i=1}^{n}b_i b=∏i=1nbi成立。【使用后续要介绍的Single value product argument实现】
2. Hadamard product argument证明Prover知道相应的witness a 11 , ⋯ , a n m a_{11},\cdots,a_{nm} a11,⋯,anm，使得 c b = c o m c k ( b 1 , ⋯ , b n ; s ) = c o m c k ( ∏ j = 1 m a 1 j , ⋯ , ∏ j = 1 m a n j ; s ) c_b=com_{ck}(b_1,\cdots,b_n;s)=com_{ck}(\prod_{j=1}^{m}a_{1j},\cdots,\prod_{j=1}^{m}a_{nj};s) cb=comck(b1,⋯,bn;s)=comck(∏j=1ma1j,⋯,∏j=1manj;s)成立。 可进一步转换为： （1）Witness： a 11 , ⋯ , a n m a_{11},\cdots,a_{nm} a11,⋯,anm以及 b 1 , ⋯ , b n b_1,\cdots,b_n b1,⋯,bn。
（2）Public info for both Prover AND Verifier：
- 对 A A A的每列向量 a i ⃗ \vec{a_i} ai 分别进行commit： c ⃗ A = c o m c k ( A ; r ⃗ ) = ( c o m c k ( a ⃗ 1 ; r 1 ) , ⋯ , c o m c k ( a ⃗ m ; r m ) ) \vec{c}_A=com_{ck}(A;\vec{r})=(com_{ck}(\vec{a}_1;r_1),\cdots,com_{ck}(\vec{a}_m;r_m)) c A=comck(A;r )=(comck(a 1;r1),⋯,comck(a m;rm))
- c b = c o m c k ( b ⃗ ; s ) = c o m c k ( b 1 , ⋯ , b n ; s ) c_b=com_{ck}(\vec{b};s)=com_{ck}(b_1,\cdots,b_n;s) cb=comck(b ;s)=comck(b1,⋯,bn;s)
（3）待证明： b i = ∏ j = 1 m a i j b_i=\prod_{j=1}^{m}a_{ij} bi=∏j=1maij或 b ⃗ = ( b 1 , ⋯ , b n ) = ∏ i = 1 m a ⃗ i \vec{b}=(b_1,\cdots,b_n)=\prod_{i=1}^{m}\vec{a}_i b =(b1,⋯,bn)=∏i=1ma i，其中 ∏ i = 1 m \prod_{i=1}^{m} ∏i=1m代表的即为entry-wise multiplication，即对应为Hadamard product证明。
思路如下：
-
Prover构建新的矩阵 B = ( b ⃗ 1 , ⋯ , b ⃗ m ) B=(\vec{b}_1,\cdots,\vec{b}_m) B=(b 1,⋯,b m)，其中 b ⃗ 1 = a ⃗ 1 , b ⃗ 2 = ∏ i = 1 2 a ⃗ i , ⋯ , b ⃗ m − 1 = ∏ i = 1 m − 1 a ⃗ i , b ⃗ m = ∏ i = 1 m a ⃗ i \vec{b}_1=\vec{a}_1,\vec{b}_2=\prod_{i=1}^{2}\vec{a}_i,\cdots,\vec{b}_{m-1}=\prod_{i=1}^{m-1}\vec{a}_i,\vec{b}_m=\prod_{i=1}^{m}\vec{a}_i b 1=a 1,b 2=∏i=12a i,⋯,b m−1=∏i=1m−1a i,b m=∏i=1ma i。 Prover对矩阵 B B B的每一列进行commit： c ⃗ B = c o m c k ( B ; s ⃗ ) = ( c o m c k ( b ⃗ 1 ; s 1 ) , ⋯ , c o m c k ( b ⃗ m ; s m ) ) = ( c B 1 , ⋯ , c B m ) \vec{c}_B=com_{ck}(B;\vec{s})=(com_{ck}(\vec{b}_1;s_1),\cdots,com_{ck}(\vec{b}_m;s_m))=(c_{B_1},\cdots,c_{B_m}) c B=comck(B;s )=(comck(b 1;s1),⋯,comck(b m;sm))=(cB1,⋯,cBm) 同时要求 c B 1 = c A 1 c_{B_1}=c_{A_1} cB1=cA1且 c b = c B m c_b=c_{B_m} cb=cBm，使得 b ⃗ 1 = a ⃗ 1 \vec{b}_1=\vec{a}_1 b 1=a 1及 b ⃗ m = b ⃗ \vec{b}_m=\vec{b} b m=b 成立。 这样Prover的证明内容就改为证明：for each i = 1 , ⋯ , m − 1 i=1,\cdots,m-1 i=1,⋯,m−1， b ⃗ i + 1 = a ⃗ i + 1 b ⃗ i \vec{b}_{i+1}=\vec{a}_{i+1}\vec{b}_i b i+1=a i+1b i成立，因为有 b ⃗ 1 = a ⃗ 1 \vec{b}_1=\vec{a}_1 b 1=a 1及 b ⃗ m = b ⃗ \vec{b}_m=\vec{b} b m=b ，从而可证明 b ⃗ = ∏ i = 1 m a ⃗ i \vec{b}=\prod_{i=1}^{m}\vec{a}_i b =∏i=1ma i成立。
-
Verifier->Prover: challenge x x x；
-
改为证明： b ⃗ i + 1 = a ⃗ i + 1 b ⃗ i ⇒ ∑ i = 1 m − 1 x i b ⃗ i + 1 = ∑ i = 1 m − 1 a ⃗ i + 1 ( x i b ⃗ i ) \vec{b}_{i+1}=\vec{a}_{i+1}\vec{b}_i\Rightarrow \sum_{i=1}^{m-1}x^i\vec{b}_{i+1}=\sum_{i=1}^{m-1}\vec{a}_{i+1}(x^i\vec{b}_i) b i+1=a i+1b i⇒∑i=1m−1xib i+1=∑i=1m−1a i+1(xib i)。 收到challenge x x x后，Prover构建新的矩阵 D ′ = ( d ⃗ 1 , d ⃗ 2 , ⋯ , d ⃗ m − 1 , d ⃗ ) = ( x b ⃗ 1 , x 2 b ⃗ 2 , ⋯ , x m − 1 b ⃗ m − 1 , ∑ i = 1 m − 1 x i b ⃗ i + 1 ) D^{'}=(\vec{d}_1,\vec{d}_2,\cdots,\vec{d}_{m-1},\vec{d})=(x\vec{b}_1,x^2\vec{b}_2,\cdots,x^{m-1}\vec{b}_{m-1},\sum_{i=1}^{m-1}x^i\vec{b}_{i+1}) D′=(d 1,d 2,⋯,d m−1,d )=(xb 1,x2b 2,⋯,xm−1b m−1,∑i=1m−1xib i+1)，其中 d ⃗ = ∑ i = 1 m − 1 x i b ⃗ i + 1 \vec{d}=\sum_{i=1}^{m-1}x^i\vec{b}_{i+1} d =∑i=1m−1xib i+1。 Prover对矩阵 D ′ D^{'} D′的每列进行commit，可根据矩阵 B B B commit的同态属性获得： for i = 1 , ⋯ , m − 1 i=1,\cdots,m-1 i=1,⋯,m−1，有 c D i = c B i x i c_{D_i}=c_{B_i}^{x^i} cDi=cBixi。 i = m i=m i=m时对应有 c D = ∏ i = 1 m − 1 c B i + 1 x i c_D=\prod_{i=1}^{m-1}c_{B_{i+1}}^{x^i} cD=∏i=1m−1cBi+1xi
-
使用如上committed值，改为证明 d ⃗ = ∑ i = 1 m − 1 x i b ⃗ i + 1 = ∑ i = 1 m − 1 a ⃗ i + 1 ( x i b ⃗ i ) = ∑ i = 1 m − 1 a ⃗ i + 1 d ⃗ i \vec{d}=\sum_{i=1}^{m-1}x^i\vec{b}_{i+1}=\sum_{i=1}^{m-1}\vec{a}_{i+1}(x^i\vec{b}_i)=\sum_{i=1}^{m-1}\vec{a}_{i+1}\vec{d}_i d =∑i=1m−1xib i+1=∑i=1m−1a i+1(xib i)=∑i=1m−1a i+1d i成立。
-
Verifier->Prover: challenge y y y；
-
改为证明： d ⃗ = ∑ i = 1 m − 1 a ⃗ i + 1 d ⃗ i ⇒ 0 = ∑ i = 1 m − 1 a ⃗ i + 1 ∗ d ⃗ i − 1 ⃗ ∗ d ⃗ \vec{d}=\sum_{i=1}^{m-1}\vec{a}_{i+1}\vec{d}_i\Rightarrow 0=\sum_{i=1}^{m-1}\vec{a}_{i+1}*\vec{d}_i-\vec{1}*\vec{d} d =∑i=1m−1a i+1d i⇒0=∑i=1m−1a i+1∗d i−1 ∗d 【此时需要使用后续将介绍的zero argument来证明】，其中 ∗ * ∗操作符代表的是bilinear map：
总的算法思路如下： 
注意：为了证明 0 = ∑ i = 1 m − 1 a ⃗ i + 1 ∗ d ⃗ i − 1 ⃗ ∗ d ⃗ = ∑ i = 1 m − 1 a ⃗ i + 1 ∗ d ⃗ i − 1 ⃗ ∗ d ⃗ m 0=\sum_{i=1}^{m-1}\vec{a}_{i+1}*\vec{d}_i-\vec{1}*\vec{d}=\sum_{i=1}^{m-1}\vec{a}_{i+1}*\vec{d}_i-\vec{1}*\vec{d}_m 0=∑i=1m−1a i+1∗d i−1 ∗d =∑i=1m−1a i+1∗d i−1 ∗d m【因为构建的矩阵 D ′ D^{'} D′中有 d ⃗ m = d ⃗ = ∑ i = 1 m − 1 x i b ⃗ i + 1 \vec{d}_m=\vec{d}=\sum_{i=1}^{m-1}x^i\vec{b}_{i+1} d m=d =∑i=1m−1xib i+1】 所以，可借助下一节zero argument的思路，按如下方式构建： 引入随机向量 d ⃗ m + 1 ← Z q n \vec{d}_{m+1}\leftarrow \mathbb{Z}_q^n d m+1←Zqn，commitment to d ⃗ m + 1 \vec{d}_{m+1} d m+1： ( a ⃗ 1 a ⃗ 2 ⋯ a ⃗ m − 1 ⃗ ) ( d 1 ⃗ d 2 ⃗ ⋮ d ⃗ m d ⃗ m + 1 ) ( a ⃗ 1 ∗ d ⃗ 1 a ⃗ 2 ∗ d ⃗ 1 ⋱ a ⃗ m ∗ d ⃗ 1 − 1 ⃗ ∗ d ⃗ 1 a ⃗ 1 ∗ d ⃗ 2 a ⃗ 2 ∗ d ⃗ 2 ⋱ a ⃗ m ∗ d ⃗ 2 − 1 ⃗ ∗ d ⃗ 2 ⋱ ⋱ ⋱ ⋱ ⋱ a ⃗ 1 ∗ d ⃗ m a ⃗ 2 ∗ d ⃗ m ⋱ a ⃗ m ∗ d ⃗ m − 1 ⃗ ∗ d ⃗ m a ⃗ 1 ∗ d ⃗ m + 1 a ⃗ 2 ∗ d ⃗ m + 1 ⋱ a ⃗ m ∗ d ⃗ m + 1 − 1 ⃗ ∗ d ⃗ m + 1 ) d 2 m d 2 m − 1 ⋮ d m + 1 d m d 0 d 1 ⋯ d m − 1 d m \begin{matrix} & \begin{pmatrix} \ \ \ \ \ \ \ \ \vec{a}_1& \ \ \ \ \ \ \ \ \ \ \ \ \vec{a}_2 & \cdots &\ \ \ \ \ \ \ \ \ \ \ \vec{a} _{m}&\ \ \ \ \ \ \ \ -\vec{1} \end{pmatrix} & \\ \begin{pmatrix} \vec{d_1}\\ \vec{d_2}\\ \vdots\\ \vec{d}_{m}\\ \vec{d}_{m+1} \end{pmatrix} & \begin{pmatrix} \vec{a}_1*{\vec{d}_1}& \vec{a}_2*{\vec{d}_1} & \ddots & \vec{a}_{m}*{\vec{d}_1} & -\vec{1}*{\vec{d}_1}\\ \vec{a}_1*{\vec{d}_2}& \vec{a}_2*{\vec{d}_2} & \ddots & \vec{a}_{m}*{\vec{d}_2} & -\vec{1}*{\vec{d}_2}\\ \ddots & \ddots & \ddots & \ddots & \ddots\\ \vec{a}_1*{\vec{d}_{m}}& \vec{a}_2*{\vec{d}_{m}} & \ddots & \vec{a}_{m}*{\vec{d}_{m}} & -\vec{1}*{\vec{d}_{m}}\\ \vec{a}_1*{\vec{d}_{m+1}}& \vec{a}_2*{\vec{d}_{m+1}} & \ddots & \vec{a}_{m}*{\vec{d}_{m+1}} & -\vec{1}*{\vec{d}_{m+1}} \end{pmatrix} & \begin{matrix} \\ d_{2m}\\ d_{2m-1}\\ \vdots\\ d_{m+1}\\ d_m \end{matrix} \\ & \begin{matrix} \ \ \ \ \ \ \ \ d_0 &\ \ \ \ \ \ \ \ \ \ \ \ d_1 & \cdots & \ \ \ \ \ \ \ \ \ \ \ d_{m-1} & \ \ \ \ \ \ \ \ d_m \end{matrix}& \end{matrix} ⎝⎜⎜⎜⎜⎜⎜⎛d1 d2 ⋮d md m+1⎠⎟⎟⎟⎟⎟⎟⎞( a 1 a 2⋯ a m −1 )⎝⎜⎜⎜⎜⎜⎛a 1∗d 1a 1∗d 2⋱a 1∗d ma 1∗d m+1a 2∗d 1a 2∗d 2⋱a 2∗d ma 2∗d m+1⋱⋱⋱⋱⋱a m∗d 1a m∗d 2⋱a m∗d ma m∗d m+1−1 ∗d 1−1 ∗d 2⋱−1 ∗d m−1 ∗d m+1⎠⎟⎟⎟⎟⎟⎞ d0 d1⋯ dm−1 dmd2md2m−1⋮dm+1dm
详细的实现参见https://github.com/3for/verifiable-shuffle中的round_7a()和round_9b()中的代码。
3. zero argument
Witness: a ⃗ 1 , b ⃗ 0 , ⋯ , a ⃗ m , b ⃗ m − 1 \vec{a}_1,\vec{b}_0,\cdots,\vec{a}_m,\vec{b}_{m-1} a 1,b 0,⋯,a m,b m−1。 Public info: commitment to a ⃗ 1 , b ⃗ 0 , ⋯ , a ⃗ m , b ⃗ m − 1 \vec{a}_1,\vec{b}_0,\cdots,\vec{a}_m,\vec{b}_{m-1} a 1,b 0,⋯,a m,b m−1。 证明： 0 = ∑ i = 1 m a ⃗ i ∗ b ⃗ i − 1 0=\sum_{i=1}^{m}\vec{a}_i*\vec{b}_{i-1} 0=∑i=1ma i∗b i−1
- Prover： 随机选择 a ⃗ 0 , b ⃗ m ← Z q n \vec{a}_0,\vec{b}_m\leftarrow \mathbb{Z}_q^n a 0,b m←Zqn，commitment to a ⃗ 0 \vec{a}_0 a 0和 b ⃗ m \vec{b}_m b m。
( a ⃗ 0 a ⃗ 1 ⋯ a ⃗ m − 1 a ⃗ m ) ( b 0 ⃗ b 1 ⃗ ⋮ b ⃗ m − 1 b ⃗ m ) ( a ⃗ 0 ∗ b ⃗ 0 a ⃗ 1 ∗ b ⃗ 0 ⋱ a ⃗ m − 1 ∗ b ⃗ 0 a ⃗ m ∗ b ⃗ 0 a ⃗ 0 ∗ b ⃗ 1 a ⃗ 1 ∗ b ⃗ 1 ⋱ a ⃗ m − 1 ∗ b ⃗ 1 a ⃗ m ∗ b ⃗ 1 ⋱ ⋱ ⋱ ⋱ ⋱ a ⃗ 0 ∗ b ⃗ m − 1 a ⃗ 1 ∗ b ⃗ m − 1 ⋱ a ⃗ m − 1 ∗ b ⃗ m − 1 a ⃗ m ∗ b ⃗ m − 1 a ⃗ 0 ∗ b ⃗ m a ⃗ 1 ∗ b ⃗ m ⋱ a ⃗ m − 1 ∗ b ⃗ m a ⃗ m ∗ b ⃗ m ) d 2 m d 2 m − 1 ⋮ d m + 1 d m d 0 d 1 ⋯ d m − 1 d m \begin{matrix} & \begin{pmatrix} \ \ \ \ \ \ \ \ \vec{a}_0& \ \ \ \ \ \ \ \ \ \ \ \ \vec{a}_1 & \cdots &\ \ \ \ \ \ \ \ \ \ \ \vec{a} _{m-1}&\ \ \ \ \ \ \ \ \vec{a}_m \end{pmatrix} & \\ \begin{pmatrix} \vec{b_0}\\ \vec{b_1}\\ \vdots\\ \vec{b}_{m-1}\\ \vec{b}_m \end{pmatrix} & \begin{pmatrix} \vec{a}_0*{\vec{b}_0}& \vec{a}_1*{\vec{b}_0} & \ddots & \vec{a}_{m-1}*{\vec{b}_0} & \vec{a}_m*{\vec{b}_0}\\ \vec{a}_0*{\vec{b}_1}& \vec{a}_1*{\vec{b}_1} & \ddots & \vec{a}_{m-1}*{\vec{b}_1} & \vec{a}_m*{\vec{b}_1}\\ \ddots & \ddots & \ddots & \ddots & \ddots\\ \vec{a}_0*{\vec{b}_{m-1}}& \vec{a}_1*{\vec{b}_{m-1}} & \ddots & \vec{a}_{m-1}*{\vec{b}_{m-1}} & \vec{a}_m*{\vec{b}_{m-1}}\\ \vec{a}_0*{\vec{b}_m}& \vec{a}_1*{\vec{b}_m} & \ddots & \vec{a}_{m-1}*{\vec{b}_m} & \vec{a}_m*{\vec{b}_m} \end{pmatrix} & \begin{matrix} \\ d_{2m}\\ d_{2m-1}\\ \vdots\\ d_{m+1}\\ d_m \end{matrix} \\ & \begin{matrix} \ \ \ \ \ \ \ \ d_0 &\ \ \ \ \ \ \ \ \ \ \ \ d_1 & \cdots & \ \ \ \ \ \ \ \ \ \ \ d_{m-1} & \ \ \ \ \ \ \ \ d_m \end{matrix}& \end{matrix} ⎝⎜⎜⎜⎜⎜⎜⎛b0 b1 ⋮b m−1b m⎠⎟⎟⎟⎟⎟⎟⎞( a 0 a 1⋯ a m−1 a m)⎝⎜⎜⎜⎜⎜⎛a 0∗b 0a 0∗b 1⋱a 0∗b m−1a 0∗b ma 1∗b 0a 1∗b 1⋱a 1∗b m−1a 1∗b m⋱⋱⋱⋱⋱a m−1∗b 0a m−1∗b 1⋱a m−1∗b m−1a m−1∗b ma m∗b 0a m∗b 1⋱a m∗b m−1a m∗b m⎠⎟⎟⎟⎟⎟⎞ d0 d1⋯ dm−1 dmd2md2m−1⋮dm+1dm
有：for k = 0 , ⋯ , 2 m k=0,\cdots,2m k=0,⋯,2m， d k = ∑ 0 ≤ i , j ≤ m ; j = ( m − k ) + i a ⃗ i ∗ b ⃗ j d_k=\sum_{0\leq i,j\leq m; j=(m-k)+i}{\vec{a}_i*\vec{b}_j} dk=∑0≤i,j≤m;j=(m−k)+ia i∗b j，从而转为证明 d m + 1 = ∑ i = 1 m a ⃗ i ∗ b ⃗ i − 1 = 0 d_{m+1}=\sum_{i=1}^{m}{\vec{a}_i}*\vec{b}_{i-1}=0 dm+1=∑i=1ma i∗b i−1=0。
-
Prover：commit to d k d_k dk为 c D k c_{D_k} cDk，其中 c D m + 1 = c o m c k ( 0 ; 0 ) c_{D_{m+1}}=com_{ck}(0;0) cDm+1=comck(0;0)从而让verifier可确定 d m + 1 = 0 d_{m+1}=0 dm+1=0。
-
Verifier给Prover：challenge x x x
因为： ∑ k = 0 2 m d k x k = ( ∑ i = 0 m x i a ⃗ i ) ∗ ( ∑ j = 0 m x m − j b ⃗ j ) \sum_{k=0}^{2m}d_kx^k=(\sum_{i=0}^{m}x^i\vec{a}_i)*(\sum_{j=0}^{m}x^{m-j}\vec{b}_j) ∑k=02mdkxk=(∑i=0mxia i)∗(∑j=0mxm−jb j)
-
Prover：计算 a ⃗ = ∑ i = 0 m x i a ⃗ i \vec{a}=\sum_{i=0}^{m}x^i\vec{a}_i a =∑i=0mxia i和 b ⃗ = ∑ j = 0 m x m − j b ⃗ j \vec{b}=\sum_{j=0}^{m}x^{m-j}\vec{b}_j b =∑j=0mxm−jb j，将 a ⃗ \vec{a} a 和 b ⃗ \vec{b} b 发送给Verifier。
-
Verifier：利用commitment的同态性，只需验证 ∏ k = 0 2 m c D k x k = c o m c k ( a ⃗ ∗ b ⃗ ; t ) \prod_{k=0}^{2m}c_{D_k}^{x^k}=com_{ck}(\vec{a}*\vec{b};t) ∏k=02mcDkxk=comck(a ∗b ;t)成立。由于 d m + 1 = 0 d_{m+1}=0 dm+1=0，则相应地基于 x x x的多项式其 x m + 1 x^{m+1} xm+1系数为0，则可证明 0 = ∑ i = 1 m a ⃗ i ∗ b ⃗ i − 1 0=\sum_{i=1}^{m}\vec{a}_i*\vec{b}_{i-1} 0=∑i=1ma i∗b i−1。
整个zero argument算法流程如下：
采用的是 J.Groth 2010年论文《A verifiable secret shuffle of homomorphic encryptions》中的算法实现。（结合博客A Verifiable Secret Shuffle of Homomorphic Encryptions学习笔记 中第2节“shuffle of known contents 明文shuffle证明”思路来理解。） Common input: commit key c k ck ck, b , c a b, c_a b,ca Witness: a 1 , ⋯ , a n , r a_1,\cdots,a_n,r a1,⋯,an,r 证明： c a = c o m c k ( a 1 , ⋯ , a n ; r ) c_a=com_{ck}(a_1,\cdots,a_n;r) ca=comck(a1,⋯,an;r)且 b = ∏ i = 1 n a i b=\prod_{i=1}^{n}a_i b=∏i=1nai
主要分为两层证明： 1）证明knowledge of opening a 1 , ⋯ , a n , r a_1,\cdots,a_n,r a1,⋯,an,r of c a c_a ca。借助sigma-protocol思路：
- Prove：commit to random d 1 , ⋯ , d n d_1,\cdots,d_n d1,⋯,dn， c d = c o m c k ( d 1 , ⋯ , d n ; r d ) c_d=com_{ck}(d_1,\cdots,d_n;r_d) cd=comck(d1,⋯,dn;rd)。Prover将 c d c_d cd发送给Verifier。
- Verifier：Challenge x x x。
- Prover：for i = 1 , ⋯ , n i=1,\cdots,n i=1,⋯,n，计算 a ~ i = x a i + d i \tilde{a}_i=xa_i+d_i a~i=xai+di， r ~ = x r + r d \tilde{r}=xr+r_d r~=xr+rd。Prover将 a ~ 1 , ⋯ , a ~ n , r ~ \tilde{a}_1,\cdots,\tilde{a}_n,\tilde{r} a~1,⋯,a~n,r~ 发送给Verifier。
- Verifier：验证 c a x c d = c o m c k ( a ~ 1 , ⋯ , a ~ n ; r ~ ) c_a^xc_d=com_{ck}(\tilde{a}_1,\cdots,\tilde{a}_n; \tilde{r}) caxcd=comck(a~1,⋯,a~n;r~)成立，即完成证明knowledge of opening a 1 , ⋯ , a n , r a_1,\cdots,a_n,r a1,⋯,an,r of c a c_a ca。
2）为证明 b = ∏ i = 1 n a i b=\prod_{i=1}^{n}a_i b=∏i=1nai，构建向量 b 1 = a 1 , b 2 = a 1 a 2 , ⋯ , b n = ∏ i = 1 n a i b_1=a_1,b_2=a_1a_2,\cdots,b_n=\prod_{i=1}^{n}a_i b1=a1,b2=a1a2,⋯,bn=∏i=1nai，转为在不暴露 b 1 , ⋯ , b n b_1,\cdots,b_n b1,⋯,bn和 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an的基础上，证明 b i + 1 = b i a i + 1 b_{i+1}=b_ia_{i+1} bi+1=biai+1。不暴露 b 1 , ⋯ , b n b_1,\cdots,b_n b1,⋯,bn可采用与不暴露 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an类似的方法：Prover引入随机值 δ 1 , ⋯ , δ n \delta_1,\cdots,\delta_n δ1,⋯,δn，计算 b ~ i = x b i + δ i \tilde{b}_i=xb_i+\delta_i b~i=xbi+δi，限定 δ 1 = d 1 , δ n = 0 \delta_1=d_1,\delta_n=0 δ1=d1,δn=0，从而有 b ~ 1 = a ~ 1 , b ~ n = x b \tilde{b}_1=\tilde{a}_1,\tilde{b}_n=xb b~1=a~1,b~n=xb。然后转为证明，for i = 1 , ⋯ , n − 1 i=1,\cdots,n-1 i=1,⋯,n−1 Prover知道 x b ~ i + 1 − b ~ i a ~ i + 1 x\tilde{b}_{i+1}-\tilde{b}_i\tilde{a}_{i+1} xb~i+1−b~ia~i+1的差值。由于 x b ~ i + 1 − b ~ i a ~ i + 1 = ( b i + 1 − b i a i + 1 ) x 2 + ( δ i + 1 − a i + 1 δ i − b i d i + 1 ) x − δ i d i + 1 x\tilde{b}_{i+1}-\tilde{b}_i\tilde{a}_{i+1}=(b_{i+1}-b_ia_{i+1})x^2+(\delta_{i+1}-a_{i+1}\delta_i-b_id_{i+1})x-\delta_id_{i+1} xb~i+1−b~ia~i+1=(bi+1−biai+1)x2+(δi+1−ai+1δi−bidi+1)x−δidi+1，若 b i + 1 = b i a i + 1 b_{i+1}=b_ia_{i+1} bi+1=biai+1成立，则该多项式的二阶系数为0，仅需分别对一阶系数和常量仅需commit，然后Verifier利用commitment加法同态性仅需验证即可。具体思路为：
- Prover：引入随机值 δ 1 , ⋯ , δ n \delta_1,\cdots,\delta_n δ1,⋯,δn，限定 δ 1 = d 1 , δ n = 0 \delta_1=d_1,\delta_n=0 δ1=d1,δn=0对多项式常量commit c δ = c o m c k ( − δ 1 d 2 , ⋯ , − δ n − 1 d n ; s 1 ) c_{\delta}=com_{ck}(-\delta_1d_2,\cdots,-\delta_{n-1}d_n;s_1) cδ=comck(−δ1d2,⋯,−δn−1dn;s1)，对一阶系数commit c Δ = c o m c k ( δ 2 − a 2 δ 1 − b 1 d 2 , ⋯ , δ n − a n δ n − 1 − b n − 1 d n ; s x ) c_{\Delta}=com_{ck}(\delta_2-a_2\delta_1-b_1d_2,\cdots,\delta_n-a_n\delta_{n-1}-b_{n-1}d_n;s_x) cΔ=comck(δ2−a2δ1−b1d2,⋯,δn−anδn−1−bn−1dn;sx) 。Prover给Verifier发送 c δ 和 c Δ c_{\delta}和c_{\Delta} cδ和cΔ。
- Verifier：Challenge x x x。
- Prover：计算 b ~ i = x b i + δ i \tilde{b}_i=xb_i+\delta_i b~i=xbi+δi，同时计算 s ~ = x s x + s 1 \tilde{s}=xs_x+s_1 s~=xsx+s1。Prover给Verifier发送 b ~ 1 , ⋯ , b ~ n , s ~ \tilde{b}_1,\cdots,\tilde{b}_n,\tilde{s} b~1,⋯,b~n,s~。
- Verifier：验证
b
~
1
=
a
~
1
和
b
~
n
=
x
b
\tilde{b}_1=\tilde{a}_1和\tilde{b}_n=xb
b~1=a~1和b~n=xb成立以及
c
Δ
x
c
δ
=
c
o
m
c
k
(
x
b
~
2
−
b
~
1
a
~
2
,
⋯
,
x
b
~
n
−
b
~
n
−
1
a
~
n
;
s
~
)
c_{\Delta}^xc_{\delta}=com_{ck}(x\tilde{b}_2-\tilde{b}_1\tilde{a}_2,\cdots,x\tilde{b}_n-\tilde{b}_{n-1}\tilde{a}_n;\tilde{s})
cΔxcδ=comck(xb~2−b~1a~2,⋯,xb~n−b~n−1a~n;s~)成立即可。
