深入解析 Zk-SNARKs：第三部分

这是解释 zk-SNARKs 背后技术的系列文章的第三部分；之前的文章关于 二次算术程序 和 椭圆曲线配对 是必读材料，本文将假设读者对这两种概念有所了解。我们也假设读者对 zk-SNARKs 的基本概念和功能有所了解。另请参阅 Christian Reitwiessner 的文章 以获得另一份技术介绍。

在之前的文章中，我们介绍了二次算术程序，这是一种用多项式方程表示任何计算问题的方式，更易于进行各种数学技巧。我们还介绍了椭圆曲线配对，这允许一种非常有限的单向同态加密形式，让你进行相等性检查。现在，我们将从我们停下的地方开始，使用椭圆曲线配对和一些其他数学技巧，使得证明者能够证明他们知道某个特定 QAP 的解，而不会透露实际解的其他任何信息。

本文将重点讨论 Parno、Gentry、Howell 和 Raykova 在 2013 年提出的 Pinocchio 协议（通常称为 PGHR13）；基本机制有一些变体，因此在实际中实现的 zk-SNARK 方案可能略有不同，但基本原则通常保持不变。

首先，让我们进入支撑我们将要使用的机制安全性上的关键密码学假设：知识指数 假设。

基本上，如果你得到一对点 P 和 Q，其中 P * k = Q，并且你得到一个点 C，那么除非 C 是以你知道的某种方式“导出”的，否则无法得出 C * k。虽然这在直觉上是显而易见的，但这个假设实际上无法从我们通常在证明椭圆曲线协议安全性时使用的任何其他假设中推导出来（例如离散对数问题的困难性），因此 zk-SNARKs 确实建立在比更广泛的椭圆曲线密码学更为脆弱的基础之上——虽然它仍然足够坚固，因此大多数密码学家对此是可以接受的。

现在，让我们来看一下这如何使用。假设一对点 (P, Q) 从天而降，其中 P * k = Q，但没有人知道 k 的值。现在，假设我找到了另一对点 (R, S)，其中 R * k = S。那么，KoE 假设意味着我唯一能得到那对点的方法是通过以某个我个人知道的因子 r 对 P 和 Q 进行乘法。还要注意，由于椭圆曲线配对的特性，检查 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，而不必去创建线性组合。因此，为了使这一切能够工作，创建这些点的任何人都必须是可信的，并且在创建这十个点后确实删除了 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 来检查这一点，因为我们可以进行配对检查），那么你知道他们给你的是什么，就是真正的对 A_i 多项式在 t 的线性组合。

因此，到目前为止，证明者必须提供：

• π _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) 所需的 t 的幂数，至少对于他们关心的特定 QAP 实例而言。有了这些，证明者可以提供验证者所需的所有信息以进行最终检查。

还有一个细节需要讨论。大多数情况下，我们不仅想抽象地证明某个特定问题存在解决方案；相反，我们希望证明某个特定解决方案的正确性（例如，证明如果你将单词“cow”进行 SHA3 哈希处理一百万次，最终结果以 0x73064fe5 开头），或者如果你限制某些参数，则存在一个解决方案。例如，在交易金额和账户余额被加密的加密货币实例中，你希望证明你知道某个解密密钥 k，使得：

1. decrypt(old_balance, k) ≥ decrypt(tx_value, k)
2. decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, 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) 各一对点，一个点 π\_k 对 b * (A(t) + B(t) + C(t))，以及一个点 π__h 对 H(t)。这七个点位于 F_p 曲线上（每个 32 字节，因为你可以将 y 坐标压缩为一位），而 Zcash 实现中的一个点（π _b）位于 F_p² 的扭曲曲线上（64 字节），因此证明的总大小为 ~288 字节。

创建证明最困难的两个部分是：

• 除以 (A * B - C) / Z 以获得 H（基于 快速傅里叶变换 的算法可以在亚二次时间内完成，但这仍然是相当计算密集型的）
• 进行椭圆曲线乘法和加法以创建 A(t)、B(t)、C(t) 和 H(t) 值及其对应的对

创建证明之所以如此困难的主要原因是，最初计算中的一个单独的二进制逻辑门在我们进行零知识证明时变成了必须通过椭圆曲线操作进行加密处理的运算。这个事实，加上快速傅里叶变换的超线性特性，因此创建证明需要 ~20-40 秒的 Zcash 交易时间。

另一个非常重要的问题是：我们能否尝试使受信任的设置变得稍稍……少一点信任需求？不幸的是，我们无法使其完全无信任；KoE 假设本身排除了在不知道 k 的情况下制作独立对 (P_i, P_i * k)。但是，通过使用 N-of-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 最近的演讲 以获取一种替代方法（但是要注意，它在数学上至少与 SNARKs 一样复杂！）

特别感谢 Ariel Gabizon 和 Christian Reitwiessner 的审阅。

• 原文链接： medium.com/@VitalikButer...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～