Merkle Treeとは何か：大量の取引を効率よく検証する仕組み

概要

大量のレシートを1つの箱にまとめて保管している場面を想像してみてください。

あとから「このレシートは本当にこの箱に入っていたものですか？」と確認したくなったとします。
箱の中身が10枚くらいなら、全部を取り出して1枚ずつ確認しても大した手間ではありません。

しかし、これが1万枚、100万枚になったらどうでしょうか。

毎回すべてのレシートを取り出して確認するのは大変です。
できれば、確認したい1枚と、必要最小限の手がかりだけを使って、
「このレシートは確かに全体の中に含まれている」と確認したくなります。

ブロックチェーンでも、これに近い問題が出てきます。

たとえばBitcoinのブロックには、複数の取引が含まれます。
その中で「ある取引が本当にこのブロックに含まれているのか」を確認したい場面があります。

もちろん、すべての取引データを毎回確認できれば分かりやすいです。
しかし、軽量なクライアントや限られた環境では、毎回すべてのデータを持つのが重くなる場合があります。

そこで役立つ考え方が、Merkle Tree です。

Merkle Treeは、ざっくり言えば、大量のデータをハッシュで木の形にまとめ、最後に1つの要約値へ集約する仕組みです。
この最後の要約値を Merkle root と呼びます。

ここでいうハッシュは、データから作る「短い指紋」のようなものです。
同じデータからは同じハッシュが作られますが、データが少しでも変わると、結果のハッシュも大きく変わって見えます。

Merkle Treeでは、まず各データをハッシュにします。
次に、隣り合うハッシュを組み合わせて、さらにハッシュにします。
これを繰り返していくと、最後に1つのハッシュ、つまりMerkle rootが残ります。

この仕組みの便利なところは、すべてのデータを見直さなくても、確認したいデータと、その周辺にある少数のハッシュを使って、Merkle rootまでたどれることです。
このとき使う証明用のハッシュ列を、Merkle proof や Merkle branch と呼ぶことがあります。

Bitcoin Developer Guideでは、取引IDからMerkle Treeを構築し、最終的に1つのMerkle rootを得る流れが説明されています。
また、SPV、つまりSimplified Payment Verificationの文脈では、ブロックヘッダにあるMerkle rootと、中間ハッシュのリストを使って、ある取引がブロックに含まれていることを確認できると説明されています。

参考: Bitcoin Developer Guide: Block Chain

ただし、Merkle Treeは「何でも完全に安全にする魔法」ではありません。

Merkle proofで確認できるのは、基本的には あるrootに対して、そのデータが含まれていること です。
そのroot自体をどこから取得したのか、rootを含むブロックヘッダやチェーンをどう信頼するのか、ハッシュ関数や実装ルールが適切か、といった点は別に考える必要があります。

また、EthereumではBitcoinと同じ単純なMerkle Treeだけを使っているわけではありません。
Ethereum公式ドキュメントでは、実行レイヤーのMerkle trieは Merkle Patricia Trie であり、ブロックヘッダには stateRoot、transactionsRoot、receiptsRoot の3つのrootが含まれると説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie

この記事では、Merkle Treeをいきなり数式や仕様から説明するのではなく、まずは「大量の記録から必要な1件をどう確認するか」という身近な問題から整理します。

そのうえで、Merkle root、Merkle proof、Bitcoinでの使われ方、Ethereumでの違い、ブロックチェーン以外での応用、そして情報セキュリティ上の注意点を順番に見ていきます。

💡 豆知識
Merkle Treeは、Bitcoin専用の仕組みではありません。
Certificate Transparencyのような証明書ログ監査の仕組みでも、Merkle Treeに近い考え方が使われています。
RFC 6962では、Merkle audit pathを、ある葉からMerkle Tree Hashを計算するために必要な追加ノードの最短リストとして説明しています。

参考: RFC 6962: Certificate Transparency

この記事の立ち位置

本記事は、以前作成した 「身近な記録から理解するブロックチェーンの全体像」 の派生記事です。

派生元の記事では、ブロックチェーンを「複数の参加者が同じ記録を共有し、その記録があとからこっそり書き換えられていないかを確認しやすくする仕組み」として整理しました。
そこでは、ブロック、チェーン、台帳、分散、ハッシュ、デジタル署名、コンセンサス、スマートコントラクトなどを広く扱いました。

本記事では、その中でも特に ブロック内の大量の取引やデータを、どのように効率よく要約・検証するのか に注目します。

派生元記事との関係を整理すると、次のようになります。

派生元記事	本記事
ブロックチェーン全体の地図を整理する	Merkle Treeに絞って整理する
身近な記録からブロックチェーンを説明する	大量のレシートや出席簿から「必要な1件だけ確認する」問題を説明する
ハッシュ、署名、分散、コンセンサスなどを広く扱う	Merkle root、Merkle proof、SPV、Merkle Patricia Trieなどを扱う
情報セキュリティ上の強みと限界を広く整理する	データの包含確認、改ざん検知のしやすさ、rootの信頼性、実装上の注意点を整理する

関連記事: 身近な記録から理解するブロックチェーンの全体像

Qiitaに投稿する際は、上記の ここに派生元記事のURLを挿入 の部分を、実際に投稿済みの派生元記事URLへ置き換えてください。

なお、本記事は「Merkle Treeだけを知ればブロックチェーン全体が分かる」という位置づけではありません。

ブロックチェーンでは、Merkle Treeのほかにも、次のような技術や設計が関係します。

• 取引が正しいかを確認する検証ルール
• ブロック同士をつなぐハッシュ
• 取引に署名するためのデジタル署名
• ノード同士が情報を伝えるP2Pネットワーク
• 誰が次のブロックを作るかを決めるコンセンサス周辺の仕組み
• ウォレット、取引所、スマートコントラクトなど周辺システムの安全性

NISTIR 8202では、ブロックはブロックヘッダとブロックデータから構成され、ブロックヘッダには前のブロックヘッダのハッシュや、ブロックデータのハッシュ表現が含まれることがあると説明されています。
そのハッシュ表現の方法として、Merkle Treeを生成してroot hashを保存する方法も例として挙げられています。

参考: NISTIR 8202: Blockchain Technology Overview

つまり、Merkle Treeはブロックチェーン全体の中の「部品」の一つです。

ただし、その部品はとても重要です。
なぜなら、ブロックに含まれる大量の取引を、1つのMerkle rootにまとめ、必要な取引だけを効率よく検証する考え方につながるからです。

この図のように、本記事ではブロックチェーン全体ではなく、ブロック内データの要約と検証に関わる部分へ焦点を当てます。

この記事で分かること

この記事で分かることは、次のとおりです。

• 大量の記録を全部見直すことがなぜ大変なのか
• Merkle Treeが何を効率化する仕組みなのか
• Merkle root、leaf、branch、proofといった用語の意味
• ハッシュを木の形に積み上げる基本的な流れ
• Merkle proofを使うと、なぜ必要な部分だけで確認しやすくなるのか
• BitcoinでMerkle Treeがどのように使われているのか
• BitcoinのSPVとMerkle branchの関係
• Ethereumでは、単純なMerkle TreeではなくMerkle Patricia Trieが登場すること
• Certificate Transparencyなど、ブロックチェーン以外での使われ方
• Merkle Treeでできること・できないこと
• Merkle Treeについてよくある誤解
• Verkle Treeなど、関連する最近の動向

特にこの記事では、次の2つを混同しないことを重視します。

混同しやすいこと	分けて考えたいこと
Merkle Tree = データを暗号化する仕組み	Merkle Treeは、ハッシュを使ってデータ集合を要約・検証しやすくする仕組み
Merkle rootだけで何でも検証できる	Merkle root、対象データ、Merkle proof、rootの信頼性を分けて考える必要がある
BitcoinとEthereumのMerkle構造は同じ	BitcoinのMerkle TreeとEthereumのMerkle Patricia Trieは目的や構造が異なる
ハッシュを使うので完全に安全	ハッシュ関数、構築ルール、実装、rootの取得元に依存する
Merkle proofがあればチェーン全体が正しい	Merkle proofで確認できるのは、基本的に「あるrootに対する包含関係」

たとえば、Merkle proofは「ある取引が、あるMerkle rootに対応する木の中に含まれていること」を確認するために役立ちます。
しかし、そのMerkle rootを含むブロックヘッダが正しいか、十分な合意のあるチェーンに含まれているかは、別の検証の話になります。

このように、Merkle Treeを理解するときは、何を証明できて、何は別の仕組みに任せているのか を分けて考えることが大切です。

対象読者

この記事は、次のような人を想定しています。

• ブロックチェーンを学び始めた人
• BitcoinやEthereumの内部構造に少し興味がある人
• Merkle rootという言葉を見たことがあるが、まだイメージがつかめていない人
• Merkle proofやMerkle branchが何を証明しているのか知りたい人
• SPVや軽量クライアントの考え方をざっくり理解したい人
• EthereumのMerkle Patricia Trieという言葉でつまずいたことがある人
• 情報セキュリティの観点から、データの整合性確認や改ざん検知を学びたい人
• いきなり論文や仕様書を読む前に、まず全体像をつかみたい人

前提知識としては、次の程度を想定しています。

前提知識	必要度
ブロックチェーンが取引や状態を記録する仕組みであること	あると読みやすい
ハッシュという言葉を聞いたことがあること	あると読みやすい
BitcoinやEthereumの名前を聞いたことがあること	あると読みやすい
暗号技術の数学的な理解	なくてもよい
データ構造や木構造の専門知識	なくてもよい
実際のBitcoinノードやEthereumノードの運用経験	なくてもよい
暗号資産取引や投資の経験	なくてもよい

途中で、leaf、root、branch、proof、SPV、Merkle Patricia Trie、Verkle Treeといった言葉が出てきます。

ただし、最初から全部を知っている必要はありません。
それぞれの用語は、できるだけ身近な例と一緒に説明します。

たとえば、Merkle rootは「大量の記録全体を表すまとめ印」、Merkle proofは「確認したい1件をrootまでたどるための手がかり」、leafは「木の一番下にある元データのハッシュ」のように、まずはざっくりしたイメージから入ります。

本記事で扱わないこと

本記事は、Merkle Treeの考え方を初学者向けに整理する記事です。

そのため、以下は深く扱いません。

• Merkle Treeに関する厳密な数学的証明
• ハッシュ関数の衝突困難性や第二原像困難性の詳細な証明
• Bitcoin Coreの実装詳細
• Ethereumクライアントの内部実装
• EthereumのMerkle Patricia Trieに関する完全な仕様解説
• RLP、Patricia Trie、Hex-prefix encodingの詳細な実装
• Verkle TreeやPolynomial commitmentの詳しい数理
• Certificate Transparencyの完全な監査プロトコル
• 暗号資産の投資判断、価格予測、取引推奨
• 実際のブロック検証やノード運用の手順

Merkle Treeは、シンプルな考え方に見えますが、実際のプロトコルへ入ると細かな違いがたくさんあります。

たとえば、Bitcoinでは取引IDをペアにしてハッシュし、奇数個の場合は最後の要素を複製して処理します。
一方で、Certificate TransparencyのRFC 6962では、葉と内部ノードで異なるprefixを付けてハッシュするdomain separationが定義されています。

参考: Bitcoin Developer Guide: Block Chain
参考: RFC 6962: Certificate Transparency

つまり、「Merkle Tree」と一言で言っても、使う場面によって細部は異なります。

本記事では、まず初学者が全体像をつかめるように、次の観点に絞って扱います。

扱う観点	扱わない観点
Merkle Treeの基本的な考え方	厳密な数理モデルや形式的証明
Merkle rootとMerkle proofの意味	各プロトコルの完全な実装仕様
Bitcoinでの使われ方	Bitcoin Coreの内部コード解説
EthereumではMPTが登場するという違い	MPTの全ノード形式やエンコード詳細
情報セキュリティ上の強みと注意点	実運用のノード検証手順
小さなPythonコードによる学習	本番用途の検証ライブラリ実装

また、本記事では「Merkle Treeを使えば絶対に改ざんされない」といった説明はしません。

Merkle Treeは、データが変わったときにrootが変わりやすく、改ざんを検知しやすくするために役立ちます。
しかし、その安全性はハッシュ関数、構築ルール、rootの信頼性、実装の正しさなどに依存します。

コードを試す場合の前提

本記事では、後半の章で、Merkle Treeの考え方をイメージするためにPythonの小さなコード例を使う予定です。

ただし、コードはすべて 考え方を理解するための学習用 です。
実際のBitcoinブロック検証、Ethereumの状態証明、証明書ログ監査、暗号資産の送金確認、秘密鍵管理へそのまま使うことは想定していません。

項目	内容
目的	Merkle Tree、Merkle root、Merkle proofの考え方を理解するための学習用
想定環境	Python 3.x系
主に使う標準ライブラリ	hashlib など
外部ライブラリ	原則なし。必要になった場合はその章で説明する
注意点	実際のBitcoin、Ethereum、Certificate Transparencyの検証処理を再現するものではない

たとえば、次のような概念コードを扱う予定です。

• 4件の取引データからMerkle rootを作る簡易モデル
• 取引が1件変わるとMerkle rootが変わることを確認する例
• Merkle proofのために必要な隣のハッシュを集める例
• 対象データとproofからrootを再計算する例
• 奇数個の葉をどう扱うかでrootが変わり得ることを確認する例

ここで扱うコードは、実際のBitcoinやEthereumの仕様を完全に再現するものではありません。
あくまで、「なぜMerkle Treeでは必要な部分だけで確認しやすくなるのか」を、手元で動かしながらイメージするためのものです。

この区別を忘れないようにしながら、必要な章で小さなコード例を使っていきます。

全体の流れ

この記事では、次の順番で話を進めます。

最初は、大量のレシートや出席簿のような身近な記録から入ります。
そこで、記録が少ないうちは全部確認できても、件数が増えると毎回すべてを見るのが大変になることを確認します。

次に、Merkle Treeの基本的な考え方を見ます。
各データをハッシュにし、隣り合うハッシュをさらにまとめていくことで、最後に1つのMerkle rootへ集約する流れを整理します。

そのあと、Merkle proofを見ていきます。
Merkle proofでは、確認したいデータそのものと、rootまでたどるために必要な周辺ハッシュを使います。
これにより、全データを見なくても、対象データがあるrootに対応する集合へ含まれていることを確認しやすくなります。

この図では、取引3を確認したい場合に、取引1や取引2の中身をすべて持たなくても、Hash4 と Hash12 のような手がかりを使ってMerkle rootまで再計算できるイメージを示しています。

その後、Bitcoinでの使われ方を扱います。
Bitcoin Developer Guideでは、取引IDをもとにMerkle Treeを構築し、最後にMerkle rootを得る流れが説明されています。
また、SPVの説明では、ブロックヘッダのMerkle rootと中間ハッシュを使って、ある取引がブロックに含まれていることを確認できると説明されています。

参考: Bitcoin Developer Guide: Block Chain

次に、Ethereumでは少し事情が違うことを整理します。
Ethereum公式ドキュメントでは、実行レイヤーのMerkle trieはMerkle Patricia Trieであり、ブロックヘッダには stateRoot、transactionsRoot、receiptsRoot が含まれると説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie

後半では、ブロックチェーン以外の使われ方として、Certificate Transparencyにも触れます。
RFC 6962では、証明書ログの監査にMerkle Hash Treeが使われ、Merkle audit pathによって葉が木に含まれていることを確認できると説明されています。

参考: RFC 6962: Certificate Transparency

最後に、Merkle Treeでできること・できないこと、よくある誤解、最近の関連動向を整理します。
たとえばEthereum公式ロードマップでは、Verkle Treeがステートレスクライアントへ向けた小さなwitnessのために説明されています。
ただし、Verkle Treeは本記事の中心ではなく、Merkle Treeを理解したあとに見えてくる関連技術として扱います。

参考: Ethereum Roadmap: Verkle Trees

この記事を通じて、最終的には次のような見方ができるようになることを目指します。

Merkle Treeは、大量の記録を1つのMerkle rootにまとめ、必要な部分だけを使って「この記録が含まれていたこと」を確認しやすくする仕組みです。
ただし、Merkle Treeだけでブロックチェーン全体の正しさが保証されるわけではありません。
rootをどこから得るのか、どのプロトコルのルールで木を作るのか、どの範囲を検証しているのかを分けて考えることが大切です。

次の章では、まず 大量の記録では「全部見直す」のが大変になる というところから整理します。
ここを押さえておくと、Merkle Treeが単なるデータ構造ではなく、「大量の記録を効率よく検証したい」という現実的な課題への答えとして見えやすくなります。

---

1. 大量の記録では「全部見直す」のが大変になる

この章では、Merkle Treeの詳しい構造に入る前に、そもそも大量の記録を確認するときに何が大変になるのかを整理します。
ポイントは、すべての記録を毎回見直すのではなく、確認したい記録に関係する部分だけで確かめられないか という発想です。

概要では、大量のレシートや出席簿のような身近な記録から、Merkle Treeの入口を見ました。

ここからは、もう少し丁寧に「大量の記録を確認する」ときの大変さを考えていきます。
まだこの章では、Merkle Treeの木構造そのものには深く入りません。

まずは、研究室やサークルの会計ノートを例にします。

たとえば、みんなで使う会計ノートに、次のような支出が記録されているとします。

No.	日付	内容	金額
1	2026-07-01	会場費	5,000円
2	2026-07-02	飲み物代	1,200円
3	2026-07-03	備品代	2,000円
4	2026-07-04	印刷代	800円

これくらいの件数なら、全部を見直しても大した手間ではありません。
「備品代 2,000円」という記録があるか確認したければ、上から順番に見ればすぐ分かります。

しかし、これが1万件、10万件、100万件になったらどうでしょうか。

毎回すべての行を見直すのは大変です。
特に、ブロックチェーンのように多くの取引を扱う仕組みでは、「全部を毎回確認する」だけでは効率が悪くなります。

もちろん、実際のブロックチェーンでは各ノードが取引やブロックを検証するための複雑なルールを持っています。
ただ、Merkle Treeを理解する入口としては、まず次の問題を押さえると分かりやすいです。

大量の記録があるとき、確認したい1件のために、毎回すべての記録を持ち出す必要があるのか。

この問いが、Merkle Treeの話につながっていきます。

1.1 まずは「全部見る」方法から考える

一番素直な確認方法は、すべての記録を上から順番に見ることです。

たとえば、会計ノートの中に「備品代 2,000円」があるか確認したい場合、次のように1行ずつ確認できます。

# これは「大量の記録から目的の1件を探す」ことを理解するための学習用コードです。
# 実際のブロックチェーンやMerkle Treeの検証処理を再現するものではありません。

records = [
    "2026-07-01 会場費 5000円",
    "2026-07-02 飲み物代 1200円",
    "2026-07-03 備品代 2000円",
    "2026-07-04 印刷代 800円",
]

# 確認したい記録です。
# 今回は、この文字列がrecordsの中に含まれているかを探します。
target = "2026-07-03 備品代 2000円"

# 上から順番に見て、targetと一致する記録があるか確認します。
# 件数が少ないうちは、この方法でも十分分かりやすいです。
found = False

for record in records:
    if record == target:
        found = True
        break

if found:
    print("目的の記録は含まれています。")
else:
    print("目的の記録は見つかりませんでした。")

この方法は、とても分かりやすいです。

ただし、記録が増えるほど、確認のために見る行数も増えやすくなります。
目的の記録が最後の方にある場合や、そもそも含まれていない場合は、ほとんど全部の記録を見ることになります。

これは、学校の出席簿でも同じです。

30人クラスなら、ある学生の名前を探すのはすぐ終わります。
しかし、全学生10万人分の一覧から毎回1人を探すとなると、単純に上から見るだけでは手間が大きくなります。

このように、全部を見る方法はシンプルですが、件数が増えるほど負担が大きくなりやすいという弱点があります。

1.2 件数が増えると、確認回数も増えやすい

次に、記録の件数が増えると、どのくらい確認回数が増えるのかを見てみます。

ここでは、目的の記録が一番最後にある場合を考えます。
この場合、単純な探索では、目的の記録にたどり着くまで全件を確認する必要があります。

# これは「記録件数が増えると、単純な確認では見る回数も増える」ことを
# 理解するための学習用コードです。
# 実際のブロックチェーン検証やデータベース検索の性能評価ではありません。


def count_checks(record_count: int) -> int:
    """
    record_count件の記録から、最後の1件を探すときの確認回数を数えます。

    ここでは説明を簡単にするため、
    - 記録は "record_0", "record_1", ... のような文字列
    - 探したい記録は最後の "record_{record_count - 1}"
    とします。
    """
    records = [f"record_{i}" for i in range(record_count)]
    target = f"record_{record_count - 1}"

    checks = 0

    for record in records:
        checks += 1  # 1件確認するたびにカウントを増やします。

        if record == target:
            break

    return checks


for size in [10, 100, 1_000, 10_000]:
    checks = count_checks(size)
    print(f"記録数: {size:>5}件 / 確認回数: {checks:>5}回")

このコードでは、記録が10件なら10回、10,000件なら10,000回確認することになります。

もちろん、現実のシステムではインデックスやデータベースなど、もっと効率的な探索方法があります。
ここで言いたいのは、「大量の記録を扱うとき、毎回すべてを見る発想には限界がある」ということです。

この感覚は、ブロックチェーンを理解するときにも大切です。

ブロックチェーンでは、ブロックの中に複数の取引が入ります。
Bitcoin Developer Guideでは、ブロック内の取引IDからMerkle Treeを作り、最終的にMerkle rootを得る流れが説明されています。

参考: Bitcoin Developer Guide: Block Chain

つまり、ブロックチェーンでは「大量の取引をどうまとめ、どう確認しやすくするか」が重要なテーマになります。

1.3 ハッシュを使うと、記録の「指紋」を作れる

ここで、Merkle Treeに入る前に、ハッシュの考え方を少しだけ確認します。

ハッシュは、ざっくり言えば データから作る固定長の要約値 です。
身近なイメージで言うと、記録の「指紋」のようなものです。

同じ記録からは同じハッシュが作られます。
一方で、記録の内容が少し変わると、ハッシュ値も大きく変わって見えます。

# これはハッシュの基本的な性質を確認するための学習用コードです。
# 実際のBitcoinのTXID計算やMerkle root計算を再現するものではありません。

import hashlib


def sha256_hex(text: str) -> str:
    """
    入力文字列からSHA-256ハッシュを作り、16進数文字列として返します。

    hashlib.sha256() はバイト列を入力にするため、
    text.encode("utf-8") で文字列をバイト列へ変換しています。
    """
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


record_a = "2026-07-03 備品代 2000円"
record_b = "2026-07-03 備品代 2001円"  # 金額を1円だけ変えています。

print("記録A:", record_a)
print("Hash A:", sha256_hex(record_a))
print()

print("記録B:", record_b)
print("Hash B:", sha256_hex(record_b))

このコードを実行すると、record_a と record_b は金額が1円違うだけなのに、出てくるハッシュ値は大きく違って見えます。

この性質を使うと、記録そのものを毎回見比べなくても、「記録の内容が変わっていないか」を確認しやすくなります。

たとえば、会計ノートの各行にハッシュを付けておけば、あとから内容が変わったときに気づきやすくなります。

ただし、ここで注意したいことがあります。

ハッシュは暗号化ではありません。
暗号化は、鍵を使って元に戻せる形でデータを変換することがあります。
一方、ハッシュは基本的に、入力から固定長の値を作る一方向の処理として使われます。

💡 豆知識
ハッシュは「データを隠すための暗号化」と混同されることがあります。
しかし、Merkle Treeで重要なのは、データを秘密にすることではなく、データのまとまりや変更を確認しやすくすることです。
そのため、本記事ではハッシュを「記録の指紋」や「要約値」のようなイメージで扱います。

1.4 全体を1つのハッシュにまとめるだけでは足りない

ハッシュを使うと、記録のまとまり全体に対しても要約値を作れます。

たとえば、会計ノート全体を1つの文字列としてつなげ、その全体に対してハッシュを計算すれば、「会計ノート全体のまとめ値」のようなものを作れます。

# これは「記録全体を1つのハッシュにまとめる」考え方を確認するための学習用コードです。
# Merkle Treeの実装ではありません。
# ここでは、全記録を単純に連結して1つのハッシュを作っています。

import hashlib


