淺談零知識證明之二：簡短無交互證明（SNARK）_AND:ERK

本文作者東澤，來自安比技術社區的小伙伴，目前就讀于斯坦福大學，研究方向密碼學，本系列文章來源于作者在斯坦福著名的課程《CS251:Cryptocurrenciesandblockchaintechnologies》上的學習筆記，該課程授課老師是密碼學大拿DanBoneh。上一期文章發表之后，非常驚訝有那么多小伙伴讀完了表示喜歡。那么我們接著這期繼續吧！這次，我們專注的聊一聊SNARK。相信看完前一篇文章的朋友們會有一點很不解的地方：為什么我們可以如此簡短的創建一個證明，并且證明很長的信息呢？在上課前我也有這同樣的疑惑，甚至覺得這個是一個“黑科技”，不過相信大家看完這篇文章，就會知道如何去駕馭這個“黑科技”了。在詳細討論之前，我們得稍微嚴肅一點，系統性的學習一下SNARK的基本構造。SNARK的四步構造

因為SNARK的“黑科技”特性，想要構建一套簡短證明系統，其實流程是略微有些復雜的。總結一下一共可以分為四步，我們來一步一步詳細描述。第一步：確定有限域

在構造之前，我們先需要確定一個可以包含所有我們想要計算的數字的大小的一個有限域。用通俗易懂的話來說，我們需要選一個很大很大的數字p，確保這個數字比我們要解決的問題里的所有數字都大。如果以前了解過類似于RSA密碼學的朋友們可能對這個概念不陌生。有限域就是給我們所有數字加了一個天花板，確定了整個數學系統的計算空間，類似于在電腦里如果我們想創建一個存數字的變量，我們需要思考到底是需要一個uint32_t，還是一個uint64_t一樣。所有超過有限域的值，都會直接溢出之后再倒回去從0開始。在數學界，符合這個特性的計算空間其實有很多種，最常見的一種就是RSA算法里面用到的正整數求模一個大質數。上文說到的找到一個數字p，其實就是一個很大的質數，然后我們可以用它來生成一個計算空間。在確定計算空間之后，我們就可以真正開始SNARK的搭建了。第二步：構建數學運算電路

當我們找到一個數字空間之后，我們下一步要做的事情，就是要把我們想要證明解決的問題用數學運算電路表示出來。什么是數學運算電路呢？我們先來看一看傳統的邏輯電路。

上圖表述的是一個與非門的電路。先不用過多了解電路的用處，我們可以發現的是，兩組輸入信號分別通過了AND和OR這兩個基礎邏輯門。像AND和OR這樣的基礎邏輯門是邏輯電路的基礎模塊，通過拼加和堆疊我們可以實現任何復雜邏輯。數學運算電路也是同理，只不過基礎模塊從邏輯門變成了數學運算。因為加法和乘法是最基礎的數學運算，通過加法和乘法我們也可以近乎實現所有其他的運算方法，所以我們可以選用“加法門”和“乘法門”作為我們數學運算電路的基礎模塊。通過疊加運算門，我們可以搭建一個復雜多項式的“電路”。為了能更好的理解運算門，我們來試試看把上面的NAND門從邏輯電路轉換成數學運算電路。我們先來看AND門：AND其實很簡單，因為只有當Inp0和Inp1都是1的時候，AND的結果才會是1。我們很快發現，一個乘法門可以完美的代替AND門：只有當兩個輸入是1的時候，相乘得到的結果才會是1。解決了AND之后，我們來轉換NOT：NOT其實也非常簡單，因為輸入信號只會是0或者1，只要用1減去輸入的信號，得到的結果就是相反的了。注意有一個問題是，因為我們只有加法和乘法，所以如果需要實現減法的話，我們需要先把輸入信號乘上一個常數-1。

美國眾議院已獲得足夠票數通過旨在避免違約的債務上限協議:金色財經報道，美國眾議院已獲得足夠票數通過旨在避免違約的債務上限協議，目前投票仍在繼續。[2023/6/1 11:51:44]

經過如此轉換，我們就成功的把一個邏輯電路轉換為數字邏輯電路了。同時因為我們已經知道如何組建AND和NOT了，理論上我們就可以把這兩個部分模塊化，拼接任意的復雜邏輯出來。看到這里，你可能會覺得運算電路非常簡單，和邏輯電路轉化也非常直白。但是其實這是因為我們一直在假設運算電路的輸入和邏輯電路一樣，都是0或者1。在真實場景下，一個運算門的輸入值可能上限非常大。所以我們必須要想辦法約束我們運算電路的輸入，使其不僅能夠在功能性上和邏輯電路相同，并且在輸入取值上只可以取這兩個數字。但是怎么用運算門來表示這么一個關系呢？因為數學運算電路其實就是一個復雜的多項式，我們可以把這個問題轉化一下：能否創造出一個多項式，只有當一個輸入滿足的取值范圍的時候，才會輸出0？最后我們發現，有這么一個多項式可以滿足這個要求：

