零知识证明和科学理论

  旧作如何定量地证伪图灵测试？中提及的证明方（Prover）想要防止向验证方（Verifier）泄密时，可以采用零知识证明这种特殊的证明方式保证验证方只知其然而不知所以然。例如，验证方询问G,H两个图是否不同构的问题时，传统证明方式是证明方直接给验证方完整的解答，但这会让验证方知道他用的特殊算法，从而暴露了比原答案更多的内容。零知识证明则是验证方反复向证明方发送G.H之一的随机重排并询问它来自两图中的哪一个，当G,H同构时这种重排会同时同构于G和H，所以证明方总是有1/2概率答错。验证方通过证明方始终作答无误这点来推断出两图不同构。此过程中证明方回答的都是验证方自己本就知道的信息，因为验证方发的图是自己选的。并且，这个证明是可靠的，因为证明方就算想欺骗验证方两图不同构，G,H同构时他也不可能知道验证方选的是什么。

  所以，零知识证明的可贵之处就在于其保持（高概率意义上的）可靠的同时尽可能地保密了证明方的知识，从而具备相当的商用前景，但看起来却和提倡知识共享的基础科学理论毫不相关，除了形似数学中只证明对象存在而给不出对象的描述的“非构造性证明”以外。奥秘在于零知识证明的具体实现上。

  怎么保证验证方不能从与证明方的互动中推断出更多的内容？那当然要从哪些知识可以被看做验证方“已有”的下手。计算机科学一般将时间不超过问题长度的某个多项式作为“计算可行”的标准，所以验证方能够用多项式时间算出的内容都可以看做“已知”。因此，零知识证明的实现是：

  在目标命题为真的条件下，验证方和证明方交流内容所服从的概率分布，与某个仿真程序用多项式时间生成结果的概率分布不可区分。

  如果将“不可区分”加强为要求“严格相等”，就称为完备零知识证明。前述的例子就是完备零知识证明，验证方自己完全清楚发送的图是由G还是H变来的，所以他当然也可以自己仿真出证明方的回答。

  科学理论成功的标志，莫过于根据该理论计算仿真出的观测结果，和实验观测的真实结果相一致。然而一致的标准是什么呢？在自然界存在随机性时逐点相等是奢望，应该是概率分布不可区分。这正是零知识证明的要求。

  将自然界看做是证明方，而科学研究者看做是验证方，他们的交流互动看做是实验观测，那么成功的理论验证就可看做零知识证明，虽然可能不是完备的，自然产生的概率分布未必总能被准确仿真。这里我们对自然界的性质并没做什么具体的假定，因为零知识证明本来就只对验证方做了算力限制，证明方的算力是不限的，他未必要是某个理智的人或精密的机器。事实上，交互证明的一个常用比喻就是验证方是耐心有限的亚瑟王，而证明方是法力无边的魔法师梅林，任何可解问题都能用魔法正确作答。NP复杂类的量子版本：量子梅林-亚瑟类（QMA）就是这么来的（中文本地化大约可以叫孔明-翼德类？）。

 于是我们得到了一个十分有趣的科学哲学断言：凡是没有对应零知识证明存在的，都不是科学理论。例如，PSPACE（多项式空间）以外的难题就不存在多项式时间内可行的零知识证明，不论证明方怎么样。