---
tags: ZKSnark
---
# ZKSanrk 入门分享（一）

## 介绍

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) 确实是一种非常精妙的方法，它可以在不揭示任何信息的前提下证明某个论断为真。但首要问题是，它为什么有用？

其实零知识证明在无数的应用中都具备优势，包括：

- 证明关于隐私数据的声明：

- 一个人 A 的银行账户金额多于 X
- 去年，一家银行未与实体 Y 进行交易
- 在不暴露全部 DNA 数据的前提下匹配 DNA
- 一个人的信用评分高于 Z
- 匿名认证：
- 在不揭露身份的情况下（比如登录密码），证明请求者 R 有权访问网站的受限区域
- 证明一个人来自一组被允许的国家/地区列表中的某个国家/地区，但不暴露具体是哪个
- 证明一个人持有地铁月票，而不透露卡号
- 匿名支付：

- 付款完全脱离任何一种身份
- 纳税而不透露收入
- 外包计算
- 将昂贵的计算外包，并在不重新执行的情况下验证结果是否正确；它打开了一种零信任计算的类别
- 改进区块链模型，从所有节点做同样的计算，到只需一方计算然后其它节点进行验证

在任意的「零知识证明」系统中，都有一个 prover 在不泄漏任何额外信息的前提下要让 verifier 确信某些陈述（Statement）是正确的。例如 verifier 仅能知道 prover 的银行账户金额超过 X（也就是不披露实际金额）。协议应当满足下面三个性质：

- 完整性 —— 只要「陈述」是正确的，prover 就可以让 verifier 确信
- 可靠性 —— 如果「陈述」是错误的，那么作弊的 prover 就没有办法让 verifier 相信
- 零知识 —— 协议的交互仅仅揭露「陈述」是否正确而不泄漏任何其它的信息

## 证明的媒介
这里我们先不要去管零知识，非交互性，其形式和适用性这些概念，就从尝试证明一些简单的东西开始。

想象一下我们有一个长度为10 的位数组，现在要向 verifier（例如，程序）证明这样一个陈述：所有的位都被设置成了 1。


verifier 一次只能检查一位。为了验证这个陈述，我们以某种任意的顺序读取元素并检查其是否确实等于 1 。如果第一次抽样检查的结果是 1，就设置「陈述」的可信度为 ⅒= 10％，否则，如果等于 0，就说明「陈述」是错误的。验证者继续进行下一轮验证，直到获得足够的可信度为止。假如在一些场景下要信任 prover 需要至少 50% 的可信度，那就意味着必须执行 5 次校验。但假如在其它一些场景下需要 95% 的可信度，就需要检查所有的元素。很明显这个证明协议的缺点是必须要根据元素的数量进行检查，如果我们处理数百万个元素的数组，这么做是不现实的。

现在我们来看一下由数学方程式表示的多项式，它可以被画成坐标系上的一条曲线：
上面的曲线对应多项式: f(x) = x³ – 6x² +11x– 6。多项式的阶数取决于 x 的最大指数，当前多项式的阶数是 3。

多项式有一个非常好的特性，就是如果我们有两个阶为 d 的不相等多项式，他们相交的点数不会超过 d。例如，稍微修改一下原来的多项式为 x³ – 6x² + 10x– 5 （注：请注意这里只修改了多项式的最后一个系数，6改成了5）并在图上用绿色标出：
这一点微小的修改就产生了变化很大的曲线。事实上，我们不可能找到两条不同的曲线，他们会在某段区域内重合（他们只会相交于一些点）。
这是从找多项式共同点方法中得出的性质。如果要查找两个多项式的交点，就要先令它们相等。例如，要找到多项式与 x 轴的交点（即 f(x) = 0），我们就要令 x³ – 6x² + 11x – 6 = 0，等式的解就是共同点：x= 1 ，x= 2 和 x= 3。在上面图中也可以很清晰得看出这些解，也就是图上蓝色曲线和 x 轴相交的地方。

同样，我们也可以令上文中原始的多项式和修改后的多项式相等，找到它们的交点。

x³ – 6x² + 11x – 6 =x³ – 6x² + 10x – 5

x-1=0
多项式化简后的结果阶数为 1，它有一个很明显的解 x = 1。因而这两个多项式有一个交点。

任意一个由阶数为 d 的多项式组成的等式，最后都会被化简为另外一个阶数至多为 d 的多项式，这是因为等式中没有能够用来构造更高阶数的乘法。例如：5x³ + 7x² – x + 2 = 3x³ – x² + 2x– 5，简化为 2x³ + 8x² – 3x + 7 = 0。另外代数的基本原理也告诉我们，对于一个阶数为 d 的多项式至多有 d 个解（以下部分将对此进行详细介绍），因而也就至多有d 个共同点。

所以我们可以得出结论，任何多项式在任意点的计算结果都可以看做是其唯一身份的表示。我们来计算一下当 x = 10 时，示例多项式的结果。

x³ – 6x² +11x - 6 = 504

x³ – 6x² +10x - 5 = 495

事实上，在 x 可以选择的所有值中，至多只有三个值能够使这些多项式相等，其它的值都是不相等的。

这也是为什么如果一个 prover 声称他知道一些 verifier 也知道的多项式（无论多项式的阶数有多大）时，他们就可以按照一个简单的协议去验证：

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

例如，我们把 x 的取值范围定在 1 到 10⁷⁷, 那么计算结果不同的点的数量，就有 10⁷⁷ – d 个。因而 x 偶然“撞到”这 d 个结果相同的点中任意一个的概率就等于$\frac{d}{10^{77}}$(可以认为几乎不可能)

这个小节我们了解了一个多项式的性质：我们不可能找到共享连续段的两条不相等曲线，也就是任何多项式在任意点的计算结果都可以看做是其唯一身份的表示。也就是说只要能证明多项式上的某个随机点就可以证明这个多项式。这就是著名的**Schwartz–Zippel lemma** 定理。可以说zksnark核心便是基于这个定理进行推论的，这也是为什么即使可能存在其他的证明媒介，**多项式依然是 zk-SNARK 相对核心的部分**。

