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

本稿について

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

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

スポンサードサーチ

今回のまとめ

• Γを2人のソロマイナーがいるマイナーネットワークとする。p_i > 1/2ならば、γ_i ≥ p_iである。さらに、Dλ > 0ならば、γ_i > p_iである。
  • 一方のマイナーのハッシュパワー比率が1/2より大きければ、そのマイナーがマイニングしたブロックが最長チェーンに属する確率はそのマイナーのハッシュパワー比率以上である。
  • さらに一方のマイナーのハッシュパワー比率が1/2より大きく、かつディレイとマイナーネットワークが毎秒マイニングできるブロック数の期待値がともに0より大きければ、そのマイナーがマイニングしたブロックが最長チェーンに属する確率はそのマイナーのハッシュパワー比率よりも大きくなる。
  • 元となる定理については本文中で補足。

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

4. 2マイナーの場合

SompolinskyとZohar[43]からマイナーネットワークの分析を2マイナー（でプールなし）の場合に拡張する。

定理3

Γを2人のソロマイナーがいるマイナーネットワークとする。このとき、次が成り立つ。

さらに、p₁ = p₂ = 1/2であるならば、

である。

定理4

Γを2人のソロマイナーがいるマイナーネットワークとする。このとき、次が成り立つ。

この定理はγ(Γ)₂ = 1 - γ(Γ)₁であることを示す。p₁ = p₂ = 1/2ならば、ロピタルの定理によりγ₁ = γ₂ = 1/2を得る。証明にはSompolinskyとZohar[43]が用いたものと同様の手法を用いるが、紙面の都合上省略する。

筆者補足：

定理3について

• ここまでくると数式自体を説明しても難解なので、どういった考え方をしているのかを説明します。
• まず、大本となるのがSompolinskyとZoharのこの論文の定理9というものです。この定理9というのは、メインチェーン（本論文に即して言うなら最長チェーン）の毎秒あたりの伸びは最大でどれくらいなのか？を定式化したものです。なお、ネットワークは単一のノード2つ（本論文に即して言うならソロマイナー2人）のみからなるという前提です。
• さて、マイナーが2人（Aさん、Bさん、とします。それぞれのハッシュパワーをp₁、p₂とします。）いるとして、どのような場合にメインチェーンがブロックが追加されるでしょうか。逆説的ですが「片方のマイナーがブロックを作る間に他のマイナーがブロックを作っていない」場合にブロックが追加されます。要するにフォークが起きない場合です。
• ではこの「間」とはどれくらいでしょうか。AさんがいまブロックXを作ったとします。マイナーネットワークのレイテンシは定義上Dですから、まずAさんのブロックXが作られてからD秒間Bさんがブロックを生成しなければメインチェーンに入ります。一方で、AさんのブロックXが作られるD秒前までにBさんが別のブロックYを作っていたとすれば、ブロックXは取り込まれないかもしれません。このように考えると、ブロック生成時点を基準として前後D秒間は必ずしもブロックが取り込まれるか分からない時間なわけです。SompolinskyとZoharらの論文ではこの時間帯を「ウィンドウ（window）」と呼び、この取り込まれない可能性がある状態を「脅かされている（threatened）」と呼んでいます。また、このウィンドウが発生してから実際に脅かされるようになるまでの時間を「オープン（open）」、ウィンドウ発生から脅かされている状態が収束するまでの時間を「クローズ（close）」と呼んでいます。
• さて、この「ウィンドウ」が終わるのは単純にいって①時間経過するか②対立ブロックが作られてしまうかのどちらかです。①は厳密に言えば2D秒経過してもう一人のマイナーがメッセージを受け取った場合、②は2D秒経過する前に対立ブロックを生成した場合です。①は単純ですが、②は2D秒間のうちのどこで起きるか予想がつきません。従ってどこで起きてもいいように、積分を使ってどのくらいの確率かを求めてあげる必要があるわけです。これをω_2Dとします。（これがSompolinskyとZoharらの論文でω_2dとして定義されているものです）。
• ということで、翻って最長チェーンの毎秒あたりの伸びはどのくらいかといえば、Aさんのハッシュパワー分でマイニングできる期待ブロック数＋Bさんのハッシュパワーで取って代わる期待ブロック数になります。
  • これを式で表すと、p₁λ + ω_2D・p₂λになります。
  • で、このω_2Dに積分で計算した結果を当てはめて計算すると定理3が得られます。

定理4について

• 証明については省略されていることもあり説明ができませんが、γ(Γ)₂ = 1 - γ(Γ)₁である点を押さえるのが重要です。
• このマイナーネットワークにはソロマイナーが2人しかおらず、それぞれのハッシュパワーをp₁、p₂とすると、p₁ + p₂ = 1が成り立ちます。この点に注意しつつ、γ(Γ)₂ + γ(Γ)₁を計算してあげると1になります。
• 直観的に言えばAさんBさんの2人しかいないマイナーネットワークで、最長チェーンに属するブロックがマイナーiによりマイニングされた確率γ(Γ)₁と最長チェーンに属するブロックがマイナーBさんによりマイニングされたγ(Γ)₂確率を足したら1になるというのは至極当然の話ではあります。ここで重要なのは、γ(Γ)がそのハッシュパワーとディレイを用いて示されていて、ハッシュパワーの差が大きいほど、ディレイが大きいほどγ(Γ)が一気に大きくなるということが端的に表されている点です。これが次の系1につながっています。

系1

Γを2人のソロマイナーがいるマイナーネットワークとする。p_i > 1/2ならば、γ_i ≥ p_iである。さらに、Dλ > 0ならば、γ_i > p_iである。

例1

あるマイナーネットワークに2人のソロマイナーがいて、一方が55%のハッシュレート（計算パワー）、もう一方が45%のハッシュレートを持っているとしてみよう。Dλの関数γ_iは図3で与えられる。これはマイナー間のハッシュレートが比較的近しい場合でも、Dλが大きくなるにつれて最長チェーンにおけるマイナーの分け前も増大し、最終的には分け前の全て（100%）を占めるに至る。もしこのマイナーネットワークにディレイがない（Dλ = 0）ならば各マイナーの分け前は自身の持つ計算パワーの比率に完全に一致する。

筆者補足

• 「マイナーネットワークにディレイがない（Dλ = 0）ならば各マイナーの分け前は自身の持つ計算パワーの比率に完全に一致する」ことは、定理4の式をDλ = 0として計算してみると分かります。
  • まず先に少し厄介な分子の右辺の括弧内について、Dλ = 0としてしまうと分母に0が出てきてしまうのでDλ → +0として極限を計算すると、-(p₁+p₂-2)/(p₁+p₂) = 1となります。
    • p₁+p₂ = 1を利用。Dλ → +0とするのはディレイやブロックの期待値が0より小さいことはありえず、右側極限（正の方から限りなく0に近づく）を想定するのが妥当なため。
  • よって定理4の式はDλ = 0として、
    • γ(Γ)₁ = ((p₁²*e⁰)-p₁p₂*1)/(p₁²*e⁰-p₂²*e⁰)
    • = (p₁²-p₁p₂)/(p₁²-p₂²)
    • = p₁(p₁-p₂)/((p₁+p₂)(p₁-p₂))
    • = p₁/(p₁+p₂)
    • = p₁/1
    • = p₁
    • となり、確か自身の計算パワーに一致します。

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

免責

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

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