密码学 101：零知识证明（第 2 部分）

这是一系列关于密码学的文章中的一篇。如果这是你第一次阅读本系列文章，我强烈建议你从本系列的开篇开始。

在过去的几篇文章中，我们涵盖了许多基础构件。现在终于到了将这些乐高积木组合成一个协议的时候了。万岁！

请记住，我们之所以如此努力理解这些动态部分，是为了尝试为零知识证明构建一个通用框架——因为正如我们所看到的，为特定应用创建协议有些不切实际，需要专门的研究。

现在，我们准备引入一个利用我们预先定义的每个元素的知识证明家族：SNARKs。

具体来说，我们将研究一个名为Plonk的方案。要全面了解该技术，请参考此处。我会尽力尽可能准确地解释它。此外，这并不是唯一符合SNARK标准的协议。还存在其他机制，如Groth16、Marlin和Halo。我可能会在未来探讨这些内容，但现在，我只在这里留下几个链接，以防你想满足好奇心！

免责声明

这篇文章会很长，而且说实话，很复杂。也就是说，可能比平常更难。对于一个非常复杂的协议，我能简化解释的余地实在有限。

但是，如果要用一句话概括整个过程，那就是：

在 Plonk 中，我们将电路的计算编码为一系列多项式，这些多项式代表电路施加的约束，通过一系列测试来证明陈述，而无需揭示多项式本身——从而不泄露秘密输入。

要完全理解这将是一次疯狂的旅程。我们需要涵盖几个要素。以下是计划的概述，也可作为目录：

提示：你可以通过 command + 点击跳转到链接部分！

• 电路作为约束集合
• 将电路编码为多项式.-,Encoding%20the%20Circuit,-Having%20said%20all)
• 列出验证要求
• 验证技术
• 验证

此外，我假设你已经阅读了关于多项式承诺方案的文章，以及关于算术电路的文章。如果还没有，我强烈建议先阅读它们！

闲话少说，我们开始吧！

什么是 SNARK？

这个缩写代表简洁非交互式知识论证（Succinct Non-interactive ARguments of Knowledge）。用简单英语来说：一种证明知识的机制，具有简洁（或短小）和非交互的特点。我们需要在此剖析几点，以更好地理解构造的目标：

• 简洁意味着我们生成的任何证明在大小上必须小，且验证时间快。
• 非交互意味着验证者在收到证明后，无需与证明者进一步交互。稍后会详细说明。
• 最后，我们说这是一种知识证明，但不一定是零知识证明（尽管它可以是）。特别是，Plonk由于其构造方式，符合零知识标准。

别担心——我们暂时还不能构建SNARK。我们需要先涵盖几个概念。

重温电路

在之前的文章中，我们看到了算术电路如何优雅地表示计算，以及如何为陈述的验证制定方案。

因此，证明者的目标将是试图说服验证者，他们知道某个秘密值 x——实际上是一个值的向量——满足：

证明者不想揭示x，同时，我们也不希望验证者运行昂贵的电路计算。因此，实际发生的情况是，证明者将评估电路，然后将输入和每个门的结果（也称为计算轨迹）编码。

以下是一个使用域 𝔽₁₁₃ 的评估示例：

注意：在本例中，我们使用模 n = 113

我们可以将此评估视为以下轨迹，以表格形式可视化：

+-----------+------+------+------+
|           |  w1  |  x1  |  x2  |
+-----------+--------------------+
| inputs    |  20  |  13  |  5   |
+-----------+--------------------+

+-----------+--------------+---------------+----------+
|           |  left input  |  right input  |  output  |
+-----------+--------------+---------------+----------+
| gate 0    |  5           |  20           |  100     |
+-----------+--------------+---------------+----------+
| gate 1    |  13          |  100          |  0       |
+-----------+--------------+---------------+----------+

包括Plonk在内的现代 SNARK 的绝妙思想是将此轨迹编码为多项式，最终使验证者能够检查计算的有效性。这里的有效意味着遵循一组特定的约束。即：

