回看Tornado Cash原理:監管者的眼中釘卻是最精妙的ZK應用

作者:Faust,極客web3

導語:近期Vitalik和一些學者聯名發表了新論文,其中提到了Tornado Cash如何實現反xi錢方案(其實就是讓取款人證明,自己的存款記錄屬於一個不包含黑錢的集合),但文中缺乏對Tornado Cash業務邏輯與原理的細緻解讀,讓人似懂非懂。

此外值得一提的是,Tornado為代表的隱私項目才是真正用到了ZK-SNARK算法的零知識性,而大多數打著ZK旗號的Rollup,用到的只是ZK-SNARK的簡潔性。很多時候人們往往混淆了Validity Proof與ZK的區別,而Tornado恰好是理解ZK應用的極佳案例。

本文作者恰好在2022年於Web3Caff Research寫過一篇關於Tornado原理的文章,今日將其部分段落節選並拓展,整理成文,以便大家系統的理解Tornado Cash。

原文鏈接:

https://research.web3caff.com/zh/archives/2663?ref=157

“龍捲風”的原理

Tornado Cash是利用了零知識證明的混幣器協議,舊版本在2019年投入使用,新版本在2021年底啟動了beta版。 Tornado舊版本基本實現了去中心化,鏈上合約開源且無多簽控制,前端代碼開源且備份在了IPFS網絡裡。由於舊版Tornado的整體結構更簡單易懂,所以本文將針對舊版本進行解讀。

Tornado的主要思路是:把大量的存取款行為混雜在一起,存款者在Tornado存入Token後,出示ZK Proof證明自己存過款,再用一個新地址提款,以此切斷存取款地址之間的關聯性。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

更具體的概括,Tornado就像一個玻璃箱,混雜了很多人放進去的Coin硬幣。我們能看到放Coin的是哪些人,但這些Coin高度同質化,如果有生面孔的人從玻璃箱拿走一枚Coin,我們很難知道他拿走的Coin最初是誰放進去的。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

這種場景似乎屢見不鮮:當我們從Uniswap池子裡SWAP幾枚ETH時,根本無法知道劃走的ETH是誰提供的,因為曾給Uniswap提供流動性的人太多了。但不同之處是,每次用Uniswap劃走Token,我們需要用其他Token作為等價的成本,且不能把資金“私密的”轉讓給別人;而混幣器只需要提款者出示存款憑證就行。

為了讓存取款動作看起來有同質性,Tornado池子的存款地址每次存入的資金、取款地址每次取出的資金都保持一致,比如某個池子的100個存款者和100名取款者,雖然公開可見,但看起來彼此沒有任何联系,而且每人存入的金額、取出的金額,都是一樣的。這時就可以混淆視聽,沒法按照存取款金額判斷關聯性,進而切斷資金轉移痕跡,顯而易見的是,這為xi錢行為提供了天然的便利。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

但有一個關鍵問題:取款者在提款時,怎麼證明自己存過款?向混幣器發起取款的地址,與所有的存款地址都不關聯,那麼該如何判斷他的提款資格?看起來最直接的方法,是取款者直接披露自己的存款記錄是哪一筆,但這就直接洩露了身份。此時零知識證明就派上了用場。

提款者出具一個ZK Proof,證明自己在Tornado合約裡有存款記錄,且該筆存款尚未被提取,就能順利發起取款。零知識證明本身就實現了隱私保護,外界只知道:取款人的確往資金池裡存過款,但不知道他對應哪個存款者。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

要證明“我在Tornado資金池裡存過款”可以被轉化為“我的存款記錄可以在Tornado合約裡找到”。如果用Cn表示存款記錄,問題就歸納為:

已知Tornado的存款記錄集合為{C1,C2,…C100…},取款者Bob證明自己曾用手上的密鑰,生成了存款記錄裡的某個Cn,但通過ZK不洩露Cn具體是哪個。

