Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（3）

1. 前言

• 在博客 Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1）中介绍了Shuffle argument总体算法以及Multi-exponentiation Argument算法。
• 在博客Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（2）中，将重点介绍product argument算法——拆分为三个：hadamard product argument、zero argument和single value product argument.。

在本博客中，主要介绍对Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》中各算法的代码实现。目前github上主要有两类实现：

• https://github.com/derbear/verifiable-shuffle
• https://github.com/nirvantyagi/stadium和https://github.com/grnet/bg-mixnet

2. https://github.com/derbear/verifiable-shuffle中代码实现

round_n，$n$n为奇数对应是Prover操作，$n$n为偶数对应是Verifier操作。

• round_1：shuffle argument中的commit to $\pi(1),…,\pi(N)$π(1),…,π(N)。
• round_2：challenge $chal\_x2$chal_x2。
• round_3：$x=chal\_x2$x=chal_x2， commit to $x^{\pi(1)},…,x^{\pi(N)}$xπ(1),…,xπ(N)。
• round_4：challenge $chal\_y4,chal\_z4$chal_y4,chal_z4。
• round_5a： $y=chal\_y4,z=chal\_z4$y=chal_y4,z=chal_z4，构建矩阵$D=(d_1-z=y\pi(1)+x^{\pi(1)}-z,…,d_N-z=y\pi(N)+x^{\pi(N)}-z)=(\vec{d}_1,\vec{d}_2,\cdots,\vec{d}_m)$D=(d1​−z=yπ(1)+xπ(1)−z,…,dN​−z=yπ(N)+xπ(N)−z)=(d1​,d2​,⋯,dm​)，构建用于product argument的矩阵$D\_h=(\vec{d}_1,\vec{d}_1\cdot\vec{d}_2,\cdots,\vec{d}_1\cdot\vec{d}_2\cdots\vec{d}_m)=(\vec{d}_{h_1},\vec{d}_{h_2},\cdots,\vec{d}_{h_{m-1}},\vec{d}_{h_m})$D_h=(d1​,d1​⋅d2​,⋯,d1​⋅d2​⋯dm​)=(dh1​​,dh2​​,⋯,dhm−1​​,dhm​​)，并对$D\_h$D_h进行commit。
• round_5b：引入随机变量$B_0\leftarrow \mathbb{Z}_q^n$B0​←Zqn​和$a\leftarrow \mathbb{Z}_q^{2m}$a←Zq2m​并分别对其commit，分别对应Multi-exponentiation Argument中的$c_{A_0}和\{c_{B_k}\}_{k=0}^{2m-1}$cA0​​和{cBk​​}k=02m−1​。
• round_5c：计算Multi-exponentiation Argument中的$\{E_{k}\}_{k=0}^{2m-1}${Ek​}k=02m−1​。
• round_6：challenge $chal\_x6\leftarrow\mathbb{Z}_q^{2m}:(x,x^2,\cdots,x^{2m})和chal\_y6\leftarrow\mathbb{Z}_q^{n}:(y,y^2,\cdots,y^{n})$chal_x6←Zq2m​:(x,x2,⋯,x2m)和chal_y6←Zqn​:(y,y2,⋯,yn)。
• round_7a：
  为Hadamard product argument服务，引入随机向量$\vec{d}_{m+1}\leftarrow \mathbb{Z}_q^n$dm+1​←Zqn​，commitment to $\vec{d}_{m+1}$dm+1​，构建矩阵$D\_s=(x\vec{d}_{h_1},x^2\vec{d}_{h_2},\cdots,x^{m-1}\vec{d}_{h_{m-1}},\sum_{i=1}^{m-1}{x^i\vec{d}_{h_{i+1}}},\vec{d}_{m+1})$D_s=(xdh1​​,x2dh2​​,⋯,xm−1dhm−1​​,∑i=1m−1​xidhi+1​​,dm+1​)，commit to $D\_s$D_s。
  为zero argument服务，构建相应的$D\_l$D_l并commit，对应其中的$\vec{c}_D、c_{A_0}和c_{B_m}$cD​、cA0​​和cBm​​。
  为Single value product argument服务，引入随机变量$\vec{d}\leftarrow\mathbb{Z}_q^n$d←Zqn​，计算$c_d、c_{\delta}和c_{\Delta}$cd​、cδ​和cΔ​。
• round_7b：计算Multi-exponentiation Argument中的$\vec{a},r,b,s,\tau$a,r,b,s,τ。
• round_8：challenge $chal\_x8\leftarrow\mathbb{Z}_q^{2m+1}:(x,x^2,\cdots,x^{2m+1})$chal_x8←Zq2m+1​:(x,x2,⋯,x2m+1)。
• round_9a：计算Single value product argument中的$\tilde{a}_1,\cdots,\tilde{a}_n,\tilde{r}$a~1​,⋯,a~n​,r~和$\tilde{b}_1,\cdots,\tilde{b}_n,\tilde{s}$b~1​,⋯,b~n​,s~。
• round_9b：计算zero argument中的$\vec{a},\vec{b},r,s,t$a,b,r,s,t。
• round_10：分别对shuffle argument、Multi-exponentiation Argument、Hadamard product argument、zero argument以及Single value product argument的最后一步verify即可。

3. https://github.com/nirvantyagi/stadium和https://github.com/grnet/bg-mixnet中代码实现

https://github.com/nirvantyagi/stadium和https://github.com/grnet/bg-mixnet两套代码之间的关系为：
bg-mixnet builds on top of the Stadium software project, which is hosted at https://github.com/nirvantyagi/stadium. Stadium is a distributed metadata-private messaging system.

性能相对于https://github.com/derbear/verifiable-shuffle做了性能优化：