簡單分析RLP編碼原理

買賣虛擬貨幣


RLP(Recursive Length Prefix,遞迴長度字首)是一種編碼演算法,用於編碼任意的巢狀結構的二進位制資料,它是以太坊中資料序列化/反序列化的主要方法,區塊、交易等資料結構在持久化時會先經過RLP編碼後再儲存到資料庫中。



RLP編碼的定義只處理兩類資料:一類是字串(例如位元組陣列),一類是列表。字串指的是一串二進位制資料,列表是一個巢狀遞迴的結構,裡面可以包含字串和列表,例如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]就是一個複雜的列表。其他型別的資料需要轉成以上的兩類,轉換的規則不是RLP編碼定義的,可以根據自己的規則轉換,例如struct可以轉成列表,int可以轉成二進位制(屬於字串一類),以太坊中整數都以大端形式儲存。


從RLP編碼的名字可以看出它的特點:一個是遞迴,被編碼的資料是遞迴的結構,編碼演算法也是遞迴進行處理的;二是長度字首,也就是RLP編碼都帶有一個字首,這個字首是跟被編碼資料的長度相關的,從下面的編碼規則中可以看出這一點。



規則一、對於單個位元組,如果它的值範圍是[0x00, 0x7f],它的RLP編碼就是它本身。這裡面需要注意的是0x7f這個邊界,因為ASCII編碼最大值就是0x7f,也就是說在0x7f以內完全當做ASCII編碼使用


規則二、如果一個字串的長度是0-55位元組,它的RLP編碼包含一個單位元組的字首,後面跟著字串本身,這個字首的值是0x80加上字串的長度。由於被編碼的字串最大長度是55=0x37,因此單位元組字首的最大值是0x80+0x37=0xb7,即編碼的第一個位元組的取值範圍是[0x80, 0xb7]。


規則三、如果字串的長度大於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。


規則四、如果一個列表的總長度(列表的總長度指的是它包含的項的數量加它包含的各項的長度之和)是0-55位元組,它的RLP編碼包含一個單位元組的字首,後面跟著列表中各元素項的RLP編碼,這個字首的值是0xc0加上列表的總長度。編碼的第一個位元組的取值範圍是[0xc0, 0xf7]。


規則五、如果一個列表的總長度大於55位元組,它的RLP編碼包含一個單位元組的字首,後面跟著列表的長度,後面再跟著列表中各元素項的RLP編碼,這個字首的值是0xf7加上列表總長度的二進位制形式的位元組長度。編碼的第一個位元組的取值範圍是[0xf8, 0xff]。



字串 "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'](規則三)



以上我們可以看出RLP編碼的設計思想,就是透過首位元組快速判斷一串編碼的型別,充分利用了一個位元組的儲存空間,將0x7f以後的值賦予了新的含義,以往我們見到的編碼方式主要是對指定長度位元組進行編碼,比如Unicode等,在處理這些編碼時一般按照指定長度進行拆分解碼,最大的弊端是傳統編碼無法表現一個結構,就是本文說的列表,RLP最大的優點是在充分利用位元組的情況下,同時支援列表結構,也就是說可以很輕易的利用RLP儲存一個樹狀結構。


程式處理RLP編碼時也非常容易,根據首位元組就可以判斷出這段編碼的型別,同時呼叫不同的方法進行解碼,如果您熟悉jason這種結構,會發現RLP很類似,支援巢狀的結構,透過遞迴呼叫可以將整個RLP快速還原成一顆樹,或者轉譯成一個jason結構,便於其他程式使用。


RLP使用首位元組儲存長度的位數,再用後續的位元組表明整體字串的長度,根據規則二計算,RLP可以支援的單個最大字串長度為2的64次方,這無疑是個天文數字,再加上巢狀規則,所以理論上RLP可以編碼任何資料。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;