Tornado Cash - with code

隱藏交易訊息的解方：混幣協議 - Tornado Cash 的背後運作原理。
(本篇文章不包含任何對美國制裁的評論，單就技術層面進行介紹。)

Published on October 12, 2022 by Chen YanLong.

tags: `blockchain` `ethereum`

你需要具備的基礎知識：

merkle tree
smart contract

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 進行提領。

因為有 Gas 的問題，提款者可能會想使用 Relayer。
想要完全的隱藏交易訊息最好的方式就是建立一個新的錢包去提領。由於在提款的時候合約會向提款者收取 gas fee。如果用舊錢包打幣給新錢包，那這筆打幣的交易就容易成為追蹤的對象。於是為了使 gas fee 不要成為隱藏交易訊息的敗因，使用者可以請 Relayer 代為執行提領的動作並預先支出 gas fee，扣除 gas fee 及服務費之後，Relayer 再將剩下的金額退還給使用者。

Code

Tornado Cash 在 2022 八月遭到美國政府制裁，原因是其洗錢功能過於強大，甚至連 github 的原始碼都曾被封存。所幸近期又開放讀取。

Tornado Cash 的原始碼中包含 contracts 和 circuits 及其他資料夾，前者存放合約，後者則是存放產生零知識證明的 .circom 檔案。

整個 Tornado Cash 最主要做的事情就是 Deposit 和 Withdraw，以下會跟著這兩件事情看程式在背後做了哪些事。

Deposit

deposit 的函數接收一個參數 _commitment，由 Pedersen 雜湊函數將 nullifier 與 secret concat 加雜湊產生。這些東西要在線下產生。









  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 雜湊函數。

這裡需要注意一點，Tornado Cash 所使用的是 Sparse Merkle Tree，他跟普通的 Merkle Tree 不一樣的是他在初始設定時先將每個 leaf 設定好了預設值。換言之，在儲存資料之前這棵樹已經「長」好了。

function zeros(uint256 i) public pure returns (bytes32)

zeros( )這個函數裡面寫好了每一層的預設值。

_insert( ) 做的事情是將傳入的 commitment 存入已存在的 Merkle Tree 當中的其中一個 leaf 並回傳所存入的 index。

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( )進行驗證。









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

首先確認傳入的 nullifierHash 未被使用過，若沒有使用過，合約會將這個nullifierHash 標示為已使用；若是使用過，則合約會報錯。

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

接著確認傳來的 root 確實是在過去的某一個時點存在過的。
Tornado Cash 的合約中存有歷史上所有的 merkle root，意即每次執行完_insert( ) 時都會更新新的 merkle root 在 roots[ ]裡頭。

require(isKnownRoot(_root), "Cannot find your merkle root");

最後交由 verifiyProof( ) 驗證 _proof 的真實性。此函數使用到密碼學中 Pairing 的概念，詳細的邏輯我也沒有到非常清楚。總之這個函數若是傳回 true 則代表 _proof 是真的，false 則否。

require(
      verifier.verifyProof(
        _proof,
        [uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund]
      ),
      "Invalid withdraw proof"
    );

若一切都沒有問題，合約就會進行轉帳的部分，結束這個交易。

 _processWithdraw(_recipient, _relayer, _fee, _refund);

Conclusion

Tornado Cash 在2022年8月被列入 OFAC 的 SDN 制裁名單當中，禁止所有美國人與該協議或相關錢包地址進行互動 ( link )。目前除了原始碼重新開源沒有其他更進一步的消息。不過 Tornado Cash 還是一個學習 ZKP 很好的教材。

Circom 所產生的零知識證明可以保證在沒有擁有真實的 preimage 的情況之下你很難做出正確的 proof。而如果你擁有真實的 preimage，則在不透漏真實的preimage 之下你可以證明自己知道這個 preimage ，這方面可以相信密碼學家的奧妙，也就是零知識證明的厲害的地方。

Tornado Cash - with code

tags: blockchain ethereum

Table of contents

Intro

Architecture

Code

Deposit

Withdraw

Conclusion

Ref.

Read more

賽局論補充包 Game Theory Big Pack I.

賽局論補充包 Game Theory Big Pack II.

TypeScript Cheatsheep

Circom cheatsheep

tags: `blockchain` `ethereum`