Tornado Cash 简介
Tornado Cash 是一个加密货币智能合约混币器（mixer），它允许用户使用一个地址存入加密货币，并使用另一个钱包提取，而不会在这两个地址之间产生可追踪的联系。
Tornado Cash 可能是最具标志性的零知识（zero knowledge）智能合约应用，因此我们将从足够底层的角度解释它的工作原理，以便程序员能够复现该应用程序。
本文假设读者了解 Merkle 树的工作原理，并且知道逆向推导密码学哈希是不可行的。同时假设读者至少具备扎实的 Solidity 中级水平（因为我们将阅读部分源代码片段）。
Tornado Cash 是一个相当高级的智能合约，如果你对这门语言还不熟悉，请先查看我们的 Solidity Tutorial。
关于 Tornado Cash 的简短警告
法律问题
Tornado Cash 目前受到美国政府的制裁，与之交互可能会“污染”（taint）你的钱包，并导致其中的交易在以后与中心化交易所交互时被标记。
2024 年更新：截至 2024 年 11 月 28 日，美国上诉法院已解除该制裁。
Tornado Cash 黑客事件
在 5 月 27 日，Tornado Cash governance smart contracts（不是我们在此要审查的智能合约）遭到黑客攻击，攻击者通过了一项恶意提案，使他们获得了大多数用于治理的 ERC20 投票代币 ERC20 voting tokens for governance。他们随后 handed back control（交还了控制权），只为自己保留了相对较少的一部分。
零知识证明的工作原理（写给讨厌数学的程序员）
你不需要了解零知识证明算法也能理解 Tornado Cash 的工作原理，但你必须知道零知识证明是如何工作的。与它们的名称以及许多流行的例子相反，零知识证明（Zero Knowledge Proofs）证明的是计算的有效性，而不是对某个事实的知情权。它们并不执行计算本身。它们接受一个预先商定的计算、一个该计算已被执行的证明，以及计算的结果，然后确定证明者是否真的运行了该计算并产生了该输出。零知识的部分来自于一个可选特性，即计算证明的表示方式可以不泄露关于输入的任何信息。
例如，你可以使用 RSA algorithm 证明你知道一个数字的质因数而不泄露它们。RSA 并不孤立地声明“我知道两个秘密数字”；它证明了你将两个隐藏的数字相乘并生成了公开的数字。RSA 加密实际上只是零知识证明的一个特例。在 RSA 中，你证明你知道两个相乘能产生公钥的秘密质数。在零知识证明中，你可以将这种“神奇的乘法”推广到任意算术和布尔运算。一旦我们有了基本运算的零知识操作，我们就可以为更奇特的事物构建零知识证明，例如证明我们知道哈希函数、Merkle 根的预映像（preimage），甚至是一个功能完备的虚拟机。
另一点：零知识证明的验证并不执行计算，它只验证某人执行了计算并产生了其所声明的输出。
还有一个有用的推论：为了生成（而不是验证）一个计算的零知识证明，你必须实际执行该计算。
这很有道理，对吧？如果你没有实际对预映像进行哈希处理，你怎么能证明你知道一个哈希的预映像呢？因此，证明者实际上执行了计算，并创建了一些被称为证明的辅助数据，以证明他们正确地完成了计算。
当你验证 RSA 签名时，你并不会把别人的私钥因子相乘来产生他们的公钥，那就本末倒置了。你只是验证签名并使用单独的算法核对消息。因此，一个计算包含以下内容：
verifier_algorithm(proof, computation, public_output) == true
在 RSA 的语境中，你可以把公钥看作计算的结果，把签名和消息看作零知识证明。
计算和输出是公开的。我们同意我们正在使用某种哈希函数并得到了某个输出。证明“隐藏”了被使用的输入，并且只证明了执行该哈希函数并产生了该输出。
仅凭证明，验证者无法计算出 public_output。验证步骤不执行计算，它只基于证明来验证声称产生公开输出的计算。
我们在本文中不会教授零知识算法，但只要你能接受我们可以在不亲自执行计算的情况下证明计算已发生，我们就可以继续前进了。
匿名加密货币转账是如何工作的：混币（mixing）
从根本上说，Tornado Cash 的匿名化策略是混币，类似于 Monero 等其他匿名加密货币。多个用户将他们的加密货币提交到一个地址，将他们的存款“混合”在一起。然后他们以一种存款人和取款人无法联系在一起的方式取款。
想象一下有 100 个人各自把一张一美元钞票放到一堆里。一天后，另外 100 个人出现，每个人从中拿走一张一美元钞票。在这种机制下，我们完全不知道最初的存款人想把钱寄给谁。
这里有一个明显的问题，如果_任何人_都可以从堆里拿走现金，钱很快就会被偷光。但如果我们试图留下一些关于谁有权提取的元数据，那就会暴露存款人试图把钱寄给谁。
混币永远不可能完全私密
当你向 Tornado Cash 发送 Ether 时，这是完全公开的。当你从 Tornado Cash 提取时，这也同样是完全公开的。不公开的是所涉及的这两个地址之间的关联（假设有足够多的其他存款人和取款人）。
人们对一个地址所能知道的只是“这个地址的 Ether 来自 Tornado Cash”或“这另一个地址向 Tornado Cash 存过款”。当一个地址从 Tornado Cash 取款时，人们无法分辨这些加密货币来自哪个存款人。
没有零知识证明的 Tornado Cash：大量哈希预映像证明的逻辑或（OR）
让我们试着在不考虑隐私的情况下解决这个问题。
存款人生成两个秘密数字，将它们拼接起来，并在存入 ETH 时将其哈希值放在链上（稍后我们将讨论为什么要生成两个秘密数字而不是一个）。当几个人存款时，智能合约中就会存放几个我们不知道预映像的公开哈希值。
取款人出现，并揭示其中一个哈希值的预映像（这两个秘密数字），然后取出他们的存款。
这显然行不通，因为这表明存款人在链下将秘密数字传达给了取款人。
然而，如果取款人能够证明他们知道_其中一个哈希_的预映像，而_不暴露具体是哪一个哈希_，并且_不暴露该哈希的预映像_，那么我们就拥有了一个功能完整的加密货币混币器！
对此的一个朴素的解决方案是创建一个循环遍历哈希的计算：
zkproof_preimage_is_valid(proof, hash_{1}) OR
zkproof_preimage_is_valid(proof, hash_{2}) OR
zkproof_preimage_is_valid(proof, hash_{3}) OR
...
zkproof_preimage_is_valid(proof, hash_{n-1}) OR
zkproof_preimage_is_valid(proof, hash_{n})
请记住，验证者并没有实际执行上述计算，所以我们不知道哪个哈希是有效的那一个。验证者（Tornado Cash）只是验证证明者执行了上述计算并且它返回了 true。它是如何返回 true 的并不重要，重要的是它确实返回了 true；并且只有在证明者知道其中一个预映像时，它才能返回 true。
此时需要注意的一点非常重要：所有存款的哈希值都是公开已知的。当用户存款时，他们提交这两个秘密数字的哈希值，而且该哈希值是公开的。我们试图隐瞒的是取款人知道哪个哈希值的预映像。
但这涉及到一个非常庞大的计算。包含大量存款的大型 for 循环成本非常昂贵。[1]
我们需要一个能够紧凑地容纳大量哈希值的数据结构，幸运的是我们确实有：Merkle 树。
使用 Merkle 树存储大量哈希值
与其循环遍历所有的哈希，我们不如这样声明：“我知道其中一个哈希的预映像”，并且“该哈希在 Merkle 树内”。这与指着一个非常长的哈希数组说“我知道其中一个哈希的预映像”效果相同，只不过效率要高得多。
Merkle 证明（Merkle Proofs）的大小随树的大小呈对数增长，因此不需要太多的额外工作（相比于我们之前庞大的 for 循环）。
当存入加密货币时，用户生成两个秘密数字，拼接它们，对它们进行哈希运算，并将该哈希放入 Merkle 树中。
取款时，取款人提供一个叶子哈希的预映像，然后通过 Merkle 证明该叶子哈希在树中。
这当然会将存款人和取款人联系起来，但如果我们以零知识的方式同时执行 Merkle 证明和叶子预映像验证，这种联系就被切断了！
零知识证明让我们能够证明我们确实针对公开的 Merkle 根生成了有效的 Merkle 证明以及叶子的预映像——而不必展示我们是如何进行该计算的。
仅仅提供拥有 Merkle 证明并生成了根的零知识证明是不够安全的，取款人还必须证明他们知道该叶子的预映像。
Merkle 树的叶子都是公开的。每次有人存款时，他们提供的哈希都会被公开存储。由于 Merkle 树是完全公开的，任何人都可以为任何叶子计算 Merkle 证明。
因此，仅仅证明叶子在树中并不足以防止伪造证明导致的盗窃。
取款人还必须证明知晓讨论中的该叶子的预映像，而不泄露叶子本身。请记住，叶子本身就是两个数字的哈希。
你可以看到在 function for deposit 中的 _commitment 参数是公开的。_commitment 变量是被添加到树中的叶子，也就是那两个秘密数字的哈希，存款人不会公开这两个秘密数字。
/**
@dev Deposit funds into the contract. The caller must send (for ETH) or approve (for ERC20) value equal to or `denomination` of this instance.
@param _commitment the note commitment, which is PedersenHash(nullifier + secret)
**/
function deposit(bytes32 _commitment) external payable nonReentrant {
require(!commitments[_commitment], "The commitment has been submitted");
uint32 insertedIndex = _insert(_commitment);
commitments[_commitment] = true;
_processDeposit();
emit Deposit(_commitment, insertedIndex, block.timestamp);
}
实际上，取款证明包括证明已经执行了以下计算：
processMerkleProof(merkleProof, hash(concat(secret1, secret2))) == root
其中 processMerkleProof 将 Merkle 证明和叶子作为参数，而 hash(concat(secret1, secret2)) 生成该叶子。
在 Tornado Cash 的上下文中，验证者就是 Tornado Cash 智能合约，它会向任何提供有效证明的人释放资金。
证明者是能够证明自己执行了哈希计算并生成了其中一个叶子的取款人。通常，唯一能够取款的人也就是当初存款的人，因为只有该方能证明他们知道哈希预映像。当然，该用户必须使用一个不同且完全无关联的地址来进行取款！
取款人实际执行了上述计算（Merkle 证明和叶子哈希生成），生成了他们正确执行该计算的 zk-proof（零知识证明），然后将这个证明提供给智能合约。
在证明中，merkleProof 和 {secret1, secret2} 是隐藏的，但借助于计算证明，验证者可以验证取款人确实运行了计算来正确生成叶子和 Merkle 根。
所以让我们总结一下：
- 存款人：
- 生成两个秘密数字，并由它们的拼接内容创建一个 commitment 哈希
- 提交一个 commitment 哈希
- 将加密货币转入 Tornado Cash
- Tornado Cash：
- 在存款阶段：
- 将 commitment 哈希添加到 Merkle 树中
- 在存款阶段：
- 取款人：
- 为 Merkle 根生成有效的 Merkle 证明
- 根据两个秘密数字生成 commitment 哈希
- 生成上述计算的 zk-proof
- 将证明提交给 Tornado Cash
- Tornado Cash
- 在取款阶段：
- 根据 Merkle 根验证各项证明
- 将加密货币转给取款人
- 在取款阶段：
防止多次取款
上面的方案存在一个问题：什么能防止我们多次取款？按理说，为了将已经提取的存款入账，我们不得不将叶子从 Merkle 树中“移除”，但这就会暴露哪个存款是我们的！
Tornado Cash 的处理方式是永远不会从 Merkle 树中移除叶子。一旦叶子被添加到 Merkle 树中，它就会永远留在那。
为了防止多次取款，智能合约使用了一种被称为“作废者机制（nullifier scheme）”的方法，这在零知识应用和协议中非常常见。
作废者机制（Nullifier Scheme）
零知识证明中的 Nullifier 机制表现得就像一种提供了匿名层的奇特 nonce。
现在就很清楚为什么组成叶子的是两个秘密数字而不是一个了。
进入存款哈希的这两个数字分别是 nullifier（作废者）和 secret（秘密），而叶子是按顺序 concat(nullifier, secret) 的哈希值。
在取款期间，用户必须提交 nullifier 的哈希值（即 nullifierHash），并证明他们将 nullifier 和 secret 拼接并哈希以产生其中一个叶子。智能合约随后可以（使用零知识算法）验证发送者是否真的知道 nullifier 哈希的预映像证明。
nullifier 哈希被添加到一个 mapping 中以确保其不会被重复使用。
这就是为什么我们需要两个秘密数字。如果我们公开了这两个数字，我们就会知道取款人指向的是哪个叶子！通过只公开其中一个构成数字，就不可能确定它与哪个叶子相关联。
请记住，在给出隐秘输入的情况下，零知识证明验证无法计算出 nullifier，它只能验证计算、输出和证明是一致的。这就是为什么用户必须提交公开的 nullifierHash 并证明他们是通过隐藏的 nullifier 计算出它的。
你可以在下方截图中 Tornado Cash 的 withdraw function 中看到这个逻辑。
总结一下。用户必须证明：
- 他们知道叶子的预映像
nullifier以前从未使用过（这是一个简单的 Solidity mapping，不是 zk 验证步骤）- 他们可以生成
nullifier哈希及nullifier的预映像
以下是可能的结果：
- 用户提供了错误的
nullifier：用于检查nullifier及其预映像的 zk 证明将无法通过 - 用户提供了错误的
secret：用于叶子预映像的 zk 证明将无法通过 - 用户提供了错误的
nullifierHash（试图绕过第 86 行的检查）：用于nullifier及其预映像的 zk 证明将无法通过
增量 Merkle 树（Incremental Merkle Tree）是一种 gas 高效的 Merkle 树
你可能已经注意到，我们在前面的解释中耍了个小把戏。你如何能在链上更新 Merkle 树而不耗尽 gas 呢？想必有大量的存款，重新计算整棵树是不切实际的。
增量 Merkle 树通过一些聪明的优化绕过了这些限制。但在讨论这些优化之前，我们需要先了解这些限制。
增量 Merkle 树是一种固定深度的 Merkle 树，其中每个叶子初始值为零，非零值通过从最左侧的叶子向最右侧的叶子逐个替换零叶子来添加。
下面的动画演示了深度为 3 的增量 Merkle 树，它最多可容纳 8 个叶子。为了与我们 Tornado Cash 的领域术语保持一致，我们将这些称为变量标签为 的 “commitments”。
以下是增量 Merkle 树的一些重要特性：
- Merkle 树的深度固定为 32。这意味着它处理的存款不能超过
2^32 - 1笔。（这是 Tornado Cash 任意选择的深度，但它必须是一个常数）。 - Merkle 树的初始状态是一棵所有叶子都是
hash(bytes32(0))的树。 - 随着存款操作的进行，最左侧未使用的叶子将被 commitment 哈希覆盖。存款以“从左到右”的方式被添加到叶子上。
- 一旦向 Merkle 树进行了存款，它就不能被移除。
- 对于每一笔新的存款，都会存储一个新的根。Tornado Cash 将此称为“带有历史记录的 Merkle 树（Merkle Tree with history）”。因此 Tornado Cash 实际上存储的是 Merkle 根的一个数组，而不是单一的一个根。显然，随着成员的添加，Merkle 根会发生变化。
现在我们面临一个问题：在链上构建一棵有 2^32 - 1 个叶子的 Merkle 树将会耗尽 gas。仅仅计算第一层就需要超过 400 万次迭代，这显然行不通。
但是增量 Merkle 树的限制使得智能合约能够利用两个关键的不变性来走一条很大的计算捷径：当前节点右侧的所有内容都是具有可预测高度且所有根均为零的 Merkle 子树，而当前节点左侧的所有内容都可以被缓存而无需重新计算。
聪明的捷径 1：最新成员右侧的所有子树均由全零叶子的 Merkle 子树组成
全零叶子的 Merkle 子树具有可预先计算的预期根值。
由于所有的叶子初始都是零，构建 Merkle 树的很大一部分工作将包括计算所有叶子都为零的 Merkle 树。
请看下图，注意当所有的叶子都是零时，有多少计算是重复的：
大多数叶子对将是 bytes32(0) 和 bytes32(0) 的拼接。然后该哈希将与姐妹子树中完全相同的哈希进行拼接，依此类推。
Tornado Cash 预先计算了深度为零的树的哈希（只是 bytes32(0) 叶子的哈希）、拥有两个零叶子的子树的根、拥有四个零叶子的子树的根、拥有八个零叶子的子树的根，等等。
这意味着我们可以为一个（所有叶子全为零的）高度为 0、1、2……一直到 31 的 Merkle 树预先计算 Merkle 根（记住，Merkle 树的高度是固定的）。
对于叶子全部为零的 Merkle 子树的每一个可能高度，Tornado Cash 都预先进行了计算。以下是 Tornado Cash’s Merkle Tree With History 中的预计算列表：
/// @dev provides Zero (Empty) elements for a MiMC MerkleTree. Up to 32 levels
function zeros(uint256 i) public pure returns (bytes32) {
if (i == 0) return bytes32(0x2fe54c60d3acabf3343a35b6eba15db4821b340f76e741e2249685ed4899af6c);
else if (i == 1) return bytes32(0x256a6135777eee2fd26f54b8b7037a25439d5235caee224154186d2b8a52e31d);
else if (i == 2) return bytes32(0x1151949895e82ab19924de92c40a3d6f7bcb60d92b00504b8199613683f0c200);
else if (i == 3) return bytes32(0x20121ee811489ff8d61f09fb89e313f14959a0f28bb428a20dba6b0b068b3bdb);
else if (i == 4) return bytes32(0x0a89ca6ffa14cc462cfedb842c30ed221a50a3d6bf022a6a57dc82ab24c157c9);
else if (i == 5) return bytes32(0x24ca05c2b5cd42e890d6be94c68d0689f4f21c9cec9c0f13fe41d566dfb54959);
else if (i == 6) return bytes32(0x1ccb97c932565a92c60156bdba2d08f3bf1377464e025cee765679e604a7315c);
else if (i == 7) return bytes32(0x19156fbd7d1a8bf5cba8909367de1b624534ebab4f0f79e003bccdd1b182bdb4);
else if (i == 8) return bytes32(0x261af8c1f0912e465744641409f622d466c3920ac6e5ff37e36604cb11dfff80);
else if (i == 9) return bytes32(0x0058459724ff6ca5a1652fcbc3e82b93895cf08e975b19beab3f54c217d1c007);
else if (i == 10) return bytes32(0x1f04ef20dee48d39984d8eabe768a70eafa6310ad20849d4573c3c40c2ad1e30);
else if (i == 11) return bytes32(0x1bea3dec5dab51567ce7e200a30f7ba6d4276aeaa53e2686f962a46c66d511e5);
else if (i == 12) return bytes32(0x0ee0f941e2da4b9e31c3ca97a40d8fa9ce68d97c084177071b3cb46cd3372f0f);
else if (i == 13) return bytes32(0x1ca9503e8935884501bbaf20be14eb4c46b89772c97b96e3b2ebf3a36a948bbd);
else if (i == 14) return bytes32(0x133a80e30697cd55d8f7d4b0965b7be24057ba5dc3da898ee2187232446cb108);
else if (i == 15) return bytes32(0x13e6d8fc88839ed76e182c2a779af5b2c0da9dd18c90427a644f7e148a6253b6);
else if (i == 16) return bytes32(0x1eb16b057a477f4bc8f572ea6bee39561098f78f15bfb3699dcbb7bd8db61854);
else if (i == 17) return bytes32(0x0da2cb16a1ceaabf1c16b838f7a9e3f2a3a3088d9e0a6debaa748114620696ea);
else if (i == 18) return bytes32(0x24a3b3d822420b14b5d8cb6c28a574f01e98ea9e940551d2ebd75cee12649f9d);
else if (i == 19) return bytes32(0x198622acbd783d1b0d9064105b1fc8e4d8889de95c4c519b3f635809fe6afc05);
else if (i == 20) return bytes32(0x29d7ed391256ccc3ea596c86e933b89ff339d25ea8ddced975ae2fe30b5296d4);
else if (i == 21) return bytes32(0x19be59f2f0413ce78c0c3703a3a5451b1d7f39629fa33abd11548a76065b2967);
else if (i == 22) return bytes32(0x1ff3f61797e538b70e619310d33f2a063e7eb59104e112e95738da1254dc3453);
else if (i == 23) return bytes32(0x10c16ae9959cf8358980d9dd9616e48228737310a10e2b6b731c1a548f036c48);
else if (i == 24) return bytes32(0x0ba433a63174a90ac20992e75e3095496812b652685b5e1a2eae0b1bf4e8fcd1);
else if (i == 25) return bytes32(0x019ddb9df2bc98d987d0dfeca9d2b643deafab8f7036562e627c3667266a044c);
else if (i == 26) return bytes32(0x2d3c88b23175c5a5565db928414c66d1912b11acf974b2e644caaac04739ce99);
else if (i == 27) return bytes32(0x2eab55f6ae4e66e32c5189eed5c470840863445760f5ed7e7b69b2a62600f354);
else if (i == 28) return bytes32(0x002df37a2642621802383cf952bf4dd1f32e05433beeb1fd41031fb7eace979d);
else if (i == 29) return bytes32(0x104aeb41435db66c3e62feccc1d6f5d98d0a0ed75d1374db457cf462e3a1f427);
else if (i == 30) return bytes32(0x1f3c6fd858e9a7d4b0d1f38e256a09d81d5a5e3c963987e2d4b814cfab7c6ebb);
else if (i == 31) return bytes32(0x2c7a07d20dff79d01fecedc1134284a8d08436606c93693b67e333f671bf69cc);
else revert("Index out of bounds");
}
在计算 Merkle 根时，我们始终知道我们所处的“z 级别”，并且可以简单地获取预先计算好的、所有叶子均为零的 Merkle 子树根。
关于“零根（zero roots）”的技术细节
Tornado Cash 实际上并没有使用 hash(bytes32(0)) 作为空值，而是使用 hash(“tornado”)。这不影响算法，因为它只是一个常量。然而，使用零值代表“空”的概念来讨论增量 Merkle 树，比使用一个奇怪的常量更容易理解。
聪明的捷径 2：最新成员左侧的所有子树由根已被缓存（而无需重新计算）的子树组成
考虑我们添加第二笔存款的情况。我们已经计算过第一笔存款的哈希了。该哈希被缓存在 Tornado Cash 称之为 filledSubtrees 的一个 mapping 中。filledSubtree 就是 Merkle 树中的一个其中所有叶子非零的子树。在下方的动画中我们将其称为 fs：
重点是，只要你需要左侧的中间哈希，它就已经为你计算好了。
这个很好的特性是因为叶子不可改变或移除的限制而产生的副产品。一旦一棵子树填满了 commitments 而非零，它就永远不需要被重新计算。
现在让我们将其泛化。不要把我们左边的节点看作是“第一笔存款”，而是把它本身想象成一棵子树的根。
在最极端的情况下，考虑当我们放入最后一个叶子时。紧挨着我们左边的将是一棵由倒数第二个叶子（深度 0）组成的“树”，在其左边将是一个深度 1 的子树，在其左边将是一个深度 2（有 4 个叶子）的子树，在其左边将是一个深度 3（有 8 个叶子）的子树，等等。在最极端的情况下，这样的树也不会超过 32 棵。
结合捷径
我们左侧的所有部分都是已填充的子树（即使它只是一个叶子），我们右侧的所有部分则始终是零叶子或由全零叶子组成的子树。因为左侧的根已被缓存，而右侧的根是通过高度为 的全零子树预先计算好的，所以我们可以有效地计算任何层的任何中间哈希拼接，只需 32 次迭代即可在链上生成一棵深度为 32 的 Merkle 树。 这样做虽然也不便宜，但确是可行的。而且它绝对比 400 万次计算好太多了！
向左哈希还是向右哈希？
但当我们“一路哈希至根部”时，我们如何知道以什么顺序拼接各个子树的哈希值？
例如，我们将一个新的 commitment 哈希作为叶子添加进来。在我们上方的节点处，我们是将其拼接为 new_commitment | other_value 还是 other_value | new_commitment？
这里的技巧是：每个索引为偶数的节点都是左子节点，每个索引为奇数的节点都是右子节点。对于叶子节点和树的每一层都是如此。你可以在下图中看到这种模式。
让我们对这个模式建立一点直觉认识。如果要插入的是第 0 个叶子，那么在到根的路上我们只会一直向右哈希。0 ÷ 2 仍然是 0，根据上面的定义，0 是一个偶数。因为 0 是偶数，我们在通往根部的路上将永远是向右哈希。
现在让我们看看另一个极端情况。插入最后一个叶子时，在通向根部的路上必须总是向左哈希。向上的每一步对应的节点都是奇数。这种模式可泛化至中间的每一个节点；从叶子的索引开始，当我们在树上往上走时，重复除以二会告诉我们当前是在左子节点还是右子节点。以下动画说明了，当处于奇数节点时向左哈希，处于偶数节点时向右哈希：
所以在任何层级，我们都知道哈希值与其兄弟节点之间的相对位置关系。
因此，我们需要两方面的信息：
- 我们正在插入的节点的索引
- 当前索引是偶数还是奇数
下面是 Tornado Cash 源代码使用这些信息的截图。for 循环遍历了各个层级，以根据刚刚添加的新叶子重新生成 Merkle 根。
总而言之，要在链上更新 Merkle 根，我们需要：
- 在一个新索引处添加一个叶子，将其设为
currentIndex - 向上移动一层并将
currentIndex设为currentIndex除以2。然后，- 如果
currentIndex为奇数（odd），则与filledSubtree向左哈希 - 如果
currentIndex为偶数（even），则与预计算（precomputed）的零树向右哈希。
- 如果
如此不简单的算法能被浓缩进这么小的一段 Solidity 代码中，这非常酷。
由于根会随着每一笔存款而改变，Tornado Cash 会存储最近的 30 个根
每当插入一项数据，Merkle 根必定会发生改变。如果取款人针对最新根生成了一个 Merkle 证明（请记住，叶子是公开获取的），但刚好有一笔存款交易抢先成交并改变了根，这就可能产生问题；此时，Merkle 证明就不再有效了。zk 验证者算法确保提交的 Merkle 证明对于该根来说是有效的，所以如果根改变了，证明也就通不过了。
为了给取款人预留提取交易的时间，他们可以引用包含最近 30 个根中的任意一个。
变量 roots 是一个从 uint256 到 bytes32 的 mapping。当 Merkle 证明计算至根部时（循环完成），它被存入 roots 中。currentRootIndex 会不断增加直到 ROOT_HISTORY_SIZE，但一旦达到最大值（30），它就会覆盖索引 0 处的根。因此，它的表现就像一个固定大小的队列。下面是 Tornado Cash 的 Merkle 树代码中 _insert 函数的片段。根被重新计算后，就会以上述方式被存储。
增量 Merkle 树的存储变量
以下是让带有历史记录的 Merkle 树工作所需的存储变量。
mapping(uint256 => bytes32) public filledSubtrees;
mapping(uint256 => bytes32) public roots;
uint32 public constant ROOT_HISTORY_SIZE = 30;
uint32 public currentRootIndex = 0;
uint32 public nextIndex = 0;
filledSubtrees是我们已经计算完毕的子树（即所有的叶子都是非零的）roots是最近的 30 个根currentRootIndex是一个 0 到 29 的数字，用于作为roots的索引nextIndex是如果用户调用存款时即将被填充的当前叶子。
公开的 deposit() 函数是如何更新增量 Merkle 树的
当用户向 Tornado Cash 调用 deposit 时，系统会调用 _insert() 更新 Merkle 树，随后会调用 _processDeposit()。
function deposit(bytes32 _commitment) external payable nonReentrant {
require(!commitments[_commitment], "The commitment has been submitted");
uint32 insertedIndex = _insert(_commitment);
commitments[_commitment] = true;
_processDeposit();
emit Deposit(_commitment, insertedIndex, block.timestamp);
}
_processDeposit() 只是用来确保面额是准确的（根据你互动的不同 Tornado Cash 实例，你只能存入 0.1、1 或 10 个 Ether）。这个非常简单操作的代码如下所示。
function _processDeposit() internal override {
require(msg.value == denomination, "Please send `mixDenomination` ETH along with transaction");
}
超高度优化的 MiMC 哈希
为了在链上计算 Merkle 根，人们（显然）必须使用哈希算法，但 Tornado Cash 并没有使用传统的 keccak256；它使用的是 MiMC。
深究其原因有点超出了本文范围，但本质是由于对零知识证明生成而言，有些哈希的计算成本更低。MiMC 被设计为“zk 友好的（zk friendly）”，而 keccak256 则不然。
“zk 友好的”意思是，该算法能够自然地映射到零知识证明算法表示计算的方式上。
但这制造了一个有趣的难题：当添加新节点以重新计算根时，必须在链上计算 MiMC，而以太坊（Ethereum）并没有针对 zk 友好哈希的预编译合约。（也许你可以为此起草一个 EIP？）
因此，Tornado Cash 团队亲自用原始字节码编写了它。如果你在 Etherscan 查看 Tornado Cash 的合约验证，你会看到一个警告：
Etherscan 无法将原始字节码验证为 Solidity，因为 MiMC 哈希根本不是用 Solidity 编写的。
Tornado Cash 团队将 MiMC Hasher 部署为了一个单独的 smart contract。要使用 MiMC 哈希，Merkle 树代码会对该合约进行跨合约调用。正如你在下面的代码中所见，这些都是 static calls，因为接口将其定义为 pure，因此 Etherscan 显示它没有交易历史记录。
interface IHasher {
function MiMCSponge(uint256 in_xL, uint256 in_xR) external pure returns (uint256 xL, uint256 xR);
}
根据上文引用的 Tornado Cash 代码，我们知道它是以“接口（interface）”存在的。（github link）。
在 circom 库的 github issue 上，你可以看到对于为什么该代码甚至没用通过汇编块来实现 Solidity 版本的解释：直接进行栈操作是不可能的。
（旁注：非常底层的密码学算法是 Huff 语言的绝佳用例，你可以通过我们的 Huff Language Puzzles 来学习它。）
将你自己的哈希函数部署为原始字节码
circomlib js 代码库包含了用于创建原始字节码哈希的 JavaScript 工具。这里是生成 MiMC 和 Poseidon Hash 的代码。
从 Tornado Cash 中取款
首先，用户必须在本地使用 updateTree script 重建 Merkle 树。此脚本将下载所有相关的 solidity events 并重建 Merkle 树。然后，用户将针对 Merkle 证明和叶子 commitment 的预映像生成零知识证明。如前所述，Tornado Cash 存储了最近的 30 个 Merkle 根，因此这应当给用户留下了充足的时间来提交他们的证明。如果用户生成证明后等待太长时间，他们将不得不重新生成证明。
Tornado Cash 合约将检查：
- 提交的
nullifierHash以前未被使用过 - 根包含在根历史记录中（最近的 30 个根内）
- 零知识证明的核验：
a. 隐藏的哈希预映像确实生成了该叶子
b. 用户实际知道nullifierHash的预映像
c. 用户使用该叶子创建了一个 Merkle 证明，进而推导出了所提出的根。
d. 提出的根是最近 30 个根之一（这是在 Solidity 代码中公开检查的）
以下是上述步骤的可视化形式：
有了这样的理解后，下面 Tornado Cash 取款函数中的代码应该就不言自明了。
function withdraw(bytes calldata _proof,
bytes32 _root,
bytes32 _nullifierHash,
address payable _recipient,
address payable _relayer,
uint256 _fee,
uint256 _refund
) external payable nonReentrant {
require(_fee <= denomination, "Fee exceeds transfer value");
require(!nullifierHashes[_nullifierHash], "The note has been already spent");
require(isKnownRoot(_root), "Cannot find your merkle root"); // Make sure to use a recent onerequire(
verifier.verifyProof(
_proof,
[uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund]
),
"Invalid withdraw proof"
);
nullifierHashes[_nullifierHash] = true;
_processWithdraw(_recipient, _relayer, _fee, _refund);
emit Withdrawal(_recipient, _nullifierHash, _relayer, _fee);
}
上面的 _relayer、_fee 和 _refund 与向可选的交易中继者（relayers）支付费用有关，我们稍后会进行解释。
函数 isKnownRoot(root) 验证提交的根是否在最近的 30 个之内
这是一个简单的 do-while 循环，从当前索引（最后一个活动的叶子）向后循环查找，看看提交给取款函数的根是否在根的历史记录中。（github link）
因为回溯次数只有 30，所以我们不必担心无限循环耗尽过多的 gas。
/**
@dev Whether the root is present in the root history
*/function isKnownRoot(bytes32 _root) public view returns (bool) {
if (_root == 0) {
return false;
}
uint32 _currentRootIndex = currentRootIndex;
uint32 i = _currentRootIndex;
do {
if (_root == roots[i]) {
return true;
}
if (i == 0) {
i = ROOT_HISTORY_SIZE; // 30
}
i--;
} while (i != _currentRootIndex);
return false;
}
定义零知识证明计算的 Circom 代码
本节描述了用于生成验证 ZK 证明的电路的 Circom 代码。如果你对 Circom 还不熟悉并想学习它，请查看我们的 Circom zero knowledge puzzles。
尽管如此，我们还是会尝试在较高的层面上解释这部分 Circom 代码。
Circom 并不在区块链上执行，它被转译成了看起来令人发指的 Solidity 代码，你可以在 Tornado Cash 的 Verifier.sol 中看到。之所以它看起来如此可怕，是因为它实际上在执行用于 zk 证明验证的数学运算。谢天谢地，Circom 可读性强得多。
这里我们有三个组件：用来组合哈希的 HashLeftRight、DualMux（它只是给 MerkleTreeChecker 用的辅助工具）以及 MerkleTreeChecker。MerkleTreeChecker 接收一个 leaf、一个 root 和一个 proof。proof 包含两部分：pathElements（姐妹子树的 Merkle 根）和 pathIndices（指引电路在当前层级以何种顺序拼接哈希的指示器）。
最后一行，root === hashers[levels - 1].hash 就是最终判断根是否与 leaf 及 proof 相匹配的地方。
回顾一下，nullifierHash 是 nullifier 的哈希值，而 commitment 是 nullifier 和 secret 共同的哈希值。该计算的 Circom 表达方式如下。虽然可能难以阅读，但应该能清楚地看出输入是 nullifier 和 secret，而输出是 commitment 和 nullifierHash。
现在我们可以切入零知识算法的核心部分了
私有信号（private signal）意味着它是按照早先的命名法“隐藏在证明中”的。
在上述代码中，程序验证了 nullifier 哈希运算是否以有效方式进行。然后，commitment 预映像和 Merkle 证明会被提供给前面的 MerkleTree Verifier。
如果所有的检查都通过了，verifier 将返回 true，表示该证明有效，随后这个匿名地址就可以提取该笔存款了。
在取款期间防止被抢跑（Frontrunning）
安全研究人员可能已经注意到 Solidity 代码没有针对抢跑的防御机制。当有人向内存池（mempool）提交了一个有效的零知识证明时，是什么能阻止别人复制该证明并将取款地址替换为他们自己的？
这是我们为了简便而一笔带过的内容，但其实 Withdraw.circom 文件包含了用以将接收者（以及为 relayer 准备的其他所需参数）求平方的虚设信号（dummy signals）。这意味着 zk-proof 还必须展示取款人对接收者的地址求了平方并得到了其地址的平方值（请记住，地址只是 20 字节的数字）。将地址平方并同时计算 nullifier 与 secret 的哈希是一整套运算，因此任何部分的错误都会使整个证明失效。
什么是中继者（relayer）及手续费（fee）？
中继者（relayer）是一个离线机器人，它代其他用户支付 gas，作为交换会获得某种形式的报酬。Tornado Cash 的取款人通常希望使用全新的地址以增强隐私性，但是全新的地址没有任何 gas 用于支付取款所需的费用。
为了解决这个问题，取款人可以请求中继者执行交易，条件是中继者会获得一部分 Tornado Cash 的提取款作为回报。
中继者的取款地址也必须使用上文所描述的同样的抢跑保护机制，正如你可以在上面的代码截图中看到的那样。
deposit() 与 withdrawal() 过程的总结
当调用 deposit 时：
- 用户提交
hash(concat(nullifier, secret))，以及他们打算存入的加密货币。 - Tornado Cash 验证存入的金额是否符合其可接受的面额。
- Tornado Cash 将 commitment 添加为下一个叶子。叶子永远不会被移除。
当调用 withdraw 时：
- 用户根据 Tornado Cash 发出的事件在本地重建 Merkle 树。
- 用户必须（公开地）提供
nullifier的哈希值、他们作为验证目标的 Merkle 根，以及一份可以证明自己知晓nullifier、secret以及 Merkle 证明的 zk-proof。 - Tornado Cash 验证该
nullifier以前从未使用过。 - Tornado Cash 验证被提交的根是否属于最近的 30 个根之一。
- Tornado Cash 验证零知识证明。
没有任何东西能阻止用户提交一个没有已知预映像的无意义的叶子。但在那种情况下，存入的加密货币将永远卡在合约里。
智能合约架构的简要概述
以下是构成 Tornado Cash 的各种智能合约
Tornado.sol 是一个抽象合约，其实际上由 ERC20Tornado.sol 或 ETHTornado.sol 来实现，具体取决于其部署的目的是为了混币 ERC20 还是某种面额的 ETH。不同的 ETH 面额和 ERC20 代币都有各自专属的 Tornado Cash 实例。
MerkleTreeWithHistory.sol 包含了我们前面详细讨论过的 _insert() 和 isKnownRoot() 功能。
Verifier.sol 是 Circom 电路的 Solidity 转译输出。
cTornado.sol 是用于治理的 ERC20 代币，并不属于核心协议的一部分。
Tornado Cash 可进一步优化 gas 效率的地方
Tornado Cash 整体架构非常优秀，但仍存在一些 gas optimization 的机会。
- Tornado Cash 对具有全零叶子的预计算 Merkle 子树进行的是线性查找，但这实际上可以通过硬编码的二分查找在更少的操作次数内完成。
- Tornado Cash 常常为栈变量使用 uint32 类型；如果为了避免 EVM 执行隐式类型转换，使用 uint256 会是一个更好的选择。
- Tornado Cash 中有一些常量被没有必要地修饰为了 public。除非有智能合约要去读取这些值，否则不必要设为公开的常量，这只会增加智能合约的体积。
- 前缀操作符（++i）比后缀操作符（i++）的 gas 效率更高，并且 Tornado Cash 可以通过改变此操作而不影响自身逻辑。
nullifierHashes本身就是一个 public 的 mapping，但它还被包装在了一个isSpent()的公开 view 函数中。这是多余的。
结论
就是这样；我们已经审查了 Tornado Cash 的整个代码库，并对每个变量和函数的作用建立了深入的理解。Tornado Cash 将令人惊叹的复杂度装载到了一个相对小巧的代码库中。我们在这里分析了各种非同小可的技术，其中包括：
- 使用零知识证明来展示对哈希预映像的知悉且不泄露该预映像本身
- 如何在链上使用增量 Merkle 树
- 如何使用原生字节码编码出来的自定义哈希函数
- Nullifier 机制是如何工作的
- 如何匿名取款
- 如何防止基于零知识证明的 DApp 被抢跑
RareSkills
本资料是我们 Zero Knowledge Course 的一部分。如果你对通用的智能合约开发感兴趣，请查看我们为专业 Solidity 开发者设计的 Solidity Bootcamp。我们提供世界上最为严谨和最新的智能合约培训课程。
补充说明
[1] 任何熟悉 ZK 电路的人都知道我们不能创建任意长度的 for 循环。电路在创建时必须能容纳非常大的数组。然而，若说是对那么多的哈希进行“循环”在计算上是极其昂贵的，这种说法也是准确的，因为这等同于要创建一个大到不可行的巨型电路。
首发于 2023 年 6 月 27 日