零知识证明: 抛砖引玉

当今密码学世界中最酷炫的一件事，莫过于那些优美又神秘的专有名词。我们可以自由的以这些术语给朋克乐队或 Tumbirs 博客起名字，像是“硬核谓词(hard-core predicate)”、“陷门函数(trapdoor function)”，或“不可差分密码分析(impossible differential cryptanalysis)”等热词都受到追捧。 当然，我今天要提到的这个术语热度绝不亚于前面三者，它就是“零知识(zero knowledge)”。

事实上太过受欢迎也不一定是件好事，因为”零知识“概念如此吸引眼球，也导致许多理解错误和误用。许多人将零知识和“非常非常安全”划上等号，并将它与加密系统或匿名网络挂钩——但这是不正确的，这与真正的零知识协议毫无关系。

这一切都说明 “零知识证明” 是密码学家所设计出来最强大的工具之一，同时理解的人也相对较少。接下来，我将试着（尽可能）以 非数学 领域的表述方式，介绍什么是“零知识证明”，并解释到底是什么使得它如此特别。同时在此篇和下篇文章中，我们会谈及一些常用的零知识证明协议。

零知识起源

“零知识”的概念最早在80年代由麻省理工学院的研究人员 Shafi Goldwasser，Silvio Micali 和 Charles Rackoff 所提出。当时这些人正在研究与交互证明系统相关的问题——即一种理论系统，使得甲方（证明者）可以和乙方（验证者）交换信息，并借此说服乙方接受（通过验证）某个数学论述为真 [作者注1]。

在Goldwasser等人之前，这个领域的研究工作主要聚焦在加强证明系统的可靠性（Soundness）。也就是说原先大家都假设，会有恶意的证明者试图耍手段，误导验证者接受错误的论述。但 Goldwasser 等人却从另一个角度思考了这个问题：如果我们压根就不相信 验证者，该怎么办？

更具体的来说，他们更关心信息泄露的问题。他们抛出了这样的思考：“在验证者的验证过程中，究竟会获取多少单纯验证论述真假无需知道的额外信息。”

这里要强调一下，这个问题不是单纯的理论思考，而是在真实、具体的应用中，会面到临的问题。

我们举个例子，假设今天在真实世界有个客户端想要使用密码登录web服务器，在“真实世界”的标准操作流程中，包含将密码以哈希形式储存在客户端。我们可以将”登录“这个动作视作某种证明——也就是我们要能够提供一串输入，这串输入经过哈希运算后的值与密码的哈希相同（因为哈希运算的单向性，这串输入只能是我们的密码）。但这有个问题是：客户端实际上 知道 我们的密码。

大多数系统以这种绝对最糟糕的方式进行“证明”——客户端直接将原始密码发送给服务器，服务器重新计算密码哈希并将其与存储值进行比较。这里的问题很明显：在协议结束时，服务器已经取得我们的明文密码。 因此，保障现代密码安全很大程度上要祈祷服务器不会遭受攻击。

Goldwasser，Micali 和 Rackoff 等人提出了一种全新的方法来完成“证明”。如果零知识证明真的可行，它将允许我们在证明某些数学陈述为真的同时，保证 不会有任何不相关的信息 被透露出去。

一个“真实世界中”的案例

目前为止，我们的讨论还比较抽象。为了让大家能有更具体的概念，现在我们举个“真正的”（脑洞微开的）零知识证明例子。

请大家配合我想象一下，现在我是个电信业巨头，并且打算部署一个新的蜂窝电信网络。这个网络架构图如下（图一）。图中的每个顶点代表一个无线电塔，每一条连线（边）代表无线电塔信号 两两重叠 的区域，这意味着连线上的信号会互相干扰。

这种重叠的情况是有问题的，这表示来自相邻电塔的信号会互相混淆。幸好在设计之初我预见这个问题，现在通信网络允许传递三种波段的信号，这样就避免了临近电塔信号干涉的问题。

不过现在我们有了新的挑战！这个挑战来自我该如何部署不同的波段，使得相邻的每两个电塔不具有相同波段。我们现在用不同颜色来表示不同波段，可以很快找到一种解决方案如下图二所示：

