Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bitcoinネットワークの安全性を向上させるための新しいトランザクションリレープロトコル「Erlay」

先日、Gleb Naumenko, Pieter Wuille, Gregory Maxwell, Sasha Fedorova, Ivan Beschastnikhらが発表したBitcoinの新しいトランザクションリレープロトコル「Erlay」について論文読んでみた↓

https://arxiv.org/pdf/1905.10518.pdf

現在のトランザクションリレープロトコル

現在、Bitcoinトランザクションリレーは以下のプロセスで行われている。

f:id:techmedia-think:20190611105900p:plain
現在のBitcoinトランザクションリレーフロー

  1. ノード(Peer 1)が接続中のピアからトランザクションを受信する。
  2. Peer 1はそのトランザクションについて、そのトランザクションのハッシュをINVメッセージを使って、接続中の(まだそのトランザクションのハッシュをINVで送っていない)他のピアにトランザクションをアナウンスする。
  3. INVメッセージを受け取ったノード(Peer 2)は、そのハッシュのトランザクションについて自身が知らない場合、送信元のPeer 1にGETDATAメッセージを送信しそのトランザクションを要求する。
  4. GETDATAメッセージを受信したノードは(Peer 1)は、該当するトランザクション情報をGETDATAの送信元(Peer 2)にTXメッセージで送信する。

新しいトランザクションを受信したピアが、そのトランザクション情報を自身が接続している全てのピアに一斉に送信する(正確にはピア毎にランダムな遅延時間がある)このような方式をフラッディング方式と呼ぶ。なお、Bitcoinネットワークには、以下の2種類のノードが存在する。

  • パブリックノード
    8つのアウトバウンド接続とデフォルトで最大125のインバウンド接続(インバウンド接続の最大値は1000まで設定可能)を持つノード(一般的なフルノード)
  • プライベートノード
    8つのアウトバウンド接続を持つが、インバウンド接続は持たないノード(トランザクションを検証できいない軽量ノードとかはこっち)

このフラッディング方式は非常に単純でトランザクションの存在をBitcoinネットワーク全体に素早く伝播するという点では効果的だ。だが、効率的ではない。ノードが接続中のインバウンド、アウトバウンドピア全てに配信するため、各ピアが既に自身が知っているトランザクションハッシュ値INVメッセージで受け取ることが多い。Bitcoinの場合トランザクションハッシュ値は32バイトなので、1つのトランザクションのリレーについて、32バイト×冗長なメッセージの個数分、ネットワークの帯域幅を無駄に使用していることになる。

論文で言及されている分析結果では、トランザクションのアナウンスに使われている帯域幅の88%が冗長で、それは使用される全帯域幅の44%を占めるとされている。

一方、Bitcoinのネットワークを堅牢にするためには、各ノードが繋がるノードの数を増やす必要がある。ネットワークの接続性が高いほどネットワーク・セキュリティも向上する。しかし、現状のリレープロトコルのままアウトバウンドの接続数を増やすと、帯域幅の使用量もリニアに増えてしまう。

Erlayプロトコル

↑のようなリレープロトコルの冗長性を軽減し、接続数に対してスケール可能な新しいリレープロトコルがErlayだ。Erlayではトランザクションのリレーを以下の2段階(ファンアウト、reconciliation)で行う。

ファンアウトフェーズ

フラッディング方式は、情報素早くネットワーク全体に伝播するという意味では効果的なので、これを限定的に利用する=ファンアウトフラッディング。このフェーズでは、パブリックノードがアウトバウンド接続のみを使って*18つのピアに対し新しいトランザクションの存在をフラッディングする。パブリックノードのアウトバウンド接続のリンクを使ってトランザクションを受け取るのはインバウンド接続を許可している同じくパブリックノードであるため、このフラッディングではパブリックノード間にトランザクションを迅速に伝播していくことになる。

この時、現状8つであるアウトバウンド接続のピアの数を将来的に増やしたとしても、ファンアウトフェーズでフラッディングするピアの数は8つのままとする。そうすることで8つ以上アウトバウンド接続を増やしてもトランザクションの伝播コストはそれに比例して増えることはない。

set reconciliationフェーズ

↑のファンアウトフェーズだけではトランザクションはネットワークの全体には行き渡らない。特にプライベートには行き渡らない。そこで続けてset reconciliationフェーズを実行する。

set reconciliationフェーズでは、P2Pネットワーク内のノードはローカルの状態と接続しているピアの状態を定期的に比較し、必要な情報(状態の差分)のみを送信/要求する。つまり各ノードは自分が知っているトランザクションセット(状態)を累積し、あるタイミングで接続先のピアとトランザクションセット(状態)の差を計算し、自身に不足しているトランザクションのみを要求する。

この二者間の状態セットの差分の計算と不足データの復元を効率的に行うためのライブラリが以前公開された、エラー訂正符号に基づいた帯域幅効率の高いMinisketchだ↓

GitHub - sipa/minisketch: Minisketch: an optimized library for BCH-based set reconciliation

