はじめに
今回は「マークルツリー」について解説していきます！
「マークルツリー」はブロックチェーンや仮想通貨にも関係してくるものです。
図解たっぷりで解説していくのでこの記事を読み終わる頃にはしっかり理解できます！
「ブロックチェーンや仮想通貨に興味がある」
「マークルツリーって何？」
「アルゴリズムに興味がある」
こんな人の役に立てば幸いです。
前置きは早々に早速みていきましょう！
マークルツリーとは？
まずは「マークルツリー」がどんなものなのかや関連用語について解説していきます。
概要
データが正しいか効率的に検証するデータ構造。
「マークルツリー」を一言でいえばこのようになります。
複数のデータがあるとして、その全てのデータが正しいものかを検証するにはどのような方法があるでしょうか？
１つ１つ検証していけば良いのですが、それでは時間がかかりすぎてしまいます。
その際に用いられるのがこの「マークルツリー」です。
名前の通り下記のような二分木の「ツリー」構造になっています。
この図を基準として、「マークルツリー」に近づけていきましょう。
「マークルツリー」はデータの検証を行う役割を持つため、どちらかというと上記のように矢印が上から下にいくよりも、下から上にいくほうが正しいです。
このようにボトムアップで要素を足し合わせていき、最終的に１つの値になります。
この「ツリー」のAの部分を検証用の値として用いるのが「マークルツリー」です。
しかし、この図ではまだイメージが湧きづらいと思うので、さらに変更を加えます。
これでイメージしやすくなったはずです！
各要素をどんどん足し合わせていって、最終的にABCDEFGHという値になっています。
これが「マークルツリー」というものです。
ちなみにこの値は本来全て「ハッシュ化」して「ハッシュ値」となります。
「ハッシュ化」についてわからない方は以下を参考にしてください。
説明のためにわかりやすいものにしています。
そのため実際はこんな感じになります。
「２つのハッシュ値を足し合わせたものをハッシュ化する」ということを繰り返して、最終的に１つの値となります。
ちなみにハッシュ値は、どんな長さのデータを入力しても同じ長さの値を返します。
上の図でも全て同じサイズの「ハッシュ値」になっているのが確認できますね。
そのため、どんな大きなどんな大きなデータやどんなに多くのデータを入力しても、最終的に得られる値は決まった長さになります。
ここでもしかしたら以下のような疑問を持つ人がいるかもしれません。
データが奇数個の場合はどうするの？
図を見てもらえればわかると思いますが、データが偶数個でないとツリー構造は作れません。
ではどうするかというと、末尾のデータを複製させます。
このように末尾であるGを複製して足し合わせていきます。
最終的に出力される値はあくまで検証のための「ハッシュ値」なので、このように複製しても問題がないのです。
続き
これより先は以下の記事にまとめています。
より詳しくマークルツリーについて学ぶことができるので、興味がある方はぜひ！
（もちろん無料です！）