零知识证明：无需语义泄露地编码数独和 Mario 速通

Václav Rozhoň Uncategorized March 17, 2025

我们发布了关于零知识证明的视频！

令人惊讶的是，制作这个视频花费了很多功夫。用于着色的零知识证明是那种事后看起来非常简单明了的算法之一。 但这只是一种错觉——实际上背后有很多事情在发生。 我们在决定深入到什么程度以及讨论哪些应用方面遇到了困难。 最后，该视频涵盖了各个方面，我希望不同的观众会发现一些能激发他们好奇心的东西。 如果是这样，你一定要查看一些更慢、更深入的资料； 实际上，从 20 分钟的视频中理解零知识证明太难了。 例如，以下关于密码学的书籍是一本经典之作：https://www.wisdom.weizmann.ac.il/~oded/foc.html

以下是未包含在视频中的主题列表。

1. 如何将可满足性问题规约到着色问题？

我们指出，几乎所有问题都可以规约到 3-着色问题。 这与我们关于 NP 完全性的视频密切相关——许多问题都可以表述为“这里有一个检查解决方案的（多项式时间）算法：你能找到一个被它接受的输入吗？” 这样的算法可以表示为一个电路，每个电路都可以被认为是布尔变量上的一组约束——即，可满足性问题。

以下是如何将具体的可满足性问题转换为具有三种颜色的图着色问题。 下图显示了一个可满足性问题，要求我们将二进制变量设置为某些值以使公式满足。 我们假设问题中的每个约束都是几个变量或其否定的析取； 任何可满足性问题都可以转换为这种形式。1 公式下方是等效的图 3-着色问题。

这是对该图的解释：

图各部分的解释：

每个部分——通常称为 gadget——在将可满足性问题转换为着色问题中发挥着特定的作用。

三角形 Gadget：

有一个三角形，其中每个顶点必须用三种颜色之一进行着色。 在第二张图片中，我已经用红色、蓝色和绿色对三角形的节点进行了着色。 这使得谈论着色变得更简单； 我们不必说“这个节点必须与三角形顶部节点具有相同的颜色”，我们可以说“这个节点必须是绿色的”。

变量 Gadget：

我们用两个节点之间的边来表示每个变量。 所有这些节点都连接到绿色节点，这意味着在任何有效的解决方案中，边要么被着色为红-蓝，要么被着色为蓝-红。 这表示该变量是真还是假。

子句 Gadget：

对于像 x_1 OR x_2 OR x_3 这样的子句，我们将其视为“唯一禁止的组合是 x_1 = \text{FALSE},\; x_2 = \text{FALSE},\; x_3 = \text{FALSE}。” 我们的任务是构建一个 gadget 来消除这一个禁止的组合，同时允许所有其他组合。 方法如下：如果 x_1 和 x_2 均为假（表示为边被着色为红-蓝），则标记为 x_1 OR x_2 的节点必须为蓝色。 类似地，标记为 x_1 OR x_2 OR x_3 的节点必须为蓝色。 你可以验证任何其他组合都是可以接受的。

2. 我最喜欢的定理

在视频的最后，我们提到零知识证明解决了“在没有可信机构的情况下可以做什么？”的问题。 通过“可信机构”，我们指的是每个人都信任的诚实且安全地保守秘密的人——比如银行、国家或软件公司。 零知识证明表明，我们可以在没有任何可信机构的情况下完成某些任务。

但零知识证明仅涉及“说服他人我可以做某事”类型的任务。 我们可以更有雄心壮志！ 例如：

事实证明，对于这两个问题——以及所有类似的问题——答案是肯定的，至少在理论上是这样。 在第二种情况下，实现方式是臭名昭著的加密货币。 还有一些区块链协议试图实现安全的私有投票。

所有这一切都有可能的事实得到了我最喜欢的理论计算机科学定理之一的支持，该定理是在零知识证明提出几年后证明的。 这篇论文名为How to play ANY mental game，作者是 Goldreich（写了我开头链接的书），Micali（我在 MIT 时办公室离他很近，但不幸的是从未在那里见过他）和 Wigderson（最近获得了图灵奖，他在密码学方面的工作，例如这篇论文，被引为原因之一）。

