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

本稿について

Bitcoinマイニングプールのインセンティブ設計について協力ゲーム理論の観点から分析したLewenbergらの論文を見ていきます。本稿では「3. A Network of Miners」を見ます。

原文はこちらになります。

スポンサードサーチ

今回のまとめ

• マイナーのインタラクションを表すのに、Γ = <M, S, P, D, d, λ>で定義されるモデル「マイナーネットワーク」を用いる。
  • Mはマイナーの集合である。
  • Sはマイナーをプールに分ける分割である。
  • Pはマイナーの計算パワーの分布である。
  • pはマイナーの計算パワーの割合である。
  • Dはプール間のディレイである。
  • dはプール内のディレイである。
  • λはマイナーネットワークが毎秒マイニングできるブロック数の期待値である。
  • プールに参加していないマイナーをソロマイナーと呼ぶ。
  • βは毎秒最長チェーンに追加されるブロックの比率である。
  • γは最長チェーンに属するブロックがマイナーiによりマイニングされた確率である。
• Γ = <M, S, P, D, d, λ>を|M| > 1、D > 0, d > 0のマイナーネットワークであるとする。全てのソロマイナーiについて、λ ≥ β(Γ) > p_iλが成り立つ。
  • マイナーが少なくとも2人、プール間のディレイもプール内のディレイも0より大きいマイナーネットワークがあるとすると、毎秒最長チェーンに追加されるブロックの比率は、「毎秒マイニングネットワークがマイニングできるブロックの期待値以下」であり、「毎秒マイナー個人がマイニングできるブロックの期待値よりも大きい」。
• Γ = <M, S, P, D, d, λ>を1プールだけがあってソロマイナーが存在しないマイナーネットワークであるとする。このとき、 β(Γ) = ^λ/_1+2dλである。
  • ソロマイナーがいなくて1プールだけ存在するマイナーネットワークがあるとすると、毎秒最長チェーンに追加されるブロックの比率は「プール内ディレイ2回分と次のブロックを作るのにかかる期待秒数を足したものの逆数」に等しい。
• 期待するβを得るために閾値を調整することをリターゲティングと呼ぶ。

※以下、今回まとめた範囲の論文和訳になりますので詳細をご覧になりたい方は読み進めてください。

3. マイナーのネットワーク

マイニングプールのインタラクションを「マイナーネットワーク（miner network）」としてモデル化する。マイナーネットワークはタプルΓ = <M, S, P, D, d, λ>である。ここで、M = {1, ..., n}はマイナーの集合、Sはいくつかのマイナーをプールに分ける分割（Sの各要素は1つのプールを構成するマイナーのチームである）を表す。P = {p₁, ..., p_n}はマイナー間における計算パワーの分布であり、p_iがエージェントiの計算パワーの割合であるならば、∀_i ∈ M、p_i ∈ [0, 1]、Σ_i∈Mp_i = 1である。D > 0は「異なる（different）」プールのマシン間の通信ディレイ（「プール間（between pools）」のディレイ）で、数秒である。d > 0は「同一の（same）」プールのマシン間のディレイ（「プール内（within a pool）」のディレイ）である。λはマイナーネットワークが毎秒マイニングできるブロック数の期待値である。全てのマイナーi∈Mはパラメータp_iλのポアソン過程に従ってブロックをマイニングするものと仮定する。プールに参加しないマイナーを「ソロマイナー（solo miner）」と呼ぶ。私たちのモデルでは、プール内のマイナーはプール管理者を介してのみ通信を行うものとする。ゆえに、プールC_jのマイナーiが時点tでブロックBをマイニングしたとすると、プールC_jのプール管理者は時点t + dでブロックBがマイニングされたと分かる。この時点でブロックBが最長チェーンを伸ばすものであるならば、プール管理者は残りのネットワークへブロックBを公開し、次にマイニングするブロックのヘッダについて参加者をアップデートする。その後すぐ時点t + 2dでプールC_jの他のマイナーはブロックBを把握し、時点t + d + Dで他プールのプール管理者とソロマイナーがブロックBを把握する。9人のマイナーと3つのプールがあるネットワークを図2に示す。

記法はSompolinskyとZoharのもの[43]に準じる。所与のマイナーネットワークΓについて、毎秒「最長チェーン（the longest chain）」に追加されるブロックの比率を示すものとしてβ = β(Γ)を定義する。

全てのマイナーiについて、最長チェーンに属するブロックがマイナーiによりマイニングされた確率をγ_i = γ(Γ)_i ∈ [0,1]で表す。全てのプールC_j ∈ Sについて、γ_Cj = Σ_i∈Cjγ_iを定義する。マイナーは最長チェーンのブロックについてのみ報酬をもらえるので、マイナーiはγ_iを増やすインセンティブがある。

補題1.

Γ = <M, S, P, D, d, λ>を|M| > 1、D > 0, d > 0のマイナーネットワークであるとする。全てのソロマイナーiについて、λ ≥ β(Γ) > p_iλが成り立つ。

