マークル木と包含証明

マークル木とは何か

ブロックチェーンのブロックには数千件の取引が入りますが、その中身を一切持たずに「特定の取引がブロックに含まれるか」を検証したい場面があります。これを可能にするのがマークル木（Merkle tree、ハッシュ木）です。Ralph Merkle が1979年に出願（米国特許 4,309,569、成立は1982年）したデータ構造で、暗号学的ハッシュ関数（/security/ の領域）を木状に積み上げ、任意個のデータを単一のルートハッシュに要約します。

構成は単純です。まず各データ（取引）をハッシュ化して葉とします。次に葉を左右のペアにまとめ、2つのハッシュを連結して再度ハッシュした値を親ノードにします。これを1つのノードになるまで繰り返した最上位がマークルルート（ルートハッシュ）です。ビットコインの場合、ハッシュ関数は SHA-256 を2回かける double-SHA256 が使われます。

              Root = H( H12 || H34 )
             /                      \
      H12 = H(H1||H2)          H34 = H(H3||H4)
        /        \               /        \
   H1=H(Tx1)  H2=H(Tx2)     H3=H(Tx3)  H4=H(Tx4)
      |          |             |          |
     Tx1        Tx2           Tx3        Tx4

包含証明（マークルproof）の仕組み

マークル木の真価は包含証明（inclusion proof / Merkle proof）にあります。「Tx3 がこの木に含まれる」ことを、木全体を渡さずに証明したい。必要なのは、対象の葉から根へ登る経路上で、各段の兄弟（sibling）ノードのハッシュだけです。

上図で Tx3 の包含を示すには、検証者に H4（同じ段の兄弟）と H12（1つ上の段の兄弟）を渡します。検証者は手元の Tx3 から以下を再計算します。

h  = H(Tx3)              # 検証者が対象データから自分で計算
h  = H(h  || H4)         # 兄弟 H4 と連結 → H34 を得る
h  = H(H12 || h)         # 兄弟 H12 と連結 → Root を得る
Root' == Root ?          # 既知の正しいルートと一致すれば包含が成立

ここで連結の左右が重要です。対象が右の子なら H(sibling || h)、左の子なら H(h || sibling) となり、順序を間違えると別のハッシュになります。そのため proof の各要素には、その兄弟が左右どちらかを示すフラグ（またはインデックスの偶奇）を添えます。

証明サイズが対数で済むのが決定的な利点です。葉が n 枚の平衡二分木の高さは約 log2(n) なので、proof に含める兄弟ハッシュも約 log2(n) 個。検証計算も同じく約 log2(n) 回のハッシュで完了します。

葉が100万件（およそ2の20乗）でも、proof はわずか20個程度のハッシュで足ります。この「n が増えても証明は対数でしか伸びない」性質こそ、後述する軽量クライアントを成立させる土台です。

軽量クライアント（SPV）による効率的検証

ビットコインのフルノードは全ブロック・全取引を保持しますが、スマートフォンのような端末には重すぎます。そこで Nakamoto の原論文が提示したのが SPV（Simplified Payment Verification、簡易支払い検証）です。SPVクライアント（軽量クライアント）は取引本体を持たず、各ブロックのヘッダだけを連鎖として保持します。

ブロックヘッダは80バイト程度と小さく、その中にマークルルートが埋め込まれています。ヘッダはさらに前ブロックのハッシュとProof-of-Workの難易度目標を含むため、ヘッダ連鎖を辿るだけで「そのルートが最も work を積んだ正当なチェーン上にある」ことを確認できます。ここに包含証明を組み合わせます。

検証の流れは次のとおりです。

1. SPVは信頼するフルノードへ「Txの包含証明が欲しい」と要求する
2. フルノードは Tx を含むブロックのマークル経路（兄弟ハッシュ列）を返す
3. SPVは手元の Tx から proof を畳み込み、ルートを再計算する
4. 再計算したルートが、自分が持つブロックヘッダ内のルートと一致するか照合
5. 一致し、かつそのヘッダが最長（最大 work）チェーン上にあれば包含を承認

セキュリティ上の注意点

マークル木の安全性は下敷きのハッシュ関数の衝突困難性に全面的に依存します。関数が破られて自由に衝突を作れると、同じルートを持つ別の取引集合を捏造できてしまいます。さらに実装レベルでは、葉と内部ノードでドメイン分離（別々のプレフィックスを付けてハッシュ）を怠ると、内部ノードのハッシュを葉と誤認させる攻撃が成立し得ます。

まとめ

• マークル木は葉データをハッシュ化し、隣接ペアを連結・再ハッシュして単一のルートハッシュに畳み込む二分木。ルートは全データの改竄検知用の要約になる。
• 包含証明は根までの経路上の兄弟ハッシュ列だけで構成され、サイズも検証計算もO(log n)。全走査 O(n) を避けて特定取引の包含を確かめられる。
• **SPV（軽量クライアント）**はブロックヘッダのルートのみ保持し、フルノードの proof を畳み込んでルートを照合。台帳全体を持たずに包含を検証できるが、状態の正しさは多数派の正直さに依存する。
• 安全性はハッシュの衝突困難性が土台。奇数ノードや重複葉、ドメイン分離の扱いを誤ると（CVE-2012-2459 のように）同一ルートの捏造を許すため、実装では慎重な設計が要る。