BIP 152 — コンパクトブロックリレー

  BIP: 152
  Layer: Peer Services
  Title: Compact Block Relay
  Authors: Matt Corallo <bip152@bluematt.me>
  Comments-Summary: Unanimously Recommended for implementation
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0152
  Status: Deployed
  Type: Specification
  Assigned: 2016-04-27
  License: PD

概要

P2P ネットワーク上のノードの帯域幅を節約する手段として、ワイヤー上でコンパクトブロックをやり取りする。

本文書における「MUST」「MUST NOT」「REQUIRED」「SHALL」「SHALL NOT」「SHOULD」「SHOULD NOT」「RECOMMENDED」「MAY」「OPTIONAL」は、RFC 2119 に記載されるとおりに解釈される。

動機

歴史的に、ビットコインの P2P プロトコルはブロックリレーにおいて帯域幅効率があまり良くなかった。ブロック内のトランザクションは、そのブロックがリレーされる前に既に多数のノードにとって入手済みであることが多いにもかかわらず、リレー時にはブロック内のすべてのトランザクションが含まれる。これにより、ブロックを受信するノードには中程度のインバウンド帯域幅スパイクが生じるが、ピアより先にブロックを受信した一部のノードでは、非常に大きなアウトバウンド帯域幅スパイクが生じることがある。このようなスパイクが発生すると、コンシューマー向けインターネット接続がバッファブロートにより一時的に使用不能になることがあり、また、混雑の少ない他のピアへ重複してブロックを要求するのではなく待つことを選ぶリモートピアへのブロックのリレーが遅延することがある。

したがって、ブロックリレー時に使用される帯域幅を削減することは、ノードを運用する多くの個人にとって非常に有用である。

本作業の目標は明示的にブロック転送レイテンシーの削減ではないが、副次的効果としてブロック転送レイテンシーをかなり大きく削減する。加えて、本作業は、低レイテンシーのブロック転送を明示的に狙う将来の作業の基盤を形成する。

バージョン 1 向け仕様

想定されるプロトコルフロー

本プロトコルは、後述するとおり、利用可能なピアと帯域幅に応じて 2 通りの使い方を想定している。「高帯域幅」モードは、ノードが一部のピアに対してのみ有効化してよいモードで、sendcmpctメッセージ内の最初のブール値を 1 に設定することで有効化される。このモードでは、ピアは新しいブロックの告知を、（cmpctblockメッセージ経由で）短縮トランザクション ID を既に含めて送信し、場合によってはブロックの完全な検証を終える前にさえ送信する（上記画像内のグレーのボックスで示されるとおり）。一部のケースではそれ以上の往復が不要で、受信側は直ちにブロックを再構成し通常どおり処理できる。一部のトランザクションがローカルの情報源（すなわちメンプール）から入手できなかった場合は、getblocktxn/blocktxnの往復が必要となり、ベストケースのレイテンシーは、帯域幅使用量は大幅に少ないままながら、現在ノードが要する最小時間である 1.5*RTT と同程度になる。

「低帯域幅」モードは、sendcmpctメッセージ内の最初のブール値を 0 に設定することで有効化される。このモードでは、ピアは新しいブロックの告知を（BIP130 のとおり、かつブロックを完全に検証した後に）通常の inv/headers 告知で送信する。受信側ピアは、その後 MSG_CMPCT_BLOCK のgetdata要求を用いてブロックを要求でき、ヘッダーと短縮トランザクション ID の応答を受け取る。一部のケースではそれ以上の往復が不要で、受信側は通常どおりブロックを再構成し処理でき、帯域幅使用量は大幅に少ないままながら、現在ノードが要する最小時間である 1.5RTT を要する。一部のトランザクションがローカルの情報源（すなわちメンプール）から入手できなかった場合は、getblocktxn/blocktxnの往復が必要となり、この場合のレイテンシーは少なくとも 2.5RTT になるが、それでも今日と比べて帯域幅使用量は大幅に少ない。TCP はデータサイズが大きいほど（RTT の倍数として見た）転送レイテンシーが悪化する傾向があるため、完全な 2.5*RTT の転送機構が使われる場合であっても、総レイテンシーは削減されると見込まれる。

