死磕以太坊源码分析之MPT树-上

前缀树Trie

前缀树（又称字典树），通常来说，一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。如下图所示：

Trie的结点看上去是这样子的：

[ [Ia, Ib, … I*], value]

其中 [Ia, Ib, ... I*] 在本文中我们将其称为结点的 索引数组 ，它以 key 中的下一个字符为索引，每个元素I*指向对应的子结点。 value 则代表从根节点到当前结点的路径组成的key所对应的值。如果不存在这样一个 key，则 value 的值为空。

前缀树的性质：

1. 每一层节点上面的值都不相同；

2. 根节点不存储值；除根节点外每一个节点都只包含一个字符，代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符。

3. 前缀树的查找效率是$O(m)$，$m$为所查找节点的长度，而哈希表的查找效率为$O(1)$。且一次查找会有 m 次 IO开销，相比于直接查找，无论是速率、还是对磁盘的压力都比较大。

4. 当存在一个节点，其内容很长（如一串很长的字符串），当树中没有与他相同前缀的分支时，为了存储该节点，需要创建许多非叶子节点来构建根节点到该节点间的路径，造成了存储空间的浪费。

压缩前缀树Patricia Tree

基数树（也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的前缀树，其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数 r ，其中 r 为正整数， x 为 2 的幂， x≥1 ，这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。

图中可以很容易看出数中所存储的键值对：

• 6c0a5c71ec20bq3w => 5
• 6c0a5c71ec20CX7j => 27
• 6c0a5c71781a1FXq => 18
• 6c0a5c71781a9Dog => 64
• 6c0a8f743b95zUfe => 30
• 6c0a8f743b95jx5R => 2
• 6c0a8f740d16y03G => 43
• 6c0a8f740d16vcc1 => 48

默克尔树Merkle Tree

Merkle树看起来非常像二叉树，其叶子节点上的值通常为数据块的哈希值，而非叶子节点上的值，所以有时候Merkle tree也表示为Hash tree，如下图所示：

在构造Merkle树时，首先要计算数据块的哈希值，通常，选用SHA-256等哈希算法。但如果仅仅防止数据不是蓄意的损坏或篡改，可以改用一些安全性低但效率高的校验和算法，如CRC。然后将数据块计算的哈希值两两配对（如果是奇数个数，最后一个自己与自己配对），计算上一层哈希，再重复这个步骤，一直到计算出根哈希值。

所以我们可以简单总结出merkle Tree 有以下几个性质：

• 校验整体数据的正确性
• 快速定位错误
• 快速校验部分数据是否在原始的数据中
• 存储空间开销大（大量中间哈希）

以太坊的改进方案

使用[]byte作为key类型

在以太坊的Trie模块中，key和value都是[]byte类型。如果要使用其它类型，需要将其转换成[]byte类型（比如使用rlp进行转换）。

Nibble ：是 key 的基本单元，是一个四元组（四个 bit 位的组合例如二进制表达的 0010 就是一个四元组）

在Trie模块对外提供的接口中，key类型是[]byte。但在内部实现里，将key中的每个字节按高4位和低4位拆分成了两个字节。比如你传入的key是：

[0x1a, 0x2b, 0x3c, 0x4d]

Trie内部将这个key拆分成：

[0x1, 0xa, 0x2, 0xb, 0x3, 0xc, 0x4, 0xd]

Trie内部的编码中将拆分后的每一个字节称为 nibble

如果使用一个完整的 byte 作为 key 的最小单位，那么前文提到的索引数组的大小应该是 256（byte作为数组的索引，最大值为255，最小值为0）。而索引数组的每个元素都是一个 32 字节的哈希,这样每个结点要占用大量的空间。并且索引数组中的元素多数情况下是空的，不指向任何结点。因此这种实现方法占用大量空间而不使用。以太坊的改进方法，可以将索引数组的大小降为 16（4个bit的最大值为0xF，最小值为 0），因此大大减少空间的浪费。

新增类型节点

前缀树和merkle树存在明显的局限性，所以以太坊为MPT树新增了几种不同类型的树节点，通过针对不同节点不同操作来解决效率以及存储上的问题。

1. 空白节点 ：简单的表示空，在代码中是一个空串
2. 分支节点 ：分支节点有 17 个元素，回到 Nibble，四元组是 key 的基本单元，四元组最多有 16 个值。所以前 16 个必将落入到在其遍历中的键的十六个可能的半字节值中的每一个。第 17 个是存储那些在当前结点结束了的节点(例如， 有三个 key,分别是 (abc ,abd, ab) 第 17 个字段储存了 ab 节点的值)
3. 叶子节点：只有两个元素，分别为 key 和 value
4. 扩展节点 ：有两个元素，一个是 key 值，还有一个是 hash 值，这个 hash 值指向下一个节点

