MPT树详解

目录

• MPT树定义
  • MPT树的作用是什么？
  • 前缀树与默克尔树
    • 前缀树
    • 默克尔树
  • 三种节点类型
  • MPT中的Merkle
  • HP编码
  • 官方表示形式
  • 相关MPT树
• 参考目录

@

MPT树定义

ps:

1. 交易树：记录交易的状态和变化。每个块都有各自的交易树，且不可更改 
2. 收据树(交易收据)：交易收据的存储
3. 状态树(账户信息)：帐户中各种状态的保存。如余额等。
4. Storage Trie 存储树 ：存储只能合约状态 ，每个账号有自己的Storage Trie 。

回想我们我们上一次所讲的RLP：
在网络节点的本地以trie树的形式存储，发送给客户端的时候序列化成列表。这不就是RLP的作用嘛，用来对trie树种所有的条目进行编码
这个树，在以太坊，指的就MPT树

MPT树的作用是什么？

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

前缀树与默克尔树

前缀树

前缀树（又称字典树），用于保存关联数组，其键（key）的内容通常为字符串。前缀树节点在树中的位置是由其键的内容所决定的，即前缀树的key值被编码在根节点到该节点的路径中。

如下图所示，图中共有6个叶子节点，其key的值分别为（1）to（2）tea（3）ted（4）ten（5）A（6）inn。

默克尔树

merkle树是自底向上构建的。在下图的例子中，首先将L1-L4四个单元数据哈希化，然后将哈希值存储至相应的叶子节点。

将相邻两个节点的哈希值合并成一个字符串，然后计算这个字符串的哈希，得到的就是这两个节点的父节点的哈希值。

重要结论：
若两棵树的根哈希一致，则这两棵树的结构、节点的内容必然相同。

分析：

三种节点类型

知道了Merkle Tree，知道了Patricia Tree，MPT（Merkle Patricia Tree）就是这两者混合后的产物。下面我们介绍一下MPT树的三种节点类型

• 分支结点（branch node）：包含16个分支，以及1个value
• 扩展结点（extension node）：只有1个子结点

• 叶子结点（leaf node）：没有子结点，包含一个value
  
  需要注意的是：Key-value 这里的value存储的是key，key存储在路径上
  详细解释：

MPT中的Merkle

即指向下一级节点的指针是使用 节点的确定性加密hash，而不是传统意义上下一级节点地址的指针

如果给定的trie的根哈希是公开的，则任何人都可以 通过给出给定path上的所有节点, 来证明在给定path上存在一个给定值 ，对于攻击者,不可能提供一个不存在的（key，value）对的证明, 因为根哈希最终基于它下面的所有哈希，所以任何修改都会改变根哈希。

HP编码

HP-编码：特殊的十六进制前缀编码

引入：对nibble和节点奇偶性进行编码

举例:
对"0x5b3ed"编码（奇数位）
"0x5b3ed" = "0005 1011 0003 1110 1101"t=0 时, "0001"+"0005 1011 0003 1110 1101"->"00010005 10110003 11101101"->"0x15b3ed"
t !=0时 "0011"+"0005 1011 0003 1110 1101"->"00110005 10110003 11101101"->"0x35b3ed“

对"0x5b3e"编码（偶数位）
"0x5b3e" = "0005 1011 0003 1110"t=0 时, "0000"+"0005 1011 0003 1110 1101"->"00000005 10110003 11101101"->"0x005b3e"
t !=0时 "0010"+"0005 1011 0003 1110 1101"->"00100005 10110003 11101101"->"0x205b3e"

这里的t就是是否结束的标志位
最低位表示奇偶性，第二低位编码终止符状态。
最低位为0的时候表示偶数位置，反之奇数。
第二低位为1的时候表示结束，反之不结束。

官方表示形式

这里的prefix就是HP编码！对终止符的状态和奇偶性进行编码。最低位表示奇偶性，第二低位编码终止符状态。
总共有2个扩展节点，2个分支节点，4个叶子节点。 右边是叶子节点的情况，左边代表的是节点的prefix（HP编码）
这就是一个状态树的存储形式，其实他应当长的样子，我们可以细细想一下，他的key被编码成一种特殊的16进制的表示，value是一些rlp后的数据，而且比上图要大的多的多。

相关MPT树

现在，我们来回看一下，状态、存储以及交易树使用的MPT树。
首先说，全局状态树，这个全局状态树包含了以太坊网络中每一个账户的一组键值对。
对全局状态树的几点说明：

1. 状态前缀树包含了以太坊网络中每一个账户的一组键值对。
2. 他的Key是一个 160 位的标识符（以太坊账户的地址）。
3. 全局状态树中的 “值” 是通过编码以太坊账户中的如下细节来得到的（使用RLP的方法）：

• nonce 值
• 余额
• 存储前缀树根节点哈希
• 代码哈希
  我们可以从下图很清晰的了解：
  

存储树是智能合约数据存储的位置，每一个以太坊账户都有自己的存储树。
本图接上图；

参考目录

[1]. 深入浅出以太坊MPT(Merkle Patricia Tree)
[2]. 以太坊学习（2）MPT树--白话版
[3]. Merkle Patricia Tree 梅克尔帕特里夏树（MPT）规范
[4]. merkle树、Trie树、MPT树、以太坊中的那些树