基于自適應(yīng)零行列式策略的區(qū)塊鏈礦池合作演化方法

范麗 鄭紅 黃建華 李忠誠 江亞慧

摘 要：礦工加入礦池是目前比特幣挖礦最常見的方式。然而，比特幣系統(tǒng)中存在礦池互相滲透攻擊的現(xiàn)象，這將導(dǎo)致被攻擊礦池的礦工收益減少，發(fā)起攻擊的礦池算力降低，從而造成比特幣系統(tǒng)的整體算力減小。針對礦池之間互相攻擊，不合作挖礦的問題，提出自適應(yīng)零行列式策略（AZD），采取“比較預(yù)期合作收益與背叛收益，選擇促進(jìn)高收益的策略”的思想促進(jìn)礦池合作。首先，通過結(jié)合時(shí)序差分增強(qiáng)算法與零行列式策略的方法預(yù)測下一輪合作收益與背叛收益;其次，通過決策過程（DMP）選擇策略進(jìn)一步改變下一輪的合作概率和背叛概率;最后，通過迭代執(zhí)行自適應(yīng)零行列式策略，達(dá)到網(wǎng)絡(luò)中礦池均互相合作、積極挖礦的目的。實(shí)驗(yàn)?zāi)M表明，AZD策略與自適應(yīng)策略相比，合作概率收斂為1的速度提高了36.54%;與零行列式策略相比，穩(wěn)定度提高了50%。這個結(jié)果表明AZD策略能夠有效促進(jìn)礦工合作，提高合作收斂速率，保證礦池的穩(wěn)定收益。

關(guān)鍵詞：比特幣;時(shí)序差分增強(qiáng)算法;自適應(yīng)策略方法;零行列式策略;決策過程

中圖分類號： TP399

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-9081（2019）03-0918-06

Abstract： At present， the most common way for bitcoin mining is miners joining in a pool. However， there is a phenomenon that the mining pools penetrate each other， which will result in a decrease in the miners'?income of the attacked pools， and a reduction in computing power of the attacking pools. Therefore， the overall computing power of the bitcoin system is reduced. Aiming at the problem of mutual attack and non-cooperative mining between mining pools， an Adaptive Zero-Determinant strategy （AZD） was proposed to promote the cooperation of miners. The strategy adopted the idea of comparing expected payoff with cooperation and defection in the next round then choosing a strategy with high payoff. Firstly， miners'?payoff in the next round under two situations could be predicted by the combination of Temporal Difference Learning Method （TD（λ）） and Zero-Determinant strategy （ZD）. Secondly， by comparing the cooperation payoff with defection payoff in the next round， a more favorable strategy was chosen for miners by ?Decision Making Process （DMP）， so the cooperation probability and defection probability in the next round were changed correspondingly. Finally， through the iterative implementation of AZD strategy， the ming pools in the network would cooperate with each other and mine actively. Simulation results show that compared with adaptive strategy， AZD strategy increases the speed of converging cooperation probability to 1 by 36.54%， compared with ZD strategy， it improves the stability by 50%. This result indicates that AZD strategy can effectively promote the cooperation of miners， improve the convergence rate of cooperation and ensure the stable income of mining pools.

Key words： bitcoin; temporal difference learning method; adaptive strategy; zero-determinant strategy; Decision Making Process （DMP）

0 引言

區(qū)塊鏈[1-3]是一種分布式的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，網(wǎng)絡(luò)中每個節(jié)點(diǎn)上保存一個完整的副本，并通過共識算法將全網(wǎng)信息統(tǒng)一。比特幣是[4-5]區(qū)塊鏈一個成熟的應(yīng)用，工作量證明算法（Proof-of-Work， PoW）[6]是比特幣采用的共識機(jī)制，它保證了區(qū)塊鏈的數(shù)據(jù)一致性和交易的難以篡改。在比特幣中，節(jié)點(diǎn)收集交易并消耗算力爭奪記賬權(quán)來獲取收益，這一過程叫作挖礦[7-9]。隨著比特幣的流行與價(jià)值增長，越來越多的節(jié)點(diǎn)加入網(wǎng)絡(luò)成為礦工，網(wǎng)絡(luò)算力的增加導(dǎo)致挖礦難度迅速上升[10]，單個節(jié)點(diǎn)成功挖礦的概率極低。為了獲得穩(wěn)定的收益，礦工自發(fā)聚集，形成礦池[11]，礦池成員互相合作，分享自己的工作量證明，并按照貢獻(xiàn)分得獎勵。

