零知識證明系列之一——初探零知識證明

前言

區塊鏈的發展可謂是日新月異，分布式賬本，哈希函式，merkle tree，公鑰演算法，p2p網路，共識機制，智能合約等等很高大上的名詞相信大家一定都不會很陌生，區塊鏈像一個有機體，融合了各種不同的理論技術，零知識證明是構建信任的重要技術，也是區塊鏈這個有機體中不可缺少的一環，

拋磚引玉的小故事

大家一定對數獨游戲不陌生，數獨游戲就是有一個9×9的盤面，我們要根據盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮（33）內的數字均含1-9，不能重復，假設現在有一個非常難的數獨，我廢了千辛萬苦的力氣終于得到了這個數獨的解，但是現在我告訴你，我會用零知識證明的方法給你證明我會這題的解，也就是說我不會把解透露給你，卻能讓你信服我確實有這題的解，仔細想想這是不是一件非常神奇的事情，

首先我拿出81（9x9）張空白的卡片放在桌上，在每張紙上寫上1-9中的一個數字，然后我把數獨題目給出的已知數字朝上放置，把我自己已經得到的解朝下放置，像下面這樣：

然后我對你說，你挑一種檢驗方式吧，你可以按照每一行，每一列或者每一個小九宮格檢驗到底我的數字是不是重復的，

那具體的驗證方法是什么樣子的呢？很簡單，我準備了9個袋子，然后按照你指定的驗證方法，把每一行，每一列或者每一個小九宮的卡片分別收集到9個袋子中去，

這時候我們打開這些布袋，給你進行驗證，如果我確實知道這個數獨的解并且正確放置了每一張朝下的卡片的話，此時每個布袋里應該都有9張沒有重復數字的，分別是數字1-9的卡片，

這種做法真的能夠讓人信服嗎？你可能會說如果我挑了去檢驗每一行是不是符合要求，那我就沒辦法檢驗每一列或者每一個九宮格是不是符合要求了，你完全可以給我一個只滿足行，列或者九宮格要求的錯誤的數獨答案，

但是你不要忘記了，我事先是不會知道你是按照哪種方式去驗證的，如果我真的沒有數獨的解的話，你至少可以以三分之一的概率抓到我在騙人，而且如果進行多次這樣的重復驗證，我能夠瞞天過海的概率也會越來越小，假設驗證次數為n，則我欺騙你的概率是3分之2的n次方，這樣就可以說明我有很大的幾率知道這個問題的解，

從這個小故事可以看出零知識證明的本質就是在不揭曉我所知道或擁有的某樣東西的前提下，向別人證明我有很大幾率（這點很重要，零知識證明說到底是一個概率上的證明）確實知道或擁有這個東西，

零知識證明的定義

