Gunosy Blockchain Blog

Gunosyの開発メンバーが知見を共有するブログです。

ビットコインのブロック伝搬とCompact Block Relay

はじめに

こんにちは。開発本部の @yamarkz です。

今回はビットコインネットワーク上のやりとりに注目して、マイニングされたブロックの伝搬手法を紹介します。

また、ブロック伝搬が抱える問題とその問題を解決する Compact Block Relay と呼ばれる新たな伝搬手法も紹介したいと思います。

f:id:yamarkz:20180109190820p:plain:w400

※今回はフルノードのブロック伝搬を想定しています。

ビットコインネットワークでのブロック伝搬

f:id:yamarkz:20180109235938p:plain:w400

ビットコインでは Proof of work と呼ばれる取引の証明作業 (マイニング) が行われ、ブロックが生成されます。生成されたブロックはチェーンに繋がれていきブロックチェーンを形成します。

また、マイニングされたブロックはノード間を伝搬 (以下、リレー) し、ビットコインネットワークに接続されている全てのノードに共有されます。

ブロックは無作為に関連ノードにリレーされるわけではなく、ノード間でメッセージのやりとりを行い、互いの状況を把握し、状況に応じてリレーを行っています。

具体的なリレーの流れを見てみます。例として、 送信元ノードA 受信元ノードB があり、AからBへブロックリレーを行う場面を想定します。

f:id:yamarkz:20180110181436p:plain:w400

  1. 送信元ノードAが invメッセージ をノードBへ送信

    invメッセージとは、 inventryメッセージ (在庫メッセージ) のことで、新しくチェーンに繋がれたブロックを関連ノードにアナウンスします。

  2. ノードBが getheadersメッセージgetdataメッセージ をノードAに送信

    ノードBはノードAからのinvメッセージにより、新しいブロックの存在のアナウンスを受けます。ノードBこの新しいブロックが自身のチェーンに繋がれていないことを知ると、ノードAにぶろっくをリレーするようにメッセージを送ります。このブロックを要求するのが getheadersメッセージgetdataメッセージ です。

  3. headersメッセージ でブロックヘッダーをノードBへ送信。続いて blockメッセージ でブロックデータをノードBへ送信

    ノードAはノードBからの要求に応じて、該当するブロックをノードBにリレーします。この時ブロックヘッダーとトランザクションの一覧が含まれるブロックデータは別々にリレーされます。

  4. 受け取ったブロックヘッダーとブロックデータの正当性を検証。正当性が証明されたブロックは自身のチェーンに追加され、関連ノードに invメッセージ を送信しアナウンスしていく。

このように、ブロックリレーではノードの状況 (チェーンの最新状態) をinvメッセージでアナウンスし、自身のチェーンに最新ブロックの追加が必要である場合にのみブロックを要求しリレーを行います。

ブロックリレー時の問題

invメッセージを用いたブロックリレーは、互いに関連ノードの状況を把握しリレーを行いますが、これはあまり効率の良い方法ではありませんでした。 それはブロックのリレー時にノードがトランザクションを2度受け取る状況になっており、通信帯域を無駄に使用してしまっているからです。

f:id:yamarkz:20180110002307p:plain:w400

1度目のトランザクション受け取りは、ネットワーク上にトランザクションがブロードキャストされるタイミングです。 ブロードキャストされたトランザクションはノードが持つメモリ空間の mempool (メモリプール) に保持され、ブロックと同様に関連ノードにトランザクションが共有されていきます。

f:id:yamarkz:20180111134036p:plain:w400

2度目のトランザクションの受け取りは、マイニングされたブロックがリレーするタイミングです。 mempool に存在するトランザクションがリレーされてきたブロック内にも含まれていた場合、そのブロックを受け取ることはノードで同一のトランザクションを受け取ることになります。

この様に、2度に渡って同一トランザクションをやりとりすることは、ネットワークの通信帯域を無駄に使用することになります。

実際に通信帯域が狭いネットワークに存在するノードがブロックリレーを行うことで、帯域が混雑しクリティカルなスパイクが発生していました。 その結果、ネットワークが一時的に切断されたり、通信遅延が発生するという状況が生まれていました。これによりユーザー側はトランザクションの承認が遅れたりする状況に遭遇することになります。

こういった問題を解決するために、効率的なブロックリレーの手法として Compact Block Relay が後発で考えられました。

使用する帯域幅を減らした Compact Block Relay という手法