当然，很多人可能已经发现我刚才是在讲述著名的算法问题——三色问题(graph three-coloring)。大家也就知道，这个问题有趣的地方在：某些非常庞大的网路中，我们很难找到解，甚至连证明问题 有解 都办不到。事实上三色问题——特别是指这种给定图形是否有解的决策问题，已经被归类为NP完全问题。

如果只是上面给的这种示例图，我们用手就能轻松找出解。但如果今天我的无线通信网路规模特别复杂而庞大，我以我所能调配的计算资源都无法找到解答的情况下，我该怎么办？我还可以把这个问题 外包 给拥有更庞大算力的人呀！比如我会去找我在谷歌的朋友帮忙。

但这又会导致另一个问题。

假设谷歌动用了大量的算力来帮我找寻有效的着色方法。当然，在我确实得到有效着色方法之前，我是不打算付钱给谷歌的。同样对谷歌来说，在我付款之前，谷歌也不愿意给我着色方法的副本。因此我俩就会陷入僵局。

在现实生活中，可能有点常识都能解决这个困境，但这涉及律师和账户托管。不过今天这篇博客不是表述现实生活，而是关于密码学的。如果你曾经看过任何加密相关文章，你可能知道，解决这种困境的正确方法，就是 想出一个绝对疯狂的技术手段 ！

一种疯狂的技术手段（用帽子！）

谷歌的工程师向Micali 等人在麻省理工进行了咨询。他们想出了一种非常聪明而优雅，甚至不需要任何计算机的方法来打破上述的僵局。我们只需要一个大仓库、大量的蜡笔和纸张。噢，对了，我们还需要一堆的帽子！[作者注2]

下面是运作原理。

首先，我先进入仓库，在地板上铺满纸张，并在空白的纸上画出电塔图。接下来我离开仓库，换谷歌工程师进入仓库。谷歌工程师先从一大堆的蜡笔中，随机选定三个颜色（与上面的例子一样，我们假设随机选中红色/蓝色/紫色），并在纸上照着他们的解决方案上色。请注意，用哪种颜色上色并不重要，只要上色的方案是有效的就行！

谷歌工程师们上色结束后，在离开仓库前，他们会先用帽子把每个纸上的电塔盖住。所以当我回到仓库的时候，我会看到如下图三：

显然的，这种方法保障了谷歌着色方法的秘密性。但这样对我一点帮助都没有！我不知道他们是不是进行了有效着色，或是他们根本没有着色？

为了消除我的疑虑，谷歌工程师们决定给我机会“挑战”他们的着色方案。我被允许——随机选择图上的一条边（两个相邻帽子中间的一条线），然后要求谷歌工程师揭开两边覆盖着的帽子，让我看到他们着色方案中的一小部分，如图四：

产生两种结果：

1. 如果两个点颜色相同（或是根本没有被着色！），我就可以确信谷歌工程师们对我撒谎。因此我也很清楚我不需要付钱。
2. 如果两个点颜色不同，那么谷歌工程师 可能没有 撒谎。

第一种情况很单纯（我不付钱！），第二种情况下我要进行更多考虑。即使我刚才进行了一轮观察，毕竟我只揭开两顶帽子，只看到两个点，仍然不能保证谷歌工程师给我的方法是有效的。假如图上有 E 条不同边，在目前条件下谷歌仍有很大的可能是给了我一个无效的着色方案。实际上，在经过一次揭帽观察后，我仍有高达 (E-1)/E 的概率会被骗（假如有1000条边，有99.9%的概率这个方案无效。）

好在谷歌决定让我们再一次、重新进行观察！

我再次走出仓库，他们重新铺上新的纸张，并把空白的电塔图画上。谷歌工程师再次从大量蜡笔中随机选出三种颜色进行着色。他们再次完成有效着色方案，但使用新的三种随机颜色。

接着帽子又被盖上啦。我走进仓库再一次进行“挑战”，选择一条新的、随机的边。上述逻辑再一次适用。不过这次情况稍好，我会对谷歌工程师们多了那么一点点信心，相信他们没有对我撒谎。因为如果他们要欺骗我，他们必须连续两次都这么幸运。这当然有可能发生——但发生的可能性相对较低。现在谷歌连续两次都骗到我的概率为 [(E-1)/E] * [(E-1)/E]（在1000条边的情况下，大约有99.8%的可能性，还是很高）。

