第3章　零知識證明

零知識證明技術(shù)是現(xiàn)代密碼學三大基礎(chǔ)之一，由格沃斯（S.Goldwasser）、米加里（S.Micali）及拉科夫（C.Rackoff）在20世紀80年代初提出（SHAFI GOLDWASSER, SILVIO MICALI,AND CHARLES RACKOFF, 1989.《The Knowledge Complexity of Interactive Proof System》，下載地址：http://crypto.cs.mcgill.ca/～crepeau/COMP647/2007/TOPIC01/GMR89.pdf）。

早期的零知識證明由于其效率和可用性等限制，未得到很好的利用，僅停留在理論層面。

從2010年開始，零知識證明的理論研究才開始不斷突破，同時區(qū)塊鏈也為零知識證明創(chuàng)造了大展拳腳的機會，使之走進了大眾視野。

零知識證明的英文全稱是zero-knowledge proofs，簡寫為ZKP，是一種有用的密碼學方法。

證明過程涉及兩個對象：一個是宣稱某一命題為真的示證者（prover），另一個是確認該命題確實為真的驗證者（verifier）。

所謂“零知識”，意味著當證明完成后，驗證者除了獲得對命題正確與否的答案之外，其他信息一無所知，獲得的“知識”為零。

零知識證明是構(gòu)建信任的重要技術(shù)，也是區(qū)塊鏈這個有機體中不可缺少的一環(huán)。

什么是證明？

最早接觸“證明”這個概念，應該是在中學課程中見到的各種相似三角形的證明。當我們畫出一條“神奇”的輔助線之后，證明過程突然變得簡單。其實，證明的發(fā)展經(jīng)歷了漫長時間長河的沉淀。

1．古希臘時期：證明=知其然，更知其所以然

數(shù)學證明最早源于古希臘。古希臘人發(fā)明了公理與邏輯，他們用證明來說服對方，而不是靠權(quán)威。這是徹頭徹尾的“去中心化”。自古希臘以來，這種方法論影響了整個人類文明的進程。

2．20世紀初：證明=符號推理

到了19世紀末，康托、布爾、弗雷格、希爾伯特、羅素、布勞威、哥德爾等人定義了形式化邏輯的符號系統(tǒng)。而“證明”則是利用形式化邏輯的符號語言編寫的推理過程。邏輯本身靠譜么？邏輯本身“自洽”嗎？邏輯推理本身對不對，能夠證明嗎？這讓數(shù)學家／邏輯學家／計算機科學家發(fā)明了符號系統(tǒng)。

3．20世紀60年代：證明=程序

又過了半個世紀，到20世紀60年代，邏輯學家哈斯卡·咖里（Haskell Curry）和威廉·霍華德（William Howard）相繼發(fā)現(xiàn)了在“邏輯系統(tǒng)”和“計算系統(tǒng)——Lambda演算”中出現(xiàn)了很多“神奇的對應”，這就是后來被命名的“柯里-霍華德對應”（Curry-Howard Correspondence）。這個發(fā)現(xiàn)使得大家恍然大悟，“編寫程序”和“編寫證明”實際上在概念上是完全統(tǒng)一的。

在這之后的50年，相關(guān)理論與技術(shù)的發(fā)展使得證明不再停留在草稿紙上，而是可以用程序來表達。這個同構(gòu)映射非常有趣：程序的類型對應于證明的定理，循環(huán)對應于歸納，在直覺主義框架中，證明就意味著構(gòu)造算法，構(gòu)造算法實際上就是在寫代碼。（反過來也成立）

目前，在計算機科學領(lǐng)域，許多理論的證明已經(jīng)從紙上的草圖變成了代碼的形式，比較流行的“證明編程語言”有Coq、Isabelle、Agda等。采用編程的方式來構(gòu)造證明，證明的正確性檢查可以機械地由程序完成，并且許多重復性的勞動可以由程序來輔助完成。數(shù)學理論證明的大廈正在像計算機軟件一樣逐步地構(gòu)建。1996年12月，麥昆（W.McCune）利用自動定理證明工具EQP證明了一個有63年歷史的數(shù)學猜想“Ronbins猜想”，《紐約時報》隨后發(fā)表了一篇題為Computer Math Proof Shows Reasoning Power的文章，再一次探討機器能否代替人類產(chǎn)生創(chuàng)造性思維的可能性。

利用機器的輔助確實能夠有效地幫助數(shù)學家的思維抵達更多未知的空間，但是“尋找證明”仍然是最有挑戰(zhàn)性的工作。“驗證證明”則必須是一個簡單、機械并且有限的工作。這是一種天然的“不對稱性”。

4．20世紀80年代：證明=交互

時間撥到1985年，喬布斯剛剛離開蘋果，而格沃斯（S. Goldwasser）博士畢業(yè)后來到了MIT，與米加里（S.Micali）、拉科夫（Rackoff）合寫了一篇能載入計算機科學史冊的經(jīng)典：《交互式證明系統(tǒng)中的知識復雜性》。

他們對“證明”一詞進行了重新的詮釋，并提出了交互式證明系統(tǒng)的概念：通過構(gòu)造兩個圖靈機進行“交互”而不是“推理”，來證明一個命題在概率上是否成立。“證明”這個概念再一次被拓展。

交互證明的表現(xiàn)形式是兩個（或者多個）圖靈機的“對話腳本”，或者稱為Transcript。而這個對話過程中有一個顯式的“證明者”角色，還有一個顯式的“驗證者”角色。其中，證明者向驗證者證明一個命題成立，同時還“不泄露其他任何知識”。這種證明方式就被稱為“零知識證明”。

證明凝結(jié)了“知識”，但是證明過程卻可以不泄露“知識“，同時這個證明的驗證過程仍然保持簡單、機械，以及有限。