データの検証などで利用される Merkle tree/マークル木/hash tree/ハッシュ木についてメモ。 Merkle Tree の概要 wikipedia の概要をそのままコピペ。 暗号理論および計算機科学において、ハッシュ木(Hash tree, ハッシュツリー)またはマークル木(Merkle tree)とは、より大きなデータ(例えばファイル)の要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。このデータ構造はハッシュリストとハッシュチェインの組み合わせでできており、ハッシュ法の延長上にある手法といえる。 Merkle tree の利用例 merkle tree が2つ与えられた時に、ルートノードから子ノードに向かってハッシュ値をたどっていけば、どこが壊れているのか特定が簡単で、壊れている部分木だけを更新すればよい。 Amazon dynamo/cassan