最精妙的 ZK 應用：回看 Tornado Cash 的原理與業務邏輯
作者：Faust，極客 Web3
封面：Tornado Cash
導語：近期 Vitalik 和一些學者聯名發表了新論文，其中提到了 Tornado Cash 如何實現反 xi 錢方案（其實就是讓取款人證明，自己的存款記錄屬於一個不包含黑錢的集合），但文中缺乏對 Tornado Cash 業務邏輯與原理的細緻解讀，讓人似懂非懂。
此外值得一提的是，Tornado 為代表的隱私專案才是真正用到了 ZK-SNARK 演算法的零知識性，而大多數打著 ZK 旗號的 Rollup，用到的只是 ZK-SNARK 的簡潔性。 很多時候人們往往混淆了 Validity Proof 與 ZK 的區別，而 Tornado 恰好是理解 ZK 應用的極佳案例。
本文作者恰好在 2022 年於 Web3Caff Research 寫過一篇關於 Tornado 原理的文章，今日將其部分段落節選並拓展，整理成文，以便大家系統的理解 Tornado Cash。
原文連結：
“龍捲風” 的原理
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 的所有存款記錄，都存進了鏈上構造的一棵 Merkle Tree，作為其最底層的葉子結點，而葉子總數約為 2 的 20 次冪>100 萬，大多數都處於空白狀態（賦予了初始值）。 每當有新存款行為產生時，合約就會把其對應的特徵值 Commitment 寫入一個葉子里，然後更新 Merkle Tree 的 root。
比如，Bob 的存款操作是 Tornado 有史以來第 1 萬筆，那麼與這筆存款有關聯的一個特徵值 Cn 會寫入 Merkle Tree 的第 1 萬個葉子結點，也即 C10000 = Cn。 然後合約會自動算出新的 Root，update 一下。（ps：為了節約計算量，Tornado 合約會緩存之前一批有變化的節點的數據，比如下圖中的 Fs1 和 Fs2、Fs0）
而 Merkle Proof 本身很簡潔輕便，它利用了樹狀數據結構在檢索/溯源過程中的簡潔性。 若想對外證明某筆交易 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 使用者介面的前端代碼中事先實現了很多功能，當一名存款者打開 Tornado Cash 網頁並點擊存款按鈕後，前端代碼附帶的程式會在本地生成 2 個隨機數 K 和 r，隨後會計算出 Cn=Hash（K，r）的值，再把 Cn（就是下圖中的 commitment）傳入 Tornado 合約，插入到後者記錄的 Merkle Tree 裡。 說白了，K 和 r 相當於私鑰。 它們很重要，系統會提示使用者妥善保存。 後面提款時仍然要用到 K 和 r。
（此處的 encryptedNote 是可選項，允許使用者把憑證 K 和 r 用私鑰加密，存儲到鏈上，防止遺忘）
值得注意的是，以上工作皆发生于链下，也就是说：Tornado 合约和外界观察者都不知晓 K 和 r。如果 K 和 r 被泄露了，就类似于钱包私钥被盗。
Tornado 合約收到使用者存款，並收到使用者提交的 Cn=Hash（K，r）後，便將 Cn 插入到 Merkle 樹的最底層，作為新的葉子結點，同時會更新 Root 的數值。 所以，Cn 和使用者的存款動作是一對一關聯的，外界可以知道每個 Cn 對應著哪個使用者，知道有哪些人往混幣器里存入了 Token，並且知道每個存款者對應的存款記錄 Cn。
在取款步驟中，取款者在前端網頁里輸入憑證/私鑰（存款時生成的隨機數 K 和 r），Tornado Cash 前端代碼中的程式會使用 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 個參數會公開發佈到鏈上，外界可以獲知，但不影響隱私。
這裡面有個細節，就是存款操作生成 Po 時，用了 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 實例解析
免責聲明：作為區塊鏈資訊平臺，本站所發佈文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。 本文內容僅用於資訊分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
