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编码规则
-
对于值在
[0x00, 0x7f]范围内的单个字节，编码就是本身。例如，"a"的编码为：[0x61] 整数0的编码为：[0x00] -
如果一个字符串的长度是0-55字节，其RLP编码是前缀再拼接字符串本身，前缀的值是
0x80加上字符串的长度。前缀取值范围是[0x80, 0xb7]。例如，空字符串(‘null’)的编码为：[0x80] 整数1024('\x04\x00')的编码为：[ 0x82, 0x04, 0x00 ] 字符串"dog"的编码为：[0x83,'d','o','g'] -
如果一个字符串的长度大于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'] -
以上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] 如果列表长度超过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解码的输入一律视为二进制字符数组，其过程如下：
根据输入首字节数据，解码数据类型、实际数据长度和位置；
根据类型和实际数据，解码不同类型的数据；
继续解码剩余的数据；
其中，解码数据类型、实际数据类型和位置的规则如下：
如果首字节(prefix)的值在[0x00, 0x7f]范围之间，那么该数据是字符串，且字符串就是首字节本身；
如果首字节的值在[0x80, 0xb7]范围之间，那么该数据是字符串，且字符串的长度等于首字节减去
0x80，且字符串位于首字节之后；如果首字节的值在[0xb8, 0xbf]范围之间，那么该数据是字符串，且字符串的长度的字节长度等于首字节减去
0xb7，数据的长度位于首字节之后，且字符串位于数据的长度之后；如果首字节的值在[0xc0, 0xf7]范围之间，那么该数据是列表，在这种情况下，需要对列表各项的数据进行递归解码。列表的总长度（列表各项编码后的长度之和）等于首字节减去
0xc0，且列表各项位于首字节之后；如果首字节的值在[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
