前陣子被監管者盯上的混幣器協議 Tornado Cash，其實是理解 ZK 應用的最佳案例。
（前情提要：解讀V神論文「隱私池Privacy Pools」：實現合規相容、防範Tornado Cash監管悲劇 ）
（背景補充：Tornado Cash創辦人遭美司法部控洗錢，專家：「於法無理」恐破壞開源信仰 ）
近期 Vitalik 和一些學者聯名發表了新論文，其中提到了 Tornado Cash 如何實現反洗錢方案（其實就是讓取款人證明，自己的存款記錄屬於一個不包含黑錢的集合）， 但文中缺乏對 Tornado Cash 業務邏輯與原理的細緻解讀，讓人似懂非懂。
此外值得一提的是，Tornado 為代表的隱私專案才是真正用到了 ZK-SNARK 演算法的零知識性，而大多數打著 ZK 旗號的 Rollup，用到的只是 ZK-SNARK 的簡潔性。很多時候人們往往混淆了 Validity Proof 與 ZK 的區別，而 Tornado 恰好是理解 ZK 應用的極佳案例。
延伸閱讀：科普｜zk-SNARKs是什麼？V神定調零知識證明未來十年「非常重要」
本文作者恰好在 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 名取款者，雖然公開可見，但看起來彼此沒有任何聯絡，而且每人存入的金額、取出的金額，都是一樣的。
這時就可以混淆視聽，沒法按照存取款金額判斷關聯性，進而切斷資金轉移痕跡，顯而易見的是，這為洗錢行為提供了天然的便利。
但有一個關鍵問題：取款者在提款時，怎麼證明自己存過款？向混幣器發起取款的地址，與所有的存款地址都不關聯，那麼該如何判斷他的提款資格？看起來最直接的方法，是取款者直接披露自己的存款記錄是哪一筆，但這就直接洩露了身份。此時零知識證明就派上了用場。
提款者出具一個 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。
延伸閱讀：CZ開嗆：銀行該用默克爾樹作證明，就算儲備沒100%也該知道有多少
比如，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 上有記錄的某筆存款hash 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 個引數會公開發布到鏈上，外界可以獲知，但不影響隱私。
延伸閱讀：重入攻擊是什麼？Curve池內的7000萬美元怎麼丟的？
這裡面有個細節，就是存款操作生成 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 相關的最巧妙的應用層專案之一。
相關報導
Tornado Cash開發者傳已被釋放，治理代幣TORN暴漲27%