上面這串表達式的意思是，只有當數字n取值于這個范圍的時候，后面的多項式才會輸出0。也就是說，我們就可以把上文提到的Inp0和Inp1接到這個多項式轉換成的運算電路內，只要這個運算電路的輸出結果是0，那么我們就可以確信上文的NAND運算電路的輸出也是對的。有人可能會問，上文限制取值的多項式只能限制一個輸入，但是我們有兩個輸入，如何同時限制他們的取值范圍呢？其實答案很簡單，只需要把同樣的多項式復制一份，兩者加起來就好了。

有了這兩個電路之后，我們只要確定約束電路的輸出是0，那么NAND門電路就會正常運轉了。有一點需要注意的是，因為我們的邏輯門是從運算門搭建起來的，我們會發現其實邏輯運算非常的慢：任何邏輯運算至少得做一次乘法，然而熟悉計算機硬件的朋友們會知道，乘法其實是相對來說比較昂貴的運算。這樣一來有一點顛倒黑白的感覺，在計算機里邏輯運算是最便宜也是最簡單的計算，然而在數學運算電路里，邏輯運算反而是一個比較繁瑣的過程了。第三步：轉換為可證明數學運算電路

當我們有了數字運算電路這個概念之后，我們就可以把不同的電路模塊拼接起來，生成一個可以用作證明的運算電路出來。首先，我們先定義一下可以用作證明的數字運算電路C(x,w)，具體構造如下：

簡單的來說，這個電路C有兩組輸入。第一組輸入標記為x，我們稱之為公有輸入，也就是說所有人都會知道x的值。這個x一般來說表達了想要證明的問題的特性和一些固定的環境變量。第二組輸入標記為w，我們稱之為私密輸入，或者又稱之為witness。這一組數據就是真正提交證明的一方的謎底，只有證明的一方才會知道，其他人是不可以得之的。當我們有C這一個電路之后，我們的目標就是證明C(x,w)=0。換句話來說，在A和B已知數學運算電路C輸出為0，并且公有輸入為x的情況下，A需要證明她知道能夠構成這個輸出的私密輸入值w。如果我們把這個C(x,w)的概念代入上文提到的NAND門的例子里，我們會發現，光是NAND門不足以成為一個用做證明的電路。我們可以重新定義一下我們想證明的問題：如果我們已知一個NAND門的輸出為0，并且其中的一個輸入Inp0為1，A想證明她知道另一個輸入Inp1的值。這個證明的過程中，不僅要保證NAND門的輸出是對的，而且要保證所有的輸入值都取值在我們事先約定好的區間內。

Seed Club推出200萬美元“消費者加密加速器”計劃并開放第一批次申請:5月4日消息，加密社區Seed Club推出“消費者加密加速器”（The Consumer Crypto Accelerator），承諾向早期團隊投入200萬美元，其中第一批次申請現在開放2周（截止至太平洋時間5月15日23:59）。該計劃將于六月正式開始，在為期3個月的計劃中，通過申請的項目將獲得高達20萬美元的資金以及核心團隊、顧問和網絡的支持。[2023/5/4 14:41:40]

我們結合上面討論的方案，把NAND的電路輸出和我們的取值約束電路接在一起拼接成運算電路C，x為Inp0，w為Inp1，輸出我們約束為0，從而構成一個完整的NAND門私密輸入證明體系。當我們得到最后的證明電路C之后，我們可以計算出這個運算電路的復雜度。如果我們想知道一個數字運算電路C有多難算的時候，我們可以用里面有多少個運算門來描述它的復雜度。一般來說我們會用來表示。像是上面提到的NAND證明電路，大概是在10左右。在現實使用場景中，如果我們要把像SHA256這樣的復雜函數用數字運算電路來表示，可能會達到25000這么大。這也就是為什么真正落地的證明還是非常慢的原因。第四步：非交互簡短證明體系

當我們通過第三步得到了最終的證明電路C，還有對應的x和w之后，我們的準備工作已經做的差不多了。剩下來的事情，我們就可以交給SNARK算法來生成和驗證我們的證明了。首先，我們看看整個非交互式證明體系的官方定義。一個SNARK系統，往往由三個核心算法組成：Setup，Prove和Verify。生成算法Setup：Setup算法會把我們實現確定好的電路C拿進來進行一系列的預處理，然后生成兩組參數。Sp是給證明方的參數，Sv是給驗證方的。這些參數的用處就是方便雙方來生成和驗證簡短證明。一般來說，生成算法的復雜度和電路C的復雜度是等比例的，O(|C|)。

