マークルのハッシュ木は、一握りのハッシュで1つのレコードが巨大なファイルの中にあることを証明する

あるレコードが大規模なデータセットの一部であることを証明するには、通常はデータセットを送る必要があった。これはバックアップ、トランザクションのファイル、あるいはウェブキャッシュにとって非現実的である。

マークルの1979年の学位論文と1989年の論文は、各ブロックをハッシュ化し、ハッシュを対にして1つのルートが残るまで続ける木を記述している。ある要素の検証には、ファイル全体ではなく、経路上のlog n個のハッシュが必要となる。

この木は、要素が含まれるかどうかの検査をルートに対する等値検査に変え、どこかで変更があれば変更された経路として現れる。こうして、すべてのバイトを見ることなくデータ構造全体を保証できる。

葉を、1つのルートに至るまで対ごとにハッシュ化することでコミットする

証明のサイズは対数的であるため、最大規模のデータセットでも検証は安価に済む。

ルートはデータセット全体にコミットするため、いかなる改ざんも検出される。

検証者が必要とするのはルートと短い経路だけで、サーバーを信頼する必要はない。

一方向ハッシュの連鎖であるため、データに関する情報は開示されない。

巨大な全体についての事実を証明するには、全体を送ってはならない。それを1つのダイジェストに畳み込み、そのうえで、その1つの主張をそのダイジェストに結びつける短い経路だけを与えればよい。

マークル木は、Git、暗号通貨のブロックチェーン、証明書の透明性、分散ストレージの基盤となっている。これにより、クライアントは1つの短いルートだけを信頼して、大規模で認証されていないストアの小さな一部を検証できる。