楊 天，薛 質(zhì)

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

0 引 言

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

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

1 背景知識

1.1 礦池概念

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

1.2 區(qū)塊截留攻擊

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

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

1.3 初步建模及策略

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

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

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

P2--ALLD：All Defect，永遠(yuǎn)背叛策略，無論對手采取何種策略，都選擇背叛，即令滲透算力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，區(qū)別在于第一次選擇背叛(即a=max)。

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

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

2 礦池博弈模型與IPD

2.1 數(shù)學(xué)建模

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

同理，B池產(chǎn)出為：

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

同理：

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

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

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

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

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

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

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

2.2 囚徒困境與IPD

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

表1 經(jīng)典囚徒困境收益矩陣

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

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

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

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

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

2.3 不定值策略與定值策略

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

P10--不定值策略：a的取值在[0,max]區(qū)間內(nèi)均勻分布。

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

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

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

3 數(shù)值仿真

3.1 兩兩博弈的仿真結(jié)果

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

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

部分結(jié)果如圖3、圖4、圖5、圖6所示。

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

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

圖3 P1與P6的競爭結(jié)果

圖4 P1與P11的競爭結(jié)果

圖5 P3與P4的競爭結(jié)果

圖6 P10與P11的競爭結(jié)果

圖6 表明，定值策略會根據(jù)對手策略做出相應(yīng)的調(diào)整，導(dǎo)致不管和誰博弈，其收益都接近，除了ALLD。定值策略和ALLD的博弈與ALLC和ALLD的博弈是一樣的。

3.2 總體表現(xiàn)的仿真結(jié)果

單看兩兩博弈的結(jié)果很難分析每一個策略的優(yōu)劣，為此，我們統(tǒng)計了每個策略與其它所有策略進(jìn)行博弈時的平均收益，并從高到低進(jìn)行排序，結(jié)果如圖7所示。

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

圖7 11種策略的總體表現(xiàn)排名

3.3 仿真結(jié)果分析

對上述仿真結(jié)果進(jìn)行分析，歸納出該博弈模型的以下特點：

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

（2）一般而言，“善意”的策略表現(xiàn)要優(yōu)于“貪心”的策略；

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

傳統(tǒng)IPD中，TFT策略和Grim策略表現(xiàn)最佳。而在該區(qū)塊鏈博弈模型中，定值策略和WSFS策略表現(xiàn)最好，且定值策略較傳統(tǒng)的WSFS更勝一籌。

4 總結(jié)與展望

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

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

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

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