【密码学】零知识证明 zk-SNARK

2020-12-17密码学

零知识证明（zk-SNARK）

1.零知识证明的作用

在区块链的世界中，用地址来表示交易双方，这样达到了匿名的作用。然而，链上的信息虽然是匿名的，但是通过链上信息绑定的链下信息，像很多交易所都绑定了链上地址与链下的银行账户、支付宝，使得可以很方便的追溯真实世界的交易双方，使得匿名性荡然无存。
零知识证明是由S.Goldwasser、S.Micali及 C.Rackoff在20世纪80年代初提出的。能够在隐藏发送方、接受方以及交易金额等其他细节的情况下，保证交易有效。

2.零知识证明原理

以多项式方程$x^2+2x + 1= 9$为例，该方程的解为2。若Alice知道这个方程的解，那么他为了证明这一点，除了直接将解公布出来，并没有其它好的方法。那么需要将该问题进行转化。

2.1 问题转化

在计算该方程的过程中，首先需要将其转化为若干个简单问题，若t为临时变量，则原式变为：

$t_1 = x*x\\ t_2 = 2*x\\ t_3 = t_1+t_2\\ out = t_3+1$

定义解向量为 $s=[one,x,out,t_1,t_2,t_3]$，其中one代表1，并将每个等式变为 $s\cdot c =s\cdot a * s\cdot b$ ，则等式 $t_1 = x*x$ 变为：

$\begin{bmatrix} one\\ x \\ out\\ t_1 \\t_2 \\t_3 \end{bmatrix}\cdot \begin{bmatrix} 0\\ 0 \\ 0\\ 1 \\0 \\0 \end{bmatrix}=\begin{bmatrix} one\\ x \\ out\\ t_1 \\t_2 \\t_3 \end{bmatrix}\cdot \begin{bmatrix} 0\\ 1 \\ 0\\ 0 \\0 \\0 \end{bmatrix}*\begin{bmatrix} one\\ x \\ out\\ t_1 \\t_2 \\t_3 \end{bmatrix}\cdot \begin{bmatrix} 0\\ 1 \\ 0\\ 0 \\0 \\0 \end{bmatrix}$

其他等式以同样的方式进行变化，该方程的解即为满足所有转换后的等式的向量s，即$[one,x,out,t_1,t_2,t_3]=[1,2,9,4,4,8]$。将各个转换后的等式a向量，b向量，c向量转置后组合成一个矩阵，该结果为：

$C = \begin{bmatrix} 0 &0 &0 &1 &0 &0 \\ 0 &0 &0 &0 &1 &0 \\ 0 &0 &0 &0 &0 &1 \\ 0 &0 &1 &0 &0 &0 \end{bmatrix},A = \begin{bmatrix} 0 &1 &0 &0 &0 &0 \\ 2 &0 &0 &0 &0 &0 \\ 0 &0 &0 &1 &1 &0 \\ 1 &0 &0 &0 &0 &1 \end{bmatrix},B = \begin{bmatrix} 0 &1 &0 &0 &0 &0 \\ 0 &1 &0 &0 &0 &0 \\ 1 &0 &0 &0 &0 &0 \\ 1 &0 &0 &0 &0 &0 \end{bmatrix}$

对每个矩阵的每一列分别作拉格朗日插值法，如C矩阵第一列插值的结果为$C_1(n)=0$，第三列插值结果为$C_3(n)=\frac{1}{6}n^3-n^2+\frac{11}{6}n-1$，即 $C_3(1)=0, C_3(2)=0, C_3(3)=0, C_3(4)=1$。以此类推。

那么矩阵$A,B,C$转换成了三个方程组：

$A(n) = [A_1(n),A_2(n),A_3(n),A_4(n),A_5(n),A_6(n)]\\ B(n) = [B_1(n),B_2(n),B_3(n),B_4(n),B_5(n),B_6(n)]\\ C(n) = [C_1(n),C_2(n),C_3(n),C_4(n),C_5(n),C_6(n)]$

