以太坊 RLP编码

RLP（Recursive Length Rrefix）就是递归长度前缀编码，它提供了一种适用于任意数据和数组的二进制编码方法。

RLP 是以太坊对象进行序列化的主要编码方式，主要用于以太坊中数据的网络传输和持久化存储。

1. 为什么使用 RLP 编码

对象序列化方法有很多种，比如常见的 JSON 编码，但是 JSON 缺点很明显，它的编码结果体积比较大。

例如：

type Student struct{
    Name string `json:"name"`
    Sex string `json:"sex"`
}
student := Student{Name:"aizws",Sex:"male"}
result,_ := json.Marsal(&student)
print(string(result))

// 输出结果：{"name":"aizws","sex":"male"}

变量 student 序列化的结果是 {"name":"aizws","sex":"male"}，字符串长度 33，实际有效数据是 aizws 和 male，共计 13 个字节，我们可以看到 JSON 的序列化时引入了太多的冗余信息。假设以太坊采用 JSON 来序列化，那么本来 50G 的区块链数据可能现在就要 100G。所以，以太坊设计了一种体积更小的编码方法 RLP。

2.  RLP 编码定义

RLP 编码的定义只处理两类数据：一类是字符串（例如字节数组），一类是列表。字符串指的是一串二进制数据，列表是一个嵌套递归的结构，里面可以包含字符串和列表，例如：["cat",["puppy","cow"],"pig",[""],"sheep"] 就是一个复杂的列表。

所有类型的数据需要转成以上的两类，转换的规则不是 RLP 编码定义的，可以根据自己的规则转换，例如：原子数据类型（比如：字符串，整数型，浮点型）可以转成二进制，它们属于字符串类。struct、map 等类型可以转成列表。另外，以太坊中的整数都以大端形式存储。

从RLP编码的名字可以看出它的特点：

• 递归：被编码的数据是递归的结构，编码算法也是递归进行处理；
• 长度前缀：RLP编码都带有一个前缀，这个前缀与编码数据的长度相关联。

3.  RLP 编码规则

规则1：

对于值在[0, 127] 之间的单个字节，其编码是其本身，即前缀为空。

例1：字符 'a' 的编码是 97。

规则2：

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

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

例3：abc编码结果是 131 97 98 99，其中：131=128+len("abc")，97 98 99 依次是a b c。

规则3：

如果数组长度 l > 55， 编码结果先是 183 加数组长度编码的长度，然后是数组长度本身的编码，最后是byte数组的编码。

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

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

这段字符串共 86 个字节，而 86 的编码只需要一个字节，那就是 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 = 183 + 1，因为数组长度 86 编码后仅占用一个字节。

第二个字节 86 ，这是数组长度。

第三个字节 84，这是字符 T 的编码。

例5：编码一个重复 1024 次 "a" 的字符串，其结果为：185 4 0 97 97 97 97 97 97 ...。

其中 1024 的编码为0x0400，长度为 2，因此：185 = 183 + 2。

规则 1~3 定义了 byte 数组的编码方案，下面介绍列表的编码规则。在此之前，我们先定义列表长度是指子列表编码后的长度之和。

规则4：

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

注意规则 4 本身是递归定义的。

例6：["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。

规则5：

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

规则5本身也是递归定义的，和规则3相似。

例7：

["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。

例8：最后我们再来看个稍复杂点的例子以加深理解递归长度前缀。

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

编码结果：

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 

列表第一项字符串abc根据规则2，编码结果为131 97 98 99,长度为4。 列表第二项也是一个列表项：

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

根据规则5，编码结果：

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

内容长度为 90，因此，整个列表的编码结果第二位是 90 + 4 = 94, 占用1个字节，第一位 247 + 1 = 248。

以上 5 条就是 RLP 的全部编码规则。

4. RLP 编码代码

编程语言在具体实现 RLP 编码时，首先需要将对像映射成 byte 数组或列表两种形式。以 go 语言编码 struct 为例，会将其映射为列表，例如 Student 这个对象处理成列表 ["aizws","male"]：

package main

import (
  "bytes"
  "fmt"
  "github.com/ethereum/go-ethereum/rlp"
)

type Student struct{
    Name string
    Sex string
}

func main() {
  s := Student{Name:"aizws",Sex:"male"}
  buff := bytes.Buffer{}
  rpl.Encode(&buff, &s)
  fmt.Println(buff.Bytes())
  //输出结果： [207 137 99 111 100 101 98 97 111 107 117 132 109 97 108 101]
}

5. RLP 解码流程

解码时，首先根据编码结果第一个字节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。递归使用规则1~4进行解码。
• 如果f∈(247,256]，那么它是编码后长度大于55的列表，其长度本身的编码长度ll=f-247,然后从第二个字节读取长度为ll的bytes,按BigEndian编码成整数l，l即为子列表长度。然后递归根据解码规则进行解码。

RLP 名字本身很好的解释了编码规则。