Develop with pleasure!

福岡でCloudとかBlockchainとか。

Block受信時に重複したトランザクションの受信を抑制するCompact Block（BIP-152）

BIP Bitcoin

BIPに登場してからマージ＆デプロイまで結構なスピード感で導入されたBIP-152。
フルノードでは、ブロードキャストされたトランザクションの受信と、マイニングされたブロック受信時にブロック内に含まれるトランザクションとで、同じトランザクションの情報を２度受信する。この重複したデータの受信を回避するために新しくBIP-152としてCompact Blockという仕様が提案されたので見てみる。

bips/bip-0152.mediawiki at master · bitcoin/bips · GitHub

動機

歴史的にBitcoinのP2Pプロトコルはブロックを中継するのに効率的ではなかった。ブロックが中継される際そのブロックに含まれるトランザクションの大半が、既に中継先のノードにあったとしても、中継されるブロックには全てのトランザクションが含まれる。これによりブロック受信時にはインバウンドの帯域幅には適度なスパイクが発生するが、アウトバウンドの帯域幅においては重大なスパイクを引き起こす可能性がある。このようなスパイクが発生すると、バッファの膨張によりインターネット接続が一時的にできなくなったり、リモートピアへのブロックの中継が遅れる。

そのためブロックを中継する際の帯域幅を減らすことはノードを実行している多くの人にとって有用である。

このBIPの目的はブロック転送のレイテンシーを少なくすることではないが、副次的にブロック転送のレイテンシーを大きく減少させることになる。また将来的に低レイテンシーのブロック転送をするための基盤を形成する。

仕様

Intended Protocol Flow

https://github.com/bitcoin/bips/raw/master/bip-0152/protocol-flow.png

プロトコルは利用可能なピアと帯域幅に応じて、２つの方法で使われることが意図されている（後述となってるけどリンク切れ）。いくつかのピアのみに有効な”high-bandwidth”モードは、 sendcmpct メッセージ内の最初のbooleanに１をセットすることで有効になる。このモードでは、ピアは上図の灰色のボックスで記述しているように完全にBlockの検証をする前であっても、cmpctblockメッセージを介してShort transaction IDsを使った新しいブロックのアナウンスを送信する。場合によっては追加のメッセージのやりとりを必要とせず、受信側はブロックを再構築しすぐにその新しいブロックを扱えるようになる。一部のトランザクションがローカルのmempoolに存在しない場合は、 getblocktxn / blocktxn メッセージのやりとりが必要になり、大幅に少ない帯域幅とはいえ現在のノードがとる1.5*RTTの最小時間と同様の待ち時間が発生する。

”low-bandwidth”モードは sendcmpct メッセージ内の最初の最初のbooleanに０をセットすることで有効になる。このモードでは、ピアは（BIP-130に従い完全にブロックを検証した後）通常のinv/headersで新しいブロックのアナウンスを送信する。受信側のピアは続いてMSG_CMPCT_BLOCKのgetdataリクエストを使ってブロックを要求すると、ブロックヘッダとShort transaction IDsのレスポンスが返ってくる。場合によっては追加のメッセージのやりとりを必要とせず、受信側はブロックを再構築することで新しいブロックが扱えるようになる。現在のノードがとる1.5RTTの最小時間を割くことになるが、使用する帯域幅は大幅に少なくなる。一部のトランザクションがローカルのmempoolに存在しない場合は、 getblocktxn / blocktxn メッセージのやりとりが必要になり、この場合2.5RTTの待ち時間が発生する。TCPではよくデータサイズが大きい場合の転送レイテンシーは悪化するため、トータルのレイテンシーは2.5*RTT transferメカニズムを使用しても低減することが期待できる。

新しいデータ構造

compact blocksを中継するため、PrefilledTransaction、HeaderAndShortIDs、BlockTransactionsRequest、BlockTransactionsといったいくつかのデータ構造がP2Pネットワークに追加される。

