[数据结构与算法]以太坊源码阅读3——MPT原理

以太坊源码阅读3——MPT原理

介绍

• MPT（Merkel-Patricia Tree），翻译为梅克尔-帕特里夏树
• MPT提供了一个基于密码学验证的底层数据结构，用来存储键值对( key-value)关系
• MPT是完全确定性的，这是指在一颗MPT上一-组键值对
  是唯一确定的，相同内容的键可以保证找到同样的值，并
  且有同样的根哈希( root hash)
• MPT的插入、查找、删除操作的事件复杂度都是0(log(n)),
  相对于其它基于复杂比较的树结构(比如红黑树)，MPT
  更容易理解，也更易于编码实现

字典树（Trie）

• 字典树(Trie) 也称前缀树( prefix tree)，属于搜索树，是一种有序的树数据结构
• 字典树用于存储动态的集合或映射，其中的键通常是字符串

字典树在非根节点存储数据，在叶子节点存储最终的value，CRUD的时候只需要依据数据的每个字符遍历节点向下查询，缺点就是存储空间消耗大

基数树（Radix Tree）

为了解决字典树存储空间消耗大的问题而产生

基数树又叫压缩前缀树( compact prefix tree)是一种空间优化后的字典树，其中如果一个节点只有唯一的子节点，那么这个子节点就会与父节点合并存储

简单的说就是，如果有多个字符分支，那就分叉，否则就压缩合并

基数树的问题：

• 数据校验: 基数树节点之间的连接方式是指针，一般是用32位或64位的内存地址作为指针的值，比如C语言就是这么做的。但这种直接存
  地址的方式无法提供对数据内容的校验，而这在区块链这样的
  分布式系统中非常重要。

• 访问效率：基数树的另一个问题是低效。如果我们只想存-一个bytes32类型的键值对，访问路径长度就是64(在以太坊定义的Hex字符集下) ;每一级访问的节点都至少需要存储16个字节，这样就需要至少1k字节的额外空间，而且每次查找和删除都必须完整地执行64次下探访问。

梅克尔树（Merkel Tree）

解决数据校验问题

也被称作哈希树(Hash Tree)，以数据块的hash值作为叶子节点存储值。梅克尔树的非叶子节点存储其子节点内容串联拼接后的hash.值。

在梅克尔树中，使用rlp（value）再做hash，hash会作为地址（key）

帕特里夏树(Patricia Tree)

解决访问效率问题

• 如果一个基数树的“基数”(radix) 为2或2的整数次幂，就被称为“帕特里夏树”，有时也直接认为帕特里夏树就是基数树
• 以太坊中采用Hex字符作为key的字符集，也就是基数为16的帕特里夏树
• 以太坊中的树结构，每个节点可以有最多16个子节点，再加上value，所以共有17个“插槽”(slot) 位置
• 以太坊中的帕特里夏树加入了一些额外的数据结构，主要是为了解决效率问题

MPT (Merkel Patricia Tree)

详情

• 梅克尔-帕特里夏树是梅克尔树和帕特里夏树的结合
• 以太坊中的实现，对key采用Hex编码，每个Hex字符就是一.
  个nibble (半字节)
• 遍历路径时对-一个节点只访问它的一一个nibble，大多数节点是.一个包含17个元素的数组:其中16个分别以hex字符作为索引值，存储路径中下一个nibble的指针;另–个存储如果路径到此已遍历结束，需要返回的最终值。这样的节点叫做“分支节点”( branch node)
• 分支节点的每个元素存储的是指向下一-级节点的指针。与传统做法不同，MPT是用所指向节点的hash来代表这个指针的;每个节点将下个节点的hash作为自己存储内容的一部分，这样就实现了Merkel树结构，保证了数据校验的有效性

节点分类

• 空节点(NULL)
  • 表示空字符串
• 分支节点(branch )
  • 17个元素的节点，结构为[v0… v15, vt]
