3.2.4　场景四：一个“真实世界中”的案例

某电信业巨头打算部署新一代的5G电信网络。这个网络的结构如图3-7所示。图中的每个顶点代表一个无线电塔，每一条连线（边）代表无线电塔信号两两重叠的区域，这意味着连线上的信号会互相干扰。

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

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

到目前为止，这个难题就是著名的算法问题——三色问题（graph three-coloring）。这个问题有趣的地方在于：某些非常庞大的网络中，我们很难找到解，甚至连证明问题有解都办不到。

如果只是上面给的这种示例图，我们用人工计算就能轻松找出题的解。但是，如果无线通信网路规模特别复杂而庞大，动用企业常规所有能调配的计算资源都无法找到解答的情况下，该怎么处理呢？

假设某个乙方公司动用了大量的算力来寻找有效的着色方法。必然，在电信公司在得到确实有效着色方法之前，并不打算付钱给乙方。同样，对于乙方来说，在电信公司付款之前，也不愿意给出着色方法的真正副本。因此双方就会陷入僵局。

谷歌工程师向在麻省理工学院的米加里（Micali）等人进行了咨询，同时想出了一种非常聪明而优雅，甚至不需要任何计算机的方法来打破上述的僵局。只需要一个大仓库、大量的蜡笔和纸张，以及一堆帽子。

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

谷歌工程师们上色结束后，在离开仓库前，会先用帽子把每张纸上的电塔盖住。所以当电信公司回到仓库的时候，会看到如图3-9所示的界面。

显然的，这种方法保障了谷歌着色方法的秘密性。但是如何证明进行了有效的着色呢？

谷歌工程师们决定给我机会“挑战”他们的着色方案。电信公司被允许——随机选择图上的一条边（两个相邻帽子中间的一条线），然后要求谷歌工程师揭开两边覆盖着的帽子，让我看到他们着色方案中的一小部分，如图3-10所示。

这样做，会产生两种结果：

（1）如果两个点颜色相同（或是根本没有被着色！），则表明谷歌工程师们对我撒谎。

（2）如果两个点颜色不同，那么谷歌工程师可能没有撒谎。

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

那就再一次、重新进行观察！

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

电信公司走进仓库再一次进行“挑战”，选择一条新的、随机的边。上述逻辑再一次适用。如此持续反复n次，那么如果谷歌工程师作弊，他必须连续n次都这么幸运。这当然有可能发生——但发生的可能性相对较低。现在谷歌工程师连续两次都骗到我的概率为[（E-1）/E] * [（E-1）/E]（在1 000条边的情况下，大约有99.8%的可能性，还是很高）。

电信公司被骗的概率总会存在，即使概率很小。但经过大量的迭代后，最终可以将信心提升到一个程度，那时候谷歌工程师只剩下微不足道的概率可能骗到我——这概率低到我可以安全地把钱交给谷歌工程师。

在这个过程中，谷歌工程师同样受到保护。即使电信公司试图在挑战的过程中推敲出正确的着色方案，那也不要紧。因为谷歌工程师在每一次迭代前随机更换三种新的颜色，这让电信公司获得的讯息毫无帮助，每次挑战的结果也无法被串联起来。

1．是什么让它“零知识”的

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

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

怎么办呢？他们潜入Google X研究室，并“借用”谷歌时光机的原型机。最初想将时间倒退几年，这样可以获得更多时间来解决问题。不幸的是，这台原型机有限制——只能倒退四分半钟的时间。

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

因为谷歌工程师们实际上不知道正确的着色方案，只能直接从大量蜡笔中随机选出颜色来涂，然后盖上帽子。如果足够幸运，电信公司在挑战时选中不同颜色点，他们就可以松口气然后继续进行挑战，以此类推。万一某次挑战揭开两顶帽子时，发现两个相同颜色的点！他们就用时光机挽回颓势——让时间倒退四分半钟，然后再以新的完全随机方式着色。接着时间正常前进，挑战将继续进行。

时光机让谷歌工程师可以挽回在欺骗过程中的任何失误，同时让电信公司误以为这个挑战过程完全符合规则。从谷歌工程师的角度来看，造假被发现的情况只有1/3，所以整个挑战时间只会比诚实情况下（即知道有效解答）的挑战时间稍微长一点；从电信公司的角度来看，会认为这是完全公平的挑战，因为电信公司并不知道时光机的存在，所以看到的每一次挑战结果，都会认定这就是真实的！而统计结果也完全一致。（在时光机作弊的情境下，谷歌工程师们绝对不知道正确着色方案。）

2．这到底说明了什么

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

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

从电信公司的角度出发，这两种情况有什么区别？考虑从这两种情况下的统计分布，会发现根本没有区别，两者都表达了相同量级的有效信息。这恰好证明了下面这件非常重要的事情。

假设电信公司（验证者）在正常挑战协议过程中，有办法“提取”关于谷歌正确着色方案的相关信息。那么当电信公司被时光机愚弄的时候，验证者的“提取”策略应该仍然有效。但从验证者的角度来看，协议运行结果在统计学上毫无二致，验证者根本无法区别。因此，如果验证者在“公平的挑战”和“时光机实验”下，所能得到的信息量相同，且谷歌在“时光机实验”中投入的信息量为零，则证明即使在公平的挑战下，也不会透露任何相关信息给验证者知道。

3．抛开帽子和时光机

在现实世界中一般不会想使用帽子来验证协议，谷歌（可能）也没有真正意义上的时光机。

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

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

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

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

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

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

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

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

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

4．我们到底知道了什么

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

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

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

5．证明所有的NP完全问题

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

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

所以我们迄今展示的，是要表达这种证明是“可能的”。我们仍然需要找到更多的实例来支撑零知识证明的可用性，还好，区块链的世界里不乏这样的例子。