零知识证明的 5 个难度级别解析

计算机科学家 阿米特·萨海 (Amit Sahai) 是加州大学洛杉矶分校 (UCLA) 萨缪里工程学院的教授，在这部 WIRED 制作的视频中，他从儿童到专家的五个复杂程度解释了零知识证明。该概念通过物理类比进行演示，并以不断增加的技术深度进行讨论，使密码学中最重要的概念之一变得通俗易懂。

本文字稿是 WIRED 发布的原始视频文字稿 (opens in a new tab)的无障碍副本。为了提高可读性，对其进行了轻微的编辑。

简介 (0:00)

Amit Sahai: 大家好，我叫 Amit Sahai，是加州大学洛杉矶分校萨缪里工程学院的计算机科学教授。今天，我受邀以五个不断增加的复杂程度来解释零知识证明。

零知识证明是证明者向验证者确证某个陈述为真的一种方式，并且除了该陈述为真这一事实之外，不透露任何额外信息。零知识证明正被应用于区块链和加密货币中。密码学家对零知识感到兴奋，不仅因为其惊人的数学特性，还因为它在许多不同场景中具有令人难以置信的适用性。

第 1 级：儿童 (0:41)

Amit Sahai: 你最喜欢的科目是什么？

Chelsea: 我觉得是数学。有些小问题实际上可能非常庞大且复杂。它就像一个谜题。

Amit Sahai: 我也因为同样的原因喜欢数学。今天，我要告诉你一个叫做零知识证明的东西。在零知识证明中，有两个人——一个是证明者，一个是验证者。我想向你证明某件事是真的，但奇怪的是，我想向你证明它是真的，却不告诉你任何原因。我记得我第一次听说它时，我的反应是，等等，什么？这怎么可能？

那么你在这张照片里看到了什么？

Chelsea: 很多企鹅。

Amit Sahai: 是的。在所有这些企鹅中隐藏着一只海鹦。你想试着找找看吗？你看到它在哪里了吗？我知道它在哪里，但我不想告诉你。你相信我吗？

Chelsea: 相信。

Amit Sahai: 但是，如果我能向你证明我知道海鹦在哪里，而不向你透露它的具体位置呢？让我演示给你看。我把那张照片放在了这张海报后面。你为什么不通过那个洞看一眼呢？

Chelsea: 我看到海鹦了。

Amit Sahai: 所以当你看着这块板子时，我们不知道照片在哪里，对吧？照片的角是在这里吗？如果是这样，海鹦就会一直在这边。或者照片的角是在这里吗？如果是这样，海鹦就会在另一边。所以这是一个非常简单的零知识证明的例子。我让你相信我知道海鹦在哪里，但你没有了解到任何其他信息。

Chelsea: 你为什么研究零知识证明？

Amit Sahai: 当我第一次了解到它们时，我只是觉得它们太酷了。但事实证明它们也非常有用——不仅仅是为了寻找海鹦。如果你只是输入密码，而黑客侵入了计算机，他们就可以直接获取你的密码。如果相反，我们能以某种方式使用零知识证明来登录呢？你只需能够证明你是 Chelsea，而不向他们透露任何信息。如果你能做到这一点，那将是惊人的，因为即使黑客侵入了计算机，他们也学不到任何东西——因为连计算机都没有学到任何东西。

那么 Chelsea，用你自己的话来说，什么是零知识证明？

Chelsea: 零知识证明是对一个陈述的证明。你不向他们展示原因或内容。你只是向他们展示一小部分，或者只是做某种并非真正魔术的奇怪魔术，他们就会被说服。而且你没有向他们展示原因，或任何类似的东西。

第 2 级：青少年 (3:31)

Amit Sahai: 那么你以前听说过零知识证明这个词吗？

Teen: 没有，没听过。

Amit Sahai: 它是证明者向验证者确证某事为真的一种方式，而不透露任何关于它为何为真的信息，这听起来完全不可思议。我想做的是向你证明我知道这个密码组合，而不向你透露这个组合。你可以做的是写一张小纸条，一个我绝对不知道的秘密。把它折起来，塞进这里。然后，如果我知道密码组合，我就应该能够打开它并告诉你写了什么。

好了。“我的狗叫 Doug。”

Teen: 你弄清楚密码组合是什么了吗？

