區(qū)塊鏈系統(tǒng)中礦池間的博弈問題及優(yōu)化*

楊 天，薛 質(zhì)

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

0 引 言

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

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

1 背景知識(shí)

1.1 礦池概念

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

1.2 區(qū)塊截留攻擊

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

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

1.3 初步建模及策略

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

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

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

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

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

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

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

P6--Random：離散型隨機(jī)取值策略，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)中的兩個(gè)礦池A和B互相派出滲透礦工攻擊對(duì)方。為方便計(jì)算，設(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)實(shí)際算力從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）可以化簡(jiǎn)為：

同理：

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

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

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

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

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

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

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

2.2 囚徒困境與IPD

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

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

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

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

囚徒困境的主旨為，囚徒們雖然彼此合作，堅(jiān)不吐實(shí)，可為全體帶來最佳利益，但在無法溝通的情況下，因?yàn)槌鲑u同伙可為自己帶來利益，也因?yàn)橥锇炎约赫谐鰜砜蔀樗麕砝?，因此彼此出賣雖違反最佳共同利益，反而是自己最大利益所在。但實(shí)際上，執(zhí)法機(jī)構(gòu)不可能設(shè)立如此情境來誘使所有囚徒招供，因?yàn)榍敉絺儽仨毧紤]刑期以外之因素（出賣同伙會(huì)受到報(bào)復(fù)），而無法完全以執(zhí)法者所設(shè)立之利益（刑期）作考量。

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

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

2.3 不定值策略與定值策略

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

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

在此基礎(chǔ)上對(duì)不定值策略進(jìn)行帕累托優(yōu)化（在沒有使任何礦池收益減少的情況下，至少使一個(gè)礦池的收益增加）。單次博弈不可能保證該優(yōu)化的實(shí)現(xiàn)，因?yàn)槿鬭=0，b=0，根據(jù)等式（5），總收益G(a,b)已達(dá)到最大值，則礦池A,B其中一個(gè)收益增加必然會(huì)導(dǎo)致另一個(gè)收益減少；同理，若a、b不全為0，說明至少有一個(gè)礦池在攻擊對(duì)方，則無論是攻擊礦池還是合作礦池收益增加后必然會(huì)導(dǎo)致對(duì)方收益減少。所以只有盡可能地在重復(fù)博弈中實(shí)現(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時(shí)，a在b不為0時(shí)取0；而在b再次為0時(shí)，設(shè)b從不為0到重新取0共經(jīng)歷了n+1輪，a此時(shí)取值為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í)設(shè)a取值為m，且m滿足：

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

3 數(shù)值仿真

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

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

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

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

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

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

圖3 P1與P6的競(jìng)爭(zhēng)結(jié)果

圖4 P1與P11的競(jìng)爭(zhēng)結(jié)果

圖5 P3與P4的競(jìng)爭(zhēng)結(jié)果

圖6 P10與P11的競(jìng)爭(zhēng)結(jié)果

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

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

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

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

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

3.3 仿真結(jié)果分析

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

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

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

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

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

4 總結(jié)與展望

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

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

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

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