Compact Block Relay (以下、CBR)は、BIP-152で定義されているノード間でのブロックリレー手法の1つです。CBRは上記で紹介した通常のブロックリレーよりもネットワーク帯域幅の使用量を減らしてリレーを行います。 その結果、ネットワークが一時的に切断されるなどのクリティカルな帯域幅スパイクを削減することができます。 また、帯域幅の使用量を減らすことは副次的にブロックリレーのレイテンシーを減らすことにもなります。

CBRは 2016/08/25 にリリースされた bitcoin core 0.13.0 から導入された PeerServiceレイヤー の機能で、後方互換性があります。 また、初期リリース後も都度改善が行われ、bitcoin core 0.14.0 ではsegwitトランザクションに対応した version 2 がリリースされています。

Compact Block Relay の基本的な仕組み

CBRでは「スケッチ」と呼ばれるcompact blockデータを用いてブロックリレーを行います。

CBRには2つのモードが存在します。 高帯域モード 低帯域モード です。

どちらもスケッチのやり取りを行いますが、若干手順が異なります。この2つのモードの仕組みとその違いを見ていきます。

先ほどと同じく、ブロックの送信元をノードA、ブロックの受信元をノードBとし、ノードAからノードBへスケッチをリレーする場面を想定します。

スケッチ (compact block)

CBRでは「スケッチ」と呼ばれるデータを送受信します。 スケッチでは新たに定義された、「HeaderAndShortIDs」「PrefilledTransaction」というデータ構造が用いられます。

スケッチに含まれるデータは以下

  • BlockHeaderAndNonce
    • 80バイトのブロックヘッダーとnonce値 (nonce値は送信先ノードごとにランダムに付与する)
  • ShortTransactionID
    • 短縮されたトランザクション識別子(計算式から算出する短略化されたトランザクションID)
  • PrefilledTransaction
    • 受信側のピアがおそらく持っていないと思われるトランザクションデータ (ex: コインベーストランザクション)

上記のデータをやりとりし、ブロックリレーを行います。

高帯域モード (High band width)

f:id:yamarkz:20180111124307p:plain:w400

高帯域モードでスケッチの送信を有効化するため、ノードBはノードAに sendcmpct を送信します。この時メッセージの第1引数には 1 をセットします。

高帯域モードでは、 ブロックの検証終了前 に関連ノードにスケッチを送信します。

ブロックヘッダーの正当性検証が終了後、ノードAはノードBに対してスケッチを送信します。 スケッチにはBlockHeaderとnonce値、ShortTransactionIDの一覧、そしてPrefilledTransactionの一覧が含まれており、受け取ったノードBはこのスケッチを基にブロックを再構築します。

以降、高帯域と低帯域 同一のブロック再構築フロー ↓

ノードBはブロックを再構築するため、受け取ったスケッチを基にブロックに含められたトランザクションの探索を行います。 トランザクションの探索は自身のmempoolにある未承認トランザクションからShortTransactionIDを算出し、スケッチで受け取ったShortTransactionIDと比較します。 この比較でIDが一致するものを探していきます。この探索により発見されたトランザクションはブロックにセットしていきます。

ShortTransactionIDの計算はスケッチで受け取ったBlockHeaderのハッシュ値とnonce値、そして自身のmempoolに存在する未承認トランザクションのIDを基に行います。

算出は下記の図の様に行われます。実際の算出ロジックは こちら に定義されています。

f:id:yamarkz:20180111124351p:plain:w400

全ての未承認トランザクションの探索を行い、該当するトランザクションを揃えることができた場合、受け取ったブロックヘッダーとPrefiiledTransactionで受け取ったトランザクションと共にブロックを構築し正当性検証を行います。

もし、探索で該当するトランザクションが見つからなかった場合は、送信元であるノードAに不足分のトランザクションをリクエストします。

ノードAはこのリクエストに応じて該当するトランザクションをレスポンスとして返します。

そして、全てのトランザクションが揃った時点で、ブロックヘッダーとPrefiiledTransactionで受け取ったトランザクションと共にブロックを構築し正当性検証を行います。

検証後、正当性が証明されればブロックを自身のチェーンに追加し、自身の関連ノードにブロック情報をinvメッセージでアナウンスしていきます。

低帯域モード (Low band width)

低帯域は高帯域と比較するとスケッチリレー部分が異なっており、ブロックの再構築は高帯域と同じフローで行われます。

f:id:yamarkz:20180111124233p:plain:w400

