回看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。
原文链接：
“龙卷风”的原理
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的所有存款记录，都存进了链上构造的一棵MerkleTree，作为其最底层的叶子结点，而叶子总数约为2的20次幂>100万，大多数都处于空白状态（赋予了初始值）。每当有新存款行为产生时，合约就会把其对应的特征值Commitment写入一个叶子里，然后更新Merkle Tree的root。
比如，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上有记录的某笔存款哈希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个参数会公开发布到链上，外界可以获知，但不影响隐私。
这里面有个细节，就是存款操作生成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相关的最巧妙的应用层项目之一。
参考资料
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實例解析