區塊鏈系統中礦池間的博弈問題及優化*

楊 天，薛 質

（上海交通大學 電子信息與電氣工程學院，上海 200240）

0 引 言

區塊鏈是一種分布式共享總賬，系統中的每一個參與者都負責數據的記錄與存儲，從而實現了去中心化[1]。目前在各種區塊鏈系統中，比特幣是區塊鏈最成功的應用之一，它在區塊的生成過程中使用了PoW（Proof of Work，工作量證明）機制。PoW是一種激勵性算法，它的核心概念是通過礦工之間的競爭來保證數據的安全性、連續性與一致性。系統中各節點根據各自的算力爭相角逐，共同解決一個求解復雜但是驗證容易的SHA256數學問題[2]。其中解決該問題的節點會提供一個合理的Block Hash，同時獲得在區塊中記錄數據的權利，并得到系統自動生成的比特幣獎勵。一個符合要求的Block Hash由N個前導零構成，零的個數取決于網絡的難度值。要得到合理的Block Hash需要經過大量嘗試計算，計算時間取決于機器的哈希運算速度。當某個節點提供出一個合理的Block Hash值，說明該節點確實經過了大量的嘗試計算，當然，并不能得出計算次數的絕對值，因為尋找合理Hash是一個概率事件。可見在PoW機制下，每個礦工為了獲得比特幣獎勵將會盡其所能地利用其算力解決問題并嘗試挖礦，新的數據區塊不斷生成，從而產生了區塊鏈[3]。

其它基于PoW的區塊鏈系統也是以同樣的方式運作的，雖然各種系統所提出的數學難題并不相同，但是都有一個共同特征：用算力換收益，并且利用分布網絡節點的工作量證明使各個節點達成共識，從而實現交易數據的記錄與存儲，同時產生了一套有時間先后順序的，不可篡改的，可信任的數據庫。通過復雜的校驗機制，區塊鏈系統可以保證數據庫中數據的完整性，連續性，和一致性。即使部分參與者作假也無法改變區塊鏈的完整性，也無法篡改區塊鏈中的數據。簡而言之，區塊鏈技術涉及的關鍵點有：去中心化、集體維護、去信任、可靠數據庫、時間戳、非對稱加密等[4]。

1 背景知識

1.1 礦池概念

區塊鏈系統中，生成區塊的過程被稱為挖礦，所有參與挖礦的節點被稱為礦工。由于全網算力非常巨大，而區塊產出有限，單個設備或少量的算力都很難在比特幣網絡上獲取到比特幣網絡提供的區塊獎勵。為追求穩定收益，人們自發地將算力聯合起來形成礦池。一個礦池有一位管理員，當礦池的一位參與者挖到區塊時，比特幣獎勵會發送到礦池管理員。然后，管理員根據每個參與者對礦池算力的貢獻，向參與者發放比特幣獎勵。在此機制中，不論個人礦工所能使用的運算力多寡，只要是通過加入礦池來參與挖礦活動，無論是否有成功挖掘出有效資料塊，皆可經由對礦池的貢獻來獲得少量比特幣獎勵，亦即多人合作挖礦，獲得的比特幣獎勵也由多人依照貢獻度分享。

1.2 區塊截留攻擊

由于每一個礦工只要提供一個網絡ID數字就可以加入礦池，一個開放的礦池很容易遭受攻擊。具體形式為：一些礦工會發送部分工作量證明（Partial Proof of Work，對產出幾乎無幫助，只是證明干了活），拋棄完整工作量證明（Full Proofs of Work，收益來源）。這就是所謂的區塊截留攻擊，這個行為看似損人不利己，那么選擇攻擊的礦工的目的是什么呢?主要原因是，區塊鏈協議具有難度自適應的特征，會根據當前區塊生成速度調整前導0的個數，從而改變難度，控制區塊生成速度保持不變。有礦工選擇攻擊會導致礦池有效算力減少，協議為了保持區塊生成速度不變，自會降低挖礦難度，這樣濫竽充數的礦工就會得到更多收益。其次是因為，得到獎勵的礦池會根據工作量證明按照礦池中每個礦工貢獻算力的比例將所獲獎勵分配給每一個礦工。而完整的工作量證明很難生成，偷奸耍滑的礦工可以選擇向開放礦池發送部分工作量證明來獲得本該貢獻實際算力才能得到的獎勵。

