【まーくるつりー】
マークルツリー とは？
最終更新:
💡 データのハッシュを枝ごとにまとめ、ルートと照合する
データのハッシュを木構造でまとめ、子のハッシュから親のハッシュを計算してルートに集約するデータ構造。信頼できるルートと途中のハッシュを使い、一部のデータが含まれることを効率よく検証できる。
📌 このページのポイント
- 葉のデータからハッシュを作り、上の階層へまとめる
- データの変更を、再計算したルートと基準のルートとの比較で検知する
- 対象データと経路に必要なハッシュで、全データを取得せず包含を検証できる
- ハッシュの安全性と基準のルートの信頼が必要で、内容の正しさを保証する仕組みではない
ひよこ マークルツリーって、普通のツリーと何が違うの？
ペンギン先生 葉にデータのハッシュを置き、子のハッシュをまとめて親を計算するのが特徴だよ。例えば二分木なら、左右のハッシュを順番に連結してさらにハッシュ化し、最後にルートへまとめる。細かな計算規則は方式によるんだ。
ひよこ ルートを見るだけで、改ざんが勝手に分かるの？
ペンギン先生 比較の基準が必要だよ。データから計算したルートを、信頼できる基準のルートと照合するんだ。攻撃者がデータと基準の両方を置き換えられるなら、それだけでは検知できない。使うハッシュの安全性も前提になるよ。
ひよこ 全部のデータを読まなくても確認できる？
ペンギン先生 一つのデータが含まれるかなら、そのデータと、葉からルートへ計算するための兄弟側のハッシュを使えるよ。これが包含証明。全てのデータが正しいかを丸ごと検査することとは区別しよう。
ひよこ ビットコインでも使うんだよね？
ペンギン先生 ブロックのヘッダーに取引のマークルルートが入っているよ。SPVではヘッダーとマークル枝を使って取引がブロックに含まれることを確認する。ただし、含まれるという証明だけで取引の妥当性全てを検査したことにはならないんだ。
ひよこ 大量のデータでも、計算量はいつも少ない？
ペンギン先生 バランスのよい二分木で一件の包含を調べる経路は、データ件数に対して対数的に増えるよ。でも最初に全データを読んで木を作る作業まで対数回で済むわけではない。証明の準備やデータの大きさも含めて考えよう。
まとめ：ざっくりこれだけ覚えればOK！
「マークルツリー」って出てきたら「ハッシュを木にまとめてデータを照合する仕組み」と思えばだいたいOK！
📖 おまけ：英語の意味
「Merkle Tree」 ＝ マークルの木
💬 Ralph Merkleにちなむ名前で、ハッシュツリーとも呼ぶよ。関連する米国特許US4309569Aは1979年に出願され、1982年に成立しているんだ