目次
1. はじめに
セルフィッシュマイニング（SM）は、ビットコインのプロトコルにおける難易度調整メカニズムの欠陥を悪用するブロック保留戦略です。常に公開された最長チェーンを延長する正直なマイナーとは異なり、セルフィッシュマイナーは新たにマイニングしたブロックを保留して秘密のフォークを作成し、収益を最大化するために戦略的に公開します。このような戦略を評価するための重要な指標は、長期的な見かけのハッシュレート $\tilde{q}$ であり、これは時間の経過とともに攻撃者が公式ブロックチェーンに貢献したブロックの割合を表します。
従来の分析は複雑なマルコフ連鎖やマルチンゲール手法に依存していました。本研究では、ダイク語とカタラン数を用いた直感的な組み合わせ論的証明を提示し、導出をより理解しやすく洗練されたものにします。
2. 攻撃サイクルとダイク語
攻撃サイクルは、各ブロックがセルフィッシュマイナー（S）または正直なマイナー（H）によってマイニングされる一連のイベントとしてモデル化できます。
2.1. シーケンス表現
例：シーケンス SSSHSHH は、セルフィッシュマイナーが3ブロックをマイニングし、その後正直なマイナーが1ブロック、次にセルフィッシュマイナーが1ブロック、最後に正直なマイナーが2ブロックをマイニングしたことを示します。サイクルは、セルフィッシュマイナーのリードが減少し、彼らが自分のフォークを公開するよう促されたときに終了します。
2.2. Lの分布
$L$ を攻撃サイクルごとに公式ブロックチェーンに追加されるブロック数とします。
定理 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, そして $n \geq 3$ に対して、 $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ ここで $C_n = \frac{(2n)!}{n!(n+1)!}$ は $n$ 番目のカタラン数です。
証明の概略: $n \geq 3$ に対して、事象 ${L=n}$ は SS で始まり H で終わり、中間部分が S→"("、H→")" とマッピングされたときに、長さ $2(n-2)$ のダイク語（バランスの取れた括弧列）を形成するシーケンスに対応します。カタラン数 $C_{n-2}$ はそのようなダイク語の数を数えます。
3. 主要な数学的結果
3.1. Lの期待値
系 2.3: $E[L] = 1 + \frac{p^2 q}{p - q}$.
これはカタラン数の既知の母関数関係から導かれます。
3.2. 見かけのハッシュレートの公式
$Z$ を攻撃者がサイクルごとに公式チェーンに追加するブロック数とします。長期的な見かけのハッシュレートは $\tilde{q} = E[Z] / E[L]$ です。
定理 2.4: ビットコインにおける見かけのハッシュレートは次の通りです： $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ ここで、$p$ は正直なマイナーのハッシュレート、$q$ は攻撃者のハッシュレート（$p+q=1$, $q<1/2$）、$\gamma$ はフォーク中に攻撃者のブロック上でマイニングを行う正直なマイナーの割合です。
主要パラメータ
- p: 正直なネットワークのハッシュレート
- q: 攻撃者のハッシュレート ($q < 0.5$)
- γ: 接続性パラメータ ($0 \leq \gamma \leq 1$)
- L: サイクルごとに公式チェーンに追加されるブロック数
- Z: サイクルごとに公式チェーンに含まれる攻撃者のブロック数
4. 技術分析とフレームワーク
4.1. 数学的フレームワーク
中核となる革新は、攻撃シーケンスをダイクパス（バランスの取れた括弧列）にマッピングすることです。これにより、セルフィッシュマイニングが確立された組み合わせ論と結びつき、確率過程を必要とした従来の確率計算が簡略化されます。
主要公式: $n\geq3$ に対する確率 $P[L=n]$ は、カタラン数 $C_{n-2}$ に確率重み $p$ と $q$ をスケーリングしたものに直接比例します： $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.
4.2. 分析フレームワークの例
L=4 の場合分析:
- シーケンスは
SSで始まりHで終わらなければならない。 - 中間の2つの位置は長さ2のダイク語を形成しなければならない：
SHまたはHSのみ？確認してみよう：L=4の場合、n=4なので、n-2=2。中間部分に長さ2*(2)=4文字のダイク語が必要？注意：定理によれば、n≥3に対して、P[L=n] は w = SS X1...X_{2(n-2)} H の形式のシーケンスに対応し、Xの部分が長さ 2(n-2) のダイク語を形成する。n=4の場合、長さは2*(4-2)=4。したがって、中間部分は4文字でダイク語を形成する。例：SS(SHSH)H？ S→(, H→) とマッピング。中間の "SHSH" は "()()" となり、これはダイク語である。確率重みは p^{#S} q^{#H} = p^3 q^3？ w=SS S H S H H のSとHを数えてみよう：Sは4回出現？実際：SS S H S H H：位置：S,S,S,H,S,H,H。これはSが4つ、Hが3つ。したがって p^4 q^3。公式は p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4 を与える。不一致がある。PDFには「wにおける文字'S'（および'H'）の数はそれぞれ n（および n-1）である。したがって、P[L=n] = p^{n-1} q^n C_{n-2} を得る」とある。n=4の場合、p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4。これは公式と一致する。したがって、例のシーケンス SS S H S H H はSが4つ、Hが3つで、p^4 q^3 であり、p^3 q^4 ではない。つまり、SS S H S H H はダイク語の条件下での L=4 の有効なシーケンスではない？バランスが取れていない可能性がある。マッピングしてみよう：S→(, H→)。SS S H S H H は ((( ) ( ) ) となる。これはバランスが取れていない（開き括弧3つ、閉じ括弧2つ）。したがって、確かに有効なシーケンスは、Sの総数が n、Hの総数が n-1 であり、かつ中間部分がダイク語であるものに限られる。ダイク条件はバランスを強制し、特定のカウントをもたらす。したがって、このフレームワークは有効な攻撃経路を優雅に捉えている。
このフレームワークにより、マルコフ連鎖をシミュレートすることなく、体系的な列挙と確率計算が可能になります。
5. 結果と示唆
導出された $\tilde{q}_B$ の公式は、セルフィッシュマイニングの利益閾値を定量化します。例えば、$\gamma=0$ の場合、攻撃者が利益を得るには $q > \approx 0.25$ が必要であり、素朴な仮定 $q>0.5$ よりも低くなります。これはプロトコルの重大な脆弱性を浮き彫りにします。
チャートの説明: 異なる $\gamma$ 値に対する $\tilde{q}_B$ と $q$ のプロットは次のことを示すでしょう：1) 閾値を超える $q$ に対して $\tilde{q}_B > q$ となり、収益性を示す。2) $\gamma$ が高いほど（攻撃者の接続性が良いほど）、収益性の閾値が下がり、見かけのハッシュレートの増加が大きくなる。
6. 業界アナリストの視点
中核的洞察: 本論文の優れた点は、複雑で状態を持つ攻撃を、クリーンな組み合わせモデルに還元したことです。これは、セルフィッシュマイニングの収益性が単なる生のハッシュレートではなく、攻撃シーケンスと正準的な組み合わせオブジェクト（ダイク語）との構造的結合に関するものであることを明らかにしています。これは単なる数学のトリックではなく、ビットコインプロトコルの脆弱性を形式言語問題として暴露しています——その安全性は、ブロック競争における特定の文字列パターンの確率分布に依存しているのです。
論理的流れ: 著者らはまず、攻撃サイクルを文字列（S/Hシーケンス）として捉えます。重要な動きは、成功した攻撃（攻撃者のブロックがすべて承認される場合）が、本質的に特定の開始/終了記号で囲まれたダイク語である文字列に対応することを認識したことです。これにより、マルコフ連鎖の平衡方程式を解く必要を迂回して、カタラン組み合わせ論の広大な仕組みを直接利用して数え上げと確率生成を行うことが可能になります。最終的な公式は、Lの期待値（カタランの母関数を通じて）とZの期待値（L=1,2のようなエッジケースを考慮して）を結びつけることで導出されます。
長所と欠点:
長所: 証明は非常に簡潔で理解しやすい。セルフィッシュマイニングの収益公式の神秘を解き明かす。ダイク語との関連付けは、形式言語理論を用いた他のブロックチェーン攻撃（例：バランシング攻撃、エクリプス攻撃）の新たな分析を刺激する可能性がある。学際的アプローチ（暗号＋組み合わせ論）の価値を強化する。
欠点: モデルは、一定の q を持つ静的で持続的な攻撃者を仮定している。動的適応、マイナーの参入/退出、または複数のセルフィッシュマイナーが存在する場合の影響（潜在的寡占問題）を捉えていない。$\gamma$ パラメータは単純化されすぎている。現実世界のネットワークトポロジーと伝播遅延はより複雑である。"Optimal Selfish Mining Strategies in Bitcoin"（Gervais et al., Financial Crypto 2016）などの追跡研究で指摘されているように、元のセルフィッシュマイニング戦略は常に最適とは限らず、より適応的な戦略が存在する。本論文の貢献は基礎的であり、網羅的ではない。
実用的な洞察:
- プロトコル設計者向け: 根本原因は「最初に見たものを優先」ルールと遅いブロック伝播にある。Gervaisの「新鮮さ優先」やDeckerとWattenhoferの「コンパクトブロックリレー」（Bitcoin Coreで実装済み）のような解決策は、$\gamma$ と伝播のばらつきを減らすことを目指している。本論文の公式は、そのような修正をテストするための定量化可能な指標を提供する。
- マイニングプール向け: 閾値計算（$q$ ~0.25）は警戒ラインである。この規模に近づいているプールは精査されるべきである。分散化は単なる理念ではなく、$\tilde{q}$ 公式におけるセキュリティパラメータである。
- アナリスト向け: ダイク語マッピングは強力なテンプレートである。参加者の行動が形式言語クラス（正則、文脈自由）で分析可能なシーケンスを生成する他の合意メカニズムを探せ。明示的な投票シーケンスを持つProof-of-Stakeシステムは、同様の分析に適している可能性がある。
7. 将来の応用と方向性
1. 拡張攻撃モデル: ダイク語フレームワークは、攻撃者の公開戦略が異なるスタボーンマイニングやトレイルマイニングの亜種を分析するために適応できます。
2. 他の合意プロトコル: 同様の組み合わせ論的手法をProof-of-Stake（例：EthereumのCasper）やDAGベースのプロトコル（例：IOTA, Avalanche）に適用することで、保留攻撃に対する耐性に関する新たな洞察が得られる可能性があります。
3. 自動化されたセキュリティ検証: 合意プロトコルのルールを形式文法に自動翻訳し、ここで見つかったダイク構造に類似した「収益性のある攻撃文法」の存在をチェックするツールを開発できます。
4. ネットワークダイナミクスの統合: 将来の研究では、より現実的なネットワークモデル（例：ブロック伝播のための伝染病モデル）を組み合わせ論的確率重みに組み込み、単純な $\gamma$ パラメータを超えることができます。
8. 参考文献
- Eyal, I., & Sirer, E. G. (2014). Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (pp. 436-454). Springer.
- Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
- Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.
- Grunspan, C., & Pérez-Marco, R. (2018). On profitability of selfish mining. arXiv preprint arXiv:1805.08281.
- Gervais, A., Karame, G. O., Wüst, K., Glykantzis, V., Ritzdorf, H., & Capkun, S. (2016). On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (pp. 3-16).
- Bitcoin Wiki. Difficulty. https://en.bitcoin.it/wiki/Difficulty.
- Decker, C., & Wattenhofer, R. (2013). Information propagation in the Bitcoin network. In IEEE P2P 2013 Proceedings (pp. 1-10). IEEE.