- 區(qū)塊鏈應用開發(fā)指南:業(yè)務場景剖析與實戰(zhàn)
- 熊麗兵 董一凡等
- 1655字
- 2022-07-28 20:18:05
第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é)了“知識”,但是證明過程卻可以不泄露“知識“,同時這個證明的驗證過程仍然保持簡單、機械,以及有限。
- Effective Amazon Machine Learning
- Live Longer with AI
- Hadoop大數(shù)據(jù)實戰(zhàn)權(quán)威指南(第2版)
- 從0到1:JavaScript 快速上手
- 數(shù)據(jù)庫技術(shù)實用教程
- Hands-On Mathematics for Deep Learning
- MATLAB Graphics and Data Visualization Cookbook
- 跨領(lǐng)域信息交換方法與技術(shù)(第二版)
- 數(shù)據(jù)庫技術(shù)及應用
- 中文版Access 2007實例與操作
- 大數(shù)據(jù)數(shù)學基礎(chǔ)(Python語言描述)
- 數(shù)據(jù)庫查詢優(yōu)化器的藝術(shù):原理解析與SQL性能優(yōu)化
- Node.js High Performance
- Kubernetes快速進階與實戰(zhàn)
- Trino權(quán)威指南(原書第2版)