零知识证明学习（三）—— 非交互式零知识证明(zkSNARKs)
非交互式零知识证明
本节主要介绍一种新的零知识证明-
z
k
S
N
A
R
K
zkSNARK
zkSNARK，
z
k
S
N
A
R
K
：
z
e
r
o
−
k
n
o
w
l
e
d
g
e
S
u
c
c
i
n
c
t
N
o
n
−
I
n
t
e
r
a
c
t
i
v
e
A
r
g
u
m
e
n
t
s
o
f
K
n
o
w
l
e
d
g
e
zkSNARK：zero-knowledge Succinct Non-Interactive Arguments of Knowledge
zkSNARK：zero−knowledgeSuccinctNon−InteractiveArgumentsofKnowledge。
背景
z
k
S
N
A
R
K
zkSNARK
zkSNARK是零知识证明中最经典的加密算法体系。目前已经被应用在很多地方，特别是在区块链领域，包括实际生活中隐私保护相关的应用。
Z
e
r
o
−
K
n
o
w
l
e
d
g
e
Zero-Knowledge
Zero−Knowledge: 零知识证明体系里有两个角色，一个是证明者(Prover)， 一个是验证者(Verifier)。举个例子，比特币创始人中本聪身份不明，之前传出过很多人声称自己是中本聪最后都不了了之。那么一个人如何证明自己是中本聪呢？因为大家知道中本聪钱包的地址。因此他只需要用这个钱包的私钥对这句话签名 “我是XXX，我其实就是中本聪"。然后其他人(Verifier) 都可以用中本聪钱包的公钥对这个签名进行验证。这个就是一个零知识证明。首先只有私钥持有方的签名才能通过验证，其次这个签名没有泄漏私钥的任何信息，钱包不会被其他人盗用。因此零知识证明解决了两个问题，一个是信任问题，一个是隐私问题。
S
u
c
c
i
n
c
t
Succinct
Succinct：是指对于一个很复杂的问题，验证者可能需要进行很长时间的计算才能提供出相应的证明，但是我们希望证明的大小不要太大 (比如实际应用中只有几十
k
b
kb
kb)，同时验证者只需要很少的时间(比如微秒级别的时间) 就能够验证计算是否正确。
N
o
n
−
I
n
t
e
r
a
c
t
i
v
e
Non-Interactive
Non−Interactive：是指在证明的过程中双方不需要互相交换信息。有一些算法体系需要证明者和验证者之间互相对话几次，交换信息。这对于实际应用就很不方便，增加了系统特别是网络通讯的复杂度。因此最好的情况是证明者一次性地把证明发送给验证者，验证者直接验证即可。
A
r
g
u
m
e
n
t
o
f
K
n
o
w
l
e
d
g
e
Argumentquad of quad Knowledge
ArgumentofKnowledge：指的是证明者只有知道问题的答案才可能提供证明。这个比较绕口，另一个解释就是证明者造假成功的概率可以忽略不计。这里还有一个类似的概念 Proof of Knowledge。它们之间是有区别的。对于Argument来说，证明者的计算能力有限，也就是多项式的算力，而Proof of Knowledge则对证明者计算能力没有要求。比如一个验证者是从未来穿越回来，带着最先进的量子计算机，那么对于Proof of Knolwege的系统，他仍然没法造假。但是对于Argument of Knowledge的系统则有可能。简单的说就是：proof（证明）和argument（论证）在零知识证明里，是有区别的，在proof system中，即便是计算能力无限的prover也没法欺骗verifier去相信一个错误的陈述为真（统计可靠性），而在argument system中，只有多项式时间计算能力的没法欺骗（计算可靠性），假设能破解椭圆曲线离散对数问题，那么可能就不再安全。
多项式知识的证明（Proving Knowledge of a Polynomial）
我们从一个证明多项式知识的问题开始，然后使用一般方法。我们还会发现多项式的其他性质。
到目前为止，问题集中在一个薄弱的证明概念上，各方必须相互信任。例如，证明者不需要知道多项式，他可以使用任何其他可用的方法来得出正确的结果。而且，如果验证者多项式求值的范围并不大，她可能有概率会猜到一个数，这个概率是无法忽视的。接下来我们来处理这个缺陷，但首先要清楚的分析多项式的性质。一个多项式表达形式如下（n阶多项式）：
c
n
x
n
+
.
.
.
+
c
1
x
1
+
c
0
x
0
c_nx^n+...+c_1x^1+c_0x^0
cnxn+...+c1x1+c0x0
如果证明者或者验证者知道是1阶多项式（
c
1
x
1
+
c
0
c_1x^1+c_0
c1x1+c0），那意味着他们知道该多项式系统为
c
1
,
c
0
c_1,c_0
c1,c0，而且系数可能为任意值。代数基本定理指出，任何多项式都可以分解成线性多项式(即，1阶多项式代表一条直线)，只要它是可解的。因此，我们可以将任何有效多项式表示为线性多项式的乘积：
(
x
−
a
0
)
(
x
−
a
1
)
.
.
.
(
x
−
a
n
)
=
0
(x-a_0)(x-a_1)...(x-a_n)=0
(x−a0)(x−a1)...(x−an)=0
从上式看出一个多项式可以由多个1阶多项式组成。例如多项式
x
3
−
3
x
2
+
2
x
x^3-3x^2+2x
x3−3x2+2x分解为
(
x
−
0
)
(
x
−
1
)
(
x
−
2
)
(x-0)(x-1)(x-2)
(x−0)(x−1)(x−2)。从分解的多项式可以明显的看出解为
0
,
1
,
2
0,1,2
0,1,2，你可以很容易地在多项式的任意一种形式上检查这个解，但是分解形式在表面上有所有以上的解(也称为根)。
假设证明者声明，他知道一个3次多项式的根是1和2，这意味着他的多项式具有这种形式：
(
x
−
1
)
(
x
−
2
)
.
.
.
(x-1)(x-2)...
(x−1)(x−2)...，换句话说，
(
x
−
1
)
(x-1)
(x−1)和
(
x
−
2
)
(x-2)
(x−2)可以看作多项式
x
3
−
3
x
2
+
2
x
x^3-3x^2+2x
x3−3x2+2x的余子式。因此，如果证明者想要证明他声明的多项式有这些根，但又不想揭露多项式本身，他需要证明他的多项式
p
(
x
)
p(x)
p(x)是这些余子式
t
(
x
)
=
(
x
−
1
)
(
x
−
2
)
t(x)=(x-1)(x-2)
t(x)=(x−1)(x−2)的乘积，所以存在任意多项式
h
(
x
)
h(x)
h(x)有以下形式：
p
(
x
)
=
t
(
x
)
h
(
x
)
p(x) = t(x)h(x)
p(x)=t(x)h(x)
因此，多项式多项式
p
(
x
)
p(x)
p(x)是由多项式
t
(
x
)
t(x)
t(x)和多项式
h
(
x
)
h(x)
h(x)乘积等到，多项式
p
(
x
)
p(x)
p(x)包含多项式
t
(
x
)
t(x)
t(x)。
如何得到多项式
h
(
x
)
h(x)
h(x)，这里我们很自然想到
h
(
x
)
=
p
(
x
)
t
(
x
)
h(x)=frac{p(x)}{t(x)}
h(x)=t(x)p(x)，如果证明者不能找到多项式
h
(
x
)
h(x)
h(x)，这意味着多项式
p
(
x
)
p(x)
p(x)并没有多项式
t
(
x
)
t(x)
t(x)余子式，这也以为多项式除法有余数。这里举个小例子：
p
(
x
)
=
x
3
−
3
x
2
+
2
x
p(x)=x^3-3x^2+2x
p(x)=x3−3x2+2x，
t
(
x
)
=
(
x
−
1
)
(
x
−
2
)
=
x
2
−
3
x
+
2
t(x)=(x-1)(x-2)=x^2-3x+2
t(x)=(x−1)(x−2)=x2−3x+2，这里很容易得到
h
(
x
)
=
x
h(x)=x
h(x)=x。
证明者和验证者具体验证协议如下：
- 验证者随机选取一个值
r
r
r，计算t
=
t
(
r
)
t=t(r)
t=t(r)，并把r
r
r发送给证明者 - 证明者计算
h
(
x
)
=
p
(
x
)
t
(
x
)
h(x)=frac{p(x)}{t(x)}
h(x)=t(x)p(x)，将p
(
r
)
p(r)
p(r)和h
(
r
)
h(r)
h(r)值发送给验证者 - 验证者检查
p
=
t
×
h
p=ttimes h
p=t×h，如果多项式相等，意味着多项式p
(
x
)
p(x)
p(x)有t
(
x
)
t(x)
t(x)余子式
这里还需要介绍一种情况，如果证明者使用不同的
p
′
(
x
)
pprime (x)
p′(x)，它没有必要的代数余子式,，例如：
p
′
(
x
)
=
2
x
3
−
3
x
2
+
2
x
pprime (x)=2x^3-3x^2+2x
p′(x)=2x3−3x2+2x，这里我们可以得到
p
′
(
x
)
=
t
(
x
)
×
(
2
x
+
3
)
+
7
x
−
6
pprime (x)=t(x)times (2x+3) +7x-6
p′(x)=t(x)×(2x+3)+7x−6。因此证明者整除将会有余数，所以我们将式子
p
′
(
x
)
=
t
(
x
)
×
(
2
x
+
3
)
+
7
x
−
6
pprime (x)=t(x)times (2x+3) +7x-6
p′(x)=t(x)×(2x+3)+7x−6整除
t
(
x
)
t(x)
t(x)得到
h
(
x
)
=
2
x
+
3
+
7
x
−
6
t
(
x
)
h(x)=2x+3+frac{7x-6}{t(x)}
h(x)=2x+3+t(x)7x−6。因为x是由验证者随机选择的,有一个低概率概率余数
7
x
−
6
7x-6
7x−6被
t
(
x
)
t(x)
t(x)整除,如果验证者检查
p
(
x
)
,
h
(
x
)
p(x),h(x)
p(x),h(x)必须是整数,这样的证明将被拒绝。但是，该检查要求多项式系数也是整数，这对协议造成了很大的限制。因此，这就是引入密码原语的原因，这使得这种除法不可能实现，即使原始的计算结果碰巧是可除的。
问题（issues）
- 证明者可能不知道声明的多项式
p
(
x
)
p(x)
p(x)，他可以计算t
=
t
(
r
)
t=t(r)
t=t(r)，并选择一个随机数h
h
h，计算p
=
t
×
h
p=t times h
p=t×h，验证者接收到值是正确的。 - 证明者知道随机点
x
=
r
x=r
x=r，他能构造任意多项式在r
r
r处有一个共享点与t
(
r
)
×
h
(
r
)
t(r) times h(r)
t(r)×h(r)。 - 在初始情况下，证明者声称知道一个特定次数的多项式，在当前的协议中没有阶数的强调。因此，证明者可以利用一个满足余子式检查的高次多项式进行欺骗。
这里说明一下，零知识证明的研究方向，本文主要一环扣一环的讲解，希望有兴趣的朋友能耐心读下去。