一覺醒來，忽然發現零知識證明這一小眾專業和阿里巴巴的故事儼然成了大眾話題。昨日發呆，在微信上寫了人生的第一個科普，後來發現了一些typos，決定在這裡重寫一個稍微豐滿的版本。感謝一些好友的提醒和提供的例子。

構成一個傳統數學定理證明的精髓有兩點：

能夠高效地、機械式（無需任何創造性）地對證明進行驗證；

對於一個錯誤的斷言無法找到一個能夠透過驗證的證明。

這兩點本質上都只與驗證有關：它只強調普通的時間有限的驗證者能進行驗證而不會被惡意的證明所欺騙。通常我們並不關心一個證明是怎麼找到的，有些時候尋找一個定理的證明需要漫長的時間和極高的創造力，這也解釋了為什麼我們會有菲爾茲獎，沃爾夫獎。。。。

傳統的證明是非互動的，我們可以把它寫在紙上供驗證者在無需證明者在場的情況下進行驗證。1985年Goldwasser，Micali和Rackoff透過給傳統的數學證明引入隨機性和互動，即以問答方式進行證明，由此產生的互動證明系統，這給後來整個計算機科學和密碼學的發展帶來了（遠遠超出概念提出者所預料的）深遠的影響。

現在回過頭去看，如果把目光放寬一點，你會發現互動證明已經在人類歷史上出現很久了，比如法庭上控方律師對被告的詰問，可以看成是被告對自己無罪所作的的一個互動證明。這裡互動和隨機性的作用體現的淋漓盡致：試想如果被告能在開庭前一天獲得控方律師所有的提問，那麼他很可能能夠編造一個完美的故事騙過對方；如果控方律師所有的提問都是未知的，那麼他能騙過對方的機率應該不大，畢竟在短時間內一個謊言接著一個謊言地編下去還能使對方信服，這對智商要求太高。

但這絲毫不影響互動證明這一概念的（在當時的）前衛性和革命性。我想強調的是，在科學上，一個好的定義本身的意義並不亞於一個好的結果的意義。 互動性證明的革命性本質上體現在下面兩個方面（均是傳統數學證明無法實現的）：

第一個方面是它能實現零知識性，允許你安全地向他人進行證明。互動的訊息能構成一個證明（仍然體現了傳統證明的精髓）而它們本身不洩漏“斷言為真”之外的任何知識。這裡的“知識”可以理解為“計算能力”，證明是“零知識的”意味著整個證明過程沒有增加驗證者的計算能力（即驗證者之前無法解決的問題在證明完成之後仍然無法解決）。這個性質保證了互動完成後驗證者只知道被證明的斷言為真，但他並不知道怎麼轉而向其他人證明這一斷言，它的代價是會產生一些微小的錯誤。

這裡一個比較精確一點的例子就是向紅綠色盲來證明兩個球著色不同（一個紅一個 綠，見這裡）：視覺正常的證明者持有的傳統證明/證據是眼裡看到的不同顏色，他先將兩個球分別放在色盲的兩隻手中，記住左右手中的顏色；色盲將手放背後，腦子裡隨機決定是否在背後交換手中的球，然後將雙手握球展示給證明者並問他自己是否剛才在背後交換了手中的球，證明者透過對比之前色盲兩手中球的顏色來回答他的問題。這一互動證明體現了上述傳統證明系統的兩點精髓，對於第二點， 這裡帶來了1/2的錯誤機率，即對於錯誤的斷言（即兩個球顏色相同），證明者仍能以1/2的機率騙過驗證者，不過這可以重複多次來降低這一機率。零知識在這裡顯而易見：色盲在互動結束後除了相信他手中球是顏色不同的之外並沒有得到任何額外的知識。

還有一些其他的例子，如證明兩種白酒味道不同，可口可樂和百事可樂的味道不同（見這裡） ， 但這兩個例子一般用來說明互動的威力，而非零知識性。

零知識證明一個顯然的密碼學應用就是身份認證。如你可以隨機挑選兩個素數

和

，計算

，公佈你的身份

，需要進行身份認證時，你持有私鑰

和

”向驗證方證明“我知道

