Alice 再次把颜色做一次变换，把蓝色改成紫色，改绿色改成棕色，把橙色改成灰色，然后把所有的顶点盖上纸片。然后 Bob 再挑选一条边，比如像上图一样，选择的是一条竖着的边，然后让 Alice 揭开纸片看看，如果这时候 Bob 再次发现这条边两端的顶点颜色不同，那么 Bob 这时候已经有点动摇了，可能 Alice 真的有这个染色答案。可是，两次仍然不够，Bob 还想再多来几遍。

那么经过反复多次重复这三个步骤，可以让 Alice 作弊并能成功骗过 Bob 的概率会以指数级的方式减小。

可是，Bob 每次看到的局部染色情况都是 Alice 变换过后的结果，无论 Bob 看多少次，都不能拼出一个完整的三染色答案出来。实际上，Bob 在这个过程中，虽然获得了很多「信息」，但是却没有获得真正的「知识」。

在地图三染色问题的交互证明中，当重复交互很多次之后，Bob 得到了大量的信息，但是这好比 Alice 发给 Bob 一堆随机数一样，Bob 并没有「知道」更多的东西。打个比方，如果 Alice 告诉 Bob 「1+1=2」，Bob 得到了这个信息，可是 Bob 并没有额外获取更多的「知识」，因为这个事实人人皆知。

假如 Alice 告诉 Bob 2^74,207,281-1这个数是一个质数，很显然这个是「知识」，因为要算出来这个数是不是一个质数，这需要耗费大量的算力。

假如 Alice 告诉 Bob，总共有两个顶点用了绿颜色，那么 Bob 就获得了宝贵的「知识」，因为基于他刚刚获取的这个信息，Bob 可以用更短的时间用一台图灵机去求解三染色问题。假如 Alice 又透露给 Bob，最左边的顶点颜色？是用橙色，那么很显然，这个「信息」对于 Bob 求解问题并没有实质上的帮助。

1. 「知识」与「计算难度」相关，而「信息」不是。
2. 「知识」是与公共所知的东西有关，而「信息」主要与部分公开的东西有关。

引用自Oded, Goldreich. "Foundations of cryptography basic tools." (2001).

综上，实现知识的零知识证明的必要条件是要求验证者提供交互输入。这种交互式输入通常以一个或多个挑战的形式进行，证明者的回答让验证者确信陈述为真时，即说明证明者大概率拥有相关知识。验证者可以记录交互的执行并重播再现，以说服其他人他们拥有机密信息。

哥猜

任一大于2的偶数都可写成两个质数之和。

怎么证明我已经证明了这个原来是猜想现在是被我证明了的证明？

就好比有二扇门通向你家，第一道门在外，第二道门在内。有个大盗说他能打开第一道门的锁，但不想让你知道他是怎么开的。那你就把第二道门的钥匙给他，如果他能打开第二道门进入你家，说明他能打开第一道门。

首先先排除民科那种声称“证明”了哥德巴赫猜想‘在概率意义下是对的’的情况。实际上这只是“证明”了例外偶数是零密度。这个结论华罗庚早在60年前就已真正证明出来。

很简单，让Bob基于哥德巴赫猜想的公钥加密算法给出一个加密信息和公钥，如果Alice在没有私钥的情况下能解密，说明她解决了哥德巴赫猜想。

简单的说，验证者Bob会给Alice出一个其它的题，而能做出这道题的前提条件是已经解决了那个数学难题，否则的话无解，而且这个条件是学术界所公认的，这个题就是所谓的平行问题。不出所料，Alice靠着已经解开数学难题的基础把这个平行问题做出来了，但Bob还是不信，他又出了一道平行问题，你又做出来了，多次较量后，验证者就确信了你已经解决了那个数学难题，虽然他并没有看到具体的解法。

后记

零知识证明并不是数学意义上的证明，因为存在作弊者能够说服验证者的小概率可能(稳健性)。换句话说，零知识证明是概率“证明”，而不是确定性证明。但是，有一些技术可以将误差减小到可以忽略的较小值。另外，零知识证明必须使用某种计算模型，其中最常见的是图灵机模型。

总结

对于哥猜来说，

零知识证明未必是最佳方案。

仅仅是最符合提问者的方案。

2019年11月5日更新

针对大家提问最多的具体的编程方案，恕我直言，不是我的专长，可以读一下同问题下的这个回答。