def sha256_hex(text: str) -> str:
    """入力文字列のSHA-256ハッシュを16進数文字列で返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


records = [
    "2026-07-01 会場費 5000円",
    "2026-07-02 飲み物代 1200円",
    "2026-07-03 備品代 2000円",
    "2026-07-04 印刷代 800円",
]

# 記録を区切り文字つきで1つの文字列にまとめます。
# 区切り文字を入れることで、記録同士の境目を分かりやすくしています。
joined_records = "|".join(records)

# 全体のハッシュを計算します。
summary_hash = sha256_hex(joined_records)

print("全体のまとめ値:")
print(summary_hash)

この方法を使うと、会計ノート全体が少しでも変わったときに、まとめ値も変わります。
そのため、「全体として同じ内容か」を確認する用途には役立ちます。

しかし、ここで新しい問題が出てきます。

たとえば、誰かから次のように聞かれたとします。

「2026-07-03 備品代 2000円」という記録は、この会計ノート全体に含まれていますか？

全体のハッシュだけを持っていても、この質問には直接答えにくいです。
なぜなら、全体のハッシュは「全部をまとめた結果」であって、特定の1件がどこに入っているかを示すものではないからです。

確認するには、結局すべての記録をもう一度集めて、同じように全体のハッシュを計算する必要があります。

方法	できること	困ること
全記録を上から見る	目的の記録があるか分かる	件数が多いと確認が重い
全体を1つのハッシュにする	全体が変わっていないか確認しやすい	1件だけの存在確認には使いにくい
各記録にハッシュを付ける	各記録の変更には気づきやすい	全体との結びつきをどう示すかが課題

つまり、単に「全部をハッシュ化する」だけでは、まだ十分ではありません。

欲しいのは、次のような仕組みです。

• 全体を1つの要約値で表したい
• でも、1件の記録を確認するために全件を渡したくない
• その1件が全体に含まれていたことを、少ない手がかりで確認したい
• どこかの記録が変われば、全体の要約値にも影響してほしい

この条件を満たすために出てくるのが、Merkle Treeです。

1.5 「全部」ではなく「必要な道筋」だけで確認したい

ここまでの話を整理すると、確認方法には段階があります。

Merkle Treeでは、各記録をハッシュ化したあと、それらをペアにしてさらにハッシュ化し、最終的に1つのrootへまとめます。

このrootは、全体を代表する要約値のようなものです。

さらに、特定の1件を確認したいときは、その1件からrootまでたどるために必要な周辺ハッシュだけを使います。
この「確認に必要な周辺ハッシュの集まり」が、後の章で扱う Merkle proof や Merkle branch につながります。

Bitcoin Developer Guideでは、SPVの文脈で、ブロックヘッダのMerkle rootと中間ハッシュを使い、ある取引がブロックに含まれていることを確認できると説明されています。

参考: Bitcoin Developer Guide: Block Chain

ここでは、まだ詳しい仕組みを覚える必要はありません。
まずは、次のイメージを持てれば十分です。

Merkle Treeは、大量の記録を1つのrootへまとめつつ、確認したい1件については、rootまでの道筋だけを使って確認できるようにする考え方です。

この「道筋だけで確認する」という発想が、Merkle Treeを理解するうえでとても大切です。

1.6 ブロックチェーンでこの考え方が重要になる理由

ブロックチェーンでは、1つのブロックに複数の取引が含まれます。

そのとき、ブロックの中にあるすべての取引を、毎回すべての参加者へ丸ごと渡して確認するだけでは、効率面で課題が出ます。
特に、軽量なクライアントや、特定の取引だけを確認したい場面では、必要な情報をできるだけ少なくしたくなります。

NISTIR 8202では、ブロックはヘッダとデータで構成され、ブロックヘッダには前のブロックのハッシュや、ブロックデータを表すハッシュ値、たとえばMerkle tree rootが含まれる場合があると説明されています。

参考: NISTIR 8202: Blockchain Technology Overview

Bitcoinでも、ブロックヘッダにはMerkle rootが含まれます。
Bitcoin Developer Referenceでは、Merkle root hashはブロック内のすべての取引から導かれる値であり、取引が変更されるとブロックヘッダにも影響すると説明されています。

参考: Bitcoin Developer Reference: Block Chain

つまり、Merkle Treeは単なる便利なデータ構造ではありません。
ブロック内の大量の取引と、ブロックヘッダのような小さな要約情報を結びつけるための重要な部品として使われています。

この図のように、Merkle Treeは「大量の取引」と「小さな代表値」をつなぐ橋のような役割を持ちます。

ただし、ここでも注意が必要です。

Merkle rootがあるからといって、それだけでブロックチェーン全体の正しさが分かるわけではありません。
Merkle rootで確認しやすくなるのは、主に「ある取引が、そのrootに対応する取引集合に含まれているか」という部分です。

そのrootを含むブロックが有効か、そのブロックがどのチェーン上にあるのか、そのチェーンをどの程度信頼するのかは、別の検証やコンセンサスの話になります。

この切り分けは、後の章でも何度か出てきます。

💡 豆知識
Merkle Treeを理解するときは、「含まれていることの確認」と「ブロックチェーン全体の正しさ」を分けて考えると混乱しにくくなります。
Merkle proofで確認できるのは、あるrootに対して対象データが含まれていることです。
そのroot自体をどこから得るのか、どのチェーンのブロックヘッダを信頼するのかは、別のレイヤーの話になります。

1.7 この章のまとめ

この章では、Merkle Treeの詳しい構造に入る前に、大量の記録を確認するときに何が大変になるのかを整理しました。

会計ノート、出席簿、レシート一覧、スマホ決済履歴のような身近な記録でも、件数が少ないうちは全部を見直せます。
しかし、記録が大量になると、確認したい1件のために毎回すべてを見るのは負担が大きくなります。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
全部を見る方法は分かりやすい	ただし、件数が増えるほど確認の負担も増えやすい
ハッシュは記録の要約値として使える	同じ入力なら同じ値になり、内容が変わると値も変わる
全体を1つのハッシュにするだけでは足りない	全体の変更確認には使えても、1件の存在確認には不便
必要な道筋だけで確認したい	これがMerkle TreeやMerkle proofの考え方につながる
Merkle rootは全体の代表値として使われる	ただし、rootだけでブロックチェーン全体が正しいと分かるわけではない

次の章では、いよいよ Merkle Treeを一言でいうと何か を整理します。

ただし、難しい定義から入るのではなく、この章で見た「大量の記録を全部見直すのは大変」という問題を受けて、Merkle Treeを 大量の記録を1つのrootへまとめ、必要な道筋だけで確認しやすくする仕組み として見ていきます。

---

2. Merkle Treeを一言でいうと

この章では、Merkle Treeをいきなり厳密な定義で覚えるのではなく、大量の記録を1つの代表値にまとめ、必要な部分だけで確認しやすくする仕組み として整理します。
ポイントは、記録をただ1列に並べるのではなく、ハッシュを木の形に積み上げていくことです。

前の章では、大量の記録を毎回すべて見直すのは大変だという話をしました。

たとえば、1万件のレシートの中から「この1枚が本当に含まれていたか」を確認したいとします。
全部を順番に見れば確認はできますが、毎回それを行うのは少し大変です。

また、すべての記録を1つにつなげてハッシュにする方法も考えられます。
この方法なら、「全体が変わっていないか」は確認しやすくなります。

しかし、「この1件がどこに含まれていたか」を確認するには、結局ほかの記録もかなり見直す必要があります。

そこで出てくるのが、Merkle Treeです。

Merkle Treeを一言でいうと、次のように表せます。

Merkle Treeは、大量のデータをハッシュで木の形にまとめ、最後に1つのMerkle rootを作る仕組みです。
そのrootと必要な途中のハッシュを使うことで、対象のデータが全体の中に含まれていることを確認しやすくします。

ここで大切なのは、Merkle Treeが「データを暗号化して隠す仕組み」ではないことです。
Merkle Treeは、データを秘密にするための仕組みではなく、データのまとまりを要約し、整合性や包含関係を確認しやすくするための構造 です。

まずは、構成要素をざっくり見てみます。

用語	ざっくりした意味	身近なイメージ
leaf / 葉	元データをハッシュ化した一番下の要素	レシート1枚ごとの指紋
parent / 親ノード	2つの子ノードをまとめてハッシュ化したもの	2枚分のレシートをまとめたチェック印
Merkle root	木の一番上にある最終的なハッシュ	箱全体を代表するまとめ印
Merkle proof	あるデータをrootまでたどるために必要な周辺ハッシュ	対象レシートを確認するための手がかり

BitcoinのDeveloper Referenceでは、BitcoinのMerkle rootはブロック内のすべての取引IDから構築され、取引が変更されるとMerkle rootも変わると説明されています。
また、TXIDをペアにして二重SHA-256でハッシュし、1つのrootになるまで繰り返す流れも説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

2.1 「1つの大きなハッシュ」と「木構造」は何が違うのか

前の章で、すべての記録を1つにつなげてハッシュ化する方法を見ました。

たとえば、次のような4件の記録があるとします。

番号	記録
1	会場費 5,000円
2	飲み物代 1,200円
3	備品代 2,000円
4	印刷代 800円

これらを全部つなげて1つのハッシュにすることもできます。

Hash(会場費 + 飲み物代 + 備品代 + 印刷代)

この方法は分かりやすいです。
全体の内容が1文字でも変われば、最終的なハッシュも変わります。

ただし、「備品代 2,000円が本当に含まれていたか」を確認したいときには不便です。
全体をもう一度つなげてハッシュを計算し直すには、結局すべての記録が必要になるからです。

Merkle Treeでは、記録をいきなり全部まとめるのではなく、まず小さな単位でハッシュ化し、それをペアでまとめていきます。

このように木の形にしておくと、後で「備品代 2,000円が含まれていたか」を確認するときに、すべての記録を渡さなくても済みます。

たとえば、備品代 2,000円 を確認したい場合、必要になるのは主に次のような情報です。

必要なもの	役割
確認したい記録	備品代 2,000円 そのもの
隣のハッシュ	印刷代 800円 側のハッシュ
反対側のまとまり	会場費 + 飲み物代 側のハッシュ
Merkle root	最終的に一致するか確認する基準

この「対象データからrootへたどるために必要な手がかり」が、後の章で扱う Merkle proof です。

2.2 小さなコードで見る：4件の記録からMerkle rootを作る

ここで、4件の記録からMerkle rootを作る流れをPythonで見てみます。

このコードは、Merkle Treeの考え方を理解するための学習用です。
実際のBitcoinでは、TXIDの扱い、エンディアン、二重SHA-256、ブロック内の取引順序など、プロトコル固有のルールがあります。
ここでは初学者向けに、文字列をSHA-256でハッシュする単純な例にしています。

# これはMerkle Treeの基本的な考え方を理解するための学習用コードです。
# 実際のBitcoinブロック検証やEthereumの状態証明を再現するものではありません。

import hashlib


def sha256_hex(text: str) -> str:
    """
    入力文字列をSHA-256でハッシュ化し、16進数文字列として返します。

    hashlib.sha256() はバイト列を入力として受け取るため、
    text.encode("utf-8") で文字列をバイト列に変換しています。
    """
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


# 学習用の記録です。
# 実際のブロックチェーンでは、ここに取引データやTXIDなどが入ると考えると近いです。
records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "印刷代 800円",
]

# 1. まず、各記録をハッシュ化してleafを作ります。
# leafはMerkle Treeの一番下にある要素です。
leaf_hashes = [sha256_hex(record) for record in records]

# 2. 隣り合うleafをペアにして、親ノードを作ります。
# ここでは、2つのハッシュ文字列を連結してから、もう一度ハッシュ化しています。
hash_12 = sha256_hex(leaf_hashes[0] + leaf_hashes[1])
hash_34 = sha256_hex(leaf_hashes[2] + leaf_hashes[3])

# 3. 最後に、2つの親ノードをまとめてMerkle rootを作ります。
merkle_root = sha256_hex(hash_12 + hash_34)

print("leaf hashes:")
for i, leaf_hash in enumerate(leaf_hashes, start=1):
    print(f"  Hash{i}: {leaf_hash}")

print("\nparent hashes:")
print("  Hash12:", hash_12)
print("  Hash34:", hash_34)

print("\nMerkle root:")
print(" ", merkle_root)

このコードでは、処理を3段階に分けています。

1. 各記録をハッシュ化する
2. 隣り合うハッシュをまとめて親ノードを作る
3. 親ノード同士をまとめてMerkle rootを作る

ここで出てくる leaf_hashes が木の一番下、hash_12 と hash_34 が途中の枝、merkle_root が木の一番上です。

この流れを図で見ると、次のようになります。

ここだけ見ると、「結局ハッシュを何度も計算しているだけでは？」と思うかもしれません。

たしかに、最初にMerkle rootを作るときは、すべての記録を使ってハッシュを計算します。
ただし、Merkle Treeの便利さは、rootを作ったあとに出てきます。

ある1件の記録が含まれているかを確認するとき、すべての記録をもう一度見直すのではなく、対象の記録と、その記録からrootへ進むために必要なハッシュだけで確認できるようになります。

この話は、第4章のMerkle proofで詳しく扱います。

💡 豆知識
Merkle Treeでは、木の一番下にあるデータを leaf、つまり「葉」と呼びます。
これは、木を逆さまに見たような構造になっているからです。
データが下に並び、それらをまとめたハッシュが上へ上へ積み上がって、最後にrootへ到達します。

2.3 小さなコードで見る：記録が1つ変わるとrootも変わる

Merkle Treeでは、元の記録が1つ変わると、その記録のleaf hashが変わります。
そして、その親ノードも変わり、最終的なMerkle rootも変わります。

これは、記録の改ざんや不一致に気づきやすくするうえで重要です。

次のコードでは、4件の記録からMerkle rootを作ったあと、1件だけ内容を変えて、rootがどう変わるかを確認します。

# 記録が1つ変わるとMerkle rootも変わることを確認する学習用コードです。
# 実際のブロックチェーンの改ざん検知を完全に再現するものではありません。

import hashlib


def sha256_hex(text: str) -> str:
    """入力文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def make_merkle_root_for_four_records(records: list[str]) -> str:
    """
    4件の記録からMerkle rootを作ります。

    注意:
    - この関数は説明を分かりやすくするため、記録が4件である前提にしています。
    - 実際には、任意の件数に対応する処理が必要です。
    """
    if len(records) != 4:
        raise ValueError("この学習用関数では、recordsは4件にしてください。")

    # 各記録をleaf hashに変換します。
    leaf_hashes = [sha256_hex(record) for record in records]

    # 2件ずつまとめて親ノードを作ります。
    hash_12 = sha256_hex(leaf_hashes[0] + leaf_hashes[1])
    hash_34 = sha256_hex(leaf_hashes[2] + leaf_hashes[3])

    # 親ノードをさらにまとめてrootを作ります。
    return sha256_hex(hash_12 + hash_34)


original_records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "印刷代 800円",
]

# 3件目だけ、金額を少し変えた記録を用意します。
changed_records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,001円",  # ここだけ変更しています。
    "印刷代 800円",
]

original_root = make_merkle_root_for_four_records(original_records)
changed_root = make_merkle_root_for_four_records(changed_records)

print("変更前のMerkle root:")
print(original_root)

print("\n変更後のMerkle root:")
print(changed_root)

print("\nrootは同じですか？")
print(original_root == changed_root)

このコードでは、備品代 2,000円 を 備品代 2,001円 に変えています。

変更はたった1円分ですが、最終的なMerkle rootは変わります。
これは、1件の記録の変更が、leaf、親ノード、rootへと伝わっていくためです。

このように、Merkle Treeでは、下の方の小さな変更が上のrootまで影響します。

ただし、ここでも注意があります。

Merkle rootが変わったからといって、「誰が、なぜ、どのように変更したか」まで自動で分かるわけではありません。
Merkle Treeが教えてくれるのは、主に 同じデータ集合から作ったrootかどうか や あるデータがrootに対応する集合に含まれるか です。

変更の理由や正当性は、取引の署名、ブロックの検証、コンセンサス、運用ログなど、別の仕組みとあわせて判断する必要があります。

2.4 任意の件数に対応するにはどうするのか

ここまでは、分かりやすさのために4件の記録だけを使いました。

しかし、実際には記録が3件、5件、100件、100万件になることもあります。
そのため、Merkle Treeを作る処理は、任意の件数に対応できるようにする必要があります。

ここで問題になるのが、奇数個のデータです。

たとえば、記録が5件あると、ペアにしたときに1件だけ余ります。

1件目 + 2件目
3件目 + 4件目
5件目 + ？

この余った要素をどう扱うかは、実装やプロトコルによって異なります。
Bitcoinでは、Merkle Treeの各段でハッシュが奇数個になった場合、最後のハッシュを複製してペアを作ると説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

次のコードでは、このBitcoinの説明に近い形で、奇数個の場合に最後のハッシュを複製してMerkle rootを作ります。

# 任意の件数の記録からMerkle rootを作る学習用コードです。
# 奇数個の場合は、最後のハッシュを複製してペアを作ります。
# これはBitcoinのMerkle Tree説明に近い考え方ですが、実際のBitcoin実装を完全に再現するものではありません。

import hashlib


def sha256_hex(text: str) -> str:
    """入力文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def make_merkle_tree_levels(records: list[str]) -> list[list[str]]:
    """
    記録のリストからMerkle Treeの各段を作ります。

    戻り値:
    - levels[0] はleaf hashの一覧
    - levels[-1][0] はMerkle root

    注意:
    - ここでは説明のため、文字列をそのままSHA-256でハッシュ化しています。
    - 実際のBitcoinではTXIDや二重SHA-256など、プロトコル固有の処理があります。
    """
    if not records:
        raise ValueError("recordsは1件以上必要です。")

    # 最初の段は、各記録をハッシュ化したleafです。
    current_level = [sha256_hex(record) for record in records]
    levels = [current_level]

    # rootが1つになるまで、上の段を作り続けます。
    while len(current_level) > 1:
        # 奇数個の場合は、最後のハッシュを複製して偶数個にします。
        # これにより、隣り合う2つずつを必ずペアにできます。
        if len(current_level) % 2 == 1:
            current_level = current_level + [current_level[-1]]

        next_level = []

        # 2つずつ取り出して親ノードを作ります。
        for i in range(0, len(current_level), 2):
            left = current_level[i]
            right = current_level[i + 1]

            # 左右のハッシュを連結し、さらにハッシュ化して親ノードを作ります。
            parent_hash = sha256_hex(left + right)
            next_level.append(parent_hash)

        # 作成した親ノードの段を保存し、次のループでさらに上へ進みます。
        levels.append(next_level)
        current_level = next_level

    return levels


records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "印刷代 800円",
    "交通費 1,500円",  # 5件目なので、途中で奇数個になります。
]

levels = make_merkle_tree_levels(records)

for depth, level in enumerate(levels):
    print(f"level {depth}: {len(level)}個")
    for value in level:
        # ハッシュ値は長いので、先頭だけ表示します。
        print(" ", value[:16] + "...")

print("\nMerkle root:")
print(levels[-1][0])

このコードでは、各段のハッシュ数を表示しています。

5件の記録から始めると、途中で奇数個になるため、最後のハッシュを複製してペアを作ります。
そして、段を上がるごとにハッシュの数が減っていき、最後に1つのMerkle rootだけが残ります。

ここで大切なのは、Merkle Treeの考え方自体はシンプルでも、実装ルールはプロトコルごとに確認する必要がある という点です。

Bitcoinでは奇数個のときに最後を複製する説明がありますが、すべてのシステムが同じルールを使うとは限りません。
また、Certificate Transparencyのような別の用途では、葉と内部ノードでハッシュ計算にprefixを入れるなど、別の安全設計が使われます。

参考: RFC 6962: Certificate Transparency

2.5 Merkle Treeは「省略できる魔法」ではなく「確認しやすくする構造」

Merkle Treeを初めて学ぶと、「全部のデータを見なくてよいなら、とても便利な魔法の圧縮方法なのでは？」と思うかもしれません。

しかし、ここは少し丁寧に分けて考える必要があります。

Merkle Treeは、元データを消しても何でも復元できる圧縮方法ではありません。
Merkle rootだけを見ても、元の取引一覧やレシート一覧を復元することはできません。

Merkle rootは、あくまで全体の代表値です。

できること	説明
全体のデータが同じか確認しやすくする	同じデータ集合から同じルールで作れば、同じrootになる
1件のデータが含まれているか確認しやすくする	対象データとMerkle proofを使ってrootまで再計算できる
変更があったことに気づきやすくする	データが変わると、leafからrootまでのハッシュが変わる

一方で、次のようなことはMerkle Treeだけではできません。

できないこと	理由
rootだけから元データを復元する	ハッシュは元データを復元するためのものではない
rootだけで取引の正当性を判断する	署名や残高、形式などの検証は別に必要
rootだけでブロックチェーン全体を信頼する	rootを含むブロックやチェーンの検証が別に必要
データを暗号化して秘密にする	Merkle Treeは暗号化ではなく、ハッシュによる要約・検証の構造

このように見ると、Merkle Treeは「何でも省略できる魔法」ではなく、必要な検証を効率よく行うための構造 と考えるのが自然です。

2.6 ブロックチェーンでMerkle Treeが重要になる理由

ブロックチェーンでは、1つのブロックの中に複数の取引が含まれます。

もしブロック内の取引を毎回すべて確認しなければならないなら、軽量な確認をしたい利用者やアプリケーションにとって負担が大きくなります。

Bitcoinのホワイトペーパーでは、フルノードを動かさなくても支払いを検証する方法として、ブロックヘッダとMerkle branchを使うSimplified Payment Verification、つまりSPVが説明されています。
SPVでは、取引を含むブロックのMerkle branchを取得し、そのブロックがチェーンに含まれていることを確認するという考え方が示されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

ここでMerkle Treeが役立つのは、ブロック内のすべての取引を毎回渡さなくても、特定の取引がそのブロックのMerkle rootに対応する取引集合へ含まれていることを確認しやすくなるからです。

ただし、SPVはフルノードと同じ検証をすべて行うものではありません。
Bitcoinのホワイトペーパーでも、SPVは正直なノードがネットワークを支配している限り信頼できる一方、攻撃者がネットワークを上回る場合には弱くなると説明されています。

そのため、本記事では、Merkle Treeの便利さと限界を分けて説明します。

この図のように、Merkle Treeはブロックチェーンの中で「取引一覧」と「ブロックヘッダ」をつなぐ重要な役割を持ちます。

💡 豆知識
Bitcoinのブロックヘッダには、前のブロックヘッダのハッシュだけでなく、ブロック内の取引から作られるMerkle rootも含まれます。
つまり、ブロック同士のつながりだけでなく、ブロック内の取引一覧とのつながりもハッシュで確認しやすくなっています。
ただし、Merkle rootは「取引一覧の要約」であり、取引の署名や残高などを自動で検証してくれるものではありません。

2.7 この章のまとめ

この章では、Merkle Treeを一言でいうと何かを整理しました。

Merkle Treeは、大量のデータをハッシュで木の形にまとめ、最後に1つのMerkle rootを作る仕組みです。
各データをleafとしてハッシュ化し、隣り合うハッシュをまとめ、さらに上へ上へと積み上げていきます。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Merkle Treeはハッシュを木構造にしたもの	各データをleafにし、ペアでまとめながらrootを作る
Merkle rootは全体の代表値	大量の記録全体を1つのハッシュで表す
記録が変わるとrootも変わる	1件の変更がleaf、親ノード、rootへ伝わる
Merkle proofにつながる	対象データと必要な周辺ハッシュでrootまで再計算できる
rootだけで何でも分かるわけではない	取引の正当性やチェーン全体の信頼性は別途検証が必要
実装ルールはプロトコルごとに異なる	Bitcoin、Ethereum、Certificate Transparencyでは細部が違う

ここまでで、Merkle Treeの大まかなイメージはつかめました。

ただ、まだ少し抽象的です。
次の章では、leaf、親ノード、rootという構成要素をもう少し丁寧に分けながら、Merkle Treeの基本構造を見ていきます。

特に、木構造をどのように作るのか、なぜペアでまとめるのか、奇数個のときにどう扱うのかを、図とコードを使って整理していきます。

---

3. Merkle Treeの基本構造

この章では、Merkle Treeを構成する部品を、もう少し丁寧に分けて見ていきます。
ポイントは、記録をいきなり1つにまとめるのではなく、下から順番にペアでまとめていく ことです。

前の章では、Merkle Treeを「大量の記録を1つのrootにまとめ、必要な部分だけで確認しやすくする木構造」として見ました。

ここからは、その木構造を少し分解してみます。

といっても、最初から難しいデータ構造として考える必要はありません。
まずは、レシートや出席簿のような記録を、次のように段階的にまとめるイメージで考えます。

1. それぞれの記録にハッシュを付ける
2. 隣り合うハッシュをペアにして、さらにハッシュ化する
3. それを繰り返して、最後に1つのrootを作る

このとき、一番下にある記録のハッシュを leaf、途中で作られるハッシュを 内部ノード、一番上に残るハッシュを Merkle root と呼びます。

部品	読み方	ざっくりした意味	身近なイメージ
leaf	リーフ	木の一番下にあるデータのハッシュ	レシート1枚ごとの指紋
internal node	内部ノード	複数のハッシュをまとめた途中のハッシュ	レシートの小さな束につけた指紋
Merkle root	マークルルート	木全体を代表する一番上のハッシュ	箱全体につけたまとめ印
Merkle proof	マークルプルーフ	あるleafからrootへたどるために必要な周辺ハッシュ	対象レシートを確認するための手がかり

Bitcoin Developer Referenceでは、BitcoinのMerkle rootは、ブロック内のすべての取引ID、つまりTXIDから順番に作られると説明されています。
また、ペアごとに連結して二重SHA-256を行い、奇数個の場合は最後のTXIDを複製して処理することも説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

3.1 leaf：一番下に置かれる「記録のハッシュ」

Merkle Treeの一番下には、確認したいデータそのもの、またはそのデータから作ったハッシュが並びます。
この一番下の要素を leaf と呼びます。

たとえば、4件の会計記録があるとします。

番号	記録
1	会場費 5,000円
2	飲み物代 1,200円
3	備品代 2,000円
4	印刷代 800円

これらをそのまま木に置くのではなく、まず各記録をハッシュ化します。

ここでのハッシュは、記録の内容から作られる「指紋」のようなものです。

同じ記録からは同じハッシュが作られます。
一方で、金額や文字が少しでも変わると、基本的にはまったく違うハッシュに見える値になります。

💡 豆知識
Bitcoinの場合、leafに相当するものは、ブロック内の取引から作られるTXIDです。
ただし、この記事の学習用コードでは、分かりやすさを優先して文字列をそのままSHA-256でハッシュ化します。
実際のBitcoinでは、トランザクションのシリアライズ形式、二重SHA-256、表示上のバイト順など、細かい仕様があります。

3.2 親ノード：隣り合うハッシュをペアでまとめる

leafを作ったら、次は隣り合うleafをペアにして、さらにハッシュ化します。

たとえば、Hash1 と Hash2 をまとめて Hash12 を作ります。
同じように、Hash3 と Hash4 をまとめて Hash34 を作ります。

ここで作られる Hash12 や Hash34 が、途中の 内部ノード です。

身近な例でいうと、レシート1枚ずつに指紋を付けたあと、2枚ずつの小さな束を作り、その束にも指紋を付けるようなイメージです。

段階	何をしているか	身近なイメージ
leaf	1件ずつハッシュ化する	レシート1枚ごとに指紋を付ける
親ノード	隣り合う2つのハッシュをまとめる	2枚のレシート束に指紋を付ける
root	最後の2つのハッシュをまとめる	箱全体にまとめ印を付ける

ここで大切なのは、ペアの左右の順番も意味を持つ という点です。

Hash1 + Hash2 をハッシュ化した値と、Hash2 + Hash1 をハッシュ化した値は、基本的には別の値になります。
つまり、Merkle Treeでは「何が含まれているか」だけでなく、「どの順番で並んでいるか」もrootに影響します。

3.3 小さなコードで見る：左右の順番が変わると親ノードも変わる

ここで、左右の順番が大切であることを、Pythonで確認してみます。

次のコードは、2つの記録をハッシュ化し、左 + 右 と 右 + 左 で親ノードが変わることを見るための学習用コードです。

# これは、Merkle Treeで左右の順番が大切であることを確認するための学習用コードです。
# 実際のBitcoinのTXID処理やバイト順の扱いを再現するものではありません。

import hashlib


def sha256_hex(text: str) -> str:
    """文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def parent_hash(left_hash: str, right_hash: str) -> str:
    """
    左右2つのハッシュを連結して、親ノードのハッシュを作ります。

    Merkle Treeでは、どちらを左に置き、どちらを右に置くかも重要です。
    ここでは説明用に、16進数文字列をそのまま連結しています。
    """
    return sha256_hex(left_hash + right_hash)


# 学習用の2件の記録です。
record_a = "会場費 5,000円"
record_b = "飲み物代 1,200円"

# まず、各記録からleafに相当するハッシュを作ります。
hash_a = sha256_hex(record_a)
hash_b = sha256_hex(record_b)

# 左右の順番を変えて、親ノードを作ります。
parent_ab = parent_hash(hash_a, hash_b)
parent_ba = parent_hash(hash_b, hash_a)

print("Aを左、Bを右にした親ノード:")
print(parent_ab)
print()

print("Bを左、Aを右にした親ノード:")
print(parent_ba)
print()

print("同じ値ですか？", parent_ab == parent_ba)

このコードを実行すると、多くの場合、parent_ab と parent_ba は異なる値になります。

これは、Merkle Treeで順序が重要であることを示しています。
ブロックチェーンの取引一覧でも、単に「同じ取引が含まれているか」だけでなく、どの順番で並べられているかがrootに影響します。

ここは、後でMerkle proofを理解するときにも重要になります。
Merkle proofでは、隣のハッシュを受け取るだけでなく、それが左側にあったのか、右側にあったのかも正しく扱う必要があるからです。

3.4 root：最後に残る1つのまとめ値

ペアでまとめる処理を繰り返していくと、最後に1つのハッシュだけが残ります。
この一番上のハッシュが Merkle root です。

4件の記録であれば、流れは次のようになります。

記録1 ┐
      ├─ Hash12 ┐
記録2 ┘          │
                 ├─ Merkle root
記録3 ┐          │
      ├─ Hash34 ┘
記録4 ┘

もう少しMerkle Treeらしい形で見ると、次のようになります。

Merkle rootは、木全体を代表する値です。

どこか1件の記録が変わると、そのleafが変わります。
leafが変わると、その親ノードも変わります。
親ノードが変わると、最終的なMerkle rootも変わります。

このように、Merkle rootは「全体の要約値」として働きます。

ただし、ここで注意したいのは、Merkle rootだけで中身を復元できるわけではないことです。
ハッシュは要約値であり、元の記録そのものではありません。

💡 豆知識
Merkle rootは、箱の中身をすべて圧縮して元に戻せる「圧縮ファイル」ではありません。
どちらかというと、箱全体につけた「まとめ印」に近いです。
その印だけを見ても中身は分かりませんが、中身が変わると印も変わるため、整合性確認に使いやすくなります。

3.5 奇数個のときはどうするのか

ここまでの例では、記録が4件ありました。
4件なら、2件ずつきれいにペアを作れます。

では、記録が5件だったらどうなるでしょうか。

記録1, 記録2, 記録3, 記録4, 記録5

この場合、記録1・記録2、記録3・記録4 はペアにできます。
しかし、記録5 だけが余ってしまいます。

BitcoinのMerkle Tree説明では、奇数個の場合、最後のハッシュを複製してペアを作ると説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

たとえば、5件なら次のようなイメージです。

Hash1 + Hash2 -> Hash12
Hash3 + Hash4 -> Hash34
Hash5 + Hash5 -> Hash55

図にすると、次のようになります。

ただし、これはあくまでBitcoinの説明に基づく代表的な扱いです。
すべてのMerkle Tree実装が必ず同じ方法を使うわけではありません。

たとえば、Certificate TransparencyのMerkle Treeでは、葉ノードと内部ノードでprefixを分けるなど、Bitcoinとは異なるルールが使われます。
RFC 6962では、ログのエントリを葉として扱い、監査のためにbinary Merkle Hash Treeを使うことが説明されています。

参考: RFC 6962: Certificate Transparency

そのため、実装するときは「Merkle Treeだから全部同じ」と考えず、対象となるプロトコルの仕様に合わせる必要があります。

3.6 小さなコードで見る：階層を表示しながらMerkle Treeを作る

ここまでの説明を、Pythonコードで確認してみます。

次のコードでは、記録一覧からleafを作り、ペアでまとめながら、各階層のハッシュを表示します。
どの段階で何が作られているのかを追いやすいように、コメントを多めに入れています。

# これはMerkle Treeの階層構造を理解するための学習用コードです。
# 実際のBitcoinブロック検証やEthereumの状態証明を再現するものではありません。

import hashlib
from typing import List


