Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

二叉状态树的结构

有个胖子他姓杨
129 0 0
    在设计十六进制trie时,一些设计选择在当时听起来很棒,但是经过5年的实践,被证明带来了很多复杂性。鉴于ETH1.x想要转向二进制trie,我们正好可以借此机会研究一下状态的存储方式。
! V4 f1 J. ^, z, f8 s1 Z7 Q6 Z6 X- r( p2 q( @+ B6 z  i
    问题的根源
. E! I& L# r4 `1 G( u) U

0 x+ O3 P* A- G- e    在重新设计存储格式时,我们至少可以从5个方面进行改进。8 X2 r) [8 S  Z7 P" x# p0 q- n
# q, }; G& W% `) Z$ Y/ {( \
    将账户trie和存储trie合并:维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户7 n' Z% F/ W3 a) X( d) B8 \
" @" p; P+ y5 n) b7 x6 o
    trie,得到存储trie的根,然后再到存储trie上获取数据。
1 G: \9 ^" L' |7 e: Y$ T# L8 ^  B3 I7 \0 s, R" g( F0 R/ S* z5 f
    扩展节点(extensionnodes):这是一种特殊的节点,负责给特定子树上的所有key加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的key必须以特定方式打包。
. ?  S3 [- O2 C  X) u* P* E
" h! I& Q& I$ G    RLP编码格式旨在高效地对任意结构进行编码。由于其复杂性,它也带来了很多麻烦:必须费尽千辛万苦打包key块(packkeychunk)。另外,由于每个节点的结构相当固定,可以使用更简单的序列化方法来代替RLP。, T: O: u) O- U( S

7 i& Z! R4 ?0 g1 i' e8 W4 \    与前两个问题相关的是,十六进制的前缀也会带来复杂性和混乱。
4 H* C/ j: [3 G' K9 f4 }1 Z  W3 i' K% ~4 }/ D* e7 e
    十六进制trie的证明【即,“见证数据(witness)”】比二进制trie的证明大4倍左右。(欲知详情,请阅读这篇文章。(中文译本))
& O% o7 C( ^+ }1 W8 L4 J4 G7 \9 k2 @4 y
    RLP
' ^2 b1 w. c4 u* ?$ D, u- O5 g* l& Q9 J  V& q7 ~
    ——Ramble,LoseyourselfandPester?6 o9 M: w' t/ N/ X/ x, B
% u- n" i+ q. |  W
    (译者注:“RLP”是“RecursiveLengthPrefix(递归长度前缀)”的缩写,但作者这里使用了几个R、L、P开头的词“漫无目的、迷失自我、喋喋不休”,就是批评之意。)本文我们会讨论怎么解决RLP问题。如果RLP被取代,绝大多数核心开发者都不会感到伤心。这是因为RLP过于复杂。实际上,我听过的唯一一个支持保留RLP的理由是:“RLP实在太过复杂,不要再冒险选择新的格式了,以免重蹈覆辙。”RLP
% O3 \$ F3 F! E2 c$ X$ q" z% H3 o
, f' N% G, N% V' [3 W    的基本原理是采用简单的size+data格式。这就是复杂性的由来。首先,size可以是任何整数(实际上,它不可能超过2字节,但是从原则上来说是可以的,因此你必须确保能够支持超过23 |1 z" ~* I, E$ m# x! R
( |, F3 s- \7 l  d) y
    字节的size)。我们如何知道size部分在哪里结束,data部分在哪里开始?
3 [- J' Z" o0 l2 d  M& \; F
) c7 ^6 ]- `% d  m0 v  T    在大多数情况下,开头会加上一个header。这个
0 X  ~, B- z* J( O" k! P5 p" C. O1 d& t( |
    header是一个值h,然后再加上size值:因此,RLP编码是[length(data)+h][data]
$ Y6 ]% f" O  _; d9 M5 k0 U% i. u2 P
    如果length(data)+h4 q) `3 |3 s% a* O6 O! L& s

7 u& ~% N! R  `& L5 v# ?+ x    如果数据大小为一个字节,你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做?部分情况下可以,但是会另外增加复杂程度!如果data[0]0 V* M% K7 S1 H" c5 O$ V

5 x. Z5 J6 |7 f$ F    还能再酸爽一点吗?当然可以了!RLP涉及两类“对象”:结构列表和字节数组。7 {9 J- p$ _  d: t

; P& I3 p$ K8 T0 B0 W    字节数组:header=128,overflow_header=1837 @) f. a* B! G' z6 V% ]# o8 x. U, N
6 h6 o0 d% Y4 j  a( W0 Z4 y
    结构列表:header=192,overflow_header=247
; @8 k1 n1 [6 w) ~9 \4 T7 |3 x' o( _1 D- t( E, D
    请注意,datasize部分的最大规模是8bytes,也就是一个. Y2 n/ ~0 l3 j9 o7 F1 F

2 N8 ]. S& Q2 O    64bits(原文为“64-bytes”,应有误)的数字。确实,无论什么数据,18014398509481984KB应该都够用了。虽然还有很多棘手的细节有待深入,但要点看起来很清楚了:RLP难以驯服。我们再来看看它是如何与状态树交织在一起的。1 h: \" p+ b8 G$ I& {' x% h6 U% X# e% @

8 A- M* z: H6 T  G7 |
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    10