マークルツリー (Merkle Tree) — 効率的なデータ検証
マークルツリーは大量のデータを1つのハッシュ値で要約し、効率的に整合性を検証できるバイナリハッシュツリー構造です。
**マークルツリー (Merkle Tree)**は大量のデータを1つのハッシュ値(マークルルート)で要約し、効率的に整合性を検証できるバイナリハッシュツリー構造です。1979年にラルフ・マークル(Ralph Merkle)が発明したこのデータ構造は、ビットコインのブロック構造において中心的な役割を果たし、軽量クライアントの効率的な検証を可能にしています。
graph TD ROOT["ルートハッシュ
Hash(H12+H34)"] H12["Hash(H1+H2)"] H34["Hash(H3+H4)"] H1["Hash(Tx1)"] H2["Hash(Tx2)"] H3["Hash(Tx3)"] H4["Hash(Tx4)"] TX1["Tx1"] TX2["Tx2"] TX3["Tx3"] TX4["Tx4"] ROOT --> H12 ROOT --> H34 H12 --> H1 H12 --> H2 H34 --> H3 H34 --> H4 H1 --> TX1 H2 --> TX2 H3 --> TX3 H4 --> TX4 style ROOT fill:#f7931a,stroke:#f7931a,color:#000 style H12 fill:#21262d,stroke:#f7931a,color:#e6edf3 style H34 fill:#21262d,stroke:#f7931a,color:#e6edf3 style H1 fill:#161b22,stroke:#30363d,color:#8b949e style H2 fill:#161b22,stroke:#30363d,color:#8b949e style H3 fill:#161b22,stroke:#30363d,color:#8b949e style H4 fill:#161b22,stroke:#30363d,color:#8b949e
バイナリハッシュツリーの構造
マークルツリーは最下位のリーフ（leaf）ノードから最上位のルートまでボトムアップで構築されます。具体的な手順は以下の通りです。
ステップ1 - リーフハッシュ生成: ブロックに含まれる各トランザクションのtxidをリーフノードとして使用します。ビットコインではSHA-256を2回適用(double-SHA256)して各トランザクションのハッシュを生成します。
ステップ2 - ペアワイズ結合: 隣接する2つのハッシュを連結(concatenate)した後、再度double-SHA256を適用して親ノードを生成します。例えばH(A)とH(B)が隣接するリーフであれば、親ノードはSHA256(SHA256(H(A) || H(B)))となります。
ステップ3 - 反復: ノードが1つだけ残るまでこのプロセスを繰り返します。最終的に残る単一のハッシュが**マークルルート(Merkle Root)**であり、これがブロックヘッダーのhashMerkleRootフィールドに記録されます。
ツリーの深さはlog₂(N)であるため、1,000件のトランザクションがあるブロックでもわずか10段階のハッシュ演算でマークルルートに到達します。この対数スケールの効率性がマークルツリーの核心的価値です。
マークル証明（Merkle Proof）の動作原理
マークル証明は、特定のトランザクションがブロックに含まれていることを証明するデータ構造です。ブロック全体のすべてのトランザクションをダウンロードする必要はなく、当該トランザクションからマークルルートまでのパスにある兄弟ハッシュだけを提供すれば済みます。
例えば、8件のトランザクションがあるブロックでトランザクションDの包含を証明するには、H(C)、H(AB)、H(EFGH)の3つのハッシュだけで十分です。検証者はH(D)を計算し、H(C)と結合してH(CD)を求め、H(AB)と結合してH(ABCD)を求め、最終的にH(EFGH)と結合してマークルルートを計算します。この結果がブロックヘッダーのマークルルートと一致すれば、トランザクションDがそのブロックに含まれていることが証明されます。
時間計算量はO(log n)です。ブロックに4,000件のトランザクションがあっても約12個のハッシュで証明が完了します。これはブロック全体（数MB）をダウンロードすることと比較して劇的な効率性の向上です。
SPV軽量検証での活用
SPV（Simplified Payment Verification）はサトシ・ナカモトのホワイトペーパー第8節に記述された軽量検証方式で、マークル証明に全面的に依存しています。SPVクライアントはブロックヘッダー（80バイト）のみをダウンロードし、関心のあるトランザクションについてフルノードにマークル証明を要求します。
この方式の利点はストレージと帯域幅の要件が極めて少ないことです。ブロックチェーン全体ではなくブロックヘッダーチェーンのみを保存するため、数十MBレベルのデータでもトランザクション検証が可能です。この効率性のおかげでモバイルウォレットなどの軽量クライアントが実現できました。ただしSPVはフルノードに依存するため、フルノードが特定のトランザクションの存在を隠す攻撃には脆弱です。
ビットコインでの実装の詳細
ビットコインのマークルツリー実装にはいくつかの特殊なルールがあります。
txidペアリング: トランザクションハッシュは順序通りにペアを形成して結合されます。1番目と2番目、3番目と4番目というようにペアリングされます。
奇数処理: 特定のレベルでノード数が奇数の場合、最後のノードを複製して自分自身とペアリングします。例えば3つのトランザクションA、B、Cがある場合、Cを複製して(A,B)、(C,C)として処理します。
コインベーストランザクション: ブロックの最初のトランザクションは常にコインベース（マイニング報酬）トランザクションであり、これもマークルツリーの最初のリーフとして含まれます。
CVE-2012-2459 脆弱性と解決
2012年に発見されたCVE-2012-2459は、ビットコインのマークルツリー実装における奇数ノード複製方式を悪用した脆弱性でした。攻撃者が同一のマークルルートを生成しながらも実際のトランザクションリストが異なる改ざんブロックを作成できました。具体的には、奇数個のトランザクションがあるブロックで最後のトランザクションを複製して追加すると同一のマークルルートが生成される問題でした。
この脆弱性はノードが無効なブロックを有効と判断させるものではなく、有効なブロックを無効として拒否させるDoS（サービス拒否）ベクトルとして悪用される可能性がありました。修正は、マークルツリー計算過程で同一のハッシュペアが発見された場合にそのブロックを無効として処理する検証ロジックを追加することでした。
タップルートのMAST（Merklized Abstract Syntax Trees）
MASTはマークルツリー構造をビットコインスクリプトに適用したもので、2021年に有効化されたタップルート(Taproot)アップグレードの核心的な構成要素です。従来のビットコインスクリプトはすべての可能な支出条件をトランザクションに含める必要がありましたが、MASTは各支出条件をマークルツリーのリーフとして配置し、実際に使用される条件のパスのみを公開します。
例えば「3-of-5マルチシグ、または1年後の2-of-5マルチシグ、または2年後の単独署名」という複雑な支出条件がある場合、MASTを使用すると実際の支出時に使用された条件とマークル証明のみを公開すればよく、他の条件の存在自体が明らかになりません。これによりプライバシーが大幅に向上し、公開すべきデータ量が減少するため手数料も削減されます。