RLP
※RLPの翻訳です。
RLPの目的は、どこまでも入れ子にすることのできるバイナリデータの配列を符号化することである。RLPはEthereumにおいてオブジェクトを直列化するために使用される主たる符号化方式である。RLPの唯一の目的は、構造を符号化することであって、特定の基本データ型(たとえば、文字列型、整数型、不動小数点数型)の符号化は、高次のプロトコルに委譲されている。Ethereumにおいては、整数は通常ビッグエンディアンのバイナリ形式で表現される。RLPを用いて辞書(dictionary)を符号化したい場合には、鍵(key)を辞書式順序に並べた [[k1,v1],[k2,v2]...]という形式を使用するか、Patricia木(Patricia tree)の符号化を使用することが推奨される。Ethereumでは後者の方法が採用されている。
定義
RLP符号化関数は、項目(item)を引数として取る。項目は以下のように定義される。
・文字列(バイト配列)は項目である。
・項目のリストは項目である。
たとえば、長さが空の文字列は項目である。「cat」という単語を含む文字列は項目である。任意の数の文字列を含むリストは項目である。 ["cat",["puppy","cow"],"horse",[],"pig",[""],"sheep"]のようなより複雑なデータ構造は項目である。以降の本記事の文脈では、「文字列」が「バイナリデータを表す任意の長さのバイト配列」の同義語として使用されていることに注意してほしい。特別な符号化が使用されることはないし、文字列の内容に関する如何なる情報も含意されない。
RLP符号化は次のように定義される。
・長さが1の文字列で、値が[0x00, 0x7f]の範囲であるものは、その文字列自体がそのRLP符号化である。
・上に当て嵌まるもの以外で長さが0から55までの文字列は、0x80にその文字列の長さを加えたものに、その文字列自体を繋げたものがそのRLP符号化である。そのため、最初のバイトの値の範囲は、[0x80, 0xb7]である。
・長さが56以上の文字列は、0xb7にその文字列の長さをバイナリ形式にしたものの長さを加えたものに、その文字列の長さを繋げ、更に、その文字列自体を繋げたものがそのRLP符号化である(訳注:ただし、文字列の長さは8バイトまでのようだ)。たとえば、長さが1024の文字列は、\xb9\x04\x00にその文字列自体を繋げたものがそのRLP符号化となる。
・リストの全ての項目の長さを合計した結果が0から55までである場合には、0xc0にそのリストの全ての項目の長さを合計した結果を加えたものに、全ての項目をRLP符号化したものを結合したものを繋げたものがそのRLP符号化である。そのため、最初のバイトの値の範囲は、[0xc0, 0xf7]である。
・リストの全ての項目の長さを合計した結果が56以上である場合には、0xf7にそのリストの全ての項目の長さを合計した結果をバイナリ形式にしたものの長さを加えたものに、そのリストの全ての項目の長さを合計した結果を繋げ、更に、全ての項目をRLP符号化したものを結合したものを繋げたものがそのRLP符号化である。そのため、最初のバイトの値の範囲は、[0xf8, 0xff]である。
コードで表すと以下のようになる。
def rlp_encode(input):
if isinstance(input,str):
if len(input) == 1 and chr(input) < 128: return input
else: return encode_length(len(input),128) + input
elif isinstance(input,list):
output = encode_length(len(input),192)
for item in input: output += rlp_encode(item)
return 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
else:
raise Exception("input too long")
def to_binary(x):
return '' if x == 0 else to_binary(int(x / 256)) + chr(x % 256)
例
The string "dog" = [ 0x83, 'd', 'o', 'g' ]
The list [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
The empty string ('null') = [ 0x80 ]
The empty list = [ 0xc0 ]
The integer 15 = [ 0x0f ]
The integer 1024 = [ 0x82, 0x04, 0x00 ]
The set theoretical representation of two, [ , [], [ , [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
The string "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]