Bitcoin における合意形成アルゴリズム Part 2
「Bitcoin における合意形成アルゴリズム Part 1」の続きです.
ここでは, Bitcoin の合意形成アルゴリズムが実用的には上手く機能している理由について,
攻撃者 (悪意のあるノード) を想定しながら述べます.
Bitcoin のブロックチェーンでは, 悪意のあるマイナー含め, 各マイナーが自主的にチェーンを伸ばしていきます.
このとき, 必然的にチェーンの分岐が起こってしまいますが, その中の最長チェーンだけを有効なものとするという
ルールを定めています*1.
これにより, ブロックの有効性について, マイナーの多数決での合意形成が行われたことになります.
*1 もちろん2つの有効なブロックが同時に作成されても, チェーンに組み込まれるのはそれらのうちどちらか一方となります.
最終的にどちらのブロックが組み込まれるかは, 他のマイナーがどちらのブロックを選択するかによって決まります.
図1 Bitcoin ブロックチェーンの分岐と最長チェーン
不正なブロックを作成する攻撃者は, PoW により大量の計算コストをかけることになりますが,
最長チェーンに組み込まれる確率は非常に低く, さらに報酬を得ることもできません.
そのため, わざわざ高いコストを支払ってまで不正なブロックを作成しようとする動機にならず,
全てのノードがルールに従い続けようというインセンティブが働くのです.
攻撃者の負ける確率が非常に高いという数学的根拠は Bitcoin の原論文に記述があります:
Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, bitcoin.org, 2008.
まず P を善良ノードが次のブロックを見つける確率, Q を攻撃者が次のブロックを見つける確率,
Qz を攻撃者が z ブロックの遅れから追いつく確率とします.
ここで, P > Q と仮定すれば、Qz = (Q/P)z が成り立つため,
追いつく必要のあるブロック数の増加に伴い, 攻撃者が追いつく確率は指数関数的に下がっていきます.
一方, P ≦ Q と仮定すれば Qz = 1 が成り立ち, 攻撃者の勝利となります.
ここで, P ≦ Q のとき, つまり Q が 50% 以上というのは、
攻撃者が全体のハッシュレートのうち半分以上の割合を支配しているという意味で*2,
不正な合意形成が行われてしまいます. これは 51% 攻撃などと呼ばれています.
しかし, 現実的には 50% 以上のハッシュレートを確保するのは非常に高コストであるため,
難しいとされています.
*2 ハッシュレートとは, 1秒あたりに何回ハッシュ計算ができるかという単位 [H/s] です.
ハッシュパワーや採掘速度とも言います.
いま見たように, 51% 攻撃が行われなければ Bitcoin ブロックチェーンは安心, と誰もが信じたいところですが,
実はそれが覆される攻撃手法が存在するのです.
これは 利己的マイニング (selfish mining) と呼ばれる攻撃で, 2013年に Eyal と Sirer により提案されました:
Ittay Eyal, Emin Gun Sirer, Majority is not Enough: Bitcoin Mining is Vulnerable, 2013.
具体的には, 攻撃者はマイニングに成功してもそのブロックを公開せず,
数ブロック分を公開しないままマイニングを進め, ある時点でまとめて数ブロック分を公開することで,
最長チェーンを伸ばす競争を利己的に進めることができるというものです.
Q を攻撃者が次のブロックを見つける確率,
2つの公開 (分岐) チェーンがあったとき, Z を善良ノードが攻撃者のチェーン上にブロックを追加する確率とします.
このとき, Z = 1/2 ならば, Q > 1/4 で攻撃者は通常マイニングよりも利己的マイニングの方が儲かります.
さらに, Q > 1/3 ならば, 任意の Z に対して, 攻撃者は利己的マイニングの方が儲かることになります.
よって, ハッシュレートの 50% 以上を支配していないマイナーがいなければ安全と信じ込むのは危険です.
Bitcoin における合意形成アルゴリズム Part 2 Read More »