求解原等式的问题转化为求解向量s，使$s\cdot C_i(n)-s\cdot A_i(n)*s\cdot B_i(n) = 0$, 在n取1，2，3，4时都成立。这等价于：

$s\cdot C(n)-s\cdot A(n)*s\cdot B(n) = H(n)*Z(n)\\ 其中Z(n)=(n-1)(n-2)(n-3)(n-4)$

设 $P(n)=s\cdot C(n)-s\cdot A(n)*s\cdot B(n)=H(n)*Z(n)$ , 为了证明自己知道该方程的解s，Alice只要将s带入$P(n)$，将求得的解除以$Z(n)$得到多项式$H(n)$,此时只需将$P(n)$与$H(n)$发给验证者，验证者Bob使用$Z(n)*H(n)$检查是否与$P(n)$相等，即可判断对方是否有正确的解。

（本人此时的问题1）：为什么只需检查Z(n)*H(n)是否与P(n)相等就能证明Alice是否知道解$s$呢，如果Alice随便带入一个解$s’$计算出$P’(n)$，并除以$Z(n)$得到$H’(n)$，发给Bob。此时Bob也可以计算出$Z(n)*H(n)=P(n)$，不就会得到Alice知道解这个错误的结论吗。

因为$Z(n)$在$n=1,2,3,4$时为0，只有当$P(n)$也在$n=1,2,3,4$时为0，$P(n)$才可以除以$Z(n)$，否则无法做除法。实际上只有特定的解向量$s$可以做到$P(n)$在$n=1,2,3,4$时为0，其他的任何$s’$都不行。因为每个$s$对应着原问题的一个$x$，若其他$s’$使$P(n)$在$n=1,2,3,4$时为0，说明原问题有另一个解$x$。但在实际应用中，原问题只会有一个特定的解。

（本人此时的问题2）：原问题是公开的，那么Bob也可以计算出A，B，C方程组，那么Bob能否根据传输的$P(n)$和A,B,C方程组推算出解$s$呢。如果可以推算出$s$，就违背了Alice不能公开$s$的约定了。

但这是一个NP问题，Bob想根据$P(n)$解出$s$的计算量与直接求解原问题的解$x$的计算量相同。（本文例子比较简单，实际上在使用零知识证明时，原问题的次数高达几百万）。NP问题的特点就是容易“验证”，不易“求解”，所以Bob只能验证$Z(n)*H(n)=P(n)$。

（本人此时的问题3）：如何确定Alice传输的$P(n)$一定是根据当前的原问题计算出来的。如果Alice使用另一个原问题计算出$P(n)$，Bob也可以验证Alice知道答案，但Bob无法确定Alice知道的是哪一个问题的答案。

目前的计算方式还无法判断，后面的KCA（Knowledge of Coefficient Test and Assumption）会解决这个问题。

但在实际中，多项式$P(n)$的次数是很高的，在工作中要传输大量数据，效率不高，需要改变传输内容。

2.2 抽样验证

可以使用抽样的方式加快这个过程。Bob可以取一个随机抽样点$t$告诉Alice，Alice计算$P(t)$和$H(t)$将结果发给Bob，接下来Bob判断 $Z(t)*H(t)$ 是否等于 $P(t)$ 。但Alice如果不知道解$s$，并随便带入解$s’$计算出$P’(n)$，并设计一个$H’(n)$使两者在抽样点$t$处满足$P’(n)=H’(n)*Z(n)$。所以Bob需要不让Alice知道抽样点$t$的值，并让Alice计算出$P(t)$与$H(t)$,要做到这一点，要利用同态映射隐藏抽样点。

2.3 同态隐藏

