- 在博客 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
round_n， n n n为奇数对应是Prover操作， n n n为偶数对应是Verifier操作。
- round_1：shuffle argument中的commit to π ( 1 ) , … , π ( N ) \pi(1),…,\pi(N) π(1),…,π(N)。
- round_2：challenge c h a l _ x 2 chal\_x2 chal_x2。
- round_3： x = c h a l _ x 2 x=chal\_x2 x=chal_x2， commit to x π ( 1 ) , … , x π ( N ) x^{\pi(1)},…,x^{\pi(N)} xπ(1),…,xπ(N)。
- round_4：challenge c h a l _ y 4 , c h a l _ z 4 chal\_y4,chal\_z4 chal_y4,chal_z4。
- round_5a： y = c h a l _ y 4 , z = c h a l _ z 4 y=chal\_y4,z=chal\_z4 y=chal_y4,z=chal_z4，构建矩阵 D = ( d 1 − z = y π ( 1 ) + x π ( 1 ) − z , … , d N − z = y π ( N ) + x π ( N ) − z ) = ( d ⃗ 1 , d ⃗ 2 , ⋯ , d ⃗ m ) 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)=(d 1,d 2,⋯,d m)，构建用于product argument的矩阵 D _ h = ( d ⃗ 1 , d ⃗ 1 ⋅ d ⃗ 2 , ⋯ , d ⃗ 1 ⋅ d ⃗ 2 ⋯ d ⃗ m ) = ( d ⃗ h 1 , d ⃗ h 2 , ⋯ , d ⃗ h m − 1 , d ⃗ h m ) 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=(d 1,d 1⋅d 2,⋯,d 1⋅d 2⋯d m)=(d h1,d h2,⋯,d hm−1,d hm)，并对 D _ h D\_h D_h进行commit。
- round_5b：引入随机变量 B 0 ← Z q n B_0\leftarrow \mathbb{Z}_q^n B0←Zqn和 a ← Z q 2 m a\leftarrow \mathbb{Z}_q^{2m} a←Zq2m并分别对其commit，分别对应Multi-exponentiation Argument中的 c A 0 和 { c B k } k = 0 2 m − 1 c_{A_0}和\{c_{B_k}\}_{k=0}^{2m-1} cA0和{cBk}k=02m−1。
- round_5c：计算Multi-exponentiation Argument中的 { E k } k = 0 2 m − 1 \{E_{k}\}_{k=0}^{2m-1} {Ek}k=02m−1。
- round_6：challenge c h a l _ x 6 ← Z q 2 m : ( x , x 2 , ⋯ , x 2 m ) 和 c h a l _ y 6 ← Z q n : ( y , y 2 , ⋯ , y n ) 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服务，引入随机向量 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，构建矩阵 D _ s = ( x d ⃗ h 1 , x 2 d ⃗ h 2 , ⋯ , x m − 1 d ⃗ h m − 1 , ∑ i = 1 m − 1 x i d ⃗ h i + 1 , d ⃗ m + 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=(xd h1,x2d h2,⋯,xm−1d hm−1,∑i=1m−1xid hi+1,d m+1)，commit to D _ s D\_s D_s。 为zero argument服务，构建相应的 D _ l D\_l D_l并commit，对应其中的 c ⃗ D 、 c A 0 和 c B m \vec{c}_D、c_{A_0}和c_{B_m} c D、cA0和cBm。 为Single value product argument服务，引入随机变量 d ⃗ ← Z q n \vec{d}\leftarrow\mathbb{Z}_q^n d ←Zqn，计算 c d 、 c δ 和 c Δ c_d、c_{\delta}和c_{\Delta} cd、cδ和cΔ。
- round_7b：计算Multi-exponentiation Argument中的 a ⃗ , r , b , s , τ \vec{a},r,b,s,\tau a ,r,b,s,τ。
- round_8：challenge c h a l _ x 8 ← Z q 2 m + 1 : ( x , x 2 , ⋯ , x 2 m + 1 ) 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中的 a ~ 1 , ⋯ , a ~ n , r ~ \tilde{a}_1,\cdots,\tilde{a}_n,\tilde{r} a~1,⋯,a~n,r~和 b ~ 1 , ⋯ , b ~ n , s ~ \tilde{b}_1,\cdots,\tilde{b}_n,\tilde{s} b~1,⋯,b~n,s~。
- round_9b：计算zero argument中的 a ⃗ , b ⃗ , r , s , t \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即可。
Nirvan Tyagi等人2017年论文《Stadium: A Distributed Metadata-Private Messaging System》，针对的场景是：互联网环节下的private communication。即使对传输的消息messages进行了加密（data privacy），但是要想隐藏相互通讯的双方信息（metadata about which pairs of users are communicating——metadata privacy）仍不容易。如匿名网络Tor对traffic analysis流量分析是敏感的。本文的metadata指：who is communicating with whom, at what time, and their traffic volumes. 现有情况：
- Systems that leak no metadata at all, such as Riposte [12] and Dissent [13], require broadcasting all messages to all users or use computationally intensive Private Information Retrieval.
- Vuvuzela 是一个消息通讯系统。可以保护消息的内容和消息元数据的私密性。目前Vuvuzela仅能支持最高约115,000 messages per second，而此时每个Vuvuzela server对应需要的带宽约为1.3Gbit/sec（因其设计为requires transmitting all messages through a single chain of relay servers, preventing it from scaling beyond this.），增加server的成本。基于Jelle van den Hooff等人2015年论文《Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis》，代码实现可见：https://github.com/vuvuzela/vuvuzela。
Stadium——在保证吞吐量和可扩展性的前提下，可同时提供metadata privacy和data privacy，并保证efficiently distributing its work over multiple servers。与Vuvuzela类似，Stadium基于的也是differential privacy差分隐私技术，但是Stadium可支持的用户。Stadium需要distributing users’ traffic across servers，使得adversaries有机会observe it in fine granularity，为了应对该风险，Stadium采用了以下两种方法：
- a collaborative noise generation approach。
- 和a novel verifiable parallel mixnet design where the servers collaboratively check that others follow the protocol。——即基于的是Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》的verifiable shuffling 协议 extended for non-interactive proofs via the Fiat Shamir Heuristic and instantiated over a 1536-bit prime order group。
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做了性能优化： 