礦池中的礦工通過挖礦獲取收益，可能存在不合作挖礦只分享收益的礦工節(jié)點(diǎn)。由于大部分礦池是開放的，允許任何人加入，其他礦池的忠誠節(jié)點(diǎn)會滲透到本礦池，從而對本礦池發(fā)起區(qū)塊扣留攻擊（block withholding attack）[12-13]，即從不進(jìn)行工作量證明，或只向礦池管理員發(fā)送部分工作量證明，當(dāng)產(chǎn)生完整的工作量證明就將其拋棄。區(qū)塊扣留攻擊不會為礦池提供有效收益，卻共享礦池收益，導(dǎo)致被攻擊礦池的收益減少，同時(shí)也使得發(fā)起攻擊的礦池算力減少。

在比特幣礦池的場景下，礦池也面臨著相似的困境。若沒有礦池選擇攻擊，均公平挖礦，所有礦池將獲得贏得收益;若一個礦池選擇攻擊，它會因此獲得高收益，并導(dǎo)致被攻擊礦池收益降低;若兩個礦池都選擇攻擊，在雙方的滲透率達(dá)到納什均衡[14]時(shí)，每個礦池的收益都將低于雙方均不攻擊的收益。為了獲得高收益，在礦池的理性思考下，礦池均選擇滲透攻擊，即陷入PoW共識算法中的礦工困境[15]，類似于博弈論中的囚徒困境（Prisoner's Dilemma）[16-17]。同時(shí)，（攻擊，攻擊）是礦工困境唯一的納什均衡[18-19]。在本文中，礦池積極挖礦，礦池之間互不攻擊稱為合作策略，礦池選擇攻擊稱為背叛策略，即礦工困境的納什均衡是（背叛，背叛）。礦池選擇背叛策略導(dǎo)致礦池算力減小，交易處理速率降低，區(qū)塊吞吐量減小，系統(tǒng)收益減少。目前，中國地區(qū)的礦池算力占比特幣網(wǎng)絡(luò)算力的81%，加入礦池是礦工挖礦最重要的方式，礦工困境是亟待解決的問題。

為了促進(jìn)礦池互相合作，提高區(qū)塊吞吐量，增加礦池整體收益與礦工收益，本文采用自適應(yīng)零行列式（Adaptive Zero-Determinant， AZD）策略（Adaptive Zero-Determinant strategy， AZD）（簡稱AZD策略，采用AZD策略的礦池稱為AZD礦池）對PoW共識算法進(jìn)行改進(jìn)。通過采用“預(yù)測下一輪合作與背叛收益，采取使得收益高的策略”的思想，基于決策過程（Decision Making Process， DMP）作出決策，同時(shí)相應(yīng)改變下一輪的合作概率，迭代執(zhí)行自適應(yīng)零行列式策略，直到達(dá)到網(wǎng)絡(luò)中礦池均合作的狀態(tài)，最終實(shí)現(xiàn)合作共贏。

1 相關(guān)工作

1.1 比特幣挖礦

隨著比特幣價(jià)值的增加和礦工對穩(wěn)定收入的追求，礦工通常自發(fā)聚集，形成礦池。如圖1所示，Pool 1和Pool 2是比特幣系統(tǒng)中的兩個礦池，礦池中的礦工互相合作，分享工作量證明，并按照貢獻(xiàn)分得獎勵。比特幣系統(tǒng)中存在礦池合作挖礦與礦工單獨(dú)挖礦兩種挖礦策略。

一般說來，礦池的總算力與礦工數(shù)量成正比，因此，礦池挖礦的預(yù)期收益遠(yuǎn)大于單獨(dú)挖礦的收益，這為礦工帶來穩(wěn)定的收入。礦池的挖礦機(jī)制為：礦池包含一個集中控制的管理員。管理員生成任務(wù)并發(fā)給礦工，礦工執(zhí)行工作量證明算法，并向管理員發(fā)送自己的全部工作量證明，由管理員生成一個新的區(qū)塊，并且將礦池的收益按貢獻(xiàn)分配給成員。然而，礦工積極挖礦，以恒定速度產(chǎn)生一個新區(qū)塊的情況是理想化的。

