本文作者東澤，來自安比技術社區的小伙伴，目前就讀於斯坦福大學，研究方向密碼學，本系列文章來源於作者在斯坦福著名的課程《CS 251: Cryptocurrencies and blockchain technologies》上的學習筆記，該課程授課老師是密碼學大拿Dan Boneh。
本文作者東澤，來自安比技術社區的小伙伴，目前就讀於斯坦福大學，研究方向密碼學，本系列文章來源於作者在斯坦福著名的課程《CS 251: Cryptocurrencies and blockchain technologies》上的學習筆記，該課程授課老師是密碼學大拿Dan Boneh。
前言
前言
前言
一級標題
讀完了前言之後，我們就可以開始正文了。
一級標題
一級標題
一級標題
比特幣的不足
如果熟悉比特幣的話，大家應該會知道，在比特幣網絡上，每一筆交易都是公開的。
如果A要付給B一筆錢，那麼A就會拿著大喇叭向全網公佈，她要創建一筆新的交易（Tx），並且這個交易的受益人是B的公鑰（P2PK），或者是公鑰的哈希值（P2PKH）。 B只要看到了這筆交易，就可以用自己的私鑰簽署一份數字簽名，證明自己真的是這個公鑰的主人，從而花掉這筆錢。
當A提交了付錢給B的這筆交易後，作為一個網絡上的旁觀者M，她只能看到一串亂碼地址aaaaa要付x個幣給一串亂碼地址bbbbb。隨後當B再打錢給C的時候，他也只能看到bbbbb打了一筆錢給ccccc。我們可以看到比特幣裡的交易是有很強的連接性的。雖然不知道誰打錢給了誰，但是我們可以順藤摸瓜找到很多條交易鏈條。
美國現在已經有很多公司在做比特幣上的交易鏈條分析，比如Chainalysis。
一級標題
一級標題
一級標題
匿名（Anonymous） 與假名（Pseudonymous）
我們對於隱私的理解，其實分兩種。
一級標題
一級標題
二級標題
CoinJoin
二級標題
二級標題
二級標題
二級標題
Confidential Transaction（私密交易/CT）
二級標題
Confidential Transaction（私密交易/CT）
既然隱藏我是誰那麼麻煩，那麼人們就開始動腦思考：如果不隱藏參與交易的公鑰，我們還可以隱藏交易的額度。 A給B打錢的時候，就算B被暴露了，全網也不會得知A究竟給了B多少錢。
如果這步操作能實現，那麼我們甚至就可以用比特幣發工資了，大家只能看到你每個月工資到賬，但是並不知道你賺了多少錢。
想要具體實現的方法，我們先要了解一種特殊的加密算法：同態加密。
一句話概括的話，同態加密就是一種特殊的加密算法，可以讓密文保持原有的數學特性。
我們可以假設有一個加密方法E，如果E是加法同態的話，那麼E(a) + E(b) = E(a+b)。反之如果乘法同態的話，那麼E(a) x E(b) = E(axb)。
介於這篇文章是講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就是這個原理）
在提交了Pederson承諾和區間證明之外，我們額外再提供一個證明，證明交易輸入的數字和原來的世界態裡A的餘額是相符的。我們可以用Merkle Proof來實現這個證明。
ZCash：全部匿名
但是如果我們直接提交了Merkle Proof，所有旁觀者都能看到A的交易輸入了，那又違反了私密交易的前提。所以再次點題：我們還是需要藉用上文提到的神秘的算法——既可以隱藏住謎底本身（A的餘額），但又可以證明這個數字真的屬於世界態當中。
ZCash：全部匿名
ZCash是基於ZeroCoin/ZeroCash協議實現的一個數字貨幣，可以達到全匿名交易。過多的介紹我在這就不敘述了，不過依舊就是依靠著老幾樣密碼學的工具：Pederson承諾，區間證明，Merkle證明，還有我們一直在提的黑魔法：不會暴露答案本身的證明。
一級標題
一級標題
一級標題
零知識證明（zkSNARK）
在講這個話題之前，我想把思路變一變，把這個話題拆分成兩個部分：零知識（zk）和證明（SNARK）。
二級標題
二級標題
二級標題
證明（SNARK）
我們先從證明入手。SNARK的全稱是Succinct Non-interactive ARgument of Knowledge。這個名詞由三個維度組成：
簡短（Succinct）：證明本身要足夠簡短，最好驗證證明是O(logN)甚至是O(1)的複雜度。
無交互性（Non-interactive）：整體流程沒有任何交互，也就是說證明方可以扔出一大串亂碼往你桌上一拍然後就走人，你之後再去驗證這串亂碼就可以驗證他的證明。
知識的表達（Argument of Knowledge）
我們馬上可以想到一個應用：如果某個第三方機構存了大量（PB級別）的數據在自己的數據庫裡。假如政府機構想要去審計他們的數據庫，確保每個數據點都沒有問題，正常情況下可能得一行一行的看，把每個PB的數據都看完，看到天荒地老。這個時候突然SNARK橫空出世，通過O(1)或者O(logN)的大小和時間就充分的證明了這個龐大的數據庫裡每個數據都沒有任何問題，想想都有點激動。一般人覺得這是完全不可能的：怎麼可以憑藉幾個數字就驗證了幾千萬個數字的準確性呢？
二級標題
二級標題
二級標題
零知識（zk）
回到這個政府審計數據庫的概念上，我們可以假設這個數據庫是公司的納稅情況。政府一定要確定納稅的數據一定要準確無誤，但是對於企業來說，他們並不想讓審查員看到他們每天的業務流水，因為也許涉及商業機密。這個時候區區一個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快速驗證通過了之後，就可以放心的把錢打過去了。
zkSNARK恰恰可以保證數據本身不會有問題。我們可以構想出一個分佈式銀行，每個人的存款餘額都存在自己的電腦裡面。當A想轉賬給B的時候，她需要向全網提交一個證明她賬上餘額正確扣款的zkSNARK，這樣就確保了A誠實的把轉賬金額從自己的餘額裡扣除了。 B進帳的時候也會對應提交一個餘額增加的zkSNARK。
未完待續
未完待續
未完待續
更多閱讀
更多閱讀
更多閱讀
一級標題
斯坦福的課件與課後閱讀
