2022-09-04 zk-SNARKs 证明过程.md

• tags: blockchain
• date: 2022-09-04

zk-SNARKs 证明过程

• Zero Knowledge： 即0知识，不暴漏要证明的原始信息
• Succinct：证据信息比较短，方便验证
• Non-interactive：无交互的，prover只需要提供一个字符串即可。这点对于区块链应用非常重要，意味着可以把消息放在链上公开验证
• Arguments：证明过程的是计算完好的，即 prover 没发在合理的时间内伪造一个 proof 信息。跟计算完好对应的是理论完好，密码学上一般要求计算完好即可
• Of knowledge：保证证明者在不知晓密文的情况下构建出一个有效的零知识 proof 是不可能的

$P(x) = \sum_{i=0}^{d} a_i \cdot X^i$

同态加法

同态加法满足一下3个性质

1. 对于大部分的 x，在给给定 E(x) 的情况下很难求解出 x
2. 不同输入会得到不同的输出，if x ≠ y, then E(x) ≠ E(y)
3. 如果某人知道 E(x) and E(y)，则他可以计算出 E(x+y)

如果 A 有两个数字 x、y，他需要向 B 证明数字之和是 z，那么需要一下步骤：

1. A 计算出 E(x), E(y) 并发送给 B
2. B 通过A 发来的 E(x) E(y) 计算出 E(x+y)
3. B 计算出 E(z) and assert E(z) == E(x+y)

椭圆曲线运算

基于椭圆曲线的算法 RSA、ECC 都支持同态加法运算，具体原理参考这个讲解：

https://www.bilibili.com/video/BV1BY411M74G

同态加法拓展到多项式

$$ P(X) = a_0 + a_1 \cdot X + a_2 \cdot X^2 + ... + a_d \cdot X^d $$

利用同态加法的特性，我们可以简单的把零知识证明推广到多项式中。假设 A 知道一个最高 d 次的多项式 P，而 B 想要知道对应的某个 s 的 $E(P(s))$。并且，在验证过程中 A 只知道 P，不知道s，B只知道s，不知道P，则可以通过下面方式实现验证：

1. 对与 s 的每个指数，B计算出 $E(s^0),E(s^1),E(s^2)…E(s^d)$ 并发送给 A
2. A 知道所有多项式的系数，则 $E(P(s)) = \sum_{i=0}^d E(a_i) \cdot E(s^i)$

KCA过程(Knowledge of Coefficient Test and Assumption)

上面 A 计算出来的 $E(P(s))$，B并没有办法证明他就是通过多想式 P 计算出来的，因此我们需要引入一个 KCA 过程。这里再次借助椭圆曲线乘法运算，假设一对值 (a,b) 满足 $b=\alpha \cdot a$ 注意这里的乘法不是普通的乘法，而是椭圆曲线乘法，他满足两个特性：

1. 当 $\alpha$ 很大的情况下，很难通过 a、b 推导出 $\alpha$ 的值
2. 满足加法和乘法的结合律，满足同态隐藏

那么一个 KCA 过程可以描述为：

1. B 随机生成一个 $\alpha$ 对 (a,b)， $\alpha$ 自己保存，(a,b) 发送给 A
2. A 选择一个 $\gamma$ 生成 $(a’, b’) = (\gamma \cdot a, \gamma \cdot b)$ 回传给 B，则 B 可以验证 $(a’, b’)$ 也是一个 $\alpha$ 对，证明使用了乘法结合律： $b' = \gamma \cdot b = \gamma \cdot \alpha \cdot a = \alpha \cdot (\gamma \cdot a) = \alpha \cdot a'$
3. B 校验 $(a’, b’)$ 也是一个 $\alpha$ 对则能证明 A 知道 $\gamma$，并且满足 $a’=\gamma \cdot a$ 即证明了 A 知道 a 与 a’ 之间存在线性关系 $\gamma$

