導語:
近期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就像一個玻璃箱,混雜了很多人放進去的Coin硬幣。我們能看到放Coin的是哪些人,但這些Coin高度衕質化,如果有生麵孔的人從玻璃箱拿走一枚Coin,我們很難知道他拿走的Coin最初是誰放進去的。
(圖源:rareskills)
這種場景似乎屢見不鮮:當我們從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)
(圖源:RareSkills)
而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 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的數值。但需要註意的是,這棵Merkle Tree的葉子併不記録進合約狀態中,而隻作爲event參數收録進過往區塊裡。Tornado合約隻記録merkle root,提款時用戶通過merkle Proof,證明存款記録能對應當前merkle root就行,道理有點像輕客戶端跨鏈橋的提款。
這一步其實可以看出Tornado在設計上的巧妙:爲了節約gas費,不把完整的merkle tree記録進合約狀態裡,隻記録一個root;
tree的葉子作爲event數據,單純放在歷史區塊記録中,這跟Rollup節約gas成本的原理有互通之處(雖然細節不一樣)。Rollup的橋合約最少隻需要記録root,併通過merkle proof放行提款
在取款步驟中,取款者在前端網頁裡輸入憑證/私鑰(存款時生成的隨機數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個參數會公開髮布到鏈上,外界可以穫知,但不影響隱私。
這裡麵有個細節,就是存款操作生成Cn時,用了2個隨機數K和r來生成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相關的最巧妙的應用層項目之一。
導語:
近期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就像一個玻璃箱,混雜了很多人放進去的Coin硬幣。我們能看到放Coin的是哪些人,但這些Coin高度衕質化,如果有生麵孔的人從玻璃箱拿走一枚Coin,我們很難知道他拿走的Coin最初是誰放進去的。
(圖源:rareskills)
這種場景似乎屢見不鮮:當我們從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)
(圖源:RareSkills)
而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 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的數值。但需要註意的是,這棵Merkle Tree的葉子併不記録進合約狀態中,而隻作爲event參數收録進過往區塊裡。Tornado合約隻記録merkle root,提款時用戶通過merkle Proof,證明存款記録能對應當前merkle root就行,道理有點像輕客戶端跨鏈橋的提款。
這一步其實可以看出Tornado在設計上的巧妙:爲了節約gas費,不把完整的merkle tree記録進合約狀態裡,隻記録一個root;
tree的葉子作爲event數據,單純放在歷史區塊記録中,這跟Rollup節約gas成本的原理有互通之處(雖然細節不一樣)。Rollup的橋合約最少隻需要記録root,併通過merkle proof放行提款
在取款步驟中,取款者在前端網頁裡輸入憑證/私鑰(存款時生成的隨機數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個參數會公開髮布到鏈上,外界可以穫知,但不影響隱私。
這裡麵有個細節,就是存款操作生成Cn時,用了2個隨機數K和r來生成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相關的最巧妙的應用層項目之一。