新しいデータ構造

コンパクトブロックをリレーするため、P2P ネットワークに新しいデータ構造がいくつか追加される：PrefilledTransaction、HeaderAndShortIDs、BlockTransactionsRequest、BlockTransactions である。

本節において、CompactSize とは、既存の P2P プロトコル全体で配列長などを 1、3、5、9 バイトのいずれかでエンコードするために使われる可変長整数エンコーディングを指す。本仕様が使用するのは、最小エンコーディング（すなわち可能な限り短い長さ）である CompactSize エンコーディングのみである。それ以外の CompactSize エンコーディングの挙動は未定義とする。

以下で使われる CompactSize の一部は「差分エンコード」される。これらについては、生のインデックスを使う代わりに、現在のインデックスと直前のインデックスとの差から 1 を引いた値がエンコードされる。たとえば、最初のインデックスが 0 であれば実際のインデックスは 0 を意味し、その後に 2 つ目のインデックスとして 0 が現れれば実際のインデックス 1 を指す、といった具合である。

PrefilledTransaction

PrefilledTransaction 構造体は、HeaderAndShortIDs の中で、少数のトランザクションを明示的に提示するために使われる。

HeaderAndShortIDs

HeaderAndShortIDs 構造体は、ブロックヘッダー、既に入手済みのトランザクションと照合するための短縮トランザクション ID、そしてピアが持っていないと予想される少数のトランザクションをリレーするために使われる。

BlockTransactionsRequest

BlockTransactionsRequest 構造体は、要求対象のブロック内のトランザクションインデックスを列挙するために使われる。

BlockTransactions

BlockTransactions 構造体は、要求に応じてブロック内の一部のトランザクションを提供するために使われる。

短縮トランザクション ID

短縮トランザクション ID は、256 ビットの完全なハッシュを送信することなくトランザクションを表現するために使われる。計算手順は以下のとおりである。

1. ナンスを付加したブロックヘッダー（リトルエンディアン）に対して単一 SHA256 ハッシュを計算する。
2. トランザクション ID を入力とし、鍵（k0/k1）に上記ハッシュの先頭 2 つのリトルエンディアン 64 ビット整数をそれぞれ設定して、SipHash-2-4 を実行する。
3. SipHash の出力から上位 2 バイトを取り除き、6 バイトにする。

新しいメッセージ

新しい inv タイプ（MSG_CMPCT_BLOCK == 4）と、いくつかの新しいプロトコルメッセージ（sendcmpct、cmpctblock、getblocktxn、blocktxn）が追加される。

sendcmpct

1. sendcmpct メッセージは、1 バイト整数に続けて 8 バイト整数を含み、pchCommand == “sendcmpct”であるメッセージとして定義される。
2. 最初の整数はブール値として解釈される（かつ値は 1 または 0 でなければならない（MUST））。
3. 2 つ目の整数はリトルエンディアンのバージョン番号として解釈される。sendcmpct メッセージを送信するノードは、現時点ではこの値を 1 に設定しなければならない（MUST）。
4. 最初と 2 つ目の整数が両方とも 1 に設定された sendcmpct メッセージを受信した場合、ノードは cmpctblock メッセージを送信して新しいブロックを告知すべきである（SHOULD）。
5. 最初の整数が 0 に設定された sendcmpct メッセージを受信した場合、ノードは cmpctblock メッセージを送信して新しいブロックを告知すべきではなく（SHOULD NOT）、BIP130 で定義されるとおり inv または headers を送信して新しいブロックを告知すべきである（SHOULD）。
6. 2 つ目の整数が 1 以外に設定された sendcmpct メッセージを受信した場合、ノードはそのピアからメッセージを受信しなかったものとして扱わなければならない（MUST）（このピアが cmpctblock、あるいはその他のメッセージにおいて想定外のエンコーディングを提供することを示すためである）。これにより、将来のバージョンでは、バージョンハンドシェイクの一部として異なるバージョンの sendcmpct メッセージを複数回送信できる。バージョンネゴシエーションの機構の詳細については、後述するプロトコルバージョニング節を参照。
7. ノードは、sendcmpct メッセージを送信する前に、プロトコルバージョンが 70014 以上であるかを確認すべきである（SHOULD）。
8. ノードは、あるピアから sendcmpct メッセージを受信する前に、そのピアに対して MSG_CMPCT_BLOCK オブジェクトの要求を送信してはならない（MUST NOT）。
9. ノードは、送信するつもりの sendcmpct メッセージをすべてそのピアへ送信し終える前に、MSG_CMPCT_BLOCK オブジェクトを要求してはならない（MUST NOT）。これは、そうしなければピアが応答に用いるべきバージョンプロトコルを知り得ないためである。

