零時科技|| Tornado Cash中merkleTree和zk-snarks

Tornado cash是一個去中心化加密貨幣混合服務平台，使用智能合約來接受來自一個地址的代幣存款，並允許他們從另一個地址提款。這些智能合約作為混合所有已存資產的池。一旦資金通過一個全新的地址從這些池中提取，鏈上源和目的地之間的鏈接已斷開。然後將提取的加密資產匿名化。 tornado cash中通過將merkle tree 與zk-snarks結合使用實現存取款地址分離，從而實現匿名傳送代幣。

區塊鏈中網絡上產生所有的交易都要打包進區塊，通常情況下，每個區塊中包含成百上千個交易。而且由於區塊鏈去中心化的特徵，網絡中每個節點都必須是獨立的，因此每個節點都必須存儲一個區塊鏈的完整副本，當交易量逐漸增多時，區塊中數據也越來越龐大，佔據的空間也越來越多而且處理效率逐漸變低。因此提出了一個輕節點概念，輕節點只需要儲存歷史區塊頭而不需要保存整個區塊鏈，通過merkle樹證明判斷交易是否在交易列表中。

Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹。默克爾樹的葉子是數據塊(例如，文件或者文件的集合)的hash值。非葉節點是其對應子節點串聯字符串的hash。

如圖，對要存儲的數據生成hash值，這些hash值就是默克爾樹的根節點，之後將相鄰葉子節點的hash字符串連接起來再次進行hash運算，生成中間節點，繼續向上運算，最終生成了一個根節點，這個根就是默克爾根。當任意節點的值改變時，merkle根的值隨著改變。

對於merkle樹來說，並不需要知道整棵merkle樹中節點的值，如下圖，當我想要證明Hk在集合中時，我只需要將Hl，Hij，Hmnop和Habcdefgh的值發送給證明函數，如果計算出的merkle根與存儲的根相同則證明Hk在集合中。

tronado cash中對於merkle tree的使用主要在存取款操作中，進行存款操作時會創建兩個隨機數，將這兩個隨機數通過Pedersen哈希處理後生成一個字符串commitment，將此字符串作為葉子節點插入默克爾樹中，計算出merkle根的值後將merkle根返回給用戶，作為之後取款時的驗證憑證。

tornado cash中的merkle tree是一顆二叉樹，閱讀其代碼可知，re-hashing操作的次數控制在log(n)以內，當原始樹中葉子節點個數是奇數時插入後的樹沒有孤兒，原始樹中葉子節點個數時偶數時插入後的樹有孤兒，孤兒在第一個數據塊。

如圖所示，原始樹中有兩個葉子節點a，b，當插入新節點c時，判斷葉子節點個數，為偶數，c與0值進行hash計算得到Hc，葉子節點個數除2，得到葉子節點的父節點個數1，判斷節點個數為奇數，將Hc 與Hab 連接併計算hash值Habc ，此時Habc 為這顆merkle樹的根，用戶將這個根保存作為之後取款的憑證。

zk-snarks全稱為簡潔的非交互式知識認證，也稱零知識證明。它可以讓你在不執行，甚至不知道執行的具體內容是什麼的情況下就能夠驗證某個計算的結果是否正確。

舉個例子，想像一下，你是盲人，我給你兩個球，感覺完全一樣，重量也一樣。現在我告訴你這兩個球的顏色不同。附近沒有其他人。你怎麼能知道我說的是不是真的呢？

你可以在每隻手上放一個球，把它們展示給我看。現在你把它們放在你的背後，你要么在兩隻手之間交換球，要么不交換。然後你把它們拿給我看，並問我：'我是否交換了球？現在，如果兩個球都是同樣的顏色，將有50%的機會猜對。但如果連續答對了15次，你幾乎可以肯定（99.997%的把握）說這兩個球確實是不同顏色的。因為隨機猜對15次，幾乎不可能。

我現在已經向你證明了這些球是不同顏色的，但卻沒有透露實際的顏色，因此被稱為零知識證明。你不知道這些球是綠色、黑色、橙色還是別的什麼。

在區塊鏈中zk-snarks是指可以為生成特定輸出的計算提供相應的proof證明，使得驗證proof的速度遠遠高於執行相應計算的速度，對於SNARK使用的變換，在語句被表述為函數之後，遵循下圖的一般模式，即原始計算，代數電路，秩為1的約束系統，二次算數程序，線性PCP，線互式證明，最後生成零知識證明。

要生成zk-snarks，您需要一個電路。電路類似於具有公共輸入和輸出以及私有輸入的小程序。這些私人輸入是您不為驗證而透露的知識，這就是為什麼它被稱為零知識證明。使用zk-snarks，我們可以證明輸出可以從給定電路的輸入中產生。

tornado cash中取款操作需要用戶提供一個note，如下圖

這個note是由secret與nullifier通過zk-snarks電路在鏈下計算生成的，secret與nullifer是在鏈下隨機生成的31字節長度的隨機數。

tornado中，存款操作傳入的參數commitment是由secert與nullifer串聯產生一個62字節的數，通過Pedersen 哈希處理，生成的輸出表示Baby Jubjub 橢圓曲線的一個元素，編碼為32 字節大端整數。之後將commitment插入merkle樹中得到merkle root。

在tornado cash中，取款操作時需要輸入三個值，分別是proof，root，nulifierHash，proof為存款時在鏈下計算出的note值，root為存款時獲得的merkle root，nulifierHash為生成的隨機數。

nulifierHash作用是為了防止已經使用過的note再次使用，在進行證明proof之前，先確定傳入的root值是否在merkle樹中，之後驗證proof是否正確，通過電路計算出一個root，將計算出的root與取款時輸入的root比較是否一樣，一樣的話，將nullifierHash記錄為true，證明我們已經領過款。

通過以上幾步，我們就完成了一個零知識證明的過程，

tornado cash中將merkle tree運用到零知識證明中，零知識證明中proof實際捆綁了憑證note，用戶自己的merkle root，nullifierHash，資金接收者地址。取款合約中確保nullilierHash是未使用過的，以及用戶提供的Root確實是自己知道的代表完整記錄的Root。然後，合約將自己驗證過的輸入nullifierHash 和root，以及用戶方輸入的proof recipient fee等輸入Verifier合約。用零知識證明proof提供的路徑確實能聯通用戶提供的nullifier和secret生成的commitment和提供的root，用戶是這個commitment的擁有者。