RLP 递归长度前缀

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

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

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

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

RLP定义

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

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

RLP编码规则

对于值在范围内的单个字节，编码就是本身。

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

如果一个字符串的长度大于55字节，编码结果为：。本规则下前缀的取值范围是；

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

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

代码如下：

defrlp_encode(input):ifisinstance(input,str):

iflen(input) ==1andord(input)

else:returnencode_length(len(input),0x80) + input

elifisinstance(input,list):

output =''foritemininput: output += rlp_encode(item)

returnencode_length(len(output),0xc0) + output

defencode_length(L,offset):ifL

returnchr(L + offset)

elifL

returnchr(len(BL) + offset +55) + BL

else:

raiseException("input too long")

defto_binary(x):ifx ==:

return''else:returnto_binary(int(x /256)) + chr(x %256)RLP解码规则

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

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

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

继续解码剩余的数据；

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

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

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

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

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

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

代码如下：

defrlp_decode(input):iflen(input) ==:

returnoutput =''(offset, dataLen, type) = decode_length(input)

iftypeisstr: output = instantiate_str(substr(input, offset, dataLen))

eliftypeislist: output = instantiate_list(substr(input, offset, dataLen)) output + rlp_decode(substr(input, offset + dataLen))

returnoutput

defdecode_length(input):length = len(input)

iflength ==:

raiseException("input is null") prefix = ord(input[])

ifprefix

return(,1, str)

elifprefix prefix -0x80: strLen = prefix -0x80return(1, strLen, str)

elifprefix prefix -0xb7andlength > prefix -0xb7+ to_integer(substr(input,1, prefix -0xb7)): lenOfStrLen = prefix -0xb7strLen = to_integer(substr(input,1, lenOfStrLen))

return(1+ lenOfStrLen, strLen, str)

elifprefix prefix -0xc0: listLen = prefix -0xc0;

return(1, listLen, list)

elifprefix prefix -0xf7andlength > prefix -0xf7+ to_integer(substr(input,1, prefix -0xf7)): lenOfListLen = prefix -0xf7listLen = to_integer(substr(input,1, lenOfListLen))

return(1+ lenOfListLen, listLen, list)

else:

raiseException("input don't conform RLP encoding form")

defto_integer(b)length=len(b)iflength== 0:raiseException("input is null")

eliflength ==1:

returnord(b[])

else:

returnord(substr(b, -1)) + to_integer(substr(b,, -1)) *256参考链接

ethereum/wiki：RLP

RLP编码和解码

以太坊源码学习—RLP编码