1.数据结构及算法

1.1 SHA-3

以太坊中用到的hash算法,或者叫Keccak256。

1.2 RLP编码

RLP(Recursive Length Prefix,递归的长度前缀),以太坊中用到的编码格式,用来序列化和反序列化数据。如将对象进行RLP编码后保存在levelDB数据库中,再从数据库中取出后解码为对应的对象等。

1.3 MPT

一种压缩前缀树,结构如下图所示:

图中有几种节点:

Extension Node:包含了该节点的路径shared nibbles,以及下一个节点的指针next node

Branch Node:包含了一个长度为17的数组,前面16个分别表示从0到f这16进制下挂载的节点位置,最后一位表示当前节点数据。

Left Node:叶子节点,包含了key路径和value数据。

按图中数据打比方说,当有如下几个key-value需要组织成mpt树时:

存储这4组数据的4个叶子节点会有个共同的Root节点,Root节点中会有个共同的key前缀a7。

从Root往下会分出一个Branch Node,在该Branch Node的第2个位置上(代表key1)挂载着key-end为1355,value为45.0ETH的叶子节点。该叶子节点的完整key为:Root中的key(a7)+Branch Node中第二个位置代表的key(1)+该叶子节点的key-end(1355)=a711355。同理a7f9365这个叶子节点也是如此。

然后是a77d337和a77d397这两个节点。由于这两个节点有更长的共同前缀a77d3,所有从【2】中的Branch Node的第8个位置上(代表key7)再挂载一个key为d3的Extension Node,然后该Extension Node再接上一个Branch Node用于挂载叶子节点。

将a77d337和a77d397分别挂载在【3】中的第4位(代表key3)和第10位(代表key9),他们的key-end都为7 (1)Root中的key(a7)+Branch Node中第二个位置代表的key(7)+【3】中Extension Node的key(d3)+挂载的第4位(3)+自己的key-end(7)=a77d337 (2)Root中的key(a7)+Branch Node中第二个位置代表的key(7)+【3】中Extension Node的key(d3)+挂载的第10位(9)+自己的key-end(7)=a77d397

在以太坊的实际应用中,当用MPT树管理所有的账户信息时,真正的key为账户的地址,账户地址为20byte,value为该账户信息的rlp编码内容。

以上说的是MPT树的节点组织形式,另外各个节点上还有一个非常重要的属性就是节点的hash。节点的hash值计算方式可以用下图表:

叶子节点的hash值为叶子节点对应数据的hash,其父节点的hash为所有叶子节点的hash相加再取hash值。一直到最上层的root节点会有个。这样的话只要某个叶子节点中的数据有所变化,从根节点到该叶子节点的路径上所有节点的hash值都会改变。当矿工挖出一个block,其中打包了一些交易对账户产生影响时对应的MPT树变化如下:

上图表示每个Block的Header中有一个State Root(其他字段后面会具体说明,暂时忽略他们)表示该区块高度时状态树的root hash,状态树是一颗用来管理以太坊中所有账户的MPT树,而每个账户中又有一个Storage root,通过该Storage root能找到保存在账户下的存储信息。

上图的含义是:

当一个用户账户下存储内容有所改变,其对应的Storage root会有所改变,对应的该账户节点的hash也会发生变动。

一个叶子节点的hash变动后,会重新计算其父节点的hash值,最终会得到一个新的root hash。

产生的新的root hash会被挂载到新的block上。

虽然用户账户的地址是固定的,但是由于不同的block中的State Root不一样,所以根据相同的账户地址,会查找到不同时期的账户信息。BlockN通过他的State Root查找到的是高度为N时的账户信息,而BlockN+1通过他的State Root查找到的是高度为N+1时的账户信息。

MPT树的节点信息都会保存在以太坊底层的数据库中。

1.4 存储

MPT树是以太坊中组织数据用到的一种数据结构,而在以太坊底层使用的LevelDB作为数据库来存储用到的数据。存储方式是用key-value的键值对,部分key-value如下表:

该表中的key可以在中查看到。

在底层LevelDB中存储着很多账户信息,key为账户Account的地址address,value为Account的RLP编码。当需要把这些Account从LevelDB中读取出来后,会将这些Account信息组织成一个逻辑上的MPT树。

下一篇写以太坊的账户结构相关的内容。

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

扫码关注云+社区

领取腾讯云代金券