零知識證明學習筆記：背景與起源_OIN

副標題或摘要：斯坦福學霸的零知識證明學習筆記

本文作者東澤，來自安比技術社區的小伙伴，目前就讀于斯坦福大學，研究方向密碼學，本系列文章來源于作者在斯坦福著名的課程《CS251:Cryptocurrenciesandblockchaintechnologies》上的學習筆記，該課程授課老師是密碼學大拿DanBoneh。

上個學期在斯坦福跟著DanBoneh學習了區塊鏈和數字貨幣相關的技術。和以往的課程不同的是，今年的課程新添加了一個章節，叫做零知識證明。萌萌的Dan和他的大神phdBenFisch給我們輪流上課，花了兩周時間講完了零知識的起源、概念和zkSNARK的實現。

這兩天考完期末考試，復習的過程中在腦海中再三回味整堂課，覺得最精彩的部分還是零知識證明。想著最近趁著假期總結一下，分享給大家。

前言

寫完第一稿之后，分享給朋友Proofread的時候，發現很多朋友反饋到說，背景知識不太夠。所以我在開始之前額外添加了這一章節，標注了一下為了能讀懂這篇文章所需的背景閱讀：

MerkleTree/MerkleProof:https://blog.csdn.net/wo541075754/article/details/54632929

比特幣的交易:https://blog.csdn.net/liduanwh/article/details/81141972

UTXO模型:https://www.jianshu.com/p/02fd289e8853

一些基本的加密解密概念:https://www.jianshu.com/p/f7c729a41c9f

讀完了前言之后，我們就可以開始

正文了。

要說零知識證明真正火熱的出現在大家的視野里，其實還要從比特幣開始說起。

比特幣的不足

如果熟悉比特幣的話，大家應該會知道，在比特幣網絡上，每一筆交易都是公開的。

如果A要付給B一筆錢，那么A就會拿著大喇叭向全網公布，她要創建一筆新的交易，并且這個交易的受益人是B的公鑰，或者是公鑰的哈希值。B只要看到了這筆交易，就可以用自己的私鑰簽署一份數字簽名，證明自己真的是這個公鑰的主人，從而花掉這筆錢。

當A提交了付錢給B的這筆交易后，作為一個網絡上的旁觀者M，她只能看到一串亂碼地址aaaaa要付x個幣給一串亂碼地址bbbbb。隨后當B再打錢給C的時候，他也只能看到bbbbb打了一筆錢給ccccc。我們可以看到比特幣里的交易是有很強的連接性的。雖然不知道誰打錢給了誰，但是我們可以順藤摸瓜找到很多條交易鏈條。

Polygon開源零知識證明系統Plonky2:8月16日消息，Polygon宣布開源零知識證明系統Plonky2，另外，STARK證明器Starky也是開源的。Plonky2由Polygon于今年1月份公布，Plonky2是一種遞歸SNARK，并且與以太坊原生兼容，結合了PLONK和FRI，具有快速證明和無可信設置。[2022/8/16 12:28:58]

如果每個用戶都只是乖巧的來回打錢，比特幣其實還是比較安全的。

一旦有用戶看破了，不想玩了，想去交易所套現了，那么這一整條鏈的交易信息都會被暴露。交易所往往都有KYC政策，每個數字貨幣和法幣進行兌換的用戶要進行實名制認證。一旦C從ccccc這個地址提款跑路了，那么交易所就掌握了bbbbb曾經打錢給C的事實。如果C涉嫌洗錢，這個時候只需要靜靜等待B套現出來，然后一把抓住。

美國現在已經有很多公司在做比特幣上的交易鏈條分析，比如Chainalysis。

想必說到這里，大家都能感受到比特幣的不足了：隨機生成的收款公鑰只是一個假象，一旦在哪里實名制認證了，把網名和實名聯系起來了，那么之前在網上所有的所作所為也就一覽無余，毫無隱私可言。這就好比有人用網名在貼吧上發帖子噴人，然后被人用密保找到了手機號，再用手機號找到了注冊的實名，從而被人肉是一個道理。

匿名與假名

我們對于隱私的理解，其實分兩種。

第一種是匿名，意思是用戶不用透露任何和自己相關的信息，好比是學校的表白墻，你永遠無法知道到底是誰寫了上去，反正字就是寫在了上面。

