零时科技 || Tornado Cash中merkleTree和zk-snarks

背景

Tornado cash是一个去中心化加密货币混合服务平台，使用智能合约来接受来自一个地址的代币存款，并允许他们从另一个地址提款。这些智能合约作为混合所有已存资产的池。一旦资金通过一个全新的地址从这些池中提取，链上源和目的地之间的链接已断开。然后将提取的加密资产匿名化。tornado cash中通过将merkle tree 与 zk-snarks结合使用实现存取款地址分离，从而实现匿名传送代币。

Merkle Tree

区块链中网络上产生所有的交易都要打包进区块，通常情况下，每个区块中包含成百上千个交易。而且由于区块链去中心化的特征，网络中每个节点都必须是独立的，因此每个节点都必须存储一个区块链的完整副本，当交易量逐渐增多时，区块中数据也越来越庞大，占据的空间也越来越多而且处理效率逐渐变低。因此提出了一个轻节点概念，轻节点只需要储存历史区块头而不需要保存整个区块链，通过merkle树证明判断交易是否在交易列表中。

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。默克尔树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。

如图，对要存储的数据生成hash值，这些hash值就是默克尔树的根节点，之后将相邻叶子节点的hash字符串连接起来再次进行hash运算，生成中间节点，继续向上运算，最终生成了一个根节点，这个根就是默克尔根。当任意节点的值改变时，merkle根的值随着改变。

对于merkle树来说，并不需要知道整棵merkle树中节点的值，如下图，当我想要证明Hk在集合中时，我只需要将Hl，Hij，Hmnop和Habcdefgh的值发送给证明函数，如果计算出的merkle根与存储的根相同则证明Hk在集合中。

Tornado cash 中 merkle tree使用

tronado cash中对于merkle tree的使用主要在存取款操作中，进行存款操作时会创建两个随机数，将这两个随机数通过Pedersen哈希处理后生成一个字符串commitment，将此字符串作为叶子节点插入默克尔树中，计算出merkle根的值后将merkle根返回给用户，作为之后取款时的验证凭证。

tornado cash中的merkle tree是一颗二叉树，阅读其代码可知，re-hashing操作的次数控制在log(n)以内，当原始树中叶子节点个数是奇数时插入后的树没有孤儿，原始树中叶子节点个数时偶数时插入后的树有孤儿，孤儿在第一个数据块。

如图所示，原始树中有两个叶子节点a，b，当插入新节点c时，判断叶子节点个数，为偶数，c与0值进行hash计算得到Hc，叶子节点个数除2，得到叶子节点的父节点个数1，判断节点个数为奇数，将Hc 与Hab 连接并计算hash值Habc ，此时Habc 为这颗merkle树的根，用户将这个根保存作为之后取款的凭证。

zk-snarks

zk-snarks全称为简洁的非交互式知识认证，也称零知识证明。它可以让你在不执行，甚至不知道执行的具体内容是什么的情况下就能够验证某个计算的结果是否正确。

举个例子，想象一下，你是盲人，我给你两个球，感觉完全一样，重量也一样。现在我告诉你这两个球的颜色不同。附近没有其他人。你怎么能知道我说的是不是真的呢？

你可以在每只手上放一个球，把它们展示给我看。现在你把它们放在你的背后，你要么在两只手之间交换球，要么不交换。然后你把它们拿给我看，并问我：'我是否交换了球？现在，如果两个球都是同样的颜色，将有50%的机会猜对。但如果连续答对了15次，你几乎可以肯定（99.997%的把握）说这两个球确实是不同颜色的。因为随机猜对15次，几乎不可能。

我现在已经向你证明了这些球是不同颜色的，但却没有透露实际的颜色，因此被称为 零知识 证明。你不知道这些球是绿色、黑色、橙色还是别的什么。

在区块链中zk-snarks是指可以为生成特定输出的计算提供相应的proof证明，使得验证proof的速度远远高于执行相应计算的速度，对于SNARK使用的变换，在语句被表述为函数之后，遵循下图的一般模式，即原始计算，代数电路，秩为1的约束系统，二次算数程序，线性PCP，线互式证明，最后生成零知识证明。

要生成 zk-snarks，您需要一个电路。电路类似于具有公共输入和输出以及私有输入的小程序。这些私人输入是您不为验证而透露的知识，这就是为什么它被称为零知识证明。使用 zk-snarks，我们可以证明输出可以从给定电路的输入中产生。

tornado cash 中 zk-snarks使用

tornado cash中取款操作需要用户提供一个note，如下图

这个note是由secret与nullifier通过zk-snarks电路在链下计算生成的，secret与nullifer是在链下随机生成的31字节长度的随机数。

tornado中，存款操作传入的参数commitment是由secert与nullifer串联产生一个62字节的数，通过Pedersen 哈希处理，生成的输出表示 Baby Jubjub 椭圆曲线的一个元素，编码为 32 字节大端整数。之后将commitment插入merkle树中得到merkle root。

在tornado cash中，取款操作时需要输入三个值，分别是proof，root，nulifierHash，proof为存款时在链下计算出的note值，root为存款时获得的merkle root，nulifierHash为生成的随机数。

nulifierHash作用是为了防止已经使用过的note再次使用，在进行证明proof之前，先确定传入的root值是否在merkle树中，之后验证proof是否正确，通过电路计算出一个root，将计算出的root与取款时输入的root比较是否一样，一样的话，将nullifierHash记录为true，证明我们已经领过款。

通过以上几步，我们就完成了一个零知识证明的过程，

总结

tornado cash中将merkle tree运用到零知识证明中，零知识证明中proof实际捆绑了凭证note，用户自己的merkle root，nullifierHash，资金接收者地址。取款合约中确保nullilierHash是未使用过的，以及用户提供的Root确实是自己知道的代表完整记录的Root。然后，合约将自己验证过的输入nullifierHash 和 root，以及用户方输入的proof recipient fee等输入Verifier合约。用零知识证明proof提供的路径确实能联通用户提供的nullifier和secret生成的commitment和提供的root，用户是这个commitment的拥有者。