首先找到一个同态映射$E$，Bob计算出抽样点$t$的一系列指数值$t^0,t^1\dots t^N$计算出$E(t^0),E(t^1)\dots E(t^N)$，发送给Alice。因为$P(t)$和$H(t)$是$t^0, t^1, t^2 \dots t^N$的线性组合，所以在计算$E(P(t))$和$E(H(t))$时，由于同态映射的性质，实际上是在做$E(t^0),E(t^1)\dots E(t^N)$的线性组合。并且Alice无法根据$E(t^0),E(t^1)\dots E(t^N)$推算出$t$。

将计算结果发给Bob，Bob检查$E(P(t))$是否等于$E(H(t)*Z(t))$来判断Alice是否得到了正确的$P(n)$和$H(n)$。

但现在仍然存在一个漏洞，假设Alice不知道该问题的答案$s$，而知道另一个问题的另一个答案$s’$，那么Alice也可以根据另一个问题的$E(P’(t))$和$E(H’(t))$，Bob收到是会验证为正确，但这个正确只能代表Alice知道某个问题的解，不能证明Alice知道这个特定问题的解。

2.4 KCA（Knowledge of Coefficient Test and Assumption）

若数对$(a,b)$满足$b=\alpha \cdot a$，称为一个$\alpha$对。在某些情况下，不能计算除法来求解$b/a=\alpha$（如椭圆曲线），那么给出若干$\alpha$对，仅可以通过将其对应数线性组合得到新的$\alpha$对。在这样的情况下，若Bob给Alice若干$\alpha$对，返回了一个新的$\alpha$对，那么Bob可以认为Alice是通过这些已知的$\alpha$对进行线性组合计算出来的。

那么Bob通过已知问题转化后得到的A，B，C多项式后，取三个随机数$\alpha_A,\alpha_B,\alpha_C$将，并传给Alice三组$\alpha$对：

$\begin{matrix} [(E(A_1(t)),E(\alpha_A A_1(t)))\dots(E(A_M(t)),E(\alpha_A A_M(t)))] \\ [(E(B_1(t)),E(\alpha_B B_1(t)))\dots(E(B_M(t)),E(\alpha_B B_M(t)))] \\ [(E(C_1(t)),E(\alpha_C C_1(t)))\dots(E(C_M(t)),E(\alpha_C C_M(t)))] \end{matrix}$

Alice要根据这些$\alpha$对计算出新的$\alpha$对，那么只能通过线性组合：

$E(A_{total}(n)) = \Sigma a_i*E(A_i(n))\\ E(B_{total}(n)) = \Sigma b_i*E(B_i(n))\\ E(C_{total}(n)) = \Sigma c_i*E(C_i(n))$

Bob要求Alice根据收到的三组$\alpha$对，使用解向量s进行线性组合并返回三个$\alpha$对,即计算：

$A_{total}(n) = {s} \cdot A(n) = \Sigma s_i*A_i(n)\\ B_{total}(n) = {s} \cdot B(n) = \Sigma s_i*B_i(n)\\ C_{total}(n) = {s} \cdot C(n) = \Sigma s_i*C_i(n)$

并返回：

$(E(A_{total}(t)), E(α_AA_{total}(t)))\\ (E(B_{total}(t)), E(α_BB_{total}(t)))\\ (E(C_{total}(t)), E(α_CC_{total}(t)))$

不过Alice可以使用任意的系数做线性组合，所以Bob首先需要约束Alice使用同样的线性组合对这三组$\alpha$对进行计算，之后再约束Alice使用解向量$s$进行计算。设:

$L_i(n) = A_i(n) + B_i(n) + C_i(n) \\ L(n) = Σl_iL_i(n)$

那么当$a_i=b_i=c_i=l_i$时，有：

$L(n) = A_{total}(n)+B_{total}(n) + C_{total}(n)$

设$\beta$为随机数，那么有两组方法可以计算$E(βL(t))$,为：

$\begin{aligned} E(βL(t)) &= E(β*(A_{total}(t) + B_{total}(t) + C_{total}(t)))\\& = β*(E(A_{total}(t)) + E(B_{total}(t)) + E(C_{total}(t))) \end{aligned}$

