请选择 进入手机版 | 继续访问电脑版
 找回密码
 立即注册
评测文章详情

一文读懂以太坊存储数据核心数据结构:MPT

2019-05-19阅读 17481 区块链大本营 我要关注


作者 | JouyPub

来源 | 简书

出品 | 区块链大本营



MPT (Merkle Patricia Tries) 是以太坊存储数据的核心数据结构,它是由 Merkle Tree 和 Patricia Tree 结合的一种树形结构,理解 MPT 有助于我们更好的理解以太坊的数据存储


在了解 MPT 数据结构之前,我们需要先来看看基本的 Tree 结构和 Merkle Tree、Patricia Tree。




Trie 字典树


Trie 树,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。




上图是一棵 Trie 树,表示了字符串集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ,从上图中我们可以看出Trie树的特点:


  • 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

  • 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

  • 每个节点的所有子节点包含的字符互不相同。


但是从上面的结构也可以看出一个问题:高度不可控,如下图所示。所以就有了 Patricia 树 (压缩前缀树),后面会介绍到。





Merkle树


Merkle树,也被称为 Hash Tree,中文名称:默克尔树,主要用于数据集较大时的文件校验。其主要特点为:


  • 叶节点存储着数据块的 Hash(如:文件块、一段数据集)

  • 非叶子节点 (包括中间节点和根节点) 存储着对应子节点 Hash 值串联字符串之后的 Hash 值。




从上图中可以看出:


  • 在最底层,和哈希列表一样,我们把数据分成小的数据块,有相应地哈希和它对应;

  • 往上走,并不是直接去运算根哈希,而是把相邻的两个哈希合并成一个字符串,然后运算这个字符串的哈希,这样每两个哈希就结婚生子,得到了一个”子哈希“。如果最底层的哈希总数是单数,那到最后必然出现一个单身哈希,这种情况就直接对它进行哈希运算,所以也能得到它的子哈希再往上推,依然是一样的方式,可以得到数目更少的新一级哈希;

  • 最终必然形成一棵倒挂的树,到了树根的这个位置,这一代就剩下一个根哈希了,我们把它叫做 Merkle Root。


对于这种数据结构,在实际应用中会有哪些应用场景了。


举个例子,我们知道现在从网上下载文件,很多都是 P2P 下载,文件会切分成很多小的数据块,每个数据块从不同的来源上下载,这些机器可以认为是不稳定或不可信的,文件下载完之后我们需要校验文件的完整性,这时我们总不能把文件再次切分然后分别计算它的 Hash 和下载前的 Hash 做对比吧,这时就需要用到 Merkle Tree。


在下载前,先从可靠的源获得文件的 Merkle Tree 树根。下载后,在合并文件之前先对比小文件的Hash是否一样,如果一样就认为是可靠的,如果不一样,就判定文件被损坏,从新的来源重新下载。


文件合并之后,计算小数据块的 Hash 并最终计算根 Hash,也成为 Merkle Root,然后对比根 Hash 是否一致。这样就避免了对整个文件进行 Hash 计算,因为当文件太大时,这种计算是很耗时。



Patricia树


Patricia 树,或称 Patricia trie,或 crit bit tree,压缩前缀树,是一种更节省空间的 Trie。对于基数树的每个节点,如果该节点是唯一的儿子的话,就和父节点合并。




MPT (Merkle Patricia Tree)

上面我们介绍了Merkle Tree和Patricia Tree,而MPT(Merkle Patricia Tree),顾名思义就是这两者的结合。MTP树种的节点包含空节点、叶子节点、扩展节点和分支节点。


Nibble:它是 key 的基本单元,是一个四元组(四个bit位的组合例如二进制表达的 0010 就是一个四元组)


**空节点****:简单的表示空,在代码中是一个空串。


叶子节点 (leaf):只有两个元素,分别为key和value,表示为[key,value]的一个键值对,其中key是key的一种特殊十六进制编码,value是value的RLP编码。


扩展节点 (extension):也是 [key,value] 的一个键值对,但是这里的value是其他节点的hash值,这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。


分支节点 (branch):分支节点有17个元素,回到 Nibble,四元组是 key 的基本单元,四元组最多有16个值。所以前16个必将落入到在其遍历中的键的十六个可能的半字节值中的每一个。第17个是存储那些在当前结点结束了的节点(例如, 有三个 key,分别是 (abc ,abd, ab) 第17个字段储存了ab节点的值)


这里还有一些知识点需要了解的,为了将 MPT 树存储到数据库中,同时还可以把MPT树从数据库中恢复出来,对于 Extension 和 Leaf 的节点类型做了特殊的定义:如果是一个扩展节点,那么前缀为0,这个0加在 key 前面。如果是一个叶子节点,那么前缀就是1


同时对 key 的长度就奇偶类型也做了设定,如果是奇数长度则标示1,如果是偶数长度则标示0。


以太坊的每一个区块头,并非只包含一棵 MPT 树,而是包含了三棵 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树种还有一个重要的概念:特殊的十六进制前缀(hex-prefix, HP)编码来对key编码,我们先来了解一下编码定义规则:


  • RAW 原始编码,对输入不做任何变更

  • HEX 十六进制编码:a)RAW编码输入的每个字符分解为高4位和低4位。比如key=>"bob",b的ASCII十六进制编码为0x62,o的ASCII十六进制编码为0x6f,分解成高四位和第四位,16表示终结 0x10,最终编码结果为[6 2 6 15 6 2 16];b)如果是叶子节点,则在最后加上Hex值0x10表示结束;c)如果是分支节点不附加任何Hex值。


HEX-Prefix 十六进制前缀编码

  • 输入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]


官方有一个详细的结构的示例:



怎么样,看了这篇文章,对MPT和树状结构有基本的了解了吗?未来,营长将奉上更多优质的技术普及文章,敬请期待!


 

限时免费报名 | 区块链技术公开课精选

5.22晚8点,大咖与你畅聊区块链扩展技术!

如何打造未来“黑科技”?

多方位+深度详解


推荐阅读:

  • 确实, 5G与物联网离不开区块链!

  • 焦虑的 BAT、不安的编程语言,揭秘程序员技术圈生存现状!

  • 深扒! 币安被盗的7074.18枚比特币去哪了?

  • 比 Java 更具争议的 PHP,处处留坑?

  • “我月入 3 万,每天都只想跳槽”

  • 一文回顾AI绘画的成长之路:从简笔画到真实人脸生成

  • 漫画:图的 “多源” 最短路径

  • 如何使用「番茄法」高效的写算法题?


猛戳"阅读原文"有惊喜哟


老铁在看了吗?👇

上一篇:20k~75k | 区块链回温,热门岗位不断扩招,看看哪些适合你?

下一篇:9年前他用1万个比特币买了两个披萨, 9年后他把当年的代码卖给了苹果, 成为了GPU挖矿之父

分享到:

相关文章