针对以太坊实现的一种Sparse Merkle Tree

Merkle Tree（默克尔树）是一种二叉树，其最底层叶子节点存储数据以及数据的哈希，而每上一层节点则存储两个子节点的哈希，最后由根节点的哈希保证这个Merkle Tree的任何节点数据的完整性。因为修改任何一个叶子节点的数据都会导致根节点的哈希变化，因此，比特币使用Merkle Tree保证一个区块内的所有交易均不可修改：

              ┌─┐
              └─┘
       ┌───────┴───────┐
      ┌─┐             ┌─┐
      └─┘             └─┘
   ┌───┴───┐       ┌───┴───┐
  ┌─┐     ┌─┐     ┌─┐     ┌─┐
  └─┘     └─┘     └─┘     └─┘
 ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

以太坊则使用一种Merkle Tree的变体MPT（Merkle Patricia Tree）存储所有地址的数据。这种MPT的优势是可以存储任意前缀的Key-Value，而不仅限于固定长度的地址作为Key。它的缺点是数据结构比较复杂。

把Merkle Tree应用到以太坊作为账户体系是否可行？实际上是完全可行的。以太坊地址长度是20字节，把地址看作一个整数，则所有以太坊地址的范围是0 ~ 2¹⁶⁰-1，我们构造一棵高度为160、子节点数量为2¹⁶⁰的完全二叉树，就可以表示整个以太坊所有账户的状态。

我们来计算一下2¹⁶⁰的大小：

2¹⁶⁰ ≈ 1.46亿亿亿亿亿亿

虽然2¹⁶⁰是个天文数字，全世界所有计算机加起来也不可能存储这么大的数据，但是，真正使用的以太坊账户只有千万级别，相对于2¹⁶⁰来说少得可怜。如果我们只存储实际账户，剩下的未使用地址根本不存储，相当于这棵完全二叉树其中99.999...%的节点都是虚拟节点，无需存储。我们把这种二叉树称为Sparse Merkle Tree（稀疏默克尔树）。

对于一棵空SMT来说，虽然它的叶子节点有2¹⁶⁰个，但我们计算每一层节点的哈希，并不需要计算2¹⁶⁰次，因为子节点初始数据都一样（看作空字符串""），所以哈希一样，上层的2¹⁵⁹个父节点哈希也是一样的，因此，计算160次，即可获得根节点哈希，这个根哈希就是初始状态的唯一标识：

              ┌─┐
              └─┘
       ┌───────┴───────┐
      ┌─┐              .
      └─┘              .
   ┌───┴───┐           .
   .
   .
   .
 ┌─┴─┐   ┌─┴─┐           ┌─┴─┐
┌─┐ ┌─┐ ┌─┐ ┌─┐         ┌─┐ ┌─┐
└─┘ └─┘ └─┘ └─┘         └─┘ └─┘
 0   1   2   3  ... 2^160-2 2^160-1

当某个叶子节点的数据更新时，我们只需要按路径更新上层节点的哈希，最后更新到根节点哈希，就完成了状态的转移，一共需要计算160次哈希。

上述结构从理论上就可以表示以太坊所有账户的信息，以及由根节点表示的世界状态的转移。

下一步我们来实现具体的数据结构。

由于节点分两种：最底层的叶子节点和中间层节点。叶子节点比较简单，我们重点关注中间层节点。由树形结构可知，中间层节点有两个子节点，可表示为：

Node {
    String hash;
    Node left;
    Node right;
}

然而这种表示方法会导致创建大量的中间层节点，而且遍历到子节点需要160次，效率很低。我们可以用一种压缩的方式表示中间层节点：

Node {
    String hash;
    Node[16] children;
}

这种方式实际上可表示一棵16个子节点的子树，中间层的节点哈希仅计算，不存储，仅存储子树根节点哈希：

                      ┌─┐
                      └─┘
           ┌───────────┴───────────┐
          ┌─┐                     ┌─┐
          └─┘                     └─┘
      ┌────┴─────┐            ┌────┴─────┐
     ┌─┐        ┌─┐          ┌─┐        ┌─┐
     └─┘        └─┘          └─┘        └─┘
   ┌──┴─┐      ┌─┴──┐      ┌──┴─┐      ┌─┴──┐
  ┌─┐  ┌─┐    ┌─┐  ┌─┐    ┌─┐  ┌─┐    ┌─┐  ┌─┐
  └─┘  └─┘    └─┘  └─┘    └─┘  └─┘    └─┘  └─┘
 ┌─┴┐  ┌┴─┐  ┌─┴┐  ┌┴─┐  ┌─┴┐  ┌┴─┐  ┌─┴┐  ┌┴─┐
┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐┌─┐
└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘└─┘

这样就可以把树的高度从160层压缩到40层。

40层的高度对于从根开始遍历还是太长了，我们可以参考MPT，把相同前缀的节点合并，一个节点可以直接跨越几个层级挂在上层节点上，这样可以大大缩短节点路径。

例如，对于空树，我们插入第一个叶子节点0x215A1C45...，它应该直接挂在根节点表示的子树索引为2的位置上：

┌───────────────────────────────┐
│Root                           │
├─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┤
└─┴─┴┬┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
     │
     │
     ▼
    ┌──────────────────┐
    │Path=0x215A1C45...│
    ├──────────────────┤
    │Data=123          │
    └──────────────────┘

如果插入第二个叶子节点0x215AB162...，因为有共同的前缀215A，所以需要创建一个中间节点215A，再把两个叶子节点分别挂在索引为1和11的位置：

┌───────────────────────────────┐
│Root                           │
├─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┤
└─┴─┴┬┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
     │
     │
     ▼
    ┌───────────────────────────────┐
    │Path=215A                      │
    ├─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┤
    └─┴┬┴─┴─┴─┴─┴─┴─┴─┴─┴─┴┬┴─┴─┴─┴─┘
       │                   │
       │                   │
       ▼                   ▼
    ┌──────────────────┐  ┌──────────────────┐
    │Path=0x215A1C45...│  │Path=0x215AB162...│
    ├──────────────────┤  ├──────────────────┤
    │Data=123          │  │Data=456          │
    └──────────────────┘  └──────────────────┘

这样对于叶子节点来说，只需要很少几次查找就能定位。

完整的SMT实现参考源码可以从GitHub下载。

中心化交易所如何用Merkle Tree实现资产储备证明

从零开始设计并实现HDMI显卡

Comments

Loading comments...