上面 B 验证了 A 知道一个常数 $\gamma$ ，那么对多个常数组成一个向量 $C (c_0, c_1, c_2,..., c_d)$，B 同样可以使用一系列 $\alpha$对来验证 $(a’, b’) = (c_0 \cdot a_0 + c_1 \cdot a_1 + ... + c_d \cdot a_d, c_0 \cdot b_0 + c_1 \cdot b_1 + ... + c_d \cdot b_d)$ 是一个 合法的 $\alpha$ 对，从而证明 A 知道常数数组 C. 对d个系数的 KCA 过程称作 d-KCA.

结合前面多项式同态中不能确保 A 知道常数数组缺点可以改进一下，确保 B 能够验证 A 知道真正的多项式系数：

1. 因为椭圆曲线符合同态特性，则令A, B 共同选择 $x \cdot g$ 作为 $E(x)$
2. B 计算 $s^0 \cdot g, s^1 \cdot g, ... s^d \cdot g$ 和 $\alpha \cdot s^0 \cdot g, \alpha \cdot s^1 \cdot g, ... \alpha \cdot s^d \cdot g$ 发送给 A，实际上就是发送 各个 $E(s^i)$ 的同时增加了 $E(a \cdot s^i)$ 的数据； $(s^d \cdot g, \alpha s^d \cdot g)$ 是一 $\alpha$ 对
3. A 根据上面 B 发送的结果计算出 $a = P(s) \cdot g, b = \alpha \cdot P(s) \cdot g$， 并且把 a, b 回传给 B
4. B 验证 $b=\alpha \cdot a$， 即 (a, b) 是一个 $\alpha$ 对即可证明 a 即是要求的 $E(P(s))$

QAP (Quadratic Arithmetic Program)

https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

QAP 过程可以将任意计算关系转换成一个多项式证明。举个例子比如我们想证明我们知道一个数 x 使得 $x^3 + x + 5 = 35$， 但是又不能说 x 具体是多少。那么这个问题就变成了证明我们知道一系列约束关系，同时满足这些约束关系的情况下一定能够得到 $x^3 + x + 5 = 35$。加上之前我们了解了 d-KCA过程，自然联想到如果我们能把一系列约束关系用某个多项式的系数来表示，我们即可在不告知实际解的情况下证明我们知道约束关系下的解。这个转换就是 QAP，具体需要下面3个步骤。

Computation → Arithmetic Circuit → R1CS → QAP

压平

即把原来的高阶多项式关系转化为一阶关系，即加法和乘法。每个加法或乘法即使一个约束条件，我们称之为一个门电路，例如上面例子的约束关系转化为下面四个一阶约束：

1. sym_1 = x * x
2. y = sym_1 * x
3. sym_2 = y + x
4. ~out = sym_2 + 5 ( ~out = 35)

R1CS

R1CS（Rand-1 Constraint System）是指由 $(a, b, c)$ 3 个向量组成的序列，存在一个解 $s$，使得它满足 $s \cdot a * s \cdot b - s \cdot c = 0$ 其中 $\cdot$ 表示内积。我们用**(~one, x, ~out, sym_1, y, sym_2)** 6个参数取值组成想来代表 a, b, c，其中 ~one 指常数参数

那么针对第一个约束 sym_1 = x * x 我们可以得到向量组：

a = [ 0, 1, 0, 0, 0, 0 ]

b = [ 0, 1, 0, 0, 0, 0 ]

c = [ 0, 0, 0, 1, 0, 0 ]

a = [ 0, 1, 0, 0, 0, 0 ]

b = [ 0, 1, 0, 0, 0, 0 ]

c = [ 0, 0, 0, 1, 0, 0 ]

此时，对于向量 s，我们能确定它的第二个标量和第四个标量是2次幂关系，比如 [ 0, 3, 0, 9, 0, 0 ] 或者 [ 0, 7, 0, 49, 0, 0]

对于后面的 2、3、4 个约束条件我们可以表示为

a = [0, 0, 0, 1, 0, 0]

b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 0, 1, 0]

a = [0, 1, 0, 0, 1, 0] (y+x)

b = [1, 0, 0, 0, 0, 0] 对应常数 1

