マークルツリーがビットコインで数千件の取引をミリ秒で検証する仕組み。このエレガントなデータ構造の動作原理と重要性。
import InfoBox from '@components/shortcodes/InfoBox.astro';
ビットコインのブロックには数千件の取引が含まれます。自分の取引が含まれているか確認するには、ブロック内の全取引をダウンロードして一つずつ照合する必要があるでしょうか? それは遅く、帯域を消費し、スマートフォンでは事実上不可能です。
代わりにビットコインは、1979年にラルフ・マークルが発明したデータ構造を使用します: マークルツリー。数千件の取引を32バイトのハッシュ一つに圧縮し、ブロック全体ではなく少数のハッシュだけで特定の取引の存在を証明できます。
マークルツリーはハッシュの二分木です。
ステップ1: ブロック内の全取引をSHA-256でハッシュ化(ビットコインは常に二重ハッシュ)。これがリーフノード。
ステップ2: ペアにする。各ペアを結合して親ハッシュを作成。奇数の場合、最後のハッシュを複製して自分自身とペアにする。
ステップ3: 繰り返す。頂点に一つのハッシュが残るまでペアリングとハッシュ化を続ける。
頂点のハッシュがマークルルート。ブロックヘッダに含まれ、マイナーがプルーフ・オブ・ワークを探す際にハッシュする80バイトの要約の一部です。
2,000件の取引があるブロックでツリーは約11段。特定の取引一つを検証するのに2,000個ではなく11個のハッシュだけで済みます。
あるレベルで取引数が奇数の場合、ビットコインは最後のハッシュを複製して自分自身とペアにします。これは二分木構造を維持するための設計選択です。
セキュリティ上の注意: この複製により、理論的には異なる取引セットが同じマークルルートを生成する可能性があります(CVE-2012-2459)。Bitcoin Coreは重複取引を含むブロックを拒否するようパッチ済みです。
マークルツリーの真の力はマークル証明(SPV証明)です。
8件の取引があるブロックでTX3の包含を検証する場合、8件全ては不要です。必要なのは3つのハッシュだけ。ステップごとに結合してブロックヘッダのマークルルートと一致するか確認します。一致すればTX3はブロックに存在します。
4,000件の取引でもマークル証明に必要なのは約12ハッシュ(log2 4,000)。各32バイト。数メガバイトのブロックでメンバーシップを証明するのに384バイトで済みます。
ブロックヘッダ。 全ブロックヘッダに当該ブロックの取引のマークルルートが含まれる。
SPVウォレット。 Electrum、BlueWalletなど大半のモバイルウォレットがマークル証明で取引を検証。
Taproot (BIP 341)。 MAST(Merkelized Abstract Syntax Trees)というマークルツリー構造を使用して複数の支出条件をコミット。
Segregated Witness。 取引マークルツリーとは別に、ウィットネスデータ用の第二マークルツリーを導入。
ラルフ・マークルがこの構造を設計したのは1979年 - ビットコインの30年前。サトシがこれを採用した理由は、根本的なスケーリング問題を解決するからです: トラストレスなシステムに軽量デバイスがどう参加するか?
答えは、全体を明かさずにメンバーシップを証明するハッシュのツリー。スマホがミリ秒でビットコイン決済を検証できる理由であり、600GBのフルノードが同じ数学で同じ結論に達する理由です。