不过不用担心，我们不只可以进行两次挑战。事实上，我们可以不断的重复上述的挑战，直到我们相信谷歌给出了有效的着色方案。

切记不要盲目信我的话。感谢 Javascript，你可以通过简单的代码自己验证上面的逻辑。提醒下，我永远无法完全相信谷歌工程师是诚实的——我被骗的概率总会存在，即使概率很小。但经过大量的迭代后（E^2），我最终可以将信心提升到一个程度，那时候谷歌只剩下微不足道的概率可能骗到我——这概率低到我可以安全地把钱交给谷歌。

而且你需要知道的是，在这个过程中谷歌同样受到保护。即使我试图在挑战的过程中推敲出他们正确的着色方案，那也不要紧。因为谷歌在每一次迭代前随机更换三种新的颜色，这让我的小手段失效了。我获得的讯息对我毫无帮助，每次挑战的结果也无法被串联起来。

是什么让它“零知识”?

我对你声称，这种挑战不会泄露任何关于谷歌着色方案的信息，但请你们不要这么轻易放过我！现代密码学第一条守则就是：永远不要在未经证明的情况下相信一个人的宣称。

Goldwasser, Micali 和 Rackoff提出三个零知识证明的特性，任何零知识都必须满足。简单来说：

1. 完整性(Completeness)。如果谷歌说的真话，那么他们最终能说服我（至少让我相信可能性非常高）。
2. 安全性(Soundness)。只有当他们说的是真话时，谷歌才有可能说服我。
3. 零知识性(Zero-knowledgeness)（没错，就这么叫）。我无法从中习得任何关于谷歌解决方案的信息。

我们已经讨论了完整性的论点。只要重复足够多次挑战，这个协议最终能够说服我（伴随极低的失误可能）；安全性也很容易说明，因为如果谷歌试图欺骗我，会有很大的概率会被我发现。

最难说明的就是“零知识性”。为此，我们必须进行一项非常奇怪的思想试验。

思想试验（时光机？）

我们要从一个疯狂的假设开始。假如谷歌工程师并没有大家想象中厉害，他们花了数周时间，仍然没有想出着色问题的解决办法。而现在只剩下12小时他们就得展示了！他们已经感受到了绝望。绝望使人疯狂，他们决定 诱导 我相信他们已经完成有效的着色，实际上他们并没有完成。

他们的想法是潜入 GoogleX 研究室，并“借用”谷歌的时光机的原型机。最初他们想将时间倒退几年，主要可以获得更多时间来解决着色问题。不幸的是，与大多数谷歌原型机一样，这个时光机也有限制——它只能倒退 四分半钟 的时间。

虽然使用时光机获得更多工作时间的想法已经不可行，但这有限的功能已经足够欺骗我。

-我不知道这里到底发生了什么，但看起来好厉害的样子-

这个计划要命的简单！因为谷歌工程师们 实际上不知道 正确的着色方案，他们只能直接从大量蜡笔中随机选出颜色来涂，然后盖上帽子。如果他们足够幸运，我在挑战时选中不同颜色点，他们就可以松口气，然后继续进行挑战，以此类推。

然而不可避免的，我总会在某次挑战时揭开两顶帽子，然后发现两个相同 颜色的点！如果按照正常挑战规则，谷歌工程师们就原地崩溃了，而这也是时光机派上用场的时候。任何时候谷歌工程师们发现自己身处尴尬的情况（被我找到同色点），他们可以轻松挽回颓势。只要其中一个工程师按下时光机按钮，让时间倒退大约四分钟，然后他们再以新的完全随机方式着色。接着时间正常前进，挑战将继续进行。

实际上，时光机让谷歌工程师可以挽回在欺骗过程中的任何失误，同时让我误以为这个挑战过程完全符合规则。从谷歌工程师的角度来看，造假被挑战出来的情况只有1/3，所以整个挑战时间只会比诚实情况下（他们有有效解答）的挑战时间稍微长一点；从我的角度来看，我只会认为这是完全公平的挑战，因为我不知道时光机的存在。

