基于自適應零行列式策略的區塊鏈礦池合作演化方法

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

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

關鍵詞：比特幣;時序差分增強算法;自適應策略方法;零行列式策略;決策過程

中圖分類號： TP399

文獻標志碼：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 引言

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

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

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

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

1 相關工作

1.1 比特幣挖礦

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

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

1.2 比特幣中的攻擊方式

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

1）兩個礦池互不攻擊，均合作挖礦，此時礦池的收益均是應得的。

2）一個礦池發起區塊扣留攻擊，另一礦池選擇合作。假設礦池X滲透到礦池Y的節點算力為MX，Y， 網絡總算力為M， 礦池X的總算力為MX，礦池Y的總算力為MY， 則礦池X和Y的總算力占網絡總算力的百分比分別是：

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

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

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

1.3 囚徒困境中的典型策略

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

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

2 自適應零行列式策略

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

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

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

3 實驗模擬與仿真結果

為了測試自適應零行列式策略的有效性，實驗模擬了無標度網絡環境下，AZD礦池與普通礦池的合作演變情況。同時設計對照實驗，分別設置AZD礦池的初始化合作概率為0.1，0.3，0.5，0.7，0.9，以測試不同初始化合作概率條件下，最終合作概率收斂為1時所需的迭代輪數。本文假設礦池之間進行20輪博弈，首先預測AZD礦池每一輪迭代后的合作收益與背叛收益值;其次，對AZD策略與自適應策略作出對比，并比較AZD策略與自適應策略合作概率收斂到1所需輪數;最后，對AZD策略與零行列式策略作出對比，在相同的對手收益下，比較兩種策略的收益。

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

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

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

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

4 結語

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

參考文獻 （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] 喻輝，張宗洋，劉建偉.比特幣區塊鏈擴容技術研究[J].計算機研究與發展，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] 王繼業，高靈超，董愛強，等.基于區塊鏈的數據安全共享網絡體系研究[J].計算機研究與發展，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] 李勇.重復囚徒困境模型中零行列式策略的研究[D].蘇州：蘇州大學，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.