# 深入简出zkSNARKs

原创作者：香橙@cyberorange。

###### tags: `zkSNARKs`, `Groth16`

## 1. 零知识证明初探

零知识证明是近几年密码学技术中最引人注目的技术之一，在区块链领域更是高频词，但是由于其涉及较多的数学知识，对一般的开发人员来说理解难度较大，而且资料多为英文，对国内区块链技术爱好者等学习可能造成困难。

所以我就综合论文和其他博客进行一个总结，外加点自己的理解成文，但因为我本身并非密码学专业，描述如有不当，请指正。

本文偏数学推导，非科普也不讲应用，感兴趣的话，可准备纸笔一路推导下去。

本文撰写前参考了Zcash博客，安比实验室博客，Vitalik等等许多博客以及多篇相关论文，但本文并非学术论文，所以就不一一列出引用了。

首先说说零知识证明，其实这个概念的出现已经很久了，零知识证明协议有很多种，zkSNARKs是目前应用最广泛的一种（包括各种改进方案），其他还有zk-STARKs、bulletproofs等等。

其基本概念就是一个证明者Prover向验证者Verifier证明某个陈述（Statement）是真是假，但在证明过程中不揭露任何其他信息。比如身份证明，某一个组织让组织内成员提供身份证明，但不想泄露任何信息，就可以使用零知识证明来完成。但是注意，这里的说的证明并非数学意义上命题证明意义上的证明，而是Prover去让Verifier相信某个陈述为真，属于概率证明，和数学推导的证明不一样。

目前，zcash，ethereum，filecoin等很多项目都使用了零知识证明来完成某些任务，比如隐私交易，链下交易验证，存储证明等等。

证明的简单形式化定义如下：设S是一个集合，那么一个（P,V)的证明系统必须满足下面的条件：

1）完备性（Completeness） $Prob[(P,V)(x) = Accept | x \in S] \geq \epsilon$

2. 正确性（Soundness） $ProbP,V = Accept | x \notin S] \leq \delta$

其中 $\epsilon \in (\frac{1}{2}, 1]$,$\delta \in [0,\frac{1}{2})$，分别为完备性概率和正确性概率，我们肯定是希望$\epsilon$越大越好，$\delta$越小越好。

简单解释，就是我们希望Prover拥有关于Statement的证据（Witness）的时候，Prover可以让Verifier相信陈述为真（完备性），而一个恶意的Prover将无法欺骗Verifier，来通过验证（正确性）。

那么，除了完备性和正确性以外，如何理解一个证明协议是否是零知识呢？

上面也说了，零知识要求证明者提供的证明除了可以验证陈述为真外，不会泄露任何信息，即证明本身在其概率空间内是均匀分布的（从熵来理解，即不包含任何信息冗余）。那么如何去定量地分析一个协议是否是零知识的？

对于零知识证明来说，证明其为零知识就需要为证明本身构造一个模拟器（Simulator），意思就是如果verifier不需要prover参与，可以自己构造出一个不可区分的证明出来的话，那么就能证明该协议是零知识的。

听起来有点绕，但逻辑很简单，就是如果不需要prover参与就可以构造证明的话，那这个过程本身就没有任何知识的参与，自然也就是零知识的，如果通过Simulator构造出来的证明，在概率分布上无法和prover提交的证明区分开，那么就相当于prover提交的证明也是零知识的。

举个例子，假设有AB两个电脑，我向A电脑输入一个字符串，B电脑自己生成随机串，如果两个字符串在概率分布上相同，则证明其实我什么有效信息也没有输进去，所以是零知识的。

下面举一个具体的例子。

- Schnorr协议
假设prover拥有私钥sk, pk = sk*G, G为椭圆曲线群上的一个生成元。
verifier拥有pk。
现在prover想向verifier证明自己拥有私钥，步骤如下：
1. 首先prover选取一个随机数k，并计算$K = k\cdot G$ ，将$K$发送给verifier；
1. verifier选取一随机数c发送给prover；
1. prover计算$r = k + c\cdot sk$，将r发送给verifier；
1. verifier验证$rG \space ?= \space K + c \cdot pk$。

由于椭圆曲线离散对数难题，有pk = sk * G，已知pk和G是无法逆推得sk的。

上面验证的关键在于Prover无法事先知道c，根据椭圆曲线离散对数难题，prover无法找到一对sk和k，使得计算的$r = k + c\cdot sk$满足验证，所以协议是满足正确性的。

而如果Prover确实知道sk，那么验证肯定是可以通过的，所以协议是满足完备性的。

但是如何证明上面的验证是零知识的呢？我们现在假设没有Prover参与，让Verifier在自娱自乐，去模拟一个零知识证明交互过程。

构造simulator： Verifier选取随机数c以及r，计算$K = rG-c\cdot pk$。此时全流程就已经被模拟出来了。

Prover发送的K，以及Verifier选取的c，最后响应的r都有了，但是这个过程本身并没有Prover参与，构造出来的证明与Prover的证明在概率上是无法区分的，所以协议本身是零知识的，而这个模拟器是依靠在发送k之前就已经知道c来构造的。

从上面的分析也可以看出，Prover一定不能事先知道c，否则也是可以模拟证明的，所以说上述零知识证明的关键就在于这个随机数。

## 2. NP与QAP

通俗来讲，P问题即为在多项式时间内可解的一类问题，而NP问题属于在多项式时间内不可解，但是给定一个解，可以在多项式时间内验证解是否正确的一类问题，此外还有NP完全问题，属于NP问题中最难的一种，任何NP问题都可以归约（Reduction）到一个NP完全问题，所以只要找到了一个NP完全问题的多项式时间解法，由于可以相互归约，相当于解决了所有的NP问题，这个问题我也不懂，就不多说了。

zkSNARKs是基于NP问题的，因为如果是一个P问题的话，那么直接求解就行了，证明就无从谈起，所以zkSNARKs的依托于某种NP问题，很难求解但是可以快速验证。

目前zkSNARKs使用最广泛的NP完全问题是QAP（Quadratic Arithmetic Program），我们可以很快的去验证解，而很难用有限资源去求解。

简单解释QAP即，给一系列的多项式以及一个目标多项式，是否能根据这一系列的多项式，求得它们的一个线性组合，刚好可以整除多项式。即如下描述：

- 给定一系列多项式$\{l_i(x),r_i(x),o_i(x)
\}_{i=0}^n$，目标t(x)
- 求一个线性组合 $\{a_i\}_{i=0}^n$ ,使得 $\sum_{i=0}^n a_i\times l_i(x) \cdot \sum_{i=0}^n a_i\times r_i(x)- \sum_{i=0}^n a_i\times o_i(x))=t(x)h(x)$ ,可记为 $L(X)\cdot R(x) - O(x) = t(x)h(x)$ 。

这个问题如果给出了一个解$\{a_i\}_{i=0}^n$，那么验证很简单，直接除t(x)即可验证是否满足，但是想求解就很难。

zkSNARKs的思路就是，将原问题的解转化为一个QAP问题的解，然后公开QAP问题，这样的话拥有解的人用证明公开自己拥有一个解，其他人可以简单验证证明是否成立。

当然，上面的描述过于笼统，而且也没有说明zkSNARKs到底是什么东西，也没有说明如何将一个问题转化成QAP问题。

## 3. zkSNARKs概述

首先简单说一说zkSNARKs，它是zero-knowledge succinct non-interactive arguments of knowledge，分开来将：

