MPT

概述

Merkle Patricia Tree（又称为 Merkle Patricia Trie）是一种经过改良的、融合了 Merkle tree 和前缀树两种树结构优点的数据结构，是以太坊中用来组织管理账户数据、生成交易集合哈希的重要数据结构。

MPT 树有以下几个作用：

• 存储任意长度的 key-value 键值对数据，符合以太坊的 state 模型；
• 提供了一种快速计算所维护数据集哈希标识的机制；
• 提供了快速状态回滚的机制；
• 提供了一种称为默克尔证明的证明方法，进行轻节点的扩展，实现简单支付验证；

由于 MPT 结合了 Radix trie 和 Merkle 两种树结构的特点与优势 ，因此在介绍 MPT 之前，我们首先简要地介绍下这两种树结构的特点。

Radix trie

Trie 树，又称前缀树或字典树，是一种有序树，用于保存关联数组。其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定 。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。实际上 trie 每个节点是一个确定长度的数组，数组中每个元素的值是一个指向子节点的指针，最后有个标志域，标识这个位置为止是否是一个完整的字符串。
常见的用来存英文单词的 trie 每个节点是一个长度为 27 的指针数组，index0-25 代表 a-z 字符，26 为标志域。如图：

优势

相比于哈希表，使用前缀树来进行查询拥有共同前缀 key 的数据时十分高效，例如在字典中查找前缀为 pre 的单词，对于哈希表来说，需要遍历整个表，时间效率为 O(n)，然而对于前缀树来说，只需要在树中找到前缀为 pre 的节点，且遍历以这个节点为根节点的子树即可。
但是对于最差的情况（前缀为空串)，时间效率为 O(n), 仍然需要遍历整棵树，此时效率与哈希表相同。
相比于哈希表，在前缀树不会存在哈希冲突的问题。
更新数据非常容易，只需访问局部分支。

劣势

直接查找效率低下。前缀树的查找效率是 O(m)，m 为所查找节点的 key 长度，而哈希表的查找效率为 O(1)。且一次查找会有 m 次 IO 开销，相比于直接查找，无论是速率、还是对磁盘的压力都比较大。可能会造成空间浪费 当存在一个节点，其 key 值内容很长（如一串很长的字符串），当树中没有与他相同前缀的分支时，为了存储该节点，需要创建许多非叶子节点来构建根节点到该节点间的路径，造成了存储空间的浪费。

Patricia trie

他是一种更节省空间的 Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。

Patricia tree适合键值分布比较稀疏的数据，压缩效果比较明显。在以太坊中，为防止碰撞，使用了160bit长的账户，非常稀疏，因此适合使用Patricia tree数据结构。

Merkle tree

Merkle 树是由计算机科学家 Ralph Merkle 在很多年前提出的，并以他本人的名字来命名, 由于在 Bitcoin 网络中用到了这种数据结构来进行数据正确性的验证，在这里简要地介绍一下 merkle 树的特点及原理。
在 Bitcoin 网络中，merkle 树被用来归纳一个区块中的所有交易，同时生成整个交易集合的数字指纹。此外，由于 merkle 树的存在，使得在 Bitcoin 这种公链的场景下，扩展一种 “轻节点” 实现简单支付验证变成可能。

特点

• Merkle tree 是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；
• Merkle tree 叶子节点的 value 是数据项的内容，或者是数据项的哈希值；
• 非叶子节点的 value 根据其孩子节点的信息，然后按照 Hash 算法计算而得出的；

将相邻两个节点的哈希值合并成一个字符串，然后计算这个字符串的哈希，得到的就是这两个节点的父节点的哈希值。
如果该层的树节点个数是单数，那么对于最后剩下的树节点，这种情况就直接对它进行哈希运算，其父节点的哈希就是其哈希值的哈希值（对于单数个叶子节点，有着不同的处理方法，也可以采用复制最后一个叶子节点凑齐偶数个叶子节点的方式）。循环重复上述计算过程，最后计算得到最后一个节点的哈希值，将该节点的哈希值作为整棵树的哈希。
若两棵树的根哈希一致，则这两棵树的结构、节点的内容必然相同。

优势

• 快速重哈希
  Merkle tree 的特点之一就是当树节点内容发生变化时，能够在前一次哈希计算的基础上，仅仅将被修改的树节点进行哈希重计算，便能得到一个新的根哈希用来代表整棵树的状态。
