本文作者東澤，來自安比技術社區的小夥伴，目前就讀於斯坦福大學，研究方向密碼學，本系列文章來源於作者在斯坦福著名的課程《CS 251: Cryptocurrencies and blockchain technologies》上的學習筆記，該課程授課老師是密碼學大拿 Dan Boneh。
上一期文章（淺談零知識證明：背景與起源）發表之後，非常驚訝有那麼多小夥伴讀完了表示喜歡。那麼我們接着這期繼續吧！這次，我們專注的聊一聊 SNARK。
相信看完前一篇文章的朋友們會有一點很不解的地方：爲什麼我們可以如此簡短的創建一個證明，並且證明很長的信息呢？在上課前我也有這同樣的疑惑，甚至覺得這個是一個“黑科技”，不過相信大家看完這篇文章，就會知道如何去駕馭這個“黑科技”了。
在詳細討論之前，我們得稍微嚴肅一點，系統性的學習一下 SNARK 的基本構造。
SNARK 的四步構造
因爲 SNARK 的“黑科技”特性，想要構建一套簡短證明系統，其實流程是略微有些複雜的。總結一下一共可以分爲四步，我們來一步一步詳細描述。
第一步
確定有限域**
在構造之前，我們先需要確定一個可以包含所有我們想要計算的數字的大小的一個有限域（Finite Field）。用通俗易懂的話來說，我們需要選一個很大很大的數字 p，確保這個數字比我們要解決的問題裏的所有數字都大。如果以前瞭解過類似於 RSA 密碼學的朋友們可能對這個概念不陌生。有限域就是給我們所有數字加了一個天花板，確定了整個數學系統的計算空間，類似於在電腦裏如果我們想創建一個存數字的變量，我們需要思考到底是需要一個 uint32_t （32 位），還是一個 uint64_t （64 位）一樣。所有超過有限域的值，都會直接溢出之後再倒回去從 0 開始。在數學界，符合這個特性的計算空間其實有很多種，最常見的一種就是 RSA 算法裏面用到的正整數求模一個大質數（integer mod p）。上文說到的找到一個數字 p，其實就是一個很大的質數，然後我們可以用它來生成一個計算空間。在確定計算空間之後，我們就可以真正開始 SNARK 的搭建了。
第二步
構建數學運算電路 (Arithmetic Circuit)
當我們找到一個數字空間之後，我們下一步要做的事情，就是要把我們想要證明解決的問題用數學運算電路表示出來。
什麼是數學運算電路呢？我們先來看一看傳統的邏輯電路。
上圖表述的是一個與非門（NAND）的電路。先不用過多瞭解電路的用處，我們可以發現的是，兩組輸入信號分別通過了 NOT 和 AND 這兩個基礎邏輯門。像 NOT 和 AND 這樣的基礎邏輯門是邏輯電路的基礎模塊，通過拼加和堆疊我們可以實現任何複雜邏輯。
數學運算電路也是同理，只不過基礎模塊從邏輯門變成了數學運算。因爲加法和乘法是最基礎的數學運算，通過加法和乘法我們也可以近乎實現所有其他的運算方法，所以我們可以選用“加法門”和“乘法門”作爲我們數學運算電路的基礎模塊。通過疊加運算門，我們可以搭建一個複雜多項式的“電路”。
爲了能更好的理解運算門，我們來試試看把上面的 NAND 門從邏輯電路轉換成數學運算電路。（假設 Inp0 和 Inp1 和原來邏輯電路一樣，還是輸入 1/0 的邏輯信號。）
我們先來看 AND 門：AND 其實很簡單，因爲只有當 Inp0 和 Inp1 都是 1 的時候，AND 的結果纔會是 1。我們很快發現，一個乘法門可以完美的代替 AND 門：只有當兩個輸入是 1 的時候，相乘得到的結果纔會是 1。
解決了 AND 之後，我們來轉換 NOT：NOT 其實也非常簡單，因爲輸入信號只會是 0 或者 1，只要用 1 減去輸入的信號，得到的結果就是相反的了。注意有一個問題是，因爲我們只有加法和乘法，所以如果需要實現減法的話，我們需要先把輸入信號乘上一個常數-1。
經過如此轉換，我們就成功的把一個邏輯電路轉換爲數字邏輯電路了。同時因爲我們已經知道如何組建 AND 和 NOT 了，理論上我們就可以把這兩個部分模塊化，拼接任意的複雜邏輯出來。
看到這裏，你可能會覺得運算電路非常簡單，和邏輯電路轉化也非常直白。但是其實這是因爲我們一直在假設運算電路的輸入和邏輯電路一樣，都是 0 或者 1。在真實場景下，一個運算門的輸入值可能上限非常大（取決於我們有限域選擇的大小）。所以我們必須要想辦法約束我們運算電路的輸入，使其不僅能夠在功能性上和邏輯電路相同，並且在輸入取值上只可以取這兩個數字。
但是怎麼用運算門來表示這麼一個關係呢？因爲數學運算電路其實就是一個複雜的多項式（比如上圖的 NAND 電路就變成了 Out = 1 – Inp0Inp1），我們可以把這個問題轉化一下：能否創造出一個多項式，只有當一個輸入滿足 的取值範圍的時候，纔會輸出 0？*最後我們發現，有這麼一個多項式可以滿足這個要求：
上面這串表達式的意思是，只有當數字 n 取值於這個範圍的時候，後面的多項式纔會輸出 0。也就是說，我們就可以把上文提到的 Inp0 和 Inp1 接到這個多項式轉換成的運算電路內，只要這個運算電路的輸出結果是 0，那麼我們就可以確信上文的 NAND 運算電路的輸出也是對的。
有人可能會問，上文限制取值的多項式只能限制一個輸入，但是我們有兩個輸入，如何同時限制他們的取值範圍呢？其實答案很簡單， 只需要把同樣的多項式複製一份，兩者加起來就好了。
有了這兩個電路之後，我們只要確定約束電路的輸出是 0，那麼 NAND 門電路就會正常運轉了。
有一點需要注意的是，因爲我們的邏輯門是從運算門搭建起來的，我們會發現其實邏輯運算非常的慢：任何邏輯運算至少得做一次乘法，然而熟悉計算機硬件的朋友們會知道，乘法其實是相對來說比較昂貴的運算。這樣一來有一點顛倒黑白的感覺，在計算機裏邏輯運算是最便宜也是最簡單的計算，然而在數學運算電路里，邏輯運算反而是一個比較繁瑣的過程了。
第三步
轉換爲可證明數學運算電路
當我們有了數字運算電路這個概念之後，我們就可以把不同的電路模塊拼接起來，生成一個可以用作證明的運算電路出來。
首先，我們先定義一下可以用作證明的數字運算電路 C(x, w)，具體構造如下：
簡單的來說，這個電路 C 有兩組輸入。第一組輸入標記爲 x，我們稱之爲公有輸入（public input），也就是說所有人都會知道 x 的值。這個 x 一般來說表達了想要證明的問題的特性和一些固定的環境變量。第二組輸入標記爲 w，我們稱之爲私密輸入（secret input），或者又稱之爲 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 門的輸出是對的，而且要保證所有的輸入值都取值在我們事先約定好的區間內。
我們結合上面討論的方案，把 NAND 的電路輸出和我們的取值約束電路接在一起拼接成運算電路 C，x 爲 Inp0，w 爲 Inp1，輸出我們約束爲 0，從而構成一個完整的 NAND 門私密輸入證明體系。
當我們得到最後的證明電路 C 之後，我們可以計算出這個運算電路的複雜度。
如果我們想知道一個數字運算電路 C 有多難算的時候，我們可以用裏面有多少個運算門來描述它的複雜度。一般來說我們會用 來表示。像是上面提到的 NAND 證明電路，大概是在 10 左右。
在現實使用場景中，如果我們要把像 SHA256 這樣的複雜函數用數字運算電路來表示， 可能會達到 25000 這麼大。這也就是爲什麼真正落地的證明還是非常慢的原因。
第四步
非交互簡短證明體系（SNARK）
當我們通過第三步得到了最終的證明電路 C，還有對應的 x 和 w 之後，我們的準備工作已經做的差不多了。剩下來的事情，我們就可以交給 SNARK 算法來生成和驗證我們的證明了。
首先，我們看看整個非交互式證明體系的官方定義。
一個 SNARK 系統，往往由三個核心算法組成：Setup，Prove 和 Verify。
1.生成算法 Setup：Setup 算法會把我們實現確定好的電路 C 拿進來進行一系列的預處理（preprocessing），然後生成兩組參數。是給證明方的參數，是給驗證方的。這些參數的用處就是方便雙方來生成和驗證簡短證明。一般來說，生成算法的複雜度和電路 C 的複雜度是等比例的，。
2.證明算法 Prove：證明算法相比不用多講了，證明方會用 Prove 這個算法來生成一個證明，然後把這個證明發送給驗證方。Prove 算法再生成證明的時候會用到幾乎所有的數據：預處理數據，公有輸入 x，還有私密輸入 w。最後生成的證明的空間複雜度非常簡短：。
3.驗證算法 Verify：
驗證算法也非常的直白，驗證方會用 Verify 這個算法驗證我們收到的證明。這個算法會返回一個 1/0 的數值，代表驗證是否通過。驗證的過程中除了需要對方提供的證明，我們還需要預處理數據，還有公有輸入 x。驗證的複雜度也非常小，一般來說是 。
有了這三個算法之後，我們可以用很簡單的圖來描述一下整個證明體系。
證明方提交的 這個證明 可以充分說服驗證方，讓其相信證明方真的有這麼一個祕密的 w 可以滿足 C(x, w) = 0。
**
**
構造實例：私密交易的輸入輸出取值區間（Range Proof）
讀過 上一篇文章 的朋友們應該還會記得， 如果我們要進行私密交易（Confidential Transaction）的話，我們需要在交易最後附帶三組證明：
-
第一組是 Pederson 承諾，證明了輸入和輸出之間的數學關係。
-
第二組是區間證明，需要證明輸入和輸出的值全部取值於正整數的範圍。
-
第三組是所有權證明，證明交易的發起人真的有這麼多 token 作爲輸入。
Pederson 承諾的實現我們已經在上一篇文章中討論過了。現在瞭解完簡短證明的四步構造，我們可以來看看如何具體實現區間證明。
首先，我們需要找到一個合適的數學運算電路來描述我們想要證明的內容。（我們默認使用正整數的有限域，選取一個非常大的質數 p 進行求模。）
假如我們有一個數字 w，我們想要證明這個數字 w 不是一個負數，那麼我們可以先辦法證明它一定會取值於正整數區間。因爲考慮到計算機系統裏的正整數一般不會超過 256 位，所以我們可以把問題弱化一下：證明一個數字 w 取值於 0-2^256 之間。（根據此條件，有限域選擇的質數 p 需要大於 2^256。）
現在確定了要解決的問題之後，我們可以開始思考如何用加法和乘法來表達這個取值關係。還記得在前面的章節，當我們在講一個值 n 會取值在 0 和 1 之間的時候，我們用來約束這個取值範圍。同理可得，如果我們想約束 必須要取值於 0 和 5 之間的話，我們就可以用更長的一串乘法來約束它：
看到這裏，大家可能心裏已經知道如何約束這個 w 的值了：我們只要用同樣的辦法擴大這個等式，從一直連續乘到，不就可以了？聽起來很簡單，但是細心的朋友會發現，這樣最後的電路里面將會有 2^256 個乘法門。光是這麼多乘法，還沒有算加法，這個電路的複雜度已經是天文數字了。就算是跑 Setup 可能就不知道跑到猴年馬月，所以我們說這種約束的方法是不實際的。那還有什麼方法來約束這個數字 w 的空間呢？我們可以巧妙藉助二進制數的結構。既然我們想要規定 w 是個整數，並且大於 0 但小於 2^256，那麼我們就可以在二進制裏，把 w 拆分成 256 位，然後分別約束每一位。這樣的話，我們最後得到的電路大小隻會和這個數字有多少位成正比，而不會和這個數字的最大上限有關係。複雜度一下子就下來了一大個等級。具體是怎麼實現的呢？我們首先把 w 拆分成 256 位：因爲每一位都是二進制的，所以我們需要約束每一位的取值空間爲 0 和 1：
這個約束需要 256 份，每一份對應每一位。當我們把這些約束準備好之後，我們最後確定所有的位組在一起可以還原成原來的 w：
我們把上文提及的 256+1=257 組約束電路全部拼接在一起，合併成一個輸出。最後生成的電路就是我們可以用來構建證明系統的電路 C 了。如果 C 的輸出爲 0，那麼代表了輸入的數字一定要滿足：
-
這個數字是一個正整數，可以被 256 位二進制數表達。
-
這 256 位二進制數的確是二進制數。（只能取值 0 或者 1）
-
這 256 位二進制數全部拼在一起可以重新還原輸入進來的數字。
通過巧妙藉助二進制的特性，我們就有一組大小適中的數學運算電路，可以調用 Setup 來準備生成後續的 SNARK 了。
**
**
實例：私密交易輸入的所有權
解決了區間證明，我們來完成私密交易的最後一組證明： 所有權證明，證明私密交易的輸入值合理。看過前一篇文章的朋友應該會知道，我們講了兩種私密交易所有權證明的體系：第一種方案是一筆交易可以直接引用上一筆交易的輸出，但是這會帶來雞和蛋的問題：難度在如何創造出第一筆私密交易來。第二種方案是在每一筆交易的下面附加另一個新的證明，證明交易發起的用戶的賬戶餘額真的有那麼多錢。我想着重講一下第二種證明方案，也就是證明交易發起者在世界狀態中的賬戶餘額。
在很多區塊鏈的場景中，整個世界的狀態就是一個巨大的賬本。賬本的每一行都記錄了某一個用戶的賬戶餘額。
爲了更方便的表示整個世界狀態，我們往往會使用 Merkle 樹把巨大的世界賬本變成一串短小精悍的 Merkle 哈希值。只要任何一個賬戶的任何餘額發生改動，這個 Merkle 哈希值就會發生改動。
Merkle 樹其實就是一個二叉樹，每一個節點都會把下面的兩個子節點的值拼接在一起，並且算出對應的哈希值作爲自己的值。爲了方便構建 Merkle 樹，我們會把最原始的餘額數值先做一次哈希計算，然後把它們的哈希值存到 Merkle 樹的最底層來。
當我們如此構建一個 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 證明的精髓就是我們可以從要證明的值開始，一路往上算哈希值，並且和相鄰的節點的哈希值不斷的合併。但是我們發現一個非常致命的問題：雖然我們可以隱去世界狀態裏別人的餘額，但是我們還是必須要暴露自己的餘額（不然沒有辦法算出第一個哈希值 H1）。這一點和我們私密交易的本質是違背的！
這個時候，就需要藉助 SNARK 的力量了。我們可以把這個問題拆分成兩步。
**
**
第一步
證明餘額哈希值
第一步，我們通過 SNARK 來證明，賬戶 1 的餘額，通過哈希函數之後，可以得到哈希值 H1。
因爲我們想隱藏賬戶 1 的餘額，我們用 w 來表示這個數字。在套用 SNARK 之前，我們還需要變換一下問題的描述方法，使其更方便用數學運算電路表達：
假設 A 自己擁有一個祕密 w = 賬戶 1 的餘額。A 和 B 都事先知道了賬戶 1 的餘額的哈希值 H1 （我們可以用 x 來表示）。我們可以構造數學運算電路 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 生成的區間證明（Range Proof），證明輸入和輸出的數字都是大於 0 的正整數。
-
最後，A 需要附加一個所有權證明，證明她真的擁有一個賬戶 w，裏面存了錢。這個所有權證明分爲兩個部分，一個是通過 SNARK 生成的哈希值證明，另一個就是一個 Merkle 證明，證明了前面的哈希值真的屬於這個世界狀態。
通過這四步，A 就可以把所有要生成的東西打個包，然後發到網上。礦工們看到這個包，以此把所有的證明都用 Verify 來驗證一下。如果沒問題的話，那麼交易就完成啦。是不是很簡單？
未完待續
因爲篇幅的原因，這次就講到這裏啦。想必大家看到這裏，對於零知識證明的「證明」部分已經有了解了，大概知道了數學運算電路是個啥，然後我們如何把現實生活中的問題轉化爲電路。
相信很多人會好奇，那麼究竟 Setup，Prove 和 Verify 這三個算法是如何工作的呢？下一期，我們繼續 deep pe 一下，深入瞭解一下 SNARK 證明系統背後的原理。
更多閱讀
和往常一樣，在文末給出一部分 reading list，有興趣的朋友可以深入瞭解一下：
-
Merkle 證明 : http://ethbook.abyteahead.com/ch4/merkle.html
-
V 神的數學電路教程 : https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
-
Zcash7 篇的中文翻譯 : https://www.jianshu.com/p/b6a14c472cc1?from=timeline
封面圖片來自 Spencer on Unsplash
往期回顧
探索零知識證明系列（一）：初識「零知識」與「證明」
探索零知識證明系列（二）：從「模擬」理解零知識證明
探索零知識證明系列（三）：讀心術：從零知識證明中提取「知識」
探索零知識證明系列（四）：亞瑟王的「隨機」挑戰：從交互到非交互式零知識證明
零知識證明學習資源彙總
鏈上富人尋「隱私」記（一：Mixer 篇）
從零開始學習 zk-SNARK （一）——多項式的性質與證明
理解零知識證明算法 Bulletproofs （一）：Range Proof
理解零知識證明算法 Bulletproofs （二）：Improved Range Proof
zkPoD: 區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易
PoD-Tiny——實現零信任交易的最簡協議
如果量子計算時代到來，我們的比特幣安全嗎？
長按二維碼添加微信進羣討論零知識證明
安比（SECBIT）技術社區
繁體中文
简体中文
English
日本語
Español