本稿について
Bitcoinマイニングプールのインセンティブ設計について協力ゲーム理論の観点から分析したLewenbergらの論文を見ていきます。本稿では「5. Mining in Coalition Structures」の続きを見ます。
原文はこちらになります。
スポンサードサーチ
今回のまとめ
- 系2：提携構造を持つ提携形ゲームC = <M, P, D, d, β>について、全てのiについてpi ∈ (0, 1/2)ならば、全ての提携構造についてDMS-CSコアは空集合である。
- 今回の範囲はモデルのうち上記の系2を示すものであるが、数式を用いてシンプルに記載されており、どちらかと言えばまとめるよりも補足する方が必要だと思われるので下記文中にて補足を行う。必要に応じて「筆者補足」部分を参照されたい。
※以下、今回まとめた範囲の論文和訳になりますので詳細をご覧になりたい方は読み進めてください。
5. 提携構造におけるマイニング（続き）
補題7
C = <M, P, D, d, β>は提携構造を持つ提携形ゲームである。このゲームでは、D > 0かつ、β > 0かつ、∀i：pi ∈ (0, 1)である。dはある値d1より小さいものと仮定する（d1はP, D, βにより定まる上限値）。このとき、全てのS ∈ CS(M)とCi, Cj ∈ Sについて、p(Ci) > p(Cj)であるならば、vS(Ci)/p(Ci) > vS(Cj)/p(Cj)である。
証明概要
M, P, D, βを固定する。d = 0の場合についての補題7の通りの結果になることを証明し、その後で必要な条件を満たす最大の正の値dをd1として定義する方法をとる。
S ∈ CS(M)を提携構造とし、λはマイナーネットワークΓ = <M, S, P, D, d, λ>についてβ(Γ) = βを満たすλ > 0であるとする。全てのC ∈ Sについて、Cのメンバによりマイニングされたブロックが最終的に最長チェーンに取り込まれる確率をαS(C)で表す。全てのプールでβ・γ(Γ)C = λ・p(C)・αS(C)が成り立つ点を押さえておきたい。この等式が成り立つのは、左辺・右辺ともにプールCによりマイニングされたブロックが最長チェーンにいくつあるかの毎秒あたりの期待値を表しているからだ。従って、p(Ci) > p(Cj)であるならば、αS(Ci) > αS(Cj)であることを証明する必要がある。
d = 0とすると、そのプール内にディレイはなく、各プールが一人のマイナーであるかのようにふるまう。この場合、プール間でのブロックの対立があるとすると次に生成されるであろうブロックはより強力なプールCのものである可能性がずっと高いことからp(Ci) > p(Cj)ならばαS(Ci) > αS(Cj)である。当然、補題7の仮定よりD > 0であるからブロックの対立が起こる可能性は存在する。従って、全ての提携構造全てのS ∈ CS(M)とCi, Cj ∈ Sについて、p(Ci) > p(Cj)ならばαS(Ci) > αS(Cj)であるようなプール内の最大のディレイとしてd1を定義可能である。（証明終わり）
筆者補足：
- 詳細はLewenbergのプール分析論文を読んでみる7を確認してほしいが、改めてマイナーネットワークの記号の定義について。マイナーのインタラクションを表すのに、Γ = <M, S, P, D, d, λ>で定義されるモデル「マイナーネットワーク」を用いる。
- Mはマイナーの集合である。
- Sはマイナーをプールに分ける分割である。
- Pはマイナーの計算パワーの分布である。
- pはマイナーの計算パワーの割合である。
- Dはプール間のディレイである。
- dはプール内のディレイである。
- λはマイナーネットワークが毎秒マイニングできるブロック数の期待値である。
- プールに参加していないマイナーをソロマイナーと呼ぶ。
- βは毎秒最長チェーンに追加されるブロックの比率である。
- γは最長チェーンに属するブロックがマイナーiによりマイニングされた確率である。
- さて補題7と証明について補足します。
- 「p(Ci) > p(Cj)であるならば、vS(Ci)/p(Ci) > vS(Cj)/p(Cj)」の証明概要のはずなのに「αS(C)やγ(Γ)Cが出てきてvS(Ci)やvS(Cj)が消え」てしまうことを不可解に思うかもしれないが、これは実は定義1によるもの。定義1によれば「vS(C) = γ(Γ)Cを設定する。vS(C)は最長チェーンにおけるプールの利得である」ことから題意は「p(Ci) > p(Cj)であるならば、γ(Γ)Ci/p(Ci) > γ(Γ)Cj/p(Cj)を証明せよ」に変形できる。（必要条件）
- 変形できたとしても変形後の証明が確かにもとの題意を示すものか（つまり、十分条件か）を見極める必要があるので、それについて見てみる。まず、「β・γ(Γ)C = λ・p(C)・αS(C)」について見てみる。これは次のことから分かるように、両辺ともに1秒あたりにCが最長チェーンに入るブロックをいくつ生成できるか？（を示す期待値）であるので等しい。
- （左辺） = 「毎秒最長チェーンに追加されるブロックの比率」×「最長チェーンに属するブロックがCのマイナーによりマイニングされた確率」
- （右辺） = 「マイナーネットワークが毎秒マイニングできるブロック数の期待値」×「Cの計算パワーの割合」×「Cのメンバによりマイニングされたブロックが最終的に最長チェーンに取り込まれる確率」
- さて、「β・γ(Γ)C = λ・p(C)・αS(C)」をαS(C)について変形すると、「αS(C) = (β/λ)・(γ(Γ)C/p(C)) 」である。βはλは1プールを見ているわけではなくマイナーネットワーク全体での変数なのでマイナーによらず一定とみなしてよい。
- 従ってαS(Ci) > αS(Cj)であることを示すには、「p(Ci) > p(Cj)であるならば、γ(Γ)Ci/p(Ci) > γ(Γ)Cj/p(Cj)を証明」すれば十分である。（十分条件）
- この証明には「p(Ci)をp(Cj)で割った値よりも、γ(Γ)Ciをγ(Γ)Cjで割った値の方が大きくなる」、すなわち「プールCiとCjを比較した時に、計算パワーの比率の差以上に利得の差が大きく開く」ことを示せればよいともいえる。d = 0とすることで仮想的にソロマイナーだけのネットワークをみなすことができ、D, λ > 0とすることで系1を適用可能になり、自動的に証明される。...となります。
- 要は「プールの計算パワーが大きいほどさらに多くの利得を得られる」ということです。
- d1はその条件を満たすように設定してあげればよい、ということになります。
補題8
Γk = <M, S, P, D, d, λk>(k=1, 2)をマイナーが二人のネットワークで、λ1 > λ2、S = {C1, ..., Cm}(m > 2)、p(C1) ≤ ... ≤ p(Cm)、p(C1) < p(Cm)とする。このとき、γ(Γ1)C1 + γ(Γ1)C2 < γ(Γ2)C1 + γ(Γ2)C2である。
筆者補足：
- 要は「毎秒マイニングできるブロックの期待値だけが違って他の条件が同じマイナーネットワークがあるとする。計算パワーが最も低いマイナー2人は期待値が小さいマイナーネットワークに参加する方が合計で大きま利得を得られる」ということ。
- 現実的には条件の同じネットワークなんて存在しないと思われますが、弱小マイナーはブロック数の期待値の低いネットワークに移動する（＝いま参加しているネットワークを抜ける）インセンティブがあると言えますね。
紙面の都合上、煩雑な証明は省略する。
補題9
補題7と同様のC = <M, P, D, d, β>を定義する。dはある値d2より小さいものと仮定する（d2はP, D, βにより定まる上限値）。このとき、S = {C1, ..., Cm}(m > 2)かつp(C1) ≤ ... ≤ p(Cm)である全てのS ∈ CS(M)について、C = C1 ∪ C2とするとvS(C1) + vS(C2) < vSc(C)である。
証明概要
補題7の証明と同様の手法を用いる。M, P, D, βを固定し、S = {C1, ..., Cm}を補題9の条件と同様の提携構造であるとする。C = C1 ∪ C2とし、S' = SCとする。p(C1) = p(Cm)ならば、補題7よりvS(C1) + vS(C2) < vS'(C)である。従って、p(C1) < p(Cm)と仮定する。λ1、λ2を、マイナーネットワークΓS,1 = <M, S, P, D, d, λ1>とΓS',2 = <M, S', P, D, d, λ2>についてβ(ΓS,1) = βかつβ(ΓS',2) = β が成り立つようなλ1、λ2 > 0とする。さらにマイナーネットワークΓS,2 = <M, S, P, D, d, λ2>を考える。ΓS',2 はΓS,1よりも密なネットワークであるから、λ1 > λ2である点を押さえておきたい。補題8より、vS(C1) + vS(C2) = γ(ΓS,1)C1 + γ(ΓS,1)C2 < γ(ΓS,2)C1 + γ(ΓS,2)C2である。
γ(ΓS,2)C1 + γ(ΓS,2)C2 < γ(ΓS',2)C = vS'(C)を主張する。実際、2つのプールを結合することはプール間の対立を排除するし、その他のプールとブロックの対立が起きた場合には以前より多くのハッシュパワーを持つことができている。従って、vS(C1) + vS(C2) < vS'(C)を言うことができる。
以上により、この条件、すなわち全ての提携構造S = {C1, ..., Cm}についてvS(C1) + vS(C2) < vSc(C)を満たす最大の正の値dとしてd2を定義可能である。（証明終わり）
筆者補足：
- 補題9とその証明について補足します。
- 「p(C1) = p(Cm)ならば、補題7よりvS(C1) + vS(C2) < vS'(C)」について。補題7は「プールの計算パワーが大きいほどさらに多くの利得を得られる」と言い換えることができる。なので、C1とC2が別個にマイニングするより、力を合わせてCとしてマイニングした方が大きい利得を得られるという話である。よってvS(C1) + vS(C2) < vS'(C)。
- p(C1) < p(Cm)の場合
- 大本の提携構造のネットワークΓS,1と、最弱マイナー2人組んで作ったネットワークΓS',2と、大本のネットワークのブロックの期待値を最弱マイナー2人のネットワークまで下げたネットワークΓS,2を考える。当然、大本のネットワークのブロック期待値の方が高い。
- 補題8から「最弱マイナー2人にとってはブロックの期待値の小さい方が利得が大きくなる」から、vS(C1) + vS(C2) = γ(ΓS,1)C1 + γ(ΓS,1)C2 < γ(ΓS,2)C1 + γ(ΓS,2)C2である。
- でもプールを結合していればそもそもプール間対立がなくなるし、全体としてのハッシュパワーも上がって対立時に優勢である（ここらへんは本当は厳密な証明が必要なのだろうが、証明概要のため省いていると思われる）。
- 従って、最弱マイナー2人にとってはとにかく結合した方がいい。
- 要は「最弱マイナー2人は、自分たちが組んでマイニングできるブロックの期待値以上のどんな提携構造のネットワークに参加するよりも、自分たちだけで組んでマイニングする方が大きな利得を得られる」ということです。
- d2はその条件を満たすように設定してあげればよい、ということになります。
定理10
補題7と同様のC = <M, P, D, d, β>を定義する。またd1、d2はそれぞれ補題7、補題9で得られた上限値と等しいものとする。d < min{d1, d2}ならば、Cの分割関数はPに関して定和かつ非線形かつ単調である。
証明
この分割関数は全てのS ∈ CS(M)についてΣC∈SvS(C) = 1であるので定和である。d < d2であるから、補題9によりこの分割関数は単調である。さて、w ∈ R|I|を重みベクトルwi = piとしてこの分割関数がwに関して非線形であることを示す。S ∈ CS(M)はmaxC∈Sw(C) > minC∈Sw(C)である提携構造とし、Ci ∈ arg maxC∈Sw(C)とする。d < d2であるから、補題7より、
従って、vS(Ci) > p(Ci) = w(Ci)であり、この分割関数は非線形である。（証明終わり）
筆者補足：
さて、以上により本章の主たる成果であるDMS-CSコアの空集合の条件を述べることができる。これまで証明した定理を組み合わせることにより次の系2が示される。
系2
C = <M, P, D, d, β>は定理の通りの提携構造を持つ提携形ゲームであるとする。全てのiについてpi ∈ (0, 1/2)ならば、全ての提携構造についてDMS-CSコアは空集合である。
（Lewenbergのプール分析論文を読んでみる11 ←← 前）｜（次 →→ Lewenbergのプール分析論文を読んでみる13）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。