RLP編碼介紹

定義

RLP(Recursive Length Prefix，遞歸長度前綴)是一種編碼算法，用于編碼任意的嵌套結構的二進制數據，它是以太坊中數據序列化/反序列化的主要方法，區塊、交易等數據結構在持久化時會先經過RLP編碼后再存儲到數據庫中。

RLP編碼的定義只處理兩類數據：一類是字符串（例如字節數組），一類是列表。字符串指的是一串二進制數據，列表是一個嵌套遞歸的結構，里面可以包含字符串和列表，例如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]就是一個復雜的列表。其他類型的數據需要轉成以上的兩類，轉換的規則不是RLP編碼定義的，可以根據自己的規則轉換，例如struct可以轉成列表，int可以轉成二進制（屬于字符串一類），以太坊中整數都以大端形式存儲。

RLP編碼規則

1. 對于單個字節，如果它的值范圍是[0x00, 0x7f]，它的RLP編碼就是它本身。
2. 否則，如果一個字符串的長度是0-55字節，它的RLP編碼包含一個單字節的前綴，后面跟著字符串本身，這個前綴的值是0x80加上字符串的長度。由于被編碼的字符串最大長度是55=0x37,因此單字節前綴的最大值是0x80+0x37=0xb7，即編碼的第一個字節的取值范圍是[0x80, 0xb7]。
3. 如果字符串的長度大于55個字節，它的RLP編碼包含一個單字節的前綴，后面跟著字符串的長度，后面再跟著字符串本身。這個前綴的值是0xb7加上字符串長度的二進制形式的字節長度，說的有點繞，舉個例子就明白了，例如一個字符串的長度是1024，它的二進制形式是10000000000，這個二進制形式的長度是2個字節，所以前綴應該是0xb7+2=0xb9，字符串長度1024=0x400，因此整個RLP編碼應該是\xb9\x04\x00再跟上字符串本身。編碼的第一個字節即前綴的取值范圍是[0xb8, 0xbf]，因為字符串長度二進制形式最少是1個字節，因此最小值是0xb7+1=0xb8，字符串長度二進制最大是8個字節，因此最大值是0xb7+8=0xbf。
4. 如果一個列表的總長度（列表的總長度指的是它包含的項的數量加它包含的各項的長度之和）是0-55字節，它的RLP編碼包含一個單字節的前綴，后面跟著列表中各元素項的RLP編碼，這個前綴的值是0xc0加上列表的總長度。編碼的第一個字節的取值范圍是[0xc0, 0xf7]。
5. 如果一個列表的總長度大于55字節，它的RLP編碼包含一個單字節的前綴，后面跟著列表的長度，后面再跟著列表中各元素項的RLP編碼，這個前綴的值是0xf7加上列表總長度的二進制形式的字節長度。編碼的第一個字節的取值范圍是[0xf8, 0xff]。

RLP編碼例子

字符串 "dog" = [0x83, 'd', 'o', 'g' ] （規則二）

列表 ["cat","dog"] = [0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ] （規則四）

空字符串 "" = 0x80 （規則二）

空列表 [] = [0xc0] （規則四）

整數 15('\x0f') = 0x0f （規則一）

整數 1024('\x04\00') = [0x82, 0x04, 0x00] （規則二）

列表 [ [], [[]], [ [], [[]] ] ] = [0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0] （規則四）

字符串 "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't'] （規則三）

為什么又要造輪子

對象序列化方法有很多種，常見的像JSON編碼，但是JSON有個明顯的缺點：編碼結果比較大。例如有如下的結構：

type Student struct{
    Name string `json:"name"`
    Sex string `json:"sex"`
}
s := Student{Name:"icattlecoder",Sex:"male"}
bs,_ := json.Marsal(&s)
print(string(bs))
// {"name":"icattlecoder","sex":"male"}

變量s序列化的結果是{"name":"icattlecoder","sex":"male"},字符串長度35，實際有效數據是icattlecoder 和male，共計16個字節，我們可以看到JSON的序列化時引入了太多的冗余信息。假設以太坊采用JSON來序列化，那么本來50GB的區塊鏈可能現在就要100GB，當然實際沒這么簡單。

所以，以太坊需要設計一種結果更小的編碼方法。

RLP編碼定義

RLP實際只給以下兩種類型數據編碼：

1.　byte數組

2.　byte數組的數組，稱之為列表

規則1：對于值在[0, 127]之間的單個字節，其編碼是其本身。

例1：a的編碼是97。

規則2：如果byte數組長度l <= 55，編碼的結果是數組本身，再加上128+l作為前綴。

