Groth 2011年论文《Efficient Zero-Knowledge Arguments from Two-Tiered Homomorphic Commitments》，发表于Asia crypto 2011。
本文：
-
基于double pairing assumption构建了two-tiered homomorphic commitments scheme 。
-
基于本文的two-tiered homomorphic commitments scheme狗啊见的zero-knowledge argument，具有： – sublinear communication complexity – perfect completeness – perfect special honest verifier zero-knowledge – computational soundness
-
将本文的zero-knowledge argument用于实现range proof时，如证明a committed value belongs to a specific N N N-bit integer interval，相应的communication cost为 O ( N 1 3 ) O(N^{\frac{1}{3}}) O(N31) 个 group elements。
-
构建的circuit satisfiability argument的communication complexity为 O ( N 1 3 ) O(N^{\frac{1}{3}}) O(N31)个group elements，其中 N N N为gate数量。 该argument具有quasi-linear computational complexity for the prover，同时具有very efficient verification。 相关的对比见 如下表1和表2 ：（其中Prover的computation保守估计为 O ( N log 2 N ) O(N\log^2 N) O(Nlog2N)，若借助FFT，可进一步reduce为 O ( N log N ) O(N\log N) O(NlogN)。）
其中： – [8] Cramer等人1994年论文《Proofs of partial knowledge and simplified design of witness hiding protocols》，基于的是DLOG assumption。 – [22] Groth 2019年论文《Linear algebra with sub-linear zero-knowledge arguments》，基于的是DLOG assumption。 -
本文的zero-knowledge argument可实例化为in asymmetric bilinear group，在该group下computational double pairing assumption成立。而[6,7] 论文中的range proof是基于 q q q-SDH assumption in bilinear group。
-
主要技术贡献是：batch product argument。已知 3 N 3N 3N个committed elements u i , v i , w i ∈ Z p u_i,v_i,w_i\in\mathbb{Z}_p ui,vi,wi∈Zp，构建了zk argument 证明 u i v i = w i u_iv_i=w_i uivi=wi。 借助commitment 的同态属性，同时支持对committed elements的加法和乘法运算，从而允许the prover to commit to the wires in a circuit and prove that they respect the N A N D NAND NAND-gate。 而对于range proof，将数值以 N N N个bit位表示 w 1 , ⋯ , w N w_1,\cdots,w_N w1,⋯,wN，则可转为证明 w i w i = w i w_iw_i=w_i wiwi=wi， which can only be true if w i ∈ { 0 , 1 } w_i\in\{0,1\} wi∈{0,1}。然后利用commitment的同态属性计算 w = ∑ i = 1 N w i 2 i − 1 w=\sum_{i=1}^{N}w_i2^{i-1} w=∑i=1Nwi2i−1，即可证明 w ∈ [ 0 ; 2 N ) w\in [0;2^N) w∈[0;2N)。也可扩展为证明 w ∈ [ A , B ) w\in [A,B) w∈[A,B)。
本文涉及的commitment scheme 有：
- Pedersen commitment
- commitment scheme for group elements
- Pedersen commitment + commitment scheme for group elements
(1) Pedersen commitment： public key中包含the description of a group of prime order p p p和group elements g , h g,h g,h。 commitment to a ∈ Z p a\in\mathbb{Z}_p a∈Zp表示为： c = g a h r c=g^ah^r c=gahr，其中 r r r为随机值。 具有加法同态属性，即 c ⋅ c ′ = ( g a h r ) ( g b h s ) = g a + b h r + s c\cdot c'=(g^ah^r)(g^bh^s)=g^{a+b}h^{r+s} c⋅c′=(gahr)(gbhs)=ga+bhr+s 为a commitment to a + b a+b a+b。 commitment to vector ( a 1 , a 2 , ⋯ , a n ) ∈ Z p n (a_1,a_2,\cdots, a_n)\in\mathbb{Z}_p^n (a1,a2,⋯,an)∈Zpn可表示为： c = h r ∏ k = 1 n g k a k c=h^r\prod_{k=1}^{n}g_k^{a_k} c=hr∏k=1ngkak
(2) commitment scheme for group elements： Abe等人2010年论文《Structure-preserving signatures and commitments to group elements》 和 Groth 2009年论文《Homomorphic trapdoor commitments to group elements》 中均提出了commitment scheme for group elements。 其中的一种commitment scheme是使用a bilinear with a pairing e : G × G ^ → T e: \mathbb{G}\times\hat{\mathbb{G}}\rightarrow \mathbb{T} e:G×G^→T 其中 G , G ^ , T \mathbb{G},\hat{\mathbb{G}},\mathbb{T} G,G^,T均为cyclic groups of prime order p p p，将 G \mathbb{G} G和 G ^ \hat{\mathbb{G}} G^ 称为base group， T \mathbb{T} T称为target group。 该pairing应为efficiently computable, non-trivial and bilinear，即： ∀ x , y , a , b \forall x,y,a,b ∀x,y,a,b均有 e ( x a , y b ) = e ( x , y ) a b e(x^a,y^b)=e(x,y)^{ab} e(xa,yb)=e(x,y)ab 对于specific non-trivial group elements v , u 1 , ⋯ , u m ∈ G ^ v,u_1,\cdots,u_m\in\hat{\mathbb{G}} v,u1,⋯,um∈G^，a commitment to vector ( c 1 , ⋯ , c m ) ∈ G (c_1,\cdots,c_m)\in\mathbb{G} (c1,⋯,cm)∈G 可表示为： C = e ( t , v ) ∏ j = 1 m e ( c j , u j ) C=e(t,v)\prod_{j=1}^{m}e(c_j,u_j) C=e(t,v)∏j=1me(cj,uj)，其中 t t t为random point t ∈ G t\in\mathbb{G} t∈G。 以上commitment具有computationally binding under the computational double pairing assumption，即已知 u , v ∈ G ^ u,v\in\hat{\mathbb{G}} u,v∈G^，很难找到 s , t ∈ G s,t\in\mathbb{G} s,t∈G，使得 e ( s , u ) = e ( t , v ) e(s,u)=e(t,v) e(s,u)=e(t,v) 成立。 同时在Abe和Groth论文中证明了，the hardness of the computational double pairing assumption 与 the hardness of decision Diffie-Hellman assumption in G ^ \hat{\mathbb{G}} G^ 相当。 根据pairing的bilinearity属性有： C ⋅ C ′ = ( e ( t , v ) ∏ j = 1 m e ( c j , u j ) ) ( e ( t ′ , v ) ∏ j = 1 m e ( c j ′ , u j ) ) = e ( t t ′ , v ) ∏ j = 1 m e ( c j c j ′ , u j ) C\cdot C'=( e(t,v)\prod_{j=1}^{m}e(c_j,u_j))( e(t',v)\prod_{j=1}^{m}e(c_j',u_j))= e(tt',v)\prod_{j=1}^{m}e(c_jc_j',u_j) C⋅C′=(e(t,v)∏j=1me(cj,uj))(e(t′,v)∏j=1me(cj′,uj))=e(tt′,v)∏j=1me(cjcj′,uj) 即为a commitment to the entry-wise product of the messages。
(3) Pedersen commitment + commitment scheme for group elements： 将Pedersen commitment scheme 和 commitment scheme for group elements结合，可实现commit to commitments。 即若 c j = h r j ∏ k = 1 n g k a j k c_j=h^{r_j}\prod_{k=1}^{n}g_k^{a_{jk}} cj=hrj∏k=1ngkajk， C = e ( t , v ) ∏ j = 1 m e ( c j , u j ) C=e(t,v)\prod_{j=1}^{m}e(c_j,u_j) C=e(t,v)∏j=1me(cj,uj)，最终可获得 a single target group element that is a commitment to m n mn mn values { a j k } j = 1 , k = 1 m , n \{a_{jk}\}_{j=1,k=1}^{m,n} {ajk}j=1,k=1m,n。 因两种commitment scheme都是homomorphic the product of two commitments C ⋅ C ′ C\cdot C' C⋅C′ 为 a commitment to the sums of the messages a j k + a j k ′ a_{jk}+a_{jk}' ajk+ajk′。
two-tiered commitment scheme包含3个算法 ( K , c o m , c o m ( 2 ) ) (\mathcal{K}, com, com^{(2)}) (K,com,com(2))，其中： 1） K \mathcal{K} K为key generator 输入为security parameter λ \lambda λ，数字 m , n m,n m,n，输出为public key c k ck ck。the commitment key specifies cyclic groups Z p , G \mathbb{Z}_p,\mathbb{G} Zp,G和 T \mathbb{T} T of prime order p p p。【一共有 m + n + 2 m+n+2 m+n+2个group elements in G \mathbb{G} G and G ^ \hat{\mathbb{G}} G^】 2） c o m c k : Z p n × Z p → G com_{ck}:\mathbb{Z}_p^n\times \mathbb{Z}_p\rightarrow \mathbb{G} comck:Zpn×Zp→G，即对应本文的Pedersen commitment。 3） c o m c k 2 : G m → T com_{ck}^2:\mathbb{G}^m\rightarrow \mathbb{T} comck2:Gm→T，即对应本文的commitment scheme for group elements.
具有如下特性：
- 同态属性：当the maps c o m c k com_{ck} comck and c o m c k 2 com_{ck}^2 comck2 为 Z p \mathbb{Z}_p Zp-linear时，该two-tiered commitment scheme具有同态属性。
- computationally binding 属性
- perfectly hiding属性
针对的场景为：
- public info：commitments C U 1 , C V 1 , C W 1 , ⋯ , C U M , C V M , C W M C_{U_1},C_{V_1},C_{W_1},\cdots,C_{U_M},C_{V_M},C_{W_M} CU1,CV1,CW1,⋯,CUM,CVM,CWM
- private info： { u i j k ∈ Z p , v i j k ∈ Z p , w i j k ∈ Z p } i = 1 , j = 1 , k = 1 M , m , n \{u_{ijk}\in\mathbb{Z}_p, v_{ijk}\in\mathbb{Z}_p,w_{ijk}\in\mathbb{Z}_p \}_{i=1,j=1,k=1}^{M,m,n} {uijk∈Zp,vijk∈Zp,wijk∈Zp}i=1,j=1,k=1M,m,n 以及 相应的随机值 r i , j , s i , j , t i , j ∈ Z p r_{i,j},s_{i,j},t_{i,j} \in\mathbb{Z}_p ri,j,si,j,ti,j∈Zp。
- relation： u i j k v i j k = w i j k u_{ijk}v_{ijk}=w_{ijk} uijkvijk=wijk 且 c u i , j = c o m c k ( u i j 1 , ⋯ , u i j n ; r i j ) c_{u_{i,j}}=com_{ck}(u_{ij1},\cdots,u_{ijn}; r_{ij}) cui,j=comck(uij1,⋯,uijn;rij) 且 C U i = c o m c k 2 ( c u i 1 , ⋯ , c u i m ) C_{U_i}=com_{ck}^2(c_{u_{i1}},\cdots,c_{u_{im}}) CUi=comck2(cui1,⋯,cuim) 且 c v i , j = c o m c k ( v i j 1 , ⋯ , v i j n ; s i j ) c_{v_{i,j}}=com_{ck}(v_{ij1},\cdots,v_{ijn}; s_{ij}) cvi,j=comck(vij1,⋯,vijn;sij) 且 C V i = c o m c k 2 ( c v i 1 , ⋯ , c v i m ) C_{V_i}=com_{ck}^2(c_{v_{i1}},\cdots,c_{v_{im}}) CVi=comck2(cvi1,⋯,cvim) 且 c w i , j = c o m c k ( w i j 1 , ⋯ , w i j n ; t i j ) c_{w_{i,j}}=com_{ck}(w_{ij1},\cdots,w_{ijn}; t_{ij}) cwi,j=comck(wij1,⋯,wijn;tij) 且 C W i = c o m c k 2 ( c w i 1 , ⋯ , c w i m ) C_{W_i}=com_{ck}^2(c_{w_{i1}},\cdots,c_{w_{im}}) CWi=comck2(cwi1,⋯,cwim)
基本思路为：
-
若引入challenge x ∈ Z p ∗ x\in\mathbb{Z}_p^* x∈Zp∗，则可转换为证明： ∑ i = 1 M ∑ j = 1 m ∑ k = 1 n ( u i j k v i j k − w i j k ) x i ( m + 1 ) n + j n + k = 0 \sum_{i=1}^{M}\sum_{j=1}^{m}\sum_{k=1}^{n}(u_{ijk}v_{ijk}-w_{ijk})x^{i(m+1)n+jn+k}=0 ∑i=1M∑j=1m∑k=1n(uijkvijk−wijk)xi(m+1)n+jn+k=0 …… （1） 除非 u i j k v i j k = w i j k u_{ijk}v_{ijk}=w_{ijk} uijkvijk=wijk for all choices of i , j , k i,j,k i,j,k，否则对于randomly chosen challenge x ∈ Z p ∗ x\in\mathbb{Z}_p^* x∈Zp∗，以上等式成立的概率可忽略。 接下来的难点在于构建this polynomial 并convince the verifier that 方程式（1） 成立，我们实现了communication cost仅为 O ( M + m + n ) O(M+m+n) O(M+m+n)。
-
利用 c o m c K 2 com_{cK}^2 comcK2的同态属性有：
-
利用 c o m c k com_{ck} comck的同态属性有：
-
从而有：
构建多项式
∑
k
=
1
n
(
u
k
v
k
−
w
k
)
x
k
\sum_{k=1}^{n}(u_kv_k-w_k)x^k
∑k=1n(ukvk−wk)xk展开为： 
里面包含了我们需要证明的方程式（1），同时也包含了一些cross-terms corresponding to
i
≠
i
′
i\neq i'
i=i′ or
j
≠
j
′
j\neq j'
j=j′，使得以上多项式值可能为非零值。 因此需要引入
a
α
a_{\alpha}
aα和
b
β
b_{\beta}
bβ值，用于cancel out the cross-terms，需要额外再引入变量
y
,
z
y,z
y,z，使得：【本文实现的最终communication cost为
O
(
M
+
m
+
n
)
O(M+m+n)
O(M+m+n)。】 
从而有： 
可以将以上的求和情况拆解为3个部分： 1）
j
=
j
′
,
i
=
i
′
j=j',i=i'
j=j′,i=i′ 2）
j
=
j
′
,
i
≠
i
′
j=j',i\neq i'
j=j′,i=i′ 3）
j
≠
j
′
j\neq j'
j=j′ 从而有： 
此时，Prover仅需证明其知道： 
1）Prover先发送commitment
{
c
a
α
}
α
∈
{
−
M
,
⋯
,
−
1
,
1
,
⋯
,
M
}
\{c_{a_{\alpha}}\}_{\alpha\in\{-M,\cdots,-1,1,\cdots,M\}}
{caα}α∈{−M,⋯,−1,1,⋯,M}给Verifier。 2）Verifier 发送challenge
y
∈
Z
p
∗
y\in\mathbb{Z}_p^*
y∈Zp∗ 3）Prover发送commitment
{
c
b
β
}
β
∈
{
−
m
,
⋯
,
−
1
,
1
,
⋯
,
m
}
\{c_{b_{\beta}}\}_{\beta\in\{-m,\cdots,-1,1,\cdots,m\}}
{cbβ}β∈{−m,⋯,−1,1,⋯,m} 给Verifier。 4）Verifier 发送challenge
z
∈
Z
p
∗
z\in\mathbb{Z}_p^*
z∈Zp∗ 5）Prover发送相应的evaluation值
{
u
k
,
v
k
,
w
k
}
k
=
1
n
\{u_k,v_k,w_k\}_{k=1}^{n}
{uk,vk,wk}k=1n和其它randomness
R
R
R值发送给Verifier。 6）Verifier 仅需验证： 
以下为详细的zero knowledge batch Hadamard product argument协议：【引入随机commitments { c d k } k = 1 n \{c_{d_k}\}_{k=1}^{n} {cdk}k=1n 来实现hiding】 【 整个batch product argument ：
- communication cost为：3个 T \mathbb{T} T elements， 2 M + 5 m + n + 1 2M+5m+n+1 2M+5m+n+1个 G \mathbb{G} G elements和 3 n + 7 3n+7 3n+7个 Z p \mathbb{Z}_p Zp elements。
- Verifier的computation为： 3 m 3m 3m个pairings and exponenetiations in the target group T \mathbb{T} T 和 5 M + 2 m + 4 n 5M+2m+4n 5M+2m+4n个exponentiations in the base group G \mathbb{G} G，可借助multi-exponentiation技术将其reduce为 O ( M + m + n log ( M + m + n ) ) O(\frac{M+m+n}{\log (M+m+n)}) O(log(M+m+n)M+m+n) 个exponentiations。
- Prover computation为：
3
m
3m
3m个pairings 和
O
(
M
+
m
+
n
)
O(M+m+n)
O(M+m+n) 个exponentiations，以及
O
(
N
(
M
+
m
)
)
O(N(M+m))
O(N(M+m))个multiplications in
Z
p
\mathbb{Z}_p
Zp，其中
N
=
M
m
n
N=Mmn
N=Mmn。可借助polynomial multiplication来reduce Prover的computation 压力。如以下协议第3步中：
- 若部分witness值为public known的话，协议性能可进一步优化：
】 
即为了证明： ∑ i = 1 M ∑ j = 1 m ∑ k = 1 n u i j k v i j k = ∑ i = 1 M ∑ j = 1 m ∑ k = 1 n w i j k \sum_{i=1}^{M}\sum_{j=1}^{m}\sum_{k=1}^{n}u_{ijk}v_{ijk}=\sum_{i=1}^{M}\sum_{j=1}^{m}\sum_{k=1}^{n}w_{ijk} ∑i=1M∑j=1m∑k=1nuijkvijk=∑i=1M∑j=1m∑k=1nwijk
观察可发现，对于方程式（1）中的 x x x值不再由Verifier random select，而是固定为 x = 1 x=1 x=1即可。
∑ i = 1 M ∑ j = 1 m ∑ k = 1 n ( u i j k v i j k − w i j k ) x i ( m + 1 ) n + j n + k = 0 \sum_{i=1}^{M}\sum_{j=1}^{m}\sum_{k=1}^{n}(u_{ijk}v_{ijk}-w_{ijk})x^{i(m+1)n+jn+k}=0 ∑i=1M∑j=1m∑k=1n(uijkvijk−wijk)xi(m+1)n+jn+k=0 …… （1）
借助第三节的batch hadamard product argument，可构建a 7 7 7-move SHVZK argument for circuit satisfiability。 针对包含 N − 1 N-1 N−1个 与非门的 boolean circuit，使得Verifier相信存在a satisfying assignment making the circuit ouput 1 1 1。
假设circuit具有 N = M m n N=Mmn N=Mmn个与非门，每个与非门的两个输入和一个输出分别为 u i j k , v i j k , w i j k u_{ijk},v_{ijk},w_{ijk} uijk,vijk,wijk，Prover需要证明：
- all the committed values are either 0 0 0 or 1 1 1 corresponding to truth values。 可通过batch Hadamard product argument来证明 u i j k u i j k = u i j k , v i j k v i j k = v i j k . w i j k w i j k = w i j k u_{ijk}u_{ijk}=u_{ijk}, v_{ijk}v_{ijk}=v_{ijk}. w_{ijk}w_{ijk}=w_{ijk} uijkuijk=uijk,vijkvijk=vijk.wijkwijk=wijk，which can only be true if u i j k , v i j k , w i j k ∈ { 0 , 1 } u_{ijk}, v_{ijk}, w_{ijk}\in\{0,1\} uijk,vijk,wijk∈{0,1}。
- Prover可利用commitment的同态属性来计算commitments to 1 − w i j k 1-w_{ijk} 1−wijk。
- 利用另一个batch Hadamard product argument来证明 u i j k v i j k = 1 − w i j k u_{ijk}v_{ijk}=1-w_{ijk} uijkvijk=1−wijk，表示the committed values respect the NAND-gates。
- 利用Groth 2009年论文《Linear algebra with sub-linear zero-knowledge arguments》中的inner product argument技术来证明all committed values u i j k , v i j k u_{ijk},v_{ijk} uijk,vijk和 w i j k w_{ijk} wijk corresponding to the same wire x l x_l xl are consistent with each other。【其中包含了permutation argument】
详细的arguments for circuit satisfiability实现为： 
以上Boolean circuit 证明也可扩展至arithmetic circuit。
对应的场景为：
- public info：commitment c c c，和 A , B A,B A,B
- private info： w , t w,t w,t
- relation： c = c o m c k ( w ; t ) , w ∈ [ A ; B ) c=com_{ck}(w;t),w\in[A;B) c=comck(w;t),w∈[A;B)
基本思路为：
- 利用commitment的同态属性，可转为证明Prover knows an opening of c ⋅ c o m c k ( − A ; 0 ) c\cdot com_{ck}(-A;0) c⋅comck(−A;0) in the range [ 0 ; B − A ) [0;B-A) [0;B−A)。
- 设 N = ⌊ log ( B − A ) ⌋ N= \left \lfloor \log (B-A) \right \rfloor N=⌊log(B−A)⌋。 Prover构建a commitment c 0 / 1 = c o m c k ( b ; s ) c_{0/1}=com_{ck}(b;s) c0/1=comck(b;s)，并show that it contains 0 0 0 or 1 1 1 using standard techniques。
- 证明 KaTeX parse error: Undefined control sequence: \codt at position 22: … com_{ck}(-A;0)\̲c̲o̲d̲t̲ ̲c_{0/1}^{A-B+2^… 包含a value in the range [ 0 ; 2 N ) [0;2^N) [0;2N)，即可使Verifier信服 w ∈ [ A ; B ) w\in [A;B) w∈[A;B)。
以
w
∈
[
0
;
2
N
)
w\in [0;2^N)
w∈[0;2N)为例，相应的range argument实现为： 
