二叉状态树的结构，Part-1 摘要：二进制状态树如何解决

摘要：二进制状态树如何解决 RLP 编码带来的复杂性过去几个月来，我一直致力于将 trie 从十六进制树结构过渡到二进制树结构。我已经写了一篇关于如何转换状态树格式的文章（中文译本），但是没有完全说明状态树的结构。我将撰写一系列文章来探讨设计新结构时需要做出哪些权衡。本文是该系列的第一篇。
在设计十六进制 trie 时，一些设计选择在当时听起来很棒，但是经过 5 年的实践，被证明带来了很多复杂性。鉴于 ETH 1.x 想要转向二进制 trie ，我们正好可以借此机会研究一下状态的存储方式。
问题的根源在重新设计存储格式时，我们至少可以从 5 个方面进行改进。

将账户 trie 和存储 trie 合并：维护多个结构会增加复杂性，典型的例子就是节点必须先遍历账户 trie ，得到存储 trie 的根，然后再到存储 trie 上获取数据。
扩展节点（extension nodes）：这是一种特殊的节点，负责给特定子树上的所有 key 加上前缀。这些节点的作用是能够限制需要被哈希的节点数量，但是也引入了复杂性，因为它们所涉及的 key 必须以特定方式打包。
RLP 编码格式旨在高效地对任意结构进行编码。由于其复杂性，它也带来了很多麻烦：必须费尽千辛万苦打包 key 块（pack key chunk）。另外，由于每个节点的结构相当固定，可以使用更简单的序列化方法来代替 RLP 。
与前两个问题相关的是，十六进制的前缀也会带来复杂性和混乱。
十六进制 trie 的证明【即， “见证数据（witness）”】比二进制 trie 的证明大 4 倍左右。（欲知详情，请阅读这篇文章。（中文译本））

RLP —— Ramble, Lose yourself and Pester?
（译者注：“RLP” 是 “Recursive Length Prefix（递归长度前缀）” 的缩写，但作者这里使用了几个 R、L、P 开头的词 “漫无目的、迷失自我、喋喋不休” ，就是批评之意。）
本文我们会讨论怎么解决 RLP 问题。如果 RLP 被取代，绝大多数核心开发者都不会感到伤心。这是因为 RLP 过于复杂。实际上，我听过的唯一一个支持保留 RLP 的理由是：“RLP 实在太过复杂，不要再冒险选择新的格式了，以免重蹈覆辙。 ”
RLP 的基本原理是采用简单的 size + data格式。这就是复杂性的由来。首先， size 可以是任何整数（实际上，它不可能超过 2 字节，但是从原则上来说是可以的，因此你必须确保能够支持超过 2 字节的 size）。我们如何知道 size 部分在哪里结束， data 部分在哪里开始？

在大多数情况下，开头会加上一个 header 。这个 header 是一个值 h ，然后再加上 size 值：因此， RLP 编码是[length(data)+h] [data]
如果 length(data)+h < 256 ，则 RLP 编码如上所示。如果数据太大，加上h值后超过一个字节，该怎么办？没错，你还需要再增加一个字节，即，引入h'值来表示你正在使用第二种存储方案。在这种情况下， RLP 编码是[h'+length(length(data))] [length(data)] [data] 。为 “方便” 起见， h'被选定为 56 。
如果数据大小为一个字节，你发现自己必须在这个字节前再增加一个字节。有没有可能不这样做？部分情况下可以，但是会另外增加复杂程度！如果 data[0]< h ，那就不需要增加 header 。相应地，任何以小于h的值作为开头的字节负载必定只有一个字节。

还能再酸爽一点吗？当然可以了！RLP 涉及两类 “对象”：结构列表和字节数组。

字节数组：header=128 ， overflow_header=183
结构列表：header=192 ， overflow_header=247

请注意， data size 部分的最大规模是 8 bytes ，也就是一个 64 bits （原文为 “64-bytes” ，应有误）的数字。确实，无论什么数据， 18014398509481984 KB 应该都够用了。
虽然还有很多棘手的细节有待深入，但要点看起来很清楚了：RLP 难以驯服。我们再来看看它是如何与状态树交织在一起的。
默克尔化规则（Merkelization rule）我们怎么把 RLP 编码和它那令人厌烦的逻辑用到我们的默克尔化规则中？先从默克尔树底部的叶子节点开始说起。
叶子节点及其十六进制前缀叶子节点保存了一个值（value），在这个值前面还有一个不知道多少位的键（key），这个键跟其它叶子节点的键肯定是不一样的。因此，我们有了一个元组（key, value） ，这就是一个包含两个元素的列表，包含了