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

目錄

1. 簡介

自私挖礦（SM）係比特幣中一種扣留區塊嘅策略，利用協議難度調整機制嘅漏洞。同誠實礦工永遠延伸最長公開鏈唔同，自私礦工會扣留新挖出嘅區塊，創建一條秘密分叉鏈，並策略性地發布佢哋以最大化收益。評估呢類策略嘅關鍵指標係長期表面算力 $\tilde{q}$，代表隨時間推移，攻擊者貢獻到官方區塊鏈嘅區塊比例。

先前嘅分析依賴複雜嘅馬可夫鏈或鞅技術。呢項工作提出一個直接嘅組合證明，使用迪克詞同卡特蘭數，令推導更易理解同優雅。

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$ 假設。呢個突顯咗協議嘅關鍵漏洞。

圖表描述： 繪製 $\tilde{q}_B$ 對 $q$ 嘅圖（針對唔同 $\gamma$ 值）會顯示：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）或基於 DAG 嘅協議（例如 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.