他们的定理使用了拜占庭将军问题的设置（我们在之前的视频中介绍了这个问题）。 在这个问题中，一组将军想要协调——在我们的基本情况下，每个将军都从 1 位信息开始，他们希望就一个共同的位达成一致。 然而，该定理的设置更通用——每个将军都从一些信息 x_i 开始，他们一起想要模拟一个算法 A，该算法接受输入 x_1, x_2, \ldots, x_n 并输出一些结果 y。 例如，如果 A 是一个计票算法，则每个 x_i 代表编号为 i 的将军投票给谁，而 y 是当选的候选人。 我们想要对算法 A 进行分布式模拟，以便：

例如，如果将军中有一个受信任的机构——比如，一位普遍信任的女王——我们可以让每个将军将 x_i 发送给她，让她模拟 A，然后宣布 y。 但是 Goldreich、Micali 和 Wigderson 的定理表明，在没有任何可信机构的情况下，也可以对任何算法 A 完成同样的事情。

毫不奇怪，零知识证明是该证明的关键组成部分。 粗略的想法是将 A 的模拟分配给将军们，以便每个人都在没有其他人上下文的情况下对没有意义的数据进行计算。 例如，可能会要求将军“从 8 号和 42 号将军那里接收两个数字，将它们加起来，然后将结果发送给 4 号将军。” 使用承诺方案和零知识证明，将军可以使其他人确信他正确地执行了此计算，而无需透露实际数字。 这样，我们可以保持所有将军在模拟 A 中的协调，而每个人只做整个计算的一小部分，并且无法真正说出全局发生了什么。

在实践中，简单地遵循这个定理来实现加密货币将非常低效。 尽管如此，该定理是一个强大的理论结果，表明许多任务可以在没有可信机构的情况下完成。 此外，零知识证明被用于区块链实践中。 例如，你可以使用它们来实现私有交易。 ——在典型的区块链上，所有交易都是公开的，但是通过零知识证明，你可以证明你有足够的资金来进行交易，而无需透露你的余额。 还有一些方法可以使用零知识证明通过验证链下（off-chain）的某些要求来加速区块链（就我所知，人们实际上对这第二个应用程序更感兴趣）。

非交互式证明

我们的零知识证明是交互式的——证明者和验证者之间的来回对话。 这种方法在实践中并不理想； 例如，如果你想向很多人证明同一件事怎么办？ 如果证明者可以简单地发布每个人都可以验证的文档，那就更好了。 这被称为非交互式证明，也是我们通常认为的证明方式。

我认为一个不为人所知的事实是，我们协议的交互性不是固有的，并且可以很容易地消除。 方法如下：

首先，想象一下存在所谓的信标——每个人都可以观察到的公共随机源。 例如，你可能会想象一颗遥远的恒星发出光，我们在地球上测量这种光，并且我们都同意如何将信号强度中的微小波动转换为随机比特流。

在这种情况下，我们可以按如下方式“实现”验证者：我们选择信标在某个时间 t 发出的随机比特，并使用这些比特来模拟验证者发出的随机挑战。 最后，我们的证明是证明者和验证者之间对话的记录，以及时间 t。 任何验证者都可以检查该记录是否有效，以及验证者是否使用了信标在时间 t 发出的随机比特。

就是这样——一个非交互式证明。 存在一些细微的问题，例如我们可能试图通过使用某个特定时间 t 来作弊，因为该时间的随机比特流具有一些有用的属性。 但是，在我们协议中针对特定时间 t 成功作弊的概率非常低，我们可以将其降低到即使考虑到所有可能的 t 时，我们作弊的总体机会仍然可以忽略不计。

在实践中，你甚至不需要信标。 相反，如果该协议有 n 轮，你首先要对你的图 n 进行多次提交，并记录所有提交以形成一个字符串 s。 然后，你通过加密哈希函数传递 s 以生成一个“随机”字符串 r，你使用该字符串来模拟验证者。 尽管 r 中的比特不是真正的随机的，但它们是不可预测的，因为加密哈希函数是单向的，因此这几乎等同于使用真正的随机信标。 字符串 r 中比特的正确术语是它们是伪随机的——这是我们最近的视频中的另一个主题。 在制作此视频时，我真的觉得我们最近涵盖的所有主题都汇集在一起了。 🙂

  1. 我们甚至可以假设每个析取都有三个变量——所谓的 3SAT 形式——但是每个析取的变量数量并不重要 ↩︎