前言

區(qū)塊鏈的發(fā)展可謂是日新月異，分布式賬本，哈希函數(shù)，merkle tree，公鑰算法，p2p網(wǎng)絡(luò)，共識(shí)機(jī)制，智能合約等等很高大上的名詞相信大家一定都不會(huì)很陌生。區(qū)塊鏈像一個(gè)有機(jī)體，融合了各種不同的理論技術(shù)。零知識(shí)證明是構(gòu)建信任的重要技術(shù)，也是區(qū)塊鏈這個(gè)有機(jī)體中不可缺少的一環(huán)。

拋磚引玉的小故事

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

首先我拿出81（9x9）張空白的卡片放在桌上，在每張紙上寫(xiě)上1-9中的一個(gè)數(shù)字。然后我把數(shù)獨(dú)題目給出的已知數(shù)字朝上放置，把我自己已經(jīng)得到的解朝下放置，像下面這樣：

然后我對(duì)你說(shuō)，你挑一種檢驗(yàn)方式吧，你可以按照每一行，每一列或者每一個(gè)小九宮格檢驗(yàn)到底我的數(shù)字是不是重復(fù)的。

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

這時(shí)候我們打開(kāi)這些布袋，給你進(jìn)行驗(yàn)證。如果我確實(shí)知道這個(gè)數(shù)獨(dú)的解并且正確放置了每一張朝下的卡片的話，此時(shí)每個(gè)布袋里應(yīng)該都有9張沒(méi)有重復(fù)數(shù)字的，分別是數(shù)字1-9的卡片。

這種做法真的能夠讓人信服嗎？你可能會(huì)說(shuō)如果我挑了去檢驗(yàn)每一行是不是符合要求，那我就沒(méi)辦法檢驗(yàn)每一列或者每一個(gè)九宮格是不是符合要求了，你完全可以給我一個(gè)只滿足行，列或者九宮格要求的錯(cuò)誤的數(shù)獨(dú)答案。

但是你不要忘記了，我事先是不會(huì)知道你是按照哪種方式去驗(yàn)證的，如果我真的沒(méi)有數(shù)獨(dú)的解的話，你至少可以以三分之一的概率抓到我在騙人。而且如果進(jìn)行多次這樣的重復(fù)驗(yàn)證，我能夠瞞天過(guò)海的概率也會(huì)越來(lái)越小，假設(shè)驗(yàn)證次數(shù)為n，則我欺騙你的概率是3分之2的n次方，這樣就可以說(shuō)明我有很大的幾率知道這個(gè)問(wèn)題的解。

從這個(gè)小故事可以看出零知識(shí)證明的本質(zhì)就是在不揭曉我所知道或擁有的某樣?xùn)|西的前提下，向別人證明我有很大幾率（這點(diǎn)很重要，零知識(shí)證明說(shuō)到底是一個(gè)概率上的證明）確實(shí)知道或擁有這個(gè)東西。

零知識(shí)證明的定義