CompactSizeは既存のP2Pプロトコルを介してやりとりされる配列の長さをエンコードするための可変長整数のエンコーディングを指す。この仕様でも最小限のエンコードをするためCompactSizeを使用する。

CompactSizeのいくつかの用途は以下の”differentially encoded”*1になる。この場合、rawインデックスを使用する代わりに、エンコードされた数は現在のインデックスと前のインデックスの差分となる。

PrefilledTransaction

PrefilledTransaction構造は、明示的にいくつかのトランザクションのリストを提供するためにHeaderAndShortIDsで使われる。

フィールド名 タイプ サイズ エンコーディング 目的
index CompactSize 1, 3 bytes Compact Size。リスト内の最後のPrefilledTransactionからのdifferentially encoded。 このトランザクションがブロック内のどこにあるかを示すインデックス
tx Transaction 可変 エンコードされた"tx"メッセージ indexで指定されたブロック内のトランザクション
HeaderAndShortIDs

HeaderAndShortIDs構造はブロックヘッダを中継するのに使われ、 short transactions IDsを既に利用可能な（受信済みの）トランザクションを一致させるのに使用し、ピアがまだ受信していないいくつかのトランザクションを選別する。

フィールド名 タイプ サイズ エンコーディング 目的
header Block header 80 bytes ブロックの最初の80バイト。エンコーディングは"block" メッセージにて定義されている。 配布されたブロックのヘッダ
nonce uint64_t 8 bytes リトルエンディン short transaction IDを計算するのに使うnonce
shortids_length CompactSize 1 or 3 bytes 配列の長さをエンコーディング shortids内のshort transaction IDsの数（＝ブロックのトランザクション数 − prefilledtxn_length）
shortids List of 6-byte integers 6*shortids_length bytes リトルエンディン prefilledtxnで明示的に提供されなかったトランザクションから計算したshort transaction IDs
prefilledtxn_length CompactSize 1 or 3 bytes 配列の長さをエンコーディング prefilledtxn内のprefilled transactionsの数（＝ブロックのトランザクション数−shortids_length）
prefilledtxn List of PrefilledTransactions variable size * prefilledtxn_length ↑のPrefilledTransactionにて定義 コインベーストランザクションとピアで欠落されていると思われる少数のトランザクションを提供するのに使われる。
BlockTransactionsRequest

BlockTransactionsRequest構造は要求されたブロック内のトランザクションのインデックスをリスト化するのに使われる。

フィールド名 タイプ サイズ エンコーディング 目的
blockhash Binary blob 32 bytes ブロックヘッダをダブルSHA256した結果 要求されたトランザクションが含まれるブロックのブロックハッシュ
indexes_length CompactSize 1 or 3 bytes 配列の長さをエンコーディング|要求されたトランザクションの数
indexes CompactSizesのリスト 1 or 3 bytes * indexes_length differentially encoded 要求されたトランザクションのブロック内のインデックス
BlockTransactions

BlockTransactions構造は要求されたブロック内のいくつかのトランザクションを提供するのに使われる。

フィールド名 タイプ サイズ エンコーディング 目的
blockhash Binary blob 32 bytes ブロックヘッダをダブルSHA256した結果 提供されるトランザクションが含まれるブロックのブロックハッシュ
transactions_length CompactSizes 1 or 3 bytes 配列の長さをエンコーディング 提供されるトランザクションの数
transactions トランザクションのリスト 可変 エンコードされた"tx" メッセージ 提供されるトランザクション
Short transaction IDs

Short transaction IDsは完全な256-bit hashを送ることなくトランザクションを表現するために使われる。Short transaction IDsは以下の手順で計算する。

  1. ブロックヘッダに（リトルエンディンでエンコードされている）nonceを付加したデータのSHA-256ハッシュを計算する
  2. トランザクションIDと１のハッシュのから最初の２つのリトルエンディンの64bit 整数をk0/k1にセットしたkeyをインプットとしてSipHash-2-4*2を実行する。
  3. ２のSipHashで生成したハッシュ値から最上位２バイトを落として６バイトにする。

