Zk-SNARKs：引擎盖下
作者：Vitalik Buterin
原标题：《Zk-SNARKs: Under the Hood》
发表时间：2017 年 2 月 1 日
这是解释 zk-SNARKs 背后的技术如何工作的系列文章的第三部分；以前关于二次算术程序和椭圆曲线配对的文章是必读的，本文将假设这两个概念的知识。还假设了 zk-SNARK 是什么以及它们做什么的基本知识。另请参阅此处的 Christian Reitwiessner 的文章以获得另一篇技术介绍。
在之前的文章中，我们介绍了二次算术程序，这是一种用多项式方程表示任何计算问题的方法，它更适合各种形式的数学技巧。我们还介绍了椭圆曲线配对，它允许一种非常有限的单向同态加密形式，可以让你进行相等性检查。现在，我们将从上次中断的地方开始，使用椭圆曲线配对以及其他一些数学技巧，以允许证明者证明他们知道特定 QAP 的解决方案，而无需透露任何关于实际解决方案。
本文将重点介绍 Parno、Gentry、Howell 和 Raykova 从 2013 年开始的Pinocchio 协议（通常称为 PGHR13）；基本机制有一些变化，因此在实践中实施的 zk-SNARK 方案可能会略有不同，但基本原理通常保持不变。
首先，让我们进入我们将要使用的机制的安全性背后的关键密码假设：指数知识假设。
基本上，如果你得到一对点 P 和 Q，其中 P * k = Q，并且你得到一个点 C，那么除非 C 以某种方式从 P“派生”出来，否则不可能得出 C * k你知道的。这可能看起来很直观，但是这个假设实际上不能从我们通常在证明基于椭圆曲线的协议的安全性时使用的任何其他假设（例如离散对数硬度）推导出来，因此 zk-SNARK 实际上确实依赖于比椭圆曲线密码学更普遍的基础更不稳定——尽管它仍然足够坚固，大多数密码学家都可以接受。
现在，让我们来看看如何使用它。假设有一对点 (P, Q) 从天上掉下来，其中 P * k = Q，但没有人知道 k 的值是多少。现在，假设我提出了一对点 (R, S)，其中 R * k = S。那么，KoE 假设意味着我可以得出这对点的唯一方法是取 P 和 Q，并且将两者乘以我个人知道的某个因子 r 。还要注意，由于椭圆曲线配对的魔力，检查 R = k * S实际上并不需要知道 k -相反，你可以简单地检查 e(R, Q) = e(P, S)。
让我们做一些更有趣的事情。假设我们有十对点从天而降：(P_1, Q_1), (P_2, Q_2)… (P_10, Q_10)。在所有情况下，P_i * k = Q_i。假设我随后为你提供一对点 (R, S)，其中 R * k = S。你现在知道什么？你知道 R 是一些线性组合 P_1 * i_1 + P_2 * i_2 + … + P_10 * i_10，其中我知道系数 i_1, i_2 … i_10。也就是说，要得到这样的一对点（R，S），唯一的方法就是取P_1，P_2…P_10的一些倍数并将它们相加，然后用Q_1，Q_2…Q_10进行相同的计算。
请注意，给定任何你可能想要检查线性组合的特定 P_1…P_10 点集，你实际上无法在不知道 k 是什么的情况下创建随附的 Q_1…Q_10 点，如果你确实知道 k 是什么，那么你可以创建一对 (R, S) ，其中 R * k = S 为你想要的任何 R，而无需创建线性组合。因此，要使其发挥作用，绝对必须确保创建这些点的人是值得信赖的，并且在创建十个点后实际上删除 k。这就是“可信设置”概念的来源。
请记住，QAP 的解是一组多项式 (A, B, C)，使得 A(x) * B(x) - C(x) = H(x) * Z(x)，其中：
- A 是一组多项式 {A_1…A_m} 的线性组合
- B 是具有相同系数的 {B_1…B_m} 的线性组合
- C 是具有相同系数的 {C_1…C_m} 的线性组合
集合 {A_1…A_m}、{B_1…B_m} 和 {C_1…C_m} 以及多项式 Z 是问题陈述的一部分。
但是，在大多数实际情况下，A、B 和 C 都非常大；对于像散列函数这样具有数千个电路门的东西，多项式（以及线性组合的因子）可能有数千个项。因此，我们不是让证明者直接提供线性组合，而是使用我们上面介绍的技巧让证明者证明他们提供的东西是线性组合，但不透露其他任何东西。
你可能已经注意到，上面的技巧适用于椭圆曲线点，而不是多项式。因此，实际发生的是我们将以下值添加到可信设置中：
G * A_1(t), G * A_1(t) * k_a
G * A_2(t), G * A_2(t) * k_a
…
G * B_1(t), G * B_1(t) * k_b
G * B_2(t), G * B_2(t) * k_b
…
G * C_1(t), G * C_1(t) * k_c
G * C_2(t), G * C_2(t) * k_c
…
你可以将 t 视为计算多项式的“秘密点”。G 是一个“生成器”（一些随机椭圆曲线点，被指定为协议的一部分），t、k_a、k_b 和 k_c 是“有毒废物”，绝对必须不惜一切代价删除的数字，或者拥有它们的人将能够制作假证明。现在，如果有人给你一对点 P, Q 使得 P * k_a = Q （提醒：我们不需要 k_a 来检查这个，因为我们可以做配对检查），那么你知道他们给了什么你是在 t 处求值的 A_i 多项式的线性组合。
因此，到目前为止，证明者必须给出：
π_a = G * A(t), π'_a = G * A(t) * k_a
π_b = G * B (t), π'_ b = G * B(t) * k_b
π_c = G * C(t), π'_c = G * C(t) * k_c
请注意，证明者实际上不需要知道（也不应该知道！）t、k_a、k_b 或 k_c 来计算这些值；相反，证明者应该能够仅根据我们添加到可信设置的点来计算这些值。
下一步是确保所有三个线性组合具有相同的系数。我们可以通过向可信设置添加另一组值来做到这一点：G * (A_i(t) + B_i(t) + C_i(t)) * b，其中 b 是另一个应该被视为“有毒废物”的数字，并且受信任的设置完成后立即丢弃。然后，我们可以让证明者使用具有相同系数的这些值创建一个线性组合，并使用与上述相同的配对技巧来验证该值是否与提供的 A + B + C 匹配。
最后，我们需要证明 A * B - C = H * Z。我们通过配对检查再次执行此操作：
e( π_ a, π_ b) / e( π_ c, G) ?= e( π_ h, G * Z(t))
其中π_h = G * H (t)。如果这个方程和 A * B - C = H * Z 之间的联系对你来说没有意义，请返回阅读有关配对的文章。
我们在上面看到了如何将 A、B 和 C 转换为椭圆曲线点；G 只是生成器（即椭圆曲线点等价于数字一）。我们可以将 G * Z(t) 添加到可信设置中。H更硬；H 只是一个多项式，我们很少提前预测每个单独 QAP 解决方案的系数。因此，我们需要向可信设置添加更多数据；具体顺序：
G, G * t, G * t², G * t³, G * t⁴ ...。
在 Zcash 可信设置中，这里的序列高达 200 万左右；这是你需要多少次幂才能确保始终能够计算 H(t)，至少对于他们关心的特定 QAP 实例而言。这样，证明者就可以为验证者提供所有信息以进行最终检查。
还有一个细节需要我们讨论。大多数时候，我们不只是想抽象地证明某些特定问题的解决方案存在；相反，我们想证明某个特定解决方案的正确性（例如，证明如果你使用“cow”一词并对其进行 SHA3 哈希一百万次，最终结果以 0x73064fe5 开头），或者如果你限制解决方案存在一些参数。例如，在交易金额和账户余额被加密的加密货币实例中，你想证明你知道一些解密密钥 k，这样：
加密的 old_balance、tx_value 和 new_balance 应该公开指定，因为这些是我们希望在特定时间验证的特定值；只有解密密钥应该被隐藏。需要对协议进行一些细微的修改，以创建与输入的某些特定限制相对应的“自定义验证密钥”。
现在，让我们退后一步。首先，这里是完整的验证算法，由 ben Sasson、Tromer、Virza 和 Chiesa提供：
第一行处理参数化；本质上，你可以将其功能视为为指定了某些参数的问题的特定实例创建“自定义验证密钥” 。第二行是A、B、C的线性组合检查；第三行是检查线性组合是否具有相同的系数，第四行是乘积检查 A * B - C = H * Z。
总之，验证过程是几个椭圆曲线乘法（每个“公共”输入变量一个）和五次配对检查，其中一次包括额外的配对乘法。证明包含八个椭圆曲线点：A(t)、B(t) 和 C(t) 各有一对点，b * (A(t) + B(t) + C(t ) 有一个点π_k ))，以及H(t)的点π_h 。其中七个点在 F_p 曲线上（每个 32 个字节，因为你可以将 y 坐标压缩到一个位），在 Zcash 实现中，一个点 ( π_b ) 在 F_p² 的扭曲曲线上（64 个字节） ，所以证明的总大小约为 288 字节。
创建证明的两个计算上最难的部分是：
将 (A * B - C) / Z 除以得到 H（基于快速傅立叶变换的算法可以在次二次时间内完成此操作，但它的计算量仍然很大）
进行椭圆曲线乘法和加法运算以创建 A(t)、B(t)、C(t) 和 H(t) 值及其对应的对
创建证明如此困难的基本原因是，如果我们要从中制作零知识证明，原始计算中的单个二进制逻辑门变成了必须通过椭圆曲线操作进行加密处理的操作. 这一事实，加上快速傅立叶变换的超线性，意味着 Zcash 交易的证明创建需要大约 20-40 秒。
另一个非常重要的问题是：我们是否可以尝试使受信任的设置稍微……不那么需要信任？不幸的是，我们不能让它完全不信任；KoE 假设本身排除了在不知道 k 是什么的情况下制作独立对 (P_i, P_i * k)。但是，我们可以通过使用 N-of-N 多方计算来大大提高安全性——也就是说，在 N 方之间构建可信设置，只要至少有一个参与者删除他们的有毒废物，那么你就可以了.
为了稍微了解如何执行此操作，这里有一个简单的算法，用于获取现有集合（G、G * t、G * t²、G * t³…），并“添加”你自己的秘密，以便你需要你的秘密和以前的秘密（或以前的一组秘密）来作弊。
输出集很简单：
G, (G * t) * s, (G * t²) * s², (G * t³) * s³…
请注意，你可以只知道原始集合和 s 来生成此集合，并且新集合的功能与旧集合相同，只是现在使用 t*s 作为“有毒废物”而不是 t。只要你和创建前一组的人（或多人）都没有删除你的有毒废物并随后串通，那么该组是“安全的”。
为完整的受信任设置执行此操作要困难得多，因为涉及多个值，并且必须在各方之间分几轮完成算法。这是一个积极研究的领域，看看是否可以进一步简化多方计算算法并使其需要更少的轮次或更可并行化，因为你可以做的越多，参与可信设置过程的参与方就越多. 有理由看到为什么六个相互认识并一起工作的参与者之间的信任设置可能会让一些人感到不舒服，但是一个拥有数千名参与者的信任设置与完全不信任几乎没有区别——而且如果你真的很偏执，你可以自己进入并参与设置过程，并确保你亲自删除了你的值。
另一个活跃的研究领域是使用不使用配对的其他方法和相同的可信设置范例来实现相同的目标。请参阅Eli ben Sasson 最近的演示文稿以了解另一种选择（尽管请注意，它至少在数学上与 SNARK 一样复杂！）
特别感谢 Ariel Gabizon 和 Christian Reitwiessner 的审阅。
