在以太坊中，有三棵树的说法，分别是状态树、收据树和交易树。了解了这三棵树，就弄清楚了以太坊的基础数据结构设计。

前一篇文章中有提过，以太坊采用基于账户的模式，系统中显式记录每个账户的余额。而以太坊这样一个大型分布式系统中，是采用的什么样的数据结构来实现对这些数据的管理的。

引入

首先账户信息应该是账户地址—-账户信息这样kye—-value键值对的形式存储的。在以太坊中，账户地址为160字节，表示为40个16进制数。状态包含了余额(balance)、交易次数(nonce),合约账户中还包含了code(代码)、存储(stroge)。

使用hash表存储

既然是K-V键值对，我们能不能用hash表来实现？

系统中的全节点维护一个hash表，每当系统中有新节点插入或者旧节点状态改变，直接修改hash表的值，如果不考虑hash碰撞，那么查询、插入、修改都是常数级别的时间复杂度。其他节点如果想知道某个账户的账户余额，为了保证全节点发布信息的不可篡改，需要将储存账户信息的hash表组成一个merkle tree，然后把根hash发布到区块中，轻节点要验证某个账户的余额，向全节点要一个Merkle proof即可。但是，以太坊中十几秒发布一个区块，每个区块都会有一些交易，这些交易一定会改变hash表的值，那么每个区块，全节点都要重新把hash表组合成一个Merkle tree，代价很大。并且实际上每个区块改变的是一小部分账户状态。

问题来了：比特币系统也是每个区块构建一个Merkle tree，但是他构建的Merkle tree其实是订单的Merkle tree，一个区块包含一些订单，发布完之后就不会更改了，每个区块都是一些新的订单，都会构建新的Merkle tree。并且每次构建的Merkle tree上限也就4000个订单，这里要构建Merkle tree需要构建的是所有账户的Merkle tree，这个代价是很大很大的。

Merkle tree除了提供Merkle proof证明账户有多少钱之外，还有一个很重要的作用：维护全节点的状态一致性。这也是比特币系统把根哈希写进块头的原因(当前区块包含那些交易，所有全节点保持一个共识)。

使用一个Merkle tree存储

首先，Merkle tree 没有提供一个高效的查找和更新的方法。使得查找和更新效率不高。其次我们有必要对Merkle tree进行一个排序，因为如果不排序，那么各个全节点按照自己的方式(比如接收到账户信息的先后状态)组织Merkle tree，那么不同全节点组织出来的merkle tree的根哈希值是不一样的。

那么这时候我们就会想，那为什么比特币系统中的Merkle tree不用排序，不同全节点的组织方式也是不一样的，因为比特币系统中的挖矿其实是把各个信息，包括要包含的交易组成的Merkle tree的根哈希值和nonce等一起求哈希找到符合target的nonce，而且只有找到了nonce的节点才有发布区块的权力，那些没有找到符合要求的nonce的节点的Merkle tree的组织形式是没有意义的，并且比特币系统并不要求证明某个订单不在Merkle tree中，所以没有必要排序，也没有上述问题。

那么使用Sorted Merkle tree可以么？新增账户，由于其地址随机，插入Merkle Tree时候很大可能在Tree中间，就必须要重新构建Merkle tree。所以Sorted Merkle Tree插入、删除(实际上可以不删除)的代价太大。

既然哈希表和 Merkle Tree都不可以，那么我们看一下实际中以太坊采取的数据结构：MPT。

trie(字典树、前缀树)

trie是从retrieval这个单词来的。如下为一个通过5个单词组成的trie数据结构

image-20230109174725004

特点：

  • trie中每个节点的分支数目取决于Key值中每个元素的取值范围(图例中最多26个英文字母分叉+一个结束标志位=27个)。
  • trie查找效率取决于key的长度。实际应用中以太坊是40个16进制数
  • 理论上哈希会出现碰撞，而trie上面不会发生碰撞。
  • 给定输入，无论如何顺序插入，构造的trie都是一样的。
  • 更新操作局部性较好。更新操作很简单

那么trie有缺点吗？当然有：trie的存储浪费。很多节点只存储一个key，但其“儿子”只有一个，过于浪费。因此，为了解决这一问题，我们引入Patricia tree/Patricia trie

Patricia trie(Patricia tree)

Patricia trie就是进行了路径压缩的trie。如上图例子，进行路径压缩后如下图所示：

image-20230109175203559

需要注意的是，如果新插入单词，原本压缩的路径可能需要扩展开来。

那么，需要考虑什么情况下路径压缩效果较好？树中插入的键值分布较为稀疏的情况下，路径压缩效果较好。

在以太坊系统中，160位的地址存在2^160 种，该数实际上已经非常大了，和账户数目相比，可以认为地址这一键值非常稀疏。

因此，我们可以在以太坊账户管理种使用Patricia tree这一数据结构！但实际上，在以太坊种使用的并非简单的PT(Patricia tree),而是MPT(Merkle Patricia tree)

MPT(Merkle Patricia tree)

区块链和链表的区别在于区块链使用普通指针，链表使用哈希指针。Merkle tree 和binary tree的区别也是普通指针换成了哈希指针。

MPT就是用哈希指针代替普通指针的Patricia tree,并把根哈希值存储在block header中

BTC系统中只有一个交易组成的Merkle Tree，而以太坊中有三个(三棵树)。
也就是说，在以太坊的block header中，存在有三个根哈希值。

根哈希值的用处：

  • 防止篡改。
  • 提供Merkle proof，可以证明账户余额，轻节点可以进行验证。
  • 证明某个发生了交易的账户是否存在
  • 能证明某个账户不存在

以太坊中针对MPT(Merkle Patricia tree)进行了修改，我们称其为Modified MPT

下图为以太坊中使用的MPT结构示意图。右上角表示四个账户(为直观，显示较少)和其状态(只显示账户余额)。（需要注意这里的指针都是哈希指针）

image-20230110155507888

每次发布新区块，状态树中部分节点状态会改变。但改变并非在原地修改，而是新建一些分支，保留原本状态。如下图中，仅仅有新发生改变的节点才需要修改，其他未修改节点直接指向前一个区块中的对应节点。

image-20230110155922339

如上图，整棵树只有一个合约账户的nonce和balance以及存储的一个叶子节点发生了变化，其余的都指向之前的值。

此外，合约账户的存储storage实际上也是key-value的组织形式，所以在ETH中，每个合约账户的storage其实也是一颗颗小的MPT。

所以，系统中全节点并非维护一棵MPT，而是每次发布新区块都要新建MPT。只不过大部分节点共享。

为什么要保存原本状态？为何不直接修改？

如下图，因为以太坊把出块时间调整至十几秒，所以临时性的分叉很常见，加入下图最终上面的分叉会胜出，那么下面的分叉就要涉及到一个回滚操作，把下面区块的状态回滚至分叉前的状态，所以需要维护这些历史状态。

image-20230110160418406

比特币为什么不用考虑回滚的问题？

比特币的交易类型比较简单，简单的交易可以通过订单本身反向操作推断出前一个状态。而以太坊中有智能合约，它是图灵完备的，编程能力很强，从理论上来说可以执行很复杂的操作。所以智能合约执行完成之后，想不通过历史状态推算出之前的状态是不可能的

以太坊中代码的数据结构

block header 中的数据结构

image-20230110162013603

区块结构

image-20230110184112609

区块在网上真正发布时的信息

image-20230110184139006

最后说明
状态树中保存Key-value对，key就是地址，而value状态通过RLP(Recursive Length Prefix，一种进行序列化的方法)编码序列号之后再进行存储。