zk-SNARK, Pinocchio

在任意的「零知识证明」系统中，都有一个证明者（prover）在不泄漏任何额外信息的前提下要让验证者（verifier）确信某些陈述（Statement）是正确的。零知识证明协议应当满足下面三个性质：

1. 完备性（Completeness）：只要「陈述」是正确的，prover 就可以让 verifier 确信；也就是说 verifier 无法欺骗 prover；
   
2. 可靠性（Soundness）：如果「陈述」是错误的，那么作弊的 prover 就没有办法让 verifier 相信；也就是说 prover 无法欺骗 verifier；
   
3. 零知识（Zero-knowledge）：协议的交互仅仅揭露「陈述」是否正确而不泄漏任何其它的信息。
   

下面是零知识证明的一些应用场景。

1、证明关于隐私数据的声明：

• 一个人 A 的银行账户金额多于 X；
  
• 去年，一家银行未与实体 Y 进行交易；
  
• 在不暴露全部 DNA 数据的前提下匹配 DNA；
  
• 一个人的信用评分高于 Z。
  

2、匿名认证：

• 在不揭露身份的情况下（比如登录密码），证明请求者 R 有权访问网站的受限区域；
  
• 证明一个人来自一组被允许的国家/地区列表中的某个国家/地区，但不暴露具体是哪个；
  
• 证明一个人持有地铁月票，而不透露卡号。
  

3、匿名支付：

• 付款完全脱离任何一种身份；
  
• 纳税而不透露收入。
  

4、外包计算：

• 将昂贵的计算外包，并在不重新执行的情况下验证结果是否正确；它打开了一种零信任计算的类别；
  
• 改进区块链模型，从所有节点做同样的计算，到只需一方计算然后其它节点进行验证。
  

现在我们来看一下由数学方程式表示的多项式，它可以被画成坐标系上的一条曲线，如图 1 所示。

图 1 中曲线对应的多项式为： $f(x)=x^3-6x^2+11x-6$ 。多项式的阶数 $d$ 就是 $x$ 的最大指数，这个多项式的阶数是 $d=3$ 。

多项式有一个非常好的特性，就是 如果我们有两个阶为 $d$ 的不相等多项式，它们相交的点数不会超过 $d$ 。 例如，修改一下原来的多项式为 $x^3-6b^2+10x-5$ ，并在图上用绿色标出，如图 2 所示。

在 $x$ 可以选择的所有值中，最多只有 3 个值（即多项式的阶数）能够使上面两个多项式相等，其它的值都是不相等的。

代数的基本原理告诉我们， 对于一个阶数为 $d$ 的多项式最多有 $d$ 个解。 这个结论和前面说的“如果我们有两个阶为 $d$ 的不相等多项式，它们相交的点数不会超过 $d$ ”表达的是同一个意思。

事实上， 我们不可能找到两条不同的曲线，它们会在某段区域内重合（它们只会相交于一些点）。

我们来看一个证明问题。

如果一个 prover 声称他知道 verifier 也知道的某个多项式（比如 3 阶多项式 $f(x)=x^3-6x^2+11x-6$ ）。 那么 verifier 怎么证明 prover 没有说谎呢？prover 可以直接公布出多项式，verifier 验证一下即可，但这直接泄露了多项式本身，已经不是零知识证明了。

在不泄露多项式的前提下，我们可以采用下面的简单协议：

1. 在一个较大的范围内（如 $1$ 到 ${10}^{77}$ ），verifier 选择一个随机值 $x$ 并在本地计算多项式结果；
   
2. verifier 将 $x$ 值给到 prover，并让他计算相关的多项式结果；
   
3. prover 代入 $x$ 到多项式计算并将结果给到 verifier；
   
4. verifier 检查本地的计算结果和 prover 的计算结果是否相等，如果相等那就说明 prover 的陈述具有较高的可信度。
   

上面的证明过程为什么可行呢？会不会出现 prover 并不知道多项式 $f(x)=x^3-6x^2+11x-6$ ，他知道的是另外一个多项式，而恰好同一个 $x$ 两个式项式算出的值一样呢？出现这种情况的可能性很小。

上一节介绍过， 如果我们有两个阶为 $d$ 的不相等多项式，它们相交的点数不会超过 $d$ 。 也就是说，假设 prover 不知道 $f(x)=x^3-6x^2+11x-6$ 的情况下，拿另外一个 3 阶多项式作弊，能那么作弊成功的 $x$ 值最多只有 3 个，由于 $x$ 是由 verifier 在一个较大的范围（ $1$ 到 ${10}^{77}$ ）中随机选择的，所以作弊成功的可能性几乎为零（假设选择随机值时只选择 $1$ 到 ${10}^{77}$ 内的整数，那么作弊成功的概率不会超过 $\frac{3}{{10}^{77}}$ ）。当然如果 prover 不拿 3 阶多项式作弊，而是拿一个更高阶的多项式，那么作弊成功的概率会增加。

