Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

二叉状态树的结构

有个胖子他姓杨
109 0 0
    在设计十六进制trie时,一些设计选择在当时听起来很棒,但是经过5年的实践,被证明带来了很多复杂性。鉴于ETH1.x想要转向二进制trie,我们正好可以借此机会研究一下状态的存储方式。
; g( n8 t" W  t* \* n8 t
# s& N0 {- ]" q- s+ B7 w    问题的根源6 N" f, _  V& Y3 s4 x5 [
/ \# y  ?  s/ M
    在重新设计存储格式时,我们至少可以从5个方面进行改进。! `  q2 R( `) p0 H  J7 w

$ M! K# V; }9 ~    将账户trie和存储trie合并:维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户0 E" p, L( A# I% a5 h# b+ P3 t5 X

$ B7 a9 `- I% A9 W, h5 c- v8 Z! V- T% a    trie,得到存储trie的根,然后再到存储trie上获取数据。$ v5 T) f  C$ E

1 }  U3 K  r+ c+ w- T  k    扩展节点(extensionnodes):这是一种特殊的节点,负责给特定子树上的所有key加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的key必须以特定方式打包。
' U# y4 w( \5 e( ]( M' J* j8 U: d; q/ \/ w: A" h$ Z' {
    RLP编码格式旨在高效地对任意结构进行编码。由于其复杂性,它也带来了很多麻烦:必须费尽千辛万苦打包key块(packkeychunk)。另外,由于每个节点的结构相当固定,可以使用更简单的序列化方法来代替RLP。
% }4 K9 v4 [) N$ D( D3 h5 D. W2 Z: u8 I! U% z4 t3 y. i/ A
    与前两个问题相关的是,十六进制的前缀也会带来复杂性和混乱。1 i* X) j3 F4 b
+ {' [7 e0 G0 d( r$ r
    十六进制trie的证明【即,“见证数据(witness)”】比二进制trie的证明大4倍左右。(欲知详情,请阅读这篇文章。(中文译本))
4 E3 _% p- c) H( ]" }
( b- V9 _- I! M: n+ Q8 e* D4 g9 V    RLP& s2 j; a' k- R: C1 P& v
  p' U1 _4 t% r; N
    ——Ramble,LoseyourselfandPester?$ Y+ J& D6 K" M- D8 n: N! W
2 q2 s  q1 ]: j* k( R
    (译者注:“RLP”是“RecursiveLengthPrefix(递归长度前缀)”的缩写,但作者这里使用了几个R、L、P开头的词“漫无目的、迷失自我、喋喋不休”,就是批评之意。)本文我们会讨论怎么解决RLP问题。如果RLP被取代,绝大多数核心开发者都不会感到伤心。这是因为RLP过于复杂。实际上,我听过的唯一一个支持保留RLP的理由是:“RLP实在太过复杂,不要再冒险选择新的格式了,以免重蹈覆辙。”RLP
4 j! v4 a# T0 U' ^$ l0 z+ |) D0 }% o4 c  T" q
    的基本原理是采用简单的size+data格式。这就是复杂性的由来。首先,size可以是任何整数(实际上,它不可能超过2字节,但是从原则上来说是可以的,因此你必须确保能够支持超过2
1 A: G% [$ k: p8 z5 _. s" ^
, A( B4 B2 g& [* f/ R3 x    字节的size)。我们如何知道size部分在哪里结束,data部分在哪里开始?
- a4 X2 n6 D- B3 ]
$ t- d0 P) h* D- X( I, c    在大多数情况下,开头会加上一个header。这个$ V/ U! n2 P- c. S/ M
  h( k+ x  L7 N, E7 u& V; |
    header是一个值h,然后再加上size值:因此,RLP编码是[length(data)+h][data]* C/ ^3 g3 F7 x( @5 E: S1 L" p% ^

6 w7 ?# u& E1 o    如果length(data)+h
8 [3 }2 \) a2 Z7 [/ U0 K% Y7 s5 Z- r' ^
    如果数据大小为一个字节,你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做?部分情况下可以,但是会另外增加复杂程度!如果data[0]
+ D2 q1 \' M4 a2 ?9 l) s! d3 f  N+ E: N# _
    还能再酸爽一点吗?当然可以了!RLP涉及两类“对象”:结构列表和字节数组。+ Q" r' L2 J0 B5 b/ C0 o

" H! l' p! U0 Y- ]1 c    字节数组:header=128,overflow_header=183
' ?; R0 a) K0 F$ u  F0 v3 Q7 l8 v7 O' a7 W+ V7 f
    结构列表:header=192,overflow_header=247. G% Q& S8 U3 l* h2 P" ^

, Y' l2 b9 U4 l: P& d    请注意,datasize部分的最大规模是8bytes,也就是一个$ ^( n% c8 B! D& L, W# z

! H4 b1 a- j( N* q    64bits(原文为“64-bytes”,应有误)的数字。确实,无论什么数据,18014398509481984KB应该都够用了。虽然还有很多棘手的细节有待深入,但要点看起来很清楚了:RLP难以驯服。我们再来看看它是如何与状态树交织在一起的。
! l# ^$ H; ?3 h7 o% u9 M, M5 j- ^( S4 ~7 k
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    10