ブロックチェーン技術ブログ

ブロックチェーンと英語、数学に関するブログ

ブロックチェーンのデータ構造 < マークルツリーとマークルパトリシアツリー >

ブロックチェーン データ構造

BitcoinやEthereumといった仮想通貨では、ブロックチェーンのデータを複数のノードで分散管理をしています.
その際に、ブロックチェーンの改ざんを検知できるように、データを保持する必要があります.

Bitcoin、Ethereumではそれぞれマークルツリー、マークルパトリシアツリーを利用してデータを管理しています.

マークルツリー、マークルパトリシアツリーを順番にみていきましょう.

マークルツリー

マークルツリーでは、まず各リーフノードのハッシュを取得します.
2組のハッシュ値を結合したものを次のハッシュの入力値とする操作を繰り返して、最終的に1つのルートハッシュを出力します.

マークルツリーは、データが正しさ(改ざんされていないこと)を検証する用途で利用されます.
もし、データの一部が改ざんされていた場合、ルートハッシュが異なる値となります.

https://upload.wikimedia.org/wikipedia/commons/9/95/Hash_Tree.svg Merkle tree - Wikipedia から引用

上の図で、L1のデータがマークルツリーに含まれることを検証してみましょう。
まず L1 のハッシュを Hash 0-0 と比較します.
次に Hash 0-0 と Hash 0-1 を結合した文字列のハッシュ を Hash 0 と比較して検証します.
最後に、 Hash 0 と Hash 1 を結合した値のハッシュ を ルートハッシュ(Top Hash) と比較して検証します. 全てのノードのハッシュを再計算することなく、効率的にデータの検証がおこなえます.

マークルパトリシアツリーの前に、トライ木とパトリシア木をみてみましょう.

トライ

複数の文字列を保持するツリー構造です.
文字列がルートノードからのパスになっています.

https://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg

Trie - Wikipedia から引用

上の図で、文字列 "to" を検索してみましょう.
ルートノードから "t" のパスを辿って、t のノードに到達する.
t のノードから "o" のパスを辿って、to のノードに到達する.

トライはシンプルなデータ構造です.
ただし、文字列の長さだけノードが必要になるという欠点があります.
そのため、文字列の検索、追加、更新のパフォーマンスが良くありません.

より効率的にキーを保持できるようにしたのが、次に紹介するパトリシアツリーです.

パトリシアツリー

パトリシアツリーでは、複数の文字列で共通するパスの部分を1つのノードで保持するようにしました.
また、リーフノードで、パスを複数文字保持できます.

例) "leaf" と "leave" を保持する
トライの場合、root, l, e, a, f, v, e のノード必要になります.
パトリシアツリーの場合、共通文字列 "lea" と 残りの文字列 "f", "ve" の3つのノードだけで済みます.

root
|
lea
/ \
f ve

https://upload.wikimedia.org/wikipedia/commons/a/ae/Patricia_trie.svg

Radix tree - Wikipedia から引用

Ethereum は、複数のトランザクションからブロックを作成した後に、順にトランザクションを実行して状態を更新していきます.
そのため、マークルツリーのデータの改ざんを検知するのに加えて、データの更新に適したデータ構造が必要です.

マークルパトリシアツリー

マークルパトリシアツリーは、マークルツリーのデータの改ざんを検知する機能とパトリシアツリーのデータを効率よく検索、追加、更新する機能を持ったデータ構造です.

各ノードがそれぞれハッシュ値を持ち、ルートノードのハッシュが一意に定まります.

マークルパトリシアツリーは、以下のノードからなります.

ノードの種類 説明
NULL 空文字を表す
ブランチ [1 2 3 ... e f バリュー] の形式で、1~fの数字とバリューの計17種類の要素からなる
1 ~ f には参照先のノードのハッシュが入る
リーフ [パス バリュー] の形式
エクステンション [パス 参照先のノードのハッシュ] の形式
パスの共通部分を集約する

※ 今回はわかりやすさを優先して、キーのハッシュ処理やバリューのエンコード処理、パスの先頭にフラグをつける処理等を省略しました.

以下のキー・バリューのペアを順番に追加する例をみてみましょう.

キー バリュー
1020 One
820 Two
10251 Three
102 Four

まず、[1020, One] を追加します.

ルートノードの直下に、Hash1のノードが追加されました.
下の表で、左の列がハッシュ値で、右の列がハッシュの入力値となります.
Hash1 は、[1020, One] を入力値としたハッシュです.
Root は、Hash1 を入力値としたハッシュです.

Root Hash1
Hash1 [1020, One]

次に、[820, Two] を追加します.

ルートノードからの分岐が2パターン(1と8)あるので、ブランチノードを追加します.
Hash1 だったノードは、Hash4 が親になり、パスが 020 となります.
Root は、ハッシュの入力値が Hash4 に更新されました.
このように、ノードの追加によって、ルートハッシュが更新されていきます.

Root Hash4
Hash4 [N, Hash2, N, N, N, N, N, N, Hash3, N, N, N, N, N, N, N, N]
Hash3 [20, Two]
Hash2 [020, One]

続いて、(10251, Three) を追加します.

ここで、キー 10251 を検索してみましょう.
まずは、Root から Hash9 へ移動します.
キーの先頭文字は 1 なので、Hash8 に移動します.
Hash8 はブランチノードなので分岐することなく、Hash7に移動します.
ここまで、102 のパスを辿ってきたので、残りパスの 51 です.
5 のパスから Hash6 に移動します.
末尾の文字の 1 をパスに持ち、リーフノードである Hash6 に到達することができました.

Root Hash9
Hash9 [N, Hash8, N, N, N, N, N, N, Hash3, N, N, N, N, N, N, N, N]
Hash8 [02, Hash7]
Hash7 [Hash5, N, N, N, N, Hash6, N, N,N, N, N, N, N, N, N, N, N]
Hash6 [1, Three]
Hash5 [, One]
Hash3 [20, Two]

最後に、(102, Four) を追加します.

直前に Hash7 であったのノードの V のところに Four が追加されました.
それにより、Root のハッシュが更新されました.
また、Hash3, Hash5, Hash6 はそのままです.
マークルパトリシアツリーでは、ノードのデータによってルートハッシュを一意に出力すると同時に、効率的なノードの検索、追加、更新を可能にします.

Root Hash12
Hash12 [N, Hash11, N, N, N, N, N, N, Hash3, N, N, N, N, N, N, N, N]
Hash11 [02, Hash10]
Hash10 [Hash5, N, N, N, N, Hash6, N, N,N, N, N, N, N, N, N, N, Four]
Hash6 [1, Three]
Hash5 [, One]
Hash3 [20, Two]

以下のリンクから、Ethereumでの厳密なマークルパトシアツリーを確認できます.

ethereum.org