rlp

RLP简介

递归长度前缀（Recursive Length Prefix，RLP）编码是以太坊项目特别设计的一种编码方式，它的编码结果相比于JSON编码占用更少的存储空间，因为在JSON编码方式中，需要额外的字段名信息来组织编码内容。而在RLP编码里，则使用一种被称为前缀的字段来组织编码内容，这可以有效减少编码过程中产生的其他额外信息。

RLP编码结果由**编码前缀（Encoding Prefix，EP）和编码内容（Encoding content，EC）**两部分组成：

编码结果 := EP || EC

1. 类型标记位

在RLP编码中，EP由两部分组成，其中第一部分是占据1个字节存储空间的类型标记位（Type Marker Bit，TMB），它可被分为五种，对应RLP编码中处理的五种数据类型，如下所示：

• 0~127 | 0x0~0x7F：单个的ASCII码
• 128~183 | 0x80~0xB7：长度在56以内的string，即EC的长度小于56
• 184~191 | 0xB8~0xBF：长度大于55的string，即EC的长度大于55
• 192~247 | 0xC0~0xF7：编码结果的长度小于56的list，即EC的长度小于56
• 248~255 | 0xF8~0xFF：编码结果的长度大于55的list，即EC的长度大于55

在go语言中，上面提到的string我们可以将其简单理解为简单数据类型的变量，例如uint、string、byte等，而list我们可以将其理解为复合数据类型，例如struct等。值得注意的是，在go-ethereum里，[]byte和[num]byte被归类为string，而[]x和[num]x（其中x为非byte类型）被归类为list，另外，空接口，即interface{}也被归类为list。

当我们给定一个数据对象x，然后利用RLP编码技术对x进行编码，得到编码结果r，一般情况下，r的第一个字节存储的就是TMB，因此，我们可以根据TMB推断出x的数据类型。

2. 可选长度编码

前面我们介绍了EP由两部分组成，其中第一部分是类型标记位TMB，第二部分就是可选长度编码（Optional Length Coding，OLC）。当TMB的取值在184~191或248~255这两个区间内时，OLC才会出现在前缀里。根据观察TMB的取值范围和对应编码的数据类型时，我们发现，当TMB取值在128~183和192~247之间时，我们只需要TMB就可以求出EP后面紧跟着的EC的长度，例如我们利用RLP去编码一段长度为32的string，TMB将等于160，它的取值落在128~183之间，那么利用160减去128就可以得到EC长度等于32这个结论。其实，之所以EC的长度也等于32，是因为，对于string类型的数据，RLP对其编码得到的EC其实就是数据它本身。

到这里，我们可能会感受到，rlp是一种和数据类型以及数据长度息息相关的编码技术。

如果我们编码一个长度为1025的string类型数据，那么仅仅根据TMB就无法计算出EP后面跟着的EC有多长了，在这种情况下，我们需要OLC来辅助存储编码数据的长度。首先，RLP会先对1025进行长度编码，长度编码遵从大端编码规则（高位字节存储在低地址位），1025的二进制表现形式为[00000100,00000001]，其实这个1025的二进制表现形式就是它的长度编码结果，为了表示方便，我们用[4,1]来表示长度编码结果，即，如果我们编码一个长度为1025的string类型数据，那么EP中的OLC就等于[4,1]。现在我们先尝试组装一下编码结果，得到结果如下所示：

EP || EC $\rightarrow$ TMB || OLC || EC

当我们把这串数据发送给接收者后，接收者如何进行解码呢？我们知道，TMP只占据一个字节存储空间，因此接收者可以直接获得TMB，但是OLC具体占据多少字节存储空间则是未知的，接收者无法区分OLC和EC。基于这一点考虑，RLP将OLC的长度信息存储到了TMB中。

还以上面的例子为例，如果我们编码一个长度为1025的string类型数据，那么TMB的取值应当落在184~191之间，前面我们知道，1025的长度编码结果为[00000100,00000001]（简写为[4,1]），因此至少需要两个字节空间来存储1025的长度编码，换句话说，这个例子里的OLC长度为2，所以我们需要将2这个长度信息存储到TMB中，具体的存储方式如下：

TMB := 184 + (2 - 1) = 185

这样的话，接收者在拿到编码结果以后，根据TMB可以知道OLC的长度，获取到OLC的长度以后，就可将OLC与EC分隔开。根据TMB获取OLC的长度计算规则如下：

• if TMB $\in$ 184~191, then, length $\leftarrow$ TMB - 183
• if TMB $\in$ 248~255, then, length $\leftarrow$ TMB - 247

3. 递归编码

要理解递归编码这个概念，我们需要先理解list到底是什么，前面我们已经介绍过对string类型的数据进行编码，得到的EC就是数据本身，而对list类型的数据进行RLP编码，得到的EC还是数据本身吗？这里先说答案：不是。

我们给一个例子，例如我们对以下数据进行RLP编码：

x := []string{"abc", "def"}

x是一个字符串切片，根据前面对string和list数据类型的介绍，我们知道：x属于list数据类型，但是x里面存储的"abc"和"def"却是string数据类型，对string数据类型的编码结果等于EP连接上EC，EC就是数据本身，因此我们只需要计算EP是多少就行。

