以太坊区块数据结构

太过爱你忘了你带给我的痛 2023-01-22 09:53 773阅读 0赞

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

*  [EVM][]
 *  
 *  [账户存储][Link 1]
 *  
 *  [数据结构][Link 2]
 *  
 *  [底层逻辑][Link 3]

以太坊区块数据结构及以太坊的4棵数

## 1. 摘要 ##

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

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

## 2. 区块数据结构 ##

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

![0acc0dc812c324d7f48c03c0dbd9479d.png][]

## 3. 数据结构基础 ##

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

![bebb9f8bac1e02837156646feb949a50.png][]

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

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

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

![5ed73f37e1cf2ef275b70dbdb74f7543.png][]

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

![6efc94345657820b3b3040274143f0fd.png][]

## 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，存储如下：

![b16ba7550e4081bb0938384cbef02eb8.png][]

![287cc51cd2bd0593f855eacc17da86b8.png][]

![228794b374ead6815c8c2e037ad53979.png][]

![ac07de3de401f6e650bd2ea449cb0e0b.png][]

从图中可以看出，状态树的存储涉及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采用了两级缓存机制，参见下图：

![5993a76827d43b7f19fe15c2229b78d3.png][]

第一级缓存以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中的索引位置。

![5a33ec551baa345d831301f016180252.png][]

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

![00e88ed3563763b83efb0a4fb393c8c4.png][]

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

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

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

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

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

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

![a2e52a42bb0abed2ccf57010782e25f9.png][]

![f9c4a6230e2ac66f164b57ce03a6aff6.png][]

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

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

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

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

## 5，总结 ##

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

用一张图总结而言：

![2c4d5a6f42b69e510edaa6aa845b19ce.png][]

[EVM]: https://learnblockchain.cn/tags/EVM
[Link 1]: https://learnblockchain.cn/tags/%E8%B4%A6%E6%88%B7%E5%AD%98%E5%82%A8
[Link 2]: https://learnblockchain.cn/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84
[Link 3]: https://learnblockchain.cn/tags/%E5%BA%95%E5%B1%82%E9%80%BB%E8%BE%91
[0acc0dc812c324d7f48c03c0dbd9479d.png]: /images/20221020/e392334241994ee48c69eb92bbfee6cb.png
[bebb9f8bac1e02837156646feb949a50.png]: /images/20221020/dbd448228d9e40e6ad307938739d6199.png
[5ed73f37e1cf2ef275b70dbdb74f7543.png]: /images/20221020/a2bc1c14cce748cf9185aa22bfb01254.png
[6efc94345657820b3b3040274143f0fd.png]: /images/20221020/af4a6faba1ae40739371675dfee51dbf.png
[b16ba7550e4081bb0938384cbef02eb8.png]: /images/20221020/4093b9a6941e4ec08aaeee88033e0321.png
[287cc51cd2bd0593f855eacc17da86b8.png]: /images/20221020/b88d178999b24a389417ccc9c6342e0e.png
[228794b374ead6815c8c2e037ad53979.png]: /images/20221020/f023e8d8ac6b4a7d82cf765d539739d2.png
[ac07de3de401f6e650bd2ea449cb0e0b.png]: /images/20221020/9a8ce73e9d484e05b1ae7ae9db6666f2.png
[5993a76827d43b7f19fe15c2229b78d3.png]: /images/20221020/0d7a2e98bb4f4af393c86c383398ecfc.png
[5a33ec551baa345d831301f016180252.png]: /images/20221020/b67745dc0b704e3ca15c0bdf1baa13c4.png
[00e88ed3563763b83efb0a4fb393c8c4.png]: /images/20221020/71ac7e48fe5b4014ba851c488a15dafc.png
[a2e52a42bb0abed2ccf57010782e25f9.png]: /images/20221020/9be6b7708d4f45caa423136761ae2f6e.png
[f9c4a6230e2ac66f164b57ce03a6aff6.png]: /images/20221020/810401a68b4245aeb2218274944a5a65.png
[2c4d5a6f42b69e510edaa6aa845b19ce.png]: /images/20221020/17fe8ed7c35c470099ca943ed889cb29.png