Merkle Tree(マークルツリー)は、多数のデータをそれぞれハッシュ関数に通し、その値を 2 つずつ組にしてハッシュし直す操作を繰り返して、最後に 1 つの値へまとめる木です。最後に残る 1 つをルートハッシュと呼びます。名前は、この木を使った署名方式を 1979 年に特許として出願し、1987 年の論文「A Digital Signature Based on a Conventional Encryption Function」で発表した Ralph Merkle に由来します。

横軸はログの件数、縦軸は送るデータのバイト数で、どちらも対数目盛り。葉のハッシュを全件並べた灰色の直線は件数に比例して伸び、35 億件で約 1,120 億バイトに達する。手元の木で測った包含証明と一貫性証明は 10 件から 100 万件まで数百バイトでほぼ横ばい。公開ログ Argon 2026h2 の 35.0 億件での包含証明 1,024 バイトが赤い点で、記録 1 件の大きさ 819 バイトの破線のすぐ上にある。Wyvern 2027h1 の 5.3 億件での一貫性証明 832 バイトが赤い四角で、破線とほぼ同じ高さにある

ログの件数と、証明に必要なデータの大きさ(手元の木と、公開の CT ログで測った値)

図の赤い点は、TLS で使う証明書の発行を記録する公開ログ Argon 2026h2 から、1 件の記録と証明を取り寄せて手元で検証した結果です。このログには 35 億件の記録があり、葉のハッシュを全件並べると 112 GB になります。位置 3,000,000,000 の記録が入っていることは、32 個のハッシュ、1,024 バイトで示せました。記録そのもの(819 バイト)より少し大きい程度です。

1 件が入っていることを示すために渡すハッシュの並びが、包含証明(inclusion proof)です。緑の線と赤い四角は、過去の記録を書き換えていないことを示す一貫性証明(consistency proof)で、後の節で扱います。


Merkle Tree には、使っていると知らずに出会うことが多いです。Bitcoin のブロックヘッダにある merkle root、Ethereum の state root、Rollup の出金で提出する Merkle proof は、どれもこの木のルートか、ルートに対する証明です。HTTPS の証明書も、発行するとその記録が上記のようなログに入ります。


本記事では、Certificate Transparency の公開ログと手元の実験から、次の疑問を順に扱います。

  • ルートハッシュは、何を表す値なのか。
  • 35 億件に 1 件が入っていることは、なぜ 32 個のハッシュで示せるのか。
  • 過去の記録を書き換えていないことは、どう示すのか。
  • 1 ビットの誤りで、なぜ証明書のログが使えなくなったのか。
  • ハッシュの一覧や 1 件ずつの署名と比べて、何が違うのか。
  • この木で確認できないことは何か。

ルートハッシュと 1 ビットの変化

木の一番下に並ぶデータのハッシュを葉、2 つの子のハッシュを連結してハッシュした値を内部ノードと呼びます。本記事の実験では、証明書を記録するログの仕様 RFC 9162(Certificate Transparency Version 2.0)の規則で木を作ります。葉は SHA-256(0x00 || データ)、内部ノードは SHA-256(0x01 || 左 || 右) です。|| はバイト列の連結を表します。

葉の数が 2 の累乗でない時は、左側に「件数未満で最大となる 2 の累乗」個の葉を置き、残りを右側に置きます。7 件なら左に 4 件、右に 3 件です。先頭の 1 バイトで葉と内部ノードを区別する理由と、奇数個の葉を複製する Bitcoin と違う点は Merkle Tree Design で扱います。

import hashlib


def h(b: bytes) -> bytes:
    return hashlib.sha256(b).digest()


def leaf_hash(data: bytes) -> bytes:
    return h(b"\x00" + data)


def node_hash(left: bytes, right: bytes) -> bytes:
    return h(b"\x01" + left + right)


def split(n: int) -> int:
    """n 未満で最大の 2 の累乗。"""
    k = 1
    while k * 2 < n:
        k *= 2
    return k