MSG_CMPCT_BLOCK

1. getdata メッセージには、MSG_CMPCT_BLOCK オブジェクトの要求を含められるようになる。
2. 最近告知され、受信側の最有力チェーンの先端に近いブロックのハッシュを求める MSG_CMPCT_BLOCK オブジェクトの要求を含む getdata を受信し、かつ要求元ピアに対して既に sendcmpct メッセージを送信済みの場合、ノードは要求されたブロックを表す適切なデータを含む cmpctblock メッセージで応答しなければならない（MUST）。
3. MSG_CMPCT_BLOCK オブジェクトの要求を含む getdata を受信し、それに対して cmpctblock メッセージで応答しない場合は、要求されたブロックを非コンパクト形式で含む block メッセージを送信しなければならない（MUST）。
4. MSG_CMPCT_BLOCK の inv オブジェクトは、getdata メッセージ以外のいかなる場所にも現れてはならない（MUST NOT）。

cmpctblock

1. cmpctblock メッセージは、シリアライズされた HeaderAndShortIDs メッセージを含み、pchCommand == “cmpctblock”であるメッセージとして定義される。
2. sendcmpct メッセージを送信した後に cmpctblock メッセージを受信した場合、ノードは自身が入手済みの未承認トランザクション（すなわちメンプール内のもの）それぞれについて短縮トランザクション ID を計算し、それぞれを cmpctblock メッセージ内の各短縮トランザクション ID と比較すべきである（SHOULD）。
3. 既に入手済みのトランザクションを見つけた後、ブロック全体を再構成するのに必要なトランザクションをすべて持っていないノードは、getblocktxn メッセージを用いて不足しているトランザクションを要求すべきである（SHOULD）。
4. ノードは、ブロック内のすべてのトランザクションを要求する getblocktxn メッセージに応答できる状態でない限り、cmpctblock メッセージを送信してはならない（MUST NOT）。
5. ノードは、ヘッダーがブロック内の各トランザクションに適切にコミットしていること、また、既存の完全検証済みチェーンの最有力チェーンの一部として、あるいはその直上に、有効なプルーフオブワークとともに適切に構築されていることを検証しない限り、cmpctblock メッセージを送信してはならない（MUST NOT）。ノードは、ブロック内の各トランザクションが既存の UTXO セットのエントリーを正当に使用しているかを検証する前に、cmpctblock を送信してもよい（MAY）。

getblocktxn

1. getblocktxn メッセージは、シリアライズされた BlockTransactionsRequest メッセージを含み、pchCommand == “getblocktxn”であるメッセージとして定義される。
2. 適切な形式の getblocktxn メッセージを受信した場合、このメッセージが特定するブロックハッシュについて最近そのメッセージの送信者に cmpctblock を提供したノードは、適切な blocktxn メッセージ、または完全な block メッセージのいずれかで応答しなければならない（MUST）。blocktxn の応答は、getblocktxn のインデックスリストで指定された、要求された順序で、対応するブロック内に存在する各トランザクションのみを、過不足なく含まなければならない（MUST）。

blocktxn

