この記事では、“Selfish Mining” と呼ばれるブロックチェーンに対する攻撃手法の1つを提案した論文[1] を要約していきます。最初に論文の概要を述べ、論文を読むために必要な用語の解説をします。次に、提案された攻撃モデルとシミュレーション結果を示します。最後に、この論文の著者らが示したビットコインプロトコルの問題点と修正案を示します。
[1]: Majority is not Enough: Bitcoin Mining is Vulnerable
論文の概要
ビットコインはブロックチェーンと呼ばれるパブリックな履歴にトランザクションを記録する暗号通貨です。その安全性は、マイナーと呼ばれる参加者がブロックチェーンを維持するための分散型プロトコルに決定的に依存しています。これまでの常識では、ビットコインのプロトコルはインセンティブ適合性があり、少数派の結託に対して安全であるとされてきました。つまり、マイナーにインセンティブを与えて、規定通りのプロトコルを実行させることができるのです。
しかし、この論文ではビットコインのプロトコルがインセンティブに適合していないことを示します。また、結託したマイナーが公正な分配よりも大きな収益を得る攻撃を紹介しています。この攻撃は、ビットコインに大きな影響を与えます。合理的なマイナーは利己的なマイナーに加わることを好むようになり、結託したグループは過半数になるまで規模が拡大します。この時点で、ビットコインシステムは非中央集権的な通貨ではなくなります。
用語解説
マイナーとプール
あるブロックチェーンネットワークがマイナー 1, 2, ..., n で構成されているとします。各マイナー i には、\sum_{i = 1}^{n}m_{i} = 1 を満たすマイニングパワー m_{i} があります。各マイナーは、マイニングするブロックチェーンの先端を選択し、平均 m_{i}^{-1} で指数分布する時間間隔の後に、そのヘッドの後続のブロックを見つけます。マイナーは合理的であると想定しています。つまり、収益を最大化しようとし、そのプロトコルから逸脱する可能性があります。
マイナーのグループは、いくつかの戦略に従って、単一のエージェントとして動作するプール（マイニングプールとも言う）を形成できます。プールのマイニングパワーは、そのメンバーのマイニングパワーの合計であり、その収益は相対的なマイニングパワーに従ってメンバー間で分割されます。「予想される収益」、または単にプールの「収益」は、最長のチェーン内のブロックの総数のうち、そのプールによってマイニングされたブロックの予想される割合です。
Selfish-Mining
Selfish-Mining（利己的マイニング）と呼ばれる戦略について説明します。利己的マイニングを使用すると、十分なサイズのプールを使用して、マイニングパワーの比率よりも大きな収益を得ることができます。簡単にするために、マイナーは 2 つのグループ、利己的マイニング戦略に従う共謀少数派プールと、誠実なマイニング戦略に従う多数派プールに分けられると仮定します。
利己的マイニング戦略の背後にある重要なことは、誠実なマイナーに古いパブリックブランチで無駄な計算を実行させることです。具体的には、誠実なマイナーに、ブロックチェーンの一部ではない運命にあるブロックにサイクルを費やすことを強制します。
利己的マイナーは、自分でマイニングしたブロックを選択的に明らかにして、誠実なマイナーの仕事を無効にすることで、この目標を達成します。大まかに言えば、利己的マイニングプールは、マイニングされたブロックをプライベートに保ち、ブロックチェーンを密かに分岐させ、プライベートブランチを作成します。その間、誠実なマイナーはより短いパブリックブランチでマイニングを続けます。利己的マイナーは総マイニングパワーの比較的小さな部分を占めているので、彼らのプライベートブランチはいつまでもパブリックブランチより長くいることはありません。その結果、利己的マイニングはプライベートブランチからパブリックにブロックを慎重に公開し、誠実なマイナーは最近公開されたブロックに切り替えて、短いパブリックブランチを放棄します。これにより、より短いパブリックブランチに費やされた以前の努力が無駄になり、利己的プールはブロックチェーンにより多いブロックを組み込むことでより高い収益を集めることができます。
利己的マイナープールがブロックを発見した場合、誠実なマイナーが操作しているパブリックブランチよりも 1 ブロック分リードしているという有利な立場になります。利己的マイナーは、このプライベートブロックを素直に公開して他のマイナーに発見したブロックを通知する代わりに、このブロックをプール内で非公開にしておきます。この時点で考えられる結果は 2 つあります。1 つは、誠実なマイナーがパブリックブランチで新しいブロックを発見し、利己的マイニングプールのリードを無効にすること。もう 1 つは、利己的マイニングプールが 2 つ目のブロックをマイニングし、誠実なマイナーに対するリードを拡大することです。
1 つ目のシナリオの場合、利己的マイナープールは直ちにプライベートブランチ（長さ 1）を公開します。これにより、長さの等しいブランチが 2 つになるためどちらのブランチが勝ってもおかしくない状況になります。利己的マイナーは満場一致で自分達のプライベートブランチを採用して拡張し、誠実なマイナーは通知の伝搬に応じてどちらかのブランチでマイニングことを選択します。利己的プールが誠実なマイナーよりも先に後続のブロックをマイニングすることに成功した場合、そのブランチの最初のブロックと 2 番目のブロックの両方の収益を獲得できるため、すぐに公開します。誠実なマイナーがプールの公開したブロックの後にブロックをマイニングした場合、プールは 1 つ目のブロックの収益を獲得し、他のマイナーは 2 番目のブロックの収益を得ることになります。最後に、誠実なマイナーがパブリックブランチにマイニングした場合、2 つのブロックの収益を獲得し、利己的マイナープールは何も得られません。
利己的プールが公開する前に 2 つ目のブロックを見つけることに成功した 2 つ目のシナリオの場合、2 つのブロックで余裕のあるリードを築くことができたため、プールはプライベートブランチの先頭でマイニングを続けます。他のマイナーが発見したブロックごとに、利己的プールはプライベートブランチから 1 つのブロックを公開します。利己的プールは少数派なので、そのリードは最終的に高い確率で 1 ブロックになります。この時点で、プールは自分のプライベートブランチを公開します。プライベートブランチはパブリックブランチよりも 1 ブロック分長いため、すべてのマイナーがメインブランチとしてそれを採用し、プールはすべてのブロックの収益を獲得します。
分析
ここでは、利己的プールが \alpha のマイニングパワーを持ち、他のプールが 1 - \alpha のマイニングパワーを持つシステムの期待報酬を分析します。
下図は、システムの進行を状態遷移図で表したものです。システムの状態は、利己的プールのリードを表しています。つまり、プールのプライベートブランチとパブリックブランチの長さの差です。差がゼロのときは、状態 0 と 0^{'} に分けられます。状態 0 は、ブランチがない状態、つまり、単一のグローバルなパブリックなチェーンのみが存在する状態です。状態 0^{'} は、長さ 1 の 2 つのパブリックブランチがある状態です。図中の遷移は、利己的マイナーまたは他のマイナーによるマイニングイベントに対応しています。これらのイベントは指数関数的な間隔で発生し、その平均頻度はそれぞれ \alpha と 1 - \alpha です。
状態遷移図の各状態遷移に関連する頻度を考慮し、対応する報酬を計算することで、利己的マイニングから期待される報酬を分析することができます。ここでは、さまざまなケースを想定し、状態遷移のきっかけとなる関連イベントを説明します。プールに長さ 1 のプライベートブランチがあり、他のマイナーが 1 ブロックをマイニングした場合、プールはそのブランチをすぐに公開し、長さ 1 のパブリックブランチが ２ つ存在する状態を作ります。利己的プールのマイナーは全員、プールのブランチでマイニングします。誠実なマイナーは、標準的なビットコインプロトコルの実装に従って、最初に取得したブランチでマイニングします。ここでは、利己的プールのブロックを最新に採用してマイニングすることを選択した誠実なマイナーの比率を \gamma 、利己的プールではないマイナーが作成したブロックが先端にあるブランチをマイニングするマイナーを (1 - \gamma) と表します。
状態 s = 0,1,2,...では、頻度 α で、プールがブロックをマイニングし、リードは 1 つ増えて s + 1 となります。状態 s = 3,4,... では、頻度 (1 - α) で、誠実なマイナーがブロックをマイニングし、リードが1減って s - 1 となります。リードが 2 のときに他のマイナー（利己的プールに属していないマイナー）がブロックをマイニングした場合、プールはプライベートブランチを公開し、リードが 0 にします。リードが 1 のときに他の人がブロックをマイニングした場合、前述の状態 0^{'} になります。0^{'} からは3つの可能な遷移があり、いずれも合計頻度1で状態 0 に至ります。(1)プールが以前のプライベートブランチでブロックをマイニングする（頻度 \alpha）、(2)他のマイナーが公開されたプライベートブランチでブロックをマイニングする（頻度 \gamma(1 - \alpha)）、(3)他のマイナーがパブリックブランチでブロックをマイニングする（頻度(1 - \gamma)(1 - \alpha)）。
状態の確率
この状態遷移図を解析して、状態空間上の確率分布を計算します。以下の式が得られます。
この式を解くと、以下の式が得られます。
報酬
新しいブロックを発見した際の報酬は、そのブロックがメインチェーンに入る場合のみ、そのマイナーに帰属します。以下に各イベントでの収益を詳しく説明します。
-
(a) 長さ 1 の 2 つのブランチ以外の任意の状態で、プールがブロックを発見した状態
プールはそのプライベートブランチに 1 つのブロックを追加し、パブリックブランチとのリードを 1 つ増やします。このブロックからの収益は後で決定されます。
-
（b）長さ 1 の 2 つのブランチで、プールがブロックを発見した状態
プールは長さ 2 のプライベートブランチを公開し、2 ブロック分の収入を得ます。
-
(c) 長さ 1 の 2 つのブランチがあり、プールではない外部のマイナーが公開されたプールブランチの先端に続くブロックを見つけた状態
プールとその外部のマイナーはそれぞれ 1 ブロック分の収入を得ます。
-
(d) 長さ １ の ２ つのブランチがあり、外部のマイナーがプールブランチではない方に続くブロックを発見した状態
外部のマイナーが ２ ブロック分の報酬を得ます。
-
(e) プライベートブランチがなく、外部のマイナーがブロックを発見した状態
外部のマイナーが 1 ブロック分の報酬を獲得し、利己的プールも外部のマイナーもその新しいブロックを先端としてマイニングを始めます。 -
(f) プライベートブランチが 1 つリードしており、外部のマイナーがブロックを発見した状態
長さ 1 のブランチが 2 つあり、プールは 1 つのプライベートブロックを公開します。プールはもちろんそれまで非公開だったブランチでマイニングしようとし、他のマイナーは 2 つのブランチの間で分裂します。プール以外のブロックを先端としてマイニングする外部のマイナーの比率を γ で表します。
このブロックからの報酬は、どちらのブランチが勝つかによって決まるので、まだ決定できません。
-
(g) プライベートブランチが 2 つリードしており、外部のマイナーがブロックを発見した状態
外部ブランチとの差が １ に縮まりました。プールはプライベートのブランチを公開します。公開したブランチの方が長いため全てのマイナーは利己的プールが公開したブランチの先端でマイニングを始めます。利己的プールは ２ ブロック分の報酬を獲得します。
-
(h) プライベートブランチが 2 つよりもリードしており、外部のマイナーがブロックを発見した状態
外部ブランチとの差が 1 つ縮まりましたが、少なくともまだ 2 つのリードは残っています。新しいブロック（i番）は、プールがそのブランチ全体を公開するとチェーンの外側で終了するため、外部のマイナーは何も得ることができません。しかし、プールはi番目のブロックを公開し、1 つ分の収入を獲得します。
状態確率と遷移頻度から、利己的プールの収益とその他の外部マイナーの収益を計算します。
利己的なマイニングがもたらす意図的なチェーンの分岐により、誠実なマイナーはブロックチェーンの外で終わるブロックに取り組むことになります。その結果、r_{pool} + r_{others} < 1 となり、ブロック生成率の合計が低下します。プロトコルは、メインチェーンでのマイニング率が平均して 10 分間に 1 ブロックとなるようにマイニング難易度を適応させます。したがって、各エージェントの実際の収益率は収益率比、つまり、メインチェーンのブロックのうち、そのブロックの割合です。(6)-(7) の収益式に (2)-(5) の確率を代入し、 0 \leq \alpha \leq \frac{1}{2}のプールの収益を計算します。
シミュレーション
理論解析の検証のため、その結果をビットコインプロトコルのシミュレータで比較しています。このシミュレータは、前のセクションで説明したビットコインプロトコルの仕様を捕捉できるように構成されています。ただし、クリプトパズルモジュールは、実際にはクリプトパズルを計算せずにブロック発見をシミュレートするモンテカルロシミュレータに置き換えられています。本実験では、このシミュレータを使用して、1000 人のマイナーが同じレートでマイニングする様子をシミュレートしています。1000\alpha のマイナーは Selfish-Mine アルゴリズムを実行する利己的プールを形成し、他のマイナーはビットコインのプロトコルに従います。ブロックの伝搬時間は、現実の場合と同様に、マイニング時間に比べて無視できる程度であると仮定します。同じ長さの 2 つのブランチがある場合、利己的プール外のマイナー（1000(1 - \alpha)）を γ の割合で人為的に分割し、利己的プールのブランチでマイニングし、残りはもう一方のブランチでマイニングするようになります。下図は、シミュレーション結果が理論解析と一致していることを示しています。
Selfish-Mine 戦略によるプール収益を伝播係数 γ を変えて、誠実なビットコインプロトコルと比較しました。シミュレーションは理論的な分析と一致しており、両者とも、閾値以上では Selfish-Mine が誠実なプロトコルよりも高い収益を上げることを示しています。
α と γ の影響
式(8) で与えられるプールの収益があるプールサイズ α より大きいとき、プールは Selfish-Mine 戦略を使用することにより、本来よりも多くの収益を得ることができます。したがって、プールのマイナーは、マイニングパワーよりも相対的に多くの利益を得ることになります。この式は 0 ≦ α ≦ \frac{1}{2} のときのみ有効です。この範囲において得られる結果を以下の観察に表します。
観察１: ある γ に対して、サイズ α のプールは、以下の範囲で本来期待されるものよりも大きな収益を得る：
上のグラフでは、プールサイズが 0（非常に小さいプール）から 0.5（半分のマイナー）までの範囲で、異なる γ 値に対するプールの収益を示しています。利己的プールにリスクがあるのは、ちょうど 1 つのブロックをプライベートに保持しているときのみです（誠実なマイナーがそれと競合するブロックを公開するかもしれないため）。γ = 1 の場合、外部のマイナーがパブリックブランチに続くブロックを見つけたとしても、プールはプライベートにしていたブロックのブランチを素早く伝播させることができるので、すべての誠実なマイナーはプールのブランチでマイニングを続けるでしょう。この場合、プールは Selfish-Mine 戦略に従うとリスクを負わず、その収益は本来のアルゴリズムに従う場合よりも常に良くなります。
また、プールサイズの関数としてのプール収益 R_{pool} の傾きは、閾値 \alpha 以上では 1 より大きくなることに注目します。このことは、次のような観察を意味します。
観察2: Selfish-Mine 戦略を実行する利己的プールでは、プールサイズが閾値 \alpha 以上のときに、各メンバーの収益はプールサイズについて単調に増加する
ビットコインプロトコルの修正
強固な通貨システムは結託した大規模なマイナーによる攻撃に対抗できるように設計されることが理想です。利己的マイニング攻撃は、ある閾値以上のグループサイズに対して正の結果をもたらすので、閾値をできるだけ高く設定するようにプロトコルを修正する必要があります。 この章では、現在（この論文が書かれた当時）のビットコインのプロトコルは γ→1、つまり閾値がほぼゼロであることを主張します。つまり、どのような規模のプールでも Selfish-Mine を実行することで利益を得ることができます。この論文の著者らは、すべての誠実なマイナーが採用する場合、γ を 1/2 に、閾値を 1/4 に設定するシンプルなプロトコルの変更を提案しています。この変更には後方互換性があります。つまり、マイナーのどのマイナーもプロトコルに支障をきたすことなく採用することができます。さらに、この変更を採用したマイナーの比率が増えれば増えるほど、γ は減少し、その結果、閾値は増加します。
問題
ビットコインのプロトコルでは、マイナーが同じ長さの複数のブランチ情報を取得した場合、最初に受け取ったブランチのみをマイニングして伝播させることが規定されています。Selfish-Mine 戦略を実行し、リードが 1 であるプールは、プール以外のブロックが見つけた競合ブロック X を聞くと、プライベートブロック P を公表することを思い出してください。ブロック P がブロック X より先に非プールのマイナーに到達した場合、そのマイナーは P でマイニングを行います。
利己的マイニングは受動的である、つまり、誠実なノードがブロック X を発見した後に初めて行動を起こすため、不利に見えるかもしれません。しかし、狡猾なプール運営者は、ビットコインマイナーのネットワークに十分な数のゼロパワーマイナーを追加することで、誠実なマイナーにシビル攻撃を仕掛けることができます。これらの仮想マイナーは、データ配信に参加することで事前センサーとして機能しますが、新しいブロックをマイニングすることはありません。ビットコインオーバーレイネットワークのランダムなピアツーピア構造により、最終的に X はすべてのマイナーに伝播されるが、この条件下での X の伝播はブロック P の伝播より真に遅くなります。
解決策
この問題に対処し、閾値を上げるために、この論文ではビットコインのプロトコルに簡単で後方互換性のある変更が提案されています。具体的には、あるマイナーが同じ長さの競合ブランチを知った場合、そのすべてを伝播し、どちらをマイニングするかは一律にランダム に選択することです。長さ 1 の 2 つのブランチの場合、これは、（期待値で）半分のノードがプールのブランチでマイニングし、残りの半分がもう一方のブランチでマイニングすることになります。これは γ=1/2 となり、1/4 という閾値が得られます。この変更を実施するマイナーが増えるとγは減少していきます。
参考文献
この論文について Bitcoin Forum でも議論されています。
Bitcoin Forum