Amit Sahai: 没有。所以在这次互动中，你没有看到任何你还不知道的信息。然而我让你相信我知道这个密码组合。

Teen: 那么零知识证明的确切目的是什么？它是不是像证明某件事，但不提供足够的信息以免危及你正在证明的任何东西？

Amit Sahai: 人们互不信任。如果我能够向某人证明我正确地完成了某件事，而无需透露我的秘密，那么那个人就会更信任我。

Teen: 这与计算机技术有什么关系？这是一种面对面的互动吗？

Amit Sahai: 假设你想和你认识的人交换消息。你们可能会先聚在一起想出一些密码，对吧？然后用那个密码互相写消息。但是如果你以前从未见过这个人呢？如果你想和我交换秘密消息，而我们以前从未见过面呢？我们怎么可能做到这一点？

Teen: 我不知道。

Amit Sahai: 听起来不可能，对吧？但并非如此。你不会使用物理锁或物理盒子。相反，我们会使用数学来做这些事情。你可以获取一条消息并使用数学对其进行加密。然后我可以向你证明我知道密钥，打开它，并把它发回给你。这样我就可以向你证明我知道这个数学密码箱的数学密钥。

那么根据我们今天的讨论，用你自己的话来说，什么是零知识证明？

Teen: 就像如果你有一个非常重要的秘密，你想让某人知道，但你不想告诉他们一切。你可以使用零知识证明向他们证明那个秘密，但不会泄露全部。

第 3 级：大学生 (6:13)

Amit Sahai: 你在学什么专业？

College Student: 我是南加州大学维特比工程学院计算机科学专业的一年级学生。我对数据、互联网、区块链和加密货币等所有事物都很感兴趣。

Amit Sahai: 你听说过零知识证明吗？

College Student: 只是顺便听说过。

Amit Sahai: 实际上，区块链领域是我们看到零知识证明正在被实施的领域之一——而且我认为这仅仅是个开始。在其核心，零知识证明是两个人之间的互动。我应该能够让你相信某个陈述是真的，但你完全不知道它为什么是真的。

我们将通过一种叫做 NP 完全性 (NP-completeness) 的东西来探讨这个问题。NP 完全问题是一个非常难以解决的问题。但如果你能解决它，你就能解决 NP 类中的任何问题——这包括大量的问题。我们将使用一个 NP 完全问题，通过零知识证明来实际证明各种令人难以置信的陈述。我们要看的具体 NP 完全问题叫做地图三着色 (map three-coloring)。

这里我们有一张包含许多国家的地图，其排列方式使得没有相同颜色的国家共享边界。这就是使这样一张地图被有效着色的原因。事实证明，一张地图是否能以这种方式进行三着色是 NP 完全问题的一个例子。

也许你真正想做的是给出一个零知识证明，证明你至少有 0.3 个比特币，而不透露你账户的地址。事实证明，我可以将该陈述转换为一张国家地图。只有当你至少有 0.2 个比特币时，那张国家地图才是可三着色的。

College Student: 我们如何将这样的东西变成零知识证明？

Amit Sahai: 当然，第一步是我们必须擦除所有的颜色。我在这些信封的每一个里面都放了一种颜色。现在，你怎么知道这是一个有效的着色？你不知道。你必须选择任意两个相邻的国家——你可以随意选择，随机选择。

College Student: 我可以选这两个吗？

Amit Sahai: 这里我们有绿色，而这边我们有蓝色。如你所见，它们是两种不同的颜色。所以你有一点信心，相信我已经成功地正确着色了——但信心没那么大，因为我只向你展示了两个国家。获得更多信心的一种方法是打开更多信封，但这会向你透露信息。我不想那样做。

所以相反，我要请你转过身去。现在，让我们改变一下这些颜色。

你能随机选择两个国家吗，我们将再次揭示两种颜色。

College Student: 我选这个和这个。

Amit Sahai: 你很聪明，检查了你已经选过的同一个国家。但正如你将看到的，现在它不是绿色——它是蓝色。而另一方面，这个是绿色。我上次给你看的颜色与这些新颜色不匹配。但它适用于我现在展示给你的这种着色。所以我们所做的是让你不可能把这些碎片拼凑起来。如果你这样做一千次，而我每次都正确地向你展示不同的颜色，你就会完全被说服。就是这样——这就是整个零知识证明。

College Student: 所以它就像一个概率证明吗？

