栏目分类
官方正规赢钱手机游戏网站-首页
资讯中心
企业热门
服务与支持
解决方案
客户
项目委托
以太坊中枢建筑者:MPT十六叉树将被替换 | BTC
发布日期:2022-07-08 12:59    点击次数:151

写在前边:

设想一下,你正在翻译一册5000页的竹素,作家一直打电话告诉你他对故事做了调整,这会影响到你还是翻译过的页面……而这可能会一直络续下去,这就所以太坊从现时使用的MPT十六叉树转换为二叉树结构中遭遇的一个访佛逆境。对此,以太坊中枢建筑者Guillaume Ballet提议了一种决议,不错在约莫几天的本事内,通过3个要领完成这一行换手术。

\r\n

予以太坊的做个手术:十六叉树变二叉树需要这三步

\r\n

(图片来自:tuchong.com)

\r\n关于该提案,以太坊磋磨首创人vitalik指摘称:\r\n 来自Ballet的进犯接头基础,它会使以太坊无状况变得友好,同期创造了一个契机,以大大简化该合同。期待在曩昔的几个月中,来自以太坊1.x建筑人员愈加出色的职责及后果。 \r\n予以太坊做个大手术:MPT十六叉树转二叉树需要这三步

以下是译文:

影响以太坊的繁密问题之一是账户和合约数据的存储口头,以太坊目下采选的结构称为默克尔帕特里夏树(Merkle Patricia Tree,或简称MPT)。尽管从表面上讲,它是很专门旨的,但在施行中,它带来的问题要比其惩办的问题要更多。多年来,中枢建筑人员一直在接头向二叉树(binary tree)的治疗,在本文中,我将讲演我对这一问题的见识,然后给出一个惩办它的步调。

提议的经由引入了一个过渡期,在此本事,两种树结构都会存在。这么做的平允是,在治疗树结构时,主链不错保持运行,况且还不错确保将统统帐户治疗为二叉树口头。

 \r\n配景\r\n 

目下,以太坊的账户是被存储到一棵十六叉树当中的。所谓十六叉,就暗示一个节点有16个子节点,表面上这是很好的,因为这意味着你需要更少的阶段来存储你统统的数据。

举例,这就所以十六叉树的体式暗示键与值对(170,v)的经由。在十六进制中,170暗示为0xaa,因此你只需要两层:其中之一用于第一个a,另一层则用于第二个a。\r\n

予以太坊的做个手术:十六叉树变二叉树需要这三步

\r\n

图1: 这是一棵十六叉trie树示例,透露了值 v 何如存储在键0xaa处。此树只消2字节长的键,况且只沿0xaa键的子树被张开。为了纯粹起见,不相干的子树被替换为 … 。

\r\n提神,这棵树很浅,也很宽。然后将其与以下疏通键与值对的二叉树暗示法进行比拟。在二进制中,170暗示为10101010。\r\n

予以太坊的做个手术:十六叉树变二叉树需要这三步

\r\n

图2: 和图1中疏通的键值对,以二叉树体式进行存储。为了纯粹起见,不相干的子树被暗示为 … 。

\r\n你不错看到,这棵树要深得多,也窄得多。

在以太坊中,每个区块都包含一个stateRoot字段,它是MPT根的哈希值。一言以蔽之,这个哈希,是通过对根的16个子项的哈希列表进行哈希运算而获取的。这些子哈希列中的每一个,又循序是其子哈希列表的哈希,以此类推。

每次生成一个新区块时,矿工都会更新帐户树并再行野心其根哈希值。哈希存储在新区块的stateRoot字段中,然后新区块被密封。\r\n

予以太坊的做个手术:十六叉树变二叉树需要这三步\r\n图3 区块头的state root字段指向十六叉树的根。

\r\n问题就出目下这里了:通过对统统节点进行哈希运算来再行野心哈希根耗尽的本事太长,因此,为了野心根节点,矿工将从数据库中检索同级哈希(sibling hash)。尽管从数据库中获取统统子叶并对整棵树进行哈希运算所需的本事未几,但此操作仍然需要渊博本事。这是因为必须要从数据库中获取每个哈希。

在十六叉树中,时常每个阶段要获取15个同级哈希。在上头的示例中,这即是30个哈希。

即使更深化,二叉树每个阶段也只需要一个同级哈希。在上头的示例中,就只消8个哈希!这即是为什么在施行当中,二叉树本体上要更好的原因。

 \r\n掩饰滚动法\r\n 

可怜的是,要将以太坊从十六叉树切换到二叉树,并不是一件容易的事。有好多数据需要治疗,况且奉行转换需要耗尽跳动15秒的区块本事。

除此以外,设想一下,你正在翻译一册5000页的竹素,作家一直打电话告诉你他对故事做了调整,这会影响到你还是翻译过的页面……而这可能会一直络续下去。

这即是目下以太坊遭遇的问题,因为用户不错更新已治疗的地址,这意味着你必须再行初始治疗经由。

惩办此问题的建议是设一个过渡期,在此本事,在十六叉树的顶部摈弃一棵掩饰二叉树,它的作用是保存状况发生的统统转换,直到基树治疗为二叉树。

这种过渡会分红三步进行:\r\n第1步-治疗\r\n在这种步调中,信服在区块高度H1处,区块具有两个stateRoots:一个用于 基础 十六叉树,一个用于 掩饰 二叉树。\r\n

予以太坊的做个手术:十六叉树变二叉树需要这三步

\r\n

图4: 在治疗经由中,区块具有2个状况根(state Root):一个是传统十六叉树的只读根,第二个是 掩饰 二叉树的根。

\r\n十六叉树被以为是只读的,因此对状况的任何更新都将是对掩饰树的更新。

当一笔往复读取或更新一个帐户时,系统率先搜索掩饰树。若是在那边找不到帐户,系统将在旧的十六叉树中搜索该值。

而在同期,十六叉树正在后台治疗。目下不错无谓追想插入,因为统统转换都存储在顶部树中。\r\n第2步-基治疗\r\n后台治疗经由完成后,矿工将通过治疗放荡替换只读的十六叉树基础根来文牍他们已准备好进行切换。对状况的读写操作与要领1疏通。\r\n

予以太坊的做个手术:十六叉树变二叉树需要这三步

\r\n

图5:治疗的第二个阶段,区块头将十六叉树基础根替换为其二叉树治疗基础根,以向荟萃发送信号,奉告它们已准备就绪。

\r\n当一个饱和大的序列区块对治疗后的基础根具有疏通的值时,这意味着大多数矿工都完成了治疗,并对治疗后的树的外观终显着共鸣。接下开,就参预到同一经由。\r\n第3步-同一两颗树\r\n同一经由会缓缓进行:每次生成新区块时,都会从重复层中删除n个键,然后将其再行插入到基础树中。该经由将络续进行,直到从重复层中删除统统键为止。在此阶段,掩饰状况根将从区块头中删除。

除此以外,若是往复奉行写入掩饰树中找到的键,则该键将从掩饰树中删除,并平直写入到基础树。

 \r\n下一步\r\n 

咱们还是创建了一个初步的原型,以便预见完成治疗所需的本事。咱们信赖,统统这个词经由不错在合理的本事内(约莫几天)完成。跟着算法的更正,我将发布更多的细节。

致谢

这项提议成绩于Alexey Akhunov,Vitalik Buterin,Anna George,Sina Mahmoodi,Tomasz Stanczak以及Martin H. Swende提供的贵重意见。

 

相干接头:https://ethresear.ch/t/overlay-method-for-hex-bin-tree-conversion/7104