RLP编码原理

RLP编码原理

RLP(Recursive Length Prefix，递归长度前缀)编码算法，是以太坊中数据序列化/反序列化的主要方法。以太坊区块链中的区块、交易等数据结构在持久化时会先经过 RLP 编码后再存储到数据库中。

RLP 编码只处理两类数据：

• 字符串 e.g. this is string
• 列表 e.g. ["cat","horse",[[]],"pig",[""],"sheep"]

其他数据类型的数据需要转换成以上的两类，转换的规则不是 RLP 编码定义的，可以根据自己的规则转换，例如 struct可以转换成列表，int 可以转换成二进制(属于字符串一类)，以太坊中整数都以大端形式存储。

RLP 编码规则：

1. 对于单个字节，如果它的值范围是[0x00,0x7f]（ASCII码），它的 RLP 编码就是它本身。
   如： a -> [0x61] (字符) 100 -> [0x64] （数字）
2. 字符串长度是0-55字节，它的 RLP 编码包含一个单字节的前缀，后面跟着字符串的长度，再接着字符串本身。这个前缀的值0x80加上字符串的长度。由于被编码的字符串最大长度是55=0x37，因此单字节前缀的最大值是0x80+0x37=0xb7，即编码的第一个字节的取值范围是[0x80,0xb7]。
   字符串长度小于55字节的RLP 编码例子：
   “dog” -> [0x83, 'd', 'o', 'g']
   其中0x83 = 0x80 + 3(“dog”字符串的长度)
3. 字符串长度大于55个字节，它的 RLP 编码包含一个单字节的前缀，后面跟着字符串的长度，再接着字符串本身。这个前缀的值是0xb7加上字符串长度的二进制形式的字节长度。由于被编码的字符串长度的二进制长度最少是1个字节，最大是8个字节，前缀的取值范围是[0xb8,0xbf]。
   字符串长度大于55字节的 RLP 编码例子：
   字符串："Lorem ipsum dolor sit amet, consectetur adipisicing elit"
   字符串长度：56字节，其二进制形式为:00111000。其二进制形式的长度为8位，也就是1个字节长度。
   前缀：0xb7 + 1 = 0xb8
   字符串长度的16进制表示： 56 -> 0x38
   该字符串的 RLP 编码形式为：
   [0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't']
4. 列表总长度(列表的总长度指的是它包含的项的数量加它包含的各项的长度之和)是0-55字节，它的 RLP 编码包含一个单字节的前缀，后面跟着列表中各元素项的 RLP 编码，这个前缀的值是0xc0加上列表的总长度。由于被编码的列表最大长度是55=0x37，因此前缀的最大值是0xc0+0x37=0xf7，前缀的取值范围为[0xc0,0xf7]。
   列表长度小于55字节的 RLP 编码例子：
   列表：[ ["dog","cat"], [["mouse"]], [["bird"], [["duck","chicken"]]] ]
   列表总长度：列表含有项13 + 所有项包含的字符总数26 = 39 -> 0x27
   拆分列表项共计13项： ["dog","cat"]、"dog"、"cat"、[["mouse"]]、["mouse"]、"mouse"、[["bird"], [["duck","chicken"]]]、["bird"]、"bird"、[["duck","chicken"]]、["duck","chicken"]、"duck"、"chicken"
   列表 RLP 编码前缀 ： 0xc0 + 0x27 = 0xe7
   列表中各项对应的 RLP 编码：套用编码规则2、3
   该列表的 RLP 编码为：
   [0xe7,0xc8,0x83,'d','o','g',0x83,'c','a','t',0xc7,0xc6,0x85,'m','o','u','s','e',0xd5,0xc5,0x84,'b','i','r','d',0xce,0xcd,0x84,'d','u','c','k',0x87,'c','h','i','c','k','e','n']
5. 列表总长度大于55字节，它的 RLP 编码包含一个单字节的前缀，后面跟着列表的长度，再接着列表中各元素项的 RLP 编码。这个前缀的值是0xf7加上列表总长度的二进制形式的字节长度。由于被编码的列表长度的二进制长度最少是1个字节，最大是8个字节，前缀的取值范围是[0xf8,0xff]。
   列表长度大于55字节的 RLP 编码例子：
   列表：["Lorem ipsum dolor sit amet, consectetur adipisicing elit"]
   列表总长度：列表含有项1 + 所有项包含的字符总数56= 57 -> 0x39
   其二进制形式为：00111001。其二进制形式的长度为8位，也就是1个
   字节长度。
   列表 RLP 编码前缀：0xf7+1=0xf8
   列表中各项对应的 RLP 编码：套用编码规则2、3
   该列表的 RLP 编码为：
   [0xf8,0x39,0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't']