以太坊源码分析---go-ethereum的MPT(Merkle

本文微信公众号，新月吉道长文章链接为：

本文中的图片可能不是很清楚。 想看清晰版的可以看原文链接微信公众号。

MPT（Merkle-Patricia Trie）实际上是以太坊中用来存储用户账户状态及其变化、交易信息、交易回执信息的一种数据结构。

说起MPT，就得说说MPT是如何演化而来的。

树

图片来自

Trie 树，也称为字典树或前缀树（prefix tree）。 这个数据结构以前在库里写过，当然是在我自己的项目中用到了。 通过对字符的直接索引，减少了字符串比较的动作，从而达到较高的查询效率。

但它也存在一些问题。

当有一个很长的字符串时，如果这个字符串不与其他字符串重叠，那么在trie中，无论是存储还是遍历都需要大量的节点，会导致trie树不平衡。

Patricia Trie（基数树）

图片来自

Patricia Trie，也称为 Radix Tree 或 compact prefix tree。 它在 trie 上进行了优化。 主要优化是如果只有一个子节点有一个父节点，那么父子节点会合并。 这样既可以减少存储空间，又可以提高搜索效率。

默克尔树

图片来自

Merkle Tree，也叫哈希树（hash tree）。 叶子节点是数据块的哈希值，非叶子节点是其对应子节点拼接字符串的哈希值。

叶子节点，也就是最底层是数据块，计算块数据的哈希值（图中的L1 L2 L3 L4）。

对于非叶子节点，从hash(L1)得到hash0-0，从hash(L2)得到hash0-1，再从hash(hash0-0 hash0-1)得到hash0。 以此向上计算，一直到根。

这样做有什么好处？

1、优点是当整棵树中的任何一个节点发生变化时，整棵树都会发生变化。

2. 当我要验证一个叶子节点时，不需要整棵树，只需要验证一个叶子节点相关的节点即可。 减少了下载和计算。

默克尔帕特里夏特里

那么MPT就是以太坊中的自定义数据结构。 它结合了 Merkle Tree 和 Patricia Trie 的特点。

然后先看源码。 注：代码在github.com/ethereum/go-ethereum/trie，版本为1.0.0

这是trie的整个mpt代码模块。 顺便说一句，以太坊的源代码结构是非常模块化的。

首先介绍节点的概念

github.com/ethereum/go-ethereum/trie/node.go

节点接口定义

然后有几种类型的节点

1. 全节点

github.com/ethereum/go-ethereum/trie/fullnode.go

fullnode用于不能合并的节点，那么会有一个完整的子节点索引（0-9a-f）。

2.短节点

github.com/ethereum/go-ethereum/trie/shortnode.go

shortnode用于优化合并节点以太坊源码解析，所以它的key就是合并结果的key。

全节点和短节点是结构节点。 如果你了解了这两个节点的区别，你就基本了解mpt的数据结构了。

那么除了结构节点，还需要数据节点。

1.价值节点

github.com/ethereum/go-ethereum/trie/valuenode.go

ValueNode很简单，就是用来存值的，没有别的。

2.哈希节点

github.com/ethereum/go-ethereum/trie/hashnode.go

trie加载的时候不需要完全加载，卸载的部分可以用hashnode表示。

ValueNode和HashNode是数据节点，只用来存储值。 不参与结构。

那么结构节点和数据节点的功能区分就是这个数据结构的重点。

结构节点：

全节点

短节点

数据节点

值节点

哈希节点

了解了结构之后，还需要看流程。

特里结构

github.com/ethereum/go-ethereum/trie/trie.go

新的

新建一个Trie。这里的流程是这样的

51：创建一个结构

52：Initialize revisions，用于保存roothash，记录roothash的变化

53：将root赋值给roothash（说明参数root是一个hash）

54-56：创建缓存

58-61：当root为nil时，表示创建一个空的Trie。

当 root 不为 nil 时，表示加载现有的 Trie。

从初始流程来看，应该是先创建一个空的。 （这很关键，这是我们跟踪过程的开始）

插入分析

更新

131-132：锁定操作

134：密钥转换

136-139：当该值不为空时以太坊源码解析，表示刷新节点或插入新节点。

创建一个 valuenode 并将 dirty 设置为 true。

调用插入。

141：当值为空时，表示要删除该节点，调用delete。

插入

178-181：当节点为零时。

当我们的 trie 为空时，root 为 nil。 然后在第一次插入时，遵循这个过程。

创建了短节点。 并归还了它。

在 Update 函数中，trie 的根将被分配给这个短节点。

那么第一次插入就完成了。

如果继续插入，执行过程就会来到这里。 第一次插入的根必须是短节点。

186-193：判断键。 如果key和待插入节点的key一致，只需要新建一个shortnode替换即可。

下面是一个很重要的插入过程。

196：变量k为插入的节点node的node_key（为了区分变量），变量key为要插入的节点的node_key。 计算其k与key的重合度。 如果重叠相同，则直接插入。

200-206：

说明k和key的长度不一样，所以shortnode需要一分为二。

pnode、nnode（也有递归insert后续动作）

当前节点替换为一个全节点，两个子节点都设置在这个全节点下。

208-210：这里判断匹配长度是否为0，如果是，则递归完成。

212：如果递归还没有完成，说明还有一些剩余的key无法匹配，那么创建一个shortnode来包含剩下的。

当插入节点为全节点时，插入相对简单。

218：直接插入全节点。

还要继续递归插入剩下的。

查询分析

获取，获取字符串

154：主进程使用get here，从根节点开始查找

229：是退出条件。 当递归找到key为0时，返回当前节点。

从237开始，根据类型进行不同的搜索

239-246：shortnode，不断进行key匹配查找，递归查询到最后一个子节点。

248：递归检查下一个fullnode节点。

这是一个全节点子节点索引查找。

至此最重要的mpt数据结构的插入查询就完成了。 如果你能看懂这些，那么你对mpt的理解就会很深了。

本文的重点是对mpt做一个简单的解释。

在Trie源码中，有缓存、编码、迭代器的代码，就不一一解释了。

Cache是​​简答缓存，里面封装了db，map等。

encoding是一种编码转换

迭代器是一个迭代器

龚浩华

祭司新月

QQ 29185807

2018 年 8 月 31 日

如果您觉得本文对您有帮助，可以转发到您的朋友圈，让更多的人一起学习。