こんにちは！CryptoGamesというブロックチェーンゲーム企業でエンジニアをしているかるでねです！
スマートコントラクトを書いたり、フロントエンド・バックエンド・インフラと幅広く触れています。
このブログ以外でも情報発信しているので、よければ他の記事も見ていってください。
https://mirror.xyz/0xcE77b9fCd390847627c84359fC1Bc02fC78f0e58
今回は「マークルツリー」について解説していきます！
「マークルツリー」はブロックチェーンや仮想通貨にも関係してくるものです。
図解たっぷりで解説していくのでこの記事を読み終わる頃にはしっかり理解できます！
「ブロックチェーンや仮想通貨に興味がある」
「マークルツリーって何？」
「アルゴリズムに興味がある」
こんな人の役に立てば幸いです。
前置きは早々に早速みていきましょう！
マークルツリーとは？
まずは「マークルツリー」がどんなものなのかや関連用語について解説していきます。
概要
データが正しいか効率的に検証するデータ構造。
「マークルツリー」を一言でいえばこのようになります。
複数のデータがあるとして、その全てのデータが正しいものかを検証するにはどのような方法があるでしょうか？
１つ１つ検証していけば良いのですが、それでは時間がかかりすぎてしまいます。
その際に用いられるのがこの「マークルツリー」です。
名前の通り下記のような二分木の「ツリー」構造になっています。
この図を基準として、「マークルツリー」に近づけていきましょう。
「マークルツリー」はデータの検証を行う役割を持つため、どちらかというと上記のように矢印が上から下にいくよりも、下から上にいくほうが正しいです。
このようにボトムアップで要素を足し合わせていき、最終的に１つの値になります。
この「ツリー」のAの部分を検証用の値として用いるのが「マークルツリー」です。
しかし、この図ではまだイメージが湧きづらいと思うので、さらに変更を加えます。
これでイメージしやすくなったはずです！
各要素をどんどん足し合わせていって、最終的にABCDEFGHという値になっています。
これが「マークルツリー」というものです。
ちなみにこの値は本来全て「ハッシュ化」して「ハッシュ値」となります。
「ハッシュ化」についてわからない方は以下を参考にしてください。
説明のためにわかりやすいものにしています。
そのため実際はこんな感じになります。
「２つのハッシュ値を足し合わせたものをハッシュ化する」ということを繰り返して、最終的に１つの値となります。
ちなみにハッシュ値は、どんな長さのデータを入力しても同じ長さの値を返します。
上の図でも全て同じサイズの「ハッシュ値」になっているのが確認できますね。
そのため、どんな大きなどんな大きなデータやどんなに多くのデータを入力しても、最終的に得られる値は決まった長さになります。
ここでもしかしたら以下のような疑問を持つ人がいるかもしれません。
データが奇数個の場合はどうするの？
図を見てもらえればわかると思いますが、データが偶数個でないとツリー構造は作れません。
ではどうするかというと、末尾のデータを複製させます。
このように末尾であるGを複製して足し合わせていきます。
最終的に出力される値はあくまで検証のための「ハッシュ値」なので、このように複製しても問題がないのです。
データの取得
１つの値が「マークルツリー」に含まれているか検証するにはどうしたら良いでしょうか？
もちろん１から検証していけばわかりますが、だいぶ手間がかかってしまいます。
ただし「マークルツリー」ではその手間が必要ありません。
上の図のようにCの値がトップに含まれているかを検証するためには、「マークルツリー」の一部のデータのみを使うだけですみます。
同じ階層に値を足し合わせた「ハッシュ値」を親の値と比較するのを一番上の値まで行えば検証ができてしまいます。
データを変えてみる
データが正しいかどうかを検証するということで、どこかのデータを変えてみましょう。
先ほどFだった部分がZとなっています。
そうするとFが含まれている部分が全てZとなってしまっています。
正しい値はABCDEFGHとわかっている状態で、このような値が出力された場合何かしらの改ざんが行われたということが一目でわかります。
では次は途中を変えてみましょう。
先ほどCDだった部分をCZに変更しました。
こちらも同じように変更された部分より上の値が変わってしまっています。
どこで異常が起きているかも上から辿っていけばすぐにわかります。
「ABDZの部分もおかしい、CZの部分もおかしい、しかしその下のCとDは正しい値になっているから、CZの部分が異常が起きている部分だ！」
このように下から辿るとデータの検証ができ、上から辿ると異常部分がわかるというなかなかの優れものです。
用語
ではこの章の最後に「マークルツリー」に関する用語について確認していきましょう。
マークルルート
マークルツリーの頂点の値。
「ルート」と入っているので道のことだと思うかもしれないですが、rootなので「根っこ」という意味です。
最終的に出力される「ハッシュ値」のことですね。
今までの図でいえばABCDEFGHがこの「マークルツリー」に該当します。
マークルパス
特定の値を検証するために必要な値の組み合わせ。
「特定の値」というのは「マークルツリー」の各要素のことを指します。
例えばこの図のBという値を検証するためには、AとCDとEFGHの２つの値が必要です。
この３つの値の組み合わせが「マークルパス」です。
わざわざ１つ１つに要素を分解する必要はないのがポイントですね。
葉（リーフ）
「マークルツリー」の１要素のことです。
上の図でいえばAやDやEF、ABCDのことを指します。
耐改ざん性
改ざんに対しての耐性がある。
「マークルツリー」のどの部分を改ざんしたとしても、その改ざんされた部分から「マークルルート」までの値が全て書き変わります。
そのため、改ざんした部分から「マークルルート」までの値を全て書き換える必要がありますが、それは相当困難です。
また、順序を変えても最終的に出力される値（「マークルルート」）が変わってしまうため、並べ替え対しても耐性があります。
使用例
この章では「マークルツリー」がどのような場面で使われているのかをみていきましょう。
ビットコイン
ビットコインなどの仮想通貨で使われています。
ブロックチェーンにはブロックヘッダーと呼ばれるブロックの細かい情報が書かれている部分があります。
１つのブロックには複数の取引を記録できます。
その際に「マークルツリー」を用いることで、複数の取引を１つの「ハッシュ値」にすることができます。
また、この値が変わっていないかを検証することで、ブロックに含まれている全取引が書き換えられていないかを確認できます。
もし１つでも書き換えられていた場合は、前述したように全体のデータも書き変わってしまうからです。
大きなデータ
大きなデータをブロックチェーンに書き込むには、ブロックサイズなどの関係から難しいです。
そこで行われているのが大きなデータを外部のサーバーに置くという手法です。
そしてそのデータを「ハッシュ化」した値をブロックチェーンに書き込みます。
しかし、この状態では１つのデータしかブロックチェーンに書き込むことができません。
そこで登場するのが「マークルツリー」です。
「マークルツリー」を使うことで、複数のデータを１つの値にまとめることができます。
このように複数のデータを１つにまとめることで、取引手数料を抑えることができ、取引も1回で済むため承認待ちなどに時間を取られなくてすみます。
以上のことから、「マークルツリー」では、葉（リーフ）１つをトランザクションとするか、複数のトランザクションの塊にするか選ぶことができます。
参考
ポイント
最後に
今回は「マークルツリー」についてわかりやすく解説してきました。
いかがだったでしょうか？
「マークルツリー」について理解できたのではないでしょうか？
普段はPythonやブロックチェーンメインに情報発信をしています。
Twiiterでは図解でわかりやすく解説する投稿をしているのでぜひフォローしてくれると嬉しいです！
Tweets by cardene777