Scaling Bitcoin 2019復習シリーズ第三弾は、「TxProbe: Discovering Bitcoin's Network Topology Using Orphan Transactions」
- 動画：https://youtu.be/-gdfxNalDIc?t=11751
- 書き起こし： http://diyhpl.us/wiki/transcripts/scalingbitcoin/tel-aviv-2019/txprobe/
- ホワイトペーパー： https://arxiv.org/pdf/1812.00942.pdf
TxProbeは、Bitcoinネットワークのネットワークトポロジーを推定するための方法。ここで推定するBitcoinネットワークは基本的にパブリックに到達可能なノードで構成されるネットワークで、NATやファイアウォールの背後にあり到達不可能のノードや、インバウンド接続を受け入れないノード（軽量ノードなど）は対象外となる。
※ Bitcoin Coreはデフォルトで８つのアウトバウンド接続を作成する。この時選択される接続先のピアはランダムに選択されるが、/16 (ipv4)ネットワークセグメントが重複しない形で選ばれる。またこの他にインバウンド接続を受け入れる。
到達可能なノードについては、Bitnodesなどのサイトで確認できる。Bitnodesでは、getaddr/addrメッセージを利用して入手したノードに実際にアクセスするクローラーを利用して到達可能なノードを検出している。ただし、こうやって得られるのは到達可能なノードの情報のみと、それらのノードがどのようなネットワークトポロジーを形成しているかは分からない。
このノード間のエッジを推定しネットワークトポロジーを推定するための手法がTxProbeだ。
オーファントランザクションと二重使用トランザクションの扱い
TxProbeの調査方法は、Bitcoin Coreのオーファントランザクションと二重使用トランザクションのハンドリング方法に依存している。
トランザクションのハンドリング
ノードがトランザクションを受信し、検証するとそのトランザクションはメモリプールに格納され、接続中のピアに伝播される。ノードは直ぐに接続中のピアにトランザクションを送るのではなく、まずinvメッセージを使ってトランザクションの存在を通知する。そして、送信先のピアが該当トランザクションを持っていない場合getdataメッセージでトランザクションデータ自体を要求する。既に該当トランザクションを持っている場合はgetdataメッセージは送られない。
オーファントランザクションのハンドリング
オーファントランザクションのハンドリングは通常のトランザクションのハンドリングとは異なる。オーファントランザクションはそのインプットが参照するUTXOのトランザクションがまだそのノードに届いていないので、オーファントランザクションを受信してもそのトランザクションが有効なトランザクションかどうか検証することができない。そのためノードはMapOrphanTransactionsとして知られるメモリプールとは別のオーファンプールに格納される。またトランザクションの検証が出来ていないためこのオーファントランザクションが接続中のピアにリレーされることもない。
二重使用トランザクションのハンドリング
二重使用トランザクションは単純に同じコイン（UTXO）を使用する２つめのトランザクションで、このトランザクションを受信したノードは、最初のトランザクションのみを受け入れ、２つめの二重使用トランザクションは受け入れない。
基本的なネットワーク・トポロジーの推定手法
上記のトランザクションのハンドリング方法を利用すると、次のようにしてネットワーク・トポロジーの推定ができる。
まず以下の３つのトランザクションを作成する。
- 親トランザクション（
）
- マーカートランザクション（
）
親トランザクションのコインを使用する子トランザクション - フラッドトランザクション（
）
親トランザクションと同じコインを使用する二重使用トランザクション
BitcoinやBitcoinベースのアルトコインのネットワークのテストや監視、測定を行えるツールであるCoinscope*1を使用し、アリスとボブ２つのノードと接続するネットワークを仮定する。
Coinscopeで、
- アリスのノードには
- ボブのノードには
これが同時に到着すると仮定した場合、アリスはボブにをボブはアリスに
をリレーしようとするが、お互いにとって通知されたトランザクションは二重使用トランザクションであるため、両者とも受けとったトランザクションを拒否する。
その後アリスにを送信する。
を受け取ったアリスは、それをボブにリレーする。この時点でアリスとボブのメモリプールとオーファンプールの状態は以下のようになる。
| アリス | ボブ | |
|---|---|---|
| メモリプール | ||
| オーファンプール |
アリスとボブのノード間にエッジが存在する場合、上記のようにボブのノードのオーファンプールにはが存在している状態になる。このエッジが存在するかどうかの確認はCoinscopeが、ボブのノードに対して
を通知する
invメッセージを送信した際のボブのノードの反応で判断できる。ボブとアリスの間にエッジが存在すれば、ボブはをオーファンプールに持っているので、
invに対してgetdataを要求することはない。逆にアリスとボブのノード間にエッジが無ければ、ボブはについて知らないので、Coinscopeの
invに対してgetdataを要求する。
以下はアリスとボブの間にエッジが存在しないパターンの構成：
で、アリスとボブのメモリプールとオーファンプールの状態は↓
| アリス | ボブ | |
|---|---|---|
| メモリプール | ||
| オーファンプール |
と簡単にエッジ検出できそうに思えるが、これはあくまでノード数が２つの場合に機能するが、ノード数が増えると破綻する。例えばアリスとボブの間にキャロルのノードが加わった場合に、Coinscopeがアリスにを送った際、
をアリスがキャロルにリレーするのを止められないので、ノードが増えると上記の手法はワークしない。
TxProveのトポロジー推定手法
上記の基本的な推定手法を、多くのノードが存在する状況で行えるようにするためには、TxProveでは、invBlockと呼ばれる手法を利用する。invBlockというのは、トランザクションを通知する際にinvで通知し、その要求がgetdataで来た際にトランザクションの送信を2分間ほど保留することでトランザクションの伝播を防ぐ手法（2分以上経過すると別のノードに問い合わせる）。
例えば、アリス、キャロル、ボブのネットワークを考える。
まず、Coinscopeが全ノードに対して、の
invを送信する。すると３ノードともそのトランザクションを要求するgetdataで返信するが、このうちアリスの要求に対してのみtxメッセージでを送る。すると
を受信したアリスがキャロルに対して
の
invを送信してもキャロルはすでにCoinscopeから最初にの
invを受け取っているので、アリスのinvには応答せず２分間待機している。続いてをボブに送信すると、ボブはそれをキャロルにリレーする。また
をアリスに送信すると、それはキャロルにリレーされるが、キャロルは
を持っていないので
をオーファンとして扱い、各ノードの状態は以下のようになる。
| アリス | キャロル | ボブ | |
|---|---|---|---|
| メモリプール | |||
| オーファンプール |
上記のようにinvBlockの仕組みを利用することで、対象トランザクションを特定のノードに固定することができるので、この仕組みを利用して以下の手順でトポロジーを計測する。
- ターゲットノードを選択
- ターゲットノード用に親、マーカー、フラッドトランザクションを作成する。
- invBLockを実行する。
- ターゲットノード以外の全ての接続ノードにフラッドを送信し、フラッドを伝播させる。
- 親をターゲットに送信する。
- マーカーをターゲットに送信する。
- マーカーが伝播する。
- ターゲットを除くすべてのノードにマーカーを要求する。
ネットワーク内の全てのノードに対して↑を実行する。
TxProbeのコスト
mainnet（約１万のノード）でTxProbeを実行するコスト見積もりは以下のようになっている。
- 時間： 8.25時間
- 手数料 = (5 sat/byteとした場合) 573210〜764280 satoshi（$20〜$30）
実際にmainnetでは検証されておらず、testnetで40回ほど検証が施行され、グラフ分析した結果が↓のような結果だったみたい。観測されたネットワークにはノードが733個で、6090個のエッジがあり、平均して16.6の接続数となっている。
サークルの大きさは接続数の多さを表現しており、色がコミュニティを表している。ランダムグラフよりも高いコミュニティ構造を持ったグラフになっている。testnetとmainnetではインセンティブも違うのでこの傾向がmainnetにもそのまま当てはまるということはないだろうが、実際にmainnetでどのようなネットワークトポロジーが形成されているかは観測してみないと分からない。この辺、誰かmainnetで計測したりしないかなー。
なお、TxProbeは↑のようなBitcoin Coreのトランザクションのハンドリング方法に依存した仕組みなので、トランザクションの伝播方法が変わるといずれそのままでは使えなくなってしまうだろう。
