2.765

2022影响因子

(CJCR)

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

留言板

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

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

区块链共识算法的发展现状与展望

袁勇 倪晓春 曾帅 王飞跃

袁勇, 倪晓春, 曾帅, 王飞跃. 区块链共识算法的发展现状与展望. 自动化学报, 2018, 44(11): 2011-2022. doi: 10.16383/j.aas.2018.c180268
引用本文: 袁勇, 倪晓春, 曾帅, 王飞跃. 区块链共识算法的发展现状与展望. 自动化学报, 2018, 44(11): 2011-2022. doi: 10.16383/j.aas.2018.c180268
YUAN Yong, NI Xiao-Chun, ZENG Shuai, WANG Fei-Yue. Blockchain Consensus Algorithms: The State of the Art and Future Trends. ACTA AUTOMATICA SINICA, 2018, 44(11): 2011-2022. doi: 10.16383/j.aas.2018.c180268
Citation: YUAN Yong, NI Xiao-Chun, ZENG Shuai, WANG Fei-Yue. Blockchain Consensus Algorithms: The State of the Art and Future Trends. ACTA AUTOMATICA SINICA, 2018, 44(11): 2011-2022. doi: 10.16383/j.aas.2018.c180268

区块链共识算法的发展现状与展望

doi: 10.16383/j.aas.2018.c180268
基金项目: 

国家自然科学基金 71702182

国家自然科学基金 61533019

国家自然科学基金 61233001

国家自然科学基金 71232006

国家自然科学基金 71472174

详细信息
    作者简介:

    倪晓春  中国科学院自动化研究所复杂系统管理与控制国家重点实验室工程师.2008年于大连海事大学获得管理科学与工程专业硕士学位.主要研究方向为社会计算与区块链.E-mail:xiaochun.ni@ia.ac.cn

    曾帅  中国科学院自动化研究所复杂系统管理与控制国家重点实验室助理研究员.2011年于北京邮电大学获得信号与信息处理专业博士学位.主要研究方向为社会计算, 策略优化, 区块链.E-mail:shuai.zeng@ia.ac.cn

    王飞跃  中国科学院自动化研究所复杂系统管理与控制国家重点实验室主任, 国防科技大学军事计算实验与平行系统技术研究中心主任, 中国科学院大学中国经济与社会安全研究中心主任, 青岛智能产业技术研究院院长.主要研究方向为平行系统的方法与应用, 社会计算, 平行智能以及知识自动化.E-mail:feiyue.wang@ia.ac.cn

    通讯作者:

    袁勇  中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员.青岛智能产业技术研究院副院长.2008年获得山东科技大学计算机软件与理论专业博士学位.主要研究方向为社会计算, 计算广告学, 区块链技术.本文通信作者.E-mail:yong.yuan@ia.ac.cn

Blockchain Consensus Algorithms: The State of the Art and Future Trends

Funds: 

National Natural Science Foundation of China 71702182

National Natural Science Foundation of China 61533019

National Natural Science Foundation of China 61233001

National Natural Science Foundation of China 71232006

National Natural Science Foundation of China 71472174

