Merkle Treeとは？
Merkle Treeは大量の記録を一つの短いフィンガープリントに圧縮するデータ構造です。全体をすべて確認するのではなく、いくつかの小さな断片だけを検査することで、ある項目が大きなリストに含まれることを証明できます。各親が子を要約し、最終的に一つの先祖に集約される家系図を想像してください。
Merkle Treeがすべてのトランザクション自体を「保存」している、という考え。完全にそうではありません。Merkle Treeはトランザクションの圧縮されたフィンガープリントのみを保存し、必要に応じて生データからツリーを再構築できます。
Merkle Treeの仕組み
すばやく検証できる要約が必要な支払いの塊を想像してください。Merkle Treeの流れを平易に説明すると次の通りです：
- ステップ1： トランザクションのような項目のリストを用意し、それぞれがツリーの葉になります。
- ステップ2： 各項目をハッシュ関数で短いフィンガープリントに変換します。
- ステップ3： 隣接するフィンガープリントを対にして結合し、親を作るために再度ハッシュします。
- ステップ4： 対にしてハッシュする操作を繰り返し、最終的に一つの上位フィンガープリントが残るまで続けます。これがこの集合のMerkle rootです。
- ステップ5： ある項目が集合に含まれることを証明するには、その項目と兄弟フィンガープリントの短い経路だけで十分です。迅速で小さな証明です。
これが要点です：小さな証明で高い信頼を得られます。
なぜMerkle Treeが重要か
取引データの膨大な山を一つの小さなフィンガープリントにまとめることで、Merkle Treeは検証を速く安価にします。
- 利点： ブロック全体をダウンロードせずに包含を確認でき、時間と帯域を節約できます。
- 視点： 「信頼するが検証もする」という現在のインターネットの姿勢に合致します。
- 関連例： Bitcoinブロック、Ethereumのレシート、NFTの許可リスト、エアドロップ、ロールアップなどで出会います。
葉の数が奇数の場合、多くの設計では最後の葉を複製してから上へハッシュします。また、チェーンやライブラリが使う正確なハッシュ処理を二重に確認してください。細かなルールの違いで証明が変わることがあります。
Merkle Treeの主な特徴
ここが特に便利な点です：
- 効率性： データ量が増えても証明は小さいままなので、ライトクライアントの負担が軽いです。
- 整合性： 葉の一バイトを変更するとその変化はルートまで波及し、改ざんが分かりやすくなります。
- ルート： すべてが一つの Merkle root に集約され、後での検証のために保存や署名ができます。
バリエーション
Merkle Treeにはよく見かけるいくつかの型があります：
- Binary： 古典的なペア方式のツリーで、Bitcoinブロックで使われます。
- Merkle Patricia： キーと値のデータ向けにトライを用いた方式で、Ethereumのステートやレシートで使われます。
- Sparse： ほとんどの葉が空の大規模なインデックス化ツリーで、加入と非加入の簡潔な証明に向いています。
- Verkle： 分岐数が非常に多い場合に短い証明を可能にする新しい派生で、将来のアップグレード向けに検討されています。
Merkle Treeの証明は、あなたが受け入れるヘッダーやチェックポイントが信頼できるかどうか次第です。誤ったルートを信頼していれば、最も整った証明でも意味がありません。
例
Bitcoin風のライトウォレットは、トランザクションからブロックヘッダーまでの短いハッシュ経路を確認することで支払いを検証でき、全ての トランザクション履歴 をダウンロードする必要はありません。
豆知識
Ralph Merkleは1970年代後半に学生のプロジェクトとしてこのアイデアを考案し、SatoshiがBitcoinで使うまで何年も学術界で温められていました。良いアイデアは長く価値があるという証拠です。
まとめ
要点：Merkle Treeは、ある項目が大きな集合に属することを示す短くて迅速な証明を提供し、手間や大容量のダウンロードが不要になります。