Hash Tree

ハッシュツリー（Hash Tree、Merkle ツリー）はデータブロックのハッシュを二分木に編成する。葉はデータブロックのハッシュ、内部ノードは子ハッシュの連結のハッシュで、根が全体のダイジェストである。

目的

大規模データの完全性を効率的に検証する——任意の葉の検証に O(log n) 個の兄弟ハッシュだけでよく、ツリー全体を再計算しない。

メカニズム

葉 h_i=H(data_i)、内部ノード h=H(h_left || h_right)、根 h_root が全体のダイジェストである。葉 i の検証には、葉から根への経路上の各レベルの兄弟ハッシュ（認証パス）が必要である。

ユースケース

Git のコミットツリー
ブロックチェーンのトランザクション検証
P2P ファイル完全性（BitTorrent）

関連ツール

ハッシュ計算ツール

Compute MD5, SHA-1, SHA-256, or SHA-512 hashes with hex or Base64 output。無料、プライベート、100%クライアントサイド。

SHA-3 / Keccak ハッシュ計算

Compute SHA-3 (224/256/384/512) and Keccak-256 hashes。無料、プライベート、100%クライアントサイド。

References