以太坊RLP编码原理

unitimes.media

全球视角,独到见解

RLP(Recursive Length Prefix,递归长度前缀)是一种编码算法,用于编码任意的嵌套结构的二进制数据,它是以太坊中数据序列化/反序列化的主要方法,区块、交易等数据结构在持久化时会先经过RLP编码后再存储到数据库中。

01

定义

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

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

02

RLP编码规则

对于单个字节,如果它的值范围是[x,x7f],它的RLP编码就是它本身。

否则,如果一个字符串的长度是0-55字节,它的RLP编码包含一个单字节的前缀,后面跟着字符串本身,这个前缀的值是**x8**加上字符串的长度。由于被编码的字符串最大长度是55=x37,因此单字节前缀的最大值是x8+x37=xb7,即编码的第一个字节的取值范围是[x8,xb7]。

如果字符串的长度大于55个字节,它的RLP编码包含一个单字节的前缀,后面跟着字符串的长度,后面再跟着字符串本身。这个前缀的值是**xb7**加上字符串长度的二进制形式的字节长度,说的有点绕,举个例子就明白了,例如一个字符串的长度是1024,它的二进制形式是10000000000,这个二进制形式的长度是2个字节,所以前缀应该是xb7+2=xb9,字符串长度124=x400,因此整个RLP编码应该是\xb9\x4\x00再跟上字符串本身。编码的第一个字节即前缀的取值范围是[xb8,xbf],因为字符串长度二进制形式最少是1个字节,因此最小值是xb7+1=xb8,字符串长度二进制最大是8个字节,因此最大值是xb7+8=xbf。

如果一个列表的总长度(列表的总长度指的是它包含的项的数量加它包含的各项的长度之和)是0-55字节,它的RLP编码包含一个单字节的前缀,后面跟着列表中各元素项的RLP编码,这个前缀的值是**xc**加上列表的总长度。编码的第一个字节的取值范围是[xc,xf7]。

如果一个列表的总长度大于55字节,它的RLP编码包含一个单字节的前缀,后面跟着列表的长度,后面再跟着列表中各元素项的RLP编码,这个前缀的值是**xf7**加上列表总长度的二进制形式的字节长度。编码的第一个字节的取值范围是[xf8,xff]。

03

RLP编码例子

字符串"dog" = [x83, 'd', 'o', 'g' ](规则二)

列表["cat","dog"] = [xc8,x83, 'c', 'a', 't',x83, 'd', 'o', 'g' ](规则四)

空字符串"" =x8(规则二)

空列表[] = [xc](规则四)

整数15('\xf') =xf(规则一)

整数124('\x4\') = [x82,x4,x](规则二)

列表[ [], [[]], [ [], [[]] ] ] = [xc7,xc,xc1,xc,xc3,xc,xc1,xc](规则四)

字符串"Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [xb8,x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't'](规则三)

本文大部分翻译自以太坊github wiki文档,并加入自己的理解。

参考资料:

https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-RLP

作者:小小

来源:链客

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181006B1LTF700?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励