這裡要用到Merkle Proof的特殊性質。因為Tornado的所有存款記錄,都存進了鏈上構造的一棵MerkleTree,作為其最底層的葉子結點,而葉子總數約為2的20次冪>100萬,大多數都處於空白狀態(賦予了初始值)。每當有新存款行為產生時,合約就會把其對應的特徵值Commitment寫入一個葉子裡,然後更新Merkle Tree的root。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

比如,Bob的存款操作是Tornado有史以來第1萬筆,那麼與這筆存款有關聯的一個特徵值Cn會寫入Merkle Tree的第1萬個葉子結點,也即C10000= Cn。然後合約會自動算出新的Root,update一下。 (ps:為了節約計算量,Tornado合約會緩存之前一批有變化的節點的數據,比如下圖中的Fs1和Fs2、Fs0)

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

而MerkleProof本身很簡潔輕便,它利用了樹狀數據結構在檢索/溯源過程中的簡潔性。若想對外證明某筆交易TD存在於MerkleTree中,只要給出Root對應的MerkleProof(如下圖中右邊的部分),它相當簡潔。如果Merkle Tree格外龐大,底層葉子有2的20次冪個,也就是包含100萬筆存款記錄,Merkle Proof也只需要包含21個節點的數值,非常短。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

如果要證明某筆交易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 Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

Tornado業務邏輯詳解

Tornado用戶界面的前端代碼中事先實現了很多功能,當一名存款者打開TornadoCash網頁並點擊存款按鈕後,前端代碼附帶的程序會在本地生成2個隨機數K和r,隨後會計算出Cn=Hash (K,r)的值,再把Cn(就是下圖中的commitment)傳入Tornado合約,插入到後者記錄的Merkle Tree裡。說白了,K和r相當於私鑰。它們很重要,系統會提示用戶妥善保存。後面提款時仍然要用到K和r。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

值得注意的是,以上工作皆發生於鏈下,也就是說:Tornado合約和外界觀察者都不知曉K和r。如果K和r被洩露了,就類似於錢包私鑰被盜。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

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個參數會公開發佈到鏈上,外界可以獲知,但不影響隱私。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

這裡面有個細節,就是存款操作生成Cn時,用了2個隨機數K和r來生成Cn,而不是單個隨機數。這是因為單個隨機數不夠安全,有一定概率發生碰撞,比如,採用單隨機數可能導致兩個不同的存款者恰巧採用1個同樣的隨機數,導致生成的Cn撞車。

至於上圖中的A,代表接收提款的地址,由提款者自己填寫。 nf則是一個防止重放攻擊的標識符,其數值nf=Hash(K),K就是存款生成Cn那一步用到的2個隨機數之一(K和r)。這樣一來,nf就與Cn關聯了起來,換言之,每個Cn都有對應的nf,兩者一一關聯。

為什麼要防止重放攻擊呢?由於混幣器在設計上的特性,取款時不知道用戶提走的幣對應Merkle樹的哪個葉子Cn,也就不知道提款人和哪些存款人關聯,就不知道提款人到底存過幾次款。提款者可以利用這一特性頻繁提款,發起重放攻擊,多次從混幣器池裡取走Token,直到把資金池抽乾。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

在這裡,nf標識符的作用類似於每個以太坊地址都有的交易計數器nonce,都是為了防止某筆交易被重放而設置。當一筆取款發生時,取款者需要提交一個nf,檢查這個nf是否已被使用過(記錄在案):如果有,此次取款無效。如果沒有,表示該nf尚未被使用,取款有效,對應的nf會被記錄下來。下次再有人提交這個nf時,對應的取款動作直接判定為無效。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

如果有人胡亂生成一個合約沒記錄過的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往往會填寫一個乾淨的新地址,也不會洩露個人信息。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

但這裡面有個小問題,就是用戶在取款時,為了不可溯源,往往用新申請的地址發起取款交易,此時新地址沒有ETH來支付gas費。所以取款地址發起取款時,要顯式聲明一個中繼者relayer,由它代付gas費,之後混幣器合約會直接從用戶提款裡扣掉一部分交給relayer,作為回報。

回看Tornado Cash原理:監管者的眼中釘,卻是最精妙的ZK應用

綜上所述,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實例解析

Total
0
Shares
Related Posts