1. blocktxn メッセージは、シリアライズされた BlockTransactions メッセージを含み、pchCommand == “blocktxn”であるメッセージとして定義される。
2. 適切な形式で要求された blocktxn メッセージを受信した場合、ノードは以下により完全なブロックの再構成を試みるべきである（SHOULD）。
   1. 元の cmpctblock から prefilledtxn のトランザクションを取り出し、マークされた位置に配置する。
   2. 元の cmpctblock 内の各短縮トランザクション ID について、順番に、blocktxn メッセージまたは他の情報源から対応するトランザクションを見つけ、ブロック内の最初の空き位置に配置する。
3. ブロックが再構成されたら、短縮トランザクション ID が時折衝突することが想定されており、そのような衝突についてノードにペナルティを科してはならない（MUST NOT）ことに留意しつつ、通常どおり処理するものとする。

プロトコルバージョニング

1. プロトコルバージョンネゴシエーションにより、2 つのノードは互いにやり取りするコンパクトブロックのバージョンについて合意できる。これは単一のフィールドにしか存在しないため、ノードが送信方向と受信方向のうち一方のみで特定バージョンをサポートすることはできない。
2. 接続確立時、ノードは、cmpctblock および blocktxn メッセージの送信、ならびに getblocktxn メッセージの受信をサポートする意思のあるコンパクトブロックエンコーディングのすべてのバージョンを含む一連の sendcmpct メッセージを送信すべきである（SHOULD）。これらのメッセージは、ノードが cmpctblock/blocktxn メッセージを受信したい優先順位の順に並べ、最優先のバージョンの sendcmpct メッセージを最初に送信すべきである（SHOULD）。
3. cmpctblock または blocktxn メッセージの送信、あるいは getblocktxn メッセージの受信に用いられるエンコーディングバージョンは、同一のバージョン番号を持つ sendcmpct メッセージが送信済みである、最初に受信した sendcmpct メッセージ内の 2 つ目の整数（バージョン番号）でなければならない（MUST）。
4. ノードは、MSG_CMPCT_BLOCK オブジェクトの要求の送信、cmpctblock・getblocktxn・blocktxn・pong メッセージのいずれかの送信の後は、cmpctblock/blocktxn メッセージの受信について既にネゴシエーション済みのバージョン番号以外を含む sendcmpct メッセージを送信してはならない（MUST NOT）。
5. ノードは、新規のバージョン告知を含むすべての sendcmpct メッセージを、その他のコンパクトブロック関連メッセージより前に送信しなければならないため、受信した各オブジェクトについてどのバージョンのコンパクトブロックが使われるかを判定できる。ただし、MSG_CMPCT_BLOCK を含む getdata、cmpctblock、getblocktxn、blocktxn、ping/pong いずれかのメッセージが交換されるまでは、コンパクトブロックオブジェクトの要求に対する応答をどのバージョンでエンコードするかを知ることはできない。
6. したがって、コンパクトブロックオブジェクトを要求する前にどのバージョンのコンパクトブロックが使われるかを正確に判定したいノードは、自身の sendcmpct バージョン告知をすべて送信した後に ping を送信し、リモートピアからのすべての sendcmpctblock バージョン告知メッセージを受信し終えたことを確認するため pong の応答を待たなければならない。もっとも、ノードは、リモートピアからそのバージョンを 2 つ目の整数として含む sendcmpct メッセージを受信した後であれば、（自身の優先順位における）少なくとも特定のバージョンが使われることは当然判定できる。

実装例