第二種是假名，意思是用戶通過自己創造的假名來發表信息，好比是貼吧，如果你不了解這個用戶，你無法建立網名到實名的聯系，你也就不知道發帖的人是誰。

這么分析一看，比特幣其實是一種假名機制：每個用戶都會隨機生成自己的公鑰，并且通過公鑰地址來收款。這就好比是A/B/C/D四個人分別化名為小明/小紅/二狗/小剛在網上匿名交易，只要D一旦在任何一個環節暴露出了自己的身份，那么小明/小紅/二狗和D之間的關系就會馬上暴露出來。

我們對于如何增強比特幣的保密性，可以從這兩種方法來討論。

增加隱秘性的方法

以太坊生態零知識協議Semaphore發布V2版本:7月7日消息，以太坊生態針對開發者的零知識協議 Semaphore 推出 V2 版本，更新內容包括不再需要擁有 EdDSA 私鑰，從而實現更簡單的電路（circuit）和更高效的零知識證明生成；用于身份承諾和 Merkle 樹的哈希函數從 MiMC 遷移到 Poseidon，將證明時間減半并提高了 Gas 效率；合約模塊化、三個新的 JavaScript 庫等。

Semaphore 最早由以太坊社區成員 Kobi Gurkan、Koh Wei Jie 和 Barry Whitehat 提出，在 2019 年發布 V1 版，可以讓以太坊用戶可以證明他們的群組成員身份，并在不透露原始身份的情況下發送諸如投票或支持的信號。Semaphore 不是面向用戶的應用程序，旨在為以太坊開發人員提供強大而簡單的工具，以使用私有憑據構建 DApp。[2022/7/7 1:57:35]

CoinJoin

既然A給B付錢會被人看到，C給D付錢也會被人看到，有人就想到了說那索性把ABCD這四個人全部扔到一筆交易里面去。因為比特幣的交易可以多個輸入輸出，所以一個旁觀者會看到一個交易里，aaaaa和ccccc都往里面打了x個幣，然后bbbbb和ddddd收款。這樣一來，就算交易所得知了這幾個地址分別對應ABCD四人，也很難分辨到底誰收了誰的錢。

如果兩組交易還是太好辨認怎么辦？兩個不夠混四個，四個不夠混八個，以此類推。把各種人的交易結合在一起，混淆視聽，讓人無法追蹤。這就是CoinJoin。

CoinJoin的弊端是什么？其實混合多筆交易并不能完美的杜絕被人順藤摸瓜，只能說在概率上減低了被一路摸上來的幾率。而且還有一個很重要的一點，如果要混合AB與CD的交易，那么他們的交易量一定要相同。如果A付給B一萬個幣，C付給D一個幣，我們只需要看輸入和輸出，就可以馬上把一筆CoinJoin交易拆散成兩個獨立的交易。所以混搭相似交易額度的交易，也是CoinJoin在實現的時候一個不容忽視的難點。

如果用上文的分類來看的話，CoinJoin只是比特幣現有系統的一個騷操作，它的本質仍然是假名機制。

ConfidentialTransaction

既然隱藏我是誰那么麻煩，那么人們就開始動腦思考：如果不隱藏參與交易的公鑰，我們還可以隱藏交易的額度。A給B打錢的時候，就算B被暴露了，全網也不會得知A究竟給了B多少錢。

動態 | 德勤在企業區塊鏈產品中添加零知識證明隱私技術:德勤（Deloitte）周二在阿姆斯特丹舉行的ZKProof社區活動上宣布，已在其企業區塊鏈產品中增加了零知識證明隱私技術。德勤與以色列的零知識證明專家QEDIT合作，幫助用戶控制區塊鏈共享有關他們所獲得的證書和資格的數據。（coindesk）[2019/10/29]

如果這步操作能實現，那么我們甚至就可以用比特幣發工資了，大家只能看到你每個月工資到賬，但是并不知道你賺了多少錢。

想要具體實現的方法，我們先要了解一種特殊的加密算法：同態加密。

一句話概括的話，同態加密就是一種特殊的加密算法，可以讓密文保持原有的數學特性。

我們可以假設有一個加密方法E，如果E是加法同態的話，那么E(a)+E(b)=E(a+b)。反之如果乘法同態的話，那么E(a)xE(b)=E(axb)。

介于這篇文章是講zkp的科普文，我們就不詳細了解具體實現的方法了。我們只需要了解，橢圓加密方程和RSA里的大數模組都有某種同態的特性。

