2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

PoW共识算法中的博弈困境分析与优化

唐长兵 杨珍 郑忠龙 陈中育 李翔

唐长兵, 杨珍, 郑忠龙, 陈中育, 李翔. PoW共识算法中的博弈困境分析与优化. 自动化学报, 2017, 43(9): 1520-1531. doi: 10.16383/j.aas.2017.c160672
引用本文: 唐长兵, 杨珍, 郑忠龙, 陈中育, 李翔. PoW共识算法中的博弈困境分析与优化. 自动化学报, 2017, 43(9): 1520-1531. doi: 10.16383/j.aas.2017.c160672
TANG Chang-Bing, YANG Zhen, ZHENG Zhong-Long, CHEN Zhong-Yu, LI Xiang. Game Dilemma Analysis and Optimization of PoW Consensus Algorithm. ACTA AUTOMATICA SINICA, 2017, 43(9): 1520-1531. doi: 10.16383/j.aas.2017.c160672
Citation: TANG Chang-Bing, YANG Zhen, ZHENG Zhong-Long, CHEN Zhong-Yu, LI Xiang. Game Dilemma Analysis and Optimization of PoW Consensus Algorithm. ACTA AUTOMATICA SINICA, 2017, 43(9): 1520-1531. doi: 10.16383/j.aas.2017.c160672

PoW共识算法中的博弈困境分析与优化

doi: 10.16383/j.aas.2017.c160672
基金项目: 

国家自然科学基金 61503342

国家杰出青年基金 61425019

国家自然科学基金 61272007

浙江省自然科学基金 LY16 F030002

国家自然科学基金重点项目 71731004

国家自然科学基金 61672467

详细信息
    作者简介:

    唐长兵    博士, 浙江师范大学数理与信息工程学院讲师. 2015年获得复旦大学博士学位.主要研究方向为复杂网络, 博弈理论及其应用, 网络安全与优化控制.E-mail: tangcb@zjnu.cn

    杨珍    浙江师范大学数理与信息工程学院硕士研究生.2015年获得河北科技师范学院学士学位.主要研究方向为区块链技术, 博弈理论及其应用.E-mail: y_zh_en@163.com

    郑忠龙    浙江师范大学数理与信息工程学院教授.2005年获得上海交通大学博士学位.主要研究方向为数据科学, 机器学习, 图像处理.E-mail: zhonglong@zjnu.edu.cn

    李翔    复旦大学信息科学与工程学院教授. 2002年获得南开大学博士学位.主要研究方向为复杂网络与系统控制.E-mail: lix@fudan.edu.cn

    通讯作者:

    陈中育    浙江师范大学数理与信息工程学院教授.2011年获得上海大学博士学位.主要研究方向为软件形式化方法, 需求建模技术, 区块链应用技术.本文通信作者. E-mail: czy@zjnu.cn

Game Dilemma Analysis and Optimization of PoW Consensus Algorithm

Funds: 

National Natural Science Foundation of China 61503342

National Science Foundation for Distinguished Young Scholar of China 61425019

National Natural Science Foundation of China 61272007

Natural Science Foundation of Zhejiang Province LY16 F030002

Key Projects of National Natural Science Foundation of China 71731004

National Natural Science Foundation of China 61672467

More Information
    Author Bio:

        Ph. D., lecturer at the College of Mathematics, Physics and Information Engineering, Zhejiang Normal University. He received his Ph.D. degree from Fudan University in 2015. His research interest covers complex networks, game theory and application, network security, and optimal control.E-mail:

        Master student at the College of Mathematics, Physics and Information Engineering, Zhejiang Normal University. She received her bachelor degree from Hebei Normal University of Science and Technology in 2015. Her research interest covers blockchain technology, game theory and application.E-mail:

        Professor at the College of Mathematics, Physics and Information Engineering, Zhejiang Normal University. He received his Ph.D. degree from Shanghai Jiao Tong University in 2005. His research interest covers data science, machine learning, and image processing.E-mail:

        Professor at the School of Information Science and Technology, Fudan University. He received his Ph.D. degree from Nankai University in 2002. His research interest covers complex networks and system control.E-mail:

    Corresponding author: CHEN Zhong-Yu     Professor at the College of Mathematics, Physics and Information Engineering, Zhejiang Normal University. He received his Ph.D. degree from Shanghai University in 2011. His research interest covers formal methods, requirement modeling, and blockchain applications. Corresponding author of this paper.E-mail:czy@zjnu.cn
  • 摘要: 区块链是随着比特币等数字加密货币逐渐兴起而盛行的一种新型去中心化分布式系统,具有去中心化、时序数据、集体维护、可编程和安全可信等特点.目前,区块链已引起政府部门、金融机构、科技企业和资本市场的高度重视与广泛关注.如何在一个去中心化的分布式系统中高效地达成共识是区块链技术研究的重要问题.本文从工作量证明(Proof of work,PoW)共识算法的挖矿困境入手,分析PoW共识过程中矿工策略选择的纳什均衡存在条件.利用零行列式(Zero determinant,ZD)策略对矿工策略选择进行优化,并通过数值仿真来验证优化算法的有效性.概括来说,本文从博弈论角度来理解和剖析PoW共识算法,为进一步设计基于博弈论的共识算法提供新的思路和方法.
    1)  本文责任编委 袁勇
  • 图  1  矿工纯策略纳什均衡分布图

    Fig.  1  The distribution of pure strategies Nash equilibrium for miners

    图  2  算力不同时矿工的收益分布情况

    Fig.  2  The payoff distribution of miners with different powers

    图  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

    图  10  当矿工算力不相同时, LM采用ZD策略, SM采用不同的三种策略, LM和SM收益的线性关系

    Fig.  10  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 different power

  • [1] 袁勇, 王飞跃.区块链技术发展现状与展望.自动化学报, 2016, 42(1): 481-494 http://www.aas.net.cn/CN/abstract/abstract18837.shtml

    Yuan 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.htm

    Fan 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
  • 加载中
图(10)
计量
  • 文章访问数:  3211
  • HTML全文浏览量:  690
  • PDF下载量:  1732
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-15
  • 录用日期:  2017-02-21
  • 刊出日期:  2017-09-20

目录

    /

    返回文章
    返回