マークルツリー入門 - Git・証明書の透明性・データ同期を支えるハッシュの木
ハッシュ関数と署名の基礎を押さえる定番。
レプリカ同期など分散データの全体像に。
木構造や計算量の考え方を基礎から。
当サイトは Amazon.co.jp を宣伝しリンクすることで紹介料を得る手段を提供する、Amazonアソシエイト・プログラムの参加者です。価格・在庫はリンク先の最新情報をご確認ください。
大きなデータが改ざんされていないかを確かめたいとき、まず思いつくのはデータ全体のハッシュ値を1つ計算して比べる方法です。これで「どこかが違う」ことは分かります。しかし、どこが違うのかは分かりませんし、「この1件が確かに含まれている」と示すにはデータ全体を渡す必要があります。
マークルツリー（ハッシュ木）は、ハッシュを木の形に積み上げることでこの2つを解決します。Git のオブジェクト、HTTPS 証明書の透明性ログ、分散データベースのレプリカ同期、Bitcoin のブロックなど、身近なところで使われている仕組みです。
ハッシュを木にするという発想
マークルツリーの名前は、Ralph Merkle にちなみます。Merkle は1979年9月5日にデジタル署名の方式として特許を出願し、1982年1月5日に米国特許 4,309,569 として登録されました。ハッシュを木の形にまとめる考え方は、もともと署名の仕組みの一部として生まれたものです。
作り方は単純です。
- データを1件ずつに分け、それぞれのハッシュを取る。これが葉になる
- 隣り合う2つのハッシュをつなげて、さらにハッシュを取る。これが1つ上のノードになる
- これを1つになるまで繰り返す。最後に残ったのが根（マークルルート）
根 = H(N01 + N23)
/ \
N01 = H(L0 + L1) N23 = H(L2 + L3)
/ \ / \
L0 = H(d0) L1 = H(d1) L2 = H(d2) L3 = H(d3)ハッシュ関数は入力が1ビットでも違えば出力がまったく変わるので、どの葉が変わっても、そこから根までの経路のハッシュがすべて変わります。つまり根のハッシュ1つが、全データの指紋になります。
実装してみる
証明書の透明性ログの仕様である RFC 9162 は、マークルツリーのハッシュ（Merkle Tree Hash）を次のように定義しています。
MTH({}) = HASH()
MTH({d[0]}) = HASH(0x00 || d[0])
MTH(D_n) = HASH(0x01 || MTH(D[0:k]) || MTH(D[k:n]))
k は n より小さい最大の2のべき乗|| は連結です。葉には先頭に 0x00、内部ノードには 0x01 を付けてからハッシュを取ります。この1バイトの意味は後で説明します。TypeScript（Node.js）で書くと次のようになります。
import { createHash } from 'node:crypto'
const sha256 = (...parts: Buffer[]) =>
createHash('sha256').update(Buffer.concat(parts)).digest()
// n より小さい最大の2のべき乗
const splitPoint = (n: number) => {
let k = 1
while (k * 2 < n) k *= 2
return k
}
export function merkleRoot(items: string[]): Buffer {
if (items.length === 0) return sha256()
if (items.length === 1) {
return sha256(Buffer.from([0x00]), Buffer.from(items[0]))
}
const k = splitPoint(items.length)
return sha256(
Buffer.from([0x01]),
merkleRoot(items.slice(0, k)),
merkleRoot(items.slice(k)),
)
}
console.log(merkleRoot(['tx-alice', 'tx-bob', 'tx-carol', 'tx-dave', 'tx-erin']).toString('hex'))同じ計算をブラウザで動かせるようにしたのが次のデモです。Web Crypto API の SHA-256 で、RFC 9162 と同じ方式で計算しています。データの1行を書き換えると、根のハッシュと、変えた葉から根までの経路がすべて変わることを確かめられます。
包含証明: log2(n) 個のハッシュで「含まれている」を示す
マークルツリーの一番の効用は、ある1件が木に含まれていることを、全データを渡さずに証明できる点です。これを包含証明（inclusion proof、監査パスとも）と呼びます。
葉 d2 が含まれていることを示したいとします。検証する側が根のハッシュを信頼できる形で持っていれば、証明する側は次の兄弟ノードのハッシュだけを渡せば足ります。
根
/ \
N01 N23
(渡す) / \
L2 L3
(自分) (渡す)検証する側は d2 から L2 を計算し、受け取った L3 と組み合わせて N23 を作り、さらに N01 と組み合わせて根を計算します。計算した根が手元の根と一致すれば、d2 は確かにその木に含まれています。
必要なハッシュの数は木の高さ、つまりおよそ log2(n) 個です。葉が100万件でも20個前後のハッシュで済みます。上のデモでは、5件のデータで葉 2 を選ぶと3個、葉 4 を選ぶと1個のハッシュで証明が組み立てられます。葉の数が2のべき乗でない場合、RFC 9162 の分け方では木の形が左右で偏るため、葉によって証明の長さが変わります。
RFC 9162 にはもう1種類、一貫性証明（consistency proof）も定義されています。木の古い版が新しい版の先頭部分にそのまま含まれていること、つまり過去のデータを書き換えずに追記だけしてきたことを示す証明です。
0x00 と 0x01 を付ける理由
先ほどの定義で、葉と内部ノードに別々の1バイトを前置していました。RFC 9162 はこの理由を、葉と内部ノードのハッシュ計算を分けるドメイン分離が、第2原像攻撃への耐性に必要だからだと説明しています。
前置しない素朴な実装では、内部ノードの計算 H(L0 + L1) と、L0 + L1 というバイト列をデータとして持つ葉の計算が区別できません。すると、攻撃者は2つのハッシュをつなげた64バイトを「1件のデータ」として差し出し、元とは違う中身の木で同じ根を作れてしまいます。葉には 0x00、内部ノードには 0x01 を付けておけば、両者が同じ入力になることはありません。
奇数個のときの扱いと CVE-2012-2459
葉の数が奇数のとき、どう組むかは実装によって違います。Bitcoin は、ある段のハッシュの数が奇数なら最後の1つを複製してペアにします。
Bitcoin Core のソースコード（src/consensus/merkle.cpp）には、この方式に深刻な欠陥があることを警告するコメントが残っています。最後を複製するため、取引の並び [1,2,3,4,5,6] と、末尾の2件を重複させた [1,2,3,4,5,6,5,6] が同じマークルルートになってしまいます。これを悪用すると、正しいブロックと同じハッシュを持つ不正なブロックを送りつけ、受け取ったノードがそのブロックを恒久的に無効と記録してしまう問題（CVE-2012-2459）が起きました。Bitcoin Core は、末尾で同一のハッシュ同士を組み合わせるケースを検出することで防いでいます。
RFC 9162 の方式は複製をせず、「n より小さい最大の2のべき乗」で左右に分けます。葉の数から木の形が一意に決まるので、この種の曖昧さが生じません。これから新しくマークルツリーを設計するなら、RFC 9162 のように複製しない方式とドメイン分離を採るのが無難です。
どこで使われているか
Git
Git は、中身のハッシュを名前にしてオブジェクトを保存する、内容アドレス型のファイルシステムです。ファイルの中身は blob、ディレクトリは tree というオブジェクトになり、tree の各エントリは中の blob や下位の tree のハッシュを持ちます。コミットは最上位の tree のハッシュを持ちます。
つまりコミットのハッシュは、そのときのリポジトリ全体の内容から決まる根のハッシュの役割を果たします。どこか1ファイルが変われば、そこから上の tree とコミットのハッシュがすべて変わります。一般的な2分木ではありませんが、ハッシュで子を指す構造という意味でマークルツリーの考え方そのものです。仕組みの詳細は Git の内部構造で書きました。
Certificate Transparency
HTTPS の証明書が誤って発行されたり、不正に発行されたりしていないかを誰でも監視できるようにするのが Certificate Transparency（CT）です。認証局が発行した証明書は公開ログに追記され、そのログが RFC 9162 で定義されたマークルツリーになっています。
ブラウザや監視者は、包含証明で「この証明書がログに載っている」ことを確かめ、一貫性証明で「ログが過去の記録を書き換えずに追記だけしている」ことを確かめます。ログ全体をダウンロードせずに、両方を少ないハッシュで検証できます。証明書そのものの役割は TLS 1.3 のハンドシェイクの記事も参考にしてください。
分散データベースのレプリカ同期
Amazon の Dynamo 論文（2007年）は、レプリカ間で食い違ったデータを見つけて揃える処理（anti-entropy）に、転送量を抑える目的でマークルツリーを使うと説明しています。各ノードがキーの範囲ごとにマークルツリーを持ち、まず根を比べます。一致すればその範囲は同じなので何も送りません。違えば子を比べ、違う枝だけをたどっていけば、食い違ったキーだけを特定できます。
Apache Cassandra の repair も同じ考え方で、レプリカごとにマークルツリーを作って比較し、差分のあるデータだけを修復します。Dynamo 系の設計の全体像は コンシステントハッシュの記事とあわせて読むと分かりやすいと思います。
Bitcoin
Bitcoin のブロックヘッダーには、そのブロックに含まれる全取引のマークルルートが入っています。軽量なクライアントは、ブロックの全取引を持たなくても、ヘッダーと包含証明だけで「自分の取引がこのブロックに入っている」ことを確かめられます。
使うときの注意
- 根を信頼できる経路で手に入れることが前提です。包含証明は「この根の木に含まれている」ことしか示しません。根そのものを攻撃者から受け取ってしまえば意味がありません。CT ではログが根に署名し、Git ではコミットのハッシュや署名を手がかりにします
- 葉の順序が結果に影響します。同じデータでも並びが違えば根は変わります。集合として扱いたいなら、ソートしてから木を作るなどの取り決めが必要です
- ハッシュ関数の強さに依存します。衝突が見つかったハッシュ関数を使うと、証明の意味が崩れます。Git が Git 3.0 で新規リポジトリの既定を SHA-256 にする予定なのもこのためです
- マークルツリーは改ざんを検出する仕組みで、データを隠す仕組みではありません。中身の秘匿が必要なら暗号化を別に考えます
まとめ
- マークルツリーは、データのハッシュを2つずつまとめて木にし、根のハッシュ1つで全体を表す
- 包含証明により、1件が含まれていることを log2(n) 個程度のハッシュで示せる
- 葉と内部ノードを
0x00/0x01で区別するドメイン分離と、奇数個のときに複製しない分け方が、安全な実装の要点 - Git、Certificate Transparency、Dynamo や Cassandra のレプリカ同期、Bitcoin など、改ざん検出と差分の特定が必要な場所で広く使われている
確率的に「含まれていないこと」を高速に判定したい場合は、別のデータ構造である Bloom フィルタが向いています。目的に応じて使い分けてください。