1. 一例として、上記プロトコルの実装は以下のようになりうる。
2. version/verack メッセージの交換後、ノードは直ちに、受信を望むバージョンを先頭にして、自身の sendcmpct 告知のリストを相手側へ送信する。
3. リモートピアから理解可能なプロトコルバージョンを含む最初の sendcmpct 告知を受信すると、ノードは、そのピアに対してコンパクトブロックをエンコードする際に使うコンパクトブロックエンコーディングバージョンを「確定」する。
4. その後ノードは、その接続で使用中の現在の受信プロトコルバージョンをそのバージョンに設定し、それを用いて新しいコンパクトブロックメッセージをデコードする。
5. リモートピアから理解可能なプロトコルバージョンを含む後続の sendcmpct 告知（すなわち、逆方向の sendcmpct で既に告知されているバージョン）を受信すると、ノードは、そのプロトコルバージョンが接続で使用中の現在の受信プロトコルバージョンより受信優先度が高いかを確認し、高ければ受信する新しいコンパクトブロックメッセージのデコードに用いるバージョンをそちらへ切り替える。
6. ノードは、コンパクトブロック関連メッセージまたは pong メッセージのいずれかの受信時に設定できる、コンパクトブロックのバージョンネゴシエーションが完了したことを示すフラグを、ピアごとに保持したいと考えるかもしれない。
7. 上記の実装が必要とするのは、何らかの静的な優先順位順のサポートバージョンのコンパイル時リスト、ピアごとの 2 つのバージョンフィールド、そしてピアごとの任意のネゴシエーション完了ブール値のみである。

バージョン 2 向け仕様

コンパクトブロックのバージョン 2 はバージョン 1 とほぼ同一だが、segregated witness トランザクション（BIP 141 および BIP 144）をサポートする。変更点は以下のとおりである。

1. sendcmpct 内の 2 つ目の整数（バージョン番号）は、1 ではなく 2 である（上記のプロトコルバージョニング節を参照）。
2. cmpctblock メッセージ内のトランザクション（直接の告知として使われるものと、getdata への応答として使われるもの双方）および blocktxn 内のトランザクションは、BIP144 で規定される、getdata MSG_WITNESS_TX への応答と同じ形式でウィットネスデータを含めるべきである（should）。
3. cmpctblock メッセージで受信する、および getblocktxn メッセージで送信する短縮トランザクション ID は、バージョン 1 と同じ手順で計算されるが、txid の代わりに BIP 141 で定義される wtxid を用いる。ノードは通常はそうすべき（SHOULD）だが、コインベーストランザクションを含めない（すなわち短縮 ID を含める必要がある）場合、それは BIP 141 で定義されるウィットネス形式でそのトランザクションをエンコードして計算しなければならない点に留意する。
4. cmpctblock メッセージが応答として送信されない MSG_CMPCT_BLOCK オブジェクトの要求を含む getdata を受信した場合、要求されたブロックを非コンパクト形式で含む block メッセージは、cmpctblock メッセージのエンコードに使われたであろうプロトコルバージョンが 2 であればウィットネス付き（MSG_WITNESS_BLOCK の getdata への応答として送られる形式）でエンコードしなければならず（MUST）、そのバージョンが 1 であればウィットネスなし（MSG_BLOCK の getdata への応答として送られる形式）でエンコードしなければならない（MUST）。

実装上の注意

1. インバウンド帯域幅に十分な余裕があるノードについては、最大 3 つのピアに対して最初の整数を 1 に設定した sendcmpct メッセージを送信することが推奨される（RECOMMENDED）。可能であれば、それらのピアは、ブロックを速く提供した過去の実績（例えば、直近 N 個のブロックのうち最も多くを最も速く提供した 3 つのピア）に基づいて選ばれることが推奨され（RECOMMENDED）、これによりノードはそれらのピアから来るブロックをわずか 0.5*RTT で受信できるようになる。

2. ノードは、こうした sendcmpct メッセージを 3 つを超えるピアに送信してはならない（MUST NOT）。これはネットワーク全体でのアウトバウンド帯域幅の浪費を助長するためである。

3. すべてのノードは、適切なすべてのピアに対して sendcmpct メッセージを送信すべきである（SHOULD）。これにより、ピアが完全なブロックの代わりにコンパクトブロックを要求できるようになり、自身のアウトバウンド帯域幅使用量が削減される。

4. インバウンド帯域幅が限られたノードは、可能な場合は MSG_CMPCT_BLOCK/getblocktxn 要求を用いてブロックを要求すべきである（SHOULD）。これは最悪ケースのメッセージ往復回数を増やすものの、TCP は低帯域幅ノードでは低スループットを示しやすいため、全体の転送レイテンシーは削減されると見込まれる。

