再帰的な長さのプレフィックス(RLP)シリアライゼーション

再帰的な長さのプレフィックス(RLP)シリアライゼーションは、イーサリアムの実行クライアントで広く使われています。 RLP はスペース効率に優れたフォーマットで、ノード間のデータ転送を標準化します。 RLP の目的は、任意のネストされたバイナリデータの配列をエンコード(符号化)することです。また、RLP はイーサリアムの実行レイヤーのオブジェクトのシリアライズに用いられる主要なエンコーディング方式です。 RLP の唯一の目的は、構造をエンコードすることです。特定のデータ型(例: 文字列型、浮動小数点型など)のエンコーディングは、上位のプロトコルが行いますが、正の RLP 整数は、先頭にゼロのないビッグエンディアン・バイナリ形式で表されます(そのため、整数値ゼロは空のバイト配列となります) 。 先頭がゼロのデシリアル化された正の整数は、無効として扱われます。 文字列長の整数表現は、ペイロード内の整数と同様にこの方法でエンコードする必要があります。

詳細については、イーサリアムイエローペーパー (付録 B)(opens in a new tab)を参照してください。

RLP を使用して辞書をエンコードするのに、次の 2 つの正規の方法があります。

• [[k1,v1],[k2,v2]...]のように辞書順にキーを並べて使用する
• イーサリアムのように上位レベルのパトリシア・ツリー・エンコーディングを使用する

定義

RLP エンコーディング関数は、アイテムを取ります。 アイテムは次のように定義されます。

• 文字列型(すなわちバイト配列) はアイテム
• アイテムのリストはアイテム

例えば、次はすべてアイテムです。

• 空文字列
• 「cat」という単語を含む文字列
• 任意の数の文字列を含むリスト
• 次のような、より複雑なデータ構造 ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]

本ページのこれ以降では、「文字列」は「あるバイト数のバイナリデータ」を意味することに注意してください。特別なエンコーディングは使用されておらず、文字列が何を指すのかの知識は必要ありません。

RLP エンコーディングは以下のように定義されます。

• [0x00, 0x7f](10 進数[0, 127])の範囲にある 1 バイトは、そのバイト自体が RLP エンコーディングとなる。
• その他、文字列が 0 ～ 55 バイトの場合、RLP エンコーディングは値が0x80(10 進数 128)に、文字列の長さを足した 1 バイト、続いて文字列で構成される。 したがって、最初の 1 バイトの範囲は[0x80, 0xb7](10 進数[128, 183])となる。
• 文字列の長さが 55 バイトを超える場合、RLP エンコーディングは、0xb7(10 進数 183)にバイナリ形式の文字列長をバイト数を加えた 1 バイト、続けて文字列の長さ、次に文字列で構成される。 例えば、1024 バイトの長さの文字列は、\xb9\x04\x00 (10 進数185, 4, 0)にエンコードされ、その後文字列となる。 ここでは、最初の 1 バイトとして0xb9 (183 + 2 = 185)、次に実際の文字列の長さを示す 2 バイトの0x0400 (10 進数 1024)が続く。 したがって、最初の 1 バイトの範囲は、[0xb8, 0xbf] (10 進数[184, 191])となる。
• リストの全ペイロード(RLP エンコードされるすべてのアイテムを合わせた長さ)が、0 ～ 55 バイトである場合、RLP エンコーディングは、0xc0にリストの長さを加えた 1 バイト、続けてアイテムを RLP エンコーディングして続けたもので構成される。 したがって、最初のバイトの範囲は[0xc0, 0xf7] (10 進数[192, 247])となる。
• リストの全ペイロードが、55 バイトを超える場合、RLP エンコーディングは、0xf7にバイナリ形式のペイロードの長さのバイト数を加えた 1 バイト、次にペイロードの長さ、アイテムの RLP エンコーディングしたものを続けたもので構成される。 したがって、最初のバイトの範囲は、[0xf8, 0xff] (10 進数[248, 255])となる 。

