ビットコインが数千件の取引を一つずつ確認せずに検証する方法

ビットコインのブロックには数千件の取引が含まれます。自分の取引が含まれているか確認するには、ブロック内の全取引をダウンロードして一つずつ照合する必要があるでしょうか? それは遅く、帯域を消費し、スマートフォンでは事実上不可能です。

代わりにビットコインは、1979年にラルフ・マークルが発明したデータ構造を使用します: マークルツリー。数千件の取引を32バイトのハッシュ一つに圧縮し、ブロック全体ではなく少数のハッシュだけで特定の取引の存在を証明できます。

あなたのスマホが気にする唯一の数字

ツリーがどう組み立てられるかを知らなくても、その恩恵は受けられます。知る必要があるのは、ツリーが何を生み出すかだけです。マークルツリーはブロック内の全取引をペア単位で畳み込み、マークルルートという単一の32バイトハッシュにまとめます。このルートはブロックヘッダの中にあります - マイナーがプルーフ・オブ・ワークを探す際にハッシュする80バイトの要約のことです。

2,000件の取引があるブロックでもツリーはわずか約11段の深さです。だから取引一つを確認するのに2,000個ではなく約11個のハッシュで済みます。この対数スケールの縮小こそが、フルノードが数メガバイトで行う検証を、スマホが数百バイトだけで同じようにこなせる理由です。

リーフの二重ハッシュ化、奇数複製ルール、CVE-2012-2459の改ざんバグ、MAST、ウィットネスツリーといった構成の詳細を知りたい場合は、技術リファレンスを参照してください: マークルツリー - 効率的なデータ検証。この記事の残りは、そのルートが軽量ウォレットに何をさせてくれるかについてです。

マークル証明 - 信頼なき検証

マークルツリーの真の力はマークル証明(SPV証明)です。

8件の取引があるブロックでTX3の包含を検証する場合、8件全ては不要です。必要なのは3つのハッシュだけ。ステップごとに結合してブロックヘッダのマークルルートと一致するか確認します。一致すればTX3はブロックに存在します。

4,000件の取引でもマークル証明に必要なのは約12ハッシュ(log2 4,000)。各32バイト。数メガバイトのブロックでメンバーシップを証明するのに384バイトで済みます。

軽量クライアントはこれで実際に何をするのか

ブロックヘッダチェーン。 全ブロックヘッダには当該ブロックのマークルルートが含まれ、ヘッダ同士はプルーフ・オブ・ワークで連結されています。軽量クライアントはこのヘッダチェーンだけ - ビットコインの全歴史を合わせても数十メガバイト - をダウンロードします。どのヘッダも書き換えるにはマイニングをやり直す必要があるため、このチェーンを信頼できます。

SPVウォレット。 Electrum、BlueWalletなど大半のモバイルウォレットがこれを実際に実装しています。ヘッダチェーンを保持し、あなたの取引を確認する必要があるたびにフルノードへマークル証明を要求します。証明はウォレットがすでに信頼しているヘッダと照合されるため、証明を提供したノード自体は信頼する必要がありません。

マークルツリーはビットコインの他の部分にも登場します - TaprootのMASTは支出条件をツリーにコミットし、SegWitは別個のウィットネスツリーを追加します - が、これらは構成レベルの用途でマークルツリーリファレンスで扱われます。ウォレットにとってやることは常に同じです: 信頼するルート一つと短い証明一つを使って包含を確認することです。

マークルツリーの優雅さ

ラルフ・マークルがこの構造を設計したのは1979年 - ビットコインの30年前。サトシがこれを採用した理由は、根本的なスケーリング問題を解決するからです: トラストレスなシステムに軽量デバイスがどう参加するか?

答えは、全体を明かさずにメンバーシップを証明するハッシュのツリー。スマホがミリ秒でビットコイン決済を検証できる理由であり、600GBのフルノードが同じ数学で同じ結論に達する理由です。