以太坊MPT数据结构介绍

介绍

go-etherum的包trie实现了Merkle Patricia Tries，这里简称为MPT。 这种数据结构实际上是 Trie 树的一种变体。 MPT是以太坊中非常重要的数据结构。 存储用户账户状态及其变化、交易信息、交易回执信息。 MPT实际上是三种数据结构的组合，分别是Trie树、Patricia Trie和Merkle树。

Trie树（引用自数据结构的Trie树）

Trie 树，也称为词典树、单词搜索树或前缀树，是一种用于快速检索的多叉树结构。 例如，英文字母的字典树是26-tree，数字的字典树是10-tree。

Trie 树可以使用字符串的公共前缀来节省存储空间。 如下图所示，trie树用10个节点保存了6个字符串：tea,ten,to,in,inn,int：

特里.jpg

在trie树中，in、inn、int这几个字符串的共同前缀是“in”，所以为了节省空间以太坊数据，可以只存一份“in”。 当然，如果系统中存在大量的字符串，而这些字符串基本没有共同的前缀，对应的trie树就会消耗大量的内存，这也是trie树的一个缺点。

Trie树的基本属性可以概括为：

Trie树的优缺点：

缺点：

优势：

帕特里夏树（简单来说引用自以太坊）

Patricia树，或Patricia trie，或crit bit tree，压缩前缀树，是一种比较节省空间的Trie。 对于基数树的每个节点，如果该节点是唯一的子节点，则将其与父节点合并。

帕特里夏.png

帕特里夏的优点和缺点：

优点：Patricia Trie相对于Trie有明显优势，减少空间消耗。

缺点：随着后续节点的不断插入和删除以太坊数据，原有节点可能发生变化，可能不会改变或合并新的节点

Merkle树（简单的引用自以太坊）

Merkle Tree，俗称哈希树，顾名思义，是一种存储哈希值的树。 Merkle 树的叶子是数据块（例如，文件或文件集合）的哈希值。 非叶节点是其相应子节点的串联字符串的散列。

要理解Merkle Tree，首先要从Hash List说起：

在点对点网络中传输数据时，会同时从多台机器下载数据，许多机器可以被认为是不稳定或不可信的。 为了验证数据的完整性，比较好的方法是将大文件分成小的数据块（比如分成2K的数据块）。 这样做的好处是，如果在传输过程中有一小块数据损坏了，只需要重新下载这块快数据，而不用重新下载整个文件。

如何保证小数据块没有损坏？ 只需要对每个数据块做Hash。 下载BT时，在下载真正的数据之前，我们会先下载一个Hash列表。 那么问题又来了，如何保证Hash列表本身是正确的呢？ 答案是把每一小块数据的Hash值放在一起，然后对这个长串进行Hash运算，从而得到Hash列表的根Hash（Top Hash或Root Hash）。 下载数据时，首先从可信数据源获取正确的根哈希，然后用它来验证哈希列表，再通过验证后的哈希列表来验证数据块。

哈希表.png

Merkle Tree可以看作是Hash List的推广（Hash List可以看作是一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree。

在最底层，就像哈希表一样，我们将数据分成小块，并有相应的哈希与之对应。 但是往上走，并不是直接计算根哈希，而是将相邻的两个哈希组合成一个字符串，然后计算这个字符串的哈希，这样每两个哈希结婚生子，就得到了一个“子” -哈希”。 如果底层的哈希总数是奇异的，那么末尾一定只有一个哈希。 此时直接对其进行哈希运算，因此也可以得到其子哈希。 所以往上推，还是老样子，可以用更少的数得到新一级的哈希，最终必然形成一棵倒树。 在树根的这个位置，这一代只剩下一个根哈希。 我们称之为默克尔根。

默克尔树.png

在 p2p 网络上下载网络之前，首先从可信来源获取文件的 Merkle Tree 根。 一旦获得根，就可以从其他不受信任的来源获得 Merkle 树。 根据可信根检查收到的 MerkleTree。 如果 Merkle Tree 损坏或伪造，则从其他来源获得另一棵 Merkle Tree，直到获得与可信树根匹配的 MerkleTree。

Merkle Tree 和 HashList 的主要区别在于 Merkle Tree 的一个分支可以直接下载并立即验证。 因为文件可以分成小的数据块，所以如果某个数据块损坏了，只要重新下载这个数据块即可。 如果文件很大，Merkle树和Hash链表都可以，但是Merkle树可以一次下载一个分支，然后立即对分支进行验证。 如果分支验证通过，则可以下载数据。 哈希列表只能通过下载整个哈希列表来验证。

MPTTrie结构

MPT是以太坊定制的Trie类数据结构。 代码中使用trie.Trie结构来管理一个MPT结构，其中每个节点都是行为接口Node的一个实现类。 下图是Trie结构和节点接口族的UML图：

特里.png

节点

节点接口族负责整个MPT中的各个节点。 节点接口分为四种实现：fullNode、shortNode、valueNode、hashNode，其中只有fullNode和shortNode可以有子节点。

fullNode 是一个可以携带多个子节点的节点。

shortNode 是只有一个孩子的节点。

valueNode MPT结构中承载真实数据部分的节点。

这三种类型构成了一个完整的PatriciaTrie结构。 当任何 [k, v] 类型的数据插入到 MPT 中时，它将以 k 字符串为路径沿着根向下扩展。 在本次插入结束时，首先会变成一个shortNode，k会从顶点到根节点终止的关键路径格式存在。 但是，随着其他节点的不断插入和删除，根据MPT结构的要求，原来的节点可能会变成其他节点实现类型，同时MPT也会不断的改变或合并新的节点。

注：黄皮书将节点类型概括为分支节点、扩展节点和叶节点。 fullNode对应黄皮书中的分支节点，s​​hortNode对应黄皮书中的扩展节点和叶子节点（shortNode.Val的类型对应是叶子节点还是分支节点，如果是valueNode，为叶节点，否则为分支节点）。

哈希节点

hashNode和valueNode一样，也是字符数组[]byte的别名，也是存储32byte的hash值，没有子节点。 不同的是hashNode是fullNode或者shortNode对象的RLP hash值，所以在用法上和valueNode有很大区别。

在MPT中，hashNode几乎不单独存在（有时遍历遇到一个hashNode，往往是因为原节点被折叠），而是以nodeFlag结构体（nodeFlag.hash）成员的形式被fullNode和shortNode间接持有。 一旦fullNode或shortNode的成员变量（包括子结构）发生变化，它们的hashNode就必须更新。 因此在trie.Trie结构体的insert()、delete()等函数的实现中，可以看到除了新建的fullNode和shortNode之外，子结构发生变化的fullNode和shortNode的nodeFlag成员也会也被重置。 hashNode 将被清除。 下次调用trie.Hash()时，自下而上遍历整个MPT时，所有清空的hashNode会被重新赋值。 这样在trie.Hash()结束后，我们就可以得到根节点root的一个hashNode，也就是此时MPT结构的hash值。 上面说到，Block的成员变量Root、TxHash、ReceiptHash的生成就是由此而来。

显然，hashNode体现了MerkleTree的特点：每个父节点的hash值来自于所有子节点的hash值的组合，一个顶点的hash值可以代表一整个树结构。

hashNode加上前面的fullNode、shortNode、valueNode构成了一个完整的Merkle-PatriciaTrie结构。

MPT的一个简单例子：

MPT.png