RLP符号化および復号化

GitHub上の英語の紹介(復号部分は本人が編集した):https://github.com/ethereum/wiki/wiki/RLP
RLP(Recursive Length Prefix、再帰的な長さ接頭辞)は、任意のネストされたバイナリ配列データを符号化するために使用できる符号化規則である.RLP符号化の結果もバイナリシーケンスである.RLPは、主にデータをシーケンス化／逆シーケンス化するために使用される.
目次

1. RLPデータ定義

2. RLP符号化規則

3. RLP符号化例

4. RLP復号規則

5. まとめ

1.RLPデータ定義

RLP符号化の定義は、以下の2種類の下位データのみを処理する.

文字列(string)はバイト配列を指す.たとえば、空欄「単語のように」cat、文「Lorem ipsum dolor sit amet,consectetur adipisicing elit」などです.

リスト(list)は、文字列とリストを含むネスト可能な構造です.たとえば、空のリスト[]は、ネストされたリストの複雑なリスト[[cat],[[puppy],[cow],[horse],[[[]],[pig],[],[sheep]]のように、2つの文字列を含むリスト[[cat],[dog]]のようになります.

RLP符号化を行うには、すべての上位層タイプのデータを上記の2種類のデータに変換する必要がある.変換のルールRLP符号化は統一的に規定されず、変換ルールをカスタマイズすることができる.例えばstructはリストに変換することができる.intはバイナリシーケンスに変換できます(文字列のようなもので、ヘッダ0を削除し、大端モードで表さなければなりません).mapタイプは、kとvからなる構造体、kが辞書順に並べられたリスト:[[k 1,v 1],[k 2,v 2]...]などに変換することができる.
上記のデータ型定義から、RLP符号化データはネスト可能であることが分かる.RLP符号化の名前から分かるように、RLP符号化は再帰的であることは、以下のルールおよびコードから分かる.

2.RLP符号化規則

RLP符号化の重点は、元のデータの前に数バイトのプレフィックスを追加することであり、このプレフィックスはデータの長さに関連し、再帰的である.
RLP符号化における長さは、データの実際の記憶空間のバイトサイズであり、先頭0の正の整数を除いて、大端モードで表されるバイナリフォーマットで表される.
RLP符号化所定データ(文字列またはリスト)の長さの長さは、8バイトを超えてはならない.8バイトを超えると、1バイトの接頭辞が格納されないためです.

文字列の長さが1バイトであり、その値が[0 x 00,0 x 7 f]の範囲である場合、RLP符号化は文字列そのものである.すなわち、接頭辞は空であり、接頭辞で文字列自体を表す.

それ以外の場合、1つの文字列の長さが0〜55バイトである場合、RLP符号化が接頭辞追従文字列自体であり、接頭辞の値は0 x 80に文字列の長さを加えたものである.このルールでは文字列の最大長は55であるため、接頭辞の最大値は0 x 80+55=0 xb 7であるため、本ルールでは接頭辞(最初のバイト)の取値範囲は[0 x 80,0 xb 7]である.

文字列の長さが55バイトより大きい場合、RLP符号化は、プレフィックス付き文字列の長さであり、文字列自体に続く.接頭辞の値は、0 xb 7に文字列長を加えたバイナリ形式のバイト長(すなわち、文字列長の記憶長)である.すなわち、文字列の長さは追加の空間で格納され、接頭辞には文字列の長さだけが格納されます.例えば、1つの長さが1024の文字列であり、文字列長のバイナリ形式がx 04x 00であるため、文字列長の長さは2バイトであるため、接頭辞は0 xb 7+2=0 xb 9であるべきであり、これにより得られるRLP符号化はxb 9x 04x 00であり、文字列自体に続く.文字列長の長さは少なくとも1バイトの記憶が必要であるため、接頭辞の最小値は0 xb 7+1=0 xb 8である.また、長さの最大値は8バイトであるため、接頭辞の最大値は0 xb 7+8=0 xbfであるため、本規則では接頭辞の取値範囲は[0 xb 8,0 xbf]である.

以上の3つのルールは文字列に対して、次の2つのルールはリストに対してです.リストの任意のネストのため、リストの符号化は再帰的であり、まず最下層リストを符号化し、それから徐々に外層リストに符号化する.1つのリストの全長(payload、リストのすべての項目が符号化されてつなぎ合わせられたバイトサイズ)が0〜55バイトである場合、そのRLP符号化は、リスト内の各項目のRLP符号化にプレフィックスが順次続く.接頭辞の値は、0 xc 0とリストの合計長です.このルールでは、接頭辞の値範囲は[0 xc 0,0 xf 7]です.この規則は規則2と類似している.

リストの合計長さが55バイトより大きい場合、そのRLP符号化は、リスト内の各要素アイテムのRLP符号化に接頭辞付きリストの長さである.接頭辞の値は、0 xf 7にリストの全長を加えた長さです.符号化された最初のバイトの値範囲は[0 xf 8,0 xff]である.この規則は規則3と類似している.

コードは次のとおりです.

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

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

3.RLP符号化の例

整数0('x 00')=[0 x 00](ルール1)

整数1024('x 0400')=[0 x 82,0 x 04,0 x 00](ルール2)

空文字列(‘null’)=[0 x 80](ルール2)

文字列「dog」=[0 x 83,‘d’,‘o’,‘g’(ルール2)

文字列「Lorem ipsum dolor sit amet,consectetur adipisicing elit」=[0 xb 8,0 x 38,‘L’,‘o’,‘r’,‘e’,‘m’,’,,,,,...,‘e’,‘l’,‘i’,‘t’」(ルール3)

空のリスト[]=[0 xc 0](ルール4)

リスト["cat","dog"]=[0 xc 8,0 x 83,‘c’,‘a’,‘t’,0 x 83,‘d’,‘o’,‘g’](ルール4)

ネストリスト[[],[]],[[],[]]]]]=[0 xc 7,0 xc 0,0 xc 1,0 xc 0,0 xc 3,0 xc 0,0 xc 1,0 xc 0](ルール4)

4.RLP復号規則

RLP符号化規則およびプロセスに従って、RLP復号化の入力はすべてバイナリ文字配列と見なされ、そのプロセスは以下の通りである.

入力先頭バイトデータに基づいて、データ型、実際のデータ長、および位置を復号する.

は、タイプと実際のデータに基づいて、異なるタイプのデータを復号する.

残りのデータの復号を継続する.

ここで、復号データ型、実際のデータ型、および位置のルールは、次のとおりです.

ヘッダバイトの値が[0 x 00,0 x 7 f]の範囲内である場合、データは文字列であり、文字列はヘッダバイト自体である.

先頭バイトの値が[0 x 80,0 xb 7]の範囲である場合、データは文字列であり、文字列の長さは先頭バイトから0 x 80を減算し、文字列は先頭バイトの後にある.

先頭バイトの値が[0 xb 8,0 xbf]の範囲内である場合、データは文字列であり、文字列の長さのバイト長は先頭バイトから0 xb 7を減算し、データの長さは先頭バイトの後にあり、文字列はデータの長さの後にある.

先頭バイトの値が[0 xc 0,0 xf 7]の範囲の場合、そのデータはリストであり、この場合、リストの各データを再帰的に復号する必要がある.リストの全長(リストの各符号化後の長さの和)は、先頭バイトから0 xc 0を減算することに等しく、リストの各項目は先頭バイトの後に位置する.

先頭バイトの値が[0 xf 8,0 xff]の範囲の間にある場合、このデータはリストであり、リストの全長のバイト長は先頭バイトから0 xf 7を減算し、リストの全長は先頭バイトの後にあり、リストの各項目はリストの全長の後にある.

コードは次のとおりです.

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)
    else:
        raise Exception("input don't conform 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])
    else:
        return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

5.まとめ

RLP符号化の利点は、他のシーケンス化方法と比較して、柔軟な長さ接頭辞を用いてデータの実際の長さを表し、かなり大きなデータを再帰的に符号化できることである.
RLP符号化されたデータを受信または復号すると、1バイト目からデータの種類、おおよその長さ、データ自体などの情報を推定することができる.他のシーケンス化方法では,1バイト目に基づいてこれほど多くの情報量を得ることはできない.