Schwartz-Zippel 定理：在有限域 $\mathbb{F}$ 上，给定一个 $n$ 元 $d$ 次多项式 $f(x_1,x_2,\cdots ,x_n)$ ，对于 $\mathbb{F}$ 的某个子集 $S$ ，我们从中随机挑选 $n$ 值给每个变量赋值，那么这个多项式等于零的概率小于等于： $$\frac{d}{|S|}$$ 其实，上一节中已经介绍过了 Schwartz-Zippel 定理，只是没有把它形式化而已。两个 3 阶多项式相等，就是一个 3 阶多项式为零。上一节中提到 $x$ 在 $1$ 到 ${10}^{77}$ 中取随机整数时，两个 3 阶多项式恰好相等的概率不超过 $\frac{3}{{10}^{77}}$ ，这表达的就是 Schwartz-Zippel 定理的特殊情况。

我们可以使用下面检查协议来证明 prover 没有说谎（即 prover 知道的 3 阶多项式 $p(x)$ 的两个根分别为 1 和 2 ）：

1. verifier 挑选一个随机值 $r$ ，计算 $t=t(r)$ ，将 $r$ 发送给 prover；
   
2. prover 计算 $h(x)=p(x)/t(x)$ ，并对 $p(r)$ 和 $h(r)$ 进行求值，将计算结果 $p,h$ 提供给 verifier；
   
3. verifier 验证 $p=t\cdot h$ ，如果这个等式成立相等，就意味着 $t(x)$ 是 $p(x)$ 的因式。
   

实践一下，假设 prover 声明他知道的 3 阶多项式为 $p(x)=(x-1)(x-2)x$ ，用下面的例子来执行这个协议：

1. verifier 选一个随机数 23，并计算 $t=t(23)=(23-1)(23-2)=462$ ，然后将 23 发给 prover；
   
2. prover 计算 $h(x)=p(x)/t(x)=x$ , 并对 $p(r)$ 和 $h(r)$ 进行求值， $p=p(23)=10626,h=h(23)=23$ ，将 $p$ 和 $h$ 提供给 verifier；
   
3. verifier 再验证 $p=t\cdot h$ ，即 $10626=462\cdot 23$ ，这显然是正确的，这样陈述就被证明了。
   

上一节的证明中有 3 个严重的问题：

1. prover 可能并不知道他所声称的 $p(x)$ ，他可以先算一下 $t=t(r)$ ，然后随便选择一个数 $h$ ，由此计算出 $p=t\cdot h$ 。因为等式是成立的，所以也能通过 verifier 的校验。比如，prover 计算出来 $t=t(23)=462$ 后，随便选择一个数，如 $h=123$ ，由此计算出 $p=t\cdot h=462\cdot 123=56826$ ，将 $p$ 和 $h$ 提供给 verifier，这也会通过 verifier 的验证。
   
2. 因为 prover 知道随机点 $x=r$ ，他可以构造出一个任意的多项式，这个任意多项式与 $t(r)\cdot h(r)$ 在 $x=r$ 处有共同点。比如，prover 知道 verifier 发送给他的值为 23 后，随便找一个包含 $(x-23)$ 因子的多项式，例如 $p^{\prime }(x)=(x-23{)}^2$ ， 去验证上面协议，照样可以通过验证。
   
3. 在前面的「陈述」中，prover 声称他知道一个特定阶数的多项式，但现在的协议对阶数并没有明确的要求。因而 prover 完全可以拿一个满足因式校验的更高阶数的多项式来欺骗 verifier。比如，尽管要证明 prover 声称知道的 $p(x)=(x-1)(x-2)x=x^3-3x^2+2x$ ，但在上面协议中，prover 使用另外一个更高阶数多项式，如 $p^{\prime }(x)=(x-1)(x-2)x^3=x^5-3x^4+2x^3$ 去验证上面协议，照样可以通过验证。
   

同态加密（Homomorphic encryption）可以解决前面提到的“原始值暴露”的问题。 同态加密允许在密文上进行算术运算，进行算术运算时不用先解密出原文。

同态加密关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。我们举个实际生活中的例子（这个例子摘自 https://www.zhihu.com/question/27645858/answer/37598506 ）。有个叫 Alice 的用户买到了一大块金子，她想让工人把这块金子打造成一个项链。但是工人在打造的过程中有可能会偷金子啊，毕竟就是一克金子也值很多钱。因此能不能有一种方法，让工人可以对金块进行加工，但是不能得到任何金子？

当然有办法啦，Alice 可以这么做：

1. Alice 将金子锁在一个密闭的盒子里面，这个盒子安装了一个手套。
   
2. 工人可以带着这个手套，对盒子内部的金子进行处理。但是盒子是锁着的，所以工人不仅拿不到金块，连处理过程中掉下的任何金子都拿不到。
   
3. 加工完成后。Alice 拿回这个盒子，把锁打开，就得到了金子。
   

这个过程如图 3 所示。

同态加密的思路是选择一个基础的（基数需要具有某些特定的属性）的自然数 $g$ （比如 5），然后我们以要加密的值为指数对 $g$ 进行求幂。例如，如果我们要对 3 进行加密：
$$5^3=125$$
这里 125 就是 3 对应的密文。如果我们想要对原数据（被加密值）乘 2，我们可以以 2 为指数来对这个密文进行计算：
$${125}^2=15625=(5^3{)}^2=5^{2\times 3}=5^6$$

