マークル木（マークルツリー）とは？ブロックチェーンの要素技術の一つを徹底解説！

「マークル木が分からない・・・。」

ブロックチェーンを勉強し始めた方にとって、マークル木はつまづきポイントの一つだと思います。その原因は、おそらくその抽象性にあるでしょう。

そこで今回は例えを用いてマークル木を理解しましょう。マークル木は何なのか、何ができるのか、どう良いのか具体的に示し、実際にブロックチェーン、ビットコインにどのように応用されているのかも解説します！

この記事を読んで、ブロックチェーンに対する理解をもう一段階深いものにしましょう！

マークル木(マークルツリー)とは？​

​例えと概観

​マークル木は、端的に言うとデータを要約・検証するための技術です。

と言っても、曖昧でよく分からないと思います。そこで、データをカラーボールに例えて説明しましょう。

今、皆さんの目の前にたくさんのカラーボールが転がっています。その色は赤や青、緑、黄色と色々あり、一つ一つに①、②、③・・・と番号が割り振られています。さて、ここで一つ質問です。皆さんが、全てのカラーボールが元の状態のまま保全されていること、つまり壊れているところもなく色もそのままであることを確認しなければならないとしましょう。さてどのように確認するでしょうか？

答えは単純です。もともと①のボールは何色でどのくらいの大きさなのかを写真に撮って保存しておきます。すべてのボールの写真を撮り、その写真と実際のボールを比較します。すべてが一致していることを確認すれば万事解決です。

しかし、この方法には一つ問題があります。ボールの数が多くなった時に非常に手間がかかるというものです。10個くらいなら全然問題なくできます。100個でも根性で何とかなるでしょう。しかし、カラーボールが1億個あったとしたら、確認の作業だけで一生が終わってしまいます。

そこで、ある賢い人が一つの機械を発明しました。その機械の名前は機械X。その機械の中に何個でもいいのでカラーボールを入れると一つのカラーボールが出てきます。カラーボールはランダムに出てくるわけではなく、ある法則を満たします。

1. ​同じカラーボールを入れれば、常に同じカラーボールが出てくる。
2. 出てきたカラーボールから、最初に入れたカラーボールを推測することはできない。
3. 入れたカラーボールのうち一つでも欠損があったり、色が違ったりすると、全く異なるカラーボールが出てくる。

その機械に赤と青と緑の3つのカラーボールを入れて、結果黒のカラーボールが出てきたとしましょう。法則1で言っていることは何時どんな状況でも、赤と青と緑のカラーボールを入れると絶対黒のカラーボールが出てくるということです。

｛赤、青、緑｝→｛黒｝となることを知っているのはあなた一人だけです。その他の人は、黒のボールが出てきたからといって最初に何色のボールを何個入れたのかということを推測できません。これが法則2で言っていることです。

緑のボールを白のボールに変えたとしましょう。すると出てくるボールの色は藍色かもしれませんし、ネズミ色かもしれません。法則3で言っているのは、少なくともその色が黒となることは決してないということです。

一億個のカラーボールが目の前にあったとして、機械Xを用いた解決策を考えます。

まず2つ一組のペアを5000万ペア作ります。そしてペアを機械Xの中に入れ5000万個の新たなカラーボールを生成します。次には、2500万ペアを作り、機械Xを用いて2500万個の新たなボールを生成します。この操作をカラーボールの数が最後の1個になるまで続けます(総数が奇数だった場合、余ったボールの相方は自信のコピー、レプリカとします)。

最後のカラーボールをRと呼びましょう。このRを写真に収めておきます。そして検証するときには1億個のボールに対して同じ操作(ペアを作り、機械Xに入れる)を行い、最後に出てきたボールとこの写真を見比べます。

この方法は最初に挙げた原始的な方法よりも圧倒的に手間が少なくすみます。最後に確認するボールは一つだけでいいのですから。