和

$E(βL(t)) = Σl_iE(βL_i(t))$

若$\beta$对于Alice是未知的，那么只有当$a_i,b_i,c_i,l_i$相等时，即对$A_i,B_i,C_i,L_i$使用相同的线性组合，这两种计算$E(βL(t))$的结果对于任意采样点t相等。

因此，Bob需要发给Alice第四组数据：$E(βL_1(t)),E(βL_2(t))\dots E(βL_M(t))$，而Alice需要返回给Bob计算后的$E(βL(t))$,其中$l_i$要与$a_i,b_i,c_i$相等。Alice使用第二种方式计算$E(βL(t))$，Bob使用Alice返回的$A_{total},B_{total},C_{total}$使用第一种方式计算$E(βL(t))$。只要两种计算结果相同，则可以证明Alice使用相同的系数做线性组合运算。接下来要约束Alice使用解向量$s$做线性组合的系数。

使用上文提到的$E(t^0), E(t^1), E(t^2), …, E(t^N)$即可，若Alice使用解向量$s$作为线性组合的系数求解$A_{total},B_{total},C_{total}$，那么他们仍然满足$P(n)=C_{total}(n)−A_{total}(n)∗B_{total}(n) = s\cdot C(n)-s\cdot A(n) * s\cdot B(n)$。

所以用上文的方法，Alice需要计算$E(P(t)), E(H(t))$，Bob需要传给Alice第五组数据，即 $E(t^0), E(t^1), E(t^2), ..., E(t^N)$ 。

所以完整的KCA过程为：

1、Bob生成随机数$\alpha_A,\alpha_B,\alpha_C,\beta,t$
2、Bob给Alice传五组数据，分别为$(E(A_i(t)),E(\alpha_AA_i(t)))$，$(E(B_i(t)),E(\alpha_BB_i(t)))$，$(E(C_i(t)),E(\alpha_CC_i(t)))$，$E(βL_i(t))$和$E(t^i)$
3、Alice经过计算，传给Bob五个结果，分别为$(E(A_{total}(t)), E(α_AA_{total}(t)))$，$(E(B_{total}(t)), E(α_BB_{total}(t)))$，$(E(C_{total}(t)), E(α_CC_{total}(t)))$，$E(βL(t))$和$E(H(t))$
4、Bob依次验证
- (1)、检查返回的前三个对是否是$alpha$对。（确定是线性组合）
- (2)、Alice返回的$E(βL(t))$与自己计算的$E(βL(t))$值是否相同。（确定是同系数的线性组合）
- (3)、检查 $E(C_{total}(t)-A_{total}(t)*B_{total}(t))$ 是否等于$E(H(t)*Z(t))$。（确定使用解向量$s$做线性组合）

但是上述过程中，Bob需要向Alice传输过多的信息用来质询，传输开销过大。

2.5 共同参考数据集（CRS，Common Reference String）

可以预先使用某种可信的方式，将Bob用来质询Alice的数据提前计算好并公开，全体节点的共识。因此所有的质询过程全变成了向验证者提交证据即可。

对于Bob，如果每次需要验证的问题是一样的，那么需要传输的$(E(A_i(t)),E(\alpha_AA_i(t)))$，$(E(B_i(t)),E(\alpha_BB_i(t)))$，$(E(C_i(t)),E(\alpha_CC_i(t)))$，$E(βL_i(t))$和$E(t^i)$也不需要变化。那么这些内容就可以作为全体节点的共识，每次验证无需Bob先发送给Alice质询信息，而是Alice直接从上述第三步发送待验证信息即可。

但若如此，Bob也无法知道验证所需的随机数$\alpha_A,\alpha_B,\alpha_C,\beta$了。（共同参考集不是由Bob公开的，可能是更权威的机构公开的，Bob也只是负责验证而已，所以Bob也无法通过共同参考集来计算出随机数$\alpha_A,\alpha_B,\alpha_C,\beta$。）