最后一点，也是最重要的一点。在我的眼中，因为我压根不知道有时光机存在，所以我看到的每一次挑战结果，我都会认定这就是真实的！而统计结果也完全一致。值得再呼吁一次，在时光机作弊的情境下，谷歌工程师们绝对不知道正确着色方案。

我到底想说什么？

请注意，我们刚才举得是一个计算机仿真 的例子。在现实世界中，时间当然不能倒退，也没有人能用时光机器骗我，所以基于帽子的挑战协议是合理且可靠的。这表示在 E^2 轮挑战后，我应该相信盖着的图是被正确着色的，同时谷歌工程师们也遵守协议规则。

方才我们展示的是，如果时间不只能够前进——特别的是谷歌能“倒退”我的时间，那即使他们没有正确的着色方案，他们仍然能使挑战正常进行。

从我的角度出发，这两种情况有什么区别？当我们考虑从这两种情况下的统计分布，会发现根本没有区别，两者都表达了相同量级的有效信息。

信不信，这恰好证明了一件非常重要的事情！

具体来讲，假设我（验证者）在正常挑战协议过程中，有办法“提取”关于谷歌正确着色方案相关信息。那么当我被时光机糊弄的时候，我的“提取”策略应该仍然有效。但从我的角度来看，协议运行结果在统计学上毫无二致，我根本无法区别。

因此如果我在“公平的挑战”和“时光机实验”下，所能得到的信息量相同；且谷歌在“时光机实验”中投入的信息量为零，则证明即使在公平的挑战下，也不会透露任何相关信息给验证者知道。

又或是这恰好说明计算机科学家有时光机？？是的，我们有。（请务必保密......）

抛开帽子（也抛开时光机）

当然在现实世界我们不会想用帽子来进行协议，谷歌（可能）也没有真正意义上的时光机。

为了将整件事情串起来，我们先把这个协议放到数字世界。这需要我们构建一个相当于“帽子”功能的等价物——它既能隐藏数字价值，又能同时“绑定”（或“承诺”）创建者，这使得事实被公布后他也不能不认账。

幸运的是，我们恰好有这种完美的工具。这就是所谓数字承诺方案。这个方案允许一方在保密的情况下“承诺”给出的信息，然后再“公开”承诺的信息。这种承诺可以有很多结构组成，包含（强）加密哈希函数。[作者注3]

我们现在有了承诺方案，也就有一切电子化运行零知识证明的要素。首先证明者(Prover)可以将每个点以数字信息形式”着色“（例如以数字0,1,2），然后为每个数字信息生成数字承诺。这些数字承诺会发送给验证者(Verifier)，当验证者进行挑战的时候，证明者只需要展示对应的两个点的承诺值就行。

所以我们已经设法消除帽子了。但如何证明这个过程是零知识的？

我们现在身处数字世界，不再需要一台时光机证明与此相关的事。其中的关键在于数字世界中，零知识证明协议不是在两个人 之间运行的，而是在两方不同的计算机程序 上运行的（或是更规范地说，是概率图灵机）。

我们现在可以证明下面的定理：如果你能做出一套程序，使得验证者（计算机）能够在挑战过程中”提取“额外的有用信息，则我们就有办法在程序中加入“时光机”的功能，使得它能够在证明者没有投入任何信息的情况下（译者注：即谷歌工程师没有正确解），从“假”的挑战过程获得等量的额外信息。

因为我们现在讨论的是计算机程序，回退、回滚等倒退时间的操作根本不是难事。实际上，我们在日常使用上就不断在回滚程序。比如带有快照功能的虚拟机软件。

-通过虚拟机快照进行回滚的例子示意图。一台初始虚拟机继续执行，回滚到一个初始的快照中，然后分叉到另一条新路径中执行-

即使你没有复杂的虚拟机软件，任何计算机程序也都可以回滚到先前状态。我们只需要重新启动程序，并提供完全相同的输入即可。只要输入的所有参数（包含随机数）都是相同的，程序将永远按照相同的执行路径操作。这意味着我们可以从头开始运行程序，并在需要的时间点进行“分叉(forking)”。

