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% 以上を支配していないマイナーがいなければ安全と信じ込むのは危険です.

Network Stock photos by Vecteezy

Bitcoin における合意形成アルゴリズム Part 2 Read More »

Bitcoin における合意形成アルゴリズム Part 1

分散ネットワークシステムで合意形成 (コンセンサス) を得るためには, Byzantine 将軍問題があり,
全ノードのうち 1/3 以上が悪意のあるノードならば, 合意形成は不可能であることを
分散型合意形成と Byzantine 将軍問題で見ました.

Byzantine 将軍問題が発生しても, ネットワークが正しい値について合意できるという性質を
BFT (Byzantine Fault Tolerance, ビザンチン障害耐性) と言います.

Bitcoin のような分散型電子通貨システムを構築する上で解決すべき重要な技術的課題の1つは,
分散型合意形成を実現することですが, Bitcoin ブロックチェーンには BFT があるでしょうか.

結論から言うと, Bitcoin ブロックチェーンは Byzantine 将軍問題に対して,
理論的な解を与えていないが, 実用的な解を与えています.
これは従前のモデルにない条件があることで, 実用的には上手く機能しています.

その条件は2つあります.
1つ目は, インセンティブという概念です.
不正取引を防ぎブロックチェーンの維持に貢献した報酬として, ブロックを作成 (マイニング) したノード (マイナー) に
Bitcoin (ブロック作成報酬と取引手数料の合計) が与えられます*1.
Bitcoin が通貨であるため, 参加ノードが誠実に行動しようと思うインセンティブが働くのです.

*1 ブロックチェーンの維持に貢献したという意味は, PoW (Proof of Work, 作業をしたことの証明) という
大量の計算コストをかけた (ハッシュ計算をした) ということです.

2つ目は, 確率的な合意形成です. Bitcoin ブロックチェーンでは, 合意形成のための特定の出発点や終点の概念がありません.
その代わりに, 合意形成に長い時間をかけ, 実際の運用では1時間程度の時間をかけています*2.
しかし, それだけの時間をかけた後も, ノードは特定の取引やブロックがブロックチェーンに書き込まれたかどうかを
確実に知ることができません.
ただし, 時間が経つにつれて, 自分から見える形は最終的に合意が得られた形に一致していき,
2つの形が乖離する確率は指数関数的に下がります.

*2 ブロックが作成される間隔が約10分であるため, ブロックがブロックチェーンに組み込まれた後に,
6個のブロックが追加されればそのブロックは有効だろうと確信できるということです.
ここで, 6個という数に理論的な根拠はなく, あくまでも経験的な答えであることに注意しましょう.

Bitcoin ブロックチェーンが従来の分散型合意形成にかかる Byzantine 将軍問題を回避する上でのポイントは,
モデルのこのような違いです.
Byzantine 将軍問題を「解決」でなく「回避」というのは, 冒頭で申し上げた通り理論的には解が与えられていないからです.

実際、理論的に解が与えられたと言うためには, 合意が覆る可能性がゼロでなければなりませんが,
Bitcoin ブロックチェーンでは, PoW による合意はブロックが作成された時点では確定しておらず,
あくまでも時間の経過とともにその時点の合意が覆る確率がゼロへ収束する, 仕組みとなっています.

Bitcoin における合意形成アルゴリズム Part 2」に続きます.

Network Stock photos by Vecteezy

Bitcoin における合意形成アルゴリズム Part 1 Read More »

分散型合意形成と Byzantine 将軍問題

分散ネットワークシステムで昔からよく知られている問題に, Byzantine (ビザンチン) 将軍問題というものがあります.

これは分散ネットワークシステム上の合意形成にかかる問題で, 1982年に Leslie Lamport 氏らによって定式化されました:
Leslie Lamport, Robert Shostak , and Marshall Pease, The Byzantine Generals Problem, SRI International, 1982.

ちなみに Leslie Lamport 氏は, 2013年にコンピューターサイエンス分野における最高の栄誉
と言われる Turing 賞を受賞しています.
賞の名称は, エニグマ暗号機の解読者であった Alan Turing の名に由来します.

分散ネットワークシステム上では, 有限個のノードがあり, それらのノードの一部は故障していたり悪意を持っていたりします.
それらのノード間において合意形成を得るためには, 次の2つが求められます:

  • 全ての善良ノードがメッセージ (値) について合意して終了しなければならない,
  • メッセージ (値) は, 善良ノードによって生成されなければならない.

Byzantine 将軍問題は, 相互に通信し合うノードにおいて, 通信および個々のノードが故障,
または故意にノードが偽の情報を伝達する可能性がある場合に, 全体として合意形成が得られるか, を問う問題です.

さて, Byzantine 将軍問題と呼ばれる由来について述べます.
これは上記で述べたシステム上の問題を, 古代東ローマ帝国 (Byzantine 帝国) の将軍に喩えたものです.

図1 Byzantine 将軍問題

Byzantine 軍は, 部隊に分かれており, それぞれが1人の将軍に率いられています.
各部隊は敵城を包囲しており, 1対1でしか互いに連絡が取れない状況を想定します.
この戦いでは, 全部隊が同時に攻め込まない限り城を落城させることができないようです.
そこで, 将軍たちは共通プランについて合意したいと考えており, 「突撃」あるいは「撤退」の判断を,
伝令を使って他の部隊へ伝えます.

しかし, 一部の将軍は裏切り者であり, 祖国に忠実な将軍たちが共通プランについて合意が形成できないように,
他の将軍から「攻撃」の情報が伝えられると, 意図的に「撤退」の情報に替えて別の将軍に伝える可能性があります.
この裏切り行為により, 一部の将軍は「突撃」と「撤退」の両方を受け取ることも考えられ,
場合によっては合意形成が得られず, 一部の部隊だけが「突撃」してしまい, Byzantine 軍は敗北することになります.

この問題のゴールは, 全ての忠実な将軍が共通プランについて合意が形成できるようにすることです.
このとき, 裏切り者の将軍の妨害により間違ったプランを採用するようなことがあってはなりません.
この問題は, 1/3 以上の将軍が裏切り者なら, 合意形成は不可能だということが証明されています.

Shapes Vectors by Vecteezy
Knight Vectors by Vecteezy
Network Stock photos by Vecteezy

分散型合意形成と Byzantine 将軍問題 Read More »