新しいメッセージ

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

sendcmpct
  1. sendcmpctメッセージは、１バイトの整数の後に8バイトの整数が続きpchCommand == "sendcmpct"を含むメッセージとして定義されている。
  2. 最初の整数はbooleanとして解釈される（そのため値は0か1）
  3. ２番目の整数はリトルエンディンでエンコードされたバージョン番号として解釈される。ノードがsendcmpctメッセージを送信する際、現在は必ず１をセットする必要がある。
  4. 1番目と２番目の値に1がセットされた"sendcmpct"メッセージを受信した場合は、ノードはcmpctblockメッセージを送ってブロックをアナウンスする必要がある。
  5. １番目の値に0がセットされた"sendcmpct"メッセージを受信した場合は、cmpctblockメッセージを送ってブロックをアナウンスするべきではなく、BIP-130に定義されているようにinvもしくはheadersの送信でブロックアナウンスしなければならない。
  6. 2番目の値に１以外の値がセットされた"sendcmpct"メッセージを受信した場合は、ノードはピアについてピアがメッセージを受信していなかったものとして扱う必要がある。（ピアから予期せぬエンコードのcmpctblockを受けっとったこと意味する）将来的にバージョンが増えると、バージョンのハンドシェイクのために異なるバージョンで重複したsendcmpctメッセージを送信できるようになる。
  7. ノードはsendcmpctメッセージを送る前にプロトコルのバージョンが70014以上であることをチェックする必要がある。
  8. ノードはピアからsendcmpctメッセージを受信する前に、ピアにMSG_CMPCT_BLOCKオブジェクトの要求を送ってはいけない。
MSG_CMPCT_BLOCK
  1. getdataメッセージにはMSG_CMPCT_BLOCKオブジェクトの要求が含まれているかもしれない。
  2. ブロックのハッシュを持つMSG_CMPCT_BLOCKオブジェクトを要求するgetdataメッセージを受信すると、ノードは要求されたブロックを表現する適切なデータを含むcmpctblockメッセージで応答しなければならない。
  3. cmpctblockメッセージがレスポンスにセットされていないMSG_CMPCT_BLOCKオブジェクトへの要求を含むgetdataメッセージを受信した場合は、要求されたブロックについて非compact形式のメッセージを送らなければならない。
  4. MSG_CMPCT_BLOCK invオブジェクトはgetdata以外のメッセージに出現してはならない。
cmpctblock
  1. cmpctblockメッセージはシリアライズされたHeaderAndShortIDsとpchCommand == "cmpctblock"を含むメッセージとして定義されている。
  2. sendcmpctメッセージを送信後、cmpctblockメッセージを受信すると、ノードはmempool内にある未確認の各トランザクションのshort transaction ID を計算しcmpctblockメッセージ内のshort transaction IDと比較する必要がある。
  3. mempool内に既に該当するトランザクションを探したあと、ブロックを構築するのに不足するトランザクションがある場合はgetblocktxnメッセージを使って不足しているトランザクションをリクエストする。
  4. ブロック内の全トランザクションを要求するgetblocktxnに応答できない場合、ノードはcmpctblockメッセージを送ってはいけない。
  5. ノードはヘッダの内容がブロック内の各トランザクションと矛盾が無いか、proof-of-workによって計算したハッシュにより既存のチェーンの最後に続くことが可能か、検証せずにcmpctblockメッセージを送信してはいけない。ただブロック内の各トランザクションの検証の前にcmpctblockメッセージを送ることはある。