證明算法Prove：證明算法相比不用多講了，證明方會用Prove這個算法來生成一個證明，然后把這個證明發送給驗證方。Prove算法再生成證明的時候會用到幾乎所有的數據：預處理數據Sp，公有輸入x，還有私密輸入w。最后生成的證明的空間復雜度非常簡短：|Π|=O(log|C|)。

驗證算法Verify：驗證算法也非常的直白，驗證方會用Verify這個算法驗證我們收到的證明。這個算法會返回一個1/0的數值，代表驗證是否通過。驗證的過程中除了需要對方提供的證明，我們還需要預處理數據，還有公有輸入x。驗證的復雜度也非常小，一般來說是O(|x|+log|C|)。

數據：超7100萬枚XRP轉移到FTX交易所:11月7日消息，據WhaleAlert的數據，最近幾個小時有超過 7100 萬 XRP 流入 FTX 交易所。此舉是通過兩筆交易完成的：第一筆是價值16,631,186美元的 35,774,039 XRP，第二筆是價值 16,557,439 美元的 35,615,409 XRP，兩者都從未知錢包轉移到 FTX 交易所。[2022/11/7 12:28:24]

有了這三個算法之后，我們可以用很簡單的圖來描述一下整個證明體系。

證明方提交的這個證明可以充分說服驗證方，讓其相信證明方真的有這么一個秘密的w可以滿足C(x,w)=0。實例：私密交易的輸入輸出取值區間

讀過上一篇文章的朋友們應該還會記得，如果我們要進行私密交易的話，我們需要在交易最后附帶三組證明：第一組是Pederson承諾，證明了輸入和輸出之間的數學關系。第二組是區間證明，需要證明輸入和輸出的值全部取值于正整數的范圍。第三組是所有權證明，證明交易的發起人真的有這么多token作為輸入。Pederson承諾的實現我們已經在上一篇文章中討論過了。現在了解完簡短證明的四步構造，我們可以來看看如何具體實現區間證明。首先，我們需要找到一個合適的數學運算電路來描述我們想要證明的內容。假如我們有一個數字w，我們想要證明這個數字w不是一個負數，那么我們可以先辦法證明它一定會取值于正整數區間。因為考慮到計算機系統里的正整數一般不會超過256位，所以我們可以把問題弱化一下：證明一個數字w取值于0-2^256之間。

現在確定了要解決的問題之后，我們可以開始思考如何用加法和乘法來表達這個取值關系。還記得在前面的章節，當我們在講一個值n會取值在0和1之間的時候，我們用n*(n-1)=0來約束這個取值范圍。同理可得，如果我們想約束必須要取值于0和5之間的話，我們就可以用更長的一串乘法來約束它：

看到這里，大家可能心里已經知道如何約束這個w的值了：我們只要用同樣的辦法擴大這個等式，從(w-1)一直連續乘到(w-2^{256})，不就可以了？聽起來很簡單，但是細心的朋友會發現，這樣最后的電路里面將會有2^256個乘法門。光是這么多乘法，還沒有算加法，這個電路的復雜度已經是天文數字了。就算是跑Setup可能就不知道跑到猴年馬月，所以我們說這種約束的方法是不實際的。那還有什么方法來約束這個數字w的空間呢？我們可以巧妙借助二進制數的結構。既然我們想要規定w是個整數，并且大于0但小于2^256，那么我們就可以在二進制里，把w拆分成256位，然后分別約束每一位。這樣的話，我們最后得到的電路大小只會和這個數字有多少位成正比，而不會和這個數字的最大上限有關系。復雜度一下子就下來了一大個等級。具體是怎么實現的呢？我們首先把w拆分成256位：

報告：DEFI市場規模預計在2030年達到2311.9億美元:金色財經報道，Grand View Research最近發布的一份報告預測，到2030年，全球去中心化金融市場規模預計將達到2311.9億美元，從2022年到 2030年的復合年增長率為 42.5%，推動行業擴張的另一個因素是DeFi（去中心化金融）網絡上金融交易的透明度和實時結算程度。（prnewswire）[2022/9/22 7:12:57]

因為每一位都是二進制的，所以我們需要約束每一位的取值空間為0和1：

這個約束需要256份，每一份對應每一位。當我們把這些約束準備好之后，我們最后確定所有的位組在一起可以還原成原來的w：

