マークルツリーとは何ですか？

データのハッシュ値を木構造で積み上げ、最終的に1つのルートハッシュにまとめるデータ構造。大量のデータの整合性を効率的に検証できる。

マークルツリーのポイントは？

データをハッシュ値のツリー構造で管理し、改ざん検知を効率化する仕組み。末端のデータが1つでも変わるとルートハッシュが変化するため不正がすぐわかる。ブロックチェーンやGitなど、データの整合性検証に幅広く使われている。全データをダウンロードしなくても一部のデータの正当性を証明できる（SPV検証）

【まーくるつりー】

💡 全ページを読まなくても改ざんがバレる、データの家系図

📌 このページのポイント

マークルツリーのイメージ

ひよこ

マークルツリーって普通のツリーと何が違うの？

ペンギン先生

各ノードが「子ノードのハッシュ値」を持っているのが特徴だよ。末端にデータがあって、それをペアにしてハッシュ化、さらにそのハッシュ同士をハッシュ化して、最終的に1つのルートハッシュにまとめるんだ

ひよこ

それの何がうれしいの？

ペンギン先生

たとえば1万件のデータがあったとして、1件でも改ざんされるとルートハッシュが変わるんだ。しかも、どの枝が変わったかツリーをたどれば素早く特定できるよ

ひよこ

ブロックチェーンで使われてるって聞いたけど？

ペンギン先生

そうだよ。ビットコインのブロックにはトランザクションのマークルルートが入っていて、全トランザクションをダウンロードしなくても特定の取引が含まれているか検証できるんだ。これをSPV（簡易支払い検証）と呼ぶよ

ひよこ

ブロックチェーン以外でも使われてるの？

ペンギン先生

Gitのコミットハッシュも似た仕組みだし、AWSのDynamoDBやApache Cassandraではデータの同期確認に使われているよ。ファイル転送プロトコルでも破損検知に活躍しているんだ

ひよこ

ハッシュを何回も計算するのって遅くならないの？

ペンギン先生

ハッシュの計算自体はとても高速だから問題ないよ。むしろ検証が効率的になるのがメリットで、N件のデータに対してlog(N)回の比較で検証できるんだ。100万件でも20回程度のハッシュ比較で済むから圧倒的に速いんだよ

まとめ：ざっくりこれだけ覚えればOK！

「マークルツリー」って出てきたら「ハッシュを積み上げてデータの改ざんを効率的に検知するツリー構造」と思えればだいたいOK！

📖 おまけ：英語の意味

「Merkle Tree」＝マークルの木

💬 1979年にラルフ・マークル（Ralph Merkle）が特許を取得した技術で、発明者の名前がそのまま付いているよ。ハッシュツリーとも呼ばれるんだ