Why and How zk-SNARK Works: Definitive Explanation（1）

看了好几天的论文，额，真的看不懂。。先看看这个吧，这个应该相对容易一些。

引用：https://zhuanlan.zhihu.com/p/100636577 https://zhuanlan.zhihu.com/p/99260386

简介

概念。

协议满足的三个属性。

证明的媒介。

即使可能存在其他的证明媒介，多项式依然是 zk-SNARK 相对核心的部分。

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

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

多项式的一个重要性质：我们不可能找到共享连续段的两条不相等曲线，也就是任何多项式在任意点的计算结果都可以看做是其唯一身份的表示。也就是说只要能证明多项式上的某个随机点就可以证明这个多项式（只有在知道了多项式，才能算出这个点对于的值）。

多项式的知识：多项式的系数。所谓知道多项式就是指知道多项式的系数。

prover 宣称他知道一个阶数为 3，其中两个根分别为 1 和 2 的多项式，也就是说这个多项式的形式为：

(x–1) 和 (x–2) 是prover的多项式中的两个因式。如果 prover 想要在不揭示多项式的前提下证明他的多项式确实有这两个根，那么他就需要去证明他的多项式p(x)是t(x) = (x- 1)(x- 2) （目标多项式）和一些任意多项式h(x)（也就是我们的例子里面的x - 0）的乘积，即：

换句话说，存在一些多项式h(x)能够使得t(x)与之相乘后等于p(x)，由此得出，p(x)中包含t(x)，所以p(x)的根中也包含t(x) 的所有根，这也就是我们要证明的东西。

自然算出h(x)的方式就是直接相除：

(x)=xh(x)也就意味着p(x)中不包含因式t(x)，那么多项式相除就会有余数。例如我们用 p(x)=x^3-3x+2x 除以 t(x) = (x – 1)(x – 2) = x^2 – 3x+ 2 得到 h(x)=x ，没有余数。

利用多项式一致性检查协议我们就可以比较多项式 p(x) 和 t(x) ⋅ h(x)：

• verifier 挑选一个随机值 r, 计算 t = t(r) (即，求值) ，然后将 r 发送给 prover。
• prover 计算 h(x) =p(x) / t(x) ，并对 p(r) 和 h(r) 进行求值，将计算结果 p, h 提供给 verifier。
• verifier 验证 p= t⋅h，如果多项式相等，就意味着 t(x) 是 p(x) 的因式。

实践一下，用下面的例子来执行这个协议：

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

存在的问题：

• 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，然后我们以要加密的值为指数对g进行求幂。例如，如果我们要对 3 进行加密： 5^3=125

这里 125 就是 3 对应的密文。如果我们想要对被加密的值乘 2，我们可以以 2 为指数来对这个密文进行计算。125^2=15625=(5^3)^2=5^{2\cdot3}=5^6

我们不仅可以用 2 来乘以一个未知的值并保持密文的有效性，还可以通过密文相乘来使两个值相加，例如 3+2：

5^3\cdot5^2=5^{3+2}=5^5=3125

不过由于基数 5 是公开的，很容易就可以找到被加密的数字。只要将密文一直除以 5，直到结果为 1，那么做除法的次数也就是被加密值的数。可以采用模运算进行解决。

强同态加密：

E(v)=g^v(mod\ n) ，v 是要加密的值。

不同指数下运算得到了同样的结果：5^5=5^{11}=5^{17}=3\ mod\ 7 。这样就很难知道指数是多少了。事实上，如果模取得相当大，从运算结果倒推指数运算就不可行了；现代密码学很大程度上就是基于这个问题的“困难”。

方案中所有的同态性质都在模运算中保留了下来：

这个同态加密模式有一个限制，我们可以把一个加密的值和一个未加密的值相乘，但我们不能将两个加密的值相乘（或者相除），也就是说我们不能对加密值取幂。虽然这些性质第一感觉看起来很不友好，但是这却构成了zk-SNARK的基础。这个限制后面将在“加密值乘法”一节中讲到。算出 E(x) , 不能计算 E(x)\cdot E(x) ,即 (E(x))^n 。

