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の実装。

謝辞

初期の提案、そして何度もやり取りを重ねた設計と重要なテストについて、グレゴリー・マクスウェルに感謝する。 プロトコルフロー図について、ニコラ・ドリエに感謝する。

著作権

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