【深度知识】以太坊区块数据结构及以太坊的4棵数 | 深入浅出区块链技术博客

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

• 区块数据结构
• 数据结构基础
• 以太坊的 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 树的根节点哈希值称为 存储树 。
存储树 是账户状态的一个 域 ，该值随着合约的存储区的增加、删除、改动而不断变更。
代码存储 是只读的，它是合约账户的所执行的代码，它在合约第一次创建完毕后就不可以再变更。

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

用一张图总结而言：