加密多项式：

配合这些工具，我们现在就可以在加密的随机数 x 上做运算并相应地修改零知识 协议了。

我们来看一下如何计算多项式 p(x) = x³ – 3x² + 2x。我们前面明确了，知道一个多项式就是知道它的系数，也就是这个例子中知道：1，-3，2。因为同态加密并不允许再对加密值求幂，所以我们必须要给出 x 的 1 到 3 次幂取加密值：E(x)，E(x²)，E(x³)，那么我们要计算的加密多项式就是：

[公式]

所以通过这些运算，我们就获得了多项式在一些未知数 x 处的加密计算结果。这确实是一个很强大的机制，因为同态的性质，同一个多项式的加密运算在加密空间中始终是相同的。

更新前面版本的协议了，比如对于阶数为 d 的多项式：

• Verifier
  • 取一个随机数 s ，也就是秘密值。
  • 指数 i 取值为 0，1，…，d 时分别计算对 s 求幂的加密结果，即：E(s^i)=g^{s^i} 。
  • 代入s计算未加密的目标多项式：t(s) 。
  • 将对s求幂的加密结果提供给 prover: E(s^0),E(s^1),E(s^2),......,E(s^d) 。
• Prover
  • 计算多项式 h(x)=p(x)/t(x) 。
  • 使用加密值 g^{s^0},g^{s^1},......,g^{s^d} 和系数 c_0,c_1,......,c_d ,计算 E(p(s))= g^{p(s)}=(g^{s^d})^{c_d} ......(g^{s^0})^{c_0} ,同样计算 E(h(s)) 。
  • 将结果 g^{p(s)} 和 g^{h(s)} 提供给 verifier。
• Verifier
  • 最后一步是 verifier 在加密空间中去校验 p(s)=h(s)\cdot t(s) : g^{p(s)}=(g^{h(s)})^{t(s)}=g^{h(s)\cdot t(s)} 。

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

存在的问题：

利用强同态加密这个工具，构造了一个相对较强的零知识证明协议。但是如上文所述，这里还是存在一些问题—— 无法验证 prover 是否是真的使用了 verifier 提供的值来构造证明的。

限制多项式：

我们已经限制了 prover 对s幂的加密值的选择, 但是这个限制并不是强制的 ，也就是说，prover 可以使用任何可能的方法找到满足下面等式的值 Z_p 和 Z_h ， Z_p=(Z_h)^{t(s)} 。所以 verifier 需要能够证明 prover 给出的值就是用s幂的加密值而不是其它值计算出来的。

我们要做的就是确保 prover 是拿s的加密值，即 g^s ,而不是其他值与系数 c 做同态相乘的。所以结果一定是这个形式（c为任意值）：(g^s)^c 。

解决这个问题的一种方法就是用另一个“变换”的加密值做同样的操作，充当类似算术中“校验和”（Checksum）的作用，以此确保结果是原始值的求幂值。 通过Knowledge-of-Exponent Assumption (简称 KEA)方法来实现：

a）Alice 有一个值 a，她想要 Bob 对其进行任意指数的求幂（这里 a 是一个有限域群的生成器），唯一的要求是只能对 a 进行求幂，为了保证这一点，她要：

• 选择一个随机数 α。
• 计算 a'=a^\alpha(mod\ \ n) 。
• 提供一个元组 (a, a') 给 Bob, 然后让他对这两个值执行任意的求幂运算，返回结果元组 (b, b')，这里的指数 “α-变换” 依然保持不变，即 b^\alpha=b'(mod\ \ n) 。

b) 因为 Bob 无法从元组 (a, a') 中提取 α 的值，通过暴力破解也难以实现，那就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤：

• 选择一个值 c 。
• 计算 b=a^c(mod\ \ n) 和 b'=(a')^c(mod\ \ n) 。
• 回复 (b,b') 。

c) 有了回复的元组和 α，Alice 就可以验证等式： b^\alpha=b' 。因为 (a^c)^\alpha=a^{c\cdot\alpha}=(a^\alpha)^c=(a')^c 。