5. cmpctblock メッセージを送信するノードは、prefilledtxn を 10KB 分のトランザクションに制限すべきである（SHOULD）。判断に迷う場合、ノードは prefilledtxn にコインベーストランザクションのみを含めるべきである（SHOULD）。

6. ノードは、送信したいブロックごとに 1 つのナンスを選んでよく（MAY）、送信したい特定のブロックについてはすべてのピア向けに cmpctblock メッセージを一度だけ構築してよい（MAY）。ノードは、異なる複数のブロックにわたって同じナンスを使うべきではない（SHOULD NOT）。

7. ノードは、cmpctblock メッセージを送信して新しいブロックを告知するタイミングについて、追加の要件を課してもよい（MAY）。たとえば、アウトバウンド帯域幅が限られたノードは、アウトバウンド帯域幅を節約するため、（BIP130 のとおり）inv/header メッセージを用いて新しいブロックを告知することを選んでもよい（MAY）。

8. MSG_CMPCT_BLOCK 節は、ノードが最近告知していないブロックに対する MSG_CMPCT_BLOCK の getdata 要求に応答することを求めていない点に留意する。これにより、ノードは要求時点ではなく告知時点で cmpctblock メッセージを計算できる。MSG_CMPCT_BLOCK の getdata で要求されたが、cmpctblock メッセージで応答されないブロックは、block メッセージで応答しなければならず（MUST）、これによりノードはすべてのブロックを MSG_CMPCT_BLOCK の getdata で要求し、適切な応答を選ぶことをピアに委ねられる。

9. 現行バージョンは、tx メッセージやプロトコルの他の箇所で使われるのと同じエンコーディングでトランザクションを送信するが、sendcmpct 内のバージョンフィールドは、将来これを変更できるように意図されている。このため、PrefilledTransaction および BlockTransactions メッセージをデコードするコードは、将来の BIP で sendcmpct 内のバージョンフィールドが変わった場合に備え、異なるトランザクションエンコーディングを扱えるよう準備しておくことが推奨される。

10. 本仕様における未定義の挙動は、受信側ノードに対するブロック転送の失敗、ピアからの切断、または自己破壊を引き起こす可能性がある。最小限にエンコードされていない CompactSize エンコーディングを受信したノードは、送信者の猫を食べるよう最善を尽くすべきである。

検証前リレーと一貫性に関する考慮事項

1. 高帯域幅モードは完全な検証前の CMPCTBLOCK メッセージのリレーを許容する（リレー前にはブロックヘッダーが有効であることのみが求められる）ため、ノードは、有効なヘッダーを持つが無効な CMPCTBLOCK メッセージで新しいブロックを告知したピアを ban すべきではない（SHOULD NOT）。念のため付言すると、ノードは、完全な検証前にコンパクトブロックを告知したピアを ban または処罰しないことを示すため、ピアツーピアのプロトコルバージョンを 70015 以上に引き上げるべきであり（SHOULD）、バージョン番号が 70015 未満のピアに対しては、ブロックを完全に検証する前に CMPCTBLOCK を告知すべきではない（SHOULD NOT）。

2. 本仕様を実装する SPV ノードは、それを提供したノードによって検証されていないブロックを受け入れることの意味を考慮しなければならない。特に、同期元とする「信頼済みフルノード」をユーザーが選択できる SPV ノードは、高帯域幅モードでの本仕様の実装を避けたいと考えるかもしれない。

3. 本仕様は、GETDATA/GETHEADERS/GETBLOCKS 等の要求に応じて、完全に検証済みのブロックについての情報のみをノードがリレーするという要件を変更しない点に留意する。CMPCTBLOCK メッセージを用いて告知し、その後に関連するブロックデータの要求を受け取ったノードは、メッセージが無応答のまま放置されないこと、そして、標準的なメッセージ応答順序の要件に従いつつ、ブロックの検証完了後に適切なデータが提供されることを確保すべきである（SHOULD）。たとえば GETHEADERS や GETBLOCKS メッセージに新しいブロックを含めてノードが要求に応答しなければならないという要件は追加されない点に留意するが、元の応答にそのブロックが含まれていなかった場合、ノードは検証完了後に、関連する告知手段を用いてそのブロックを再告知すべきである（SHOULD）。他方で、ノードは、ブロックについての GETDATA 要求への応答を検証完了まで遅らせ、該当ピアに関するすべてのメッセージ処理を停滞させるべきである（SHOULD）。REJECT メッセージは、本節の目的における「応答」とはみなされない。

