以太坊数据结构

区块数据结构

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

3. 数据结构基础

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

基本性质： 1）根节点不包含字符，除根节点外的每一个子节点都包含一个字符

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

以太坊的树

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

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

状态树的存储涉及3种编码方式。在完成Compact编码后，会通过折叠操作把子结点替换成子结点的hash值，然后以键值对的形式将所有结点存储到LevelDBA数据库中。

• 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 账户，而部署智能合约时自动生成的账户则是合约账户。每一个智能合约都有其独一无二的以太坊账户。

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

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

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

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

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

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

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

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

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

总结

以太坊有4种前缀树：

• 状态树: 包括了从地址到账户状态之间的映射。状态树的根节点哈希值由区块保存（在 stateRoot 字段），它标示了区块创建时的当前状态。整个网络中只有一个状态树。 状态标识了以太坊这台分布式计算机的硬盘。它是从地址到账户状态的映射。

• 收据树: 包含了一个区块中所有交易的收据信息。同样由区块头（在 receiptsRoot 区域）保存交易收据树的根节点哈希值；每个区块都有对应的交易收据树。

用一张图总结而言：