Amit Sahai: 是的。在实际实现中，我们不会使用信封——你会使用加密。但这就是协议。

College Student: 那么零知识证明的更广泛影响是什么？它们是为了在实施中更实用，还是为了在结构上证明某些东西？

Amit Sahai: 这不是为了让某件事变得更高效。它是为了做我们以前根本不知道如何做的事情。我实际上可以向你证明，在不透露我任何秘密的情况下，我的行为是诚实的。我可以向你证明我正确地签署了某份加密文件，而不透露那份秘密文件是什么。这种改变游戏规则的能力——真正改变我们能做什么的能力——正是零知识所带来的。

College Student: 你认为我们可以在哪里使用零知识证明建立更多信任？

Amit Sahai: 一个很好的例子是选举。如果你能以零知识的方式证明选举是正确进行的——每一张投票都被计算在内，并且总和结果是某个人以特定的总票数获胜——那么你就不必放弃任何人的实际投票。然而每个人都能看到它是正确完成的。

第 4 级：研究生 (11:59)

Amit Sahai: 很高兴你能来这里和你交谈，Eli。你能告诉我一些关于你研究的情况吗？

Eli: 我的研究领域是密码学。具体来说，我正在研究一些多方计算 (multi-party computation) 协议。我现在正在研究的是一个用于计算聚合统计数据的系统，这样像 Google Chrome 或 Tesla 这样的服务提供商就可以收集这些统计数据，而无需了解任何关于个人用户数据的信息。作为用户，我不必让 Firefox 知道我最喜欢的网站是 mylittlepony.com。但他们可以知道每天有多少用户访问 mylittlepony.com。

Amit Sahai: 太棒了。多方计算是我非常关心的领域。显然，零知识证明是关于向另一个人证明事情，而不透露你正在证明的事情的细节。但在我看来，零知识实际上远不止于此。这是一个首要概念，你在多方计算中经常能看到，你想要完成某项任务，除了完成该任务所需的确切信息之外，不透露任何其他信息。

Eli: 对，它允许你证明你的行为是诚实的，而不透露你用来实际表现诚实的任何相关秘密。我们知道针对 NP 完全语言的零知识证明在密码学中扮演着如此巨大的角色。你第一次接触 NP 完全性是什么样的体验？

Amit Sahai: 我第一次接触是在我本科的第一堂算法课上。NP 完全语言是一个惊人的问题，它不仅告诉你关于它自身的信息，而且解决这个问题实际上可以告诉你关于一整类非常有趣的问题的信息。

Eli: 当你第一次开始将证明视为我们互相交谈的互动游戏时，这是否使零知识成为可能？

Amit Sahai: 绝对是。而且随机性可能对证明某事有用的想法——如果我们考虑证明的柏拉图式理想，这似乎又非常违反直觉。那里不存在随机性，也不存在非确定性。

Eli: 这与彻底颠覆证明的整个想法有关。在古老的经典证明中，随机性专门违背了你试图实现的目标，因为你试图让一切变得明显并揭示信息流。但是一旦你彻底颠覆了这一点，你不再试图那样做，突然之间，随机性的所有坏属性都变成了好属性。

Amit Sahai: 完全正确。随机是不可预测的，而这正是我们想要的。我们希望这种不可预测性实际上能隐藏我们想要隐藏的信息。你是如何在参与的项目中使用零知识的？你发现了哪些挑战？

Eli: 通常最困难的部分是准确找出使用它的最佳位置。我写过一些以更理论化的方式使用零知识的论文，但当涉及到应用时，到目前为止我看到的一些最令人兴奋的应用是在区块链领域。

Amit Sahai: 有哪些效率瓶颈？

Eli: 零知识证明最酷的事情之一是它有很多种类——我喜欢称它们为风味。一般来说，当你在应用中使用零知识证明时，主要瓶颈往往在于证明者。

Amit Sahai: 你能把证明者的工作分解成许多并行计算吗？

Eli: 这是一个非常有趣的问题。我认为作为一个领域，我们仍然不知道答案。在过去三四年里，我看到的最酷的事情之一是从理论到应用的转变——看到人们在过去 30 年里想出的所有这些惊人的系统开始变得足够高效，从而得以实现。

