RustでEthereumのRLP

RLPとは

Recursive Length Prefixのアクロニムで、バイナリで、木構造を定義するもの。
葉ノードは、バイト配列。
ノードを短く表現するために、ノードの大きさに応じたLength Prefixをつけていく。
Ethereumのトランザクションで使われている。

ノードの種類

• バイト配列
• バイト配列のリスト

どちらのタイプのノードも、Length Prefixを除いた中身の長さは、64bitに収める必要がある。

エンコード

エンコード対象がバイト配列ノードの場合

まず、エンコード対象になるものを、バイト配列に変換する。
エンコード対象がIntegerの場合は、エンコード対象をBigEndianでByteに変換して、先頭の0を取り除く。それ以外の場合は、バイト列に変換してそのまま使う。

ルール

上から順に当てはまるルールを探す。はじめに当てはまったルールを適用してエンコードは完了。見つからなければエンコードエラー。

1. エンコード対象が１バイトで、値が0x00から0x7fの範囲にある場合は、そのバイトがLength Prefix。またLength Prefixは同時に値としても使われるので、Length Prefixのみがエンコード結果。

   （例）

   エンコード対象	エンコード結果
   0x00	[0x00]
   0x4a	[0x4a]

2. 1に当てはまらず、エンコード対象の長さが55バイト以下の場合は、0x80 + エンコード対象の長さがLength Prefix。Length Prefix + エンコード対象がエンコード結果。

   （例）

   エンコード対象	エンコード結果
   空配列	[0x80]
   0x80	[0x81, 0x80]
   "dog"	[0x83, 'd', 'o', 'g']

3. 2に当てはまらず、エンコード対象の長さが64bitでおさまる場合は、以下の、A + BがLength Prefixで、Length Prefix + エンコード対象がエンコード結果。

   記号	内容
   A	0xb7 + エンコード対象の長さのバイト表現での長さ（3の時点で空配列は除外されているので、長さは最低1になる）
   B	エンコード対象の長さのバイト表現

   例えば、長さ1024(= 0x0400)の文字列をエンコードする場合、

   記号	内容
   A	0xb9 (0xb7に、0x04,0x00の長さ2を足したもの)
   B	0x04, 0x00

   なので、A + B + エンコーディング対象は、[0xb9, 0x04, 0x00, ...1024バイトの文字列...]

エンコード対象がバイト配列のリストの場合

リストの要素をそれぞれエンコードして、全てを連結して一つにしたものがエンコード対象になる。要素がリストの場合は、葉ノードに当たるまで再帰的にエンコードする。

ルール

上から順に当てはまるルールを探す。はじめに当てはまったルールを適用してエンコードは完了。見つからなければエンコードエラー。

1. エンコード対象の長さが55以下の場合は、0xc0 + エンコード対象の長さがLength Prefix。Length Prefix + エンコード対象がエンコード結果。

   例： ["cat", "dog"] をエンコードする場合

   1. "cat"に、エンコードルール２が適用されて、[0x83, 'c', 'a', 't']
   2. "dog"も、同じルールが適用されて[0x83, 'd', 'o', 'g']
   3. 1と2を連結したエンコード対象は、[0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g']
   4. エンコード対象の長さは8なので、0xc0 + 8 = 0xc8がLengh Prefix
   5. Length Prefix + エンコード対象で、エンコード結果は、[0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g']

2. 1に当てはまらず、エンコード対象の長さが64bitに収まる場合は、以下の、A + BがLength Prefix。Length Prefix + エンコード対象がエンコード結果。

   記号	内容
   A	0xf7 + エンコード対象の長さのバイト表現での長さ（1の時点で空配列は除外されているので、長さは最低1になる）
   B	エンコード対象の長さのバイト表現

   例えば、[長さ1024の文字列, "dog"]をエンコードする場合、

   1. 上と同じやり方で、長さ1024の文字列をエンコードして、[0xb9, 0x04, 0x00, ...1024バイトの文字列...]
   2. 上と同じやり方で、"dog"をエンコードして、[0x83, 'd', 'o', 'g']
   3. 1と2を連結したエンコード対象は、[0xb9, 0x04, 0x00, ...1024バイトの文字列..., 0x83, 'd', 'o', 'g']
   4. エンコード対象の長さは、3 + 1024 + 4 = 1031 (0x0407)
   5. 0x0407は2バイトなので、Aは、0xf7 + 2 = 0xf9
   6. Bは、0x04, 0x07
   7. A + B + エンコード対象は、[0xf9, 0x04, 0x07, 0xb9, 0x04, 0x00, ...1024バイトの文字列..., 0x83, 'd', 'o', 'g']

Length Prefixのまとめ

Prefix	意味
0x00 - 0x7f	プリフィックス自体で長さ１のバイト配列 (A)
0x80 - 0xb7	(A)を除いた、長さ0から55までのバイト配列
0xb8 - 0xbf	56以上で、64bitにおさまる長さのバイト配列
0xc0 - 0xf7	プリフィックスを含めたリスト要素の合計の長さが55以下の、バイト配列のリスト
0xf8 - 0xff	56以上で、64bit内でおさまる長さの、プリフィックスを含めたリスト要素の合計の長さを持つ、バイト配列のリスト

デコード

まずLength Prefixを取得して、その内容に応じてその後のデータを処理していく。詳細はサンプルコードへ。

サンプルコード

Rustで実装。
https://github.com/parumu/eth-rlp

仕様