本站公告: 火币c3认证账户先解封在收费,悟空V信:baitu558 帮助币友解决火币C3认证账户、okex风控和币安风控等账户问题(已帮助5000币友)!

[火币c3认证是什么意思]二叉状态树的结构, Part-1

币圈新闻 火币c3认证 358浏览 0评论

火币c3认证是什么意思整理:过去几个月来,我一直致力于将 trie 从十六进制树结构过渡到二进制树结构。我已经写了一篇关于如何转换状态树格式的文章(中文译本),但是没有完全说明状态树的结构。我将撰写一系列文章来探讨设计新结构时需要做出哪些权衡。本文是该系列的第一篇。

在设计十六进制 trie 时,一些设计选择在当时听起来很棒,但是经过 5 年的实践,被证明带来了很多复杂性。鉴于 ETH 1.x 想要转向二进制 trie,我们正好可以借此机会研究一下状态的存储方式。

问题的根源

在重新设计存储格式时,我们至少可以从 5 个方面进行改进。

· 将账户 trie 和存储 trie 合并:维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户 trie,得到存储 trie 的根,然后再到存储 trie 上获取数据。

· 扩展节点(extension nodes):这是一种特殊的节点,负责给特定子树上的所有 key 加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的 key 必须以特定方式打包。

· RLP 编码格式旨在高效地对任意结构进行编码。由于其复杂性,它也带来了很多麻烦:必须费尽千辛万苦打包 key 块(pack key chunk)。另外,由于每个节点的结构相当固定,可以使用更简单的序列化方法来代替 RLP。

· 与前两个问题相关的是,十六进制的前缀也会带来复杂性和混乱。

· 十六进制 trie 的证明【即,“见证数据(witness)”】比二进制 trie 的证明大 4 倍左右。

RLP —— Ramble, Lose yourself and Pester?

(译者注:“RLP” 是 “Recursive Length Prefix(递归长度前缀)” 的缩写,但作者这里使用了几个 R、L、P 开头的词 “漫无目的、迷失自我、喋喋不休”,就是批评之意。)

本文我们会讨论怎么解决 RLP 问题。如果 RLP 被取代,绝大多数核心开发者都不会感到伤心。这是因为 RLP 过于复杂。实际上,我听过的唯一一个支持保留 RLP 的理由是:“RLP 实在太过复杂,不要再冒险选择新的格式了,以免重蹈覆辙。”

RLP 的基本原理是采用简单的 size + data 格式。这就是复杂性的由来。首先,size 可以是任何整数(实际上,它不可能超过 2 字节,但是从原则上来说是可以的,因此你必须确保能够支持超过 2 字节的 size)。我们如何知道 size 部分在哪里结束,data 部分在哪里开始?

· 在大多数情况下,开头会加上一个 header。这个 header 是一个值 h,然后再加上 size 值:因此,RLP 编码是 [length(data)+h] [data]

· 如果 length(data)+h < 256,则 RLP 编码如上所示。如果数据太大,加上 h 值后超过一个字节,该怎么办?没错,你还需要再增加一个字节,即,引入 h' 值来表示你正在使用第二种存储方案。在这种情况下,RLP 编码是 [h'+length(length(data))] [length(data)] [data]。为 “方便” 起见,h' 被选定为 56。

· 如果数据大小为一个字节,你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做?部分情况下可以,但是会另外增加复杂程度!如果 data[0]< h,那就不需要增加 header。相应地,任何以小于 h 的值作为开头的字节负载必定只有一个字节。

还能再酸爽一点吗?当然可以了!RLP 涉及两类 “对象”:结构列表和字节数组。

· 字节数组:header=128,overflow_header=183

· 结构列表:header=192,overflow_header=247

请注意,data size 部分的最大规模是 8 bytes,也就是一个 64 bits (原文为 “64-bytes”,应有误)的数字。确实,无论什么数据,18014398509481984 KB 应该都够用了。

虽然还有很多棘手的细节有待深入,但要点看起来很清楚了:RLP 难以驯服。我们再来看看它是如何与状态树交织在一起的。

默克尔化规则(Merkelization rule)

我们怎么把 RLP 编码和它那令人厌烦的逻辑用到我们的默克尔化规则中?先从默克尔树底部的叶子节点开始说起。

叶子节点及其十六进制前缀

叶子节点保存了一个值(value),在这个值前面还有一个不知道多少位的键(key),这个键跟其它叶子节点的键肯定是不一样的。因此,我们有了一个元组 (key, value),这就是一个包含两个元素的列表,包含了 key 和 value,两个数据都是字节数组(byte array)。RLP 理论上应该能帮助我们编码这两个数据吧?不那么见得。

一棵十六进制树上的 key 是基于半字节(nibble-based)的,所以如果我们取出一个键的时候,它可能在半字节处就中止了,那问题就来了:我该怎么对齐数据呢?这里面必须要有一个设计抉择。结果是,我们使用一种叫做 “十六进制前缀(hex prefix)方法” 的函数来读取键数据,它会加入一个 header 来告诉我们所读的键的长度究竟是偶数个还是奇数个半字节。

 > 先解封后收费!帮助币友解决火币C3认证账户、okex风控和币安风控等账户问题欢迎添加微信:baitu558(已帮助5000币友)
关注微信二维码扫一扫

转载请注明:火币c3认证不通过怎么办 » [火币c3认证是什么意思]二叉状态树的结构, Part-1

游客
发表我的评论 换个身份
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址