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