EthereumのRLPエンコーディングについて-Yellow Paper AppendixBより

EthereumのYellowPaperを元に、Ethereum独自のRLPエンコーディングについて実験してみました。

RLPエンコーディングとは

RLP(Recursive Length Prefix)エンコーディングはEthereumで利用されるシンプルな符号化の方法です。

独自にエンコードしており、内部DBに保存するとき、RLPエンコーディングを利用しています

RLP is intended to be a highly minimalistic serialization format; its sole purpose is to store nested arrays of bytes. Unlike protobuf, BSON and other existing solutions, RLP does not attempt to define any specific data types such as booleans, floats, doubles or even integers

RLPは高度に最小化したシリアライゼーションフォーマットで、ネストされたByte配列を保存する目的のためにある。protobufやBSONなどとは違って、BooleanやFloat、DoubleやIntegerさえ定義しない

Ethereum Wiki - Design-Rationale#rlpより

Yellow Paperには定義が書かれており、実際にコードを動かして実験してみます。

5つのエンコードパターン

バイト配列の場合

・If the byte-array contains solely a single byte and that single byte is less than 128, then the input is exactly equal to the output.

・If the byte-array contains fewer than 56 bytes, then the output is equal to the input pre fixed by the byte equal to the length of the byte array plus 128.

・Otherwise, the output is equal to the input prefixed by the minimal-length byte-array which when interpreted as a big-endian integer is equal to the length of the input byte array, which is itself prefixed by the number of bytes required to faithfully encode this length value plus 183.

1. バイト配列が単純な1バイトで、128より小さい時、そのままアウトプットする
2. バイト配列が56バイトより小さい場合、バイト配列の長さ＋128に等しいバイトを加えた配列に等しくなる
3. 他の場合、ビッグエンディアン整数として解釈した時に最小となる入力バイト配列の長さを、接頭辞として入力に付与する。加えて、その長さに183を足した長さを接頭辞に付与する

バイト配列でない場合

・If the concatenated serialisations of each contained item is less than 56 bytes in length, then the output is equal to that concatenation prefixed by the byte equal to the length of this byte array plus 192.

・Otherwise, the output is equal to the concatenated serialisations prefixed by the minimal-length byte-array which when interpreted as a big-endian integer is equal to the length of the concatenated serialisations byte array, which is itself prefixed by the number of bytes required to faithfully encode this length value plus 247.

4.それぞれの項目について連結してシリアライゼーションが56バイト未満の長さの場合、アウトプットは、このバイト配列の長さに192を加えた長さに等しいバイトを接頭辞に加えたものになる

5.それ以外の場合、ビッグエンディアンの整数として解釈した最小の長さを接頭辞に加える。更に加えた接頭辞をビッグエンディアンの整数として解釈した時の長さに247を加えた長さを接頭辞に付与する

実験に用いたコード

rlpエンコーディングには、go-ethereumのrlpパッケージを使います。

実験コード

package main

import (
    "encoding/hex"
    "fmt"
    "github.com/ethereum/go-ethereum/rlp"
)

//バイト配列の場合
var case1Inputs = []uint32{1, 2, 127}
var case2Inputs = []string{"dog", "doge", "cat", "0123456789012345678901234567890123456789012345678901234"}
var case3Inputs = []string{"01234567890123456789012345678901234567890123456789012345"}
//バイト配列以外の場合
var case4Inputs = []uint{1,2,3}
var case5Inputs = []uint{1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6}

func rlpEnc(val interface{}) {
    encoded, err := rlp.EncodeToBytes(val)
    if err != nil {
        panic(err)
    }
    fmt.Println("input:", val, "=> encoded:", hex.EncodeToString(encoded))

}

func main() {
    fmt.Println("case1")
    for _, input := range case1Inputs {
        rlpEnc(input)
    }

    fmt.Println("case2")
    for _, input := range case2Inputs {
        rlpEnc(input)
    }

    fmt.Println("case3")
    for _, input := range case3Inputs {
        rlpEnc(input)
    }

    fmt.Println("case4")
    rlpEnc(case4Inputs)

    fmt.Println("case5")
    rlpEnc(case5Inputs)
}

出力結果

case1
input: 1 => encoded: 01
input: 2 => encoded: 02
input: 127 => encoded: 7f
case2
input: dog => encoded: 83646f67
input: doge => encoded: 84646f6765
input: cat => encoded: 83636174
input: 0123456789012345678901234567890123456789012345678901234 => encoded: b730313233343536373839303132333435363738393031323334353637383930313233343536373839303132333435363738393031323334
case3
input: 01234567890123456789012345678901234567890123456789012345 => encoded: b8383031323334353637383930313233343536373839303132333435363738393031323334353637383930313233343536373839303132333435
case4
input: [1 2 3] => encoded: c3010203
case5
input: [1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6] => encoded: f8380102030405060708098001020304050607080980010203040506070809800102030405060708098001020304050607080980010203040506

