遞迴長度前綴 (RLP) 序列化

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

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

若要使用 RLP 對字典進行編碼，建議的兩種規範形式為：

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

定義

RLP 編碼函式接收一個項目 (item)。項目的定義如下：

• 字串（即位元組陣列）是一個項目
• 項目列表是一個項目
• 正整數是一個項目

例如，以下所有都是項目：

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

請注意，在本頁其餘部分的上下文中，「字串」指的是「一定數量的二進位資料位元組」；不使用任何特殊編碼，也不暗示對字串內容有任何了解（除非反對非最小正整數的規則有所要求）。

RLP 編碼定義如下：

• 對於正整數，它會被轉換為大端序解釋為該整數的最短位元組陣列，然後根據以下規則編碼為字串。
• 對於值在 [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]）。

簡而言之：

• p = 有效負載
• n = 長度（有效負載位元組數）
• N = 長度的長度偏移量（後面跟著 N+1 個 n 位元組）

在程式碼中，這表示為：

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 解碼

根據 RLP 編碼的規則和過程，RLP 解碼的輸入被視為二進位資料陣列。RLP 解碼過程如下：

1. 根據輸入資料的第一個位元組（即前綴）並解碼資料類型、實際資料的長度和偏移量；

2. 根據資料的類型和偏移量，相應地解碼資料，並遵守正整數的最小編碼規則；

3. 繼續解碼輸入的其餘部分；

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

1. 如果第一個位元組（即前綴）的範圍是 [0x00, 0x7f]，則資料為字串，且該字串正是第一個位元組本身；

2. 如果第一個位元組的範圍是 [0x80, 0xb7]，則資料為字串，且長度等於第一個位元組減去 0x80 的字串緊跟在第一個位元組之後；

3. 如果第一個位元組的範圍是 [0xb8, 0xbf]，則資料為字串，且以位元組為單位的長度等於第一個位元組減去 0xb7 的字串長度緊跟在第一個位元組之後，而字串緊跟在字串長度之後；

4. 如果第一個位元組的範圍是 [0xc0, 0xf7]，則資料為列表，且總有效負載等於第一個位元組減去 0xc0 的列表所有項目 RLP 編碼的串聯緊跟在第一個位元組之後；

5. 如果第一個位元組的範圍是 [0xf8, 0xff]，則資料為列表，且長度等於第一個位元組減去 0xf7 的列表總有效負載緊跟在第一個位元組之後，而列表所有項目 RLP 編碼的串聯緊跟在列表的總有效負載之後；

在程式碼中，這表示為：

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 (opens in a new tab)
• 以太坊底層技術：RLP (opens in a new tab)
• Coglio, A. (2020). Ethereum's Recursive Length Prefix in ACL2. arXiv preprint arXiv:2009.13769. (opens in a new tab)

相關主題

• 帕特里夏默克爾前綴樹 (Patricia merkle trie)