遞迴長度前置詞 (RLP) 序列化

遞迴長度前置詞 (RLP) 序列化在以太坊執行層用戶端中廣泛使用。遞迴長度前置詞以節省空間的格式標準化資料在節點之間的傳送。遞迴長度前置詞的目的在於，對任意嵌套的二進位資料陣列進行編碼，而遞迴長度前置詞是用於序列化以太坊執行層中物件的主要編碼方法。 RLP 的主要用途是編碼結構；除了正整數以外，RLP 會將特定資料類型 (例如字串、浮點數) 的編碼委派給更高階的協定。正整數必須以沒有前導零的大端二進位形式表示（因而使整數值零相當於空位元組陣列）。任何使用遞迴長度前置詞的高階協定都必須將具有前導零的反序列化正整數視爲無效。

更多資訊請參閱以太坊黃皮書（附錄 B） (opens in a new tab)。

要使用遞迴長度前置詞對字典進行編碼，建議的兩種規範形式為：

使用 [[k1,v1],[k2,v2]...]，並以字典順序排列鍵
像以太坊一樣使用更高階的帕特里夏樹編碼

定義

遞迴長度前置詞編碼函式接受一個項目。該項目的定義如下：

一個字串 (亦即位元組陣列) 是一個項目
一個項目清單是一個項目
一個正整數是一個項目

例如，下列所述都是項目：

空字串；
包含單詞「cat」的字串；
包含任意數量字串的清單；
以及更複雜的資料結構，例如 ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]。
數字 100

請注意，在本頁剩餘部分的情境下，「字串」表示「一定數量的二進位資料位元組」；不使用特殊編碼，並且不隱含有關字串内容的知識（除非針對非最小正整數的規則有要求）。

遞迴長度前置詞編碼的定義如下：

對於正整數，將其轉換爲最短位元組陣列，其大端解釋為整數，然後根據下面的規則編碼為字串。
對於值在 [0x00, 0x7f] (十進位 [0, 127]) 範圍內的單一位元組，該位元組即為其自身的 RLP 編碼。
否則，若字串長度為 0-55 位元組，RLP 編碼由一個值為 0x80 (十進位 128) 的單一位元組，加上字串的長度，後面再跟著字串本身所組成。因此，第一個位元組的範圍為 [0x80, 0xb7] (十進位 [128, 183])。
若字串長度超過 55 位元組，RLP 編碼由一個值為 0xb7 (十進位 183) 的單一位元組，加上以位元組為單位、二進位形式的字串長度之長度，後面跟著字串的長度，最後再跟著字串本身所組成。例如，一個 1024 位元組長的字串會被編碼為 \xb9\x04\x00 (十進位 185, 4, 0)，後面再跟著字串。在此，0xb9 (183 + 2 = 185) 是第一個位元組，後面跟著代表實際字串長度的 2 個位元組 0x0400 (十進位 1024)。因此，第一個位元組的範圍為 [0xb8, 0xbf] (十進位 [184, 191])。
如果字串長度為 2^64 位元組或者更長，則可能不會對其進行編碼。
若一個清單的總承載量 (亦即其所有 RLP 編碼項目的組合長度) 為 0-55 位元組，RLP 編碼由一個值為 0xc0 的單一位元組，加上承載量的長度，後面再跟著串連起來的各項目 RLP 編碼所組成。因此，第一個位元組的範圍為 [0xc0, 0xf7] (十進位 [192, 247])。
若一個清單的總承載量超過 55 位元組，RLP 編碼由一個值為 0xf7 的單一位元組，加上以位元組為單位、二進位形式的承載量長度，後面跟著承載量的長度，最後再跟著串連起來的各項目 RLP 編碼所組成。因此，第一個位元組的範圍為 [0xf8, 0xff] (十進位 [248, 255])。

對應的程式碼為：

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        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
    raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    return to_binary(int(x / 256)) + chr(x % 256)

範例

字串 "dog" = [ 0x83, 'd', 'o', 'g' ]
清單 [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
空字串 ('null') = [ 0x80 ]
空清單 = [ 0xc0 ]
整數 0 = [ 0x80 ]
位元組 '\x00' = [ 0x00 ]
位元組 '\x0f' = [ 0x0f ]
位元組 '\x04\x00' = [ 0x82, 0x04, 0x00 ]
3 的集合論表示法 (opens in a new tab)，[ [], [[]], [ [], [[]] ] ] = [ 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 解碼

根據遞迴長度前置詞編碼的規則和過程，遞迴長度前置詞解碼的輸入被視爲一個二進位資料陣列。遞迴長度前置詞解碼過程如下：

根據輸入資料的第一個位元組 (亦即字首) 來解碼資料類型、實際資料長度及偏移量；
根據資料的類型和位移，對資料進行相應的解碼，遵循正整數的最小編碼規則；
繼續解碼輸入的剩餘部分；

其中，解碼資料類型和位移的規則如下：

若第一個位元組 (亦即字首) 的範圍是 [0x00, 0x7f]，則資料為字串，而且字串就是第一個位元組本身；
如果第一個位元組的範圍是 [0x80, 0xb7]，則資料為字串，並且第一個位元組后跟長度等於第一個位元組減去 0x80 的字串；
如果第一個位元組的範圍是 [0xb8, 0xbf]，則資料為字串，第一個位元組后跟長度等於第一個位元組減去 0xb7 的字串長度，后跟該字串；
如果第一個位元組的範圍是 [0xc0, 0xf7]，則資料為清單，第一個位元組後跟清單中所有項目的遞迴長度前置詞編碼串聯，而清單的縂承載等於第一個位元組減去 0xc0；
如果第一個位元組的範圍是 [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)
    raise Exception("input does not conform to 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])
    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

遞迴長度前置詞 (RLP) 序列化

定義

範例

RLP 解碼

延伸閱讀

這篇文章對您有幫助嗎？

遞迴長度前置詞 (RLP) 序列化

定義

範例

RLP 解碼

延伸閱讀

相關主題

這篇文章對您有幫助嗎？