1.2 比特幣中的攻擊方式

Eyal[15]指出比特幣系統(tǒng)中存在礦工滲透到其他礦池的惡意行為，例如：礦工A是礦池X的礦工，卻加入到礦池Y，礦工A從不進(jìn)行工作量證明，或只向礦池管理員發(fā)送部分工作量證明，當(dāng)產(chǎn)生完整的工作量證明就將其拋棄，即礦池X向礦池Y發(fā)起區(qū)塊扣留攻擊。因此兩個礦池挖礦存在3種情況：

1）兩個礦池互不攻擊，均合作挖礦，此時(shí)礦池的收益均是應(yīng)得的。

2）一個礦池發(fā)起區(qū)塊扣留攻擊，另一礦池選擇合作。假設(shè)礦池X滲透到礦池Y的節(jié)點(diǎn)算力為MX，Y， 網(wǎng)絡(luò)總算力為M， 礦池X的總算力為MX，礦池Y的總算力為MY， 則礦池X和Y的總算力占網(wǎng)絡(luò)總算力的百分比分別是：

將式（3）代入式（4），能夠由系數(shù)得出rX>rY，因此，當(dāng)對手選擇合作，理性礦池選擇背叛能夠獲取更高的收益。

3）兩個礦池均互相攻擊。當(dāng)對手選擇背叛，理性礦池選擇背叛才能盡可能減少損失，因此導(dǎo)致兩個礦池均選擇攻擊策略，這種情況導(dǎo)致雙方的收益均低于互不攻擊的收益，同時(shí)降低網(wǎng)絡(luò)算力，降低區(qū)塊吞吐量。

這種理性思考使得區(qū)塊鏈礦池陷入比特幣礦工困境中，雙方都選擇攻擊是礦工困境的納什均衡，這將導(dǎo)致交易處理速率大大降低，區(qū)塊吞吐量減小，系統(tǒng)收益減少。

1.3 囚徒困境中的典型策略

研究發(fā)現(xiàn)，節(jié)點(diǎn)每輪更新自己的合作伙伴將導(dǎo)致合作概率顯著增加[20]，然而，參與者僅能夠隨機(jī)選擇建立或斷開聯(lián)系的節(jié)點(diǎn)，不允許有選擇地選擇合作伙伴，同時(shí)參與者無法拒絕其他節(jié)點(diǎn)創(chuàng)建的新連接。文獻(xiàn)[21]的工作改進(jìn)克服了節(jié)點(diǎn)不能選擇合作伙伴的不足，允許節(jié)點(diǎn)有選擇地決定合作伙伴。建立新的聯(lián)系和切斷現(xiàn)有聯(lián)系的方式導(dǎo)致參與者互相協(xié)調(diào)，大大增加合作可能性。

文獻(xiàn)[22]總結(jié)了囚徒困境中參與者采取的傳統(tǒng)策略，包括一直合作（ALways Cooperate， ALLC）、一直背叛（ALways Defect， ALLD）、針鋒相對（Tit-For Tat， TFT）和贏留輸改（Win-Stay Lose-Shift， WSLS），通過分析傳統(tǒng)策略的特點(diǎn)，利用規(guī)則圖形象描述了在不同空間結(jié)構(gòu)中傳統(tǒng)策略的合作進(jìn)化。文獻(xiàn)[23]介紹了一種用在囚徒困境中的自適應(yīng)策略，在無標(biāo)度網(wǎng)絡(luò)中，博弈雙方通過增強(qiáng)學(xué)習(xí)方法不斷改進(jìn)自己的策略，最終實(shí)現(xiàn)合作共贏。然而，采用自適應(yīng)方法達(dá)到合作概率為1所需輪數(shù)較長，不能滿足比特幣中交易量大、交易處理速度快的現(xiàn)狀。Press和Dyson提出了零行列式策略[24]，通過單方面設(shè)置對手的期望收益，從而獲得比對手高的敲詐收益。然而，零行列式策略可以提高礦工個體收益，卻不能提高礦工合作概率。

2 自適應(yīng)零行列式策略