def sha256_hex(text: str) -> str:
    """文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def make_parent_hash(left_hash: str, right_hash: str) -> str:
    """
    左右2つのハッシュから、親ノードのハッシュを作ります。

    注意:
    - ここでは説明用に、16進数文字列をそのまま連結しています。
    - 実際のプロトコルでは、バイト列の扱い、二重ハッシュ、prefixなど、仕様に応じた処理が必要です。
    """
    return sha256_hex(left_hash + right_hash)


def build_merkle_levels(records: List[str]) -> List[List[str]]:
    """
    記録一覧からMerkle Treeの各階層を作ります。

    戻り値は、階層ごとのハッシュ一覧です。
    levels[0] がleafの階層、levels[-1] がMerkle rootの階層になります。
    """
    if not records:
        raise ValueError("records must not be empty")

    # 1. まず、各記録をハッシュ化してleafを作ります。
    current_level = [sha256_hex(record) for record in records]
    levels = [current_level]

    # 2. ハッシュが1つになるまで、ペアでまとめる処理を繰り返します。
    while len(current_level) > 1:
        next_level = []

        # 2つずつ取り出すため、0, 2, 4, ... のように進めます。
        for i in range(0, len(current_level), 2):
            left = current_level[i]

            # 右側のペアが存在しない場合は、最後のハッシュを複製します。
            # BitcoinのMerkle Tree説明に近い扱いですが、実装ごとにルールは異なります。
            if i + 1 < len(current_level):
                right = current_level[i + 1]
            else:
                right = left

            # 左右のハッシュから親ノードを作ります。
            next_level.append(make_parent_hash(left, right))

        # 作成した次の階層を保存し、さらに上の階層へ進みます。
        levels.append(next_level)
        current_level = next_level

    return levels


def print_levels(levels: List[List[str]]) -> None:
    """各階層のハッシュを、見やすいように先頭12文字だけ表示します。"""
    for depth, level in enumerate(levels):
        short_hashes = [h[:12] for h in level]
        print(f"level {depth}: {short_hashes}")


records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "印刷代 800円",
    "交通費 1,500円",
]

levels = build_merkle_levels(records)
print_levels(levels)

merkle_root = levels[-1][0]
print("Merkle root:", merkle_root)

このコードを実行すると、次のような流れが見えてきます。

level 0: leafの階層
level 1: leafをペアでまとめた階層
level 2: さらに上へまとめた階層
...
最後: Merkle root

記録が5件あるため、途中でペアが足りない箇所では最後のハッシュを複製しています。
この処理によって、どの階層でもペアを作りながら上へ進めます。

ここで重要なのは、Merkle Treeが「一気に全体を1つのハッシュにする」のではなく、階層を作りながら少しずつ上へまとめる という点です。

3.7 Merkle Treeをアルゴリズムとして整理する

ここまでの内容を、アルゴリズムとして整理すると次のようになります。

入力: 記録の一覧 records
出力: Merkle root

1. records の各要素をハッシュ化して leaf の一覧を作る
2. 現在の階層にハッシュが1つだけなら、それを Merkle root として返す
3. 現在の階層のハッシュを左から2つずつ取り出す
4. ペアがそろっていれば、left と right を連結してハッシュ化する
5. ペアがそろっていなければ、最後のハッシュを複製してペアにする
6. 作成した親ノード一覧を次の階層とする
7. ハッシュが1つになるまで 2〜6 を繰り返す

このアルゴリズムの特徴は、下から上へ進むことです。

手順	役割	イメージ
leafを作る	1件ずつ記録の指紋を作る	レシート1枚ごとの確認印
ペアでまとめる	2件分を1つの親ノードへまとめる	小さな束にまとめ印を付ける
繰り返す	束をさらに大きな束へまとめる	箱全体に近づける
rootを得る	全体を代表する値を作る	箱全体のまとめ印

この流れは、データ件数が増えても同じです。

8件なら、8個のleafから4個、2個、1個へと減っていきます。
1024件なら、1024個のleafから512個、256個、128個……と、半分ずつ上へまとまっていきます。

そのため、Merkle Treeは「全体をまとめる」だけでなく、あとで「一部だけを確認する」ための道筋も作りやすくなります。

3.8 なぜ「木構造」にするとうれしいのか

ここまで見ると、こう思うかもしれません。

それなら、全部の記録を1つにつなげてハッシュ化するだけでもよいのでは？

たしかに、全体の改ざんを検知したいだけなら、すべての記録をまとめて1つのハッシュにする方法も考えられます。

しかし、その方法だと、ある1件の記録について「この全体に含まれている」と確認したいときに、結局ほかの記録もたくさん必要になりやすくなります。

Merkle Treeにしておくと、確認したいleafからrootまでの道筋に必要なハッシュだけを使って確認できます。

たとえば、記録3 が含まれていることを確認したい場合、すべての記録を受け取らなくても、次のような周辺ハッシュがあればrootまで再計算できます。

この図では、Hash3 を確認するために、Hash4 と Hash12 が手がかりとして必要になります。
このような手がかりが、次章で詳しく扱う Merkle proof です。

つまり、Merkle Treeを木構造にする利点は、次のように整理できます。

観点	全体を1つにハッシュ化	Merkle Tree
全体の要約	できる	できる
一部の包含確認	ほかのデータも多く必要になりやすい	必要な道筋だけで確認しやすい
データ件数が多い場合	確認負担が重くなりやすい	proofを小さくしやすい
ブロックチェーンとの相性	使いにくい場面がある	取引の包含確認と相性がよい

Bitcoinのホワイトペーパーでも、取引をMerkle Treeにハッシュ化し、rootだけをブロックのハッシュに含めることで、古いブロックの保存を工夫できることが説明されています。
また、SPVでは、ブロックヘッダとMerkle branchを使って、取引がブロックに含まれていることを確認する考え方が示されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

3.9 実装するときに気をつけたいこと

ここまでのコードでは、分かりやすさを優先して、かなり単純なMerkle Treeを作りました。

しかし、実際のプロトコルでMerkle Treeやその派生構造を扱う場合は、細かいルールが重要になります。

注意点	説明
ハッシュ関数	どのハッシュ関数を使うかは仕様に依存する
入力の形式	文字列なのか、バイト列なのか、シリアライズ形式は何かをそろえる必要がある
左右の順序	left + right と right + left は別の結果になる
奇数個の扱い	最後を複製する方式もあれば、別の定義を使う方式もある
leafと内部ノードの区別	Certificate Transparencyのようにprefixで区別する仕様もある
表示上のバイト順	BitcoinのTXID表示などでは、内部表現と表示が関係する場合がある
proofの形式	隣接ハッシュだけでなく、左右どちらに置くかの情報も必要になる

特に、学習用コードをそのまま実運用へ使わないことが大切です。

この記事のコードは、Merkle Treeの考え方を理解するためのものです。
実際のBitcoinブロック検証、Ethereumの状態証明、Certificate Transparencyの監査、暗号資産取引の検証へそのまま使うことは想定していません。

💡 豆知識
Merkle Treeはシンプルに見えますが、実際の仕様では「どうハッシュ化するか」がとても重要です。
たとえばCertificate Transparencyでは、葉と内部ノードを区別するために異なるprefixを使う設計になっています。
これは、単純に連結してハッシュ化するだけだと、意図しない解釈の余地が生まれる可能性があるためです。

参考: RFC 6962: Certificate Transparency

3.10 この章のまとめ

この章では、Merkle Treeの基本構造を、leaf、親ノード、Merkle rootに分けて整理しました。

Merkle Treeは、記録をいきなり1つにまとめるのではなく、下から順番にペアでまとめていく構造です。
各記録からleafを作り、隣り合うleafをまとめて親ノードを作り、最後に1つのMerkle rootを得ます。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
leafは一番下の要素	記録や取引から作られるハッシュ
親ノードはペアのまとめ	左右2つのハッシュをまとめて作る
Merkle rootは全体の要約値	木全体を代表する一番上のハッシュ
左右の順番が重要	left + right と right + left では結果が変わる
奇数個の扱いは実装依存	Bitcoinでは最後のハッシュを複製する説明がある
木構造にすると一部確認がしやすい	必要な道筋だけを使ってrootまで再計算しやすくなる
実装ルールは仕様に依存する	ハッシュ関数、入力形式、prefix、proof形式などに注意する

次の章では、この木構造を使って、いよいよ ある1件の記録が全体に含まれていることをどう確認するのか を見ていきます。

そこで登場するのが、Merkle proof や Merkle branch と呼ばれる考え方です。
Merkle proofを理解すると、なぜMerkle Treeが「大量の取引を効率よく検証する仕組み」と言われるのかが、よりはっきり見えてきます。

---

4. Merkle proofで「含まれていること」を確認する

この章では、Merkle Treeを使って、ある1件の記録が全体の中に含まれていることをどう確認するのかを整理します。
ポイントは、全部の記録を渡さなくても、対象の記録と少数のハッシュだけでMerkle rootまで再計算できる という点です。

前の章では、Merkle Treeの基本構造を見ました。

記録を1件ずつハッシュ化し、隣り合うハッシュを組み合わせ、さらにハッシュ化していくと、最後に1つの Merkle root が残ります。
このMerkle rootは、大量の記録全体を代表する「まとめ値」のようなものです。

ここからは、Merkle Treeの便利さが特に分かりやすい部分に入ります。

たとえば、たくさんのレシートを箱に入れて、箱全体のまとめ値を作っていたとします。
あとから「このレシートは本当にその箱に入っていたものですか？」と確認したいとき、毎回すべてのレシートを取り出して確認するのは大変です。

そこで、次のように考えます。

確認したいレシートそのものと、rootまでたどるために必要な少数の手がかりだけがあれば、全体を見直さなくても確認できないか。

この「必要な少数の手がかり」にあたるものが、Merkle proof です。

Bitcoinのホワイトペーパーでは、フルノードを動かさない場合でも、ブロックヘッダを保持し、取引をブロックに結びつけるMerkle branchを取得することで、取引がそのブロックに含まれていることを確認できると説明されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

また、Bitcoin Developer Guideでも、軽量クライアントはブロックヘッダのMerkle rootと中間ハッシュのリストを使って、対象取引がブロックに含まれていることを確認できると説明されています。

参考: Bitcoin Developer Guide: Block Chain

4.1 Merkle proofは「rootまで戻るための道しるべ」

Merkle proofは、確認したいデータからMerkle rootまで再計算するために必要な、隣のハッシュの一覧です。

たとえば、次のような4件の取引があるとします。

ここで、Tx3 が全体に含まれていることを確認したいとします。

Tx3 からMerkle rootまでたどるには、まず Tx3 のハッシュである Hash3 が必要です。
ただし、Hash3 だけでは親ノード Hash34 を計算できません。
なぜなら、Hash34 は Hash3 と Hash4 を組み合わせて作るからです。

そのため、まず隣の Hash4 が必要になります。

次に、Hash34 からMerkle rootを作るには、反対側の枝にある Hash12 が必要です。
つまり、Tx3 を確認するためのMerkle proofには、次のような情報が含まれます。

必要な情報	役割
Hash4	Hash3 と組み合わせて Hash34 を再計算する
Hash12	Hash34 と組み合わせてMerkle rootを再計算する

図にすると、次のようなイメージです。

このように、Merkle proofは「対象データからrootまで戻るために必要な隣のハッシュ」を集めたものです。

💡 豆知識
Bitcoinの資料では、Merkle proofという言い方だけでなく、Merkle branch という表現も出てきます。
branchは「枝」という意味です。
確認したい取引からMerkle rootへ向かう道筋を、木の枝として見るとイメージしやすくなります。

4.2 Merkle proofで分かること

Merkle proofを使うと、あるデータが、特定のMerkle rootに対応するデータ集合へ含まれていることを確認できます。

ここで、言い方を少し丁寧にしておく必要があります。

Merkle proofが示すのは、あくまで この対象データは、このMerkle rootへつながる道筋を持っている ということです。
つまり、rootが正しいものとして信頼できるなら、そのrootに対応する集合へ対象データが含まれていると確認できます。

一方で、Merkle proofだけでブロックチェーン全体の正しさが分かるわけではありません。
Merkle rootを含むブロックヘッダが正しいのか、そのブロックが正しいチェーンに含まれているのか、十分な確認があるのか、といった話は別に考える必要があります。

確認できること	追加で考える必要があること
対象データが、あるMerkle rootに対応する集合へ含まれていること	そのMerkle root自体を信頼してよいか
対象データとproofからrootを再計算できること	そのrootを含むブロックが正しいチェーン上にあるか
proofの道筋に沿ってハッシュが一致すること	取引そのものがプロトコル上有効かどうか

Certificate TransparencyのRFC 6962でも、Merkle audit pathは、対象の葉からMerkle Tree Hashを計算するために必要な最小限のノード一覧として説明されています。
そして、計算したrootが信頼しているrootと一致すれば、その葉が木に存在する証明になると説明されています。

参考: RFC 6962: Certificate Transparency

この考え方は、ブロックチェーン以外でも使われます。
大量のログ、証明書、記録をすべて渡すのではなく、必要な道筋だけを渡して検証しやすくする、という発想です。

4.3 Merkle proofには「左右の順番」も必要になる

Merkle proofでは、隣のハッシュ値だけでなく、そのハッシュが左側にあったのか、右側にあったのか も重要です。

たとえば、Hash3 と Hash4 から親ノードを作る場合を考えます。

Hash34 = hash(Hash3 + Hash4)

ここで、左右を入れ替えると別の値になります。

hash(Hash3 + Hash4) と hash(Hash4 + Hash3) は、通常は別の値になる

そのため、Merkle proofでは、単に「隣のハッシュはこれです」と渡すだけでは不十分です。
「その隣のハッシュは、自分から見て左にあったのか、右にあったのか」も分かる必要があります。

proofの情報	なぜ必要か
隣のハッシュ値	親ノードを再計算するため
左右の位置	どちらを先に連結するか決めるため
対象データ	leaf hashを作るため
期待するMerkle root	再計算結果と比較するため

この左右の情報を忘れると、正しいrootへたどれないことがあります。

💡 豆知識
Merkle Treeの説明では、ハッシュ値だけに注目しがちですが、実装では「順番」も大切です。
特に取引の順序や左右の位置が変わると、Merkle rootも変わります。
これは、Merkle Treeが単なるデータの集合ではなく、順序を持った構造として扱われる場面があるためです。

4.4 小さなコードで見る：Merkle proofを作る

ここからは、PythonでMerkle proofを作ってみます。

次のコードは、Merkle proofの考え方を理解するための学習用コードです。
実際のBitcoinのブロック検証や、Ethereumの状態証明を再現するものではありません。

また、説明を簡単にするために、通常のSHA-256を1回使っています。
BitcoinではTXIDやMerkle Treeの構築で二重SHA-256が関係するなど、実際の仕様には違いがあります。

# これはMerkle proofの考え方を理解するための学習用コードです。
# 実際のBitcoinブロック検証やEthereumの状態証明を再現するものではありません。

import hashlib
from typing import List, Tuple


def sha256_hex(text: str) -> str:
    """入力文字列のSHA-256ハッシュを16進数文字列で返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def hash_pair(left: str, right: str) -> str:
    """
    2つのハッシュを左、右の順番で連結し、さらにハッシュ化します。

    左右を入れ替えると結果が変わるため、
    Merkle proofでは左右の位置情報も重要になります。
    """
    return sha256_hex(left + right)


def build_merkle_tree(records: List[str]) -> List[List[str]]:
    """
    記録の一覧から、Merkle Treeを階層ごとに作ります。

    戻り値:
    - levels[0]: leafのハッシュ一覧
    - levels[1]: 1段上の親ノード一覧
    - ...
    - levels[-1]: Merkle rootだけを含む一覧
    """
    if not records:
        raise ValueError("records must not be empty")

    # 最下段のleafを作ります。
    current_level = [sha256_hex(record) for record in records]
    levels = [current_level]

    # rootが1つになるまで、2個ずつまとめて上の階層を作ります。
    while len(current_level) > 1:
        next_level = []

        for i in range(0, len(current_level), 2):
            left = current_level[i]

            # 奇数個で右側がない場合は、最後のハッシュを複製します。
            right = current_level[i + 1] if i + 1 < len(current_level) else left

            next_level.append(hash_pair(left, right))

        current_level = next_level
        levels.append(current_level)

    return levels


def build_merkle_proof(records: List[str], target_index: int) -> Tuple[str, List[Tuple[str, str]]]:
    """
    target_index番目の記録について、Merkle proofを作ります。

    戻り値:
    - target_hash:
        確認したい記録のleafハッシュ
    - proof:
        rootまで再計算するために必要な隣のハッシュ一覧

    proofの各要素は (direction, sibling_hash) の形です。
    directionは、sibling_hashがtarget側から見て left/right のどちらにあるかを表します。
    """
    levels = build_merkle_tree(records)

    if target_index < 0 or target_index >= len(levels[0]):
        raise IndexError("target_index is out of range")

    proof = []
    index = target_index

    # rootの1つ下の階層まで、隣のハッシュを集めます。
    for level in levels[:-1]:
        if index % 2 == 0:
            # 自分が左側なら、右隣が検証に必要です。
            sibling_index = index + 1

            # 右隣がない場合は、自分自身が複製されたものとして扱います。
            sibling_hash = level[sibling_index] if sibling_index < len(level) else level[index]
            proof.append(("right", sibling_hash))
        else:
            # 自分が右側なら、左隣が検証に必要です。
            sibling_index = index - 1
            sibling_hash = level[sibling_index]
            proof.append(("left", sibling_hash))

        # 1段上では、親ノードのindexに移動します。
        index //= 2

    return levels[0][target_index], proof


records = [
    "tx1: Alice -> Bob 1 BTC",
    "tx2: Carol -> Dave 2 BTC",
    "tx3: Eve -> Frank 3 BTC",
    "tx4: Grace -> Heidi 4 BTC",
]

levels = build_merkle_tree(records)
merkle_root = levels[-1][0]

target_index = 2
target_hash, proof = build_merkle_proof(records, target_index)

print("Merkle root:", merkle_root)
print("確認したい記録:", records[target_index])
print("leaf hash:", target_hash)
print("Merkle proof:")

for direction, sibling_hash in proof:
    print(f"  {direction}: {sibling_hash}")

このコードでは、tx3 が全体の中に含まれていることを確認するためのMerkle proofを作っています。

tx3 は4件のうち3番目の記録なので、まず隣にある tx4 のハッシュが必要です。
次に、反対側の枝にある tx1 と tx2 から作られた親ノードのハッシュが必要です。

このように、対象の記録からrootまで上がっていくときに、各階層で必要な隣のハッシュを集めていくのがMerkle proofです。

4.5 小さなコードで見る：Merkle proofを検証する

次に、作成したMerkle proofを使って、本当にMerkle rootまでたどれるかを確認します。

検証の流れは、次のようになります。

1. 確認したい記録をハッシュ化する
2. proofに含まれる隣のハッシュを順番に組み合わせる
3. 左右の位置に注意しながら親ノードを再計算する
4. 最後に得られた値が、期待するMerkle rootと一致するか確認する

前の節で作った関数をそのまま使うこともできますが、ここではQiita上でこのコードだけを試しても動くように、必要な関数をまとめて書いています。

# これはMerkle proofの検証を理解するための学習用コードです。
# 実際のBitcoinブロック検証やEthereumの状態証明を再現するものではありません。
# 単独でも実行しやすいように、root作成・proof作成・proof検証の関数をまとめています。

import hashlib
from typing import List, Tuple


