【深度知识】以太坊区块数据结构及以太坊的4棵数

1. 摘要

本文介绍以太坊区块链的一些基本知识，包括：

• 区块数据结构
• 数据结构基础
• 以太坊的4棵树
• 状态树
• 交易树
• 收据树
• 账户存储树

2. 区块数据结构

以太坊的区块是由区块头、交易列表和叔区块三部分组成。其中区块头包含块区号、块哈希、父块哈希等信息，其中State Root、Transaction Root、Receipt Root分别代表了状态树、交易树和交易树的哈希。除了创世块外，每个块都有父块，用Parent Hash连成一条区块链。如下图：

3. 数据结构基础

1、Merkle 树 Merkle Tree，也叫做哈希树，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块的hash值。非叶节点是其对应子节点串联字符串的hash。是一个把任意长度的数据通过哈希函数映射成固定长度数据，这个数据就叫hash值，将这些hash值放到一个List里面，就叫做Hash List。Merkle Tree可以看做Hash List的泛化。 1）Merkle Tree的原理 把数据分成小的数据块，每个数据块有相应地哈希，把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，得到了一个”子哈希“。如果哈希总数是单数，那么直接取最后一个哈希作为下个子哈希。这样就可以得到数目更少的新一级哈希。然后按照这种方式逐渐计算上去，最终必然形成一棵倒挂的树，到了树根的这个位置，就剩下一个根哈希了，我们把它叫做 Merkle Root。过程如下图：

2）Merkel树的意义 在p2p网络，下载之前，先从可信的源获得文件的Merkle Tree树根。一旦获得了树根，就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的Merkle Tree。如果Merkle Tree是损坏的或者虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的Merkle Tree。

2、Trie 树 Trie树，又称前缀树或字典树。利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。如图5

基本性质： 1）根节点不包含字符，除根节点外的每一个子节点都包含一个字符 2）从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串 3）每个节点的所有子节点包含的字符都不相同 注：键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示trie的原理

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

4，以太坊的树

以太坊区块数据有三棵树，分别为状态树，交易树和收据树。整个以太坊系统中只有一棵状态树，记录整个以太坊系统的所有账户状态。每个区块保存着一棵交易树，记录该区块的交易情况，一棵收据树用来记录该区块的交易收据。 状态树采用Merkel-Patrica(MPT)树，而交易树和状态树采用Merkel树。 对于交易树和收据树来说，一旦树已经建立，花多少时间来编辑这棵树并不重要，因为树一旦建立了，它就会永远存在并且不会改变。所以交易树和收据树采用Merkel树。 对于状态树，每个节点基本上包含了一个键值映射，其中的键是地址，而值包括账户的声明、余额、随机数nounce、代码以及每一个账户的存储。不同于交易历史记录，状态树需要经常地进行更新：账户余额和账户的随机数nonce经常会更变，更重要的是，新的账户会频繁地插入，存储的键也会经常被插入以及删除。我们需要这样的数据结构，它能在一次插入、更新、删除操作后快速计算到树根，而不需要重新计算整个树的Hash。Patricia树具有Trie树快速查找特点，并且比Trie树更加节省空间，所以以太坊中，对Merkel树改造成Merkel-Patrica(MPT)树。

账户存储树是保存与账户相关联数据的结构。该项只有合约账户才有，而在 EOA 中， storageRoot 留空、 codeHash 则是一串空字符串的哈希值。 （1）状态树

状态树中有四种节点，分别是空节点、叶子节点、扩展节点和分支节点。 空节点 ，简单的表示空，在代码中是一个空串。 叶子节点（leaf） ，表示为[key,value]的一个键值对，其中key是key的一种特殊十六进制编码，value是value的RLP编码。 扩展节点（extension） ，也是[key，value]的一个键值对，但是这里的value是其他节点的hash值，这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。 分支节点（branch） ，因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。

假如有四个账户，账户1地址0x811344，余额1ETH；账户2地址0x879337，余额2ETH；账户3地址0x8fd365，余额3ETH；账户4地址0x879397,余额4ETH，存储如下：

从图中可以看出，状态树的存储涉及3种编码方式： KeyBytes编码 Hex编码 Compact编码

在完成Compact编码后，会通过折叠操作把子结点替换成子结点的hash值，然后以键值对的形式将所有结点存储到LevelDBA数据库中。下面详细介绍上面3中编码方式。

KeyBytes编码 即原始关键字，比如图中的0x811344、0x879337等。每个字节中包含2个nibble（半字节，4 bits），每个nibble的数值范围时0x0~0xF。

Hex编码 由于我们需要以nibble为单位进行编码并插入MPT，因此需要把一个字节拆分成两个，转换为Hex编码。

Compact编码 当我们需要把内存中MPT存储到数据库中时，还需要再把两个字节合并为一个字节进行存储，这时候会碰到2个问题： 关键字长度为奇数，有一个字节无法合并 需要区分结点是扩展结点还是叶子结点

为了解决这个问题，以太坊设计了一种Compact编码方式，具体规则如下： 扩展结点，关键字长度为偶数，前面加00前缀 扩展结点，关键字长度为奇数，前面加1前缀（前缀和第1个字节合并为一个字节） 叶子结点，关键字长度为偶数，前面加20前缀（因为是Big Endian） 叶子结点，关键字长度为奇数，前面加3前缀（前缀和第1个字节合并为一个字节）

