Eclipse Attacks on Bitcoin's Peer-to-Peer Network

Eclipse Attacks on Bitcoin’s Peer-to-Peer Network

著：Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg

※この論文は bitcoind version 0.9.3 を元に書かれていることに注意してください。

Introduction

Bitcoin では各ノードは外部に接続する異なる8つピア（outgoing connections）を選択するためにランダマイズプロトコルを使用している。また、最大 117 個の外部から接続されるピア（incoming connections）を受け入れている。（プライベート IP アドレスを使用している場合、内部接続を持つことはできない。）

Bitcoin はオープンでパブリックなシステムであるが、これは攻撃者も容易にネットワークに参加できることを表している。Eclispe Attack は攻撃者が犠牲者ノード（以下：ターゲット）の外部接続先と内部接続先のピアを独占する攻撃であり、ターゲットを残りのネットワークから隔離する。攻撃者はターゲットのビュー（ブロックチェーンの状態に関するデータ）をフィルタリングすることができ、ターゲットのコンピュータパワーを浪費させることや、自分らの無法な目的に協力させたりすることができる。攻撃者がエンドホストを制御する off-path 攻撃を提示するが、ターゲットと残りのビットコインネットワーク間の主要なネットワークインフラストラクチャは制御していない。この攻撃は攻撃者の管理する IP アドレスのエンドホストの集合からターゲットへの内部接続を素早く繰り返して形成し、嘘のネットワーク情報を送信し、ターゲットが再起動するまで待つことを含む。高確率でそのターゲットはすべての8つの外部接続を攻撃者の管理するアドレスで形成し、ターゲットの117個の内部接続も独占する。

この攻撃は極度に低レートの TCP コネクションを使用しているため、十分な数の IP アドレスを得ることが主要な課題である。（また、これらの攻撃はパブリック IP アドレスを持ったノードらにのみ有効である。もし、プライベート IP アドレスを使用しているノードの外部接続が攻撃を受けたパブリックアドレスノードの場合は影響を受ける可能性がある。）

攻撃には2つの種類がある。（1）インフラストラクチャ攻撃：複数の連続した IP アドレスを持ち、そのP2Pネットワークを攻撃することで bitcoin を壊そうとする ISP や企業の脅威をモデル化する。（2）ボットネット攻撃：多様なアドレス範囲によるボットによって開始される。

大規模なマイナーや商人クライアント、オンラインウォレットなどはネットワーキングコード変更することでネットワークによる攻撃のリスクを軽減することがよく知られている。2つの対策が一般的に推奨されている。（1）内部接続を無効にする。（2）ホワイトリスト等を使ってよく接続しているピアや知られているマイナーを特定の外部接続として選択する。しかし、（1）は新規ピアノ参加ができなくなる。（2）は接続する「特定の」ピアをどのように決定するか、という問題がある。

Implication of eclipse attacks

Engineering block races
ブロックレースは2つのマイナーが同時にブロックを発見した時に発生する。1つはブロックチェーンの一部になるが、もう一方の「オーファンブロック」は無視され、それを見つけたマイナーのマイニング報酬はゼロになる。攻撃者は攻撃によって隠したマイナーによって発見されたブロックを持っておき、競合するブロックが見つかると攻撃したターゲットとそうでないグループ両方のマイナーにブロックを放すことによって、ブロックレースを設計できる。したがってターゲットグループのマイナーはオーファンブロックに労力を費やす。
Splitting mining power
マイナーの $x$ 割を隠すことでそれらのマイニングパワーを残りのネットワークから除くことができ、マイニング攻撃（51％攻撃）をより簡単にできる。自然な変化の下でのマイニングパワーの変化を隠すために、マイナーは徐々にもしくは断続的に隠さなければならない。
Selfish mining
Selfish mining では、攻撃者は公正にマイニング報酬をシェアするよりも多くの報酬を得られるようにブロックを戦略的に保持している。攻撃の成功は2つの値によってパラメタ化されている。$\alpha$：攻撃者によって管理されているマイニングパワーの割合。$\gamma$：ブロックが競合している時に攻撃者のブロックをマイニングする誠実なノードの割合。$\gamma$ が大きい時、$\alpha$ は小さくできる。マイナーを隠すことによって攻撃者は $\gamma$ を増やし、$\alpha$ を減らすことで Selfish mining は簡単になる。このために、攻撃者は利己的なマイナーによって発見されたブロックと競合する、隠したマイナーによって発見されたブロックをドロップする。次に攻撃者は、利己的マイナーのブロックチェーンビューのみを隠したマイナーに与えることで $\gamma$ の値を増やす。これによって隠したマイナーのコンピュータパワーを利己的マイナーのブロックチェーンをマイニングすることに利用することができる。マイナーへの攻撃はビットコインエコシステム全体に害がある。マイニングプールはパブリックビットコインネットワークへのゲートウェイが隠されることが可能なら脆弱である。Eclipse attack は二重使用攻撃にも利用することができる。
0-confirmation double spend
ゼロ確認トランザクションでは、ブロックを確認する前に、つまりブロックチェーン内にそのトランザクションがあるかどうかを確認する前に顧客は商品を送る側である商人にトランザクションを発行している（料金を払っている）。これらのトランザクションはブロックの確認に 5 - 10 分待つのが不適切である時に使用されている（BitPay、Betcoin など）。二重使用をするためには、攻撃者は商人のノードを隠し、商人にトランザクション（$T$）を送信する。その後、同じコインを使用するトランザクション（$T'$）を残りのネットワークに対して発行する。商人はトランザクション（$T$）を確認し、商品を配送する。しかし、もう一方のトランザクション（$T'$）の存在は知らない。残りのネットワークではトランザクション（$T'$）が入ったブロックチェーンが作成されており、その後トランザクション（$T$）は無効となり二重使用攻撃が成功する。
N-confirmation double spend
攻撃者が $x$ 割のマイナーを隠した場合、$N$ 確認二重攻撃が可能である。$N$ 確認トランザクションでは、商人はそのトランザクションが入ったブロックの後に $N - 1$ 個のブロックが続いたことを確認した時のみ商品を発送する。攻撃者はトランザクションを隠したマイナーたち（古いブロックチェーンのビューにそのトランザクションを入れようとする）に送信する。そして、そのそのビューを商人に見せ、商品を受け取る。その後、隠したマイナーと商人に隠していないマイナーたちによって作られた最新のビュー（トランザクションが入っていない）を見せ、先ほどのブロックをオーファンにする。これによって攻撃者はお金を支払うことなく商品を手に入れることができる。