• 每个门被正确评估
• 线（具有相同来源）具有相同的值

这里的线指的是电路中门之间的连接或输入到门的连接。我们可以将这些线视为保存电路的值，而不是节点本身：

在此图中，你可以看到某些线应保持相同的值：W₀、W₁和W₂，以及W₄和W₅。此外，门应有意义——例如，W₀ + W₁应等于W₄。

电路既可以作为计算的方案，也可以作为要检查的约束集合！

每组约束——线值、门约束和布线约束——将被编码到不同的多项式中。

例如，整个计算轨迹可以编码为单个多项式P，其中P(xᵢ)对应于某条线。

我们有线值Wᵢ，但需要选择将哪些xᵢ值编码到其中。使用某些整数是完全可以的选项——比如集合{0,1,2,3…,N}。但使用域 𝔽ₚ 的单位根会带来更多好处。

嗯？

单位根

我之前提到过这个概念，但像《黑客帝国》中的尼奥一样避而不谈。现在正是深入理解即将出现的符号的好时机。

因此，定义如下：如果满足以下条件，我们称值ω（希腊字母 omega）为域 𝔽ₚ 的k 次单位根：

在这种情况下，集合H：

同时也是一个由ω生成的循环乘法群：

使用此集合中的元素作为编码多项式P(X)的输入有两个好处。首先，从一个单位根移动到下一个单位根，只需乘以 ω。同样，向后移动则是乘以ω 的逆元。并且它是循环的：根据定义：

其次——也是最重要的部分——使用此集合允许我们使用最高效的算法进行插值：快速傅里叶变换。我们不会深入探讨其工作原理（至少现在不会！），但要知道这大大缩短了插值时间——这意味着生成证明的速度更快（相较于其他插值方法）。

编码电路

说了这么多，是时候进入正题了。实际看看计算轨迹是如何被编码的。

我们用|I|表示电路的输入数量，用|C|表示门的数量。由此，我们定义：

每个门有三个关联值：两个输入和一个输出。这就是我们使用 3|C| 的原因。注意这个神奇的数字 d 恰好等于计算轨迹中的值数量！

我们将所有这些值编码到d 次单位根中：

但哪个根编码到哪条线呢？我们需要一个计划！

• |I| 个输入将使用ω 的负幂进行编码。对于输入#j，我们使用：

• 每个门k 关联的三条线（按左输入、右输入、输出顺序）将由以下值编码：

查看我们的示例轨迹，将得到如下结果：

通过这种方式，计算轨迹中的所有值都被包含在多项式中。我们只需插值即可得到P(X)，其次数为d - 1。

门编码

门带来了一个复杂问题：它们可以是加法门或乘法门。这意味着要证明门的评估正确，需要传达其类型的信息。

我们通过选择器多项式 S(X) 实现这一点。对于门k：

当门k是加法门时，S(X) 取值 1；如果是乘法门，则取值 0。为简化书写，我们定义：

然后构造以下表达式：

别被表达式吓到——实际发生的事相当直接。你看，要么S(α) = 0，要么1 - S(α) = 0。因此，只有包含S(X) 的一个项会对某个门k 激活，从而将门的输入（P(α) 和 P(ωα)）和输出（编码在 P(ω²α) 中）与门类型联系起来。

布线编码

这是最棘手的一部分。如前所述，某些线可能对应相同的值，因为它们来自同一来源，例如：

这意味着编码到P(X) 中的某些值需要匹配：

如果分析整个电路，最终将得到一组此类约束：

以上面的示例为例。但一般来说，每个等式可能包含超过 2 个成员

当然，每个这样的约束都必须以某种方式编码到多项式中。我们的做法相当有趣：对于每个约束，我们定义一个置换或轮换应匹配的根的子集的多项式。例如，如果条件是：

那么我们定义子集：

并使用H'，我们创建一个多项式W(X)，其具有以下属性：

它本质上在子集H' 中循环。这实际上是 Plonk 得名的部分原因！

由于W(X) 总是返回H' 中的“下一个”元素，并且由于H' 中根上的P(X) 值应相等，我们通过证明以下内容来证明布线约束成立：

