マークルツリーとは？
マークルツリーはハッシュツリー（ハッシュ木）とも呼ばれ、大量のデータの完全性を効率的に検証するために使用されるデータ構造です。ツリー状の構造で、各リーフ（葉）ノードにはデータブロックのハッシュが格納され、非リーフノードには子ノードのハッシュが格納されます。ツリーのルートノードはマークルルートと呼ばれ、すべてのリーフノードのハッシュです。
マークルルートは、ツリー内のすべてのデータブロックのハッシュです。つまり、データブロックのいずれかが変更されると、マークルルートも変更されます。この性質を利用して、マークルリー内のすべてのデータの整合性を検証することができます。
マークルツリー内のデータの完全性を検証するには、各データブロックのハッシュを計算し、ツリーに格納されているハッシュと比較を行います。ハッシュが一致すれば、データは改ざんされていないことになります。
マークルツリーは、以下のような様々なアプリケーションで使用されています。
ブロックチェーン
マークルツリーは、ブロックチェーンにおけるトランザクションの真正性を検証するために使用されます。
例えば、ビットコインでは、トランザクションの各ブロックをハッシュ化してマークルルートを作成する。そして、このマークルルートが次のブロックのブロックヘッダーに含まれる、ということです。このようにして、ブロックチェーン内のすべての取引が改ざんされていないことを検証することができます。
分散システム
マークルツリーは、分散システムにおけるデータの完全性を検証するために使用でされます。例えば、あるファイルが複数のサーバーに保存されている場合、マークルツリーを使用してファイルのハッシュを作成し、そのファイルがすべてのサーバーで同じであることを検証することができます。
ファイルの検証
マークルツリーは、ファイルの完全性を検証するために使用されます。例えば、インターネットからファイルをダウンロードした場合、マークルツリーを使ってそのファイルが不正に改ざんされていないことを検証することができます。
以下は、取引所のお客様の預り残高を表すマークルツリーを図示したものです。
マークルツリーの方法では、各データのサブセットを表す個々の「リーフ（葉）」を作成し、各「リーフ」はその中に含まれる情報を表すハッシュを持ちます。いくつかの「リーフ」データのサブセットを集めると、データの「ブランチ（枝）」を構築することができます。この「ブランチ」もまた、すべての「リーフ」のハッシュを新しい単一の固定サイズのハッシュ値として結合することによって作成されるハッシュによって表すことができる。すべての「ブランチ」ハッシュを集めることで、最終的なハッシュツリーを作ることができ、その結果、完全なデータ構造に含まれるすべての情報を含む最終的なマークルルートハッシュが得られます。
このプロセスは、ファイル全体ではなくブロックのハッシュのみを計算する必要があるため、非常に効率的です。そのため、大きなファイルの完全性を迅速かつ簡単に検証することができます。
マークルツリーはなぜ重要なのか？
マークルツリーは、データの完全性を検証するための強力なツールです。効率的で拡張性があり、安全です。その結果、データが改ざんされていないことを保証することが重要なさまざまなアプリケーションで使用されています。当社の場合は「Proof of Solvency（支払い能力の証明）」として使用しています。各ユーザは、自分の情報のリーフノード（葉ノード）、つまり口座残高がマークルツリーに「存在する」こと、そしてマークルツリーのリーフがどれも改ざんされていないことを検証できます。