我们不仅可以用 2 来乘以一个未知的值并保持密文的有效性，还可以通过密文相乘来使两个原数据相加，例如原数据上的 $3+2$ 运算，对应密文上的操作就是它们的加密值相乘：
$$5^3\cdot 5^2=5^{3+2}=5^5=3125$$

不过由于基数 5 是公开的，很容易就可以找到被加密的数字。只要将密文一直除以 5，直到结果为 1，那么做除法的次数也就是被加密值的数。如密文 $125$ 除以 5，重复 3 次就是结果 1，重复除法次数就是原数据，这泄露了原数据 3。 为了把基数 g 和原数据（上面例子中的 3）的关系切断，更好地保护原数据，我们在同态加密中引入「模运算」。

先看几个模运算的例子（对 7 取模）：

$$\begin{array}{rl}{5}^1& =5(\mathrm{mod}7)\\ 5^2& =4(\mathrm{mod}7)\\ 5^3& =6(\mathrm{mod}7)\\ & \cdots \\ 5^9& =6(\mathrm{mod}7)\\ & \cdots \\ 5^{15}& =6(\mathrm{mod}7)\\ & \cdots \end{array}$$

引入模运算后，告诉你加密后的值，就很难知道指数（原值）是多少了。比如，告诉你加密后的值为 6，那么 3,9,15 都满足条件，就无法知道原值到底是多少了。

引入模运算后，前面介绍的性质没变：

$$\begin{array}{rlrl}\text{encryption:}& 5^3& & =6(\mathrm{mod}7)\\ \text{multiplication:}& (5^3{)}^2=5^{3\times 2}& & =1(\mathrm{mod}7)\\ \text{addition:}& 5^3\cdot 5^2=5^{3+2}& & =3(\mathrm{mod}7)\end{array}$$

上面第 2/3 个式子的含义是： 对加密后的值取 $n$ 次幂，相当于对原数据乘以数字 $n$ 后再加密；两个加密后的值相乘，相当于对原数据相加后再加密。

我们来明确地说明一下加密函数：

$$E(v)=g^v(\mathrm{mod}m)$$

这里 $v$ 就是我们要加密的值。

有了同态加密后，对于在节 3 中提到的证明问题，可以为它重新设计一个验证协议了，在这个验证协议中，不会暴露原始的随机数了。

在介绍新验证协议之前，先介绍一下已知在 $x$ 处 $x,x^2,x^3$ 的加密值为 $E(x),E(x^2),E(x^3)$ ，如何计算多项式 $p(x)=x^3-3x^2+2x$ 的加密计算结果。

$$\begin{array}{rl}E(p(x))& =g^{p(x)}=g^{x^3-3x^2+2x}=(g^{x^3}{)}^1\cdot (g^{x^2}{)}^{-3}\cdot (g^x{)}^2\\ & =E(x^3{)}^1\cdot E(x^2{)}^{-3}\cdot E(x{)}^2\end{array}$$

现在我们更新一下节 3 中设计的证明协议。

prover 声称他知道一个 $d$ 阶多项式 $p(x)=c_d{x}^d+\cdots +c_1{x}^1+c_0{x}^0$ ，这个多项式包含因子 $t(x)$ （这个多项式前面介绍过，称为目标多项式）。那么 verifier 怎么证明 prover 没有说谎呢？

验证过程如下（在下面的写法中把 $E(v)=g^v(\mathrm{mod}m)$ 直接省写为了 $E(v)=g^v$ ）。

第一步，verifier 进行下面操作：

1. 取一个随机数 $s$ ，也称为秘密值；
   
2. 分别计算 $i$ 取值为 $0,1,\cdots ,d$ 时 $s^i$ 的加密结果，即 $E(s^i)=g^{s^i}$ ；
   
3. 代入 $s$ 计算未加密的目标多项式 $t(s)$ ；
   
4. 将第 2 步计算出来的加密值 $g^{s^0},g^{s^1},g^{s^2},\cdots ,g^{s^d}$ 提供给 prover。
   

第二步，prover 进行下面操作：

1. 计算多项式 $h(x)=p(x)/t(x)$ ；
   
2. 使用加密值 $g^{s^0},g^{s^1},g^{s^2},\cdots ,g^{s^d}$ 和 prover 所已知的 $p(x)$ 的系数 $c_0,c_1,\cdots ,c_d$ 计算出 $p(x)$ 的加密值，采用式子 $E(p(s))=g^{p(s)}=(g^{s^d}{)}^{c_d}\cdots (g^{s^1}{)}^{c_1}\cdot (g^{s^0}{)}^{c_0}$ 即可，其结果记为 $g^p$ ；
   
3. 使用和上一步相同的方法计算出 $h(s)$ 的加密值 $E(h(s))$ ，记为 $g^h$ ；
   
