今回はEthereumで用いられている２つのデータエンコード方式、RLP(Recursive Length Prefix)とPatricia Tree(Trie)について説明します。
RLP(Recursive Length Prefix)
概要
RLPはその名の通り、「再帰的な長さの接頭辞」です。入れ子構造のバイト列を定義するためのエンコード方式であり、先頭バイトにそのバイト列の長さと構造（フラットなデータか、配列データかのどちらか）を示す接頭辞をつけるエンコード方式です。
単純な文字列"hello world"や、集合論的表現 [ , [], [ , [] ] ]が可能です。
公式のドキュメントは以下になります。
github.com
接頭辞の種別
接頭辞としては以下の5種類が定義されています。
| バイト | 種別 | 説明 |
|---|---|---|
| 0x00 ~ 0x7f | single data | 接頭辞がこの範囲のbyteはそれ自体がデータである。つまり1byteのデータとなる。 |
| 0x80 ~ 0xb7 | multi flat bytes | 55byteまでのデータ列を示す。0x80は長さ0のbyte列である。つまり0x80はnullを示す。 |
| 0xb8 ~ 0xbf | multi flat bytes(larger than 55) | 55byteより長いデータ列を示す。接頭辞は次に続く長さを示すbyteのサイズとなる。 接頭辞から0xb7を引いた残りの数値が次に続く長さを示すbyteである。 1024byteのdata列の場合の接頭辞は、0xb9 0x04 0x00 となる。 |
| 0xc0 ~ 0xf7 | byte array | 合計のペイロードが55byteまでのbyte列の配列を示す。 ペイロード全体の長さは接頭辞から0xc0を引いた値となる。 0xc0は空の配列 "[ ]" を示す。配列の内部にはRLPエンコードされたbyte列が並ぶ。 |
| 0xf8 ~ 0xff | byte array(larger than 55) | ペイロードが55byteより長いbyte列の配列を示す。 接頭辞は次に続く長さを示すbyteのサイズとなる。 接頭辞から0xf7を引いた残りの数値が次に続く長さを示すbyteである。 |
例
以下、公式のwikiにも記載されている例を再掲します。
- 文字列："dog" = [ 0x83, 'd', 'o', 'g' ]
- データの配列： [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
- 空文字列 ('null') = [ 0x80 ]
- 空の配列 = [ 0xc0 ]
- 整数値： 0 = [ 0x80 ]
- エンコードされた数字： 0 ('\x00') = [ 0x00 ]
- エンコードされた数字：15 ('\x0f') = [ 0x0f ]
- エンコードされた数字：1024 ('\x04\x00') = [ 0x82, 0x04, 0x00 ]
- 集合論的表現： [ , [], [ , [] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
- 文字列： "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]
Merkle Patricia Tree(Trie)
概要
以下、日本語wikiからの抜粋です。
Merkle Patricia tree は、あらゆる、「 ( key, value ) の帳簿 」を保存するのに使用できる、 暗号学的認証が付与されたデータ構造を提供します。
O(log(n)) という優秀な計算時間内でデータの挿入、検索、削除が可能であり、 red black tree のような複雑な比較基盤のデータ構造よりも、簡単に理解しコード化する事ができます。
Merkle Patricia Treeはkey、path、valueの3つの要素で構成されます。詳細は後述しますが、Merkle Patricia Treeでは、keyはそのノードのvalueのhash値であり、また、pathをたどるためのbranchノードには、次のノードのkeyが格納されます。このように、pathの構成に他のノードのhash値が関係する構造がMerkleの部分になります。また、Merkle Patricia Treeを構成する各ノードのhash値を元に、rootノードのhash値が決まるため、攻撃者はrootノードのhash値を偽ることなく、任意のノードのvalueを変更することが不可能です。このことを、wikiでは暗号学的認証と呼んでいます。
公式のドキュメントは以下になります。
github.com
前提：基本的なRadix Trie（基数木）の定義
Merkle Patricia Treeを説明する前に、まずは非常に単純なRadix Trieを考えます。
与えられたpath=valueのデータに対して、pathを二ブル(4bitのデータ。1byteの半分)データに分解し、各pathを元にツリーを構成します。pathは二ブルなので、常に次のpathを示すための16個(4bit=>0~15)の子ノードを持ちます。また、valueを格納するための枠も持つため、1つのノードは合計して、17個の枠を持つことになります。
このRadix Trieのノードをbranch nodeとします。
branch nodeは17個の要素を持ち、うち、0〜15までは次のbranch nodeのkeyを保持します。16番目の要素にはそのpathにmapされたvalueを格納します。
言葉で説明すると難しいので、wikiの説明でも使われているdog(0x64 0x6f 0x67)=puppyというデータを格納するBasic Radix Trieを以下に図で示します。
さらに、2つのデータdo=verb、horse=stallionを加えたツリーの状態を以下に図で示します。
図中に表記しているHashA（〜HashK）のあたいは、それぞれのnodeをsha3(rlp(value))した値であり、このhash値はそれぞれのノードのkeyです。このBasic Redix Trieでは以下の順序で与えられたpathからvalueを取得します。
1. root hashを元にkey-valueストアから最初のノードを取得する。
2. pathのbyte列を二ブル列に変換し、その先頭のデータをindex値として取得する。
3. ノードから、2.のindex値に格納されているhash値を取得する。
4. 3. で取得したhash値をkeyにしてkey-valueストアからノードを取得する。
5. pathの終端になるまで、2~4を繰り返す。
6. pathの終端に到達した場合は、現在のノードの16番目の要素をvalueとして取得する。
例えば、pathが"do"の値を取得する場合は、HashAから最初のノードを取り出し -> index 6のhash値を取得 -> HashBのノード取得 -> index 4のhash値を取得 -> HashCのノードを取得 -> index 6のhash値を取得 -> HashDのノードを取得 -> index fのhash値を取得 -> HashEのノードを取得 -> pathの終端に到達したので、16番目の要素を読み取る。
となります。
Merkle Patricia Treeのノードとprefixの種別
上述したBasic Radix Trieはメモリ非常に悪い（branchノードを確保するのに必要なメモリ量は16 * 32byte +
追加される最適化の詳細内容については、公式のwikiを参照ください。ここでは、Merkle Patricia Treeで扱う各種ノードと、ノード識別のためのprefixを紹介します。
ノード種別
| type | 要素数 | 説明 |
|---|---|---|
| branch | 17 | 次のnodeへの分岐を格納するノード。前述したBasic Radix trieで定義したbranch ノードと同様のもの。 |
| leaf | 2 | pathとvalueを持つノード。leafなのでここは終端ノードであり、valueは探索結果の値である。pathは残りの部分パス全てを結合したものになる。 |
| extension | 2 | 分岐が存在しない間のpathをスキップするためのノードpathは分岐が存在しない範囲の二ブルを結合した部分パスとなる。valueには次のbranchノードのhashが格納される。 |
branchとleaf or extensionの識別はRLPデコードで得られたデータ配列の要素数で区別できます。しかしながら、leafとextensionは同じ要素数を持つため、識別できません。そのため、Patricia Merkle Treeではleafとextensionのための識別子を定義しています。
次に、これらの識別子について紹介します。
leafとextensionを区別するための識別子
leafとextensionを区別するための識別子はそのノードが持つpathの先頭に付与されます。しかしながら、pathは二ブル（=4bit）単位でスライスされながら、branchノードに割り当てられるため、pathの二ブルが奇数か偶数か識別するために、それぞれ２種類の識別子が定義されています。具体的には以下の表の通りです。
| bit | node type | path length |
|---|---|---|
| 0000 (0) | extension | even |
| 0001 (1) | extension | odd |
| 0010 (2) | leaf | even |
| 0011 (3) | leaf | odd |
奇数と偶数を区別する理由としては、例えば、path=[1,2,3]とpath=[0,1,2,3]の部分pathを持つleafがあった場合、どちらの部分pathもbyte列で表すと、pathは二ブル(4bit)単位で分割されているので、byte(8bit)データに変換されるときは、奇数の場合は先頭に0が補完され、"0x01, 0x23"となり両方ともが同じ値になってしまいます。
そのため、両者を識別するために、偶数と奇数で識別子がそれぞれ定義されています。
部分pathが奇数の二ブルで構成されている場合は、識別子が先頭に付与されます。部分pathが偶数で定義されている場合は、識別子とパディンとしての0が挿入（つまり1byte分のデータ）されます。具体例を挙げると以下の通りです。
Patricia Merkle Treeの各ノードのハッシュ値の求め方
各ノードのハッシュ値は以下の式で求めることができます。
keccak256(rlp(node raw data))
node raw dataはbranchの場合はArray(17)、leafとextentionの場合は[prefix + path, value]になります。そのため、それぞれのノードでのハッシュ値は以下の式で求まります。
// in the leaf and extension node case const hash = keccak256(rlp([prefix + path, value])) // in the extension node case const hash = keccak256(rlp([[ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]]
extensionノードは実際には各要素に次のノードを指すためのhash値が入ります。また、場合によってはindex 16番目の要素にvalue値が入ります。
具体的な使用例
EthereumではBlock headerに格納される、State root hash、transaction root hash、transaction receipt root hashはこのMerkle Patricia Treeを用いて算出されます。また、Accountデータに格納されるStorage root hashもMerkle Patricia Treeを用いて算出されます。
Storageデータを格納するMerkle Patricia Treeではkeccak256(stroage address)をpathとして用います。つまり、storageの0番目に1024という値を格納した場合は、
const path = 290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563; // keccak256(0x0000000.....000) const value = 0x820400; // (rlp(1024) => rlp(0x04, 0x00) => 0x82, 0x04, 0x00)
というデータをMerkle Patricia Treeに追加します。
また、StateのMerkle Patricia Treeでは、データはpath=keccak256(address), value=rlp([nonce, balance, storage root hash, codeHash])のデータをMerkle Patricia Treeに追加します。
Merkle Patricia Treeの構造の具体例
ここでは、wikiに記載されている、('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')の4つのpathとvalueのペアデータからなるMerkle Patricia Treeの構造を出力例を示します。
なお、ここでは簡略化のために、pathはkeccak256ハッシュ値ではなく、文字列の二ブルをそのまま利用しています。
下記のデータは、左から順に、ノードのハッシュ値、ノード種別、ノードデータの順に表示しています。
[5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84] extention: 16=bd3ee507e6c67cfefca98f84be47c1bbc009315fabc4405db4ba32190374572a [bd3ee507e6c67cfefca98f84be47c1bbc009315fabc4405db4ba32190374572a] branch: <>, <>, <>, <>, <94a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68>, <>, <>, <>, <59ef9c45a1ec7389dcf28e77737ea85920d423b6f7619e0629a56d3f74edcfc6>, <>, <>, <>, <>, <>, <>, <>, <>, [c13f2b5c8322fd221fc6104d344a0f07e7216e42fd15635af617b7a12b2be2ed] leaf: 206f727365=stallion [94a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68] extention: 006f=d43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36 [d43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36] branch: <>, <>, <>, <>, <>, <>, <6781ea95827831ff947dde3774e42ee3b9c214057abacf2c9923b00af442dd3d>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <verb>, [84de34899207d43ee9f036cece1bfbd9245b0a19b28b65a4556c8bce7f8abb49] extention: 17=329dbdce644bc10623dc3116fbd854386efa333b7e51dc9ac086b599d2c8f8c6 [329dbdce644bc10623dc3116fbd854386efa333b7e51dc9ac086b599d2c8f8c6] branch: <>, <>, <>, <>, <>, <>, <8df0ca4566a8e965bb5117f3357c06e301c2439cbfd902dc850290cdc4991ed3>, <>, <>, <>, <>, <>, <>, <>, <>, <>, <puppy>, [8a341bee87338ac4b1932bd668b9d6daae6d6cbd4fe834d33fa39490e5228b34] leaf: 35=coin
上記の例でわかる通り、このMekrle Patricia Treeのroot hashは [5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84] です。
また、上記例は偶数二ブルと奇数二ブルからなる部分pathを持つleafとextensionが両方登場するので、Merkle Patricia Treeの各種ノードと全体構成を把握しやすいと思います。
上記のダンプデータはnpmのmerkle-patricia-treeを用いて出力しています。以下にサンプルコードも示します。
gist.github.com
まとめ
今回はEthereumを支えるデータフォーマットについてまとめてみました。どちらかというと自分の理解のための記事になっています。
RLPとMerkle Patricia Treeについては概要は理解していたのですが、細かい内容までは把握していなかったので非常に勉強になりました。特に、Merkle Patricia Treeはそれを用いてどのようにroot hashを算出するのかを理解していなかったので、今回の記事を執筆するにあたり、その辺りの処理が理解できました。
特に、Merkle Patricia Treeはフラットなkey-valueストアに比べて確かに、検索、挿入、削除が高速に行えることが理解できました。