例2：空字符串編碼是128，即128 = 128 + 0。

例3：abc編碼結果是131 97 98 99，其中131=128+len("abc")，97 98 99依次是a b c。
　　

規則3：如果數組長度大于55， 編碼結果第一個是183加數組長度的編碼的長度，然后是數組長度的本身的編碼，最后是byte數組的編碼。

請把上面的規則多讀幾篇，特別是數組長度的編碼的長度。

例4：編碼下面這段字符串：

The length of this sentence is more than 55 bytes, I know it because I pre-designed it

這段字符串共86個字節，而86的編碼只需要一個字節，那就是它自己，因此，編碼的結果如下：

184 86 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前三個字節的計算方式如下：

184 = 183 + 1，因為數組長度86編碼后僅占用一個字節。

86即數組長度86

84是T的編碼

例5：編碼一個重復1024次"a"的字符串，其結果為：185 4 0 97 97 97 97 97 97 ...。

1024按 big endian編碼為0 0 4 0，省略掉前面的零，長度為2（我的理解：1024(10000000000)需要用到2個字節），因此185 = 183 + 2。

規則1~3定義了byte數組的編碼方案，下面介紹列表的編碼規則。在此之前，我們先定義列表長度是指子列表編碼后的長度之和。

規則4：如果列表長度小于55，編碼結果第一位是192加列表長度的編碼的長度，然后依次連接各子列表的編碼。

注意規則4本身是遞歸定義的。

例6：["abc", "def"]的編碼結果是200 131 97 98 99 131 100 101 102。
其中abc的編碼為131 97 98 99,def的編碼為131 100 101 102。兩個子字符串的編碼后總長度是8，因此編碼結果第一位計算得出：192 + 8 = 200。

規則5：如果列表長度超過55，編碼結果第一位是247加列表長度的編碼長度，然后是列表長度本身的編碼，最后依次連接各子列表的編碼。

規則5本身也是遞歸定義的，和規則3相似。

例7：

["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]

的編碼結果是:

248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前兩個字節的計算方式如下：

248 = 247 +1

88 = 86 + 2

在規則3的示例中，長度為86，而在此例中，由于有兩個子字符串，每個子字符串本身的長度的編碼各占1字節，因此總共占2字節。
第3個字節179依據規則2得出179 = 128 + 51
第55個字節163同樣依據規則2得出163 = 128 + 35

例8：最后我們再來看個稍復雜點的例子以加深理解遞歸長度前綴，

["abc",["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]]

編碼結果是：

248 94 131 97 98 99 248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

列表第一項字符串abc根據規則2，編碼結果為131 97 98 99,長度為4。
列表第二項也是一個列表項：

["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]

根據規則5，結果為

248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

長度為90，因此，整個列表的編碼結果第二位是90 + 4 = 94, 占用1個字節，第一位247 + 1 = 248

以上5條就是RPL的全部編碼規則。

語言實現

各語言在具體實現RLP編碼時，首先需要將對像映射成byte數組或列表兩種形式。以go語言編碼struct為例，會將其映射為列表，例如Student這個對象處理成列表["icattlecoder","male"]

type Student struct{
    Name string
    Sex string
}
s := Student{Name:"icattlecoder",Sex:"male"}
buff := bytes.Buffer{}
rpl.Encode(&buff, &s)
print(buff.Bytes())
// [210 140 105 99 97 116 116 108 101 99 111 100 101 114 132 109 97 108 101]

如果編碼map類型，可以采用以下列表形式：

[["",""],["",""],["",""]]

RLP解碼

解碼時，首先根據編碼結果第一個字節f的大小，執行以下的規則判斷：

1.　如果f∈ [0,128),　那么它是一個字節本身。

2.　如果f∈[128,184)，那么它是一個長度不超過55的byte數組，數組的長度為 l=f-128

3.　如果f∈[184,192)，那么它是一個長度超過55的數組，長度本身的編碼長度ll=f-183,然后從第二個字節開始讀取長度為ll的bytes，按照BigEndian編碼成整數l，l即為數組的長度。

4.　如果f∈(192,247]，那么它是一個編碼后總長度不超過55的列表，列表長度為l=f-192。遞歸使用規則1~4進行解碼。

5.　如果f∈(247,256]，那么它是編碼后長度大于55的列表，其長度本身的編碼長度ll=f-247,然后從第二個字節讀取長度為ll的bytes,按BigEndian編碼成整數l，l即為子列表長度。然后遞歸根據解碼規則進行解碼。

以上解釋了什么叫遞歸長度前綴編碼，這個名字本身很好的解釋了編碼規則。