Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

二叉状态树的结构

有个胖子他姓杨
189 0 0
    在设计十六进制trie时,一些设计选择在当时听起来很棒,但是经过5年的实践,被证明带来了很多复杂性。鉴于ETH1.x想要转向二进制trie,我们正好可以借此机会研究一下状态的存储方式。  \) r- j/ V: E; I5 V2 C
' D6 R& q# o8 X1 j) k
    问题的根源8 l: l2 H1 z! ^% p4 X) H* Q! H0 \
) X' z2 F! c) f
    在重新设计存储格式时,我们至少可以从5个方面进行改进。
5 d% t( f% R. C. E/ R' f
- c4 l! b' T/ X) i    将账户trie和存储trie合并:维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户- F- J# o! M! i# ~
- n7 U* G' b% _0 t# V$ F3 r
    trie,得到存储trie的根,然后再到存储trie上获取数据。9 w( ]* |) [5 p  k# o

: o" t5 w* t; D  b  ~6 W    扩展节点(extensionnodes):这是一种特殊的节点,负责给特定子树上的所有key加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的key必须以特定方式打包。; S, ~; I- I8 c2 N0 \' H

  G8 O  C  a6 z9 m4 h    RLP编码格式旨在高效地对任意结构进行编码。由于其复杂性,它也带来了很多麻烦:必须费尽千辛万苦打包key块(packkeychunk)。另外,由于每个节点的结构相当固定,可以使用更简单的序列化方法来代替RLP。1 w- K  W# X8 ]: d! _
, b! C& i7 d- P/ v. P$ f' @
    与前两个问题相关的是,十六进制的前缀也会带来复杂性和混乱。; S+ b5 B& ?# `2 C; s9 N

9 \5 \7 R- H+ B; x  j( x9 ^5 Q    十六进制trie的证明【即,“见证数据(witness)”】比二进制trie的证明大4倍左右。(欲知详情,请阅读这篇文章。(中文译本))
# z% f& N2 _" i6 t3 K( V% D: Z+ o3 h
% J" t6 R: @! K* H# n    RLP" T& P7 [' e4 K
) e$ M1 s& S! T. |0 H; Z
    ——Ramble,LoseyourselfandPester?
3 B$ v2 ~# ^0 b/ z
9 C0 y8 E' S9 |, ~    (译者注:“RLP”是“RecursiveLengthPrefix(递归长度前缀)”的缩写,但作者这里使用了几个R、L、P开头的词“漫无目的、迷失自我、喋喋不休”,就是批评之意。)本文我们会讨论怎么解决RLP问题。如果RLP被取代,绝大多数核心开发者都不会感到伤心。这是因为RLP过于复杂。实际上,我听过的唯一一个支持保留RLP的理由是:“RLP实在太过复杂,不要再冒险选择新的格式了,以免重蹈覆辙。”RLP! P) \( f2 j  O

4 \# |' l: [* u- l" i7 r7 |1 g# R    的基本原理是采用简单的size+data格式。这就是复杂性的由来。首先,size可以是任何整数(实际上,它不可能超过2字节,但是从原则上来说是可以的,因此你必须确保能够支持超过2
1 J5 K, j$ v$ c3 k; p% R+ t! `- x$ V5 Z& P" S
    字节的size)。我们如何知道size部分在哪里结束,data部分在哪里开始?
7 }4 m' Y6 L# ?' D4 _/ R- L$ }5 f6 Y% H: q1 x
    在大多数情况下,开头会加上一个header。这个; h% i6 f6 N3 F" l) s  K

* \5 k& z+ ^6 U, W% x: J    header是一个值h,然后再加上size值:因此,RLP编码是[length(data)+h][data]
  t* p/ a7 y* I8 ?1 V5 C" Z' p8 k& g; ]2 s/ \2 Z4 {8 @  h( _( s. F
    如果length(data)+h
' I' v  }. [2 l2 M; d
+ q6 j0 @' ~7 ~5 \1 C/ b" s( [    如果数据大小为一个字节,你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做?部分情况下可以,但是会另外增加复杂程度!如果data[0]
$ J! E4 O: S8 S+ r- _* ~7 N3 p' P% w3 l7 a% ^$ f  j* C$ K
    还能再酸爽一点吗?当然可以了!RLP涉及两类“对象”:结构列表和字节数组。* L( @# O# r: `9 E/ H0 Z

, z, d; M# [3 d+ s4 C    字节数组:header=128,overflow_header=183
9 X& D2 P5 @1 k; Q3 w
$ a. M7 t" T; @4 {" y" d/ n  B" f    结构列表:header=192,overflow_header=247* e9 w! l$ N! @9 G
; P; l8 o3 F, R5 J" T, {, h
    请注意,datasize部分的最大规模是8bytes,也就是一个% ]+ f$ H/ K$ t# h; W+ H
$ z2 ^6 r3 B" I* Y/ P+ y, q
    64bits(原文为“64-bytes”,应有误)的数字。确实,无论什么数据,18014398509481984KB应该都够用了。虽然还有很多棘手的细节有待深入,但要点看起来很清楚了:RLP难以驯服。我们再来看看它是如何与状态树交织在一起的。1 I9 t3 `4 N1 K) A; B8 Y

& p) j' v: D( I7 }7 x4 ~2 t! L0 d5 U9 {
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

有个胖子他姓杨 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    10