c = [0, 0, 0, 0, 0, 1] 

a = [5, 0, 0, 0, 0, 1] 对应(sym_2 + 5)

b = [1, 0, 0, 0, 0, 0] 常数 1

c = [0, 0, 1, 0, 0, 0]

现在，我们假设 x = 3 根据第一个门，得到 sym_1 = 9，根据第二个门得到 y = 27，根据第三个门，得到 sym_2 = 30，根据第四个门得到 ~out = 35，所以 s = [ 1, 3, 35, 9, 27, 30 ]

• 此时我们针对 a,b,c 各自得到了 4 个约束条件：

  A
  
  [0, 1, 0, 0, 0, 0]
  
  [0, 0, 0, 1, 0, 0]
  
  [0, 1, 0, 0, 1, 0]
  
  [5, 0, 0, 0, 0, 1]
  
  B
  
  [0, 1, 0, 0, 0, 0]
  
  [0, 1, 0, 0, 0, 0]
  
  [1, 0, 0, 0, 0, 0]
  
  [1, 0, 0, 0, 0, 0]
  
  C
  
  [0, 0, 0, 1, 0, 0]
  
  [0, 0, 0, 0, 1, 0]
  
  [0, 0, 0, 0, 0, 1]
  
  [0, 0, 1, 0, 0, 0]

QAP

使用多项式形式而不是内积（R1CS）来描述这些约束关系的方法即是 QAP。我们需要把 4 组长度为 6 的 3 个向量 转化为 6（因为系统中又6个符号） 组 3（因为系统中又4个约束条件，即4个点，通常多项式中d个点可以确定 d-1阶多项式） 阶多项式。在每个约束条件的 x 坐标处的值代表一个约束条件。满足4个约束我们可以分别确定 a 向量每个标量的约束多项式。

针对 A 的第一个标量，四个约束条件确定的 4个点(x, y) 分别是(1,0), (2,0), (3,0), ***(4,5)，***那么这个问题就变成了求过以上四个点的 3 阶多项式的各个系数，这个多项式描述了 A 的第一个标量的约束。

求过 n 个点的多项式，可以使用 拉格朗日插值定理 https://en.wikipedia.org/wiki/Lagrange_polynomial 具体过程不再详述。至此我们得到了 A 向量第一个标量的约束多项式，可以记为一个 3 个元素的向量，由此推算，我们可以计算出 A、B、C 每个标量的约束多项式，V 神用 Python实现了计算过程：/~https://github.com/ethereum/research/tree/master/zksnark

• 这里直接给出计算结果

  (1,0), (2,0), (3,0), (4,5) 的多项式，类似的我们可以求出其余的四个约束所对应的每个向量的第i个值的多项式。
  
  这里，直接给出答案：
  
  A polynomials
  
  [-5.0, 9.166, -5.0, 0.833]
  
  [8.0, -11.333, 5.0, -0.666]
  
  [0.0, 0.0, 0.0, 0.0]
  
  [-6.0, 9.5, -4.0, 0.5]
  
  [4.0, -7.0, 3.5, -0.5]
  
  [-1.0, 1.833, -1.0, 0.166]
  
  B polynomials
  
  [3.0, -5.166, 2.5, -0.333]
  
  [-2.0, 5.166, -2.5, 0.333]
  
  [0.0, 0.0, 0.0, 0.0]
  
  [0.0, 0.0, 0.0, 0.0]
  
  [0.0, 0.0, 0.0, 0.0]
  
  [0.0, 0.0, 0.0, 0.0]
  
  C polynomials
  
  [0.0, 0.0, 0.0, 0.0]
  
  [0.0, 0.0, 0.0, 0.0]
  
  [-1.0, 1.833, -1.0, 0.166]
  
  [4.0, -4.333, 1.5, -0.166]
  
  [-6.0, 9.5, -4.0, 0.5]
  
  [4.0, -7.0, 3.5, -0.5]
  

这些是系数为升序的多项式排列，例如第一个多项式表达的是 $0.833 * x^3 - 5 * x^2 + 9.166 * x -5 = 0$

