椭圆曲线形式下的Pedersen commitment——vector commitment和polynomial commitment
1. 椭圆曲线下的Pedersen commitment
椭圆曲线下Pedersen commitment可用scalar multiplication of curve points来表示：
C
=
r
H
+
a
G
C=rH+aG
C=rH+aG
其中，
C
C
C为椭圆曲线上的一个点curve point，作为commitment；
a
a
a为commit to 的数值；
r
r
r为随机数，可提供隐藏功能；
G
G
G为所选择椭圆曲线广泛接受的generator；
H
H
H为椭圆曲线上的另一个点，且保证无任何可推导
q
q
q，使得
H
=
q
G
H=qG
H=qG，这个H与G直接无明确关系非常重要。
如需open commitment C C C，需要提供r值和a值。
Pedersen commitment具有加法同态性：
C
(
r
1
,
a
1
)
+
C
(
r
2
,
a
2
)
=
r
1
H
+
a
1
G
+
r
2
H
+
a
2
G
=
(
r
1
+
r
2
)
H
+
(
a
1
+
a
2
)
G
=
C
(
r
1
+
r
2
,
a
1
+
a
2
)
C(r_1,a_1)+C(r_2,a_2)=r_1H+a_1G+r_2H+a_2G=(r_1+r_2)H+(a_1+a_2)G=C(r_1+r_2,a_1+a_2)
C(r1,a1)+C(r2,a2)=r1H+a1G+r2H+a2G=(r1+r2)H+(a1+a2)G=C(r1+r2,a1+a2)
2. Vector Pedersen Commitment 向量commitment
C
=
r
H
+
(
v
1
G
1
+
v
2
G
2
+
.
.
.
.
+
v
n
G
n
)
=
r
H
+
v
⃗
G
⃗
C=rH+(v_1G_1+v_2G_2+....+v_nG_n)=rH+\vec v\vec G
C=rH+(v1G1+v2G2+....+vnGn)=rH+v
其中，各个
G
i
G_i
Gi可由
H
a
s
h
(
e
n
c
o
d
e
(
G
)
∣
∣
i
)
Hash(encode(G)||i)
Hash(encode(G)∣∣i)来获取。
如需open commitment
C
C
C，需要提供随机数r值和向量值
v
⃗
\vec v
v
向量值
v
⃗
\vec v
v
也可以同时对多个Vector进行commitment，如对
v
⃗
,
w
⃗
\vec v,\vec w
v
C
=
r
H
+
v
⃗
G
⃗
+
w
⃗
H
⃗
C=rH+\vec v\vec G+\vec w\vec H
C=rH+v
其中，各个
H
i
H_i
Hi可由
H
a
s
h
(
e
n
c
o
d
e
(
H
)
∣
∣
i
)
Hash(encode(H)||i)
Hash(encode(H)∣∣i)来获取，即curve point
H
H
H不在vector
H
⃗
\vec H
H
3. A zero knowledge argument of knowledge of a set of vectors——一系列向量的零知识证明
假设有m个向量
x
⃗
1
,
x
⃗
2
,
.
.
.
,
x
⃗
m
\vec x_1,\vec x_2, ..., \vec x_m
x
C
1
=
r
1
H
+
x
⃗
1
G
⃗
C_1=r_1H+\vec x_1 \vec G
C1=r1H+x
C
2
=
r
2
H
+
x
⃗
2
G
⃗
C_2=r_2H+\vec x_2 \vec G
C2=r2H+x
.
.
.
...
...
C
m
=
r
m
H
+
x
⃗
m
G
⃗
C_m=r_mH+\vec x_m \vec G
Cm=rmH+x
以下
P
P
P代表prover,
V
V
V代表Verifier。
a)
P
→
V
:
C
0
P \rightarrow V: C_0
P→V:C0 (a new commitment to a newly chosen random vector of dimension N)
b)
V
→
P
:
e
V \rightarrow P: e
V→P:e (a random scalar，也可称为challenge值。)
c)
P
→
V
:
(
z
⃗
,
s
)
P \rightarrow V: (\vec z, s)
P→V:(z
其中：
z
⃗
=
∑
i
=
0
m
e
i
x
⃗
i
,
s
=
∑
i
=
0
m
e
i
r
i
\vec z=\sum_{i=0}^{m}e^i\vec x_i, \quad s=\sum_{i=0}^{m}e^ir_i
z
通过随机数
e
e
e，可很好的隐藏向量
x
⃗
\vec x
x
有1*m维矩阵：
(
1
,
e
,
e
2
,
.
.
.
,
e
m
)
(1,e,e^2,...,e^m)
(1,e,e2,...,em)
使得z值无法获取相应的x值。
对于Verifier，只需验证：
∑
i
=
0
m
e
i
C
i
=
?
s
H
+
z
⃗
G
⃗
\sum_{i=0}^{m}e^iC_i=?sH+\vec z\vec G
∑i=0meiCi=?sH+z
证明过程如下：
s
H
+
z
⃗
G
⃗
=
∑
i
=
0
m
e
i
(
r
i
H
)
+
∑
i
=
0
m
e
i
x
⃗
i
G
⃗
=
∑
i
=
0
m
e
i
(
r
i
H
+
x
⃗
i
G
⃗
)
=
∑
i
=
0
m
e
i
C
i
sH+\vec z\vec G=\sum_{i=0}^{m}e^i(r_iH)+\sum_{i=0}^{m}e^i\vec x_i\vec G=\sum_{i=0}^{m}e^i(r_iH+\vec x_i\vec G)=\sum_{i=0}^{m}e^iC_i
sH+z
由以上证明可知，Verifer可根据信息
(
C
0
,
e
,
(
z
⃗
,
s
)
)
(C_0,e,(\vec z, s))
(C0,e,(z
但是对于不诚信的prover，他可以随机选择
e
,
(
z
⃗
,
s
)
e,(\vec z, s)
e,(z
使得
∑
i
=
0
m
e
i
C
i
=
C
0
+
∑
i
=
1
m
e
i
C
i
=
(
s
H
+
z
⃗
G
⃗
)
−
(
∑
i
=
1
m
e
i
C
i
)
+
∑
i
=
1
m
e
i
C
i
=
s
H
+
z
⃗
G
⃗
\sum_{i=0}^{m}e^iC_i=C_0+\sum_{i=1}^{m}e^{i}C_i=(sH+\vec z\vec G)-(\sum_{i=1}^{m}e^{i}C_i)+\sum_{i=1}^{m}e^{i}C_i=sH+\vec z\vec G
∑i=0meiCi=C0+∑i=1meiCi=(sH+z
若需要open此种情况下的commitment，需要提供 C 1 , C 2 , . . . C m C_1,C_2,...C_m C1,C2,...Cm对应的共m个scalar数 r 1 , r 2 , . . . , r m r_1,r_2,...,r_m r1,r2,...,rm，以及 m ∗ N m*N m∗N个向量元素 x 11 , x 12 , . . . , x m N x_{11},x_{12},...,x_{mN} x11,x12,...,xmN。
3.1 一系列向量的零知识证明的soundness验证
修改上面的流程，重复a)b)c)步骤m+1次，每次均为scalar e提供不同的随机值
e
j
e_j
ej：
(
C
0
,
0
,
e
0
,
(
z
⃗
0
,
s
0
)
)
(C_{0,0},e_0,(\vec z_0,s_0))
(C0,0,e0,(z
(
C
0
,
1
,
e
1
,
(
z
⃗
1
,
s
1
)
)
(C_{0,1},e_1,(\vec z_1,s_1))
(C0,1,e1,(z
(
C
0
,
2
,
e
2
,
(
z
⃗
2
,
s
2
)
)
(C_{0,2},e_2,(\vec z_2,s_2))
(C0,2,e2,(z
.
.
.
...
...
(
C
0
,
m
,
e
m
,
(
z
⃗
m
,
s
m
)
)
(C_{0,m},e_m,(\vec z_m,s_m))
(C0,m,em,(z
相应地：
z
⃗
j
=
∑
i
=
0
m
e
j
i
x
⃗
i
,
s
j
=
∑
i
=
0
m
e
j
i
r
i
,
其
中
j
∈
[
0
,
m
]
\vec z_j=\sum_{i=0}^{m}e_j^i\vec x_i, \quad s_j=\sum_{i=0}^{m}e_j^ir_i, \quad 其中j\in [0,m]
z
则 有(m+1)*(m+1)维矩阵：
A
−
1
=
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
A^{-1}=\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}
A−1=⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞
使得z值无法获取相应的x值。该矩阵为Vandermonde 矩阵。
若
e
0
,
e
1
,
.
.
.
,
e
m
e_0,e_1,...,e_m
e0,e1,...,em互异，则存在对应的逆矩阵为：
A
=
(
a
00
a
01
a
02
.
.
.
a
0
m
a
10
a
11
a
12
.
.
.
a
1
m
a
20
a
21
a
22
.
.
.
a
2
m
.
.
.
a
m
0
a
m
1
a
m
2
.
.
.
a
m
m
)
A=\begin{pmatrix} a_{00}& a_{01}& a_{02}&... &a_{0m} \\ a_{10}& a_{11}& a_{12}&... &a_{1m} \\ a_{20}& a_{21}& a_{22}&... &a_{2m} \\ ...& & & & \\ a_{m0}& a_{m1}& a_{m2}&... &a_{mm} \end{pmatrix}
A=⎝⎜⎜⎜⎜⎛a00a10a20...am0a01a11a21am1a02a12a22am2............a0ma1ma2mamm⎠⎟⎟⎟⎟⎞
相应的Z也为矩阵，满足：
Z
=
A
−
1
X
=
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
(
x
⃗
0
x
⃗
1
x
⃗
2
.
.
.
x
⃗
m
)
=
(
∑
i
=
0
m
e
0
i
x
⃗
i
∑
i
=
0
m
e
1
i
x
⃗
i
∑
i
=
0
m
e
2
i
x
⃗
i
.
.
.
∑
i
=
0
m
e
m
i
x
⃗
i
)
=
(
z
⃗
0
z
⃗
1
z
⃗
2
.
.
.
z
⃗
m
)
Z=A^{-1}X=\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}\begin{pmatrix} \vec x_0\\ \vec x_1\\ \vec x_2\\ ... \\ \vec x_m \end{pmatrix}=\begin{pmatrix} \sum_{i=0}^{m}e_0^i\vec x_i\\ \sum_{i=0}^{m}e_1^i\vec x_i\\ \sum_{i=0}^{m}e_2^i\vec x_i\\ ... \\ \sum_{i=0}^{m}e_m^i\vec x_i \end{pmatrix}=\begin{pmatrix} \vec z_0\\ \vec z_1\\ \vec z_2\\ ... \\ \vec z_m \end{pmatrix}
Z=A−1X=⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛x
即相当于求m+1个方程式，存在唯一解
(
x
⃗
0
,
x
⃗
1
,
.
.
.
,
x
⃗
m
)
(\vec x_0, \vec x_1,..., \vec x_m)
(x
若 e 0 , e 1 , . . . , e m e_0,e_1,...,e_m e0,e1,...,em不互异，则可逆矩阵A不存在，也不能保证解的唯一性。
根据矩阵基础知识，矩阵B存在可逆矩阵的充分必要条件为B的判别式不为零，即det|B|!=0。
A的可逆矩阵A-1之间的关系有：
A
A
−
1
=
I
,
I
为
单
位
矩
阵
AA^{-1}=I,I为单位矩阵
AA−1=I,I为单位矩阵，即：
A
A
−
1
=
(
a
00
a
01
a
02
.
.
.
a
0
m
a
10
a
11
a
12
.
.
.
a
1
m
a
20
a
21
a
22
.
.
.
a
2
m
.
.
.
a
m
0
a
m
1
a
m
2
.
.
.
a
m
m
)
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
=
(
1
0
0
.
.
.
0
0
1
0
.
.
.
0
0
0
1
.
.
.
0
.
.
.
0
0
0
.
.
.
1
)
=
(
δ
00
δ
01
δ
02
.
.
.
δ
0
m
δ
10
δ
11
δ
12
.
.
.
δ
1
m
δ
20
δ
21
δ
22
.
.
.
δ
2
m
.
.
.
δ
m
0
δ
m
1
δ
m
2
.
.
.
δ
m
m
)
AA^{-1}=\begin{pmatrix} a_{00}& a_{01}& a_{02}&... &a_{0m} \\ a_{10}& a_{11}& a_{12}&... &a_{1m} \\ a_{20}& a_{21}& a_{22}&... &a_{2m} \\ ...& & & & \\ a_{m0}& a_{m1}& a_{m2}&... &a_{mm} \end{pmatrix}\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}=\begin{pmatrix} 1& 0& 0 &... &0 \\ 0& 1& 0 &... &0 \\ 0& 0& 1 &... &0 \\ ...& & & & \\ 0& 0& 0 &... &1 \end{pmatrix}=\begin{pmatrix} \delta _{00}& \delta _{01}& \delta _{02} &... &\delta _{0m} \\ \delta _{10}& \delta _{11}& \delta _{12} &... &\delta _{1m} \\ \delta _{20}& \delta _{21}& \delta _{22} &... &\delta _{2m} \\ ...& & & & \\ \delta _{m0}& \delta _{m1}& \delta _{m2} &... &\delta _{mm} \end{pmatrix}
AA−1=⎝⎜⎜⎜⎜⎛a00a10a20...am0a01a11a21am1a02a12a22am2............a0ma1ma2mamm⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎛100...001000010............0001⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎛δ00δ10δ20...δm0δ01δ11δ21δm1δ02δ12δ22δm2............δ0mδ1mδ2mδmm⎠⎟⎟⎟⎟⎞
上面公式中，
e
j
e_j
ej为challenge值，有：
δ
h
i
=
∑
j
=
0
m
a
h
j
e
j
i
\delta _{hi}=\sum_{j=0}^{m}a_{hj}e_j^i
δhi=∑j=0mahjeji
当 h = = i h==i h==i时，有 δ h i = 1 \delta _{hi}=1 δhi=1；当 h ! = i h!=i h!=i时，有 δ h i = 0 \delta _{hi}=0 δhi=0。也可称 δ h i \delta _{hi} δhi为Kronecker delta函数。
基于
δ
h
i
\delta _{hi}
δhi的特性，有：
C
h
=
∑
i
=
0
m
δ
h
i
C
i
C_h=\sum_{i=0}^{m}\delta _{hi}C_i
Ch=∑i=0mδhiCi
⇔
C
h
=
∑
i
=
0
m
δ
h
i
C
i
=
∑
i
=
0
m
(
∑
j
=
0
m
a
h
j
e
j
i
)
C
i
\Leftrightarrow C_h=\sum_{i=0}^{m}\delta _{hi}C_i=\sum_{i=0}^{m}(\sum_{j=0}^{m}a_{hj}e_j^i)C_i
⇔Ch=∑i=0mδhiCi=∑i=0m(∑j=0mahjeji)Ci
⇔
根
据
加
法
交
换
律
有
:
C
h
=
∑
i
=
0
m
(
∑
j
=
0
m
a
h
j
e
j
i
)
C
i
=
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
C
i
)
\Leftrightarrow 根据加法交换律有: \quad C_h=\sum_{i=0}^{m}(\sum_{j=0}^{m}a_{hj}e_j^i)C_i=\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^iC_i)
⇔根据加法交换律有:Ch=∑i=0m(∑j=0mahjeji)Ci=∑j=0mahj(∑i=0mejiCi)
∵
C
i
=
r
i
H
+
x
⃗
i
G
⃗
,
z
⃗
j
=
∑
i
=
0
m
e
j
i
x
⃗
i
,
s
j
=
∑
i
=
0
m
e
j
i
r
i
,
以
及
加
法
结
合
律
\because C_i=r_iH+\vec x_i\vec G, \quad \vec z_j=\sum_{i=0}^{m}e_j^i\vec x_i, \quad s_j=\sum_{i=0}^{m}e_j^ir_i, \quad 以及加法结合律
∵Ci=riH+x
∴
C
h
=
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
(
r
i
H
+
x
⃗
i
G
⃗
)
)
=
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
r
i
H
)
+
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
x
⃗
i
G
⃗
)
=
∑
j
=
0
m
a
h
j
s
j
H
+
∑
j
=
0
m
a
h
j
z
⃗
j
G
⃗
\therefore C_h=\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^i(r_iH+\vec x_i\vec G))=\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^ir_iH)+\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^i\vec x_i\vec G)=\sum_{j=0}^{m}a_{hj}s_jH+\sum_{j=0}^{m}a_{hj}\vec z_j\vec G
∴Ch=∑j=0mahj(∑i=0meji(riH+x
⇒
C
h
\Rightarrow C_h
⇒Chis a commitment to
∑
j
=
0
m
a
h
j
z
⃗
j
\sum_{j=0}^{m}a_{hj}\vec z_j
∑j=0mahjz
∵
C
h
=
r
h
H
+
x
⃗
h
G
⃗
，
以
及
有
且
仅
有
一
个
值
对
应
一
个
c
o
m
m
i
t
m
e
n
t
\because C_h=r_hH+\vec x_h\vec G，\quad以及有且仅有一个值对应一个commitment
∵Ch=rhH+x
⇒
x
⃗
h
=
∑
j
=
0
m
a
h
j
z
⃗
j
\Rightarrow \vec x_h=\sum_{j=0}^{m}a_{hj}\vec z_j
⇒x
以上公式推导可知，当有m+1个不同的方程式时，可以通过
(
z
⃗
0
,
z
⃗
1
,
z
⃗
2
,
.
.
.
,
z
⃗
m
)
(\vec z_0, \vec z_1, \vec z_2,...,\vec z_m)
(z
通过本算法，根据proof信息，可提取witness信息，且为唯一解，即保证了“knowledge-soundness”。由于解的唯一性，当Prover不知道解的情况下，无法提供可验证通过的proof。
3.2 Polynomial Interpolation多项式插值
Z
=
A
−
1
X
=
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
(
x
⃗
0
x
⃗
1
x
⃗
2
.
.
.
x
⃗
m
)
=
(
∑
i
=
0
m
e
0
i
x
⃗
i
∑
i
=
0
m
e
1
i
x
⃗
i
∑
i
=
0
m
e
2
i
x
⃗
i
.
.
.
∑
i
=
0
m
e
m
i
x
⃗
i
)
=
(
z
⃗
0
z
⃗
1
z
⃗
2
.
.
.
z
⃗
m
)
Z=A^{-1}X=\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}\begin{pmatrix} \vec x_0\\ \vec x_1\\ \vec x_2\\ ... \\ \vec x_m \end{pmatrix}=\begin{pmatrix} \sum_{i=0}^{m}e_0^i\vec x_i\\ \sum_{i=0}^{m}e_1^i\vec x_i\\ \sum_{i=0}^{m}e_2^i\vec x_i\\ ... \\ \sum_{i=0}^{m}e_m^i\vec x_i \end{pmatrix}=\begin{pmatrix} \vec z_0\\ \vec z_1\\ \vec z_2\\ ... \\ \vec z_m \end{pmatrix}
Z=A−1X=⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛x
以上公式，可抽象为一个多项式，该多项式的变量为e，系数分别为
x
⃗
0
,
x
⃗
1
,
x
⃗
2
,
.
.
.
,
x
⃗
m
\vec x_0, \vec x_1, \vec x_2,...,\vec x_m
x
Z
(
e
)
=
x
⃗
0
+
x
⃗
1
e
+
x
⃗
2
e
2
+
.
.
.
+
x
⃗
m
e
m
Z(e)=\vec x_0+\vec x_1e+\vec x_2e^2+...+\vec x_me^m
Z(e)=x
对
Z
(
e
)
Z(e)
Z(e)多项式的变量
e
e
e分别取m+1不同的值
e
0
,
e
1
,
e
2
,
.
.
.
,
e
m
e_0,e_1, e_2,...,e_m
e0,e1,e2,...,em,可通过Lagrange interpolation来唯一确定
Z
(
e
)
Z(e)
Z(e)多项式的系数
x
⃗
0
,
x
⃗
1
,
x
⃗
2
,
.
.
.
,
x
⃗
m
\vec x_0, \vec x_1, \vec x_2,...,\vec x_m
x
参考资料：
[1] .Groth/MatrixZK.pdf
[2] .pdf
椭圆曲线形式下的Pedersen commitment——vector commitment和polynomial commitment
1. 椭圆曲线下的Pedersen commitment
椭圆曲线下Pedersen commitment可用scalar multiplication of curve points来表示：
C
=
r
H
+
a
G
C=rH+aG
C=rH+aG
其中，
C
C
C为椭圆曲线上的一个点curve point，作为commitment；
a
a
a为commit to 的数值；
r
r
r为随机数，可提供隐藏功能；
G
G
G为所选择椭圆曲线广泛接受的generator；
H
H
H为椭圆曲线上的另一个点，且保证无任何可推导
q
q
q，使得
H
=
q
G
H=qG
H=qG，这个H与G直接无明确关系非常重要。
如需open commitment C C C，需要提供r值和a值。
Pedersen commitment具有加法同态性：
C
(
r
1
,
a
1
)
+
C
(
r
2
,
a
2
)
=
r
1
H
+
a
1
G
+
r
2
H
+
a
2
G
=
(
r
1
+
r
2
)
H
+
(
a
1
+
a
2
)
G
=
C
(
r
1
+
r
2
,
a
1
+
a
2
)
C(r_1,a_1)+C(r_2,a_2)=r_1H+a_1G+r_2H+a_2G=(r_1+r_2)H+(a_1+a_2)G=C(r_1+r_2,a_1+a_2)
C(r1,a1)+C(r2,a2)=r1H+a1G+r2H+a2G=(r1+r2)H+(a1+a2)G=C(r1+r2,a1+a2)
2. Vector Pedersen Commitment 向量commitment
C
=
r
H
+
(
v
1
G
1
+
v
2
G
2
+
.
.
.
.
+
v
n
G
n
)
=
r
H
+
v
⃗
G
⃗
C=rH+(v_1G_1+v_2G_2+....+v_nG_n)=rH+\vec v\vec G
C=rH+(v1G1+v2G2+....+vnGn)=rH+v
其中，各个
G
i
G_i
Gi可由
H
a
s
h
(
e
n
c
o
d
e
(
G
)
∣
∣
i
)
Hash(encode(G)||i)
Hash(encode(G)∣∣i)来获取。
如需open commitment
C
C
C，需要提供随机数r值和向量值
v
⃗
\vec v
v
向量值
v
⃗
\vec v
v
也可以同时对多个Vector进行commitment，如对
v
⃗
,
w
⃗
\vec v,\vec w
v
C
=
r
H
+
v
⃗
G
⃗
+
w
⃗
H
⃗
C=rH+\vec v\vec G+\vec w\vec H
C=rH+v
其中，各个
H
i
H_i
Hi可由
H
a
s
h
(
e
n
c
o
d
e
(
H
)
∣
∣
i
)
Hash(encode(H)||i)
Hash(encode(H)∣∣i)来获取，即curve point
H
H
H不在vector
H
⃗
\vec H
H
3. A zero knowledge argument of knowledge of a set of vectors——一系列向量的零知识证明
假设有m个向量
x
⃗
1
,
x
⃗
2
,
.
.
.
,
x
⃗
m
\vec x_1,\vec x_2, ..., \vec x_m
x
C
1
=
r
1
H
+
x
⃗
1
G
⃗
C_1=r_1H+\vec x_1 \vec G
C1=r1H+x
C
2
=
r
2
H
+
x
⃗
2
G
⃗
C_2=r_2H+\vec x_2 \vec G
C2=r2H+x
.
.
.
...
...
C
m
=
r
m
H
+
x
⃗
m
G
⃗
C_m=r_mH+\vec x_m \vec G
Cm=rmH+x
以下
P
P
P代表prover,
V
V
V代表Verifier。
a)
P
→
V
:
C
0
P \rightarrow V: C_0
P→V:C0 (a new commitment to a newly chosen random vector of dimension N)
b)
V
→
P
:
e
V \rightarrow P: e
V→P:e (a random scalar，也可称为challenge值。)
c)
P
→
V
:
(
z
⃗
,
s
)
P \rightarrow V: (\vec z, s)
P→V:(z
其中：
z
⃗
=
∑
i
=
0
m
e
i
x
⃗
i
,
s
=
∑
i
=
0
m
e
i
r
i
\vec z=\sum_{i=0}^{m}e^i\vec x_i, \quad s=\sum_{i=0}^{m}e^ir_i
z
通过随机数
e
e
e，可很好的隐藏向量
x
⃗
\vec x
x
有1*m维矩阵：
(
1
,
e
,
e
2
,
.
.
.
,
e
m
)
(1,e,e^2,...,e^m)
(1,e,e2,...,em)
使得z值无法获取相应的x值。
对于Verifier，只需验证：
∑
i
=
0
m
e
i
C
i
=
?
s
H
+
z
⃗
G
⃗
\sum_{i=0}^{m}e^iC_i=?sH+\vec z\vec G
∑i=0meiCi=?sH+z
证明过程如下：
s
H
+
z
⃗
G
⃗
=
∑
i
=
0
m
e
i
(
r
i
H
)
+
∑
i
=
0
m
e
i
x
⃗
i
G
⃗
=
∑
i
=
0
m
e
i
(
r
i
H
+
x
⃗
i
G
⃗
)
=
∑
i
=
0
m
e
i
C
i
sH+\vec z\vec G=\sum_{i=0}^{m}e^i(r_iH)+\sum_{i=0}^{m}e^i\vec x_i\vec G=\sum_{i=0}^{m}e^i(r_iH+\vec x_i\vec G)=\sum_{i=0}^{m}e^iC_i
sH+z
由以上证明可知，Verifer可根据信息
(
C
0
,
e
,
(
z
⃗
,
s
)
)
(C_0,e,(\vec z, s))
(C0,e,(z
但是对于不诚信的prover，他可以随机选择
e
,
(
z
⃗
,
s
)
e,(\vec z, s)
e,(z
使得
∑
i
=
0
m
e
i
C
i
=
C
0
+
∑
i
=
1
m
e
i
C
i
=
(
s
H
+
z
⃗
G
⃗
)
−
(
∑
i
=
1
m
e
i
C
i
)
+
∑
i
=
1
m
e
i
C
i
=
s
H
+
z
⃗
G
⃗
\sum_{i=0}^{m}e^iC_i=C_0+\sum_{i=1}^{m}e^{i}C_i=(sH+\vec z\vec G)-(\sum_{i=1}^{m}e^{i}C_i)+\sum_{i=1}^{m}e^{i}C_i=sH+\vec z\vec G
∑i=0meiCi=C0+∑i=1meiCi=(sH+z
若需要open此种情况下的commitment，需要提供 C 1 , C 2 , . . . C m C_1,C_2,...C_m C1,C2,...Cm对应的共m个scalar数 r 1 , r 2 , . . . , r m r_1,r_2,...,r_m r1,r2,...,rm，以及 m ∗ N m*N m∗N个向量元素 x 11 , x 12 , . . . , x m N x_{11},x_{12},...,x_{mN} x11,x12,...,xmN。
3.1 一系列向量的零知识证明的soundness验证
修改上面的流程，重复a)b)c)步骤m+1次，每次均为scalar e提供不同的随机值
e
j
e_j
ej：
(
C
0
,
0
,
e
0
,
(
z
⃗
0
,
s
0
)
)
(C_{0,0},e_0,(\vec z_0,s_0))
(C0,0,e0,(z
(
C
0
,
1
,
e
1
,
(
z
⃗
1
,
s
1
)
)
(C_{0,1},e_1,(\vec z_1,s_1))
(C0,1,e1,(z
(
C
0
,
2
,
e
2
,
(
z
⃗
2
,
s
2
)
)
(C_{0,2},e_2,(\vec z_2,s_2))
(C0,2,e2,(z
.
.
.
...
...
(
C
0
,
m
,
e
m
,
(
z
⃗
m
,
s
m
)
)
(C_{0,m},e_m,(\vec z_m,s_m))
(C0,m,em,(z
相应地：
z
⃗
j
=
∑
i
=
0
m
e
j
i
x
⃗
i
,
s
j
=
∑
i
=
0
m
e
j
i
r
i
,
其
中
j
∈
[
0
,
m
]
\vec z_j=\sum_{i=0}^{m}e_j^i\vec x_i, \quad s_j=\sum_{i=0}^{m}e_j^ir_i, \quad 其中j\in [0,m]
z
则 有(m+1)*(m+1)维矩阵：
A
−
1
=
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
A^{-1}=\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}
A−1=⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞
使得z值无法获取相应的x值。该矩阵为Vandermonde 矩阵。
若
e
0
,
e
1
,
.
.
.
,
e
m
e_0,e_1,...,e_m
e0,e1,...,em互异，则存在对应的逆矩阵为：
A
=
(
a
00
a
01
a
02
.
.
.
a
0
m
a
10
a
11
a
12
.
.
.
a
1
m
a
20
a
21
a
22
.
.
.
a
2
m
.
.
.
a
m
0
a
m
1
a
m
2
.
.
.
a
m
m
)
A=\begin{pmatrix} a_{00}& a_{01}& a_{02}&... &a_{0m} \\ a_{10}& a_{11}& a_{12}&... &a_{1m} \\ a_{20}& a_{21}& a_{22}&... &a_{2m} \\ ...& & & & \\ a_{m0}& a_{m1}& a_{m2}&... &a_{mm} \end{pmatrix}
A=⎝⎜⎜⎜⎜⎛a00a10a20...am0a01a11a21am1a02a12a22am2............a0ma1ma2mamm⎠⎟⎟⎟⎟⎞
相应的Z也为矩阵，满足：
Z
=
A
−
1
X
=
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
(
x
⃗
0
x
⃗
1
x
⃗
2
.
.
.
x
⃗
m
)
=
(
∑
i
=
0
m
e
0
i
x
⃗
i
∑
i
=
0
m
e
1
i
x
⃗
i
∑
i
=
0
m
e
2
i
x
⃗
i
.
.
.
∑
i
=
0
m
e
m
i
x
⃗
i
)
=
(
z
⃗
0
z
⃗
1
z
⃗
2
.
.
.
z
⃗
m
)
Z=A^{-1}X=\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}\begin{pmatrix} \vec x_0\\ \vec x_1\\ \vec x_2\\ ... \\ \vec x_m \end{pmatrix}=\begin{pmatrix} \sum_{i=0}^{m}e_0^i\vec x_i\\ \sum_{i=0}^{m}e_1^i\vec x_i\\ \sum_{i=0}^{m}e_2^i\vec x_i\\ ... \\ \sum_{i=0}^{m}e_m^i\vec x_i \end{pmatrix}=\begin{pmatrix} \vec z_0\\ \vec z_1\\ \vec z_2\\ ... \\ \vec z_m \end{pmatrix}
Z=A−1X=⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛x
即相当于求m+1个方程式，存在唯一解
(
x
⃗
0
,
x
⃗
1
,
.
.
.
,
x
⃗
m
)
(\vec x_0, \vec x_1,..., \vec x_m)
(x
若 e 0 , e 1 , . . . , e m e_0,e_1,...,e_m e0,e1,...,em不互异，则可逆矩阵A不存在，也不能保证解的唯一性。
根据矩阵基础知识，矩阵B存在可逆矩阵的充分必要条件为B的判别式不为零，即det|B|!=0。
A的可逆矩阵A-1之间的关系有：
A
A
−
1
=
I
,
I
为
单
位
矩
阵
AA^{-1}=I,I为单位矩阵
AA−1=I,I为单位矩阵，即：
A
A
−
1
=
(
a
00
a
01
a
02
.
.
.
a
0
m
a
10
a
11
a
12
.
.
.
a
1
m
a
20
a
21
a
22
.
.
.
a
2
m
.
.
.
a
m
0
a
m
1
a
m
2
.
.
.
a
m
m
)
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
=
(
1
0
0
.
.
.
0
0
1
0
.
.
.
0
0
0
1
.
.
.
0
.
.
.
0
0
0
.
.
.
1
)
=
(
δ
00
δ
01
δ
02
.
.
.
δ
0
m
δ
10
δ
11
δ
12
.
.
.
δ
1
m
δ
20
δ
21
δ
22
.
.
.
δ
2
m
.
.
.
δ
m
0
δ
m
1
δ
m
2
.
.
.
δ
m
m
)
AA^{-1}=\begin{pmatrix} a_{00}& a_{01}& a_{02}&... &a_{0m} \\ a_{10}& a_{11}& a_{12}&... &a_{1m} \\ a_{20}& a_{21}& a_{22}&... &a_{2m} \\ ...& & & & \\ a_{m0}& a_{m1}& a_{m2}&... &a_{mm} \end{pmatrix}\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}=\begin{pmatrix} 1& 0& 0 &... &0 \\ 0& 1& 0 &... &0 \\ 0& 0& 1 &... &0 \\ ...& & & & \\ 0& 0& 0 &... &1 \end{pmatrix}=\begin{pmatrix} \delta _{00}& \delta _{01}& \delta _{02} &... &\delta _{0m} \\ \delta _{10}& \delta _{11}& \delta _{12} &... &\delta _{1m} \\ \delta _{20}& \delta _{21}& \delta _{22} &... &\delta _{2m} \\ ...& & & & \\ \delta _{m0}& \delta _{m1}& \delta _{m2} &... &\delta _{mm} \end{pmatrix}
AA−1=⎝⎜⎜⎜⎜⎛a00a10a20...am0a01a11a21am1a02a12a22am2............a0ma1ma2mamm⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎛100...001000010............0001⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎛δ00δ10δ20...δm0δ01δ11δ21δm1δ02δ12δ22δm2............δ0mδ1mδ2mδmm⎠⎟⎟⎟⎟⎞
上面公式中，
e
j
e_j
ej为challenge值，有：
δ
h
i
=
∑
j
=
0
m
a
h
j
e
j
i
\delta _{hi}=\sum_{j=0}^{m}a_{hj}e_j^i
δhi=∑j=0mahjeji
当 h = = i h==i h==i时，有 δ h i = 1 \delta _{hi}=1 δhi=1；当 h ! = i h!=i h!=i时，有 δ h i = 0 \delta _{hi}=0 δhi=0。也可称 δ h i \delta _{hi} δhi为Kronecker delta函数。
基于
δ
h
i
\delta _{hi}
δhi的特性，有：
C
h
=
∑
i
=
0
m
δ
h
i
C
i
C_h=\sum_{i=0}^{m}\delta _{hi}C_i
Ch=∑i=0mδhiCi
⇔
C
h
=
∑
i
=
0
m
δ
h
i
C
i
=
∑
i
=
0
m
(
∑
j
=
0
m
a
h
j
e
j
i
)
C
i
\Leftrightarrow C_h=\sum_{i=0}^{m}\delta _{hi}C_i=\sum_{i=0}^{m}(\sum_{j=0}^{m}a_{hj}e_j^i)C_i
⇔Ch=∑i=0mδhiCi=∑i=0m(∑j=0mahjeji)Ci
⇔
根
据
加
法
交
换
律
有
:
C
h
=
∑
i
=
0
m
(
∑
j
=
0
m
a
h
j
e
j
i
)
C
i
=
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
C
i
)
\Leftrightarrow 根据加法交换律有: \quad C_h=\sum_{i=0}^{m}(\sum_{j=0}^{m}a_{hj}e_j^i)C_i=\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^iC_i)
⇔根据加法交换律有:Ch=∑i=0m(∑j=0mahjeji)Ci=∑j=0mahj(∑i=0mejiCi)
∵
C
i
=
r
i
H
+
x
⃗
i
G
⃗
,
z
⃗
j
=
∑
i
=
0
m
e
j
i
x
⃗
i
,
s
j
=
∑
i
=
0
m
e
j
i
r
i
,
以
及
加
法
结
合
律
\because C_i=r_iH+\vec x_i\vec G, \quad \vec z_j=\sum_{i=0}^{m}e_j^i\vec x_i, \quad s_j=\sum_{i=0}^{m}e_j^ir_i, \quad 以及加法结合律
∵Ci=riH+x
∴
C
h
=
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
(
r
i
H
+
x
⃗
i
G
⃗
)
)
=
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
r
i
H
)
+
∑
j
=
0
m
a
h
j
(
∑
i
=
0
m
e
j
i
x
⃗
i
G
⃗
)
=
∑
j
=
0
m
a
h
j
s
j
H
+
∑
j
=
0
m
a
h
j
z
⃗
j
G
⃗
\therefore C_h=\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^i(r_iH+\vec x_i\vec G))=\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^ir_iH)+\sum_{j=0}^{m}a_{hj}(\sum_{i=0}^{m}e_j^i\vec x_i\vec G)=\sum_{j=0}^{m}a_{hj}s_jH+\sum_{j=0}^{m}a_{hj}\vec z_j\vec G
∴Ch=∑j=0mahj(∑i=0meji(riH+x
⇒
C
h
\Rightarrow C_h
⇒Chis a commitment to
∑
j
=
0
m
a
h
j
z
⃗
j
\sum_{j=0}^{m}a_{hj}\vec z_j
∑j=0mahjz
∵
C
h
=
r
h
H
+
x
⃗
h
G
⃗
，
以
及
有
且
仅
有
一
个
值
对
应
一
个
c
o
m
m
i
t
m
e
n
t
\because C_h=r_hH+\vec x_h\vec G，\quad以及有且仅有一个值对应一个commitment
∵Ch=rhH+x
⇒
x
⃗
h
=
∑
j
=
0
m
a
h
j
z
⃗
j
\Rightarrow \vec x_h=\sum_{j=0}^{m}a_{hj}\vec z_j
⇒x
以上公式推导可知，当有m+1个不同的方程式时，可以通过
(
z
⃗
0
,
z
⃗
1
,
z
⃗
2
,
.
.
.
,
z
⃗
m
)
(\vec z_0, \vec z_1, \vec z_2,...,\vec z_m)
(z
通过本算法，根据proof信息，可提取witness信息，且为唯一解，即保证了“knowledge-soundness”。由于解的唯一性，当Prover不知道解的情况下，无法提供可验证通过的proof。
3.2 Polynomial Interpolation多项式插值
Z
=
A
−
1
X
=
(
1
e
0
e
0
2
.
.
.
e
0
m
1
e
1
e
1
2
.
.
.
e
1
m
1
e
2
e
2
2
.
.
.
e
2
m
.
.
.
1
e
m
e
m
2
.
.
.
e
m
m
)
(
x
⃗
0
x
⃗
1
x
⃗
2
.
.
.
x
⃗
m
)
=
(
∑
i
=
0
m
e
0
i
x
⃗
i
∑
i
=
0
m
e
1
i
x
⃗
i
∑
i
=
0
m
e
2
i
x
⃗
i
.
.
.
∑
i
=
0
m
e
m
i
x
⃗
i
)
=
(
z
⃗
0
z
⃗
1
z
⃗
2
.
.
.
z
⃗
m
)
Z=A^{-1}X=\begin{pmatrix} 1& e_0& e_0^2 &... &e_0^m \\ 1& e_1& e_1^2 &... &e_1^m\\ 1& e_2& e_2^2 &... &e_2^m\\ ...& & & & \\ 1& e_m& e_m^2 &... &e_m^m \end{pmatrix}\begin{pmatrix} \vec x_0\\ \vec x_1\\ \vec x_2\\ ... \\ \vec x_m \end{pmatrix}=\begin{pmatrix} \sum_{i=0}^{m}e_0^i\vec x_i\\ \sum_{i=0}^{m}e_1^i\vec x_i\\ \sum_{i=0}^{m}e_2^i\vec x_i\\ ... \\ \sum_{i=0}^{m}e_m^i\vec x_i \end{pmatrix}=\begin{pmatrix} \vec z_0\\ \vec z_1\\ \vec z_2\\ ... \\ \vec z_m \end{pmatrix}
Z=A−1X=⎝⎜⎜⎜⎜⎛111...1e0e1e2eme02e12e22em2............e0me1me2memm⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛x
以上公式，可抽象为一个多项式，该多项式的变量为e，系数分别为
x
⃗
0
,
x
⃗
1
,
x
⃗
2
,
.
.
.
,
x
⃗
m
\vec x_0, \vec x_1, \vec x_2,...,\vec x_m
x
Z
(
e
)
=
x
⃗
0
+
x
⃗
1
e
+
x
⃗
2
e
2
+
.
.
.
+
x
⃗
m
e
m
Z(e)=\vec x_0+\vec x_1e+\vec x_2e^2+...+\vec x_me^m
Z(e)=x
对
Z
(
e
)
Z(e)
Z(e)多项式的变量
e
e
e分别取m+1不同的值
e
0
,
e
1
,
e
2
,
.
.
.
,
e
m
e_0,e_1, e_2,...,e_m
e0,e1,e2,...,em,可通过Lagrange interpolation来唯一确定
Z
(
e
)
Z(e)
Z(e)多项式的系数
x
⃗
0
,
x
⃗
1
,
x
⃗
2
,
.
.
.
,
x
⃗
m
\vec x_0, \vec x_1, \vec x_2,...,\vec x_m
x
参考资料：
[1] .Groth/MatrixZK.pdf
[2] .pdf