getblocktxn
  1. getblocktxnメッセージはシリアライズされたBlockTransactionsRequestメッセージとpchCommand == "getblocktxn"を含むメッセージとして定義されている。
  2. 適切なフォーマットのgetblocktxnメッセージを受信すると、メッセージ内に確認できるブロックハッシュのcmpctblockメッセージを送信者に提供したノードはは、適切なblocktxnメッセージで応答しなければならない。そのblocktxnメッセージには、getblocktxnメッセージのインデックスリストで指定されたブロック内に存在する個々の正確なトランザクションが含まれていなければならない。
blocktxn
  1. blocktxnメッセージは、シリアライズされたBlockTransactionsとpchCommand == "blocktxn"を含むメッセージとして定義されている。
  2. 適切なフォーマットのblocktxnメッセージを受信すると、ノードは以下の手順でブロックを再構築する必要がある。
    1. オリジナルのcmpctblockからprefilledtxnトランザクションを取得し、マークされた位置に配置する。
    2. オリジナルのcmpctblockの各short transaction IDについては、順番にblocktxnメッセージからもしくは他のソース（mempool内？）から対応するトランザクションをみつけ、ブロック内に配置する。
  3. ブロックが再構築されたら、あとは通常通り処理する。またshort transaction IDはときおり衝突することが考えられるが、ノードはそのような衝突についてペナルティを課してはならない。

実装上の注意事項

  1. 充分なインバウンドの帯域幅は持つノードの場合、３つまでのピアに対して最初の引数に1をセットしたsendcmpctメッセージを送信する（＝high-bandwidthモードで動作させる）ことを推奨する。可能であれば、ここで選択する３つのピアは過去の実績において素早くブロック情報を返すピアを選択することが推奨され、ノードはそれらのピアからほんの0.5*RTTでブロックを受信することが可能になる。
  2. ノードは（アウトバウンドの帯域幅をムダに使用することになるため）３つ以上のピアにhigh-bandwidthモードのsendcmpctメッセージを送ってはならない。
  3. 全てのノードは適切なノード全てにsendcmpctメッセージを送信する必要がある。ピアに対して既存のfull blocksの代わりにcompact blocksを要求することで、そのピアのアウトバウンドの帯域幅は削減することが可能になる。
  4. インバウンドの帯域幅が限られているノードは、可能であればMSG_CMPCT_BLOCK/getblocktxn要求を使ってブロックを要求する必要がある。最悪の場合メッセージのラウンドトリップを増加させるが、（低帯域幅においてTCPのスループットが低下することからも）全体的な転送待ち時間を削減することが期待できる。
  5. cmpctblockメッセージを送っているノードは、prefilledtxnを10KBのトランザクションに制限する必要がある。疑わしい時は、ノードはprefilledtxnに入れるのはコインベーストランザクションのみにすること。
  6. ノードは送信するブロック毎にnonceを選択してよく、ブロックを送信したい全てのピアに対して一度だけcmpctblockを構築する。ノードは複数の異なるブロック間で同じnonceを使用してはならない。
  7. ノードはcmpctblockメッセージを送信して新しいブロックをアナウンスする際に追加の要件を課すこともできる。例えば、アウトバウンドの帯域幅が限定されているノードは、アウトバウンドの帯域幅を節約するため新しいブロックをアナウンスするのにinv/headerメッセージの使用（BIP-130）を選択してもいい。
  8. MSG_CMPCT_BLOCKセクションは、直近でアナウンスしていないブロックに対するMSG_CMPCT_BLOCK getdataリクエストに必ずしも応答しないことに注意する必要がある。そのためノードはリクエスト時ではなくアナウンス時にcmpctblockメッセージを計算することが可能になる。MSG_CMPCT_BLOCK getdataを使ってブロックを要求したが、cmpctblockメッセージで応答しない場合はblockメッセージで応答する必要がある。そのためノードはMSG_CMPCT_BLOCK getdataを使って全てのブロックを要求して、適切なレスポンスを返すかはピアに依存する。
  9. 現在のバージョンではトランザクションを送付する際、プロトコルの他で使われているのと同じエンコーディングを使用しているが、sendcmpctメッセージのversionフィールドはこれを将来的に変更できるよう用意されている。そのため将来のBIPでsendcmpctのversionフィールドに変更が入ることを考慮して、PrefilledTransactionとBlockTransactionsのメッセージをデコードする際に使用するコードは異なるトランザクションエンコーディングを取る準備をしておくことを推奨する。
  10. この仕様で未定義の動作は、ブロックの転送の失敗や受信ノードによるピアの切断、自己破壊を引き起こす可能性がある。

