【深入知识】以太坊区块数据结构及以太坊的4个树数

一、总结

本文介绍以太坊区块链的一些基础知识，包括： 区块数据结构 数据结构基础 以太坊的4棵树 状态树 交易树 收据树 账户存储树

2. 块数据结构

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

3. 数据结构基础

1.默克尔树默克尔树，也叫哈希树，顾名思义，就是一种存储哈希值的树。 Merkle树的叶子是数据块的哈希值。 非叶节点是其相应子节点的串联字符串的散列。 它是一种通过哈希函数将任意长度的数据映射为固定长度数据的方法。 该数据称为散列值。 把这些散列值放到一个List中，就叫做Hash List。 Merkle Tree 可以看作是 Hash List 的推广。 1）Merkle Tree的原理是把数据分成小的数据块，每个数据块都有一个对应的hash，将相邻的两个hash合并成一个字符串，然后计算这个字符串的hash，得到一个“subhash”。 如果哈希总数为单数，则直接将最后一个哈希作为下一个子哈希。 这导致更少的新哈希级别。 然后就这样逐渐计算，最终一定会形成一棵倒挂的树。 在树根的这个位置，只剩下一个根哈希，我们称之为 Merkle Root。 过程如下：

2）默克尔树的意义 在p2p网络中，下载前，从可信来源获取文件的默克尔树根。 一旦获得根，就可以从其他不受信任的来源获得 Merkle 树。 根据可信根检查收到的默克尔树。 如果 Merkle Tree 损坏或伪造，则从其他来源获得另一棵 Merkle Tree，直到获得与可信树根匹配的 Merkle Tree。

2. Trie树 Trie树，又称前缀树或字典树。 使用字符串的公共前缀减少查询时间，尽量减少不必要的字符串比较，查询效率高于哈希树。 典型应用用于对大量字符串（不限于字符串）进行统计、排序和保存，常被搜索引擎系统用于文本词频统计。 图 5

基本属性： 1）根节点不包含字符，除根节点外的每个子节点都包含一个字符 2）从根节点到某个节点。 路径上传递的字符被拼接起来，就是该节点对应的字符串 3）每个节点的所有子节点包含不同的字符 注意：节点中不需要显式存储key，完整的单词在插图，只是为了演示trie的原理

3. Patricia树Patricia树，即Patricia trie，是一种压缩前缀树，是一种比较节省空间的Trie。 对于基数树的每个节点，如果该节点是唯一的子节点，则将其与父节点合并。

4. 以太坊之树

以太坊区块数据中一共有三棵树，分别是状态树、交易树和收据树。 整个以太坊系统只有一棵状态树，它记录了整个以太坊系统所有账户的状态。 每个区块保存一棵交易树，记录该区块的交易，一棵回执树用于记录该区块的交易回执。 状态树使用默克尔-帕特里卡（MPT）树，而交易树和状态树使用默克尔树。 对于交易树和收据树以太坊账户停付，树一旦建好，花多少时间编辑树就无所谓了，因为树一旦建好，就永远存在，不会改变。 所以交易树和收据树使用默克尔树。 对于状态树，每个节点基本上包含一个键值映射，其中键是地址，值包括每个账户的账户的声明、余额、随机数、代码和存储。 与交易历史不同，状态树需要经常更新：账户余额和账户随机数经常变化，更重要的是，新账户经常被插入，存储的密钥经常被插入和删除。 我们需要这样一种数据结构，它可以在一次插入、更新、删除操作后快速计算到树的根节点，而不用重新计算整棵树的Hash。 Patricia 树具有 Trie 树的快速查找特性，并且比 Trie 树更节省空间，因此在以太坊中，Merkel 树被转化为 Merkel-Patrica (MPT) 树。

帐户存储树是一种保存与帐户关联的数据的结构。 此项仅适用于合约账户，而在EOA中，storageRoot留空，codeHash为一串空字符串的hash值。 (1) 状态树

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

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

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

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

KeyBytes编码就是原始key，比如图中的0x811344、0x879337。 每个字节包含2个半字节（nibble，4位），每个半字节的取值范围为0x0~0xF。

Hex编码 由于我们需要以半字节为单位对MPT进行编码和插入，所以我们需要将一个字节拆分为两个，并转换为Hex编码。

Compact encoding 当我们需要将内存中的MPT存入数据库时​​，需要将两个字节合并为一个字节进行存储。 这时候我们会遇到两个问题：关键字长度为奇数，有一个字节无法合并，需要区分节点是展开节点还是叶子节点

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

StateDB存储 StateDB存储了很多stateObject，每个stateObject代表一个以太坊账户，包括账户地址、余额、nonce、合约代码hash等状态信息。 所有账户当前的状态在以太坊中称为“世界状态”，每次挖出或接收到新区块时都需要更新世界状态。 为了快速获取和更新账户状态，StateDB采用了二级缓存机制，如下图所示：

一级缓存以map的形式存储stateObject。 二级缓存以MPT的形式存储stateObject。 第三层是 LevelDB 上的持久化存储。 载入。

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

(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为一串空字符串的hash值。 所有智能合约数据以 32 字节映射的形式存储在账户存储树中。 账户状态树如何维护合约数据这里不再赘述。 账户状态中的storageRoot区域负责维护账户存储树根节点的哈希值。

存储树、账户状态、世界状态的组成关系

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

如果我们继续放大观察存储树，就是上图中最左边的树。 存储树保存了智能合约的可变数据，它维护着256位的可变​​数据索引和经过RLP算法编码的256位数据本身。

为了保证数据的完整性，这些数据也被组织成一棵 MPT 树。 MPT树根节点的哈希值称为存储树。 存储树是账户状态的一个域，值随着合约存储区的增删改查而不断变化。 代码存储为只读，为合约账户执行代码，首次创建合约后不可更改。

5.总结

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

用一张图来概括：