背景
Tornado cash是一個去中心化加密貨币混合服務平台，使用智能合約來接受來自一個位址的代币存款，并允許他們從另一個位址提款。這些智能合約作為混合所有已存資産的池。一旦資金通過一個全新的位址從這些池中提取，鍊上源和目的地之間的連結已斷開。然後将提取的加密資産匿名化。tornado cash中通過将merkle tree 與 zk-snarks結合使用實作存取款位址分離，進而實作匿名傳送代币。
Merkle Tree
區塊鍊中網絡上産生所有的交易都要打包進區塊，通常情況下，每個區塊中包含成百上千個交易。而且由于區塊鍊去中心化的特征，網絡中每個節點都必須是獨立的，是以每個節點都必須存儲一個區塊鍊的完整副本，當交易量逐漸增多時，區塊中資料也越來越龐大，占據的空間也越來越多而且處理效率逐漸變低。是以提出了一個輕節點概念，輕節點隻需要儲存曆史區塊頭而不需要儲存整個區塊鍊，通過merkle樹證明判斷交易是否在交易清單中。
Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹。默克爾樹的葉子是資料塊(例如，檔案或者檔案的集合)的hash值。非葉節點是其對應子節點串聯字元串的hash。
如圖，對要存儲的資料生成hash值，這些hash值就是默克爾樹的根節點，之後将相鄰葉子節點的hash字元串連接配接起來再次進行hash運算，生成中間節點，繼續向上運算，最終生成了一個根節點，這個根就是默克爾根。當任意節點的值改變時，merkle根的值随着改變。
對于merkle樹來說，并不需要知道整棵merkle樹中節點的值，如下圖，當我想要證明Hk在集合中時，我隻需要将Hl，Hij，Hmnop和Habcdefgh的值發送給證明函數，如果計算出的merkle根與存儲的根相同則證明Hk在集合中。
Tornado cash 中 merkle tree使用
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
zk-snarks全稱為簡潔的非互動式知識認證，也稱零知識證明。它可以讓你在不執行，甚至不知道執行的具體内容是什麼的情況下就能夠驗證某個計算的結果是否正确。
舉個例子，想象一下，你是盲人，我給你兩個球，感覺完全一樣，重量也一樣。現在我告訴你這兩個球的顔色不同。附近沒有其他人。你怎麼能知道我說的是不是真的呢？
你可以在每隻手上放一個球，把它們展示給我看。現在你把它們放在你的背後，你要麼在兩隻手之間交換球，要麼不交換。然後你把它們拿給我看，并問我：'我是否交換了球？現在，如果兩個球都是同樣的顔色，将有50%的機會猜對。但如果連續答對了15次，你幾乎可以肯定（99.997%的把握）說這兩個球确實是不同顔色的。因為随機猜對15次，幾乎不可能。
我現在已經向你證明了這些球是不同顔色的，但卻沒有透露實際的顔色，是以被稱為 零知識 證明。你不知道這些球是綠色、黑色、橙色還是别的什麼。
在區塊鍊中zk-snarks是指可以為生成特定輸出的計算提供相應的proof證明，使得驗證proof的速度遠遠高于執行相應計算的速度，對于SNARK使用的變換，在語句被表述為函數之後，遵循下圖的一般模式，即原始計算，代數電路，秩為1的限制系統，二次算數程式，線性PCP，線互式證明，最後生成零知識證明。
要生成 zk-snarks，您需要一個電路。電路類似于具有公共輸入和輸出以及私有輸入的小程式。這些私人輸入是您不為驗證而透露的知識，這就是為什麼它被稱為零知識證明。使用 zk-snarks，我們可以證明輸出可以從給定電路的輸入中産生。
tornado cash 中 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的擁有者。