零知識(shí)證明(Zero-Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在1985提出的。證明者能夠在不向驗(yàn)證者提供任何有用的信息的情況下，使驗(yàn)證者相信某個(gè)論斷是正確的。零知識(shí)證明實(shí)質(zhì)上是一種涉及兩方或更多方的協(xié)議，即兩方或更多方完成一項(xiàng)任務(wù)列步驟。迄今為止，零知識(shí)證明已經(jīng)是密碼學(xué)的重要構(gòu)建，數(shù)據(jù)的隱私保護(hù)，計(jì)算壓縮與區(qū)塊鏈擴(kuò)容，端到端的通訊加密，身份認(rèn)證，去中心化存儲(chǔ)，信用存貯…….都可以看到它的身影。

其實(shí)上述的小故事就是一個(gè)簡(jiǎn)易的交互式零知識(shí)證明系統(tǒng)。交互式零知識(shí)證明需要驗(yàn)證方（你）在證明方（我）放好答案后，不斷的發(fā)送隨機(jī)試驗(yàn)。

由此可見(jiàn)一套完善的零知識(shí)證明體系需要以下的條件：

（1）完備性。如果證明方和驗(yàn)證方都是誠(chéng)實(shí)的，并遵循證明過(guò)程的每一步，進(jìn)行正確的計(jì)算，那么這個(gè)證明一定是成功的，驗(yàn)證方一定能夠接受證明方。（如果我知道這個(gè)數(shù)獨(dú)的解并且我和你都按照小故事里約定好的流程并且沒(méi)有人作弊的話，你一定可以驗(yàn)證每個(gè)袋子分別裝有9個(gè)不同的數(shù)字）

（2）合理性。沒(méi)有人能夠假冒證明方，使這個(gè)證明成功。（不知道這個(gè)數(shù)獨(dú)解的人一定沒(méi)辦法冒充我和你進(jìn)行驗(yàn)證并且讓你相信他能知道數(shù)獨(dú)的解）

（3）零知識(shí)性。證明過(guò)程執(zhí)行完之后，驗(yàn)證方只獲得了“證明方擁有這個(gè)知識(shí)”這條信息，而沒(méi)有獲得關(guān)于這個(gè)知識(shí)本身的任何一點(diǎn)信息。（這里可能需要涉及模擬器的相關(guān)概念，簡(jiǎn)單的說(shuō)就是你沒(méi)有辦法從從知道數(shù)獨(dú)的解的我這里得到任何關(guān)于數(shù)獨(dú)的解的知識(shí)）

零知識(shí)證明的發(fā)展

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

Zero knowledge：零知識(shí)證明。

succinct：簡(jiǎn)明的，證據(jù)信息較短，方便驗(yàn)證。

Non-interactivity：非交互的，證明者只要提供一個(gè)字符串，可放在鏈上公開(kāi)驗(yàn)證。

Arguments：證明過(guò)程是計(jì)算完好（computationally soundness）的，證明者無(wú)法在合理的時(shí)間內(nèi)造出偽證（破解）。

of knowledge：對(duì)于一個(gè)證明者來(lái)說(shuō)，在不知曉特定證明 (witness) 的前提下，構(gòu)建一個(gè)有效的零知識(shí)證據(jù)是不可能的。

自此以后，Libra、Sonic、SuperSonic、PLONK、SLONK、Halo、Marlin、Fractal、Spartan、Succinct 、Aurora ，OpenZKP、Hodor GenSTARK、RedShift、AirAssembly……各式各樣的零知識(shí)證明協(xié)議接連問(wèn)世。他們都有著各自的優(yōu)缺點(diǎn)，其中的很多協(xié)議被運(yùn)用在了區(qū)塊鏈以及加密貨幣中。

結(jié)語(yǔ)

總之，零知識(shí)證明學(xué)習(xí)曲線陡峭，它涉及密碼學(xué)，抽象代數(shù)，線性代數(shù)，數(shù)論等學(xué)科的綜合應(yīng)用，它引入的概念、符號(hào)很多會(huì)讓人眼花繚亂。下一篇文章我們會(huì)先簡(jiǎn)單介紹一下Schnorr協(xié)議以及從完備性，合理性和零知識(shí)性去進(jìn)行分析。希望各位保持耐心，由淺入深，循序漸進(jìn)，揭開(kāi)零知識(shí)證明的神秘面紗。

參考

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

• 公眾號(hào)“安比實(shí)驗(yàn)室”：--https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md

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

Tips

更多長(zhǎng)安鏈開(kāi)源項(xiàng)目QA，可登陸開(kāi)源社區(qū)、技術(shù)文檔庫(kù)查看。

下載源碼

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

查閱文檔

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

更多社區(qū)權(quán)益申請(qǐng)

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

“長(zhǎng)安鏈ChainMaker”是國(guó)內(nèi)首個(gè)自主可控區(qū)塊鏈軟硬件技術(shù)體系，由微芯研究院聯(lián)合頭部企業(yè)和高校共同研發(fā)，具有全自主、高性能、強(qiáng)隱私、廣協(xié)作的突出特點(diǎn)。長(zhǎng)安鏈面向大規(guī)模節(jié)點(diǎn)組網(wǎng)、高交易處理性能、強(qiáng)數(shù)據(jù)安全隱私等下一代區(qū)塊鏈技術(shù)需求，融合區(qū)塊鏈專用加速芯片硬件和可裝配底層軟件平臺(tái)，為構(gòu)建高性能、高可信、高安全的數(shù)字基礎(chǔ)設(shè)施提供新的解決方案，為長(zhǎng)安鏈生態(tài)聯(lián)盟提供強(qiáng)有力的區(qū)塊鏈技術(shù)支撐。取名“長(zhǎng)安鏈”，喻意“長(zhǎng)治久安、再創(chuàng)輝煌、鏈接世界”。

總結(jié)

以上是生活随笔為你收集整理的零知识证明系列之一——初探零知识证明的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。