在一個開放礦池中，一個礦工可以選擇與其他礦工合作或是對其他礦工發動區塊截留攻擊，兩種選擇都會獲得相應的收益。當所有礦工都選擇攻擊時，它們獲得的收益比所有礦工都不選擇攻擊時獲得的收益要小。這種情況被稱為PoW共識算法中的挖礦困境[5]，對于一個礦工來說攻擊是最好的選擇，而這個選擇會使系統收益減少。所以，為了促使礦池中的所有礦工合作挖礦提高系統收益，需要開發一種激勵性機制來促進礦工合作從而優化區塊鏈PoW共識算法。

1.3 初步建模及策略

為了避免區塊鏈中的礦工陷入挖礦困境，選擇合作的礦工可以采取一些策略來解決攻擊礦工“拿錢不干事”的問題或者盡量減小損失。有了相應的策略，礦池中一個礦工不管與它競爭的對手礦工采取什么策略，它都能單方面地控制對手從自己這里得到的期望收益并分給對手一定比例的期望收益從而促進對手更傾向于合作。以更宏觀的視角分析，不妨嘗試將兩個礦工之間的博弈以類似的思路放大為兩個礦池間的博弈。考慮到全網的其中兩個礦池A和礦池B，B礦池派出總算力為b的礦工，在A礦池注冊，這些礦工在A礦池進行區塊截留攻擊。這樣一來總算力降低，根據協議，區塊生成難度降低，B礦池獲得正收益，而A礦池通過不斷減少的收益中能發現它正在遭受攻擊，但很難發現究竟是那些礦工進行攻擊。實際情況中，攻擊往往是雙向的，設A礦池派出的滲透算力為a，B礦池的滲透算力為，則對于A礦池來說，面對B礦池可以采取多種策略來應對。

目前常見的策略有如下9種[6]（分別用Pn表示）：

P1--ALLC：All Cooperate，永遠合作策略，無論對手采取何種策略，都選擇合作，即令滲透算力a恒為0。

P2--ALLD：All Defect，永遠背叛策略，無論對手采取何種策略，都選擇背叛，即令滲透算力a恒為最大。

P3--TFT：Tit For Tat，一報還一報策略，第一次選擇合作(即a=0)此后，如果對手的滲透算力b大于某一閾值，則下一輪背叛（即a=max），否則合作（即a=0）。

P4--Grim：冷酷策略，第一次選擇合作(即a=0),只要對手背叛一次，就不再合作，令a=max。

P5--WSFS：Win Stay Fail Shift，贏存輸變策略，第一次選擇合作(即a=0)，之后每一輪如果收益高于某一閾值，就保持策略不變，否則采取相反的策略(即a=max)。

P6--Random：離散型隨機取值策略，a以等概率取0或max。

P7--TFT_D：TFT_Defect，類似于TFT，區別在于第一次選擇背叛(即a=max)。

P8--Grim_D：Grim_Defect，同上，類似于Grim。

P9--WSFS_D：WSFS_Defect，同上，類似于WSFS。

2 礦池博弈模型與IPD

2.1 數學建模

根據1.3所描述的情況，全網中的兩個礦池A和B互相派出滲透礦工攻擊對方。為方便計算，設全網總算力為1，A礦池算力為s，B礦池算力為t，顯然s+t＜1。A礦池派出的滲透算力為a，B礦池的滲透算力為b，派出的間諜礦工將進行區塊截留攻擊，因此不貢獻任何算力。能派出的算力有限，故可設0≤a≤0.1s。全網實際算力從1降低為1-ab，故單位算力的產出速度提升到原來的倍。

同理，B池產出為：

由于0≤a≤0.1s，0≤b≤0.1t，s與t的值相差不大，故可將a、b視為小量，則a2、b2、ab趨近于0。所以等式（1）可以化簡為：

同理：

設s=0.2，t=0.2，b=0，A(a,0)的圖像如圖1所示。

圖1 礦池B選擇合作時，A礦池收益與滲透算力a的關系

這是近似線性的單調遞增函數，即A礦池攻擊越強（a↑），其收益越高（A(a,b)↑）。

