本文作者東澤，來自安比技術社區的小夥伴，目前就讀於史丹福大學，研究方向密碼學，本系列文章來源於作者在斯坦福著名的課程《CS 251: Cryptocurrencies and blockchain technologies》上的學習筆記，該課程授課老師是密碼學大拿 Dan Boneh。
上個學期在斯坦福跟著Dan Boneh學習了區塊鏈和數字貨幣相關的技術。和以往的課程不同的是，今年的課程新添加了一個章節，叫做零知識證明。萌萌的Dan和他的大神phd Ben Fisch給我們輪流上課，花了兩周時間講完了零知識的起源、概念和zkSNARK的實現。這兩天考完期末考試，複習的過程中在腦海中再三回味整堂課，覺得最精彩的部分還是零知識證明。想著最近趁著假期總結一下，分享給大家。前言寫完第一稿之後，分享給朋友Proofread的時候，發現很多朋友反饋到說，背景知識不太夠。所以我在開始之前額外添加了這一章節，標註了一下為了能讀懂這篇文章所需的背景閱讀：
Merkle Tree/Merkle Proof: https://blog.csdn.net/wo541075754/article/details/54632929比特幣的交易: https://blog.csdn.net/liduanwh/article/details/81141972UTXO模型: https://www.jianshu.com/p/02fd289e8853一些基本的加密解密概念: https://www.jianshu.com/p/f7c729a41c9f讀完了前言之後，我們就可以開始正文了。要說零知識證明真正火熱的出現在大家的視野裡，其實還要從比特幣開始說起。比特幣的不足如果熟悉比特幣的話，大家應該會知道，在比特幣網絡上，每一筆交易都是公開的。
如果A要付給B一筆錢，那麼A就會拿著大喇叭向全網公布，她要創建一筆新的交易（Tx），並且這個交易的受益人是B的公鑰（P2PK），或者是公鑰的哈希值（P2PKH）。B只要看到了這筆交易，就可以用自己的私鑰籤署一份數字籤名，證明自己真的是這個公鑰的主人，從而花掉這筆錢。當A提交了付錢給B的這筆交易後，作為一個網絡上的旁觀者M，她只能看到一串亂碼地址aaaaa要付x個幣給一串亂碼地址bbbbb。隨後當B再打錢給C的時候，他也只能看到bbbbb打了一筆錢給ccccc。我們可以看到比特幣裡的交易是有很強的連接性的。雖然不知道誰打錢給了誰，但是我們可以順藤摸瓜找到很多條交易鏈條。如果每個用戶都只是乖巧的來回打錢，比特幣其實還是比較安全的。
一旦有用戶看破了，不想玩了，想去交易所套現了，那麼這一整條鏈的交易信息都會被暴露。交易所往往都有KYC（Know Your Customer）政策，每個數字貨幣和法幣進行兌換的用戶要進行實名制認證。一旦C從ccccc這個地址提款跑路了，那麼交易所就掌握了bbbbb曾經打錢給C的事實。如果C涉嫌洗錢，這個時候只需要靜靜等待B套現出來，然後一把抓住。美國現在已經有很多公司在做比特幣上的交易鏈條分析，比如Chainalysis。想必說到這裡，大家都能感受到比特幣的不足了：隨機生成的收款公鑰只是一個假象（網名），一旦在哪裡實名制認證了，把網名和實名聯繫起來了，那麼之前在網上所有的所作所為也就一覽無餘，毫無隱私可言。這就好比有人用網名在貼吧上發帖子噴人，然後被人用密保找到了手機號，再用手機號找到了註冊的實名，從而被人肉是一個道理。匿名(Anonymous) 與假名(Pseudonymous)我們對於隱私的理解，其實分兩種。第一種是匿名（Anonymous），意思是用戶不用透露任何和自己相關的信息，好比是學校的表白牆，你永遠無法知道到底是誰寫了上去，反正字就是寫在了上面。
第二種是假名（Pseudonymous），意思是用戶通過自己創造的假名來發表信息，好比是貼吧，如果你不了解這個用戶，你無法建立網名到實名的聯繫，你也就不知道發帖的人是誰。這麼分析一看，比特幣其實是一種假名機制：每個用戶都會隨機生成自己的公鑰（假名），並且通過公鑰地址來收款。這就好比是A/B/C/D四個人分別化名為小明/小紅/二狗/小剛在網上匿名交易，只要D一旦在任何一個環節暴露出了自己的身份（比如在交易所提現），那麼小明/小紅/二狗和D之間的關係就會馬上暴露出來。我們對於如何增強比特幣的保密性，可以從這兩種方法來討論。增加隱秘性的方法CoinJoin既然A給B付錢會被人看到，C給D付錢也會被人看到，有人就想到了說那索性把ABCD這四個人全部扔到一筆交易裡面去。因為比特幣的交易可以多個輸入輸出，所以一個旁觀者會看到一個交易裡，aaaaa和ccccc都往裡面打了x個幣，然後bbbbb和ddddd收款。這樣一來，就算交易所得知了這幾個地址分別對應ABCD四人，也很難分辨到底誰收了誰的錢。
如果兩組交易還是太好辨認怎麼辦？兩個不夠混四個，四個不夠混八個，以此類推。把各種人的交易結合在一起，混淆視聽，讓人無法追蹤。這就是CoinJoin。CoinJoin的弊端是什麼？其實混合多筆交易並不能完美的杜絕被人順藤摸瓜，只能說在概率上減低了被一路摸上來的機率。而且還有一個很重要的一點，如果要混合AB與CD的交易，那麼他們的交易量一定要相同。如果A付給B一萬個幣，C付給D一個幣，我們只需要看輸入和輸出，就可以馬上把一筆CoinJoin交易拆散成兩個獨立的交易。所以混搭相似交易額度的交易，也是CoinJoin在實現的時候一個不容忽視的難點。如果用上文的分類來看的話，CoinJoin只是比特幣現有系統的一個騷操作，它的本質仍然是假名機制。Confidential Transaction（私密交易/CT）既然隱藏我是誰那麼麻煩，那麼人們就開始動腦思考：如果不隱藏參與交易的公鑰，我們還可以隱藏交易的額度。A給B打錢的時候，就算B被暴露了，全網也不會得知A究竟給了B多少錢。如果這步操作能實現，那麼我們甚至就可以用比特幣發工資了，大家只能看到你每個月工資到帳，但是並不知道你賺了多少錢。想要具體實現的方法，我們先要了解一種特殊的加密算法：同態加密。一句話概括的話，同態加密就是一種特殊的加密算法，可以讓密文保持原有的數學特性。我們可以假設有一個加密方法E，如果E是加法同態的話，那麼E(a) + E(b) = E(a+b)。反之如果乘法同態的話，那麼E(a) x E(b) = E(a x b)。介於這篇文章是講zkp的科普文，我們就不詳細了解具體實現的方法了。我們只需要了解，橢圓加密方程和RSA裡的大數模組都有某種同態的特性。
Pederson Commitment （Pederson承諾）
繼續回到隱藏交易量的話題。如果A有100個幣的餘額，付10個幣給B，那麼這筆交易大概長這樣：
結合上文提到的加法同態，如果我們有一個加法同態的加密方法E，我們就可以把這筆交易轉化成：
只要第一個數等於後兩個數之和，一個旁觀者到頭來也不會看到交易量，但是又不得不承認A真的分了一部分錢給B，然後還有一部分錢又退回給了A。這個方法叫做Pederson Commitment（Pederson承諾），隱藏了數據本身，但是證明了數據的關係。
負數漏洞
讀到這裡，有些朋友就會發現一個天大的漏洞：雖然Pederson承諾證明了數字之間的關係，但是並沒有限制任何數字的取值區間！那也就說，A就可以使壞，提交一筆交易，說自己要付-100個幣給B，然後「找」給自己200個幣，這樣一來一去，等式還是成立的。A就可以藉此無限印鈔，從而摧毀整個系統。
怎麼去避免負數的存在？在Pederson承諾之餘，我們還需要另外一組證明來證明所有交易裡的數字都是正數。換句話來說，所有交易裡的數字，都被限制在0到2^256（正整數最大值）的區間（Range Proof）。
聽起來似乎不難，最簡單的方法無疑就是這幾個數字全部公開出去。但是這就違背了隱藏交易量的前提。所以我們必須得找到另一種證明方法，即不能暴露原始數字，又要證明他們的特性（取值在0～2^256）。聽起來是不是在點題了？先不要急，我們再看另一個問題。
所有權漏洞
在我們繼續深入研究之前，我想快速的指出一下，其實這個協議現在還有個天大的漏洞：所有權不明。對比特幣了解的朋友們可能會知道，在創建一個比特幣交易的時候，是需要提供輸入交易的UTXO Txid的，這樣可以快速的驗證，準備付款給B的A是不是真的有這筆錢。但是現在，至始至終我們都沒有提及任何關於指向前一筆交易的內容。也就是說，因為全網不知道A花了多少錢，所以A純粹就可以把input的數字改的異想天開，改成幾千幾萬，然後再全部打給自己，給自己偷偷鑄幣。如何解決這個問題？有兩種方案。第一種方案是繼續引入比特幣的交易機制，把上一筆私密交易的輸出當作交易的輸入。這種思路有點像問題的轉換，我這筆交易用上筆交易的結果，那麼只要上筆交易沒問題，我這筆交易也沒有問題。
這是一個雞和蛋的問題，如何創造出第一筆沒有問題的私密交易呢？我們可以通過一種特殊交易，把普通的幣轉換成私密的輸出。這種交易的輸入是一個存在的交易id（比特幣UTXO），然後輸出就變成了隱私的輸出。這樣我們就變出了最早的蛋來。（ZCash的shielded transaction就是這個原理）第二種方案是證明A的輸入真正屬於A。像類似於Ethereum一類的系統裡，都有一個世界態（World State）的概念。世界態就是當前整個鏈上所有用戶和智能合約的餘額和狀態。一般一個完整的節點都會保留整個世界態（大小很大），而輕節點則只需要保存世界態的Merkle Commit。
在提交了Pederson承諾和區間證明之外，我們額外再提供一個證明，證明交易輸入的數字和原來的世界態裡A的餘額是相符的。我們可以用Merkle Proof來實現這個證明。但是如果我們直接提交了Merkle Proof，所有旁觀者都能看到A的交易輸入了，那又違反了私密交易的前提。所以再次點題：我們還是需要借用上文提到的神秘的算法——既可以隱藏住謎底本身（A的餘額），但又可以證明這個數字真的屬於世界態當中。ZCash：全部匿名當CT的概念被提出來之後，很多人不滿於現狀，不禁感慨：如果連自己的名字都能隱藏起來就好了。於是ZeroCoin/ZeroCash的概念就被提出來了：基於CT，但是額外新增了新的機制，可以把交易的用戶都匿名起來。這下在一邊吃瓜的旁觀者C真的就一臉懵逼了，看到網絡中一串亂碼飄過，但是完全不知道是個啥，但是又不得不相信是真的。ZCash是基於ZeroCoin/ZeroCash協議實現的一個數字貨幣，可以達到全匿名交易。過多的介紹我在這就不敘述了，不過依舊就是依靠著老幾樣密碼學的工具：Pederson承諾，區間證明，Merkle證明，還有我們一直在提的黑魔法：不會暴露答案本身的證明。千呼萬喚始出來，我們終於要講到重頭戲了：這種不會暴露答案本身的證明方式就叫做零知識證明。零知識證明（zkSNARK）相信看完上文，大家已經對我們想要解決的問題大概有所理解了。我們想要證明數字之間的關係，比如0 <= a <= 2^256，或者SHA256(x) = y。但是我們又不想暴露出這幾個數字來，比如說前文的a和x。如何構建一套系統來實現這點呢？在講這個話題之前，我想把思路變一變，把這個話題拆分成兩個部分：零知識（zk）和證明（SNARK）。和往常一樣，我們先講定義和應用，後面再說如何實現。證明（SNARK）我們先從證明入手。SNARK的全稱是Succinct Non-interactive ARgument of Knowledge。這個名詞由三個維度組成：
簡短（Succinct）：證明本身要足夠簡短，最好驗證證明是O(logN)甚至是O(1)的複雜度。無交互性（Non-interactive）：整體流程沒有任何交互，也就是說證明方可以扔出一大串亂碼往你桌上一拍然後就走人，你之後再去驗證這串亂碼就可以驗證他的證明。知識的表達（Argument of Knowledge）：這玩意比較晦澀難懂。不過大概的意思就是說你要證明的東西得是能表達知識的（Proof of Knowledge）。關於PoK的證明又涉及到一個更加抽象的抽取器（Extractor）的概念，具體的內容可以參照郭宇老師的文章。不過一句話總結就是，你證明的東西是有價值的，通過計算得到的，而不是亂七八糟別的東西。看了定義之後，我們會發現，光是能實現SNARK就已經非常強了，尤其是在簡短這一點上。我們馬上可以想到一個應用：如果某個第三方機構存了大量（PB級別）的數據在自己的資料庫裡。假如政府機構想要去審計他們的資料庫，確保每個數據點都沒有問題，正常情況下可能得一行一行的看，把每個PB的數據都看完，看到天荒地老。這個時候突然SNARK橫空出世，通過O(1)或者O(logN)的大小和時間就充分的證明了這個龐大的資料庫裡每個數據都沒有任何問題，想想都有點激動。一般人覺得這是完全不可能的：怎麼可以憑藉幾個數字就驗證了幾千萬個數字的準確性呢？留下懸念，後面再講。零知識（zk）我們再回歸到零知識（zero knowledge）上來。其實零知識只是在這個SNARK證明的基礎上又額外多了一個要求：整個證明本身不能暴露任何關於要證明的謎底有關的數據。零知識這個概念的官方定義又是非常晦澀難懂的，引入了一個模擬器（Simulator）的概念。詳細的介紹還是可以去參考郭宇老師的文章，我這兒就一筆帶過了。一句話總結就是：一個再聰明的黑客，怎麼瞅著零知識的證明，都沒法提取出任何和答案本身有關的信息來。回到這個政府審計資料庫的概念上，我們可以假設這個資料庫是公司的納稅情況。政府一定要確定納稅的數據一定要準確無誤，但是對於企業來說，他們並不想讓審查員看到他們每天的業務流水，因為也許涉及商業機密。這個時候區區一個SNARK就不夠了，我們需要zkSNARK才能夠實現：既可以證明我如實的交了稅，又不給你看到我每一筆交易的詳細信息。零知識證明的應用有了zkSNARK之後，我們可以做什麼呢？第一件事，就是可以把上文講的私密交易（Confidential Transaction）給實現了。ZCash的私密交易機制就是基於zkSNARK之上實現的。這樣一下，數字貨幣交易就變得安全了很多。第二件事，我們可以用這個技術來更好的解決區塊鏈效率的問題。現在目前區塊鏈Scaling的方法無疑是幾種：犧牲共識強度增加出塊速度，啟用側鏈，或者類似於Lightning一樣的線下點對點通道。
其實其中還有一個想法叫做Rollup。Rollup的概念大概就是，主鏈的負荷太大了， 於是我們就多開幾個小伺服器，也可以接收交易，做一做交易的認證，然後再批量性的把一段時間內累積下來的交易全部更新到主鏈上去。但是如果這個更新過程仍然需要向主鏈發送大批量的交易信息，這個Rollup的意義就不存在了，並不會減少任何主鏈的負荷。這個時候SNARK就派上用場了：通過SNARK（可以zk，也可以不要），Rollup伺服器就可以用非常簡短的證明提交給主鏈，證明一大批的交易都沒有問題，主鏈只需要根據最後的結果增加減少一些UTXO就完事了。通過ZK Rollup，我們可以大大的減少主鏈的負荷，把更多的驗證外包到別處去。 第三件事，我們可以真正實現去第三方的交易。
假設A在做機器學習方面的研究，但是並沒有很好的電腦，於是她打算把訓練模型的任務外包給B。過了三天之後，B告訴A他跑完了，需要讓A先付錢再給她提供訓練完的模型。A擔心B並沒有誠實的訓練模型，而是隨便生成了點隨機數打了個包，所以想讓B先把模型給A驗證通過了再付錢。B擔心A拿到模型之後偷偷抄走了模型，然後不給錢直接把他拉黑。面對這類的問題，傳統的解決方法是委託第三方，或者設計智能合約在鏈上來完成數據和貨幣的驗證交換。現在有了zkSNARK，B可以直接向A提交一個模型訓練的zkSNARK，證明他真的老老實實的跑了三天，並沒有在作弊。A快速驗證通過了之後，就可以放心的把錢打過去了。第四件事，我們可以徹底做到數據所有權的轉移。
假設銀行的帳戶餘額資料庫是一個sql table，那麼一億客戶就會有一億行記錄。每年銀行需要花不少成本來維護這麼大的數據系統。如果每個人都可以把屬於自己的那一行記錄搬運到本地，自己維護自己的帳戶數據，那麼銀行一分錢都不用花。之所以銀行不去這麼做，是因為用戶極有可能為了利益篡改自己的數據，把100塊變成100萬。zkSNARK恰恰可以保證數據本身不會有問題。我們可以構想出一個分布式銀行，每個人的存款餘額都存在自己的電腦裡面。當A想轉帳給B的時候，她需要向全網提交一個證明她帳上餘額正確扣款的zkSNARK，這樣就確保了A誠實的把轉帳金額從自己的餘額裡扣除了。B進帳的時候也會對應提交一個餘額增加的zkSNARK。我們可以把這個概念應用到所有的領域裡，社交網絡，銀行，健康，金融審計，企業納稅，等等。通過zkSNARK，服務提供商不需要為大量數據的存儲而買單，使用者也不需要擔心自己的隱私被人偷了去。未完待續篇幅原因，這次就寫到這兒。想必看到這裡，大家對為什麼需要零知識證明，和零知識證明到底有多強大，有了一個更加深入的了解。下一篇開始，我會寫的更加深入一點，主要討論一下zkSNARK具體的構造。PS：本文中零知識證明和zkSNARK交替使用。但其實zkSNARK只是零知識證明協議中比較經典的一個，還有許許多多別的協議在後文也會介紹。
責任編輯：李萍萍 /