Erlayを実装したピアは、Minisketchを利用してローカルの状態セットのSketchを計算し、set reconciliationを実行する。ここで計算するSketchは以下の2つの特性を持つ。

  • Sketcheは事前定義された容量を持ち、セット内の要素数がその容量を超えなければ、sketchをデコードすることでsketchからセット全体を復元することが常に可能である。容量cで、bビットの要素のsketchはbcビットで保存できる。
  • 2つのセットの対称差のsketchは、2つのセットのsketchのビット表現をXORすることで得られる。

具体的には、次のプロセスで二者間のトランザクションセットを同期する。アリスとボブがそれぞれ要素のセットを持っているとする。両者のセットは大部分が同じであるが、完全に同じではない。この場合両者は自分に不足している要素を学習するために以下のプロセスを実行する。なお、実際に両者が持つセットの要素というのはトランザクションの短い識別子(短縮txid)で構成される。

  1. アリスとボブは共にローカルでそれぞれのセットのsketchを計算する。
  2. アリスは自分のsketchをボブに送る。
  3. ボブは2つのsketchを結合し、対称差のsketchを入手する。
  4. ボブは対称差のsketchから要素の復元を試みる。
  5. ボブはアリスにアリスが持っていない要素を送り、ボブが持っていない要素をアリスに要求する。

このプロセスはセットの差のサイズ(アリスが持っているがボブは持っていない要素+ボブが持っているがアリスは持っていない要素)がアリスが送ったsketchのサイズを超えない場合は常に成功する。そうでない場合、手順は失敗する可能性がかなり高い。

この手順の重要な特性は、実際のセットサイズに関係なく機能することで、セットの差のサイズだけが重要になる。

上記のようにファンアウトフェーズで伝播されなかったトランザクションは、その後のset reconciliationフェーズでノード間のトランザクションのセットの差異を効率的に解消することでネットワーク全般にトランザクションがいきわたること保証する。プライベートノードは基本的にそのアウトバウンド接続先であるパブリックノードとset reconciliationを実行することでトランザクションを同期する。

f:id:techmedia-think:20190611152535p:plain
フラッディングとset reconciliationを組み合わせたトランザクションリレーフロー

Sketchのデコードに失敗した場合

set reconciliationは二者間のセットの差分の上限が予測可能であるという仮定に依存している。つまり、実際の差分が見積もりよりも大きい場合、Sketchのデコードに失敗する。この場合ノードは二分法を使って再度set reconciliationを試みる。これでも失敗する場合、従来のフラッディングによりトランザクションを通知する。

set reconciliationの実行スケジュール

各ノードは1秒ごとに1つのアウトバウンドピアとreconciliationを開始する。この設定で現在のプライベートノードとパブリックノードの比率では、各パブリックノードが1秒間に約8回のreconciliationを実行する。現在の最大Bitcoinネットワークトランザクションレートが7トランザクション/秒であると仮定すると、このプロトコルの平均差分セットのサイズは7要素。毎秒1回新しいピアに対して繰り返され、ファンアウトアナウンスを介して受信しなかったトランザクションを迅速に受信できる。

拡散遅延

従来のBitcoinのフラッディング方式ではトランザクションのアナウンスにランダムな遅延を入れることで、タイミング攻撃および飛行中の衝突*2を軽減している。Erlayにおいては、各フェーズの拡散遅延は以下のようになる。

ファンアウトの拡散遅延

ファンアウトフラッディングはアウトバウンド接続のピアに対してのみ行われるため、タイミング攻撃および飛行中の衝突の心配がないため、レイテンシーを減らすこともあり、より小さな拡散インターバルは1秒。

set reconciliationの拡散遅延

set reconciliationフェーズではタイミング攻撃の可能性が考えられることから、それをコスト高にするため、各ピアにreconciliation要求に応える前に小さなランダムな遅延(平均1秒であるポイズン分布の確率変数)を設けるのを強制する。

Erlay導入の効果予測

限定されたフラッディング方式の利用と断続的なreconciliationを組み合わせた代替プロトコルであるErlayの論文で紹介されているシミュレーション結果(60000ノードのシミュレーションネットワークと、複数のデータセンターにまたがって国際的に広がる100ノードのライブセットの両方を使ってパフォーマンスを分析している)では、Erlayが新しいトランザクションの存在をアナウンスするのに使われる帯域幅の84%を削減するという結果が出ている。この帯域幅の削減効果は大きく、将来的にBitcoinネットワークの接続性を向上させ、ネットワーク・セキュリティを向上させるために重要な改善と言える。

ただ、トランザクションがネットワーク全体に伝播するまでにかかる時間は約2.6秒長くなるとされている。この点については、トランザクションの承認は10分に1回であるという側面もあることからトレードオフとしては問題の無い範囲のように思える。

特に異議がなければ今後Bitcoin Coreに実装されていくことになるだろう。P2Pネットワークのような分散環境を堅牢にしていくための地道な取り組みを行っていくのがBitcoinらしくて良い!

*1:インバウンド接続ではなくアウトバウンド接続を利用するのは、タイミング攻撃を防ぐためでもある。

*2:同じタイミングで接続中のノードがそれぞれ同じトランザクションを相手に送り合う