- zero-knowledge：表示零知识，证明某个陈述为真但不揭露任何其他信息。
- succinct代表简洁：表示证明大小很短且易于验证
- no-interactive：非交互，上面说的schnorr协议需要verifier生成一个随机数，故而是交互证明，而非交互，则不需要这样的角色，prover可以自行生成证明，给所有人验证。
- arguments：注意这里没有用proofs这个词，proof（证明）和argument（论证）在零知识证明里，是有区别的，在proof system中，即便是计算能力无限的prover也没法欺骗verifier去相信一个错误的陈述为真（统计可靠性），而在argument system中，只有多项式时间计算能力的没法欺骗（计算可靠性），比如说假设能破解椭圆曲线离散对数问题，那么可能就不再安全。
- of Knowledge：如果prover没有相应的witness（证据），那么构建相应的proof（对于proof system）或argument（对于argument system）是不可能的。

简洁之类的后面再讲，但有一个问题先说下，上面举的例子schnorr是交互型协议，其基础来源于prover无法事先预知verifier给的随机数，但是如果不能交互的话，没有第三方提供随机数，怎么构造证明？怎么构造模拟器？

对于schnorr，我们其实可以在prover生成随机数r时，用哈希函数c = hash(pk,r)，来生成这个c，然后后面的过程与原本的类似，就可以不用交互了，但是这个依赖于hash函数的安全性，我们需要将其认定为是一个随机预言机（ 随机预言机定义：就是它对任何输入都回传一个真正均匀随机的输出，但对相同的输入每次都会回传一模一样的输出，相当于一个黑盒。事实上哈希函数不是随机预言机 ），可以看到，其实这样schnorr零知识证明就变成一个数字签名协议了，就是schnorr签名协议。

这个过程叫Fiat-Shamir Transform，即用随机预言机解决这个随机的问题，其他有一些零知识证明方案就采用了这个思路去掉了可信setup过程。

而对于zkSNARKs，则采取了可信Setup的方法，在初始的时候就把这个随机值先生成好了，再把这个值隐藏起来不让大家知道，生成人也要保证永不泄露，具体后面再讲。

## 4. 问题转化

接下来我来先讲解如何将一个具体的问题转换为一个zkSNARKs能处理的问题（即QAP形式），然后再将如何在QAP上构建zkSNARKs。

比如说，我想要验证prover是否执行了下面的代码，但prover在证明过程中不想泄露自己的输入值，应该怎么做呢？

func calc(w bool, a, b int) int {
    if w {
        return 3*a*b
    } else {
        return 5*a+b
    }
}

一段代码逻辑，我们怎么把一段具体的代码逻辑转换为一个zkSNARKs可以处理的东西呢？上面说了zkSNARKS依赖某种NP问题，最常用的是QAP也就以QAP举例。讲怎么把代码逻辑转换成QAP。

第一步是将代码逻辑写成多项式，上述代码其实就是两个等式，其中v是返回值。

$w \cdot (3a\cdot b) + (1-w)\cdot(5a+b) = v,\space w \cdot (w-1)=0$

我们需要将这两个多项式转换成一系列多项式$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，并且给出目标多项式t(x)，最后代入解应该是应该是$L(X)\cdot R(x) - O(x) = t(x)h(x)$的形式。

我先用一种简单的方法计算一遍方便大家理解内在逻辑，再讲另一种标准做法。

简单做法：

先对上面多项式的形式进行一些改变，转换为近似A op B = C的形式。，

$w \cdot (3a\cdot b) + (1-w)\cdot(5a+b) = v$
-> $w \cdot (3a\cdot b) +5a+b -w(5a+b)=v$
->$w \cdot (3a\cdot b - 5a-b) +5a+b=v$
->$1:\space w \cdot (3a\cdot b - 5a - b ) = v - 5a -b \space$

$w\cdot (w-1)=0$
->$2:\space w\cdot w = w \space$

如上，将两个式子都转换成了$a\times b = c$的形式了，但式(1)在乘法内部也出现了乘法，我们可以再取一个中间值，得：

$1:\space 1 \cdot a \times 1\cdot b = 1\cdot m\space$
$2:\space 1 \cdot w \times (3\cdot m + - 5\cdot a + - 1\cdot b ) = 1\cdot v + -5\cdot a + -1 \cdot b \space$
$3: \space 1 \cdot w \times 1 \cdot w = 1 \cdot w$

现在我们拥有了三个多项式，由上我们可以看到，$\{l_i(x)\}_{i=0}^n$只与a，w有关，$\{r_i(x)\}_{i=0}^n$与m, a, b, w有关，$\{o_i(x)\}_{i=0}^n$与m, v, a, b, w有关

现在我们把多项式里变量的系数当成另一个多项式的函数值，则有三个多项式，为了方便，就假设这些系数是取点1, 2, 3时的函数值。

相当于:

$1:\space l_a(1) \cdot a \times r_b(1)\cdot b =o_m(1) \cdot m\space$
$2:\space l_w(2) \cdot w \times (r_m(2)\cdot m +r_a(2)\cdot a + r_b(2)\cdot b ) = o_v(2)\cdot v + o_a(2)\cdot a + o_b(2) \cdot b \space$
$3: \space l_w(3) \cdot w \times r_w(3) \cdot w = o_w(3) \cdot w$

可得：

$\{l_i(x) \}_{i=0}^n$：

$l_a(1)=1，l_a(2)=0，l_a(3)=0$（因为左操作数里，a只在第一个式子出现，下面与其类似）
$l_w(1)=0，l_w(2)=1，l_w(3)=1$

$\{r_i(x) \}_{i=0}^n$：

$r_m(1)=0，r_m(2)=3，r_m(3)=0$
$r_a(1)=0，r_a(2)=-5，r_a(3)=0$
$r_b(1)=1，r_m(2)=-1，r_b(3)=0$
$r_w(1)=0，r_w(2)=0，r_w(3)=1$

$\{o_i(x) \}_{i=0}^n$：

$o_m(1)=1,o_m(2)=0,o_m(3)=0$
$o_a(1)=0,o_a(2)=-5,o_a(3)=0$
$o_b(1)=0,o_b(2)=-1,o_m(3)=0$
$o_w(1)=0,o_w(2)=0,o_m(3)=1$
$o_v(1)=0,o_v(2)=1,o_v(3)=0$