低帯域モードでスケッチの送信を有効化するため、ノードBはノードAに sendcmpct を送信します。この時メッセージの第1引数には 0 をセットします。

低帯域モードでは、 ブロックの検証終了後 に関連ノードにスケッチを送信します。

ノードAはブロックの検証が終了後、そのブロックの正当性が証明された場合はブロックを自身のチェーンに追加します。 そして自身のチェーンに追加後、invメッセージ でノードBにアナウンスします。

メッセージを受け取ったノードBは、自身のチェーンよりもノードAのチェーンが伸びていることを知ります。 ノードBは自身のチェーンを最新状態に保つために、自身のチェーンに不足しているのブロックをスケッチで送信するよう getdata(CMPCT) メッセージを送信します。

このメッセージを受け取ったノードAは該当するブロックのスケッチを送信します。

スケッチにはBlockHeaderとnonce値、ShortTransactionIDの一覧、そしてPrefilledTransactionの一覧が含まれており、受け取ったノードBはこのスケッチを基にブロックを再構築します。

以降、高帯域と同一のブロック再構築フローになります。

2つのモードの違いとまとめ

2つのモードで異なるのはスケッチリレーの部分。

高帯域は一方的にリレーを行いますが、低帯域はメッセージのやりとりを行い、要求があった場合にのみリレーを行います。

通常のブロックリレーも使われるが、最新のブロックを追う場合はCBRを用いたリレーを行う方がメリットが大きい。

(余談ですが、高帯域と低帯域という表現の意味は以下の理由からです。)

高帯域モードは関連ノードの状況を考慮せずリレーを行います。 これは一方的にリレーを行うので、結果的に不要なリレーも発生することになります。 発生した不要なリレーは帯域を無駄に使用すること (帯域幅の浪費) に繋がるので、 高帯域 という表現がされている。

低帯域モードはリレー前にメッセージやりとりを行い、リクエストがあった場合にのみリレーを行います。 高帯域より多くのメッセージを介すものの、リクエストがあった場合にのみリレーが行われます。 状況に応じてリレーを行うことは帯域の使用量を減らすこと (帯域幅の節約) に繋がるので、 低帯域 という表現がされている。

Compact Block Relay の 技術仕様

詳細な技術仕様の紹介は今回割愛させていただきますが、詳細が気になる方に「ここは見るべき!」と思った情報ソースをまとめておきます。

恐らく疑問思うと思われる「短略トランザクションIDの衝突確率」や「バージョン1とバージョン2の共存の仕組み」などは BIP-152 に解説が記載されているのでそちらをご覧ください。

まとめ

今回の内容をざっくりとまとめると。

ブロックはメッセージのやり取りを介してリレーを行う。

通常のブロックリレーは帯域を無駄に使用することになりクリティカルなスパイクが発生する問題があった。

スパイクが発生する問題を解決するために、効率的なブロックリレーの手法としてCompact Block Relayが考えられた。

CBRは1Mのブロックをリレーせず、ブロックヘッダー、短略トランザクションID、特定のトランザクションをリレーするのでリレーするデータの容量が小さくて済む。

リレー後は渡ったデータを基にブロックの再構築を行いチェーンに繋げていく。

最後に

今回はビットコインネットワークに注目して、基本的なブロックリレーの流れと新しく考えられた Compact Block Relay という手法を紹介しました。

PeerServiceレイヤーの改善はあまり注目されていませんが、Compact Block Relay はフルノードを持つユーザーにとっては大きな機能追加でした。

今回詳細な技術仕様までは触れることができなかったのですが、Compact Block RelayはBIPやリリースノートに詳細に解説が記載されていますので気になる方はそちらご覧ください。

宣伝

Gunosyではブロックチェーンを始めとしてスマートスピーカー、VR/ARと言った新規領域での研究・開発を進めており、メンバーを募集しています。

少し話を聞いてみたい!という方も歓迎していますので、下記のリンクからの応募お待ちしております。

www.wantedly.com

また弊社は、blockchain.tokyo を主催するなど、ブロックチェーンや仮想通貨に関する調査を行っています。

次回は1/16に、メルカリさんに会場をお借りしてイベントを開催します。残念ながら今回の募集は終了してしまいました。 来月は弊社を会場に開催する予定です。少しでも興味のある方は下記リンクからのご参加お待ちしております。 また、イベントグループへメンバー登録をしていただくとイベント参加者募集の通知が来るのでこちらもぜひ登録してみてください。

blockchain-tokyo.connpass.com