第3章　零知識(shí)證明

零知識(shí)證明技術(shù)是現(xiàn)代密碼學(xué)三大基礎(chǔ)之一，由格沃斯（S.Goldwasser）、米加里（S.Micali）及拉科夫（C.Rackoff）在20世紀(jì)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）。

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

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

零知識(shí)證明的英文全稱是zero-knowledge proofs，簡(jiǎn)寫為ZKP，是一種有用的密碼學(xué)方法。

證明過程涉及兩個(gè)對(duì)象：一個(gè)是宣稱某一命題為真的示證者（prover），另一個(gè)是確認(rèn)該命題確實(shí)為真的驗(yàn)證者（verifier）。

所謂“零知識(shí)”，意味著當(dāng)證明完成后，驗(yàn)證者除了獲得對(duì)命題正確與否的答案之外，其他信息一無所知，獲得的“知識(shí)”為零。

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

什么是證明？

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

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

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

2．20世紀(jì)初：證明=符號(hào)推理

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

3．20世紀(jì)60年代：證明=程序

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

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

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

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

4．20世紀(jì)80年代：證明=交互

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

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

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

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