通过上面的定点，我们就分别把三个式子中参数的系数，变成了函数值，然后我们可以用拉格朗日插值法(不懂的自行百度），将上面的描点拟合成曲线，最后可以计算得。

$\{l_i(x)\}_{i=0}^n$:

$l_a(x)=\frac{1}{2}x^2-\frac{5}{2}x+3$
$l_w(x)=-\frac{1}{2}x^2+\frac{5}{2}x-2$

$\{r_i(x)\}_{i=0}^n$：

$r_m(x)=-3x^2+12x-9$
$r_a(x)=5x^2-20x+15$
$r_b(x)=\frac{3}{2}x^2-\frac{13}{2}x+6$
$r_w(x)=\frac{1}{2}x^2-\frac{3}{2}x+1$

$\{o_i(x)\}_{i=0}^n$：

$o_m(x)=\frac{1}{2}x^2-\frac{5}{2}x+3$
$o_a(x)=5x^2-20x+15$
$o_b(x)=x^2-4x+3$
$o_w(x)=\frac{1}{2}x^2-\frac{3}{2}x+1$
$o_v(x)=-x^2+4x-3$

由此，我们就求得了一系列多项式$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，而t(x)=(x-1)(x-2)(x-3)，这里的逻辑可能有点费解，要理清楚。

细讲一下，我们在上面用系数当成点1，2，3处的函数值得出了一系列多项式，现在我们把正确的m, v, a, b, w当做系数给这些多项式做排列组合后得到$P(x) = L(x)\cdot R(x) - O(x)$，代入 1 相当于就退化为$P(1) = 1 \cdot a \times 1\cdot b - 1\cdot m = 0$，代入2，3也类似，所以组合成的多项式P(x)一定有根1, 2, 3，自然有因式t(x)=(x-1)(x-2)(x-3)。

我们是从系数中得到多项式，而原来多项式中变量的值当做系数，知道一个正确的系数，就相当于执行了下面这个函数逻辑。

假设输入$w=1,a=2,b=3$，则可以求出$m=6, v=18$，用这个参数排列组合上述多项式一定满足条件。

func calc(w bool, a, b int) int {
    if w {
        return 3*a*b
    } else {
        return 5*a+b
    }
}

不相信可以用上面的值算一下:

$L(x)=2l_a(x)+l_w(x)=2\cdot(\frac{1}{2}x^2-\frac{5}{2}x+3)-\frac{1}{2}x^2+\frac{5}{2}x-2 = \frac{1}{2}x^2-\frac{5}{2}x+4$

$R(x)=6r_m(x)+2r_a(x)+3r_b(x)+r_w(x)=-3x^2+11x-5$

$O(x)=6o_m(x)+2o_a(x)+3o_b(x)+o_w(x)+18o_v(x)=-\frac{3}{2}x^2+\frac{7}{2}x+4$

再计算$P(x)=L(x)R(x)-O(x)=-\frac{3}{2}x^4+13x^3-\frac{81}{2}x^2+53x-24$

接下来验证P(x)能否整除t(x)=(x-1)(x-2)(x-3)，$h(x)=\frac{P(x)}{(x-1)(x-2)(x-3)}=-\frac{3}{2}x+4$，可以看到，代入正确的witness确实是可以得到一个满足的多项式的。

此时我们完成了zk-SNARKs的第一步，即将验证代码的执行转成了验证多项式是否成立。

上面讲了一个简单版的怎么将问题转化为QAP，下面讲一个更通用的方法，但其实原理和上面的过程是一样的，所以下面的过程有什么地方理解不了，看看上面的简化版就行了，只不过下面拆解得更基础，电路更多了而已。

用constraint system来做，一般举例都用的R1CS(rank 1 constraint system)，R1CS是由一系列三向量组(x,y,z)组成的序列，R1CS有一个解向量s，需要满足$s \cdot \mathbf{x}\times s\cdot \mathbf{y}-s \cdot \mathbf{z} = 0$。

所谓constraint system就是要限制，比如说w(w-1)=0，就限制了w只能为1或0，(w-2)*1=0，就限制了w只能为2。

我们首先需要将多项式转成算术电路，因为电路的可满足性是一个NP问题，我们可以等会再将这个NP问题规约成QAP问题，还是以上面的多项式为例。

- From 多项式 to R1CS
- 算术电路拍平
首先将多项式的所有操作转化为 $x\space (op) \space y = z$ 的形式，op可以是+,-,*,/ 等。
$1:w \cdot (3a\cdot b - 5a-b) +5a+b=v$
$2:\space w\cdot w = w \space$

那么转化为$x\space (op) \space y = z$ 以后，可以得到下面这个电路：

sym_1 = a * b
sym_2 = 3 * sym_1
sym_3 = 5 * a
sym_4 = sym_2 - sym_3
sym_5 = sym_4 - b
sym_6 = w * sym_5
sym_7 = sym_3 + b
v = sym_6 + sym_7
w = w * w

- 可以看出，为了将所有操作都转成 $x\space (op) \space y = z$ 的形式，加入了sym_1...sym_7等中间变量。
上面的形式即算数电路形式，向电路输入参数得到结果，即将代码逻辑拆成了电路的计算，计算完以后就会得到一组满足电路的值，至于为什么叫电路，我就不画图了，引一张图，这是$x^3+x+5=out$的算术电路形式，上面的电路化成图自己脑补。
- 
- 电路转成R1CS
现在我们把所有变量包括中间变量组成一组向量，`s = [one,a,b,w,v,sym_1,sym_2,sym_3,sym_4,sym_5,sym_6,sym_7]^T`，s即为R1CS中的解向量，其中one表示数字1。
现在我们对上面的式子进行转换，这部分应该很好理解，下面向量里的值作用相当于简单版里的「系数」，原理和简单版差不多，除了式子更多些而已。
a * b = sym_1

x = [0,1,0,0,0,0,0,0,0,0,0,0]
y = [0,0,1,0,0,0,0,0,0,0,0,0]
z = [0,0,0,0,0,1,0,0,0,0,0,0]

- 可知对于上面的x,y,x和s，向量式$s \cdot x\times s\cdot y-s \cdot z = 0$是满足的。
3 * sym_1 = sym_2

x = [3,0,0,0,0,0,0,0,0,0,0,0]
y = [0,0,0,0,0,1,0,0,0,0,0,0]
z = [0,0,0,0,0,0,1,0,0,0,0,0]

- 5 * a = sym_3

x = [5,0,0,0,0,0,0,0,0,0,0,0]
y = [0,1,0,0,0,0,0,0,0,0,0,0]
z = [0,0,0,0,0,0,0,1,0,0,0,0]

- (sym_2 - sym_3) * 1 = sym_4

x = [0,0,0,0,0,0,0,1,-1,0,0,0]
y = [1,0,0,0,0,0,0,0,0,0,0,0]
z = [0,0,0,0,0,0,0,0,1,0,0,0]

- (sym_4 - b) * 1 = sym_5

x = [0,0,-1,0,0,0,0,0,1,0,0,0]
y = [1,0,0,0,0,0,0,0,0,0,0,0]
z = [0,0,0,0,0,0,0,0,0,1,0,0]

- w * sym_5 = sym_6

x = [0,0,0,1,0,0,0,0,0,0,0,0]
y = [0,0,0,0,0,0,0,0,0,1,0,0]
z = [0,0,0,0,0,0,0,0,0,0,1,0]

- (sym_3 + b) * 1 = sym_7

x = [0,0,1,0,0,0,0,1,0,0,0,0]
y = [1,0,0,0,0,0,0,0,0,0,0,0]
z = [0,0,0,0,0,0,0,0,0,0,0,1]

- (sym_6 + sym_7) * 1 = v

x = [0,0,0,0,0,0,0,0,0,0,1,1]
y = [1,0,0,0,0,0,0,0,0,0,0,0]
z = [0,0,0,0,1,0,1,0,0,0,0,0]

- w * w = w

x = [0,0,0,1,0,0,0,0,0,0,0,0]
y = [0,0,0,1,0,0,0,0,0,0,0,0]
z = [0,0,0,1,0,0,0,0,0,0,0,0]

- From R1CS to QAP
我们就得到了一组$\mathbf{x,y,z}$向量，$\mathbf{x,y,z}$各自组合可以得到一个矩阵，每一行均满足$s \cdot \mathbf{x}\times s\cdot \mathbf{y}-s \cdot \mathbf{z} = 0$。
我们可以对每一列进行根简单版本一样的处理，即使用拉格朗日插值法算出多项式。
比如可以算出代入x=1,2,3,4,5,6,7,8,9，用x,y,z的每一列的值当做函数值，然后用拉格朗日插值法，即可得多项式系列$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，基本思路和简单方案一致，只不过这个方案中多项式的阶数更高, t(x) = (x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9)。
举个例子，可以计算$l_1(x)$如下：
$l_1(x)=\frac{29}{10080}x^8-\frac{101}{840}x^7+\frac{127}{60}x^6-\frac{4889}{240}x^5+\frac{18597}{160}x^4-\frac{95489}{240}x^3+\frac{494329}{630}x^2-{83647}{105}x+312$
其他的一样求出，后续思路与简单版一样，代入正确的s可以得到一个能整除t(x)的P(x)。
当一个prover知道一组正确的解向量s时，即可通过验证，跟简单形式的理解是一样的。

## 5. 细节详解

上面花了很大篇幅讲述如何将一个代码逻辑问题转换为一个zkSNARKs可以处理的QAP表达，现在来讲讲，针对一个QAP问题，怎么做zkSNARKs的证明过程呢？

让我们慢慢去思考这个问题，首先，我们有一系列的多项式$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，以及一个t(x)，在非零知识的过程中我们只需要让prover传回一个解即可，但如果要做成零知识呢？我们一步一步引入密码工具完成zk-SNARKs。

我们首先明确我们的目的，对于一个QAP问题，witness就是$\{a_i\}_{i=0}^n$，我们想达到的是，prover知道这么一组满足给定QAP问题的系数witness，是prover能通过验证的充要条件，但是witness的信息不会泄露。

我们先思考需要交互的情况：

1）此时verifier随机选取一个数s，发送给prover。

2）prover根据$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，代入自己的系数计算出L(x),R(x),O(x)，并令P(x) = L(x)R(x)-O(x),求得P(x)/t(x) = h(x)，发送L(s),R(s),O(s)与h(s)给verifier。

3. verifier计算$L(s)R(s)=h(s)\cdot t(s)+O(s)$是否成立。

但是很明显，上述协议根本不是一个证明协议，证明本身是可以任意伪造的，因为我们只通过一次检验，没法保证prover如实计算了P(x)以及h(x)，这个不能用来证明的协议放在这里这里仅作一个引子。

另外，最开始我们不考虑通用化的问题，所以要证明的statement就体现在构造出来的QAP问题中，后面会讲通用化。

接下来要引入密码学工具一步一步限制prover达到目的，**准备纸笔开始推公式吧！**

**圈一个重点，免得大家迷失方向，下面做的所有工作都是为了这三件事**：

1. 验证证明是用给定CRS公共参考串里面的值线性组合而来。
1. 验证证明中L R O三者的系数是一致的。
1. 验证给出的证明是满足QAP的解。

### 5.1 同态隐藏

首先我们要用上同态隐藏，假设有一个映射E()，映射前的某些操作可以在映射后体现，就说明映射具有同态性。

定义：
（1）对于一个给定的x,知道E(x),很难逆推得到x。
（2）对于不同的x和y，$E(x) \neq E(y)$。
（3）对于某些操作，映射后依然存在，比如E(x+y)可以从E(x)和E(y)中计算出来。

一个简单的例子是椭圆曲线域上的幂运算，$E(x) = g^x$，g为生成元，根据椭圆曲线离散对数问题，知道E(x)和g并不能反推回x。

$E(x+y) = g^{(x+y)} = g^x\space \times g^y\space =E(x)E(y)$

在未引入双线性映射的时候，图方便用E(s)来写，引入后都用幂形式$g^s$写，两者在本文意义相同。

举个例子，verifier可以选择一个随机数s，然后发送$\{g^{\{s^i\}}\}_{i=0}^n = g^s, g^{s^1}, g^{s^2}...g^{s^n}$给prover，verifier知道一个多项式$f(x) = 3x^2+2$，想验证prover知不知道此多项式，可将$\{g^{\{s^i\}}\}_{i=0}^n$发送给prover，prover计算$g^{f(s)} =g^{3s^2+2}= {(g^{s^2})}^3\cdot (g)^2$，将$g^{f(s)}$发回，verifier既可验证，计算过程prover无法知道具体的s值为多少。

概念上科普下同态隐藏——上面的计算好像是对一堆黑盒子做操作，虽然不知道黑盒子里面是什么（隐藏性质），但操作完又能得到想要的值（同态性质）。在zkSNARKs里我们不需要全同态操作，全同态操作目前尚不实用。

根据同态隐藏的性质，我们修改下上面的基础协议看看能不能行：

1）此时verifier随机选取一个数s，计算$\{ E(s^i) \}_{i=0}^d$(d为h的阶，可以算出来）以及$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$，发送给prover。

2）prover根据$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，代入自己的系数计算出L(x),R(x),O(x)，并令P(x) = L(x)R(x)-O(x),求得P(x)/t(x) = h(x)。用$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$计算出E(P(x))，用$\{ E(s^i) \}_{i=0}^d$计算出E(h(s))，并将计算结果发送给verifier。

3)verifier计算$E(P(s))=E(h(s)\cdot t(s))$是否成立。

虽然prover现在可以用参数计算结果了，但仔细揣摩会发现这个协议依然是无效的，因为没法保证prover一定是用$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$的排列组合计算出来的值，比如Verifier发送$E(l_i(5))$，prover也可以用随便选个E(3)进行计算。verifier无法识别这种情况，看来我们需要引出另一个工具来解决这个问题了。

### 5.2 KCA（Knowledge of Coefficient Test and Assumption）

假如Verifier对$\{E(s^i)\}_{i=0}^n$，每一个值再计算相应的$\{E(\alpha\cdot s^i)\}_{i=0}^n$，而$\alpha$对于prover是未知的，因为离散对数难题，prover也无法从中提取出$\alpha$，那么我们就能限制prover只能用我发送的值进行计算了。

比如Verifier发送$E(5), E(5^1), E(5^2)...E(5^n),E(\alpha5), E(\alpha5^1), E(\alpha5^2)...E(\alpha5^n)$，那么prover就只能被迫用5这个值进行计算$E(f(5))$,以及$E(\alpha f(5))$，最终验证prover返回的两个值，$E(f(5))^\alpha ?= E(\alpha f(5))$即可保证prover一定是诚实的按照$E(5^i)$的排列组合计算出来的，如果prover想用$E(4)$进行计算，可是他提供不了$E(\alpha 4)$就通过不了这一步验证了。

#### 5.2.1 串用问题

但是上面的解决方案可能导致串用问题，因为所有的$\alpha$都一样，prover可能用$l_i(x)$串在R(x)的计算中，那么我们给$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$三个不同的 $\{ \alpha_l,\alpha_r,\alpha_o \}$，所以verifier需要事先计算$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$以及对应的$\{E(\alpha_l\cdot l_i(x)),E(\alpha_r\cdot r_i(x)),E(\alpha_o\cdot o_i(x))\}_{i=0}^n$，即可保证都是根据各自的隐藏值算的。

这样的话，prover就可以直接通过$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$计算$E(L(s))，E(R(s))，E(O(s))$，通过$\{E(s^i)\}_{i=0}^d$计算$E(h(s))$，并用$\{E(\alpha_l\cdot l_i(x)),E(\alpha_r\cdot r_i(x)),E(\alpha_o\cdot o_i(x))\}_{i=0}^n$计算得$L_{\alpha_l} =E(\alpha_l\cdot L(x)),R_{\alpha_r} =E(\alpha_r\cdot R(x)),O_{\alpha_o} =E(\alpha_o\cdot O(x))$，并将结果全部发送给verifier。
verifier在收到以后，验证$E(L(s))^{\alpha_l}=E(L_{\alpha_l})$，$E(R(s))^{\alpha_r}=E(R_{\alpha_r})$，$E(O(s))^{\alpha_o}=E(O_{\alpha_o})$几个等式是否成立，再验证$E(L(s)\cdot R(s))=E(h(s)\cdot t(s)+O(s))$是否成立。(**注意，此时方案已经不成立，因为在验证中出现了乘法，但是verifier无法得到隐藏值的乘法值，这个问题在下面的双线性映射部分会得到解决，因为双线性映射具备乘法同态，这一步放这里起一个递进的作用**)

等于多加了一步验证解决了**"证明是用给定参考串里面的值线性组合计算而来。"**

#### 5.2.2 系数一致性问题

但是又有新的问题，我们知道QAP问题中，$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，三个多项式分别排列组合后得到L(x), R(x),O(x)，他们的系数序列$\{a_i\}_{i=0}^n$应该是相同的。

但仅仅通过不同的$\alpha$并不能保证prover一定会用相同的系数序列计算，我们可以用不同的几组系数a1, a2, a3计算，也可能能通过验证。我们又需要新的思路，经过上面一步的经验你们应该已经清楚了，没错，我们再加一步验证。

此时我们搬出检验和思路，可以通过检验和来解决这个问题，verifier除了需要事先计算$\{E(s^i)\}_{i=0}^d$，$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$，$\{E(\alpha_l\cdot l_i(x)),E(\alpha_r\cdot r_i(x)),E(\alpha_o\cdot o_i(x))\}_{i=0}^n$之外，还需要计算一个$\{E(\beta(l_i(s)),E(\beta(r_i(s)),E(\beta(o_i(s)))\}_{i=0}^n$，相当于对每一个$\{l_i(s),r_i(s),o_i(s)\}$三元组，都计算一个检验和，最后加起来，需要系数序列相等才可能满足$\beta$的系数约束。

基于这个新的序列，prover在生成证明的时候还需要多计算一个结果，$E(z_i(s))=E(\beta\cdot (l_i(s)+r_i(s)+o_i(s)))^{a_i}$，这个$a_i$就是针对每一组$\{l_i(x),r_i(x),o_i(x)\}$解中相同的系数，得$Z = E(Z(s))=\prod_{i=0}^n E(z_i(s))$发送给verifier。

verifier再多一步验证$E(Z(s)) = E(L(s)+R(s)+O(s))^\beta$，即可验证线性组合是否相同。

但是如果只用一个$\beta$，其实prover还是有操作空间的，比如当l(s)=r(s)的时候，有检验和$\beta(v_L\cdot l(s)+v_R\cdot r(s)+v_O\cdot o(s))$，按理说需要$v_L=v_R=v_O$，才能提取出一个公因子$v\cdot \beta$，变成统一的$v\cdot \beta(l(s)+r(s)+o(s))$。

但由于l(s)=r(s)，则可以进行如下操作：

$\beta((2v_O-v_R)\cdot l(s)+v_R\cdot r(s)+v_O\cdot o(s))$

$=\beta(2v_O\cdot l(s)-v_R\cdot l(s)+v_R\cdot r(s)+v_O\cdot o(s))$

$=\beta(2v_O\cdot l(s)+v_O\cdot o(s))=v_O\beta(2l(s)+o(s))$.

也得到了满足提取公因子的形式，可以通过验证，但此时系数并不一样。为了解决这个问题，我们可以对不同的$\{l_i(x),r_i(x),o_i(x)\}{i=0}^n$选择不同的$\beta$，即分别生成${E(\beta_l\cdot l_i(s)),E(\beta_r\cdot r_i(s)),E(\beta_o\cdot o_i(s)}{i=0}^n$，可避免这种情况，此时prover计算$E(z_i(s))=E(\beta_l\cdot l_i(s)+\beta_r\cdot r_i(s)+\beta_o\cdot o_i(s))^{a_i}$，$Z = E(Z(s))=\prod_{i=0}^n E(z_i(s))$替代上面得操作，verifier验证$E(Z(s)) = E(\beta_lL(s)+\beta_rR(s)+\beta_oO(s))$是否成立。

总之这一步我们的目的就是确保prover计算的时候，三个系数序列一定要是相等的。

### 5.3. 变为非交互

上面说了一堆，其实还是针对交互型协议的，每一次verifier每次都需要计算特别多的数字序列，如$\{E(s^i)\}_{i=0}^d$，$\{E(\alpha\cdot s^i)\}_{i=0}^n$，$\{E(l_i(s)),E(r_i(s)),E(o_i(s))\}_{i=0}^n$，$\{E(\alpha_l\cdot l_i(x)),E(\alpha_r\cdot r_i(x)),E(\alpha_o\cdot o_i(x))\}_{i=0}^n$，$\{E(\beta_l\cdot l_i(s)+\beta_r\cdot r_i(s)+\beta_o\cdot o_i(s)\}_{i=0}^n$。

现实情况中，多项式的阶数都非常高（即算数电路特别多），一般都几百万甚至上亿，每一次参数生成需要几小时乃至几天，对于verifier太耗时了，但如果$s,\alpha,\beta,\gamma$等值没有泄露的话，其实所有的prover可以用相同的参数生成证明，这个就叫公共参考串（CRS)。

但如果用公共参考串这里就引出两个问题：

- 如何保证生成公共参考串的人不泄露这几个隐私参数？
- 在verifier验证的时候，很多地方都直接用上了$s,\alpha,\beta,\gamma$这几个参数才可以验证，但是这几个参数在非交互情况下又必须隐藏，怎么保证还可以验证呢？

#### 5.3.1 安全多方计算

关于上面两个问题，第一个问题是通过安全多方计算解决的，就是会有很多人参与生成公共参考串，每个人贡献出自己的随机数，最后通过某些手段拼合，由于没人知道所有的随机值，那么只要还剩一个人没有作恶，协议就是安全的。

举个例子，计算$\{E(s^i)\}_{i=0}^n$，$\{E(\alpha\cdot s^i)\}_{i=0}^n$；

让a先计算$\{E(s_a^i)\}_{i=0}^n$，$\{E(\alpha\cdot_a s_a^i)\}_{i=0}^n$，交给b；

b在此基础上计算，$\{E(s_a^i)^{s_b^i}\}_{i=0}^n$，$\{E(\alpha_a\cdot s_a^i) ^ {\alpha_b\cdot s_b^i}\}_{i=0}^n$，得到$\{E(s_as_b)^i\}_{i=0}^n$，$\{E(\alpha_a\alpha_b \cdot (s_as_b)^i )\}_{i=0}^n$；

以此类推，可以扩展到计算其他参数以及更多人参与，细节就不赘述了，这里能理解即可。

#### 5.3.2 双线性映射

第二个问题是通过双线性映射（椭圆曲线配对，Pairing）解决的，双线性映射是具有如下性质的映射函数：

双线性映射可以用五元组$(p,G_1,G_2,G_T,e,g_1,g_2)$来描述，G1，G2，GT是三个素数阶乘法循环群，阶数皆为p，定义在这三个群上的一个映射关系e：$G1\times G2 —>GT$，$g_1$是$G_1$的生成元，$g_2$是$G_2$的生成元，$e(g_1,g_2)$是$G_T$的生成元$g_t$，若$G_1=G_2$则称为对称双线性映射，否则为非对称双线性映射。下面举例子为了方便，未特定指明都用对称双线性映射计算，因为非对称还需注明哪些元素属于G1，哪些属于G2，不过要清楚，两种双线性映射都可以用于zk-SNARKs，且由于非对称效率更高，实际中一般用的都是非对称，比如基于BLS12-381曲线构造的Pairing。

并满足以下性质：

- 双线性性：对于任意$a，b, c\in Zp$，有$e(g_1^a, g_2^b) = e(g_1, g_2)^{ab}$，$e(g_1^a\cdot g_1^b,g_2^c)=e(g_1^a,g_2^c)e(g_1^b,g_2^c)$；
- 非退化性：存在$a\in G_1,b\in G_2$，使得$e(a,b)\neq(1)G_t$（ $(1)G_t$ 代表GT群的单位元）；
- 可计算性：对任意的$R\in G1,S\in G2$，存在有效的算法计算e(R, S)的值。

具体关于这样的双线性配对如何构造就超出本文谈论范围了。

那么如何利用双线性配对在不知道$s,\alpha,\beta,\gamma$这几个参数的时候，进行验证呢？

举个例子，在上面验证$\alpha$对的验证中，本来需要verifier知道$\alpha$的值，验证$E(L(s))^{\alpha_l}=E(L_{\alpha_l})$，现在可以改为验证$e(g^{L(s)},g^{\alpha_l})=e(g^{L_{\alpha_l}},g)$是否成立即可，这样的话，就可以只公开$g^{\alpha_l}$而不是用私密参数$\alpha_l$本身做验证了。

#### 5.3.3 malleable问题

但这样的话又会导致新的问题，即证明得可操作问题-malleable问题，因为prover此时可以获取$g^{\alpha_l},g^{\alpha_r},g^{\alpha_o},g^{\beta_l},g^{\beta_r},g^{\beta_o}$。这样的话，prover甚至非prover都可以对证明做一些小操作了。

比如对于证明中的$g^{L(x)}$，我们给它加一个数5，$g^{L(s)+5}$，其他的不做任何改动，由于我们知道$g^{\alpha_l},g^{\beta_l}$，则可以算出$g^{\alpha_lL(s)}*({g^{\alpha_l}})^5=g^{\alpha_l(L(s)+5)}$，$g^{\beta_lL(s)}*({g^{\beta_l}})^5=g^{\beta_l(L(s)+5)}$。

这样的话，也可以通过验证$e(g^{L(s)+5},g^{\alpha_l})=e(g^{\alpha_l(L(s)+5)},g)$，以及$e(g^{L(s)+5},g^{\beta_l})\cdot e(g^{R(x)},g^{\beta_r})\cdot e(g^{O(x)},g^{\beta_o})=e(g^{Z(s)}\cdot ({g^{\beta_l}})^5,g)$，其中$g^z=g^{\beta L(s)}\cdot g^{\beta R(s)}\cdot g^{\beta O(s)}$,这个计算上面已经讲过了，也就是说，我可能很容易用一个证明伪造出另一个可以通过的证明。

那么为了避免这种可操作性，需要新加一层限制，这个改进可以有多种思路。

我们首先可以把$\beta$验证变得更严格，即把在生成证明的proving key中将$\{g^{(\beta_l\cdot l_i(s)+\beta_r\cdot r_i(s)+\beta_o\cdot o_i(s)}\}_{i=0}^n$改为$\{g^{\gamma(\beta_l\cdot l_i(s)+\beta_r\cdot r_i(s)+\beta_o\cdot o_i(s)}\}_{i=0}^n$，这样的话，在trust Setup时就需要多一个$\gamma$，与之相应的，用于验证的verification key中就需要加入$\{g^{\beta_l\gamma},g^{\beta_r\gamma},g^{\beta_o\gamma},g^{\gamma}\}$。

验证这一步时变为，$e(g^{L(s)},g^{\beta_l\gamma})\cdot e(g^{R(x)},g^{\beta_r\gamma})\cdot e(g^{O(x)},g^{\beta_o\gamma})=e(g^Z,g^\gamma)$，由于无法求出$\gamma$，也就无法进行操作了。

不过上面的解决方案有一个问题就是，这一步验证需要四次Pairing双线性计算，而双线性计算是很耗时的，那我们能不能从$\alpha$验证入手来解决这个问题呢？也是可以的，针对$L,R，O$选取随机$\rho_l,\rho_r$，并令$\rho_o=\rho_l\cdot\rho_r$，此时给他们分配不同的生成元$g_l=g^{\rho_l},g_r=g^{\rho_r},g_r=g^{\rho_o}$。

这样的话，proving key变为$(\{g^{s^i}\}_{i=0}^d,\{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)},g_l^{\alpha_ll_i(s)},g_r^{\alpha_rr_i(s)},g_o^{\alpha_oo_i(s)},g_l^{\beta l_i(s)},g_r^{\beta r_i(s)},g_o^{\beta o_i(s)}\}_{i=0}^n )$，然后verification key变为$\{g^{\alpha_l},g^{\alpha_r},g^{\alpha_o},g^{\beta\gamma},g^{\gamma}\}$。

则在做$\alpha$对验证时，变为$e(g_l^{l_{\alpha_l}},g)=e(g_l^{l},g^{\alpha_l})$，其他类似，由于不知道$\rho_l,\rho_r$，那就无法进行操作了，同时$\beta$共用，则验证变为，$e(g_l^{L(s)}\cdot g_r^{R(s)}\cdot g_o^{O(s)},g^{\beta\gamma})=e(g^{Z(s)},g^{\gamma})$，只用两次配对计算。

这样就在非交互的前提下解决了这个问题。

### 5.4 σ偏移

此外，prover为了保证零知识，可能连$g_l^{L(s)},g_r^{R(s)},g_o^{(O(s))}$这些值都不想透露，因为在解比较少的时候，可以通过暴力法匹配计算出L(s)的值，所以我们可以对每个值都加一点只有prover自己知道的偏移，但同时保证验证可以通过，就能避免被暴力破解。

由于等式最终要满足$L(s)\cdot R(s) - O(s) = t(s)\cdot h(s)$成立，而t(s)又是所有人都知道的，所以我们只能改动$L(s),R(s),O(s)$，观察这个式子可知，我们只能$L(s),R(s),O(s)$上偏移t(s)的倍数，否则没法保证还能整除。

我们可以计算一下偏移的具体数值：

$(L(s)+\sigma_lt(s))\cdot (R(s)+\sigma_rt(s))-(O(s)+\sigma_ot(s))=t(s)(\Delta+h(s))$

现在我们可以将$\Delta$求出来。

$L(s)R(s)-O(s)+t(s)(\delta_rL(s)+\delta_lR(s)+\delta_l\delta_rt(s)-\delta_o)=t(s)\Delta+t(s)h(s)$

由于$L(s)R(s)-O(s)=t(s)h(s)$

所以约掉以后得：

$\Delta=\delta_rL(s)+\delta_lR(s)+\delta_l\delta_rt(s)-\delta_o$

这个式子放到证明过程中即为，

$g_l^{L_p(s)}=(g_l^{t(s)})^{\sigma_l} \cdot g_l^{L(s)}$，$g_l^{L_{\alpha p}(s)}=(g_l^{\alpha_l t(s)})^{\sigma_l} \cdot g_l^{\alpha_l L(s)}$（L(s)的计算和上面差不多，然后$g_r^{R_p(s)},g_o^{O_p(s)}$用同样的方法求得。

同时计算$h_{\sigma}(x)=\frac{L(x)R(x)-O(x)}{t(x)}+\delta_rL(x)+\delta_lR(x)+\delta_l\delta_rt(x)-\delta_o$，并计算出$g^{h(s)}$。

$g^{z_p(s)}=(g_l^{\beta t(s)})^{\sigma_l}(g_r^{\beta t(s)})^{\sigma_r}(g_o^{\beta t(s)})^{\sigma_o}g_l^{\beta L(s)}\cdot g_r^{\beta R(s)}\cdot g_o^{\beta O(s)}$

然后也是可以通过验证的，不过通过上面我们也可以发现要在proving key中加入$\{g_l^{t(x)},g_r^{t(x)},g_o^{t(x)},g_l^{\alpha_lt(x)},g_r^{\alpha_rt(x)},g_o^{\alpha_ot(x)},g_l^{\beta t(x)},g_r^{\beta t(x)},g_o^{\beta t(x)}\}$供prover所用，才能在偏移后生成证明。

verifier进行下面的验证：

$e(g_l{L_p(s)},g{\alpha_l})=e(g_l^{L_{\alpha p}(s)},g)$，对R和O做相同验证。

$e(g_l^{L_p(s)}g_r^{R_p(s)}g_o^{O_p(s)},g^{\beta\gamma})=e(g^Z_p(s),g^\gamma)$

$e(g_l^{L_p(s)},g_r^{R_p(s)})=e(g_o^{t(s)},g^{h(s)})\cdot(g_o^{O_p(s)},g)$

这几个式子的成立，是可以从前面推出来的，不相信的同学依旧可以动手推导一番，用一点加减乘除以及双线性计算的拆分组合即可。

由于这个偏移的存在，即便想暴力匹配也是不可能的了。

### 5.5 通用化

上面写了这么多内容，但是却有一个问题，那就是，针对每一个问题，都需要一次参数生成。

proving key：$(\{g^{s^i}\}_{i=0}^d,\{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)},g_l^{\alpha_ll_i(s)},g_r^{\alpha_rr_i(s)},g_o^{\alpha_oo_i(s)},g_l^{\beta l_i(s)},g_r^{\beta r_i(s)},g_o^{\beta o_i(s)}\}_{i=0}^n)$。
verification key：$\{g^{\alpha_l},g^{\alpha_r},g^{\alpha_o},g^{\beta\gamma},g^{\gamma}\}$。

虽然针对这个具体的问题，参数可以一直复用，但换一个问题，似乎又得做一遍重复操作了。

此时，我们希望我们设计的协议是通用的，即我们可以往协议中加入一个公共输入，针对不同的公共输入，就对应不同的问题。

这个该怎么做呢？首先回想一下，最开始我们想证明什么？是给定一系列多项式$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，目标t(x)，然后想求一个线性组合$\{a_i\}_{i=0}^n$，使得 $\sum_{i=0}^n a_il_i(x) \cdot \sum_{i=0}^n a_ir_i(x)-\sum_{i=0}^n a_io_i(x)=t(x)h(x)$ 。

那么我们可不可以针多项式，从里面摘出一部分系数做验证，prover再生成证明呢？或者针对同一个多项式，我加入一些限制条件呢？比如说，按上面那个例子，我可以要求给出的证明必须满足，输出值为183，在此前提下给出证明。

即prover生成的证明必须是要和公共输出对应，针对的是同一个问题，这样的话，我每次选择不同多项式的局部，prover都得生成针对性的证明才行，就可以对不同的问题复用参数生成。

现在我有一个特定的$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，对应一个特定的问题，我可以取出前l个用于验证。

即将上面的多项式分为$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^l$和$\{l_i(x),r_i(x),o_i(x)\}_{i=l+1}^n$，只对后面这部分进行KCA处理，而前面一部分$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^l$放入verification key，对应的$\{a_i\}_{i=0}^l$直接当成公共输入（可认为是prover要证明的论述statement）用来限制prover的证明，根据不同的问题，这个公共输入也不一样。

这样prover生成证明时，verifier验证证明时也将公共输入输进去，如果依然成立就能保证prover是对一个特定问题生成证明，相当于把问题本身的一部分当成了公共输入。

下面以数学形式进行推导理解：

结合上面所有的改进，我们对协议进行一个总结：

整个协议过程变为：

- Setup：
- 选择两个椭圆曲线群$G_1，G_2$以及一个双线性映射$e()$;
- 将一个具体的问题转化为QAP问题，即得到一系列多项式$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^n$，目标t(x)；
- 通过安全多方计算生成参数，注意有$\rho_o=\rho_l\cdot\rho_r,g_l=g^{p_l},g_r=g^{p_r},g_o=g^{p_o}$：proving Key:$(\{g^{s^i}\}_{i=0}^d,\{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)}\}_{i=0}^n,\{g_l^{\alpha_ll_i(s)},g_r^{\alpha_rr_i(s)},g_o^{\alpha_oo_i(s)},g_l^{\beta l_i(s)},g_r^{\beta r_i(s)},g_o^{\beta o_i(s)}\}_{i=l+1}^n,g_l^{t(x)},g_r^{t(x)},g_o^{t(x)},g_l^{\alpha_lt(x)},g_r^{\alpha_rt(x)},g_o^{\alpha_ot(x)},g_l^{\beta t(x)},g_r^{\beta t(x)},g_o^{\beta t(x)})$,

