作者：Faust，極客web3
導語：近期Vitalik和一些學者聯名發表了新論文，其中提到了Tornado Cash如何實現反xi錢方案（其實就是讓取款人證明，自己的存款記錄屬於一個不包含黑錢的集合），但文中缺乏對Tornado Cash業務邏輯與原理的細緻解讀，讓人似懂非懂。
此外值得一提的是，Tornado為代表的隱私項目才是真正用到了ZK-SNARK算法的零知識性，而大多數打著ZK旗號的Rollup，用到的只是ZK-SNARK的簡潔性。很多時候人們往往混淆了Validity Proof與ZK的區別，而Tornado恰好是理解ZK應用的極佳案例。
本文作者恰好在2022年於Web3Caff Research寫過一篇關於Tornado原理的文章，今日將其部分段落節選並拓展，整理成文，以便大家系統的理解Tornado Cash。
原文鏈接：
https://research.web3caff.com/zh/archives/2663?ref=157
“龍捲風”的原理
Tornado Cash是利用了零知識證明的混幣器協議，舊版本在2019年投入使用，新版本在2021年底啟動了beta版。 Tornado舊版本基本實現了去中心化，鏈上合約開源且無多簽控制，前端代碼開源且備份在了IPFS網絡裡。由於舊版Tornado的整體結構更簡單易懂，所以本文將針對舊版本進行解讀。
Tornado的主要思路是：把大量的存取款行為混雜在一起，存款者在Tornado存入Token後，出示ZK Proof證明自己存過款，再用一個新地址提款，以此切斷存取款地址之間的關聯性。
更具體的概括，Tornado就像一個玻璃箱，混雜了很多人放進去的Coin硬幣。我們能看到放Coin的是哪些人，但這些Coin高度同質化，如果有生面孔的人從玻璃箱拿走一枚Coin，我們很難知道他拿走的Coin最初是誰放進去的。
這種場景似乎屢見不鮮：當我們從Uniswap池子裡SWAP幾枚ETH時，根本無法知道劃走的ETH是誰提供的，因為曾給Uniswap提供流動性的人太多了。但不同之處是，每次用Uniswap劃走Token，我們需要用其他Token作為等價的成本，且不能把資金“私密的”轉讓給別人；而混幣器只需要提款者出示存款憑證就行。
為了讓存取款動作看起來有同質性，Tornado池子的存款地址每次存入的資金、取款地址每次取出的資金都保持一致，比如某個池子的100個存款者和100名取款者，雖然公開可見，但看起來彼此沒有任何联系，而且每人存入的金額、取出的金額，都是一樣的。 這時就可以混淆視聽，沒法按照存取款金額判斷關聯性，進而切斷資金轉移痕跡，顯而易見的是，這為xi錢行為提供了天然的便利。
但有一個關鍵問題：取款者在提款時，怎麼證明自己存過款？向混幣器發起取款的地址，與所有的存款地址都不關聯，那麼該如何判斷他的提款資格？看起來最直接的方法，是取款者直接披露自己的存款記錄是哪一筆，但這就直接洩露了身份。此時零知識證明就派上了用場。
提款者出具一個ZK Proof，證明自己在Tornado合約裡有存款記錄，且該筆存款尚未被提取，就能順利發起取款。零知識證明本身就實現了隱私保護，外界只知道：取款人的確往資金池裡存過款，但不知道他對應哪個存款者。
要證明“我在Tornado資金池裡存過款”可以被轉化為“我的存款記錄可以在Tornado合約裡找到”。如果用Cn表示存款記錄，問題就歸納為：
已知Tornado的存款記錄集合為{C1，C2，…C100…}，取款者Bob證明自己曾用手上的密鑰，生成了存款記錄裡的某個Cn，但通過ZK不洩露Cn具體是哪個。
這裡要用到Merkle Proof的特殊性質。因為Tornado的所有存款記錄，都存進了鏈上構造的一棵MerkleTree，作為其最底層的葉子結點，而葉子總數約為2的20次冪>100萬，大多數都處於空白狀態（賦予了初始值）。每當有新存款行為產生時，合約就會把其對應的特徵值Commitment寫入一個葉子裡，然後更新Merkle Tree的root。
比如，Bob的存款操作是Tornado有史以來第1萬筆，那麼與這筆存款有關聯的一個特徵值Cn會寫入Merkle Tree的第1萬個葉子結點，也即C10000= Cn。然後合約會自動算出新的Root，update一下。 （ps：為了節約計算量，Tornado合約會緩存之前一批有變化的節點的數據，比如下圖中的Fs1和Fs2、Fs0）
而MerkleProof本身很簡潔輕便，它利用了樹狀數據結構在檢索/溯源過程中的簡潔性。若想對外證明某筆交易TD存在於MerkleTree中，只要給出Root對應的MerkleProof（如下圖中右邊的部分），它相當簡潔。如果Merkle Tree格外龐大，底層葉子有2的20次冪個，也就是包含100萬筆存款記錄，Merkle Proof也只需要包含21個節點的數值，非常短。
如果要證明某筆交易H3的確包含在Merkle Tree中，設法證明用H3和Merkle Tree上其他的部分數據，可以生成Root，而生成Root所需要的那部分數據（包括Td在內）就構成了Merkle Proof。
而Bob在取款時，要證明自己擁有的憑證對應著Merkle Tree上有記錄的某筆存款哈希Cn。也就是說，他要證明兩件事：
·Cn存在於鏈上Tornado合約裡的Merkle Tree中，具體可以構造一個Merkle Proof，裡麵包含Cn；
·Cn與Bob手上的存款憑證有關聯。
Tornado業務邏輯詳解
Tornado用戶界面的前端代碼中事先實現了很多功能，當一名存款者打開TornadoCash網頁並點擊存款按鈕後，前端代碼附帶的程序會在本地生成2個隨機數K和r，隨後會計算出Cn=Hash(K，r)的值，再把Cn（就是下圖中的commitment）傳入Tornado合約，插入到後者記錄的Merkle Tree裡。說白了，K和r相當於私鑰。它們很重要，系統會提示用戶妥善保存。後面提款時仍然要用到K和r。
值得注意的是，以上工作皆發生於鏈下，也就是說：Tornado合約和外界觀察者都不知曉K和r。 如果K和r被洩露了，就類似於錢包私鑰被盜。
Tornado合約收到用戶存款，並收到用戶提交的Cn=Hash(K，r)後，便將Cn插入到Merkle樹的最底層，作為新的葉子結點，同時會更新Root的數值。 所以，Cn和用戶的存款動作是一對一關聯的，外界可以知道每個Cn對應著哪個用戶，知道有哪些人往混幣器裡存入了Token，並且知道每個存款者對應的存款記錄Cn。
在取款步驟中，取款者在前端網頁裡輸入憑證/私鑰（存款時生成的隨機數K和r），TornadoCash前端代碼中的程序會使用K和r、Cn=Hash(K，r )、Cn對應的Merkle Proof作為輸入參數，生成ZK Proof，證明Cn是存在於Merkle Tree上的某筆存款記錄，而K和r是對應Cn的憑證。
這一步就相當於證明：我知道某筆記錄於Merkle Tree上的存款記錄對應的密鑰。當ZK Proof被提交給Tornado合約時，上述4個參數均被隱藏，外界（包括Tornado合約）無法獲知，藉此保障了隱私。
生成ZKProof涉及的其他參數還包括：取款時Tornado合約裡Merkle Tree的根root、自定義的收款地址A、防止重放攻擊的標識符nf(後面會講)。這3個參數會公開發佈到鏈上，外界可以獲知，但不影響隱私。
這裡面有個細節，就是存款操作生成Cn時，用了2個隨機數K和r來生成Cn，而不是單個隨機數。這是因為單個隨機數不夠安全，有一定概率發生碰撞，比如，採用單隨機數可能導致兩個不同的存款者恰巧採用1個同樣的隨機數，導致生成的Cn撞車。
至於上圖中的A，代表接收提款的地址，由提款者自己填寫。 nf則是一個防止重放攻擊的標識符，其數值nf=Hash（K），K就是存款生成Cn那一步用到的2個隨機數之一（K和r）。這樣一來，nf就與Cn關聯了起來，換言之，每個Cn都有對應的nf，兩者一一關聯。
為什麼要防止重放攻擊呢？ 由於混幣器在設計上的特性，取款時不知道用戶提走的幣對應Merkle樹的哪個葉子Cn，也就不知道提款人和哪些存款人關聯，就不知道提款人到底存過幾次款。提款者可以利用這一特性頻繁提款，發起重放攻擊，多次從混幣器池裡取走Token，直到把資金池抽乾。
在這裡，nf標識符的作用類似於每個以太坊地址都有的交易計數器nonce，都是為了防止某筆交易被重放而設置。當一筆取款發生時，取款者需要提交一個nf，檢查這個nf是否已被使用過（記錄在案）：如果有，此次取款無效。如果沒有，表示該nf尚未被使用，取款有效，對應的nf會被記錄下來。下次再有人提交這個nf時，對應的取款動作直接判定為無效。
如果有人胡亂生成一個合約沒記錄過的nf行不行？ 當然不行，因為取款者生成ZK Proof時，需要保證nf=Hash（K），而隨機數K與存款記錄Cn關聯，也就是說，nf與某筆有記錄的存款Cn關聯。如果隨便編造一個nf，這個nf與存款記錄中的所有存款都對不上號，就不能順利生成有效的ZK Proof，後續的工作就無法順利完成，取款操作就不會成功。
可能也有人會問：不用nf行不行？既然提款者在提款時需要提交ZK證明，證明自己和某個Cn有關聯，那麼每當提款動作發生時，查找對應的ZK Proof是否被提交到鏈上過，不就行了嗎？
但事實上，這樣做的成本很高，因為Tornado cash合約不會永久存儲過去提交的ZK Proof，因為這會嚴重浪費存儲空間。與其比較每個新交到鏈上的ZKProof和既有的Proof是否一致，還不如設置個佔地很小的標識符nf並將其永久存儲來的更划算。
按照取款函數的代碼示例，其需要的參數和業務邏輯如下：
用戶提交ZKProof、nf（NullifierHash）=Hash（K），自定義一個接收提款的地址recipent，ZKProof隱藏了Cn和K、r的數值，讓外界無法獲取判斷用戶身份。 recipent往往會填寫一個乾淨的新地址，也不會洩露個人信息。
但這裡面有個小問題，就是用戶在取款時，為了不可溯源，往往用新申請的地址發起取款交易，此時新地址沒有ETH來支付gas費。所以取款地址發起取款時，要顯式聲明一個中繼者relayer，由它代付gas費，之後混幣器合約會直接從用戶提款裡扣掉一部分交給relayer，作為回報。
綜上所述，TornadoCash可以隱瞞取款者與存款者的關聯，在用戶量很大的情況下，就如同一個鬧市區，犯人混進人群後警方就難以追踪。取款過程中需要用到ZK-SNARK，被隱藏起來的witness部分包含取款人關鍵信息，這是整個混幣器最關鍵的一點。目前看來，Tornado可能是與ZK相關的最巧妙的應用層項目之一。
參考資料
1.https://etherscan.io/address/0xa160cdab225685da1d56aa342ad8841c3b53f291#codeTornado合約源碼
2.https://mirror.xyz/mazemax.eth/BTbTOrEKzGkc-XoDcFtLPfJPtQ1Mt96BZYsW83m33IUTornado.cash新舊版機制對比
3.https://www.youtube.com/watch?v=Z0s4W3UBxM8AnonymousPayments
4.https://medium.com/taipei-ethereum-meetup/zkp-study-group-tornado-cash-fdbb84d44b93[ZKP讀書會]TornadoCash
5.https://medium.com/taipei-ethereum-meetup/tornado-cash-%E5%AF%A6%E4%BE%8B%E8%A7%A3%E6%9E%90-eb84db35de04TornadoCash實例解析