def sha256_hex(text: str) -> str:
    """入力文字列のSHA-256ハッシュを16進数文字列で返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def hash_pair(left: str, right: str) -> str:
    """
    2つのハッシュを左、右の順番で連結し、さらにハッシュ化します。

    Merkle proofを検証するときは、左右の順番を間違えると
    別のrootになってしまうため、この順番が重要です。
    """
    return sha256_hex(left + right)


def build_merkle_tree(records: List[str]) -> List[List[str]]:
    """記録の一覧から、Merkle Treeを階層ごとに作ります。"""
    if not records:
        raise ValueError("records must not be empty")

    # 最下段のleafを作ります。
    current_level = [sha256_hex(record) for record in records]
    levels = [current_level]

    # rootが1つになるまで、2個ずつまとめます。
    while len(current_level) > 1:
        next_level = []

        for i in range(0, len(current_level), 2):
            left = current_level[i]

            # 奇数個で右側がない場合は、最後のハッシュを複製します。
            right = current_level[i + 1] if i + 1 < len(current_level) else left
            next_level.append(hash_pair(left, right))

        current_level = next_level
        levels.append(current_level)

    return levels


def build_merkle_proof(records: List[str], target_index: int) -> Tuple[str, List[Tuple[str, str]]]:
    """
    target_index番目の記録について、Merkle proofを作ります。

    proofの各要素は (direction, sibling_hash) の形です。
    directionは、sibling_hashが対象ノードから見て left/right のどちらにあるかを表します。
    """
    levels = build_merkle_tree(records)

    if target_index < 0 or target_index >= len(levels[0]):
        raise IndexError("target_index is out of range")

    proof = []
    index = target_index

    # rootの1つ下の階層まで、隣のハッシュを集めます。
    for level in levels[:-1]:
        if index % 2 == 0:
            sibling_index = index + 1
            sibling_hash = level[sibling_index] if sibling_index < len(level) else level[index]
            proof.append(("right", sibling_hash))
        else:
            sibling_index = index - 1
            sibling_hash = level[sibling_index]
            proof.append(("left", sibling_hash))

        # 1段上では、親ノードのindexに移動します。
        index //= 2

    return levels[0][target_index], proof


def verify_merkle_proof(
    target_record: str,
    proof: List[Tuple[str, str]],
    expected_root: str,
) -> bool:
    """
    対象の記録とMerkle proofからrootを再計算し、
    期待するMerkle rootと一致するか確認します。
    """
    # まず、確認したい記録そのものをハッシュ化してleafを作ります。
    current_hash = sha256_hex(target_record)

    # proofに含まれる隣のハッシュを、下の階層から順に使います。
    for direction, sibling_hash in proof:
        if direction == "right":
            # 隣のハッシュが右側にある場合は、自分を左、隣を右として結合します。
            current_hash = hash_pair(current_hash, sibling_hash)
        elif direction == "left":
            # 隣のハッシュが左側にある場合は、隣を左、自分を右として結合します。
            current_hash = hash_pair(sibling_hash, current_hash)
        else:
            raise ValueError(f"unknown direction: {direction}")

    # 最後に、再計算したrootが期待するrootと一致するか確認します。
    return current_hash == expected_root


records = [
    "tx1: Alice -> Bob 1 BTC",
    "tx2: Carol -> Dave 2 BTC",
    "tx3: Eve -> Frank 3 BTC",
    "tx4: Grace -> Heidi 4 BTC",
]

target_index = 2
levels = build_merkle_tree(records)
merkle_root = levels[-1][0]
_, proof = build_merkle_proof(records, target_index)

# 元の記録で検証します。
valid_result = verify_merkle_proof(
    target_record=records[target_index],
    proof=proof,
    expected_root=merkle_root,
)

# 対象の記録を少し変更すると、leaf hashが変わります。
# そのため、同じproofを使っても期待するrootには一致しません。
tampered_record = "tx3: Eve -> Frank 999 BTC"
tampered_result = verify_merkle_proof(
    target_record=tampered_record,
    proof=proof,
    expected_root=merkle_root,
)

print("元の記録での検証結果:", valid_result)
print("書き換えた記録での検証結果:", tampered_result)

検証結果が True になれば、対象の記録とproofから、期待するMerkle rootまで正しくたどれたことになります。
一方で、対象の記録を少し書き換えると、検証結果は False になります。

なぜなら、tx3 の内容が変わると、最初のleaf hashが変わるからです。
leaf hashが変わると、その上の親ノードも変わり、最終的に再計算されるrootも変わります。

このように、Merkle proofを使うと、対象データがrootに対応する集合へ含まれているかを確認できます。
逆に、対象データが書き換えられていると、同じproofではrootと一致しにくくなります。

4.6 proofはデータ件数に対してゆっくり増える

Merkle proofの大きな利点は、必要なハッシュの数が、データ件数に対してゆっくり増えることです。

4件の記録なら、proofに必要なハッシュはだいたい2個です。
8件なら3個、16件なら4個というように、木の高さに応じて増えていきます。

これをコードで見てみます。

# Merkle proofに必要な要素数が、記録件数に対してどのように増えるかを見るコードです。
# ここでは二分木の高さを使って、おおよそのproof要素数を計算します。
# 実際のproof形式や要素数は、木の作り方やプロトコルによって変わります。

import math


def estimated_proof_length(record_count: int) -> int:
    """
    record_count件の記録があるとき、
    二分木でrootまでたどるために必要になりやすい階層数を返します。

    たとえば、8件なら 3階層分の隣ハッシュが必要になるイメージです。
    """
    if record_count <= 0:
        raise ValueError("record_count must be positive")

    # log2(record_count) を切り上げると、二分木の高さの目安になります。
    return math.ceil(math.log2(record_count))


for record_count in [4, 8, 16, 1024, 1_000_000]:
    print(f"{record_count:,}件: proof要素数の目安 = {estimated_proof_length(record_count)}")

実行すると、たとえば次のような結果になります。

4件: proof要素数の目安 = 2
8件: proof要素数の目安 = 3
16件: proof要素数の目安 = 4
1,024件: proof要素数の目安 = 10
1,000,000件: proof要素数の目安 = 20

ここで見たいのは、100万件の記録があっても、確認したい1件に対するproofの要素数は20個程度に収まる、という感覚です。

もちろん、これは今回の単純な二分木モデルでの例です。
実際のプロトコルでは、ハッシュの形式、エンコード、木の作り方、proofの表現方法によって細部は変わります。

それでも、Merkle Treeの基本的な強みは次のように言えます。

全部のデータを渡すのではなく、rootまでたどるために必要な道筋だけを渡せばよい。

この性質があるため、Merkle Treeは大量のデータを扱う場面で役立ちます。

4.7 BitcoinのSPVとMerkle proof

Bitcoinでは、Merkle proofの考え方が SPV と関係します。

SPVは、Simplified Payment Verificationの略です。
日本語にすると「簡易支払い検証」のような意味になります。

Bitcoinホワイトペーパーでは、フルノードを動かさずに支払いを検証する方法として、ユーザーがブロックヘッダのコピーを保持し、対象取引を含むブロックに結びつけるMerkle branchを取得する方法が説明されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

Bitcoin Developer Guideでも、軽量クライアントは全取引を含むブロック全体を受け取るのではなく、ブロックヘッダとMerkle branchを使って、対象取引がブロックに含まれていることを確認できると説明されています。

参考: Bitcoin Developer Guide: Block Chain

ざっくり整理すると、次のようになります。

フルノードのイメージ	軽量クライアントのイメージ
ブロックや取引をより多く保持・検証する	ブロックヘッダを中心に保持する
取引やブロックを自分で詳しく検証する	Merkle branchで対象取引の包含を確認する
負荷は大きいが検証能力が高い	軽量だが信頼前提や限界もある

ただし、SPVは万能ではありません。

Bitcoinホワイトペーパーでも、SPVは正直なノードがネットワークを支配している限り信頼できる一方、攻撃者がネットワークを上回る場合には弱くなると説明されています。
また、頻繁に支払いを受ける事業者は、より独立したセキュリティと速い検証のために、自分のノードを動かすのがよいとも述べられています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

そのため、記事では次のように理解するのが安全です。

Merkle proofは、ある取引が特定のMerkle rootに含まれることを効率よく確認する仕組みです。
ただし、そのrootを含むブロックやチェーン自体をどこまで信頼するかは、別の検証やネットワーク前提と関係します。

4.8 Merkle proofでできること・できないこと

ここまで見ると、Merkle proofはとても便利に見えます。

実際、Merkle proofは大量のデータの中から、対象の1件が含まれているかを効率よく確認するのに役立ちます。
一方で、できることとできないことを分けておかないと、誤解につながります。

観点	Merkle proofでできること	Merkle proofだけではできないこと
包含確認	対象データが、あるMerkle rootへつながることを確認する	rootそのものが正しいかを単独で保証する
データ量削減	全データではなく、必要なハッシュだけで確認する	全取引の内容をすべて検証する
改ざん検知	対象データが変わるとrootと一致しにくくなる	ハッシュ関数や実装が不適切な場合の問題を自動で解決する
軽量検証	ブロック全体を持たずに包含を確認する助けになる	チェーン全体の正当性を完全に判断する
ログ監査	大量ログの一部が含まれることを証明しやすくする	ログ運用者が正しく振る舞っていることを常に保証する

特に大切なのは、Merkle proofは 包含証明 であるという点です。

「この取引が、このMerkle rootに対応する木の中に含まれている」ということを示すものであり、「その取引が経済的・法的・業務的に正しい」ことまで保証するものではありません。

たとえば、あるレシートが箱の中に含まれていることを確認できても、その支出が本当に妥当だったかどうかは別の話です。
同じように、ある取引がブロックのMerkle rootに含まれていることを確認できても、そのブロックやチェーンをどう信頼するか、取引を何回確認するか、といった点は別途考える必要があります。

4.9 実装するときの注意点

Merkle proofを自分で実装するときは、いくつか注意点があります。

今回のコードでは、初学者が理解しやすいように、かなり単純化したMerkle Treeを作りました。
しかし、実際のプロトコルでは、細かい仕様がとても大切です。

注意点	説明
ハッシュ関数	どのハッシュ関数を使うかはプロトコルによって異なる
ハッシュ回数	Bitcoinのように二重SHA-256が関係する場合がある
エンコード	文字列をどうバイト列に変換するかで結果が変わる
左右の順番	sibling hashが左か右かを間違えるとrootが一致しない
奇数個の扱い	最後の要素を複製するか、別のルールにするかは仕様に依存する
leafと内部ノードの区別	Certificate Transparencyのようにprefixで区別する仕様もある
proof形式	どの順番で、どの形式のハッシュを渡すかは実装に依存する

RFC 6962では、Certificate TransparencyのMerkle Treeにおいて、leaf hashと内部ノードのhashで異なるprefixを付けることが定義されています。
これは、葉と内部ノードの解釈を混同しにくくするための重要な設計です。

参考: RFC 6962: Certificate Transparency

そのため、実装するときは「Merkle Treeっぽいもの」を自分で作るだけでは不十分です。
BitcoinならBitcoinの仕様、Certificate TransparencyならRFC、EthereumならEthereumのデータ構造に合わせる必要があります。

💡 豆知識
Merkle proofのコードは、学習用なら比較的短く書けます。
しかし、実運用ではハッシュ関数、バイト列の扱い、木の構築ルール、proofの形式、セキュリティ上の前提をきちんとそろえる必要があります。
「考え方はシンプル、仕様合わせは慎重に」と覚えておくとよいです。

4.10 この章のまとめ

この章では、Merkle proofを使って、ある1件の記録が全体に含まれていることを確認する流れを整理しました。

Merkle proofは、確認したいデータからMerkle rootまで再計算するために必要な、隣のハッシュの一覧です。
対象データとMerkle proofを使ってrootを再計算し、期待するMerkle rootと一致すれば、その対象データがそのrootに対応する木へ含まれていることを確認できます。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Merkle proofはrootまで戻るための道しるべ	対象データからrootまで再計算するために必要な隣のハッシュを集めたもの
全データを渡さなくても確認できる	確認したいデータと少数のハッシュだけでrootまでたどれる
左右の順番が重要	どちらを先に連結するかでハッシュ結果が変わる
proofはデータ件数に対してゆっくり増える	木の高さに応じて必要なハッシュ数が増える
BitcoinのSPVと関係する	軽量クライアントが取引の包含を確認する考え方につながる
proofだけで全てが分かるわけではない	rootやブロック、チェーンそのものの信頼性は別に考える必要がある
実装ルールは仕様に依存する	ハッシュ関数、エンコード、prefix、proof形式などを合わせる必要がある

ここまでで、Merkle Treeの基本構造と、Merkle proofによる包含確認の考え方を見ました。

次の章では、これをBitcoinの文脈に寄せて整理します。
Bitcoinでは、ブロック内の取引からMerkle rootを作り、そのMerkle rootがブロックヘッダに入ります。
この構造が、ブロック内の取引検証やSPVとどのように関係するのかを見ていきます。

---

5. BitcoinではMerkle Treeがどのように使われるのか

この章では、ここまで見てきたMerkle Treeを、Bitcoinのブロック構造に当てはめて整理します。
ポイントは、ブロック内の取引一覧をMerkle rootとしてまとめ、そのrootをブロックヘッダに入れる という流れです。

前の章では、Merkle proofを使うと、全データを毎回見直さなくても「このデータが、あるMerkle rootに対応する集合に含まれている」ことを確認できる、と説明しました。

ここからは、その考え方がBitcoinではどこに出てくるのかを見ていきます。

Bitcoinでは、取引がそのままバラバラに保存されているだけではありません。
複数の取引がブロックにまとめられ、そのブロック同士が前後につながることで、取引履歴全体が作られていきます。

Bitcoin Developer Guideでは、ブロック内の取引のコピーをハッシュ化し、ペアにしてさらにハッシュ化する処理を繰り返して、最後に1つの merkle root を作ると説明されています。
そして、そのmerkle rootはブロックヘッダに保存されます。

参考: Bitcoin Developer Guide: Block Chain

この章では、Bitcoinの細かい実装すべてを追うのではなく、Merkle TreeがBitcoinの中でどのような役割を持っているのかに絞って整理します。

5.1 Bitcoinのブロックは「ヘッダ」と「取引一覧」に分けて見ると分かりやすい

まず、Bitcoinのブロックをざっくり見ると、次の2つに分けられます。

部分	ざっくりした役割	Merkle Treeとの関係
ブロックヘッダ	ブロックの要約情報を持つ	Merkle rootが入る
取引一覧	ブロックに含まれる取引本体を持つ	TXIDからMerkle Treeを作る

イメージとしては、分厚い会計ファイルの表紙に「この中に入っている記録全体のまとめ値」が書かれているようなものです。

ファイルの中身には、たくさんの取引があります。
しかし、表紙にあたるブロックヘッダには、取引本体を全部入れるのではなく、取引一覧から作ったMerkle rootを入れます。

Bitcoin Developer Referenceでは、Bitcoinのブロックヘッダは80バイトの形式でシリアライズされ、Proof of Workの対象としてハッシュされると説明されています。
また、ブロックヘッダには、前のブロックヘッダのハッシュ、Merkle root、時刻、nBits、nonceなどが含まれます。

参考: Bitcoin Developer Reference: Block Headers

ここで注目したいのが、Merkle rootがブロックヘッダに入っている という点です。

Bitcoin Developer Referenceでは、Merkle rootはそのブロックに含まれるすべての取引のハッシュから導かれ、取引を変更するとブロックヘッダも変更しなければならないと説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

つまり、Bitcoinでは次のような関係になります。

変更するもの	影響するもの
取引の内容	TXIDが変わる
TXID	Merkle Treeの途中のハッシュが変わる
Merkle Treeの途中のハッシュ	Merkle rootが変わる
Merkle root	ブロックヘッダが変わる
ブロックヘッダ	ブロックハッシュやPoWに影響する

ここだけ見ると少し大げさに感じるかもしれません。

しかし、これがBitcoinにおいて重要です。
ブロック内の取引をこっそり変えようとすると、取引一覧の中だけで話が終わらず、Merkle root、ブロックヘッダ、さらに後続ブロックとのつながりにも影響していきます。

💡 豆知識
Bitcoinでは、ブロックヘッダ自体にすべての取引データが入っているわけではありません。
ブロックヘッダには、取引一覧そのものではなく、取引一覧をMerkle Treeでまとめた Merkle root が入ります。
そのため、Merkle rootは「ブロック内の取引全体を代表する要約値」のような役割を持ちます。

5.2 BitcoinではTXIDからMerkle rootを作る

BitcoinでMerkle Treeを作るとき、葉に相当するのは主に TXID です。

TXIDは、ざっくり言えば 取引を識別するためのID です。
Bitcoin Developer Guideでは、TXIDは署名済み取引のハッシュであると説明されています。

参考: Bitcoin Developer Guide: Block Chain

Bitcoin Developer Referenceでは、Merkle rootの構築について、ブロック内のすべてのTXIDを使い、まずTXIDをconsensus rulesで要求される順序に並べると説明されています。
そのうえで、ペアにして連結し、SHA256(SHA256()) でハッシュします。
TXIDの数が奇数の場合は、最後のTXIDを自分自身とペアにして処理します。

参考: Bitcoin Developer Reference: Merkle Trees

かなり単純化すると、流れは次のようになります。

1. ブロック内の取引からTXIDを並べる
2. TXIDを2つずつペアにする
3. ペアを連結して、二重SHA-256でハッシュする
4. できたハッシュをまた2つずつペアにする
5. 1つになるまで繰り返す
6. 最後に残った値がMerkle rootになる

図で見ると、次のような形です。

ここで、TXID 1 にcoinbase transactionが入っている点もBitcoinらしいポイントです。
Bitcoin Developer Referenceでは、coinbase transactionのTXIDは常に最初に置かれると説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

💡 豆知識
coinbase transaction は、マイナーへのブロック報酬や手数料を扱う特別な取引です。
暗号資産取引所のCoinbase社とは別の意味です。
Bitcoinのブロックでは、このcoinbase transactionが最初の取引として置かれます。

5.3 PythonでBitcoin風のMerkle rootを作ってみる

ここで、BitcoinのMerkle root構築をかなり単純化したPythonコードで見てみます。

次のコードは、Bitcoin Coreの実装を再現するものではありません。
TXIDのバイト順やブロックデータの厳密なシリアライズなどは省略し、TXIDをペアにして二重SHA-256でまとめる流れ を理解するための学習用コードです。

# これはBitcoin風のMerkle root構築を理解するための学習用コードです。
# 実際のBitcoin Coreの実装やブロック検証を再現するものではありません。
# ここでは、TXIDを64文字の16進数文字列として扱い、ペアごとに二重SHA-256でまとめます。

import hashlib
from typing import List


def double_sha256(data: bytes) -> bytes:
    """
    Bitcoinでよく使われる二重SHA-256を計算します。

    SHA-256を1回ではなく2回かけるため、
    SHA256(SHA256(data)) の形になります。
    """
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()


def merkle_parent(left_hex: str, right_hex: str) -> str:
    """
    左右2つのハッシュから、1つ上の親ハッシュを作ります。

    left_hex / right_hex:
        64文字の16進数文字列を想定しています。

    注意:
        実際のBitcoinでは内部バイト順なども重要です。
        ここでは学習用に、16進数文字列をbytesへ変換して連結しています。
    """
    left = bytes.fromhex(left_hex)
    right = bytes.fromhex(right_hex)

    # 左右のハッシュを連結し、二重SHA-256で親ハッシュを作ります。
    return double_sha256(left + right).hex()


def merkle_root(txids: List[str]) -> str:
    """
    TXIDの一覧からMerkle rootを作ります。

    処理の流れ:
    1. 現在の階層にTXID一覧を置く
    2. 奇数個なら最後の要素を複製する
    3. 2つずつペアにして親ハッシュを作る
    4. 1つになるまで繰り返す
    """
    if not txids:
        raise ValueError("txids must not be empty")

    # 元のリストを壊さないようにコピーします。
    current_level = txids[:]

    while len(current_level) > 1:
        # BitcoinのMerkle Treeでは、奇数個の場合に最後のハッシュを複製してペアにします。
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])

        next_level = []

        # 2つずつ取り出して親ハッシュを作ります。
        for i in range(0, len(current_level), 2):
            parent = merkle_parent(current_level[i], current_level[i + 1])
            next_level.append(parent)

        # 1つ上の階層へ進みます。
        current_level = next_level

    return current_level[0]


def make_dummy_txid(text: str) -> str:
    """
    学習用のダミーTXIDを作ります。

    実際のTXIDは取引データから計算されます。
    ここでは説明用に、文字列から二重SHA-256を計算してTXIDのように扱います。
    """
    return double_sha256(text.encode("utf-8")).hex()


# 学習用のダミーTXID一覧です。
# 先頭にcoinbase transaction相当のダミー取引を置いています。
txids = [
    make_dummy_txid("coinbase transaction"),
    make_dummy_txid("Alice -> Bob: 0.01 BTC"),
    make_dummy_txid("Carol -> Dave: 0.02 BTC"),
    make_dummy_txid("Eve -> Frank: 0.03 BTC"),
]

print("TXID一覧:")
for index, txid in enumerate(txids, start=1):
    print(f"{index}: {txid}")

root = merkle_root(txids)

print("\nMerkle root:")
print(root)

このコードでは、4つのダミーTXIDからMerkle rootを作っています。

流れとしては、まず TXID 1 と TXID 2 から親ハッシュを作り、TXID 3 と TXID 4 からもう一つの親ハッシュを作ります。
最後に、その2つの親ハッシュを組み合わせてMerkle rootを作ります。

もちろん、実際のBitcoinでは、取引データのシリアライズ、TXIDの表示順と内部バイト順、consensus rulesに従った取引順序など、より細かい点があります。
そのため、このコードは「仕組みの入口」を理解するためのものとして見てください。

5.4 取引が変わるとMerkle rootもブロックヘッダも変わる

Merkle Treeの重要な性質は、取引が1つでも変わると、そこから上のハッシュが変わり、最終的なMerkle rootも変わることです。

Bitcoinでは、そのMerkle rootがブロックヘッダに入ります。
そのため、ブロック内の取引を変えようとすると、Merkle rootだけでなく、ブロックヘッダにも影響します。

次のコードでは、取引を1つだけ変えると、Merkle rootとブロックヘッダ由来のハッシュが変わることを確認します。

# これは「取引が変わるとMerkle rootとブロックヘッダ側にも影響する」ことを
# 理解するための学習用コードです。
# 実際のBitcoinブロックヘッダのシリアライズやPoW検証を再現するものではありません。

import hashlib
from typing import List


def double_sha256(data: bytes) -> bytes:
    """二重SHA-256を計算します。"""
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()


def make_dummy_txid(text: str) -> str:
    """説明用の文字列から、TXIDのような64文字の16進数文字列を作ります。"""
    return double_sha256(text.encode("utf-8")).hex()


def merkle_parent(left_hex: str, right_hex: str) -> str:
    """左右2つのハッシュから親ハッシュを作ります。"""
    left = bytes.fromhex(left_hex)
    right = bytes.fromhex(right_hex)
    return double_sha256(left + right).hex()


def merkle_root(txids: List[str]) -> str:
    """TXID一覧からMerkle rootを作ります。"""
    if not txids:
        raise ValueError("txids must not be empty")

    current_level = txids[:]

    while len(current_level) > 1:
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])

        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(merkle_parent(current_level[i], current_level[i + 1]))

        current_level = next_level

    return current_level[0]


def simplified_block_hash(previous_block_hash: str, merkle_root_value: str, nonce: int) -> str:
    """
    学習用の簡易ブロックヘッダから、ブロックハッシュのような値を作ります。

    実際のBitcoinのブロックヘッダは80バイトの決まった形式を持ちます。
    ここでは、前ブロックハッシュ・Merkle root・nonceだけを文字列としてまとめています。
    """
    header_text = f"prev={previous_block_hash}|merkle={merkle_root_value}|nonce={nonce}"
    return double_sha256(header_text.encode("utf-8")).hex()


previous_block_hash = double_sha256(b"previous block header").hex()

original_txids = [
    make_dummy_txid("coinbase transaction"),
    make_dummy_txid("Alice -> Bob: 0.01 BTC"),
    make_dummy_txid("Carol -> Dave: 0.02 BTC"),
    make_dummy_txid("Eve -> Frank: 0.03 BTC"),
]

# 2件目の取引だけを変更します。
changed_txids = original_txids[:]
changed_txids[1] = make_dummy_txid("Alice -> Bob: 9.99 BTC")

original_root = merkle_root(original_txids)
changed_root = merkle_root(changed_txids)

original_block_hash = simplified_block_hash(previous_block_hash, original_root, nonce=100)
changed_block_hash = simplified_block_hash(previous_block_hash, changed_root, nonce=100)

print("元のMerkle root:")
print(original_root)

print("\n変更後のMerkle root:")
print(changed_root)

print("\n元のブロックハッシュ:")
print(original_block_hash)

print("\n変更後のブロックハッシュ:")
print(changed_block_hash)

print("\nrootは同じですか？", original_root == changed_root)
print("ブロックハッシュは同じですか？", original_block_hash == changed_block_hash)

このコードでは、Alice -> Bob: 0.01 BTC という取引を、Alice -> Bob: 9.99 BTC へ変更しています。

変更したのは1件だけですが、Merkle rootは変わります。
そして、Merkle rootを含む簡易ブロックヘッダのハッシュも変わります。

実際のBitcoinでは、ブロックヘッダのハッシュはProof of Workと関係します。
そのため、過去の取引を書き換えることは、単に取引一覧を変更するだけでは済みません。
Merkle root、ブロックヘッダ、PoW、さらに後続ブロックとのつながりにも影響します。

この点は、Bitcoin Developer Guideでも説明されています。
ブロック内の取引を変更するには、そのブロックと後続ブロックを変更する必要があり、新しいブロックが追加されるほど変更コストが大きくなる、という説明です。

参考: Bitcoin Developer Guide: Proof Of Work

5.5 SPVではMerkle rootとMerkle branchが重要になる

BitcoinでMerkle Treeが分かりやすく役立つ場面の一つが、SPV です。

SPVは、Simplified Payment Verificationの略です。
日本語では「簡易支払い検証」のように説明されることがあります。

ざっくり言えば、SPVは すべてのブロックデータを持たずに、ブロックヘッダとMerkle branchを使って取引の存在を確認する考え方 です。

Bitcoin Developer GuideのOperating Modesでは、Bitcoinクライアントの検証方法としてFull nodeとSPV clientが説明されています。
SPV clientは初期同期時にブロックヘッダだけをダウンロードし、必要に応じてfull nodeから取引を要求します。
また、ブロックヘッダ内のMerkle rootとMerkle branchによって、対象取引がそのブロックに埋め込まれていることをSPV clientへ示せると説明されています。

参考: Bitcoin Developer Guide: Operating Modes / Simplified Payment Verification

ここで出てくる Merkle branch は、第4章で扱ったMerkle proofに近いものです。
対象TXIDからMerkle rootまで再計算するために必要な、周辺のハッシュ一覧だと考えると分かりやすいです。

この図では、確認したいTXIDからrootへ向かうために、隣のハッシュと反対側の親ハッシュが必要になります。
それらを使って再計算したrootが、ブロックヘッダ内のMerkle rootと一致すれば、「このTXIDは、そのMerkle rootに対応する取引集合に含まれている」と確認できます。

5.6 PythonでMerkle branchによる確認をBitcoin風に見る

第4章でもMerkle proofを扱いましたが、ここではBitcoinの文脈に合わせて、TXID、Merkle branch、ブロックヘッダ内のMerkle rootという言葉で整理します。

次のコードは、対象TXIDに対するMerkle branchを作り、ブロックヘッダに入っていると仮定したMerkle rootと一致するかを確認します。

# これはBitcoinのSPVで出てくるMerkle branchの考え方を理解するための学習用コードです。
# 実際のBitcoinノード、merkleblockメッセージ、BIP37、ブロックヘッダ検証を再現するものではありません。

import hashlib
from typing import List, Tuple

# Merkle branchの1ステップを表します。
# 1つ目は隣のハッシュ、2つ目はその隣のハッシュがleft/rightのどちらにあるかです。
MerkleStep = Tuple[str, str]


def double_sha256(data: bytes) -> bytes:
    """二重SHA-256を計算します。"""
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()


def make_dummy_txid(text: str) -> str:
    """学習用のダミーTXIDを作ります。"""
    return double_sha256(text.encode("utf-8")).hex()


def merkle_parent(left_hex: str, right_hex: str) -> str:
    """左右2つのハッシュから親ハッシュを作ります。"""
    left = bytes.fromhex(left_hex)
    right = bytes.fromhex(right_hex)
    return double_sha256(left + right).hex()


def merkle_parent_with_position(current_hash: str, sibling_hash: str, sibling_position: str) -> str:
    """
    現在のハッシュと隣のハッシュから、1つ上の親ハッシュを作ります。

    sibling_position:
        隣のハッシュが右側にあるなら "right"
        隣のハッシュが左側にあるなら "left"

    左右の順番を間違えると、別の親ハッシュになってしまいます。
    """
    if sibling_position == "right":
        return merkle_parent(current_hash, sibling_hash)

    if sibling_position == "left":
        return merkle_parent(sibling_hash, current_hash)

    raise ValueError("sibling_position must be left or right")


def merkle_root(txids: List[str]) -> str:
    """TXID一覧からMerkle rootを作ります。"""
    if not txids:
        raise ValueError("txids must not be empty")

    current_level = txids[:]

    while len(current_level) > 1:
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])

        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(merkle_parent(current_level[i], current_level[i + 1]))

        current_level = next_level

    return current_level[0]


def build_merkle_branch(txids: List[str], target_index: int) -> List[MerkleStep]:
    """
    指定したTXIDからMerkle rootへたどるためのMerkle branchを作ります。

    target_index:
        確認したいTXIDが、txids一覧の何番目にあるかを表します。
    """
    if not 0 <= target_index < len(txids):
        raise IndexError("target_index is out of range")

    branch: List[MerkleStep] = []
    current_level = txids[:]
    index = target_index

    while len(current_level) > 1:
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])

        # 自分が左側なら、隣は右側です。
        # 自分が右側なら、隣は左側です。
        if index % 2 == 0:
            sibling_index = index + 1
            sibling_position = "right"
        else:
            sibling_index = index - 1
            sibling_position = "left"

        branch.append((current_level[sibling_index], sibling_position))

        # 次の階層を作ります。
        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(merkle_parent(current_level[i], current_level[i + 1]))

        # 親階層では、indexは半分になります。
        index //= 2
        current_level = next_level

    return branch


def verify_merkle_branch(txid: str, branch: List[MerkleStep], expected_root: str) -> bool:
    """
    TXIDとMerkle branchからrootを再計算し、期待するMerkle rootと一致するか確認します。
    """
    current_hash = txid

    for sibling_hash, sibling_position in branch:
        current_hash = merkle_parent_with_position(current_hash, sibling_hash, sibling_position)

    return current_hash == expected_root


# 学習用のダミーTXID一覧です。
txids = [
    make_dummy_txid("coinbase transaction"),
    make_dummy_txid("Alice -> Bob: 0.01 BTC"),
    make_dummy_txid("Carol -> Dave: 0.02 BTC"),
    make_dummy_txid("Eve -> Frank: 0.03 BTC"),
]

# 3番目の取引を確認したい、という想定です。
target_index = 2
target_txid = txids[target_index]

# ブロックヘッダに入っていると仮定するMerkle rootです。
block_header_merkle_root = merkle_root(txids)

# full nodeなどから受け取るMerkle branchを作る、という学習用の想定です。
branch = build_merkle_branch(txids, target_index)

print("確認したいTXID:")
print(target_txid)

print("\nMerkle branch:")
for sibling_hash, position in branch:
    print(f"  sibling_position={position}, sibling_hash={sibling_hash}")

print("\n検証結果:")
print(verify_merkle_branch(target_txid, branch, block_header_merkle_root))

このコードでは、確認したいTXIDとMerkle branchを使って、Merkle rootを再計算しています。
そして、再計算したrootがブロックヘッダ内のMerkle rootと一致するかを確認しています。

ここで大切なのは、SPVで分かることの範囲です。

Bitcoin Developer Guideでは、Merkle rootとMerkle branchによって、対象取引がブロックに埋め込まれていることは示せる一方、それだけで埋め込まれた取引の妥当性を保証するわけではないと説明されています。

参考: Bitcoin Developer Guide: Operating Modes / SPV

つまり、Merkle branchで確認できるのは、主に次のことです。

確認できること	説明
対象TXIDがMerkle rootに対応する木に含まれていること	Merkle branchでrootまで再計算できるため
そのrootがブロックヘッダに入っていること	ブロックヘッダを持っていれば確認できる
そのブロックの上にどれだけブロックが積まれているか	ヘッダチェーンを見れば深さを確認できる

一方で、次のことはMerkle branchだけでは分かりません。

Merkle branchだけでは分からないこと	理由
取引そのものが有効か	署名、UTXO、二重支払いなどの検証が別に必要
ブロック全体が正しいか	ブロック全体の検証やconsensus rulesの確認が必要
接続先ノードが情報を隠していないか	悪意あるノードが「存在しない」と嘘をつく可能性がある
そのチェーンが十分安全か	累積Proof of Workやネットワーク状況も関係する

このように、Merkle Treeはとても便利ですが、それだけでBitcoinの安全性がすべて決まるわけではありません。
Merkle Treeは、あくまで「取引一覧とブロックヘッダを効率よく結びつける部品」として見ると理解しやすいです。

5.7 Full nodeとSPV clientの違い

ここで、Full nodeとSPV clientの違いも軽く整理しておきます。

Bitcoin Developer GuideのOperating Modesでは、ブロックチェーンをクライアントとして検証する主な方法としてFull nodeとSPV clientが説明されています。
Full nodeは、genesis blockから最新ブロックまでをダウンロードして検証するモデルです。
一方、SPV clientはブロックヘッダを中心に扱い、必要に応じてfull nodeから取引やMerkle branchを取得します。

参考: Bitcoin Developer Guide: Operating Modes

整理すると、次のようになります。

観点	Full node	SPV client
持つデータ	ブロックと取引を広く保持・検証する	主にブロックヘッダを持つ
取引検証	自分でルールに従って検証する	Merkle branchなどで含まれていることを確認する
セキュリティ	より強い検証ができる	軽量だが信頼前提や弱点がある
負荷	ストレージ・通信・処理負荷が大きい	Full nodeより軽い
Merkle Treeの役割	ブロック内取引とrootの整合性を確認する	取引がブロックに含まれることを確認する

身近な例でいうと、Full nodeは「会計ノートの全ページとレシートを自分で保管して確認する人」です。
SPV clientは「表紙のまとめ値と、確認したいレシートに関係する道しるべだけを受け取って確認する人」に近いです。

どちらが常に良いというより、目的が違います。

Full nodeは自分で多くを検証できますが、その分だけ負荷が大きくなります。
SPV clientは軽量ですが、接続先ノードやネットワーク分断、プライバシーなどの注意点があります。

Bitcoin Developer Guideでも、SPV clientには、full nodeが情報を省略して嘘をつく可能性や、ネットワーク分断・Sybil攻撃、プライバシー上の懸念などがあると説明されています。

参考: Bitcoin Developer Guide: Potential SPV Weaknesses

💡 豆知識
SPVは「軽量に確認するための工夫」として便利ですが、Full nodeと同じ検証をしているわけではありません。
Merkle branchで分かるのは、対象取引があるブロックのMerkle rootにつながることです。
その取引やブロック全体をどこまで自分で検証しているかは、Full nodeとは異なります。

5.8 BitcoinにおけるMerkle Treeを理解するときの注意点

BitcoinのMerkle Treeは、ここまで見るとかなりシンプルに感じるかもしれません。

ただし、実際に仕様や実装を読むときには、いくつか注意点があります。

注意点	説明
Merkle rootとブロックハッシュは別物	Merkle rootは取引一覧のroot、ブロックハッシュはブロックヘッダをハッシュしたもの
TXIDの順序が重要	順序が変わるとMerkle rootも変わる
coinbase transactionは最初	Bitcoinではcoinbase transactionのTXIDが最初に置かれる
奇数個のときは最後を複製する	Bitcoinでは奇数個のTXIDがある場合、最後のTXIDをコピーしてペアにする
バイト順に注意	仕様や表示形式ではinternal byte orderなどが出てくる
Merkle branchだけで取引の妥当性は保証されない	署名やUTXOなどの検証は別に必要
実装ごとの細部に注意	学習用コードと実際のBitcoin Core実装は同じではない

特に、Merkle rootとブロックハッシュを混同しないこと は大切です。

Merkle rootは、ブロック内の取引一覧から作られるrootです。
ブロックハッシュは、前ブロックハッシュ、Merkle root、時刻、nBits、nonceなどを含むブロックヘッダから計算されます。

かなり単純化すると、次のような関係です。

つまり、Merkle rootはブロックハッシュを作る材料の一つです。
同じものではありません。

この区別を押さえておくと、Bitcoinのブロック構造がかなり見えやすくなります。

5.9 この章のまとめ

この章では、BitcoinにおけるMerkle Treeの使われ方を整理しました。

Bitcoinでは、ブロック内の取引からTXIDを取り出し、それらをMerkle TreeでまとめてMerkle rootを作ります。
そのMerkle rootはブロックヘッダに入り、取引一覧とブロックヘッダを結びつける役割を持ちます。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Bitcoinのブロックはヘッダと取引一覧に分けて見ると分かりやすい	Merkle rootはブロックヘッダに入る
Merkle rootはTXIDから作られる	TXIDを順序どおりに並べ、ペアにしてハッシュする
Bitcoinでは二重SHA-256が使われる	ペアを連結して SHA256(SHA256()) で親ハッシュを作る
奇数個の場合は最後を複製する	ペアを作るために最後のTXIDをコピーして扱う
取引が変わるとMerkle rootも変わる	その影響はブロックヘッダにも及ぶ
SPVではMerkle branchが重要になる	取引がブロックに含まれていることを軽量に確認するために使われる
Merkle branchだけで取引の妥当性までは保証されない	Full nodeによる検証とは信頼前提が異なる
Merkle rootとブロックハッシュは別物	Merkle rootはブロックヘッダに含まれる要素の一つ

ここまでで、BitcoinにおけるMerkle Treeの使われ方を見ました。

Bitcoinでは、取引一覧をMerkle Treeでまとめ、そのrootをブロックヘッダに入れることで、取引一覧とブロックの要約情報を結びつけています。
また、SPVではMerkle branchを使うことで、すべての取引データを持たなくても、対象取引があるブロックに含まれていることを確認できます。

次の章では、Ethereumに目を移します。
EthereumでもMerkle系の構造は重要ですが、BitcoinのMerkle Treeと同じものをそのまま使っているわけではありません。
Ethereumでは、アカウントやコントラクトの状態を扱うために、Merkle Patricia Trie という少し発展した構造が登場します。

---

6. Ethereumでは少し違う：Merkle Patricia Trie

この章では、BitcoinのMerkle Treeから少し視点を広げて、Ethereumで使われる Merkle Patricia Trie を整理します。
ポイントは、Ethereumでは単に「ブロック内の取引一覧をまとめる」だけでなく、アカウント残高やコントラクトの状態のような、更新され続けるデータも扱う必要がある という点です。

前の章では、BitcoinにおけるMerkle Treeの使われ方を見ました。

Bitcoinでは、ブロック内の取引からTXIDを作り、それらをMerkle TreeでまとめてMerkle rootを作ります。
このMerkle rootはブロックヘッダに入り、ブロック内の取引一覧を1つの値で要約する役割を持ちます。

では、Ethereumでも同じように「取引一覧をMerkle Treeにするだけ」で十分なのでしょうか。

ここで、BitcoinとEthereumの性格の違いを少し考えてみます。

Bitcoinは、かなり大まかに言えば、UTXOという仕組みを使って「誰がどの資金を使えるか」を追跡する設計です。
一方、Ethereumは、アカウント、残高、スマートコントラクト、コントラクト内部の保存データ、取引実行結果、ログなど、より多くの状態を扱います。

身近な例で言えば、Bitcoinのブロックを「レシートの束」と考えるなら、Ethereumはそれに加えて、次のような台帳も持っているイメージです。

Ethereumで扱うもの	身近なたとえ	ざっくりした意味
アカウント残高	会計ノートの各メンバーの残高	誰がどれだけ持っているか
nonce	その人が何回操作したかの番号	二重処理や順序の管理に関係する値
コントラクトコード	自動処理のルール	条件に応じて動くプログラム
コントラクトストレージ	契約ごとの保管棚	スマートコントラクトが保持するデータ
取引	操作依頼	送金やコントラクト実行の指示
レシート	実行結果の控え	成功・失敗、ガス使用量、ログなど

このように、Ethereumでは「ブロック内にどんな取引が入っていたか」だけでなく、取引を実行した結果、状態がどう変わったか も大切になります。

そのため、EthereumではBitcoinのような単純なMerkle Treeだけではなく、Merkle Patricia Trie という構造が使われます。

Ethereum公式ドキュメントでは、Ethereumの実行レイヤーにあるmerkle trieはすべてMerkle Patricia Trieを使い、ブロックヘッダには stateRoot、transactionsRoot、receiptsRoot の3つのrootが含まれると説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie

ここからは、Bitcoinとの違いを意識しながら、EthereumのMerkle Patricia Trieを初学者向けに整理していきます。

6.1 BitcoinのMerkle TreeとEthereumのMerkle Patricia Trieの違い

まず、ざっくり比較すると次のようになります。

観点	BitcoinのMerkle Tree	EthereumのMerkle Patricia Trie
主な対象	ブロック内の取引一覧	状態、取引、レシートなど
データの見方	順番に並んだ取引のリスト	key-value形式のデータ
rootの代表例	Merkle root	stateRoot、transactionsRoot、receiptsRoot
使われ方	取引一覧をブロックヘッダへ要約する	状態や取引、実行結果をrootで要約する
直感的なイメージ	レシート一覧を1つのまとめ印にする	残高表や契約データも含めた台帳をまとめる

Bitcoinでは、ブロック内の取引一覧を順番に並べ、そのTXIDをペアにしてハッシュ化していく説明が中心でした。

一方、Ethereumでは、アカウントアドレスやストレージ位置のような key に対して、アカウント情報や保存データのような value が対応します。

たとえば、かなり単純化すると次のようなイメージです。

key	valueの例
Aliceのアドレス	Aliceのnonce、残高、コード情報など
Bobのアドレス	Bobのnonce、残高、コード情報など
あるコントラクトの保存場所	そのコントラクトが持つデータ

つまり、Ethereumで考えたいのは「1列に並んだ取引一覧」だけではありません。
たくさんのkey-valueデータを、効率よく更新・検証できるようにしたいのです。

そこで登場するのが、Trieの考え方です。

6.2 Trieは「文字列の共通部分を共有する木」と考えると分かりやすい

Trieは、日本語では「トライ」と読まれることが多いデータ構造です。
最初は、辞書や住所録のようなものをイメージすると分かりやすいです。

たとえば、次の3つの名前を管理したいとします。

alice
alicia
bob

alice と alicia は、どちらも ali までが共通しています。
Trieでは、この共通する部分を枝として共有しながら、木の形でデータを持ちます。

かなり単純化したイメージは次の通りです。

この図では、alice と alicia が途中まで同じ道を使っています。
データのkeyに共通部分があると、それを枝として共有できるのがTrieの直感です。

💡 豆知識
Trieは、単なる「木」ではなく、keyの文字やビット列をたどってvalueへ到達するためのデータ構造です。
辞書のオートコンプリートや文字列検索の説明で出てくることもあります。
EthereumのMerkle Patricia Trieは、このTrieの考え方に、ハッシュによる検証しやすさや、Patricia trieの圧縮の考え方を組み合わせたものとして見ると入口がつかみやすいです。

ここで、Trieの雰囲気を小さなPythonコードで見てみます。

# これはTrieの基本イメージを理解するための学習用コードです。
# 実際のEthereumのMerkle Patricia Trieを再現するものではありません。

from dataclasses import dataclass, field
from typing import Dict, Optional


@dataclass
class TrieNode:
    """学習用の単純なTrieノードです。"""
    children: Dict[str, "TrieNode"] = field(default_factory=dict)
    value: Optional[str] = None


def insert(root: TrieNode, key: str, value: str) -> None:
    """keyを1文字ずつたどりながら、最後のノードにvalueを保存します。"""
    node = root

    for char in key:
        # まだ枝がなければ、新しいノードを作ります。
        node = node.children.setdefault(char, TrieNode())

    # keyの最後までたどった場所にvalueを保存します。
    node.value = value


def print_trie(node: TrieNode, prefix: str = "") -> None:
    """Trieの中身を、prefixとvalueの対応として表示します。"""
    if node.value is not None:
        print(f"{prefix} -> {node.value}")

    # 表示順を安定させるために、枝を文字順に並べています。
    for char, child in sorted(node.children.items()):
        print_trie(child, prefix + char)


# 学習用のTrieを作ります。
root = TrieNode()
insert(root, "alice", "balance=10")
insert(root, "alicia", "balance=20")
insert(root, "bob", "balance=5")

print_trie(root)

このコードでは、alice、alicia、bob というkeyをTrieに入れています。
実行すると、それぞれのkeyに対応するvalueが表示されます。

このコードは、EthereumのMPTとはまったく同じではありません。
ただし、keyをたどってvalueに到達するという感覚をつかむには十分です。

Ethereumでは、このようなkey-valueの考え方に加えて、各ノードのハッシュを使ってrootを作ります。
そのrootがブロックヘッダに入ることで、「このブロックを処理した後の状態は、このrootで表される状態です」と確認しやすくなります。

6.3 Ethereumのブロックヘッダには3つのrootがある

Bitcoinの章では、ブロックヘッダにMerkle rootが入ることを見ました。

Ethereumでは、ブロックヘッダに複数のrootが登場します。
Ethereum公式ドキュメントでは、ブロックヘッダから参照される3つのrootとして、次のものが説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie

root	ざっくりした意味	身近なたとえ
stateRoot	ブロック処理後のEthereum全体の状態を表すroot	全員の残高表や契約データをまとめた印
transactionsRoot	そのブロックに含まれる取引を表すroot	そのページに書かれた操作依頼一覧のまとめ印
receiptsRoot	取引実行後の結果を表すroot	操作後の控えや実行結果一覧のまとめ印

EthereumのJSON-RPC APIのブロック情報でも、ブロックオブジェクトの返り値として transactionsRoot、stateRoot、receiptsRoot が説明されています。

参考: Ethereum Documentation: JSON-RPC API / eth_getBlockByHash

図にすると、次のようなイメージです。

ここで大切なのは、Ethereumでは「取引が入っているか」だけでなく、取引を実行した結果として状態がどうなったか もrootで確認できるようにしている点です。

たとえば、AliceがBobへ3 ETH送る取引を考えます。
このとき、取引そのものは transactionsRoot 側で扱われます。
一方で、実行後にAliceの残高が減り、Bobの残高が増えた状態は stateRoot 側に関係します。
さらに、その取引が成功したか、どれだけgasを使ったか、どのようなログが出たかは receiptsRoot 側に関係します。

このように分けると、Ethereumの3つのrootはかなり理解しやすくなります。

6.4 stateRootは「実行後の状態」を表す

Ethereumで特に重要なのが、stateRoot です。

Ethereum公式ドキュメントでは、1つのグローバルなstate trieが存在し、クライアントがブロックを処理するたびに更新されると説明されています。
また、state trieにおけるpathは keccak256(ethereumAddress)、valueは rlp(ethereumAccount) であり、Ethereumのaccountは [nonce, balance, storageRoot, codeHash] の4項目で表されると説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie / State Trie

ここは少し難しいので、身近な例に置き換えてみます。

Ethereumのaccount要素	ざっくりした意味	身近なたとえ
nonce	そのアカウントから送った取引数などに関係する値	操作回数のカウンタ
balance	残高	会計ノート上の残高
storageRoot	コントラクトの保存データを表す別のtrieのroot	契約ごとの保管棚のまとめ印
codeHash	コントラクトコードのハッシュ	自動処理ルールの指紋

Ethereumの状態は、単なる残高一覧ではありません。
スマートコントラクトがあるため、「このコントラクトはどんなコードを持っているのか」「そのコントラクト内部にはどんなデータが保存されているのか」も重要になります。

そのため、stateRoot は、Ethereum全体の状態を1つのrootで表すための重要な値です。

次のコードでは、実際のEthereum MPTではなく、学習用に「状態が変わるとroot風のハッシュも変わる」ことだけを確認します。

# これはEthereumのstateRootの雰囲気を理解するための学習用コードです。
# 実際のEthereumのMerkle Patricia Trie、RLP、Keccak-256を再現するものではありません。

import hashlib
import json
from copy import deepcopy


def sha256_hex(text: str) -> str:
    """学習用にSHA-256でハッシュ値を作ります。実際のEthereumはKeccak-256などを使います。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def simple_state_root(state: dict) -> str:
    """
    key-value形式の状態を、学習用に1つのrootへまとめます。

    注意:
    - これはMerkle Patricia Trieではありません。
    - 実際のEthereumでは、RLPエンコード、Keccak-256、Trieノードなどが関係します。
    - ここでは「状態が変わるとrootも変わる」ことだけを確認します。
    """
    # 辞書の順序に左右されないように、keyで並べ替えます。
    normalized = json.dumps(state, sort_keys=True, ensure_ascii=False)
    return sha256_hex(normalized)


