Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

二叉状态树的结构

有个胖子他姓杨
139 0 0
    在设计十六进制trie时,一些设计选择在当时听起来很棒,但是经过5年的实践,被证明带来了很多复杂性。鉴于ETH1.x想要转向二进制trie,我们正好可以借此机会研究一下状态的存储方式。/ p$ r* l6 m# @+ B2 O

& @; T9 |. C8 E0 R- v1 X    问题的根源
% Y" P. X, L/ y

3 ~" u9 k$ X9 L# i, v    在重新设计存储格式时,我们至少可以从5个方面进行改进。
% Y8 l* }: T/ C- M! N1 s5 t, C4 U; b; j) L& A
    将账户trie和存储trie合并:维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户& Q" [! \0 M' @. t3 q! ~8 s# z

: {$ J3 C7 Y8 T9 U7 C( [    trie,得到存储trie的根,然后再到存储trie上获取数据。" h( w; D" ^7 Y+ T

) ~% }8 E! S! n0 M7 W; n) n" V    扩展节点(extensionnodes):这是一种特殊的节点,负责给特定子树上的所有key加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的key必须以特定方式打包。8 j8 }) I5 _5 ~( H$ Z

9 o  }5 \4 ~8 j' J8 E: _    RLP编码格式旨在高效地对任意结构进行编码。由于其复杂性,它也带来了很多麻烦:必须费尽千辛万苦打包key块(packkeychunk)。另外,由于每个节点的结构相当固定,可以使用更简单的序列化方法来代替RLP。; F! u* L6 A7 s& a& q
2 t4 `5 m: C1 q( A
    与前两个问题相关的是,十六进制的前缀也会带来复杂性和混乱。: x; R6 `/ F1 r3 ~6 U

3 `/ \  C' U/ L3 C: b    十六进制trie的证明【即,“见证数据(witness)”】比二进制trie的证明大4倍左右。(欲知详情,请阅读这篇文章。(中文译本))/ f$ i& D' X: I; m, I( T: B

2 z, V. a3 l% g+ H: o2 E' _    RLP
/ m9 A# g7 M+ j0 t/ t8 L$ @/ U* {8 ^- e
    ——Ramble,LoseyourselfandPester?
& `+ X+ [/ G9 K
- P* E! m9 c4 o/ P' W7 l    (译者注:“RLP”是“RecursiveLengthPrefix(递归长度前缀)”的缩写,但作者这里使用了几个R、L、P开头的词“漫无目的、迷失自我、喋喋不休”,就是批评之意。)本文我们会讨论怎么解决RLP问题。如果RLP被取代,绝大多数核心开发者都不会感到伤心。这是因为RLP过于复杂。实际上,我听过的唯一一个支持保留RLP的理由是:“RLP实在太过复杂,不要再冒险选择新的格式了,以免重蹈覆辙。”RLP
4 M. J) l; j( N( T/ u7 x, Z" s; X( ?$ a7 N. p0 V* Y
    的基本原理是采用简单的size+data格式。这就是复杂性的由来。首先,size可以是任何整数(实际上,它不可能超过2字节,但是从原则上来说是可以的,因此你必须确保能够支持超过2
8 K7 y2 q7 h! H7 G2 J$ J/ X4 Y, Z6 P# s3 G4 c
    字节的size)。我们如何知道size部分在哪里结束,data部分在哪里开始?2 c: C) Z  V+ X) B3 c3 }) L
2 ]" `5 |) O2 T" c
    在大多数情况下,开头会加上一个header。这个& V# z4 I" z4 Y5 @2 `6 I4 e

6 |9 ~4 {9 r# E2 \& \! G    header是一个值h,然后再加上size值:因此,RLP编码是[length(data)+h][data]
- T. c; g7 T1 w! ~# T
3 ?0 |) C3 N2 {8 l9 i    如果length(data)+h
1 h" a+ v# ?; L9 W3 x5 \' ~' ], }+ {) T  U/ ~
    如果数据大小为一个字节,你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做?部分情况下可以,但是会另外增加复杂程度!如果data[0]: V6 t( E! C3 Z4 l, r3 ?
3 n6 h7 s5 b4 C+ }& m9 m- p
    还能再酸爽一点吗?当然可以了!RLP涉及两类“对象”:结构列表和字节数组。
% k+ t8 \% j, ?% B
$ I, H' ]4 [; J* i  q    字节数组:header=128,overflow_header=183
8 k/ s+ Z7 C4 o' M- i# }' x; J! W) T! M4 d6 n+ X
    结构列表:header=192,overflow_header=247; h& ]: ^- |, m0 q# r4 }; q1 g
% @: g, L' Z1 |0 [& r
    请注意,datasize部分的最大规模是8bytes,也就是一个- ~7 A3 t6 b  y: E  G. a

' U7 {, G0 H0 W    64bits(原文为“64-bytes”,应有误)的数字。确实,无论什么数据,18014398509481984KB应该都够用了。虽然还有很多棘手的细节有待深入,但要点看起来很清楚了:RLP难以驯服。我们再来看看它是如何与状态树交织在一起的。
- _* ~& @0 x/ Y8 z' i
% c7 J/ F+ \" w
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    10