Merkle Tree

ウォレットが「支払いはブロックに含まれた」と表示したとします。全内容をダウンロードせずに確認するにはどうすればよいでしょうか。ここで Merkle Tree が役立ちます。まず取引をハッシュ、つまり短い暗号学的な指紋で表し、それらを段階的にまとめて一つの共通の指紋であるルートにします。ヘッダーにこの Merkle root が入ることで、ブロックと取引が結びつきます。ルートは全支払いを読み戻せる保存庫ではなく、提示されたデータを検証するためのものです。 [1] [2]

A、B、C、D という四つの取引を考えましょう。それぞれの指紋を取り、A と B をつなげて新しいハッシュ AB を計算します。C と D も同様にして CD を得ます。最後に AB と CD の指紋をつなげ、ルートを計算します。この文字は取引と途中の結果のラベルで、本物のハッシュではありません。多くの葉が枝を通って一つの根に集まる、逆さの木のような構造です。取引が増えると段数が増えますが、原理は変わりません。 [3]

B を確認するには、そのデータから指紋を計算します。追加で必要なのは A の指紋と、C と D をまとめた CD の指紋、そして正しい順序だけです。A と B から AB、次に AB と CD からルートを計算し、ヘッダー内のルートと比較します。この補助的な経路を Merkle proof と呼びます。A、C、D の内容は不要です。1024 件の取引がある均衡した木では、経路上の兄弟ハッシュは 10 個です。そのため、ブロックが大きくなっても証明のサイズは全取引の一覧ほど速く増えません。 [2] [3]

証明がルートと一致しても、提示されたヘッダーを無条件に信用してよいわけではありません。Proof of Work、つまりマイニング計算の結果が必要な難易度を満たしているかも確認します。さらに、ヘッダーが適切なチェーンにつながっていることも確かめる必要があります。それでも Merkle proof は、ブロック内の全取引の署名や規則をすべて検証するものではありません。それを行うのは Full Node です。そのため whitepaper の簡易支払い検証 SPV は、完全な検証とは異なる安全性の前提を持ちます。また、再編成でブロックが有効な枝から外れる場合もあります。内容の証明は残りますが、現在の履歴での支払いの位置は変わり得ます。 [2]

Bitcoin の通常の木では、葉はブロック内の取引順に並ぶ txid で、先頭は Coinbase Transaction、つまりマイナーがブロック報酬を受け取るための特別な取引です。対になる値をバイト列としてつなげ、SHA-256 を二度使ってハッシュします。ある段の最後に相手のないハッシュが残れば、その計算のために複製します。支払いを追加するわけではありません。取引が一つだけなら、その txid がそのままルートになります。この複製の仕組みには、実装での慎重な重複チェックが必要です。プロトコルの改良である SegWit は、署名などの witness データも分離します。Coinbase Transaction に記録される別の暗号学的な指紋が、このデータをブロックに結びつけます。この指紋を witness commitment と呼びます。通常の txid の木と witness の木を混同してはいけません。 [3] [4]