PedersonCommitment

繼續回到隱藏交易量的話題。如果A有100個幣的余額，付10個幣給B，那么這筆交易大概長這樣：

結合上文提到的加法同態，如果我們有一個加法同態的加密方法E，我們就可以把這筆交易轉化成：

只要第一個數等于后兩個數之和，一個旁觀者到頭來也不會看到交易量，但是又不得不承認A真的分了一部分錢給B，然后還有一部分錢又退回給了A。這個方法叫做PedersonCommitment，隱藏了數據本身，但是證明了數據的關系。

負數漏洞

讀到這里，有些朋友就會發現一個天大的漏洞：雖然Pederson承諾證明了數字之間的關系，但是并沒有限制任何數字的取值區間！那也就說，A就可以使壞，提交一筆交易，說自己要付-100個幣給B，然后“找”給自己200個幣，這樣一來一去，等式還是成立的。A就可以借此無限印鈔，從而摧毀整個系統。

怎么去避免負數的存在？在Pederson承諾之余，我們還需要另外一組證明來證明所有交易里的數字都是正數。換句話來說，所有交易里的數字，都被限制在0到2^256的區間。

聲音 | CFTC專員：繼續看好隱私幣的零知識證明技術:據AMBCrypto消息，近日，美國商品期貨交易委員會（CFTC）專員Brian Quintenz接受采訪時表示，盡管存在AML（反洗錢）的問題，但對零知識證明協議持積極態度。政府接受任何形式的隱私幣的可能性很小，加密貨幣交易平臺也禁止用戶進行不受監控的交易，這也是為什么Monero沒有在Coinbase上線的原因。[2019/6/28]

聽起來似乎不難，最簡單的方法無疑就是這幾個數字全部公開出去。但是這就違背了隱藏交易量的前提。所以我們必須得找到另一種證明方法，即不能暴露原始數字，又要證明他們的特性。聽起來是不是在點題了？先不要急，我們再看另一個問題。

所有權漏洞

在我們繼續深入研究之前，我想快速的指出一下，其實這個協議現在還有個天大的漏洞：所有權不明。

對比特幣了解的朋友們可能會知道，在創建一個比特幣交易的時候，是需要提供輸入交易的UTXOTxid的，這樣可以快速的驗證，準備付款給B的A是不是真的有這筆錢。

但是現在，至始至終我們都沒有提及任何關于指向前一筆交易的內容。也就是說，因為全網不知道A花了多少錢，所以A純粹就可以把input的數字改的異想天開，改成幾千幾萬，然后再全部打給自己，給自己偷偷鑄幣。

如何解決這個問題？有兩種方案。

第一種方案是繼續引入比特幣的交易機制，把上一筆私密交易的輸出當作交易的輸入。這種思路有點像問題的轉換，我這筆交易用上筆交易的結果，那么只要上筆交易沒問題，我這筆交易也沒有問題。

這是一個雞和蛋的問題，如何創造出第一筆沒有問題的私密交易呢？

我們可以通過一種特殊交易，把普通的幣轉換成私密的輸出。這種交易的輸入是一個存在的交易id，然后輸出就變成了隱私的輸出。這樣我們就變出了最早的蛋來。

第二種方案是證明A的輸入真正屬于A。像類似于Ethereum一類的系統里，都有一個世界態的概念。世界態就是當前整個鏈上所有用戶和智能合約的余額和狀態。一般一個完整的節點都會保留整個世界態，而輕節點則只需要保存世界態的MerkleCommit。

動態 | 0x 協議推出基于零知識證明技術的 StarkDEX 測試版，每秒可處理逾 550 筆交易:去中心化交易協議 0x 宣布推出去中心化交易基礎設施 StarkDEX，并提供了 Alpha 測試版供模擬交易。StarkDEX 由 0x 與零知識證明技術開發公司 StarkWare 合作開發，目的是使用 STARKs 技術突破非監管交易的無形限制，使加密貨幣交易所為用戶提供大規模而無對手風險的交易。0x 表示目前 StarkDEX 每區塊最多可批量處理 8000 筆交易，每秒可處理逾 550 筆交易，手續費成本則降低 200 倍。[2019/6/4]

在提交了Pederson承諾和區間證明之外，我們額外再提供一個證明，證明交易輸入的數字和原來的世界態里A的余額是相符的。我們可以用MerkleProof來實現這個證明。

