マークル木 とは、ファイルのような大きなデータを要約した結果を格納するツリー構造の一種です。
主に入出金記録などの大きなデータの要約と検証を行う際に使用されます。
データ要約および検証時の計算にハッシュ関数を用いているので、ハッシュ木とも呼ばれます。
マークル木は、公開鍵暗号方式の開発者ラルフ・マークルが1979年に発明しています。
原著論文はこちら
マークル木 の構造
マークル木では、2つのデータを1つにまとめて1単位のデータとして取り扱います。
上の図では、トランザクション0（Tx0）のハッシュ、トランザクション1（Tx1）のハッシュをそれぞれ計算しています。
このAのハッシュ、Bのハッシュそれぞれを合わせた値のハッシュが頂点のハッシュ値となります。
データが蓄積されるにつれ、複数段のツリー構造が構成されてゆき、2段、3段と2個ずつハッシュ値がまとめられてゆきます。
最終的に得られた頂点のハッシュ値はマークルルート（トップハッシュやマスターハッシュとも）と呼ばれています。
マークル木には、どんなデータを入力しても一定長の値を返すハッシュ関数が使用されています。
そのため、どんなに多くの大きなデータを入力しても最終的に得られる値は一定のデータ長になります。
つまり、2個のデータを要約しても、175386個のデータを要約しても、最終的には同じデータ長にまとめることができるのです。
また、計算が単純なため、マークルルートの値を得るのに負荷が少なくて済みます。
ビットコインなどの仮想通貨では、この特性を応用することで要約元のデータの検証に用いています。
すなわち、予め保存しておいたマークルルート値とブロックのデータがあれば、
新たなブロックのデータから算出したマークルルートの値と、予め保存されたマークルルートの値を比較検証することが可能になっています。