# 送金前の状態を、かなり単純化して表します。
state_before = {
    "Alice": {"nonce": 0, "balance": 10},
    "Bob": {"nonce": 0, "balance": 5},
}

# AliceがBobへ3送る、という状態変化を作ります。
state_after = deepcopy(state_before)
state_after["Alice"]["balance"] -= 3
state_after["Bob"]["balance"] += 3
state_after["Alice"]["nonce"] += 1

print("更新前のstateRoot風ハッシュ:", simple_state_root(state_before))
print("更新後のstateRoot風ハッシュ:", simple_state_root(state_after))
print("rootが同じか:", simple_state_root(state_before) == simple_state_root(state_after))

このコードを実行すると、送金前と送金後でroot風のハッシュが変わります。

もちろん、実際のEthereumでは、このように単純にJSONをハッシュしているわけではありません。
ただ、入口としては次の感覚が大切です。

Ethereumでは、取引を実行すると状態が変わります。
そして、その状態の変化は stateRoot に反映されます。

つまり、stateRoot は、ブロック処理後のEthereumの状態を確認するための重要な要約値です。

6.5 transactionsRootとreceiptsRootも役割が違う

次に、transactionsRoot と receiptsRoot を見ていきます。

Ethereum公式ドキュメントでは、transactions trieはブロックごとに別々に存在し、pathは rlp(transactionIndex) だと説明されています。
また、receipts trieも各ブロックに存在し、pathは同じく rlp(transactionIndex) で、取引の実行結果に関する情報を扱うと説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie / Transactions Trie

参考: Ethereum Documentation: Merkle Patricia Trie / Receipts Trie

この2つは、身近な例で考えると分かりやすいです。

たとえば、研究室の備品購入システムを考えます。

データ	身近な例	Ethereumでのイメージ
取引	「Aさんが備品を申請した」「Bさんが支払いを行った」	ブロック内の取引
レシート	「申請は成功した」「支払いに手数料がかかった」	取引実行後の結果
状態	「残高が減った」「備品リストが更新された」	実行後のstate

取引は、操作の依頼です。
レシートは、その操作を実行した結果の控えです。
状態は、操作の結果として変わった台帳そのものです。

この3つを混同しないようにすると、Ethereumのrootが理解しやすくなります。

次のコードでは、取引一覧とレシート一覧をそれぞれroot風にまとめます。
これも実際のEthereum仕様ではなく、学習用です。

# これはtransactionsRootとreceiptsRootの違いを理解するための学習用コードです。
# 実際のEthereumのRLPエンコードやMerkle Patricia Trieを再現するものではありません。

import hashlib
import json


def sha256_hex(text: str) -> str:
    """学習用のハッシュ関数です。実際のEthereumの仕様を再現するものではありません。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def ordered_list_root(items: list[dict]) -> str:
    """
    ブロック内の取引やレシートのように、順番が意味を持つデータをroot風にまとめます。

    注意:
    - 実際のEthereumのtransactionsRoot/receiptsRootではありません。
    - ここでは「同じ要素でも順序が変わるとrootも変わる」ことを確認します。
    """
    encoded_items = []

    for index, item in enumerate(items):
        # indexも含めてエンコードすることで、順番の違いがrootへ影響します。
        encoded = json.dumps({"index": index, "item": item}, sort_keys=True, ensure_ascii=False)
        encoded_items.append(sha256_hex(encoded))

    return sha256_hex("|".join(encoded_items))


transactions = [
    {"from": "Alice", "to": "Bob", "value": 3},
    {"from": "Carol", "to": "Dave", "value": 1},
]

receipts = [
    {"status": "success", "gasUsed": 21000},
    {"status": "success", "gasUsed": 50000},
]

print("transactionsRoot風ハッシュ:", ordered_list_root(transactions))
print("receiptsRoot風ハッシュ:", ordered_list_root(receipts))

# 取引の順番を入れ替えると、root風ハッシュも変わることを確認します。
reordered_transactions = list(reversed(transactions))
print("順序を変えたtransactionsRoot風ハッシュ:", ordered_list_root(reordered_transactions))

このコードでは、取引一覧とレシート一覧を別々にroot風の値へまとめています。
また、取引の順序を変えるとroot風のハッシュが変わることも確認しています。

ここで伝えたいのは、Ethereumでは「取引」「実行結果」「状態」がそれぞれ別の観点として扱われるということです。

6.6 Merkle Patricia Trieで何が確認しやすくなるのか

では、Merkle Patricia Trieがあると何がうれしいのでしょうか。

大まかには、次のような確認がしやすくなります。

確認したいこと	関係するroot	ざっくりした説明
あるアカウント状態が、特定ブロックの状態に含まれているか	stateRoot	その時点の状態に対する確認
ある取引が、特定ブロックに含まれているか	transactionsRoot	そのブロック内の取引に対する確認
ある取引の実行結果が、特定ブロックに含まれているか	receiptsRoot	成功・失敗やログなどに対する確認

ただし、ここで注意が必要です。

Merkle Patricia Trieのproofを扱うには、MPTのノード形式、RLP、Keccak-256、パスのエンコードなど、細かい仕様が関係します。
そのため、本記事ではEthereumのMPT proofを実装レベルで再現することまでは扱いません。

この記事での目的は、次の理解までです。

Ethereumでは、Bitcoinのように取引一覧だけをMerkle Treeでまとめるのではなく、状態・取引・レシートをそれぞれrootで要約している。
そのために、key-valueデータを扱いやすいMerkle Patricia Trieが使われている。

この理解があると、stateRoot、transactionsRoot、receiptsRoot という言葉を見たときに、かなり迷いにくくなります。

6.7 Verkle Treeは「今後の関連話題」として押さえる

Ethereumの状態管理に関連して、Verkle Tree という言葉も出てきます。

Ethereum公式ロードマップでは、Verkle Treeは「Vector commitment」と「Merkle Tree」を組み合わせた名前であり、Ethereumノードが大量の状態データを保存し続けなくてもブロックを検証できるようにするためのデータ構造として説明されています。
また、stateless clientに向けて、witnessを小さくすることが期待されていると説明されています。

参考: Ethereum Roadmap: Verkle Trees

ここは、今回の記事の中心ではありません。
ただ、Merkle Treeを学んでいると、Ethereumの文脈でVerkle Treeという関連用語に出会う可能性があります。

かなりざっくり整理すると、次のようになります。

用語	ざっくりした位置づけ
Merkle Tree	ハッシュを木構造にして、データ全体をrootへまとめる基本的な考え方
Merkle Patricia Trie	Ethereumで状態や取引、レシートを扱うための構造
Verkle Tree	Ethereumのstateless clientなどを見据えた、より小さなwitnessを目指す関連技術

💡 豆知識
Verkle Treeの Verkle は、Vector commitment と Merkle Tree を合わせた名前です。
「Merkle Treeの親戚」のように見えますが、内部ではvector commitmentなど別の考え方も関係します。
この記事では深追いせず、「Ethereumの状態証明をより軽くするために議論されている関連技術」くらいに押さえておきます。

6.8 EthereumのMerkle Patricia Trieを理解するときの注意点

ここまでの内容を踏まえて、EthereumのMPTを理解するときの注意点を整理します。

注意点	説明
BitcoinのMerkle Treeと同じものとして説明しない	Ethereumではkey-value形式の状態を扱うため、Merkle Patricia Trieが使われる
stateRoot と transactionsRoot を混同しない	stateRootは状態、transactionsRootはブロック内取引に関係する
receiptsRoot を忘れない	Ethereumでは取引の実行結果やログも重要になる
学習用コードと実仕様を分ける	実際にはRLP、Keccak-256、ノード形式、パスエンコードが関係する
rootは「そのデータ構造の要約値」	rootだけで何でも分かるわけではなく、proofや元データ、検証ルールが必要
Verkle Treeは現時点では関連話題として扱う	今後のEthereum状態管理に関係するが、MPTそのものとは別の話題

特に、stateRoot はEthereumらしさがよく出る値です。

Bitcoinの章では、「ブロックにどの取引が入っているか」を中心に見ました。
一方、Ethereumでは「取引を実行した結果、世界の状態がどう変わったか」も重要になります。

そのため、EthereumのMerkle Patricia Trieは、単なる取引一覧の要約というより、状態を検証しやすくするための土台 として見ると理解しやすいです。

6.9 この章のまとめ

この章では、EthereumにおけるMerkle Patricia Trieを整理しました。

Bitcoinでは、ブロック内の取引一覧をMerkle Treeでまとめ、そのMerkle rootをブロックヘッダに入れる説明が中心でした。
一方、Ethereumでは、アカウント、残高、コントラクトコード、コントラクトストレージ、取引、レシートなど、より多くのデータを扱います。

そのため、EthereumではMerkle Patricia Trieを使い、ブロックヘッダに stateRoot、transactionsRoot、receiptsRoot という複数のrootを持ちます。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
EthereumではMerkle Patricia Trieが使われる	Ethereumの実行レイヤーのmerkle trieはMPTを使う
ブロックヘッダには3つのrootがある	stateRoot、transactionsRoot、receiptsRoot が重要
stateRootは状態を表す	アカウント残高やコントラクト情報など、実行後の状態に関係する
transactionsRootは取引を表す	ブロック内の取引一覧に関係する
receiptsRootは実行結果を表す	取引の成功・失敗、gas使用量、ログなどに関係する
BitcoinのMerkle Treeと混同しない	Ethereumではkey-value形式や状態管理が重要になる
Verkle Treeは関連する今後の話題	stateless clientや小さなwitnessと関係する

ここまでで、BitcoinとEthereumにおけるMerkle系の構造の違いを見てきました。

Bitcoinでは、取引一覧をまとめるMerkle Treeが中心でした。
Ethereumでは、取引だけでなく状態や実行結果もrootで表すため、Merkle Patricia Trieという少し発展した構造が登場しました。

次の章では、ブロックチェーンから少し離れて、Merkle Treeがブロックチェーン以外でどのように使われるのかを見ていきます。
特に、Certificate Transparencyのように、公開ログを監査しやすくする仕組みにもMerkle Treeの考え方が使われます。

7. ブロックチェーン以外での使われ方

この章では、Merkle Treeがブロックチェーン専用の仕組みではないことを整理します。
ポイントは、大量の記録を公開し、あとから必要な部分だけを検証しやすくする という考え方が、証明書ログやソフトウェア開発の世界でも役立つことです。

ここまで、BitcoinとEthereumを例にして、Merkle TreeやMerkle Patricia Trieの使われ方を見てきました。

Bitcoinでは、ブロック内の取引一覧をMerkle rootへまとめることで、ブロックヘッダと取引一覧を結びつけていました。
Ethereumでは、取引だけでなく状態やレシートも扱うため、Merkle Patricia Trieという少し発展した構造が登場しました。

ここまで読むと、Merkle Treeは「ブロックチェーンのための技術」のように見えるかもしれません。

しかし、Merkle Treeの考え方そのものは、ブロックチェーンだけに閉じたものではありません。
むしろ、次のような場面と相性がよいです。

• 大量の記録を公開ログとして残したい
• あとから、ある記録が本当に含まれていたか確認したい
• ログが途中でこっそり書き換えられていないか監査したい
• すべてのデータを毎回ダウンロードせずに、必要な部分だけ検証したい

身近な例で考えると、学校の出席簿や会計ノートを、あとから誰でも確認できるように公開しているようなものです。

ただし、単に一覧表を公開するだけでは、あとからこっそり途中の行を差し替えられても気づきにくい場合があります。
そこで、記録をハッシュで結びつけ、全体をrootとして公開しておくと、記録の追加や検証をしやすくなります。

この章では、代表例として Certificate Transparency、Gitのオブジェクト構造、そして 透明性ログ を見ていきます。

7.1 Certificate Transparency：証明書を公開ログで監査する

まず、Merkle Treeのブロックチェーン外の応用として特に分かりやすいのが、Certificate Transparency です。

Certificate Transparencyは、TLS証明書の発行を公開ログに記録し、不正な証明書や誤発行された証明書を見つけやすくするための仕組みです。

Webサイトにアクセスするとき、ブラウザはTLS証明書を使って「このサイトは本当にそのドメインのサイトなのか」を確認します。
しかし、もし誤って不正な証明書が発行された場合、その証明書に気づけなければ、利用者は危険な接続を信じてしまう可能性があります。

そこで、証明書の発行を公開ログに記録し、誰でも監視・監査できるようにする考え方が使われます。

かなりざっくり言えば、次のようなイメージです。

身近な例	Certificate Transparencyでのイメージ
学校の掲示板に出席記録を公開する	発行された証明書を公開ログに記録する
自分の名前が勝手に出席扱いされていないか確認する	自分のドメインに対して不審な証明書が出ていないか確認する
掲示板の記録が途中で差し替えられていないか見る	ログがappend-onlyに保たれているか監査する

RFC 6962では、Certificate Transparencyのログが効率的な監査のためにbinary Merkle Hash Treeを使うと説明されています。
また、ログの入力はデータエントリのリストであり、それらを葉としてハッシュし、最終的に1つの32バイトのMerkle Tree Hashを出力すると説明されています。

参考: RFC 6962: Certificate Transparency

ここで、Bitcoinとの共通点と違いを整理しておきます。

観点	Bitcoin	Certificate Transparency
まとめる対象	ブロック内の取引	証明書ログのエントリ
rootの役割	ブロック内取引の要約	ログ全体の要約
proofの役割	取引がブロックに含まれることを示す	証明書がログに含まれることを示す
重要な性質	ブロックヘッダと取引一覧の結びつき	公開ログの監査・append-only性

どちらも、「大量の記録をハッシュでまとめ、必要な部分だけ確認しやすくする」という点では共通しています。
ただし、Bitcoinは分散台帳のブロック構造の一部として使い、Certificate Transparencyは証明書ログの監査に使う、という目的の違いがあります。

💡 豆知識
Certificate Transparencyは、ブロックチェーンではありません。
ただし、公開ログを監査しやすくするためにMerkle Treeを使う点は、ブロックチェーンを理解するときの良い比較対象になります。
「Merkle Tree = 暗号資産専用」ではなく、「大量の記録を検証しやすくする部品」と見ると応用範囲が広く見えてきます。

7.2 Merkle audit pathとinclusion proof

Certificate Transparencyの文脈では、Merkle audit path や Merkle inclusion proof という言葉が出てきます。

これは、これまでの記事で説明してきたMerkle proofとかなり近い考え方です。
対象のログエントリからrootまでを再計算するために、必要な隣のハッシュを集めたものだと考えると分かりやすいです。

RFC 6962では、Merkle audit pathを、ある葉からMerkle Tree Hashを計算するために必要な追加ノードの最短リストとして説明しています。
また、RFC 9162でも、Merkle inclusion proofは、ある葉からMerkle Tree Hashを計算するために必要な追加ノードの最短リストとして説明されています。

参考: RFC 9162: Certificate Transparency Version 2.0

図にすると、これまで見てきたMerkle proofと同じような流れです。

この例では、証明書3がログに含まれていることを確認したいとします。
その場合、証明書3そのものに加えて、隣にある Hash4 と、反対側のまとまりである Hash12 があれば、rootまで再計算できます。

つまり、ログ全体をすべて取り寄せなくても、対象の証明書がそのログのrootに含まれていることを確認しやすくなります。

ただし、ここでも注意があります。

Merkle proofで分かるのは、あくまで あるrootに対して、そのエントリが含まれていること です。
そのrootがどのログ運営者によって公開されたものなのか、ログが正しく運用されているのか、ブラウザや監視者がどのように扱うのかは、別の仕組みも関係します。

7.3 小さなコードで見る：証明書ログをMerkle rootにまとめる

ここで、Certificate Transparencyの雰囲気をかなり単純化したコードで見てみます。

次のコードは、実際のCertificate Transparencyログを再現するものではありません。
目的は、複数の証明書エントリを葉として扱い、Merkle rootへまとめる感覚をつかむことです。

# これはCertificate Transparencyの考え方を理解するための学習用コードです。
# 実際のCTログ、RFC 6962、RFC 9162の完全な実装ではありません。

import hashlib
from typing import List


def hash_leaf(entry: str) -> str:
    """
    ログの葉をハッシュ化します。

    ここでは、葉であることを区別するために 'leaf:' という文字列を付けています。
    実際のCertificate Transparencyでは、葉と内部ノードを区別するための
    prefixを使う仕様になっています。
    """
    data = f"leaf:{entry}".encode("utf-8")
    return hashlib.sha256(data).hexdigest()


def hash_node(left_hash: str, right_hash: str) -> str:
    """
    2つの子ノードのハッシュをまとめて、親ノードのハッシュを作ります。

    ここでも、内部ノードであることを区別するために 'node:' を付けています。
    葉と内部ノードを区別することは、実装上の安全性を考えるうえで重要です。
    """
    data = f"node:{left_hash}:{right_hash}".encode("utf-8")
    return hashlib.sha256(data).hexdigest()


def build_merkle_root(entries: List[str]) -> str:
    """
    ログエントリの一覧からMerkle rootを作ります。

    entries:
        証明書ログのエントリを、説明用に文字列として表したものです。

    戻り値:
        すべてのエントリをまとめたMerkle rootです。
    """
    if not entries:
        return hashlib.sha256(b"empty").hexdigest()

    # まず、各ログエントリをleaf hashにします。
    current_level = [hash_leaf(entry) for entry in entries]

    # 1つのrootになるまで、隣り合うハッシュをまとめ続けます。
    while len(current_level) > 1:
        next_level = []

        # 2個ずつ取り出して親ノードを作ります。
        for i in range(0, len(current_level), 2):
            left = current_level[i]

            # 奇数個の場合は、最後の要素を自分自身とペアにします。
            # これは学習用の単純化であり、CT仕様そのものの再現ではありません。
            right = current_level[i + 1] if i + 1 < len(current_level) else left

            parent = hash_node(left, right)
            next_level.append(parent)

        current_level = next_level

    return current_level[0]


# 説明用の証明書ログエントリです。
certificate_entries = [
    "cert: example.com",
    "cert: qiita.com",
    "cert: example.jp",
    "cert: research.example",
]

root = build_merkle_root(certificate_entries)

print("証明書ログのMerkle root:")
print(root)

このコードでは、4件の証明書ログエントリをMerkle rootへまとめています。

ここで注目したいのは、hash_leaf() と hash_node() を分けている点です。
これは、葉と内部ノードを同じように扱ってしまうと、構造上のあいまいさが生まれる可能性があるためです。

RFC 6962やRFC 9162では、葉と内部ノードを区別してハッシュするためのprefixが仕様として説明されています。
このように、実際のプロトコルでは、単に「左右のハッシュを連結してハッシュする」だけではなく、安全に検証できるように細かいルールが決められています。

参考: RFC 6962: Certificate Transparency
参考: RFC 9162: Certificate Transparency Version 2.0

7.4 append-only：あとからこっそり差し替えにくくする考え方

Certificate Transparencyのような公開ログでは、append-only という性質も重要です。

append-onlyは、ざっくり言えば 過去の記録を消したり差し替えたりせず、新しい記録を末尾に追加していく という考え方です。

身近な例でいうと、会計ノートに新しい支出を追記していくようなものです。
過去のページをこっそり破って差し替えるのではなく、新しいページを後ろに追加していくイメージです。

操作	append-onlyなログでの扱い
新しい記録を追加する	末尾に追加する
過去の記録を修正する	原則として、こっそり差し替えない
過去の記録を消す	原則として、こっそり削除しない
ログの成長を確認する	consistency proofなどで確認する

RFC 6962では、古いTree Hashと新しいTree Hashの間で、ログがappend-onlyに成長していることを示す Merkle consistency proof が説明されています。
また、RFC 9162でも、inclusion proofだけでなく、tree head同士の一貫性を示すproofが扱われます。

参考: RFC 6962: Certificate Transparency

ここで、少し注意が必要です。

Merkle rootが変わったからといって、それだけで「不正があった」とは言えません。
新しいエントリを追加すれば、rootは自然に変わります。

大切なのは、古いログを保ったまま、新しいエントリが後ろに追加されているか です。
つまり、「rootが変わったか」ではなく、「どのように変わったか」が重要になります。

7.5 小さなコードで見る：追記と差し替えの違い

次のコードでは、ログに新しいエントリを追加した場合と、過去のエントリをこっそり差し替えた場合を比較します。

このコードは、本物のMerkle consistency proofではありません。
実際のCertificate Transparencyでは、すべての古いログエントリを再取得しなくても一貫性を確認できるように、専用のconsistency proofが使われます。

ここではまず、追記と差し替えは違う という感覚をつかむための学習用コードとして見てください。

# append-onlyなログの考え方を理解するための学習用コードです。
# 実際のCertificate Transparencyのconsistency proofを実装するものではありません。

import hashlib
from typing import List


def simple_hash(text: str) -> str:
    """説明用に文字列をSHA-256でハッシュ化します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def digest_entries(entries: List[str]) -> List[str]:
    """
    各ログエントリを個別にハッシュ化します。

    ここでは、過去のエントリが変わっていないかを確認するために、
    各エントリのハッシュ一覧を作っています。
    """
    return [simple_hash(entry) for entry in entries]