• 我们将 x=1 带入这个 18 个多项式，可以得到结果：

  A results at x=1
  0
  1
  0
  0
  0
  0
  B results at x=1
  0
  1
  0
  0
  0
  0
  C results at x=1
  0
  0
  0
  1
  0
  0
  

可以看到，结果就是我们第一个门电路的约束条件，同理后面 3 个门电路约束条件也是这样。

验证一个 QAP

R1CS 中需要单独的检查每一个约束满足 $s \cdot a * s \cdot b - s \cdot c = 0$。如果是多项式表示，则我们可以使用多项式的内积来一次性验证所有约束：

这种情况下，如果得到的多项式在我们上面的4个约束门电路中么一个x坐标处的值都是0就意味着验证通过，否则如果有一个非0值，那么就意味着验证不通过。

事实上我们不计算多项式 $p = A \cdot s * B \cdot s - C \cdot * s$ 。而是把 p 除以两一个多项式 T，然后检查是否能够整除，没有余数，T 是一个最简多项式形如 $(x - 1) * (x - 2) * (x-3)…$，如果一个多项式是 T 的倍数，那么它在任意 x 的取值上都是 0，也即符合验证条件。

事实上，如果一个约束系统确定之后，那么它的约束多项式 QAP 和 T 就确定了，这只需要在系统构建的时候运算一次，后面可以重复使用

• 我们使用上面 R1CS 里的 s 来验证我们得到的中间多项式

  A . s = [43.0, -73.333, 38.5, -5.166]
  B . s = [-3.0, 10.333, -5.0, 0.666]
  C . s = [-41.0, 71.666, -24.5, 2.833]
  
  其中：
  43.0 = -5 * 1 + 8 * 3 + 0 * 35 - 6 * 9 + 4 * 27 - 1 * 30
  -73.333 = 9.166 * 1 - 11.333 * 3 + 0 * 35 + 9.5 * 9 - 7 * 27 + 1.833 * 30
  ...
  -3 = 3 * 1 - 2 * 3 + 0 * 35 + 0 * 9 + 0 * 27 + 0 * 30
  ...
  

P = A . s * B . s - C . s = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

T = (x - 1) * (x - 2) * (x - 3) * (x - 4) = [24, -50, 35, -10, 1]

H = P / T = [-3.666, 17.055, -3.444] 没有余数，则验证通过

如果伪造 R1CS 的解 s，则带入上面的运算 h 将包含余数，不能通过验证

至此我们看到将任意一个运算约束关系转化成了证明满足某个多项式关系的问题。但是注意这里我们将原计算的4个约束关系转化成了一个多项式，相当于中间插入了很多没有意义的取值，这是是与元计算无关的点，也就是说多项式的验证与原计算的验证本质上不是一一等价的，但是验证了多项式也就验证了元计算。

皮诺曹协议

我们定义 $L(x) = s \cdot A(x), R(x) = s \cdot B(x), O(x) = s \cdot C(x)$，那么我们需要验证的等式就是 $L(x) * R(x) - O(x) = T(x) * H(x)$ ，L、R、O都是d阶，那么相乘最高为2d阶，两个2d阶多项式交点最多只有2d个，那么如果 A 不知道这个多项式同时还能猜中计算结果的概率就是2d/p ，p是多项式的自变量取值域，这是很小概率。那么这个验证过程将是：

1. A 按照 QAP 方式选出多项式 L、R、O、H
2. B 随机选择取样点 s， 计算 E(T(s))
3. A 计算出 E(L(s)), E(R(s)), E(O(s)), E(H(s))，根据 B 发过来的 E(s) E(s^2)…
4. B 校验 E(L(s)*R(s)-O(s))=E(H(s)*T(s))

那么这里面仍有几个问题：

1. 保证 L、R、O 是由同一组参数 s 生成的

