死磕以太坊源码分析之MPT树-上
前缀树Trie
前缀树(又称字典树),通常来说,一个前缀树是用来存储字符串
的。前缀树的每一个节点代表一个字符串
(前缀
)。每一个节点会有多个子节点,通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串
,以及通往该子节点路径上所有的字符
组成的。如下图所示:
Trie的结点看上去是这样子的:
[ [Ia, Ib, … I*], value]
其中 [Ia, Ib, ... I*]
在本文中我们将其称为结点的 索引数组 ,它以 key 中的下一个字符为索引,每个元素I*
指向对应的子结点。 value
则代表从根节点到当前结点的路径组成的key所对应的值。如果不存在这样一个 key,则 value 的值为空。
前缀树的性质:
-
每一层节点上面的值都不相同;
-
根节点不存储值;除根节点外每一个节点都只包含一个字符,代表的字符串是由节点本身的
原始字符串
,以及通往该子节点路径上所有的字符
。 -
前缀树的查找效率是,为所查找节点的长度,而哈希表的查找效率为。且一次查找会有 m 次
IO
开销,相比于直接查找,无论是速率、还是对磁盘的压力都比较大。 -
当存在一个节点,其内容很长(如一串很长的字符串),当树中没有与他相同前缀的分支时,为了存储该节点,需要创建许多非叶子节点来构建根节点到该节点间的路径,造成了存储空间的浪费。
压缩前缀树Patricia Tree
基数树(也叫基数特里树或压缩前缀树)是一种数据结构,是一种更节省空间的前缀树,其中作为唯一子节点的每个节点都与其父节点合并,边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数 r ,其中 r 为正整数, x 为 2 的幂, x≥1 ,这使得基数树更适用于对于较小的集合(尤其是字符串很长的情况下)和有很长相同前缀的字符串集合。
image-20201231133805927图中可以很容易看出数中所存储的键值对:
- 6c0a5c71ec20bq3w => 5
- 6c0a5c71ec20CX7j => 27
- 6c0a5c71781a1FXq => 18
- 6c0a5c71781a9Dog => 64
- 6c0a8f743b95zUfe => 30
- 6c0a8f743b95jx5R => 2
- 6c0a8f740d16y03G => 43
- 6c0a8f740d16vcc1 => 48
默克尔树Merkle Tree
Merkle树看起来非常像二叉树,其叶子节点上的值通常为数据块的哈希值,而非叶子节点上的值,所以有时候Merkle tree也表示为Hash tree,如下图所示:
image-20201230225028932在构造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树新增了几种不同类型的树节点,通过针对不同节点不同操作来解决效率以及存储上的问题。
- 空白节点 :简单的表示空,在代码中是一个空串
- 分支节点 :分支节点有 17 个元素,回到 Nibble,四元组是 key 的基本单元,四元组最多有 16 个值。所以前 16 个必将落入到在其遍历中的键的十六个可能的半字节值中的每一个。第 17 个是存储那些在当前结点结束了的节点(例如, 有三个 key,分别是 (abc ,abd, ab) 第 17 个字段储存了 ab 节点的值)
- 叶子节点:只有两个元素,分别为 key 和 value
- 扩展节点 :有两个元素,一个是 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编码规则
三种编码方式分别为:
- Raw编码(原生的字符);
- Hex编码(扩展的16进制编码);
- 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 编码时将其依次处理:
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编码
数学公式定义:
image-20201231170415071Hex-Prefix 编码是一种任意量的半字节转换为数组的有效方式,还可以在存入一个标识符来区分不同节点类型。 因此 HP 编码是在由一个标识符前缀和半字节转换为数组的两部分组成。存入到数据库中存在节点 Key 的只有扩展节点和叶子节点,因此 HP 只用于区分扩展节点和叶子节点,不涉及无节点 key 的分支节点。其编码规则如下图:
image-20201231164209626前缀标识符由两部分组成:节点类型和奇偶标识,并存储在编码后字节的第一个半字节中。 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编码;
如下图:
image-20201231150011417以上介绍的MPT树,可以用来存储内容为任何长度的key-value
数据项。倘若数据项的key
长度没有限制时,当树中维护的数据量较大时,仍然会造成整棵树的深度变得越来越深,会造成以下影响:
- 查询一个节点可能会需要许多次 IO 读取,效率低下;
- 系统易遭受 Dos 攻击,攻击者可以通过在合约中存储特定的数据,“构造”一棵拥有一条很长路径的树,然后不断地调用
SLOAD
指令读取该树节点的内容,造成系统执行效率极度下降; - 所有的 key 其实是一种明文的形式进行存储;
为了解决以上问题,以太坊对MPT再进行了一次封装,对数据项的key进行了一次哈希计算,因此最终作为参数传入到MPT接口的数据项其实是(sha3(key), value)
优势:
- 传入MPT接口的 key 是固定长度的(32字节),可以避免出现树中出现长度很长的路径;
劣势:
- 每次树操作需要增加一次哈希计算;
- 需要在数据库中存储额外的
sha3(key)
与key
之间的对应关系;
完整的编码流程如图:
image-20201231150520220MPT轻节点
上面的MPT树,有两个问题:
- 每个节点都包含有大量信息,并且叶子节点中还包含有完整的数据信息。如果该MPT树并没有发生任何变化,并且没有被使用,则会白白占用一大片空间,想象一个以太坊,有多少个MPT树,都在内存中,那还了得。
- 并不是任何的客户端都对所有的MPT树都感兴趣,若每次都把完整的节点信息都下载下,下载时间长不说,并且会占用大量的磁盘空间。
解决方式
为了解决上述问题,以太坊使用了一种缓存机制,可以称为是轻节点机制,大体如下:
- 若某节点数据一直没有发生变化,则仅仅保留该节点的32位hash值,剩下的内容全部释放
- 若需要插入或者删除某节点,先通过该hash值db中查找对应的节点,并加载到内存,之后再进行删除插入操作
轻节点中添加数据
内存中只有这么一个轻节点,但是我要添加一个数据,也就是要给完整的MPT树中添加一个叶子节点,怎么添加?大体如下图所示:
image-20210101204824090到此以太坊的MPT树的基础讲解结束。
参考
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
网友评论