def is_append_only(old_entries: List[str], new_entries: List[str]) -> bool:
    """
    new_entries が old_entries を先頭部分として保っているか確認します。

    注意:
    - これは学習用の単純な確認です。
    - 実際の透明性ログでは、全エントリを直接見比べずに、
      Merkle consistency proofを使って確認します。
    """
    if len(new_entries) < len(old_entries):
        return False

    # 古いログの長さ分だけ、新しいログの先頭と比較します。
    return new_entries[:len(old_entries)] == old_entries


old_log = [
    "cert: example.com",
    "cert: qiita.com",
    "cert: example.jp",
]

# 正しい追記: 末尾に新しいエントリを追加しています。
appended_log = old_log + ["cert: new.example"]

# 不正な差し替えの例: 先頭のエントリが別のものに変わっています。
modified_log = [
    "cert: attacker.example",
    "cert: qiita.com",
    "cert: example.jp",
    "cert: new.example",
]

print("古いログの各エントリハッシュ:")
print(digest_entries(old_log))
print()

print("appended_log はappend-onlyに見えるか:", is_append_only(old_log, appended_log))
print("modified_log はappend-onlyに見えるか:", is_append_only(old_log, modified_log))

このコードでは、appended_log は古いログをそのまま保ち、末尾に新しいエントリを追加しています。
一方、modified_log は過去のエントリを差し替えているため、append-onlyではないと判断されます。

実際のCertificate Transparencyでは、ログ全体を毎回ダウンロードして比較するのではなく、Merkle Treeを使ったconsistency proofで確認します。
ここが、Merkle Treeを公開ログに使う大きな理由です。

💡 豆知識
inclusion proofは「この記録がログに含まれているか」を確認するための証明です。
一方、consistency proofは「ログが過去の状態から正しく追記されているか」を確認するための証明です。
どちらもMerkle Treeの考え方を使いますが、確認したいことが少し違います。

7.6 Gitのオブジェクト構造：ファイルのつながりをハッシュで表す

もう一つ、Merkle Treeの考え方に近い例として、Git があります。

Gitは、ソースコードの変更履歴を管理するための分散バージョン管理システムです。
Gitを使うと、ファイルの変更履歴をcommitとして記録し、過去の状態へ戻ったり、差分を確認したりできます。

Git公式Bookでは、Gitの内部オブジェクトとして、ファイル内容を表す blob、ディレクトリのようにblobや別のtreeを参照する tree、そしてある時点のプロジェクト状態を表す commit が説明されています。
また、commit objectを作るときには、1つのtree SHA-1と、必要に応じて親commitを指定すると説明されています。

参考: Git Book: Git Internals - Git Objects

ここで注意したいのは、GitをBitcoinのMerkle Treeとまったく同じものとして説明しないことです。

Gitは、ファイル内容やディレクトリ構造、commit同士のつながりをハッシュで識別します。
そのため、Merkle Treeに近い ハッシュでつながるデータ構造 として理解すると役立ちます。

かなり単純化すると、次のような関係です。

この図では、ファイルの内容が変わるとblob hashが変わります。
blob hashが変わると、それを参照するtree hashも変わります。
さらに、そのtreeを参照するcommit hashも変わります。

これは、Merkle Treeで葉が変わると親ノードやrootが変わる流れとよく似ています。

Merkle Tree	Gitのイメージ
葉	ファイル内容を表すblob
親ノード	blobやsubtreeをまとめるtree
root	プロジェクト全体の状態を表すtreeやcommit
proof	Gitでは同じ形のMerkle proofというより、オブジェクト参照をたどる

Gitでは、ブロックチェーンのような合意形成やSPVをしているわけではありません。
しかし、「内容が変わるとハッシュも変わり、その影響が上位の構造へ伝わる」という感覚をつかむには、とても分かりやすい例です。

7.7 小さなコードで見る：ファイルが変わるとcommit風ハッシュも変わる

ここでは、Gitの雰囲気をかなり単純化したコードで見てみます。

このコードは、実際のGitオブジェクト形式を再現するものではありません。
本物のGitでは、オブジェクトの種類やサイズを含めてハッシュ化するなど、細かい形式が決まっています。

ここでは、ファイル内容からblob風ハッシュを作り、それらをtree風ハッシュにまとめ、さらにcommit風ハッシュへつなげる流れだけを見ます。

# Gitのオブジェクト構造の雰囲気を理解するための学習用コードです。
# 実際のGitのオブジェクト形式やSHA-1計算を再現するものではありません。

import hashlib
from typing import Dict


def sha256_hex(text: str) -> str:
    """説明用に、文字列をSHA-256でハッシュ化します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def make_blob(content: str) -> str:
    """
    ファイル内容からblob風のハッシュを作ります。

    実際のGitでは、blobオブジェクトのヘッダやサイズも含めて
    ハッシュ化されます。ここでは説明用に単純化しています。
    """
    return sha256_hex(f"blob:{content}")


def make_tree(files: Dict[str, str]) -> str:
    """
    ファイル名とblob hashをまとめて、tree風のハッシュを作ります。

    files:
        キーにファイル名、値にファイル内容を持つ辞書です。
    """
    entries = []

    # ファイルの順序で結果が変わらないように、ファイル名でソートします。
    for filename, content in sorted(files.items()):
        blob_hash = make_blob(content)
        entries.append(f"{filename}:{blob_hash}")

    # treeは、複数のblob参照をまとめたものとして扱います。
    return sha256_hex("tree:" + "|".join(entries))


def make_commit(tree_hash: str, parent_hash: str, message: str) -> str:
    """
    tree hash、親commit、メッセージからcommit風のハッシュを作ります。

    実際のGit commitには、author、committer、timestampなども含まれます。
    """
    commit_data = f"tree={tree_hash}|parent={parent_hash}|message={message}"
    return sha256_hex("commit:" + commit_data)


files_v1 = {
    "main.py": "print('hello')",
    "README.md": "# Sample Project",
}

# 1つ目の状態をcommit風ハッシュにまとめます。
tree_v1 = make_tree(files_v1)
commit_v1 = make_commit(tree_v1, parent_hash="", message="initial commit")

print("v1 tree:", tree_v1)
print("v1 commit:", commit_v1)
print()

# main.pyの内容を少しだけ変更します。
files_v2 = {
    "main.py": "print('hello, merkle')",
    "README.md": "# Sample Project",
}

# ファイル内容が変わると、tree風ハッシュとcommit風ハッシュも変わります。
tree_v2 = make_tree(files_v2)
commit_v2 = make_commit(tree_v2, parent_hash=commit_v1, message="update main")

print("v2 tree:", tree_v2)
print("v2 commit:", commit_v2)
print()

print("treeは変わったか:", tree_v1 != tree_v2)
print("commitは変わったか:", commit_v1 != commit_v2)

このコードでは、main.py の内容を少し変えるだけで、tree風ハッシュとcommit風ハッシュが変わります。

これは、Merkle Treeで葉のデータが変わると、親ノードやrootが変わる流れに似ています。
Gitでは、この性質によって、あるcommitがどのファイル状態を指しているのかをハッシュでたどりやすくなります。

💡 豆知識
Gitの内部構造は、しばしばMerkle TreeやMerkle DAGに近いものとして説明されます。
ただし、Gitを説明するときは、BitcoinのMerkle Treeと完全に同じものとして扱うより、内容に基づくハッシュでオブジェクト同士を結びつける仕組み と捉える方が安全です。

7.8 ソフトウェアサプライチェーンの透明性ログ

近年は、ソフトウェアサプライチェーンの安全性を高める文脈でも、透明性ログが注目されています。

たとえば、ソフトウェアの署名やビルド情報、アーティファクトのメタデータを公開ログへ記録し、あとから「このソフトウェアは誰が、いつ、どのように署名したのか」を確認しやすくする考え方があります。

SigstoreのRekorは、ソフトウェアサプライチェーンで生成される署名付きメタデータを、改ざん耐性のある記録として保存することを目的とした透明性ログとして説明されています。

参考: Sigstore Documentation: Rekor
参考: sigstore/rekor: Software Supply Chain Transparency Log

また、TrillianはCertificate Transparencyの考え方を一般化し、任意のデータに対する透明でappend-onlyなログを作れるようにするプロジェクトとして説明されています。
Trillianのドキュメントでは、検証可能なログを実装するためにMerkle Treeを使い、各記録がMerkle Treeの新しい葉として追加されると説明されています。

参考: Trillian: Transparent Logging
参考: Trillian: Verifiable Data Structures

このような透明性ログは、ブロックチェーンそのものではありません。
しかし、次のような発想はMerkle Treeととても相性がよいです。

確認したいこと	Merkle Treeが役立つ理由
ある記録がログに含まれているか	inclusion proofで確認しやすい
ログが過去から追記されているか	consistency proofで確認しやすい
大量の記録を毎回全部取得したくない	proofだけで確認しやすい
ログ運営者の不審な振る舞いを監査したい	rootやproofを比較する手がかりになる

ここで大切なのは、Merkle Treeが「分散合意」そのものを提供するわけではないことです。

透明性ログでは、ログ運営者、監視者、監査者、クライアントなど、いくつかの役割が組み合わさります。
Merkle Treeは、その中で ログの内容や成長を検証しやすくするデータ構造 として役立ちます。

7.9 ブロックチェーン外で使われるときの注意点

ここまで、Certificate Transparency、Git、ソフトウェアサプライチェーンの透明性ログを見てきました。

どれもMerkle Treeや、それに近いハッシュでつながる構造が役立つ例です。
ただし、使われる目的や信頼の置き方はそれぞれ違います。

例	Merkle Tree的な役割	注意点
Certificate Transparency	証明書ログの包含確認・一貫性確認	ログ運営者、監視者、ブラウザなど周辺の仕組みも重要
Git	ファイル内容、tree、commitをハッシュで結びつける	BitcoinのMerkle Treeと完全に同一視しない
Rekor / Trillian系の透明性ログ	ソフトウェア署名や任意データの公開ログを検証しやすくする	ログの運用、監査、クライアント検証が重要
ブロックチェーン	取引や状態をrootへまとめ、検証しやすくする	合意形成、ノード検証、ネットワークの前提も必要

Merkle Treeは、データ構造としてはとても便利です。
しかし、それだけでシステム全体の安全性が決まるわけではありません。

たとえば、Certificate Transparencyでは、ログを誰が運用するのか、ブラウザや監視者がどう検証するのかが重要です。
Gitでは、ハッシュで履歴をたどれるとしても、リポジトリのアクセス制御や署名、レビュー運用は別の問題です。
ブロックチェーンでは、Merkle rootがあっても、チェーンの合意形成やフルノードによる検証が重要です。

この点は、情報セキュリティの観点で特に大切です。

Merkle Treeは「検証しやすくする部品」です。
しかし、rootを誰が信頼するのか、proofを誰が検証するのか、ログやチェーンをどう監視するのかまで含めて考える必要があります。

7.10 この章のまとめ

この章では、Merkle Treeがブロックチェーン以外でも使われることを整理しました。

BitcoinやEthereumで見てきたように、Merkle Treeはブロックチェーンの中で重要な役割を持ちます。
しかし、その本質は「暗号資産のための仕組み」ではなく、大量の記録をハッシュでまとめ、必要な部分だけ検証しやすくする仕組み です。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Merkle Treeはブロックチェーン専用ではない	公開ログやソフトウェア開発の文脈でも使われる
Certificate Transparencyでは証明書ログの監査に使われる	inclusion proofやconsistency proofが重要になる
Gitはハッシュでオブジェクトを結びつける	Merkle Treeと完全に同じではないが、近い発想を学べる
透明性ログではappend-only性が重要	過去の記録を保ったまま追記されているかを確認したい
Merkle Treeだけで安全になるわけではない	rootの信頼性、proofの検証、ログ運用、監査体制が必要になる

ここまでで、Merkle Treeの基本構造、Bitcoinでの使われ方、Ethereumでの違い、そしてブロックチェーン外での応用を見てきました。

次の章では、ここまでの内容を踏まえて、Merkle Treeでできること・できないこと を整理します。
特に、「含まれていることは確認できるが、そのデータ自体が正しいかまでは別問題」「rootをどこから信頼するかが重要」といった注意点を、情報セキュリティの観点から見ていきます。

8. Merkle Treeでできること・できないこと

この章では、ここまで見てきたMerkle Treeを、情報セキュリティの観点から整理します。
ポイントは、Merkle Treeが 大量のデータを効率よく確認するための強力な部品 である一方で、データそのものの正しさやrootの信頼性まで自動で保証するわけではない という点です。

前の章までで、Merkle Treeの基本構造、Merkle proof、Bitcoinでの使われ方、EthereumでのMerkle Patricia Trie、Certificate Transparencyのようなブロックチェーン外の応用を見てきました。

ここまで読むと、Merkle Treeはとても便利な仕組みに見えると思います。
実際、大量の記録を1つのrootにまとめ、必要な部分だけを使って確認できるという点はかなり強力です。

ただし、ここで一度立ち止まって、次の問いを整理しておきます。

• Merkle Treeで何を確認できるのか
• Merkle Treeだけでは何を確認できないのか
• rootをどこから信頼するのか
• ハッシュを使っていれば、それだけで安全と言えるのか
• 実装するときに、どのような点で間違いやすいのか

身近な例で考えると、Merkle Treeは「大量のレシートをまとめた箱に、あるレシートが含まれていたこと」を確認しやすくする仕組みに近いです。

しかし、そのレシートに書かれた金額が本当に正しいか、レシート自体が偽物ではないか、箱のまとめ値を誰が正しいものとして公開したのかまでは、別の確認が必要です。

つまり、Merkle Treeは万能の安全装置ではありません。
むしろ、何を保証していて、何を保証していないのかを分けて理解すること がとても大切です。

この章では、Merkle Treeでできること・できないことを、順番に整理していきます。

8.1 できること：あるデータが集合に含まれていることを確認しやすくする

Merkle Treeが得意なことの1つは、あるデータが、特定のrootに対応するデータ集合へ含まれていることを確認しやすくする ことです。

たとえば、1万件の取引があるブロックの中に、ある取引が含まれているかを確認したいとします。
普通に考えると、1万件の取引をすべて受け取り、1件ずつ探す必要がありそうです。

しかし、Merkle Treeを使うと、対象取引とMerkle proofを使って、rootまで再計算できます。
その結果がブロックヘッダなどに記録されたMerkle rootと一致すれば、「この取引は、このrootに対応する取引集合に含まれている」と確認できます。

Bitcoinのホワイトペーパーでも、フルノードを動かさない利用者が、ブロックヘッダとMerkle branchを使って、ある取引がブロックに含まれていることを確認するSPVの考え方が説明されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

また、Certificate Transparencyの仕様でも、Merkle audit pathによって、あるエントリが特定のMerkle Tree Hashに含まれることを確認できると説明されています。

参考: RFC 6962: Certificate Transparency
参考: RFC 9162: Certificate Transparency Version 2.0

ここで大切なのは、確認できるのが 「含まれていること」 だという点です。

確認したいこと	Merkle Treeで確認しやすいか	補足
この取引が、あるrootに対応する集合に含まれているか	確認しやすい	Merkle proofを使う
この証明書ログに、ある証明書が登録されているか	確認しやすい	Certificate Transparencyで重要
このファイルが、あるcommit風の構造に含まれているか	考え方として確認しやすい	Gitのようなハッシュ構造に近い
この取引の署名や残高が正しいか	Merkle Treeだけでは不十分	別途、取引検証が必要
このrootが本当に正しいrootか	Merkle Treeだけでは不十分	rootの入手元・合意・署名などが重要

Merkle Treeは、たくさんの記録の中から「この1件が含まれていたか」を確認しやすくする仕組みです。
ただし、その1件の中身が正しいかどうかは、別のルールで検証する必要があります。

8.2 できること：データの変更に気づきやすくする

Merkle Treeでは、葉のデータが変わると、その葉のハッシュが変わります。
すると、その親ノードのハッシュも変わり、さらに上のノードも変わり、最終的にはMerkle rootが変わります。

これは、会計ノートの1行をこっそり書き換えると、ページのチェック値、章のチェック値、ノート全体のチェック値が変わるようなイメージです。

NISTIR 8202でも、ブロックヘッダには前のブロックのハッシュや、ブロックデータのハッシュ表現、たとえばMerkle tree rootが含まれる場合があると説明されています。
また、ブロックがハッシュによってつながることで、過去のブロックの変更を検出しやすくなると説明されています。

参考: NISTIR 8202: Blockchain Technology Overview

ただし、ここでも「改ざん不可能」と言い切るのは避けた方がよいです。

Merkle Treeは、データが変わったことに気づきやすくする仕組みです。
実際に改ざんを防ぐには、rootをどこに保存するか、誰が検証するか、どのハッシュ関数を使うか、どのような合意形成を行うかなども関係します。

8.3 できること：全データを受け取らずに確認しやすくする

Merkle Treeの大きな利点は、全データを毎回受け取らなくても、必要な部分だけで検証しやすいことです。

たとえば、1024件の記録がある場合を考えます。
単純に全部を確認するなら、最大で1024件を見る必要があります。

一方、バランスのよいMerkle Treeであれば、対象の葉からrootまでの道筋は、おおよそ log2(1024) = 10 段です。
つまり、対象データと各段の隣のハッシュを使って、rootまでたどれるようになります。

記録件数	すべて見る場合の件数	Merkle proofで必要になる要素数の目安
8件	最大8件	約3個
1,024件	最大1,024件	約10個
1,048,576件	最大1,048,576件	約20個

もちろん、実際のproofサイズは木の作り方や実装によって変わります。
それでも、「全部を見る」のではなく、「rootまでの道筋だけを見る」という考え方は、Merkle Treeを理解するうえでとても重要です。

💡 豆知識
Merkle proofで必要な情報量は、データ件数そのものに比例して増えるのではなく、木の高さに近い形で増えます。
そのため、データがとても多い場面でも、必要な確認情報をかなり小さくできる場合があります。
BitcoinのSPVやCertificate Transparencyのaudit pathも、この考え方と関係しています。

8.4 できないこと：データそのものの正しさまでは保証しない

ここからは、Merkle Treeだけではできないことを見ていきます。

まず重要なのは、Merkle Treeが確認するのは、基本的に 「あるデータが、あるrootに対応する集合に含まれているか」 だという点です。

たとえば、会計ノートの中に次のような記録が含まれていたとします。

Aさんに返金 100,000円

Merkle proofを使えば、この記録があるrootに対応する記録集合に含まれていることは確認できるかもしれません。
しかし、その返金が本当に正当なものか、金額が正しいか、承認を受けているかまでは、Merkle Treeだけでは分かりません。

これはブロックチェーンでも同じです。

Bitcoinであれば、取引がブロックに含まれていることと、その取引が署名・UTXO・二重支払いなどのルールを満たすことは別です。
Bitcoinのホワイトペーパーでも、SPVでは取引がブロックに含まれていることをMerkle branchで確認できますが、受け取った警告に対応するためにはフルブロックを取得して確認する考え方が説明されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

この違いを、学習用コードで確認してみます。

# Merkle Treeが確認する「含まれていること」と、
# 業務ルールとしての「内容が正しいこと」は別である、という点を確認する学習用コードです。
# 実際のブロックチェーン取引検証を再現するものではありません。

import hashlib
from typing import List


def sha256_hex(text: str) -> str:
    """文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def hash_pair(left: str, right: str) -> str:
    """2つのハッシュを左から右の順番で連結し、親ノードのハッシュを作ります。"""
    return sha256_hex(left + right)


def merkle_root(records: List[str]) -> str:
    """記録一覧から、学習用のMerkle rootを作ります。"""
    if not records:
        raise ValueError("records must not be empty")

    # まず、各記録をleafとしてハッシュ化します。
    level = [sha256_hex(record) for record in records]

    # 1つのrootになるまで、隣同士をまとめていきます。
    while len(level) > 1:
        next_level = []

        # 2件ずつ処理します。
        for i in range(0, len(level), 2):
            left = level[i]

            # 奇数個の場合は、最後のハッシュを複製して扱います。
            right = level[i + 1] if i + 1 < len(level) else left
            next_level.append(hash_pair(left, right))

        level = next_level

    return level[0]


def is_business_rule_valid(record: str) -> bool:
    """
    会計ノートの業務ルールを、説明用にかなり単純化して確認します。

    ここでは、100,000円以上の返金には別途承認が必要という想定にし、
    文字列に「承認済み」が含まれていない場合は無効とします。
    """
    if "返金 100,000円" in record and "承認済み" not in record:
        return False

    return True


records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "Aさんに返金 100,000円",  # 集合には含まれるが、業務ルール上は問題がある想定
]

root = merkle_root(records)
target_record = records[3]

print("Merkle root:", root)
print("対象の記録:", target_record)
print("業務ルール上有効か:", is_business_rule_valid(target_record))

このコードでは、Aさんに返金 100,000円 という記録も、Merkle rootを作る対象に含まれています。
つまり、Merkle Treeの観点では、この記録は集合の一部です。

しかし、is_business_rule_valid() では、説明用に「100,000円以上の返金には承認済みの記載が必要」というルールを置いているため、この記録は業務ルール上は無効と判断されます。

ここで言いたいのは、次の点です。

Merkle Treeは、データが集合に含まれていることを確認しやすくします。
しかし、そのデータがルール上正しいかどうかは、別途検証する必要があります。

ブロックチェーンでも、Merkle proofだけで取引の妥当性がすべて分かるわけではありません。
署名、残高、二重支払い、手数料、スマートコントラクトの実行結果などは、別の検証ルールで確認する必要があります。

8.5 できないこと：rootそのものの信頼性は別問題

Merkle proofは、あくまで あるrootに対して データが含まれていることを示します。

ここで非常に重要なのが、そのrootをどこから信頼するのか という問題です。

たとえば、誰かが次のように言ってきたとします。

このMerkle rootは正しいものです。
このproofで、あなたの取引が含まれていることを確認できます。

このとき、proofの計算自体が合っていても、そのrootが攻撃者の作ったrootだったらどうでしょうか。
攻撃者が自分に都合のよいデータ集合からrootを作り、そのrootを「正しいrootです」と渡してきた場合、そのrootに対するproofは成功してしまう可能性があります。

つまり、Merkle proofを検証するときは、次の2つを分ける必要があります。

観点	説明
proofの検証	対象データとproofからrootを再計算し、一致するか確認する
rootの信頼	そのroot自体が、信頼できる場所から得られたものか確認する

Bitcoinでは、Merkle rootはブロックヘッダに含まれます。
しかし、ブロックヘッダ自体が正しいチェーン上のものか、十分なProof of Workが積み上がっているか、といった確認が別途重要になります。

参考: Bitcoin Developer Reference: Block Chain / Merkle Trees
参考: Bitcoin: A Peer-to-Peer Electronic Cash System

Certificate Transparencyでも、ログのMerkle Tree Hashをどのように監査し、過去のログと整合しているかを確認する仕組みが重要になります。
RFC 6962やRFC 9162では、inclusion proofだけでなく、append-only性を確認するconsistency proofも扱われています。

参考: RFC 6962: Certificate Transparency
参考: RFC 9162: Certificate Transparency Version 2.0

この点を、学習用コードで確認してみます。

# Merkle proofは「あるrootに対して」正しいかを確認するものです。
# root自体を攻撃者が差し替えた場合、そのrootに対するproofは成功してしまうことがあります。
# これはrootの入手元を信頼する必要がある、という点を確認する学習用コードです。

import hashlib
from typing import List, Tuple


def sha256_hex(text: str) -> str:
    """文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def hash_pair(left: str, right: str) -> str:
    """左右の順番を保ったまま2つのハッシュをまとめます。"""
    return sha256_hex(left + right)


def build_tree(records: List[str]) -> List[List[str]]:
    """記録一覧から、各階層のハッシュを持つ学習用Merkle Treeを作ります。"""
    if not records:
        raise ValueError("records must not be empty")

    tree = [[sha256_hex(record) for record in records]]

    while len(tree[-1]) > 1:
        current_level = tree[-1]
        next_level = []

        for i in range(0, len(current_level), 2):
            left = current_level[i]
            right = current_level[i + 1] if i + 1 < len(current_level) else left
            next_level.append(hash_pair(left, right))

        tree.append(next_level)

    return tree


def get_root(tree: List[List[str]]) -> str:
    """Merkle Treeのrootを返します。"""
    return tree[-1][0]


def get_proof(tree: List[List[str]], index: int) -> List[Tuple[str, str]]:
    """
    指定したleaf indexに対するMerkle proofを作ります。

    proofの各要素は、(方向, 隣のハッシュ) です。
    方向は、隣のハッシュがleft側にあるかright側にあるかを表します。
    """
    proof = []

    for level in tree[:-1]:
        is_right_node = index % 2 == 1
        sibling_index = index - 1 if is_right_node else index + 1

        if sibling_index >= len(level):
            sibling_hash = level[index]
        else:
            sibling_hash = level[sibling_index]

        direction = "left" if is_right_node else "right"
        proof.append((direction, sibling_hash))

        index //= 2

    return proof


def verify_proof(record: str, proof: List[Tuple[str, str]], expected_root: str) -> bool:
    """対象recordとproofからrootを再計算し、expected_rootと一致するか確認します。"""
    current_hash = sha256_hex(record)

    for direction, sibling_hash in proof:
        if direction == "left":
            current_hash = hash_pair(sibling_hash, current_hash)
        else:
            current_hash = hash_pair(current_hash, sibling_hash)

    return current_hash == expected_root


honest_records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "印刷代 800円",
]

malicious_records = [
    "会場費 5,000円",
    "飲み物代 1,200円",
    "備品代 2,000円",
    "Aさんに返金 100,000円",
]

honest_tree = build_tree(honest_records)
malicious_tree = build_tree(malicious_records)

honest_root = get_root(honest_tree)
malicious_root = get_root(malicious_tree)

# 攻撃者が、自分に都合のよい記録に対するproofを作る想定です。
target_record = malicious_records[3]
malicious_proof = get_proof(malicious_tree, 3)

print("正しいrootに対して検証:", verify_proof(target_record, malicious_proof, honest_root))
print("攻撃者が作ったrootに対して検証:", verify_proof(target_record, malicious_proof, malicious_root))

このコードでは、Aさんに返金 100,000円 という記録は、正しい記録集合には含まれていません。
そのため、正しいrootに対して検証すると失敗します。

一方で、攻撃者がその記録を含む別の集合からrootを作った場合、その攻撃者のrootに対してはproofが成功します。

ここでのポイントは、次の通りです。

Merkle proofの検証が成功しても、それは「そのrootに対して含まれている」ことを示しているだけです。
そのroot自体を信頼してよいかは、別の仕組みで確認する必要があります。

ブロックチェーンでは、rootがブロックヘッダに入り、そのブロックヘッダがチェーンや合意形成の中で扱われます。
透明性ログでは、rootの公開、監査、consistency proofなどが重要になります。

8.6 できないこと：ハッシュは暗号化ではない

Merkle Treeではハッシュ関数を使います。
そのため、「ハッシュを使っているなら、中身は秘密になる」と誤解してしまうことがあります。

しかし、ハッシュは暗号化とは違います。

暗号化は、鍵を使ってデータを元に戻せる形で隠す技術です。
一方、ハッシュは入力から固定長の値を作る一方向の処理であり、基本的には元のデータへ戻すためのものではありません。

技術	ざっくりした役割	元に戻せるか
暗号化	データを読めない形に変換する	鍵があれば戻せる
ハッシュ	データの指紋のような値を作る	基本的には戻せない
Merkle Tree	ハッシュを木構造にして、集合の確認をしやすくする	データを秘密にする仕組みではない

ただし、「ハッシュから元データを戻せない」といっても、元データの候補がとても少ない場合には、候補を総当たりして一致するものを探せる場合があります。

たとえば、入力が「出席」か「欠席」だけなら、両方をハッシュ化して比べれば、どちらだったか推測できてしまいます。

# ハッシュは暗号化ではない、という点を確認する学習用コードです。
# 候補が少ない場合、候補を全部試すことで元データを推測できる場合があります。

import hashlib


def sha256_hex(text: str) -> str:
    """文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


# もとの値は秘密にしたい状態だとします。
# しかし、候補が「出席」「欠席」「遅刻」くらいしかない場合を考えます。
secret_status = "欠席"
status_hash = sha256_hex(secret_status)

candidates = ["出席", "欠席", "遅刻"]

print("公開されているハッシュ:", status_hash)

for candidate in candidates:
    # 候補を1つずつハッシュ化し、公開されているハッシュと一致するか確認します。
    if sha256_hex(candidate) == status_hash:
        print("推測できた候補:", candidate)

このコードでは、元データそのものを直接復号しているわけではありません。
しかし、候補が少ないため、候補をハッシュ化して一致するか確認できてしまいます。

このため、Merkle Treeやハッシュを使うときに、データが自動的に秘密になる と考えるのは危険です。

💡 豆知識
ハッシュは「元に戻しにくい」性質を持ちますが、「何でも秘密にできる」わけではありません。
入力候補が少ない場合や、入力形式が予想しやすい場合は、候補を試して一致するハッシュを探せることがあります。
そのため、プライバシーを守る目的では、ハッシュだけでなく、設計全体を慎重に考える必要があります。

8.7 できないこと：順序やルールの違いを吸収してくれるわけではない

