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

(原创编译内容,如需转载请联系本人推特获得授权,所有权利保留)

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

一只猫给一只老鼠做了个迷宫,迷宫有南北两个入口/出口。

猫说:我的小老鼠,我打赌你不能穿越我的迷宫。如果你能,我就给你很多奶酪。如果不能,我就把你吃掉!

老鼠说:但是你是一只狡猾的猫。我怎么知道你的迷宫里有一条路可以穿越迷宫?证明给我看,我就接受你的挑战。

猫说:你太狡猾了!为了证明给你看,我必须给你指出一条穿过迷宫的路。那我们还有什么乐趣呢?

老鼠说:不一定。你可以把我丢在迷宫里的某个随机地点。然后我将随机选择北方或南方的出口,你将随机带我去那里。如果我们重复的次数够多,我就会相信这两个开口之间存在一条路。

猫说:嗯,这样你就还是不知道开口之间的路径,只是一个随机走到它们的集合。你好聪明!那我们就开始吧。

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

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

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

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

这篇文章探讨了关于交互式零知识证明的研究对哲学家在数学和理论计算机科学的认识论方面有什么启发(如果有的话)。尽管这种证明系统最初看起来是 "革命性的",而且是一种非标准的 "证明 "概念,但我将论证它们并没有什么哲学意义。从这项工作中可能得到的对数学认识论的教训--我们的数学证明模型应该包括互动,我们的数学证据理论必须考虑概率证据,我们对数学证明的评价应该只关注其说服力--不是被误导就是老生常谈。虽然交互式证明和数学证明之间的差异表明,有必要为理论计算机科学,或至少是复杂性理论(complexity theory),发展一种不同于我们的数学知识理论的单独的认识论,但随便看看复杂性理论的实际做法就会发现,这样一种独特的认识论可能没有必要。

要点摘抄:

  • 在2001年的时候,已经有学者(Goldreich等)作出大胆的预言,认为这种零知识/交互式的证明,会极大改变人类对于“证明”(这一人类文明最基本概念)的认识。
  • “对于复杂性理论来说,典型的证明系统是 NP证明,它本质上是没有互动和随机性的互动证明。在一个 NP证明系统中,证明者只是隐含的,他们的一个信息必须是可以在多项式时间内确定地验证的。” (Troyso 注:当一个决定性问题的解能在多项式时间内被验证时,则称此问题为NP问题。)
  • Goldreich一定程度上也承认:互动证明甚至不是非正式的数学证明。"定义交互式证明系统的动机并不是要取代数学证明的概念,而是要捕捉其他具有自然意义的证明形式。”在这里Goldreich所想到的更多是在动态社会环境中发现的“日常证明”,比如在法庭上经受住盘问(“证明”被告无罪),或者在政治或科学领域的辩论。尽管我们可以把这些互动交流称为 "证明",但我们并不是在任何数学上的相关意义上使用这个术语。
  • 作者认为交互式证明系统可以在数学证据理论中发挥作用,例如发现反例或完成 “穷举证明”:“计算机已经越来越多地被用于所谓的 "实验数学",特别是在测试和证伪开放的数学问题方面(例如,截至2008年2月,哥德巴赫猜想已经被Oliveira Silva验证为 n⩽11⋅1017)。检查此类猜想的特定实例与解决那些有交互式证明的算术问题并无不同。 尽管验证一般猜想的实例不能证明猜想的真实性,但计算机化的测试还是可以为我们提供猜想成立的证据,或者在某些情况下甚至可以引出一个反例。其次,计算机辅助的蛮力组合列举已经成为离散几何中的一种常见技术。“
  • “交互式证明可能是有缺陷的。如果一个交互式证明系统具有非零的可靠度误差(soundness error),那么一个成功的证明只能以高概率说服验证者相信其主张的真实性,而不是完全确定。[…] 与数学证明不同,数学证明在正确时会为前提和结论之间的牵连提供先验保证。“(Troyso 注:所谓先验就是不依赖于经验而获得的认识,例如在我看到人生中第一次看到圆形的东西之前,我的脑海中可能已经知道圆形是什么样子的)

文献来源:Justin Bledin, "Challenging epistemology: Interactive proofs and zero knowledge", Journal of Applied Logic, Volume 6, Issue 4, December 2008, Pages 490-501.

编译者:Troyso (Tromso) 是香港的一名法律工作者,关注法律和金融领域的Web3创新,本文仅为个人学术观点探讨。本人推特@Troyso_tech,即刻@Troyso。

Subscribe to Troyso
Receive the latest updates directly to your inbox.
Verification
This entry has been permanently stored onchain and signed by its creator.