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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/708398.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Redis的缓存击穿、缓存穿透和缓存雪崩是什么?怎么预防?

Redis的缓存击穿、缓存穿透和缓存雪崩是什么?怎么预防? 前言缓存击穿定义解决思路实现加锁设置过期时间Lua脚本刷新锁 缓存穿透定义实现 缓存雪崩定义解决思路 总结 前言 最近在CSDN上看到了一篇博客,Redis缓存击穿、雪崩、穿透!…

04 DNS域名解析服务

1、DNS系统的作用及类型 在整个互联网大家庭中,大部分的网站、邮件等服务器都使用了域名形式的地址,如www.baidu.com、mail.163.com等。很显然这种地址形式要比使用61.233.189.147、202.108.33.74的IP地址形式更加直观,且更容易被用户记住。…

UE4中性能优化工具合集

UE4中性能优化工具合集 简述CPUUnreal InsightUnreal ProfilerSimpleperfAndroid StudioPerfettoXCode TimeprofilerBest Practice GPUAdreno GPUMali GPUAndroid GPU Inspector (AGI) 内存堆内存分析Android StudioLoliProfilerUE5 Memory InsightsUnity Mono 内存MemreportRH…

父亲节献礼,让爱从脚下升起!一双舒适劳保鞋,守护他的每一步

时光荏苒,转眼间我们又迎来了一个温馨的节日——父亲节。在这个特别的日子里,你是否已经为父亲精心挑选了一份特别的礼物呢?如果没有,那么今天就来给大家推荐一款既实用又贴心的父亲节礼物——一双舒适耐用的劳保鞋。它不仅能守护…

长亭Nginx入门

在学习Nginx时我们先学习下防火墙原理】 将流量代理给防火墙 这样WAF 会分析流量 防火墙安装网络拓扑图 流量给防火墙 再给负载均衡 反向代理这个网络拓扑图是 防火墙充当了反向代理角色 所以我们就知道了我们为了要学习Nginx 因为这个服务器支持很多功能模块 自己本身就能…

IO高级 -- 文件操作(Path、Paths、Files)

一、基础:File 1.1 构造方法: 1、 public File(String pathname) :通过给定的路径来创建新的 File实例。2、 public File(String parent, String child) :从父路径(字符串)和子路径创建新的 File实例。3、 public File(File pare…

【Windows10】查看WIFI密码

操作步骤 电脑上查看已连接Wi-Fi的密码的步骤如下: 连接需要查看密码的Wi-Fi。右键点击任务栏上的 [网络] 图标,选择 [开启"网络和Internet"设置]。在 高级网络设置 项目中,点选 [网络和共享中心]。开启网络和共享中心的窗口后,点…

vue+showdown展示Markdown 文本

前言&#xff1a; vueshowdown展示Markdown 文本&#xff0c;资料整理 使用教程-vditor&#xff1a; 1、安装 npm install vditor --save 2、使用 <template><div id"vditor" name"description" ></div> </template> <scri…

探索高效存储与快速查找: 深入了解B树数据结构

探索高效存储与快速查找: 深入了解B树数据结构 一、什么是B树二、B树的实现2.1 节点的定义2.2 插入关键字2.3 删除关键字2.4 查找关键字2.5 遍历B树 一、什么是B树 B树&#xff0c;也称为B-tree&#xff0c;是一种多路平衡查找树。它被广泛用于文件系统和数据库之中&#xff0c…

2024年6月-Docker配置镜像代理

步骤1&#xff1a;编辑 daemon.json 文件 vim /etc/docker/daemon.json步骤2&#xff1a;添加配置 将以下内容粘贴到文件中&#xff1a; {"insecure-registries": ["192.168.0.99:8800"],"data-root": "/mnt/docker","registr…

区间分割求解方程

本文实现了基于mpi4py的多进程算法 mpi不过多介绍&#xff0c;某些函数的用法也不是介绍范围&#xff0c;这里只给出怎么实现多进程的方程求根算法。区间划分求解方程&#xff0c;在串行程序里&#xff0c;二分法是非常经典的算法&#xff0c;现在对其进行拓展&#xff0c;实现…

YUV格式与RGB格式详解

图像处理 文章目录 图像处理前言YUV 格式YUV 采样 前言 像素格式描述了像素数据存储所用的格式&#xff0c;定义了像素在内存中的编码方式。RGB 和 YUV 为两种经常使用的像素格式。/ 1024 / 1024 2.63 MB 存储空间。 RGB 和 RGBA 格式 RGB 图像具有三个通道 R、G、B&#xff…

进程状态及其转换

0号进程(idle):在linux系统启动的时候最先运行的进程就是0号进程&#xff0c;0号进程又叫空闲进程。如果系统上没有其他进程执行那么0号进程就执行。0号进程是1号进程和2号进程的父进程 1号进程(init):init进程是由0号进程创建得到的&#xff0c;它的主要工作是系统的初始化。…

《C++ Primer》导学系列:第 1 章 - 开始

1.1 编写一个简单的C程序 概述 本小节介绍了如何编写和运行一个简单的C程序&#xff0c;帮助初学者了解C程序的基本结构和编译运行过程。 编写第一个C程序 我们从一个简单的C程序开始&#xff0c;它的功能是在控制台输出 "Hello, World!"。这是学习任何编程语言的…

【CGAL】圆柱体检测结果后处理

文章目录 文章说明算法思路代码展示结果展示 文章说明 这篇文章主要介绍&#xff0c;对使用CGAL中的 Region Growing 算法爬取圆柱体的结果进行后处理&#xff0c;以获取位置、轴向量、半径都较为合理的单个圆柱体。 在之前的一篇文章中&#xff0c;使用了open3D生成的标准圆…

560亿美元薪酬获批!马斯克:特斯拉未来市值将不止5万亿美元

KlipC报道&#xff1a;6月13日&#xff0c;美国电动汽车制造商特斯拉公司举办年度股东大会&#xff0c;其CEO马斯克对特斯拉生产销售、未来车型计划和在无人驾驶能等领域的发展进行了报告。此外&#xff0c;特斯拉股东批准了马斯克的560亿美元薪酬方案以及特斯拉总部迁至得克萨…

基于Verilog表达的FSM状态机

基于Verilog表达的FSM状态机 1 FSM1.1 Intro1.2 Why FSM?1.3 How to do 在这里聚焦基于Verilog的三段式状态机编程&#xff1b; 1 FSM 1.1 Intro 状态机是一种代码实现功能的范式&#xff1b;一切皆可状态机&#xff1b; 状态机编程四要素&#xff1a;– 1.状态State&#…

深入理解计算机系统 家庭作业6.22

每条磁道存 位 有r-xr条磁道 二者相乘就是我们要求的容量) 所以最大值x0.5

java-多态数组的多态参数

介绍 代码 employer父类 package hansunping;public class employer {private String name;private double salary;public employer(String name,double salary) {this.namename;this.salarysalary;// TODO Auto-generated constructor stub}public double getsalary() {retu…

GlusterFS企业分布式存储

GlusterFS 分布式文件系统代表-nfs常见分布式存储Gluster存储基础梳理GlusterFS 适合大文件还是小文件存储&#xff1f; 应用场景术语Trusted Storage PoolBrickVolumes Glusterfs整体工作流程-数据访问流程GlusterFS客户端访问流程 GlusterFS常用命令部署 GlusterFS 群集准备环…