概述
- 状态树
- 交易树和收据树
状态树
ETH 采用的是基于账户的模式，也就是说系统中显示记录着每个账户的当前状态信息。
每个账户都是由一个 160bit 的地址组成，外部账户中的状态包含余额（balance）、交易次数（nonce），合约账户包含 code(代码)、存储(stroge)。
对于一个出块时间只有十几秒的系统，如何高效地维护这些状态就成了十分重要的事情。
为何不使用 HashTable？
由于每个账户都是一个 160bit 的地址，所以很容易想到用 HashTable 来建立地址到账户状态的映射，在不考虑哈希碰撞的情况下，增删改查都是常数时间。国安民乐，岂不美哉？
那么为什么 ETH 没有使用 HashTable 呢？原因就是建立共识代价太大。
BTC 建立共识是通过将区块内的交易组织成一颗 Merkle Tree，并将根哈希值写入 Block Header，其它全节点验证时只需要重新计算区根哈希值即可，同时因为一个 Block 的大小有限制，所以达成共识的代价比较小。
ETH 如果使用 HashTable 管理账户状态的话，两个全节点要达成共识代价都很大，因为要遍历整个 HashTable 才可以。
为何不使用 Merkle Tree？
那么如果把账户的状态组织成一颗 Merkle Tree 怎么样呢？这样是不是就可以像 BTC 一样方便了？
看起来我们可以直接将根哈希值写入到 Block Header 里，以求向 BTC 一样达成共识。
Q：如果两个全节点记录的账户状态完全一致，它们的根哈希值一定相同么？
A：不一定，因为两个全节点听到各个账户的顺序可能不同，如果不对 Merkle Tree 进行排序的话，两个全节点构造出来的 Merkle Tree 的根哈希值很可能不同。如果不同，也就无法达成共识。
Q：如果使用排序的 Merkle Tree 是不是就没问题了？
A：如果监听到了一个新的账户，由于 Merkle Tree 时排序的，所以就要将其插入到合适的位置，那么就需要重新组织 Merkle Tree，代价过大，不能接受。
MPT（Merkle Patricia Trie）
最终 ETH 使用了 MPT 管理各个账户的状态，MPT 是 Merkle Tree 和 Patricia Trie 组合而成的数据结构。
Patricia Trie 就是经过路径压缩的 Trie。
Q：新增一个账户时的代价是否可以接受？
A：可以，因为 160bit 的账户地址很容易地就能添加到 Patricia Trie，且由于 Patricia Trie 的特点，对其更新都是局部的，不会导致整棵树的重组。
Q：更改一个账户状态时的代价是否可以接受？
A：可以，因为 Patricia Trie 的查找仅需对数时间，同时由于 Patricia Trie 的特点，其更改也是局部的，同样不会导致整棵树的重组。
Q：达成共识的代价是否可以接受？
A：Merkle Patricia Trie 中 将 Patricia Trie 中的传统的地址指针改成了哈希指针，且由于只要存储的地址完全一致，则无论存储顺序的先后，Patricia Trie 只有一种形态，所以可以算出 Merkle Patricia Trie 的根哈希值并写道 Block Header 中，达成共识十分简单。
每个区块都会保存完整的状态树，而不是仅和当前区块内交易有关的节点。因为这样可以便于回滚。也可以这么考虑：
- 账户 A 转账给 账户 B 一个币。
- 那么就应该先知道两个账户的余额。
- 如果每个区块只保存与当前区块有关联的账户的状态树节点。
- 且假设 B 是一个新的账户。
- 那么这个新账户肯定不会存在于状态树中。
- 由于每个区块没有保留完整的状态树，所以只能顺着区块链去找。
- 那么查询账户 B 的状态，最终会找到 Genesis Block，才会发现这是一个新账户。
- 代价太大，不能接受。
交易树和收据树
ETH 每次发布区块的时候其包含的交易会被组织成一颗交易树，每笔交易执行完后会产生一个收据，记录相关信息，最终也会被组织成收据树，这两棵树均为 MPT。
交易树和收据树也可以提供根哈希值。同时 ETH 也提供了比较复杂的查询操作，如查询 10 天内和某个智能合约有交易的账户等。为了降低这类查询操作的代价，ETH 使用了 Bloom Filter ，它可以让矿工在沿着区块链查找交易等信息时快速地排除不可能包含所需信息区块。