def root(leaves: list[bytes]) -> bytes:
    """葉のハッシュの並びからルートハッシュを計算する。"""
    n = len(leaves)
    if n == 0:
        return h(b"")
    if n == 1:
        return leaves[0]
    k = split(n)
    return node_hash(root(leaves[:k]), root(leaves[k:]))

ルートハッシュは、全ての葉から計算した値です。どれか 1 件の記録が 1 ビットでも変わると、その葉のハッシュが変わり、親、その親と順に変わって、ルートハッシュも変わります。

記録 0 から 6 の 7 件の木。記録 2 を 1 ビット変えると、葉 2、内部ノード 2–3、0–3、ルート 0–6 の 4 個が赤で値が変わる。その経路の兄弟にあたる葉 3、内部ノード 0–1、4–6 の 3 個が黄土色で包含証明に入る。残りの葉 0・1・4・5・6 と内部ノード 4–5 は灰色で、値は変わらず送らない

7 件の木で記録 2 を変えた時に変わるハッシュと、包含証明に入るハッシュ

変わるのは、変えた葉からルートまでの経路にあるハッシュだけです。その数は、葉とルートを含めて、7 件の木で記録 2 を変えるなら 4 個、100 万件の木でも多くて 21 個です。証明に入る兄弟は、これより 1 個少なくなります。一方で、ルートハッシュそのものは別の値に大きく変わります。後で Yeti 2022 の再現に使う 11,000 件の木で葉を 1 ビット反転させて測ると、正しいルートとの差は 256 ビットのうち 123 ビットでした。1 ビットの違いが出力全体に広がるのは、SHA-256 が入力を何度もかき混ぜて出力を作るからです。

ルートハッシュが表すのは、「この件数の、この並びのデータ」です。1 件を足しても、2 件の順番を入れ替えても、別の値になります。そのため、記録を 1 件足したり変えたりするたびに経路を計算し直し、新しいルートを配り直す必要があります。


包含証明

ルートハッシュだけを持っている人に、ある記録が木に入っていることを示すには、記録のハッシュから始めてルートまで計算し直せれば十分です。そのために必要なのは、上の図で黄土色にした経路の兄弟だけです。兄弟のハッシュを葉に近い順に並べたものが、冒頭で触れた包含証明です。

検証する側は、記録から葉のハッシュを計算し、兄弟と順に連結してハッシュし、最後に得た値がルートハッシュと一致するかを見ます。兄弟を左に置くか右に置くかは、記録の位置(何番目か)と木の件数から決まります。上の図で記録 2 を検証するなら、葉 3 を右、内部ノード 0–1 を左、4–6 を右に置いて連結します。コードでは fn が記録の位置、sn が末尾にある記録の位置を持ち、1 段上がるたびに 2 で割って、その偶奇で向きを決めます。以下は、RFC 9162 の 2.1.3.2 節の手順をそのまま書いた検証です。

def verify_inclusion(index, size, leaf, proof, expected_root) -> bool:
    """RFC 9162 2.1.3.2 の手順。"""
    if index >= size:
        return False
    fn, sn, r = index, size - 1, leaf
    for p in proof:
        if sn == 0:
            return False
        if fn & 1 or fn == sn:
            r = node_hash(p, r)      # 兄弟が左
            while not fn & 1 and fn != 0:   # 右端で兄弟の無い段を飛ばす
                fn >>= 1
                sn >>= 1
        else:
            r = node_hash(r, p)      # 兄弟が右
        fn >>= 1
        sn >>= 1
    return sn == 0 and r == expected_root

木の段数は、件数を 2 で割り続けて 1 になるまでの回数で、件数が 2 倍になるごとに 1 段増えます。証明に入るハッシュの個数は、葉からルートまでの段数と同じです。手元で件数を 10 倍ずつ増やして木を作り、件数の 60% の位置にある記録の証明を数えました。先頭や末尾のような端ではない位置の例として選びました。

件数包含証明葉のハッシュを全件手元での検証
1,00010 個(320 バイト)32,000 バイト15 µs
100,00017 個(544 バイト)3,200,000 バイト22 µs
1,000,00020 個(640 バイト)32,000,000 バイト43 µs

