-
摘要: 区块链是随着比特币等数字加密货币逐渐兴起而盛行的一种新型去中心化分布式系统，具有去中心化、时序数据、集体维护、可编程和安全可信等特点.目前，区块链已引起政府部门、金融机构、科技企业和资本市场的高度重视与广泛关注.如何在一个去中心化的分布式系统中高效地达成共识是区块链技术研究的重要问题.本文从工作量证明（Proof of work，PoW）共识算法的挖矿困境入手，分析PoW共识过程中矿工策略选择的纳什均衡存在条件.利用零行列式（Zero determinant，ZD）策略对矿工策略选择进行优化，并通过数值仿真来验证优化算法的有效性.概括来说，本文从博弈论角度来理解和剖析PoW共识算法，为进一步设计基于博弈论的共识算法提供新的思路和方法.Abstract: Blockchain is a new decentralized distributed system with the prevalence of Bitcoin and other cryptocurrencies, whose characteristics include decentralization, time-series data, collective maintenance, programmability, security, and so on. Currently, blockchain has attracted intensive attention from governments, financial institutions, high-tech enterprises, and capital markets. Under the framework of this decentralized distributed system, one of the key research issues is how to reach a consensus effectively. In this paper, we analyze the Nash equilibria existence of the miner's strategy choice in the process of proof of work (PoW) consensus algorithm. Besides, we apply the zero determinant (ZD) strategy to optimize the strategy choosing of the miner, and verify the effectiveness of the optimization algorithm through numerical simulation. In brief, this work contributes understanding and analyzeing the PoW consensus algorithm, and provides a new idea and method for the design of consensus algorithm based on the game theory.1) 本文责任编委 袁勇
-
图 1 矿工纯策略纳什均衡分布图
Fig. 1 The distribution of pure strategies Nash equilibrium for miners
图 3 当矿工算力相同时, LM采用不同策略, SM始终采用WSFS策略后, 系统收益分布情况
Fig. 3 The distribution of systematic revenue, when LM takes different strategies and SM all uses WSFS strategy in the condition of same power
图 4 当矿工算力相同时, LM采用不同策略, SM始终采用TFT策略后, 系统收益分布情况
Fig. 4 The distribution of systematic revenue, when LM takes different strategies and SM all uses TFT strategy in the condition of same power
图 5 当矿工算力相同时, LM采用不同策略, SM始终采用$[0.1, 0.2, 0.3, 0.4]$策略后, 系统收益分布情况
Fig. 5 The distribution of systematic revenue, when LM takes different strategies and SM all uses $[0.1, 0.2, 0.3, 0.4]$ strategy in the condition of same power
图 6 当矿工算力相同时, LM采用ZD策略, SM采用不同的三种策略, LM和SM收益的线性关系
Fig. 6 The linear relationship between LM$'$ payoff and SM$'$ payoff, when LM takes a ZD strategies and SM uses three different strategy in the condition of same power
图 7 当矿工算力不相同时, SM采用WSFS策略, LM采用不同的四种策略, 系统收益情况
Fig. 7 The distribution of systematic revenue, when SM all uses WSFS strategy and LM takes different four strategies and in the condition of different power
图 8 当矿工算力不相同时, SM采用TFT策略, LM采用不同的四种策略, 系统收益情况
Fig. 8 The distribution of systematic revenue, when SM all uses TFT strategy and LM takes different four strategies and in the condition of different power
图 9 当矿工算力不相同时, SM采用$[0.1, 0.2, 0.3, 0.4]$策略, LM采用不同的四种策略, 系统收益情况
Fig. 9 The distribution of systematic revenue, when SM all uses $[0.1, 0.2, 0.3, 0.4]$ strategy and LM takes different four strategies and in the condition of different power
-
[1] 袁勇, 王飞跃.区块链技术发展现状与展望.自动化学报, 2016, 42(1): 481-494 http://www.aas.net.cn/CN/abstract/abstract18837.shtmlYuan Yong, Wang Fei-Yue. Blockchain: the state of the art and future trends. Acta Automatica Sinica, 2016, 42(4): 481-494 http://www.aas.net.cn/CN/abstract/abstract18837.shtml [2] Block chain depth report: let the world be your witness (2) [Online], available: http://www.wxrw123.com/rm/20160420/472846_2.html, April 20, 2016 [3] Blockchain introduction [Online], available: http://brave-newcoin.com/assets/Uploads/TransactionsAsProofOfStake-10.pdf, December 14, 2015 [4] McConaghy T, Marques R, Müller A, De Jonghe D, McConaghy T T, McMullen G, Henderson R, Bellemare S, Granzotto A. BigchainDB: a scalable Blockchain database [Online], available: https://www.bigchaindb.com/whitepa-per/bigchaindb-whitepaper.pdf, June 8, 2016 [5] Castro M, Liskov B. Practical byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 2002, 20(4): 398-461 doi: 10.1145/571637.571640 [6] 范捷, 易乐天, 舒继武.拜占庭系统技术研究综述.软件学报, 2013, 24(6): 1346-1360 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201306012.htmFan Jie, Yi Le-Tian, Shu Ji-Wu. Research on the technologies of Byzantine system. Journal of Software, 2013, 24(6): 1346-1360 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201306012.htm [7] Bentov I, Lee C, Mizrahi A, Rosenfeld M. Proof of activity: extending Bitcoin's proof of work via proof of stake. ACM SIGMETRICS Performance Evaluation Review, 2014, 42(3): 34-37 doi: 10.1145/2695533 [8] Consensus in Bitcoin: one system, many models [Online], available: https://freedom-to-tinker.com/blog/randomwal-ker/consensus-in-bitcoin-one-system-many-models/, Dece-mber 26, 2014 [9] Rosenfeld M. Analysis of bitcoin pooled mining reward systems. Distributed, parallel, and cluster computing. arXiv preprint arXiv:1112.4980, 2011. [10] Block withholding attacks-recent research [Online], available: http://blog.bettercrypto.com/?p=1131, December 2, 2014 [11] Eyal I, Gün Sirer E. It's time for a hard bitcoin fork [Online], available: http://hackingdistributed.com/2014/06/13/tim-efor-a-hard-bitcoin-fork/, June 13, 2014 [12] Courtois N T. Bitcoin miner optimization [Online], available:http://www.knaw.nl/shared/resources/actueel/bestanden/140212_Bitcoin_presentatie_Nicolas_Courtois.pdf, August 24, 2017 [13] Study when be threatened, the bitcoin pool attacking [Online], available: http://www.bitecoin.com/online/2015/01/11102.html, January 4, 2015 [14] Tang C B, Li A, Li X. When reputation enforces evolutionary cooperation in unreliable MANETs. IEEE Transactions on Cybernetics, 2015, 45(10): 2190-2201 doi: 10.1109/TCYB.2014.2366971 [15] Rong Z H, Wu Z X, Chen G R. Coevolution of strategy-selection time scale and cooperation in spatial prisoner's dilemma game. Europhysics Letters, 2013, 102(6): 68005 doi: 10.1209/0295-5075/102/68005 [16] Hofbauer J, Sigmund K. Evolutionary Games and Population Dynamics. Cambridge: Cambridge University Press, 1998. 50-54 [17] Eyal I. The miner's dilemma. In: Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP). San Jose, CA, USA: IEEE, 2015. 89-103 [18] Larimer D. Transactions as proof-of-stake [Online], available: http://bravenewcoin.com/assets/Uploads/Transacti-onsAsProofOfStake10.pdf, November 28, 2013 [19] BitFury Group. Proof of stake versus proof of work [Online], available: http://bitfury.com/content/5-white-papers-research/pos-vs-pow-1.0.2.pdf, September 13, 2015 [20] Popov S. The tangle [Online], available: https://iotatoken.com/IOTA_Whitepaper.pdf, December 28, 2015 [21] Kwon J. Tendermint: consensus without mining [Online], available: https://iota.org/IOTA_Whitepaper.pdf, September 17, 2015 [22] Press W H, Dyson F J. Iterated prisoner's dilemma contains strategies that dominate any evolutionary opponent. Proceedings of the National Academy of Sciences of the United States of America, 2012, 109(26): 10409-10413 doi: 10.1073/pnas.1206569109 [23] Hilbe C, Wu B, Traulsen A, Nowak M A. Evolutionary performance of zero-determinant strategies in multiplayer games. Journal of Theoretical Biology, 2015, 374: 115-124 doi: 10.1016/j.jtbi.2015.03.032 [24] Pan L M, Hao D, Rong Z H, Zhou T. Zero-determinant strategies in iterated public goods game. Scientific Reports, 2014, 5: Article number: 13096 [25] Zhang H Q, Niyato D, Song L Y, Jiang T, Han Z. Zero-determinant strategy for resource sharing in wireless cooperations. IEEE Transactions on Wireless Communications, 2016, 15(3): 2179-2192 doi: 10.1109/TWC.2015.2499185 [26] Al Daoud A, Kesidis G, Liebeherr J. Zero-determinant strategies: a game-theoretic approach for sharing licensed spectrum bands. IEEE Journal on Selected Areas in Communications, 2014, 32(11): 2297-2308 doi: 10.1109/JSAC.2014.141126 [27] Nash J F. Equilibrium points in N-person games. Proceedings of the National Academy of Sciences of the United States of America, 1950, 36(1): 48-49 doi: 10.1073/pnas.36.1.48 -
下载:
计量
- 文章访问数: 3320
- HTML全文浏览量: 716
- PDF下载量: 1746
- 被引次数: 0
