比特幣自私挖礦與戴克字：一個組合證明

目錄

1. 簡介

自私挖礦（Selfish Mining, SM）是比特幣中的一種區塊隱藏策略，它利用了協議難度調整機制中的一個缺陷。與總是擴展公開最長鏈的誠實礦工不同，自私礦工會隱藏新挖出的區塊以建立一個秘密分叉，並策略性地發布它們以最大化收益。評估此類策略的關鍵指標是長期表面算力 $\tilde{q}$，它代表了隨時間推移，攻擊者在官方區塊鏈中所貢獻區塊的比例。

先前的分析依賴於複雜的馬可夫鏈或鞅論技巧。本研究提出了一個直觀的組合證明，使用戴克字（Dyck words）和卡特蘭數（Catalan numbers），使推導過程更易於理解且更為優雅。

2. 攻擊循環與戴克字

一個攻擊循環可以建模為一系列事件，其中每個區塊由自私礦工（S）或誠實礦工（H）挖出。

2.1. 序列表示法

範例：序列 SSSHSHH 表示自私礦工挖出三個區塊，然後誠實礦工挖出一個，接著自私礦工挖出一個，最後誠實礦工挖出兩個。當自私礦工的領先優勢減少時，循環結束，促使他們發布其分叉。

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$ 是在分叉期間於攻擊者區塊上挖礦的誠實礦工比例。

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 的案例分析：

1. 序列必須以 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。那是 4 個 S 和 3 個 H。所以是 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 寫道 "字母 'S'（對應地，'H'）在 w 中的數量是 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 有 4 個 S 和 3 個 H，即 p^4 q^3，不是 p^3 q^4。因此，在戴克字條件下，SS S H S H H 不是 L=4 的有效序列？它可能不平衡。讓我們映射：S→(, H→)。SS S H S H H 變成 ((( ) ( ) )。這不平衡（三個開括號，兩個閉括號）。所以確實，有效的序列是那些 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$ 參數過於簡化；現實世界的網路拓撲和傳播延遲更為複雜。正如後續研究（如 Gervais 等人，Financial Crypto 2016 的「比特幣中的最優自私挖礦策略」）所指出的，原始的自私挖礦策略並非總是最優的；存在更具適應性的策略。本文的貢獻是基礎性的，而非詳盡無遺的。

可操作的見解：

1. 對於協議設計者： 根本原因在於「先見為準」規則和緩慢的區塊傳播。像 Gervais 的「偏好新鮮度」或 Decker 和 Wattenhofer 的「緊湊區塊中繼」（已在 Bitcoin Core 中部署）等解決方案旨在減少 $\gamma$ 和傳播變異性。本文的公式提供了一個可量化的指標來測試此類修復措施。
2. 對於礦池： 門檻計算（$q$ ~0.25）是一條紅線。接近此規模的礦池應受到審查。去中心化不僅僅是意識形態；它是 $\tilde{q}$ 公式中的一個安全參數。
3. 對於分析師： 戴克字映射是一個強大的模板。尋找其他共識機制，其中參與者的行為產生了可由形式語言類別（正則、上下文無關）分析的序列。權益證明系統，因其明確的投票序列，可能適合進行類似分析。

結論：區塊鏈安全日益成為應用數學家和語言學家的領域，而不僅僅是密碼學家。本文是這一轉變的典型範例。

7. 未來應用與方向

1. 擴展攻擊模型： 戴克字框架可以改編用於分析頑固挖礦或追蹤挖礦等變體，其中攻擊者的發布策略有所不同。

2. 其他共識協議： 將類似的組合方法應用於權益證明（例如，以太坊的 Casper）或基於有向無環圖的協議（例如，IOTA, Avalanche），可能對其抵禦隱藏攻擊的韌性產生新的見解。

3. 自動化安全驗證： 可以開發工具，自動將共識協議的規則轉換為形式文法，並檢查是否存在類似於此處發現的戴克結構的「有利可圖的攻擊文法」。

4. 網路動態整合： 未來的工作可以將更真實的網路模型（例如，使用流行病模型進行區塊傳播）整合到組合機率權重中，超越簡單的 $\gamma$ 參數。

8. 參考文獻

1. Eyal, I., & Sirer, E. G. (2014). Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (pp. 436-454). Springer.
2. Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
3. Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.
4. Grunspan, C., & Pérez-Marco, R. (2018). On profitability of selfish mining. arXiv preprint arXiv:1805.08281.
5. 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).
6. Bitcoin Wiki. Difficulty. https://en.bitcoin.it/wiki/Difficulty.
7. Decker, C., & Wattenhofer, R. (2013). Information propagation in the Bitcoin network. In IEEE P2P 2013 Proceedings (pp. 1-10). IEEE.