本文提出自適應(yīng)零行列式策略，采用“預(yù)測下一輪合作/背叛收益，選擇取得高收益策略”的思想，結(jié)合時(shí)序差分增強(qiáng)學(xué)習(xí)方法（Temporal Difference Learning Method， TD（λ））[25]和零行列式策略（Zero-Determinant strategy，ZD）預(yù)測下一輪收益，通過DMP選擇策略，并改變下一輪的合作和背叛概率。通過迭代執(zhí)行自適應(yīng)零行列式策略，促進(jìn)礦池相互合作，同時(shí)取得比對手高的收益，達(dá)到提高區(qū)塊吞吐量、增加系統(tǒng)整體收益的目的。

設(shè)TD（λ）為時(shí)序差分學(xué)習(xí)方法，ZD為零行列式策略，DMP為策略選擇并改變下一輪合作概率的過程。礦池上一次選擇策略之后，到下一次作出選擇的過程稱為一輪，用t表示輪次，t = 1，2，…， N。圖2描述的是第t輪中，AZD策略預(yù)測第t+1輪收益的整體架構(gòu)。

表1描述了礦池不同策略下的收益。表中：C代表礦池選擇合作策略，D代表礦池選擇背叛策略。當(dāng)兩個礦池均選擇合作時(shí)，雙方的收益均為R;當(dāng)兩個礦池均選擇背叛時(shí)，雙方的收益均為P;當(dāng)一個礦池選擇合作，另一個礦池選擇背叛時(shí)，合作礦池的收益為S，背叛礦池的收益為T，其中T>R>P>S，且2R>T+S。

3 實(shí)驗(yàn)?zāi)M與仿真結(jié)果

為了測試自適應(yīng)零行列式策略的有效性，實(shí)驗(yàn)?zāi)M了無標(biāo)度網(wǎng)絡(luò)環(huán)境下，AZD礦池與普通礦池的合作演變情況。同時(shí)設(shè)計(jì)對照實(shí)驗(yàn)，分別設(shè)置AZD礦池的初始化合作概率為0.1，0.3，0.5，0.7，0.9，以測試不同初始化合作概率條件下，最終合作概率收斂為1時(shí)所需的迭代輪數(shù)。本文假設(shè)礦池之間進(jìn)行20輪博弈，首先預(yù)測AZD礦池每一輪迭代后的合作收益與背叛收益值;其次，對AZD策略與自適應(yīng)策略作出對比，并比較AZD策略與自適應(yīng)策略合作概率收斂到1所需輪數(shù);最后，對AZD策略與零行列式策略作出對比，在相同的對手收益下，比較兩種策略的收益。

圖3反映了在不同的初始化合作概率條件下，每一輪決策后的合作概率變化情況。如圖所示，采用AZD策略的礦池的合作概率隨迭代輪數(shù)的增加呈現(xiàn)整體上升趨勢，同時(shí)，由于每一輪合作概率增加是漸變的過程，初始合作概率（P）越小，概率收斂為1所需輪數(shù)越多;反之，初始合作概率越大，概率收斂為1所需輪數(shù)就越少。

AZD礦池與采用自適應(yīng)策略礦池的合作概率收斂所需輪數(shù)如圖4所示。不管初始合作概率設(shè)置為多少，本文提出的基于AZD策略的算法最終合作概率收斂為1所需輪數(shù)均比自適應(yīng)策略少1～3輪，比自適應(yīng)策略有更好的表現(xiàn)。

礦池收益隨輪數(shù)變化的情況如圖5所示，AZD礦池合作的收益較礦池背叛的收益有明顯的優(yōu)勢，從而吸引礦池執(zhí)行合作策略。當(dāng)合作概率較小時(shí)，由式（15）可知，自適應(yīng)策略得到的Tcp （t+1）較小，由于AZD礦池采用動態(tài)敲詐因子χ=10/PC，由式（14）可知，零行列式策略得到的敲詐收益較大，由于零行列式策略在促進(jìn)收益方面具有優(yōu)勢，由式（17）可知，合作收益Scp （t+1）較大;隨著對DMP過程的執(zhí)行，合作概率增加，自適應(yīng)策略得到的Tcp （t+1）略微增大，零行列式策略得到的敲詐收益卻明顯減小，因此合作收益Scp （t+1）變小，從而驗(yàn)證圖5最初收益上下波動的現(xiàn)象。當(dāng)合作概率收斂為1后，礦池的收益穩(wěn)定維持在較高水平。同時(shí)，由于合作概率收斂到1 后，敲詐因子穩(wěn)定為10，由計(jì)算下一輪收益的公式得出：與不采用AZD策略的礦池收益相比，AZD礦池的平均收益提高了400%，圖5也驗(yàn)證了此結(jié)果。