4. 把上两步的结果 $g^p$ 和 $g^h$ 提供给 verifier。
   

最后，verifier 进行下面验证：

1. 在加密空间中，校验 $g^p={\left(g^h\right)}^{t(s)}=g^{t(s)\cdot h}$ 是否成立。如果成立，则说明 $p=t(s)\cdot h$ ，从而 prover 所知道的多项式 $p(x)$ 有很大的可能性确实具有因子 $t(x)$ 。
   

在这个证明协议中，prover 并不知道跟秘密值 $s$ 相关的任何信息，这就使得他很难提出不合法但是能够匹配验证的计算结果（节 3.2 中提到的前 2 个问题得到了解决）。

尽管这个协议中对 prover 作弊的手段进行了限制，但 prover 依然可以在实际根本不使用 verifier 所提供的加密值进行计算，而是通过其它的方式来伪造证明。也就是说，在 prover 提交给 verifier 的两个值 $g^p$ 和 $g^h$ 时，并不是按照协议规定的方式计算出来的，而是 prover 用其它方式得到的只要满足条件 $z_p=(z_h{)}^{t(s)}$ 的 $z_p,z_h$ ，如果 prover 用 $z_p,z_h$ 来分别伪造 $g^p$ 和 $g^h$ ，下一步 verifier 验证时，照样可以通过验证。为了堵住这个漏洞，请看节 4.3 的内容。

上一节的验证协议中有个漏洞：prover 可能使用另外的值 $z_p,z_h$ 来伪造 $g^p$ 和 $g^h$ 。我们需要想办法确保 prover 给出的值（ $g^p$ 和 $g^h$ ）就是通过 verifier 提供给 prover 的加密值 $g^{s^0},g^{s^1},g^{s^2},\cdots ,g^{s^d}$ 计算而来。

我们看一个由一个变量和一个系数组成的一阶多项式的简单例子，对应的 $s$ 的加密值为 $E(s)=g^s$ 。这里我们要做的就是确保 prover 是拿 $g^s$ （而不是其他值）与系数 $c$ 做同态相乘的。所以结果一定是这个形式：
$${\left(g^s\right)}^c$$

通过 Knowledge-of-Exponent Assumption（简称 KEA）方法可以实现上面的目标。 后文将描述 KEA。

  Alice                                                                  Bob