Justification

プロトコル設計

ブロックを中継する際、wire bytesを保存するための多くの提案があった。この仕様では、ブロックの中継時間の短縮にフォーカスしていないので設計はよりシンプルである。執筆時点のテストでは、時間の90%前後にあたる余計なgetblocktxn/blocktxn RTTを必要とせずにブロックを中継することができた。compact-block-announcemenポリシーでは、1.5RTTでなく0.5RTTでノード間のブロックの中継を可能にするかもしれない。

Short transaction IDの計算

Short ID calculationについてはいくつかの設計目標がある。

  • Performance
    送信者はブロック内の全トランザクションについてShort transaction IDを計算する必要があり、受信者はmempoorl内のトランザクションとそれらを比較する比較する必要がある。我々は数千トランザクションレベルの話をしているいので、１トランザクションあたりマイクロ秒単位で処理する必要がある。
  • Space
    cmpctblockメッセージはこのプロトコルではオプションになることはなく、ブロック内のnon-prefilledトランザクションにはShort IDが含まれている。そのためShort IDのサイズはそのまま最大帯域幅の節約と比例する。
  • Collision resistance（衝突耐性）
    ネットワークの参加者が衝突を引き起こすトランザクションを作成するのは難しくすべきである。もし攻撃者がそのような衝突を引き起すことができると、それでmempoolをいっぱいにし、新しいブロックの伝搬に支障をきたす。

SipHashはネットワークトラフィック認証と衝突耐性ハッシュテーブルのために設計されたシンプルな64-bit MACでセキュアかつ高速である。我々はスペース削減のためSipHash-2-4の結果から48bitまで出力を切り詰める。得られた48bitのハッシュは意図的に作成された個々の衝突を避けるのに充分な大きさとはいえないが、SipHashのキーととしてブロックハッシュを使うことで、攻撃者は中継されたブロックのトランザクションに対しどのキーが使用されるか予め予測することはできない。我々は、全ての接続において独立したShort IDを得るため、接続毎に64bitのnonceをミックスする。そのためブロックの作成者がどこで衝突が起きるか制御することはできず、ランダムな衝突が影響するのも少数のコネクションに対してのみとなる。nonceの混合はSHA256（block_header || nonce）を使って行われる。これはSipHashと比べると遅いが、計算されるのはブロックあたり１回だけ。また必須ではないが、衝突を最小限にするためnonceの選択をランダムよりも良い選択方法を取るよう機能を追加することも可能だ。逆にノードはブロック内の衝突を増加させるためにこの機能を悪用することもできるが、ブロックの中継を拒否することでより多くの問題を引き起こす可能性がある。必然的にこの設計はネットワーク全体の誤動作を防止することを目的とする。

ランダムな衝突確率

ブロックヘッダベースのSipHashキーのおかげで、正直なノード間のリンク上で唯一の衝突がランダムなものであると仮定できる。

tブロックの各トランザクション tについて、受信者は m 個のmempool内のトランザクションと受信したShort IDを比較する。t が m 内にある確率を r と仮定する。受信したShort IDとmempoolのトランザクションの比較のため、我々がB bitのShort IDを使用したとして、ミスマッチとなる確率はP = 1 - 1 / 2B。