圖6模擬在相同的對手收益下，AZD礦池與采用零行列式策略的礦池收益隨輪數(shù)的變化情況。在決策前5輪，由于網(wǎng)絡(luò)中存在合作概率較小的礦池，AZD礦池將獲得較高敲詐型收益以保證自己的收入，因此圖中顯示本文采用的策略收益較高;5輪決策之后，網(wǎng)絡(luò)中礦池合作概率均收斂為1，AZD策略不再以獲取高收益為目的，而是傾向于保持合作，使收益保持在一個穩(wěn)定水平。

4 結(jié)語

本文分析了比特幣工作量證明機(jī)制中存在的囚徒困境問題，并借鑒博弈論中自適應(yīng)方法與零行列式策略的思想優(yōu)化了PoW共識機(jī)制，設(shè)計(jì)了自適應(yīng)零行列式策略，采取“比較預(yù)期收益，選擇收益大的策略”的思想，采用自適應(yīng)與零行列式策略相結(jié)合的方法預(yù)測下一輪收益，通過DMP選擇策略進(jìn)一步改變下一輪的合作和背叛概率。迭代執(zhí)行自適應(yīng)零行列式策略，能夠快速將合作概率收斂為1，即網(wǎng)絡(luò)中礦池均采用合作策略，積極挖礦，獲得高而穩(wěn)定的收益。模擬實(shí)驗(yàn)驗(yàn)證了自適應(yīng)零行列式策略的有效性，能夠在較小的輪數(shù)內(nèi)將合作概率收斂為1，同時(shí)獲得比對手更高的收益。

參考文獻(xiàn) （References）

[1] GIUNGATO P， RANA R， TARABELLA A， et al. Current trends in sustainability of bitcoins and related blockchain technology [J]. Sustainability， 2017， 9（12）： 1-11.

[2] 喻輝，張宗洋，劉建偉.比特幣區(qū)塊鏈擴(kuò)容技術(shù)研究[J].計(jì)算機(jī)研究與發(fā)展，2017，54（10）：2390-2403.（YU H， ZHANG Z Y， LIU J W. Research on scaling technology of bitcoin blockchain [J]. Journal of Computer Research and Development， 2017， 54（10）： 2390-2403.）

[3] 王繼業(yè)，高靈超，董愛強(qiáng)，等.基于區(qū)塊鏈的數(shù)據(jù)安全共享網(wǎng)絡(luò)體系研究[J].計(jì)算機(jī)研究與發(fā)展，2017，54（4）：742-749.（WANG J Y， GAO L C， DONG A Q， et al. Block chain based data security sharing network architecture research [J]. Journal of Computer Research and Development， 2017， 54（4）：742-749.）

[4] NAKAMOTO S. Bitcoin： a peer-to-peer electronic cash system [EB/OL]. （2008） [2018-05-03]. http：//bitcoin.org/bitcoin.pdf.

[5] DELGADO-SEGURA S， TANAS C， HERRERA-JOANCOMART J. Reputation and reward： two sides of the same bitcoin [J]. Sensors， 2016， 16（6）： 776.

[6] GARDNER-STEPHEN P. Escalating the war on SPAM through practical PoW exchange [C]// Proceedings of the 2007 15th IEEE International Conference on Networks. Piscataway， NJ： IEEE， 2007： 473-476.

[7] GOBEL J， KRZESINSKI A E. Increased block size and bitcoin blockchain dynamics [C]// Proceedings of the 2017 27th International Telecommunication Networks and Applications Conference. Piscataway， NJ： IEEE， 2017：1-6.

[8] COURTOIS N T， EMIRDAG P， WANG Z. On detection of bitcoin mining redirection attacks [C]// Proceedings of the 2015 International Conference on Information Systems Security and Privacy. Piscataway， NJ： IEEE， 2015： 98-105.

