為此，我們特別刊登來自中國科學院資訊工程研究所鄧燚研究員的《零知識證明：一個略微嚴肅的科普》，對“零知識性”的本質和“互動證明”的革命性及歷史演變進行了全面的詮釋，建議收藏。
構成一個傳統數學定理證明的精髓有兩點：
(1) 能夠高效地、機械式（無需任何創造性）地對證明進行驗證；
(2) 對於一個錯誤的斷言無法找到一個能夠透過驗證的證明。
這兩點本質上都只與驗證有關：它只強調普通的時間有限的驗證者能進行驗證而不會被惡意的證明所欺騙。通常我們並不關心一個證明是怎麼找到的，有些時候尋找一個定理的證明需要漫長的時間和極高的創造力，這也解釋了為什麼我們會有菲爾茲獎，沃爾夫獎.....
傳統的證明是非互動的，我們可以把它寫在紙上供驗證者在無需證明者在場的情況下進行驗證。1985年Goldwasser，Micali和Rackoff透過給傳統的數學證明引入隨機性和互動，即以問答方式進行證明，由此產生的互動證明系統，這給後來整個電腦科學和密碼學的發展帶來了（遠遠超出概念提出者所預料的）深遠的影響。
一、互動證明的革命性
現在回過頭去看，如果把目光放寬一點，你會發現互動證明已經在人類歷史上出現很久了，比如法庭上控方律師對被告的詰問，可以看成是被告對自己無罪所作的的一個互動證明。這裡互動和隨機性的作用體現的淋漓盡致：
試想如果被告能在開庭前一天獲得控方律師所有的提問，那麼他很可能能夠編造一個完美的故事騙過對方；如果控方律師所有的提問都是未知的，那麼他能騙過對方的概率應該不大，畢竟在短時間內一個謊言接著一個謊言地編下去還能使對方信服，這對智商要求太高。
但這絲毫不影響互動證明這一概念的（在當時的）前衛性和革命性。我想強調的是，在科學上，一個好的定義本身的意義並不亞於一個好的結果的意義。互動性證明的革命性本質上體現在下面兩個方面（均是傳統數學證明無法實現的）:
第一個方面是它能實現零知識性，允許你安全地向他人進行證明。互動的訊息能構成一個證明（仍然體現了傳統證明的精髓）而它們本身不洩漏“斷言為真”之外的任何知識。這裡的“知識”可以理解為“計算能力”，證明是“零知識的”意味著整個證明過程沒有增加驗證者的計算能力（即驗證者之前無法解決的問題在證明完成之後仍然無法解決）。這個性質保證了互動完成後驗證者只知道被證明的斷言為真，但他並不知道怎麼轉而向其他人證明這一斷言，它的代價是會產生一些微小的錯誤。
這裡一個比較精確一點的例子就是向紅綠色盲來證明兩個球著色不同：
視覺正常的證明者持有的傳統證明/證據是眼裡看到的不同顏色，他先將兩個球分別放在色盲的兩隻手中，記住左右手中的顏色；色盲將手放背後，腦子裡隨機決定是否在背後交換手中的球，然後將雙手握球展示給證明者並問他自己是否剛才在背後交換了手中的球，證明者透過對比之前色盲兩手中球的顏色來回答他的問題。
這一互動證明體現了上述傳統證明系統的兩點精髓，對於第二點，這裡帶來了1/2的錯誤概率，即對於錯誤的斷言（即兩個球顏色相同），證明者仍能以1/2的概率騙過驗證者，不過這可以重複多次來降低這一概率。零知識在這裡顯而易見：色盲在互動結束後除了相信他手中球是顏色不同的之外並沒有得到任何額外的知識。
還有一些其他的例子，如證明兩種白酒味道不同，可口可樂和百事可樂的味道不同（見下文①），但這兩個例子一般用來說明互動的威力，而非零知識性。
零知識證明一個顯然的密碼學應用就是身份認證。如你可以隨機挑選兩個素數 , 計算它們的乘積，將乘積作為你的身份公佈 。需要進行身份認證時，你向驗證方證明“我知道我的身份對應的兩個素因子”。
在“分解整數是困難的”假設下，這構成了一個身份認證系統：驗證方在證明完成後沒有得到任何有關兩個素因子的知識。GMR透過引入模擬正規化精確定義了零知識性。這一模擬正規化對密碼學影響深遠，它為密碼學從藝術到科學的轉變奠定了基礎。
第二個方面是它能夠產生不可思議的可極端高效驗證的證明，允許證明者來證明在傳統證明系統下幾乎無法（即使給定證明）驗證的斷言，如下方案例：
斷言B：“斷言A不存在長度小於1000個字元（為方便，假設為2進位制字元）的傳統數學證明”。注意到斷言B本身的傳統證明有可能是所有可能的長度為 1000位元的字串，它的長度約為1000×21000 位元，即驗證者驗證斷言B很可能需要檢查幾乎所有長度為1000位元的字串， 並且逐一否定其構成斷言A的證明才能確定斷言B的正確性，這顯然不會“高效”，即使給定斷言B的傳統數學證明，你也無法在有限的一生中驗證完畢。
當然不是所有的這種型別的數學斷言都需要這麼長的證明，對於某些斷言A我們容易證明它是錯誤的（因此不存在任何長度的證明），但注意到所有有著多項式長度證明的數學定理構成一個NP完全集合，上述型別的斷言在某種意義上組成一個Co-NP的集合，在合理的假設下總會有一些這型別斷言會有很長很長的傳統證明。
然而，互動證明能夠讓驗證者在遠遠遠遠小於1000×21000時間（機器執行步數）-比如1分鐘-內高效驗證斷言B的正確性。一個經典的例子就是：
如何在短時間內向他人證明斷言C：“這兩個n頂點的圖G0和G1是不同構的”。這個斷言的傳統數學證明會很長（你可以認為就是由幾乎所有n個點到n個點上的置換對映組成，驗證者逐一驗證每一個置換對映都不構成這倆圖的同構後確認這兩圖不同構。這雖然不正確, 但不影響我們的討論。圖同構目前有準多項式時間演算法②），你無法在有限的時間內驗證完畢。0.
如果假定存在一個無所不能的超級計算機M它能在瞬間判斷兩個圖是否同構，則你可以透過互動在M（它扮演證明者的角色）的協助下驗證斷言C的正確性：
你隨機選擇一個位元 b和一個同構對映Φ並計算一個新的圖H=Φ（Gb），將H傳送給M並詢問M是與G0和G1中的哪個圖同構，如果M的回答剛好等於b，你就可以接受斷言C。如果M足夠強大，這一證明過程將在很短的時間內結束。
這個證明系統也會帶來1/2的錯誤，注意到如果上述斷言錯誤，即給定的兩個圖是同構的（進而上述三個圖 G0，G1和H 相互同構），那麼即使全能的機器也不能以超過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 互動證明系統讓全能的證明者協助驗證者高效地驗證，當我們對那些有著比較短傳統證明的斷言應用同樣的互動證明系統時，則我們可以讓普通的能高效實現的證明者來協助驗證者以驚人的效率來驗證。
這些研究也是最近十年來興起的一些浪潮背後的理論工具，如雲/外包計算，區塊鏈中的簡潔非互動證明系統等。這些或許是對人類好奇心的回報吧。
歡迎參考如下附加文件，獲取更多幹貨內容：
①連結地址：
https://www.cs.princeton.edu/courses/archive/fall07/cos433/lec15.pdf
②連結地址：
http://people.cs.uchicago.edu/~laci/update.html
③連結地址：
https://www.sciencedirect.com/sdfe/pdf/download/eid/1-s2.0-0020019088901998/first-page-pdf
④連結地址：
https://www.cs.princeton.edu/courses/archive/spr09/cos522/BabaiEmail.pdf
⑤連結地址：
http://www.lirmm.fr/~ashen/mathtext/ip/1992/ip-pspace-simplified.pdf
⑥連結地址：
https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf
⑦連結地址：
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D09EEB939ED2251B3D7C1648A1B2C4E6?doi=10.1.1.42.5832&rep=rep1&type=pdf