​なぜ、最後のボールだけを確認すればいいのでしょうか？機械Xの性質3より、一億個のボールのうち一つでも色が違っていたり欠けていたりすると最後に出てくるボールはRと異なります。​よって、最後のボールが写真と一致していれば、全部のボールが元の状態のままであると言えます。

最後にこの操作を図にしてまとめると木のような構造をしていることが分かります。それゆえ、このような方法を用いてできた構造をマークル木(マークルツリー)といいます(マークルはこの手法の発明者ラルフ・マークルに由来します)。

以上、マークル木を例えを用いて説明しました。カラーボールをデータに戻して考えます。

マークル木を用いることによって複数のデータを一つのデータにまとめることができます。その最終的なデータの完備性を確かめれば、そのマークル木を構成するすべてのデータの完備性を確かめることができるのです。

重要なのは、データを要約する過程であり、マークル木では以下の操作が行われます。

1. ​データの断片を2つ1組にする(断片の総数が奇数だった場合、最後の断片の相方は自分自身のコピー)。​
2. そのペアを組み合わせハッシュ関数という関数に通し、一つの値を出力する。
3. 出力された値でまたペアを作り同じ操作を繰り返す。

この操作をデータの総数が一つになるまで続けます。最終的に残ったデータのことをはマークルルート(マークル木の根っこ)と呼びます。このマークルルートにデータの断片全ての情報が集約されており、マークルルートを確認することでそのマークルルートを構成するデータの完備性を確認することができます。

ハッシュ関数

​機械Xは現実の何に対応しているのかここで確認しておきます。操作2のところで、ハッシュ関数という耳慣れない単語がでてきました。このハッシュ関数なるものが機械Xに当たります。ハッシュ関数の説明をしましょう。

ハッシュ関数とはあるデータが与えられたときにそのデータを代表するような値を返す関数のことで、要約関数とも呼ばれます。また、ハッシュ関数を通して得られた値のことをハッシュ値といいます。得られたハッシュ値でペアを作り、再びハッシュ関数を通すことによって最終的にマークルルートを得ます(難しく言うと再帰的にハッシュ関数を適応するということです)。

マークルツリーで用いられているハッシュ関数は特に暗号学的ハッシュ関数と呼ばれ、通常のハッシュ関数に暗号学的な性質を加えたものです。その暗号数理的性質は以下の通りです。

1. 同じハッシュ​値を持つようなデータを作成することはできない。
2. ハッシュ値から元のデータを推測することはできない。
3. 同じハッシュ値を持つようなデータのペアを作ることはできない。

上記の性質は以下の行為を不可能にしています。

例えば、Hさんがデータを改ざんしようとしたとしましょう。Hさんは周りの人達にバレないように改ざんしなければなりません。つまり、ハッシュ値を変えないようにデータを変えようとするということです。しかし、性質1によりこの行為は不可能です。

次にHさんが元のデータの中身を見るために、マークルルートから本来のデータを復元しようとしたとしましょう。しかし、性質2によりこの行為は不可能です。ハッシュ値から元のデータを推測することは実質不可能だからです。

前述したように、マークルルートを検証することによってデータの完備性を検証することができます。これはハッシュ関数が上記のような性質を持っているからです。

以上がハッシュ関数の簡単な説明です。以下ハッシュ関数の具体例です。

SHA(Secure Hash Algorithm)

​最もメジャーなハッシュ関数の一つです。SHAの中にも種類があり、SHA1やSHA2などがあります。SHA1はセキュリティの面で問題があり現在は使われていません。セキュリティ面での問題とは、一定以上の計算能力を費やすと前述の暗号数理的性質を満たさなくなるということです。例えば、異なるデータから同じハッシュ値が得られてしまったり、ハッシュ値から元のデータを類推することができてしまったりということです。

現在主に使われている関数はSHA2というハッシュ関数です。ビットコインのアドレス発行の際に使われているハッシュ関数はSHA256です。

マークルルート

