论文《Efficient zero-knowledge arguments in the discrete log setting,revisited (Full version)》发表于2019年8月31日。 相应的代码实现见：https://github.com/crate-crypto/qesa
根据第2.2节内容，qesa不需要trusted setup，需用到common reference string model（CRS）.
1. polynomial commitment
在本人代码库中create_lmpa_noZK()和verify_lmpa_noZK()函数对protocol 3.9中k值的选择做了更通用的实现，而不仅仅是针对k=2的情况。 对应的u_proof_Block中需要传递的group elements数量为：
[
2
(
k
−
1
)
+
1
]
m
log
k
n
[2(k-1)+1]m\log_{k}{n}
[2(k−1)+1]mlogkn，该算法的communication开销较大，与方程式的个数
m
m
m线性相关。
simple_zk.rs中的create()函数采用的是类似sigma-protocol的方式对witness
w
w
w来实现blinding (zero-knowledge)——
z
=
r
+
β
w
z=r+\beta w
z=r+βw。但是需要计算并传输
[
A
]
r
=
a
[A]r=a
[A]r=a开销很大。（Computing [A]r for random r is expensive.）
因为对blinding witness的计算复杂度较高，可考虑blinding the prover’s responses.
3. 巧妙的矩阵转换来表示二次方程式、Arithmetic circuit和R1CS
上图对应的可理解为：
(
1
w
⃗
T
)
(
0
0
−
c
⃗
a
⃗
b
⃗
T
)
(
1
w
⃗
)
\begin{pmatrix} 1 & \vec{w}^{T} \end{pmatrix}\begin{pmatrix} 0 & 0 \\ -\vec{c}& \vec{a}\vec{b}^{T} \end{pmatrix}\begin{pmatrix} 1 \\ \vec{w} \end{pmatrix}
(1w
T)(0−c
0a
b
T)(1w
)
⇒
(
w
⃗
T
a
⃗
)
(
b
⃗
T
w
⃗
)
−
c
⃗
T
w
⃗
=
0
\Rightarrow (\vec{w}^{T}\vec{a})(\vec{b}^{T}\vec{w})-\vec{c}^{T}\vec{w}=0
⇒(w
Ta
)(b
Tw
)−c
Tw
=0 
结合vitalik(Quadratic Arithmetic Programs: from zero to hero) 中gate 1的R1CS证明实现，见https://github.com/3for/qesa/blob/master/src/ipa/qesa_inner.rs中的test_create_qesa_inner_proof_vitalik_g1()，具体为：
Γ
i
=
(
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
−
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
)
\Gamma _i=\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}
Γi=⎝⎜⎜⎜⎜⎜⎜⎛000−100010000000000000000000000000000⎠⎟⎟⎟⎟⎟⎟⎞
w
T
=
(
1
3
r
a
n
d
o
m
9
r
a
n
d
o
m
r
a
n
d
o
m
)
w^T=\begin{pmatrix} 1 & 3 & random & 9 & random & random \end{pmatrix}
wT=(13random9randomrandom) 具有
w
T
Γ
i
w
=
0
⃗
w^T\Gamma_iw=\vec{0}
wTΓiw=0
。
算法设计得巧妙，不过verifier的计算复杂性相对于prover来说，减少得有限？
基于以上Matrix kernel assumption假设，所以有： 
参考资料： [1] 论文《Efficient zero-knowledge arguments in the discrete log setting,revisited (Full version)》 [2] https://github.com/topics/zero-knowledge?o=desc&s=stars