Amit Sahai: 毫无疑问。特别是随着云计算的发展——利用云的力量来实现零知识证明将是惊人的。同样在区块链领域，如果你想加快证明的生成速度，如果能以分布式的方式完成，那就太好了。我的一个希望是，多方计算的力量在于将互不信任的人聚集在一起。我们能否利用密码学中的这种力量，用它来帮助解决当今社会中存在的巨大不信任感？

Eli: 我认为这是我如此被多方计算吸引的原因之一。世界上最重要的问题之一是许多人互不信任这一事实。能够使用数学创造出允许人们在不必互相信任的情况下协同工作的技术，是一项非常酷且了不起的使命。

第 5 级：专家 (17:10)

Amit Sahai: 尚华，很高兴再次见到你。我想我们上次见面是在 2017 年左右。

Shang-Hua: 我想我们在疫情期间用 Zoom 开过一次会，但很高兴能见到你本人。实际上，在 86 年，我正在上 Leonard Adleman 教授（RSA 中的 A）的密码学课。他给我布置了 Goldwasser、Micali 和 Charlie Rackoff 关于零知识证明的论文。所以那确实是我在这个国家的第一次演讲——关于零知识。

Amit Sahai: 太棒了。这几乎是一个令人着迷的概念。

Shang-Hua: 如何在数学上阐述这些概念也很有趣。例如，我们有数据。最终从数据中，通过数据挖掘，你可以获得信息。然后你有了“知识”这个词。知识甚至在哲学中也争论了很久。什么是知识？但这里有一种非常迷人的方式，数学家或计算机科学家想要捕捉这种知识。它没有说“零信息证明”。那么你对为什么是“知识”而不是“信息”或“零数据证明”有什么看法？显然那里有数据，所以它不可能是零数据。

Amit Sahai: 绝对是。我认为我们对这个问题仍然没有一个完全令人满意的答案。如此美妙的见解是，零知识是你已经可以预测的东西。如果你已经可以预测答案，那么你一定没有通过那种互动获得任何知识。这种见解——能够准确预测未来，并且这是缺乏新知识的证据——是如此美妙、惊人的见解。

Shang-Hua: 嗯，这里并不是零信息。从根本上说，从计算和安全的角度来看，重要的是你获得了多少知识，而不是你获得了多少信息以及你拥有多少数据。数据并不直接意味着知识。但人们并不总是能区分。

Amit Sahai: 对。例如，在医学研究中——拥有一种药物并证明它在这个模型中有效，而无需透露化合物的结构，那将是多么惊人？

Shang-Hua: 你认为这个领域的下一个方向是什么？

Amit Sahai: 零知识程序这个概念将允许你以零知识的方式执行完全任意的计算，而无需任何交互。我只需获取程序，将其转换为零知识程序——或混淆程序——然后直接发送给你。你可以运行它并获得该计算的好处，而无需再与我交谈。

Shang-Hua: 没错。它具有非交互的性质。但其中包含可验证性。在区块链中，他们也开始在账本中纳入更通用的零知识证明。

Amit Sahai: 我们现在绝对处于零知识将被越来越多地使用的时刻。在零知识领域有如此多的会议和聚会，你和我都没有被邀请——因为那是为开发人员、编程人员准备的，而不是我们这些数学家。我认为这是一个标志。这标志着我们的孩子已经长大了，是时候让它得到发展了。

Shang-Hua: 我认为意义深远的是，学生们经常问我未来的方向是什么——无论是在密码学、零知识证明方面，还是在现实世界和数学计算方面。

Amit Sahai: 这是一个很好的问题。我希望我能看到未来。我不能，但让我试一试。我认为在过去的几十年里，我们在密码学方面做了很多工作，但我们了解的却很少。最基本的方面是理解难度——我们如何获得难题？我们如何实际构建数学上的难题，以便我们随后可以使用它们来构建高效的零知识程序和证明？

Shang-Hua: 我想在量子计算中，你也需要更难的问题。

Amit Sahai: 确实如此。现在量子计算的幽灵正向我们逼近，我们都知道量子计算机可以破解许多密码系统。这是一个深刻的挑战。那么我们能否找到抗量子的新难度来源——甚至连量子计算机也无法破解？这是我过去几年一直在研究的问题。

Shang-Hua: 但我确信它们会激发美妙的数学。

Amit Sahai: 是的，没错。现实世界的一大好处是现实世界中的人们有需求。而这些需求通常听起来是不可能的。这就是我们介入的地方——让不可能成为可能就是我们的工作。