將（3）與（4）相加得到A礦池與B礦池的總收益：

將a+b視作一個變量，則G(a,b)與a+b關系如圖2所示。

圖2 A、B兩礦池收益總和與滲透算力a、b之和的關系

這是近似線性的單調遞減函數，即兩者的攻擊越強（(a+b)↑）,總收益越低（G(a,b)↓）。

2.2 囚徒困境與IPD

以上所述的特征與經典的囚徒困境十分相似。即兩個共謀嫌疑犯被捕后單獨審訊，如果兩個人都不坦白罪行，則由于證據不足各判一年；如果其中一人坦白，另一人不坦白，則坦白的人因立功而立即獲釋，不坦白的人因不合作而被判十年；兩個人都坦白罪行，則證據確鑿，各判八年。由于囚徒無法信任對方，因此傾向于互相揭發，而不是同守沉默。最終導致納什均衡僅落在非合作點上的博弈模型。其收益矩陣如表1所示。

表1 經典囚徒困境收益矩陣

這與挖礦困境的相同點在于，坦白（攻擊）對個體而言是最優的選擇，而對于總體（全網）而言，每個個體都選擇坦白（攻擊）就不是最優選擇了。不同點在于，經典囚徒困境中策略集只有（坦白，沉默）兩種取值，是一個離散問題；而礦池間的博弈問題中，策略集是滲透算力（a,b），是連續的 控制量。

囚徒困境指出，如果只進行一次博弈，那么雙方都會毫無疑問地選擇背叛（在礦池博弈中，即令a=0.1s，b=0.1t）。但在實際情況中，雙方往往會進行多次，甚至海量的相互博弈，為此引入IPD（Iterated Prisoner's Dilemma，重復囚徒困境）模型。IPD中，博弈被反復地進行。因而每個參與者都有機會去“懲罰”另一個參與者前一回合的不合作行為。這時，合作可能會作為均衡的結果出現。欺騙的動機這時可能被受到懲罰的威脅所克服，從而可能導向一個較好的、合作的結果。作為反復接近無限的數量，納什均衡趨向于帕累托最優（沒有再進行帕累托優化的余地）[7]。

囚徒困境的主旨為，囚徒們雖然彼此合作，堅不吐實，可為全體帶來最佳利益，但在無法溝通的情況下，因為出賣同伙可為自己帶來利益，也因為同伙把自己招出來可為他帶來利益，因此彼此出賣雖違反最佳共同利益，反而是自己最大利益所在。但實際上，執法機構不可能設立如此情境來誘使所有囚徒招供，因為囚徒們必須考慮刑期以外之因素（出賣同伙會受到報復），而無法完全以執法者所設立之利益（刑期）作考量。

同樣的，對于兩個礦池A和B在無限次重復博弈中，博弈者可以采用的策略有無窮多種，采用什么樣的策略才可以實現相對更高的收益呢？收益較高的策略之間存在共性嗎？Axelrod實驗可以解決這個問題。

Axelrod實驗是以計算機程序對弈、競賽的方式進行的。他要求參與競賽的編程者充當囚徒困境的局中人，以謀求博弈收益的長期最大化為目標，用計算機程序編成特定的策略，每一策略按一定的規則實施合作或者背叛來對付對手。然后用單循環賽的方式將有所參賽程序兩兩對弈。[6]顯然，不同的策略對弈會有不同的得分結局，這樣就可以通過比較每個策略得分的多少來衡量其優劣。

2.3 不定值策略與定值策略

第一節最后提到的九種策略正是經典Axelrod實驗中的常見策略，在本文的礦池博弈問題中，策略集被連續化，取值并不確定，在此基礎上設計出新的策略：

P10--不定值策略：a的取值在[0,max]區間內均勻分布。