件数が 1,000 倍になっても、証明は 10 個増えただけでした。件数を n とすると、証明の個数は多くても ceil(log2 n) 個で、件数が 2 の累乗でない RFC 9162 の木では、浅い位置にある葉の証明はこれより短くなります。各段で末尾の値を複製して組む Bitcoin の規則では、どの葉の証明もちょうど ceil(log2 n) 個です。

検証は数十マイクロ秒で終わります。一方で、ルートを作る側は全ての葉をハッシュする必要があり、100 万件で 1.1 秒かかりました。計測の全体は proof_size.py にあり、Python の標準ライブラリ hashlib が計算する SHA-256(FIPS 180-4)だけを使います。

偽の記録で検証を通すには、同じルートに辿り着く別の入力を見つける必要があり、SHA-256 では現実的にできません。

証明を作る側も、全ての記録を持ち続ける必要はありません。古い記録を消しても、その部分木のハッシュを残しておけば、残った記録について証明を作れます。Bitcoin のホワイトペーパーは、この性質で古いトランザクションを消して保存量を減らす方法と、Proof of Work を自分で検証したブロックヘッダだけを持つ利用者が、そのヘッダのルートと包含証明で支払いを確認する方法を示しています。


公開ログでの検証

次に、実際に運用されているログで同じ検証を行います。Certificate Transparency(CT)は、認証局が発行した証明書を誰でも読める追記だけのログに残す仕組みです。Chrome などのブラウザは、公開の証明書にこのログへの登録を求めています。ログは全ての記録を Merkle Tree の葉にし、その時点の件数とルートハッシュに署名して公開します。この署名した値を STH(Signed Tree Head)と呼びます。

ログの API は RFC 6962 で決まっています。木の作り方は RFC 9162 と同じなので、上記の検証をそのまま使えます。2026 年 11 月 13 日に、Argon 2026h2 の STH、位置 3,000,000,000 の記録、その包含証明を 1 回ずつ取得してファイルに保存しました。検証はその保存したファイルだけで行います。

import base64, json
from merkle import leaf_hash, verify_inclusion

load = lambda name: json.load(open(f"ct/{name}.json"))
b64 = base64.b64decode

sth = load("sth1")                       # get-sth の応答
size, signed_root = sth["tree_size"], b64(sth["sha256_root_hash"])
entry, proof = load("entry"), load("inclusion")   # get-entries の 1 件に位置を足したもの、get-proof-by-hash の応答
data = b64(entry["leaf_input"])
path = [b64(p) for p in proof["audit_path"]]

print(verify_inclusion(entry["index"], size, leaf_hash(data), path, signed_root))