这必须对H' 中的每个元素执行，从而通过单一约束涵盖所有等式。

好吧！这确实很多。尽管如此，我们已经涵盖了大量内容。

此时，证明者拥有编码整个计算轨迹的所有多项式。还缺少什么？只有最重要的部分：说服验证者轨迹正确。一旦我们理解这是如何发生的，一切终将串联起来。

验证要求

当然，验证者不知道我们刚才讨论的多项式。特别是，他们永远不能知道完整的P(X)。原因是，如果他们确实掌握了它，就可以轻松揭示秘密信息x，通过计算：

通过使用多项式来永不揭示这些值的能力，是 Plonk 具备零知识属性的原因！

如果验证者无法知道多项式，那么我们如何说服他们任何事情？我们是否走进了死胡同？现在应该恐慌吗？

我猜你已经知道这个叙事技巧了

虽然验证者无法请求完整的多项式，但他们肯定可以请求它们的单个评估。他们应该能够查询P(X)、S(X) 或W(X) 的任何部分——当然，除了秘密输入。

此时，我们选择的多项式承诺方案（PCS）派上用场：当请求P(X) 在某个点b 的值（即P(b)）时，验证者可以通过检查承诺来验证其正确性！妙啊。

不过，他们为什么要这么做？为了检查约束是否成立！

为了确信计算轨迹正确，验证者需要检查：

• 最后一个门的输出恰好为 0，
• 输入（公共输入或见证）被正确编码，
• 每个门的评估正确（加法或乘法成立），
• 布线正确。

第一个检查很简单——验证者只需请求最后一个门的输出，即：

对于其他检查，我们需要加入一些魔法（此时已是惯例）。

我从未真正理解这家伙，但嘿，这是个好梗

最后的密码魔法

我们需要稍微绕个弯。这里有个问题：给定某个次数最多为 d 且非零（即f(x) ≠ 0）的多项式，对于随机输入 r（从模 n 的整数中采样），f(r) = 0 的概率有多大？

由于多项式的次数最多为 d，它最多有d 个根。因此，f(r) = 0 的概率恰好是r 恰好是f 的根的概率：

只要n 足够大于d，这就是一个可忽略的值（非常接近于零）。这很重要：如果我们随机选择某个r 并得到f(r) = 0，那么我们可以高概率断言f(x) 恒等于零！

这被称为零测试。看起来没什么大不了，但我们需要用它来使SNARK 工作。

还有几个其他检查可以执行，即加法检查和乘积检查。这已经需要消化大量信息，所以暂时跳过这些。

有趣的是，存在高效的交互式预言证明来执行这些测试。

抱歉……交互式什么？

*崩溃*

交互式预言证明

我警告过你这不会容易！再加把劲，我们就完成了。

交互式预言证明（IOPs）本质上是一组机制，通过它们，证明者和验证者相互交互，使证明者能够说服验证者某个陈述的真实性。大致如下：

我希望你已经看出此图与描述多项式承诺方案（PCSs）的图相似！

我们将使用此模型执行测试。为说明目的，描述零测试如何进行。

假设你想证明某个集合S 是给定多项式P(X) 的根的集合：

你能做什么？由于S 中的值是根，你可以将多项式P(X) 除以所谓的消失多项式：

消失一词源于该多项式仅在集合 S 上为零，因此它们正是其根。

如果S 确实是P(X) 的根，则P 应可被V(X) 整除，没有余数。

现在，我们需要使用多项式承诺方案（PCS）继续。你可能需要先阅读那篇文章！

本质上，证明者承诺P(X) 和Q(X)，然后请求在某个随机sᵢ 处进行评估。通过这些评估，他们可以检查以下是否为真：

如果结果为零，那么他们可以高概率断定该多项式恰好为零！即：

因此，他们可以确信，实际上，S 是P(X) 的根集合。如果出于某种原因他们还不信，可以请求P(s) 和Q(s) 的另一组评估，并再次运行检查。

