区块链-以太坊MPT存储

最近研究以太坊MPT的数据存储性能,仔细地确认了一下MPT树的数据存储方式。众所周知,以太坊中的世界状态是通过MPT树实现的。MPT树是在内存中的连接关系,为了持久化存储,MPT树的连接关系转化为一系列的K-V对。以太坊将这些K-V对存储在levelDB中。有关MPT树的基本知识,可以查看

以太源代码 - MPT原理以及实现

1)MPT树的内存结构

MPT树的内存结构,如下图。一颗MPT树由4种节点连接组成:fullnode是分支节点,shortnode代表扩展节点或者叶子节点(取决于value是hashNode还是valueNode)。

需要指出的是:MPT的叶子节点(账户信息)是按照账户的地址(Address)的字典排序形成。也就是说,MPT树上的一个叶子节点路径上的所有的key组成的是账户地址。

2)MPT树物理存储

在内存中,节点和节点的连接关系可以通过“指针”完成。为了将连接关系持久化,需要将节点内容生成对应的,唯一的“地址”。其他引用节点内容的节点,只需要记录引用节点的地址即可,示意如下图中的蓝色部分。

以太坊中,节点内容的地址就是节点内容的hash。比如一个由“key”以及一个“hashNode”组成的节点,节点内容是rlp(key,hashNode),对应的地址是内容的hash。在存储中,存储的是hash到rlp的KV对。其他引用节点的“连接”用hash值代替,从而隐性的实现“连接”。

再举fullnode的例子,在存储中,fullnode的内容是rlp(hashNode,hashNode ... hashNode, valueNode)组成。

3)账户修改

从上述可见,一个叶子节点的改变,导致节点内容的改变,节点的“地址”也会发生变化。也就是说,父亲节点和该节点的“连接”地址发生变化。因为父亲节点的内容包括“连接”地址,所以父亲节点的内容也发生变化,父亲节点的“地址”也随着变化。随即,父亲的父亲也发生变化,一直变化到MPT的树根。

总的来说,一个账户的改变,导致MPT树,从叶子到树根,整条路径上的所有节点的KV对都发生变化,需要更新到存储中。

以太坊中的节点间的“连接”关系用hash来代替,主要原因,hash结果唯一。还有个原因,有关账户中的Storage数据的MPT树。在Storage的数据构建的MPT树,节点排序是通过Storage数据内容的hash,这样保证MPT树的最大高度,避免攻击者通过构造Storage创建深度很高的MPT树。

MPT树中的分支节点的分支个数设置为16,而不是更大的原因,可能是怕分支节点内容变的太大,在节点内容大小和树高之间的一个平衡。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180829G1YTMR00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券