我们定义了 $L(x) = s \cdot A(x), R(x) = s \cdot B(x), O(x) = s \cdot C(x)$，如果 L、R、O生成的过程中s的取值不一样，那么A就有可能伪造proof，为了保障L、R、O的生成过程中使用的是同一个向量 s,那么我们就把 s 的各个标量看作是一个多项式 F 的各个系数，从而使用一个 d-KCA 过程保障 L、R、O 的生成过程使用的是同一个向量 s

定义：

$F_i = L_i + X^{d+1} \cdot R_i + X^{d+2} \cdot O_i$

$F = L + X^{d+1} \cdot R + X^{d+2} \cdot O$

$F = \sum_{i=1}^m c_i \cdot F_i$

即只要 A 能证明 F 和 $F_i$ 的线性组合，即可证明 L、R、O 是由用一组向量 s 产生的，那么这便转换成了一个 d-KCA 问题：

1. B 选择 $\alpha$，并计算 $E(\alpha \cdot F_i)$ 并发送给 A
2. A 计算 $E(\alpha F)$ 并回传给 B
3. B 计算 E(F) 并校验 $\alpha$ 对

2. 暴力破解

如果如果需要验证的问题解 s 不多的情况下，B可以通过暴力穷举的方式倒推出原来的多项式，得到A得原始数据。例如我们已知A有两个正整数，要求盲验证这两个正整数的乘积是12，那么B完全可以穷举乘积是12的所有正整数组合，正向执行验证过程，与E(L(s))，E(R(s))和E(O(s))比对即可知道正确的答案是什么。那么我们的解决思路是引入一个随机偏量：

$L_z = L + \rho_1 \cdot T; R_z = R + \rho_2 \cdot T; O_z = O + \rho_3 \cdot T$

则： $L_z \cdot R_z - O_z = (L + \rho_1 \cdot T)(R + \rho_2 \cdot T) - O - \rho_3 \cdot T$

$= (L \cdot R - O) + L \cdot \rho_2 \cdot T + \rho_1 \cdot T \cdot R + \rho_1 \rho_2 \cdot T^2 - \rho_3 \cdot T$

$= T \cdot (H + L \cdot \rho_2 + \rho_1 \cdot R + \rho_1 \rho_2 \cdot T - \rho_3)$

其中 $Hz = H + L \cdot \rho_2 + \rho_1 \cdot R + \rho_1 \rho_2 \cdot T - \rho_3$

那么 $L_z, R_z, O_z, H_z$ 将是符合原约束解的新组合

3. 同态乘法

开篇我们介绍了同态加法，但是各种对同态函数E的证明中需要在乘法上也具有同态特性。椭圆曲线很好的解决了这个问题。

4. 验证点 s 和 $\alpha$ 值的选择需要交互

还有一个非常关键的问题没有解决，即 B 需要生成验证点 s、 $\alpha$发送给A，然后开始后续验证，这里面 A、B 之间交互太多，如果要在区块链中公开验证，则这种交互是破坏性的。但是严格意义上的0交互的证明已经被证明不能满足所有场景。为了减少交互，采用一种CRS（COMMON REFERENCE STRING）方式，将 s, $\alpha$ 事先预置到系统中。

在预置数据的设置上，为了保证数据不被任何人掌握，依然采取了椭圆曲线非对称加密。选取多个人私钥各产生一个公钥，然后拼接在一起作为预置数据并计算各个 E(s) 等需要的值，之后每个人销毁自己的私钥。

最终的非交互式证明过程

1. 设置预置数据 s, $\alpha$，并计算 $E_1(s^0),E_1(s^1),…,E_1(s^d);E_2(\alpha s^0),E_2(\alpha s^1),…,E_2(\alpha s^d)$ 并公示
2. A 计算 $a = E_1(P(s)); b = E_2(\alpha P(s))$
3. B 计算 $E(\alpha a) = Tate(E_1(a), E_2(\alpha)); E(b)=Tate(E_1(1), E_2(b))$ 然后验证他们是相同的。如果 $E(\alpha a) = E(b)$，那么我们可以得到 $\alpha a = b$，即 a、b 是一个 $\alpha$ 对。