suweet

• • RLP序列化（Recursive Length Prefix 递归长度前缀）
    • 编码
      • Rules
      • Examples
      • Code
    • 解码
      • Rules
      • Code
    • 参考

RLP序列化（Recursive Length Prefix 递归长度前缀）

科大讯飞星火 AI大语言模型：

RLP编码，全称是Recursive Length Prefix，是一种在区块链系统中常用的数据编码方式。它是由以太坊的开发者Gavin Wood提出的，用于解决在区块链中存储和传输数据的问题。

RLP编码的主要特点是它可以处理任意长度的数据（实际上支持的最大字符串长度为2^64，相当之大所以说任意），并且可以递归地处理嵌套的数据结构。这使得它非常适合于处理复杂的数据结构，如区块链中的交易信息、智能合约等。

RLP编码的基本规则是：对于每一个数据项，首先将其转换为字节数组，然后计算字节数组的长度，并将长度编码为一个或多个字节（如果长度小于55，则直接编码为一个字节；如果长度大于等于55，则先编码长度的长度，然后再编码长度本身）。最后，将长度编码和字节数组连接起来，就得到了这个数据项的RLP编码。

RLP编码的一个优点是它的解码过程非常简单：只需要从左到右扫描编码结果，根据第一个字节的值就可以确定下一个数据项的长度，然后取出相应长度的字节数组，就得到了这个数据项的原始数据。

以太坊 RECURSIVE-LENGTH PREFIX (RLP) SERIALIZATION ：

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

为什么还要提出一种新的编码？

对象序列化方法有很多种，如JSON编码，但这些编码结果都比较大，所以提出RLP。

编码

RLP编码前需要将对象映射成字节数组或列表。对于int类型需要去掉前导零，使用大端模式。

Rules

len()返回int64，最大8字节。表格中RLP列中的len(X)返回的数据长度是整数类型，且以大端模式的最小字节数组表示。

任意X，len(X) ∈[0, 2^64]，len(len(X))∈[1, 8]。

Examples

• 整数 0 = [0x80]
• 整数 1 = [0x01]
• 整数 1024('0x04,0x00') = [0x82, 0x04, 0x00]
• 字符串 "" = ['0x80']
• 字符串 "d" = ['d']
• 字符串 "dog" = [0x83, 'd', 'o', 'g']
• 56位字符串 "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]
• 列表 [] = [0xc0]
• 列表 ["cat","dog"] = [0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g']
• 嵌套列表 [ [], [[]], [ [], [[]] ] ] = [0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0]
• 大列表 ["cat", "Lorem ipsum dolor sit amet, consectetur adipisicing elit"] = [0xf8, 0x3e, 0x83, 'c', 'a', 't', 0xb8, 0x38, 'L', 'o', 'r', ..., 't']

Code

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        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
     raise Exception("input too long")

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

解码

根据编码，二进制数组结果的形式为{prefix, [size], [data]}，其中prefix在五中规则中分别占用128,56,8,56,8个值，正好1字节，由此通过RLP编码的首字节（前缀）即可判断类型

Rules

Code

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)
    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])
    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

参考

• RECURSIVE-LENGTH PREFIX (RLP) SERIALIZATION

• 区块链之 RLP序列化