マークルツリー とは？

各ノードが「子ノードのハッシュ値」を持っているのが特徴だよ。末端にデータがあって、それをペアにしてハッシュ化、さらにそのハッシュ同士をハッシュ化して、最終的に1つのルートハッシュにまとめるんだ

たとえば1万件のデータがあったとして、1件でも改ざんされるとルートハッシュが変わるんだ。しかも、どの枝が変わったかツリーをたどれば素早く特定できるよ

そうだよ。ビットコインのブロックにはトランザクションのマークルルートが入っていて、全トランザクションをダウンロードしなくても特定の取引が含まれているか検証できるんだ。これをSPV（簡易支払い検証）と呼ぶよ

Gitのコミットハッシュも似た仕組みだし、AWSのDynamoDBやApache Cassandraではデータの同期確認に使われているよ。ファイル転送プロトコルでも破損検知に活躍しているんだ

ハッシュの計算自体はとても高速だから問題ないよ。むしろ検証が効率的になるのがメリットで、N件のデータに対してlog(N)回の比較で検証できるんだ。100万件でも20回程度のハッシュ比較で済むから圧倒的に速いんだよ