这就需要引入另一个方法———双线性映射(bilinear map）：乘法的同态隐藏

2.5.1 双线性映射

双线性映射形如$e(X, Y) → Z$，同时具有以下特性：

$e(P+R, Q) = e(P, Q) + e(R, Q)\\ e(P, Q+S) = e(P, Q) + e(P, S)$

即在两个输入上都具备线性。

若$x$有两组不同的质因数分解：$x=ab=cd$，那么存在
有两个加法同态映射$E_1(x), E_2(y)$，和一个双线性映射$e$，使：

$e(E_1(a), E_2(b)) = e(E_1(c), E_2(d))$

于是基于共同参考集的零知识证明过程如下：
使用上述两个加法同态映射$E_1(x), E_2(y)$和一个双线性映射$e$：

定义共同参考集：
- $(E_1(A_i(t)),E_1(\alpha_AA_i(t)))$ (这里是$E_1$)
- $(E_2(B_i(t)),E_2(\alpha_BB_i(t)))$ (这里是$E_2$)
- $(E_1(C_i(t)),E_1(\alpha_CC_i(t)))$ (这里是$E_1$)
- $E_1(βL_i(t))$
- $E_1(t^i), E_2(t^i)$
- $E_1(\alpha_B), E_1(\beta)$
- $E_2(\alpha_A), E_2(\alpha_C),E_2(\beta)$
验证过程：
- Alice直接计算并发送：
  - 1、 $\left<\pi_A, \pi_A'\right> = \left<E_1(A_{total}(t), E_1(\alpha_A A_{total}(t))\right>$ (这里是$E_1$)
  - 2、 $\left<\pi_B, \pi_B'\right> = \left<E_2(B_{total}(t), E_2(\alpha_B B_{total}(t))\right>$ (这里是$E_2$)
  - 3、 $\left<\pi_C, \pi_C'\right> = \left<E_1(C_{total}(t), E_1(\alpha_C C_{total}(t))\right>$ (这里是$E_1$)
  - 4、$\pi_L’ = E_1(\beta L(t))$
  - 5、$\pi_H = E_1(H(t))$
- Bob收到Alice的验证请求，并开始验证：
  - 1、检查Alice是否返回三个$\alpha$对，确定是线性组合：
    - $e(\pi_A, E_2(\alpha_A))$ 是否等于 $e(\pi_A’, E_2(1))$ （其中$E_2(1)$来自于共同参考集中的$E_2(t^0)$，下同）
    - $e(E_1(\alpha_B), \pi_B)$ 是否等于 $e(E_1(1), \pi_B’)$
    - 3、$e(\pi_C, E_2(\alpha_C))$ 是否等于 $e(\pi_C’, E_2(1))$
  - 2、检测两种方法计算的$E(βL(t))$是否相同，确定是同系数的线性组合
    - 计算$e(\pi_L’, E_2(1))$ 是否等于 $e(\pi_A + \pi_C, E_2(\beta))+e(E_1(\beta), \pi_B)$
  - 3、验证Alice使用解向量s做线性组合
    - 计算 $E_2(Z(t)) = (t-1)(t-2)\dots(t-N)$ 为 $E_2(t^0)\dots E_2(t^N)$的线性组合。
    - 计算$e(\pi_C, E_2(1))$ 是否等于 $e(\pi_A, \pi_B)+ e(\pi_H, E_2(Z(t)))$
    - 注： $C(t) = A(t)*B(t) + H(t)*Z(t)$

3、参考文献

[1] A practical beginner’s guide to creating, proving, and verifying zkSNARKs in your contracts
[2] 区块链之零知识证明（zk-SNARK从小白到明白）（这是这篇文章的主要参考，本篇部分细节与原文有差异，本人认为原文可能有些错误，但原文没有开放评论，所以我只能将我的理解写在这篇文章里，欢迎留言讨论）