​マークルルートは、再帰的にハッシュ関数を適応することにより得られるただ一つのハッシュ値です。この値を検証することによって、データの完備性を確認することができます。例えの中で、最後に出てきたボールRがこれに該当します。

ビットコインでは、元となるデータはトランザクションです。AからBに1BTC送るというトランザクションのBをCに変えた場合、それによってマークルルートが変わり、データに何かしらの変化が加えられたことが即座に分かります。

ところで、マークルルートは一体どこに保存されるのでしょうか？答えは、ブロックヘッダーという場所に保存されています。具体的なことは、「マークル木とブロックチェーン」「マークル木とビットコイン」で説明しますが、このブロックヘッダーのハッシュ値が次のブロックにパラメータとして入ることが、ブロックチェーンの非改竄性の観点から非常に重要です。

マークル木の用途​

​マークル木の用途には大きく以下の二つがあります。データの要約と検証です。

データの要約

​マークル木を使うことによって、多くのデータを一つのハッシュ値に要約することができます。要約する、つまりマークルルートを求めることでデータ全てを扱う必要がなくなります。

ハッシュ関数には、「どんなに大きなデータを関数に通しても、出てくるデータは常に一定の大きさである」という重要な特徴があります。この特徴を利用することで、膨大なデータを1つのデータにまとめることができます。

データの検証

​これがマークル木の最も大きな役割です。データが欠損していたり、データが改ざんされていることをハッシュ値を見ることで一瞬で検知できるのです。全データが元のままであることを知るためには、最後のハッシュ値だけを見ればいいということです。

例えの中で、勘のいい方は気づかれたかもしれません。もしカラーボールが元のままであることだけを確認したいのであれば、一番初めに1億個すべてを機械Xの中に入れてしまうのが一番いいのではないかと。

確かにその通りです。そのほうが圧倒的に処理は少なくて済みます。しかしながら、問題点は最後に得られたボールがRと異なる場合、どのボールに問題があるのかが分からないという点です。これを解決するためにペアを作っているのです。

​さて、実際にデータに破損があった時どのデータに問題があるのかどう調べればよいでしょうか？

カラーボールの例えを用いて説明しましょう。1番の番号が割り振られたボール(以降①と呼びます)の色が変えられたとしましょう。1億個のボールの中から①だけに問題があることを検出します。

まず初めに、マークルルートを確認します。①が変わっているので、マークルルートも当然変わっています。

次にその直前の枝(マークルルートを構成する2つのカラーボール)を確認します。①だけに変化が加えられているのであれば、①が含まれている枝の方のボールは変化しており、一方のボールは変化していないはずです。この操作で変化が加えられたボールを含む枝を判別することができました。

この操作を①のボールにたどり着くまで続けます。これがマークル木を用いた、破損ボール検出の方法です。

さて、この方法を用いると一体どれくらい操作が少なくて済むのでしょうか？

マークル木を用いない場合、当然一つ一つボールを確認していくしか方法はありません。1億個のボールの中から①のボールを見つけ出すために何回試行が必要かを計算します。1回の試行で1個のボールを確認できるとします。

計算すると、期待値(①のボールを引くまでの試行回数の期待値)は約5千万回です。平均して5千万回ボールを引けば①のボールを引き当てられます。

マークル木を用いた場合はどうでしょうか。答えだけ先に示します。​log2(100000000)+1です。約27～28回です。

この違いは一目瞭然でしょう。マークル木はそれほど強力な手法なのです。

​マークル木の発明​

​マークル木は、1979年ラルフ・マークルによって発明されました。彼は公開鍵暗号の発明にも大きな影響を与えています。彼がマークル木を発明したのは、大量のランポート署名を効率よく処理するためでした。マークル木が発明される以前、ランポート署名において一つの鍵は一つのメッセージに対してのみ署名することができました。

しかし、マークル木を導入することで、1つの鍵で複数のメッセージに対して署名ができるようになったのです。

マークル木とブロックチェーン​

​マークル木自体がどんな仕組みなのか理解できたでしょう。ここからは、ブロックチェーンの中でどのようにブロックチェーンが使われているのか見ていきます。

