chike0905の日記

何者かになりたい

【論文】Information Propagation in the Bitcoin Network

論文 ブロックチェーン

読んだ論文をまとめる。

論文は

Information propagation in the Bitcoin network - IEEE Conference Publication

発表スライドは以下

https://www.tik.ee.ethz.ch/file/0bc1493ba049fe69dbafccef4220c666/presentation.pdf

概要

Bitcoinネットワークでの情報伝播

  • BItcoinネットワークは均一なノードによるネットワーク
    • それぞれのノードは協働することはなく、TXの検証に必要な完全な複製を持つ*1
    • それぞれのノードは独立しているので、ノード間の信頼は最小となる
  • ネットワークトポロジはランダムグラフ
    • ノードが参加すると、幾つかのDNSに問い合わせを行う
    • DNSは現在ネットワークに参加する幾つかのbootstrapノードを返す
    • ネットワークに参加すると、ノードは他ノードに隣接ノードを尋ねる
    • ネットワークからの離脱の表明手段はない
      • ノードの隣接アドレスセットから数時間で削除される
    • ノードはそれぞれ pのコネクションを持つ
      • 内向きのコネクションは閉じないので、実際にはコネクションの数は pより多くなる
      • Bitcoindではデフォルトは p = 8で、平均して32のコネクション
    • ネットワークの分断の積極的検知はない
      • マイニングパワー総量の監視によって推測は可能
  • 台帳の同期にはtxメッセージとblockメッセージを用いる
    • ブロック/TXをBlock/txメッセージによって受け取ると、検証を行ってから隣接ノードにinvメッセージを送る
    • invメッセージを受け、当該ブロック/TXを持っていなければgetdataメッセージを返す

メッセージのやりとり f:id:chike0905:20180820100720p:plain 論文本文より

  • それぞれのメッセージングで伝播遅延が発生する
    • 遅延はメッセージの転送と、ブロック/TXの検証の組み合わせである
      • TXの検証はディスクへのランダムアクセスが必要*2
  • i_{i,j}をブロック/TXiが生成され、広告されてからノードjが受信するまでの時間とする
  • 伝播は2つのフェーズに分かれる
    • 多くのノードがinvメッセージを受け取り、持っていないデータを収集するフェーズ
    • 多くのノードが持っているデータのinvメッセージを受け取り、集束するフェーズ
  • 180000〜190000ブロックの受信した時間とブロックのタイムスタンプを収集
    • 中央値は6.5秒で、平均して12.6秒で受信する
    • ロングテールになり、40秒後には5%のノードがまだ受信していない

f:id:chike0905:20180820111746p:plain 論文本文より

  • 送信するデータサイズは、20kBまでは遅延に深く影響する
    • 96%のTXは1kB未満
    • ブロックのほとんどは20kB以上で過半数が知るまでに80msかかる
  • ネットワークへの侵食
    • ネットワーク上のノードをV、エッジを Eとし、ネットワークを G = (V,E)で表す
    • ブロック高hを持つネットワークの一部のノード群をP_h \subset Vとする
    • h+1のブロックbを見つけ、それを持つノード群はP_{h+1,b}となる
      • bが見つかり、他のブロックが見つからなければ、ノードはP_hを離脱し、P_hが空になるまでP_{h+1,b}に参加する
    • b'が見つかった時、P_{h+1,b'}が発生する
    • ノードはどちらかを選択し、もう一方の伝播を止める
      • これはTXでも同様の動作をする
    • トランザクションの場合、伝播を止めることはネットワーク上での検証コストとフォークさせる攻撃とのトレードオフとなる
    • ブロックの場合、任意の値を持つブロックを生成することは困難なため、攻撃になり得ない

