Merkle Tree

目的

大規模データの整合性検証を効率的にし、特定データブロックに絞り込めるようにする。

メカニズム

葉はデータブロックのハッシュ H(d_i) を保持し、内部ノードは子の連結のハッシュ H(left||right) を保持する。根ハッシュが全体を表す。1 ブロックの検証には根から葉までの経路上の兄弟ハッシュ O(log n) 個だけでよい（マークルプルーフ）。データブロックの変更は根ハッシュを変える。

ユースケース

• Gitオブジェクトツリーの検証
• ブロックチェーン取引の検証
• IPFSコンテンツアドレッシング
• 分散ストレージの整合性

例

• 入力

  4 data blocks → a 2-level Merkle tree

  Output

  The root hash represents all of them

  O(log n) verification

よくあるエラー

Weak hashes enable collision forgery

Use a secure hash such as SHA-256