ETH
以太坊中的状态是什么？
以太坊是基于账户的系统，所以以太坊中的状态是由账户信息去表示的。那每个工作节点使用怎样的数据结构去维护这些账户信息的呢？要知道以太坊网络中的账户数量是极其庞大的，什么样的数据结构可以让我们能够轻易的在其中去进行新增账户，查找账户以及如何进行零知识证明呢？以太坊提出了一种数据结构叫做Merkel Patricia Tree。首先先不去详细的讲MPT是怎样的结构，让我们按照需要解决的问题去慢慢的讨论。
状态存储数据结构需要解决的问题
为什么不能用Merkel Tree
每一次状态的改变都会涉及产生新的Merkel Tree。比特币中为每个区块里的交易构建Merkel Tree，因为交易的数量有限，所以每次重新构建没有问题。但是以太坊当中的账户数量十分庞大，要每次都为他重新构建一棵新的Merkel Tree太浪费时间和资源了
那为什么不维护一个全局的Merkel Tree，哪里发生了改动就修改哪里？
Merkel Tree只能证明“交易存在于区块中而不能证明“交易不存在于区块中”，也就是只能证明membership而不能证明non-membership。而且如果是全局的话，那就说明每个节点自己再根据交易列表来维护自己的Merkel Tree，但是Merkel Tree的叶子节点是没有顺序的，那么每个节点都将维护出来一个不同的Merkel Tree。而且账户涉及到需要查询余额等信息，查询的复杂度也是O(n)
那如果使用Sorted Merkel Tree呢？
新增账户怎么办呢？Sorted Merkel Tree其实是不能动态扩展的。如果我们产生了一个新的账户要插入到Sorted Merkel Tree当中呢？因为新账户的在Sorted Merkel Tree中的顺序是不定的，很可能需要在中间插入一个新的账户，这个时候我们就只能又重头搭建一个新的Sorted Merkel Tree了，这又回到了要重新构建的问题。
为什么不适使用HashTable呢？
因为从理论上来说，只要key的数量够多，是可能出现Hash碰撞的，即两个不同的地址映射到了同一个账户。
综上所述：
我们需要找到一种，能够提供快速查询和更新，动态扩展，且结构稳定一致，避免碰撞问题，又能提供零知识证明的数据结构。
Merkel Patricia Tree
Trie (Retrieval Tree字典树)
下图中是一个字典树的样例，在这样的一个字典树中，每个节点的子节点的数量是26个，也就是26个英文字母，我们每次查询一个单词的时候，只需要从上往下依次匹配即可，假如我们插入的的单词的长度是有范围的，假如<=40，那么这棵树的深度就会是40，我们需要找到一个单词，最多就只需要查询40次，这是一个常数级别的复杂度。而且我们可以看到，即使我们插入单词的顺序不一样，最终也会产生一个一摸一样的树结构，这也就解决了新插入的问题。
那么放到以太坊中来看，以太坊的账户地址是16进制的形式，按照2^160的地址空间，以太坊的账户会是一个长度为40的16进制串，那么这样的地址构建出来的字典树将是一个深度为40，分叉因子为17的树(因为除了0~f还有一个结束标识符)。所以我们可以看到这样的一个数据结构符合了快速查询更新，且可以动态扩展且扩展后的数据结构呈现一致性，而且也不会产生碰撞问题的要求。
Trie的缺点以及Patricia Tree
从上图当中，我们可以看到Trie的一个缺点就是当Trie能容纳的分布空间远大于存进去的地址数量的时候，我们整棵树是比较稀疏的，也就是会浪费不少空间。这个时候我们就提出了一种带有路径压缩功能的树Patricia Tree。如下图我们可以看到，很多其实不包含分叉的单链区间被压缩了。下面这棵树明显是比上面这棵树节省空间的。只是当压缩的单链中出现分叉的时候，我们需要将他重新打开。总之，这样的一棵树在键值插入的分布比较稀疏的时候效果比较好。其实看似我们的地址有很多，几千万个几亿个，但是和2^160的分布空间下是很渺小的，所以注定我们的树是比较稀疏的。
Merkel Patricia Tree
MPT和PT的区别是什么呢？首先Merkel Tree和普通的Binary Tree的区别是什么呢？其实跟区块链和普通链表的区别一样，就是把普通指针换成了Hash指针。那么MPT和PT的区别其实也是这样，把指针换成了Hash指针，这样我们也能够计算出一个MPT的根Hash值并运用于零知识证明当中，这个时候，需要解决的最后一个问题也解决了。而且因为构建的树结构是稳定的有序的，所以我们不仅能证明membership，还能证明non-membership。也就是说不仅能证明一个账户是否在状态树中，也能证明一个账户不在这个状态树中
Modified Merkel Patricia Tree
节点分为三种
- Extension Node：只要发生了节点压缩，就会产生一个extension node。一个Shared nibble是一个十六进制数，shared nibbles就是所有被压缩的十六进制数。
- Branch Node：当存在多个分支的时候，就不能压缩了，这个时候就需要构建一个能指向所有子节点的Branch Node，里面一般维护了一个数组，只是数组中的每个位置对应的是一个分支的hash值。
- Leaf Node：当节点能代表一个账户的时候，他就是一个leaf node，里面就会存一些相应的账户信息，key-end就是代表最后的key值，可能一串可压缩的字符，也可能就是一个最终的字符。
(prefix的意思图中的左下角有解释)
以太坊中MPT是怎么跟随区块改变的呢
每个账户中的字段：
- Nonce
- Balance
- CodeHash
- StorageRoot
每个新的区块都会有一个新的StateRoot，但是它对于没有被卷入改动中的节点，他是依旧指向他的，但是对于涉及到了改变的节点就会指向新的改变后的节点。上图当中，只有原本的中间分支的节点被改动了，而其他的分支节点都是没有要改变指针的。而最后涉及改动的账户当中也依旧同理，每个账户其实也维护着一些小的MPT树，比如Storage root就指向了一个MPT树，而它上面的改动也依旧只波及从下往上的链上节点。所以其实全节点在更新状态树的时候，不是在对上面的节点的值做更改，而是对受到影响的链上节点重新构造一条新的链，然后改变hash指针指向这条新的，而没有被改动波及的节点的hash指针指向则依旧保持不变。
问题：
- 为什么要保留历史状态，为什么不直接就在原本的树上修改？
` `主要是为了应对分叉，临时性的分叉是常态，也就是说在不同主链上进行切换是很常见的，如果只是对维护的一棵树上的信息直接修改，意味着你要切换主链的时候，你要对当前的状态树进行回滚，然后根据新的主链上的节点再去更新。因为以太坊的状态是很复杂的，回滚操作也很困难。跟比特币不一样，比特币只是很简单的交易信息，要回滚还比较简单，但是以太坊要支持的是智能合约，以太坊中的智能合约是图灵完备的，能够执行很多比较复杂的操作，而你要针对这样一个智能合约去做回滚，就太困难了。所以这种直接保留历史状态的方法，就能很方便快捷的实现回滚并在做出新的fork decision的时候快速将状态切换到另一条分支链上。
Block 和Header的定义
这是发布的时候需要发布的信息。
