Skip to content

Latest commit

 

History

History
111 lines (67 loc) · 9.61 KB

MPT report.md

File metadata and controls

111 lines (67 loc) · 9.61 KB

Merkle Tree

Merkle Tree 协议对比特币的长期持续性可以说是至关重要的。在2014年4月，比特币网络中的一个全节点-存储和处理所有区块的全部数据的节点-需要占用15GB的存储空间，而且还以每个月超过1GB的速度增长。目前，这一存储空间对台式计算机来说尚可接受，但是手机已经负载不了如此巨大的数据了。未来只有商业机构和爱好者才会充当完整节点。简化支付确认（SPV)协议允许另一种节点存在，这样的节点被成为“轻节点”，它下载区块头，使用区块头确认工作量证明，然后只下载与其交易相关的默克尔树“分支”。这使得轻节点只要下载整个区块链的一小部分就可以安全地确定任何一笔比特币交易的状态和账户的当前余额。

其中比特币和以太坊的merkle树构造方式并不相同：

  • 比特币中的Merkle 树采用复制最右边节点的方式保证树的平衡；在RFC6962中，提出了新的解决方式，具体见项目中的实现
  • 以太坊为账户状态的存储和更新设计了Merkle Patricia树

关于Merle Tree的具体构造，比较简单且课上介绍过，这里不再介绍，本文关注以太坊的实践：Merkle Patricia Trie

image-20220729175548538

Patricia Trie

在介绍Patricia Trie之前有必要先了解什么是trie。trie这种数据结构在《数据结构》课程中介绍过，其又称前缀树或字典树，是一种有序树，用于保存关联数组。广泛地应用于各种检索的场景之中，尤其是字符串的匹配，有比较高的性能。我们可以将Trie与哈希表进行一个对比：

  • Trie优点：

    相比于哈希表，使用前缀树来进行查询拥有共同前缀key的数据时十分高效，例如在字典中查找前缀为pre的单词，对于哈希表来说，时间效率为O(n)，然而对于前缀树来说，只需要在树中找到前缀为pre的节点，且遍历以这个节点为根节点的子树即可。

    但是对于最差的情况（前缀为空串)，时间效率为$O(n)$,仍然需要遍历整棵树，此时效率与哈希表相同。

    相比于哈希表，在前缀树不会存在哈希冲突的问题。

  • Trie缺点：

    1. 直接查找效率低下 前缀树的查找效率是O(m)，m为所查找节点的key长度，而哈希表的查找效率为O(1)。

    2. 可能会造成空间浪费当存在一个节点，其key值内容很长（如一串很长的字符串），当树中没有与他相同前缀的分支时，为了存储该节点，需要创建许多非叶子节点来构建根节点到该节点间的路径，造成了存储空间的浪费。

那么什么是Patricia Trie呢？

  • Patricia Trie 或是 Patricia Tree， 在一些论文中又称其为 compact trie（紧凑trie），或 compressed trie（压缩 trie）。
  • Patricia 的全称是 "practical algorithm to retrieve information coded in alphanumeric"，是 Morrison 于1968年提出的数据结构，原论文是二进制位比较的形式。

在Patricia Trie 中，对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。接下来看一个他的合并和分裂操作的例子：

合并操作

对于Trie 如果一个非根节点仅有一个子节点，则将其子节点与该节点合并(图源字典树之旅03.Patricia Trie(一))：

image-20220729175838428$\Longrightarrow$image-20220729175924295

分裂操作

如果需要添加键 "bc"，我们需要将 "bcd" 分裂成两个节点(图源字典树之旅03.Patricia Trie(一))：

image-20220729180049770$\Longrightarrow$ image-20220729180120946

MPT

接下来可以正式介绍MPT。根据回答以太坊 Merkle Patricia Tree 全解析 - 知乎 (zhihu.com) 中的介绍：

