递归长度前缀 (RLP)

递归长度前缀 (RLP)

•

递归长度前缀 (RLP) 序列化广泛用于以太坊的执行客户端。 数据在节点之间以节省空间的格式传输，而递归长度前缀可使这一过程标准化。

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

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

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

1.定义

递归长度前缀编码函数接受一个项目。 该项目的定义如下：

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

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

2.递归长度前缀编码的定义

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

对应的代码为：

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80: return input
        else: return encode_length(len(input), 0x80) + input
    elif isinstance(input,list):
        output = ''
        for item in input: output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L,offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    else:
         raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    else:
        return to_binary(int(x / 256)) + chr(x % 256)

示例

[0x00, 0x7f] (十进制 [0, 127])

比如数值 26, 小于 [0, 127]范围。 26 转化成16进制 0x1A,在这种情况下，当数值 26 被视为一个单个字节的数据时,不需要对长度进行编码，它的 RLP 编码为 [0x1A]。

[0x80, 0xb7]（十进制 [128, 183]）

字符串“dog”, 首先dog不是单个字节，其次dog的长度小于55个字节,则编码为一个字节, 其值等于字符串的长度加上 128。

由于dog字符长度3， 128 + 3 = 131 -> 0x83(16进制)。 dog = RLP [0x83, ‘d’, ‘o’, ‘g’]

[0x80, 0xb7]（十进制 [128, 183]）

“Lorem ipsum dolor sit amet, consectetur adipisicing elit” 是一个长度56字符串，长度大于55， 则递归长度前缀编码由一个值为 0xb7（十进制为 183）的单个字节， 加上二进制字符串长度的以字节为单位的长度，后跟字符串的长度，然后是字符串。

第一个字节是 0xb7 + 1 => 0xb8, 因为字符串长度是56，56可以用一个字节来表示，所以字节长度是 1

第二个字节是 0x38, 因为长度是56（十进制） => 0x38(十六进制)

第三个字节是字符串， ‘L’, ‘o’, ‘r’, ‘e’, ‘m’, ‘ ‘, … , ‘e’, ‘l’, ‘i’, ‘t’

“Lorem ipsum dolor sit amet, consectetur adipisicing elit” = RLP [0xb8, 0x38, ‘L’, ‘o’, ‘r’, ‘e’, ‘m’, ‘ ‘, … , ‘e’, ‘l’, ‘i’, ‘t’ ]

[0xc0, 0xf7]（十进制 [192, 247]） 列表长度小于55

1.[‘cat’, ‘dog’] 是一个列表，列表长度小于 55个字节。则递归长度前缀编码包含一个值为 0xc0 的单字节，加上列表长度。

所以第一个字节是0xc0 + 8 => 0xc8

‘cat’ 长度是3， 0x80 + 3 => 0x83, cat = RLP [0x83, ‘c’, ‘a’,’t’]

‘dog’ 长度是3， 0x80 + 3 => 0x83, dog = RLP [0x83, ‘d’, ‘o’,’g’]

[‘cat’, ‘dog’] = RLP[0xc8,0x83, ‘c’, ‘a’,’t’, 0x83, ‘d’, ‘o’,’g’]

2. [ [], [[]], [ [], [[]] ]] 是一个列表长度小于55个字节，则递归长度前缀编码包含一个值为 0xc0 的单字节，加上列表长度。

[] = RLP[0xc0]

[[]] = RLP[0xc1, 0xc0]

[ [], [[]] ] = RLP[0xc3,0xc0, 0xc1, 0xc0]

[ [], [[]], [ [], [[]] ]] = RLP[0xc7,0xc0,0xc1, 0xc0, 0xc3,0xc0, 0xc1, 0xc0]

3.递归长度前缀解码

根据递归长度前缀编码的规则和过程，递归长度前缀译码的输入被视为一个二进制数据数组。 递归长度前缀解码过程如下：

其中，解码数据类型和偏移量的规则如下：

对应的代码为：

def rlp_decode(input):
    if len(input) == 0:
        return
    output = ''
    (offset, dataLen, type) = decode_length(input)
    if type is str:
        output = instantiate_str(substr(input, offset, dataLen))
    elif type is list:
        output = instantiate_list(substr(input, offset, dataLen))
    output + rlp_decode(substr(input, offset + dataLen))
    return output

def decode_length(input):
    length = len(input)
    if length == 0:
        raise Exception("input is null")
    prefix = ord(input[0])
    if prefix <= 0x7f:
        return (0, 1, str)
    elif prefix <= 0xb7 and length > prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix <= 0xbf and length > 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 <= 0xf7 and length > prefix - 0xc0:
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix <= 0xff and length > 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 does not conform to 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

blockchain

区块链基础知识 交易 递归长度前缀 (RLP) ABI Gas