RLP 编码

原文 @icattlecoder 以太坊源码学习—RLP 编码

RLP(Recursive Length Prefix)递归长度前缀编码，RLP 次要用于以太坊中数据的网络传输和长久化存储。

劣势

比 JSON 省空间，JSON 编码了过多冗余信息，上面有用信息只有 joy 和male

type Student struct {
    Name string `json:"name"`
    Sex string `json:"sex"`
}
s := Student{"joy", "male"}
marshal, _ := json.Marshal(s)
fmt.Println(string(marshal))
//{"name":"joy","sex":"male"}

编码规定

RLP 理论只给两种类型数据编码：

• byte 数组
• byte 数组的数组，称之为列表

规定 1

对于值在 [0,127] 之间的 单个字节，编码就是其自身

例 1：a 的编码是97

规定 2

如果 byte 数组长度 l <=55，编码的后果是，前缀（l+128），加数组自身

例 2：空字符串编码是128，即 128+0

例 3：abc 的编码是131 97 98 99，前缀是 128+3，前面是 abc 的编码

规定 3

如果 byte 数组的长度 l >55，前缀是（长度 l 的编码的长度）+183，而后是数组长度的编码，而后是 byte 数组的编码

例 4：编码上面这段字符串

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

字符串长度 l =86，86 的编码只须要一个字节，所以

前缀是 183+1=184

而后是 l 的编码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

例 5：编码一个反复 1024 次 ”a” 的字符串

字符串长度是 1024，长度的编码是 0x0400，占用两个字节，所以

前缀是 183+2=185

而后是长度编码4 0

而后是一长串 a 的编码97 97 97 ...

规定 4

如果列表长度小于 55，前缀是 192+ 列表各个元素长度总和，而后顺次链接各个子列表（递归定义）

例 6：编码列表[“abc”,”edf”]

对于 ”abc”，长度小于 55，前缀是 128+3=131，而后是 abc 的编码，一起就是131 97 98 99，共 4 个字节

对于 ”edf”，编码131 100 101 102，也是 4 字节

列表总长度是 8，所以前缀是 192+8=200，所以残缺的编码是200 131 97 98 99 131 100 101 102

规定 5

如果列表元素总长度超过 55，前缀是 247+（长度编码的长度），而后是长度编码，而后顺次是各个元素的编码（递归定义）

例子 7：编码["The length of this sentence is more than 55 bytes,", "I know it because I pre-designed it"]

第一个元素长度是 51，不是列表，实用规定 3，它的前缀是 128+51=179，而后是这个字符原本的编码，它的长度是 52 个字节

对于第二个元素前缀是 128+35=163，它的长度是 36 个字节

所以整个列表长度是 88 个字节，大于 55，对于整个列表，其前缀是 247+1（长度 86 占用一个字节）=248

而后是长度的编码88

而后顺次是各个元素的编码

最终编码后果如下：

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

例 8：上面是一个简单的，加深了解，编码

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

第一个元素的编码是 131 97 98 99，总长度4 个字节

第二个元素的第一个元素的编码是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，其前缀是 128+51=179，它编码后的长度是 52

第二个元素的第二个元素的编码是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，其前缀是 128+35=163，它编码后的长度是 36 个字节

第二个元素是列表，且其子元素总长度为 52+36=88 个字节，大于 55，实用规定 5，它的前缀是 247+1（88 占用一个字节）=248，而后是长度编码 88，而后顺次是两个子元素的编码，所以第二个元素 编码后 的总长度是 1（前缀 248 编码占用一个字节）+1（长度 88 编码占用一个字节）+88=90

所以整个列表各个子元素总长度为 4（第一个元素）+90（第二个元素）=94，对于整体来讲，是列表且长度 94>55，实用规定 5，其前缀是 247+1（长度 94 占用一个字节）=248，而后是长度编码94，而后顺次是各个元素编码，最终编码后果如下

248 94 131 97 98 99 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

解码规定

依据须要解码 byte 数组的第一个元素的值 v 判断

• v ∈ [0,128)，单个字节
• v ∈ [128,183)，长度小于等于 55 的 byte 数组
• v ∈ [183,192)，长度大于 55 的 byte 数组
• v ∈ [192,247)，长度不大于 55 的列表（递归）
• v ∈ [247,256)，长度大于 55 的列表（递归）

语言实现

各语言在实现 RLP 编码时，首先须要将对象映射成 byte 数组或者列表（byte 数组的数组），以 go 语言编码下面提到的 Student 对象（struct 类型）为例，其解决成列表的后果为"[joy", "male"]，最终 RLP 编码为[203 131 106 111 121 134 102 101 109 97 108 101]

如果是 map 类型，其解决成列表的模式如下

[["",""],["",""],["",""]]

试了以太坊如同不反对 map 类型编码