可以看到proving key中只对l+1...m范围内的多项式组进行了KCA。
verification key:
$(g,\{g_o^{t(x)},{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)}}\}_{i=0}^l,g^{\alpha_l},g^{\alpha_r},g^{\alpha_o},g^{\gamma},g^{\beta\gamma})$ 
在verification key中也加入了部分多项式组。

- Proving
- 随机选取$\delta_l,\delta_r,\delta_o$，计算$L(x) = \sum_{i=0}^n a_il_i(x)$_，_$g_l^{L_p(s)}=(g_l^{t(s)})^{\sigma_l} \cdot \prod_{i=l+1}^n (g_l^{l_i(s)})^{a_i}$_，_$g_l^{L_{\alpha p}(s)}=(g_l^{\alpha_l t(s)})^{\sigma_l} \cdot \prod_{i=l+1}^n (g_l^{\alpha_ll_i(s)})^{a_i}$，这里只有部分加入了$\alpha$对的计算，并用同样的方法求出$g_r^{R_p(s)},g_r^{R_{\alpha p}(s)},g_o^{O_p(s)},g_o^{O_{\alpha p}(s)}$。
- 计算$h_\delta(x)=\frac{L(x)R(x)-O(x)}{t(x)}+\delta_rL(x)+\delta_lR(x)+\delta_l\delta_rt(x)-\delta_o$_，_并计算$g^{h_\delta(s)}$。
- 计算$g^{z_p(s)}=(g_l^{\beta t(s)})^{\sigma_l}(g_r^{\beta t(s)})^{\sigma_r}(g_o^{\beta t(s)})^{\sigma_o}\prod_{i=l+1}^n (g_l^{\beta l_i(s)}g_r^{\beta r_i(s)}g_o^{\beta o_i(s)})^{a_i}$，这里也只有部分参与KCA计算，最后生成完整证明$\{g_l^{L_p(s)},g_r^{R_p(s)},g_o^{O_p(s)},g_l^{L_{\alpha p}(s)},g_r^{R_{\alpha p}(s)},g_o^{O_{\alpha p}(s)},g^{h_\delta(s)},g^{z_p(s)}\}$。
- 验证
- 加入对公共输入加入特定系数：$g_l^{L_v(s)}=\prod_{i=0}^m(g_l^{l_i(s)})^{a_i}$，用同样的方法生成$g_r^{R_v(s)},g_o^{O_v(s)}$.
- 验证$\alpha$对，即验证$e(g_l^{L_p(s)},g^{\alpha_l})=e(g_l^{L_{\alpha p}(s)},g)$，对R和O做相同验证。
- 验证系数一致性，即验证$e(g_l^{L_p(s)}g_r^{R_p(s)}g_o^{O_p(s)},g^{\beta\gamma})=e(g^Z_p(s),g^\gamma)$
- 验证答案是否正确：$e(g_l^{L_p(s)}g_l^{L_v(s)},g_r^{R_p(s)}g_r^{R_v(s)})=e(g_o^{t(s)},g^{h(s)})\cdot(g_o^{O_p(s)}g_o^{O_v(s)},g)$

