Tornado Cash 實例解析

Tornado Cash 是一個使用 zk-SNARKs 建立的 Dapp，它實現了匿名的代幣交易，這篇文章就用一些程式碼片段，來分享它是怎麼運作的。

本文為 Tornado Cash 研究系列的 Part 3，本系列以 tornado-core 為教材，學習開發 ZKP 的應用，另兩篇為：

• Part 1：Merkle Tree in JavaScript
• Part 2：ZKP 與智能合約的開發入門

Special thanks to C.C. Liang for review and enlightenment.

我們知道在以太坊上的交易紀錄都是公開的，你可以在 etherscan 上看到某個地址的所有歷史交易紀錄，當然地址是合約的話也是一樣。

也許創建一個新的錢包和地址就好了？假設一個情境是 Alice 想要匿名傳送 1 ETH 給 Bob，Alice 原本的錢包是 A，但她不想讓 A 地址傳給 Bob 的交易紀錄被看到，所以 Alice 創建另一個錢包 B，顯然 B 錢包是空的，Alice 必須把 A 錢包的 1 ETH 傳到 B 錢包，再用 B 錢包的地址傳給 Bob。

但問題就在於，只要追蹤 B 錢包的地址，就能看到 B 的歷史交易紀錄中 A 錢包曾經打幣給 B 錢包，於是到頭來交易還是被追蹤到了。

Tornado Cash 的解決方案，簡單來說，它是一份合約，當你要匿名傳送代幣時，就把一定數量的幣丟進合約裡 (Deposit)，此時你會拿到一個 note，長得像這樣：

tornado-eth-0.1-5-0x3863c2e16abc85d72b64d78c68fca5936db2501832e26345226efdfb2bc45804977f167d86b711bb6b4095ddaa646ec93f0a93ac4884a66c1d881f4fc985

note 就是一串字串，擁有這字串的人，就能提領 (Withdraw) 剛剛傳入合約的代幣。握有 note 就代表擁有提款的權利，所以 note 一旦被別人知道，別人就可以把錢給提走。

其中，後面那段亂碼，本篇文章就以「秘密」來稱呼，這個秘密是由 secret 與 nullifier 組成，而這兩個都是在鏈下隨機產生的亂數。

因此 Tornado 的合約基本上會有兩個函式：

1. Deposit
2. Withdraw

有興趣的人可以先到 Dapp 上先玩一次看看，使用 Goerli 測試網，這裡可以領 Goerli 的代幣：https://goerli-faucet.slock.it/

Deposit

我們就從 Deposit 開始說起，簡單來說， Deposit 是將資料儲存到合約的 Merkle Tree 上。

剛剛提到的秘密，它是在鏈下產生，由 secret 跟 nullifier 組成，合在一起之後也稱作 preimage，因為我們要對這個 preimage 進行 hash，就會成為 commitment。

合約中 Deposit 如下：

deposit 除了傳送代幣到合約之外，需填入一個參數 _commitment。

我們對 preimage 使用 Pedersen 作為 hash function 加密後產生 commitment，以偽代碼表示如下：

const preimage = secret + nullifier;
const commitment = pedersenHash(preimage);

這個 commitment 會成為 Merkle Tree 的葉子，所以合約中的 _insert(commitment) 來自 MerkleTreeWithHistory.sol 的合約，將我們的資料插入 Merkle Tree，然後回傳一個 index 給你，告訴你這個 commitment 在 Merkle Tree 上的位置，最後一起發布成公開的 Deposit 事件。

我們知道 MerkleTree 是將一大筆資料兩兩做雜湊後產生一個唯一值 root，這個 root 就是合約上所儲存的歷史資料。

root 的特性就是只要底下的資料一有更動，就會重新產生新的 root。

所以只要一有用戶 deposit ，就會插入新的葉子到 Merkle Tree 上，於是就會產生新的 root，所以在合約中有一個陣列是用來儲存所有的 root 的 roots：

bytes32[ROOT_HISTORY_SIZE] public roots;

roots 是用來紀錄每個 deposit 的歷史，每一次 deposit 都會創造新的 root，而所有 root 都會被儲存進 roots 裡，於是當你要提領的時候，就要證明你的 commitment 所算出的 root 曾經出現在 roots 裡，代表曾經有 deposit 的動作，因此才可以進行提領。

Withdraw

在 Deposit 之前 Tornado Cash 就會在鏈下產生秘密後交給使用者，擁有這個秘密的人等於擁有提款的權利。

提領的時候，秘密會在鏈下計算後產生 proof，proof 是 withdraw 需要的參數，所以只要確保這個 proof 能夠被驗證，那麼代幣的接收地址 (recipient) 就可以隨便我們填，只要不填上當初拿來 deposit 用的地址，基本上就做到匿名交易的效果了。

也就是說，產生這個 proof 並提交給合約，能夠證明此人知道秘密，但卻不告訴合約秘密本身是什麼。

function withdraw(bytes calldata _proof, bytes32 _root, bytes32 _nullifierHash, address payable _recipient, address payable _relayer, uint256 _fee, uint256 _refund) external payable nonReentrant;

我們可以清楚看到 withdraw 函式裡沒有接收有關秘密的任何資訊作為參數，也就是秘密不會與合約有所接觸，也不會暴露在 etherscan 上。

回顧 ZKP 所帶來的效果：

• 鏈下計算
• 隱藏秘密

在 Tornado Cash 的例子中，我們用秘密來產生證明，完成的鏈下計算包括：

1. 將秘密 hash 成 commitment
2. 算出 Merkle Tree 的 root。

以下是簡化後的 withdraw.circom：

