Leap BlockChain

RLP 递归长度前缀

2018-06-01  本文已影响0人  Jisen

RLP 递归长度前缀

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

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

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

与RLP具有相同功能的方案是protobufBSON,它们是一直被使用的算法。然而,以太坊中,更偏向于使用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

参考链接

上一篇下一篇

猜你喜欢

热点阅读