MPT（merkle Patricia trie ）及理解solidity里的storage

what？

MPT树是一种数据结构，用于在以太坊区块链中高效地存储和检索账户状态、交易历史和其他重要数据。MPT树的设计旨在结合Merkle树和Patricia树的优点，以提供高效的数据存储和验证

MPT树由四种类型的节点组成：

**扩展节点（Extension Node）**：存储一个前缀和一个指向下一个节点的引用。它的作用是为了压缩树的高度，提高存储效率。

**分支节点（Branch Node）**：包含16个子节点的数组，每个子节点对应一个16进制字符（0到f）。这些子节点可以是叶子节点、扩展节点或其他分支节点，用于构建树的层次结构。

**叶子节点（Leaf Node）**：包含键值对，存储着具体的数据。在以太坊中，这些数据通常是账户的状态信息，如余额、合约代码等。

**空节点（Null Node）**：表示空指针或空链接，用于表示树的末端。

是什么？

1. Merkel Patricia Tree(MPT)，翻译为梅克尔-帕特里夏树
2. MPT提供了一个基于密码学验证的底层数据结构，用来存储键值对(key-value)关系
3. MPT是完全确定性的，这是指在一颗MPT上一组键值对是唯一确定的，相同内容的键可以保证找到同样的值，并且有同样的根哈希(root hash)
4. MPT 的插入、查找、删除操作的时间复杂度都是O(log(n))相对于其它基于复杂比较的树结构(比如红黑树)，MPT更容易理解，也更易于编码实现

字典树（trie 前缀树）Data Structure Visualization

基数树（Radix Tree 压缩前缀树）

基数树又叫压缩前缀树(compact prefix tree)，是一种空间优化后的字典树，其中如果一个节点只有唯一的子节点那么这个子节点就会与父节点合并存储。

在一个标准的基数树里，每个节点存储的数据如下:[i0, i1, .. in, value]

• 这里的 i0,i1...,in 表示定义好的字母表中的字符，字母表中一共有n+1个字符，这颗树的基数(radix)就是n+1
• value 表示这个节点中最终存储的值
• 每一个i0 到in 的“槽位”存储的或者是nul，或者是指向另一节点的指针
• 用节点的访问路径表示key，用节点的最末位置存储 value:这就实现了一个基本的键值对存储

Merkle Tree

也被称作哈希树(HashTree)，以数据块的hash值作为叶子节点存储值。梅克尔树的非叶子节点存储其子节点内容串联拼接后的hash值。

帕特里夏树(Patricia Tree)

1. 如果一个基数树的“基数’(radix)为2或2的整数次幂就被称为“帕特里夏树”，有时也直接认为帕特里夏树就是基数树
2. 以太坊中采用 Hex字符作为key的字符集，也就是基数为16的帕特里夏树
3. 以太坊中的树结构，每个节点可以有最多16个子节点，再加上 value，所以共有 17 个“插槽”(slot)位置
4. 以太坊中的帕特里夏树加入了一些额外的数据结构，主要是为了解决效率问题

MPT(Merkel Patricia Tree)

1. 梅克尔-帕特里夏树是梅克尔树和帕特里夏树的结合
2. 以太坊中的实现，对key采用 Hex编码，每个Hex字符就是一个nibble(半字节)
3. 遍历路径时对一个节点只访问它的一个nibble，大多数节点是一个包含17个元素的数组;中16个分别以hex字符作为索引值，存储路径中下一个nibble的指针;另一个存储如果路径到此已遍历结束，需要返回的最终值。这样的节点叫做“分支节点”(branch node)
4. 分支节点的每个元素存储的是指向下一级节点的指针。与传统做法不同，MPT是用所指向节点的hash来代表这个指针的;每个节点将下个节点的hash作为自己存储内容的一部分，这样就实现了Merkel树结构，保证了数据校验的有效性

MPT节点分类

MPT中的节点有以下几类:

• 空节点(NULL)

• • 表示空字符串

• 分支节点(branch)

• • 17个元素的节点，结构为[v0..... v15,vt]

• 叶子节点(leaf)

• • 拥有两个元素，编码路径encodedPath 和值 value

• 扩展节点(extension)

• • 拥有两个元素，编码路径encodedPath 和键 key

MPT中数据结构的优化

