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类型编码