以太坊RLP编码原理

RLP编码是什么

  RLP(Recursive Length Prefix,递归的长度前缀)是一种编码规则,主要用来序列化/反序列化数据,可用于编码任意嵌套的二进制数组数据。
  RLP编码是以太坊数据序列化的主要编码方式,具有较好的数据处理效率,尤其是将长度和类型统一作为前缀,实际上RLP是基于ASCII编码的一种结构化扩充,既能表示长度还能表示类型,是一种非常紧凑的结构化编码方案。区块、交易等数据结构在持久化时会先经过RLP编码后再存储到数据库中。
  RLP的唯一目标就是解决结构体的编码问题;对原子数据类型(比如,字符串,整数型,浮点型)的编码则交给更高层的协议;以太坊中要求数字必须是一个大端字节序的、没有零占位的存储的格式(也就是说,一个整数0和一个空数组是等同的)。
  对于在RLP格式中对一个字典数据的编码问题,有两种建议的方式,一种是通过二维数组表达键值对,比如[[k1,v1],[k2,v2]...],并且对键进行字典序排序;另一种方式是通过以太坊文档中提到的高级的基数树编码来实现。

RLP编码的优势

对象序列化方式又很多,比如常见的JSON格式,但是这些编码方式显示更直观,结构却不够紧凑,不是合适用来存储,例如json

1
2
3
4
5
6
7
8
type Student struct{
Name string `json:"name"`
Sex string `json:"sex"`
}
s := Student{Name:"cateria",Sex:"male"}
bs,_ := json.Marsal(&s)
print(string(bs))
// {"name":"icattlecoder","sex":"male"}

变量s序列化的结果是{"name":"icattlecoder","sex":"male"},字符串长度35,实际有效数据是cateria和male,共计16个字节,我们可以看到JSON的序列化时引入了太多的冗余信息,这就会导致存储时占用空间太大。所以,以太坊需要设计一种结果更小的编码方法。

RLP编码定义

RLP编码只处理两类数据:一类是字符串(字节数组),一类是列表。

  1. 字符串,指的是一串二进制数据,
  2. 列表,是一个嵌套递归的结构,里面可以包含字符串和列表,例如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]就是一个复杂的列表。
    其他类型的数据需要转成以上的两类,转换的规则不是RLP编码定义的,可以根据自己的规则转换。例如struct可以转成列表,int可以转成二进制(属于字符串一类),以太坊中整数都以大端形式存储。

RLP编码方式的特点:

  1. 递归,被编码的数据是递归的结构,编码算法也是递归进行处理的;
  2. 长度前缀,也就是RLP编码都带有一个前缀,这个前缀是跟被编码数据的长度相关的,从下面的编码规则中可以看出这一点。

RLP编码规则

  1. 规则一:对于单个字节,如果它的值范围是[0x00, 0x7f],它的RLP编码就是它本身。这里面需要注意的是0x7f这个边界,因为ASCII编码最大值就是0x7f,也就是说在0x7f以内完全当做ASCII编码使用。
  2. 规则二:如果一个字符串的长度是0-55字节,它的RLP编码包含一个单字节的前缀,后面跟着字符串本身,这个前缀的值是0x80加上字符串的长度。由于被编码的字符串最大长度是55=0x37,因此单字节前缀的最大值是0x80+0x37=0xb7,即编码的第一个字节的取值范围是[0x80, 0xb7]
  3. 规则三:如果字符串的长度大于55个字节,它的RLP编码包含一个单字节的前缀,后面跟着字符串的长度,后面再跟着字符串本身。这个前缀的值是0xb7加上字符串长度的二进制形式的字节长度,说的有点绕,举个例子就明白了,例如一个字符串的长度是1024,它的二进制形式是10000000000,这个二进制形式的长度是2个字节,所以前缀应该是0xb7+2=0xb9,字符串长度1024=0x400,因此整个RLP编码应该是\xb9\x04\x00再跟上字符串本身。编码的第一个字节即前缀的取值范围是[0xb8, 0xbf],因为字符串长度二进制形式最少是1个字节,因此最小值是0xb7+1=0xb8,字符串长度二进制最大是8个字节,因此最大值是0xb7+8=0xbf
  4. 规则四:如果一个列表的总长度(列表的总长度指的是它包含的项的数量加它包含的各项的长度之和)是0-55字节,它的RLP编码包含一个单字节的前缀,后面跟着列表中各元素项的RLP编码,这个前缀的值是0xc0加上列表的总长度。编码的第一个字节的取值范围是[0xc0, 0xf7]
  5. 规则五:如果一个列表的总长度大于55字节,它的RLP编码包含一个单字节的前缀,后面跟着列表的长度,后面再跟着列表中各元素项的RLP编码,这个前缀的值是0xf7加上列表总长度的二进制形式的字节长度。编码的第一个字节的取值范围是[0xf8, 0xff]

例子分析:

  1. 15('\x0f') = 0x0f (规则一)
  2. 空字符串 "" = 0x80 (规则二)
  3. 字符串 "dog" = [0x83, 'd', 'o', 'g' ] (规则二)
  4. 1024('\x04\00') = [0x82, 0x04, 0x00] (规则二)
  5. 字符串 "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't'](规则三)
  6. 空列表 [] = [0xc0] (规则四)
  7. 列表 ["cat","dog"] = [0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ] (规则四)

总结

  通过上述的案例分析我们可以看出RLP的设计思想,就是通过首字节快速判断一串编码的类型,充分利用了一个字节的存储空间,将0x7f以后的值赋予了新的含义,以往我们见到的编码方式主要是对指定长度字节进行编码,比如Unicode等,在处理这些编码时一般按照指定长度进行拆分解码,最大的弊端是传统编码无法表现一个结构,就是本文说的列表,RLP最大的优点是在充分利用字节的情况下,同时支持列表结构,也就是说可以很轻易的利用RLP存储一个树状结构。
  程序处理RLP编码时也非常容易,根据首字节就可以判断出这段编码的类型,同时调用不同的方法进行解码,如果您熟悉jason这种结构,会发现RLP很类似,支持嵌套的结构,通过递归调用可以将整个RLP快速还原成一颗树,或者转译成一个jason结构,便于其他程序使用。
  RLP使用首字节存储长度的位数,再用后续的字节表明整体字符串的长度,根据规则二计算,RLP可以支持的单个最大字符串长度为2的64次方,这无疑是个天文数字,再加上嵌套规则,所以理论上RLP可以编码任何数据。

JouyPub wechat
欢迎订阅「K叔区块链」 - 专注于区块链技术学习