[镜像] Zk-SNARKs：深入解析

[镜像] Zk-SNARKs：机制解析

这是原文的镜像，地址为https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

这是系列文章的第三部分，解释了 zk-SNARKs 背后的技术是如何工作的；之前的文章涉及二次算术程序和椭圆曲线配对，是必读材料，本文将假设对这两个概念有一定了解。同时也假设读者对 zk-SNARKs 的基本概念及其功能有基本的认识。另请参阅 Christian Reitwiessner 的文章 以获取另一种技术介绍。

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

本文将重点介绍2013年由 Parno、Gentry、Howell 和 Raykova 提出的Pinocchio 协议（通常称为 PGHR13）；虽然基本机制有一些变化，但实际实现的 zk-SNARK 方案可能稍有不同，但基本原理通常保持不变。

首先，让我们深入探讨我们要使用的机制安全性所依赖的关键密码学假设：知识指数假设 (Knowledge-of-Exponent) 。

基本上，如果你获得一对点 P 和 Q，其中 P⋅k=Q，并且你获得一个点 C，那么除非 C 以某种方式是从 P "派生" 的，否则不可能得出 C⋅k。这看起来可能直观，但这个假设实际上不能从我们通常用来验证椭圆曲线协议安全性的任何其他假设（例如离散对数难度）中推导出，因此 zk-SNARKs 确实依赖于比椭圆曲线密码学更动摇的基础——尽管对于大多数密码学家来说，这仍然足够稳固。

现在，让我们探讨这可以如何使用。假设一对点 (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)。

让我们做一些更有趣的事情。假设有十对点从天而降：(P1, Q1), (P2, Q2)...(P10, Q10)。在所有情况下，Pi⋅k=Qi。假设我随后提供你一对点 (R, S)，使得 R⋅k=S。那么你现在知道什么？你知道 R 是某种线性组合 P1⋅i1 + P2⋅i2 + ... + P10⋅i10，我知道系数 i1, i2... i10。 也就是说，得到这样一对点 (R, S) 的唯一方法是取 P1, P2... P10 的某些倍数并将它们相加，然后对 Q1, Q2... Q10 进行相同的计算。

请注意，给定你想要检查线性组合的任何特定 P1...P10 点集，你实际上无法创建伴随的 Q1...Q10 点而不知 k 的值，而如果你知道 k 的值，那么你可以创建一对 (R, S)，使得 R⋅k=S，为你想要的任意 R，而不必创建线性组合。因此，为了使其有效，创建这些点的任何人绝对必须值得信任，并在创建十个点后实际删除 k。这就是“受信设置”概念的来源。

请记住，QAP 的解是一组多项式 (A, B, C)，使得 A(x)⋅B(x)−C(x)=H(x)⋅Z(x)，其中：

• A 是一组多项式 {A1...Am} 的线性组合
• B 是 {B1...Bm} 的线性组合，系数相同
• C 是 {C1...Cm} 的线性组合，系数相同

集合 {A1...Am}, {B1...Bm} 和 {C1...Cm} 以及多项式 Z 是问题陈述的一部分。

然而，在大多数现实情况中，A、B 和 C 是极大的；对于拥有数千个电路门的哈希函数，只有多项式（及其线性组合的系数）可能有数千项。因此，我们不打算让证明者直接提供线性组合，我们将利用上述引入的技巧来让证明者证明他们提供的是线性组合而不透露任何其他内容。

你可能注意到，上述技巧适用的是椭圆曲线点，而不是多项式。因此，实际发生的事情是，我们将以下值添加到受信设置中：

• G⋅A1(t), G⋅A1(t)⋅ka
• G⋅A2(t), G⋅A2(t)⋅ka
• ...
• G⋅B1(t), G⋅B1(t)⋅kb
• G⋅B2(t), G⋅B2(t)⋅kb
• ...
• G⋅C1(t), G⋅C1(t)⋅kc
• G⋅C2(t), G⋅C2(t)⋅kc
• ...

你可以将 t 理解为“秘密点”，在该点评估多项式。G 是一个“生成器”（一个作为协议的一部分指定的随机椭圆曲线点），而 t, ka, kb 和 kc 是“毒性废物”，这些数字必须毫无例外地被删除，否则拥有它们的人将能够伪造证明。现在，如果有人给你一对点 P, Q，使得 P⋅ka=Q（提醒：我们不需要 ka 来检查这一点，因为我们可以进行配对检查），那么你知道他们给你的是在 t 上评估的 Ai 多项式的线性组合。

因此，到现在为止，证明者必须提供：

• πa=G⋅A(t), πa′=G⋅A(t)⋅ka
• πb=G⋅B(t), πb′=G⋅B(t)⋅kb
• πc=G⋅C(t), πc′=G⋅C(t)⋅kc

请注意，证明者实际上并不需要（也不应该需要！）t, ka, kb 或 kc 来计算这些值；相反，证明者应该能够仅凭我们添加到受信设置中的点计算这些值。

下一步是确保所有三个线性组合具有相同的系数。我们可以通过将另一组值添加到受信设置来做到这一点：G⋅(Ai(t)+Bi(t)+Ci(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)。这七个点都是 Fp 曲线上的（每个32字节，因为你可以将 y 坐标压缩到一个位），而在 Zcash 实现中一个点（πb）位于 Fp2 中的扭曲曲线上（64 字节），因此证明的总大小为 ~288 字节。

生成证明的两个计算最困难的部分是：

• 除了 (A⋅B−C)/Z 得到 H（基于快速傅里叶变换 的算法可以做到这一点，整个过程是次二次时间，但它仍然是相当占计算资源的）

• 进行椭圆曲线的乘法和加法以创建 A(t)、B(t)、C(t) 和 H(t) 值及其对应的配对

创建证明如此困难的基本原因在于，原始计算中的单一二进制逻辑门变成需要通过椭圆曲线操作进行加密处理的操作，如果我们要将其制成零知识证明。这一点，加上快速傅里叶变换的超级线性特性，意味着生成 Zcash 交易的证明大约需要 20-40 秒。

另一个非常重要的问题是：我们可以尝试让受信设置变得稍微... 少一些信任要求吗？不幸的是，我们无法做到完全无信任；知识指数假设本身禁止在不知道 k 的情况下独立生成对 (Pi, Pi⋅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最近的演讲以获取一个替代方案（但请注意，它在数学上至少和 SNARKs 一样复杂！）

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

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