以太坊的数据结构（状态树、交易树、收据树）及代码分析

一、状态树

以太坊是基于账户的账本，因此需要进行账户地址和账户状态的映射，如下所示：

我们尝试寻找一种合适的数据结构来完成这个需求：

1. 如果以哈希表的形式保存状态数据，可以非常有效率地查找、更新账户状态数据，但是由于状态数据只保存在区块体中，轻节点难以进行Merkle Proof，那么接下来考虑构建Merkle tree；
2. 如果将账户数据简单组织成Merkle tree，不进行排序，就需要发布所有账户到区块中，保证根哈希一致，但是数量级太大，不可行；如果只发布状态变化的账户，就会导致所有节点的根哈希不一致，无法共识；
3. 如果使用排序的Merkle tree，各个节点的根哈希就会相同，但是增加账户时，需要重构Merkle tree，代价太大。另外Merkle tree不能够快速查找、更新状态数据。以太坊中使用的是一种新的数据结构Merkle Patricia trie。

1.1 trie

trie是一种字典前缀树，信息检索较为方便。如果有General、Genesis、Go、God、Good这几个单词，组成trie如下所示：

1. 每个节点的分支取决于元素范围，上面例子中为26个英文字母和结束标志，最多27个分叉。在以太坊中使用16进制（0~F）表示账户，加上结束标志，最多17个分支；
2. 查找效率取决于key值长度，键值越长，查找访问次数越多。以太坊中账户为40位16进制数，因此查找长度固定是40；
3. 不会出现碰撞，哈希表则有碰撞的问题；
4. 给定一组输入，构成的trie一致；
5. 更新数据非常容易，只需访问局部分支。

1.2 Patricia tree(trie)

Patricia tree称为路径压缩前缀树，可以节省存储空间，同时还可以降低了查找访问次数，提高查找效率。例如将上例中的trie改进为Patricia tree，如下图所示：

Patricia tree适合键值分布比较稀疏的数据，压缩效果比较明显，如下图所示：

在以太坊中，为防止碰撞，使用了160bit长的账户，非常稀疏，因此适合使用Patricia tree数据结构。

1.3 Merkle Patricia tree(trie)

将Patricia tree的指针全部换成哈希指针，就构建成了Merkle Patricia tree，可以计算出根哈希值，保存在区块头中。

1. 通过根哈希保证树不被篡改，每个账户的状态都是不可篡改的；
2. 通过Merkle proof，可以用来证明任意一个账户的状态，比如账户余额；
3. 通过Merkle proof，可以证明某个账户不存在。

1.4 Modified Merkle Patricia tree(trie)

以太坊使用的是修改版的Merkle Patricia tree，与Merkle Patricia tree没有本质区别。例如下图中有4个7位的地址，保存账户余额信息（value），树中有3种节点，每个节点存储关联节点的哈希值：

1. Extension Node：扩展节点，保存路径压缩压缩数据，即shared nibbles中保存的16进制数据；
2. Branch Node：分支节点，无法压缩；
3. Leaf Node：叶子节点，保存账户状态数据；
   

新发布一个区块的时候，某些账户的状态会发生变化，新区快中会为变化的账户重新建立分支，大部分不变的数据则指向历史区块中的分支，因此区块间会共享大部分不变的状态分支。如下图所示：

保留历史状态的好处：
未胜出的临时性分叉需要回滚才能继续出块，由于智能合约的执行不易反推执行，保留起始与结束的记录，回滚才比较方便。

账户树中保存全部账户信息的原因：
查找某个账户更快速，如果区块内只保存区块内交易的相关账户信息，查询某个很久没有交易的账户就要花费很长时间，最坏的情况是如果转账给一个从未进行交易的账户，就必须追溯到创世区块，最后有可能发现区块内没有该账户的信息。

1.5 账户状态值存储

账户状态数据经过RLP（Recursive Length Prefix）序列化后存储，RLP序列化方式相比protobuf较为简单，只支持字符嵌套数组（nested array of bytes），实现起来比较容易。

二、交易树、收据树

2.1 概述

区块内的交易列表组成交易树，与比特币的Merkle tree作用类似。

每个交易执行完会有一个收据，记录这个交易的相关信息，与交易树上的节点一一对应。以太坊中以太坊的智能合约执行过程比较复杂，增加收据树，有助于快速查询一些交易执行结果。

2.2 Modified Merkle Patricia tree(trie)

交易树与收据树同样采用的是MPT数据结构，这样三棵树的代码更加统一，便于管理。同时MPT具有良好的数据查询性能。

与状态树不同的是，交易树和收据树都只把当前区块发布的交易包含进来，独立于其他区块，没有共享分支。

MPT的作用：
MPT可以给轻节点提供Merkle proof，交易树可以证明某个交易确实属于某个区块，收据树同样可以证明某个交易结果。

2.3 布隆过滤器（bloom filter）

布隆过滤器给包含很多元素的集合计算出一个很紧凑的摘要，用较少的空间来表示较大集合的存在关系，可以高效地查找某个元素是否在一个大的集合里。

对于给定输入集合，用Hash函数给集合中元素分别计算出地址，分别在位串的这些地址上标记为1。在查找时，进行同样的计算过程，并查看位串上的元素，如果是 1，则说明较大概率是存在该输入。如下图所示：

通常用多个哈希函数来防止哈希碰撞，可以降低误判率，仍存在着误报（FalsePositive）的情况，但绝对不会漏报（False Negative）。

布隆过滤器的作用：
每个交易执行完会形成一个收据，收据里面包含bloom filter，记录交易类型、地址等信息，发布的区块头里面会有一个总的bloom filter，是区块内所有交易的bloom filter的并集，根据区块头里的bloom filter，即使是轻节点就可以过滤掉大部分区块，然后向全节点请求候选区块体数据，查询区块内每个交易的bloom filter，得知哪些区块有想要的交易，当然也有可能某些区块是误报，里面没有想要的交易。

如上所述，交易树通过布隆过滤器可以进行更加复杂的查询，比如查询过去10天跟某个智能合约所有有关的交易，或者查询过去10天内某种类型（众筹、发行新币等）的事件。

2.4 总结：交易驱动的状态机

以太坊是一个交易驱动的状态机（transaction-driven state machine），状态指的是所有账户的状态，即状态树包含的内容，交易指的是区块内包含的那些交易，通过执行这些交易会驱动系统从当前状态转移到下一个状态，且状态的转移具有确定性。

比特币同样可以认为是一个交易驱动的状态机，比特币的状态是UTXO，每次发布的区块内的交易会驱动状态机从当前状态确定地转移到下一个状态。

三、区块及数据结构代码分析

3.1 区块信息结构体

区块头的结构定义如下所示：
ParentHash表示父区块的哈希，UncleHash是叔父区块哈希，Coinbase是示矿工账户地址，Root是状态树的根哈希，TxHash是交易树的根哈希，ReceiptHash是收据树的根哈希，Bloom是块头的bloom filter，Difficulty是挖矿难度（可根据需要调整），GasLimit和GasUsed与汽油费相关，Time是区块大致产生时间，MixDigest与挖矿过程相关，从Nonce经过一些列计算而来，Nonce是挖矿的谜底随机数。

// Header represents a block header in the Ethereum blockchain.
type Header struct {
   
    ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
    UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
    Coinbase    common.Address `json:"miner"            gencodec:"required"`
    Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
    TxHash      common.Hash    `json:"transac
1
2
3
4
5
6
7