递归长度前缀 (RLP) 序列化

递归长度前缀 (RLP) 序列化广泛用于以太坊的执行客户端。

数据在节点之间以节省空间的格式传输，而递归长度前缀可使这一过程标准化。

递归长度前缀的目的在于，对任意嵌套的二进制数据数组进行编码，而递归长度前缀是用于序列化以太坊执行层中对象的主要编码方法。

递归长度前缀的唯一目的是对结构进行编码；而对特定数据类型（例如字符串、浮点数）进行编码的工作，则留给高阶协议；但正递归长度前缀整数必须以不带前导零的大端序二进制形式表示（从而使整数值零相当于空字节数组）。

带有前导零的反序列化正整数被视为无效。

字符串长度的整数表示也必须以这种方式编码，有效载荷中的整数也是如此。

更多信息请见以太坊黄皮书（附录 B）。

要使用递归长度前缀对字典进行编码，建议的两种规范形式为：

1. 使用 [[k1,v1],[k2,v2]...] 加上按字典顺序排列的键

2. 像以太坊一样使用更高级别的前缀树编码

定义

递归长度前缀编码函数接受一个项目。

该项目的定义如下：

• 一个字符串（即字节数组）是一个项目

• 项目列表也是一个项目

例如，以下所有都是项目：

• 空字符串；

• 包含单词“cat”的字符串；

• 包含任意数量字符串的列表；

• 以及更复杂的数据结构，例如 ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]。

请注意，在本页其余部分的上下文中，“字符串”表示“一定数量的二进制数据字节”；没有使用特殊的编码，也没有暗示关于字符串内容的信息。

递归长度前缀编码的定义如下：

• 对于值在 [0x00, 0x7f]（十进制 [0, 127]）范围内的单个字节，该字节即是它自己的递归长度前缀编码。

• 否则，如果字符串的长度为 0-55 个字节，则递归长度前缀编码包含一个值为 0x80（十进制 128）的单字节，加上该字符串之后字符串的长度。 因此，第一个字节的范围是 [0x80, 0xb7]（十进制 [128, 183]）。

• 如果字符串的长度超过 55 个字节，则递归长度前缀编码由一个值为 0xb7（十进制为 183）的单个字节，加上二进制字符串长度的以字节为单位的长度，后跟字符串的长度，然后是字符串。 例如，一个长 1024 字节的字符串将被编码为 \xb9\x04\x00（十进制 185, 4, 0）后跟该字符串。 在这里，0xb9 (183 + 2 = 185) 为第一个字节，然后是表示实际字符串长度的 2 个字节 0x0400（十进制 1024）。 因此，第一个字节的范围是 [0xb8, 0xbf]（十进制 [184, 191]）。

• 如果列表的总有效载荷长度（即其所有经过递归长度前缀编码的项目的组合长度）为 0-55 个字节，则递归长度前缀编码包含一个值为 0xc0 的单字节，加上列表长度，后跟一串项目递归长度前缀编码。 因此，第一个字节的范围是 [0xc0, 0xf7]（十进制 [192, 247]）。

• 如果列表的总有效载荷长度超过 55 个字节，则递归长度前缀编码包含一个值为 0xf7 的单字节，加上二进制格式的有效载荷长度的以字节为单位的长度，后跟有效载荷的长度，然后是项目递归长度前缀编码串。 因此，第一个字节的范围是 [0xf8, 0xff]（十进制 [248, 255]）。

对应的代码为：

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input)  prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix  prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
        lenOfStrLen = prefix - 0xb7
        strLen = to_integer(substr(input, 1, lenOfStrLen))
        return (1 + lenOfStrLen, strLen, str)
    elif prefix  prefix - 0xc0:
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix  prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
        lenOfListLen = prefix - 0xf7
        listLen = to_integer(substr(input, 1, lenOfListLen))
        return (1 + lenOfListLen, listLen, list)
    else:
        raise Exception("input don't conform RLP encoding form")

def to_integer(b):
    length = len(b)
    if length == 0:
        raise Exception("input is null")
    elif length == 1:
        return ord(b[0])
    else:
        return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

参考资料

https://ethereum.org/zh/developers/docs/data-structures-and-encoding/rlp/