StateDB的存储 StateDB中存储了很多stateObject，而每一个stateObject则代表了一个以太坊账户，包含了账户的地址、余额、nonce、合约代码hash等状态信息。所有账户的当前状态在以太坊中被称为“世界状态”，在每次挖出或者接收到新区块时需要更新世界状态。 为了能够快速检索和更新账户状态，StateDB采用了两级缓存机制，参见下图：

第一级缓存以map的形式存储stateObject 第二级缓存以MPT的形式存储 第三级就是LevelDB上的持久化存储 当上一级缓存中没有所需的数据时，会从下一级缓存或者数据库中进行加载。

（2）交易树 从下图中可以看出，MPT是以交易在区块中的索引的RLP编码作为key，存储交易数据的RLP编码。事实上交易在LeveDB中并不是单独存储的，而是存储在区块的Body中。在往LeveDB中存储不同类型的键值对时，会在关键字中添加不同的前缀予以区分。 因此，以b + block index + block hash作为关键字就可以唯一确定某个区块的Body所在的位置。另外，为了能够快速查询某笔交易的数据，在数据库中还存储了每笔交易的索引信息，称为TxLookupEntry。TxLookupEntry中包含了block index和block hash用于定位区块Body，同时还包含了该笔交易在区块Body中的索引位置。

（3）收据树 交易回执的存储和交易类似，区别是交易回执是单独存储到LevelDB中的，以r为前缀。另外，由于交易回执和交易是一一对应的，因此也可以通过TxLookupEntry快速定位交易回执所在的位置，加速交易回执的查找。

（3）账户存储树 以太坊中有两种账户类型：外部所有账户（Externally Owned Accounts 简称 EOA）以及合约账户。我们用来互相收发以太币、部署智能合约的账户就是 EOA 账户，而部署智能合约时自动生成的账户则是合约账户。每一个智能合约都有其独一无二的以太坊账户。

账户状态反映了一个以太坊账户的各项信息。例如，它存储了当前账户以太币的余额信息、当前账户发送过的交易数量...每一个账户都有账户状态。

下面就来看看账户状态中都包括什么： nonce 从此地址发送出去的交易数量（如果当前为 EOA 账户）或者此账号产生的合约创建操作（现在先别管合约创建操作是什么）。 balance 此账号所拥有的以太币数量（以 Wei 计量）。 storageRoot 账户存储树的根节点哈希值（稍后介绍账户存储是什么）。 codeHash 对于合约账户，就是此账户存储 EVM 代码的哈希值。对于 EOA 账户，此处留空。

账户状态中不容忽视的一个细节是，上述对象在内的所有对象都可变（除了 codeHash）。举例来说，当一个账户向其他账户发送以太币时，除了 nonce 会增加，账户的余额也会相应改变。

而 codeHash 的不可变性使得，如果部署了有漏洞的智能合约，也无法修复更新此合约。对应的，只能部署一个新合约（而有漏洞的版本会一直存在于区块链上）。这也是为什么使用 Truffle 进行智能合约的开发和部署十分必要，并且用 Solidity 编程时要遵循 最佳实践 的要求。

账户存储树是保存与账户相关联数据的结构。该项只有合约账户才有，而在 EOA 中， storageRoot 留空、 codeHash 则是一串空字符串的哈希值。所有智能合约的数据都以 32 字节映射的形式保存在账户存储树中。此处不再赘述账户状态树如何维持合约数据。账户状态中的 storageRoot 区域负责维持账户存储树根节点哈希值。

存储树，账户状态，世界状态的构成关系

根据以太坊黄皮书，账户若是一个智能合约账户，则必定包含了 存储树 （storageRoot）和 代码存储 （codeHash）。

若我们继续放大观察存储树，即为上图最左边的树。存储树保存了智能合约的变量数据，它维持着256位的变量数据索引与RLP 算法编码过的256位数据本身。

为保证数据完整性，这些数据 也被组织成一棵 MPT 树的形式 。该MPT树的根节点哈希值称为 存储树 。 存储树 是账户状态的一个 域 ，该值随着合约的存储区的增加、删除、改动而不断变更。 代码存储 是只读的，它是合约账户的所执行的代码，它在合约第一次创建完毕后就不可以再变更。

5，总结

总结一下，以太坊有四种前缀树： （1）状态树包括了从地址到账户状态之间的映射。状态树的根节点哈希值由区块保存（在 stateRoot 字段），它标示了区块创建时的当前状态。整个网络中只有一个状态树。 状态标识了以太坊这台分布式计算机的硬盘。它是从地址到账户状态的映射。 （2）交易树包含了一个区块中的所有交易信息。由区块头（在 transactionsRoot 区域）保存交易树的根节点哈希值。每个区块都有一棵交易树。 交易标示了系统中的状态转移。它可以是资金的转移、消息调用或是合约的部署。 （3）交易收据树包含了一个区块中所有交易的收据信息。同样由区块头（在 receiptsRoot 区域）保存交易收据树的根节点哈希值；每个区块都有对应的交易收据树。 （4）账户存储树保存了与某一智能合约相关的数据信息。由账户状态保存账户存储树的根节点哈希值（在 storageRoot 字段）。每个账户都有一个账户存储树。 账户状态保存着每个以太坊账户的状态信息。账户状态同样保存着账户状态树的 storageRoot，后者包含了该账户的存储数据。

用一张图总结而言：