从零开始学习 zk-SNARK（二）——多项式的非交互式零知识证明

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

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

解决这个问题的一种方法就是用另一个“变换”的加密值做同样的操作，充当类似算术中“校验和”（Checksum）  的作用，以此确保结果是原始值的求幂值。

这个是通过 Knowledge-of-Exponent Assumption (简称 KEA) 方法来实现的，在  [Dam91] 中有介绍，更精准一点（注意 a 和 α(alpha)这两个字符的不同）说：

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

• 选择一个随机数 α

• 计算 a' = a ^α(mod n)

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

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

• 选择一个值 c

• 计算 b=(a)^c(mod n) 和 b' = (a')^c (mod n)

• 回复 (b,b')

c) 有了回复的元组和 α，Alice 就可以验证等式：

    (b)^α = b'

    (a^c)^α = (a')^c

    a^c·α = (a^α)^c

结论是：

• Bob 在元组的两个值的计算上都用了同一个指数（即 c）

• Bob 只能用 Alice 原本的元组来保持 α 关系

• Bob 知道指数 c，因为构造验证值 (b,b′) 的唯一方式是用同一个指数

• Alice 并不知道 c，这和 Bob 不知道 α 的原因一样

• 虽然 c 是被加密的，但它的可能取值范围并不足够大到保持其零知识的性质，这个问题我们将在后面“零知识”那一节解决。

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

在同态加密中，求幂是对被加密值进行乘法运算。我们可以应用这个结构到一个简单的系数多项式 f(x) = c⋅ x的例子中：

• verifier 选择随机数 s, α，然后提供令 x=s 的一阶及其转换的计算值：
• prover 代入系数 c 计算:

• verifier 验证：

这个结构“限制” prover 只能用 verifier 提供的加密的 s 进行计算，因而 prover 只能将系数 c 赋给 verifier 提供的多项式。现在我们可以扩展这种单项式上的方法到多项式上，因为计算是先将每项的分配分开计算然后再 “同态地” 相加在一起的（这个方法是 Jens Groth 在 [Gro10] 中介绍的）。所以如果给定 prover 一个指数为 s 的幂以及它们的变换的加密值，他就可以计算原始的和变换后的多项式，这里也必须要满足同样的校验。对于阶数为 d 的多项式：

• verifier 提供加密值 ,,…, 和他们的变换  ,,…,
• prover:
• 计算给定的带有 s 的幂的加密多项式
  
  
• 计算给定的带有 s 的幂的转换的加密“转换”多项式：
• 将计算结果 , 发给verfier
• verifier 校验：

前面的多项式例子 p(x) = x3 - 3x2 +2x 就变成了：

• verifier 提供 , ,  和它们的变换  , , 

• prover 计算：

• verifier 校验：

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

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

它们参与到了下面的验证：

问题是我们如何选择证明使得这个校验依然有效，同时又保证没有知识能被提取？

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

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

具体来讲，就是 prover 选择一个随机值 δ ，并用它对证明中的值进行求幂

然后提供验证内容给 verifier：

再合并一下我们就可以看到校验的等式依然成立：

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

到现在为止，我们已经讲完了一个交互式的零知识方案。但为什么我们还需要有非交互式呢？因为交互式证明只对原始的 verifier 有效，其他任何人（其他的 verifier）都不能够信任这个证明，因为：

• verifier 可以和 prover 串通，告诉他密码参数 s, α，有了这些参数 prover 就可以伪造证明，就像前面  remark 3.1 提到的那样。

• verifier 也可以使用同样的方法自己伪造证明。

• verifier 必须保存 α and t(s) 直到所有相关证明被验证完毕，这就带来了一个可能造成秘密参数泄漏的额外攻击面。

因而 prover 就需要分别和每个 verifier 做交互来证明一个陈述（就是例子中指的多项式的知识）。

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

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

我们先来思考一下如何在构造出秘密值 (t(s),α) 构造之后保证它的安全性。我们可以对其进行加密，方式与 verifier 在发送加密值给 prover 之前对 s 的幂使用的加密方式一致。但是 remark 3.2 中提到，我们使用的同态加密并不支持两个秘密值相乘，这一点对 t(s) 和 h 的加密值相乘以及 p 和 α 的加密值相乘的验证都很重要。这个问题适合用Pairing配对操作来解决。

因而因为基数在“转换”中被修改了，所以在另一个配对中不能再使用这个结果 (ab)ᵍ （即：e((ab)ᵍ, gᵈ)）构造出想要的加密乘积 abd 了。配对的核心性质可以表示成下面的等式：

严格来讲一个配对的结果是在目标集的一个不同生成元 g 下对原始值乘积的加密，即 e(gᵃ, gᵇ) = gᵃᵇ。因而它具备同态加密的性质，也就是说我们可以把乘法配对的加密乘积放到一起：

有了配对，我们现在就准备去设置安全公开且可复用的参数了。假定一下我们让一个诚实的参与方来生成秘密值 s 和 α。只有  α 和所有必要的 s 的幂及其对应的  α-变换被加密了，那么原始数据就必须要被删除（ i 为 0，1,…,d ）：

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

把 CRS 分成两组（ i 为 0，1,…,d ）：

• proving  key（也被称为 evaluation key）：
• verification key：

只要能够乘以加密值，verifier 就可以在协议的最后一步验证多项式了：

• 有了verification key，verifier 就可以处理从 prover 那里得到的加密多项式的值 ，，：
• 在加密空间中校验  p = t·h：
• 校验多项式的限制：

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

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

• Alice 选择随机数  和 ，然后公开她的 CRS：
  Bob 选择他的随机数  和 ，然后通过同态乘法结合 Alice 的 CRS：

   
  
  
  然后公开两方 Alice-Bob 的 CRS 结果：
  
• Carol 用她的随机数   和  做同样的事：
   
  然后公开 Alice-Bob-Carol 的 CRS:
  

这个协议最后我们就获得了一个混合的 sⁱ 和 α：

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

注意：这个过程可以被尽可能多的参与者重复完成。

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

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

• 我们用 s 的 1 次幂作为标准来校验每一个其它次幂的值与之是否保持一致

  例如：

• 2 次幂：

• 3 次幂：

   ，等。

• 我们现在再验证一下前面步骤中 α-变换后的值是否正确：

  例如：

• 3 次幂：

   ，等。

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

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

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

我们现在准备来合并这个逐步演化出来的 zk-SNARKOP 协议。为简洁起见，我们将使用大括号来表示由旁边的下标填充的一组元素，例如：

表示一组数 s¹，s²， …， s^d 。我们已经明确目标多项式 t(x) 和 prover 的多项式阶数 d：

• Setup
• 挑选随机值 s，α
• 计算加密值  和 ，
• 生成 proving key：
• 生成 verification key: 
• Proving
• 分配系数  (即知识)得 
• 求多项式 
• 代入  计算多项式  和  的值
• 代入  计算变换多项式  的值
• 选择随机数 δ
• 构造随机化的证明 
• verification
• 映射证明 π 为 
• 验证多项式约束：
• 验证多项式系数：

Remark 3.3 如果 pairing 的结果有可能在其它类似的乘法协议中被复用，那么这里就完全没有安全性可言了，因为这样的话 prover 就可以构造

这样也可以通过"多项式约束"的检查：

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

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

长按二维码添加微信进群讨论零知识证明

info@secbit.io

安比（SECBIT）实验室