的兩個素因子”。在“分解整數是困難的”假設下，這構成了一個身份認證系統：驗證方在證明完成後沒有得到任何有關兩個素因子的知識。（對整數分解的零知識證明詳細的描述比較複雜，有興趣的讀者參見這裡） 。

GMR透過引入模擬正規化精確定義了零知識性。這一模擬正規化對密碼學影響深遠，它為密碼學從藝術到科學的轉變奠定了基礎。

第二個方面是它能夠產生不可思議的可極端高效驗證的證明，允許證明者來證明在傳統證明系統下幾乎無法（即使給定證明）驗證的斷言，比如斷言B：“斷言A不存在 長度小於

個字元（為方便，假設為2進位制字元）的傳統數學證明”。

注意到斷言B本身的傳統證明有可能是所有可能的長度為

位元的字串，它的長度約為

位元，即驗證者驗證斷言B很可能需要檢查幾乎所有長度為10000位元的字串， 並逐一否定其構成斷言A的證明才能確定斷言B的正確性，這顯然不會“高效”，即使給定斷言B的傳統數學證明，你也無法在有限的一生中驗證完畢。

（當然不是所有的這種型別的數學斷言都需要這麼長的證明，對於某些斷言A我們容易證明它是錯誤的（因此不存在任何長度的證明），但注意到所有有著多項式長度證明的數學定理構成一個NP完全集合，上述型別的斷言在某種意義上組成一個Co-NP的集合，在合理的假設下總會有一些這型別斷言會有很長很長的傳統證明。）

然而，互動證明能夠讓驗證者在遠遠遠遠小於

時間（機器執行步數）-比如5分鐘-內高效驗證斷言B的正確性。一個經典的例子就是如何在短時間內向他人證明斷言C：“這兩個

頂點的圖

是不同構的”。這個斷言的傳統數學證明會很長（你可以認為就是由幾乎所有

個點到

個點上的置換對映組成，驗證者逐一驗證每一個置換對映都不構成這倆圖的同構後確認這兩圖不同構。這雖然不正確， 但不影響我們的討論。參見圖同構的準多項式時間演算法），你無法在有限的時間內驗證完畢。如果假定存在一個無所不能的超級計算機

他能在瞬間判斷兩個圖是否同構，則你可以透過互動在

（它扮演證明者的角色）的協助下驗證斷言C的正確性：你隨機選擇一個位元

和一個同構對映

並計算一個新的圖

，將

傳送給

並詢問

是與

，

中的哪個圖同構，如果

的回答剛好等於

，你就可以接受斷言C。如果

足夠強大，這一證明過程將在很短的時間內結束。這個證明系統也會帶來1/2的錯誤，注意到如果上述斷言錯誤，即給定的兩個圖是同構的（進而上述三個圖

和

相互同構），那麼即使全能的機器也不能以超過1/2的機率使得驗證者接受。我們可以照上面的例子處理來降低這一風險。

讀者可能會對第二個方向上研究的應用價值產生懷疑。畢竟在能夠大多數能想象得到的場景下我們需要證明方（在擁有傳統的數學證明前提下）也能夠中被高效地實現，而不是一臺全能的能瞬間回答任何難題的假想機器。

然而，好奇心驅動的基礎研究就是這樣，無論你對它持有什麼態度，你無法證明它將來沒有用。上面第二個方向上的研究經歷了幾年的曲折和意外。Fortnow在互動證明提出不久後給出了一個證據暗示互動證明可能無法證明上面提到的斷言B型別的斷言（後來的研究大大突破了他的負面結果）。第一次對理解互動證明威力的突破性進展是Nisan 在1989年的在他著名的郵件（參見Babai的演講， 這裡你可以看到Nisan所引發的空前慘烈的學術競爭，提到了蔡進一老師的結果）中宣佈的，然後導致了Shamir的IP=PSPACE（這個證明可以在兩頁半紙上寫下），Arora等人的——我認為是理論計算機領域繼Cook-Levin定理之後最為深刻的——PCP定理（對歷史感興趣的同學請參考這裡）。這方面的研究最後能夠落地應用在於Babai和Levin（是的，同Cook-Levin中的Levin，Micali稱他為“a force of nature”）等人實現的 “universal 互動證明系統”：對於有著極端冗長傳統證明的斷言我們可以透過universal 互動證明系統讓

