簡単まとめ

LewenbergのBitcoinマイニングプールにおける協力ゲーム理論分析論文を読んでみる12

更新日:

本稿について

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かつ、∀ipi ∈ (0, 1)である。dはある値d1より小さいものと仮定する(d1P, D, βにより定まる上限値)。このとき、全てのSCS(M)とCi, CjSについて、p(Ci) > p(Cj)であるならば、vS(Ci)/p(Ci) > vS(Cj)/p(Cj)である。

証明概要

M, P, D, βを固定する。d = 0の場合についての補題7の通りの結果になることを証明し、その後で必要な条件を満たす最大の正の値dd1として定義する方法をとる。

SCS(M)を提携構造とし、λはマイナーネットワークΓ = <M, S, P, D, d, λ>についてβ(Γ) = βを満たすλ > 0であるとする。全てのCSについて、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であるからブロックの対立が起こる可能性は存在する。従って全ての提携構造全てのSCS(M)とCi, CjSについて、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で割った値の方が大きくなる」、すなわち「プールCiCjを比較した時に、計算パワーの比率の差以上に利得の差が大きく開く」ことを示せればよいともいえる。d = 0とすることで仮想的にソロマイナーだけのネットワークをみなすことができ、D, λ > 0とすることで系1を適用可能になり、自動的に証明される。...となります。
  • 要は「プールの計算パワーが大きいほどさらに多くの利得を得られる」ということです。
  • d1はその条件を満たすように設定してあげればよい、ということになります。
補題8

Γk = <M, S, P, D, d, λk>(k=1, 2)をマイナーが二人のネットワークで、λ1 > λ2S = {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より小さいものと仮定する(d2P, D, βにより定まる上限値)。このとき、S = {C1, ..., Cm}(m > 2)かつp(C1) ≤  ... ≤ p(Cm)である全てのSCS(M)について、C = C1C2とするとvS(C1) + vS(C2) < vSc(C)である。

証明概要

補題7の証明と同様の手法を用いる。M, P, D, βを固定し、S = {C1, ..., Cm}を補題9の条件と同様の提携構造であるとする。C = C1C2とし、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は「プールの計算パワーが大きいほどさらに多くの利得を得られる」と言い換えることができる。なので、C1C2が別個にマイニングするより、力を合わせて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, β>を定義する。またd1d2はそれぞれ補題7、補題9で得られた上限値と等しいものとする。d < min{d1, d2}ならば、Cの分割関数はPに関して定和かつ非線形かつ単調である。

証明

この分割関数は全てのSCS(M)についてΣCSvS(C) = 1であるので定和である。d < d2であるから、補題9によりこの分割関数は単調である。さて、wR|I|を重みベクトルwi = piとしてこの分割関数がwに関して非線形であることを示す。SCS(M)はmaxCSw(C) > minCSw(C)である提携構造とし、Ci ∈ arg maxCSw(C)とする。d < d2であるから、補題7より、

従って、vS(Ci) > p(Ci) = w(Ci)であり、この分割関数は非線形である。(証明終わり)

筆者補足:

  • 全てのSCS(M)についてΣCSvS(C) = 1であるので、定義3より定和である。
  • d < d2ならば補題9は全てのSCS(M)について、C = C1C2とするとvS(C1) + vS(C2) < vSc(C)であり、これも定義3より単調である。
  • 重みベクトルとマイナーの計算パワーの比率が一緒とすると、少なくとも最も計算パワーの大きいマイナーは補題7より計算パワーより大きな利得を得ているのは明らかである。よってvS(Ci) > p(Ci) = w(Ci)で、定義3より非線形である。

さて、以上により本章の主たる成果であるDMS-CSコアの空集合の条件を述べることができる。これまで証明した定理を組み合わせることにより次の系2が示される。

系2

C = <M, P, D, d, β>は定理の通りの提携構造を持つ提携形ゲームであるとする。全てのiについてpi ∈ (0, 1/2)ならば、全ての提携構造についてDMS-CSコアは空集合である。

Lewenbergのプール分析論文を読んでみる11 ←← 前)|(次 →→ Lewenbergのプール分析論文を読んでみる13

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。

-簡単まとめ
-, , , , ,

Copyright© 暗号通貨界隈のメモ書きなど。 , 2019 All Rights Reserved Powered by STINGER.

%d人のブロガーが「いいね」をつけました。