Merkle Treeでは、どの順番でデータを並べるか、どのようにハッシュ化するか、奇数個のデータをどう扱うかが重要です。

同じデータ集合でも、順番が違えばMerkle rootは変わります。
また、葉のハッシュと内部ノードのハッシュをどう区別するか、文字列化やエンコードをどうするかによっても結果が変わります。

Bitcoinでは、取引のTXIDを使ってMerkle rootを作る手順が仕様として決まっています。
奇数個のハッシュがある場合には最後のハッシュを複製して処理する点も、Bitcoin Developer Referenceで説明されています。

参考: Bitcoin Developer Reference: Merkle Trees

一方、Certificate Transparencyでは、leaf hashとnode hashでprefixを変えるdomain separationが仕様に含まれています。
RFC 9162では、葉と内部ノードで異なるprefixを付けてハッシュすることで、second preimage attackへの耐性に関係する設計が説明されています。

参考: RFC 9162: Certificate Transparency Version 2.0

つまり、Merkle Treeは考え方としてはシンプルですが、実装時には次のような点をそろえる必要があります。

実装上の観点	注意点
データの順序	同じデータでも順番が変わるとrootが変わる
ハッシュ関数	SHA-256など、仕様に合ったものを使う必要がある
エンコード	文字列、バイト列、整数などの扱いを統一する必要がある
奇数個の処理	最後を複製するのか、別ルールにするのかを決める必要がある
leafと内部ノードの区別	domain separationが必要になる設計もある
rootの保存場所	rootをどこに保存し、どう信頼するかを決める必要がある

ここを曖昧にすると、同じデータを使っているつもりでも、実装ごとに違うrootが出てしまいます。

記事内の学習用コードでは、理解しやすさを優先して単純なルールを使っています。
しかし、実際のプロトコルを扱う場合は、必ず対象プロトコルの仕様に合わせる必要があります。

8.8 情報セキュリティの観点で見るMerkle Treeの役割

情報セキュリティの観点で見ると、Merkle Treeは主に 完全性 や 検証可能性 に関係します。

完全性とは、データが意図せず、または不正に変更されていないことを確認できる性質です。
検証可能性とは、第三者や別の参加者が、与えられた情報を使って正しさを確認できる性質です。

Merkle Treeは、この2つを支える部品として使われます。

セキュリティ上の観点	Merkle Treeが役立つこと	Merkle Treeだけでは足りないこと
完全性	データ変更がrootに反映されやすい	root自体の保護・公開方法が必要
包含証明	あるデータが集合に含まれることを示しやすい	データ内容の妥当性検証は別途必要
軽量検証	全データを受け取らずに確認しやすい	フル検証と同じ安全性とは限らない
監査	ログや記録の一部を効率よく確認しやすい	ログ運用者の監視やconsistency proofが必要な場合がある
プライバシー	データそのものを送らずに済む場面がある	ハッシュだけで秘密が守られるとは限らない

このように見ると、Merkle Treeはセキュリティ対策の「全部」ではなく、検証を効率化するための重要な部品 だと分かります。

たとえば、ブロックチェーンでは、Merkle rootだけでなく、次のような仕組みと組み合わさります。

• ハッシュ関数
• デジタル署名
• ブロックヘッダ
• P2Pネットワーク
• コンセンサス
• フルノードによる取引検証
• 軽量クライアントによるMerkle proof検証

Certificate Transparencyでは、次のような仕組みと組み合わさります。

• 公開ログ
• Signed Certificate Timestamp
• inclusion proof
• consistency proof
• monitorやauditorによる監査

つまり、Merkle Treeは「安全性を支える部品」ですが、「これだけ入れれば全部安全」というものではありません。

8.9 実装・説明で気をつけたいこと

Merkle Treeを実装したり説明したりするときには、次のような表現に注意するとよいです。

避けたい表現	より丁寧な表現
Merkle Treeがあれば改ざんできない	Merkle Treeにより、変更を検出しやすくなる
Merkle proofがあれば取引が正しいと分かる	Merkle proofで分かるのは、特定rootに対する包含関係
Merkle rootだけで全取引を検証できる	root、対象データ、proof、rootの信頼性が必要
ハッシュを使っているので秘密になる	ハッシュは暗号化ではなく、入力候補が少ないと推測される場合がある
BitcoinとEthereumは同じMerkle Treeを使う	BitcoinとEthereumでは構造や目的が異なる

特に、初学者向けの記事では「ざっくり分かりやすくすること」と「雑に言い切らないこと」のバランスが大切です。

たとえば、次のように表現すると、読みやすさと正確さを両立しやすくなります。

Merkle Treeは、大量のデータを1つのrootにまとめ、必要な部分だけを使って含まれていることを確認しやすくする仕組みです。
ただし、そのデータ自体が正しいか、rootを信頼してよいかまでは、別の仕組みで確認する必要があります。

このように、できることとできないことを分けて書くと、読者が過度に期待したり、逆に仕組みを軽く見たりすることを避けやすくなります。

8.10 この章のまとめ

この章では、Merkle Treeでできること・できないことを整理しました。

Merkle Treeは、大量のデータを1つのrootにまとめ、必要な部分だけを使って検証しやすくする仕組みです。
特に、あるデータが特定のrootに対応する集合へ含まれていることを確認する場面で役立ちます。

一方で、Merkle Treeだけでデータの妥当性やrootの信頼性まで保証できるわけではありません。
そのため、実際のシステムでは、署名、取引検証、合意形成、公開ログ、監査、rootの配布方法などと組み合わせて使われます。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Merkle Treeは包含証明に強い	あるデータが特定rootに対応する集合へ含まれていることを確認しやすい
データ変更に気づきやすい	データが変わると、leafからrootまでのハッシュが変わる
全データを受け取らずに検証しやすい	Merkle proofにより、必要な道筋だけを確認できる
データ自体の正しさは別問題	取引の署名、残高、業務ルールなどは別途検証が必要
rootの信頼性が重要	proofは「あるrootに対して」正しいだけで、root自体の正しさは別問題
ハッシュは暗号化ではない	データを秘密にする仕組みとして過信しない
実装ルールをそろえる必要がある	順序、エンコード、ハッシュ関数、奇数個処理などでrootが変わる

ここまでで、Merkle Treeの基本的な仕組みと、実際に使うときの注意点がかなり見えてきました。

次の章では、ここまでの内容をもとに、Merkle Treeについてよくある誤解 を整理します。
特に、「Merkle Treeは暗号化なのか」「Merkle rootだけで全部検証できるのか」「BitcoinとEthereumで同じように考えてよいのか」といった、初学者がつまずきやすい点をまとめて確認します。

9. よくある誤解

この章では、ここまで見てきた内容をもとに、Merkle Treeについてよくある誤解を整理します。
ポイントは、Merkle Treeを「何でも正しくしてくれる魔法」ではなく、大量のデータを要約し、必要な部分を検証しやすくするための部品 として見ることです。

ここまでで、Merkle Treeの基本構造、Merkle proof、Bitcoinでの使われ方、Ethereumでの違い、ブロックチェーン外での応用、そしてできること・できないことを見てきました。

Merkle Treeはとても便利な仕組みです。
ただし、便利だからこそ、少し大きく言いすぎた説明も見かけます。

たとえば、次のような説明です。

• Merkle Treeはデータを暗号化する仕組み
• Merkle rootがあれば、取引が正しいことまで分かる
• Merkle proofがあれば、ブロックチェーン全体の正しさまで分かる
• BitcoinとEthereumのMerkle構造は同じ
• ハッシュを使っているので、絶対に改ざんできない

どれも、まったく無関係な説明ではありません。
しかし、そのまま受け取ると少し誤解が残ります。

この章では、初学者がつまずきやすいポイントを1つずつ整理し、より正確な見方に直していきます。

9.1 誤解1：Merkle Treeはデータを暗号化する仕組みである

まず一つ目の誤解は、Merkle Treeを 暗号化の仕組み と考えてしまうことです。

Merkle Treeではハッシュ関数を使います。
そのため、「暗号っぽい」「データを守っている」という印象を持ちやすいかもしれません。

ただし、Merkle Treeの主な役割は、データを読めない形に隠すことではありません。

観点	暗号化	Merkle Tree
主な目的	データの中身を読めないようにする	データの改変や包含関係を確認しやすくする
復元	正しい鍵があれば元に戻せる	ハッシュ値から元データを復元する仕組みではない
使う場面	秘密にしたい通信や保存	大量データの要約、包含証明、整合性確認
身近なイメージ	鍵付きの封筒	書類の指紋を束ねた目次

たとえば、レシートの内容を暗号化すれば、鍵を持っていない人には中身を読みにくくできます。
一方で、レシートをハッシュ化してMerkle Treeに入れても、Merkle Tree自体がレシートの内容を秘密にしてくれるわけではありません。

Merkle Treeは、どちらかというと「このレシートが、ある記録の束に含まれていたか」「途中で別の内容に変わっていないか」を確認しやすくする仕組みです。

参考: NISTIR 8202: Blockchain Technology Overview

💡 豆知識
ハッシュ関数は暗号技術の文脈でよく使われますが、ハッシュ化と暗号化は同じではありません。
暗号化は、鍵を使って元データへ戻せるように設計されることが多いです。
一方、ハッシュは基本的に、元データへ戻すためではなく、データの要約値を作るために使われます。

9.2 小さなコードで見る：ハッシュ値から元データは戻せない

ここで、ハッシュと暗号化の違いを、かなり小さなコードで見てみます。

次のコードは、入力文字列からSHA-256ハッシュを作るだけの学習用コードです。
ハッシュ値は出力できますが、そのハッシュ値だけから元の文字列を復元する処理はありません。

# ハッシュ化と暗号化を混同しないための学習用コードです。
# このコードは、入力文字列からSHA-256ハッシュを作るだけです。
# ハッシュ値から元の文字列を復元する処理はありません。

import hashlib


def sha256_hex(text: str) -> str:
    """
    入力文字列をSHA-256でハッシュ化し、16進数文字列として返します。

    注意:
    - これは暗号化ではありません。
    - 復号用の鍵もありません。
    - ハッシュ値から元のtextを取り出すことを目的にした処理ではありません。
    """
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


record = "2026-07-05, 備品代, 2000円"

digest = sha256_hex(record)

print("元の記録:")
print(record)
print()

print("ハッシュ値:")
print(digest)
print()

print("このハッシュ値だけを見ても、元の記録の内容を復元できるわけではありません。")

このコードでは、record の内容からハッシュ値を作っています。
しかし、ハッシュ値から 2026-07-05, 備品代, 2000円 という元の文字列を取り出す処理はありません。

もちろん、入力候補がとても少ない場合は、候補を総当たりして一致するハッシュを探すことは考えられます。
そのため、「ハッシュにしたから中身を絶対に知られない」と考えるのも危険です。

ここで押さえたいのは、次の点です。

Merkle Treeは、データを秘密にするための仕組みではありません。
データの要約値を使って、整合性や包含関係を確認しやすくする仕組みです。

9.3 誤解2：Merkle rootだけあれば、対象データが含まれていると分かる

次の誤解は、Merkle rootだけあれば、ある取引が含まれているか分かる というものです。

Merkle rootは、たしかにデータ集合全体を代表する大切な値です。
Bitcoinでは、ブロック内の全取引からMerkle rootが作られ、ブロックヘッダに含まれます。

参考: Bitcoin Developer Reference: Block Chain / Merkle Trees

ただし、Merkle rootだけを見ても、対象データが含まれているかは確認できません。
確認するには、少なくとも次の情報が必要です。

必要なもの	役割
対象データ	確認したい取引や記録そのもの
Merkle proof / Merkle branch	対象データからrootまで再計算するための周辺ハッシュ
Merkle root	最終的に一致するか確認する基準
ハッシュ関数や構築ルール	どのようにハッシュを組み合わせるかのルール

つまり、Merkle rootは「答え合わせに使う最終的な基準」です。
しかし、答え合わせをするには、そこへたどるための道筋であるMerkle proofも必要です。

身近な例で言えば、Merkle rootは「箱全体に貼られた封印シール」のようなものです。
封印シールだけを見ても、特定のレシートが箱に入っていたかは分かりません。
確認したいレシートと、そのレシートが箱全体の封印につながる道筋が必要になります。

9.4 誤解3：Merkle proofがあれば、取引そのものが正しいことまで分かる

Merkle proofは、あるデータが特定のrootに対応する集合へ含まれていることを確認するために使えます。
ただし、それは データの内容が業務ルールやプロトコル上も正しい ことを直接保証するわけではありません。

たとえば、BitcoinのSPVでは、ブロックヘッダとMerkle branchを使って、ある取引がブロックに含まれていることを確認できます。
Bitcoinホワイトペーパーでも、ブロックヘッダとMerkle branchにより、取引があるブロックに含まれていることを確認する考え方が説明されています。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

しかし、取引が「含まれている」ことと、その取引が「自分にとって安全に受け入れられる」ことは別です。

確認したいこと	Merkle proofで分かるか	補足
その取引が、あるrootに対応する集合に含まれるか	確認できる	proofとrootが一致すれば確認できる
その取引の署名が正しいか	それだけでは分からない	署名検証が別途必要
二重支払いではないか	それだけでは不十分	チェーンやUTXOなどの検証が必要
そのrootを含むブロックが正当か	proofだけでは不十分	ブロックヘッダやチェーンの検証が必要
そのチェーンをどこまで信頼できるか	proofだけでは不十分	コンセンサスや確認数などの話になる

ここはかなり大切です。

Merkle proofは、あくまで「このデータは、このrootに対して含まれていると言えるか」を確認するものです。
データの意味や正当性、チェーン全体の安全性まで、全部まとめて保証するわけではありません。

💡 豆知識
Merkle proofは「包含証明」と説明されることがあります。
ここでの「証明」は、あるrootに対してデータが含まれていることを示す、という意味です。
取引の署名、残高、スマートコントラクトの実行結果、チェーンの正当性まで一気に証明するものではありません。

9.5 小さなコードで見る：rootだけでは検証できない

次のコードでは、Merkle rootだけを持っていても、対象データの包含を確認できないことを簡単に確認します。

実際のプロトコルでは、proofの形式や検証ルールが仕様で定められます。
ここでは、「rootだけでは道筋がない」という点を理解するための学習用コードです。

# Merkle rootだけでは、対象データが含まれるか確認できないことを理解するための学習用コードです。
# 実際のBitcoinやCertificate Transparencyのproof形式を再現するものではありません。

def verify_with_root_only(target_data: str, merkle_root: str) -> bool:
    """
    Merkle rootだけを使って、target_dataの包含を確認しようとする関数です。

    しかし、Merkle Treeでは、target_dataからrootまで再計算するために
    隣のハッシュや左右の位置情報が必要になります。

    そのため、この関数では正しい検証ができません。
    """
    print("確認したいデータ:", target_data)
    print("与えられたMerkle root:", merkle_root)
    print("しかし、rootまでの道筋となるMerkle proofがありません。")
    print("この情報だけでは、対象データが含まれていたか判断できません。")

    # rootだけでは検証できないため、常にFalseを返します。
    return False


target = "tx3: C -> D 500円"
root = "dummy_merkle_root"

result = verify_with_root_only(target, root)

print("検証結果:", result)

このコードは少し極端ですが、考え方としては重要です。

Merkle rootだけでは、対象データからrootを再計算できません。
そのため、実際にはMerkle proof、つまり隣のハッシュや左右の順番が必要になります。

9.6 誤解4：BitcoinとEthereumのMerkle構造は同じである

次の誤解は、BitcoinとEthereumで同じMerkle Treeが使われている、と考えてしまうことです。

Bitcoinでは、ブロック内の取引からMerkle rootを作り、そのrootをブロックヘッダに入れる構造が代表的です。
Bitcoin Developer Referenceでは、ブロックヘッダにMerkle root hashが含まれ、これはブロック内の全取引から導かれると説明されています。

参考: Bitcoin Developer Reference: Block Chain

一方で、Ethereumでは、単純なMerkle Treeだけではなく Merkle Patricia Trie が使われます。
Ethereum公式ドキュメントでは、Ethereumの実行レイヤーのMerkle trieはMerkle Patricia Trieであり、ブロックヘッダには stateRoot、transactionsRoot、receiptsRoot が含まれると説明されています。

参考: Ethereum Documentation: Merkle Patricia Trie

両者をざっくり比較すると、次のようになります。

観点	Bitcoin	Ethereum
代表的な構造	取引一覧から作るMerkle Tree	状態・取引・レシートを扱うMerkle Patricia Trie
rootの例	Merkle root	stateRoot、transactionsRoot、receiptsRoot
主な対象	ブロック内の取引	アカウント状態、取引、実行結果など
説明するときの注意	TXIDからrootを作る流れが中心	key-value構造や状態管理の文脈が重要

どちらも「ハッシュを使った木構造」という意味では関係があります。
しかし、同じものとして説明すると、Ethereumの状態管理やTrie構造が見えにくくなります。

本記事では、次のように分けて扱います。

Bitcoinでは、ブロック内の取引をまとめるMerkle Treeを中心に見る。
Ethereumでは、状態や取引、レシートを扱うMerkle Patricia Trieとして見る。

9.7 誤解5：ハッシュを使っているので絶対に改ざんできない

Merkle Treeでは、データが少しでも変わるとハッシュが変わり、rootまで影響します。
そのため、データの変更に気づきやすくなります。

ただし、ここから「絶対に改ざんできない」と言い切るのは強すぎます。

より丁寧には、次のように説明するのが安全です。

Merkle Treeは、データが変わったときにrootの不一致として検知しやすくする仕組みです。
ただし、root自体を誰が信頼できる形で持っているのか、どのハッシュ関数を使うのか、どのような構築ルールなのかによって安全性は変わります。

たとえば、悪意ある人がデータもrootもまとめて差し替えた場合、受け取る側が正しいrootを知らなければ、差し替えに気づけない可能性があります。

状況	Merkle Treeで気づけるか
正しいrootを持っていて、データだけが変わった	気づきやすい
データとrootが両方差し替えられた	正しいrootを別途知らないと気づきにくい
弱いハッシュ関数を使っている	安全性に問題が出る可能性がある
実装ルールが参加者ごとに違う	同じデータでもrootが一致しない可能性がある

この点は、ブロックチェーンでも透明性ログでも重要です。
rootやブロックヘッダ、ログのcheckpointなどを、どのように信頼できる形で共有するかが大切になります。

9.8 誤解6：データの順番やエンコードは気にしなくてよい

Merkle Treeでは、データの順番やエンコードも重要です。

同じ記録を使っていても、順番が変わればMerkle rootが変わることがあります。
また、文字列の作り方やバイト列への変換方法が違っても、ハッシュ値が変わります。

身近な例で言えば、同じレシート4枚でも、束ねる順番が違うと、目次の作り方が変わるようなものです。

Bitcoin Developer Referenceでも、Merkle rootは取引IDを順番に並べ、ペアごとにハッシュして作る流れとして説明されています。
つまり、取引の順序はrootの計算に関係します。

参考: Bitcoin Developer Reference: Merkle Trees

実装時に気をつけるポイントを整理すると、次のようになります。

注意点	なぜ重要か
データの順序	左右や並び順が変わるとrootが変わる
エンコード	文字列・バイト列の変換方法が違うとハッシュが変わる
ハッシュ関数	SHA-256なのか、二重SHA-256なのかなどで結果が変わる
奇数個の処理	最後を複製するのか、別ルールにするのかでrootが変わる
葉と内部ノードの区別	CTのようにprefixを付ける仕様では重要になる

RFC 6962やRFC 9162のCertificate Transparencyでは、葉と内部ノードで異なるprefixを付けてハッシュする設計が説明されています。
これは、単に値を連結してハッシュすればよい、という単純な話ではないことを示しています。

参考: RFC 6962: Certificate Transparency
参考: RFC 9162: Certificate Transparency Version 2.0

9.9 小さなコードで見る：順番が違うとMerkle rootも変わる

次のコードでは、同じ4件の記録を使っていても、順番が違うとMerkle rootが変わることを確認します。

これは、Merkle Treeでは左右の順番やデータの並びが重要であることを理解するための学習用コードです。

# Merkle Treeでは、データの順番がrootに影響することを確認する学習用コードです。
# 実際のBitcoinの二重SHA-256やバイト順の扱いを再現するものではありません。

import hashlib
from typing import List


def sha256_hex(text: str) -> str:
    """入力文字列をSHA-256でハッシュ化し、16進数文字列として返します。"""
    return hashlib.sha256(text.encode("utf-8")).hexdigest()


def hash_pair(left: str, right: str) -> str:
    """
    2つのハッシュを左→右の順に連結して、親ノードのハッシュを作ります。

    注意:
    - leftとrightの順番を入れ替えると、通常は別のハッシュになります。
    - そのため、Merkle proofでも左右の位置情報が重要になります。
    """
    return sha256_hex(left + right)


def merkle_root(records: List[str]) -> str:
    """
    記録一覧からMerkle rootを作る学習用関数です。

    処理の流れ:
    1. 各記録をleaf hashにする
    2. 2つずつ組にして親ノードを作る
    3. 奇数個の場合は最後のハッシュを複製する
    4. rootが1つになるまで繰り返す
    """
    if not records:
        raise ValueError("records must not be empty")

    level = [sha256_hex(record) for record in records]

    while len(level) > 1:
        next_level = []

        for i in range(0, len(level), 2):
            left = level[i]

            # 奇数個の場合は、最後のハッシュを複製してペアにします。
            right = level[i + 1] if i + 1 < len(level) else left

            next_level.append(hash_pair(left, right))

        level = next_level

    return level[0]


records_a = [
    "tx1: A -> B 100円",
    "tx2: B -> C 200円",
    "tx3: C -> D 300円",
    "tx4: D -> E 400円",
]

# 同じ記録を使っていますが、順番だけを変えています。
records_b = [
    "tx2: B -> C 200円",
    "tx1: A -> B 100円",
    "tx3: C -> D 300円",
    "tx4: D -> E 400円",
]

root_a = merkle_root(records_a)
root_b = merkle_root(records_b)

print("root A:", root_a)
print("root B:", root_b)
print("rootは同じですか？", root_a == root_b)

このコードでは、records_a と records_b に含まれる記録は同じです。
しかし、最初の2件の順番だけを入れ替えています。

実行すると、通常はMerkle rootが異なります。

ここから分かるのは、Merkle Treeでは「何が含まれているか」だけでなく、「どの順番で並べ、どのようにハッシュを組み合わせるか」も重要だということです。

9.10 誤解7：Merkle Treeを使えば、保存容量が必ず小さくなる

Merkle Treeは、全データを毎回送らずに検証しやすくするために役立ちます。
そのため、「Merkle Treeを使えば保存容量が必ず小さくなる」と考えたくなるかもしれません。

しかし、少し注意が必要です。

Merkle Treeを使うと、rootや中間ノード、proofなどの情報を扱います。
用途によっては、全データに加えて木構造の情報も保存するため、単純に保存量が減るとは限りません。

観点	説明
検証に使うデータ量	対象データとproofだけで済むため小さくしやすい
全体を保持する側の保存量	データ本体に加えて、中間ハッシュを保存する場合がある
再計算する場合	中間ノードを保存しない代わりに、必要に応じて再計算することもある
用途による違い	ブロックチェーン、透明性ログ、データベースなどで設計が異なる

Bitcoinホワイトペーパーでは、古いブロックで使われた取引について、Merkle Treeの枝を切り詰めることでディスク容量を節約できる考え方が説明されています。
ただし、これはBitcoinのブロック構造や用途に関係する説明であり、Merkle Treeを使えばどんな場面でも保存量が自動的に減る、という意味ではありません。

参考: Bitcoin: A Peer-to-Peer Electronic Cash System

ここでは、次のように理解するのがよいです。

Merkle Treeは、特定データの検証に必要な情報量を小さくしやすい仕組みです。
ただし、システム全体の保存容量が必ず減るかどうかは、何を保存し、何を再計算し、どのように運用するかによります。

9.11 誤解8：Merkle Treeはブロックチェーン専用の仕組みである

最後の誤解は、Merkle Treeをブロックチェーン専用の仕組みだと思ってしまうことです。

たしかに、BitcoinやEthereumを学ぶと、Merkle TreeやMerkle rootという言葉をよく見かけます。
しかし、Merkle Treeはブロックチェーンだけのものではありません。

第7章で見たように、Certificate Transparencyでは、公開ログを監査しやすくするためにbinary Merkle Hash Treeが使われます。
RFC 6962では、Certificate Transparencyのログが効率的な監査のためにMerkle Hash Treeを使うと説明されています。

参考: RFC 6962: Certificate Transparency

また、Gitのように、内容に基づくハッシュでオブジェクトを結びつける仕組みもあります。
GitはBitcoinのMerkle Treeと同じ構造そのものではありませんが、ファイル内容やディレクトリ構造、commitをハッシュでつなぐという点で、近い考え方を学ぶ例になります。

参考: Git Book: Git Internals - Git Objects

つまり、Merkle Treeは、ブロックチェーンを理解するための重要な部品であると同時に、より広く 大量の記録を検証しやすくするためのデータ構造 として見ることができます。

9.12 よくある誤解の整理表

ここまでの内容を表にまとめます。

よくある誤解	より丁寧な見方
Merkle Treeは暗号化である	暗号化ではなく、ハッシュで要約・検証しやすくする仕組み
Merkle rootだけで包含を確認できる	対象データとMerkle proofが必要
Merkle proofがあれば取引自体も正しい	proofで分かるのは、特定rootに対する包含関係
BitcoinとEthereumのMerkle構造は同じ	EthereumではMerkle Patricia Trieなど派生構造が使われる
ハッシュを使えば絶対に改ざんできない	改変を検知しやすくするが、rootの信頼性や実装に依存する
順番やエンコードは気にしなくてよい	並び順、左右、バイト表現、ハッシュ関数でrootが変わる
Merkle Treeを使えば保存容量が必ず減る	検証データを小さくしやすいが、全体の保存設計による
ブロックチェーン専用である	Certificate Transparencyなど、ブロックチェーン外でも使われる

9.13 この章のまとめ

この章では、Merkle Treeについてよくある誤解を整理しました。

Merkle Treeは、大量のデータを効率よく検証するための便利な仕組みです。
ただし、何でも保証してくれる万能な仕組みではありません。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Merkle Treeは暗号化ではない	データを秘密にするのではなく、要約と検証に使う
rootだけでは包含を確認できない	対象データとMerkle proofが必要
proofはデータの意味まで保証しない	取引の妥当性やチェーンの正当性は別の検証が必要
BitcoinとEthereumでは構造が違う	BitcoinのMerkle TreeとEthereumのMerkle Patricia Trieを分けて考える
「絶対安全」とは言わない	rootの信頼性、ハッシュ関数、実装ルールに依存する
順番やエンコードが重要	同じデータでも構築ルールが違えばrootは変わる
ブロックチェーン外でも使われる	透明性ログやソフトウェアサプライチェーンでも重要な考え方になる

Merkle Treeを正しく理解するには、「何ができるか」だけでなく、「何はできないか」もセットで見ることが大切です。

次の章では、ここまでの基本を踏まえて、Merkle Treeに関連する最近の動向を見ていきます。
特に、EthereumのVerkle Tree、透明性ログ、ソフトウェアサプライチェーンの検証など、Merkle Treeの考え方がどのように広がっているのかを整理します。

10. 最近の動向

この章では、Merkle Treeそのものの基本から少し視野を広げて、最近どのような場面で関連する考え方が使われているのかを整理します。
ポイントは、Merkle Treeを「昔からあるブロックチェーンの部品」としてだけではなく、大量の記録を検証しやすくするための土台として見ることです。

ここまでの章では、Merkle Treeの基本構造、Merkle proof、Bitcoinでの使われ方、EthereumのMerkle Patricia Trie、Certificate Transparencyなどを見てきました。

ここまで読むと、Merkle Treeは少し古典的な仕組みに見えるかもしれません。
実際、Merkle Treeの考え方自体は新しいものではありません。

しかし、最近のブロックチェーンやセキュリティの文脈でも、Merkle Treeやその周辺の考え方はまだ重要です。

特に、次のような流れがあります。

最近の動向	ざっくりした内容	Merkle Treeとの関係
EthereumのVerkle Tree	Ethereumの状態証明を小さくし、stateless clientへ近づけるための構造	Merkle Treeの発想を、vector commitmentと組み合わせて発展させる
Stateless client	ノードが巨大な状態データをすべて持たなくても検証しやすくする考え方	rootとwitnessを使って必要な状態だけを検証する
透明性ログの広がり	証明書、ソフトウェア、AIモデルなどの記録を公開ログに残す	inclusion proofやconsistency proofでログを検証する
ソフトウェアサプライチェーン検証	署名、ビルド、リリース情報を検証可能なログに残す	改ざんを検知しやすいログとしてMerkle系の構造を使う
Merkle Tree Certificates	証明書と公開ログをより強く統合しようとする提案	証明書がログに含まれることを証明書の構成要素として扱う
IoTや監査ログの軽量検証	ブロックチェーンを使わずに、ログの改ざん検知を軽く行う研究	Merkle rootやinclusion proofを監査ログに応用する

この章では、これらを「すべて詳しく理解する」ことよりも、Merkle Treeの考え方がどの方向へ広がっているのかをつかむことを目標にします。

10.1 EthereumではVerkle Treeが注目されている

Ethereumの文脈で、Merkle Treeに関連する最近の大きな話題が Verkle Tree です。