MPT 有以下几个特点：

  • 存储任意长度的key-value键值对数据，符合以太坊的state模型；
  • 提供了一种快速计算所维护数据集哈希标识的机制；
  • 提供了快速状态回滚的机制；
  • 提供了一种称为默克尔证明的证明方法，进行轻节点的扩展，实现简单支付验证；

  • 关于以太坊中MPT的编码：在以太坊中，MPT树有3种编码方式 1）Raw编码（原生的字符）；2）Hex编码（扩展的16进制编码）；3）Hex-Prefix编码（16进制前缀编码）；前两种方式比较trivial，这里解释一下Hex-Prefix编码：Hex-Prefix编码是为了区分leaf和extension（后文具体解释），以及把奇数路径变成偶数路径。具体来说，如果有terminator（16）那么就去掉terminator，然后根据固定的表格给key加上prefix。

  • 关于以太坊种MPT的extension节点：关于空节点和叶子节点没有太多特殊的地方，关于extension节点，是针对前缀树中出现存储空间浪费的情况进行了优化：当MPT试图插入一个节点，插入过程中发现目前没有与该节点Key拥有相同前缀的路径。此时MPT把剩余的Key存储在leaf or extension节点的Key字段中，充当一个快照。这种做法可以提高节点的查找效率

Get操作

将需要查找Key转成Hex编码，得到搜索路径，从根节点开始搜寻与搜索路径内容一致的路径；

  1. 若当前节点为叶子节点，存储的内容是数据项的内容，且搜索路径的内容与叶子节点的key一致，则表示找到该节点；反之则表示该节点在树中不存在。

  2. 若当前节点为扩展节点，且存储的内容是哈希索引，则利用哈希索引从数据库中加载该节点，再将搜索路径作为参数，对新解析出来的节点递归地调用查找函数。

  3. 若当前节点为扩展节点，存储的内容是另外一个节点的引用，且当前节点的key是搜索路径的前缀，则将搜索路径减去当前节点的key，将剩余的搜索路径作为参数，对其子节点递归地调用查找函数；若当前节点的key不是搜索路径的前缀，表示该节点在树中不存在。

  4. 若当前节点为分支节点，若搜索路径为空，则返回分支节点的存储内容；反之利用搜索路径的第一个字节选择分支节点的孩子节点，将剩余的搜索路径作为参数递归地调用查找函数。

Insert操作

  1. 首先找到与新插入节点拥有最长相同路径前缀的节点，记为Node；

  2. 若该Node为分支节点：

    1. 剩余的搜索路径不为空，则将新节点作为一个叶子节点插入到对应的孩子列表中；
    2. 剩余的搜索路径为空（完全匹配），则将新节点的内容存储在分支节点的第17个孩子节点项中（Value）；

  3. 若该节点为叶子／扩展节点：

    1. 剩余的搜索路径与当前节点的key一致，则把当前节点Val更新即可；
    2. 剩余的搜索路径与当前节点的key不完全一致，则将叶子／扩展节点的孩子节点替换成分支节点，将新节点与当前节点key的共同前缀作为当前节点的key，将新节点与当前节点的孩子节点作为两个孩子插入到分支节点的孩子列表中，同时当前节点转换成了一个扩展节点（若新节点与当前节点没有共同前缀，则直接用生成的分支节点替换当前节点）；

  4. 若插入成功，则将被修改节点的dirty标志置为true，hash标志置空（之前的结果已经不可能用），且将节点的诞生标记更新为现在。

Delete操作

  1. 找到与需要插入的节点拥有最长相同路径前缀的节点，记为Node；
  2. 若Node为叶子／扩展节点：
    1. 若剩余的搜索路径与node的Key完全一致，则将整个node删除；
    2. 若剩余的搜索路径与node的key不匹配，则表示需要删除的节点不存于树中，删除失败；
    3. 若node的key是剩余搜索路径的前缀，则对该节点的Val做递归的删除调用；
  3. 若Node为分支节点：
    1. 删除孩子列表中相应下标标志的节点；
    2. 删除结束，若Node的孩子个数只剩下一个，那么将分支节点替换成一个叶子／扩展节点；
  4. 若删除成功，则将被修改节点的dirty标志置为true，hash标志置空（之前的结果已经不可能用），且将节点的诞生标记更新为现在。

inclusion proof & exclusion proof & consistency proof

校验过程与传统的Merkle Tree区别不大，其中RFC6962描述了一种针对奇数个数据块build tree以及一致性校验的过程。而非存在性证明需要数据块之间是有序存储的：

非存在性证明的基本逻辑为，找到树中存在的值小于目标元素值的最大元素，并找到树中存在的值大于目标元素值的最小元素，构造这两个元素的存在性证明并去除重复的中间节点。如果根据非存在性证明计算出来的简单Merkle树的散列值与正确的值相等，并且证明中包含的两个叶子节点为相邻的叶子节点，就证明树中确实不存在目标元素。

参考