零知识证明与交互式证明的认识论问题

零知识证明是近期 Web3 行业非常火的概念，然而，什么是零知识证明（和交互证明）？近期读到一篇 2008 年的论文，Justin Bledin（现在供职于约翰霍普金斯大学）讨论了所谓的交互证明和零知识证明的认识论问题（epistemology），特别是它们可否被归类为一种数学意义上的 “证明”，文章开头作者用一个很有趣的小故事来解释零知识证明：

除了作者的这个小故事之外，其实我们可能用验证码的例子来解释更容易理解：网站会用一些找图片的机制来验证操作人员是真人还是机器人。比如一次成功验证有 90% 的概率可以确定操作者是真人，那么只要连续做足够多次（例如一百次），那就可以在统计学意义上认定操作者是真人。这样用户就不用在暴露个人隐私的情况下（例如开摄像头）向网站证明自己是真人了。因为这个过程存在着证明方（做题人）和验证方（出题人）两方，因此也就被称之为 “交互式证明”。

但是这种证明和数学中的证明是一回事吗？如果是的话，那么我们对于数学体系的原有认知就会需遭到革命性的挑战，因为这种证据从性质上是一种 “概率证据”（即便有 99.999% 的概率是真人，和那个人站在你面前说我是真人之间还是存在区别的）。只不过这种区别在日常生活中可以被近似掉，但是在理论世界中，这两种证明手段会存在认识论基础上的天差地别。因此作者在这篇文章里就讨论了这个问题，他不认为零知识证明会对数学理论带来多么 “革命性的改变”。

这篇论文虽然包含了大量数学哲学、逻辑学、计算机科学（复杂性理论）的论述，但其大意是足够让普通读者理解的：即我们有必要对 “零知识证明” 的性质有清醒的认识，并且将它与传统的数学证明相区分。与 1+1=2 的数学证明不同，零知识证明可能更像是人与人之间的交流，就像在朋友圈里晒豪宅奢侈品——在不告诉其他人自己有多少钱的情况下，向周围人 “证明” 自己有钱的事实。

下面是该文的摘要与一些要点摘抄：

要点摘抄：

• 在 2001 年的时候，已经有学者（Goldreich 等）作出大胆的预言，认为这种零知识/交互式的证明，会极大改变人类对于 “证明”（这一人类文明最基本概念）的认识。

• “对于复杂性理论来说，典型的证明系统是 NP 证明，它本质上是没有互动和随机性的互动证明。在一个 NP 证明系统中，证明者只是隐含的，他们的一个信息必须是可以在多项式时间内确定地验证的。” （Troyso 注：当一个决定性问题的解能在多项式时间内被验证时，则称此问题为 NP 问题。）

• Goldreich 一定程度上也承认：互动证明甚至不是非正式的数学证明。”定义交互式证明系统的动机并不是要取代数学证明的概念，而是要捕捉其他具有自然意义的证明形式。” 在这里 Goldreich 所想到的更多是在动态社会环境中发现的 “日常证明”，比如在法庭上经受住盘问（“证明” 被告无罪)，或者在政治或科学领域的辩论。尽管我们可以把这些互动交流称为 “证明”，但我们并不是在任何数学上的相关意义上使用这个术语。

• 作者认为交互式证明系统可以在数学证据理论中发挥作用，例如发现反例或完成 “穷举证明”：“计算机已经越来越多地被用于所谓的 “实验数学”，特别是在测试和证伪开放的数学问题方面（例如，截至 2008 年 2 月，哥德巴赫猜想已经被 Oliveira Silva 验证为  n⩽11⋅1017）。检查此类猜想的特定实例与解决那些有交互式证明的算术问题并无不同。 尽管验证一般猜想的实例不能证明猜想的真实性，但计算机化的测试还是可以为我们提供猜想成立的证据，或者在某些情况下甚至可以引出一个反例。其次，计算机辅助的蛮力组合列举已经成为离散几何中的一种常见技术。“

• “交互式证明可能是有缺陷的。如果一个交互式证明系统具有非零的可靠度误差（soundness error），那么一个成功的证明只能以高概率说服验证者相信其主张的真实性，而不是完全确定。[…] 与数学证明不同，数学证明在正确时会为前提和结论之间的牵连提供先验保证。“（Troyso 注：所谓先验就是不依赖于经验而获得的认识，例如在我看到人生中第一次看到圆形的东西之前，我的脑海中可能已经知道圆形是什么样子的）