• 对于64个字符的路径长度，很有可能在某个节点处会发现，下面至少有一段路径没 有分叉;这很难避免
• 我们当然可以依然用标准的分支节点来表示，强制要求这个节点必须有完整的16个索引，并给没有用到的那15个位置全部赋空值;但这样有点蠢
• 通过设置“扩展节点”，就可以有效地缩短访问路径，将几长的层级关系压缩成一个键值对，避免不必要的空间浪费
• 扩展节点(extensionnode)的内容形式是[encodedPath,key]，,其中 encodedPath包含了下面不分叉的那部分路径，key是指向下一个节点的指针(hash，也即在底层db中的存储位置)
• 叶子节点(leafnode):如果在某节点后就没有了分叉路径那这是一个叶子节点，它的第二个元素就是自己的value

MPT紧凑编码（compact coding）

• 路径压缩的处理相当于实现了压缩前缀树的功能;不过路径表示是Hex字符串(nibbles)，而存储却是以字节(byte)为单位的，这相当于浪费了一倍的存储空间
• 我们可以采用一种紧凑编码(compactcoding)方式，将两个 nibble 整合在一个字节中保存，这就避免了不必要的浪费
• 这里就会带来一个问题:有可能nibble 总数是一个奇数，而数据总是以字节形式存储的，所以无法区分nibble1和nibbles01;这就使我们必须分别处理奇偶两种情况
• 为了区分路径长度的奇偶性，我们在encodedPath中引入标识位

• • 我们在encodedPath中，加入一个nibble 作为前缀，它的后两位用来标识节点类型和路径长度的奇偶性

• • MPT中还有一个可选的“结束标记”(用T表示)，值为0x10十进制的16)，它仅能在路径末尾出现，代表节点是一个最终节点(叶子节点)
  • 如果路径是奇数，就与前缀nibble凑成整字节;如果是偶数，则前缀nibble后补0000构成整字节

how

MPT树的工作原理如下：

• 根据键值对构建树：将键值对插入到MPT树中，根据键的字节表示构建树的路径
• 哈希计算：每个节点存储其子节点的哈希值，以确保数据的完整性和安全性
• 路径压缩：利用扩展节点将具有相同前缀的节点合并，以减少树的高度和存储空间
• 快速检索：通过树的根节点可以快速检索任意键的值，而不必遍历整个树

以太坊中的MPT

1. StateDB结构，我们可以看到它有一个stateObjects字段，是地址到stateObjects的映射表（记得 "State Root"Merkle Patricia Trie是以太坊地址到以太坊账户的映射，stateObject是一个正在被修改的以太坊账户。）
2. stateObject结构，我们可以看到它有一个数据字段，属于StateAccount类型（记得在文章的前面，我们将Ethereum账户映射到Geth中的StateAccount）。
3. StateAccount结构，我们已经学习了这个结构，它代表一个以太坊账户，Root字段代表我们之前讨论的 "Storage Root"。
   在这个阶段，一些拼图的碎片开始拼凑起来。现在我们有了背景，可以看到一个新的 "以太坊账户"（StateAccount）是如何初始化的。

初始一个新的以太坊用户

为了创建一个新的StateAccount，我们需要与statedb.go代码和StateDB结构交互。

StateDB有一个createObject函数，可以创建一个新的stateObject，并将一个空的StateAccount传给它。这实际上是创建一个空的"以太坊账户"。

下图详细说明了代码流程。

1. StateDB有一个createObject函数，它接收一个Ethereum地址并返回一个stateObject（记住一个stateObject代表一个正在修改的Ethereum账户。）
2. createObject函数调用newObject函数，输入stateDB、地址和一个空的StateAccount（记住一个StateAccount=以太坊账户），返回一个stateObject。
3. 在newObject函数的返回语句中，我们可以看到有许多与stateObject相关的字段，地址、数据、dirtyStorage等。
4. stateObject的data字段映射到函数中的空StateAccount输入--注意在第103-111行StateAccount中的nil值被赋值。
5. 创建的stateObject包含初始化的StateAccount作为数据字段被返回。

好了，我们有一个空的stateAccount，接下来我们要做什么？

我们想存储一些数据，为此我们需要使用SSTORE操作码。

