マークルツリー

トランザクションのハッシュを2つずつ組にし、各組をハッシュ化することを、ハッシュが1つだけ残るまで繰り返します。その単一の値がブロックヘッダーに入り、あるトランザクションがその下に属することを証明するには、1本の経路に沿ったハッシュだけで足ります。2,000件の支払いを含むブロックでは、その11個、352バイトです。だからこそ、スマートフォンのウォレットはブロックをダウンロードしなくても、あなたのコインが届いたことを確認できるのです。

仕組み

マークルツリーは、隣り合う要素をレベルごとにまとめてハッシュ化し、ハッシュが1つだけ残るまで続けることで、リストをピラミッドに変えます。

葉にあたるのは、マイナーが並べた順序のトランザクションIDです。ビットコインでは、2つの32バイトの値を連結し、その結果にSHA-256を2回適用することで各組を結合します。あるレベルに奇数個の要素がある場合、最後の1つはそれ自身のコピーと組にされます。これはアルゴリズムを単純に保つ一方で、かつて実際のトラブルを引き起こしました。CVE-2012-2459として分類された脆弱性は、2012年5月に公表され、同じ月に修正されたものであり、この重複を悪用して、基礎となるトランザクションは正常であるにもかかわらずノードには無効に見えるブロックを構成していました。

利点は対数的です。トランザクション数が2倍になっても、レベルが1つ増えるだけで、トランザクションごとにハッシュが1つ増えるわけではありません。1,024件の支払いを含むブロックでは、包含を証明するのに10個のハッシュ、320バイトが必要です。四千九十六件では12個、384バイトです。証明を検証する人は経路を上向きに再計算し、ヘッダーからすでに信頼しているルートと結果を比較します。SHA-256を破ることなく経路を偽造する方法はありません。

この仕組みはビットコインに起源を持つものではありません。Ralph Merkleは、US 4,309,569となった特許出願でこの構造を説明しました。この出願は1979年に出願され、1982年1月に特許が付与されました。ホワイトペーパーは彼の業績を引用し、このツリーを2つの用途に用いています。第7節ではディスクを節約するために古いブロックから使用済みトランザクションを取り除くこと、第8節ではヘッダーだけを保持したままクライアントが支払いを検証できるようにすることです。

どこで見られるか

マークルツリーは、集合全体を送らずに、ある要素が大きな集合に属することをシステムが証明する必要があるあらゆる場面に現れます。

ビットコインの内部では、すべてのブロックヘッダーが1つのツリーの頂点を保持しています。ノードは受け取ったトランザクションからツリーを再構築し、結果が一致しなければそのブロックを拒否します。Bitcoin Coreはこの仕組みを直接公開しています。gettxoutproofはトランザクションがブロックに含まれたことのシリアライズされた証明を生成し、verifytxoutproofはその証明を検証します。これはウォレットを渡さずに支払いの証拠を相手に渡す実用的な方法です。

ビットコインの別の場所では、Taprootが2つ目のツリーを構築します。Taproot出力の代替の支払い条件はツリーとして配置されるため、使用した枝を明かしても、使用しなかった枝について何も開示されません。ビットコインの外では、同じ構造がGitのコミット履歴、不正に発行されたウェブ証明書を検知するCertificate Transparencyのログ、ZFSファイルシステムのデータ整合性チェックを支えています。

ウォレットの利用者にとって、目に見える結果は小さくて有用です。数十メガバイトのヘッダーを保持する軽量クライアントは、あなたのトランザクションが特定のブロックに、特定の深さで含まれていることを確認できます。誤った答えが返るのは、誰かが偽のチェーン上で有効なプルーフ・オブ・ワークを生成した場合だけであり、それには実際の資金がかかります。

マークルツリーvsマークルルート

マークルツリーは作業用の構造であり、マークルルートはその後残される単一の値です。ノードはブロックを検証する間、ピラミッド全体をメモリ上に構築し、その後それを破棄して、最上段に残った32バイトだけを保存します。その下のすべてはトランザクションから再生成できるからです。ブロックエクスプローラーがマークルルートという名前のフィールドを表示するとき、それが残された値です。ツリーを保存する人はおらず、保存する必要もありません。