简述

RLP(Recursive Length Prefix)，中文翻译过来叫递归长度前缀编码，它是以太坊序列化所采用的编码方式。RLP主要用于以太坊中数据的网络传输和持久化存储。
为什么要说这个东西，因为ETH在构建状态树的时候，使用到了这个编码，有比较强的关联性。

为什么要有RLP这种编码?

是为了通用性，使数据成为平台无关性的数据。

递归长度前缀的目的在于，对任意嵌套的二进制数据数组进行编码，而递归长度前缀是用于序列化以太坊执行层中对象的主要编码方法。 递归长度前缀的唯一目的是对结构进行编码；而对特定数据类型（例如字符串、浮点数）进行编码的工作，则留给高阶协议；但正递归长度前缀整数必须以不带前导零的大端序二进制形式表示（从而使整数值零相当于空字节数组）。 带有前导零的反序列化正整数被视为无效。 字符串长度的整数表示也必须以这种方式编码，有效载荷中的整数也是如此。

意思就是说，底层存储的数据要保持一致，如果通过别的工具序列化出来的二进制数据，具有平台相关性，所以索性自己规定一种编码格式，上层使用者，自行解码。

编码

RLP主要用于以太坊中数据的网络传输和持久化存储。
分四种情况：
1.单一字节
2.字符串长度小于: 56
3.字符串长度大于: 55
4.针对列表编码

单一字节长度

单一字节 如果其值介于[0x00, 0x7F]之间, 则保持不变(0-127)
0x7f：表示的是一个十六进制数7F，即十进制127
对于值在[0, 127]之间的单个字节，其编码是其本身。
举个例子：
a的编码是97。其对应的就是ASCII码。

1
a = [97]

取值范围

[0x00, 0x7f]（十进制 [0, 127]）范围内的单个字节，该字节即是它自己的递归长度前缀编码。

字符串长度小于56，前缀 128+ len

第二种情况，字符串长度小于56，则需要添加一个字节做为前缀，该前缀的值是0x80+该字符串的长度。
0x80+：对应10进制128。
这里说的长度，是指byte[]的len。

如果byte数组长度len <= 55，编码的结果是数组本身，再加上128 + len 作为前缀。

举个例子：

有一个字符串：abc，对它进行编码，abc 编码结果是

1
"abc" = [131 97 98 99]

解释一下上面的结果：
1.131是怎么来的。如果超过一个字节且长度 <= 55，必须多一位前缀用来记录长度，这个是人家的规则。abc分别占3个字节。
2.131 = 128 + len("abc")。
3.97 98 99依次是: a b c。

后面的编码也就基本套着这个规则。

取值范围

如果字符串的长度为 0-55 个字节，则递归长度前缀编码包含一个值为 0x80（十进制 128）的单字节，加上该字符串之后字符串的长度。 因此，第一个字节的范围是 [0x80, 0xb7]（十进制 [128, 183]）。

3.如果数组长度大于55

这个跟前面有点不一样，会再多一个位置：
1.编码结果第一个是183加数组长度的编码的长度
2.然后是数组长度的本身的编码最后是byte数组的编码
3.最后是byte数组的编码。

官方文档的例子以16进制表示，看着别扭，我找了一个10进制表示的例子。

编码下面这段字符串：

The length of this sentence is more than 55 bytes, I know it because I pre-designed it

这段字符串共86个字节，包含空格。

注意结果的前两位，有迷惑性

184 86 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前三个字节的计算方式如下：

184: 由前一位的长度计算得来的，因为数组长度86编码后仅占用一个字节，所以 184 = 183 + 1。后面会再给个例子。
86: 即数组长度86
84: 是上面字符串中，首个字母T的编码

再看个例子

编码一个重复1024次"a"的字符串，其结果为：

185 4 0 97 97 97 97 97 97 ... 97。

1024长度编码后为：0x40 0x00，省略掉前面的零，长度为2，因此185 = 183 + 2。

列表

如果列表长度小于55

如果列表长度小于55，编码结果第一位是192加列表长度的编码的长度，然后依次连接各子列表的编码。

例如：
["abc", "def"] = [200 131 97 98 99 131 100 101 102]

其中，"abc"的编码为：131 97 98 99，"def"的编码为：131 100 101 102。
两个子字符串的编码后总长度是8，因此编码结果第一位计算得出：192 + 8 = 200。

192是怎么来的？

如果列表的总有效载荷长度（即其所有经过递归长度前缀编码的项目的组合长度）为 0-55 个字节，则递归长度前缀编码包含一个值为 0xc0 的单字节，加上列表长度，后跟一串项目递归长度前缀编码。 因此，第一个字节的范围是 [0xc0, 0xf7]（十进制 [192, 247]）。

如果列表长度超过55

如果列表长度超过55，编码结果第一位是247加列表长度的编码长度，然后是列表长度本身的编码，最后依次连接各子列表的编码。

举个例子：
这段数据，两个元素双眼号内的数据包含空格是86个字符

["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]

编码结果是:

248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前两个字节的计算方式如下：

说明：

248 = 247 + 1
88 = 86 + 2，在规则3的示例中，长度为86，而在此例中，由于有两个子字符串（就是两个数组元素），每个子字符串本身的长度的编码各占1字节，因此总共占2字节。
第3个字节179依据规则2得出179 = 128 + 51
第55个字节163同样依据规则2得出163 = 128 + 35

如果列表的总有效载荷长度超过 55 个字节，则递归长度前缀编码包含一个值为 0xf7 的单字节，加上二进制格式的有效载荷长度的以字节为单位的长度，后跟有效载荷的长度，然后是项目递归长度前缀编码串。 因此，第一个字节的范围是 [0xf8, 0xff]（十进制 [248, 255]）。

总结

对面上的例子做一个总结，第一个字节f的大小

首字节大小 类型 长度
f∈ [0,128) 字节 一个字节本身
f∈[128,184) 数组 长度不超过55的byte数组，数组的长度为 l=f-128
f∈[184,192) 数组 一个长度超过55的数组，长度本身的编码长度ll=f-183,然后从第二个字节开始读取长度为ll的bytes，按照BigEndian编码成整数l，l即为数组的长度。
f∈(192,247] 数组 一个编码后总长度不超过55的列表，列表长度为l=f-192
f∈(247,256] 数组 编码后长度大于55的列表，其长度本身的编码长度ll=f-247,然后从第二个字节读取长度为ll的bytes,按BigEndian编码成整数l，l即为子列表长度。然后递归根据解码规则进行解码。

以上解释了什么叫递归长度前缀编码，这个名字本身很好的解释了编码规则。

RLP编码的话，大至就是这样，重点要了解它在构建状态树时，是如何使用的。

参考文档

https://ethereum.org/zh/developers/docs/data-structures-and-encoding/rlp