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

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

詳細はイーサリアム・イエローペーパー（付録B） (opens in a new tab)をご覧ください。

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

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

定義

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

• 文字列 (すなわちバイト配列) はアイテムです。
• アイテムのリストはアイテム
• 正の整数はアイテム

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

• 空文字列
• 「cat」という単語を含む文字列
• 任意の数の文字列を含むリスト
• および `[\
• 数値 100

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

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

• 正の整数では、ビックエンディアンを整数として解釈した最短のバイト配列に変換されます。そして、次に以下の規則に従って文字列としてエンコードします。
• 値が[0x00, 0x7f](10進数で[0, 127])の範囲にある単一バイトの場合、そのバイト自体がRLPエンコーディングになります。
• それ以外の場合で、文字列が0〜55バイト長の場合、RLPエンコーディングは、0x80(10進数で128)に文字列の長さを加算した値を持つ単一バイトと、その後に続く文字列で構成されます。 したがって、最初のバイトの範囲は [0x80, 0xb7](10進数で[128, 183])です。
• 文字列が55バイトより長い場合、RLPエンコーディングは、0xb7(10進数183)に文字列の長さ(バイナリ形式)のバイト数を加えた値を持つ単一バイト、その後に文字列の長さ、さらにその後に文字列自体が続く構成となります。 例えば、長さ1024バイトの文字列は \xb9\x04\x00 (10進数で 185, 4, 0) とエンコードされ、その後に文字列が続きます。 ここで、最初のバイトは 0xb9 (183 + 2 = 185) となり、その後に実際の文字列の長さを示す2バイト 0x0400 (10進数で1024) が続きます。 したがって、最初のバイトの範囲は [0xb8, 0xbf] (10進数で [184, 191]) となります。
• 文字列が2^64バイト長以上の場合、エンコードされない可能性があります。
• リストの合計ペイロード(すなわち、RLPエンコードされた全アイテムの合計長)が0〜55バイト長の場合、RLPエンコーディングは、0xc0にペイロード長を加算した値を持つ単一バイトと、その後に続く各アイテムのRLPエンコーディングの連結で構成されます。 したがって、最初のバイトの範囲は [0xc0, 0xf7](10進数で[192, 247])となります。
• リストの合計ペイロードが55バイトを超える場合、RLPエンコーディングは、0xf7にペイロードの長さ(バイナリ形式)のバイト数を加えた値を持つ単一バイト、その後にペイロードの長さ、さらにその後に各アイテムのRLPエンコーディングの連結が続く構成となります。 したがって、最初のバイトの範囲は [0xf8, 0xff](10進数で [248, 255])となります。

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

1def rlp_encode(input):
2    if isinstance(input,str):
3        if len(input) == 1 and ord(input) < 0x80:
4            return input
5        return encode_length(len(input), 0x80) + input
6    elif isinstance(input, list):
7        output = ''
8        for item in input:
9            output += rlp_encode(item)
10        return encode_length(len(output), 0xc0) + output
11
12def encode_length(L, offset):
13    if L < 56:
14         return chr(L + offset)
15    elif L < 256**8:
16         BL = to_binary(L)
17         return chr(len(BL) + offset + 55) + BL
18    raise Exception("input too long")
19
20def to_binary(x):
21    if x == 0:
22        return ''
23    return to_binary(int(x / 256)) + chr(x % 256)
すべて表示
コピー

実例

• 文字列「dog」= [ 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 ]
• 文字列 \ , 'e', 'l', 'i', 't' ]

RLPデコーディング

RLPエンコーディング規則とプロセスに従って、RLPデコードの入力は、バイナリデータ配列とみなされます。 RLPのデコーディングプロセスは、次のようになります。

1. 入力データの最初のバイト(すなわち、プレフィックス)に従ってデータ型、実際のデータ長、オフセットをデコードします;

2. データのタイプおよびオフセットに応じて、正の整数に関する最小エンコード規則に従って、対応するデータをデコードします。

3. 残りの入力のデコードを続行

その中で、データ型とオフセットのデコード規則は次のようになります。

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    raise Exception("input does not conform to RLP encoding form")
35
36def to_integer(b):
37    length = len(b)
38    if length == 0:
39        raise Exception("input is null")
40    elif length == 1:
41        return ord(b[0])
42    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プレプリント arXiv:2009.13769. (opens in a new tab)

関連トピック

• パトリシア・マークル・トライ