バイト配列をRLPエンコーディングする場合

1. バイト配列が単純な1バイトで、128より小さい時、そのままアウトプットする

バイト配列が単純な1バイトで、128より小さい時、そのままアウトプットするケースを見てみましょう。

encodedを16進数で考えると入力値と同じ数値が出てきています。

input: 1 => encoded: 01
input: 2 => encoded: 02
input: 127 => encoded: 7f

2. バイト配列が56バイトより小さい場合、バイト配列の長さ＋128に等しいバイトを加えた配列に等しくなる

コードでdogをRLPエンコーディングをした結果を見てみます。

input: dog => encoded: 83646f67

エンコード後の数値は83 64 6f 67の要素に分解できます。

左から見てみましょう。83は16進数であり、10進数で考えると131に等しくなります。（16*8 + 3 = 131）

この131がバイト配列の長さ＋128に等しいバイトを加えた数`と等しくなるはずです。バイト配列の長さについて、dogは3バイトのため、合計は131になります。

len(dog) + 128 = 3 + 128 = 131

131は16進数では0x83となり、一致することがわかります。

次の0x64,0x6f,0x67についてはそれぞれd,o,gと対応する数値です。

同様に、dogeでRLPエンコーディングをした結果を見てみます。

input: doge => encoded: 84646f6765

エンコード後の数値は84 64 6f 67 65の要素に分解できます。

84は16進数であり、10進数で考えると132に等しくなります。

dog同様に、バイト配列の長さ+128に等しいバイトを計算すると、今度はdogeで4バイトの長さのため4+128=132になります。

次の0x64,0x6f,0x67,0x65についてはそれぞれd,o,g,eと対応する数値になリます。

3. 他の場合、ビッグエンディアン整数として解釈した時に最小となる入力バイト配列の長さを、接頭辞として入力に付与する。加えて、その長さに183を足した長さを接頭辞に付与する

input: 01234567890123456789012345678901234567890123456789012345 => encoded:b8383031323334353637383930313233343536373839303132333435363738393031323334353637383930313233343536373839303132333435
0138 / 0x0204
0xb8 : 183 + LEN(BE(LEN(input))) = 183 + LEN([38]) = 183 + 1 = 184 = 0xb8
0x38 : BE(LEN(input)) = BE(56) = BE(0x38) = 0x38
0x30 : 0, 0x31: 1, … 0x35 : 5

エンコード結果は

b8383031323334353637383930313233343536373839303132333435363738393031323334353637383930313233343536373839303132333435

です。

接頭辞b838を見ます。

後の0x38から確認します。

0x38はビッグエンディアン整数として解釈した時に最小となる入力バイト配列の長さを、接頭辞として入力に付与するでついたものになります。

インプットの長さは56バイトであり16進数では0x38となるため解釈が合います。

次に一番頭の0xb8を確認します。加えて、その長さに183を足した長さを接頭辞に付与するとなります。

接頭辞としてついた分は0x38だけです。つまり、1個だけになります。

183 + 1 = 184がつくことになります。184を16進数に直すと0xb8となり、計算通りです。

接頭辞以降は303132...と続いています。123...というインプットに対応する16進数が連なっている結果です。

バイト配列以外をRLPエンコーディングする場合

4. 56バイト未満の場合

次はバイト配列以外のパターンを見ていきます。56バイト未満の場合の{1 2 3}を見てみます。

input: [1 2 3] => encoded: c3010203

uint{1,2,3}のinputに対してはprefix C3がついて、後ろに010203と続いています。

192は10進数に直すと0xC0です。数字が3個あるため0xC0 + 0x03 = 0xC3となります。c3010203となっています。

定義は(192 + ‖s(x)‖)・s(x)でした。

• 192 + ‖s(x)‖ = 192 + 3 = 0xc3
• s(x) = 010203

なので当てはめると想定通りの結果になっていることがわかります。

5. 56バイト以上の場合

今度は56バイトをインプットにしてみます。

input: [1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6] => encoded: f8380102030405060708090a0102030405060708090a0102030405060708090a0102030405060708090a0102030405060708090a010203040506

接頭辞はf838です。

0xf8は10進数にすると248,

0x38は10進数にすると56です。

• 247 + ‖BE(‖s(x)‖)‖ … 247 + 1 = 0xf7 + 0x01 = 0xf8

• BE(‖s(x)‖) … 56 = 0x38

• s(x) … 01020304050607...0506

となり、想定通りの結果となります。

まとめ

RLPエンコーディングは独特の形式ですが、実はこう見ると単純なつなぎ合わせで理解できることがわかります。

Etheruem内部のデータを理解する際には、RLPのエンコード・デコードを利用する機会も多そうですが、うまく利用していけば符号化前のデータも取れそうで解釈しやすそうです。

先日した発表でもRLPエンコーディングの話を含めています。参考までに。（この記事と内容は被っています）