以太坊RLP机制分析

目录1 RLP 定义2 RLP 编码规则3 RLP 编码实例4 RLP 分析1 RLP 定义RLP,即 Recursive Length Prefix, 递归长度前缀编码,是以太坊数据序列化的主要方法, 具有较好的数据处理效率,尤其是将长度和类型统一作为前缀,实际上 RLP 是基于 ASCII 编码的一种结构化扩充,既能表示长度还能表示类型,是一种非常紧凑的结构化编码方案。 该编码方案用于编码任意的嵌套结构的二进制数据,区块、交易等数据结构在持久化时会先 经过 RLP 编码后再存储到数据库中。RLP 的唯一目标就是解决结构体的编码问题;对原子 数据类型(比如,字符串,整数型,浮点型)的编码则交给更高层的协议;以太坊中要求数 字必须是一个大端字节序的、没有零占位的存储的格式(也就是说,一个整数 0 和一个空数 组是等同的)。如果要编码一个字典,推荐使用两种规范的编码格式——一是通过 key 的字 典序来组织字典[[k1,v1],[k2,v2]……],另一种是以太坊中使用的高层的 Patricia Tree。RLP 编码的定义只处理两类数据:一类是字符串(例如字节数组),即一串二进制数据(strings);一类是列表。即一个嵌套递归的结构,里面可以包含字符串和列表。例如:[“cat”,[“puppy”,“cow”],“horse”,[[]],“pig”,[“”],“sheep”]其他类型的数据需要转成以上的两类,转换的规则不是 RLP 编码定义的,可以根据自己的 规则转换,例如 struct 可以转成列表,int 可以转成二进制(属于字符串一类),以太坊中整 数都以大端形式存储。从 RLP 编码的名字可以看出它的特点:一是递归,被编码的数据是递归的结构,编码算法也是递归进行处理的;二是长度前缀,即 RLP 编码都带有一个前缀,这个前缀是跟被编码数据的长度相关的。2 RLP 编码规则规则一:单字节值在[0x00,0x7f]之间的,编码就是自身。需要注意的是 0x7f 这个边界,因为 ASCII 编码最大值就是 0x7f(即二进制 1111,1111),也就是说在 0x7f 以内完全当做 ASCII 编码使用。规则二:如果一个 string 长度在 0-55 之间,编码结果的为在 string 开头加一个字节,这个字 节的值是 0x80 加上 string 的长度。由于被编码的字符串最大长度是 55=0x37,因此单字节前 缀的最大值是 0x80+0x37=0xb7,即编码的第一个字节的取值范围是[0x80, 0xb7]。 (128—183)(0x80+[string 的长度]) || string规则三:如果一个 string 长度超过了 55 个字节,编码结果的第 1 个字节为 0xb7+string 的长度 值(字节表示)的长度,后跟着string的长度,后跟着string。所以第一个字节的范围为[0xb8,0xbf]。(0xb7+string 长度值的长度) || (string 的长度) || string比如某个 string 长度为 1024(0x0400),0x0400 的长度为 2,因此第 1 个字节为前缀应该是 0xb7+2=0xb9,后面跟着0x0400,再后面跟着string,即整个RLP编码应该是\xb9\x0400\string。 编码的第一个字节即前缀的取值范围是[0xb8, 0xbf],因为字符串长度二进制形式最少是 1个字节,因此最小值是 0xb7+1=0xb8,字符串长度二进制最大是 8 个字节,因此最大值是 0xb7+8=0xbf。(184—191)规则四:如果一个数组中所有元素的长度之和在 0-55 之间,编码结果的第 1 个字节为 0xc0+ 所有元素的长度,后面跟着列表中各元素的编码串,因此第 1 个字节的范围在[0xc0,0xf7]。 [192—247](0xc0+列表元素总长度) || 列表各元素的编码串规则五:如果数组中所有元素的长度超过 55 个字节,编码结果的第 1 个字节为 0xf7 加上所 有元素长度值(字节表示)的长度,后跟所有元素长度,后面跟着数组。第 1 个字节的范围是 [0xf8,0xff]。 [248—255](0xf7+所有元素长度值的长度) || 列表元素总长度 || 列表各元素的编码串3 RLP 编码实例字符串 “dog” = [0x83, ’d’, ‘o’, ‘g’ ] (规则二)列表 [“cat”,“dog”] = [0xc8, 0x83, ‘c’, ‘a’, ’t’, 0x83, ’d’, ‘o’, ‘g’ ] (规则四)空字符串 “” = 0x80 (规则二)空列表 [] = [0xc0] (规则四)整数 15(‘\x0f’) = 0x0f (规则一)整数 1024(‘\x04\00’) = [0x82, 0x04, 0x00] (规则二)列表 [ [], [[]], [ [], [[]] ] ] = [0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0] (规则四)字符串 “Lorem ipsum dolor sit amet, consectetur adipisicing elit” = [0xb8, 0x38, ‘L’, ‘o’, ‘r’, ‘e’, ’m’, ‘ ’, … , ‘e’, ‘l’, ‘i’, ’t’](规则三)4 RLP 分析RLP 编码的设计思想,就是通过首字节快速判断一串编码的类型,充分利用了一个字 节的存储空间,将 0x7f 以后的值赋予了新的含义。相比于 Unicode 的对指定长度字节进行 编码,处理这些编码时一般按照指定长度进行拆分解码,最大的弊端是传统编码无法表现一 个结构,即列表。RLP 最大的优点是在充分利用字节的情况下,同时支持列表结构,也就 是说可以很轻易的利用 RLP 存储一个树状结构。程序处理 RLP 编码时也非常容易,根据首字节就可以判断出这段编码的类型,同时调用不 同的方法进行解码,类似于 json 结构, RLP 支持嵌套的结构,通过递归调用可以将整个 RLP 快速还原成一颗树,或者转译成一个 json 结构,便于其他程序使用。RLP 使用首字节存储长度的位数,再用后续的字节表明整体字符串的长度,根据规则二计 算,RLP 可以支持的单个最大字符串长度为 2 的 64 次方,再加上嵌套规则,理论上 RLP 可 以编码任何数据。

关于我:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180731G197T400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券