在此基礎上對不定值策略進行帕累托優化（在沒有使任何礦池收益減少的情況下，至少使一個礦池的收益增加）。單次博弈不可能保證該優化的實現，因為若a=0，b=0，根據等式（5），總收益G(a,b)已達到最大值，則礦池A,B其中一個收益增加必然會導致另一個收益減少；同理，若a、b不全為0，說明至少有一個礦池在攻擊對方，則無論是攻擊礦池還是合作礦池收益增加后必然會導致對方收益減少。所以只有盡可能地在重復博弈中實現帕累托優化。在非合作關系中（a、b不全為0），納什均衡狀態即為帕累托最優，即總收益G(a,b)不變。為了接近最優狀態，根據等式（5），a，b不全為0時，a在b不為0時取0；而在b再次為0時，設b從不為0到重新取0共經歷了n+1輪，a此時取值為m，且滿足本輪G(a,b)的n倍等于前n輪G(a,b)之和。這就是基于不定值策略的優化策略--定值策略：

P11--定值策略：第一次令a=0，若此后b一直取0，則a繼續取0，若某一輪b＞0,則a繼續取0,設本輪b取值為b1，下一輪若b＞0則a繼續取0，b取值為b2，依此類推。在b＞0之后的第n+1輪b再次為0，此時設a取值為m，且m滿足：

該策略理論上可以使兩礦池接近納什均衡，具體表現還要通過數值仿真來驗證。

3 數值仿真

3.1 兩兩博弈的仿真結果

本文一共提出了11種不同的策略（經典策略9種，新設計策略2種），兩兩匹配，共有55次不同的博弈（每次模擬100輪），這里僅選取其中一些具有代表性的結果進行展示和分析。

計算可知，每輪博弈中，一方的最低收益為0.183 7，最高收益為0.204 1，差距僅10%左右，直接將收益作為縱軸作圖，近似為線性，很不直觀。為解決這個問題，可將每輪的收益減去0.183 7，稱為“額外收益”，并以此為縱軸作圖，使得結果較為直觀。

部分結果如圖3、圖4、圖5、圖6所示。

圖3表明，ALLC策略平均收益低于離散型隨機取值策略。

圖4、圖5表明，當定值策略、ALLC、TFT、Grim、WSFS等友善型策略兩兩互相博弈時，會進行持續合作從而獲得不錯的收益（約1.6）。

圖3 P1與P6的競爭結果

圖4 P1與P11的競爭結果

圖5 P3與P4的競爭結果

圖6 P10與P11的競爭結果

圖6 表明，定值策略會根據對手策略做出相應的調整，導致不管和誰博弈，其收益都接近，除了ALLD。定值策略和ALLD的博弈與ALLC和ALLD的博弈是一樣的。

3.2 總體表現的仿真結果

單看兩兩博弈的結果很難分析每一個策略的優劣，為此，我們統計了每個策略與其它所有策略進行博弈時的平均收益，并從高到低進行排序，結果如圖7所示。

圖7表明，表現最好的是定值策略，WSFS僅次于定值策略。表現最差的是TFT_D、Grim_D。

圖7 11種策略的總體表現排名

3.3 仿真結果分析

對上述仿真結果進行分析，歸納出該博弈模型的以下特點：

（1）ALLD策略在每一次博弈中都不吃虧，但在總體上卻是一種很差的策略；

（2）一般而言，“善意”的策略表現要優于“貪心”的策略；

（3）第一次的選擇非常重要，對整個策略的表現影響很大。

傳統IPD中，TFT策略和Grim策略表現最佳。而在該區塊鏈博弈模型中，定值策略和WSFS策略表現最好，且定值策略較傳統的WSFS更勝一籌。

4 總結與展望

礦池間的相互攻擊是區塊鏈中的常見現象，但此前的研究工作大多集中在單個礦池內礦工間的相互博弈。在本文中，我們首次對該問題進行了研究。

在研究方法上，我們選用了數學建模和數值仿真的方法，參考了經典的囚徒困境模型和IPD模型，但根據該問題的特點自行建立了具有連續性的收益矩陣，并根據該矩陣設計了兩種新的策略——不定值策略、定值策略，并編寫代碼進行仿真。

在仿真中，我們比較了11種不同的策略，結果也與傳統IPD模型有較大差異。根據結果，我們建議礦池的管理者采取定值策略或WSFS策略。

在礦池的博弈模型中一定存在更為優秀的策略等待我們去發掘，也有很多問題擺在我們面前。是否可以引入某些遺傳算法，令目前設計的策略進行組合、突變或演化呢？超過兩個礦池的多礦池博弈模型中，各種策略及其效果又會如何呢？后續工作將對這些情況進行研究和分析。