真正的ZK應用：回看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。
原文鏈接：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用戶界麵的前端代碼中事先實現了很多功能，當一名存款者打開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相關的最巧妙的應用層項目之一。
聲明：
- 本文轉載自[medium]，著作權歸屬原作者[Faust，極客web3]，如對轉載有異議，請聯繫Gate Learn團隊（gatelearn@gate.io），團隊會根據相關流程盡速處理。
- 免責聲明：本文所錶達的觀點和意見僅代錶作者個人觀點，不構成任何投資建議。
- 文章其他語言版本由Gate Learn團隊翻譯， 在未提及Gate.io的情況下不得覆製、傳播或抄襲經翻譯文章。
مقالات ذات صلة
如何質押 ETH？
什麼是穩定幣 USDT？
真正的ZK應用：回看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。
原文鏈接：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用戶界麵的前端代碼中事先實現了很多功能，當一名存款者打開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相關的最巧妙的應用層項目之一。
聲明：
- 本文轉載自[medium]，著作權歸屬原作者[Faust，極客web3]，如對轉載有異議，請聯繫Gate Learn團隊（gatelearn@gate.io），團隊會根據相關流程盡速處理。
- 免責聲明：本文所錶達的觀點和意見僅代錶作者個人觀點，不構成任何投資建議。
- 文章其他語言版本由Gate Learn團隊翻譯， 在未提及Gate.io的情況下不得覆製、傳播或抄襲經翻譯文章。
مقالات ذات صلة
如何質押 ETH？