jsp做网站案例,电商网站开源授权二次开发,网站聊天代码,怎么形容网站做的好what#xff1f;
MPT树是一种数据结构#xff0c;用于在以太坊区块链中高效地存储和检索账户状态、交易历史和其他重要数据。MPT树的设计旨在结合Merkle树和Patricia树的优点#xff0c;以提供高效的数据存储和验证 MPT树由四种类型的节点组成#xff1a;
**扩展节点
MPT树是一种数据结构用于在以太坊区块链中高效地存储和检索账户状态、交易历史和其他重要数据。MPT树的设计旨在结合Merkle树和Patricia树的优点以提供高效的数据存储和验证 MPT树由四种类型的节点组成
**扩展节点Extension Node**存储一个前缀和一个指向下一个节点的引用。它的作用是为了压缩树的高度提高存储效率。 **分支节点Branch Node**包含16个子节点的数组每个子节点对应一个16进制字符0到f。这些子节点可以是叶子节点、扩展节点或其他分支节点用于构建树的层次结构。 **叶子节点Leaf Node**包含键值对存储着具体的数据。在以太坊中这些数据通常是账户的状态信息如余额、合约代码等。 **空节点Null Node**表示空指针或空链接用于表示树的末端。
是什么
Merkel Patricia Tree(MPT)翻译为梅克尔-帕特里夏树MPT提供了一个基于密码学验证的底层数据结构用来存储键值对(key-value)关系MPT是完全确定性的这是指在一颗MPT上一组键值对是唯一确定的相同内容的键可以保证找到同样的值并且有同样的根哈希(root hash)MPT 的插入、查找、删除操作的时间复杂度都是O(log(n))相对于其它基于复杂比较的树结构(比如红黑树)MPT更容易理解也更易于编码实现
字典树trie 前缀树Data Structure Visualization 基数树Radix Tree 压缩前缀树
基数树又叫压缩前缀树(compact prefix tree)是一种空间优化后的字典树其中如果一个节点只有唯一的子节点那么这个子节点就会与父节点合并存储。 在一个标准的基数树里每个节点存储的数据如下:[i0, i1, .. in, value]
这里的 i0,i1...,in 表示定义好的字母表中的字符字母表中一共有n1个字符这颗树的基数(radix)就是n1value 表示这个节点中最终存储的值每一个i0 到in 的“槽位”存储的或者是nul或者是指向另一节点的指针用节点的访问路径表示key用节点的最末位置存储 value:这就实现了一个基本的键值对存储
Merkle Tree
也被称作哈希树(HashTree)以数据块的hash值作为叶子节点存储值。梅克尔树的非叶子节点存储其子节点内容串联拼接后的hash值。 帕特里夏树(Patricia Tree)
如果一个基数树的“基数’(radix)为2或2的整数次幂就被称为“帕特里夏树”有时也直接认为帕特里夏树就是基数树以太坊中采用 Hex字符作为key的字符集也就是基数为16的帕特里夏树以太坊中的树结构每个节点可以有最多16个子节点再加上 value所以共有 17 个“插槽”(slot)位置以太坊中的帕特里夏树加入了一些额外的数据结构主要是为了解决效率问题
MPT(Merkel Patricia Tree)
梅克尔-帕特里夏树是梅克尔树和帕特里夏树的结合以太坊中的实现对key采用 Hex编码每个Hex字符就是一个nibble(半字节)遍历路径时对一个节点只访问它的一个nibble大多数节点是一个包含17个元素的数组;中16个分别以hex字符作为索引值存储路径中下一个nibble的指针;另一个存储如果路径到此已遍历结束需要返回的最终值。这样的节点叫做“分支节点”(branch node)分支节点的每个元素存储的是指向下一级节点的指针。与传统做法不同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 StateDB结构我们可以看到它有一个stateObjects字段是地址到stateObjects的映射表记得 State RootMerkle Patricia Trie是以太坊地址到以太坊账户的映射stateObject是一个正在被修改的以太坊账户。stateObject结构我们可以看到它有一个数据字段属于StateAccount类型记得在文章的前面我们将Ethereum账户映射到Geth中的StateAccount。StateAccount结构我们已经学习了这个结构它代表一个以太坊账户Root字段代表我们之前讨论的 Storage Root。 在这个阶段一些拼图的碎片开始拼凑起来。现在我们有了背景可以看到一个新的 以太坊账户StateAccount是如何初始化的。
初始一个新的以太坊用户
为了创建一个新的StateAccount我们需要与statedb.go代码和StateDB结构交互。
StateDB有一个createObject函数可以创建一个新的stateObject并将一个空的StateAccount传给它。这实际上是创建一个空的以太坊账户。
下图详细说明了代码流程。 StateDB有一个createObject函数它接收一个Ethereum地址并返回一个stateObject记住一个stateObject代表一个正在修改的Ethereum账户。createObject函数调用newObject函数输入stateDB、地址和一个空的StateAccount记住一个StateAccount以太坊账户返回一个stateObject。在newObject函数的返回语句中我们可以看到有许多与stateObject相关的字段地址、数据、dirtyStorage等。stateObject的data字段映射到函数中的空StateAccount输入--注意在第103-111行StateAccount中的nil值被赋值。创建的stateObject包含初始化的StateAccount作为数据字段被返回。
好了我们有一个空的stateAccount接下来我们要做什么
我们想存储一些数据为此我们需要使用SSTORE操作码。 我们从定义了所有EVM操作码的instruction.go文件开始。在这个文件中我们找到了 opSstore 函数。传入该函数的范围变量包含合同上下文如堆栈、内存等。我们从堆栈中弹出2个值并标记为loc位置的缩写和val值的缩写。然后从堆栈中弹出的2个值以及合约地址一起被用作StateDB对象的SetState函数的输入。SetState函数先用合约地址来检查该合约是否存在一个stateObject如果不存在它将创建一个。然后它在该stateObject上调用SetState传入StateDB db、相应的key和value值。stateObject SetState函数对fake storage做了一些空值检查然后检查value是否有变化如果有变化则通过journal结构记录变化。如果你看一下关于journal结构的代码注释你会发现journal是用来跟踪状态修改的以便在出现执行异常或请求撤销的情况下可以恢复这些修改。在journal结构被更新后storageObject的setState函数被调用入参为key和value。这将更新storageObjects的dirtyStorage。 好了我们已经用key和value更新了stateObject的dirtyStorage。这实际上意味着什么它与我们到目前为止所学的一切有什么关系?
让我们从代码中的dirtyStorage定义继续学习。 dirtyStorage被定义在stateObject结构中它属于Storage类型被描述为 在当前交易执行中被修改的存储条目。与dirtyStorage相对应的类型Storage是common.Hash到common.Hash的简单映射。类型Hash只是一个长度为HashLength的数组。HashLength是一个常数定义为32 这对你来说应该很熟悉一个32字节的key映射到一个32字节的value。这正是我们在EVM深度探讨的第三部分中从概念上看待合约storage存储空间的方式。
你可能已经注意到stateObject中的pendingStorage和originStorage就在dirtyStorage字段的上方。它们都是相关的在最终确定过程中dirtyStorage被复制到pendingStorage而pendingStorage在 trie被更新时又被复制到originStorage。
在 trie 被更新后StateAccount 的 存储根 也将在 StateDB 的 提交 中被更新。这将把新的状态写入底层的内存 trie 数据库中。
现在到了拼图的最后一块SLOAD。 我们再次从 instructions.go 文件开始在那里我们可以找到 opSload 函数。我们使用peek从堆栈的顶部抓取SLOAD的位置存储槽。我们调用StateDB上的GetState函数输入合约地址和slot位置。GetState函数返回与该合约地址相关的stateObject。如果返回的stateObject不是空值则调用该stateObject上的GetState函数。在stateObject上的GetState函数对fakeStorage进行了检查然后对dirtyStorage进行检查。如果dirtyStorage存在返回dirtyStorage映射表中位置key相对应的值。(dirtyStorage代表了合约的最新状态这就是为什么我们试图首先返回它)否则就调用GetCommitedState函数尝试在storage trie中查找该值。同样需要先检查fakeStorage。如果pendingStorage存在返回pendingStorage映射表中位置key相对应的值。如果上述方法都没有返回就去找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?sr
https://www.youtube.com/watch?vx0Kn0_za2RQlistPLmOn9nNkQxJG2agxy_3liL-dJi6jfefTYindex84