[9] VILIM M， DUWE H， KUMAR R. Approximate bitcoin mining [C]// Proceedings of the 53rd Annual Design Automation Conference. New York： ACM， 2016： Article No. 97.

[10] KRAFT D. Difficulty control for blockchain-based consensus systems [J]. Peer-to-Peer Networking and Applications， 2016， 9（2）： 397-413.

[11] LIU Y， CHEN X Y， ZHANG L， et al. An intelligent strategy to gain profit for bitcoin mining pools [C]// Proceedings of the 10th International Symposium on Computational Intelligence and Design. Piscataway， NJ： IEEE， 2017： 427-430.

[12] BAG S， RUJ S， SAKURAI K. Bitcoin block withholding attack： analysis and mitigation [J]. IEEE Transactions on Information Forensics and Security， 2017， 12（8）： 1967-1978.

[13] GBEL J， KRZESINSKI A E， KEELER H P， et al. Bitcoin blockchain dynamics： the selfish-mine strategy in the presence of propagation delay [J]. Performance Evaluation， 2016， 104： 23-41.

[14] LI J， KENDALL G， JOHN R. Computing Nash equilibria and evolutionarily stable states of evolutionary games [J]. IEEE Transactions on Evolutionary Computation， 2016， 20（3）： 460-469.

[15] EYAL I. The miner's dilemma [C]// Proceedings of the 2015 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2015： 89-103.

[16] KENTER F， MEIGS E. Iterated prisoner's dilemma with extortionate zero-determinant strategies and random-memory opponents [C]// Proceedings of the 2016 IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2016： 3499-3506.

[17] KOSTYUK N. The digital prisoner's dilemma： challenges and opportunities for cooperation [C]// Proceedings of the 2013 World Cyberspace Cooperation Summit Ⅳ. Piscataway， NJ： IEEE， 2015： 1-6.

KOSTYUK N. The digital prisoner's dilemma： challenges and opportunities for cooperation [EB/OL]. [2018-07-11]. http：//cybersummit.info/sites/cybersummit.info/files/The%20Digital%20Prisoner's%20Dilemma-Challenges%20and%20Opportunities%20for%20Cooperation_Nadiya%20Kostyuk%20.pdf.

[18] CARBONELL-NICOLAU O， McLEAN R P. On the existence of Nash equilibrium in Bayesian games [J]. GeomorphologyMathematics of Operations Research， 2017， 60（S1/2）：73-87.

[19] BARLOW L A. The impact of Agent size and number of rounds on cooperation in the iterated prisoner's dilemma [C]// Proceedings of 2014 IEEE Symposium on Foundations of Computational Intelligence. Piscataway， NJ： IEEE， 2014： 120-127.

[20] FEHL K， van der POST D J， SEMMANN D. Co-evolution of behaviour and social network structure promotes human cooperation [J]. Ecology Letters， 2011， 14（6）： 546-551.

[21] WANG J， SURI S， WATTS D J. Cooperation and assortativity with dynamic partner updating [J]. Proceedings of the National Academy of Sciences of the United States of America， 2012， 109（36）： 14363-14368.

[22] 李勇.重復(fù)囚徒困境模型中零行列式策略的研究[D].蘇州：蘇州大學(xué)，2015：1-50.（LI Y. Study on zero-determinant strategies in Iterated prisoner's dilemma game [D]. Suzhou： Soochow University， 2015： 1-50.）

[23] XUE L， SUN C Y， WUNSCH D， et al. An adaptive strategy via reinforcement learning for the prisoner's dilemma game [J]. IEEE/CAA Journal of Automatica Sinica， 2018， 5（1）： 1-10.

[24] PRESS W H， DYSON F J. Iterated prisoner's dilemma contains strategies that dominate any evolutionary opponent [J]. Proceedings of the National Academy of Sciences of the United States of America， 2012， 109（26）： 10409-10413.

[25] BABA N， TAKAGAWARA Y. Application of temporal difference learning method to computer gaming [C]// Proceedings of the 1998 2nd International Conference on Knowledge-based Intelligent Electronic Systems. Piscataway， NJ： IEEE， 1998： 36-39.