注：没有全部复原，抽取了主体知识，加入了一些自己的理解，强烈建议去学习肖臻老师的课程，这绝对算得上是国内区块链讲解的*教程，纯学术和技术

完成的功能：账户地址->账户状态的映射

​ address->state

​ 地址是160bits 40个16进制的数

状态就是指外部账户与合约账户的状态，包括余额，交易次数nonce,对合约账户还包含代码和存储

• 对于设计什么样的数据结构来实现这个映射的思考？
  1. 是不是很直观的key-value pair就可以呢（哈希表）？
     • 系统中的全节点维护一个哈希表，每有一个新的账户插入到哈希表里，要查询账户的余额，就直接在哈希表中查询，如果不考虑哈希碰撞，那么查询的时间是常数级别的，更新也可以在哈希表中更新。
       • 问题：如果使用哈希表来提供Merkle proof怎么提供？
       • 希望一个人证明一下其余额，一种方法是把哈希表的内容组成一棵Merkle Tree，求出其根哈希值，保存在block header里
       • Problem在于如果有新区块发布，执行新区块中的交易就必然会使得哈希表的内容进行变化，发布下一个区块的时候再重新将这些哈希表中的内容组织成一棵Merkle tree?代价是不是太大了？其实大多数账户状态是不变的，所以每次都重新构建一棵新的树代价很大。
       • BTC系统中难道不是没出一个区块构建一棵新的Merkle Tree吗？
         • 为什么没有上述问题？那个Merkle-tree是干什么的？BTC的Merkle Tree是干嘛的，是把区块里包含的那些交易组织成一个Merkle Tree。BTC中的Merkle Tree是immutable不变的，每次发布一个新的区块对应一个Merkle Tree,构建完之后是不会再改的，下次发布新的区块再构建一个新的Merkle tree。区块里大概有多少个交易呢？每个区块大小为1M，每个交易大小250B左右，最多4000个左右，不是很大的merkle tree。
         • 如果ETH所有账户都使用Merkle来存储，那规模就太大了,代价也太大
         • Merkle tree 除了提供Merkle proof证明账户上有多少钱之外，Merle tree还可以维护各个全节点之间状态的一致性，这也是为什么BTC把root hash根哈希值写在块头里的原因
  2. 第二种思路：直接用一棵Merkle tree把所有账户放进去
     • 改的时候直接在Merkle tree里改，每次更新都是改一小部分，所以改的也是一小部分
       • Problem1:Merkle tree没有提供一个高效的查找和更新的方法
       • Problem2:这个Merkle tree要不要排序？
         • 不排序的话，一个问题是查找速度慢，另一个问题是叶节点是这些账户的信息，如果不规定账户在叶节点出现的顺序，那么构建出的Merkle tree不是唯一的。每个全节点按照自己的顺序构建Merkle tree,那么叶节点的顺序是乱的，构建出的merkle tree是不一样的，root hash值也不一样。
           • BTC没有这个问题是因为最后获得记账权得节点说了算，自己决定，大家跟随。如果ETH也这样操作，那么需要将账户的状态发布到区块中，那么发布到区块链中的是账户的状态，而账户的状态基本是不变的，这样操作是不可行的，浪费太多空间
         • 排序的话，Sorted Merkle Tree是不是就没有问题了？
           • 插入的话代价太大
     • 所以这两种简单的数据结构都不可以（真的太震惊了，为了引出MPT进行了多少思考）

以太坊使用的数据结构：MPT(Merkle Patricia Tree)

trie: 来源于retrieval(信息检索)，前缀树或字典树，也是key-value

特点：

1. trie中每个节点的分支数目取决于Key值中每个元素的取值范围（16进制0-f)
2. 键值越长，查找访问内存的次数也就越多，ETH都是40位16进制的数。（ETH和BTC的地址不通用）
3. trie不会出现碰撞
4. 输入不变，构造的trie是一样的
5. 更新操作局部性很友好

• trie的缺点：
  存储浪费。比如General路径上很多节点都是用不到的，但是都需要单独存储，会浪费空间
• 如果我们能将这些节点进行合并，那么可以节省存储的开销，同时提高查找的效率。不用一次一个往下找

Patricia Tree/Trie(压缩前缀树)

• 优点：
  • 树的高度明显压缩，访问内存的次数就会大大减少，效率就提高了
• 注意：
  • 如果新加入节点，可能就会弹开，公共部分减少
• 键值分布比较稀疏的时候，压缩效果比较显著
  • 去中心化系统防止账户冲突的唯一办法：很长的地址，稀疏分布

Merkle Patricia Tree

• Merkle tree与Binary tree有什么区别，区块链和链表有什么区别

  • 把普通指令换成哈希指令

• MPT与PT的区别也是一样，将地址转为哈希值，最后生成一个根哈希值

• root hash的作用？

  1. 防止篡改
  2. Merkle Proof:证明账户上有多少钱，证明某个账户是不存在的

• 以太坊使用的不是原生版的MPT，用的是Modified MPT

shared nibble:16进制数，一个nibble就是一个16进制数

三种节点：

• ​ Extension Node:如果出现了路径压缩，就是Extension Node
• ​ Branch Node:树枝节点
• ​ Leaf Node :叶子节点

每一个合约账户的存储都是一个小的MPT

• 为什么要保留历史状态?
  • 查看历史信息
  • ETH很容易分叉，会进行roll back 回滚，有历史记录才可以做到回滚
  • ETH中有智能合约，执行交易之后没有办法知道之前的状态，所以必须保留

ETH中代码的数据结构：

块头的结构

• ParentHash:前一个区块块头的哈希值
• UncleHash:叔区块可能比父区块大好几个辈分
• Root:状态树的根哈希值，
• TxHash:交易树的根哈希值
• ReciptHash:收据树的根哈希值
• Bloom:与数据树相关，提供某种高效的查询某种条件的交易的执行结果
• MixDigest:
• Nonce:挖矿的随机数

区块的数据结构:

• header:指向blockheader的指针
• uncles:指向叔区块的blockheader的指针，是一个数组，可以有多个叔区块
• Transactions:交易的列表

真正在网上发布的就是这些信息

前面讲（key,value)键值对，没有讲Value部分的存储，他需要进行序列化

RPL:Recursive Length Prefix是一种序列化的方法，特点是简单，极简主义，越简单越好，

只支持一种类型，nested array of bytes字节数组，一个一个字节组成的数组，可以嵌套

protocal buffer，protobuf:很有名的做序列化的库