Ethereum理解①（RLP編）

## はじめに
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の範囲の場合は、接頭辞自体がデータを表す。<br>（厳密には、nullを表す0x80も、接頭辞自体がデータを表す。） |
| 2 | 0x80 ～ 0xb7 | 56 |  バイト列 | 55byteまでのバイト列を表す。<br>[接頭辞 - 0x80] がバイト列の長さになる。<br>0x80はnullを表す。<br>0xb7は55byteのバイト列を表す。 |
| 3 | 0xb8 ～ 0xbf | 8 |  バイト列 | 55byteより長いバイト列を表す。<br>[接頭辞 - 0xb7]は、**バイト列の長さの情報が、接頭辞以降の何バイトにあるのか**を表す。<br> 0xb8は接頭辞以降の1byteにバイト列の長さの情報があることを表し、バイト列の長さは、0byte ～ 255byteである。<br> 0xbfは接頭辞以降の8byteにバイト列の長さの情報があることを表し、バイト列の長さは、0byte ～ 18,446,744,073,709,551,615byte( = 0xffffffffffffffff )である。 |
| 4 | 0xc0 ～ 0xf7 | 56 |  配列 | 合計のペイロードが55byteまでの配列を表す。<br>ペイロードは配列の長さとイコールではない。配列の各要素もRLPで表されるため、ペイロードの中にはRLPの接頭辞の1byteがたくさん入ることになる。<br>ペイロードの長さは[接頭辞 - 0xc0]である。<br>0xc0は空の配列[]を表す。<br>0xf7は55byteのペイロードを持つ配列を表す。<br>接頭辞が0xf7だったとしても、配列の要素数は1個かもしれないし、10個かもしれない。 |
| 5 | 0xf8 ～ 0xff | 8 |  配列 | ペイロードが55byteより長い配列を表す。<br>[接頭辞 - 0xf7] が、**ペイロードの長さの情報が、接頭辞以降の何バイトにあるのか**を表す。<br>0xf8は、0byte ～ 255byteの範囲のペイロードを表す。<br>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が利用されているらしいので、理解していきたい。