Tornado Cash简介
Tornado Cash是加密货币混币器，其本质是智能合约，它允许用户用一个地址存入加密货币，然后再用另一个钱包地址取出，但却不会在这两个地址之间留下任何可被追踪的联系。
Tornado Cash可能是最具代表性的零知识智能合约应用了，因此我们会详细解析其底层原理，以便开发人员能够复现该应用。
这里先假定读者了解Merkle树的工作原理以及逆推哈希值是不可行的。同时，读者至少应具备扎实的Solidity中级水平（因为我们将阅读源码片段）。
Tornado Cash是一个相当高级的智能合约，所以如果您对这门编程语言还不熟悉，建议您首先阅读我们的Solidity教程。
关于Tornado Cash的快速提醒
法律问题
Tornado Cash目前受到美国政府的制裁，与其交互可能会“污染”您的钱包，这会导致后续由这个钱包发起的与中心化交易所交互的交易都会被标记。
Tornado cash攻击事件
在5月27日，Tornado Cash治理合约（与我们将要解析的智能合约不同）遭到黑客攻击，攻击者提交了一个恶意提案，赋予了他们治理合约中大部分ERC20投票代币的控制权。随后，他们归还了控制权并保留了相对较少的一部分代币。
零知识工作原理（适用于讨厌数学的程序员）
想要理解Tornado Cash的工作原理，您可以不了解零知识证明算法，但您必须了解零知识证明的工作原理。
与它们的名称和许多常见示例相反，零知识证明是证明一个计算的有效性，而不是某个特定事实的知识。它们不执行计算。它们通过一个约定好的计算过程、一个计算被执行的证明以及计算结果，来确定证明者是否确实执行了计算并得出了计算结果。零知识的部分来自可选特性，即计算的证明能够以不提供输入信息的方式表示。
举个例子，您可以使用RSA算法证明您知道一个数的质因数，但却不需要透露它们。RSA算法并不是单纯地证明了“我知道两个秘密数字”，它还证明了您将两个秘密数字相乘并生成了一个公开的数。RSA加密仅仅只是众多零知识证明应用中的一个特例。在RSA中，您可以通过将两个秘密的质因数相乘后得到您的公钥来证明您知道它们。在零知识证明中，我们将这种“魔法乘积”推广到任意算术和布尔操作。只要我们拥有了基本操作的零知识运算，我们就可以构建更加复杂的零知识证明，例如证明我们知道一个哈希的原像、Merkle根，甚至是一个功能完备的虚拟机。
另外一点：零知识证明的验证过程不会执行计算，它仅仅验证某人执行了计算并生成了他所声称的结果。
还有一个有用的推论：要生成(不是验证)一个计算过程的零知识证明，您必须实际地执行该计算。
这很有道理对吧？如果你没有实际地计算一个原像的哈希值，那你怎么证明你知道这个哈希的原像呢？因此，证明者需要实际地执行计算，同时会生成了一些辅助数据，这些辅助数据就是所说的证明，用来证明他们正确地执行了计算。
当您验证一个RSA签名时，您无法将别人的私钥因子相乘去生成他们的公钥，这么做的话就违背了最开始的初衷。您只需使用一个独立的算法就可以验证签名和消息是否正确了。
因此，一个由下列内容组成的计算：
verifier_algorithm(proof, computation, public_output) == true在RSA中，你可以将公钥视为计算的结果，将签名和消息视为零知识证明。
计算过程和输出是公开的。我们约定好使用一个确定的哈希函数，这样的话输出也是确定的。证明将使用到的输入给“隐藏”起来了，只证明了哈希函数被执行并生成了输出。
仅凭一个证明，验证者是无法计算出public_output的。验证步骤也不会执行计算，它只是验证公开的输出结果，证明和所声称的计算过程是否相匹配。
我们不会在本文中教授零知识算法，但是你只需要知道：我们可以在不执行计算的情况下去证明计算被执行了，然后我们就可以开始了。
匿名加密货币转账的工作原理：混合
从根本上来说，Tornado Cash的匿名化策略是混合，与Monero等其他匿名加密货币类似。用户们通过将其加密货币提交到同一个地址的方式，来把他们的存款“混合”到一起。以一种无法追踪存款人和取款人之间联系的方式取出。
你可以想象一下，现在有一百个人将一美元纸币叠放在一起。然后，第二天来了一百个不同的人，每人抽走一张纸币。在这种模式下，我们就无法知晓最初的存款人想要将钱打给谁了。
这里有一个很显而易见的问题，如果任何人都可以从这一摞钞票中抽出现金，那么它很快就会被偷光。但是，如果我们留下一些关于谁有权取款的元数据，则可以明确存款人的意图。
混合不可能是全部私密的
当您向Tornado Cash发送ETH时，这是完全公开的。当您从Tornado Cash中取款时，这也是完全公开的。不公开的是整个过程中所涉及到的两个地址之间的联系（假设有足够多的存款人和取款人）。
人们能够获得到的关于某个地址的全部信息就只有：“这个地址从Tornado Cash获得了ETH”或“其他地址向Tornado Cash存入了ETH”。当一个地址从Tornado Cash中取款时，人们无法知晓该加密货币来自于哪个存款人。
没有零知识的Tornado Cash： 需要使用非常多的逻辑或运算来验证哈希原像的证明
我们先不考虑隐私，然后尝试着解决一下这个问题。
存款人创建两个秘密数字，将它们拼接起来，然后在存入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。
很重要的一点是：所有的存款哈希都是公开的。当用户存款时，他们提交了两个秘密数字的哈希，而该哈希是公开的。我们需要隐藏的是取款人知道原像的那个哈希。
但是这个计算过程的计算量非常大。在大量的for循环中执行存款操作是很昂贵的。[1]
我们需要一个能够紧凑地存储大量哈希值的数据结构，幸运的是我们有：Merkle树。
使用Merkle树来批量存储哈希
相比于遍历所有哈希值，我们还可以说“我知道其中一个哈希值的原像”，“该哈希值存在于Merkle树中”。这与指着一个非常长的哈希数组说“我知道其中一个哈希值的原像”是一样的，只不过更加高效。
Merkle证明的大小与树的大小成对数关系，它不需要太多额外的工作量(与之前需要使用大量for循环相比)。
当存入加密货币时，用户生成两个秘密数字，将它们拼接在一起，对其做哈希运算，然后将哈希值加入到Merkle树中。
在取款时，取款人生成一个叶子节点哈希的原像，然后通过Merkle证明来证明该叶子哈希位于树中。
毫无疑问，这将存款人与取款人联系在了一起，但如果我们以零知识的方式验证Merkle证明和叶子哈希原像，那么这个联系将被切断！
零知识证明能够证明我们生成了基于公开的Merkle根的有效Merkle证明以及叶子节点的原像，而无需展示我们如何执行的这个计算
只提供一个零知识证明来证明你拥有能够生成Merkle根的Merkle证明是不够安全的，取款人还必须证明他们知道叶子节点的原像。
Merkle树的叶子节点全都是公开的。每当有人存款时，他们需要提供一个公开存储的承诺(commitment)哈希。因此，任何人都能够为任何叶子节点生成一个Merkle证明，然后再生成对应的零知识证明，来证明他们的Merkle证明是有效的。
因此，证明叶子节点存在于树中还不够保险，因为窃贼可以通过伪造证明的方式来实施盗窃。取款人必须在不透露具体是哪个叶子节点的前提下证明他们知道叶子节点的原像。
您可以看到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证明和叶节点哈希)，然后生成一个能够证明该计算被正确执行了的零知识证明，最后将此证明提交给智能合约。
这样，merkleProof和secret{1,2}就被隐藏到证明中了，但是通过这个证明，验证者就可以确认取款人的确执行了计算并且也正确地生成了叶子节点和Merkle根。
让我们总结一下：
存款人:
生成两个秘密数字，对它们的拼接值做哈希运算获得一个承诺哈希
提交承诺哈希
将加密货币发送到Tornado Cash
Tornado Cash:
存款阶段:
将承诺哈希添加到Merkle树中
取款人:
为Merkle根生成一个有效的Merkle证明
根据两个秘密数字生成承诺哈希
生成上述计算过程的零知识证明
将证明提交到Tornado Cash
Tornado Cash
取款阶段:
验证证明是否与Merkle根匹配
将送加密货币发送给取款人
预防多次提款
上面的方案存在着一个问题：如何防止我们多次取款呢？
假设我们从Merkle树中“删除”叶子节点用以记录被取出的存款，但这会暴露哪笔存款是我们的！
Tornado Cash的做法是永远不从Merkle树中删除叶子节点。一旦叶子节点被添加到Merkle树中，它将永远存在。
为了防止多次取款，智能合约使用了一个叫做“nullifier方案”的技术，它在零知识相关的应用和协议中非常常见。
Nullifier方案
零知识中的nullifier就像一个特殊的随机数，它能额外提供一层匿名性。
接下来你就会明白，为什么是由两个秘密数字组成一个叶子节点，而不是一个。
存款时候提交的哈希是由nullifier和secret这两个数字构成的，需要将它们按规定顺序拼接（concat(nullifier, secret)）然后对其做哈希运算，得到的哈希值即为叶子结点。
在取款过程中，用户必须提交nullifier的哈希(即nullifierHash)以及一个证明，用来证明其中一个叶子节点是对nullifier和secret的拼接值做哈希运算得到的。随后，智能合约可以通过零知识算法来验证发送者是否真的知道nullifier哈希的原像。
nullifier哈希会被添加到mapping中，保证它永远不会被重复使用。
这就是为什么我们需要两个秘密数字。如果我们同时揭露两个数字，那么我们就会知道取款人的目标是哪个叶子节点！如果只揭露其中一个数字，那么就无法确定相关的叶子节点是哪一个了。
请记住，零知识证明验证时，无法根据输入的secret来计算nullifier，它只能验证计算过程、输出和证明是一致的。这就是为什么用户必须提交一个公开的nullifierHash和一个由隐藏的nullifier计算而来的证明的原因。
你可以在下面的Tornado Cash withdraw函数的截图中看到这一逻辑。
让我们总结一下。用户必须证明：
他们知道叶子节点的原像
nullifier以前没有被使用过(这是一个简单的Solidity mapping，不是零知识验证步骤)
他们能生成nullifier的哈希以及nullifier的原像
以下是可能出现的结果：
用户提供了错误的nullifier：检查nullifier和nullifier原像的零知识证明将无法通过
用户提供了错误的secret：叶子节点的零知识证明将无法通过
用户提供了错误的nullifier哈希值（以绕过第 86 行的检查）：检查nullifier和nullifier原像的零知识证明将无法通过
增量式Merkle树是gas高效的Merkle树
增量式Merkle树是一种叶子结点初始值为零且深度固定的Merkle树，通过从最左到最右，逐个将零值替换为非零值的方式来添加叶子节点。
下面的动图演示了一个深度为3的增量式Merkle树，它最多可容纳8个叶子节点。为了与Tornado Cash中的术语保持一致，我们将这些标注着c的节点称为"承诺哈希"(commitments)。
你可能已经注意到了，上面只举了一个简单例子。如何在不耗尽gas的情况下更新一个链上的Merkle树？假如有很多笔存款，那么重新计算整棵树就会变得很令人很绝望。
增量式Merkle树通过一些巧妙的优化绕过了这些限制。但在介绍优化措施之前，我们需要先了解一下都有哪些限制。
Merkle树的深度固定为32。这意味着它无法处理超过 2 ^ 32 - 1 笔存款(这是Tornado Cash规定的深度，但必须遵守)。
Merkle树初始状态下，所有叶子节点的值都为hash(bytes32(0))。
存款成功后，最左边且未被使用的叶子节点会被承诺哈希覆盖。存款以“从左到右”的方式添加到叶子节点中。
一旦存款被记录到Merkle树中，就不会被删除掉。
每新增一笔存款，就会存储一个新的根。Tornado Cash称其为"具有历史记录的Merkle树"。所以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)叶子节点的哈希值），由两个零值叶子节点组成的子树的根、由四个零值叶子节点组成的子树的根、由八个零值叶子节点组成的子树的根，等等。
叶子节点数量和树的深度级别(level)之间存在一对一的关系。只有一个叶子节点的树的深度level为0，有两个叶子节点的树的深度level为1，有四个叶子节点的树的深度level为2，有八个叶子节点的树的深度level为3，一般来说，levels = log2(num_leaves)。
这意味着我们可以预先计算出高度为 0、1、2 等Merkle树(所有叶子节点都是零值)的Merkle根，直到 31（记住，Merkle树的高度是固定的）。
对于的Merkle子树(所有叶子节点都是零值)每个可能的高度，Tornado Cash都会对其做预计算。以下是Tornado Cash的Merkle Tree with History中的预先计算列表
/// @dev provides Zero (Empty) elements for a MiMC MerkleTree. Up to 32 levelsfunction 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-level"，因此只需获取预先计算好的Merkle子树(所有叶子节点都是零值)的根即可。
关于“零根”的技术细节
Tornado Cash实际上并没有使用hash(bytes32(0))作为空值，而是使用了hash("tornado")。这并不会影响算法，因为它只是一个常数。然而，使用零值这个概念而不是一个奇怪的常数来讨论增量式Merkle树会更容易让人理解。
巧妙的捷径 #2：最新成员左侧的所有子树都是由Merkle子树组成的，它们的根节点可以被缓存而不需要重新计算
假设我们要添加第二笔存款。此时我们已经计算了第一笔存款的哈希。该哈希已经被缓存到Tornado Cash叫做filledSubtrees的mapping中了。filledSubtree只是Merkle树中所有叶子节点都是非零值的子树。在下面的动图中，我们将其称为fs：
关键在于，每当你需要左侧的中间哈希值时，它已经为你计算好了。
这一非常有用的特性是叶子节点无法被更改或删除这一限制带来的产物。当一棵子树充满了承诺哈希而非零值之后，它也不再需要重新计算了。
现在让我们将这一点加以推广。不要将左侧的节点看作“第一笔存款”，而是想象它本身就是一个子树的根。
在最极端的情况下，想象一下，当我们放入最后一个叶子节点时。在我们左侧的是由倒数第二个叶子节点组成的“树”(深度为0)，再往左是深度为1的子树(有2个叶子节点)，再往左是深度为2的子树(有4个叶子节点)，依此类推。在最极端的情况下，不会有超过32个这样的树。
将这两条捷径相结合
左侧所有的内容都是填充了哈希值的子树(即便它只是一个叶子节点)，而我们右侧的所有内容始终是一个零值叶子节点或者是一颗子树(所有叶子节点都是零值)。由于左侧的根是已经缓存了的，而右侧的根是预先计算好的，因此我们可以高效地计算任意深度级别(level)的任意中间哈希值，并且在链上只需32次迭代就能生成深度为32的Merkle树。这并不便宜，但却是可行的。不过，这肯定比400万次计算要好得多！
对左侧做哈希还是对右侧做哈希?
但是在我们“获得根节点哈希”的过程中，我们如何得知子树哈希的拼接顺序呢？
例如，我们有一个新的承诺哈希，现在想要将其添加为叶子节点。在先入我们的节点中，我们是应该按照 new_commitment | other_value 来拼接还是按照 other_value | new_commitment 来拼接呢？
窍门就在于：每个偶数索引的节点是左子节点，每个奇数索引的节点是右子节点。所有叶子节点以及树的每一层都是如此。你可以在下图中看到这个模式。
让我们对这个模式有个直观的认识。如果正在插入索引值为0的叶子节点，那么在通往根节点的路径上我们只需要对右侧做哈希。0除以2仍为0，而根据上面的定义，零是一个偶数。因为零是偶数，所以我们在通往根节点的路径上始终对右侧做哈希运算。
现在让我们看看另一种极端情况。当插入最后一个叶子节点时，在通往根节点的路径上始终对左侧做哈希运算。通往根节点的每个节点都是奇数节点。
这个模式也适用于树中间的每个节点：以叶子节点的索引值开始，随着我们沿路径向上走，不断地用索引值除以2，得到的新索引值将告诉我们当前是左子节点还是右子节点。下面的动图演示了当我们是奇数节点时对左侧节点做哈希运算，是偶数节点时对右侧节点做哈希运算：
所以无论我们处于哪个level上，我们都可以知道我们的哈希值与兄弟节点的关系。
因此，我们需要的两部分信息为：
被插入的节点的索引值
当前的索引是偶数还是奇数
下边是Tornado Cash源码的截图，代码中使用到了这些信息。for循环遍历各个level，根据新添加的叶子节点重新生成Merkle根。
总结一下，想要更新位于链上的Merkle根，我们需要：
在新索引的位置添加叶子节点，将新的索引值设置为currentIndex。
移动到上一层level，将currentIndex / 2赋值给currentIndex。然后：
如果currentIndex是奇数，则filledSubtree作为左节点参与哈希运算。
如果currentIndex是偶数，则预先计算好的“零树(所有叶子节点都是零值)”作为右节点参与哈希运算。
如此重要的算法能被压缩成一小段Solidity代码也是太牛逼了。
因为每次存款根节点都会变化，所以Tornado Cash只会存储最近30个根节点
无论什么时候插入一个节点，Merkle根必定会改变。
现在面临的一个问题是：如果取款人为最新的根创建了一个Merkle证明(请记住，所有叶子节点都是公开的)，但是另外一个存款交易提前到来并改变了根，那么Merkle证明将不再有效。零知识证明验证算法是保证Merkle证明的零知识证明特定于某个根节点有效，所以如果根节点发生变化，那么零知识证明将无法通过校验。
为了让取款人有时间完成取款交易，他们可以参考最近的30个根。
roots变量是一个由uint256映射到bytes32的mapping。Merkle证明会被存储到roots中(循环完成后)。currentRootIndex会递增到ROOT_HISTORY_SIZE，但一旦达到最大值(30)，它就会覆盖索引值0所对应的根节点。因此，它表现得像一个固定长度的队列。以下是Tornado Cash的Merkle树 _insert函数的代码片段。在根节点被重新生成之后，它就会以我们描述的方式存储。
增量式Merkle树所使用的storage变量
以下是MerkleTreeWithHistory合约运行时所需要的storage变量。
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树的工作原理
当一个用户使用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() 只是确保面额正确(您只能存入0.1，1或10个ETH，这具体取决于您交互的Tornado Cash实例)。以下是这个非常简单操作的代码。
function _processDeposit() internal override {
require(msg.value == denomination, "Please send `mixDenomination` ETH along with transaction");
}
高度优化的MiMC哈希算法
想要在链上计算Merkle根，必须使用哈希算法(显而易见)，但Tornado Cash并不使用传统的keccak256，而是使用 MiMC。
讨论具体为什么会有这样的区别就有点超出本文的范畴了，但原因是：就零知识证明的生成而言，某些哈希算法比其他哈希算法的计算成本更低。MiMC被设计成“zk友好(零知识友好)”的，而keccak256则不是。
“zk友好”是指该算法能够更自然地映射零知识证明算法所代表的计算。
因此，Tornado Cash团队自己用原始字节码编写了一个。
如果你查看Etherscan上的合约验证，你会看到一个警告。
Etherscan无法验证Solidity的原始字节码，而MIMC哈希算法不是用Solidity编写的。
注：Tornado Cash团队将MiMC哈希算法作为一个独立的智能合约部署到了链上。
为了使用MiMC哈希算法，Merkle树的代码通过跨合约调用的方式与该合约进行交互。你可以在下边的代码中看到，这些都是静态调用，因为接口将其定义为pure，所以Etherscan上显示它没有交易历史。
interface IHasher {
function MiMCSponge(uint256 in_xL, uint256 in_xR) external pure returns (uint256 xL, uint256 xR);
}
我们从Tornado Cash的代码知道了MIMC哈希算法的“接口”(github 链接)。
在Circom库的issue中，你可以查看代码没有Solidity的版本信息，甚至没有汇编块的理由：直接操作堆栈是不可能的。
(旁注：非常底层的加密算法是Huff语言绝佳的应用场景，您可以通过我们的Huff Language Puzzles来学习）。
部署你自己的原始字节码哈希函数
circomlib JS库包含一系列用于创建原始字节码哈希函数的JavaScript工具。这里是用来生成MiMC和Poseidon Hash的代码的链接。
从Tornado Cash中取款
首先，用户必须使用updateTree脚本在本地重新构建Merkle树。该脚本将下载所有相关的Solidity事件，并重新构建Merkle树。
然后，用户会生成Merkle证明的零知识证明和叶子节点(承诺哈希)的原像。
正如前面讨论的，Tornado Cash会存储最近的30个Merkle根，因此用户有足够的时间来提交证明。如果用户生成证明后等待的时间过长，就必须重新生成证明。
Tornado Cash合约将会做如下检查
提交的nullifierHash之前未被使用过
根节点是否在最近的30个历史记录中
零知识证明会核查：
a) 隐藏哈希的原像生成了叶子节点
b) 用户是否真的知道nullifierHash的原像
c) 用户使用该叶子节点创建了Merkle证明，并生成了所提议的根节点。
d) 提议的根节点是最近30个根节点之一（这在Solidity代码中进行了公开检查）
以下是上述步骤的可视化示意图：
理解了这一点，下面Tornado Cash的withdraw函数中的代码就很好理解了。
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与向可选的交易中继器支付费用有关，我们稍后将对此进行解释。
isKnownRoot(root) 函数会验证提议的根节点是最近30个根节点之一
这是一个简单的do-while循环，从当前索引(最新激活的叶子节点)向前循环，以检查在withdraw函数中提交的根节点是否存在于根节点的历史记录中。 (github 链接)
因为我们只回看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代码
本节介绍Circom代码，它们用于生成能够验证零知识证明的电路。如果您不熟悉Circom并想学习它，请查阅我们用Circom编写的zero knowledge puzzles。
不过，我们仍然会尝试在一个较高的层面来解释Circom代码。
Circom并不会在区块链上执行，而是会被转译成可怕的难以阅读的Solidity代码，你可以在Tornado Cash的Verifier.sol合约中看到。它之所以看起来如此吓人，是因为它实际上会执行零知识证明验证过程的数学运算。值得庆幸的是，Circom代码的可读性更高一些。
这里，我们有三个组件：用于组合哈希的HashLeftRight，DualMux（只是MerkleTreeChecker的工具）和 MerkleTreeChecker。MerkleTreeChecker的参数是一个叶子节点、一个根节点和一个证明。证明分两部分：路径元素（姐妹子树的Merkle根）和 路径标识（用于告知电路在各个level下哈希的拼接顺序的指示器）。
最后一行(root === hashers[levels - 1].hash)是最终确定根节点与叶子结点以及证明相匹配的地方。
回想一下，nullifierHash 是 nullifier 的哈希值，commitment是nullifier和secret的哈希值。这个计算对应的Circom代码实现如下所示。尽管它可能有点难以阅读，但可以清楚地看出 nullifier和secret是输入，commitment和nullifierHash是输出。
现在我们可以开始分析零知识算法的核心部分了。
根据前面提到的术语，private signal 意味着变量会"被隐藏到证明中"。
在上面的代码中，代码会验证用户使用了一个有效的计算过程来生成nullifier哈希。然后将承诺哈希的原像和Merkle证明作为参数传入前面提到的MerkleTree验证器(MerkleTreeChecker)中。
如果一切都验证通过，验证器将返回true，表示证明有效，匿名地址就可以取出存款了。
预防取款时发生的抢跑(frontrunning)攻击
研究过智能合约审计的工程师们可能已经注意到，Solidity代码没有任何能够防御抢跑攻击的措施。当有人向mempool提交有效的零知识证明时，如何防止有人复制证明并将取款地址替换为他们自己的地址呢？
为了简单起见，我们先忽略其他文件，withdraw.circom文件中将recipient（以及其他中继器所需要的参数）的平方作为虚拟signal。这意味着，零知识证明还必须证明取款人对收款人的地址做了平方运算，并得到了他们地址的平方值（请记住，地址只是20个字节的数字）。计算地址的平方值以及nullifier和secret的哈希值都需要做一次计算，因此，计算中的任何部分出错都会导致整个证明无效。
中继器(relayer)和手续费(fee)是什么?
中继器是一个链下机器人，它能够为用户支付gas费用以换取某种报酬。Tornado Cash的取款人通常情况下会希望使用一个全新的地址来保证隐私性，但全新的地址没有任何能用来支付取款手续费的gas。
为了解决这个问题，取款人可以请求中继器代为执行交易，作为回报，中继器将获得Tornado Cash取款的一部分。
中继器的取款地址也必须使用前面提到的相同的防抢跑攻击保护措施，这可以在上面的代码截图中看到。
对 deposit() 和 withdrawal() 的总结
当deposit()被调用时：
用户在存入加密货币的同时提交 hash(concat(nullifier, secret))
Tornado Cash会验证存入的金额是其能接受的面额
Tornado Cash将承诺哈希加入到下一个叶子节点中。所有的叶子节点都不会被移除。
当withdrawal()被调用时：
用户根据Tornado Cash已触发的事件重新构建Merkle树
用户必须提供nullifer的哈希值(公开的)，验证时需要的对应的Merkle根，以及证明他们知道 nullifier、secret和Merkle证明的零知识证明
Tornado Cash验证nullifer之前未被使用过
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优化的机会。
Tornado Cash使用线性算法来查找预先计算好的Merkle子树(所有叶子节点都是零值)，但这里可以通过硬编码的二分算法来减少操作次数。
Tornado Cash经常使用uint32类型作为堆栈变量，但uint256类型是更好的选择，可以避免EVM的隐式转换。
Tornado Cash有一些常量被不必要地设为public。除非有其他合约读取它们的值，否则没必要将其设置为public，它们会增加智能合约的体积。
前缀运算符(i)比后缀运算符(i)更节省gas，Tornado Cash可以在不影响逻辑的前提更改这个操作符。
nullifierHashes 已经是public可见性的mapping了， 但还将它封装到一个可见性为public的isSpent()函数中。这完全是多余的。
总结
就这样，我们对Tornado Cash的所有代码都做了分析，并对每个变量和函数的功能也有了很深的了解。
Tornado Cash在相对较小的代码中包含了很多令人印象深刻且复杂的功能。我们讨论过的重点技术包括：
在不给出原像的前提下，使用零知识证明来证明我们知道哈希的原像
如何在链上使用增量式Merkle树
如何使用由原始字节码编写的自定义哈希函数
nullifier方案的工作原理
如何匿名取款
如何防止零知识证明dapp遭受抢跑攻击
RareSkills
这些内容是我们的零知识课程的一部分。关于普通的智能合约开发，请参阅我们为专业Solidity开发人员提供的Solidity 培训。我们提供了目前全球范围内最为严谨和最前沿的智能合约培训计划。
澄清说明
[1] 任何熟悉零知识电路的人都知道我们不能创建任意长度的 for 循环。电路在创建时必须为非常大的数组做好准备。然而，依旧可以确定地说，对如此多的哈希做“循环计算”的成本是非常昂贵的，因为这等同于创建了一个庞大到无法想象的电路。
翻译
本文由Yifeng Cao翻译。这是英文原版How Tornado Cash Works (Line by Line for Devs)文章链接。