以"def"为例，它的长度等于3（EC的长度也等于3），因此EP将只含有TMB，不含有OLC，所以EP=TMB=128+3=131，将EP和EC进行组合，得到：[131 100 101 102]，其中100、101和102分别是'a'、'b'和'c'的ASCII码值。

同理，对"abc"进行RLP编码，得到结果：[131 97 98 99]。

x内部元素RLP编码结果已知，现在需要返回到list这一层，对x进行编码，对x进行RLP编码，得到的编码结果中的EC等于什么呢？实际上，EC就等于"abc"和"def"的编码结果“之和”：[131 97 98 99 131 100 101 102]，那么EC的长度我们就可以求得等于8，根据TMB和不同数据类型的对应关系，我们可以推断TMB的取值应当落在192~247之间，且根据OLC的出现条件，我们可以判断此处EC和TMB可以划等号，所以EC=TMB=192+8=200，所以，x最终的编码结果为：[200, 131 97 98 99 131 100 101 102]。

上面的例子可能还不能很好地体会到递归的精髓，下面给一个新的例子：

x := []interface{}{[]interface{}{}, [][]interface{}{{}}}

它的RLP编码结果为：[195 192 193 192]。

对上面编码结果如果存在疑问，可以查看源码，其中空接口的编码方式如下：

if val.IsNil() {
	buf.str = append(buf.str, 0xC0)
	return nil
}

4. 结构体中的编码规则

rlpstruct\rlpstruct.go文件里定义了使用RLP编码如何对用户自定义的数据结构进行编解码的方式，通过为结构体字段的tag设置不同的rlp标签，可以实现若干种编解码方式。go-ethereum定义了一个Tags结构体来维护结构体字段的rlp标签，如下所示：

type Tags struct {
    NilKind NilKind
    NilManual bool
    Optional bool
    Tail bool
    Ignored bool
}

• NilKind字段定义了结构体字段的空值编码规则：NilKindString或NilKindList。

• NilManual如果设置为true，则表明结构体字段的空值编码规则被手动设置为：rlp:"nil"、 rlp:"nilString"或 rlp:"nilList"。

• Optional用来表示该字段的rlp标签是否被设置成rlp:"optional"，如果某个结构体定义了4个可导出的字段，并且在第二个字段的rlp标签里设置了rlp:"optional"，那么第三和第四个字段的tag里也必须要设置rlp:optional，除非第四个字段是一个切片，并且它的rlp标签已经被设置为rlp:"tail"，那么这第四个字段的tag就不能设置为rlp:"optional"。给结构体的字段的rlp标签设置成optional具有以下作用呢：当我们对结构体进行编码时，如果从某个字段开始往后所有字段的tag都被设置成optional，且这些字段中存在违未被始化的情况，，它会遵循以下规则进行编码：排在最后一个rlp标签为optional且值为非零值的字段前面的字段（包括该字段），不管它们的rlp标签有没有设置为optional，也不管它们的值是否等于零值，这些字段都将参与编码，而排在后面的值为零值的字段，这些字段由于它们的rlp标签一定被设置成optional，且它们的值在运行时阶段是零值，所以它们将不参与编码，下面给一个例子做为说明：

  type People struct {
      Name string
      Age uint8 `rlp:"optional"`
      Son *People `rlp:"optional"`
      Daughter *People `rlp:"optional"`
  }
  var p1 People = People{Name: "Tom", Age: 35, Daughter: &People{Name: "Lina", Age: 8}}
  // 由于People的第二、三、四3个字段的tag都被设置成optional，所以当对p1进行编码时，因为最后一个非零值字段是Daughter，所以排在它前面的字段（包括Son字段，尽管它的值等于零值）包括它自己（Daughter字段）都会被编码，所以编码结果如下：
  // [205 131 84 111 109 35 192 198 132 76 105 110 97 8]
  var p2 People = People{Name: "Tom", Son: &People{Name: "David", Age: 10}}
  // 我们对p2进行编码，发现p2最后一个非零字段是Son，尽管它前面的Age字段是零值，但是它排在Son前面，所以依然会被编码，而Daughter字段为零值，且排在Son
  // 之后，所以不会被编码，那么编码结果就如下所示：
  // [205 131 84 111 109 128 199 133 68 97 118 105 100 10]
  