• 轻节点扩展
  采用 Merkle tree，可以在公链环境下扩展一种 “轻节点”。轻节点的特点是对于每个区块，仅仅需要存储约 80 个字节大小的区块头数据，而不存储交易列表，回执列表等数据。然而通过轻节点，可以实现在非信任的公链环境中验证某一笔交易是否被收录在区块链账本的功能。这使得像比特币，以太坊这样的区块链能够运行在个人 PC，智能手机等拥有小存储容量的终端上。
  对于轻节点来说，验证一条交易只需要验证包含该交易的路径即可，并不需要把所有交易的 Hash 全部重新算一遍。
  

  劣势

  存储空间开销大

  MPT

  概念

  在深入 MPT 数据结构之前，我们先了解一下如下概念：
• 世界状态：在以太坊中，所有账户（包括合约账户、普通账户）的状态数据统称为世界状态；
• 轻节点：指只存储区块头数据的区块链节点；
• 区块链分叉：指向同一个父块的 2 个区块被同时生成的情况，某些部分的矿工看到其中一个区块，其他的矿工则看到另外一个区块。这导致 2 种区块链同时增长；
• 区块头：指以太坊区块结构体的一部分，用于存储该区块的头部信息，如父区块哈希、世界状态哈希、交易回执集合哈希等。区块头仅存储一些 “固定” 长度的哈希字段；

  MPT 树中的节点

• 空节点 (NULL) - represented as the empty string
  简单的表示空，在代码中是一个空串。
• 叶子节点 (leaf) - a 2-item node [encodedPath, value]
  表示为 [key,value] 的一个键值对，其中 key 是 key 的一种特殊十六进制编码 (MP 编码)， value 是 value 的 RLP 编码。
• 分支节点 (branch) - a 17-item node [v0 … v15, vt]
  因为 MPT 树中的 key 被编码成一种特殊的 16 进制的表示，再加上最后的 value，所以分支节点是一个 长度为 17 的 list，前 16 个元素对应着 key 中的 16 个可能的十六进制字符，如果有一个 [key,value] 对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。
• 扩展节点 (extension) - a 2-item node [encodedPath, key]也是 [key，value] 的一个键值对 ，但是这里的 value 是其他节点的 hash 值 ，这个 hash 可以被用来查询数据库中的节点。也就是说通过 hash 链接到其他节点。
  因此，有两种 [key,value] 节点(叶节点和扩展节点)

  以太坊中对 Key 的编码

  在以太坊中，MPT 树的 key 值共有三种不同的编码方式，以满足不同场景的不同需求。
  三种编码方式分别为：
  1.Raw 编码（原生的字符）；
  2.Hex 编码（扩展的 16 进制编码）；
  3.Hex-Prefix 编码（16 进制前缀编码）；

  Raw 编码

  Raw 编码就是原生的 key 值，不做任何改变。这种编码方式的 key，是 MPT 对外提供接口的默认编码方式。
  例如一条 key 为 “cat”，value 为“dog” 的数据项，其 key 的 Raw 编码就是[‘c’, ‘a’, ‘t’]，换成 ASCII 表示方式就是[63, 61, 74]（Hex）

  Hex 编码

  Hex 编码就是把一个 8 位的字节数据用两个十六进制数展示出来，编码时，将 8 位二进制码重新分组成两个 4 位的字节，其中一个字节的低 4 位是原字节的高四位，另一个字节的低 4 位是原数据的低 4 位，高 4 位都补 0，然后输出这两个字节对应十六进制数字作为编码。Hex 编码后的长度是源数据的 2 倍。
  例如：
  ASCII 码：A (65) 二进制码：0100_0001 重新分组：0000_0100 0000_0001 十六进制： 4 1 Hex 编码：41
  若该 Key 对应的节点存储的是真实的数据项内容（即该节点是叶子节点），则在末位添加一个 ASCII 值为 16 的字符作为 terminator；
  若该 key 对应的节点存储的是另外一个节点的哈希索引（即该节点是扩展节点），则不加任何字符；
  [‘c’,’a’,’t’] -> [6,3,6,1,7,4,16]

  HP 编码

  目的：
• 区分 leaf 和 extension
• 把奇数路径变成偶数路径

步骤：

• 如果有 terminator（16）那么就去掉 terminator。根据表格给 key 加上 prefix

node type	path length	prefix	hexchar
extension	even	0000	0x0
extension	odd	0001	0x1
leaf	even	0010	0x2
leaf	odd	0011	0x3

如果 prefix 是 0x0 或者 0x2，加一个 padding nibble 0 在 prefix 后面，所以最终应该是 0x00 和 0x20。原因是为了保证 key（path）的长度为偶数。
例子： 末尾的字符 “16” 说明该节点为叶子结点，并且加上了 0x20
[ 0, f, 1, c, b, 8, 16] -> ‘20 0f 1c b8’

编码转换关系

