ブロックチェーン/レベル II · 仕組み/2.3 ブロックとチェーン/レッスン 2
マークルツリー
数千件のトランザクションを束ねる32バイトのフィンガープリント
用意するものマークルブランチを可視化できるブロックエクスプローラー4つの短い英数字ラベル（A、B、C、D）ダブルSHA-256ハッシュ計算ツール
問い
- 1つのハッシュ値だけで、4,000件もの異なるトランザクションが含まれていることを、どうやって証明できるのでしょうか？
- なぜサトシは、最後に残った単独のエントリーをそれ自身とペアにすることを選んだのでしょうか？ そして、その選択にはどのような代償があったのでしょうか？
- 重複ペアリングのルールは、ビットコインの初期実装にどのような具体的な脆弱性をもたらしたのでしょうか？
探究
- ラルフ・マークルは1979年にバイナリハッシュツリーの特許を出願しました（1982年に取得）。これは大規模なデータセットを効率よく要約するためのデータ構造です。ビットコインでは、この仕組みにより数千のトランザクションIDが、マークルルートと呼ばれる単一の32バイトの値にまとめられます。このルートは80バイトのブロックヘッダーに直接埋め込まれ、そのブロック内のすべてのトランザクションに対する改ざん不可能な暗号学的コミットメントとなります。
- 構築はボトムアップで再帰的に進みます。トランザクションIDをペアで連結し、ダブルSHA-256でハッシュして親ノードを生成します。このペアリングを階層ごとに繰り返し、最終的にルートハッシュが1つだけ残ります。ある階層のエントリー数が奇数の場合は、二分構造を保つために最後のエントリーをそれ自身とペアにし、各段階でツリーが正しく釣り合うようにします。
- この構造の対数的な性質により、簡易支払い検証（SPV）が可能になります。ライトクライアントはブロック全体をダウンロードせず、代わりにフルノードにマークルブランチを要求します。このブランチは、特定のトランザクションからルートまでの経路上にある兄弟ハッシュだけで構成されます。4,000件のトランザクションを含むブロックなら、この証明に必要なハッシュ値は約12個で、全データサイズのごく一部にすぎません。
- ライトクライアントは、自身のトランザクションハッシュと提供された兄弟ハッシュを組み合わせてマークルルートを再計算し、ダウンロード済みのブロックヘッダーの値と比較します。一致すれば、チェーン全体を保存しなくても、トランザクションが含まれていることが暗号学的に検証されます。この仕組みにより、ストレージや処理能力が限られたデバイスでも、モバイルウォレットが安全に機能します。
- 2017年8月に有効化されたSegregated Witness（SegWit）は、2つ目のマークルツリー構造を導入しました。元のツリーがトランザクションIDにコミットするのに対し、ウィットネスツリーはウィットネストランザクションIDにコミットします。この2つ目のツリーのルートはヘッダーには格納されず、コインベーストランザクションのOP_RETURNアウトプットにコミットされます。古いノードはこれを通常のデータとして扱うため、互換性が保たれます。
- 自己ペアリングのルールには欠陥（CVE-2012-2459）が潜んでいました。最後に残った単独のエントリーがそれ自身とペアにされるため、末尾が重複したペアで終わるトランザクションリストは、重複のないリストと同じマークルルートを生成します。攻撃者は有効なブロックのこの不正な変種を中継でき、それを拒否したノードは本物のブロックのハッシュを無効として記録してしまい、ネットワークと歩調が合わなくなるおそれがありました。2012年の修正により、ノードはブロックを不正なものとしてキャッシュするのではなく、このパターンを認識するようになりました。
重要な事実
- マークルルートは、ブロックヘッダーに格納される単一の32バイトのハッシュで、そのブロック内のすべてのトランザクションにコミットします。
- ビットコインは、マークルツリー構築のすべての階層でダブルSHA-256ハッシュを使用します。
- どの階層でもエントリー数が奇数の場合は、最後のエントリーをそれ自身とペアにして処理します。
- 大きなブロック内のトランザクションのマークル証明には、通常、約12個の兄弟ハッシュが必要です。
- SegWitは、ウィットネストランザクションIDを対象とする2つ目のマークルツリーを追加し、それをコインベーストランザクション内でコミットするようにしました。
- CVE-2012-2459は、初期のBitcoin Coreバージョンにおける重複ペアリングロジックに関するバグでした。
演習 九・六・三・一
9集めるデータの完全性検証にハッシュツリーを利用している、実世界のシステムやプロトコルを9つ挙げてください。
6まとめる9つを、保護対象によって6つにグループ分けしてください：ファイル、ソフトウェアパッケージ、証明書、データベース、ブロックチェーン、その他。
3絞り込む6つのグループを、大規模なデータセットにおいて対数的な証明構造が線形スキャンより好まれる3つの核心的な理由に絞り込んでください。
1結晶化するリーフノードの1ビットの変更が、全体のルートハッシュをどのように変化させるかを1文で説明してください。
事実確認
日付、数字、主張は、下記に記載された公表資料と照合して確認しました。