証明

左辺の不等式は、最高の条件でも全てのブロックが最長チェーンに含まれるので成立する。右辺の不等式について、同じエージェントにより生成されたブロックの順序はどんなものであれブロック高を増やす。ゆえに最長チェーンの成長率はどんなに小さくてもあらゆるソロマイナーのブロック生成率よりは大きい。（証明終わり）

筆者補足：

• 左辺・右辺ともに次のようにイメージするとよいでしょう。
• 左辺：生成されたブロックが全て運よくブロックチェーンに取り込まれることはあるが、マイニングが遅かった結果、ブロックが取り込まれないという状況もありうる。従って、「毎秒最長ブロックチェーンに追加されるブロックの比率」が「毎秒生成されるブロックの比率」を超えることはない。
• 右辺：ブロックが追加される場合を、①同じ人が連続してマイニングした場合と②違う人がマイニングした場合」に分けてみよう。①の場合、自分（マイナーiさん）で作ったブロックのあとにブロックを追加しているのだから、必ずブロックは追加される。この期待値はp_iλである。②について、マイナーは2人以上いてそれぞれがハッシュパワーを費やしてマイニングしようとしているのだから、当然この確率が0であることはありえない。
• ※ビザンチンなマイナー（例えば故障したマイナーを仮定）がいるならば①の場合でも必ずブロックが追加されるとは限らない...という指摘があるかと思いますが、本論文第2章で誠実なマイナーでありプロトコルに従うという仮定を置いているため成立します。（参照：Lewenbergのプール分析論文を読んでみる3）

補題2.

Γ = <M, S, P, D, d, λ>を1プールだけがあってソロマイナーが存在しないマイナーネットワークであるとする。このとき、 β(Γ) = ^λ/_1+2dλである。

証明

このマイナーネットワークでは、プール管理者の最長チェーンとネットワークの最長チェーンは一致する。ブロックBは最長チェーンを伸ばすものとして作られてプール管理者に受け入れられた最新のブロックであるとする。プール管理者がブロックを受信すると、プール管理者はd秒でマイニングすべき新しいブロックヘッダを送りマイナー（Bの生成者を含む）を更新する。この間に生成されたブロックは古いものとして全てプール管理者に無視される。期待値でλ^-1秒後、前ブロックとしてブロックBを参照する新しいブロックCが生成されると、d秒でプール管理者がブロックCを把握し、先と同様にこの間に作られた全てのブロックは無効になる。従って最長チェーンが一度延伸してから次に延伸するまでの時間の期待値は2d+λ^-1であるから、最長チェーンの成長率は(2d+λ^-1)^-1 = ^λ/_1+2dλとなる。（証明終わり）

筆者補足：

• まず、補題2では1プールだけがある状況を仮定している。また、本論文のモデルでは必ずプールの管理者を通じて通信をする点は忘れずに押さえておきたい。
• 以上をもとにすると、プール内でブロックを追加するプロセスは次のようになる。
  • ①何らかのマイナーがブロックを生成する→②プール管理者が把握し、他のマイナーへ新しいブロックのブロックヘッダを送る→③マイナーが新しいブロックを把握する→①何らかのマイナーがブロックを生成する...以下略。
  • さて、それぞれにどのくらいの時間がかかるのかを考えてみよう。定義上、プール内のディレイはdであるので、①→②にd秒かかり、②→③にd秒かかる。③→①はどうだろうか。1秒あたりに生成されるブロック数の期待値は定義上λであるから、ブロック1個を作るのにかかる秒数の期待値は1をλで割ればよく、1/λ（＝λ^-1）である。従って、ブロックが1個追加されるまでにかかる秒数の期待値はこれらを全て足して2d+λ^-1である。
  • 従ってβ、つまり毎秒最長チェーンに追加されるブロック数の比率は1を2d+λ^-1で割ってあげればよい。つまり1/(2d+λ^-1)=^λ/_1+2dλとなる。

リターゲティング

最長チェーンのトランザクションだけが有効とみなされるので、Bitcoinネットワークが処理できるトランザクション量はマイニングされたブロック数ではなく最長チェーンに追加されるブロックの比率により決まる。マイナーネットワークΓにおける最長チェーン延伸の目標率βを考ると、プロトコルのパラメータはβ(Γ) = βであるように設定される²。これはハッシュ後の値が下回るべき閾値tを決定することで設定する。ハッシュ値によりたくさんのゼロの羅列を必要とする（つまり閾値tよりも小さい値である）ことは空間から選んだナンスが条件を満たすものである可能性を下げ、マイナーの計算面での負担を上げる。期待するβ(Γ) = βの値を得るために閾値を調整することを「リターゲティング(retargeting)」という。

脚注2：記法通りではないが、パラメータと関数の両方を表すのにβを用いている。

（Lewenbergのプール分析論文を読んでみる6　←←　前）｜（次　→→　Lewenbergのプール分析論文を読んでみる8）

免責

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

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