结论是：

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

更新协议：

如果给定 prover 一个指数为s的幂以及它们的变换的加密值，他就可以计算原始的和变换后的多项式，这里也必须要满足同样的校验。对于阶数为d的多项式：

• verifier 提供加密值 g^{s^0},g^{s^1},...,g^{s^d} 和 g^{\alpha s^0},g^{\alpha s^1},...,g^{\alpha s^d} 。
• prover:
  • 计算给定的带有 s 的幂的加密多项式 : g^{p(s)}=(g^{s^0})^{c_0}\cdot(g^{s^1})^{c_1}...(g^{s^d})^{c_d}=g^{s^0c0+s^1c1+...s^dc_d}
  • 计算给定的带有 s 的幂的转换的加密“转换”多项式： g^{\alpha p(s)}=(g^{\alpha s^0})^{c_0}\cdot(g^{\alpha s^1})^{c_1}...(g^{\alpha s^d})^{c_d}=g^{\alpha (s^0c0+s^1c1+...s^dc_d)}
  • 将计算结果 g^p 和 g^{p'} 发给verfier 。
• verifier 校验：(g^p)^\alpha=g^{p'}

现在我们就可以确保 prover 是用了 verifier 提供的多项式而不是其它值做计算的了，因为别的方法不能够保持 α-变换。 当然如果 verifier 想要确保在 prover 的多项式中排除了 s 的某些次幂，如 j， 他就不提供对应的密文及其变换：g^{s^j} 和 g^{\alpha s^j} 。

有了 KEA，就可以约束 prover 只能通过用 verifier 提供的加密值去构造证明了。严格点讲，这里是用的是 KEA的扩展版本，叫做 The q-power Knowledge of Exponent Assumption。

存在的问题：即理论上多项式参数 c_i 是一个很广的取值范围内的值，实际上这个范围可能很有限（比如前面例子中的 6），这就意味着 verifier 可以在有限范围的系数组合中进行暴力破解，最终计算出一个与 prover 的答案相等的结果。

零知识：

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

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

前面章节给了我们一个答案：我们可以使用随机值δ (delta)来“变换”这些值, 如 (g^p)^\delta 。 现在，为了提取知识，就必须首先要知道一个不可知的值δ。并且，这种随机化在统计学上与随机值没有什么区别。

为了保持这种关系，我们在 verifier 的检查中验证一下。等式的每一边都有一个 prover 提供的值。所以如果我们用同一个δ来“变换” 每一个值，那么等式一定保持相等。

具体来讲，就是 prover 选择一个随机值δ，并用它对证明中的值进行求幂：(g^{p(s)})^\delta,(g^{\alpha p(s)})^\delta,(g^{h(s)})^\delta 。

然后提供验证内容给 verifier：

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

非交互式：

到现在为止，讲完了一个交互式的零知识方案。但为什么还需要有非交互式呢？因为交互式证明只对原始的 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(g^a,g^b)=e(g,g)^{ab} 。

因为源数据集和输出数据集（通常被称为一个 group）是不同的，所以一个配对的结果不能用做其他配对计算的输入。我们可以将输出集（也称为“目标集”）视为“不同的宇宙”。因而我们不能用另一个加密值乘以结果，而且配对这个名称本身也表明了，我们一次只能将两个加密值相乘。配对只支持 x * y 这种两个值的乘法，但不支持三个或以上的值相乘，比如不支持 x * y * z。

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

因而因为基数在“转换”中被修改了，所以在另一个配对中不能再使用这个结果 (ab)^\mathfrak{g} （即：e((ab)^\mathfrak{g},g^d) ) 构造出想要的加密乘积abd了。配对的核心性质可以表示成下面的等式：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}=...

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

可信任参与方的 Setup:

有了配对，就去设置安全公开且可复用的参数了。假定一下我们让一个诚实的参与方来生成秘密值s和α。只有α和所有必要的s的幂及其对应的α-变换被加密了，那么原始数据就必须要被删除（ 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）： (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'} ：

• 在加密空间中校验 p = t·h： e(g^p,g^1)=e(g^t,g^h) 等价于 e(g,g)^p=e(g,g)^{t\cdot h}
• 校验多项式的限制： e(g^p,g^\alpha)=e(g^{p'},g)

信任任意一个参与者:

尽管受信任设置很有效率，但众多 CRS 用户也必须要相信生成者确实删除了 α 和 s ，这一点没有办法证明（proof of ignorance ），所以这种方法依然是无效的。因而很有必要去最小化或者消除这种信任。否则一个不诚实的参与方就可以构造假证明而不被发现。

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

• Alice 选择随机数 s_A 和 \alpha_A ，然后公开她的 CRS： (g^{s^i_A},g^{\alpha_A},g^{\alpha_A s^i_A}) 。
• Bob 选择他的随机数 s_B 和 \alpha_B ，然后通过同态乘法结合 Alice 的 CRS：((g^{s^i_A})^{s^i_B},(g^{\alpha_A})^{\alpha_B},(g^{\alpha_As^i_A})^{\alpha_Bs^i_B})，然后公开两方 Alice-Bob 的 CRS 结果: (g^{s^i_{AB}},g^{\alpha_{AB}},g^{\alpha_{AB} s^i_{AB}}) 。
• Carol 用她的随机数 s_C 和 \alpha_C 做同样的事：然后公开 Alice-Bob-Carol 的 CRS: (g^{s^i_{ABC}},g^{\alpha_{ABC}},g^{\alpha_{ABC} s^i_{ABC}}) 。

这个协议最后我们就获得了一个混合的 s^i 和 \alpha：s^i=s_A^is_B^is_C^i 和 \alpha=\alpha^A\alpha^B\alpha^C

除非他们串谋，否则参与者们互相之间并不知道其他人的秘密参数。实际上，一个参与者必须要和其它所有的参与者串谋才能得到s和α，这样在所有的参与者中只要有一个是诚实的，就没有办法伪造证明。

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

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

这就可以去验证 Bob 的 CRS 是乘以了 Alice 的参数后正常获得的，这里 i 为 1, 2,…, d：e(g^{s^i_{AB}},g)=e(g^{s^i_A},g^{s^i_B}) ,e(g^{\alpha_{AB}},g)=e(g^{\alpha_A,g^{\alpha_B}}) ,e(g^{\alpha_{AB} s^i_{AB}},g)=e(g^{\alpha_A s^i_A},g^{\alpha_B s^i_B}) 。

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

多项式的 SNARK：

我们现在准备来合并这个逐步演化出来的 zk-SNARKOP 协议。为简洁起见，我们将使用大括号来表示由旁边的下标填充的一组元素，例如： \{s^i\}_{i\in[d]} 表示一组数 s^1,s^2,...,s^d 。

我们已经明确目标多项式 t(x) 和 prover 的多项式阶数 d：

• Setup
  • 挑选随机值 s，α
  • 计算加密值 g^\alpha 和 \{g^{s^i}\}_{i\in[d]} ， \{g^{\alpha s^i}\}_{i\in\{0,...,d\}}
  • 生成 proving key： (\{g^{s^i}\}_{i\in[d]},\{g^{\alpha s^i}\}_{i\in\{0,...,d\}})
  • 生成 verification key: (g^\alpha,g^{t(s)})
• Proving
  • 分配系数 \{c_i\}_{i\in\{0,...,d\}} (即知识)得 p(x)=c_dx^d+...+c_1x^1+c_0x^0
  • 求多项式 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)} 的值
  • 选择随机数 δ
  • 构造随机化的证明 \pi=(g^{\delta p(s)},g^{\delta h(s)},g^{\delta \alpha p(s)})
• verification
  • 映射证明 π 为 (g^p,g^h,g^{p'})
  • 验证多项式约束： e(g^{p'},g)=e(g^p,g^\alpha)
  • 验证多项式系数： e(g^p,g)=e(g^{t(s)},g^h)

结论：

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