ETH-状态树
以太坊的账户是基于账户的模式，系统中显示的维护每个账户有多少余额。
我们需要完成的是账户地址，到账户状态的映射（addr(160 bits == 表示成40个16进制的数)->state）,这里的状态指的是外部账户和合约账户的状态。
①这有点像key-value对，给出一个账户地址，要找出一个相应的状态。如果就用一个哈希表怎么样？每创建一个账户就存入哈希表（不考虑哈希碰撞，它的效率是常量级的）
用这个表的话，如果要提供Merkle proof，怎么提供？
比如说，你要和一个人签合同，希望他能证明一下他有多少钱，一种方法是，把这个哈希表中的元素（内容）组织成一个Merkle tree，然后算出一个根哈希值，这个根哈希值得保存在block header里，公布出去，那么这个根哈希值只要是正确的，就能保证底下的树不会被篡改。那如果有新的交易怎么办，新的交易必然会导致哈希表的内容变化，然后我们发布下一个区块的时候，要把这些哈希表中的内容在组织成一棵Merkle tree吗？这个代价会不会太大了点，实际上发生变化的状态只是一小部分。难道，比特币在构建新区块的时候就不用构建一颗新的Merkle tree吗？那个为什么没有这个问题？因为比特币发布的区块中的Merkle tree是通过区块中的交易来构建的，每个区块中的交易都不一样。如果像以太坊中的所有账户都构成一个Merkle tree来比较，代价就太大了（这比交易构成Merkle tree要高出好几个数量级）。
除了提供Merkle proof 证明账户上有多少钱之外，这个Merkle tree还有另外的作用：维护各个全节点之间状态的一致性（这也就是为什么比特币把根哈希值写在块头里的一个原因，对于这个区块中包含那些交易，全节点要有一个共识）。
所以如果就简单的全节点在本地维护一个哈希表，然后需要Merkle tree的时候构建Merkle tree，根哈希值放在块头，这个方法是不行的。
②我们不需要哈希表了，直接就把所有的账户放进去，你要改的时候直接在Merkle tree里改，因为你每次更新的都是一小部分账户，所以你每次修改的都是Merkle tree中的一小部分？
这个方法的问题在于，没有提供一个高效的查找和更新的方法，还有一个问题在于，我们这个Merkle tree要排序吗？如果不排序会怎么样？
如果不规定这些账户在叶子节点的顺序，那么构建出来的Merkle tree不是唯一的。系统中有很多的全节点，每个 全节点按照自己的某个顺序，构建一颗Merkle tree，最后构建出来的Merkle tree是不一样的。比特币中不也是不 排序吗？为什么比特币中就没有这个问题？
比特币中每个结点收到的交易顺序也是不一样的，所以理论上说，这样构建的Merkle tree也是不一样的，但是比 特币中的Merkle tree最终是获得记账权的结点说了算。
如果以太坊也这么做的话，需要把账户的状态发布到区块里（也就是每个全节点决定怎么把账户组织成一个Merkle tree），但是你是发布的账户的状态，不是交易的状态，差了好几个数量级。
如果使用排序的Merkle tree呢？
如果你新增一个账户怎么办，这个账户地址生成的时候是随机的，可能是在中间，那么后面的这些账户的结构都得变。其实可以这样：你产生一个新账户，其他人其实是没有必要知道的，当你产生交互的时候或者别人往里面转账别人才需要知道，当产生交易需要把这个账户加入到数据结构中，问题在于，这个代价有多大？如果你用哈希表的话，代价是常量级的，如果直接使用账户的哈希，这个代价可能得重构这个数据结构。
以太坊采用的做法：
首先介绍trie（中文叫做字典树）的数据结构。
这个结构的特点：
①在trie中，每个节点的分支数目，取决于这个key值里每个元素得取值范围，这个例子中，每个结点得分支个数最多是26个加上一个结束标志位，表示这个单词到这是不是就结束了。
②trie的查找效率，取决于这个key的长度。
③如果使用哈希表来存储这个key-value对，从理论上说，是有可能出现哈希碰撞（两个地址不一样，但是它的内容碰巧一样）的，但是trie是如果两个的地址不一样，最后肯定映射到树中的不同分支，所以trie不会出现碰撞
④我们前面讲的Merkle tree，如果你不排序，一个问题是，你的账户插入到Merkle tree中的顺序不一样 ，Merkle tree的结构也不一样，trie中只要给定一组输入，这个输入不变，最后插入这个trie当中是一样的。
⑤每次发布一个区块，系统中的绝大多数状态是不变的，只有个别受到影响的状态才会变，所以更新操作的局部性很重要，要想访问genesis，只要访问对应的分支即可，更新的局部性也是很好的
但是trie也有缺点：只有一个分支的情况很浪费内存，如果能把一个分支的分支合并起来，就能够提高存储的开销，同时提高查找和更新的开销，这就引入了我们的Patricia tree（trie）[经过路径压缩的前缀树]，如果经过路径压缩，上例就变成了下图：
对于Patricia tree来说，如果你需要添加结点，原来压缩的结点可能会需要扩展开来，路径压缩在什么情况下比较好？
树中插入的这些键值的分布如果是比较稀疏的情况下。比如上图中的，每个单词都很长，但是总共没有多少个单词的时候。
例如：下图的三个单词插入一个普通的tria中，效率就变得特别低
如果用Patricia tree，如下图
在以太坊中是怎么样的？
我们在前面讲过，地址表示成40个16进制的数，所以这个分叉数目，有时候管他叫做branching factor（17 == 16个[0 - f] 加上一个结束标志位），比特币和以太坊的地址是不通用的，两个地址的格式、长度都是不一样的，有一点是一样的，以太坊中的地址，也是公钥经过转化得来的（公钥取哈希，截一段，前面不要，只要后面的一部分）
那么我们这个应用场景（以太坊）中键值是否是稀疏的呢？
键值是地址，160位，总共的地址空间有2^160，以太坊中全世界的账户数目加在一起也远远没有这么大，所以以太坊的账户是非常非常稀疏的。
为什么不把账户地址缩短一点？这样访问效率还快，也没必要那么稀疏了
更大地避免哈希碰撞，这是一个去中心化的系统防止账户冲突的唯一办法。
MPT
Merkle Patricia tree
和Patricia tree有什么区别？
把普通指针换成了哈希指针，所有的账户组织成一个Patricia tree，用路劲压缩提高效率，然后把普通指针换成哈希指针，所以就能计算出一个根哈希值，存放在block header里。比特币有一个根哈希值（这个区块里所有交易组成的根哈希值），以太坊中有三个，这里讲的是状态树。
这个根哈希值有什么用？
①防止篡改，只要根哈希值不变，整棵树的任何部分都没有办法被篡改。
②Merkle Proof，这棵树能证明什么？能证明每个账户的余额：这个账户所在的分支，作为Merkle Proof，发给轻结点，轻结点就可以验证账户上有多少钱。
③能不能证明一个账户是不存在的？你想给一个账户转账之前，你想验证一下节点里，有没有这个账户信息，证明方法和sorted Merkle tree类似，如果存在是存在什么样的分支里，把这个分支作为Merkle tree发出去，可以证明它是不存在的。
以太坊中用到的还不是原生的MPT，以太坊中使用的是Modified MPT：
根节点取得的根哈希值KECCAK256是要写在块头里的，这里的指针都是哈希指针。
每次发布一个新的区块的时候，这个状态树中有一些结点的值会发生变化，这些改变不是在原地改的，而是新建一些分支，原来的状态其实是保留下来的：
我们可以看到，虽然每个区块都有一个状态树，但是这两棵树的大部分节点，是共享的，只有那些发生改变的节点，是需要新建一个分支的，这个例子中合约账户发生了变化（因为他有code，还有存储），合约账户的存储也是用MPT的形式保存下来的，这个存储其实也是一个key-value，维护的是从变量到这个变量取值的映射，所以以太坊中的结构是一个大的MPT，包含很多小的MPT（每个合约账户的存储都是一棵小的MPT）
这个例子中，nonce、balance发生了变化，code不变，所以Codehash指向原来树中的节点，存储中大部分结点也是没有变化，只有一个节点发生了变化，整数变量从29变为了45，所以新建了一个分支。
所以，系统中的全节点维护的不是一棵MPT，而是每次出现一个区块，都要新建一个MPT，只不过这些状态树中大部分节点是共享的，只有少数发生变化的节点是需要新建分支的，那么，为什么要保留历史状态？（为什么不在原地直接改了）
系统中可能会出现分叉，临时性的分叉实际上是很普遍的，以太坊把出块时间降到十几秒之后，临时性的分叉是常态。
回滚的话，就需要维护这些历史记录，不是为了证明我以前有多少钱，而是因为当前这个交易有可能要undo，
比特币中简单的转账交易是很容易的，以太坊中为什么不行？
以太坊中有智能合约，以太坊如果不保存原来的状态，智能合约执行完成之后，你想要roll back，这是不可能的。
以太坊中代码的数据结构：
block header：
ParentHash：前一个区块块头的哈希值
uncleHash：叔父区块的哈希值（ghost协议中会提到）[uncle可能回避parent大很多辈分]
CoinBase：挖出这个区块的矿工的地址
Root：状态数的根哈希
TxHash：交易树的根哈希值
ReceiptHash：收据树的根哈希值
Bloom：和收据树相关，提供一种高效的查询，符合某种条件的交易的执行结果
Difficulty：挖矿的难度，会根据需要调整
GasLimit、GasUsed：和汽油费相关，有点类似比特币中的交易费
Time：这个区块大致的产生时间
MixDigest、Nonce：和挖矿过程相关，Nonce：类似于比特币中的随机数；MixDigest是从Nonce通过一些计算出来的哈希值。
区块的结构：
header：指向block header的指针
uncles：指向叔父区块block header的指针（数组类型）
transactions：交易列表
区块真正在网上发布的信息：
状态树中保存的是key-value pair，key就是地址， 我们前面所讲的都是key（地址的管理方式），那么这个value（账户的状态）呢？
实际上是要经过一个序列化的过程：RLP（Recursive Length Prefix），极简主义，和protocal buffer相比；它只支持一种类型：nested array of bytes，说白了就是字节数组，以太坊的其他所有类型（整数、哈希表），最后都得变成nested array of bytes，所以你要实现一个RLP，比较容易。