RLP編碼原理

RLP(Recursive Length Prefix康震，遞歸長度前綴)編碼算法纱烘，是以太坊中數(shù)據(jù)序列化/反序列化的主要方法曲楚。以太坊區(qū)塊鏈中的區(qū)塊幢痘、交易等數(shù)據(jù)結(jié)構(gòu)在持久化時會先經(jīng)過 RLP 編碼后再存儲到數(shù)據(jù)庫中裂七。

RLP 編碼只處理兩類數(shù)據(jù)：

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

其他數(shù)據(jù)類型的數(shù)據(jù)需要轉(zhuǎn)換成以上的兩類皆看，轉(zhuǎn)換的規(guī)則不是 RLP 編碼定義的，可以根據(jù)自己的規(guī)則轉(zhuǎn)換背零，例如 struct可以轉(zhuǎn)換成列表腰吟，int 可以轉(zhuǎn)換成二進(jìn)制(屬于字符串一類)，以太坊中整數(shù)都以大端形式存儲徙瓶。

RLP 編碼規(guī)則：

1. 對于單個字節(jié)毛雇，如果它的值范圍是[0x00,0x7f]（ASCII碼），它的 RLP 編碼就是它本身侦镇。
   如： a -> [0x61] (字符) 100 -> [0x64] （數(shù)字）
2. 字符串長度是0-55字節(jié)灵疮，它的 RLP 編碼包含一個單字節(jié)的前綴，后面跟著字符串的長度壳繁，再接著字符串本身震捣。這個前綴的值0x80加上字符串的長度荔棉。由于被編碼的字符串最大長度是55=0x37，因此單字節(jié)前綴的最大值是0x80+0x37=0xb7蒿赢，即編碼的第一個字節(jié)的取值范圍是[0x80,0xb7]润樱。
   字符串長度小于55字節(jié)的RLP 編碼例子：
   “dog” -> [0x83, 'd', 'o', 'g']
   其中0x83 = 0x80 + 3(“dog”字符串的長度)
3. 字符串長度大于55個字節(jié)，它的 RLP 編碼包含一個單字節(jié)的前綴羡棵，后面跟著字符串的長度壹若，再接著字符串本身。這個前綴的值是0xb7加上字符串長度的二進(jìn)制形式的字節(jié)長度晾腔。由于被編碼的字符串長度的二進(jìn)制長度最少是1個字節(jié)舌稀，最大是8個字節(jié)，前綴的取值范圍是[0xb8,0xbf]灼擂。
   字符串長度大于55字節(jié)的 RLP 編碼例子：
   字符串："Lorem ipsum dolor sit amet, consectetur adipisicing elit"
   字符串長度：56字節(jié)壁查，其二進(jìn)制形式為:00111000。其二進(jìn)制形式的長度為8位剔应，也就是1個字節(jié)長度睡腿。
   前綴：0xb7 + 1 = 0xb8
   字符串長度的16進(jìn)制表示： 56 -> 0x38
   該字符串的 RLP 編碼形式為：
   [0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't']
4. 列表總長度(列表的總長度指的是它包含的項(xiàng)的數(shù)量加它包含的各項(xiàng)的長度之和)是0-55字節(jié)，它的 RLP 編碼包含一個單字節(jié)的前綴峻贮，后面跟著列表中各元素項(xiàng)的 RLP 編碼席怪，這個前綴的值是0xc0加上列表的總長度。由于被編碼的列表最大長度是55=0x37纤控，因此前綴的最大值是0xc0+0x37=0xf7挂捻，前綴的取值范圍為[0xc0,0xf7]。
   列表長度小于55字節(jié)的 RLP 編碼例子：
   列表：[ ["dog","cat"], [["mouse"]], [["bird"], [["duck","chicken"]]] ]
   列表總長度：列表含有項(xiàng)13 + 所有項(xiàng)包含的字符總數(shù)26 = 39 -> 0x27
   拆分列表項(xiàng)共計(jì)13項(xiàng)： ["dog","cat"]船万、"dog"刻撒、"cat"、[["mouse"]]耿导、["mouse"]声怔、"mouse"、[["bird"], [["duck","chicken"]]]舱呻、["bird"]醋火、"bird"、[["duck","chicken"]]箱吕、["duck","chicken"]芥驳、"duck"、"chicken"
   列表 RLP 編碼前綴 ： 0xc0 + 0x27 = 0xe7
   列表中各項(xiàng)對應(yīng)的 RLP 編碼：套用編碼規(guī)則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字節(jié)兆旬，它的 RLP 編碼包含一個單字節(jié)的前綴，后面跟著列表的長度雅采，再接著列表中各元素項(xiàng)的 RLP 編碼爵憎。這個前綴的值是0xf7加上列表總長度的二進(jìn)制形式的字節(jié)長度。由于被編碼的列表長度的二進(jìn)制長度最少是1個字節(jié)婚瓜，最大是8個字節(jié)宝鼓，前綴的取值范圍是[0xf8,0xff]。
   列表長度大于55字節(jié)的 RLP 編碼例子：
   列表：["Lorem ipsum dolor sit amet, consectetur adipisicing elit"]
   列表總長度：列表含有項(xiàng)1 + 所有項(xiàng)包含的字符總數(shù)56= 57 -> 0x39
   其二進(jìn)制形式為：00111001巴刻。其二進(jìn)制形式的長度為8位愚铡，也就是1個
   字節(jié)長度。
   列表 RLP 編碼前綴：0xf7+1=0xf8
   列表中各項(xiàng)對應(yīng)的 RLP 編碼：套用編碼規(guī)則2胡陪、3
   該列表的 RLP 編碼為：
   [0xf8,0x39,0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't']