template Withdraw(levels) {
    signal input root;
    signal input nullifierHash;
    signal private input nullifier;
    signal private input secret;
    signal private input pathElements[levels];
    signal private input pathIndices[levels];
    component hasher = CommitmentHasher();  // Pedersen
    hasher.nullifier <== nullifier;
    hasher.secret <== secret;
    hasher.nullifierHash === nullifierHash;
    component tree = MerkleTreeChecker(levels); // MiMC
    tree.leaf <== hasher.commitment;
    tree.root <== root;
    for (var i = 0; i < levels; i++) {
        tree.pathElements[i] <== pathElements[i];
        tree.pathIndices[i] <== pathIndices[i];
    }
}
component main = Withdraw(20);

從上述代碼就可以看出這份 circuit 的 private 變數有：

• secret
• nullifier
• pathElements
• pathIndices

而 public 變數有：

• root
• nullifierHash

如同我們一開始說過的，秘密就是指 secret 與 nullifier。這裡進行的鏈下計算就是對 secret 與 nullifier 雜湊成 commitment。而使用的 hash function 叫做 Pedersen。

在進行 Merkle Tree 的計算之前，我們還檢查了 nullifier 雜湊後的 nullifierHash 跟 public 變數 nullifierHash 是不是一樣的。

hasher.nullifierHash === nullifierHash;

接下來，開始計算 Merkle Proof，用意是確認經過雜湊後的 commitment 有沒有出現在 Merkle Tree 上，所以我們的 private input 還有 pathElements 與 pathIndices（詳情參考 Part 1 Merkle Tree in JavaScript），讓它跑一趟 Merkle Proof 的計算，最後就能夠算出一個 root，再確認計算後的 root 與我們的 public 變數 root 是否一樣。

tree.root <== root;

於是我們就能產生一個 ZKP 的證明 — 證明 private 變數：secret, nullifier, pathElements, pathIndices 可以計算出 public 變數：root 與 nullifierHash。

把這個證明提交給合約，合約透過 Verifier 驗證 proof 是否正確，以及必須事先確認：

1. public 變數 root 有在合約的 roots 裡面。
2. public 變數 nullifierHash 在合約中是第一次出現。

以下附上完整的 withdraw 原始碼：

必須注意 ZKP 是向合約證明使用者填入的 secret 和 nullifier 可以計算出某個 root，但無法保證這個 root 曾經在合約的 roots 歷史上。

所以合約的 withdraw 中，除了 verifyProof 之外，還要事先檢查 ZKP 算出來的 root 是不是真的在歷史上發生過，所以需要 isKnownRoot 的檢查：

function isKnownRoot(bytes32 _root) public view returns(bool)

必須先檢查 isKnownRoot 後才能進行 verifyProof。

經過 verifyProof 驗證成功後，合約就開始進行提款的動作，也就會將代幣傳到 recipient 的地址，最後拋出 Withdrawal 的事件。

nullifier 與 nullifierHash

為什麼我們的秘密不是只有 secret 還要額外加一個 nullifier？

簡單來說，這是為了防止已經提領過的 note 又再提領一次，也就是所謂的 double spend。

require(!nullifierHashes[_nullifierHash], "The note has been already spent");

可以看到 withdraw 需要填入參數 nullifierHash，跟 isKnownRoot 一樣的狀況，我們需要對電路的 public 變數先經過一層檢查之後，才能帶入到 verifyProof 裡面。

nullifierHash 可以理解為這個 note 的 id，但它不會連結到 deposit，因此可以用來紀錄這個 note 是否已經被提領過。

所以當 verifyProof 驗證成功之後，我們要紀錄 nullifierHash 已完成提領：

nullifierHashes[_nullifierHash] = true;

有關為什麼需要事先檢查 public 變數後，才能帶入 verifyProof ，可以參考 Part 2：ZKP 與智能合約的開發入門 提到的 publicSignals 的部分。

附上 Tornado Cash 的架構圖：

簡化版的 tornado-core

tornado-core 的程式碼很簡潔漂亮，所以我模仿該專案自己實作一遍：

simple-tornado：https://github.com/chnejohnson/simple-tornado

這份專案只完成了 tornado-core 的核心部分，不一樣的是我的開發環境使用 hardhat 與 ethers 寫成，而 circom 與 snarkjs 使用官方當前的版本，合約用 0.7.0，測試使用 Typescript 。

比起兩年前的 tornado-core ，simple-tornado 使用的技術更新，可能更適合初學者理解這份專案，但是它有 bug…我在 issues 的地方有紀錄說明。

在開發的過程中，我的順序是先從最小單位的 MiMC hash function 開始玩，發現必須 javascript 算一次 hash、solidity 算一次、circom 再算一次，確保這三個語言對同一個值算出同樣的 hash 之後，才能放心去做更複雜的 Merkle Tree。

總結

我們可以看到 Tornado Cash 簡單的兩個函式：Deposit 與 Withdraw，透過將代幣送入合約後再提領到另一個地址的流程，應用 ZKP 達成匿名的交易。

除了斷開 Deposit 與 Withdraw 的地址關聯性之外，Tornado Cash 還有做了一層「藏樹於林」的隱私防護，這部份的解釋就請參考 ZKP 讀書會 Tornado Cash。

網路上很多關於 ZKP 的文章或專案都是在 2019 年後出產的，經過許多人對這項技術的嘗試，讓我們對 ZKP 有了更清晰的理解，如今兩年後，開發工具也變得更加成熟，期待未來在 web 隱私議題上能看到更多 ZKP 大放異彩的應用。

原始碼

• tornado-core
• simple-tornado

參考資料

• ZKP 讀書會 Tornado Cash
• Tornado Privacy Solution Cryptographic Review