Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

二叉状态树的结构

有个胖子他姓杨
128 0 0
    在设计十六进制trie时,一些设计选择在当时听起来很棒,但是经过5年的实践,被证明带来了很多复杂性。鉴于ETH1.x想要转向二进制trie,我们正好可以借此机会研究一下状态的存储方式。
/ k" b+ W  L! f/ B( g2 v# G( A7 C& \9 d% J. P7 a
    问题的根源
# w3 B3 d. H: g! L
- g6 Y# a2 [+ m2 G/ @
    在重新设计存储格式时,我们至少可以从5个方面进行改进。! N+ r  T/ O5 o, N' e% |
- O- L( @& h$ O& ~
    将账户trie和存储trie合并:维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户
( @- [2 r9 M" N4 Q6 q* n& R4 E8 K/ v
    trie,得到存储trie的根,然后再到存储trie上获取数据。- p0 N' a" u: m( w. Z* X  O

9 j2 l% {4 {2 |: @1 U1 V    扩展节点(extensionnodes):这是一种特殊的节点,负责给特定子树上的所有key加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的key必须以特定方式打包。
( u5 O# U$ B: S2 G& B
4 j: H* }) A1 \8 N    RLP编码格式旨在高效地对任意结构进行编码。由于其复杂性,它也带来了很多麻烦:必须费尽千辛万苦打包key块(packkeychunk)。另外,由于每个节点的结构相当固定,可以使用更简单的序列化方法来代替RLP。
! c- g1 b) i" t* K& A+ Y3 U$ ]. F: N9 Y/ b
    与前两个问题相关的是,十六进制的前缀也会带来复杂性和混乱。1 k2 t% M& |% ~& ]3 C; W% R
9 R  L4 n5 @8 K7 j/ N
    十六进制trie的证明【即,“见证数据(witness)”】比二进制trie的证明大4倍左右。(欲知详情,请阅读这篇文章。(中文译本))6 i5 a+ {4 M+ V- y. \# ]1 l2 s

* W$ D* P6 a* r    RLP
! G! U0 b0 `* i$ S! E9 s. T2 V2 v4 c# E' y7 N& Q9 C
    ——Ramble,LoseyourselfandPester?7 U9 I! [/ E4 N
) n& b& Q) ?, _. D; {9 L
    (译者注:“RLP”是“RecursiveLengthPrefix(递归长度前缀)”的缩写,但作者这里使用了几个R、L、P开头的词“漫无目的、迷失自我、喋喋不休”,就是批评之意。)本文我们会讨论怎么解决RLP问题。如果RLP被取代,绝大多数核心开发者都不会感到伤心。这是因为RLP过于复杂。实际上,我听过的唯一一个支持保留RLP的理由是:“RLP实在太过复杂,不要再冒险选择新的格式了,以免重蹈覆辙。”RLP- l1 J$ N* B, [, G' d: R

0 I! |1 o) o! v( @( m7 u4 J    的基本原理是采用简单的size+data格式。这就是复杂性的由来。首先,size可以是任何整数(实际上,它不可能超过2字节,但是从原则上来说是可以的,因此你必须确保能够支持超过2/ L9 Q" L0 J" A7 `

, d6 i( n9 z) O' @    字节的size)。我们如何知道size部分在哪里结束,data部分在哪里开始?: ]* u) F) p8 i
6 }( U: I8 [: }7 e" N: Y9 F
    在大多数情况下,开头会加上一个header。这个
7 E: ^) |: Z& l! y) c; i5 V* t7 _* k( N1 `( G
    header是一个值h,然后再加上size值:因此,RLP编码是[length(data)+h][data]
) @* X% G% D( `; k2 e3 [  Z: j+ b  X( }9 V% \& m( e6 d
    如果length(data)+h9 K- ]  c; b; W- N4 W4 w' c) U

, h' Z4 }  p) e, g. c4 o. }    如果数据大小为一个字节,你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做?部分情况下可以,但是会另外增加复杂程度!如果data[0]5 b* p% F1 D5 I# a' V/ g

+ q" J2 S, L1 C& ]$ L( R' ?# d) x7 {# h: S    还能再酸爽一点吗?当然可以了!RLP涉及两类“对象”:结构列表和字节数组。
& B8 T# m4 ^0 l6 [9 B2 G6 ]7 K' g
    字节数组:header=128,overflow_header=183
6 V3 y( H  c. Z$ T
& H4 ^) z1 a! E% Y    结构列表:header=192,overflow_header=247- Q& ?1 k2 o2 A: c* ^& l9 `
9 y, H0 v9 t0 [4 ^9 m4 L
    请注意,datasize部分的最大规模是8bytes,也就是一个1 @9 r$ l$ n+ E% d5 I. ?
0 _# b3 ^% y1 v+ S
    64bits(原文为“64-bytes”,应有误)的数字。确实,无论什么数据,18014398509481984KB应该都够用了。虽然还有很多棘手的细节有待深入,但要点看起来很清楚了:RLP难以驯服。我们再来看看它是如何与状态树交织在一起的。
- ]/ E( p% |6 y  _4 ?. b5 b0 x2 X+ h9 ]; Q' b2 c, X
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    10