Verkle Treeは、名前からも分かるように、Vector commitment と Merkle Tree を組み合わせたような考え方として説明されます。
Ethereum公式ロードマップでは、Verkle Treeは、Ethereumノードが大量の状態データを保存し続けなくても、ブロックを検証できるようにするためのデータ構造として説明されています。

参考: Ethereum Roadmap: Verkle Trees

ここで大切なのは、Verkle Treeを「Merkle Treeの完全な置き換え」と雑に見るのではなく、より小さな証明を作りやすくするための発展形として見ることです。

Ethereumでは、アカウント残高、nonce、コントラクトのストレージなど、非常に多くの状態データを扱います。
現在のEthereumクライアントは、状態データをローカルに持ち、ブロック内の取引を実行し、計算後のstate rootがブロック提案者の示すrootと一致するかを確認します。

Ethereum公式のVerkle Tree解説でも、現在のPatricia Merkle Trieでは、ブロック検証のために大きな状態データへアクセスする必要があること、Verkle Treeによって小さなwitnessを使った検証へ近づけることが説明されています。

参考: Ethereum Roadmap: Verkle Trees

身近な例で言うと、巨大な会計台帳を毎回すべて持ち歩くのではなく、必要なページと、そのページが台帳全体に含まれていることを示す証明だけを持って確認できるようにしたい、という方向です。

ただし、ここで注意したいのは、Verkle TreeがすでにEthereum mainnetで完全に使われている、と断定しないことです。

Ethereum公式のstatelessnessページでは、weak statelessnessは研究が進んでいる一方で、Verkle TreesやProposer-builder separationなどの前提が必要であり、Ethereum mainnetへの導入は数年先の可能性があると説明されています。

参考: Ethereum Roadmap: Statelessness, state expiry and history expiry

また、EIP-6800ではEthereumの状態をunified Verkle treeで扱う提案がまとめられていますが、2026年7月時点でEIPページ上の状態は Stagnant と表示されています。

参考: EIP-6800: Ethereum state using a unified verkle tree

そのため、記事では次のように書くのが安全です。

Ethereumでは、将来的に状態証明を小さくし、stateless clientへ近づけるための構造としてVerkle Treeが検討されています。
ただし、導入状況や仕様は今後変わる可能性があるため、最新情報はEthereum公式ロードマップやEIPを確認する必要があります。

💡 豆知識
Verkle Treeの Verkle は、Vector commitment と Merkle Tree を合わせた名前として説明されます。
「Merkle Treeより少し名前が変わっただけ」と思うと見落としやすいですが、目的は主に証明サイズを小さくし、状態検証を軽くする方向にあります。
ただし、内部では楕円曲線や多項式コミットメントなど、この記事の範囲を超える話題も出てきます。

10.2 証明を小さくしたい、という流れ

Merkle Treeでは、対象データが含まれていることを確認するために、rootまでの道筋にある隣のハッシュを使います。

これはとても便利ですが、データ構造が大きくなると、証明データの大きさも無視できなくなります。
特に、Ethereumの状態のように巨大なデータを扱う場合、witnessを小さくできるかどうかは重要です。

ここで、かなり単純化したコードで「木の高さ」のイメージを見てみます。

次のコードは、Verkle Treeの証明サイズを正確に計算するものではありません。
あくまで、枝分かれの数が増えると、rootまでの段数が減りやすい という直感を確認するための学習用コードです。

# これは「木の枝分かれ数が増えると、高さが小さくなりやすい」ことを
# 理解するための学習用コードです。
# 実際のMerkle proofやVerkle proofのサイズを正確に計算するものではありません。

import math


def tree_height(num_leaves: int, branching_factor: int) -> int:
    """
    leaf数と分岐数から、木の高さの目安を計算します。

    num_leaves:
        葉の数です。ここでは記録件数のようなものだと考えます。

    branching_factor:
        1つの親ノードが何個の子を持つかを表します。
        binary Merkle Treeなら2です。

    注意:
        これは単純な数学上の目安です。
        実際のVerkle Treeでは、vector commitmentやエンコード方式などが関係します。
    """
    if num_leaves <= 1:
        return 0

    return math.ceil(math.log(num_leaves, branching_factor))


leaf_counts = [1_000, 1_000_000, 1_000_000_000]
branching_factors = [2, 16, 256]

for leaves in leaf_counts:
    print(f"leaf数: {leaves:,}")

    for branching_factor in branching_factors:
        height = tree_height(leaves, branching_factor)
        print(f"  分岐数 {branching_factor:>3}: 高さの目安 {height}")

    print()

このコードを実行すると、分岐数が2の場合より、16や256のように枝分かれが多い場合の方が、高さの目安が小さくなることが分かります。

もちろん、これだけでVerkle Treeを説明できるわけではありません。
Verkle Treeでは、単に枝を増やすだけでなく、vector commitmentを使って証明を小さくする考え方が重要です。

ただ、初学者向けには、まず次の感覚を押さえておくと読みやすくなります。

Merkle Treeでは、対象データからrootまでの道筋をたどります。
データが巨大になると、この道筋や証明の大きさを小さくしたい場面が出てきます。
Verkle Treeは、その方向で注目されている発展的なデータ構造です。

10.3 透明性ログは、証明書だけでなくソフトウェアにも広がっている

第7章では、Certificate Transparencyを例に、証明書を公開ログへ記録し、Merkle Treeで検証しやすくする考え方を見ました。

最近は、この 透明性ログ の考え方が、証明書だけでなく、ソフトウェアサプライチェーンの文脈にも広がっています。

たとえばSigstoreのRekorは、ソフトウェアサプライチェーンで生成される署名付きメタデータを、改ざんを検知しやすい記録として扱うことを目的としています。Sigstoreのドキュメントでは、Rekorがverifiable data structureの上に構築され、監査者はログがappend-onlyであり、エントリが変更・削除されていないことを監視できると説明されています。

参考: Sigstore Documentation: Rekor

また、RekorのGitHubリポジトリでも、Rekorはソフトウェアプロジェクトのサプライチェーン内で生成されたメタデータを、改ざん耐性のある台帳に記録することを目標としていると説明されています。

参考: sigstore/rekor: Software Supply Chain Transparency Log

ここで大切なのは、「ログに入っているから絶対安全」と見るのではなく、ログを監視できること が重要だという点です。

透明性ログは、悪いことを完全に事前防止する魔法ではありません。
むしろ、想定外の証明書発行、想定外の署名、怪しいリリースなどを、あとから隠しにくくし、検出しやすくするための仕組みです。

Transparency.devの記事でも、透明性ログでは「エントリがログに含まれていること」「新しいcheckpointが過去の版と整合していること」「全ユーザーが同じエントリを見ていること」「ログ内のエントリを監視して不正を見つけること」など、複数のレベルで検証できると説明されています。

参考: Transparency Logs: A Verifiable Transport Layer

身近な例に置き換えると、次のようなイメージです。

場面	透明性ログがない場合	透明性ログがある場合
ソフトウェアのリリース	署名だけを見て信頼する	署名イベントが公開ログに残っているかも確認できる
鍵の悪用	盗まれた鍵で署名されても気づきにくい	想定外の署名イベントを監視しやすくなる
ビルドの再現性	どの手順で作られたか追いにくい	ビルド情報や証明をログに残し、第三者が確認しやすくなる
監査	管理者の説明に頼りやすい	ログの整合性や追加履歴を検証しやすい

💡 豆知識
Certificate Transparencyは、Webサイトの証明書を公開ログで監視しやすくする仕組みとして広まりました。
その発想は、ソフトウェアの署名、ビルド、リリース、AIモデルの公開履歴などにも応用されつつあります。
「何を信じるか」だけでなく、「信じる根拠が公開され、あとから検証できるか」が重要になっています。

10.4 ログは「入れる」だけでなく「監視する」ことが大切

透明性ログの話で誤解しやすいのは、ログに記録すればそれだけで安全になる、という見方です。

実際には、ログに入った情報を誰も見なければ、怪しいイベントに気づけません。
そのため、透明性ログでは monitor や auditor の役割が重要になります。

ここで、かなり小さな例として、ソフトウェアの署名イベントを監視するコードを見てみます。

次のコードは、実際のRekorやSigstoreの検証を再現するものではありません。
目的は、公開ログに記録されたイベントを見て、想定外の署名者がいないか確認する という考え方を理解することです。

# これは透明性ログの監視イメージを理解するための学習用コードです。
# 実際のRekor API、署名検証、Merkle inclusion proof検証を再現するものではありません。

# 公開ログから取得した署名イベントのようなものを、説明用に用意します。
log_entries = [
    {"package": "payment-api", "version": "1.0.0", "signer": "[e-mail]"},
    {"package": "payment-api", "version": "1.0.1", "signer": "[e-mail]"},
    {"package": "payment-api", "version": "1.0.2", "signer": "[e-mail]"},
    {"package": "web-frontend", "version": "2.3.0", "signer": "[e-mail]"},
]

# パッケージごとに、想定している署名者を定義します。
# 実際の運用では、組織のポリシーやCI/CDの設定と対応づけて管理します。
allowed_signers = {
    "payment-api": {"[e-mail]"},
    "web-frontend": {"[e-mail]"},
}


def find_unexpected_signatures(entries, policy):
    """
    ログ内の署名イベントを確認し、想定外の署名者を探します。

    entries:
        ログから取得した署名イベントの一覧です。

    policy:
        パッケージごとに許可された署名者をまとめた辞書です。

    戻り値:
        想定外の署名者によるイベントをリストで返します。
    """
    alerts = []

    for entry in entries:
        package = entry["package"]
        signer = entry["signer"]

        expected = policy.get(package, set())

        # 許可された署名者に含まれていなければ、確認が必要なイベントとして扱います。
        if signer not in expected:
            alerts.append(entry)

    return alerts


alerts = find_unexpected_signatures(log_entries, allowed_signers)

if alerts:
    print("想定外の署名イベントが見つかりました。")
    for alert in alerts:
        print(
            f"  package={alert['package']}, "
            f"version={alert['version']}, "
            f"signer={alert['signer']}"
        )
else:
    print("想定外の署名イベントはありません。")

このコードでは、payment-api の 1.0.2 に対して、想定外の [e-mail] が署名したイベントを検出します。

実際の透明性ログでは、ここに次のような検証も加わります。

• そのエントリが本当にログに含まれているか
• ログがappend-onlyに成長しているか
• 自分と他の利用者が同じログ状態を見ているか
• 署名者や証明書が組織のポリシーに合っているか
• ビルドやリリースの手順が期待通りか

Merkle Treeは、このうち「ログに含まれていること」や「ログが過去から一貫して成長していること」を検証しやすくする部品です。
一方で、署名者が適切か、リリース内容が安全か、ビルド手順が妥当かは、別のポリシーや監査で確認する必要があります。

この点は、ブロックチェーンのMerkle proofとよく似ています。

場面	Merkle系の証明で確認しやすいこと	別途確認が必要なこと
Bitcoin	取引があるブロックに含まれていること	取引の妥当性、チェーンの正当性、確認数
Certificate Transparency	証明書がログに含まれていること	証明書が正当か、ドメイン所有者が期待しているか
ソフトウェア署名ログ	署名イベントがログに含まれていること	署名者が正しいか、ビルドが安全か
監査ログ	ログ項目が記録されていたこと	そのイベントの意味や業務上の正当性

10.5 Merkle Tree Certificatesという発展的な提案

証明書まわりでは、Merkle Tree Certificates という提案もあります。

IETFのInternet-Draftでは、Merkle Tree Certificatesは、Certificate Transparencyのような公開ログを証明書発行と統合する新しいX.509証明書の形として説明されています。
この提案は、短命証明書やポスト量子署名アルゴリズムによって証明書やログのサイズが大きくなる課題に対し、ログ記録と証明書をより一体化する方向を示しています。

参考: Internet-Draft: Merkle Tree Certificates

ただし、Internet-Draftは正式な標準ではなく、更新・置き換え・失効する可能性があります。
そのため、この記事では「今後の関連話題」として紹介するに留めます。

ここで大切なのは、Merkle Treeの考え方が、単に「ブロックチェーンの中の取引をまとめる」だけでなく、証明書やPKIの設計にも関係し続けている点です。

特に、ポスト量子暗号の移行では、公開鍵や署名サイズが大きくなりやすいという課題があります。
Merkle Tree Certificatesのdraftでも、大きな公開鍵・署名や、短命証明書によるログエントリ増加が課題として説明されています。

参考: IETF Datatracker: Merkle Tree Certificates

この話題は少し発展的ですが、初学者向けには次のように押さえると十分です。

証明書の世界でも、「発行されたものを公開ログで確認できるようにする」「必要な証明だけで確認しやすくする」という方向で、Merkle Treeに近い考え方が使われ続けています。

10.6 ブロックチェーンを使わないログ検証にも応用される

Merkle Treeというと、どうしてもブロックチェーンを連想しがちです。

しかし、最近の研究や実装例を見ると、ブロックチェーンを使わずに、Merkle Treeだけを使ってログの改ざん検知を軽量に行う方向もあります。

たとえば、2026年にarXivへ投稿されたIoT Edge環境向けの研究では、IoTデバイスが生成する監査ログの完全性を確認するために、Merkle-tree commitmentsと適応的なchunkingを組み合わせた軽量な検証パイプラインが提案されています。
この研究では、ブロックチェーン型のログ基盤は、合意形成のオーバーヘッドやネットワーク依存、導入の複雑さがIoT edge環境では重くなり得るため、分散台帳に依存しない改ざん検知の方向が示されています。

参考: arXiv: Lightweight Tamper-Evident Log Integrity Verification for IoT Edge Environments

このような研究は、まだ査読済みの標準仕様というより、研究動向として見るのが安全です。
ただ、方向性としてはとても分かりやすいです。

つまり、Merkle Treeは「ブロックチェーンそのもの」ではありません。
必要なのは、次のような場面です。

• ログが大量にある
• すべてを毎回確認するのは重い
• ある1件が本当に記録されていたか確認したい
• 過去のログがこっそり差し替えられていないか検知したい
• ブロックチェーンほど大きな仕組みは使いたくない

このような条件では、Merkle Treeだけを使った軽量な改ざん検知も選択肢になります。

選択肢	向いている場面	注意点
ブロックチェーン	複数主体で合意形成しながら記録を共有したい	合意形成、運用、コストが重くなる場合がある
透明性ログ	公開ログとして、第三者が監視・検証できるようにしたい	ログ運営者、監視者、rootの信頼前提が重要
Merkle Tree単体のログ検証	組織内ログやIoTログの改ざん検知を軽く行いたい	rootの保管場所や信頼できる固定方法が重要

ここは、情報セキュリティの観点でも大切です。

何でもブロックチェーンにすればよいわけではありません。
本当に必要なのは、どのような脅威に対して、どの程度の検証可能性が必要なのかを見極めることです。

10.7 最近の動向を読むときの注意点

ここまで見てきたように、Merkle Treeに関連する話題は今も広がっています。

ただし、最近の技術動向を読むときには注意も必要です。

特に、次のような表現には少し慎重になった方がよいです。

よくある表現	注意したい見方
Verkle TreeでEthereumが完全に軽くなる	導入状況、仕様、クライアント実装、運用上の制約を確認する必要がある
stateless clientなら状態データが不要になる	どのノードが何を保存するのか、witnessを誰が作るのかを分けて見る
透明性ログに入っていれば安全	ログの監視、署名者ポリシー、ログ運営者、rootの信頼性も必要
Merkle proofがあれば正当性が完全に分かる	proofは包含や整合性の確認であり、データの意味や妥当性は別問題
ブロックチェーンを使えば監査ログは全部安全	合意形成が必要か、rootをどこに固定するか、運用コストが妥当かを考える

Merkle TreeやVerkle Treeは、あくまでデータ構造や証明の部品です。
それ自体が、システム全体のセキュリティを自動的に保証するわけではありません。

たとえば、Merkle rootが正しく計算されていても、そのrootを攻撃者が差し替えられるなら意味が弱くなります。
また、ログに含まれていることが確認できても、そのログを誰も監視していなければ、異常なイベントに気づくのが遅れるかもしれません。

そのため、最近の動向を読むときは、次の4つに分けて見ると整理しやすいです。

観点	確認したいこと
データ構造	Merkle Tree、Merkle Patricia Trie、Verkle Treeなど、何を使っているか
証明	inclusion proof、consistency proof、witnessなどで何を証明しているか
信頼前提	root、checkpoint、署名、ログ運営者、監視者をどう信頼するか
運用	誰がデータを保存し、誰が監視し、異常時にどう対応するか

この4つを分けて見ると、「新しいデータ構造が出てきたからすべて解決」というより、システム全体の中でどの役割を担っているのかを理解しやすくなります。

10.8 この章のまとめ

この章では、Merkle Treeに関連する最近の動向を整理しました。

Merkle Treeの基本的な考え方は古くからありますが、現在もさまざまな形で使われています。
特に、EthereumのVerkle Tree、stateless client、透明性ログ、ソフトウェアサプライチェーン検証、Merkle Tree Certificates、IoTログ検証などは、Merkle Treeの発想が今も発展し続けていることを示しています。

この章で押さえたいポイントは、次の通りです。

ポイント	説明
Verkle TreeはEthereumの重要な関連話題	状態証明を小さくし、stateless clientへ近づけるために検討されている
stateless clientではwitnessが重要	全状態を持たず、必要な状態と証明を使って検証する方向性がある
透明性ログは証明書以外にも広がっている	ソフトウェア署名、ビルド、リリース、AIモデルなどの検証にも使われる
ログは監視してこそ意味がある	inclusion proofだけでなく、異常なエントリを見つけるmonitorの役割が重要
Merkle Tree Certificatesは発展的な提案	証明書と公開ログをより強く統合する方向だが、仕様状況の確認が必要
ブロックチェーンを使わないログ検証にも応用される	監査ログやIoTログなどで、軽量な改ざん検知に使われる研究がある
新技術は万能ではない	データ構造、証明、信頼前提、運用を分けて考える必要がある

Merkle Treeは、Bitcoinのブロック内取引をまとめるためだけの仕組みではありません。
大量の記録を要約し、必要な部分だけを検証しやすくするという考え方は、ブロックチェーン、証明書、ソフトウェア、監査ログなど、さまざまな領域に広がっています。

次の章では、記事全体のまとめに入ります。
Merkle Treeを学ぶうえで特に大切だった「大量の記録を1つのrootにまとめること」「Merkle proofで必要な部分だけ確認すること」「ただしrootの信頼性やデータの意味までは別途確認が必要なこと」を、最後に整理します。

11. まとめ

この章では、記事全体を振り返りながら、Merkle Treeをどのように理解するとよいかを整理します。
ポイントは、Merkle Treeを「難しい暗号技術そのもの」として見るのではなく、大量の記録を効率よくまとめ、必要な部分だけを確認しやすくするための仕組み として見ることです。

ここまで、Merkle Treeについて、身近な記録の例から順番に整理してきました。

最初に見たのは、大量のレシート、出席簿、会計ノート、スマホ決済履歴、ログのような「たくさんの記録」です。
数件であれば、全部を1つずつ確認しても大きな負担にはなりません。

しかし、記録が1万件、100万件と増えていくと、毎回すべてを見直すのは大変です。
また、確認したいのは「全部の中身」ではなく、「この1件が、確かに全体の中に含まれているか」だけの場合もあります。

このような場面で、すべての記録を毎回渡すのではなく、全体を代表する値と、確認に必要な少数の手がかりだけで検証できると便利です。

この考え方を支える代表的なデータ構造が、Merkle Treeでした。

11.1 記事全体の振り返り

この記事では、Merkle Treeをいきなり定義から覚えるのではなく、次の流れで整理しました。

最初に確認したように、Merkle Treeは「データを暗号化して隠す仕組み」ではありません。
また、Merkle rootだけを見れば、すべての取引やログの正しさが分かる、という仕組みでもありません。

Merkle Treeの大きな役割は、大量のデータを木構造としてまとめ、あとから必要な部分だけを検証しやすくすることです。

この見方を持っておくと、BitcoinのMerkle root、SPVのMerkle branch、EthereumのMerkle Patricia Trie、Certificate Transparencyのaudit pathなども、別々の暗記項目ではなく、同じ「検証しやすい記録」の話としてつながって見えます。

11.2 本記事で整理したこと

本記事で整理した内容を、章ごとに振り返ると次のようになります。

章	整理したこと	大事なポイント
1章	大量の記録では「全部見直す」のが大変になる理由	記録件数が増えると、毎回すべてを確認する負担が大きくなる
2章	Merkle Treeを一言で整理	大量のデータをハッシュで木構造にまとめ、1つのrootへ集約する
3章	Merkle Treeの基本構造	leaf、内部ノード、Merkle root、左右の順番、奇数個処理を整理する
4章	Merkle proofによる包含確認	対象データと必要な手がかりだけで、rootまで再計算できる
5章	Bitcoinでの使われ方	ブロック内の取引からMerkle rootを作り、ブロックヘッダに含める
6章	Ethereumでの使われ方	単純なMerkle Treeだけでなく、Merkle Patricia Trieなどの派生構造を使う
7章	ブロックチェーン以外の使われ方	Certificate Transparencyや透明性ログなどでも、検証しやすい記録に使われる
8章	できること・できないこと	包含確認と、データ自体の妥当性やrootの信頼性は分けて考える
9章	よくある誤解	暗号化、万能な安全性、BitcoinとEthereumの同一視などを避ける
10章	最近の動向	Verkle Tree、stateless client、透明性ログ、ソフトウェアサプライチェーンなどへ広がっている

こうして見ると、Merkle Treeは単なる「木っぽいデータ構造」ではなく、ブロックチェーン、証明書ログ、ソフトウェアサプライチェーン、監査ログなど、あとから検証できる記録を考えるうえで重要な部品だと分かります。

11.3 Merkle Treeは「何を確認しやすくするか」の仕組み

この記事全体を一言でまとめるなら、次のようになります。

Merkle Treeは、大量の記録を1つのrootにまとめ、必要な手がかりだけで「その記録が含まれていること」を確認しやすくする仕組みです。

ここで大切なのは、Merkle Treeを「全部を安全にしてくれる技術」として広げすぎないことです。

Merkle Treeで特に確認しやすくなるのは、あるデータが、あるrootに対応する集合の中に含まれているか です。
一方で、そのデータが業務上正しいか、署名が正しいか、残高が足りているか、スマートコントラクトの実行結果が妥当か、という話は別に確認する必要があります。

観点	Merkle Treeで見やすくなること	別途考えること
記録の包含	このデータがrootに対応する集合へ含まれているか	そのデータの意味や業務上の正しさ
改ざん検知	データが変わるとrootも変わりやすい	正しいrootをどこから信頼するか
軽量な確認	全データではなくproofだけで確認しやすい	proofの作り方、順序、エンコードの統一
監査	公開ログや履歴をあとから確認しやすい	ログ運用者、監視者、周辺システムの信頼性

たとえるなら、Merkle Treeは「大量の書類を、あとから照合しやすいように整理する索引」のようなものです。
索引があると確認は楽になりますが、書類の内容そのものが正しいか、誰が承認したのか、どのルールで扱うのかは、また別の観点で確認しなければなりません。

💡 豆知識
Merkle Treeは「圧縮ファイル」のように、rootから元データを復元する仕組みではありません。
Merkle rootは、全体を代表する要約値です。
そのため、rootだけを見ても、元の取引一覧やログ一覧を取り出すことはできません。

11.4 Merkle Treeはブロックチェーン全体の一部である

本記事ではMerkle Treeを中心に扱いましたが、ここで一度、ブロックチェーン全体の中での位置づけを整理しておきます。

ブロックチェーンの安全性や検証可能性は、Merkle Treeだけで成り立っているわけではありません。

たとえば、次のような要素も関係します。

• 取引を作った本人を確認するデジタル署名
• 取引やブロックの形式を確認する検証ルール
• ブロック同士をつなぐ前ブロックのハッシュ
• どの履歴を正しいものとして扱うかを決めるコンセンサス周辺の仕組み
• ノード同士が情報を共有するP2Pネットワーク
• 秘密鍵、ウォレット、取引所、ブリッジなどの周辺システム

Merkle Treeは、その中でも特に、ブロック内の取引やログのような大量の記録をまとめ、必要な部分を検証しやすくする部品として働きます。

この図のように、Merkle Treeはブロックチェーン全体の中の重要な一部分です。

Bitcoinでは、ブロック内の取引をまとめるMerkle rootがブロックヘッダに含まれます。
Ethereumでは、状態、取引、レシートなどを扱うために、Merkle Patricia Trieのような派生構造が登場します。

どちらも「rootで全体を代表させる」という考え方は近いですが、何をまとめているのか、どの構造を使っているのかは違います。
そのため、Merkle Treeを理解するときは、どのチェーンの、どのデータを、どのrootにまとめているのか を確認することが大切です。

11.5 Merkle Treeを学ぶときに意識したいこと

Merkle Treeは、図で見るとシンプルです。
leafを作り、隣同士をハッシュ化し、最後にrootを作る。
ここだけ見ると、そこまで難しくないように感じます。

ただし、実際にブロックチェーンや透明性ログの文脈で使うときは、次の点を意識する必要があります。

意識したいこと	なぜ大事か
rootをどこから信頼するのか	proofはrootに対する包含を示すため、root自体の信頼性が重要になる
データの順序をどう扱うのか	左右の順番や並び順が変わるとrootも変わる
エンコードをどうそろえるのか	同じ意味のデータでも、バイト列が違えばハッシュも変わる
ハッシュ関数をどう選ぶのか	衝突耐性やプロトコル仕様に関わる
奇数個の葉をどう扱うのか	Bitcoinのように最後を複製する場合など、実装ごとにルールがある
proofで何が分かるのか	分かるのは主に包含関係であり、データの妥当性そのものではない
どのプロトコルの話なのか	Bitcoin、Ethereum、Certificate Transparencyでは構造や目的が異なる

このように見ると、Merkle Treeは「ハッシュを木にしただけ」と言うには少しもったいない仕組みです。
設計の細部をそろえることで、軽量な検証、監査、透明性、改ざん検知に役立つ部品になります。

ただし、繰り返しになりますが、Merkle Treeだけでシステム全体が安全になるわけではありません。
秘密鍵管理、署名検証、ネットワーク、コンセンサス、実装、運用、監視などと組み合わせて考えることが大切です。

11.6 今後深掘りしたいテーマ

Merkle Treeを理解すると、次に学びやすくなるテーマがいくつかあります。

テーマ	Merkle Treeとのつながり
ハッシュ関数	Merkle Treeの土台になる技術。衝突耐性や一方向性を理解すると、rootの意味が見えやすくなる
Bitcoinのブロック構造	Merkle rootがブロックヘッダに入る理由や、SPVの考え方を深掘りできる
Ethereumの状態管理	stateRoot、transactionsRoot、receiptsRoot、Merkle Patricia Trieをより詳しく理解できる
Verkle Tree	Ethereumのstateless client構想や、証明サイズを小さくする方向性につながる
Certificate Transparency	証明書ログを公開し、監査しやすくする仕組みとしてMerkle Treeを見直せる
透明性ログ・ソフトウェアサプライチェーン	Sigstore Rekorなど、ソフトウェア成果物の検証可能性に話が広がる
監査ログの改ざん検知	システム運用やセキュリティ監査で、ログをあとから検証しやすくする設計につながる
Merkle proofとゼロ知識証明	データ構造の証明を、より高度な証明システムの中で使う話へ発展する

一度にすべてを学ぶ必要はありません。
まずは本記事で整理したように、大量の記録をどうまとめるか、必要な部分だけをどう確認するか、rootをどこまで信頼するか という3点を押さえると、関連技術を追いやすくなります。

11.7 最後に

Merkle Treeは、名前だけ見ると少し難しそうに感じるかもしれません。

しかし、考え方の入口はかなり身近です。

大量のレシートや出席簿、ログ、取引履歴の中から、確認したい1件だけを効率よく確認したい。
全部を毎回見直すのではなく、全体を代表する値と、必要な手がかりだけで確認したい。

Merkle Treeは、このような発想を支える仕組みです。

もちろん、実際のBitcoinやEthereum、Certificate Transparencyでは、単純な学習用コードよりもずっと厳密なルールが使われています。
どのデータをどの順番でハッシュ化するのか、rootをどこへ保存するのか、proofをどう検証するのか、どのプロトコルの仕様に従うのかを確認する必要があります。

それでも、この記事で見てきた基本の流れは共通しています。

大量の記録をハッシュ化する
隣り合うハッシュをまとめる
最後にrootを作る
確認したいデータについてproofを使ってrootまでたどる
計算したrootが信頼しているrootと一致するか確認する

この流れを押さえておくと、Merkle root、Merkle proof、Merkle branch、Merkle Patricia Trie、透明性ログ、Verkle Treeといった言葉が、少しずつ同じ地図の上に乗ってきます。

Merkle Treeは、ブロックチェーンを支える「派手な主役」というより、記録をあとから検証しやすくするための大事な土台の一つです。

ブロックチェーンを学ぶときは、PoWやPoS、スマートコントラクトのような目立つテーマに目が向きやすいです。
その一方で、Merkle Treeのようなデータ構造を理解しておくと、「なぜ軽量な検証ができるのか」「なぜrootが重要なのか」「なぜ実装ルールをそろえる必要があるのか」が見えやすくなります。

この記事が、Merkle Treeを単なる専門用語としてではなく、大量の記録を検証しやすくするための考え方として理解するきっかけになればうれしいです。