• Tail字段用来表示该字段的rlp标签是否被设置成rlp:"tail"，RLP编码规则规定：在任何自定义结构体中，只有最后一个可导出字段，且该字段还必须是切片类型，才能给该字段的rlp标签设置成rlp:"tail"，这也映证了Tail的中文含义。那么它的作用是什么呢？根据RLP的编码规则，我们知道那些元素类型为非byte类型的切片或者数组会被当成列表进行编码，并且在go代码中，切片或者数组里的所有元素类型必须统一，那么如果我们给结构体的最后一个字段的rlp标签设置成tail，在编码时，会将该字段“拆开看”，所谓拆开看就是不会将该字段看成一个整体：list，而是会逐一对该字段所表示的切片里的元素进行编码，例如下面给出了两个示例：

  // 示例1
  type class struct {
  	ClassID  uint8
  	Students []string `rlp:"tail"`
  }
  var c class = class{ClassID: 3, Students: []string{"abc", "def"}}
  // 由于此时我们给class结构体的Students字段的tag设置成tail，所以在编码时，会将其拆开看，不会将其看成整体一个，也就是说在编码时是会把class结构体看
  // 成如下的结构体：
  // type class struct {
  //     ClassID  uint8
  //     Student1 string
  //     Student2 string
  //     Student3 string
  //     ...
  // }
  // 所以对上面的c进行编码的结果是：[201 3 131 97 98 99 131 100 101 102]
  // 而如果我们把Students字段的tag里的tail去掉，编码结果则变为：[202 3 200 131 97 98 99 131 100 101 102]，将其作为一个列表（整体）进行编码
  

  // 示例3
  type class struct {
  	ClassID  uint8
  	Students []string `rlp:"tail"`
  }
  var c class = class{ClassID: 3}
  // 对c进行编码，因为c里面并没有初始化Students字段，所以它的值等于零值，又因为Students的tag被设置为tail，所以不会将其看成一个列表在对其进行编码，
  // 仅仅是将其看成若干个连续的string类型的字段，所以对c的编码结果为：[193 3]
  // 而如果我们把Students字段的tag里的tail去掉，编码结果则变为：[194 3 192]，因为此时会将Students字段看成是一个整体（列表），空列表的编码结果为
  // 0XC0
  

• Ignored字段用来表示该字段的rlp标签是否被设置成rlp:"-"，如果被设置成rlp:"-"，那么该字段在编码时会被直接忽略，不参与编码，例如下面给出了一个代码示例：

  type student struct {
  	Name  string
      Age   uint8 `rlp:"-"`
  	Birth string
  }
  var s student = student{Name: "abc", Age: 18, Birth: "def"}
  // 比如上面给出了一个结构体student，该结构体内定义了一个学生的姓名、年龄和出生日期，一般来说，我们对数据进行编码是为了进行网络传输或者文件存储，为了
  // 减小网络开销，我们提倡只编码有用的数据，例如在这个例子里，当我们知道一个学生的出生日期，那么就可以推出该学生的年龄，所以我们忽略对student结构体的
  // Age字段进行编码，那么对s进行编码的结果是：[200 131 97 98 99 131 100 101 102]
  // 如果我们将Age字段的tag里的“-”给去掉，编码结果则变为：[201 131 97 98 99 18 131 100 101 102]
  

总结下来，利用rlp编码规则对自定义结构体进行编码，我们可以在结构体字段的tag里设置以下种编码标记：

• rlp:"nil"
• rlp:"nilString"
• rlp:"nilList"
• rlp:"optional"
• rlp:"tail"
• rlp:"-"

5. 案例

5.1 编码bool类型数据

5.2 编码无符号整数

5.3 编码大整数

5.4 编码字节数组

5.5 编码字节切片

5.6 编码字符串

5.7 编码非字节切片

5.8 编码结构体

type simplestruct struct {
	A uint
	B string
}

type recstruct struct {
	I     uint
	Child *recstruct `rlp:"nil"`
}

type intField struct {
	X int
}

type ignoredFiled struct {
	A uint
	B uint `rlp:"-"`
	C uint
}

type tailStruct struct {
	A    uint
	Tail []RawValue `rlp:"tail"`
}

type optionalFields struct {
	A uint
	B uint `rlp:"optional"`
	C uint `rlp:"optional"`
}

type optionalAndTailField struct {
	A    uint
	B    uint   `rlp:"optional"`
	Tail []uint `rlp:"tail"`
}

type optionalBigIntField struct {
	A uint
	B *big.Int `rlp:"optional"`
}

type optionalPtrFiled struct {
	A uint
	B *[3]byte `rlp:"optional"`
}

type optionalPtrFieldNil struct {
	A uint
	B *[3]byte `rlp:"optional,nil"`
}

6. 注意

遗憾的是，目前乙太坊官方实现的RLP编码还无法随心所欲地对任何自定义数据类型进行编解码，比如在下面的这个例子里，有一个数据结构如下所示：

type Dog struct {
	Child *Dog
	Name string
}

然后我们实例化一个*Dog：

d := &Dog{Child: &Dog{Name: "bb", Child: nil}, Name: "aa"}

接着我们对其进行编码：

bz, _ := EncodeToBytes(d) // bz: [200 196 192 130 98 98 130 97 97]

再然后我们对编码结果进行解码：

dst := &Dog{}
err := DecodeBytes(bz, dst)

程序运行到这里，会报错：

*&rlp.decodeError{msg:"too few elements", typ:(reflect.rtype)(0x6ddba0), ctx:[]string{".Child", ".Child", "(rlp.Dog)"}}

那么上面的问题如何解决呢？其实我们只需要在定义Dog结构体时做一点调整就可以了，如下所示：

type Dog struct {
	Name  string
	Child *Dog `rlp:"optional"`
}