零知識證明作為一種密碼學(xué)工具/思想，在加密，區(qū)塊鏈，隱私保護，可信計算，聯(lián)邦學(xué)習(xí)等諸多重要領(lǐng)域都有很重要的應(yīng)用，但是其思想和具體的協(xié)議又相對比較具有技巧性，這給普通開發(fā)者和愛好者的理解帶來了很高挑戰(zhàn)。目前中文世界中能看到的零知識證明介紹有些過于簡單，甚至例子本身有問題，不滿足零知識性；有些則過于專業(yè)，對讀者的背景知識提出了很高的挑戰(zhàn)。所以本系列力圖從基礎(chǔ)的數(shù)學(xué)工具出發(fā)，通過嚴謹?shù)耐评韼椭x者理解零知識證明的機制，并且能夠自己推導(dǎo)，證明，直至構(gòu)造零知識證明。本系列力求使用盡可能簡單的數(shù)學(xué)工具，大多數(shù)推理基于高中的數(shù)學(xué)知識，部分涉及到大學(xué)數(shù)學(xué)代數(shù)和離散數(shù)學(xué)的部分，但這些部分也會被指出，并給予解釋。如果讀者依舊具有閱讀困難，可以只接受結(jié)論，回過頭來再看之前的證明的細節(jié)。本系列參考了Shafi Goldwasser，Silvio Micali和Charles Rackoff的《The Knowledge Complexity of Interactive Proof Systems》，Maksym Petkus的《Why and How zk-SNARK Works: Definitive Explanation》等一些專家學(xué)者的著作，建議讀者在閱讀本系列之后能夠去閱讀這些經(jīng)典論文的原文，想必會有更深的收獲。
零知識證明誕生的標(biāo)志是Shafi Goldwasser, Silvio Micali, 和Charles Rackoff在1985年發(fā)表在SIAM Journal on computing的《The Knowledge Complexity of Interactive Proof Systems》一文。這篇論文創(chuàng)造性的使用計算復(fù)雜度理論分析了一個證明需要提供多少知識，并且指出了通常定理的證明比定理本身包含了更多的知識。比如，證明方程x^2-3x+2=0存在解，那么只需要展示其中一個解即可，比如x=1，但是，我們可以看出，這比證明方程存在解本身提供了更多的知識——揭示了其中的一個解。因此，如果一個證明，除了被討論的命題的正確性本身之外，不傳達出任何其他知識，那么這個證明可以被認為是”零知識性“的。由于這些跨時代的工作，這篇論文的三位作者都獲得了計算理論最高榮譽”哥德爾獎“，論文的前兩位作者更因其在密碼學(xué)領(lǐng)域的杰出貢獻共同獲得了2012年的圖靈獎。
但是零知識證明被學(xué)術(shù)界和公眾接受并不是一件一帆風(fēng)順的事情，即使《The Knowledge Complexity of Interactive Proof Systems》這篇具有跨時代意義，并且開創(chuàng)了一個新領(lǐng)域乃至產(chǎn)業(yè)的論文，在最初的的投稿的時候也被拒絕了六七次。理解零知識證明，尤其是直觀的建立一個簡單的理解是困難的，即使是發(fā)明者本身，在舉例子的時候仍然非常謹慎，有興趣的讀者可以參看Goldwasser的圖靈獎采訪中的一個片段（http://youtube.com/watch?v=DfJ8W49R0rI）。這也是許多剛接觸到零知識證明的讀者會產(chǎn)生不適的原因。所以與其去嘗試在了解細節(jié)之前嘗試建立一個宏觀的直覺，反倒不如跟隨數(shù)學(xué)和邏輯的指引，逐步深入。因為可能零知識證明本身就并不是一個簡單的知識。
并且，很多讀者在學(xué)習(xí)零知識證明，乃至各種密碼學(xué)工具的過程中，最大的障礙可能不是如何實現(xiàn)，而是這些算法的數(shù)學(xué)基礎(chǔ)。因此本系列從數(shù)學(xué)基礎(chǔ)開始，一步步解決這些困難。
零知識證明的思想可以追溯到1977年由Ron Rivest （2002年圖靈獎），Adi Shamir（2002年圖靈獎），和Leonard Adleman（2002年圖靈獎）提出了的RSA非對稱加密算法，乃至1976年由Ralph C. Merkle （2010年IEEE理察·衛(wèi)斯里·漢明獎?wù)?，Merkle tree發(fā)明者），Bailey Whitfield Diffie（2015年圖靈獎）和Martin Edward Hellman（2015年圖靈獎）提出的Diffie–Hellman密鑰交換協(xié)議。這些重要的密碼學(xué)算法的數(shù)學(xué)基礎(chǔ)都有很多通用的，因此學(xué)習(xí)這部分知識也會為進一步理解密碼學(xué)打下比較好的基礎(chǔ)。不僅是這些數(shù)學(xué)基礎(chǔ)，零知識證明本身在數(shù)學(xué)結(jié)構(gòu)上也很具有啟發(fā)性，匈牙利數(shù)學(xué)家數(shù)學(xué)家László Lovász和以色列計算機科學(xué)家Avi Wigderson也因相關(guān)工作，剛剛在2021年獲得了數(shù)學(xué)領(lǐng)域舉足輕重的阿貝爾獎。另外，與之相關(guān)的研究還有姚期智（2000年圖靈獎）在1982年提出的”百萬富翁“問題，但這個問題之后往往被用作不經(jīng)意傳輸?shù)臉永?/p>
零知識證明=零知識+證明
零知識證明本身是一個證明，可以嘗試證明任何命題，比如：
- 用戶A的信用評分大于10；
- 公司C在2021年的營業(yè)額大于100萬；
- 用戶R有登錄訂票系統(tǒng)的權(quán)限。
當(dāng)然，命題也可以更數(shù)學(xué)化，比如：
- 證明人P知道一個三階多項式，1和2是這個多項式的兩個根。
不要擔(dān)心數(shù)學(xué)化的命題如何證明實際中有意義的命題，因為我們可以比較容易的設(shè)計一套映射規(guī)則，把實際命題映射到數(shù)學(xué)命題上，比如ASCII碼表就可以用數(shù)字來表示英文字母和符號，組成”有意義“的句子?？傊?，從數(shù)學(xué)的角度來看，這些命題之間并沒有不可逾越的鴻溝（當(dāng)然，僅僅是我們關(guān)注的這些命題）。
證明則是針對某一個命題。在公理的基礎(chǔ)上，經(jīng)行邏輯推導(dǎo)的過程。最著名的公理-證明系統(tǒng)之一就是歐幾里得在《幾何原本》中構(gòu)造的幾何學(xué)。我們在中學(xué)時代應(yīng)該都接觸過歐幾里得的平面幾何的五條公理：
- 從一點向另一點可以引一條直線；
- 任意線段能無限延伸成一條直線；
- 給定任意線段，可以以其一個端點作為圓心，該線段作為半徑作一個圓；
- 所有直角都相等；
- 若兩條直線都與第三條直線相交，并且在同一邊的內(nèi)角之和小于兩個直角，則這兩條直線在這一邊必定相交。
在這幾條公理的基礎(chǔ)上，通過邏輯推理，可以證明/證否各種各樣的幾何定理。比如
- 平行于同一平面的兩條直線平行.
零知識證明則是一種特殊的證明，其特殊體現(xiàn)在這種證明具有”零知識性“，也就是證明本身只會說明命題的真?zhèn)闻c否，而不會揭示其他任何信息。比如可以證明：
- 用戶A的信用評分大于10，但是不用揭示用戶的信用評分或者其他個人數(shù)據(jù)；
- 證明人P知道一個三階多項式，1和2是這個多項式的兩個根，但是證明人P不需要揭示這個多項式是什么，也不需要提供關(guān)于多項式的其他信息。
因此，一個零知識證明系統(tǒng)中至少需要包含兩個角色：證明者和驗證者，證明者需要提供一份證明，使得驗證者確認某個特定命題的真?zhèn)危⑶?，證明過程不應(yīng)該泄露任何其他知識。
在此基礎(chǔ)上，我們可以看出零知識證明具有的三個屬性：
- 完備性：如果命題是真的，那么證明者可以使驗證者確信命題為真；
- 正確性：如果命題是假的，那么證明者無法使驗證者確信命題為真；
- 零知識性：整個證明過程除了揭示了命題本身的真假，不能夠揭示其他任何知識。
可以看出，其中性質(zhì)1和2都是證明本身具有的屬性，而性質(zhì)3則是零知識證明的關(guān)鍵，也就是說，之后的所有的工作，都是在證明的基礎(chǔ)上，通過數(shù)學(xué)方式，來避免揭示其他任何知識，保證零知識性。
【1】Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems[J]. SIAM Journal on computing, 1989, 18(1): 186-208.
【2】Petkus M. Why and How Zk-SNARK Works[J]. ArXiv, 2019.
【3】https://zh.m.wikipedia.org/zh-cn/歐幾里得幾何
作者：好奇的貓_CuriousCat
微信公眾號：Bit_heart
InfoQ：比特之心
知乎：比特之心