ブロックチェーンのフォーク

  • フォークはネットワークの一部によって観測される
    • NATやFirewallの中などのノードへは到達できない可能性が高いので、全てのフォークは観測できない
  • 180000〜190000ブロックまでを観測した結果、169回のフォークが発生し、発生頻度は1.69%となった
  • フォークのモデル化*3
    • PoWはブロックの発見をランダムな独立事象にする
    • 伝播によるブロックチェーンのフォークの２要素
      1. ブロックの発見確率
        • 10分に一回ブロックが発見されるので、1秒間にブロックが発見される確率は以下
        • P_b = Pr[X_b \lt t+ 1 \mid X_b \geq t] \approx 1/600
      2. ネットワークの一部による競合ブロックの発見
        • ブロックチェーンのフォークはbが伝播している時にb'が見つかることで発生する
          • b'はbを知らないノードによってのみ発見される
        • t_jをbが発見されてからノードjが存在を知るまでの時間とする
        • I_j(t)をjがtにbを知っているかどうかの判定関数とする
        • bをtまでに全てのノードが知るとすると
          • I_j(t) = \begin{cases} 0\ t_j \gt t \\ 1\ t_j \le t \end{cases}
          • I(t) = \sum_{j \in V} I_j(t)
        • 知っているノードの割合は
          • f(t) = \mathbb{E}[I(t)] \cdot n^{-1}
        • 以上よりフォークの確率は
          • Pr[F \le 1] = 1 - (1 - P_b)^{\int_\bullet^ \infty(1-f(t))dt}
    • P_bとI_jはネットワーク上の計算パワーとネットワークのトポロジに影響を受ける
    • 180000〜190000ブロックの計測を元にした分析
      • ブロックの発見確率はPoWによってポアゾン事象となる
      • 確率分布を元にすると \lambda = 0.001579程度
        • 1/\lambda = 633.68であり、おおよそ600に近似されている
        • 計算パワーが平均10分に1回見つかる調整よりも少し多く投入されているためのズレ
        • これを元に先の式を計算すると平均11.37秒でブロックが伝播する
      • 11.37秒で伝播するということは、伝播する間に費やされる計算パワーは無駄となる
      • 1 - 11.37 / 633.68 = 98.20%なので、実質49.1%の有効な計算パワーを費やすことで攻撃が可能となる

伝播を速める施作

  • 伝播を速める手法として提案するのは3つ
    1. 検証の最小化
      • ブロックの検証作業は以下の二つに分割できる
      • difficultyの検証が終わったら即座に隣接ノードにinvメッセージを出す
      • 同じdifficultyを持つブロックの生成は困難なため、DoSのリスクを高めることはない
    2. ブロック伝播のパイプライン化
      • invメッセージを受け取ったらすぐに転送する
    3. 接続性の増加
      • 一つのノードのコネクション数を増やす

f:id:chike0905:20180820101257p:plain 論文本文より

  • 計測結果
    • 200000〜210000ブロックで改善を行った上で計測を行った
    • フォークの頻度は0.78%となった
    • 最も影響したのは接続性の増加 　 * 帯域はおおよそ100MB/s必要となった

結論

  • ネットワーク上での伝播の分析を行った
  • モデル化と計測を行い、モデルの検証を行った
  • ネットワーク上でフォークを解決することは台帳の複製の非一貫性の解決に重要
  • しかしイクリプスされると多くのノードは検知できない
  • 幾つかの伝播を促進する施作を提案し、計測した
  • それぞれは短期的な対策であり、スケーラブルな長期的な解決策を見つける必要がある

感想

結構早めの段階(2013年)に出た論文でネットワークの分析を行ったということで、かなり引用されている論文。やはり、先日の記事でも触れたようにネットワークへの前提を持たないことで伝播がフォークへ影響しており、興味深かった。伝播中に費やされたコンピューティングパワーは浪費になる、というのも面白く、例えば攻撃者としては伝播をわざと遅らせるなどする攻撃もできそうだ。この論文を根っことしてネットワークへの攻撃や分析の論文が多数出ているので、その辺を追っていく。

*1:全てフルノードであることを想定している

*2:おそらくUTXOの探索のことを言っている

*3:ここはうまく読めていないので数式などは暫定で記述する