コードでは、これは次のようになります。

1def rlp_encode(input):
2    if isinstance(input,str):
3        if len(input) == 1 and ord(input) < 0x80: return input
4        else: return encode_length(len(input), 0x80) + input
5    elif isinstance(input,list):
6        output = ''
7        for item in input: output += rlp_encode(item)
8        return encode_length(len(output), 0xc0) + output
9
10def encode_length(L,offset):
11    if L < 56:
12         return chr(L + offset)
13    elif L < 256**8:
14         BL = to_binary(L)
15         return chr(len(BL) + offset + 55) + BL
16    else:
17         raise Exception("input too long")
18
19def to_binary(x):
20    if x == 0:
21        return ''
22    else:
23        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 ]
• 整数 0 ('\x00')のエンコード = [ 0x00 ]
• 整数 15 ('\x0f')エンコード = [ 0x0f ]
• 整数 1024 ('\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. 最初の 1 バイト(プレフィックス)の範囲が [0x00, 0x7f]の場合は、データは文字列型で、文字列はそのバイトそのもの。

2. 最初の 1 バイトの範囲が[0x80, 0xb7]の場合、データは文字列型。最初の 1 バイト、続いて最初の 1 バイトから 0x80 を引いた長さの文字列となる。

3. 最初の 1 バイトの範囲が[0xb8, 0xbf]の場合は、データは文字列型。最初の 1 バイト、続いて最初の 1 バイトから 0xb7 を引いた文字列長(バイトで表す)、最後に文字列となる。

4. 最初の 1 バイトの範囲が[0xc0, 0xf7]の場合は、データはリスト型。最初の 1 バイト、続いて全ペイロードが最初のバイトから 0xc0 を引いたものに等しい、リストの全アイテムを RLP エンコーディングして続けたものとなる。

5. 最初の 1 バイトの範囲が[0xf8, 0xff]の場合は、データはリスト型。最初の 1 バイト、続いてリストの長さが最初の 1 バイトから 0xf7 を引いたリストの全ペイロード、最後にリストのすべてのアイテムを RLP エンコーディングして続けたものとなる。

コードでは、これは次のようになります。

1def rlp_decode(input):
2    if len(input) == 0:
3        return
4    output = ''
5    (offset, dataLen, type) = decode_length(input)
6    if type is str:
7        output = instantiate_str(substr(input, offset, dataLen))
8    elif type is list:
9        output = instantiate_list(substr(input, offset, dataLen))
10    output + rlp_decode(substr(input, offset + dataLen))
11    return output
12
13def decode_length(input):
14    length = len(input)
15    if length == 0:
16        raise Exception("input is null")
17    prefix = ord(input[0])
18    if prefix <= 0x7f:
19        return (0, 1, str)
20    elif prefix <= 0xb7 and length > prefix - 0x80:
21        strLen = prefix - 0x80
22        return (1, strLen, str)
23    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
24        lenOfStrLen = prefix - 0xb7
25        strLen = to_integer(substr(input, 1, lenOfStrLen))
26        return (1 + lenOfStrLen, strLen, str)
27    elif prefix <= 0xf7 and length > prefix - 0xc0:
28        listLen = prefix - 0xc0;
29        return (1, listLen, list)
30    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
31        lenOfListLen = prefix - 0xf7
32        listLen = to_integer(substr(input, 1, lenOfListLen))
33        return (1 + lenOfListLen, listLen, list)
34    else:
35        raise Exception("input does not conform to RLP encoding form")
36
37def to_integer(b):
38    length = len(b)
39    if length == 0:
40        raise Exception("input is null")
41    elif length == 1:
42        return ord(b[0])
43    else:
44        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). ACL2 のイーサリアムの再帰的な長さのプレフィックス arXiv preprint arXiv:2009.13769.(opens in a new tab)

関連トピック

• パトリシア・マークル・ツリー