はじめに
Ethereumの勉強しているため、理解したことをまとめる。
第一弾は、RLP編。
※間違っている情報があれば、ご指摘いただければ幸いです。
RLPは何の略？
RLPとは、Recursive Length Prefixの略である。
・Recursive・・・再帰的
・Length・・・長さ
・Prefix・・・接頭辞
直訳すると、「再帰的な長さの接頭辞」という意味になる。
データの長さを定義するPrefixというイメージで良いと思う。
RLPの概要
RLPは、Ethereumで利用されている、バイト列を定義するためのエンコード方式である。
Ethereumでは、RLPを利用することで、データの格納効率を上げている。
先頭バイトに、バイト列の長さと構造（バイト列か、配列か）を示す接頭辞をつけるエンコード方式である。
さらに配列の場合、各要素の先頭1byteにも、RLPの接頭辞が含まれている。
ドキュメント
https://ethereum.org/en/developers/docs/data-structures-and-encoding/rlp/
接頭辞の5パターン
RLPでは接頭辞により、データの表し方が5パターンに分けられる。
| # | 接頭辞(1byte) | 接頭辞の種類 | データ型 | 説明 |
|---|---|---|---|---|
| 1 | 0x00 ～ 0x7f | 128 | バイト列 | 接頭辞が0x00～0x7fの範囲の場合は、接頭辞自体がデータを表す。 （厳密には、nullを表す0x80も、接頭辞自体がデータを表す。） |
| 2 | 0x80 ～ 0xb7 | 56 | バイト列 | 55byteまでのバイト列を表す。 [接頭辞 - 0x80] がバイト列の長さになる。 0x80はnullを表す。 0xb7は55byteのバイト列を表す。 |
| 3 | 0xb8 ～ 0xbf | 8 | バイト列 | 55byteより長いバイト列を表す。 [接頭辞 - 0xb7]は、バイト列の長さの情報が、接頭辞以降の何バイトにあるのかを表す。 0xb8は接頭辞以降の1byteにバイト列の長さの情報があることを表し、バイト列の長さは、0byte ～ 255byteである。 0xbfは接頭辞以降の8byteにバイト列の長さの情報があることを表し、バイト列の長さは、0byte ～ 18,446,744,073,709,551,615byte( = 0xffffffffffffffff )である。 |
| 4 | 0xc0 ～ 0xf7 | 56 | 配列 | 合計のペイロードが55byteまでの配列を表す。 ペイロードは配列の長さとイコールではない。配列の各要素もRLPで表されるため、ペイロードの中にはRLPの接頭辞の1byteがたくさん入ることになる。 ペイロードの長さは[接頭辞 - 0xc0]である。 0xc0は空の配列[]を表す。 0xf7は55byteのペイロードを持つ配列を表す。 接頭辞が0xf7だったとしても、配列の要素数は1個かもしれないし、10個かもしれない。 |
| 5 | 0xf8 ～ 0xff | 8 | 配列 | ペイロードが55byteより長い配列を表す。 [接頭辞 - 0xf7] が、ペイロードの長さの情報が、接頭辞以降の何バイトにあるのかを表す。 0xf8は、0byte ～ 255byteの範囲のペイロードを表す。 0xffは、0byte ～ 18,446,744,073,709,551,615byte( = 0xffffffffffffffff )の範囲のペイロードを表す。 |
例
RLPの例を記載する。
前提として、アルファベット1文字は全て1byteで表せる。
また、半角空白も1byteで表せる。
RLPでエンコードされた整数0
0を16進数で表すと0x00である。
0x00は0x00 ～ 0x7fに含まれるので、パターン1に当てはまる。
パターン1では、接頭辞自体がデータを表すため、0をRLPエンコードすると、【0x00】となる。
RLPでエンコードされていない整数0
パターン1で整数0を表すと、RLPでエンコードされた整数0を表すことになる。
エンコードされていない整数0を表す場合、パターン2を利用する。
整数0をRLPエンコードすると、【0x80】となる。
RLPでエンコードされた整数15
15を16進数で表すと0x0fである。
0x0fは0x00 ～ 0x7fに含まれるので、パターン1に当てはまる。
パターン1では、接頭辞自体がデータを表すため、15をRLPエンコードすると、【0x0f】となる。
dog
アルファベット1文字は1byteで表せるので、dogは3byteのデータである。よって、パターン2に当てはまる。
[接頭辞 - 0x80] が3とならなければならないので、接頭辞は、[0x83]となる。
接頭辞以降の3byteに、d・o・gを表すバイト列を格納することになる。
dogをRLPエンコードすると、【0x83 d o g】となる。
[ "cat", "dog" ]
ペイロードが55byte以下の配列であるため、パターン4に当てはまる。
[ "cat", "dog" ]のペイロードの計算は下記のようになる。
・catの接頭辞が1byte
・catはアルファベット3文字なので3byte
・dogの接頭辞が1byte
・dogはアルファベット3文字なので3byte
・合計8byte
ペイロードの長さは、[接頭辞 - 0xc0]で表される。
[接頭辞 - 0xc0]が8とならなければならないので、接頭辞は、[0xc8]となる。
接頭辞以降は、catとdogをそれぞれRLPエンコードしたbyte列を格納することになる。
[ "cat", "dog" ]をRLPエンコードすると、【0xc8 0x83 c a t 0x83 d o g】となる。
null
nullはパターン2に当てはまる。
nullをRLPエンコードすると、【0x80】となる。
空の配列
空の配列はパターン4に当てはまる。
空の配列をRLPエンコードすると、【0xc0】となる。
エンコードされた整数 1024
1024を16進数で表すと0x0400なので、1024は2byteのデータである。よって、パターン2に当てはまる。
[接頭辞 - 0x80] が2とならなければならないので、接頭辞は、[0x82]となる。
接頭辞以降の2byteに、1024を表すバイト列を格納することになる。
1024をRLPエンコードすると、【0x83 0x04 0x00】となる。
[ [], [[]], [ [], [[]] ] ]
[ [], [[]], [ [], [[]] ] ] は、ペイロードが55byte以下の配列であるので、パターン4に当てはまる。
[ [], [[]], [ [], [[]] ] ]は、下記の3つの要素を持つ配列である。
① []
② [[]]
③ [ [], [[]] ]
各要素はペイロードが55byte以下の配列であるので、各要素はパターン4に当てはまる。
①は空の配列なので、[0xc0]で表される。
②は空の配列を要素に持つ、要素数1の配列である。ペイロードは1である。
よって②は、[0xc1 0xc0]で表される。
③は、①と②を要素に持つ配列である。ペイロードは3である。
よって③は、[0xc3 0xc0 0xc1 0xc0]で表される。
①, ②, ③をまとめると、[ [], [[]], [ [], [[]] ] ] のペイロードは7である。
[ [], [[]], [ [], [[]] ] ] をRLPエンコードすると、【0xc7 0xc0 0xc1 0xc0 0xc3 0xc0 0xc1 0xc0】となる。
Lorem ipsum dolor sit amet, consectetur adipisicing elit
Lorem ipsum dolor sit amet, consectetur adipisicing elitは、空白や「,」も含め56文字ある。よって、パターン3に当てはまる。
56は1byteで表すことできる。
よって、「[接頭辞 - 0xb7] が1とならなければならないので、接頭辞は、[0xb8]となる。
56は16進数で表すと0x38である。
Lorem ipsum dolor sit amet, consectetur adipisicing elitをRLPエンコードすると、【0xb8 0x38 L o r m 空白 i p s u m d o .......... c i n g 空白 e l i t】となる。
まとめ
Ethereumでデータをどのようにエンコードしているかを理解できた。
merkle patricia trieでも、RLPが利用されているらしいので、理解していきたい。