• 叶子节点(leaf)
  • 拥有两个元素，编码路径encodedPath和值value
• 扩展节点( extension)
  • 拥有两个元素，编码路径encodedPath和键key
  • 用于压缩前缀，encodedPath存储压缩后的数据，key用于指向下一个节点

MPT中数据结构的优化

• 对于64个字符的路径长度，很有可能在某个节点处会发现，下面至少有一段路径没有分叉;这很难避免
• 我们当然可以依然用标准的分支节点来表示，强制要求这个节点必须有完整的16个索引，并给没有用到的那15个位置全部赋空值;但这样有点蠢.
• 通过设置“扩展节点”，就可以有效地缩短访问路径，将冗长的层级关系压缩成一个键值对，避免不必要的空间浪费
• 扩展节点(extension node)的内容形式是[encodedPath, key],其中encodedPath包含了下面不分叉的那部分路径，key 是指向下一个节点的指针(hash，也即在底层db中的存储位置)
• 叶子节点(leafnode) :如果在某节点后就没有了分叉路径，那这是一个叶子节点，它的第二个元素就是自己的value

紧凑编码(compact coding)

16进制前缀编码

它能够存储一个额外的标志，当在trie的上下文（使用它的唯一上下文）中使用时，可以消除节点类型之间的歧义。

详情

• 路径压缩的处理相当于实现了压缩前缀树的功能;不过路径表示是Hex字符串( nibbles)，而存储却是以字节(byte)为单位的，这相当浪费了一倍的存储空间
• 我们可以采用一种紧凑编码(compact coding)方式，将两个nibble整合在个字节中保存，这就避免了不必要的浪费
• 这里就会带来一个问题:有可能nibble总数是一个奇数，而数据总是以字节形式存储的，所以无法区分nibble1和nibbles01;这就使我们必须分别处理奇偶两种情况
• 为了区分路径长度的奇偶性，我们在encodedPath中引入标识位

Hex序列的压缩编码规则

• 我们在encodedPath中，加入一个nibble作为前缀，它的后两
  位用来标识节点类型和路径长度的奇偶性

• MPT中还有一一个可选的“结束标记”(用T表示) ，值为0x10(十进制的16)，它仅能在路径末尾出现，代表节点是一一个最终节点(叶子节点)
• 如果路径是奇数，就与前缀nibble凑成整字节;如果是偶数，则前缀nibble后补0000构成整字节

编码示例：

MPT树结构示例

以查询45.0ETH为例，右上角指明keys为 a711355 ，root 的nibbles为a7，下一个key为1，则root的next node 指向branch node的branch node[1],keys a711355 已经查询完a71 ，左节点的key-end正好为剩下的1355，则该节点的value即为45.2ETH。由于抵达该路径的距离为2，且是叶子节点，根据上面的Hex序列的压缩编码规则，可得前缀为2。

以太坊中树结构

以太坊中所有的merkel树都是MPT
在一个区块的头部(block head)中，有三颗MPT的树根:

• stateRoot
  • 状态树的树根
• transactionRoot
  • 交易树的树根
• receiptsRoot
  • 收据树的树根

• 状态树(state trie)

  • 世界状态树，随时更新;它存储的键值对(path, value)可以表示为(sha3(ethereumAddress), rlp(ethereumAccount))

  • 这里的account是4个元素构成的数组: [nonce,balance,storageRoot,codeHash]

• 存储树(storage trie )

  • 存储树是保存所有合约数据的地方:每个合约账户都有一个独立隔离的存储空间

• 交易树(transaction trie )

  • 每个区块都会有单独的交易树;它的路径(path)是rlp(transactionIndex)，只有在挖矿时才能确定:一旦出块， 不再更改

• 收据树(receipts trie)

  • 每个区块也有自己的收据树:路径也表示为rlp(transactionlndex)

参考

尚硅谷区块链全套教程完整版(深入掌握以太坊核心技术)_哔哩哔哩_bilibili