ブロックチェーン技術の仕組みを深く理解しようとすると、「マークルツリー」（Merkle Tree）という用語に出会うことがあります。一見すると難しそうな概念ですが、その基本的なアイデアは比較的シンプルで、ハッシュ関数の応用として非常にエレガントなデータ構造です。
マークルツリーは、ビットコインのブロック内に含まれる大量のトランザクションデータを効率的に管理し、検証するための仕組みとして採用されています。この構造がなければ、ブロックチェーンのスケーラビリティや軽量クライアント（SPVノード）の実現は極めて困難だったと考えられます。
本記事では、マークルツリーの基本概念から構築プロセス、ビットコインにおける具体的な活用方法、そしてマークルプルーフによる効率的な検証の仕組みまで、図解的な説明を交えながら丁寧に解説していきます。前回の記事で解説したハッシュ関数の知識を前提としていますが、ハッシュ関数についても必要に応じて振り返りますので、安心してお読みいただければと思います。
目次
1. マークルツリーの基本概念
1-1. マークルツリーとは何か
マークルツリー（Merkle Tree）は、1979年にアメリカの暗号学者ラルフ・マークル（Ralph Merkle）が発明したハッシュベースのデータ構造です。「ハッシュツリー」（Hash Tree）とも呼ばれ、大量のデータの整合性を効率的に検証するための仕組みです。
マークルツリーの基本的なアイデアは、データをペアにしてハッシュ化し、さらにそのハッシュ値をペアにしてハッシュ化するという操作を繰り返して、最終的に1つのハッシュ値（マークルルート）にまとめるというものです。
木構造（ツリー構造）の最下層には個々のデータのハッシュ値が並び、上の層に行くほどデータが集約されていきます。最上層にあるたった1つのハッシュ値（マークルルート）が、ツリー全体のデータの要約として機能します。
1-2. なぜ「ツリー」と呼ばれるのか
マークルツリーが「ツリー」（木）と呼ばれるのは、その構造がコンピュータサイエンスにおける「二分木」（Binary Tree）に類似しているからです。
二分木とは、各ノード（節点）が最大2つの子ノードを持つ木構造のことです。マークルツリーでは、各ノードが2つの子ノードのハッシュ値を結合してハッシュ化した値を保持しています。
用語を整理しておきましょう。
- リーフノード（葉ノード）: ツリーの最下層にあるノード。個々のデータ（トランザクション）のハッシュ値を保持します
- 内部ノード: リーフノードでもルートノードでもないノード。2つの子ノードのハッシュ値を結合してハッシュ化した値を保持します
- ルートノード（マークルルート）: ツリーの最上層にあるただ1つのノード。ツリー全体のデータを代表するハッシュ値を保持します
1-3. マークルツリーの構造を視覚的に理解する
4つのトランザクション（TxA, TxB, TxC, TxD）を含むマークルツリーの構造を、テキストで図示してみましょう。
マークルルート
Hash(AB + CD)
/ \
Hash(AB) Hash(CD)
/ \ / \
Hash(A) Hash(B) Hash(C) Hash(D)
| | | |
TxA TxB TxC TxD
<ul>
<li>最下層: 各トランザクション（TxA〜TxD）のハッシュ値を計算します</li>
<li>第2層: Hash(A)とHash(B)を結合してハッシュ化しHash(AB)を得ます。同様にHash(C)とHash(D)からHash(CD)を得ます</li>
<li>最上層: Hash(AB)とHash(CD)を結合してハッシュ化し、マークルルートを得ます</li>
</ul>
<p>このように、4つのトランザクションが2回のハッシュ化の積み重ねで、1つのハッシュ値に集約されます。トランザクションの数が増えても、同じ原理でツリーの層を増やしていくことで、最終的に1つのマークルルートにまとめることができます。</p>
<hr/>
<h2>2. マークルツリーの構築プロセス</h2>
<h3>2-1. ステップ1: リーフノードの生成</h3>
<p>マークルツリーの構築は、最下層のリーフノードの生成から始まります。</p>
<p>ビットコインのブロックに含まれるすべてのトランザクションに対して、それぞれのハッシュ値を計算します。ビットコインでは、トランザクションデータをSHA-256で2回ハッシュ化（ダブルSHA-256）したものがトランザクションID（TXID）として使われます。</p>
<p>たとえば、あるブロックに8つのトランザクション（Tx1〜Tx8）が含まれている場合、8つのリーフノードが生成されます。</p>
<p>H1 = SHA256d(Tx1)
H2 = SHA256d(Tx2)
H3 = SHA256d(Tx3)
...
H8 = SHA256d(Tx8)
ここで「SHA256d」は「ダブルSHA-256」を意味しています。
2-2. ステップ2: 親ノードの生成
リーフノードが生成されたら、隣接する2つのハッシュ値をペアにして結合し、その結合データをさらにハッシュ化します。
H12 = SHA256d(H1 + H2)
H34 = SHA256d(H3 + H4)
H56 = SHA256d(H5 + H6)
H78 = SHA256d(H7 + H8)
ここで「+」はデータの結合（連結）を意味しています。H1のバイト列の後ろにH2のバイト列をつなげたものをハッシュ化する、という操作です。
この操作により、8つのリーフノードが4つの親ノードに集約されました。
2-3. ステップ3: ルートまでの繰り返し
同じ操作を繰り返し、ノード数が1になるまで続けます。
H1234 = SHA256d(H12 + H34)
H5678 = SHA256d(H56 + H78)
そして最後に、
マークルルート = SHA256d(H1234 + H5678)
この最終的なハッシュ値がマークルルートであり、ブロックヘッダーに格納されます。8つのトランザクションが、3層の二分木構造を経て、1つの256ビットのハッシュ値にまとめられました。
2-4. トランザクション数が奇数の場合の処理
マークルツリーはペアを作って処理するため、各層でノードの数が奇数になると問題が生じます。ビットコインのプロトコルでは、奇数の場合、最後のノードを複製してペアを作るという方法で対処しています。
たとえば、3つのトランザクション（Tx1, Tx2, Tx3）の場合、Tx3のハッシュ値を複製して4つのリーフノードとします。
H1, H2, H3, H3（H3を複製）
5つのトランザクションの場合は、まず最下層でTx5を複製して6つにし、さらに第2層で奇数になった場合も同様に複製します。
この複製処理は、マークルツリーの構築を簡潔にするための実装上の工夫ですが、一方でセキュリティ上の微妙な問題（CVE-2012-2459として報告された脆弱性）を引き起こした経緯もあります。この問題についてはBitcoin Coreの開発チームによって修正されています。
2-5. 構築の計算量
マークルツリーの構築に必要な計算量を分析してみましょう。
n個のトランザクションがある場合、リーフノードの生成にn回のハッシュ計算が必要です。第2層ではn/2回、第3層ではn/4回と、各層で半減していきます。全体の計算回数は以下のようになります。
n + n/2 + n/4 + ... + 1 ≒ 2n
つまり、マークルツリーの構築に必要なハッシュ計算の回数は、トランザクション数のおよそ2倍です。計算量のオーダーとしてはO(n)であり、非常に効率的な処理です。
3. ビットコインにおけるマークルツリーの役割
3-1. ブロックヘッダーとマークルルート
ビットコインのブロックヘッダーは80バイトの固定長データで構成されており、その中にマークルルートが含まれています。ブロックヘッダーの構造を改めて見てみましょう。
| フィールド | サイズ | 説明 |
|---|---|---|
| バージョン | 4バイト | ブロックのバージョン番号 |
| 前ブロックハッシュ | 32バイト | 直前のブロックのハッシュ値 |
| マークルルート | 32バイト | トランザクションのマークルツリーのルートハッシュ |
| タイムスタンプ | 4バイト | ブロック作成時刻 |
| 難易度ターゲット | 4バイト | マイニング難易度 |
| ナンス | 4バイト | マイニングで調整する値 |
マークルルートは32バイト（256ビット）の固定長であり、ブロックに含まれるトランザクションが1件であっても1万件であっても、同じサイズに収まります。これにより、ブロックヘッダーのサイズが常に80バイトで固定され、ブロックの検証やマイニングのプロセスがトランザクション数に依存しない効率的な構造となっています。
3-2. データの整合性保証
マークルルートの最も重要な役割は、ブロック内のすべてのトランザクションデータの整合性を保証することです。
ハッシュ関数の雪崩効果により、ブロック内のどのトランザクションが少しでも変更されると、マークルルートの値が完全に変わります。マークルルートはブロックヘッダーに含まれており、ブロックヘッダーはそのブロックのハッシュ値の計算に使われます。つまり、トランザクションの改ざんは、ブロックのハッシュ値の変化を引き起こし、最終的にはブロックチェーン全体の整合性の破綻につながります。
この連鎖的な保護メカニズムにより、過去のトランザクションを改ざんするためには、そのブロック以降のすべてのブロックを再計算する必要が生じます。これが、ブロックチェーンの改ざん耐性の根幹を支える仕組みです。
3-3. coinbaseトランザクションの位置
ビットコインのマークルツリーにおいて、一番最初のリーフノード（左端）には必ず「coinbaseトランザクション」が配置されます。coinbaseトランザクションとは、マイナーが新しいブロックを採掘した際の報酬を自分自身に支払うトランザクションのことです。
coinbaseトランザクションには、ブロック報酬（新規発行のBTC + トランザクション手数料）の他に、マイナーが自由に使えるデータ領域（coinbaseデータ）が含まれています。この領域は、Extra Nonceの格納や、マイナーの識別情報の埋め込み、任意のメッセージの記録などに使われます。
ビットコインのジェネシスブロック（最初のブロック）のcoinbaseトランザクションには、サトシ・ナカモトが「The Times 03/Jan/2009 Chancellor on brink of second bailout for banks」というメッセージを埋め込んだことが知られています。
3-4. Witness Merkle Tree（SegWit）
2017年にSegWit（Segregated Witness）が導入されたことで、ビットコインのブロックには従来のマークルツリーに加えて、新たなマークルツリーが追加されました。
SegWitでは、トランザクションの署名データ（Witness Data）がトランザクション本体から分離されています。この署名データに対して別途マークルツリー（Witness Merkle Tree）が構築され、そのルートハッシュはcoinbaseトランザクションのOP_RETURN出力に埋め込まれます。
この設計により、従来のブロックヘッダーのマークルルートは、署名データを除いたトランザクションデータから計算されます。これがSegWitの「Segregated（分離された）Witness（証拠）」という名前の由来です。
4. マークルプルーフと軽量検証
4-1. SPV（Simplified Payment Verification）とは
マークルツリーの最も実用的な応用の一つが、SPV（Simplified Payment Verification）です。SPVは、サトシ・ナカモトがビットコインのホワイトペーパーで提唱した概念で、ブロックチェーン全体をダウンロードしなくても、特定のトランザクションがブロックに含まれていることを検証できる仕組みです。
フルノードは、すべてのブロックとトランザクションをダウンロードして検証しますが、これには数百GBのストレージと大量の帯域幅が必要です。一方、SPVノード（軽量クライアント）は、ブロックヘッダーのみをダウンロードし、特定のトランザクションの検証にはマークルプルーフを使用します。
ブロックヘッダーは1つあたり80バイトなので、約80万ブロック分のヘッダーでも約64MBに収まります。これは、スマートフォンのような限られたストレージの端末でも十分に扱える量です。
4-2. マークルプルーフの仕組み
マークルプルーフとは、特定のトランザクションがマークルツリーに含まれていることを証明するために必要な最小限のハッシュ値のセットです。
先ほどの8トランザクションの例で、Tx3がブロックに含まれていることを証明したい場合を考えてみましょう。
マークルルート
Hash(AB + CD)
/ \
Hash(AB) Hash(CD) ← Hash(AB)が必要
/ \ / \
Hash(A) Hash(B) Hash(C) Hash(D) ← Hash(D)が必要
| | | |
TxA TxB TxC TxD ← Hash(C)は自分で計算
^
検証対象
Tx3の包含証明に必要なデータは以下のとおりです。
この3つの情報があれば、以下の手順でマークルルートを再現できます。
一致すれば、Tx3がこのブロックに確かに含まれていることが証明されます。
4-3. マークルプルーフの効率性
マークルプルーフの効率性は、マークルツリーの二分木構造に由来します。
n個のトランザクションを含むブロックで、特定のトランザクションの包含証明に必要なハッシュ値の数は、ツリーの深さに等しく、log2(n)個です。
具体的な数字で見てみましょう。
| トランザクション数 | 必要なハッシュ値の数 |
|---|---|
| 4 | 2 |
| 16 | 4 |
| 256 | 8 |
| 1,024 | 10 |
| 4,096 | 12 |
| 65,536 | 16 |
トランザクション数が1,000件あるブロックでも、わずか10個のハッシュ値（各32バイト）で包含証明が完了します。全トランザクションデータをダウンロードする場合と比較すると、必要なデータ量は桁違いに少なくなります。
この対数的なスケーリング特性が、マークルプルーフの最大の利点です。トランザクション数が増えても、証明に必要なデータ量はほぼ一定に保たれます。
4-4. SPVノードのセキュリティモデル
SPVノードのセキュリティモデルは、フルノードとは異なる前提に基づいています。
フルノードは、すべてのトランザクションを検証するため、不正なトランザクションを自ら検出できます。一方、SPVノードは、マークルプルーフによってトランザクションがブロックに「含まれている」ことは検証できますが、そのトランザクション自体が「有効である」ことの完全な検証は行えません。
SPVノードは以下の信頼の前提に依存しています。
- 最長チェーン（最もProof of Workが積み重なったチェーン）が正当なチェーンであること
- マイナーが不正なトランザクションをブロックに含めていないこと
- 接続先のフルノードが正確なブロックヘッダーを提供していること
実用上は、これらの前提は十分に成り立つと考えられていますが、フルノードと比較するとセキュリティレベルは低いということを理解しておく必要があります。
4-5. ブルームフィルターとプライバシー
SPVノードが特定のトランザクションに関するマークルプルーフを要求する際、接続先のフルノードに対して「どのトランザクションに関心があるか」を伝える必要があります。これはプライバシーの観点から問題となりえます。
ビットコインのプロトコル（BIP37）では、「ブルームフィルター」という確率的データ構造を使って、関心のあるトランザクションの情報をある程度曖昧にして伝える仕組みが導入されています。ブルームフィルターを使うことで、SPVノードは自分が実際に関心のあるトランザクション以外のトランザクションも一定の確率でマッチするように設定でき、フルノードに対して正確な関心事を隠すことができます。
ただし、ブルームフィルターのプライバシー保護は完全ではなく、複数のクエリの相関分析によってユーザーの関心事が推定される可能性があることが研究者によって指摘されています。この問題に対処するため、BIP157/158で定義された「Compact Block Filters」という新しいアプローチも提案されており、プライバシーの向上が期待されています。
5. マークルツリーの数学的性質
5-1. 二分木としてのマークルツリー
マークルツリーは、コンピュータサイエンスにおける完全二分木（Complete Binary Tree）として構成されます。完全二分木とは、すべてのリーフノードが同じ深さにある（または最下層のみリーフが左詰めで配置される）二分木のことです。
n個のリーフノードを持つ完全二分木の高さ（ルートからリーフまでの最大距離）は、ceil(log2(n))です。ここでceilは天井関数（切り上げ）を意味します。
この性質が、マークルプルーフの効率性を保証しています。ツリーの高さが対数的に増加するため、リーフの数（トランザクション数）が指数的に増えても、ルートまでのパスの長さ（証明に必要なハッシュ値の数）はゆっくりとしか増加しません。
5-2. ハッシュ関数との関係
マークルツリーのセキュリティは、使用されるハッシュ関数のセキュリティに完全に依存しています。
具体的には、以下のハッシュ関数の性質がマークルツリーの安全性を支えています。
- 衝突耐性: 異なるトランザクションセットから同じマークルルートが生成されることが不可能であること
- 原像耐性: マークルルートから元のトランザクションデータを逆算することが不可能であること
- 第2原像耐性: あるマークルルートに対して、別のトランザクションセットで同じマークルルートを生成することが不可能であること
SHA-256の衝突耐性が破られた場合、マークルツリーの安全性も損なわれることになります。ただし、前の記事で説明したとおり、SHA-256の衝突を発見するために必要な計算量は天文学的であり、現実的な脅威とは考えられていません。
5-3. 空間効率
マークルツリーの空間効率について分析してみましょう。
n個のリーフノードを持つマークルツリーの内部ノード数は、n – 1個です（完全二分木の性質）。ルートノードを含めた全ノード数は2n – 1個となります。
各ノードが32バイト（SHA-256のハッシュ値）を保持するとすると、ツリー全体のサイズは(2n – 1) x 32バイトです。1,000トランザクションのブロックであれば、マークルツリー全体のサイズは約64KBに収まります。
ただし、実際のビットコインノードの実装では、マークルツリー全体を常にメモリに保持しているわけではありません。必要に応じてトランザクションデータからマークルツリーを再構築するアプローチが取られることもあります。
6. マークルツリーの発展形
6-1. パトリシアマークルツリー
イーサリアムで使用されている「Modified Merkle Patricia Trie（修正マークルパトリシアトライ）」は、マークルツリーの発展形の一つです。
通常のマークルツリーが「データのリスト」を扱うのに対し、パトリシアマークルツリーは「キーと値のペア（マッピング）」を効率的に扱うことができます。イーサリアムでは、アカウントの状態（残高、ナンス、コントラクトコード、ストレージ）をキーバリューストアとして管理する必要があるため、この拡張が必要でした。
パトリシアマークルツリーの詳細はイーサリアムの章で改めて解説しますが、基本的なコンセプトは同じです。つまり、大量のデータを1つのハッシュ値（ルート）に要約し、効率的な検証を可能にするという点は、マークルツリーと共通しています。
6-2. スパースマークルツリー
スパースマークルツリー（Sparse Merkle Tree）は、非常に広い鍵空間（たとえば2の256乗通りの鍵）に対応したマークルツリーです。
通常のマークルツリーでは、存在するデータだけでツリーを構築しますが、スパースマークルツリーでは、すべての可能な鍵に対してデフォルト値（通常はゼロ）を持つ仮想的な完全二分木を前提とします。実際には、デフォルト値のサブツリーは計算済みのハッシュ値を使って効率的に表現するため、メモリ使用量は実際に存在するデータの量に比例します。
スパースマークルツリーの重要な特徴は、「あるデータが存在しないこと」（非包含証明）を効率的に証明できる点です。これは、通常のマークルツリーでは困難な操作です。
6-3. マークルマウンテンレンジ（MMR）
マークルマウンテンレンジ（Merkle Mountain Range、MMR）は、データが逐次追加される場合に適した変種のマークルツリーです。
通常のマークルツリーは、すべてのデータが揃った時点で構築されますが、MMRはデータが1つずつ追加されるたびに効率的に更新できる構造を持っています。ブロックチェーンのように、ブロックが逐次追加される場面での利用に適しています。
MMRは、複数の完全二分木（マークルツリー）を「山」のように並べた構造で、新しいデータが追加されるたびに、同じ高さの「山」をマージしていくことで成長します。
6-4. Verkle Tree
Verkle Tree（ベクルツリー）は、マークルツリーの次世代として注目されているデータ構造で、イーサリアムのアップグレードロードマップにも含まれています。
Verkle Treeの最大の利点は、マークルプルーフよりもはるかにコンパクトな証明（Verkle Proof）を生成できる点です。マークルツリーでは、各層で兄弟ノードのハッシュ値が必要でしたが、Verkle Treeでは「ベクトルコミットメント」という暗号技術を使うことで、証明サイズを大幅に削減できます。
特に、ツリーの分岐数（各ノードの子ノード数）を大きく取れるため、ツリーの深さが浅くなり、結果として証明サイズが小さくなります。マークルツリーは分岐数2（二分木）が一般的ですが、Verkle Treeでは分岐数256以上も実用的です。
7. イーサリアムにおけるマークルツリーの活用
7-1. イーサリアムの3つのマークルツリー
イーサリアムでは、各ブロックに3つのマークルツリーのルートハッシュが格納されています。
State Trie（ステートツリー）: イーサリアムの全アカウントの現在の状態（アドレス、残高、ナンス、コントラクトコード、ストレージルート）を保持するグローバルな状態ツリーです。すべてのアカウントの状態が1つのルートハッシュに集約されています。
Transaction Trie（トランザクションツリー）: ブロック内のすべてのトランザクションを保持するツリーです。ビットコインのマークルツリーと同様の役割を果たします。
Receipt Trie（レシートツリー）: 各トランザクションの実行結果（成功/失敗、消費ガス量、ログなど）を保持するツリーです。スマートコントラクトのイベントログもこのツリーに記録されます。
7-2. State Trieの役割と課題
イーサリアムのState Trieは、ビットコインのUTXOモデルとは根本的に異なるアプローチでアカウントの状態を管理しています。
State Trieの利点は、任意のアカウントの現在の残高やコントラクトの状態を、ツリーのルートハッシュに対する証明（マークルプルーフ）で検証できる点です。これにより、軽量クライアントでもアカウント情報の検証が可能になります。
一方で、State Trieは時間の経過とともに巨大化するという課題を抱えています。イーサリアムの全アカウントとコントラクトの状態を含むState Trieのデータサイズは膨大であり、フルノードのストレージ要件を押し上げる主要な要因となっています。
この問題に対処するため、イーサリアムコミュニティでは「State Expiry（状態の期限切れ）」や前述のVerkle Treeへの移行といった提案が議論されています。
7-3. Receipt TrieとEvent Log
Receipt Trieは、DApp（分散型アプリケーション）の開発において重要な役割を果たしています。
スマートコントラクトが「イベント」を発行すると、そのイベントのデータはReceipt Trie内のログとして記録されます。DAppのフロントエンドは、このイベントログを購読（subscribe）することで、ブロックチェーン上の状態変化をリアルタイムに把握できます。
たとえば、ERC-20トークンの送金が行われると、「Transfer」イベントが発行され、Receipt Trieに記録されます。ウォレットアプリやDExのインターフェースは、このイベントログをモニタリングすることで、トークンの送受信をリアルタイムに表示しています。
8. マークルツリーの実世界応用
8-1. Gitのバージョン管理
ソフトウェア開発で広く使われているGit（バージョン管理システム）も、内部的にマークルツリーに類似した構造（有向非巡回グラフ、DAG）を使ってファイルの変更履歴を管理しています。
Gitでは、ファイルの内容、ディレクトリ構造、コミット情報がそれぞれハッシュ値で識別され、親子関係で連結されています。コミットのハッシュ値は、そのコミットに含まれるすべてのファイルの状態を間接的に要約しており、マークルルートと同様の役割を果たしています。
8-2. Certificate Transparency
Certificate Transparency（CT）は、SSL/TLS証明書の発行を公開的に監視するための仕組みで、マークルツリーが重要な構成要素として使われています。
認証局（CA）が発行するすべての証明書は、CTログサーバーのマークルツリーに記録されます。これにより、不正な証明書の発行を検出したり、特定の証明書がCTログに含まれていることを効率的に検証したりすることが可能になります。
CTは、ブロックチェーンの外部でマークルツリーが大規模に活用されている好例です。
8-3. データベースの整合性検証
Amazon QLDBやImmuDBなどのデータベースシステムでは、マークルツリーを使ってデータの整合性と改ざんの有無を検証する機能が提供されています。
これらのシステムでは、データベースへの書き込み操作がジャーナル（ログ）として記録され、マークルツリーに組み込まれます。後からデータの変更や削除が行われた場合、マークルルートの不整合として検出することができます。
8-4. エアドロップとホワイトリスト
暗号資産の世界では、マークルツリーがエアドロップ（トークンの無料配布）やホワイトリストの管理に活用されています。
たとえば、10万件のウォレットアドレスにトークンをエアドロップする場合、すべてのアドレスと配布量をマークルツリーにまとめ、そのマークルルートだけをスマートコントラクトに格納します。各ユーザーは、自分のアドレスに対するマークルプルーフをスマートコントラクトに提示することで、トークンを受け取ることができます。
この方法では、スマートコントラクトに格納する必要があるデータが32バイトのマークルルートだけで済むため、ガス代を大幅に節約できます。10万件のアドレスをすべてスマートコントラクトに格納するのと比較すると、コスト差は桁違いです。
まとめ
本記事では、マークルツリーの基本概念から構築プロセス、ビットコインやイーサリアムでの活用、マークルプルーフによる効率的な検証の仕組み、そして発展形や実世界での応用まで、幅広く解説してきました。要点を振り返ってみましょう。
- マークルツリーは、大量のデータを1つのハッシュ値（マークルルート）に要約するハッシュベースの二分木構造です
- ビットコインのブロックヘッダーにはマークルルートが含まれており、ブロック内のすべてのトランザクションの整合性を保証しています
- マークルプルーフにより、特定のトランザクションの包含証明がlog2(n)個のハッシュ値で実現でき、SPVノード（軽量クライアント）の動作を可能にしています
- イーサリアムでは、State Trie、Transaction Trie、Receipt Trieの3つのマークルツリーが使われています
- マークルツリーの発展形として、パトリシアマークルツリー、スパースマークルツリー、Verkle Treeなどが開発されています
- ブロックチェーン以外にも、Git、Certificate Transparency、データベースの整合性検証など、幅広い分野で活用されています
マークルツリーは、ハッシュ関数の性質を巧みに組み合わせた、シンプルでありながら極めて強力なデータ構造です。ブロックチェーン技術の効率性とセキュリティの両立を支える重要な要素として、今後もその役割は大きいと考えられます。
よくある質問（FAQ）
Q1. マークルツリーとハッシュチェーンの違いは何ですか？
ハッシュチェーンは、データを直列に（一列に）ハッシュ化していく構造で、あるデータのハッシュ値が次のデータの入力に含まれます。ブロックチェーンのブロック間の連結がハッシュチェーンの例です。一方、マークルツリーは二分木構造で、データを階層的にハッシュ化していきます。マークルツリーの最大の利点は、特定のデータの包含証明がlog2(n)の効率で行える点で、ハッシュチェーンでは全データを順にたどる必要があるためO(n)の効率になります。
Q2. マークルルートが同じでも中身が異なるブロックは存在しえますか？
理論上は、ハッシュ衝突が発生すれば、異なるトランザクションセットから同じマークルルートが生成される可能性があります。しかし、SHA-256の衝突耐性を考慮すると、意図的にそのようなブロックを作成することは計算上不可能です。偶然に衝突が発生する確率も、宇宙の寿命よりも長い時間をかけても無視できるほど小さいため、実用上は「マークルルートが同じであればトランザクションセットも同じ」と見なして問題ないと考えられています。
Q3. ビットコインのブロックにトランザクションが1つしかない場合、マークルツリーはどうなりますか？
ブロックには必ず少なくともcoinbaseトランザクション（マイナー報酬のトランザクション）が含まれるため、トランザクション数がゼロになることはありません。coinbaseトランザクション1つだけの場合、マークルツリーは「ツリー」というよりも、そのトランザクションのハッシュ値がそのままマークルルートになります。ツリーの構造は実質的にリーフノードが1つだけの退化したケースとなります。
Q4. マークルプルーフのサイズは実際にどのくらいですか？
マークルプルーフのサイズは、ブロック内のトランザクション数によって決まります。SHA-256のハッシュ値は32バイトであり、必要なハッシュ値の数はlog2(n)です。たとえば、2,000トランザクションを含むブロックの場合、log2(2000)は約11ですので、マークルプルーフのサイズは約352バイト（32バイト x 11）にパス情報のオーバーヘッドを加えた程度です。トランザクションデータ全体が数MB以上になりうることを考えると、マークルプルーフの効率性は非常に高いと言えます。
Q5. なぜビットコインは二分木のマークルツリーを採用しているのですか？
二分木は、最もシンプルな木構造であり、実装が容易で検証ロジックも単純です。各ノードは2つの子ノードのハッシュ値を結合してハッシュ化するだけでよく、分岐数が多い場合のような結合順序の曖昧さが生じません。また、マークルプルーフの検証も、各層で1つのハッシュ値と結合してハッシュ化するという単純な操作の繰り返しで済みます。分岐数を増やすと各層で必要な兄弟ノードの数が増えるため、証明サイズとの兼ね合いで二分木が最適とは限りませんが、ビットコインの設計時点ではシンプルさが重視されたと考えられます。
Q6. マークルツリーはブロックチェーン以外にどのように使われていますか？
マークルツリーは、ブロックチェーン以外でも広く活用されています。Gitのバージョン管理では、ファイルやディレクトリの変更をハッシュベースのツリー構造で管理しています。Certificate Transparencyでは、SSL/TLS証明書の監視にマークルツリーが使われています。P2Pファイル共有では、大きなファイルを分割してダウンロードする際に、各チャンクの整合性をマークルツリーで検証しています。Amazon QLDBのような改ざん検知データベースでも、マークルツリーが核心的なデータ構造として採用されています。このように、データの整合性を効率的に検証する必要がある場面であれば、分野を問わず応用されている技術です。
※本記事は2026年3月時点の情報に基づいて作成しており、情報提供を目的としたものです。暗号資産への投資を推奨するものではありません。暗号技術に関する記述は一般的な解説であり、特定のシステムやプロダクトの安全性を保証するものではありません。暗号資産の価格は大きく変動し、元本割れのリスクがあります。投資判断はご自身の責任で行ってください。
