Merkle Patricia Tree

MPT树是一种融合Merkle树和前缀树的数据结构，用于以太坊管理账户数据，生成交易集合哈希以及交易收据管理。主要以下功能：

• 存储key-value键值对；
• 快速计算所维护数据的哈希标识；
• 提供快速回滚机制；
• 提供Merkle证明方法，实现轻节点SPV验证。

前缀树

前缀树，又称为字典树，节点在树中的位置为key决定，即key编码根节点到该节点的路径。

前缀树对查询操作比较高效，但对于较长的key, 容易造成空间浪费。

Merkle树

Merkle树通常是一种二叉树， 能够允许在公链环境下实现轻点节验证，但会造成存储空间变大。

MPT树

从图中可以看出， MPT树中有4种类型的节点：

• 叶子节点，为[key, value] 的键值对，key为16进制编码的字符串， 每个字符范围为0~16，value为RLP编码的数据；
• 扩展节点，为[key, value]的键值对，value为其它节点的hash值，链接到其到节点；
• 分支节点，为长度为17的list, 前16个元素对应着key中16个可能的路径的中间节点， 分支节点的父节点为扩展节点；
• 空节点，用null表示 。

相关操作

Get操作

示例：

上图是一次查找key为”cat“节点的过程。

1. 将key"cat"转换成hex编码[3,15,3,13,4,10,T] ；
2. 当前节点是根节点，且是扩展节点，其key为3,15，则递归地对其子节点进行查找调用，剩余的搜索路径为[3,13,4,10,T];
3. 当前节点是分支节点，以搜索路径的第一个字节内容3选择第4个孩子节点递归进行查找，剩余的搜索路径为[13,4,10,T]；
4. 当前节点是叶子节点，且key与剩余的搜索路径一致，表示找到了该节点，返回Val为“dog”；

Insert 操作

示例： 下图是一次将key为“cau”, value为“dog1”节点插入的过程。

1. 将key"cau"转换成hex编码[3,15,3,13,4,11,T] ；
2. 通过查找算法，找到左图蓝线圈出的节点node1，且拥有与新插入节点最长的共同前缀[3,15,3,13,4]；
3. 新增一个分支节点node2，将node1的val与新节点作为孩子插入到node2的孩子列表中，将node1的val替换成node2；
4. node1变成了一个扩展节点

删除操作

示例：下面是一次将key为“cau”, value为“dog1”节点删除的过程。

1. 将key"cau"转换成hex编码[3,15,3,13,4,11,T] ；
2. 通过查找算法，找到用叉表示的节点node1，从根节点到node1的路径与搜索路径完全一致；
3. 从node1的父节点中删除该节点，父节点仅剩一个孩子节点，故将父节点转换成一个叶子节点；
4. 新生成的叶子节点又与其父节点（扩展节点）发生了合并，最终生成了一个叶子节点包含了所有的信息；

Update操作

更新操作为insert和delete操作的结合。

Commit操作

MPT树的提交过程就是以根节点为入口，对根节点进行提交调用即可。下图展示了MPT树被持久化的过程：

左下角的叶子节点计算得到哈希为0xaa，将其存入数据库中，并在其父节点中用哈希值进行替换；粉色的扩展节点计算得到哈希为0xcc，在父节点用中0xcc进行替换；递归至根节点，计算得到根节点的哈希为0xee，即整棵树的哈希为0xee。

在某一次事务操作中，对整棵MPT树的部分节点的内容产生了修改，那么一次哈希重计算，仅需对这些被修改的节点、以及从这些节点到根节点路径上的节点进行重计算，便能重新获得整棵树的新哈希。

状态快速回滚

MPT树就提供了一种机制，可以零延迟地完成世界状态的回滚。这种优势的代价就是需要浪费存储空间去冗余地存储每个节点的历史状态。

示例：

mpt_10.jpg

在上图中，一个节点的内容由27变为45，就对应成创建了一条由蓝线圈出的新路径，通过复用绿线圈出的未修改节点信息，构造一棵新树，而旧路径依旧保留。故通过旧stateRoot，我们依旧能够查询到该节点的值为27。

所以，在以太坊中，发生分叉而进行世界状态回滚时，仅需要用旧的MPT根节点作为入口，即可完成“状态回滚”

Merkle证明

如有棵如下图所示的merkle树，如果某个轻节点想要验证9Dog:64这个树节点是否存在与默克尔树中，只需要向全节点发送该请求，全节点会返回一个1FXq:18, ec20,
8f74的一个路径（默克尔路径，如图中黄色框所表示的）。得到路径之后，轻节点利用9Dog:64与1FXq:18求哈希，在与ec20求哈希，最后与8f74求哈希，得到的结果与本地维护的根哈希相比，是否相等。

在以太坊中，利用默克尔证明在轻节点中实现简单支付验证，即在无需维护具体交易信息的前提下，证明某一笔交易是否存在于区块链中。

以太坊中的状态树

以太坊中中有世界状态树，收据树和交易树，如下图所示：

世界状态主要是地址和账户状态的映射：

以太坊有两种账户：外部账户EOA和合约账户，账户中的字段有：

• nonce: 发送的交易个数（EOA），或者合约创建的那个nonce；
• balance: 账户余额；
• storageRoot: 账户存储树的根（合约账户），对于EOA， 为空。MPT由Soliddity组成变量的方式确定。
• codeHash: 对于合约账户，存储EVM代码的hash值； 对于EOA, 为空。

参考

http://gavwood.com/paper.pdf

https://medium.com/@chiqing/merkle-patricia-trie-explained-ae3ac6a7e123

https://github.com/zhangchiqing/merkle-patricia-trie

https://eth.wiki/en/fundamentals/patricia-tree

https://ethfans.org/toya/articles/588

https://blog.csdn.net/ITleaks/article/details/79992072

https://dzone.com/articles/ethereum-yellow-paper-walkthrough-27