此外，为了将 MPT 树存储到数据库中，同时还可以把 MPT 树从数据库中恢复出来，对于 Extension 和 Leaf 的节点类型做了特殊的定义：如果是一个扩展节点，那么前缀为 0，这个 0 加在 key 前面。如果是一个叶子节点，那么前缀就是 1。同时对key 的长度就奇偶类型也做了设定，如果是奇数长度则标示 1，如果是偶数长度则标示 0。

以太坊中使用到的MPT树结构

• State Trie 区块头中的状态树
  • key => sha3(以太坊账户地址 address)
  • value => rlp(账号内容信息 account)
• Transactions Trie 区块头中的交易树
  • key => rlp(交易的偏移量 transaction index)
  • 每个块都有各自的交易树，且不可更改
• Receipts Trie 区块头中的收据树
  • key = rlp(交易的偏移量 transaction index)
  • 每个块都有各自的交易树，且不可更改
• Storage Trie 存储树
  • 存储只能合约状态
  • 每个账号有自己的 Storage Trie

这两个区块头中，state root、tx root、 receipt root分别存储了这三棵树的树根，第二个区块显示了当账号 17 5的数据变更(27 -> 45)的时候，只需要存储跟这个账号相关的部分数据，而且老的区块中的数据还是可以正常访问。

key编码规则

三种编码方式分别为：

1. Raw编码（原生的字符）；
2. Hex编码（扩展的16进制编码）；
3. Hex-Prefix编码（16进制前缀编码）；

Raw编码

Raw编码就是原生的key值，不做任何改变。这种编码方式的key，是MPT对外提供接口的默认编码方式。

例如一条key为“cat”，value为“dog”的数据项，其Raw编码就是[‘c’, ‘a’, ‘t’]，换成ASCII表示方式就是[63, 61, 74]

Hex编码

Hex编码用于对内存中MPT树节点key进行编码.

为了减少分支节点孩子的个数，将数据 key 进行半字节拆解而成。即依次将 key[0],key[1],…,key[n] 分别进行半字节拆分成两个数，再依次存放在长度为 len(key)+1 的数组中。 并在数组末尾写入终止符 16。算法如下：

半字节，在计算机中，通常将8位二进制数称为字节，而把4位二进制数称为半字节。 高四位和低四位，这里的“位”是针对二进制来说的。比如数字 250 的二进制数为 11111010，则高四位是左边的 1111，低四位是右边的 1010。

从Raw编码向Hex编码的转换规则是：

• Raw编码输入的每个字符分解为高 4 位和低 4 位
• 如果是叶子节点，则在最后加上Hex值0x10表示结束
• 如果是分支节点不附加任何Hex值

例如：字符串 “romane” 的 bytes 是 [114 111 109 97 110 101]，在 HEX 编码时将其依次处理：

最终得到 Hex(“romane”) = [7 2 6 15 6 13 6 1 6 14 6 5 16]

// 源码实现
func keybytesToHex(str []byte) []byte {
	l := len(str)*2 + 1
	var nibbles = make([]byte, l)
	for i, b := range str {
		nibbles[i*2] = b / 16   // 高四位
		nibbles[i*2+1] = b % 16 // 低四位
	}
	nibbles[l-1] = 16 // 最后一位存入标示符 代表是hex编码
	return nibbles
}

Hex-Prefix编码

数学公式定义：

Hex-Prefix 编码是一种任意量的半字节转换为数组的有效方式，还可以在存入一个标识符来区分不同节点类型。 因此 HP 编码是在由一个标识符前缀和半字节转换为数组的两部分组成。存入到数据库中存在节点 Key 的只有扩展节点和叶子节点，因此 HP 只用于区分扩展节点和叶子节点，不涉及无节点 key 的分支节点。其编码规则如下图：

前缀标识符由两部分组成：节点类型和奇偶标识，并存储在编码后字节的第一个半字节中。 0 表示扩展节点类型，1 表示叶子节点，偶为 0，奇为 1。最终可以得到唯一标识的前缀标识：

• 0：偶长度的扩展节点
• 1：奇长度的扩展节点
• 2：偶长度的叶子节点
• 3：奇长度的叶子节点

当偶长度时，第一个字节的低四位用0填充，当是奇长度时，则将 key[0] 存放在第一个字节的低四位中，这样 HP 编码结果始终是偶长度。 这里为什么要区分节点 key 长度的奇偶呢？这是因为，半字节 1 和 01 在转换为 bytes 格式时都成为<01>，无法区分两者。

例如，上图 “以太坊 MPT 树的哈希计算”中的控制节点1的key 为 [ 7 2 6 f 6 d]，因为是偶长度，则 HP[0]= (00000000) =0，H[1:]= 解码半字节(key)。 而节点 3 的 key 为 [1 6 e 6 5]，为奇长度，则 HP[0]= (0001 0001)=17。