最终我们得到以下定理。如果存在任何的验证者计算机(Verifier)程序，它可以通过与证明者的协议交互过程中提取信息，那么证明者计算机(Prover)同样可以通过程序回滚来”欺骗“验证者——即证明者无法通过挑战，却以回滚的方式作弊。我们已经在上面给出了相同的逻辑：如果验证者程序能从真实的协议中提取信息，那么它也应该能从模拟的、会回滚的协议中获取等量的信息。又因为模拟的协议根本没有放入有效信息，因此没有可提取的信息。所以验证者计算机能提取的信息一定始终为零。

这，到底在说什么？

让我们回顾一下。根据我们上面的分析，可以知道这个协议是完整且可靠的。该可靠性的论点在我们知道没有人玩弄时间的前提下都是站得住脚的。也就是说，只要验证者计算机正常运行，并且保证没有人在进行回滚作弊的话，协议是完整且可靠的。

同时我们也证明这种协议是零知识的。我们已经证明了任何能成功提取信息的验证者程序，也一定能从回滚的协议运行中提取信息，而后者是没有信息放入的。这明显自相矛盾，间接论证该协议在任何情况下都不会泄露信息。

这一切有个重要的好处。比如在谷歌工程师向我证明他们有正确的着色方案后，我也无法将这个证明过程转传给其他人用以证明同样的事（如，法官），这使得伪造协议证明变成了不可能的事。因为法官也不能保证我们的视频是真是假，不能保证我们没有使用时光机不断回滚修改 证明。所以零知识证明只有在我们自己参与的情况下才有意义，同时我们可以确定这是实时发生的。

证明所有的NP问题！

如果你能坚持看到这儿，我敢打包票你已经准备好迎接一个大新闻！就是我们讲了半天的三色电信网络网络，其实并不有趣——至少，本身不咋地。

真正有意思的地方在于，三色问题属于NP完全问题。简单来说，这件事的奇妙之处在于任何其他的NP问题都可以转化为这个问题的实例。在一次不经意的尝试下，Goldreich, Micali 和 Wigderson 发现“有效的”零知识证明大量存在于这类问题的表述中。其中许多问题比分配蜂窝网格问题有趣得多。你只需要在NP问题中找到想要证明的论述，比如上面的哈希函数示例，然后转化为三色问题。然后再进行数字版的帽子协议就行啦！

总结

当然，单纯为了兴趣来运行这项协议，对任何人来说都是疯狂而近乎愚蠢的——因为这样做的成本包含原始状态和证人的规模大小、转化为图形的花费，以及理论上我们必须运行E^2 次才能说服某人这是有效的。

理论上说这个协议是“高效率的”，因为证明的总成本会是输入状态的多项式，但其实不然。

所以我们迄今展示的，是要表达这种证明是“可能的”。接下来我们仍然需要找到更多的实例来支撑零知识证明的可用性。

在下一章节，我们会特别谈及一些被实际用于各种有效论述证明的方法。我们也会举出一些真实场景中的例子。另外，因应读者要求，我也会聊聊为什么我不是很喜欢SRP（安全远程密码协议）。

注解：

作者注1：形式上，交互证明系统的目标是要说服验证者，使得验证者相信某特定字符串属于某种语言。在该系统中，通常证明者的权利非常大（无限的），而验证者的计算能力是有限的。

作者注2：本文中举的例子基于Goldwasser, Micali和Rackoff的原始解决方案，而帽子方法则是基于Silvio Micali的解释。我个人只供献了一些愚蠢的失误。

作者注3：我们可以通过哈希函数来构造一个数字承诺的例子。为了承诺一个值“x”，我们需要生成一段（长度适合）的随机字符串，这段随机字符又叫做“盐”。然后输出数字承诺*C = Hash(salt || x)*。必须公开“x”和“盐”，才能通过承诺验证。任何人都可以通过重新计算哈希来检查承诺是否有效。这对于函数本身的某些（适当强度）假设是安全的。

原文链接: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
作者: Matthew Green
翻译&校对: IAN LIU & Elisa

本文由作者授权 EthFans 翻译及再出版。

你可能还会喜欢：

干货 | 公有链的基本挑战: Part 1
Zcash对以太坊来说意味着什么？
干货 | zkSNARKs（零知识证明）简述