密码学基础：零知识证明（第一部分）

这是关于加密技术的系列文章的一部分。如果这是你遇到的第一篇文章，我强烈建议你从系列的开头开始阅读。

现在是时候讲解一些零知识证明了！

在这个系列的前面，我们概述了它们是什么。不过这次我们会更加深入地定义，并查看一个更高级的例子。

零知识证明（ZKP）的一般思想是说服某人某个关于一些信息的声明是真实的，而不泄露该信息。这一声明可能具有不同的性质。我们可能想证明：

• 知识某个离散对数（Schnorr 协议）
• 某个数字在某个范围内
• 一个元素是某个集合的成员

等等。通常，这些声明需要不同的证明系统，这意味着需要特定的协议。这在某种程度上是不实用的——如果我们能对知识证明进行概括，那将是非常好的。

所以我们的计划如下：我们将查看一种叫做Bulletproofs的ZKP技术。我们将看到它们如何解决一个非常特定的问题，并在接下来的几篇文章中评估几乎同样的事情如何以更一般的方式实现。

我们将专注于简单、未优化的版本（这已经足够复杂了！）。如果这篇文章不够满足你的好奇心，查看原始论文或这里的这篇文章可能就是你所寻找的。

在深入数学之前，让我们先简单介绍一下这个主题。

零知识基础

当我们谈论证明声明的有效性时，广义的技术家族称为知识证明（proofs of knowledge）。在这些类型的协议中，通常涉及两个参与者：一个证明者（prover）和一个验证者（verifier）。

还有两个关键要素：我们想要证明的声明，和一个见证（witness），这是一段信息，让我们能够有效地检查该声明是否为真。大概如下图所示：

但这并不是完整的故事！

如果你记得我们对Schnorr协议的简要回顾，我们看到证明者和验证者之间存在一些来回的通信。这是有充分理由的：验证者向证明者提供了一段不可预测的信息。这样做可以使得生成虚假证明极其困难——只要证明者是诚实的，产生有效证明就非常简单。这种“通配符”因素通常被称为挑战（challenge）。

一个简单的例子

为了理解这个想法，这里有一个很简单的练习：想象一下，Alice（Alice）将一组秘密的扑克牌面朝下放在桌子上。坐在桌子对面的Bob（Bob）想检查Alice是否知道这组秘密牌。他可以怎么做？

好吧，他可以问“告诉我第四张牌是什么”。如果Alice确实知道这组牌，她可以自信地回答“黑桃7”，而Bob可以仅仅查看那张面朝下的牌并检查其是否一致。Bob选择了一张牌提出了一个挑战，而只有通过对牌序列的诚实知识，Alice才能提供正确的信息。否则，她只能猜测——而她说对的牌的可能性是不太可能的。

当然，这不是零知识，因为序列的部分信息被揭示了！

将这个挑战加入到混合中，我们得到了一个更完整的图像：

这个想法是，证明者在知道验证者的输入之前对他们的信息进行承诺，而在我们的例子中，Alice是通过将牌面朝下放置来承诺——这种做法在一定程度上防止了她作弊。

正式地说，我们刚刚描述的结构典型于西格玛协议。你可能还会见到公共币验证者这一术语，这意味着验证者的随机选择被公开。为了避免混淆，了解一下就好！

为了结束我们的简要介绍，这里是知识证明应该可以满足的两个关键属性：

• 完整性：一个诚实的证明者有诚实的声明，能够说服验证者该声明的有效性。
• 健壮性：一个拥有虚假声明的证明者不应该能够说服验证者该声明为真。或者说，这种情况发生的概率应该非常低。

现在，如果我们添加条件，使得证明不泄露关于声明的任何信息，那么我们就有了一个零知识证明。我们将不会正式定义“揭示什么都没有”是什么意思，但如果你想深入研究，有一些资源解释这一想法。

至此，介绍结束。前方有动荡，请保持镇定。

范围证明

如前所述，我们需要决定的是我们想证明什么。例如，在Schnorr协议的情况下，我们希望证明某个值的离散对数的知识。

我们更希望证明的另一个声明是某个值位于一个范围内。这在私人余额的系统中可能很有用，在此情况下，证明某个交易完成后，剩余余额是非负的（正数或零）就显得很重要。在这种情况下，我们只需证明该值位于一个范围内：

这就是Bulletproofs等技术发挥作用的地方。现在……我们到底如何证明这一点呢？

嗯……

切换视角

想象一个以字节（8位）表示的数字v。那么，这个数字的范围只能在0到255（2⁸ - 1）之间。因此，如果我们能够证明以下声明：