现在的协议相比于之前的抽样检查，效率已经提升了很多，如果多项式的阶d远小于x的取值范围，那么我们就可以几乎100%相信prove知道该多项式。

## 一个多项式的非交互零知识
### 证明多项式的知识

我们的讨论从证明多项式的知识开始，再将证明协议逐步转换成一种通用的方法，在这个过程中我们也将发现多项式的很多其它性质。

但是到目前为止，我们的协议还只是一个很弱的证明，因为协议中并没有采取任何措施去保证参与方必须按照协议的规则生成证明，所以参与方只能互相信任。例如，prover 并不需要知道多项式，也可能通过其它方式得到正确的答案。而且，如果 verifier 要验证的多项式的解的取值范围不够大，比如我们前文说的 10，那个就可以去猜一个数字，猜对答案的概率是不可忽略不计的。因而我们必须要解决协议中的这个缺陷，在解决问题之前首先来想一下，知道多项式意味着什么呢？

多项式可以用下面的形式来表示（其中 n 指的是多项式的阶）：
$$
c_{n} x^{n}+\ldots+c_{1} x^{1}+c_{0} x^{0}
$$
如果一个人说他或她知道一个一阶多项式（即：$c_{1} x^{1}+c_{0}=0$），那么这就意味着他或她确实知道 系数 $c_{1}, c_{0}$的值。这个系数可以是包括 0 在内的任意值。

假设证明者声称他知道一个包含 x=1 和 x=2 两个解的三阶多项式。满足此条件的一个有效的多项式就是 $x^{3}-3 x^{2}+2 x=0$。因为x= 1: 1 – 3 + 2 = 0，x= 2: 8 – 12 + 4 = 0。

我们先来仔细得研究一下这个答案的结构。

### 因式分解

代数的基本定理表明了任意的一个多项式只要它有解，就可以将它分解成线性多项式（即，一个阶数为 1 的多项式代表一条线），因此，我们可以把任意有效的多项式看成是其因式的乘积：
$$
\left(x-a_{0}\right)\left(x-a_{1}\right) \ldots\left(x-a_{n}\right)=0
$$
也就是说如果任意一个因式为 0，那么整个等式都为 0
事实上，我们的例子可以被分解为下面的多项式：
$$
x^{3}-3 x^{2}+2 x=(x-0)(x-1)(x-2)
$$
所以这个多项式的解（x 的值）就是：0，1，2，在任何形式下多项式的解都可以很轻松的被验证，只不过因式的形式可以让我们一眼就看出这些解（也称为根）。
我们再回到前面的问题， prover 宣称他知道一个阶数为 3，其中两个根分别为 1 和 2 的多项式，也就是说这个多项式的形式为：
$$
(x-1)(x-2) \cdot \ldots
$$

换句话说 (x–1) 和 (x –2) 是问题中多项式的两个因式。因而如果 prover 想要在不揭示多项式的前提下证明他的多项式确实有这两个根，那么他就需要去证明他的多项式 p(x) 是 t(x) = (x- 1)(x- 2) （也称为目标多项式）和一些任意多项式 h(x) （也就是我们的例子里面的 x - 0）的乘积，即：
$$
p(x)=t(x) \cdot h(x)
$$
换句话说，存在一些多项式 h(x) 能够使得 t(x) 与之相乘后等于 p(x)，由此得出， p(x) 中包含 t(x)，所以 p(x) 的根中也包含 t(x) 的所有根，这也就是我们要证明的东西。
自然算出 h(x) 的方式就是直接相除：$h(x)=\frac{p(x)}{t(x)}$。如果一个 prover 不能找到这样一个 h(x) 也就意味着 p(x) 中不包含因式 t(x)，那么多项式相除就会有余数。例如我们用 p(x) = x³ – 3x² + 2x 除以 t(x) = (x – 1)(x – 2) = x² – 3x+ 2

注意：多项式除法是采用**长除法**计算的。左边的式子是分母，右上角的是计算结果。底部是余数

我们算出结果 h(x) = x，没有余数。

为了简化起见，后面我们会用多项式的字母变量来代替计算结果值，例如：$p=p(r)$。