(a, a^\alpha mod n)   ----希望 Bob 对这两个值只进行指数取模运算---->
                                                                        黑盒子
                       <----- 运算后返回 (b, b') -------


如果 Alice 验证 b^\alpha = b' mod n 成立，则数 b 确实是由 Bob 对 a 进行「指数取模」运算而来。

Cryptographic pairings (bilinear map) 是一个数学结构，记为函数 $e(g^{\ast },g^{\ast })$ ，它给定一个数据集中的两个加密的输入（即 $g^a,g^b$ ），可以将他们确定性地映射到另一组不同的输出数据集上的它们的乘积，即 $e(g^a,g^b)=e(g,g{)}^{ab}$ ，如图 4 所示。

因为源数据集和输出数据集是不同的，所以一个配对的结果不能用做其他配对计算的输入。我们可以将输出集（也称为“目标集”）视为“不同的宇宙”。因而我们不能用另一个加密值乘以结果，而且配对这个名称本身也表明了，我们一次只能将两个加密值相乘。 注：乍一眼看过去，这个限制可能会阻碍相关功能的实现，但在 zk-SNARK 中这反而是保证安全模式的最重要性质，参见节 6.4。

在某种意义上，这个类似于一个哈希函数，他将所有可能的输入值映射到输出值的集合中的一个元素上，而且这个过程是不可逆的。

配对函数 $e(g,g)$ 可以初步地（严格来说是不对的）类比成“交换”每一个输出的基数和指数的操作，使得基数 $g$ 在交换过程中被修改成了指数的方式，即 $g^a\to a^{\mathbf{g}}$ （注：这是两个不同的 g，所以使用了不同的字体）。“被转换”的两个输入一起被修改了，这样原始值 $a$ 和 $b$ 就在同一个指数下相乘了，即：
$$e(g^a,g^b)=a^{\mathbf{g}}\cdot b^{\mathbf{g}}=(ab{)}^{\mathbf{g}}\text{(注：这仅是个类比，是不对的)}$$

因为基数在“转换”中被修改了，所以在另一个配对中不能再使用这个结果 $(ab{)}^{\mathbf{g}}$ ，也就是说 $e((ab{)}^{\mathbf{g}},g^c)$ 并不会构造出想要的加密乘积 $abc$ 。

配对的核心性质可以表示成下面的等式：
$$e(g^a,g^b)=e(g^b,g^a)=e(g^{ab},g^1)=e(g^1,g^{ab})=e(g^1,g^a{)}^b=e(g^1,g^1{)}^{ab}=\cdots$$

严格来说，一个 Cryptographic pairing 的结果是在目标集的一个不同生成元 $\mathbf{g}$ 下对原始值乘积的加密，即 $e(g^a,g^b)={\mathbf{g}}^{ab}$ 。 因而它具备同态加密的性质，也就是说我们可以把多个 Cryptographic pairing 的加密乘积放到一起：
$$e(g^a,g^b)\cdot e(g^c,g^d)={\mathbf{g}}^{ab}\cdot {\mathbf{g}}^{cd}={\mathbf{g}}^{ab+cd}=e(g,g{)}^{ab+cd}$$

Cryptographic pairing 利用“椭圆曲线”来实现上面性质，也可称“Elliptic Curve Pairings”。

关于 Cryptographic pairings 的更多知识，可参考 Pairings for beginners, by Craig Costello 。

有了 Cryptographic pairing，我们现在就准备去设置安全公开且可复用的参数了。假定一下我们让一个诚实的参与方来生成秘密值 $s$ 和 $\alpha$ 。 一旦 $\alpha$ 和所有必要的 $s$ 的幂及其对应的 $\alpha$ 变换被加密了（即生成 $g^{\alpha },g^{s^i},g^{\alpha s^i},i=0,1,\cdots ,d$ ），那么原始数据就必须要被删除。

注：Zcash 团队在论文 A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK 中提出了 MPC 协议来进行“可信任参与方的 Setup”。

这些参数通常被称为 common reference string 或者 CRS。CRS 生成后，任何的 prover 和任何的 verifier 都可以使用它来构造非交互式的零知识证明协议。CRS 的优化版本将包含目标多项式的加密值 $g^{t(s)}$ ，尽管这个值并不重要。

CRS 可分成两组（ $i=0,1,\cdots ,d$ ）：

• proving key（也被称为 evaluation key）： $(g^{s^i},g^{\alpha s^i})$
  
• verification key： $(g^{t(s)},g^{\alpha })$
  

只要能够乘以加密值，verifier 就可以在协议的最后一步验证多项式了。有了 verification key，verifier 就可以处理从 prover 那里得到的加密多项式的值 $g^p,g^h,g^{p^{\prime }}$ ，进行下面两个校验即可：

• 在加密空间中校验 $p=t\cdot h$ ，即校验 ：
  

$$e(g^p,g^1)=e(g^t,g^h)$$

• 校验多项式的限制：
  

$$e(g^p,g^{\alpha })=e(g^{p^{\prime }},g^1)$$

可信任参与方的 Setup 很有效率，但众多 CRS 用户也必须要相信生成者确实删除了 $\alpha$ 和 $s$ ，不过我们没有办法证明生成者删除了它们。因而很有必要去最小化或者消除这种信任。否则一个不诚实的参与方就可以构造假证明而不被发现。

一种解决办法就是由多个参与方使用前面小节中介绍的数学工具来生成一个组合式 CRS，这样这些参与方就都不知道“秘密”了。 下面是一个实现方案，我们假设有三个参与者 Alice，Bob 和 Carol ，对应为 A，B 和 C，其中 $i=1,2,\cdots ,d$ ：

• Alice 选择随机数 $s_A$ 和 ${\alpha }_A$ ，然后公开她的 CRS： $(g^{s_A^i},g^{{\alpha }_A},g^{{\alpha }_A{s}_A^i})$
  
• Bob 选择他的随机数 $s_B$ 和 ${\alpha }_B$ ，然后通过同态乘法结合 Alice 的 CRS： $((g^{s_A^i}{)}^{s_B^i},(g^{{\alpha }_A}{)}^{{\alpha }_B},(g^{{\alpha }_A{s}_A^i}{)}^{{\alpha }_B{s}_B^i})=(g^{(s_A{s}_B{)}^i},g^{{\alpha }_A{\alpha }_B},g^{{\alpha }_A{\alpha }_B(s_A{s}_B{)}^i})$ 然后公开两方 Alice-Bob 的 CRS 结果： $(g^{s_{AB}^i},g^{{\alpha }_{AB}},g^{{\alpha }_{AB}{s}_{AB}^i})$
  
• Carol 用她的随机数 $s_C$ 和 ${\alpha }_C$ 做同样的事： $((g^{s_{AB}^i}{)}^{s_C^i},(g^{{\alpha }_{AB}}{)}^{{\alpha }_C},(g^{{\alpha }_{AB}{s}_{AB}^i}{)}^{{\alpha }_C{s}_C^i})=(g^{(s_A{s}_B{s}_C{)}^i},g^{{\alpha }_A{\alpha }_B{\alpha }_C},g^{{\alpha }_A{\alpha }_B{\alpha }_C(s_A{s}_B{s}_C{)}^i})$ 然后公开 Alice-Bob-Carol 的 CRS 结果： $(g^{s_{ABC}^i},g^{{\alpha }_{ABC}},g^{{\alpha }_{ABC}{s}_{ABC}^i})$
  

这个协议最后我们就获得了一个混合的 $s^i=s_A^i{s}_B^i{s}_C^i$ 和 $\alpha ={\alpha }_A{\alpha }_B{\alpha }_C$ 。除非他们串谋，否则参与者们互相之间并不知道其他人的秘密参数。实际上，一个参与者必须要和其它所有的参与者串谋才能得到 $s$ 和 $\alpha$ ，这样在所有的参与者中只要有一个是诚实的，就没有办法伪造证明。

有一个问题是如何验证参与者在生成 CRS 时用的随机数值是一致的（有效的），因为攻击者可以生成多个不同的随机数 $s_1,s_2,\cdots$ 和 ${\alpha }_1,{\alpha }_2,\cdots$ ，然后代入这些不同的随机数去执行 $s$ 的不同次幂计算（或提供随机数作为一个 CRS 的扩充），从而导致 CRS 无效或者不可用。

庆幸的是，因为我们可以使用配对来乘以加密值，所以我们就可以从第一个参数开始逐一执行一致性校验，并且确保了每个参数都源于前一个。

• 我们用 $s$ 的 1 次幂作为标准来校验每一个其它次幂的值与之是否保持一致： $e(g^{s^i},g)={e(g^{s^1},g^{s^{i-1}})|}_{i\in 2,3,\cdots ,d}$ 。例如：对于 2 次幂这样验证： $e(g^{s^2},g)=e(g^{s^1},g^{s^1})\Rightarrow e(g,g{)}^{s^2}=e(g,g{)}^{s^{1+1}}$ ；对于 3 次幂这样验证： $e(g^{s^3},g)=e(g^{s^1},g^{s^2})\Rightarrow e(g,g{)}^{s^3}=e(g,g{)}^{s^{1+2}}$
  
• 我们现在再验证一下前面步骤中 $\alpha$ 变换后的值是否正确： $e(g^{s^i},g^{\alpha })={e(g^{\alpha s^i},g)|}_{i\in [d]}$ 。记号 $[d]$ 表示 $1,2,\cdots ,d$ ，后文将大量使用这个记号。例如：对于 3 次幂这样验证： $e(g^{s^3},g^{\alpha })=e(g^{\alpha s^3},g)\Rightarrow e(g,g{)}^{s^3\cdot \alpha }=e(g,g{)}^{\alpha s^3}$
  

当我们在验证每一个参与者秘密参数的一致性时，要注意参与者生成 CRS 的过程并没有强制后一个参与者（就是我们例子中的 Bob 和 Carol）都要使用前面已经公开的 CRS。因而如果一个攻击者是链上的最后一个参与者，他可以像链上的第一个参与者一样忽略前面的 CRS 随便构造一个有效的 CRS，这样他就变成了唯一一个知道秘密 $s$ 和 $\alpha$ 的人。

为了解决这个问题，我们可以额外再要求除了第一个以外的每一个参与者去加密然后公开他的参数。例如，Bob 同时还要公开：
$${(g^{s_B^i},g^{{\alpha }_B},g^{{\alpha }_B{s}_B^i})|}_{i\in [d]}$$

这样，为了确认 Bob 的 CRS 确实是乘以了 Alice 的参数后获得的，验证下面式子即可：

$$\begin{array}{rl}e(g^{s_{AB}^i},g)& =e(g^{s_A^i},g^{s_B^i})\\ e(g^{{\alpha }_{AB}},g)& =e(g^{{\alpha }_A},g^{{\alpha }_B})\\ e(g^{{\alpha }_{AB}{s}_{AB}^i},g)& =e(g^{{\alpha }_A{s}_A^i},g^{{\alpha }_B{s}_B^i})\end{array}$$

类似的方法，Carol 也可证明她的 CRS 是乘以了 Alice-Bob 的 CRS 后正常获得的。

这是一个健壮的 CRS 设置模式，它并不完全依赖于单个参与者。事实上，即使其它所有的参与者都串谋了，只要有一个参与者是诚实的，他能够删除并且永远不共享它的秘密参数，这个 CRS 就是有效的。

到目前为止，我们已经介绍了多项式的 SNARK (Succinct Non-Interactive Argument of Knowledge) 协议。

为简洁起见，我们将使用大括号来表示由旁边的下标填充的一组元素，例如： $\{s^i{\}}_{i\in [d]}$ 表示集合 $s^1,s^2,\cdots ,s^d$

这里再重复一下所要证明的问题。 prover 声称他知道一个 $d$ 阶多项式 $p(x)=c_d{x}^d+\cdots +c_1{x}^1+c_0{x}^0$ ，这个多项式包含因子 $t(x)$ （称为目标多项式）。 通过下面步骤可证明 prover 没有说谎。

• Setup
  
  • 挑选随机值 $s,\alpha$
    
  • 计算加密值 $g^{\alpha },\{g^{s^i}{\}}_{i\in [d]},\{g^{\alpha s^i}{\}}_{i\in 0,\cdots ,d}$
    
  • 生成 proving key: $(\{g^{s^i}{\}}_{i\in [d]},\{g^{\alpha s^i}{\}}_{i\in 0,\cdots ,d})$
    
  • 生成 verification key: $(g^{\alpha },g^{t(s)})$
    
• Proving
  
  • 求多项式 $h(x)=p(x)/t(x)$
    
  • 使用 $\{g^{s^i}{\}}_{i\in [d]}$ 计算多项式 $g^{p(s)}$ 和 $g^{h(s)}$ 的值
    
  • 使用 $\{g^{\alpha s^i}{\}}_{i\in [d]}$ 计算多项式 $g^{\alpha p(s)}$ 的值
    
  • 选择随机数 $\delta$
    
  • 构造 $(g^{\delta p(s)},g^{\delta h(s),g^{\delta \alpha p(s)}})$ ，它们被称为“提供的证明”，简记为 $(g^p,g^h,g^{p^{\prime }})$
    
• Verification
  
  • 验证多项式约束： $e(g^{p^{\prime }},g)=e(g^p,g^{\alpha })$
    
  • 验证多项式系数： $e(g^p,g)=e(g^{t(s)},g^h)$
    

我们用 zk-SNARK 协议来解决多项式问题的知识，不过这是一个有局限的例子。因为大家可以说 prover 只要用另外一个有界的多项式去乘以 $t(x)$ 就可以很容易得构造出一个能够通过测试的多项式 $p(x)$ ，并且这种结构也是有效的。

verifier 知道 prover 有一个有效的多项式，但是并不知道是哪一个。我们可以利用多项式的其他性质添加额外的证明，如：被多个多项式整除，是某个多项式的平方等等。

下面总结一下这篇文章中是如何一步一步解决了下面的几个问题：

• 保证 prover 的证明是按照规则正确构造的 ——> KEA
  
• 保证知识的零知性 ——> “无成本的” $\delta$ 变换
  
• 可复用证明 ——> 非交互式
  
• 非交互中如何设置安全公开且可复用的参数 ——> 参数加密，verifier 借助密码配对进行验证
  
• 保证参数的生成者不泄密 ——> 多方的 Setup
  

至此，一个用来证明多项式知识的完整的 zk-SNARK 协议就构造出来了，不过现在的协议在通用性上依然还有很多限制，后面的文章将继续介绍如何构造通用的 zk-SNARK。

来看一段用伪代码写的简单程序：

Algorithm 1: Operation depends on an input
————————————————————————————————————————————————————————————————————

function calc(w, a, b)
    if w then
        return a × b
    else
        return a + b
    end if
end function

看起来这段程序和我们协议里面的多项式并没有什么关系。我们现在就 需要找到一种方式来将程序转换成多项式。 第一步是将程序转换成数学语言，这个相对简单一些，声明可以表达成下面的形式（假定 $w$ 是 0 或 1）：
$$f(w,a,b)=w(a\times b)+(1-w)(a+b)$$

执行 $calc(1,4,2)$ 和对 $f(1,4,2)$ 求值都可以得到相同的结果：8。如果执行 $calc(0,4,2)$ 和 $f(0,4,2)$ 也都能够得到 6。其实 我们可以用这种方法表达任何形式的有限程序。

接下来（上面的例子）需要我们证明的是，对于表达式 $f(w,a,b)$ ，输入为 $(1,4,2)$ 时输出为 8，换句话说，我们要校验多项式：
$$w(a\times b)+(1-w)(a+b)=8$$

尽管已经将程序转换成了由数学语言表达的一般计算形式，我们还是需要再把它翻译成多项式。我们先来仔细研究一下计算的本质。任何计算的内核都是由以下形式的基本运算组成的：

$$\text{左操作数}\text{运算操作符}\text{右操作数}=\text{输出}$$

两个操作数（即值）与一个运算符（即 +,-,×,÷）放在一起执行运算。例如操作数是 2 和 3，运算符为乘，那么运算出来就是 $2\times 3=6$ 。由于任何复杂的计算（或者程序）都是由一系列这样的基本运算组成的，所以首先我们需要知道在多项式中单个运算是怎么表示的。

如果一个 prover 声称知道某两个数字的乘积，verifier 要怎样去验证呢？为了证明单个计算的正确性，我们就 必须首先确保所提供的操作数的输出（结果）的正确性。 我们再来看一下运算的形式：
$$\text{左操作数}\text{运算操作符}\text{右操作数}=\text{输出}$$

类似地，我们也可以将其表示为一个运算多项式：
$$l(x)\text{运算操作符}r(x)=o(x)$$

在一些选定的取值 $x=a$ 处的运算：

• $l(x)$ ：表示（运算结果为）左操作数
  
• $r(x)$ ：表示（运算结果为）右操作数
  
• $o(x)$ ：表示运算结果（输出）
  

因而在计算过程中如果操作数和结果都可以用多项式的形式正确地表示出来，那么 $l(a)operatorr(a)=o(a)$ 就能够成立。也就是说假如输出多项式 $o(x)$ 所代表的值是由运算符在操作数多项式 $l(x)$ 和 $r(x)$ 上进行某种运算得出的正确结果，那么我们把输出多项式 $o(x)$ 放到等式的左边就能够得到： $l(a)operatorr(a)-o(a)=0$ ，这也就表明了当取值为 $a$ 时多项式 $l(x)operatorr(x)-o(x)$ 计算结果为 0 。那么只要多项式是有效的，运算多项式就一定有一个根 $a$ 。因此，根据前面的基础这个多项式里面一定包含因式 $(x-a)$ ，这就是我们要证明的目标多项式，即 $t(x)=x-a$ 。

例如，我们来看一个运算： $3\times 2=6$ 。可以用一个简单的多项式表示它： $l(x)=3x,r(x)=2x,o(x)=6x$ ，取 $a=1$ 进行计算，即 $l(1)=3;r(1)=2;o(1)=6$ ，如图 8 所示。

$l(x)\times r(x)-o(x)=2x\times 3x-6x=6x^2-6x=6x(x-1)$ ，显然 $l(x)\times r(x)-o(x)$ 是有因子 $x-1$ 的。

因而如果 prover 用 $l(x),r(x),o(x)$ 这些多项式来代替 $p(x)$ ，因为它们依然可以被 $t(x)$ 整除，所以 verifier 就可以认为它们是有效的。相反，如果 prover 尝试用 4 来代替输出值去欺骗 verifier ，即 $o(x)=4x$ ，那么运算多项式就变成了 $6x^2-4x=0$ ，如图 9 所示。

图 9 中这个多项式并没有 $x=1$ 的解，因而 $l(x)\times r(x)-o(x)$ 就不能被 $t(x)$ 整除。因而 verifier 不会接受 4 这个计算结果。

现在我们来修改一下最新协议使它支持单个乘法计算的证明。在节 6.4 中，我们已经有证明多项式 $p(x)$ 的知识了，只不过现在要计算的是三个多项式 $l(x),r(x),o(x)$ 。我们可以定义 $p(x)=l(x)\times r(x)-o(x)$ ，但这里存在两个争议点。首先，在我们的协议中证明阶段是不能做加密值乘法计算的（即 $l(s)\times r(s)$ ），因为配对只能用一次，这个要用在校验多项式的约束上。第二，这里给 prover 留下了一个可以修改多项式结构但依然保留有效因式 $t(x)$ 的机会，例如可以令 $p(x)=l(x)$ 或者 $p(x)=l(x)-r(x)$ 甚至是 $p(x)=l(x)\times r(x)+o(x)$ ，只要这里的 $p(x)$ 还保留着根 $a$ 就可以了。这个修改本质上是让证明的内容变成了别的声明，所以这样是不行的。

所以 prover 必须要分别提供多项式 $l(s),r(s),o(s)$ 值的证明，即协议必须修改要证明的多项式的知识。verifier 在加密空间中要验证的是 $l(s)\times r(s)–o(s)=t(s)h(s)$ 。verifier 可以使用密码学配对来执行乘法，但还有一个小问题就是做减法（ $–o(x)$ ）是非常昂贵的计算（这需要去找到一个 $g^{o(s)}$ 的逆向转换），这里我们可以把 $o(x)$ 移到等式右边来： $l(x)r(x)=t(x)h(x)+o(x)$ 。在加密空间中，verifier 的验证就可以转换成：

$$\begin{array}{rl}e(g^{l(s)},g^{r(s)})& =e(g^{t(s)},g^{h(s)})\cdot e(g^{o(s)},g)\\ e(g,g{)}^{r(s)}& =e(g,g{)}^{t(s)h(s)}\cdot e(g,g{)}^{o(s)}\\ e(g,g{)}^{l(s)r(s)}& =e(g,g{)}^{t(s)h(s)+o(s)}\end{array}$$

保持 setup 阶段（参见节 6.4）不变，协议更新为：

• Proving
  
  • 计算多项式 $h(x)=\frac{l(x)\times r(x)-o(x)}{t(x)}$
    
  • 使用 $\{g^{s^i}{\}}_{i\in [d]}$ 计算多项式 $g^{l(s)},g^{r(s)},g^{o(s)},g^{h(s)}$ 的值
    
  • 使用 $\{g^{\alpha s^i}{\}}_{i\in [d]}$ 计算多项式 $g^{\alpha l(s)},g^{\alpha r(s)},g^{\alpha o(s)}$ 的值
    
  • 构造 $(g^{l(s)},g^{r(s)},g^{o(s)},g^{h(s)},g^{\alpha l(s)},g^{\alpha r(s)},g^{\alpha o(s)})$ ，它们被称为“提供的证明”，简记为 $(g^l,g^r,g^o,g^h,g^{l^{\prime }},g^{r^{\prime }},g^{o^{\prime }})$
    
• Verification
  
  • 验证多项式约束：$e(g^{l^{\prime }},g)=e(g^l,g^{\alpha }),e(g^{r^{\prime }},g)=e(g^r,g^{\alpha }),e(g^{o^{\prime }},g)=e(g^o,g^{\alpha })$
    
  • 验证运算的有效性： $e(g^l,g^r)=e(g^{t(s)},g^h)\cdot e(g^o,g)$
    

这个协议就能够证明两个值相乘的计算结果是正确的了。

你可能注意到了在这个新的协议中我们放弃了零知识部分（即没有引入节 6.4 中用于实现零知识的随机数 $\delta$ ）。这么做是为了简化协议的变换。后面的章节（节 7.12）我们会再变回零知识。