ハッシュチェーン

​いかなる取引においても取引の時間的な前後関係は非常に重要です。どの取引が先に行われたのかによって、その取引が有効となったり、無効となったりします。インターネット上でどのように時間を参照するのでしょうか？

中央集権的な構造の場合、時間はサーバーから受信します。UNIX標準時刻とも言われ、この時間を参照して取引の前後関係を定義します。

一方で、分散的な構造の場合、各々が好きなところから時間を参照します。日本にいる人が日本サーバーで見て12時だとしても、イギリスにいる人はイギリスサーバーで見ると3時と言うことになります。つまり、絶対的な時間を定義することができないのです。

そうなると、相対的に定義するしかありません。時間は一切関係なく、ただどの取引がどの取引よりも先に存在するのかを定義するのです。

​ここでハッシュ関数を使います。「ハッシュ関数」のところで説明したように、ハッシュ関数では出力値から入力値を類推することはできません。つまり、入力値は出力値以前に存在しているということになります。

 

​上図を見るとわかるように、データ0はデータ1よりも以前に存在し、データ1はデータ2よりも以前に存在します。これで取引の前後関係を定義することができました。

ハッシュ関数を用いてできる上図の構造は一般的にハッシュチェーンと呼ばれます。

ハッシュチェーンからブロックチェーンへ

​相対的な時間を定義することができました。しかしまだ問題があります。このネットワークに参加するすべての人間が最新のデータを見れるのかという問題です。

ハッシュチェーンの状態だと、コンピュータの処理能力によってある人は最新のデータを参照できるのですが、ある人はそこに追いつくことができません。

これを解決するものがマークル木です。マークル木によってデータは要約され、各人が参照するデータの量は圧倒的に減ります。​一つのマークル木に含まれるデータはすべて同時刻のモノとして扱われます。またマークル木を使うことで破損データの検出をすることもできます。

このようなハッシュチェーンにマークル木が加わった構造がブロックチェーンの原型と言うことができるでしょう。​

マークル木とビットコイン​

​今度はビットコインを見ていきます。ビットコインの中で、マークル木はどのように利用されているのでしょうか。

マークル木とSPV

​ネットワークを構成する要素のことをノードと言います。ノードの中でもいくつか種類があります。分け方によって変わるのですが、今回は参照できるデータの量によって分類します。

1つ目はフルノードです。フルノードは今までのすべての取引情報を保持しており検証することができます。フルノードになるためにはそれだけ多くのデータ容量が必要となるので、簡単にフルノードになることはできません。

それでは、取引の検証をするノードが少なくなってしまいます。そこで出てくるのが軽量(SPV)ノードというノードです。軽量ノードはブロックヘッダの情報だけを参照できます。「マークルルート」のところで説明したように、ブロックヘッダに中にはマークルルートが含まれています。

SPVノードはマークルルートだけを参照してデータの検証を行います。しかし、どのデータに問題があるのかまでは特定することができません。

その部分の情報はフルノードに要求します。つまり、SPVノードの検証はフルノードの検証に依存しているのです。

しかし、SPVノードには簡単になることができるので検証するノードがそれだけ増えます。するとネットワークの信頼性がそれだけ増すことと同義です。すべてはマークル木という要約技術があるおかげです。

マークルツリー(マークル木)まとめ

​以上、マークル木の説明でした。データの要約・検証に役立つ非常に興味深い技術だったと思います。

「ブロックチェーンはすごい！」と巷でよく言われていますが、ブロックチェーンはそれ単独で生まれ来たわけではありません。インターネット技術、自律分散システム、暗号技術などそれらがすべて組み合わさってできた技術の総体です。マークル木はあくまでそのうちの一つの要素技術であり、ブロックチェーンを本気で学ぼうとしたら他にも学ぶことが多々あると思います。

以下、大事な点をまとめました。このような長い記事を読んでいただきありがとうございました。