在 2001 年的時候,已經有學者(Goldreich 等)作出大膽的預言,認為這種零知識/交互式的證明,會極大改變人類對於 “證明”(這一人類文明最基本概念)的認識。“然而這種證明又與數學上的證明有什麼區別呢?”

原文:Challenging epistemology: Interactive proofs and zero knowledge

作者: Justin Bledin

編譯:Troyso (Tromso) ,香港法律工作者,關注法律和金融領域的 Web3 創新

封面: Photo by Shubham Dhage on Unsplash

零知識證明是近期 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 注:所謂先驗就是不依賴於經驗而獲得的認識,例如在我看到人生中第一次看到圓形的東西之前,我的腦海中可能已經知道圓形是什麼樣子的)

版權聲明:原創編譯內容,如需轉載請聯繫本人推特獲得授權,所有權利保留

免責聲明:作為區塊鏈信息平台,本站所發布文章僅代表作者及嘉賓個人觀點,與 Web3Caff 立場無關。本文內容僅用於信息分享,均不構成任何投資建議及要約,並請您遵守所在國家或地區的相關法律法規。