与えられたブロックをmempoolの全トランザクションのセットと比較する際は、５つのケースが考えられる。

  1. 受信側に正確に合致する１つのデータがある。この場合の確率はr * Pm - 1
  2. 受信側に合致するものが無い場合。確率は(1 - r) * Pm
  3. 受信側で合致するのが２つあり、そのうち正しいのは１つの場合。その確率は r * (1 - Pm - 1)
  4. 受信側で合致するのが２つあり、どちらも正しくない場合。その確率は(1 - r) * (1 - Pm - m * (1 - P) * Pm - 1)
  5. 受信側で合致するのが１つあり、ただそれは正しくない場合。その確率は(1 - r) * m * (1 - P) * Pm - 1

ケース１の場合は良い。ケース２，３、４の場合、不確実な状態であるためフルトランザクションを要求する。ケース５の場合、ブロックの再構築に失敗する。ケース５でブロック内のtトランザクションにいずれも存在しない確率は(1 - (1 - r) * m * (1 - P) * Pm - 1)t。この表現は1 - (1 - r) * m * (1 - P) * t = 1 - (1 - r) * m * t / 2Bで近似される。したがって、正直なノード間でr = 0の仮定のもと、F ブロックの伝送が１回で失敗してほしい場合、log2(F * m * t) bitのハッシュ関数が必要になる。

これは、ブロックのt = 10000トランザクションまで、mempoolのmが100000トランザクションまでB=48bitのShrot IDで充分であることを意味する。ブロックの再構築に失敗するのは281474ブロックに１つ。再構築に失敗しても通常のinv/headerベースへのフォールバックするだけなので、再構築の失敗を完全に回避する必要はない。それにそのようなケースは送信の失敗（ネットワークの切断やオーバーロードされたノードなど）より稀である。

後方互換性

古いクライアントはこの変更後も完全な互換性と相互運用性がある。（Compact Block使って通信しないだけだかから）

実装

↓のプルリク参照 github.com

まとめ＆所感

  • 現状の仕様だとブロック中継時にブロック内の全トランザクションの情報も中継されるけど、中継先のノードが既にトランザクション情報を知っている場合、ブロック中継時にそのトランザクションのデータも全部送るというのはムダなので、それを削減すると中継するデータ量の削減になると。
  • ブロックデータを受信する際に、sendcmpctを送ることでCompact Blockを扱うようになる。
  • Compact Blockには２つのモードがあり、sendcmpctメッセージにセットするboolean値が１であればhigh-bandwidthモード、０であればlow-bandwidthモードになる。high-bandwidthモードで通信するピアは３つまで。
  • ”high-bandwidth”モードでブロックの検証が終わる前に新しいブロックのアナウンスしてもOKなのは、最終的にブロックは検証すればいいし、ネットワークの帯域的にそれがムダになっても問題にならないレベルと解釈するのでいいのか？
  • cmpctblockメッセージを送る前にヘッダの整合性（ブロック内の各トランザクションデータとの矛盾やブロックハッシュが正しいか）については検証する必要がある。
  • Short transaction IDを計算する際にSipHashのキーにブロックハッシュを利用することでキーの衝突の可能性を下げる。
  • 受信側がCompact Blockで受信したブロックの再構築に失敗した場合は、従来のinv/headerメッセージを使った方法にフォールバックすればいい。
  • cmpctblockメッセージを受信したノードがmempool内のトランザクションの照合にtxidではなくshort transaction IDを計算して使うのは、short transaction IDの計算にnonceを使うあたりからCompact Blockに含めるデータサイズの削減以外にtxidの衝突を防ぐ意味とかがあるんだろうか？
  • 衝突の確率部分の計算がイマイチよく分かってない。
  • みんなリトルエンディン好きね。

バージョン２（追記）

↑に加えてバージョン２が定義されていたので追記↓

techmedia-think.hatenablog.com

*1:差動符号化

*2:意図的にハッシュの衝突を起こすDoS攻撃を回避するためのハッシュ関数の１つで64bitのハッシュ値を生成する