HP编码的规则如下：

• key结尾为0x10，则去掉这个终止符
• key之前补一个四元组这个Byte第0位区分奇偶信息，第 1 位区分节点类型
• 如果输入key的长度是偶数，则再添加一个四元组0x0在flag四元组后
• 将原来的key内容压缩，将分离的两个byte以高四位低四位进行合并

十六进制前缀编码相当于一个逆向的过程，比如输入的是[6 2 6 15 6 2 16]，

根据第一个规则去掉终止符16。根据第二个规则key前补一个四元组，从右往左第一位为1表示叶子节点，

从右往左第0位如果后面key的长度为偶数设置为0，奇数长度设置为1，那么四元组0010就是2。

根据第三个规则，添加一个全0的补在后面，那么就是20.根据第三个规则内容压缩合并，那么结果就是[0x20 0x62 0x6f 0x62]

HP 编码源码实现:

func hexToCompact(hex []byte) []byte {
	terminator := byte(0) //初始化一个值为0的byte，它就是我们上面公式中提到的t
	if hasTerm(hex) {     //验证hex有后缀编码，
		terminator = 1         //hex编码有后缀，则t=1
		hex = hex[:len(hex)-1] //此处只是去掉后缀部分的hex编码
	}
	////Compact开辟的空间长度为hex编码的一半再加1，这个1对应的空间是Compact的前缀
	buf := make([]byte, len(hex)/2+1)
	////这一阶段的buf[0]可以理解为公式中的16*f(t)
	buf[0] = terminator << 5 // the flag byte
	if len(hex)&1 == 1 {     //hex 长度为奇数，则逻辑上说明hex有前缀
		buf[0] |= 1 << 4 ////这一阶段的buf[0]可以理解为公式中的16*（f(t)+1）
		buf[0] |= hex[0] // first nibble is contained in the first byte
		hex = hex[1:]    //此时获取的hex编码无前缀无后缀
	}
	decodeNibbles(hex, buf[1:]) //将hex编码映射到compact编码中
	return buf                  //返回compact编码
}

以上三种编码方式的转换关系为：

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

如下图：

以上介绍的MPT树，可以用来存储内容为任何长度的key-value数据项。倘若数据项的key长度没有限制时，当树中维护的数据量较大时，仍然会造成整棵树的深度变得越来越深，会造成以下影响：

• 查询一个节点可能会需要许多次 IO 读取，效率低下；
• 系统易遭受 Dos 攻击，攻击者可以通过在合约中存储特定的数据，“构造”一棵拥有一条很长路径的树，然后不断地调用SLOAD指令读取该树节点的内容，造成系统执行效率极度下降；
• 所有的 key 其实是一种明文的形式进行存储；

为了解决以上问题，以太坊对MPT再进行了一次封装，对数据项的key进行了一次哈希计算，因此最终作为参数传入到MPT接口的数据项其实是(sha3(key), value)

优势：

• 传入MPT接口的 key 是固定长度的（32字节），可以避免出现树中出现长度很长的路径；

劣势：

• 每次树操作需要增加一次哈希计算；
• 需要在数据库中存储额外的sha3(key)与key之间的对应关系；

完整的编码流程如图：

MPT轻节点

上面的MPT树，有两个问题：

• 每个节点都包含有大量信息，并且叶子节点中还包含有完整的数据信息。如果该MPT树并没有发生任何变化，并且没有被使用，则会白白占用一大片空间，想象一个以太坊，有多少个MPT树，都在内存中，那还了得。
• 并不是任何的客户端都对所有的MPT树都感兴趣，若每次都把完整的节点信息都下载下，下载时间长不说，并且会占用大量的磁盘空间。

解决方式

为了解决上述问题，以太坊使用了一种缓存机制，可以称为是轻节点机制，大体如下：

• 若某节点数据一直没有发生变化，则仅仅保留该节点的32位hash值，剩下的内容全部释放
• 若需要插入或者删除某节点，先通过该hash值db中查找对应的节点，并加载到内存，之后再进行删除插入操作

轻节点中添加数据

内存中只有这么一个轻节点，但是我要添加一个数据，也就是要给完整的MPT树中添加一个叶子节点，怎么添加？大体如下图所示：

到此以太坊的MPT树的基础讲解结束。

参考

https://mindcarver.cn

https://github.com/blockchainGuide 文章及视频学习资料

https://eth.wiki/en/fundamentals/patricia-tree

https://ethereum.github.io/yellowpaper/paper.pdf#appendix.D

https://ethfans.org/toya/articles/588

https://learnblockchain.cn/books/geth/part3/mpt.html

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

https://arxiv.org/pdf/1909.11590.pdf