作者: Ittay Eyal
原文標題:《引介 | 區塊鏈中的自私挖礦》
來源:以太坊愛好者
翻譯: 阿劍
工作量證明(PoW)區塊鏈實現了一種形式的狀態機複製系統(State Machine Replication,SMR)。不像傳統的 SMR 協議,PoW 區塊鏈是開放的,即,任何人都可以加入這個協議,而且系統也會用經濟利益來激勵參與者(也叫「礦工」)遵守協議。因此,同樣迥異於傳統 SMR 協議的地方是,在推理區塊鏈的安全性時,僅僅假設惡意參與者的數量往往並不能得到答案。關鍵是要問一問,礦工是否真的有足夠的動機來遵守所在的協議。這就是本文要討論的東西。
爲使討論更具體一些,我們把討論的語境限定爲中本聰的比特幣協議。Ling 已經提供了一些相關的背景知識,以及一個對惡意敵手的安全性分析。在我們的分析中,我們準備把這個系統描述爲礦工之間的一個遊戲(game,亦可稱「博弈」)。
遊戲
遊戲玩家就是出塊的礦工。這個遊戲是按回合(round)來進行的,每一回合都有一個礦工可以出一個區塊,其他礦工可以發佈(publish)這個區塊。同時,遊戲中的消息是同步(synchronous)傳播的,因此,所有礦工都會收到上一輪發布的區塊。
這樣當然是簡化了現實,例如,這個模型忽略了系統中挖礦總算力的緩慢變化,也忽略了偶爾會發生的出塊衝突(即分叉)(這種情況雖然少見,但還是會發生的)。雖然如此,這個模型作爲一階近似,也足夠了。
協議的規定是讓每一個礦工都在最長鏈上出塊,或者,如果分叉中的兩條鏈長度相同,他們就跟隨自己先接收到的那條鏈。
遊戲中的每一個玩家都致力於最大化自己的收益——這個就是 TA 的效用函數(utility function)了。具體來說,我們還假設這是一個 infinite-horizon 遊戲,即,隨着遊戲時間不斷趨近於無限,一個礦工的收益就是其平均出塊比例。這就代表,密碼學貨幣形式的獎勵是按礦工所出的區塊發給出塊礦工的。注意,主鏈之外的區塊不會進入礦工的收益。
重要觀察
主鏈上的出塊比例就是對礦工收益的實時模擬。
假設系統中的挖礦總算力是靜態不變的,系統每 10 分鐘出一個區塊,攻擊在一次難度調整完成後立即發動。假設一種出塊策略會導致網絡中一定比例的區塊被拋棄,比如所有礦工出的塊中有 20% 的塊會產生在主鏈之外,而且這個比例是穩定的。那麼,雖然這個系統仍然是每 10 分鐘出一個塊,但只有 80% 會出在主鏈上,也就是主鏈的生長速度會變成每 12.5 分鐘延長一個塊,而不是每 10 分鐘延長一次。比特幣協議每出 2016 個塊會調整一次難度,如此一來,調整難度所需的時間也會比一般情形要長(是 12.5×2016 分鐘,而不是 10×2016 分鐘)。
一旦難度調整發生,難度又會下降,使得主鏈的出塊間隔重新變回 10 分鐘。這就意味着系統的整體出塊速度更高了,每 8 分鐘就能出一個塊。
所以,一個礦工如果有算力佔全網比例爲 α,且在主鏈上出塊的佔比爲 α′ >α,則其每小時收益會與 α′ 成比例(而不是與 α 成比例)。
自私挖礦算法
自私挖礦(Selfish Mining)是一種投機挖礦算法,用於證明前述協議對小礦工並不公平(not an equilibrium)。我們先來看看自私挖礦的機制,然後討論看看自私挖礦爲什麼以及何時會產生這樣的效果。
一開始,自私的礦工會在最長鏈上挖礦,就像協議希望的那樣。不過,一旦 TA 挖出了一個區塊,TA 會先把這個區塊藏起來,而不是立即發佈出去,然後嘗試在這個祕密塊後繼續出塊,形成一個「祕密分支」。

與此同時,其它礦工會延長公開的那條鏈,這條鏈最終會變得更長(概率爲 1),因爲他們的挖礦算力佔大頭。而自私挖礦的礦工會繼續延長其祕密分支,直到公開分支落後一個區塊。然後自私礦工就會把自己的祕密分支發佈出來。

因爲祕密分支更長,那麼另一方就會認爲這條纔是主鏈,從這時開始,所有人都會跟隨自私礦工的分支,而其他礦工挖出的區塊會被拋棄——被忽略,並使得出塊礦工一無所獲。
但這種策略也不是萬無一失——從開始祕密挖礦時起,自私礦工就一直承擔着風險。如果 TA 出了一個祕密區塊同時別的礦工也出了一個區塊,TA 就不能靠發佈這個祕密區塊來變成最長鏈;相反,此時會變成兩個同樣長的分支在競爭最長鏈。

自私礦工會嘗試延長自己的分支;爲簡化分析,我們假設其他礦工也會嘗試延長自己所在的分支。如果 TA 能搶先出下一個塊,則 TA 的分支會變成最長鏈,然後下一次攻擊會在這條最長鏈的末端重新開始。如果其他礦工生出,那麼自私礦工就屬於不利地位(TA 的鏈更短)。在這種情況下,TA 會放棄這次攻擊,尋找下一次機會。在這次攻擊中,TA 的祕密分支會變成一條較短的分叉,使 TA 一無所獲。
自私挖礦分析
乍一看,這種攻擊應該不會奏效——自私礦工的算力只佔少數,必定是贏少輸多。不過,一個細緻的分析表明,並不總是如此。這個遊戲可以自然而然地描述成一個 Markov Chain(譯者注:馬爾可夫鏈,在狀態轉換的過程中是「無記憶性」的,即新一回閤中的得益跟以往任何一回合的得益都無關)。通過計算自私礦工的出塊和其他礦工的出塊情況,我們可以計算出自私礦工的區塊(及收益)在主鏈上的比例,其實就是其算力規模的函數。

我們可以看出,算力佔比超過 1/3 的自私礦工可以通過違反協議及執行自私挖礦算法來提高自己的收益。
結論
上述分析表面,當自私礦工的算力超過 1/3 時,自私挖礦的策略比誠實挖礦的策略收益高,但這是在樂觀的假設下的結果。想要更深度的分析(包括更弱的模型以及加強協議的路徑),請看 Financial Crypto 2013 上的論文以及 ACM 2018 會議上的論文。
後續的 研究,包括最近的一個,都使用馬爾可夫方法來確定誠實挖礦策略佔優的算力閥值(就跟本文使用的方法一樣)。
感謝 Ittai Abraham 富有教益的反饋。請在 Twitter 裏給我們一些評論。
(完)
原文鏈接:https://decentralizedthoughts.github.io/2020-02-26-selfish-mining/
歡迎加入律動 BlockBeats 官方社群:
Telegram 訂閱群:https://t.me/theblockbeats
Telegram 交流群:https://t.me/BlockBeats_App
Twitter 官方帳號:https://twitter.com/BlockBeatsAsia