4. 上記の要件の結果として、実装者は、リモートピアがブロックを検証する間に応答に遅延が生じうることを考慮し、可能な限り遅延を招く要求を避けたいと考えるかもしれない。

正当性

プロトコル設計

ブロックのリレー時にワイヤーバイト数を節約するための提案はこれまで数多く存在する。それらの多くは、ブロックリレー時間の削減という二重の目標を持ち、そのため追加の最悪ケース RTT を生じさせないよう、かなりの処理能力の使用に依存している。本作業はブロックリレー時間の削減を主眼としていないため、その設計ははるかに単純である（すなわちセット照合プロトコルに依存しない）。それでも、本文書執筆時点でのテストでは、ノードは追加の getblocktxn/blocktxn の RTT なしに、約 90%の割合でブロックをリレーできている。賢いコンパクトブロック告知ポリシーを組み合わせれば、本作業により、ノード間でのブロックリレーが、少なくとも 75%の割合で 1.5RTT ではなく 0.5RTT で行えるようになると見込まれる。

短縮トランザクション ID 計算

短縮 ID 計算には、いくつかの設計目標がある。

• 性能送信側はブロック内のすべてのトランザクションについて短縮 ID を計算する必要があり、受信側は比較対象となるメンプール内のすべてのトランザクションについて短縮 ID を計算する必要がある。数千件のトランザクションを扱うことも容易にありうるため、トランザクションあたりサブマイクロ秒の処理が求められる。
• サイズ cmpctblock メッセージは本プロトコルにおいて常に必須であり、ブロック内のプリフィルされていない各トランザクションについて短縮 ID を含む。したがって、短縮 ID のサイズは、可能な最大の帯域幅節約量に直接比例する。
• 衝突耐性ネットワーク参加者が衝突を引き起こすトランザクションを作成することは困難であるべきである。攻撃者がそのような衝突を引き起こせた場合、それらでメンプール（ひいてはブロック）を埋めることで、新しい（あるいは、マイナー自身が攻撃者でない場合は非攻撃者の）ブロックのネットワーク伝播を悪化させることになる。

SipHash は、ネットワークトラフィックの認証と衝突耐性のあるハッシュテーブル向けに設計された、安全・高速・単純な 64 ビット MAC である。空間を最小化するため、SipHash-2-4 の出力を（次節で述べるとおり）48 ビットに切り詰める。この 48 ビットのハッシュは、意図的に作成された個別の衝突を避けるには確実に十分な大きさではないが、ブロックハッシュを SipHash の鍵として用いることで、攻撃者は、自身のトランザクションが実際にリレーされるブロックへ組み込まれるまで、どの鍵が使われるかを予測できない。接続ごとに独立した短縮 ID を得るため、接続ごとの 64 ビットナンスを混ぜ込んでおり、これによりブロック生成者であっても衝突がどこで起きるかを制御できず、偶発的な衝突が影響する接続数は常にごく少数に限られる。この混合はSHA256(block_header || nonce)を用いて行われ、SipHash に比べると低速だが、ブロックごとに一度しか行われない。これはまた、ノードが衝突を最小化するようランダムより良い方法でナンスを選ぶ余地を与えるが、それは正しい挙動のために必須ではない。逆に、ノードは、自身が中継するブロックにおいて衝突を発生させる能力を高めるためにこの余地を悪用することもできる。もっとも、ノードは単純にブロックのリレーを拒否するだけで既により多くの問題を引き起こせるため、これは避けられないことであり、本設計はネットワーク全体にわたる不正行為の防止のみを狙っている。

偶発的衝突の確率

ブロックヘッダーに基づく SipHash の鍵のおかげで、正直なノード間のリンク上で起きる衝突はすべて偶発的なものと仮定できる。

