这篇文章会说明Merkle Tree 的运作原理，以及解释Merkle Proofs 的用意，并以JavaScript / TypeScript 简单实作出来。

本文中实作的Merkle Tree是以TypeScript重写的版本，原始版本为tornado-core以JavaScript实作而成，基本上大同小异。

Merkle Tree 的原理

在理解Merkle Tree 之前，最基本的先备知识是hash function，利用hash 我们可以对资料进行哈希，而哈希后的值是不可逆的，假设我们要对x 值做哈希，就以H(x) 来表示。

而所谓的Merkle Tree 就是利用特定的hash function，将一大批资料两两进行杂凑，最后产生一个最顶层的杂凑值root。

当有一笔资料假设是const leaves = [A, B, C, D]，我们就用function Hash(left, right)，开始制作这颗树，产生H(H(A) + H(B))与H(H(C) + H(D))，再将这两个值再做一次Hash变成H(H(H(A) + H(B)) + H(H(C) + H(D)))，就会得到这批资料的唯一值，也就是root。

本文中使用的命名如下：

root：Merkle Tree 最顶端的值，特色是只要底下的资料一有变动，root 值就会改变。 leaf：指单一个资料，如H(A)。 levels：指树的高度(height)，以上述4 个资料的假设，制作出来的levels 是2，levels 通常会作为递回的次数。 leaves：指Merkle Tree上的所有资料，如上述例子中的H(A), H(B), H(C), H(D)。leaves的数量会决定树的levels，公式是leaves.length == 2**levels，这段建议先想清楚！ node：指的是非leaves也非root的节点，或称作branch，如上述例子中的H(H(A) + H(B))和H(H(C) + H(D))。 index：指某个leaf所在的位置，leaf = leaves[index]，index如果是偶数，leaf一定在左边，如果是奇数leaf一定在右边。

Merkle Proofs

Merkle Proofs的重点就是要证明资料有没有在树上。

如何证明就是提供要证明的leaf 以及其相对应的路径(path) ，经过计算后一旦能够产生所需要的root，就能证明这个leaf 在这颗树上。

因此这类要判断资料有无在树上的证明，类似的说法有：proving inclusion, proving existence, or proving membership。

这个proof 的特点在于，我们只提供leaf 和path 就可以算出root，而不需要提供所有的资料(leaves) 去重新计算整颗Merkle Tree。这让我们在验证资料有没有在树上时，不需要花费大量的计算时间，更棒的是，这让我们只需要储存root 就好，而不需要储存所有的资料。

在区块链上，储存资料的成本通常很高，也因此Merkle Tree 的设计往往成为扩容上的重点。

我们知道n 层的Merkle Tree 可以存放2**n 个叶子，以Tornado Cash 的设计来说，他们设定Merkle Tree 有20 层，也就是一颗树上会有2**20 = 1048576 个叶子，而我们用一个root 就代表了这1048576 笔资料。

接续上段的例子，这颗20 层的Merkle Tree 所产生的Proof ，其路径(path) 要从最底下的叶子hash 几次才能到达顶端的root 呢答案就是跟一棵树的levels 一样，我们要验证Proof 所要递回的次数就会是20 次。

在实作之前，我们先来看MerkleTree 在client 端是怎么调用的，这有助于我们理解Merkle Proofs 在做什么。

基本上一个proof 的场景会有两个人：prover 与verifier。

在给定一笔leaves的树，必定产生一特定root。prover标示他的leaf在树上的index等于2，也就是leaves[2] == 30，以此来产生一个proof，这个proof的内容大致上会是这个样子：

对verifier来说，他要验证这个proof，就是用里面的leaf去一个一个与pathElements的值做hash，上述就是H('30', 40)后得出node，再hash一次H('19786...', node)于是就能得出这棵树的root。

重点来了，这么做有什么意义它的巧思在于对verifier 来说，他只需要储存一个root，由prover 提交证明给他，经过计算后产生的root 如果跟verifier 储存的root 一样，那就证明了prover 所提供的资料确实存在于这个树上。

而verifier若不透过proof ，要验证某个leaf是否存在于树上，也可以把leaves = [10, 20 ,leaf ,40]整笔资料拿去做MerkleTree的演算法跑一趟也能产生特定的root。

但由prover 先行计算后所提交的proof，让verifier 不必储存整批资料，也省去了大量的计算时间，即可做出某资料有无在Merkle Tree 上的判断。

Sparse Merkle Tree

上述能够证明资料有无在树上的Merkle Proofs 是属于标准的Merkle Tree 的功能。但接下来我们要实作的是稍微不一样的树，叫做Sparse Merkle Tree。

Sparse Merkle Tree的特色在于除了proving inclusion之外，还可以proving non-inclusion。也就是能够证明某笔资料不在某个index，例如H(A)不在index 2 ，这是一般Merkle Tree没办法做到的。

而要做到non-membership的功能其实也不难，就是我们要在没有资料的叶子里补上zero value，或是说null值。

实作细节

本节将完整的程式码分成三个片段来解释。

首先，这里使用的Hash Function 是MiMC，主要是为了之后在ZKP 专案上的效率考量，你可以替换成其他较常见的hash function 例如node.js 内建crypto 的sha256：

crypto.createHash("sha256").update(data.toString()).digest("hex");

这里定义简单的Merkle Tree 介面有root, proof, and insert。

首先我们必须先给定这颗树的levels，也就是树的高度先决定好，树所能容纳的资料量也因此固定为2**levels 笔资料，至于要不要有defaultLeaves 则看创建Merkle Tree 的client 自行决定，如果有defaultLeaves 的话，constructor 就会跑下方一大段计算，对default 资料开始作hash 去建立Merkle Tree。

如果没有defaultLeaves，我们的树也不会是空白的，因为这是颗Sparse Merkle Tree，这里使用zeroValue 作为没有填上资料的值，zeros 阵列会储存不同level 所应该使用的zero value。假设我们已经填上第0 笔与第1 笔资料，要填上第2 笔资料时，第2 笔资料就要跟zeros[0] 做hash，第2 笔放左边， zero value 放右边。

我们将所有的点不论是leaf, node, root 都用标签(index) 标示，并以key-value 的形式储存在storage 里面。例如第0 笔资料会是0–0，第1 笔会是0–1，这两个hash 后的节点(node) 会是1–0。假设levels 是2，1–0 节点就要跟1–1 节点做hash，即可产出root (2–0)。

后半部份的重点在于proof，先把proof 和traverse 看懂，基本上就算是打通任督二脉了，之后有兴趣再看insert 和update。

sibling 是指要和current 一起hashLeftRight 的值…也就是相邻在两旁的leaf (or node)。

到这里程式码的部分就结束了。

最后，让我们回到一开始client 调用merkleTree 的例子：

以及proof 的内容：

前面略过了proof 里头的pathIndices，pathIndices 告诉你的是当前的leaf (or node) 是要放在左边，还是放在右边，大概是这个样子：

if (indices == 0) hash(A, B); if (indices == 1) hash(B, A);

有兴趣的读者可以实作verify function 看看就会知道了！