以上三种编码方式的转换关系为：
Raw 编码：原生的 key 编码，是 MPT 对外提供接口中使用的编码方式，当数据项被插入到树中时，Raw 编码被转换成 Hex 编码；
Hex 编码：16 进制扩展编码，用于对内存中树节点 key 进行编码，当树节点被持久化到数据库时，Hex 编码被转换成 HP 编码；
HP 编码：16 进制前缀编码，用于对数据库中树节点 key 进行编码，当树节点被加载到内存时，HP 编码被转换成 Hex 编码；

MPT 的结构

MPT 树的特点如下:

• 叶子节点和分支节点可以保存 value, 扩展节点保存 key；
• 没有公共的 key 就成为 2 个叶子节点；key1=[1,2,3] key2=[2,2,3]
• 有公共的 key 需要提取为一个扩展节点；key1=[1,2,3] key2=[1,3,3] => ex-node=[1], 下一级分支 node 的 key
• 如果公共的 key 也是一个完整的 key，数据保存到下一级的分支节点中；key1=[1,2] key2=[1,2,3] => ex-node=[1,2], 下一级分支 node 的 key; 下一级分支 =[3], 上一级 key 对应的 value

简单的结构如下图：

我们将存入如下 state 数据:

key	values
a711355	45.0 ETH
a77d337	1.00 WEI
a7f9365	1.1 ETH
a77d397	0.12 ETH

插入第一个，由于只有一个 key, 直接用 leaf node 既可表示
接着插入 a77d337, 由于和 a711355 共享前缀’a7’, 因而可以创建’a7’扩展节点。
接着插入 a7f9365, 也是共享’a7’, 只需新增一个 leaf node.
最后插入 a77d397, 这个 key 和 a77d337 共享’a7’+’d3’, 因而再需要创建一个’d3’扩展节点
将叶子节点和最后的 short node 合并到一个节点了，事实上源码实现需要再深一层，最后一层的叶子节点只有数据

// nodeFlag contains caching-related metadata about a node.
type nodeFlag struct {
    hash  hashNode // cached hash of the node (may be nil)
    gen   uint16   // cache generation counter
    dirty bool     // whether the node has changes that must be written to the database
}

MPT 节点有个 flag 字，nodeFlag，记录了一些辅助数据：

• 节点哈希：若该字段不为空，则当需要进行哈希计算时，可以跳过计算过程而直接使用上次计算的结果（当节点变脏时，该字段被置空）；
• 诞生标志：当该节点第一次被载入内存中（或被修改时），会被赋予一个计数值作为诞生标志，该标志会被作为节点驱除的依据，清除内存中 “太老” 的未被修改的节点，防止占用的内存空间过多；
• 脏标志：当一个节点被修改时，该标志位被置为 1；

flag.hash 会保存该节点采用 merkle tree 类似算法生成的 hash。同时会将 hash 和源数据以 方式保存在 leveldb 数据库中。这样后面通过 hash 就可以反推出节点数据。具体结构如下 (蓝色的 hash 部分就是 flag.hash 字段)

核心思想

hash 可以还原出节点上的数据，这样只需要保存一个 root(hash)，即可还原出完整的树结构，同时还可以按需展开节点数据，比如如果需要访问 这个数据，只需展开 h00, h10, h20, h30 这四个 hash 对应的节点。

出块后的变化

新发布一个区块的时候，某些账户的状态会发生变化，新区块中会为变化的账户重新建立分支，大部分不变的数据则指向历史区块中的分支，因此区块间会共享大部分不变的状态分支。如下图所示：

保留历史状态的好处：
未胜出的临时性分叉需要回滚才能继续出块，由于智能合约的执行不易反推执行，保留起始与结束的记录，回滚才比较方便。

账户树中保存全部账户信息的原因：
查找某个账户更快速，如果区块内只保存区块内交易的相关账户信息，查询某个很久没有交易的账户就要花费很长时间，最坏的情况是如果转账给一个从未进行交易的账户，就必须追溯到创世区块，最后有可能发现区块内没有该账户的信息。

应用

以太坊中的状态树、交易树、收据树都采用MPT。只有状态树会共享分支。

交易树

NewBlock函数里包含交易树、收据树的创建以及叔父区块处理。
创建交易树的步骤：

• 判断交易列表是否为空，如果为空，那么块头的根哈希就是空哈希值
• 如果不为空，调用DeriveSha函数得到交易树的根哈希值
• 然后创建区块的交易列表

  收据树

  创建收据树的步骤：
• 判断收据列表是否为空，如果为空，那么根哈希就是空哈希值
• 如果不为空，调用DeriveSha函数得到收据树的根哈希值
• 然后调用CreateBloom函数创建块头里的bloom filter

  叔父区块

  处理叔父区块：
• 判断叔父区块列表是否为空，如果为空，那么块头的叔父区块哈希值就是空的哈希值
• 如果不为空，调用CalcUncleHash计算哈希值
• 通过一个循环构建区块里的叔父数组

参考

MPT