Merkle Mountain Ranges和Merkle Tr

Merkle Tree

由Ralph Merkle在1970年代提出，它是绝对对称的二叉树结构。每个叶子(leaf)是对应数据的hash，其它的节点则是它的2个子节点合并后的hash值。^[1]

image

当遇到叶子数量不是2^n的时候，无法形成完全对称的二叉树结构，即存在节点无法凑对的情况，这时候就和自己凑对。^[2]

       ABCDEEEE .......Merkle root
      /        \
   ABCD        EEEE
  /    \      /
 AB    CD    EE .......E is paired with itself
/  \  /  \  /
A  B  C  D  E .........Transactions

当添加一个新叶子的时候，这个叶子从下到上的整个路径都要重新计算hash。如果总叶子数是n，那么就需要进行roof(Log2(n))次计算。

Merkle Mountain Ranges(MMR)

最初由Peter Todd在2016年提出^[3]，和Merkle Tree一样，叶子是一块数据的hash，其它节点是子节点拼起来之后的hash。不同的是对非对称二叉树结构的处理方式。它会在当前叶子数量的条件下，尽量构建对称的二叉树。

比如如果叶子数位14，那么：

• 前8个叶子可以构建一个深度为3的对称二叉树
• 剩余6个叶子，其中4个叶子可以构建一个深度为2的对称二叉树
• 剩余2个叶子，可以构建一个深度为1的对称二叉树

   /\
  /  \
 /\  /\  /\
/\/\/\/\/\/\/\

形状上就像是3座小山，这也是MMR名字的由来。MMR root的计算方法是，将第一个小山的root hash和第二个小山的root hash拼接，计算得到hash。然后在此基础上，再和第3个小山进行拼接，计算得到hash。^[4]如果还有更多，就依次循环。

          /\
         /\ \
        /  \ \
       /\   \ \
      /  \   \ \
     /\  /\  /\ \
    /\/\/\/\/\/\/\

将叶子数用二进制表示，即1110。此时添加一个新叶子，只需要进行1次hash。

• 如果叶子数是1101101，添加新叶子需要进行2次hash。
• 如果叶子数是1100111，添加新叶子需要进行4次hash。
• 如果叶子数是1011111，添加新叶子需要进行6次hash。

计算规律是，最右侧连续的小山数量+1。
如果用Merkle Tree，上述3种情况需要做的hash次数都是7次，即Log2(n)并向上取整。

对于MMR而言，最坏情况是所有的小山都是连续的，即叶子数为1111111的情况，添加新叶子需要进行7次hash，和使用Merkle Tree一样。

MMR被用于Grin^[5]，同时也是Flyclient的基础。

MMR可以通过递归实现^[6]

---

1. https://en.wikipedia.org/wiki/Merkle_tree ↩

2. https://bitcoin.org/en/developer-guide#transaction-data ↩

3. https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md ↩

4. https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py ↩

5. https://github.com/mimblewimble/grin/blob/master/doc/mmr.md ↩

6. FlyClient: Super-Light Clients for Cryptocurrencies https://eprint.iacr.org/2019/226.pdf ↩