在完整的写完协议后，我们可以分析下怎么做到的，首先由于同态性，上面的式子肯定是成立的，并且由于verifier在验证时，已经输入了一部分系数，所以说prover给出的证明必须要在verifier给出系数的前提下才可以通过。

讲个具体实例可能比较好理解，比如说你想设计一个电路，用于验证prover持不持有跟某个比特币地址对应的私钥，如果没有公共输入，你要么给每个地址都生成一次参数，要么就只能证明prover有没有某个私钥对应任意一个比特币地址（这个没有任何意义）。

但是如果加入公共输入，那就可以通用化，我们可以把地址的限制当成公共输入，那么prover的证明就必须得有与公共地址对应的私钥才行。

比如将比特币创世地址`1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa`转化为公共输出的限制，如果有人能证明自己拥有对应的私钥，那就有大概率可以证明自己是中本聪了。

### 5.6 模拟器

对了，前面说到，如果零知识证明要是零知识的，协议要可以构造模拟器出来，且模拟器生成的证明在概率分布上与prover生成的证明无法区分。

那么对于zk-SNARKs，如何构造模拟器呢？

其实很简单，只要我们知道$\alpha_l,\alpha_r,\alpha_o,\beta,\gamma,s$这些被隐藏的值具体是什么，很容易就能伪造出一个证明，且不需要任何知识，所以这些参数又被称为陷门（trapdoor)或者有毒废料(toxic waste），是不能公开的，否则证明就无意义了。

具体推导就不推了，这个很简单，就跟最前面用来做引子的例子里，没有任何安全防护的状态是一样的。

### 5.7 改进-Groth16

上面的分析应该已经足够去理解zk-SNARKs了，不过最后给出的方案其实还有改进空间，或者说还可以权衡。上面方案prover的证明一共包括$\{g_l^{L_p(s)},g_r^{R_p(s)},g_o^{O_p(s)},g_l^{L_{\alpha p}(s)},g_r^{R_{\alpha p}(s)},g_o^{O_{\alpha p}(s)},g^{h_\delta(s)},g^{z_p(s)}\}$。

即证明中包括八个椭圆曲线群元素，但我们知道，如果零知识证明要上链的话，我们肯定希望证明的size越小越好。

Jens Groth在16年发布了《On the Size of Pairing-based Non-interactive Arguments》里面提出了一种新的zk-SNARKs改进-被称为Groth16，证明只需要三个椭圆曲线群元素，大大减少了proof Size，按证明上链来说，等于一个区块可以塞下更多证明了，而且通信消耗也降低了。（当然，改进一直在继续），那么Groth16是怎么做的呢？

为了方便，我这就按最简单的写一些推导，示例是用非对称双线性映射，所以区分$g_1,g_2且g_t=e(g_1,g_2)$：

proving key:$(g_1^{\alpha},g_1^{\beta},g_1^{\delta},g_2^{\beta},g_2^{\gamma},g_2^{\delta},\{g_1^{s^i}\}_{i=0}^{n-1},\{g_2^{s^i}\}_{i=0}^{n-1},\{g_1^{\frac{\beta l_i(s)+\alpha r_i(s)+o_i(s)}{\gamma}}\}_{i=0}^{l},\{g_1^{\frac{\beta l_i(s)+\alpha r_i(s)+o_i(s)}{\delta}}\}_{i=l+1}^{m},\{g_1^{\frac{s^it(s)}{\delta}}\}_{i=0}^{n-2})$

以及$\{l_i(x),r_i(x),o_i(x)\}_{i=0}^m$

verification key：

$(g_1,g_2,g_2^{\gamma},g_2^{\delta},g_t^{\alpha\beta},\{g_1^{\frac{\beta l_i(s)+\alpha r_i(s)+o_i(s)}{\gamma}}\}_{i=0}^{l}\})$