我們把上文提及的256+1=257組約束電路全部拼接在一起，合并成一個輸出。最后生成的電路就是我們可以用來構建證明系統的電路C了。如果C的輸出為0，那么代表了輸入的數字一定要滿足：這個數字是一個正整數，可以被256位二進制數表達。這256位二進制數的確是二進制數。這256位二進制數全部拼在一起可以重新還原輸入進來的數字。

通過巧妙借助二進制的特性，我們就有一組大小適中的數學運算電路，可以調用Setup來準備生成后續的SNARK了。實例：私密交易輸入的所有權

解決了區間證明，我們來完成私密交易的最后一組證明：所有權證明，證明私密交易的輸入值合理。看過前一篇文章的朋友應該會知道，我們講了兩種私密交易所有權證明的體系：第一種方案是一筆交易可以直接引用上一筆交易的輸出，但是這會帶來雞和蛋的問題：難度在如何創造出第一筆私密交易來。第二種方案是在每一筆交易的下面附加另一個新的證明，證明交易發起的用戶的賬戶余額真的有那么多錢。我想著重講一下第二種證明方案，也就是證明交易發起者在世界狀態中的賬戶余額。在很多區塊鏈的場景中，整個世界的狀態就是一個巨大的賬本。賬本的每一行都記錄了某一個用戶的賬戶余額。為了更方便的表示整個世界狀態，我們往往會使用Merkle樹把巨大的世界賬本變成一串短小精悍的Merkle哈希值。只要任何一個賬戶的任何余額發生改動，這個Merkle哈希值就會發生改動。Merkle樹其實就是一個二叉樹，每一個節點都會把下面的兩個子節點的值拼接在一起，并且算出對應的哈希值作為自己的值。為了方便構建Merkle樹，我們會把最原始的余額數值先做一次哈希計算，然后把它們的哈希值存到Merkle樹的最底層來。

SEMI：芯片短缺將延續至2024年:6月22日消息，國際半導體產業協會(SEMI)21日表示，由于俄烏戰爭持續威脅半導體關鍵特殊氣體等原料的供給，全球恐怕到2024年都將持續面臨全球芯片短缺的問題，并示警未來晶圓廠大量擴產后的潛在風險。（財聯社）[2022/6/22 4:44:48]

當我們如此構建一個Merkle樹之后，我們就可以把輸出的Merkle哈希值當作一個承諾：只要承諾不發生改變，那么當前的世界狀態就肯定不會發生改變。在區塊鏈中，如果我們想要記錄一長串數據的狀態，一般為了節省空間，會在鏈上記錄所有數據的Merkle承諾，而不是把數據本身存在鏈上。當我們有了一個世界狀態的承諾之后，后續的問題就是：假如A就是上圖中的賬戶1，現在有5塊錢。A如何向B證明，在整個世界狀態中，她的余額真的為5塊呢？一個很簡單的方法就是：A可以向B提交所有賬戶的余額，然后B自己再進行一次Merkle承諾的運算。只要B算出來的承諾和當前的世界狀態承諾相等，并且A提交的她自己的賬戶余額的確是5塊錢的話，B就可以相信A真的有5塊錢。聽起來好像是很不錯的方法，但是這個方法存在的問題一目了然。加入這個世界有幾億的用戶，如果A需要向B提交幾億行存款余額，先別說B怎么去有效的計算這個承諾，光是網絡流量就要用爆了。并且如此證明方法將會暴露所有用戶的余額信息，大家肯定也是不太愿意的。那怎么有效的證明賬戶1的余額屬于當前世界狀態呢？這個時候我們就可以利用Merkle樹的特點來構造Merkle證明。

如果仔細觀察上圖經過一些修剪的Merkle樹的話，我們會發現，只要證明賬戶1的余額可以在Merkle樹中和相鄰的節點一路組成最后的世界狀態承諾，我們也就能證明賬戶1的余額屬于當前世界狀態了。那具體怎么做呢？我們先從賬戶1的余額出發，一路沿著Merkle樹往上走。有了賬戶1的余額，那么我們就可以計算出H1。當有了H1之后，我們發現，我們并不需要知道賬戶0的余額，只要一個H0的值，就可以組合生成H4了。同理，我們可以通過和H5的值結合，最終生成頂點的Merkle承諾——H6。到頭來我們只需要提交三樣東西就可以完成這個Merkle證明了：賬戶1的余額、H0、H5。剩下哈希值全部可以在驗證的過程中被計算出來。這就是Merkle證明。我們通過Merkle證明可以大大的壓縮證明的體積，并且也可以盡可能的保證世界狀態中的其他用戶的余額不在證明的過程中被暴露出來。Merkle證明在密碼學上非常有用，只需要的大小就可以證明某個東西在長度為N的列表之內。往往我們都會用Merkle證明來證明一組數據屬于一個很大文件，一個用戶屬于一個很大的組織，等等。了解完Merkle證明的原理之后，我們來看看如何證明在私密交易中，A可以證明她的余額。Merkle證明的精髓就是我們可以從要證明的值開始，一路往上算哈希值，并且和相鄰的節點的哈希值不斷的合并。但是我們發現一個非常致命的問題：雖然我們可以隱去世界狀態里別人的余額，但是我們還是必須要暴露自己的余額。這一點和我們私密交易的本質是違背的！這個時候，就需要借助SNARK的力量了。我們可以把這個問題拆分成兩步。第一步：證明余額哈希值