bad = bytearray(data)
bad[len(bad) // 2] ^= 0x01               # 記録の 1 ビットを反転する
print(verify_inclusion(entry["index"], size, leaf_hash(bytes(bad)), path, signed_root))
print(verify_inclusion(entry["index"] + 1, size, leaf_hash(data), path, signed_root))

以下は、ct_verify.py が出力した行からの抜粋です。

ログの件数        : 3,501,950,757
記録の位置        : 3,000,000,000
記録の大きさ      : 819 バイト
包含証明          : 32 個 = 1,024 バイト
葉のハッシュを全件: 112.1 GB
検証              : True
1 ビット反転       : False
位置を 1 つずらす  : False

35 億件は 2 の 31 乗と 32 乗の間なので、木は 32 段で、証明も 32 個です。記録を 1 ビット変えると検証は失敗します。1 つ隣の位置にある記録の証明として同じ証明を出しても、失敗します。この規則では兄弟を置く向きが位置から決まるので、証明は「この記録がこの位置にある」ことまで示します。

ただし、この検証が意味を持つのは、比べたルートハッシュがログの署名した値だと信じられる時だけです。今回はログに直接問い合わせた STH を使い、STH の署名は検証していません。ルートが正しいことは、Merkle Tree の外にある署名で守る必要があります。


一貫性証明

包含証明で分かるのは、ある時点のルートにその記録が入っていることだけです。ログを運用する側が、ある日の STH を公開した後に過去の記録を消したり書き換えたりして、新しいルートで STH を出し直しても、包含証明だけでは気付けません。

そこで CT のログは、前の STH が表す木が、後の STH が表す木の先頭にそのまま入っていることも証明します。これが、冒頭の図で触れた一貫性証明です。以下は、6 件の時点と 8 件の時点で出した STH を結ぶ一貫性証明です。

左は 6 件の木で、ルート 0–5 の下に部分木 0–3 と 4–5 がある。右は 8 件の木で、ルート 0–7 の下に部分木 0–3 と 4–7、その下に 4–5 と 6–7 がある。部分木 0–3 と 4–5 は左右とも緑で前の木と同じ、6–7 は青で後から足した部分。この 3 個が黄土色の破線で囲まれ、一貫性証明に入る

6 件と 8 件で出した STH の間で、一貫性証明に入る 3 個のハッシュ

ログは記録を後ろに足すだけなので、前の木にあった部分木(緑)は、後の木でも同じ値で残ります。証明を受け取った側は、緑の 2 個から前のルートを計算し、緑の 2 個と青の 1 個から後のルートを計算します。両方が 2 つの STH と一致すれば、前の木は後の木で先頭にそのまま残っています。前の 6 件のどれか 1 件でも書き換わっていれば、前のルートと一致しません。

証明の大きさは、包含証明と同じく件数の対数に比例します。表紙の図にある緑の線が、手元の木で測った一貫性証明です。公開ログでも検証しました。Argon 2026h2 は 2026 年下半期に期限が切れる証明書のログで、取得した時点で件数が増えていませんでした。11 月に発行される証明書の多くは期限が 2027 年以降になり、後のログに入るためと考えていますが、2 時間で 1 件も増えない理由までは調べていません。そこで、数秒ごとに件数が増えていた DigiCert の Wyvern 2027h1 から 10 分の間をおいて 2 つの STH を取り、その間の一貫性証明を検証しました。

Wyvern 2027h1     : 526,564,726 件 → 526,677,946 件(10 分後、113,220 件増加)
一貫性証明        : 26 個 = 832 バイト
検証              : True
前のルートを 1 ビット反転: False

10 分で 11 万件増えたログについて、26 個のハッシュで、それより前の 5 億 2,656 万件が 1 件も書き換わっていないことを確認できました。検証の手順は包含証明より少し長いので、merkle.py の verify_consistency に RFC 9162 の 2.1.4.2 節のまま書いています。


Yeti 2022 の 1 ビット

一貫性証明は、ログが過去を書き換えていないことを示します。裏返すと、ログは一度署名した STH と矛盾する木を後から出せません。この性質で、実際に 1 つのログが運用を止めました。

2021 年 6 月 30 日、DigiCert が運用していた CT ログ Yeti 2022 について、記録を全件取り直してルートを計算しても、ログが署名した STH と一致しないという報告が、Chromium が CT の方針を話し合うメーリングリスト ct-policy に出ました。経緯は次の通りです。

  1. 6 月 29 日に STH へ署名した後、65,562,066 番の葉が 1 ビット違う値で木に入った。
  2. ログはその値で次の STH に署名し、前の STH との一貫性証明は通った。
  3. 記録から計算した葉は木に無く、その包含証明は「見つからない」になった。
  4. 7 月 3 日にログは読み取り専用になり、新しい記録を受け付けなくなった。
  5. Chrome は回復できないと判断し、7 月 21 日にログを Retired にした。

Retired は、Chrome がそのログを新しい記録の登録先として認めなくなる状態です。

報告したのは、CT の監視ツール Cert Spotter を作っている Andrew Ayer です。正しい葉のハッシュで、先頭 1 バイトの最下位ビットを反転させると、木に入っている値になりました。Ayer は、原因はハードウェアの誤りや宇宙線の可能性が高いと解説しています。7 件の小さなログでこの順を追うと、次のようになります。

7 件の小さなログで Yeti 2022 の順を追う動く図。1 コマ目で 4 件の STH 1 に署名する。記録 4・5 を足した後、保存した記録 5 の葉のハッシュが 1 ビット反転し、記録 5 からルートまでのノードが赤くなる。記録 6 を足して反転したまま STH 2 に署名する。STH 1 から STH 2 への一貫性証明は通るが、監視する側が全件からルートを作ると R2 と合わない。ハッシュを正しく戻すと、同じ 7 件に R2 と R2′ の 2 つのルートが並ぶ。最後のコマで、残る手は読み取り専用にすることだと示す

説明用に 7 件だけ入れたログで、Yeti 2022 で起きた順を追う(1 コマ 1.6 秒で表示)


手元での再現

記録と葉のハッシュを別々に保存する小さなログで、同じことを再現しました。10,000 件で STH 1 に署名した後、記録 10,500 の葉で、ハッシュの先頭 1 バイトの最下位ビットを反転し、11,000 件で STH 2 に署名します。ハッシュの中で反転させるビットは Yeti 2022 と同じです。

from merkle import (leaf_hash, root, inclusion_proof, verify_inclusion,
                    consistency_proof, verify_consistency)

entries = [f"certificate #{i}".encode() for i in range(11_500)]
stored = [leaf_hash(e) for e in entries[:10_000]]   # ログが保存した葉のハッシュ
sth1 = (10_000, root(stored))                         # 反転の前に署名した STH

stored += [leaf_hash(e) for e in entries[10_000:11_000]]
FLIP = 10_500
b = bytearray(stored[FLIP])
b[0] ^= 0x01                                          # 保存した葉のハッシュが 1 ビット反転
stored[FLIP] = bytes(b)
sth2 = (11_000, root(stored))                         # 反転に気付かず署名した STH

mine = [leaf_hash(e) for e in entries[:11_000]]       # 監視する側が記録から作り直した葉
fixed = mine + [leaf_hash(e) for e in entries[11_000:]]
sth3 = (11_500, root(fixed))                          # 葉を正しく戻して続きを足した木

この後で、一貫性証明・ルートの作り直し・包含証明を順に調べます。コードの全体は yeti_repro.py にあり、出力は次の通りです。

1. 一貫性証明 sth1→sth2       : True
2. 記録から作り直したルート   : 不一致
   先頭 10,000 件のルート     : 一致
3. 記録 10,500 の葉を探す     : 見つからない
   記録 10,499 の包含証明     : True
4. 件数 10,001〜11,000 のルート: 500 通りが不一致(10,501 件以上の全て)
   ルートの違い               : 256 ビットのうち 123 ビット
5. 直した木への一貫性証明 sth2→sth3: False
   直した木への一貫性証明 sth1→sth3: True

1 と 3 の 2 行目から、ログの API だけを見ている人は異常に気付けません。反転より前の部分は変わっていないので一貫性証明は通り、反転した記録以外の包含証明も通ります。気付けるのは、2 のように全件を取り直してルートを作る監視する側(monitor)だけです。

4 は、10,501 件以上のどの件数のルートも、記録から作ると一致しないことを示しています。5 が直せない理由です。葉を正しく戻した木は STH 1 とは一貫しますが、すでに署名して配った STH 2 とは一貫しません。

直した木で STH を出せば、同じログが矛盾する 2 つの歴史に署名したことになり、CT では利用者ごとに違うログを見せた証拠として扱われます。STH 2 に合わせるには、反転したハッシュになる記録を探す必要があります。これはハッシュ値から入力を逆算することで、SHA-256 では現実的にできません。

DB(データベース)なら、壊れた 1 バイトを直して終わる障害です。Merkle Tree のログでは、どんな書き換えも見つかる性質が、自分の誤りも直せない性質になります。それでも証明書が使えなくなるわけではありません。ブラウザは 1 つの証明書を複数のログに登録するよう求めており、Ayer も 1 つのログが止まっても証明書は使い続けられると説明しています。


ハッシュの一覧・署名との比較

Merkle Tree を使わなくても、データが書き換わっていないことは確認できます。他の方法と比べると、Merkle Tree が得意な所と、他の方法で足りる所が分かれます。表の「無いことの証明」は、ある記録が含まれていないことを示す証明です。表の最後にあるキーで位置が決まる木は、キーのビット列で葉の位置を決める木です。

方法1 件を示すのに送るもの過去を変えていないことの証明無いことの証明
全件をそのまま渡す全件全件を比べる全件を見ればできる
全件を連結した 1 つのハッシュ他の全件全件を比べる全件を見ればできる
1 件ずつ署名する署名 1 つできないできない
ハッシュチェーンその後に足した全件その後に足した全件できない
Merkle Tree段数と同じ個数のハッシュ一貫性証明できない
キーで位置が決まる木段数と同じ個数のハッシュ仕組みによる空の位置を示せる

1 件ずつデジタル署名を付ける方法は、証明が最も小さいです。ただし、署名する側が何件に署名したかは外から分かりません。同じ記録の集まりについて、利用者ごとに違う一覧を見せても気付けません。Merkle Tree のルートに署名すれば、1 つの署名で「この件数の、この並び」を固定できます。

ハッシュチェーンは、ブロックチェーンの基本にあるように、直前の値を含めて次の値を作る形です。追記には向きますが、古い 1 件を示すには、その後ろの全てを渡す必要があります。

Ethereum の Merkle Patricia Trie は、キーで位置が決まる木の 1 つで、アカウントの状態を管理しています。あるキーの位置が空であることを示せるので、「このアカウントに残高が無い」ことまで証明できます。


データが手元に全てあり、比べる相手も全件を持っているなら、Merkle Tree は必要ありません。葉が数件しかない時も、証明は全件を渡すのとほとんど変わりません。

どこが違うかを絞り込む用途では、Amazon Dynamo のように、複製どうしでルートを比べ、違う部分木だけを辿っていく使い方もあります。Dynamo がデータを分ける Consistent Hashing と、複製の食い違いを直すこの使い方を組み合わせる流れは、Consistent Hashing のノートで扱います。


この木で確認できないこと

Merkle Tree の証明が示すのは、「このルートの木に、この位置で、この記録が入っている」ことだけです。それ以外のことは、木の外で決める必要があります。

1 つ目は、記録が無いことです。CT で、自分のドメインに知らない証明書が発行されていないかを調べたくても、包含証明では「無い」ことを確認できません。そのため、RFC 6962 は、監視する側が少なくとも全ての新しい記録を調べる必要があるとしています。葉の並べ方を工夫して不在を示す方法は、Merkle Tree Design で比べています。

2 つ目は、比べるルートが正しいことです。証明はルートとの一致しか見ないので、偽のルートを受け入れる実装では、どんな証明も通ります。Nomad の bridge では、2022 年 4 月の初期化で 0x00 を確認済みのルートとして登録してしまい、証明されていないメッセージまで処理されました。Tornado Cash でも、ルートを計算する回路の誤りで、偽のルートを作れる状態が見つかりました。

3 つ目は、木の作り方です。葉と内部ノードを同じ計算でハッシュすると、64 バイトの記録を内部ノードとして読ませる攻撃が成り立ちます。奇数の葉を複製する規則では、件数の違う 2 つの並びが同じルートになります。どちらも Bitcoin で実際に報告され、Bitcoin Merkle Tree の弱点で扱っています。本記事の実験で使った RFC 9162 の規則は、先頭の 1 バイトと、複製しない分け方で、この 2 つを避けています。


Merkle root に出会った時

ブロックヘッダ、Rollup の出金、証明書のログで Merkle Tree に出会ったら、証明の検証を書く前に次の順で調べると、仕組みの外にある前提が見えます。

  1. ルートを誰が作り、どこから受け取るか。署名や合意で守られているか。
  2. 葉と内部ノードをどう区別し、奇数の葉をどう扱うか。
  3. 証明が位置を含むか、要素が入っていることだけを示すか。
  4. 無いことや、過去を書き換えていないことを示す必要があるか。

表紙の図にある 1,024 バイトは、35 億件から 1 件を示すには十分な大きさです。ただし、その証明が意味を持つのは、1 の答え、つまり比べたルートを信じられる時だけです。Yeti 2022 は、そのルートに一度署名すると、自分の 1 ビットの誤りも取り消せないことを示しました。