More Information
    Author Bio:

     Engineer at the State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences. He received his master degree in management science and engineering from Dalian Maritime University in 2008. His research interest covers social computing and blockchain

     Assistant professor at the State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences. She received her Ph. D. degree in signal and information processing from Beijing University of Post & Telecommunication in 2011. Her research interest covers social computing, strategy optimaization, and blockchain

     State specially appointed expert and director of the State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences. Professor of the Research Center for Computational Experiments and Parallel Systems Technology, National University of Defense Technology. Director of China Economic and Social Security Research Center in University of Chinese Academy of Sciences. Dean of Qingdao Academy of Intelligent Industries. His research interest covers methods and applications for parallel systems, social computing, parallel intelligence, and knowledge automation

    Corresponding author: YUAN Yong  Associate professor at the State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences. He is also the vice president of Qingdao Academy of Intelligent Industries. He received his Ph. D. degree of computer software and theory from Shandong University of Science and Technology in 2008. His research interest covers social computing, computational advertising, and blockchain. Corresponding author of this paper
  • 摘要: 共识算法是区块链技术的核心要素,也是近年来分布式系统研究的热点.本文系统性地梳理和讨论了区块链发展过程中的32种重要共识算法,介绍了传统分布式一致性算法以及分布式共识领域的里程碑式的重要研究和结论,提出了区块链共识算法的一种基础模型和分类方法,并总结了现有共识算法的发展脉络和若干性能指标,以期为未来共识算法的创新和区块链技术的发展提供参考.
    1)  本文责任编委 刘艳军
  • 图  1  区块链共识过程的基础模型

    Fig.  1  A basic model of blockchain consensus processes

    图  2  区块链共识算法的历史演进

    Fig.  2  The evolutionary tree of blockchain consensus algoirthms

    表  1  区块链共识算法汇总表

    Table  1  Summary of blockchain consensus algorithms

    名称 提出年份 拜占庭容错 基础算法 代表性应用
    Viewstamped replication 1988 BDB-HA
    Paxos (族) 1989 Chubby
    PBFT 1999 是(<1/3) BFT Hyperledger v0.6.0
    PoW 1999 是(<1/2) Bitcoin
    PoS 2011 是(<1/2) Peercoin, Nxt
    DPoS 2013 是(<1/2) PoS EOS, Bitshares
    Raft 2013 etcd, braft
    Ripple 2013 是(<1/5) Ripple
    Tendermint 2014 是(<1/3) PoS+PBFT Monax
    Tangaroa (BFTRaft) 2014 是(<1/3) Raft+PBFT
    Proof of activity 2014 是(<1/2) PoW+PoS Decred
    Proof of burn 2014 是(<1/2) PoW+PoS Slimcoin
    Proof of space 2014 是(<1/2) PoW Burstcoin
    Proof of stake velocity (PoSV) 2014 是(<1/2) PoW+PoS ReddCoin
    Casper 2015 是(<1/2) PoW+PoS Ethereum
    Quorum voting 2015 是(<1/3) Ripple+Stellar Sawtooth Lake
    Stellar (SCP) 2015 是(<1/3) Ripple+BFT Stellar
    Algorand 2016 是(<1/3) PoS+BFT ArcBlock
    Bitcoin-NG 2016 是(<1/2) PoW
    Byzcoin 2016 是(<1/3) BTC-NG
    dBFT 2016 是(<1/3) PoS+pBFT NEO
    Elastico 2016 是(<1/3) PBFT+PoW
    HoneyBadger 2016 是(<1/3) Tendermint
    PoET 2016 是(<1/2) PoW Sawtooth Lake
    Proof of luck 2016 是(<1/2) PoW Luckychain
    Scalable BFT 2016 是(<1/3) Tangaroa Kadena
    2-hop 2017 是(<1/2) PoW+PoS
    ByzCoinX 2017 是(<1/3) ByzCoin+Elastico OmniLedger
    Proof of authority 2017 是(<1/2) PoS Parity
    Proof of useful work 2017 是(<1/2) PoW
    Ouroboros 2017 是(<1/2) PoS Cardano
    Sleepy consensus 2017 是(<1/2) PoS
    下载: 导出CSV
  • [1] Eisenberg E, Gale D. Consensus of subjective probabilities:the pari-mutuel method. The Annals of Mathematical Statistics, 1959, 30(1):165-168 http://cid.oxfordjournals.org/external-ref?access_num=10.1214/aoms/1177706369&link_type=DOI
    [2] Nakamoto S. Bitcoin: a peer-to-peer electronic cash system[Online], available: http://bitcoins.info/bitcoin.pdf, April 10, 2018.
    [3] 袁勇, 王飞跃.区块链技术发展现状与展望.自动化学报, 2016, 42(4):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
    [4] 袁勇, 周涛, 周傲英, 段永朝, 王飞跃.区块链技术:从数据智能到知识自动化.自动化学报, 2017, 43(9):1485-1490 http://www.aas.net.cn/CN/abstract/abstract19125.shtml

    Yuan Yong, Zhou Tao, Zhou Ao-Ying, Duan Yong-Chao, Wang Fei-Yue. Blockchain technology:from data intelligence to knowledge automation. Acta Automatica Sinica, 2017, 43(9):1485-1490 http://www.aas.net.cn/CN/abstract/abstract19125.shtml
    [5] 袁勇, 王飞跃.平行区块链:概念、方法与内涵解析.自动化学报, 2017, 43(10):1703-1712 http://www.aas.net.cn/CN/abstract/abstract19148.shtml

    Yuan Yong, Wang Fei-Yue. Parallel blockchain:concept, methods and issues. Acta Automatica Sinica, 2017, 43(10):1703-1712 http://www.aas.net.cn/CN/abstract/abstract19148.shtml
    [6] 曾帅, 袁勇, 倪晓春, 王飞跃.面向比特币的区块链扩容: 关键技术, 制约因素与衍生问题.自动化学报, DOI: 10.16383/j.aas.c180100

    Zeng Shuai, Yuan Yong, Ni Xiao-Chun, Wang Fei-Yue. Scaling blockchain towards bitcoin: key technologies, constraints and related issues. Acta Automatica Sinica, DOI: 10.16383/j.aas.c180100
    [7] Akkoyunlu E A, Ekanadham K, Huber R V. Some constraints and tradeoffs in the design of network communications. In: Proceedings of the 5th ACM Symposium on Operating Systems Principles. Austin, Texas, USA: ACM, 1975. 67-74 http://www.mendeley.com/research/some-constraints-tradeoffs-design-network-communications/
    [8] Gray J N. Notes on data base operating systems. Operating Systems:An Advanced Course. Berlin:Springer-Verlag, 1978. 393-481
    [9] Pease M, Shostak R, Lamport L. Reaching agreement in the presence of faults. Journal of the ACM, 1980, 27(2):228-234 doi: 10.1145/322186.322188
    [10] Lamport L, Shostak R, Pease M. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982, 4(3):382-401 doi: 10.1145/357172.357176
    [11] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 1985, 32(2):374-382 doi: 10.1145/3149.214121
    [12] Oki B M, Liskov B H. Viewstamped replication: a new primary copy method to support highly-available distributed systems. In: Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing. Toronto, Ontario, Canada: ACM, 1988. 8-17 http://www.mendeley.com/catalog/viewstamped-replication-new-primary-copy-method-support-highlyavailable-distributed-systems/
    [13] Lamport L. The part-time parliament. ACM Transactions on Computer Systems, 1998, 16(2):133-169 doi: 10.1145/279227.279229
    [14] Wattenhofer R. The Science of the Blockchain. USA:CreateSpace Independent Publishing Platform, 2016.
    [15] Dwork C, Naor M. Pricing via processing or combatting junk mail. In: Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. Santa Barbara, California, USA: Springer-Verlag, 1992. 139-147 http://www.springerlink.com/content/l90we8aq0nre2a4n
    [16] Back A. Hashcash-a denial of service counter-measure[Online], available: http://www.hashcash.org/papers/hashcash.pdf, April 10, 2018.
    [17] Jakobsson M, Juels A. Proofs of work and bread pudding protocols (extended abstract). Secure Information Networks. Boston, MA, Germany:Springer, 1999. 258-272 http://www.springerlink.com/content/fulltext.pdf?id=doi:10.1007/978-0-387-35568-9_18
    [18] Castro M, Liskov B. Practical Byzantine fault tolerance. In: Proceedings of the 3rd Symposium on Operating Systems Design and Implementation. New Orleans, USA: USENIX Association, 1999. 173-186 http://dl.acm.org/citation.cfm?id=296824
    [19] Gilbert S, Lynch N. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, 2002, 33(2):51-59 doi: 10.1145/564585
    [20] Proof of stake[Online], available: https://en.bitcoin.it/wiki/Proof_of_Stake, April 11, 2018.
    [21] Schwartz D, Youngs N, Britto A. The Ripple protocol consensus algorithm[Online], available: https://ripple.com/files/ripple_consensus_whitepaper.pdf, April 10, 2018.
    [22] BitShares. Delegated proof of stake[Online], available: http://docs.bitshares.org/bitshares/dpos.html, April 10, 2018.
    [23] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm. In: Proceedings of the USENIX Annual Technical Conference. Philadelphia, PA, USA: USENIX ATC, 2014. 305-319
    [24] Lamport L. Paxos made simple. ACM SIGACT News, 2001, 32(4):51-58 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0235401123/
    [25] Ren L. Proof of stake velocity: building the social currency of the digital age[Online], available: https://assets.coss.io/documents/white-papers/reddcoin.pdf, April 10, 2018.
    [26] Proof of burn[Online], available: https://en.bitcoin.it/wiki/Proof of burn, April 10, 2018.
    [27] Bentov I, Lee C, Mizrahi A, Rosenfeld M. Proof of activity: extending Bitcoin's proof of work via proof of stake[Online], available: http://eprint.iacr.org/2014/452, April 10, 2018.
    [28] Duong T, Fan L, Zhou H S. 2-hop blockchain: combining proof-of-work and proof-of-stake securely[Online], available: https://eprint.iacr.org/2016/716, April 10, 2018.
    [29] Kwon J. Tendermint: consensus without mining[Online], available: https://tendermint.com/static/docs/ten-dermint.pdf, April 10, 2018.
    [30] Ethereum's Casper protocol explained in simple terms[Online], available: https://www.finder.com/ethereum-casper, April 10, 2018.
    [31] David B, Gaži P, Kiayias A, Russell A. Ouroboros Praos: an adaptively-secure, semi-synchronous proof-of-stake protocol[Online], available: http://eprint.iacr.org/2017/573, April 10, 2018.
    [32] Goodman L M. Tezos-a self-amending crypto-ledger position paper[Online], available: https://www.tezos.com/static/papers/position_paper.pdf, April 10, 2018.
    [33] Miller A, Xia Y, Croman K, Shi E, Song D. The honey badger of BFT protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. Vienna, Austria: ACM, 2016. 31-42
    [34] Zamfir V. Introducing Casper "the Friendly Ghost"[Online], available: https://blog.ethereum.org/2015/08/01/introducing-casper-friendly-ghost/, April 10, 2018.
    [35] Buterin V, Griffith V. Casper the friendly finality gadget[Online], available: https://arxiv.org/pdf/1710.09437.pdf, April 10, 2018.
    [36] Eyal I, Gencer A E, Sirer E G, van Renesse R. Bitcoin-NG: a scalable blockchain protocol. In: Proceedings of the 13th USENIX Conference on Networked Systems Design and Implementation. Santa Clara, USA: USENIX Association, 2016. 45-59 http://dl.acm.org/citation.cfm?id=2930615
    [37] Kogias E K, Jovanovic P, Gailly N, Khoffi I, Gasser L, Ford B. Enhancing bitcoin security and performance with strong consistency via collective signing. In: Proceedings of the 25th USENIX Security Symposium. Austin, TX, USA: USENIX Association, 2016. 279-296 http://memento.epfl.ch/event/enhancing-bitcoin-security-and-performance-with-st/
    [38] Luu L, Narayanan V, Zheng C D, Baweja K, Gilbert S, Saxena P. A secure sharding protocol for open blockchains. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. Vienna, Austria: ACM, 2016. 17-30 http://www.deepdyve.com/lp/association-for-computing-machinery/a-secure-sharding-protocol-for-open-blockchains-GYAJ0F0KdC
    [39] Kokoris-Kogias E, Jovanovic P, Gasser L, Gailly N, Syta E, Ford B. OmniLedger: A secure, scale-out, decentralized ledger via sharding[Online], available: http://eprint.iacr.org/2017/406, April 10, 2018.
    [40] Buntinx J P. What is proof of elapsed time?[Online], available: https://themerkle.com/what-is-proof-of-elapsed-time/, April 10, 2018.
    [41] Milutinovic M, He W, Wu H, Kanwal M. Proof of luck: an efficient blockchain consensus protocol[Online], available: https://eprint.iacr.org/2017/249.pdf, April 10, 2018.
    [42] Ateniese G, Bonacina I, Faonio A, Galesi A. Proofs of space: when space is of the essence. In: Proceedings of the 9th International Conference on Security and Cryptography for Networks. Amalfi, Italy: Springer, 2014. 538-557 doi: 10.1007%2F978-3-319-10879-7_31
    [43] Ball M, Rosen A, Sabin M, Vasudevan P V. Proofs of useful work[Online], available: https://allquantor.at/blockchain-bib/pdf/ball2017proofs.pdf, April 10, 2018.
    [44] Copeland C, Zhong H X. Tangaroa: a byzantine fault tolerant raft[Online], available: http://www.scs.stanford.edu/14au-cs244b/labs/projects/copeland_zhong.pdf, April 10, 2018.
    [45] Martino W. Kadena: the first scalable, high performance private blockchain[Online], available: http://kadena.io/docs/Kadena-ConsensusWhitePaper-Aug2016.pdf, April 10, 2018.
    [46] Maziéres D. The stellar consensus protocol: a federated model for internet-level consensus[Online], available: https://www.stellar.org/papers/stellar-consensus-protocol.pdf, April 10, 2018.
    [47] Gilad Y, Hemo R, Micali S, Vlachos G, Zeldovich N. Algorand: scaling byzantine agreements for cryptocurrencies[Online], available: http://eprint.iacr.org/2017/454, April 10, 2018.
    [48] Pass R, Shi E. The sleepy model of consensus[Online], available: https://eprint.iacr.org/2016/918.pdf, August 16, 2018.
    [49] Yuan Y, Wang F Y. Blockchain and cryptocurrencies:model, techniques, and applications. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2018, 48(9):1421-1428 doi: 10.1109/TSMC.2018.2854904
    [50] Zeng S, Ni X C, Yuan Y, Wang F Y. A bibliometric analysis of blockchain research. In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium (Ⅳ'18). Changshu, China: IEEE, 2018. 102-107
    [51] Ni X C, Zeng S, Han X, Yuan Y, Wang F Y. Organizational management using software-defined robots based on smart contracts. In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium (Ⅳ'18). Changshu, China: IEEE, 2018. 274-279
    [52] Wang S, Yuan Y, Wang X, Li J J, Qin R, Wang F Y. An overview of smart contract: architecture, applications, and future trends. In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium (Ⅳ'18). Changshu, China: IEEE, 2018. 108-113
    [53] Li J J, Yuan Y, Wang S, Wang F Y. Transaction queue game in bitcoin blockchain. In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium (Ⅳ'18). Changshu, China: IEEE, 2018. 114-119
    [54] Qin R, Yuan Y, Wang S, Wang F Y. Economic issues in bitcoin minning and blockchain research. In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium (Ⅳ'18). Changshu, China: IEEE, 2018. 268-273
  • 加载中
图(2) / 表(1)
计量
  • 文章访问数:  3821
  • HTML全文浏览量:  1603
  • PDF下载量:  1813
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-04-29
  • 录用日期:  2018-09-17
  • 刊出日期:  2018-11-20

目录

    /

    返回文章
    返回