但是如果我們直接提交了MerkleProof，所有旁觀者都能看到A的交易輸入了，那又違反了私密交易的前提。所以再次點題：我們還是需要借用上文提到的神秘的算法——既可以隱藏住謎底本身，但又可以證明這個數字真的屬于世界態當中。

ZCash：全部匿名

當CT的概念被提出來之后，很多人不滿于現狀，不禁感慨：如果連自己的名字都能隱藏起來就好了。

于是ZeroCoin/ZeroCash的概念就被提出來了：基于CT，但是額外新增了新的機制，可以把交易的用戶都匿名起來。這下在一邊吃瓜的旁觀者C真的就一臉懵逼了，看到網絡中一串亂碼飄過，但是完全不知道是個啥，但是又不得不相信是真的。

ZCash是基于ZeroCoin/ZeroCash協議實現的一個數字貨幣，可以達到全匿名交易。過多的介紹我在這就不敘述了，不過依舊就是依靠著老幾樣密碼學的工具：Pederson承諾，區間證明，Merkle證明，還有我們一直在提的黑魔法：不會暴露答案本身的證明。

千呼萬喚始出來，我們終于要講到重頭戲了：這種不會暴露答案本身的證明方式就叫做零知識證明。

零知識證明

相信看完上文，大家已經對我們想要解決的問題大概有所理解了。

我們想要證明數字之間的關系，比如0<=a<=2^256，或者SHA256(x)=y。但是我們又不想暴露出這幾個數字來，比如說前文的a和x。如何構建一套系統來實現這點呢？

在講這個話題之前，我想把思路變一變，把這個話題拆分成兩個部分：零知識和證明。

和往常一樣，我們先講定義和應用，后面再說如何實現。

證明

我們先從證明入手。

SNARK的全稱是SuccinctNon-interactiveARgumentofKnowledge。這個名詞由三個維度組成：

簡短：證明本身要足夠簡短，最好驗證證明是O(logN)甚至是O(1)的復雜度。

無交互性：整體流程沒有任何交互，也就是說證明方可以扔出一大串亂碼往你桌上一拍然后就走人，你之后再去驗證這串亂碼就可以驗證他的證明。

知識的表達：這玩意比較晦澀難懂。不過大概的意思就是說你要證明的東西得是能表達知識的。關于PoK的證明又涉及到一個更加抽象的抽取器的概念，具體的內容可以參照郭宇老師的文章。不過一句話總結就是，你證明的東西是有價值的，通過計算得到的，而不是亂七八糟別的東西。

看了定義之后，我們會發現，光是能實現SNARK就已經非常強了，尤其是在簡短這一點上。

我們馬上可以想到一個應用：如果某個第三方機構存了大量的數據在自己的數據庫里。假如政府機構想要去審計他們的數據庫，確保每個數據點都沒有問題，正常情況下可能得一行一行的看，把每個PB的數據都看完，看到天荒地老。這個時候突然SNARK橫空出世，通過O(1)或者O(logN)的大小和時間就充分的證明了這個龐大的數據庫里每個數據都沒有任何問題，想想都有點激動。一般人覺得這是完全不可能的：怎么可以憑借幾個數字就驗證了幾千萬個數字的準確性呢？

留下懸念，后面再講。

零知識

我們再回歸到零知識上來。

其實零知識只是在這個SNARK證明的基礎上又額外多了一個要求：整個證明本身不能暴露任何關于要證明的謎底有關的數據。零知識這個概念的官方定義又是非常晦澀難懂的，引入了一個模擬器的概念。詳細的介紹還是可以去參考郭宇老師的文章，我這兒就一筆帶過了。一句話總結就是：一個再聰明的黑客，怎么瞅著零知識的證明，都沒法提取出任何和答案本身有關的信息來。

回到這個政府審計數據庫的概念上，我們可以假設這個數據庫是公司的納稅情況。政府一定要確定納稅的數據一定要準確無誤，但是對于企業來說，他們并不想讓審查員看到他們每天的業務流水，因為也許涉及商業機密。這個時候區區一個SNARK就不夠了，我們需要zkSNARK才能夠實現：

既可以證明我如實的交了稅，又不給你看到我每一筆交易的詳細信息。

零知識證明的應用

有了zkSNARK之后，我們可以做什么呢？

