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

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

前缀树Trie

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

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

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 ,这使得基数树更适用于对于较小的集合(尤其是字符串很长的情况下)和有很长相同前缀的字符串集合。

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

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

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

默克尔树Merkle Tree

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

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

在构造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

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

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

key编码规则

三种编码方式分别为:

  1. Raw编码(原生的字符);
  2. Hex编码(扩展的16进制编码);
  3. Hex-Prefix编码(16进制前缀编码);

Raw编码

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

例如一条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 位
  • 如果是叶子节点,则在最后加上Hex0x10表示结束
  • 如果是分支节点不附加任何Hex

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

i key[i] key[i]二进制 nibbles[i*2]=高四位 nibbles[i*2+1]=低四位
0 114 01110010 0111= 7 0010= 2
1 111 01101111 0110=6 1111=15
2 109 01101101 0110=6 1101=13
3 97 01100001 0110=6 0001=1
4 110 01101110 0110=6 1110=14
5 101 01100101 0110=6 0101=5

最终得到 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编码

数学公式定义:

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

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

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

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

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

当偶长度时,第一个字节的低四位用0填充,当是奇长度时,则将 key[0] 存放在第一个字节的低四位中,这样 HP 编码结果始终是偶长度。 这里为什么要区分节点 key 长度的奇偶呢?这是因为,半字节 101 在转换为 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树-上

以上介绍的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树,都在内存中,那还了得。
  • 并不是任何的客户端都对所有的MPT树都感兴趣,若每次都把完整的节点信息都下载下,下载时间长不说,并且会占用大量的磁盘空间。

解决方式

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

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

轻节点中添加数据

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

死磕以太坊源码分析之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

发表评论

评论已关闭。

相关文章