1. 我们从定义了所有EVM操作码的instruction.go文件开始。在这个文件中，我们找到了 "opSstore "函数。
2. 传入该函数的范围变量包含合同上下文，如堆栈、内存等。我们从堆栈中弹出2个值，并标记为loc（位置的缩写）和val（值的缩写）。
3. 然后，从堆栈中弹出的2个值以及合约地址一起被用作StateDB对象的SetState函数的输入。SetState函数先用合约地址来检查该合约是否存在一个stateObject，如果不存在，它将创建一个。然后，它在该stateObject上调用SetState，传入StateDB db、相应的key和value值。
4. stateObject SetState函数对'fake storage'做了一些空值检查，然后检查value是否有变化，如果有变化，则通过journal结构记录变化。
5. 如果你看一下关于journal结构的代码注释，你会发现journal是用来跟踪状态修改的，以便在出现执行异常或请求撤销的情况下可以恢复这些修改。
6. 在journal结构被更新后，storageObject的setState函数被调用，入参为key和value。这将更新storageObjects的dirtyStorage。
   好了，我们已经用key和value更新了stateObject的dirtyStorage。这实际上意味着什么，它与我们到目前为止所学的一切有什么关系?

让我们从代码中的dirtyStorage定义继续学习。

1. dirtyStorage被定义在stateObject结构中，它属于Storage类型，被描述为 "在当前交易执行中被修改的存储条目"。
2. 与dirtyStorage相对应的类型Storage是common.Hash到common.Hash的简单映射。
3. 类型Hash只是一个长度为HashLength的数组。
4. HashLength是一个常数，定义为32
   这对你来说应该很熟悉，一个32字节的key映射到一个32字节的value。这正是我们在EVM深度探讨的第三部分中从概念上看待合约storage存储空间的方式。

你可能已经注意到stateObject中的pendingStorage和originStorage就在dirtyStorage字段的上方。它们都是相关的，在最终确定过程中，dirtyStorage被复制到pendingStorage，而pendingStorage在 trie被更新时又被复制到originStorage。

在 trie 被更新后，StateAccount 的 "存储根 "也将在 StateDB 的 "提交 "中被更新。这将把新的状态写入底层的内存 trie 数据库中。

现在到了拼图的最后一块，SLOAD。

1. 我们再次从 instructions.go 文件开始，在那里我们可以找到 "opSload "函数。我们使用peek从堆栈的顶部抓取SLOAD的位置（存储槽）。
2. 我们调用StateDB上的GetState函数，输入合约地址和slot位置。GetState函数返回与该合约地址相关的stateObject。如果返回的stateObject不是空值，则调用该stateObject上的GetState函数。
3. 在stateObject上的GetState函数对fakeStorage进行了检查，然后对dirtyStorage进行检查。
4. 如果dirtyStorage存在，返回dirtyStorage映射表中位置key相对应的值。(dirtyStorage代表了合约的最新状态，这就是为什么我们试图首先返回它)
5. 否则就调用GetCommitedState函数，尝试在storage trie中查找该值。同样需要先检查fakeStorage。
6. 如果pendingStorage存在，返回pendingStorage映射表中位置key相对应的值。
7. 如果上述方法都没有返回，就去找originStorage，从那里检索并返回值。
   你会注意到，该函数试图先返回dirtyStorage，然后是pendingStorage，最后是originStorage。这是有道理的，在执行过程中，dirtyStorage是最新的存储映射，其次是pending，然后是originStorage。

一个交易可以多次操作一个存储槽，所以我们必须确保我们有最新的值。

让我们想象一下，在同一交易中，在同一存储槽的SLOAD之前，发生了一个SSTORE。在这种情况下，dirtyStorage将在SSTORE中被更新，在SLOAD中被返回。

到这里，你应该对SSTORE和SLOAD是如何在Geth客户端层面实现的有了了解。它们如何与状态和存储对象互动，以及更新存储槽与更广泛的以太坊 "世界状态 "的关系。

这很难，但你做到了。我猜这篇文章给你留下了比你开始之前更多的问题，但这也是加密货币的乐趣之一。

参考：

彻底理解solidity里的storage | 登链社区 | 区块链技术社区

https://noxx.substack.com/p/evm-deep-dives-the-path-to-shadowy-5a5?s=r

https://www.youtube.com/watch?v=x0Kn0_za2RQ&list=PLmOn9nNkQxJG2agxy_3liL-dJi6jfefTY&index=84