建议和反馈

请填写你的反馈内容

使用覆盖层改变以太坊状态树的格式

2020-05-21 ·3500次阅读 ·读完需要10分钟

账户和合约存储数据的方式是影响以太坊的众多问题之一。以太坊协议选用了 Merkle Patricia Tree(MPT,默克尔帕特里夏树)来组织账户及合约数据。尽管这种数据结构在理论上效果很好,但在实际应用中,它带来的问题却比它能够解决的问题多。核心开发者们已经讨论多年,想要把这种数据结构换为二叉树,我将在这篇文章中阐述我对这个问题的看法以及如何实现这种转变。

我所提议的处理方法包括一段时间的过渡期,在这段时间内,网络要同时维护两种树结构。这样做的好处是,转换树结构的过程不会影响链的运行,并且可以确保所有的账户都被转换成了二进制格式。

背景

目前,以太坊的状态树是十六叉制的。十六叉制表示每个节点有 16 个孩子节点。理论上讲,这种方式挺好的,因为孩子节点多意味着只需要更少的 “层” (即树高)便可存储所有数据。

例如,下图是用十六叉树表示的键值对 (170, v)。十六进制中,170 记作 0xaa,因此你只需要两层:第一层记录第一个 a,第二层记录第二个 a。

可以看出,上图的树很矮,而且很宽。给定相同的键值对,下图展示了二叉树存储的情形。170 在二叉树中被表示为 10101010。


- 图 2. 与图 1 相同的键值对,存储在二叉树中。为了简洁,不相关的子树被表示为“...” -

从图中可见,二叉树要深得多,也窄得多。

以太坊中,每个区块包含一个 stateRoot 字段,这是该块处理完成后表示以太坊全局状态的 MPT 的树根哈希值。总的来说,这个哈希值是对根节点的 16 个孩子节点的哈希值所组成的列表作哈希运算得到的。这些孩子节点的哈希值又是孩子的 16 个孩子节点的哈希值所组成的列表做哈希运算得到的,以此类推。

每次打包交易生成新区块时,矿工都会更新账户树,重新计算根哈希。根哈希存储在新区块的 stateRoot 字段,然后新区块被共识。


问题在于:如果要对所有节点做哈希,重新计算根哈希的时间就太长了,因此,为了计算根节点的哈希,矿工将从数据库中检索 同层节点的兄弟哈希值(sibling hashes) 。虽然后者(矿工从数据库检索兄弟哈希值)花费的时间没有前者(矿工从数据库库得到所有的叶子节点并做哈希)那么多,这个操作还是很耗时。因为每个哈希都必须从数据库中取出。

在十六叉树中,通常每一层你都需要取出 15 个兄弟哈希值。在上面那个我构造的例子(图 1)中,(重计算根哈希)就需要 30 个哈希值。

尽管二叉树层次更深一点,但在每一层只需要一个兄弟哈希值。在上述例子(图 2)中,仅仅需要 8 个哈希值!这就是为什么在实际中二叉树更优。

覆盖层转变方法

不幸的是,转换为二叉树并不简单。需要转换的数据 太多了,执行转换花费的时间将多于 15 秒的区块生成时间 。

除此以外,设想你要翻译一本 5000 页的书,作者还在不停地告诉你他们对故事做了些修改,并且这些修改会影响你已经翻译过的页 …… 那这个过程就没完没了。转换状态树的格式也是一样的问题:可能你刚完成某个地址的格式转换,用户就使用了该地址(因此更新了该地址的状态),那你又得从头转换一遍(因为一个地址的状态更新也会影响到整棵状态树)。

解决这个问题的办法是增加一个过渡期,过渡期间,在十六叉树基层上建立一棵覆盖树(overlay tree)。这棵覆盖树是二叉树格式的,它的作用是保存状态上发生的所有变化,直到基层十六叉树完全转换为二叉树。转换分为 3 步进行。

第 1 步 —— 转换

在这种方法下,区块高度为 H1 时肯定会有 两个 状态根:一个是 “基层” 十六叉树状态根,一个是 “覆盖层” 二叉树状态根。


十六叉树被设置为只读,因此对状态的任何更新都将在覆盖树上进行。

当一笔交易读取或者更新一个账户时,系统首先会搜索覆盖树。如果在覆盖树中找不到账户,接着将会在旧的十六叉树中搜索值。

