RLP 递归长度前缀

RLP(recursive length prefix)：递归长度前缀。

RLP编码是以太坊中主要的序列化格式，它的使用无处不在：区块、交易、账户状态以及线路协议消息。

RLP旨在成为高度简化的序列化格式，它唯一的目的是存储嵌套的字节数组。不同于protobuf、BSON等现有的解决方案，RLP并不定义任何指定的数据类型，如Boolean、floa、double或者integer。它仅仅是以嵌套数组的形式存储结构，并将其留给协议来确定数组的含义。RLP也没有明确支持map集合，半官方的建议是采用 [[k1, v1], [k2, v2], ...] 的嵌套数组来表示键值对集合，k1,k2 ... 按照字符串的标准排序。

与RLP具有相同功能的方案是protobuf或BSON，它们是一直被使用的算法。然而，以太坊中，更偏向于使用RLP，因为：(1)它易于实现；(2)绝对保证字节的一致性。许多语言的Map集合没有明确的排序，并且浮点格式有很多特殊情况，这可能造成相同数据却导致不同编码和hash值。通过内部开发协议，我们能确保它是带着这些目标设计的（这是一般原则，也适用于代码的其他部分，如VM）。BitTorrent使用的编码方式bencode也许可以替代RLP。不过它采用的是十进制的编码方式，与采用二进制的RLP相比，稍微逊色了点。

RLP定义

RLP编码功能只处理两类数据：字符串（字节数组）和列表（list）。

可以是：空字符串""、包含单词"cat"的字符串、包含任意数量字符串的列表(如，["cat","dog"])以及更复杂的数据结构["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]。请注意，“字符串”将表示为“一定数量字节的二进制数据”的同义词。

RLP编码规则

1. 对于值在[0x00, 0x7f]范围内的单个字节，编码就是本身。

    例如，"a"的编码为：[0x61]
    整数0的编码为：[0x00] 
   

2. 如果一个字符串的长度是0-55字节，其RLP编码是前缀再拼接字符串本身，前缀的值是0x80加上字符串的长度。前缀取值范围是[0x80, 0xb7]。

   例如，空字符串(‘null’)的编码为：[0x80]
   整数1024('\x04\x00')的编码为：[ 0x82, 0x04, 0x00 ]
   字符串"dog"的编码为：[0x83,'d','o','g']
   

3. 如果一个字符串的长度大于55字节，编码结果为：[0xb7+字节数组长度的编码的长度,字节数组长度本身的编码,字节数组]。本规则下前缀的取值范围是[0xb8,0xbf]；

   例如，字符串“Lorem ipsum dolor sit amet, consectetur adipisicing elit”
   1. 字符串长度为56，编码为0x38
   2. 长度56编码后仅占用一个字节,即0xb7 + 1 = 0xb8
   编码结果为：[0xb8,0x38,'L','o','r','e','m',' ',…,'e','l','i','t'] 
   

4. 以上3个规则是针对字符串的，接下来的两个规则针对列表的。由于列表是任意嵌套的，因此列表的编码是递归的，先编码最里层列表，再逐步往外层列表编码。如果列表长度小于55，编码结果第一位是0xc0加列表长度的编码的长度，然后依次连接各子列表的编码。本规则下前缀的取值范围是[0xc0, 0xf7]。

   例如，列表["cat","dog"]
   1. "cat"的编码为[0x83,'c','a','t']
   2. "dog"的编码为[0x83,'d','o','g']
   3. 两个子字符串的编码后总长度是8，即0xc0 + 8 = 0xc8
   编码结果为：[0xc8,0x83,'c','a','t',0x83,'d','o','g']
   空列表[]编码结果为：[0xc0]
   嵌套列表[[],[[]],[[],[[]]]]编码结果为：[0xc7,0xc0,0xc1,0xc0,0xc3,0xc0,0xc1,0xc0] 
   

5. 如果列表长度超过55，编码结果第一位是247加列表长度的编码长度，然后是列表长度本身的编码，最后依次连接各子列表的编码。编码的第一个字节的取值范围是[0xf8, 0xff]。

```
例如，列表["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]
1. "The length of this sentence is more than 55 bytes, "的长度为51(0x33)，根据规则二得出：0x80 + 0x33 = 0xb3
2. "I know it because I pre-designed it"的长度为35(0x23)，根据规则2得出：0x80 + 0x33 = 0xa3
3. 列表长度本身的编码为：51 + 35 + 2 = 88，即0x58
4. 最后根据规则5，0x58只占用一个字节，即0xf7 + 1 = 0xf8
编码结果为：[0xf8,0x58,0xb3,'T','h',...,'e','s',',',' ',0xa3,'I',' ','k',...,'i','t']
```

代码如下：

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)

RLP解码规则

根据RLP编码规则和过程，RLP解码的输入一律视为二进制字符数组，其过程如下：

1. 根据输入首字节数据，解码数据类型、实际数据长度和位置；

2. 根据类型和实际数据，解码不同类型的数据；

3. 继续解码剩余的数据；

其中，解码数据类型、实际数据类型和位置的规则如下：

1. 如果首字节(prefix)的值在[0x00, 0x7f]范围之间，那么该数据是字符串，且字符串就是首字节本身；

2. 如果首字节的值在[0x80, 0xb7]范围之间，那么该数据是字符串，且字符串的长度等于首字节减去0x80，且字符串位于首字节之后；

3. 如果首字节的值在[0xb8, 0xbf]范围之间，那么该数据是字符串，且字符串的长度的字节长度等于首字节减去0xb7，数据的长度位于首字节之后，且字符串位于数据的长度之后；

4. 如果首字节的值在[0xc0, 0xf7]范围之间，那么该数据是列表，在这种情况下，需要对列表各项的数据进行递归解码。列表的总长度（列表各项编码后的长度之和）等于首字节减去0xc0，且列表各项位于首字节之后；

5. 如果首字节的值在[0xf8, 0xff]范围之间，那么该数据为列表，列表的总长度的字节长度等于首字节减去0xf7，列表的总长度位于首字节之后，且列表各项位于列表的总长度之后；

代码如下：

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 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

参考链接

• ethereum/wiki：RLP
• RLP编码和解码
• 以太坊源码学习—RLP编码