生成证明：选取两个随机数$r_l,r_r$用于偏移，计算$h(x)=\frac{\sum_{i=0}^n (a_il_i(x) \cdot a_ir_i(x)-a_io_i(x))}{t(x)}$，通过$\{g_1^{\frac{s^it(x)}{\delta}}\}_{i=0}^{n-2}$线性组合算出$\{g_1^{\frac{h(s)t(s)}{\delta}}\}_{i=l+1}^{m}$

$g_1^{A(s)}=g_1^{\alpha}\cdot \prod_{i=0}^m g_1^{a_il_i(s)}\cdot g_1^{r_l\delta}$

$g_2^{B(s)}=g_2^{\beta}\cdot \prod_{i=0}^m g_2^{a_ir_i(s)}\cdot g_2^{r_r\delta}$

$g_1^{B(s)}=g_1^{\beta}\cdot \prod_{i=0}^m g_1^{a_ir_i(s)}\cdot g_1^{r_r\delta}$

$g_1^{C(s)}=\prod_{i=l+1}^m g_1^{\frac{a_i(\beta l_i(s)+\alpha r_i(s)+o_i(s))}{\delta}} \cdot {g_1^{\frac{h(s)t(s)}{\delta}}}\cdot g_1^{r_rA(s)}\cdot g_1^{r_lB(s)} \cdot g_1^{-r_lr_r\delta}$