与此同时,十六叉树在后台进行转换。此时不需要担心值插入的问题,因为所有的改变都会存储在上层的覆盖树中。

第 2 步 —— 基层树切换

当后台转换过程完成,矿工对外宣告,他们已经准备好用转换结果(只读二叉树根)来替换只读的十六进制基层树根。对状态的读写与步骤 1 阶段是一样的。(译者注:此时的只读二叉基层树是根据原本的十六进制状态树得到的)


当足够多的一系列区块对转换所得的二叉基层树根给出了相同的值,意味着大多数矿工都完成了转换,并且认可转换后的树。合并过程则开始。(译者注:此时的合并是针对只读二叉基层树和可读写二叉覆盖树)

第 3 步 —— 合并两棵树

合并过程不断推进:每产生一个新的区块,就从覆盖树上删除 n 个键,把它们重新插入二叉基层树。此过程一直持续,直到所有的键都从覆盖树上移除。到达这步时,区块头就不再保留覆盖状态树的树根。

整个步骤的核心只有一个:如果交易执行时要写的键存在于覆盖树上,这个键就会从覆盖树上删除,写操作直接在二叉基层树上进行。

下一步

为了估计完成转换所需要的时间,我已经做了一个低转换率的原型系统。我们确信,整个过程花费的时间不会太离谱,也就是说几天时间就够了。我们会随着算法的改进而公布更多细节。


评论(0)问答(0)
请先登录或注册

请先登陆或注册

相关推荐

Reddit的首次代币发行:对以太坊意味着什么?

不久前蓝狐笔记谈到Reddit基于以太坊推出其社区代币的计划,而这两天事情已经有了进展。Reddit已经开始准备发行两个子板块社区代币。目前它们正在Beta测试中,这些代币已在以太坊Rinkeby测试......
moondesign · 2020-06-02
1595阅读 · 0赞赏 · 0问答

引介 | 什么是以太坊 2.0 测试网?如何参与?

一. 什么是以太坊 2.0 测试网?所谓 “以太坊 2.0 测试网”,指的是在以太坊 2.0 正式启动以前,为测试技术标准(spec)的安全性、各客户端实现的可靠性以及客户端之间的互通性而推出的、可以......
古风 · 2020-06-02
2570阅读 · 0赞赏 · 0问答

区块链技术:以太坊2.0技术分享

01以太坊的发展之路这是一张2019年的以太坊路线图,我们看到从2013年底,以太坊创始人Vitalik Buterin发布了以太坊初版白皮书,启动了项目,到现在已经不知不觉走过了6个年头。2014年......
三地 · 2020-06-02
1586阅读 · 0赞赏 · 0问答

使用 CLion IDE 开发新项目

新建项目新建文件夹目录如下:hello|__ src //文件夹|__ include //文件夹|__ Toolchain.cmake //拷贝过来|__ CMakeLists.txt //拷贝过来......
moondesign · 2020-06-01
1085阅读 · 0赞赏 · 0问答

论DeFi协议的分叉

随着一批一层区块链将要上线,我一直在思考以太坊的网络效应,以及基于以太坊DeFi协议的护城河(defensibility)。几年前,我写了一篇关于非主权一层网络货币(如比特币和以太坊)网络效应的文章。......
波bobo · 2020-06-01
1133阅读 · 0赞赏 · 0问答

以太坊轻客户端测试教程

以太坊轻客户端开始公测(https://github.com/zsfelfoldi/go-ethereum/wiki/Light-Client-Public-Test)。以太坊开发者Alex发推特说,......
论坛咸鸟 · 2020-05-29
1377阅读 · 0赞赏 · 0问答

2006

LK币

15

粉丝

41

笔记

感谢"千羽凡尘"

这篇精彩的笔记,目前已经帮助

  • 0
  • 3
  • 5
  • 0
  • 0
喜欢0
链客社群 加入

微博进入

商务合作>

广告投放>

公司名称:北京链客行科技有限公司

联系方式:010-67707199

ICP备案号:京ICP备18032136号

Copyright:链客区块链技术问答社区 版权所有

感谢您的提问,问题被社区永久收入以便新人查看。一定要记得采纳最佳答案哦!加油!

感谢您的善举,每一次解答会成为新人的灯塔,回答被采纳后获得20算力和相应的LK币奖励

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!

您将赞赏给对方2LK币的奖励哦!感谢您的赞赏!