第一步，我們通過SNARK來證明，賬戶1的余額，通過哈希函數之后，可以得到哈希值H1。因為我們想隱藏賬戶1的余額，我們用w來表示這個數字。在套用SNARK之前，我們還需要變換一下問題的描述方法，使其更方便用數學運算電路表達：假設A自己擁有一個秘密w=賬戶1的余額。A和B都事先知道了賬戶1的余額的哈希值H1。我們可以構造數學運算電路C：Hash(w)-x=0。如果C(x,w)=0，那么代表Hash(w)=x。

為了簡化表述，我們在圖上用一個抽象的模塊表示哈希函數。在實際運用當中，我們一般會使用SHA256哈希函數。當我們得到最終的電路C之后，我們使用Setup算法生成參數，再用Prove算法生成簡短證明。通過這一步，我們會得到一個公開的x和一個證明，并且這個x的值就是賬戶1的余額的哈希值。雖然我們看不到賬戶1真正的余額，但是因為強大的SNARK證明，我們不得不相信x=Hash(w)。第二步：從H1開始完成Merkle證明

前一步讓我們得到了H1，并且也提供了證明代表H1真的是從原本的世界狀態中生成的。我們現在要做的事情，就是從H1開始，分別與相鄰的H0和H5結合，生成一個新的世界狀態承諾。如果我們比較這個生成的承諾和區塊鏈上保存的老的承諾是相同的，那么我們就可以相信賬戶1的余額真的在這個世界狀態之中。

總結起來看，我們把所有權證明分成了兩步，第一步證明秘密的w可以被哈希函數轉換為x，再證明公開的x屬于整個世界狀態的Merkle樹。提交證明的A知識證明她知道一個秘密賬戶1，并且這個賬戶在當前的世界狀態中。驗證證明的B或者其他人，仍然無從知曉到底A知道的是哪個賬戶，但是又不得不相信是真的。私密交易總結

看到這里，想必大家已經對私密交易是如何實現的已經有了一個大概的了解。現在我來總結一下如果A要向B支付一筆私密交易，她一共要做哪些事。首先，A需要向全網提交一筆私密交易，這一筆交易里面有交易的發起人和收款人，但是并沒有任何數量，原本的輸入輸出的數量被幾串亂碼代替了。在這筆交易的下面，A需要附加一項Pederson承諾，證明輸入和輸出的數字相加起來是相等的。然后A需要再附加一個通過SNARK生成的區間證明，證明輸入和輸出的數字都是大于0的正整數。最后，A需要附加一個所有權證明，證明她真的擁有一個賬戶w，里面存了錢。這個所有權證明分為兩個部分，一個是通過SNARK生成的哈希值證明，另一個就是一個Merkle證明，證明了前面的哈希值真的屬于這個世界狀態。通過這四步，A就可以把所有要生成的東西打個包，然后發到網上。礦工們看到這個包，以此把所有的證明都用Verify來驗證一下。如果沒問題的話，那么交易就完成啦。是不是很簡單？未完待續

因為篇幅的原因，這次就講到這里啦。想必大家看到這里，對于零知識證明的「證明」部分已經有所了解了，大概知道了數學運算電路是個啥，然后我們如何把現實生活中的問題轉化為電路。相信很多人會好奇，那么究竟Setup，Prove和Verify這三個算法是如何工作的呢？下一期，我們繼續deepdive一下，深入了解一下SNARK證明系統背后的原理。更多閱讀

和往常一樣，在文末給出一部分readinglist，有興趣的朋友可以深入了解一下：數學運算電路Merkle證明V神的數學電路教程Zcash7篇的中文翻譯

Tags：MERERKANDARKMER幣Terkehhsand幣有沒有價值STARK

中幣交易所