Bitcoin's Peer-to-Peer Network

ノード間の接続は TCP 上で行われており、パブリック IP のみ保存し伝搬させる。そのピアがパブリック IP かどうかは、IP パケットと Bitcoin の VERSION メッセージを比較することで確認できる。この章では、ノードがどのようにネットワーク情報を保存し伝搬しているか、どのように外部接続を選んでいるかについて解説する。

Propagating network information

ネットワーク情報は DNS シードと ADDR メッセージを通して Bitcoin ネットワークを伝搬する。DNS シードとは Bitcoin ノードの IP リスト（定期的なクローリングで作っている）を使ってノードからの DNS クエリを返答するサーバである。DNS シードにクエリを送るのは２パターンある。1つ目は新しいノードがネットワークに初めて参加する時である。そのノードはアクティブなノードのリストを DNS シードから得る。それ以外の場合は、約 600 の IP アドレスがハードコーディングされたリストにフェイルオーバーする。2つ目は既存のノードがネットワークに復帰し新しいピアと再接続をしたい時である。ここで、DNS シードはそのノードが接続の確立を試みてから 11 秒が経過し、2つ未満の外部接続を持っている場合のみクエリされる。

ADDR メッセージは最大 1000 個の IP アドレスとそれらのタイムスタンプを含んでおり、ピアからネットワーク情報を得る時に使用される。この時、ノードたちは求めていない ADDR メッセージを受け入れる。また、ADDR メッセージはあるピアと外部接続したい時のみには求められるメッセージである。そのピアはテーブルからランダムに選ばれた最大 1000 個のアドレスを含む最大3つまでの ADDR メッセージを返答する。ノードが ADDR メッセージを送るのは2つのパターンがある。1つ目は、毎日自分のアドレスを入れた ADDR メッセージを各ピアに送る場合。また、10 アドレス以下の ADDR メッセージを受け取ったノードは、そのメッセージをランダムに選ばれた2つの接続ピアに中継する。

Storing network information

パブリック 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

すべての IP アドレスは tried の単一バケットにマッピングされ、各 group は最大 4 つのバケットにマッピングされる。

あるノードがあるピアに接続が成功した場合、そのピアのアドレスは適切な tried バケットに挿入される。もしそのバケットが満杯の場合、bitcoin eviction が使用され、4つのアドレスをそのバケットからランダムに選び、tried テーブルから最も古いピアを新しいピアに置き換えて、new テーブルに挿入する。そのピアのアドレスがすでにバケットに入っている場合、そのピアの IP アドレスに関連したタイムスタンプを更新する。タイムスタンプはアクティブに接続されたいるピアが VERSION, ADDR, INVENTORY, GETDATA, PING メッセージを送った時や最後の更新から 20 分以上経過した場合にも更新される。

new テーブルは 256 個のバケットでできており、それぞれにノードがまだ正常な接続を開始していないピアの最大64個のアドレスを保持できます。ノードは DNS シードもしくは ADDR メッセージから情報を得たことによって new テーブルに現れる。new テーブルに挿入されたすべてのアドレス $a$ はそのアドレスの group と、接続されたピアの IP アドレスもしくはアドレス $a$ を教えてくれた 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 を実行し、そのアドレスが破棄される小さな変更で済む。

Selecting peers

新しい外部接続は、あるノードがリスタートするかある外部接続がネットワークから離脱したら選択される。Bitcoin ノードはブラックリストに載ったものに出会った時を除いて、故意に接続をドロップすることはない。$\omega \in [0, 7]$ の外部接続を持つノードは $\omega + 1^{th}$ 接続を以下のように選ぶ。

（1）tried もしくは new テーブルから選択するか決定する。以下の式が tried から選ぶ確率である。$\rho$ は 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, \tau)$ は $r$ と $\tau$ の関数であり、$r$ は拒否されたアドレスの数を表し、$\tau$ はアドレスのタイムスタンプと現在の時間との違い（10分ごとに計測する）を示している。

（3）アドレスに接続する。接続に失敗したら（1）へ戻る。