全能的

證明者協助驗證者

高效地

驗證，當我們對那些有著比較短傳統證明的斷言應用同樣的互動證明系統時，則我們可以讓

普通的能高效實現的

證明者來協助驗證者以

驚人的效率

來驗證。

這些研究也為最近十年來興起的一些浪潮背後的理論工具，如雲/外包計算，區塊鏈中的簡潔非互動證明系統等。這或許是對人類好奇心的回報吧。

附註：

零知識證明的定義和那些廣泛流傳的錯誤的例子

寫這個文章的一個初衷是在目前能找到的有關零知識證明的中文科普絕大部分都在使用大量誤導性極強的錯誤的例子，其中一個典型的舉例如下（來自零知識證明_百度百科，被到處使用）：

證明舉例

1）A要向B證明自己擁有某個房間的鑰匙，假設該房間只能用鑰匙開啟鎖，而其他任何方法都打不開。這時有2個方法：

①A把鑰匙出示給B，B用這把鑰匙開啟該房間的鎖，從而證明A擁有該房間的正確的鑰匙。②B確定該房間內有某一物體，A用自己擁有的鑰匙開啟該房間的門，然後把物體拿出來出示給B，從而證明自己確實擁有該房間的鑰匙。

後面的②方法屬於零知識證明。好處在於在整個證明的過程中，B始終不能看到鑰匙的樣子，從而避免了鑰匙的洩露。

2）A擁有B的公鑰，A沒有見過B，而B見過A的照片，偶然一天2人見面了，B認出了A，但A不能確定面前的人是否是B，這時B要向A證明自己是B，也有2個方法。

①B把自己的私鑰給A，A用這個私鑰對某個資料加密，然後用B的公鑰解密，如果正確，則證明對方確實是B。

②A給出一個隨機值，B用自己的私鑰對其加密，然後把加密後的資料交給A，A用B的公鑰解密，如果能夠得到原來的隨機值，則證明對方是B。

後面的方法屬於零知識證明。

這兩個例子都是謬誤。

嚴謹一點地講，零知識性是保護證明者的安全性，它保證了對於任意的（甚至是惡意的）驗證者，他在與證明者（持有斷言的傳統數學證明）整個互動過程中所看到的訊息都能夠被一個高效的機器在不知道（同一個斷言的）傳統數學證明情況下完整地模擬出來。

上面證明A擁有房間鑰匙的方法顯然不是零知識的，拋開定義不講，它跟“零知識”的字面意義也不符：考慮一個“惡意的”驗證者B（零知識本身可以抵抗惡意的驗證者），他不知道房間裡有些什麼，但他可以要求A“請把房間裡外套拿出來”，如果A拿出來了，B立即知道了原來房間裡還有件外套，這是B在證明之前所不知道的。

第二個例子中我沒看懂“用公鑰解密”。估計該作者想舉的例子如下。B向A證明自己擁有一個公鑰加密方案（其中公鑰是雙方都知道的）的私鑰：A選擇一個隨機數，用該公鑰對其加密得到一個密文 c，將 c 傳送給B；B用自己的私鑰解密後返回明文給A，如果該明文與A之前選擇的隨機數一致，則A確認B確實知道該公鑰對應的私鑰。

這是也是個錯誤的例子，對於初學者有著極強的誤導性。考慮如下場景：D 給B轉賬一筆錢，將數目用B的公鑰加密後發給B明文 c‘。A無意截獲了這個密文 c’，它可以與B進行一次互動證明：將 c‘ 傳送給B，然後B 返回 c’ 對應的明文（即該筆錢的數目）。在這個場景中，A得到了互動證明之前他不知道的知識，即D轉賬給B的數目。

》》》》》》》》》

謝謝評論中的提醒，我上面對百度百科的第二個例子可能曲解了原意。前面也提到了我無法理解原文中“A用B的公鑰解密”，如果這句話理解成“A將密文傳送給B，請求B用自己的私鑰解密，然後返回相應密文”，則整個過程連證明都算不上：B顯然能在不知道相應私鑰的情況下執行整個過程，因為它知道相應的明文（和計算密文時使用的隨機數），換句話，這一過程與被證明的斷言“我知道公鑰對應的私鑰”無關。