利用多项式一致性检查协议我们就可以比较多项式 p(x) 和 t(x) ⋅ h(x)：
1. verifier 挑选一个随机值 r, 计算 t = $t(r)$ (即，求值) ，然后将 r 发送给 prover。
2. prover 计算 $h(x)=\frac{p(x)}{t(x)}$ ，并对 $p(r)$和 $h(r)$ 进行求值，将计算结果 p, h 提供给 verifier。
3. verifier 验证 p= t⋅h，如果多项式相等，就意味着 t(x) 是 p(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⋅h：10626 = 462 ⋅ 23 是正确的，这样陈述就被证明了。

相反，如果 prover 使用一个不同的 p′(x) ，它并不包含必要的因式，例如 p′(x) = 2x³ – 3x² + 2x, 那么：

我们算出结果2x + 3 和余数7x – 6，即：p(x) = t(x) × (2x+ 3) + 7x – 6。这就意味着 prover 为了计算出结果他不得不用 余数除以t(x)，$h(x)=2 x+3+\frac{7 x-6}{t(x)}$。

不过由于 x 是 verifier 随机选择的，就有极低的概率余数 7x – 6 最终可以被 t(x) 整除。如果后面 verifier 要另外再检查 p 和 h 必须是整数的话，这个证明才会被拒绝。不过要这么校验就同时要求多项式系数也是整数，这对协议产生了极大的限制。
这就是为什么接下来我们要介绍能够使余数不被整除的密码学原理的原因，尽管这个原始值是有可能被整除的。
现在我们就可以在不知道多项式的前提下根据特定的性质来验证多项式了，这就已经给了我们一些零知识和简明性的特性。但是，这个结构中还存在好多问题：
- prover 可能并不知道他所声称的 p(x)，他可以先算一下 t = $t(r)$，然后选择一个随机值 h，由此计算出 p = t⋅h。因为等式是成立的，所以也能通过 verifier 的校验。
- 因为 prover 知道随机点 x = r ，他可以构造出一个任意的多项式，这个任意多项式与 $t(r)$ ⋅ $h(r)$ 在 r 处有共同点。
- 在前面的「陈述」中，prover 声称他知道一个特定阶数的多项式，但现在的协议对阶数并没有明确的要求。因而 prover 完全可以拿一个满足因式校验的更高阶数的多项式来欺骗 verifier。

### 模糊计算
前两个问题是由于 暴露了原始值 而导致的，也就是 prover 知道了 r 和 $t(r)$。但如果 verifier 给出的这个值像放在黑盒里一样不可见的话就完美了，也就是一个人即使不破坏协议，也依然能在这些模糊的值上面完成计算。有点类似哈希函数，从计算结果就很难再回到原始值上。
#### 同态加密

这也就是要设计同态加密的原因。它允许加密一个值并在密文上进行算术运算。获取加密的同态性质的方法有多种，我们来介绍一个简单的方法。

总体思路就是我们选择一个基础的（基数需要具有某些特定的属性）的自然数 g（如 5），然后我们以要加密的值为指数对 g 进行求幂。例如，如果我们要对 3 进行加密：
$$
5^{3}=125
$$
这里 125 就是 3 对应的密文。如果我们想要对被加密的值乘 2，我们可以以 2 为指数来对这个密文进行计算。
$$
125^{2}=15625=\left(5^{3}\right)^{2}=5^{2 \times 3}=5^{6}
$$
我们不仅可以用 2 来乘以一个未知的值并保持密文的有效性，还可以通过密文相乘来使两个值相加，例如 3+2：
$$
5^{3} \cdot 5^{2}=5^{3+2}=5^{5}=3125
$$
同样的，我们还可以通过相除提取加密的数字，例如：5-3:
$$
\frac{5^{5}}{5^{3}}=5^{5} \cdot 5^{-3}=5^{5-3}=5^{2}=25
$$
不过由于基数 5 是公开的，很容易就可以找到被加密的数字。只要将密文一直除以 5，直到结果为 1，那么做除法的次数也就是被加密值的数。

#### 模运算
这里就到了模运算发挥作用的地方了。模运算的思路如下：除了我们所选择的组成有限集合的前 n 个自然数（即，0，1，…，n-1）以外，任何超出此范围的给定整数，我们就将它“缠绕”起来。例如，我们选择前六个数。为了说明这一点，可以把它看做一个有六个单位大小相等刻度的圆；这就是我们所说的范围（通常指的是有限域）。
现在我们看一下数字八应该在哪里。打个比方，我们可以把它看成一条长度为 8 的绳子。
如果我们将绳子固定在圆圈的开头
然后用绳子缠绕圆圈，我们在缠完一圈后还剩下一部分的绳子。
然后我们继续缠绕，这根绳子将在刻度 2 的地方终止。
这就是模运算操作的结果。无论这根绳子多长，它最终都会在圆圈一个刻度处终止。因而模运算结果将保持在一定范围内（例子中是 0 到 5）。长度为 15 的绳子将会在刻度 3 的地方终止，即 6 + 6 + 3 （缠 2 个完整的圈并剩下 3 个单位长的部分）。负数运算类似，唯一不同的地方就是它是沿相反方向缠绕的，如 -8 的取模结果是 4。
我们执行算术运算，结果都将落在这 n 的范围内。现在开始我们将用符号 “mod n” 来表示这个范围内的数。
$$
3 × 5 = 3 (mod 6)
$$
$$
5 + 2 = 1 (mod6)
$$
另外，模运算最重要的性质就是运算顺序无所谓。例如，我们可以先做完所有的操作，然后再取模，或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等于：
$$
2 × 4 = 2 (mod6)
$$
$$
2 - 1 = 1 (mod6)
$$
$$
1 × 3 = 3 (mod6)
$$
那么模运算到底有什么用呢？就是如果我们使用模运算，从运算结果再回到原始值并不容易，因为很多不同的组合会产生一个同样的运算结果：
$$
5 × 4 = 2 (mod 6)
$$
$$
4 × 2 = 2 (mod 6)
$$
$$
2 × 1 = 2 (mod 6)
$$
没有模运算的话，计算结果的大小会给找出原始值提供一些线索。除非这里既能把信息隐藏起来，又可以保留常见的算术属性。

#### 强同态加密
我们再回到同态加密上，使用模运算，例如取模 7，我们可以得到：
$$
5^{1}=5(\bmod 7)
$$
$$
5^{2}=4(\bmod 7)
$$
$$
5^{3}=6(\bmod 7)
$$
$$
...
$$
不同指数下运算得到了同样的结果：
$$
5^{5}=3(\bmod 7)
$$
$$
5^{11}=3(\bmod 7)
$$
$$
5^{17}=3(\bmod 7)
$$
这样就很难知道指数是多少了。事实上，如果模取得相当大，从运算结果倒推指数运算就不可行了；现代密码学很大程度上就是基于这个问题的“困难”。
方案中所有的同态性质都在模运算中保留了下来：
$$
\text { encryption: } \quad 5^{3}=6(\bmod 7)
$$
$$
\text { multiplication: } \quad 6^{2}=\left(5^{3}\right)^{2}=5^{6}=1 \quad(\bmod 7)
$$
$$
\text { addition: } \quad 5^{3} \cdot 5^{2}=5^{5}=3(\bmod 7)
$$
我们来明确地说明一下加密函数：$E(v)=g^{v} \quad(\bmod n)$。这里 v 就是我们要加密的值。通过模运算形成的集合被称为「有限域」，而通过计算指数再进行模运算形成的集合构成「循环群」。常见的同态加密方式除了整数幂取模之外，还有椭圆曲线上的倍乘。
#### 加密多项式
配合这些工具，我们现在就可以在加密的随机数 x 上做运算并相应地修改零知识 协议了。
我们来看一下如何计算多项式 p(x) = x³ – 3x² + 2x。我们前面明确了，知道一个多项式就是知道它的系数，也就是这个例子中知道：1，-3，2。因为同态加密并不允许再对加密值求幂，所以我们必须要给出 x 的 1 到 3 次幂取加密值：E(x)，E(x²)，E(x³)，那么我们要计算的加密多项式就是：
$$
E\left(x^{3}\right)^{1} \cdot E\left(x^{2}\right)^{-3} \cdot E(x)^{2}=\left(g^{x^{3}}\right)^{1} \cdot\left(g^{x^{2}}\right)^{-3} \cdot\left(g^{x}\right)^{2}=g^{1 x^{3}} \cdot g^{-3 x^{2}} \cdot g^{2 x}=g^{x^{3}-3 x^{2}+2 x}
$$
所以通过这些运算，我们就获得了多项式在一些未知数 x 处的加密计算结果。这确实是一个很强大的机制，因为同态的性质，同一个多项式的加密运算在加密空间中始终是相同的。
我们现在就可以更新前面版本的协议了，比如对于阶数为 d 的多项式：

Verifier
* 取一个随机数 s ，也就是秘密值
* 指数 i 取值为 0，1，…，d 时分别计算对 s 求幂的加密结果，即：$E\left(s^{i}\right)=g^{s^{i}}$
* 代入 s 计算未加密的目标多项式： $t(s)$
* 将对 s 求幂的加密结果提供给 prover：$E\left(s^{0}\right), \quad E\left(s^{1}\right), \ldots, \quad E\left(s^{d}\right)$

Prover
* 计算多项式 $h(x)=\frac{p(x)}{t(x)}$
* 使用加密值 $g^{s^{0}}, g^{s^{1}}, \ldots, g^{s^{d}}$ 和系数 c0, c1, . . . , cd 计算$E(p(s))=g^{p(s)}=\left(g^{s^{d}}\right)^{c_{d}} \cdots\left(g^{s^{1}}\right)^{c_{1}} \cdot\left(g^{s^{0}}\right)^{c_{0}}$ 和 $E(h(s))=g^{h(s)}$
* 将结果 $g^{p}$ 和$g^{h}$ 提供给 verifier

Verifier
* 最后一步是 verifier 去校验 p = t(s) ·h: $g^{p}=\left(g^{h}\right)^{t(s)} \quad \Rightarrow \quad g^{p}=g^{t(s) \cdot h}$

因为证明者并不知道跟 s 相关的任何信息，这就使得他很难提出不合法但是能够匹配验证的计算结果。

尽管这个协议中 prover 的灵活性有限，他依然可以在实际不使用 verifier 所提供的加密值进行计算，而是通过其它的方式来伪造证明。例如，如果 prover 声称有一个满足条件的多项式它只使用了 2 个求幂值 s3 和 s1，这个在当前协议中是不能验证的。

### 使用KEA(Knowledge-of-Exponent Assumption)限制多项式
多项式的知识其实就是它的系数 $c_{0}, c_{1}, \ldots, c_{i}$ 的知识。协议中我们是通过对秘密值 s 的幂的加密值再进行求幂来对系数进行“赋值”。我们已经限制了 prover 对 s 幂的加密值的选择, 但是这个限制并不是强制的 ，也就是说，prover 可以使用任何可能的方法找到满足下面等式的值:$z_{p}$和 $z_{h}$:
$$
Z_{p}=\left(Z_{h}\right)^{t(s)}
$$

再用这两个值来代替 $g^{p}$ 和 $g^{h}$ 将它交给 verifier。所以 verifier 需要能够证明 prover 给出的值就是用 s 幂的加密值而不是其它值计算出来的。

我们看一个由一个变量和一个系数组成的一阶多项式的简单例子$f(x)=c \cdot x$，对应的 s 的加密值为$E(s)=g^{s}$ 。这里我们要做的就是确保 prover 是拿 s 的加密值，即 $g^{s}$ ，而不是其他值与系数 c 做同态相乘的。所以结果一定是这个形式（c 为任意值）:$\left(g^{s}\right)^{c}$。
解决这个问题的一种方法就是用另一个“变换”的加密值做同样的操作，充当类似算术中“校验和”（Checksum） 的作用，以此确保结果是原始值的求幂值。

这个是通过 Knowledge-of-Exponent Assumption 来实现的，具体过程如下：
1. Alice 有一个值 a，她想要 Bob 对其进行任意指数的求幂（这里 a 是一个有限域群的生成器），唯一的要求是只能对 a 进行求幂，为了保证这一点，她要：
- 选择一个随机数 ${alpha}$
- 计算 $a^{\prime}=a^{\alpha} \quad(\bmod n)$
- 提供一个元组 (a, a') 给 Bob, 然后让他对这两个值执行任意的求幂运算，返回结果元组 (b, b')，这里的指数 “α-shift” 依然保持不变。即$b^{\alpha}=b^{\prime} \quad(\bmod n)$

2. 因为 Bob 无法从元组 (a, a') 中提取 α 的值，通过暴力破解也难以实现，那就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤：
- 选择一个值 c
- 计算 $b=(a)^{c}(\bmod n) \quad$ and $\quad b^{\prime}=\left(a^{\prime}\right)^{c} \quad(\bmod n)$
- 给Alice回复 (b,b')
3. Alice有了(b,b') 后，就可以验证下面的等式：

$(b)^{\alpha}=b^{\prime}$

$\left(a^{c}\right)^{\alpha}=\left(a^{\prime}\right)^{c}$

$a^{c \cdot \alpha}=\left(a^{\alpha}\right)^{c}$

结论是：
* Bob 在元组的两个值的计算上都用了同一个指数（即 c）
* Bob 只能用 Alice 原本的元组来保持 α 关系
* Bob 知道指数 c，因为构造验证值 (b,b′) 的唯一方式是用同一个指数
* Alice 并不知道 c，这和 Bob 不知道 α 的原因一样
* 虽然 c 是被加密的，但它的可能取值范围并不足够大到保持其零知识的性质，这个问题我们将在后面“零知识”那一节解决

最后这个协议提供了一个证明给 Alice ，Bob 确实是用他知道的某个值对 *α* 进行求幂的，而且他也不能做别的任何操作，例如：乘法，加法，因为这样就会破坏 α-shift 关系。

在同态加密中，求幂是对被加密值进行乘法运算。我们可以应用这个结构到一个简单的系数多项式 f(x) = c⋅ x 的例子中：
- verifier 选择随机数 s, α，然后提供令 x=s 的一阶及其“shift”的计算值：$\left(g^{s}, g^{\alpha s}\right)$
- prover 代入系数 c 计算: $\left(\left(g^{s}\right)^{c},\left(g^{\alpha s}\right)^{c}\right)=\left(g^{c s}, g^{\alpha c s}\right)$
- verifier 验证： $\left(g^{c s}\right)^{\alpha}=g^{\alpha c s}$

这个结构“限制” prover 只能用 verifier 提供的加密的 s 进行计算，因而 prover 只能将系数 c 赋给 verifier 提供的多项式。现在我们可以扩展这种单项式上的方法到多项式上，因为计算是先将每项的分配分开计算然后再 “同态地” 相加在一起的。所以如果给定 prover 一个指数为 s 的幂以及它们的α变换的加密值，他就可以计算原始的和变换后的多项式，这里也必须要满足同样的校验。对于阶数为 d 的多项式：
1. verifier 提供加密值：$g^{s^{0}}, g^{s^{1}}, \ldots, g^{s^{d}}$ 和他们的变换 $g^{\alpha s^{0}}, g^{\alpha s^{1}}, \ldots, g^{\alpha s^{d}}$
2. prover 计算给定的带有 s 的幂的加密多项式：$g^{p(s)}=\left(g^{s^{0}}\right)^{c_{0}} \cdot\left(g^{s^{1}}\right)^{c_{1}} \cdot \ldots \cdot\left(g^{s^{d}}\right)^{c_{d}}=g^{c_{0} s^{0}+c_{1} s^{1}+\ldots+c_{d} s^{d}}$
3. 计算给定的带有 s 的幂的转换的加密“α-shift”多项式：
$g^{\alpha p(s)}=\left(g^{\alpha s^{0}}\right)^{c_{0}} \cdot\left(g^{\alpha s^{1}}\right)^{c_{1}} \cdot \ldots \cdot\left(g^{\alpha s^{d}}\right)^{c_{d}}=g^{c_{0} \alpha s^{0}+c_{1} \alpha s^{1}+\ldots+c_{d} \alpha s^{d}}=g^{\alpha\left(c_{0} s^{0}+c_{1} s^{1}+\ldots+c_{d} s^{d}\right)}$
4. 将计算结果 $g^{p}$ , $g^{p^{\prime}}$ 发给verfier
5. verifier 校验：$\left(g^{p}\right)^{\alpha}=g^{p^{\prime}}$

前面的例子$p(x)=x^{3}-3 x^{2}+2 x$ 就变成了：
1. verifier 提供 $E\left(s^{3}\right), E\left(s^{2}\right), E(s)$，和它们的变换 $E\left(\alpha s^{3}\right), E\left(\alpha s^{2}\right), E(\alpha s)$
2. prover 计算：
$g^{p}=g^{p(s)}=\left(g^{s^{3}}\right)^{1} \cdot\left(g^{s^{2}}\right)^{(-3)} \cdot\left(g^{s}\right)^{2}=g^{s^{3}} \cdot g^{-3 s^{2}} \cdot g^{2 s}=g^{s^{3}-3 s^{2}+2 s}$

$g^{p^{\prime}}=g^{\alpha p(s)}=\left(g^{\alpha s^{3}}\right)^{1} \cdot\left(g^{\alpha s^{2}}\right)^{-3}\cdot\left(g^{\alpha} s\right)^{2}=g^{\alpha s^{3}} \cdot g^{-3 \alpha s^{2}} \cdot g^{2 \alpha s}=g^{\alpha\left(s^{3}-3 s^{2}+2 s\right)}$
3. verifier 校验：$\left(g^{p}\right)^{\alpha}=g^{p^{\prime}}$

$\left(g^{s^{3}-3 s^{2}+2 s}\right)^{\alpha}=g^{\alpha\left(s^{3}-3 s^{2}+2 s\right)}$

$g^{\alpha\left(s^{3}-3 s^{2}+2 s\right)}=g^{\alpha\left(s^{3}-3 s^{2}+2 s\right)}$

现在我们就可以确保 prover 是用了 verifier 提供的多项式而不是其它值做计算的了。
与前面的协议相比，我们现在已经有了一个比较健壮的协议。但是尽管已经做了加密，在零知识 性质上也还依然存在一个很明显的缺陷：即理论上多项式参数 $c_{i}$ 是一个很广的取值范围内的值，实际上这个范围可能很有限（比如前面例子中的 6），这就意味着 verifier 可以在有限范围的系数组合中进行暴力破解，最终计算出一个与 prover 的答案相等的结果。比如我们将每个系数的取值范围定为 100，多项式阶数为 2，那么大概会有 100 万种不同的组合，这里可以认为暴力破解只需要少于 100 万次的迭代。更重要的是，即使在只有一个系数，值为 1 的例子中，安全协议也应该能够保证其安全。

### 零知识证明
因为 verifier 能够从 prover 发送的数据中提取未知多项式 p(x) 的知识 ，那么我们就来看一下这些提供的数据（证明）：$g^{p}, g^{p^{\prime}}, g^{h}$

它们参与到了下面的验证：
$g^{p}=\left(g^{h}\right)^{t(s)}$ (多项式 p(x) 有根 t(x))
$\left(g^{p}\right)^{\alpha}=g^{p^{\prime}}$ (用了正确形式的多项式)

问题是我们如何选择证明使得这个校验依然有效，同时又保证没有知识能被提取？
前面章节给了我们一个答案：我们可以使用随机值 δ (delta) 来“变换”这些值, 如 $\left(g^{p}\right)^{\delta}$ 。 现在，为了提取知识，就必须首先要知道一个不可知的值 δ。并且，这种随机化在统计学上与随机值没有什么区别。
为了保持这种关系，我们在 verifier 的检查中验证一下。等式的每一边都有一个 prover 提供的值。所以如果我们用同一个 δ 来“变换” 每一个值，那么等式一定保持相等。
具体来讲，就是 prover 选择一个随机值 δ ，并用它对证明中的值进行求$\left(g^{p(s)}\right)^{\delta},\left(g^{h(s)}\right)^{\delta},\left(g^{\alpha p(s)}\right)^{\delta}$

然后提供验证内容给 verifier：
$$
\left(g^{p}\right)^{\delta}=\left(\left(g^{h}\right)^{\delta}\right)^{t(s)}
$$
$$
\left(\left(g^{p}\right)^{\delta}\right)^{\alpha}=\left(g^{p^{\prime}}\right)^{\delta}
$$
再合并一下我们就可以看到校验的等式依然成立：

注意零知识是如何轻而易举地融入到这个结构中去的，这通常也被称为"无成本的"零知识。

### 非交互式
到现在为止，我们已经讲完了一个交互式的零知识方案。但为什么我们还需要有非交互式呢？因为交互式证明只对原始的 verifier 有效，其他任何人（其他的 verifier）都不能够信任这个证明，因为：
- verifier 可以和 prover 串通，告诉他密码参数 s, α，有了这些参数 prover 就可以伪造证明
- verifier 也可以使用同样的方法自己伪造证明
- verifier 必须保存 α 和 t(s) 直到所有相关证明被验证完毕，这就带来了一个可能造成秘密参数泄漏的额外攻击面

因而 prover 就需要分别和每个 verifier 做交互来证明一个陈述（就是例子中指的多项式的知识）
尽管交互式证明也有它的用处，例如一个 prover 只想让一个特定的 verifier （称为目标 verifier 确信，就不能再重复利用同一个证明去向别人证明这个声明了，但是当一个 prover 想让众多的参与者同时或者永久地确信的话，这种方法就很低效了。 prover 需要保持一直在线并且对每一个 verifier 执行相同的计算

因而，我们就需要一个可以被重复使用，公开，可信，又不会被滥用的秘密参数。

我们先来思考一下如何在构造出秘密值 (t(s),α) 构造之后保证它的安全性。我们可以对其进行加密，方式与 verifier 在发送加密值给 prover 之前对 s 的幂使用的加密方式一致。我们使用的同态加密并不支持两个秘密值相乘，这一点对 t(s) 和 h 的加密值相乘以及 p 和 α 的加密值相乘的验证都很重要。这个问题适合用Pairing配对操作来解决。
这里非交互的证明协议将对参数加密，但引入了两个问题：
1. 同态加密无法对两个加密值做乘法，那如何验证加密后的参数呢？
2. 加密值一旦泄露，协议的信任关系将无法保证，如何确保参数的安全性？
#### 加密值相乘
配对操作（双线性映射）是一个数学结构，表示为函数 e(g,g)，它给定一个数据集中的两个加密的输入(即 $g^{a} ， g^{b}$ )，可以将他们确定性地映射到另一组不同的输出数据集上的它们的乘积， 即：$e\left(g^{a}, g^{b}\right)=e(g, g)^{a b}$
因为源数据集和输出数据集（通常被称为一个 group）是不同的，所以一个配对的结果不能用做其他配对计算的输入。我们可以将输出集（也称为“目标集”）视为“不同的宇宙”。因而我们不能用另一个加密值乘以结果，而且配对这个名称本身也表明了，我们一次只能将两个加密值相乘。换句话说，配对只支持 x * y 这种两个值的乘法，但不支持三个或以上的值相乘，比如不支持 x * y * z。
在某种意义上，这个类似于一个哈希函数，他将所有可能的输入值映射到可能的输出值的集合中的一个元素上，通常情况下这个过程是不可逆的。

配对函数 e(g,g) 可以初步（严格来说是不对的）地类比成“交换”每一个输出的基数和指数的操作，使得基数 g 在交换过程中被修改成了指数的方式， 即：$g^{a} \rightarrow a^{g}$，"被转换"的两个输入一起被修改了，这样原始值 a 和 b 就在同一个指数下相乘了，即：
$$
e\left(g^{a}, g^{b}\right)=a^{\mathbf{g}} \cdot b^{\mathbf{g}}=(a b)^{\mathbf{g}}
$$
因而因为基数在“转换”中被修改了，所以在另一个配对中不能再使用这个结果 $(a b)^{g}$， 即：无法使用 $e\left((a b)^{\mathbf{g}}, g^{c}\right)$ 构造出想要的加密乘积 abd 了，配对的核心性质可以表示成下面的等式：

$$
e\left(g^{a}, g^{b}\right)=e\left(g^{b}, g^{a}\right)=e\left(g^{a b}, g^{1}\right)=e\left(g^{1}, g^{a b}\right)=e\left(g^{1}, g^{a}\right)^{b}=e\left(g^{1}, g^{1}\right)^{a b}
$$

严格来讲一个配对的结果是在目标集的一个不同生成元 g 下对原始值乘积的加密，即:$e\left(g^{a}, g^{b}\right)=g^{a b}$。因而它具备同态加密的性质，也就是说我们可以把乘法配对的加密乘积放到一起：$e\left(g^{a}, g^{b}\right) \cdot e\left(g^{c}, g^{d}\right)=g^{a b} \cdot g^{c d}=g^{a b+c d}=r(g, g)^{a b+c d}$
注意:配对操作是通过改变椭圆曲线来实现这些性质的，现在我们用的符号 gⁿ 就代表曲线上一个由生成元自相加了 n 次的点，而不是我们前面用到的乘法群生成元。

#### 可信任参与方的 Setup

有了配对，我们现在就准备去设置安全公开且可复用的参数了。假定一下我们让一个诚实的参与方来生成秘密值 s 和 α。只有 α 和所有必要的 s 的幂及其对应的 "α-shift"被加密了，那么原始数据就必须要被删除（ i 为 0，1,…,d ）：
$g^{\alpha}, g^{s^{i}}, g^{\alpha s^{i}}$
这些参数通常被称为 common reference string 或者 CRS。CRS 生成后，任何的 prover 和任何的 verifier 都可以使用它来构造非交互式的零知识证明协议。CRS 的优化版本将包含目标多项式的加密值 $g^{t(s)}$ ，尽管这个值并不重要。
把 CRS 分成两组（ i 为 0，1,…,d ）：
- proving key（也被称为 evaluation key）：$\left(g^{s^{i}}, g^{\alpha s^{i}}\right)$
- verification key： $\left(g^{t(s)}, g^{\alpha}\right)$

只要能够乘以加密值，verifier 就可以在协议的最后一步验证多项式了：
- 有了verification key，verifier 就可以处理从 prover 那里得到的加密多项式的值：$g^{p}, g^{h}, g^{p^{\prime}}$
- 在加密空间中校验 p = t·h ： $e\left(g^{p}, g^{1}\right)=e\left(g^{t}, g^{h}\right)$
- 校验多项式的限制： $e\left(g^{p}, g^{\alpha}\right)=e\left(g^{p^{\prime}}, g\right)$

#### 信任任意一个参与者
尽管受信任设置很有效率，但众多 CRS 用户也必须要相信生成者确实删除了 α 和 s ，这一点没有办法证明，所以这种方法依然是无效的。因而很有必要去最小化或者消除这种信任。否则一个不诚实的参与方就可以构造假证明而不被发现。
一种解决办法就是由多个参与方使用前面小节中介绍的数学工具来生成一个组合式CRS，这样这些参与方就都不知道「秘密」了。下面是一个实现方案，我们假设有三个参与者 Alice，Bob 和 Carol ，对应为 A，B 和 C，其中 i为 1, 2, …, d：
- Alice 选择随机数 $s_{A}$ 和 $\alpha_{A}$ ，然后公开她的 CRS：
$\left(g^{s^{i}}, g^{\alpha_{A}}, g^{\alpha_{A} s_{A}^{i}}\right)$
- Bob 选择他的随机数 $s_{B}$ 和 $\alpha_{B}$, 然后通过同态乘法结合 Alice 的 CRS:
$\left(\left(g^{s_{A}^{i}}\right)^{s_{B}^{i}},\left(g^{\alpha_{A}}\right)^{\alpha_{B}},\left(g^{\alpha_{A} s_{A}^{i}}\right)^{\alpha_{B} s_{B}^{i}}\right)=\left(g^{\left(s_{A} s_{B}\right)^{i}}, g^{\alpha_{A} \alpha_{B}}, g^{\alpha_{A} \alpha_{B}\left(s_{A} s_{B}\right)^{i}}\right)$

然后公开两方 Alice-Bob 的 CRS 结果：$\left(g^{s_{A B}^{i}}, g^{\alpha_{A B}}, g^{\alpha_{A B} s_{A B}^{i}}\right)$

- Carol 用她的随机数 $s_{C}$ 和 $\alpha_{C}$ 做同样的事：$\left(\left(g^{s_{\mathrm{AB}}^{i}}\right)^{s_{C}^{i}},\left(g^{\alpha_{\mathrm{AB}}}\right)^{\alpha_{C}},\left(g^{\alpha_{\mathrm{AB}} s_{\mathrm{AB}}^{i}}\right)^{\alpha_{C} s_{C}^{i}}\right)=\left(g^{\left(s_{A} s_{B} s_{C}\right)^{i}}, g^{\alpha_{A} \alpha_{B} \alpha_{C}}, g^{\alpha_{A} \alpha_{B} \alpha_{C}\left(s_{A} s_{B} s_{C}\right)^{i}}\right)$
然后公开 Alice-Bob-Carol 的 CRS:$\left(g^{s_{\mathrm{ABC}}^{i}}, g^{\alpha_{\mathrm{ABC}}}, g^{\alpha_{\mathrm{ABC}}} s_{\mathrm{ABC}}^{i}\right)$

这个协议最后我们就获得了一个混合的：$\boldsymbol{s}^{i}$ 和 $\alpha$：
$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}, \ldots$和 $\alpha_{1}, \alpha_{2}, \ldots$, …，然后代入这些不同的随机数去执行 s 的不同次幂计算（或提供随机数作为一个 CRS 的扩充），从而使 CRS 无效或者不可用。
庆幸的是，因为我们可以使用配对来乘以加密值，所以我们就可以从第一个参数开始逐一执行一致性校验，并且确保了每个参数都源于前一个。
- 我们用 s 的 1 次幂作为标准来校验每一个其它次幂的值与之是否保持一致
$e\left(g^{s^{i}}, g\right)=\left.e\left(g^{s^{1}}, g^{s^{i-1}}\right)\right|_{i \in 2, \ldots \ldots, d}$

例如：
2 次幂： $e\left(g^{s^{2}}, g\right)=e\left(g^{s^{1}}, g^{s^{1}}\right)=>e(g, g)^{s^{2}}=e(g, g)^{s^{1+1}}$

3 次幂：$e\left(g^{s^{3}}, g\right)=e\left(g^{s^{1}}, g^{s^{2}}\right)=>e(g, g)^{s^{3}}=e(g, g)^{s^{1+2}}$, 等

我们现在再验证一下前面步骤中 α-变换后的值是否正确：$e\left(g^{s^{i}}, g^{\alpha}\right)=\left.e\left(g^{\alpha s^{i}}, g\right)\right|_{i \in[d]}$

例如：

3 次幂：$e\left(g^{s^{3}}, g^{\alpha}\right)=e\left(g^{\alpha s^{3}, g}\right)=>e(g, g)^{s^{3} \cdot \alpha}=e(g, g)^{\alpha s^{3}}$

这里 $i \in\{2, \ldots \ldots, d\}$ 是“i 值分别为 2，3，…，d” 的缩写， [d] 是 1, 2, …, d 这个范围的缩写形式，在后面的章节这种表示方式更为常见。

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

这就可以去验证 Bob 的 CRS 是乘以了 Alice 的参数后正常获得的，这里 i 为 1, 2,…, d。

$e\left(g^{s_{A B}^{i}}, g\right)=e\left(g^{s^{i}}, g^{s_{B}^{i}}\right)$
$e\left(g^{\alpha_{A B}}, g\right)=e\left(g^{\alpha_{A}}, g^{a_{B}}\right)$
$e\left(g^{\alpha_{A B} s_{A B}^{i}}, g\right)=e\left(g^{\alpha_{A} s_{A}^{i}}, g^{\alpha_{B} s_{B}^{i}}\right)$

同样的，Carol 也必须证明她的 CRS 是乘以了 Alice-Bob 的 CRS 后正常获得的。

这是一个健壮的 CRS 设置模式，它并不完全依赖于单个参与者。事实上，即使其它所有的参与者都串谋了，只要有一个参与者是诚实的，他能够删除并且永远不共享它的秘密参数，这个 CRS 就是有效的。所以在设置 CRS （有时候被称为仪式的时候有越多不相关的参与者参与，伪造证明的可能性就越低。当有相互竞争的参与方参与的时候，就几乎不可能伪造证明了。这种模式能够包容其他一些怀疑这种 setup 可识别性的不受信方因为校验步骤确保了他们不会破坏（这里也包括很弱的 $\alpha$ 和 s 的使用）最终的 CRS。

### 多项式的 SNARK
我们现在准备来合并这个逐步演化出来的 **zk-SNARKOP** 协议。为简洁起见，我们将使用大括号来表示由旁边的下标填充的一组元素，例如： $\left\{s^{i}\right\}_{i \in[d]}$ 表示一组数 $s^{1}, s^{2}, \ldots, s^{d}$。我们已经明确目标多项式 t(x) 和 prover 的多项式阶数 d：
- Setup
- 挑选随机值 s，$\alpha$
- 计算加密值 $g^{\alpha}$ 和 $\left\{g^{s^{i}}\right\}_{i \in[d]}$ ，$\left\{g^{\alpha s^{i}}\right\}_{i \in\{0, \ldots, d\}}$
- 生成 proving key： $\left(\left\{g^{s^{i}}\right\}_{i \in[d]},\left\{g^{\alpha s^{i}}\right\}_{i \in\{0, \ldots, d\}}\right)$
- 生成 verification key: $\left(g^{\alpha}, \quad g^{t(s)}\right)$
- Proving
- 分配系数 $\left\{c_{i}\right\}_{i \in\{0, \ldots, d\}}$(即知识)得 $p(x)=c_{d} x^{d}+\ldots+c_{1} x^{1}+c_{0} x^{0}$
- 求多项式 $h(x)=p(x) / t(x)$
- 代入 $\left\{g^{s^{i}}\right\}_{i \in[d]}$ 计算多项式 $g^{p(s)}$ 和 $g^{h(s)}$的值
- 代入 $\left\{g^{\alpha s^{i}}\right\}_{i \in[d]}$ 计算变换多项式 $g^{\alpha p(s)}$ 的值
- 选择随机数 δ
- 构造随机化的证明 $\pi=\left(g^{\delta p(s)}, g^{\delta h(s)}, g^{\delta \alpha p(s)}\right)$
- verification
- 映射证明 π 为 $\left(g^{p}, g^{h}, g^{p^{\prime}}\right)$
- 验证多项式约束： $e\left(g^{p^{\prime}}, g\right)=e\left(g^{p}, g^{\alpha}\right)$
- 验证多项式系数：$e\left(g^{p}, g\right)=e\left(g^{t(s)}, g^{h}\right)$

注意： 如果 pairing 的结果有可能在其它类似的乘法协议中被复用，那么这里就完全没有安全性可言了，因为这样的话 prover 就可以构造 $g^{p^{\prime}}=e\left(g^{p}, g^{\alpha}\right)$ 。

这样也可以通过"多项式约束"的检查： $e\left(e\left(g^{p}, g^{\alpha}\right), \quad g\right)=e\left(g^{p}, g^{\alpha}\right)$

#### 结论

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

verifier 知道 prover 有一个有效的多项式，但是并不知道是哪一个。我们可以利用多项式的其他性质添加额外的证明，如：被多个多项式整除，是某个多项式的平方。虽然可能会有一个服务能够接受，存储和奖励所有经过证明的多项式，或者有一个需求，加密计算某种形式的未知多项式。然而若有通用方案就可以支撑无数的应用。

总结一下这篇文章中一步一步解决了下面的几个问题：
1. 保证 prover 的证明是按照规则正确构造的 ——> KEA
2. 保证知识的零知性 ——> “无成本的”δ 变换
3. 可复用证明 ——> 非交互式
4. 非交互中如何设置安全公开且可复用的参数 ——> 参数加密，verifier 借助密码配对进行验证
5. 保证参数的生成者不泄密 ——> 多方的 Setup

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