零知識證明(Zero-Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在1985提出的，證明者能夠在不向驗證者提供任何有用的資訊的情況下，使驗證者相信某個論斷是正確的，零知識證明實質上是一種涉及兩方或更多方的協議，即兩方或更多方完成一項任務列步驟，迄今為止，零知識證明已經是密碼學的重要構建，資料的隱私保護，計算壓縮與區塊鏈擴容，端到端的通訊加密，身份認證，去中心化存盤，信用存貯…….都可以看到它的身影，

其實上述的小故事就是一個簡易的互動式零知識證明系統，互動式零知識證明需要驗證方（你）在證明方（我）放好答案后，不斷的發送隨機試驗，

由此可見一套完善的零知識證明體系需要以下的條件：

（1）完備性，如果證明方和驗證方都是誠實的，并遵循證明程序的每一步，進行正確的計算，那么這個證明一定是成功的，驗證方一定能夠接受證明方，（如果我知道這個數獨的解并且我和你都按照小故事里約定好的流程并且沒有人作弊的話，你一定可以驗證每個袋子分別裝有9個不同的數字）

（2）合理性，沒有人能夠假冒證明方，使這個證明成功，（不知道這個數獨解的人一定沒辦法冒充我和你進行驗證并且讓你相信他能知道數獨的解）

（3）零知識性，證明程序執行完之后，驗證方只獲得了“證明方擁有這個知識”這條資訊，而沒有獲得關于這個知識本身的任何一點資訊，（這里可能需要涉及模擬器的相關概念，簡單的說就是你沒有辦法從從知道數獨的解的我這里得到任何關于數獨的解的知識）

零知識證明的發展

在1985年以后的很長一段時間內，零知識證明協議由于沒有較好的運行效率和通用性，大部分只停留在理論，這些理論的零知識證明協議各自有不同的特點，有的協議是專職協議，只能證明某些特定的事情，例如著名的Schnorr 協議、三色圖協議，有些零知識證明協議是全能的，只要你能用代碼定義的問題，它都能證明（只是理論可行，不意味著有運行效率），有些協議是互動式的，需要證明者和驗證者來回發很多輪訊息，有些是非互動式的，證明者只需要根據協議向驗證者發一次訊息，有的協議證明大小與問題規模相關，問題越復雜，證明越長，而有些協議下，無論問題多復雜，證明大小都一樣，而一個全能的，非互動的，常數大小的零知識證明協議，是密碼學研究者們多年奮斗的目標，在這個目標下，zk-SNARK橫空出世，zk-SNARK（zero-knowledge succint non-interactive arguments of knowledge）里面的每個單詞都有特定的含義：

Zero knowledge：零知識證明，

succinct：簡明的，證據資訊較短，方便驗證，

Non-interactivity：非互動的，證明者只要提供一個字串，可放在鏈上公開驗證，

Arguments：證明程序是計算完好（computationally soundness）的，證明者無法在合理的時間內造出偽證（破解），

of knowledge：對于一個證明者來說，在不知曉特定證明 (witness) 的前提下，構建一個有效的零知識證據是不可能的，

自此以后，Libra、Sonic、SuperSonic、PLONK、SLONK、Halo、Marlin、Fractal、Spartan、Succinct 、Aurora ，OpenZKP、Hodor GenSTARK、RedShift、AirAssembly……各式各樣的零知識證明協議接連問世，他們都有著各自的優缺點，其中的很多協議被運用在了區塊鏈以及加密貨幣中，

結語

總之，零知識證明學習曲線陡峭，它涉及密碼學，抽象代數，線性代數，數論等學科的綜合應用，它引入的概念、符號很多會讓人眼花繚亂，下一篇文章我們會先簡單介紹一下Schnorr協議以及從完備性，合理性和零知識性去進行分析，希望各位保持耐心，由淺入深，循序漸進，揭開零知識證明的神秘面紗，

參考

• 公眾號“星想法”：--https://mp.weixin.qq.com/s/eU8mp81VhpV-g1x89-uZYA

• 公眾號“安比實驗室”：--https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md

• 小故事的來源：--https://medium.com/qed-it/the-incredible-machine-4d1270d7363a

Tips

更多長安鏈開源專案QA，可登陸開源社區、技術檔案庫查看，

下載原始碼

https://git.chainmaker.org.cn/chainmaker/chainmaker-go

查閱檔案

https://docs.chainmaker.org.cn/

更多社區權益申請

https://wj.qq.com/s2/8620064/7abd

“長安鏈ChainMaker”是國內首個自主可控區塊鏈軟硬體技術體系，由微芯研究院聯合頭部企業和高校共同研發，具有全自主、高性能、強隱私、廣協作的突出特點，長安鏈面向大規模節點組網、高交易處理性能、強資料安全隱私等下一代區塊鏈技術需求，融合區塊鏈專用加速芯片硬體和可裝配底層軟體平臺，為構建高性能、高可信、高安全的數字基礎設施提供新的解決方案，為長安鏈生態聯盟提供強有力的區塊鏈技術支撐，取名“長安鏈”，喻意“長治久安、再創輝煌、鏈接世界”，