Merkle Tree

複数のデータをまとめてハッシュ化し、その正しさや改ざんの有無を検証できるデータ構造

もともとハッシュ木と呼んでいたが、アメリカの暗号学者ラルフ・C・マークル（Ralph C. Merkle）の名前に由来してMerkle Treeとなった

メリット

データをコンパクトにまとめられる空間効率のよさ

ルートだけを比較すれば変更が検知できるので高速性

仕組み

最下層のリーフには元データ（例：トランザクションやファイル）のハッシュ値が並ぶ

それらを2つずつ組み合わせて連結し、新たにハッシュ化する

この操作を繰り返していくと、最終的に一番上に1つのハッシュ値（マークルルート）が残る

code:text

例：4つのデータの場合

/ \

/ \ / \

| | | |

Data0 Data1 Data2 Data3

利用例