Merkle 木と認証データ構造の原理

大きなデータの完全性を「ハッシュ1本」で固定する

データ全体が改ざんされていないことを確かめたいなら、全体を1個のハッシュにかければ済みます。だが「100万件のうち、この1件だけが確かに含まれる」を、残り99万9999件を取り寄せずに検証したい――ここで効くのが Merkle 木（ハッシュ木） です。葉に個々のデータのハッシュを置き、隣り合う2つを連結して親ハッシュを作る、という操作を頂点（Merkle root）まで繰り返した二分木で、根ひとつが木全体の内容を要約します。一方向ハッシュの性質（ハッシュ関数の内部構造 を参照）により、どこか1ビットでも書き換われば根が必ず変わる。逆に言えば、信頼できる根さえ手元にあれば、巨大なデータの完全性を ハッシュ1本ぶん の情報で固定できます。これが認証データ構造（authenticated data structure）の核心です。

木の構築：葉から根へハッシュを畳む

構築は単純です。葉のハッシュを作り、ペアごとに連結してハッシュし直す操作を、ノードが1つになるまで繰り返します。

H = 暗号学的ハッシュ関数（例 SHA-256）

葉:   L0 = H(0x00 || data0)   ← 葉プレフィックス 0x00
      L1 = H(0x00 || data1)
      ...
内部: N(a,b) = H(0x01 || a || b)  ← 内部ノードプレフィックス 0x01

      Root = N( N(L0,L1), N(L2,L3) )   （4葉の例）

ここで葉と内部ノードに 異なるプレフィックス（0x00 / 0x01）を付けるのが実装上の要点です。これを省くと、内部ノードのハッシュ値を「葉のデータ」と偽る second-preimage 攻撃（葉と中間ノードの取り違え）が成立し、別の木を同じ根に見せかけられます。RFC 6962／9162（Certificate Transparency）はこのプレフィックスを明示的に規定しています。葉数が2のべき乗でない場合は、最後の孤立ノードをそのまま上に持ち上げる（複製しない）方式が安全です。葉を複製する Bitcoin 初期の方式は CVE-2012-2459 の延性（同じ根を生む別の木が作れる）を生みました。

包含証明：兄弟ハッシュだけで根を再計算する

ある葉が木に含まれることの証明（包含証明 / Merkle proof）は、その葉から根への経路上で 必要になる兄弟ノードのハッシュだけを並べたものです。これを authentication path と呼びます。検証者は葉のデータと兄弟ハッシュから根を自力で再計算し、既知の正しい根と一致するかだけを見ます。

8葉の木で leaf3 の包含を証明する：

         Root
        /    \
      N01     N23
     /  \    /   \
   N0    N1 ...
  / \   / \
 L0 L1 L2 L3 L4 L5 L6 L7
              ↑証明したい葉

証明 = [ L2, N0(=H(L0,L1)), N23の右半分 ]   ← 兄弟3つ
検証: x = H(0x01 || L2 || L3)          # まず兄弟 L2
      x = H(0x01 || N0 || x)          # 次に兄弟 N0
      x = H(0x01 || x  || sib)        # 最後の兄弟
      x == Root か？  ← 一致すれば包含が確定

葉数 N の木の高さは log2(N) なので、証明サイズも検証コストも O(log N)。100万葉でも兄弟は約20個（SHA-256 なら 640 バイト程度）で済みます。データ全体（数十MB）を送る代わりに数百バイトで完全性を保証できる、これがスケール上の決定的な利得です。各段で左右どちらの子かの情報（経路ビット）も必要で、連結順を間違えると別の根になります。

不在証明と一貫性証明

包含だけでなく、ないことの証明（不在証明 / non-membership）も作れます。素朴な木では「ない」は示せませんが、葉を キーでソートして並べると、問い合わせキーの直前と直後に来る2つの隣接葉の包含を示せば、その間に当該キーが存在し得ないことが証明できます（sorted Merkle tree）。鍵で索引する Patricia 木では、経路の途中で枝が分岐・終端する様子そのものが不在の証拠になります。

もうひとつが 一貫性証明（consistency proof） です。追記専用ログ（append-only log）が「古い根 R_old を持つ状態に、葉を足しただけで新しい根 R_new になった」ことを、ログ運営者が 過去を改ざんしていないと検証者へ示すための証明です。古い木の葉群が新しい木の左側に連続して残っていることを、共有される内部ノードのハッシュ列で確認します。これにより、ログが過去の項目をこっそり差し替える split-view 攻撃（人によって違う履歴を見せる）を監査で検出できます。

Patricia 木と Verkle 木への発展

二分 Merkle 木の弱点は、キーで索引できない点と、証明サイズが log N 本のハッシュに比例して伸びる点です。これを補う2系統の発展があります。

Merkle Patricia 木（Ethereum の状態木）は、キーのビット列で枝を選ぶ基数木（radix trie）に Merkle 構造を重ねたものです。共通プレフィックスを圧縮するため、任意のキーに対する包含・不在を効率よく証明でき、キー＝値ストア全体の状態を1つの根（state root）にまとめられます。

Verkle 木 は、各内部ノードのコミットメントを「子ハッシュの連結」ではなく ベクトルコミットメント（KZG 多項式コミットメントなど）で作ります。すると、ある段で k 本の兄弟を全部渡す代わりに、子全体に対する1個の証明 で「この位置にこの子がある」を示せます。結果、木を浅く（分岐数を256などに）しても証明が膨らまず、全体の証明サイズが Merkle 木の O(log N) 本のハッシュから ほぼ定数本 に縮みます。Ethereum が状態証明の肥大化対策として Verkle 木へ移行を検討してきた理由がこれです。

実応用：CT・ブロックチェーン・Git

この構造は現代インフラの随所で動いています。

• Certificate Transparency（CT）：全発行 TLS 証明書を、追記専用の Merkle 木ログに記録します。CA が誤発行・不正発行した証明書も、ログに載れば誰でも観測でき、一貫性証明でログ自身の改ざんも監視できます。詳細は X.509 証明書チェーン検証と CT を参照。
• ブロックチェーン：各ブロックは取引集合の Merkle root だけをヘッダに格納します。軽量クライアント（SPV）はブロック全体を持たずとも、包含証明だけで「この取引はこのブロックに入った」を検証できます。
• Git：コミット・ツリー・ブロブが内容ハッシュで連結された Merkle DAG そのものです。コミットハッシュ1つが全履歴の状態を固定し、git fsck の完全性検証や分散同期の差分検出を支えます。
• 分散ストレージ／同期：IPFS（Merkle DAG）、ZFS のブロックチェックサム、rsync/BitTorrent の塊検証も、部分取得とサーバー横断の完全性確認に同じ原理を使います。

CT・ブロックチェーンともに、ログ運営者やマイナーを 無条件には信じず、Merkle 証明で各自が検証する点が共通しています。根への署名やコンセンサスと組み合わせることで初めて改ざん不能になる構造は、鍵付き認証で生ハッシュ連結ではなく HMAC を使う発想とも通じます。

Merkle 木を「ハッシュを木状に並べた仕組み」で止めず、authentication path の数理・プレフィックス分離の理由・一貫性証明・ベクトルコミットメントへの発展まで分解できると、CT が誤発行をどう暴くか、SPV クライアントがなぜ軽いか、Git の整合性がどこで保証されるかが一本の線でつながります。