# Tornado Cash - with code
隱藏交易訊息的解方：混幣協議 - Tornado Cash 的背後運作原理。
(本篇文章不包含任何對美國制裁的評論，單就技術層面進行介紹。)
Published on October 12, 2022 by Chen YanLong.
###### tags: `blockchain` `ethereum`
---
你需要具備的基礎知識：
* merkle tree
* smart contract
---
## Table of contents
* Intro
* Architecture
* Code
* Conclusion
* Ref.
---
# Intro
以太坊，或者說整個區塊鏈都擁有的一個完美特性：透明化，是 Tornado Cash 想解決的問題。想像你的錢包裡有一百萬，你想把這些錢打到其他錢包裡，但是如果有人知道你擁有這個錢包，那他就可以在 Etherscan 上輕鬆的看到「你」把錢打進其他錢包裡。如果你想要隱藏你的交易訊息，那你可以使用混幣器： Tornado Cash。
可以想像 Tornado Cash 是一個巨大的金庫，任何人都可以使用 A 錢包存規定的固定金額（比如說100USDT、1000USDT之類的）進去(當然你可存很多次來滿足你的需求)，而協議會生成一張支票，你可以拿著這張支票用 B 錢包提領你存入的金額。當然以上只是簡化過的舉例說明，ZKP 會保證沒有人可以知道 B 錢包領出的錢是從哪一個錢包存入的。
* 當使用者越多時，交易資訊就越難以辨識。相對的，如果使用者只有一個，那就喪失隱藏交易資訊的功能。
* 固定金額讓交易資訊更難辨識
---
# Architecture
Tornado Cash 使用 **Solidity** 撰寫智能合約，透過 **circom** 編譯成的 zkSNARKs 零知識證明達成鏈上的匿名交易。
使用者存款時，需要提供 commitment 的 hash。commitment 包含兩樣東西，一個是nullifier，一個是 randomness ( 在 github 中稱做 secret )。這兩項 concat 之後成為 preimage，再 hash 之後成為 commitment。前者在提款時需要由提款人提供給合約，用於確保此個 commitment 只能使用一次；後者則增加亂數。
Tornado Cash 收到 commitment 之後，會將其儲存在合約內的 Merkle tree 之中。合約會更新 Merkle root，並傳回所存入之 leaf 的 index。等待提款者提款。
使用者提款時，需要提供 proof，證明其 commitment 確實存於此 merkle tree 當中。以及須一併提供 nullifier 供合約驗證此存款是否被提領過。合約確認此存款未被提領過後，便會將存款轉給使用者，並將 nullifier 存在合約當中，確保不會再有人使用同一個 nullifier 進行提領。
:::info
因為有 Gas 的問題， 提款者可能會想使用 **Relayer**。
想要完全的隱藏交易訊息最好的方式 就是建立一個新的錢包去提領。由於在提款的時候合約會向提款者收取 gas fee。如果用舊錢包打幣給新錢包，那這筆打幣的交易就容易成為追蹤的對象。於是**為了使 gas fee 不要成為隱藏交易訊息的敗因**，使用者可以請 Relayer 代為執行提領的動作並預先支出 gas fee，扣除 gas fee 及服務費之後，Relayer 再將剩下的金額退還給使用者。
:::
---
# Code
Tornado Cash 在 2022 八月遭到美國政府制裁，原因是其洗錢功能過於強大，甚至連 github 的[原始碼](https://github.com/tornadocash/tornado-core)都曾被封存。所幸近期又開放讀取。
Tornado Cash 的原始碼中包含 contracts 和 circuits 及其他資料夾，前者存放合約，後者則是存放產生零知識證明的 .circom 檔案。
整個 Tornado Cash 最主要做的事情就是 Deposit 和 Withdraw，以下會跟著這兩件事情看程式在背後做了哪些事。
## Deposit
deposit 的函數接收一個參數 \_commitment，由 Pedersen 雜湊函數將 nullifier 與 secret concat 加雜湊產生。這些東西要在線下產生。
```solidity=1
function deposit(bytes32 _commitment) external payable nonReentrant {
require(!commitments[_commitment], "The commitment has been submitted");
uint32 insertedIndex = _insert(_commitment);
commitments[_commitment] = true;
_processDeposit();
emit Deposit(_commitment, insertedIndex, block.timestamp);
}
```
第四行 \_insert 這個函數存於 MerkleTreeWithHistory.sol 中，這個檔案裡面處理所有有關 Merkle Tree 的事件，其中 Merkle tree 的建立使用了 MiMC 雜湊函數。
:::warning
這裡需要注意一點，Tornado Cash 所使用的是 Sparse Merkle Tree，他跟普通的 Merkle Tree 不一樣的是他在初始設定時先將每個 leaf 設定好了預設值。換言之，在儲存資料之前這棵樹已經「長」好了。
```solidity
function zeros(uint256 i) public pure returns (bytes32)
```
zeros( )這個函數裡面寫好了每一層的預設值。
:::
\_insert( ) 做的事情是將傳入的 commitment 存入已存在的 Merkle Tree 當中的其中一個 leaf 並回傳所存入的 index。
```solidity
function _insert(bytes32 _leaf) internal returns (uint32 index)
```
## Withdraw
Tornado 最難達成的就是 withdraw，為了確保交易資訊的隱密性，Tornado Cash 不能接收到原始的 nullifier 與 secret，也就是 preimage。否則有心者就可以藉此推敲出交易的資訊。
因此這方面要由 withdraw.circom 建立一個 ZK proof ， 再交由合約做驗證並提款。
```
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];
```
Withdraw( )首先接收數個參數（我僅列出有使用到的），他的功能是證明使用者提供的 secret 和 nullifier 所組合成的 commitment 真的存在於 Merkle Tree 之中。
可以注意到 nullifier 和 secret 是以 private 的方式傳入，所以再傳入一個 nullfierHash 因為合約真的不知道 nullifier 的值是多少。
pathElements[levels] 存的是目標 leaf 要計算到 root 中間需要 hash 過的元素。pathIndicies[levels] 則是由 {0, 1} 組成，標示所在位置在左邊或右邊的陣列。
```
component tree = MerkleTreeChecker(levels);
tree.leaf <== hasher.commitment;
tree.root <== root;
for (var i = 0; i < levels; i++) {
tree.pathElements[i] <== pathElements[i];
tree.pathIndices[i] <== pathIndices[i];
}
```
經由以上的運算後證明用 private 變數算出來的 root 和 public root 的結果是一致的。將 circom 產生的 proof 交由 Tornado.sol 的 withdraw( )進行驗證。
```solidity=1
function withdraw(
bytes calldata _proof,
bytes32 _root,
bytes32 _nullifierHash,
address payable _recipient,
address payable _relayer,
uint256 _fee,
uint256 _refund
) external payable nonReentrant {
```
首先確認傳入的 nullifierHash 未被使用過，若沒有使用過，合約會將這個nullifierHash 標示為已使用；若是使用過，則合約會報錯。
```solidity
require(!nullifierHashes[_nullifierHash], "The note has been already spent");
```
接著確認傳來的 root 確實是在過去的某一個時點存在過的。
Tornado Cash 的合約中存有歷史上所有的 merkle root，意即每次執行完_insert( ) 時都會更新新的 merkle root 在 roots[ ]裡頭。
```solidity
require(isKnownRoot(_root), "Cannot find your merkle root");
```
最後交由 verifiyProof( ) 驗證 \_proof 的真實性。此函數使用到密碼學中 Pairing 的概念，詳細的邏輯我也沒有到非常清楚。總之這個函數若是傳回 true 則代表 \_proof 是真的，false 則否。
```solidity
require(
verifier.verifyProof(
_proof,
[uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund]
),
"Invalid withdraw proof"
);
```
若一切都沒有問題，合約就會進行轉帳的部分，結束這個交易。
```solidity
_processWithdraw(_recipient, _relayer, _fee, _refund);
```
---
# Conclusion
Tornado Cash 在2022年8月被列入 OFAC 的 SDN 制裁名單當中，禁止所有美國人與該協議或相關錢包地址進行互動 ([ link ](https://www.blocktempo.com/tether-wont-freeze-tornado-cash-addresses/))。目前除了原始碼重新開源沒有其他更進一步的消息。不過 Tornado Cash 還是一個學習 ZKP 很好的教材。
Circom 所產生的零知識證明可以保證在沒有擁有真實的 preimage 的情況之下你很難做出正確的 proof。而如果你擁有真實的 preimage，則在不透漏真實的preimage 之下你可以證明自己知道這個 preimage ，這方面可以相信密碼學家的奧妙，也就是零知識證明的厲害的地方。
---
# Ref.
* [TornadoCash whitepaper v1.4](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://berkeley-defi.github.io/assets/material/Tornado%20Cash%20Whitepaper.pdf)
* [Understanding zero knowledge proofs through the source code of tornado cash](https://betterprogramming.pub/understanding-zero-knowledge-proofs-through-the-source-code-of-tornado-cash-41d335c5475f)
* [[ZKP 讀書會] Tornado Cash](https://medium.com/taipei-ethereum-meetup/zkp-study-group-tornado-cash-fdbb84d44b93)
* [Tornado Cash github](https://github.com/tornadocash/tornado-core)
Sign in with Wallet
Connect another wallet