将$(g_1^{A(s)},g_2^{B(s)},g_1^{C(s)})$当成证明。
verifier计算：$g_1^{C_v(s)}=\prod_{i=0}^l g_1^{a_i}\cdot \{g_1^{\frac{\beta l_i(s)+\alpha r_i(s)+o_i(s)}{\gamma}}\}_{i=0}^{l}$(这里的$a_i$即statement，prover要求解的问题)

最后验证$e(g_1^{A(s)},g_2^{B(s)})=e(g_1^{\alpha},g_2^{\beta})\cdot e(g_1^{C_v(s)},g_2^\gamma)\cdot e(g_1^{C(s)},g_2^{\delta})=g_t^{\alpha\beta}\cdot e(g_1^{C_v(s)},g_2^\gamma)\cdot e(g_1^{C(s)},g_2^{\delta})$

等式是否成立。

详细分析见星想法的文章：[零知识证明 - Groth16算法介绍](https://mp.weixin.qq.com/s/SguBb5vyAm2Vzht7WKgzug)以及Groth16原始论文，且除了Groth16，zk-SNARKs还有很多其他改进方案。

这样的话，证明就只有三个椭圆曲线群元素了，大大减少了证明大小，但是groth16是有取舍的。

groth16用$\alpha$ 和$\beta$保证系数一致性，并且用$\alpha \cdot \beta$限制证明中必包含这两个，然后用$\gamma$和$\delta$限制l r o之间的串用问题。但是groth16无法保证no-malleable，也就是说，你可以很简单的用已有的groth16证明生成一个新的有效证明。

比如有证明$(g_1^{A(s)},g_2^{B(s)},g_1^{C(s)})$，我们可以简单得到$(g_1^{A(s)},g_2^{B(s)}\cdot g_2^{x\delta},g_1^{C(s)}\cdot g_1^{x}\cdot g_1^{A(s)})$，亦可通过验证。

PPIO的朋友针对groth16的可操作性问题写了一篇详细分析：[如何利用 Groth16 的漏洞伪造证明](https://mp.weixin.qq.com/s/PAulyP65AfL2M14zJU606w)

### 5.8 进一步了解

可以进一步阅读零知识证明相关论文，或者直接了解一些零知识证明开源库，思考下和自己熟悉的领域有什么结合点。

安比试验室收集了一堆零知识证明的资料：[零知识证明学习资源汇总](https://mp.weixin.qq.com/s/-LU4FsFKt7ebX4sbKXNylA)

以及github仓库[awesome-zero-knowledge-proofs](https://github.com/matter-labs/awesome-zero-knowledge-proofs)

下面是一些开源库，可以实操一下零知识证明。

- [libsnark (C++)](https://github.com/scipr-lab/libsnark)
- [great tutorial](https://github.com/christianlundkvist/libsnark-tutorial)
- [bellmnan (rust)](https://github.com/zkcrypto/bellman/)
- [demo circuit](https://github.com/ebfull/bellman-demo)
- [jsnark (Java, bindings to libsnark)](https://github.com/akosba/jsnark)
- [snarky (Ocaml, from authors of Coda)](https://github.com/o1-labs/snarky)
- [zokrates (toolbox for zkSNARKs on Ethereum)](https://github.com/Zokrates/ZoKrates)

谢谢大家的阅读，如发现文章有错漏请指正，可联系微信@xcshuan0608，备注：区块链技术交流+组织+姓名。