存在有效的8位表示v

那么我们就构建了一种知识证明，证明v位于0到255之间。就这样。

147的二进制表示，只需8位即可！

然而，我们必须将这个想法转化为一组数学约束，以表示我们的声明。

首先，让我们用aₗ₀, aₗ₁, aₗ₂, …表示v的位值——其中aₗ₀是最低有效位。这意味着以下等式成立：

为了避免繁琐的表达，令我们引入一些新符号。假设我们的数字v以二进制向量表示，每个组件都是一个位：

另外，让我们定义此：

我们可以为W代入任意值——特别是，代入0或1，新向量aᵣ将分别变为零向量或一向量。

现在，我们可以看到之前的等式变为一个内积的形式：

啊，回忆起线性代数的感觉

这种符号相当简洁，所以在本文中我们将使用类似的表达方式。

如果这个等式成立，说明aₗ正确表示了v，因此v位于预期的范围内。但这次，这并不是完整的故事。

我们缺少一个小细节：aₗ中的值可能并不是零和一！每个数字或向量组件的可能值实际上可以在0到q之间，具体取决于我们使用的有限域。换句话说：每个组件可以是模q下的任意整数。而此等式仍然可能成立。

因此，我们将需要一个额外条件。为此，我们定义：

我们所做的，就是将1从向量中的每个元素中减去。这意味着：

• 如果某个组件aₗᵢ的值为1，那么aᵣᵢ的值将为0
• 如果aₗᵢ的值为0，那么aᵣᵢ的值将循环到q-1（这算是一种下溢）
• 否则，既aₗᵢ也aᵣᵢ将不会为0。

这很重要，因为如果aₗ确实是二进制数字，那么应该会发生这样的情况：

你看到了吗！只要我们的二进制表示正确，aₗ与aᵣ的内积将得出0！

总结一下，我们共有两个条件构成我们的声明（记得，声明是我们想要证明的内容）。

协议

我们的系统已经设定。如果我们知道v和aₗ的值，那么检查其二进制表示是否正确则相对简单——我们只需检查该系统是否成立。

然而，由于我们正在走“零知识”的路线，验证者无法知道这些值。因此，为了说服他们，证明者将不得不进行一些魔法——在本系列的这一点已经没有什么令人惊讶的地方了。

罗恩（Ron）似乎很愉悦

承诺 （ Commitments ）

一切都始于承诺。记住，承诺只能用有效值打开——因此它们绑定证明者于他们想证明的声明。

让我们从对值v的承诺开始。为此，使用Pedersen承诺（Pedersen commitment）。我们将使用一个质数阶数为q的乘法群𝔾（如果你需要复习，请查看关于同构的文章或查看上一篇文章)，使用生成元g、h。

承诺的形式如下：

其次，我们希望对aₗ和aᵣ进行承诺，这也是系统的一部分。由于这些是向量，我们需要一个稍微复杂的承诺。我们将使用生成元gₖ和hₖ，其中k范围从0到n。在这里，n + 1是我们范围内的位数。承诺如下（请掌声四起）：

哇，哇，这个符号很多。让我们停下来仔细审视这个表达。

大Π符号是一个乘积 ，它类似于求和，但不是加法，而是乘法。

为了让表达式不那么令人畏惧，我们使用向量表示法。通过这种方法，我们避免了书写乘积符号，但实际上，这两者表示的内容是相同的。

Pedersen承诺的有趣之处在于，我们可以将多个值 combine成一个承诺，只需一个混淆因子。太棒了!

我们还需要对aₗ和aᵣ的组件进行混淆因子——这将是两个随机采样的向量sₗ和sᵣ，我们用以下形式指定：

这些承诺被发送给验证者，以便证明者被约束于v以及它的二进制表示。

挑战

现在，验证者有了一些承诺，他们可以进行挑战。为此，他们会选择两个随机数y和z，并将其发送给证明者。

证明者现在要做的事情相当复杂和令人困惑，老实说。这正是我在本文中想要表达的一个观点：也许尝试为零知识证明构建一个更一般的框架会是一件有趣的事情。

证明者将计算三个表达式，这些表达式实际上代表了一系列多项式（确切地说是2n + 1个）。我们马上会理解——目前，先坚持定义。这些多项式是：

我知道，这让我第一次看到时有怎样的感觉：

*脑损伤*

这里有很多需要解读的内容。首先，一些符号的澄清：

