Merkle木：Merkle Tree・Patricia Trie・Search Tree
ブロックチェーンもBitTorrentもGitも、その信頼性の根っこをたどると必ず「ハッシュの木」に行き着きます。基本のMerkle Treeから、Ethereumの状態管理を支えるMerkle Patricia Trie、P2Pのレプリカ同期のために生まれたMerkle Search Treeまで、大量のデータを1つのハッシュへ束ねる技術を詳説します。
Merkle Treeの基礎:大量のデータを1つのハッシュに束ねる
Merkle木（Merkle Tree、マークル木）とは、大量のデータ片をハッシュ関数によって1本の木構造にまとめ上げ、最終的に「1つのハッシュ値」へ集約する仕組みです。暗号研究者のRalph Merkleが1979年の特許出願（1987年発表の論文）で考案したことからこの名がついています。構造は単純で、まず各データ片（葉ノード）をハッシュ化し、隣り合う2つのハッシュを連結して再びハッシュ化したものを親ノードとし、これを頂点が1つになるまで繰り返します。木の頂点に残る唯一のハッシュ値がMerkleルート（ルートハッシュ）で、これがデータ集合全体への「コミットメント（約束）」として機能します。ルートさえ知っていれば、後から届く個々のデータ片が改ざんされていないかを検証できるのです。
Merkle木の真価は、Merkle証明（包含証明、Merkle proof）という仕組みにあります。あるデータ片が木に含まれることを証明するには、木全体を送る必要はなく、葉からルートまでの経路上にある兄弟ノードのハッシュだけを提示すればよいのです。木の深さはデータ数nに対して概ねlog₂nなので、証明に必要なハッシュの個数もO(log n)で済みます。たとえば100万件のデータでも、わずか約20個のハッシュ（合計で数百バイト程度）を提示するだけで、検証者は手元のルートハッシュと突き合わせて包含を確認できます。全データをダウンロードしなくても検証できるこの性質が、SPV（簡易支払い検証）のような軽量クライアントを可能にしています。
- 改ざん検知: どこか1ビットでもデータが変われば、そのハッシュ、さらには経路上のすべての親ハッシュ、最終的にルートハッシュまでが連鎖的に変化するため、改ざんは即座に検出できる。
- 証明サイズO(log n): データ量が増えても証明サイズは対数的にしか増えないため、大規模データセットでも実用的な検証コストに収まる。
- 部分検証・並列ダウンロード: ピースが届いた順にその場でハッシュを検証できるため、複数の相手から並列にデータ片を取得する用途と相性がよい。
- セカンドプリイメージ攻撃への注意: 葉ノードと内部ノードを同じ方法でハッシュ化すると、内部ノードのハッシュ値をあたかも葉ノードのデータであるかのように偽装できてしまう場合がある。RFC 6962（Certificate Transparency）では、葉には
0x00、内部ノードには0x01というプレフィックスを付けてハッシュ化することでこの攻撃を防いでいる。
| システム | 何をMerkle化するか | 目的 |
|---|---|---|
| Bitcoin | ブロック内の全トランザクション → ブロックヘッダのMerkleルート | SPVクライアントがブロック全体を持たずに特定のトランザクションの取り込みを検証できる |
| BitTorrent v2（BEP 52） | ファイルをピース単位でハッシュ化したピースハッシュ木 | ピースが届くたびに逐次検証でき、悪意あるピアからの汚染データを早期に排除できる |
| IPFS | コンテンツをチャンク分割したMerkle DAG、そのルートがCID | コンテンツアドレッシングと、同一データの重複排除 |
| Certificate Transparency（RFC 6962） | 発行された証明書の追記専用ログ | 証明書ログへの包含証明・改ざんのない一貫性証明を第三者が検証できる |
| Git | commit → tree → blobへと連なるハッシュ連鎖 | リポジトリ履歴全体の完全性を、単一のコミットハッシュで保証する |
こうしてMerkle木は、「固定されたデータ集合を後から検証する」用途では非常に強力です。しかし現実のシステムには、もう少し欲張った要求もあります。データをキーで引きたい（口座残高をアドレスから即座に引き出したい）、頻繁に更新したい（状態が絶えず変わる）、あるいは2つのレプリカがどこで食い違っているかを効率よく知りたい（分散データベースの同期）、こうした要求に応えるために、Merkle木の考え方を発展させた2つの構造が生まれました。次の節から見ていきましょう。
Merkle Patricia Trie:検証可能なkey-valueストア（Ethereum）
ブロックチェーンにおける「状態（state）」、すなわち各アカウントの残高やスマートコントラクトのストレージ内容は、静的なデータ集合ではなく絶えず更新され続けるkey-valueマップです。素朴なMerkle木のように、1件更新するたびに全データを並べ直して木を再構築するのは、状態が数千万件規模になるEthereumでは到底現実的ではありません。そこで採用されたのが、トライ（trie、基数木）とMerkle木を組み合わせたMerkle Patricia Trie（MPT）です。トライは本来「キーの文字列を辿って値にたどり着く」木構造で、更新されたキーの経路上のノードだけを再計算すればよく、しかもキーの並びから木の構造が決定的に定まるという利点があります。
MPTは、基数木に経路圧縮（Patricia）の工夫を加えた構造です。Ethereumの実装では、キー（アカウントアドレスやストレージスロット）を16進数1文字＝ニブル単位で1段ずつ辿っていく、最大16分岐のトライになっています。
- branchノード
- 子への分岐点。16進数の各値（0〜f）に対応する16個の子スロットと、そのノード自身が終端キーである場合の値スロットを合わせて持つ。
- extensionノード
- 分岐のない一本道が続く区間で、共有するキーのプレフィックスをまとめて1つのノードに圧縮する。これにより長い共通接頭辞を持つキー群でもノード数を抑えられる。
- leafノード
- 残りのキー経路と、そのキーに対応する値を格納する終端ノード。leafとextensionは、格納する経路が偶数長か奇数長かを区別するhex-prefixエンコーディングによって、branchノードと確実に区別できるようになっている。
Ethereumのブロックヘッダには、全アカウントの状態をまとめたworld state trieのルートであるstateRootに加え、そのブロックに含まれるトランザクション群のtrieルート（transactionsRoot）、実行結果のtrieルート（receiptsRoot）が刻まれます。さらに各コントラクトは、自分専用のストレージ内容を保持するstorage trieを個別に持ちます。ライトクライアントは、フルノードから「このアドレスの残高はいくらか」というMerkle証明を1つ受け取り、手元のstateRootと突き合わせるだけで、状態全体をダウンロードすることなく検証できます。なおキーはそのまま使わずkeccak256(アドレス)をキーとする「secure trie」にすることで、意図的に偏った長い経路を作り読み書きを遅延させるDoS攻撃を防いでいます。
- 実装上、各ノードはRLPエンコードされ、「ノードのハッシュ→ノードの中身」という単純なkey-valueデータベース（LevelDBやRocksDBなど）に格納される。そのため1回の値の読み書きが、trieの深さぶんの複数回のDBアクセスに増幅されてしまう「I/O増幅」が実運用上の課題になっている。
- アカウント数やストレージ利用の増加とともにtrieが肥大化し続ける「state bloat」問題は、Ethereumのノード運用コストを押し上げる要因として長年議論されている。
- 証明サイズと実装の単純さを大きく改善するVerkle tree（vector commitmentを使う木）や、構造をシンプルにするbinary trieへの移行が、statelessなEthereumノードを実現する文脈で検討されている。
Merkle Search Tree:挿入順に依存しない「収束する木」（2019）
P2Pのレプリカ同期（anti-entropy）では、2台のノードが持つデータ集合について「そもそも同じ内容か、違うならどこがどう違うか」を効率よく知りたいという要求が繰り返し現れます。理屈の上では、ルートハッシュを比較して一致すれば全体が一致、不一致ならルートの子同士を再帰的に比較していけば、O(log n)で食い違っている部分だけを特定できるはずです。ところが、B木や平衡二分探索木のような一般的な索引構造は挿入した順序によって木の形が変わるため、まったく同じキー集合を持つ2台のノードでも、更新履歴が異なれば違う形の木・違うルートハッシュになってしまい、この比較のロジックが成立しません。
この問題を解決するために、Alex AuvolatとFrançois Taïaniが2019年に提案したのがMerkle Search Tree（MST）です。MSTでは各キーの所属する「層（layer）」を、そのキーをハッシュ化した値の先頭に並ぶゼロの個数（基数Bで数える）から決定論的に導き出します。層が高いキーほど木の上位（ルートに近い側）に配置され、木の形はキー集合だけから一意に定まり、挿入順序は一切関係しません。全体の形はB木によく似ており、ハッシュの分布に従って確率的にバランスします。
- 一意性: 同じキー集合を持つ2台のノードは、更新の順序や経路によらず必ず同じ形の木・同じルートハッシュに収束する。
- 期待深さO(log n): ハッシュ値の分布から層が確率的に決まるため、平均的な木の深さは対数オーダーに保たれる。
- 差分同期: ルート同士を比較し、ハッシュが異なる部分木だけを再帰的に取得すればよいため、レプリカ間の差分検出と転送が効率的に行える。
- CRDTとの好相性: 状態ベースCRDT（Conflict-free Replicated Data Type）のマージや、ゴシッププロトコルによる更新の伝播と組み合わせやすく、常時オンラインとは限らないP2P環境での結果整合性のあるレプリケーションに向く。
MSTの代表的な採用例が、分散型SNSプロトコルであるBluesky（AT Protocol）のリポジトリ構造です。各ユーザーの投稿やプロフィールといったレコード群をMSTに格納し、そのルートハッシュを含むcommitにユーザーの鍵で署名します。これにより、特定のレコードが確かにそのユーザーのリポジトリに存在するという証明と、複数のリレー間でリポジトリの更新差分だけを効率よく同期する仕組みの両方を、同じ木構造で実現しています。
3つの構造の使い分け
| 観点 | Merkle Tree | Merkle Patricia Trie | Merkle Search Tree |
|---|---|---|---|
| データモデル | 静的なリスト・集合 | 更新され続けるkey-valueマップ | 順序付きの集合・マップ |
| 構造の決定性 | 構築方法（ペアの組み方）に依存する | キー集合から一意に定まる | キー集合から一意に定まる |
| 得意な操作 | 包含証明・データ全体の一括検証 | 個々の値の更新と証明発行を両立できる | レプリカ間の差分検出と同期 |
| 証明・同期コスト | 証明はO(log n)で軽量 | 経路長×ノードサイズでMerkle Treeよりやや大きくなりがち | 差分がある部分木だけを転送すればよい |
| 代表的な採用例 | Bitcoin（SPV）・Certificate Transparency・BitTorrent v2 | Ethereumの状態管理（stateRoot） | AT Protocol（Bluesky）のリポジトリ |
3つの構造は優劣ではなく、「何を検証したいか」で選ぶべき道具です。固定されたデータの包含だけを証明したいならMerkle Treeが最も軽量で実装も単純、頻繁に更新される状態を検証可能な形で持ち続けたいならMerkle Patricia Trie、複数のレプリカ間で「どこが違うか」を効率よく突き合わせたいならMerkle Search Treeが向いています。実際のシステムでは、この3つを組み合わせて使うことも珍しくありません。
よくある誤解と注意点
- 「ルートハッシュさえあればデータを復元できる」は誤解: Merkle木が保証するのは完全性（データが改ざんされていないこと）であって、可用性（データが実際に取得できること）ではない。ルートに対応する元データがどこにも保存されていなければ証明のしようがなく、この「データ可用性問題」はブロックチェーンのrollup設計において特に重要な論点になっている。
- 「Merkle証明があれば真正」も誤解: Merkle証明が保証するのは、あくまで「そのデータが、この特定のルートハッシュに対応する木に含まれている」ことだけである。ルートハッシュ自体が信頼できるかどうかは、分散合意や署名など別の仕組みで担保する必要がある。
- 「MPTはMerkle Treeの完全な上位互換」も誤解: MPTは更新可能性と引き換えに、証明サイズの増大や実装の複雑さというコストを払っている。データが更新されない静的な集合を扱うだけなら、素朴なMerkle Treeの方がシンプルで証明も軽い。
- これらすべての安全性は、使用するハッシュ関数の衝突耐性を前提にしている。かつて広く使われたSHA-1で実用的な衝突が発見された出来事は、GitやCertificate TransparencyのようなMerkle木ベースのシステムに、ハッシュアルゴリズムの選定と将来の移行計画の重要性を改めて突きつけた。
関連ページ
Merkle木の考え方は、このサイトで扱う他の技術とも随所でつながっています。コンテンツをハッシュで一意に指し示す発想はDHTのコンテンツアドレッシングに通じ、届いたピースをその場で検証する仕組みはBitTorrentのBEP 52ピース検証そのものです。MSTのようなレプリカ同期はゴシッププロトコルによるanti-entropyと組み合わさって初めて力を発揮し、ルートハッシュそのものの正当性は分散合意によって参加者間で保証されます。また、EthereumのstateRootの上で実際に値を読み書きするのがスマートコントラクトを実行するEVMであり、Merkle木を悪用・迂回しようとする試みへの備えは攻撃手法と対策でも取り上げています。