ブロックチェーンは、各ブロックが鎖（チェーン）のように繋がることでデータを連続的に保管する台帳技術です。さらに各ブロックには、多くのトランザクション（取引）データが格納されています。ブロックチェーンでは、その多くの取引データを「マークルツリー」という技術を利用することでブロックヘッダに要約して書き込んでいます。今回は、マークルツリーについて見ていきましょう。
マークルツリーとは
マークルツリーは、公開鍵暗号の開発者の一人であるラルフ・マークルによって1979年に発明されました。マークルツリーとは、ファイルのような大きなデータを要約した結果を格納するツリー構造の一種です。主に大きなデータの要約と検証を行う際に使用されます。その計算にはハッシュ関数が利用されていることから、ハッシュ木とも呼ばれています。
まず、マークルツリーの基本形は2つのデータを1つにまとめる形になります。例えば、AとBという2つのデータがあるとします。まずは、Aのハッシュ、Bのハッシュをそれぞれ計算します。このAのハッシュ、Bのハッシュそれぞれを足し合わせた値のハッシュをとったものが頂点の値になります。
マークルツリーが実際に使われる場合は、たいてい複数段のツリー構造で構成されており、2段、3段と2個づつハッシュをまとめていきます。そして、最終的に得られた頂点のハッシュ値はマークルルート（あるいはトップハッシュ、マスターハッシュ）と呼ばれています。
マークルツリーには、どんなデータを入力しても一定の長さの値を返すハッシュ関数を使用していることから、どんなに大きなデータ、どんなに多くのデータを入力しても最終的に得られる値は一定のデータ長になりという特徴があります。言い換えると、2個のデータを要約しても、65536個のデータを要約しても、最終的には同じデータ長にまとめることができます。また、計算方式が単純であるため、比較的簡単にマークルルートの値を得ることができます。この特性を使い、予め保存されたマークルルートの値と要約元のデータがあれば、新たに要約元のデータから算出したマークルルートの値と、予め保存されたマークルルートの値することで、要約元のデータの検証にも使うことができます。この仕組は改ざん検知とても協力な力を発揮します。
ビットコインへの応用
このマークルツリーの技術は、ビットコインのブロックチェーンにおいて重要な役割を果たしています。ブロックチェーンにはブロックヘッダーと呼ばれるブロックの情報が書かれている部分があります。ブロックヘッダーには、そのブロックの情報として、以下のものが格納されています。
- 1つ前のブロックのハッシュ
- （Proof of Workを証明する）ナンス
- （今のブロックにおける取引記録全体を表す）マークルルート
Proof of Workやナンスに関する詳細な情報は以下の記事をご覧下さい。
分散ネットワークでの合意を可能にしたコンセンサスアルゴリズム「プルーフ・オブ・ワーク」
現在のブロックに入れる取引データは、各取引のハッシュ値を、マークルツリーを利用することで1つのハッシュ値にまとめあげます。2つの取引データのハッシュ値のペアを足してハッシュ化し、これを繰り返していくことで、最終的に1つのハッシュ値（マークルルート）を得ることができます。
このマークルルートをブロックヘッダに格納することで、ブロックに入れ込まれている全トランザクションの値が書き換えられていないかを確認することができます。1つでもトランザクションデータが書き換えられてしまえば、ドミノ状にマークルルートも書き換わってしまうためです。
画像：Bitcoin論文
SPVとマークルツリー
ビットコインのブロックチェーンの上で取引データを1つにまとめあげたマークルルートを活用しているのがSPVと呼ばれる方式です。SPVはSimplified Payment Verificationの略称で、ブロックチェーンに保存されている全取引データをダウンロードすることなく、取引の検証を行う方式を指します。ウォレットのような軽量型クライアントは、SPVクライアントを使用しているものが多いです。
反対に全てのトランザクションデータを保持しているものをフルノードと呼びます。フルノードは、起動するためには一番最初のブロックから現在のブロックまですべてのデータを取得しなくてはいけないのに対し、比較してSPVは全ての取引データをダウンロードする必要がないので、起動後すぐに使用することができることが大きな利点です。
SPVクライアントでは、全ての取引データは取得ぜず、検証したいブロックの取引データだけを取得し、マークルルートと比較することで取引データの検証をすることが可能となります。前述したように、マークルルートは対象となる全てのトランザクションデータをまとめ上げたハッシュ値です。さらにどれほどの量のトランザクションデータ量であるとしても、ハッシュ値としてのデータ長は変わらないので、一つの取引と同量で全てのトランザクションデータを要約してくれます。フルノードがすべての取引の不正確認を行っているという信頼を元に、SPVはこのマークルルートの部分だけの検証を行うことで、取引の確認が行えています。
全てのブロックチェーンを保存しているフルノードに比べて、SPVなどの軽量クライアントが必要とするデータは約1000分の1ほどで済むと言われており、マークルツリーの利点をうまく活かして軽量化に成功しています。
大きなデータをブロックチェーンに書き込む
ブロックチェーンはブロックサイズに限りが有ることから大きなデータを書き込むことを苦手としています。これをマークルツリーを使って克服しています。一般的に大きなデータはブロックチェーンの外のサーバーにデータを置きます。そのデータをハッシュ化しそたものをブロックチェーンに書き込みます。こうすることで、ブロックチェーンに書き込まれたデータは、消すことができなくなり、記録として残り続けます。そして元データをハッシュ化したものと、ブロックチェーンに記録されたハッシュを比較することで、データの証明を行うことができます。
この場合、1データしかブロックチェーンに保存することができません。複数のデータを保存するときにマークルツリーが活躍します。複数のデータをマークルツリーを使うことで短いハッシュにまとめることができます。こうすることで、1つの取引で多くのデータの記録を残すことができます。1つの取引にまとめられるメリットとして、書き込む際の取引手数料を抑えることができる、1回の取引回数ですむため、取引の承認待ちも、その1取引分だけ待てば良いといことで、承認までの時間短縮にもつながります。
この方法を活用しているものはたくさんありますが、有名なところだとドキュメントなどの存在証明を行うサービスであるFactomがこの方式を使っています。
普段私達が何気なく使用しているビットコインウォレットなどがストレスなく利用できているのは、マークルツリーのおかげだということが分かります。ブロックチェーンでは至る所で様々な技術を活用しているという点で、非常に興味深いものであると感じることができるのではないでしょうか。