类似的 IOP 也适用于加法检查和乘积检查。

还值得一提的是，这并不能确保多项式没有其他不在 S 中的根。但这次我们不会深入探讨！

从交互式到非交互式

但是等等……我们不是说SNARKs 是非交互式的吗？那么，交互式协议如何成为我们构造的关键部分？

事实证明，有一种方法可以将交互性转化为非交互性：Fiat-Shamir 变换。听起来比实际更可怕，相信我。

如果我们思考，可能会问“为什么这些协议一开始是交互式的？”原因是在每个查询中，验证者从某个集合中采样一些随机数 rᵢ。这些值无法被证明者预测——只有当验证者决定执行查询时，它们才会对证明者可用。这种不可预测性是一种反作弊机制。

与其等待验证者发送随机值，我们可以使用具有不可预测输出的著名密码学原语——哈希函数来模拟这种随机性！

不过，不要关注细节——你只需知道 Fiat-Shamir 启发式是一种强大的转换，可以将任何交互式协议转换为非交互式协议！

在经过堪称折磨的过程后，我们拥有了所需的所有要素。我们的艰辛旅程即将结束——只剩下最后的点睛之笔。

快结束我的痛苦吧

回到验证

好了，让我们看看。记住，我们试图说服验证者我们知道x 满足：

我们需要说服他们以下几点：

• 正确输入
• 正确的门计算
• 正确布线

从输入开始。验证者拥有公共见证 w。现在，假设验证者将此见证编码为多项式 v(X)，使得：

在这种情况下，v(x) 和 P(x) 的值应在编码公共见证的单位根处匹配：

那我们该怎么做？当然是对编码见证的输入进行多项式P(X) - v(X) 的零测试！

啊哈！开始串联起来了吧？

检查门

同样，回想一下门应满足表达式：

那么，该怎么做？对这个庞大的表达式进行零测试，在每个门上。太棒了。精彩。

当然，为此验证者需要 S(X) 的承诺。

检查线

最后，我们需要检查线约束。这些被编码到一些W(X) 多项式中，这些多项式在输入集合H' 中循环，我们需要检查：

对于H' 中的每个元素。使用零测试（尽管可行）效率不高，因此有一种通过乘积检查的替代方法。使用这个随意抛出的表达式：

是的

关键在于整个表达式应等于 1！如果你仔细想想，这完全合理：所有P(x) 值应相同，并且由于W(X) 置换 H' 中的元素，且乘积覆盖了H' 的所有元素，我们得到：

关于这一点还有更多可说，比如为什么需要将 Y 和 Z 引入其中？但说实话，我认为今天的数学已经足够了。

简而言之，总结一下：我们使用一些IOPs 来验证编码到多项式中的算术电路约束！

总结

呼。内容太多了。我知道。

我们知道你不好受，罗斯。没事的

尽管如此，我惊讶于所有这些元素如何结合形成如此复杂的协议：我们使用多项式插值编码内容，多项式承诺方案查询信息，交互式预言证明创建测试，以及Fiat-Shamir 启发式将这一切变为非交互式证明。难以置信。

最终结果，Plonk，通过允许使用任何电路实现了我们追求的通用性。由于这没有揭示x 的任何信息，因此这确实是一个零知识 SNARK（zkSNARK）！

为完整起见，我需要指出，为了确保协议是零知识的，还需要考虑其他细节，特别是关于挑战。不过，除非你打算自己实现 Plonk，否则不必担心太多！

如需更互动式的了解，可查看此优秀视频课程。还有另一篇解释该协议的文章，可能更易理解！

希望你现在能更好地理解文章开头对 Plonk 的简要描述：

在 Plonk 中，我们将电路的计算编码为一系列多项式，这些多项式代表电路施加的约束，通过一系列测试来证明陈述，而无需揭示多项式本身——从而不泄露秘密输入。

既然我们现在可以为任意电路构建证明，我想更实际些。因此，下篇文章中，我们将为一些陈述构建几个电路，然后作为 Plonk 的输入，将其转换为zkSNARKS。再见！

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