Bitcoin ネットワークの参加とピア接続について

この記事では、Bitcoin におけるネットワークへの参加方法とピア接続する仕組みについてまとめていく。（※この記事は bitcoind version 0.9.3 に基づいているため、最新バージョンとは挙動がことなるところがある）

Bitcoin におけるネットワークへ参加方法

新しいノード（A）を立ち上げたとき、接続先として他のノード（B）を見つける必要がある。B に接続するためには TCP 接続を確立（デフォルトでは 8333 番ポート）し、VERSION メッセージを送信することでハンドシェイクを始める。B は接続を承認し確立するために VERACKメッセージを返す。ではどのようにしてピアを見つけるのか？

ピアの見つけ方

ピアを見つけるには主に3つの方法がある。

DNS シードについて

2020 年 2 月時点では、DNS シードは以下の 8 つがあるようだ。この DNS シードは BitcoinCore のソースコードに書かれており、Github から確認できる。

メッセージタイプについて

ネットワーク情報の伝搬

Bitcoin では各ノードは外部に接続する異なる8つピア（outgoing connections : 外部接続）を選択するためにランダマイズプロトコルを使用している。また、最大 117 個の外部から接続されるピア（incoming connections : 内部接続）を受け入れている。（プライベート IP アドレスを使用している場合、内部接続を持つことはできない。）
ノード間の接続は TCP 上で行われており、パブリック IP のみ保存し伝搬させる。そのピアがパブリック IP かどうかは、IP パケットと Bitcoin の VERSION メッセージを比較することで確認できる。この章では、ノードがどのようにネットワーク情報を保存し伝搬しているかについて解説する。
ネットワーク情報は DNS シードと ADDR メッセージを通して Bitcoin ネットワークを伝搬する。DNS シードにクエリを送るのは２パターンある。1つ目は、新しいノードがネットワークに初めて参加する時である。そのノードはアクティブなノードのリストを DNS シードから得る。それ以外の場合は、約 600 の IP アドレスがハードコーディングされたリストにフェイルオーバーする。2つ目は、既存のノードがオフラインの状態からネットワークに復帰し新しいピアと再接続をしたい時である。ここで、DNS シードはそのノードが接続の確立を試みてから 11 秒が経過し、2つ未満の外部接続を持っている場合のみクエリされる。

ネットワーク情報の保存

パブリック IP はノードの tried テーブルと new テーブルに保存されている。テーブルはディスクに保存され、ノードがリスタートする時にも保持される。tried テーブルは 64 個のバケットからなり、それぞれに内部接続もしくは外部接続の確立に成功したピアのアドレスを最大 64 個保存できる。保存されたピアのアドレスに加えて、ノードはこのピアの成功した最も最近の接続のタイムスタンプを保持している。各ピアのアドレスはピアの IP アドレスとその IP アドレスを含む /16 IPv4 プレフィックスとして定義された group のハッシュ値を取ることによって tried のバケットにマッピングされる。バケットは以下のように選ばれる。

# SK = random value chosen when node is born
# IP = the peer's IP address and port number
# Group = the peer's group
i = Hash(SK, IP) % 4
Bucket = Hash(SK, Group, i) % 64
return Bucket

あるノードがあるピアに接続が成功した場合、そのピアのアドレスは適切な tried バケットに挿入される。もしそのバケットが満杯の場合、bitcoin eviction が使用され、4つのアドレスをそのバケットからランダムに選び、tried テーブルから最も古いピアを新しいピアに置き換えて、new テーブルに挿入する。そのピアのアドレスがすでにバケットに入っている場合、そのピアの IP アドレスに関連したタイムスタンプを更新する。タイムスタンプはアクティブに接続されたいるピアが VERSION, ADDR, INVENTORY, GETDATA, PING メッセージを送った時や最後の更新から 20 分以上経過した場合にも更新される。
new テーブルは 256 個のバケットでできており、それぞれにノードがまだ正常な接続を開始していないピアの最大64個のアドレスを保持できます。ノードは DNS シードもしくは ADDR メッセージから情報を得たことによって new テーブルに現れる。new テーブルに挿入されたすべてのアドレス aa はそのアドレスの group と、接続されたピアの IP アドレスもしくはアドレス aa を教えてくれた DNS シードが含まれているグループ（source group）に属しているところに挿入される。バケットは以下のように選ばれる。

# SK = random value chosen when node is born
# Group = /16 containing IP to be inserted
# Src_Group = /16 containing IP of peer sending IP
i = Hash(Sk, Src_Group, Group) % 32
Bucket = Hash(SK, Src_Group, i) % 256
return Bucket

各（group, source group）ペアは各 group が new テーブルに最大 32 個のバケットを選びながら、単一の new バケットにハッシュする。各バケットは一意のアドレスを持つ。もしバケットが満杯の場合、isTerrable と呼ばれる関数がバケット内のすべての 64 個のアドレスに対して実行される。もし、アドレスが terrible な場合（30 日以上たっている、もしくは接続失敗が多すぎた）、その時にそのアドレスは取り除く。そうでなければ bitcoin eviction を実行し、そのアドレスが破棄される小さな変更で済む。

接続ピアの選択

新しい外部接続は、あるノードがリスタートするかある外部接続がネットワークから離脱したら選択される。Bitcoin ノードはブラックリストに載ったものに出会った時を除いて、故意に接続をドロップすることはない。ω ∈ [0,7] 個の外部接続を持つノードは ω+1 番目接続を以下のように選ぶ。
（1）tried, new どちらのテーブルから新しいピアを選択するか決定する。以下の式が tried から選ぶ確率である。ρ は tried と new テーブルに入ったアドレスの数の比率である。

\begin{align} Pr = \frac{\sqrt{\rho}(9 - \omega)}{(\omega + 1) + \sqrt{\rho}(9 - \omega)} \end{align}

（2）より新しいタイムスタンプに偏ってテーブルからアドレスを選択する。（i）そのテーブルから空でないバケットをランダムに選ぶ。（ii）そのバケットからピックアップする位置をランダムに選ぶ。もしその位置にアドレスが存在していればそのアドレスを以下の確率で返す。

\begin{align} p(r, \tau) = min(1, \frac{1.2^r}{a + \tau}) \end{align}

そうでなければ、そのアドレスを拒否し（i）に戻る。受理確率 p(r,τ) は r と τ の関数であり、r は拒否されたアドレスの数を表し、τ はアドレスのタイムスタンプと現在の時間との違い（10分ごとに計測する）を示している。
（3）アドレスに接続する。接続に失敗したら（1）に戻りやり直し。

まとめ

今回は Bitcoin ノードがどのようにネットワークに参加するか、どのように接続相手を選択しているかについてまとめた。この記事では bitcoind version 0.9.3 に基づいて書いているが、Eclipse Attack の影響緩和のため現在のバージョンでは一部が変更されているはずである。Eclipse Attack についての記事と、その後の変更点については次回以降の記事でまとめる。