t個のブロック内トランザクションそれぞれについて、受信側は受け取った短縮 ID をm個のメンプール内トランザクションの集合と比較する。それらt個それぞれが、そのm個の集合に含まれる確率をrと仮定する。短縮 ID にBビットを使う場合、受け取った短縮 ID とメンプール内トランザクションとの比較ごとに、不一致がそのとおり検出される確率はP = 1 - 1 / 2^Bである。

あるブロック内トランザクションをメンプール内トランザクションの集合全体と比較する場合、区別すべきケースが 5 つある。

1. 受信側にちょうど 1件の一致があり、それが正しい一致である場合。この確率は*r * P^(m - 1)*である。
2. 受信側に一致が 1件もない場合。この確率は*(1 - r) * P^m*である。
3. 受信側に 2件以上の一致があり、そのうち 1件が正しい場合。この確率は*r * (1 - P^(m - 1))*である。
4. 受信側に 2件以上の一致があり、そのいずれも誤っている場合。この確率は*(1 - r) * (1 - P^m - m * (1 - P) * P^(m - 1))*である。
5. 受信側にちょうど 1件の一致があるが、それが誤っている場合。この確率は*(1 - r) * m * (1 - P) * P^(m - 1)*である。

（これら 5 つの数値は常に合計 100%になる点に留意）

ケース 1 であれば問題ない。ケース 2、3、4 では、不確かであることが分かっているため完全なトランザクションを要求する。再構成に失敗するのはケース 5 のみである。ブロック内のt個のトランザクションのいずれについてもケース 5 が発生しない確率は*(1 - (1 - r) * m * (1 - P) * P^(m - 1))^tである。この式は1 - (1 - r) * m * (1 - P) * t* = 1 - (1 - r) * m * t / 2^Bでよく近似される。したがって、正直なノード間の伝送のうち F 回に 1回のみ失敗することを、保守的なr = 0という仮定のもとで許容したい場合、*log2(F * m * t)*ビットのハッシュ関数が必要になる。

これは、B = 48ビットの短縮 ID があれば、最大t = 10000件のトランザクションを含むブロック、最大m = 100000件のトランザクションを含むメンプールにおいて、再構成の失敗が最大F = 281474ブロックに 1回に抑えられることを意味する。再構成の失敗は単に通常の inv/header ベースのリレーへフォールバックするだけを意味するため、そのような失敗を完全に避ける必要はない。必要なのは、（たとえばネットワーク切断やノード過負荷といった）ランダムな伝送失敗より影響が小さくなる程度に十分まれであることだけである。

segregated witness 向けの別バージョン

BIP 144 によるトランザクションおよびブロックリレーへの変更は、getdata 内に別個の MSG_FILTERED_版のメッセージを導入し、受信側がウィットネスデータを個別に必要かどうか選べるようにする。

この方式はコンパクトブロックには有用ではない。cmpctblockブロックは高帯域幅モードにおいて要求なしに送信されうるため、少なくともそれらがウィットネスデータを含むべきかどうかを事前にネゴシエーションする必要があるからである。ウィットネスデータを時々しか処理しない検証ノードにはほとんど意味がないため、このネゴシエーションをすべてに対して用い、別個のプロトコルバージョンとする方が理にかなっている。また、正しい再構成のためには、異なるウィットネスを持つ同一トランザクションの異なるバージョンを区別する手段も必要であり、このためこのケースでは短縮 ID のすべてで txid の代わりに wtxid を用いることが求められる。

後方互換性

古いクライアントは、本変更後も完全に互換性を保ち相互運用可能なままである。

実装

https://github.com/bitcoin/bitcoin/pull/8068 がバージョン 1 の実装。 https://github.com/bitcoin/bitcoin/pull/8393 がバージョン 2 の実装。

謝辞

初期の提案、そして数多くの往復にわたる設計と重要なテストについて、Gregory Maxwell に感謝する。 プロトコルフロー図について、ニコラ・ドリエに感謝する。

著作権

本文書はパブリックドメインに置かれる。