• 点积（ ◦ ）将被解释为逐分量相乘。如果我们写a ◦ b，那么结果将是一个形式为（ a₀b₀ ，a₁b₁ ，a₂b₂ ，……）的向量。这种表示法用于r(X)表达式。
• 标量积（ • ）用于将向量的每个分量与标量（在本例中是一个整数）相乘。因此，例如，z • a（其中z为标量）将产生形式为（ za₀ ，za₁ ，za₂ ，……）的向量。

特别地，让我们关注最后一个多项式中的独立项t₀。它可以通过如下表达式计算：

注意δ是验证者可以轻松计算的量，这在片刻之后会派上用场。

重要的是，这个项包含了值v，这对于我们最初的声明至关重要。在某种程度上，证明具有“正确”的t₀知识与证明知识v有关。而这正是接下来要做的：提供多项式的正确评估。

因此，验证者承诺剩余的t(X)系数t₁和t₂——随机抽取𝜏₁和𝜏₂作为混淆因子并计算：

这些被发送给验证者。但我们还没有完…

我并没有说这会是简单的事情！

第二个挑战

为了做到这一点，我们需要另一个挑战。如果你思考一下，这很有意义，因为我们已经将协议框架到了这里：我们有一系列多项式，因此现在我们需要对它们进行评估。

因此，验证者采样一个新的挑战x，并将其发送给验证者。随后，验证者继续计算：

为了让证明工作正常，验证者还需要计算：

别太担心这些——它们只是数学得以正常运作所需的工具。它们实际上扮演着复合混淆因子的角色。

最后，这些所有的值（向量l和r、t以及混淆因子）被发送给验证者，验证者终于进入验证步骤。耶！

验证

此时，验证者已从证明者那里收到若干值，包括：

如前所述，验证者希望检查的是多项式的评估是否正确。而这又将说服验证者v位于指定范围内。然而，这两个声明之间的联系并不明显——因此我将试图在接下来给出一些背景信息。

链接多项式

验证者检查的第一个等式是：

如果你有兴趣，理由如下：

这所有意味着什么？如果你仔细观察，你会看到在等式的左右两边，我们有多项式的评估t(X)，以及承诺V中出现的值v。因此，这个等式实际上检查的是值t(x)与原始值v的关联。所以，知识关于t(x)也意味着对v的知识。这正是验证者应该通过这个等式所相信的！总结如下：

这个检查让验证者相信，只要t(x)也正确，v就是正确的

在下一个检查中，我们需要定义这个新向量：

尽管看起来很复杂，但这实际上使接下来的检查变得如鱼得水。验证者首先计算：

然后评估：

这次我不会提供表达式匹配的证明——我认为这将是你感兴趣的时候很好的一项练习，如果你不想听我的话！

无论你选择相信我还是自己检查，事情是这样的：P包含所有aₗ和aᵣ值，而在等式的另一侧，验证的是l(X)和r(X)的评估。因为证明者收到了来自验证者的挑战（x），所以如果多项式被“错误评估”，则匹配等式中的P将是不可行的。总而言之，此检查的结果如下：

这项检查说服验证者，只要l(x)和r(x)都是正确的，v的位表示（a向量）就是正确的

最后，我们需要检查多项式的评估是否匹配。这一检查非常简单：

这个检查确保t(x)——即t “hat”——与期望值相匹配。虽然选择符合这个表达式的t(x)、l(x)和r(x)是简单的，但也极不可能它们同时符合前两个检查。所以，总体上，这个检查达成了：

这个检查说服验证者，多项式的评估是正确的

就这样！完整的证明。小菜一碟，对吧？

不是很好笑

我再说一次，因为在这个阶段的重申可能很重要：这确实相当复杂，且不简单。但好吧，这确实是一种有效的方式！

总结

我知道这并不是轻松的阅读——可能正好相反。不过，要驾驭这个协议的复杂性几乎没有其他途径，这就是他本来的样子！但在最后，我们能够实现我们的目标，并且我们找到了确认某个数字位于给定范围内的方法。

往远处看，我们可以发现我们的声明相对简单。三个简单的方程，我们就解决了。尽管如此，我们仍然需要一些複雑的密码学体操来证明这一点。

这完全没问题，但这也激发了一种渴望：我们能否更一般化？是否存在一个更通用的框架来证明声明？

确实如此。别误解我的意思——Bulletproofs及其他定制的ZKP当然很酷、实用，并且可能比广义实现更具性能。但如果每个声明都需要特定的研究和复杂的实现，那么它可能会成为新应用程序的瓶颈。

在这种精神下，我们将在系列中继续前进——探索某种通用证明框架：SNARKs。但是我们需要先奠定一些基础——这将是下一篇文章的主题！

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