第一件事，就是可以把上文講的私密交易給實現了。ZCash的私密交易機制就是基于zkSNARK之上實現的。這樣一下，數字貨幣交易就變得安全了很多。

第二件事，我們可以用這個技術來更好的解決區塊鏈效率的問題。現在目前區塊鏈Scaling的方法無疑是幾種：犧牲共識強度增加出塊速度，啟用側鏈，或者類似于Lightning一樣的線下點對點通道。

其實其中還有一個想法叫做Rollup。Rollup的概念大概就是，主鏈的負荷太大了，于是我們就多開幾個小服務器，也可以接收交易，做一做交易的認證，然后再批量性的把一段時間內累積下來的交易全部更新到主鏈上去。但是如果這個更新過程仍然需要向主鏈發送大批量的交易信息，這個Rollup的意義就不存在了，并不會減少任何主鏈的負荷。這個時候SNARK就派上用場了：通過SNARK，Rollup服務器就可以用非常簡短的證明提交給主鏈，證明一大批的交易都沒有問題，主鏈只需要根據最后的結果增加減少一些UTXO就完事了。通過ZKRollup，我們可以大大的減少主鏈的負荷，把更多的驗證外包到別處去。

第三件事，我們可以真正實現去第三方的交易。

假設A在做機器學習方面的研究，但是并沒有很好的電腦，于是她打算把訓練模型的任務外包給B。過了三天之后，B告訴A他跑完了，需要讓A先付錢再給她提供訓練完的模型。A擔心B并沒有誠實的訓練模型，而是隨便生成了點隨機數打了個包，所以想讓B先把模型給A驗證通過了再付錢。B擔心A拿到模型之后偷偷抄走了模型，然后不給錢直接把他拉黑。

面對這類的問題，傳統的解決方法是委托第三方，或者設計智能合約在鏈上來完成數據和貨幣的驗證交換。現在有了zkSNARK，B可以直接向A提交一個模型訓練的zkSNARK，證明他真的老老實實的跑了三天，并沒有在作弊。A快速驗證通過了之后，就可以放心的把錢打過去了。

第四件事，我們可以徹底做到數據所有權的轉移。

假設銀行的賬戶余額數據庫是一個sqltable，那么一億客戶就會有一億行記錄。每年銀行需要花不少成本來維護這么大的數據系統。如果每個人都可以把屬于自己的那一行記錄搬運到本地，自己維護自己的賬戶數據，那么銀行一分錢都不用花。之所以銀行不去這么做，是因為用戶極有可能為了利益篡改自己的數據，把100塊變成100萬。

zkSNARK恰恰可以保證數據本身不會有問題。我們可以構想出一個分布式銀行，每個人的存款余額都存在自己的電腦里面。當A想轉賬給B的時候，她需要向全網提交一個證明她賬上余額正確扣款的zkSNARK，這樣就確保了A誠實的把轉賬金額從自己的余額里扣除了。B進帳的時候也會對應提交一個余額增加的zkSNARK。

我們可以把這個概念應用到所有的領域里，社交網絡，銀行，健康，金融審計，企業納稅，等等。通過zkSNARK，服務提供商不需要為大量數據的存儲而買單，使用者也不需要擔心自己的隱私被人偷了去。

未完待續

篇幅原因，這次就寫到這兒。想必看到這里，大家對為什么需要零知識證明，和零知識證明到底有多強大，有了一個更加深入的了解。

下一篇開始，我會寫的更加深入一點，主要討論一下zkSNARK具體的構造。

PS：本文中零知識證明和zkSNARK交替使用。但其實zkSNARK只是零知識證明協議中比較經典的一個，還有許許多多別的協議在后文也會介紹。

更多閱讀

如果想要了解更多本文中講到的內容，我收集了一個ReadingList，放在下面。有興趣的朋友可以讀讀。

郭宇老師的零知識證明:https://www.jianshu.com/p/38ab873ae8ce

斯坦福的課件與課后閱讀:http://cs251.stanford.edu/syllabus.html

ZCash的構造:https://www.jianshu.com/p/4db439c63a96

CoinJoin:https://en.bitcoin.it/wiki/CoinJoin

ConfidentialTransaction:https://www.jianshu.com/p/22664259dee3

Tags：ARKNAROIN比特幣Yearn Shark FinanceNarwhale.financeCoinvise量子比特幣創始人

火星幣