logo

SCIENCE CHINA Information Sciences, Volume 64 , Issue 2 : 121101(2021) https://doi.org/10.1007/s11432-019-2790-1

A survey of Blockchain consensus algorithms: mechanism, design and applications

More info
  • ReceivedOct 3, 2019
  • AcceptedFeb 5, 2020
  • PublishedNov 18, 2020

Abstract

In 2008, Blockchain was introduced to the world as the underlying technology of the Bitcoin system. After more than a decade of development, various Blockchain systems have been proposed by both academia and industry. This paper focuses on the consensus algorithm, which is one of the core technologies of Blockchain. In this paper, we propose a unified consensus algorithm process model that is suitable for Blockchains based on both the chain and directed acyclic graph (DAG) structure. Subsequently, we analyze various mainstream Blockchain consensus algorithms and classify them according to their design in different phases of the process model. Additionally, we present an evaluation framework of Blockchain consensus algorithms and then discuss the security design principles that enable resistance from different attacks. Finally, we provide some suggestions for selecting consensus algorithms in different Blockchain application scenarios.


Acknowledgment

This work was supported by National Key RD Program of China (Grant No. 2016YFB1000100), National Natural Science Foundation of China (Grant No. 61772030), and GF Innovative Research Program.


References

[1] Nakamoto S. Bitcoin: a peer-to-peer electronic cash system. 2008. http://bitcoin.org/bitcoin.pdf. Google Scholar

[2] Wang H, Zheng Z, Xie S. Blockchain challenges and opportunities: a survey. IJWGS, 2018, 14: 352 CrossRef Google Scholar

[3] Yuan Y, Wang F Y. Blockchain: The state of the art and future trends. Acta Automatica Sinica, 2016, 42:. Google Scholar

[4] Wood G et al. Ethereum: a secure decentralised generalised transaction ledger. 2014. http://gavwood.com/Paper.pdf. Google Scholar

[5] Yuan Y, Wang F Y. Blockchain and Cryptocurrencies: Model, Techniques, and Applications. IEEE Trans Syst Man Cybern Syst, 2018, 48: 1421-1428 CrossRef Google Scholar

[6] Christidis K, Devetsikiotis M. Blockchains and Smart Contracts for the Internet of Things. IEEE Access, 2016, 4: 2292-2303 CrossRef Google Scholar

[7] Sharma P K, Chen M Y, Park J H. A Software Defined Fog Node Based Distributed Blockchain Cloud Architecture for IoT. IEEE Access, 2018, 6: 115-124 CrossRef Google Scholar

[8] Chen Q, Bridges R A. Automated behavioral analysis of malware: a case study of wannacry ransomware. In: Proceedings of the 16th IEEE International Conference on Machine Learning and Applications (ICMLA), 2017. 454--460. Google Scholar

[9] Bencic F M, Zarko I P. Distributed ledger technology: blockchain compared to directed acyclic graph. In: Proceedings of the 38th International Conference on Distributed Computing Systems (ICDCS), 2018. 1569--1570. Google Scholar

[10] Chen Z D, Dong A Q, Sun H, et al. Research on private blockchain based on crowdfunding. J Inf Secur Res, 2017, 3: 227--236. Google Scholar

[11] Pongnumkul S, Siripanpornchana C, Thajchayapong S. Performance analysis of private blockchain platforms in varying workloads. In: Proceedings of the 26th International Conference on Computer Communication and Networks (ICCCN), 2017. Google Scholar

[12] Lamport L, Shostak R, Pease M. The Byzantine Generals Problem. ACM Trans Program Lang Syst, 1982, 4: 382-401 CrossRef Google Scholar

[13] Perry K J, Toueg S. Distributed agreement in the presence of processor and communication faults. IIEEE Trans Software Eng, 1986, SE-12: 477-482 CrossRef Google Scholar

[14] Lamport L. The part-time parliament. ACM Trans Comput Syst, 1998, 16: 133-169 CrossRef Google Scholar

[15] Lamport L. Paxos made simple. ACM Sigact News, 2001, 32: 18--25. Google Scholar

[16] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm. In: Proceedings of USENIX Annual Technical Conference, 2014. 305--319. Google Scholar

[17] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process. J ACM, 1985, 32: 374-382 CrossRef Google Scholar

[18] Karame G, Androulaki E, Capkun S. Two bitcoins at the price of one? double-spending attacks on fast payments in bitcoin. 2012.. Google Scholar

[19] Karame G. On the security and scalability of bitcoin's blockchain. In: Proceedings of ACM Sigsac Conference on Computer and Communications Security, 2016. 1861--1862. Google Scholar

[20] King S, Nadal S. Ppcoin: peer-to-peer crypto-currency with proof-of-stake. 2012. https://decred.org/research/king2012.pdf. Google Scholar

[21] Castro M, Liskov B. Practical byzantine fault tolerance. In: Proceedings of Symposium on Operating Systems Design and Implementation, 1999. 173--186. Google Scholar

[22] Bano S, Sonnino A, Al-Bassam M, et al. Consensus in the age of blockchains. 2017,. arXiv Google Scholar

[23] Bach L, Mihaljevic B, Zagar M. Comparative analysis of blockchain consensus algorithms. In: Proceedings of the 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2018. 1545--1550. Google Scholar

[24] Wang W, Hoang D T, Hu P. A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks. IEEE Access, 2019, 7: 22328-22370 CrossRef Google Scholar

[25] Eyal I, Gencer A E, Sirer E G, et al. Bitcoin-ng: a scalable blockchain protocol. In: Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI16), 2016, 45--59. Google Scholar

[26] Gilad Y, Hemo R, Micali S, et al. Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, 2017. 51--68. Google Scholar

[27] Zhang Z W. A byzantine fault-tolerant algorithm for blockchains. 2016. https://docs.neo.org/en-us/basic/consensus/whitepaper.html. Google Scholar

[28] Churyumov A. Byteball: a decentralized system for storage and transfer of value. 2016. https://byteball.org/Byteball.pdf. Google Scholar

[29] Baird L. The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance. Swirlds Tech Reports SWIRLDS-TR-2016-01. 2016. Google Scholar

[30] Micali S, Rabin M, Vadhan S. Verifiable random functions. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. 120--130. Google Scholar

[31] Li X, Jiang P, Chen T. A survey on the security of blockchain systems. Future Generation Comput Syst, 2020, 107: 841-853 CrossRef Google Scholar

[32] Xiang F, Huaimin W, Peichang S. Jointgraph: A DAG?based efficient consensus algorithm for consortium blockchains. Softw-Pract Exper, 2019, 42: spe.2748 CrossRef Google Scholar

[33] Rachmawati D, Tarigan J T, Ginting A B C. A comparative study of Message Digest 5(MD5) and SHA256 algorithm. J Phys-Conf Ser, 2018, 978: 012116 CrossRef ADS Google Scholar

[34] K J. O'Dwyer and D Malone. Bitcoin mining and its energy footprint. 2014. doi: 10.1049/cp.2014.0699. Google Scholar

[35] Li C X, Li P L, Xu W, et al. Scaling nakamoto consensus to thousands of transactions per second. 2018,. arXiv Google Scholar

[36] D Larimer. Delegated proof-of-stake (dpos). Bitshare whitepaper, 2014. Google Scholar

[37] Milutinovic M, He W, Wu H, et al. Proof of luck: an efficient blockchain consensus protocol. In: proceedings of the 1st Workshop on System Software for Trusted Execution, 2016. Google Scholar

[38] P of burn. https://en.bitcoin.it/wiki/Proofofburn 2014. Google Scholar

[39] Sabt M, Achemlal M, Bouabdallah A. Trusted execution environment: what it is, and what it is not. In: Proceedings of the 14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 2015. Google Scholar

[40] Fabric H. Simple bft. 2018. https://jira.hyperledger.org/browse/FAB-378. Google Scholar

[41] Androulaki E, Barger A, Bortnikov V, et al. Hyperledger fabric: a distributed operating system for permissioned blockchains. In: Proceedings of European Conference on Computer Systems, 2018. Google Scholar

[42] Yin M F, Malkhi D, Reiter M K, et al. Hotstuff: BFT consensus with linearity and responsiveness. In: Proceedings of ACM Symposium on Principles of Distributed Computing, 2019. Google Scholar

[43] Stathakopoulou C, David T, Vukolić M. Mir-BFT: high-throughput BFT for blockchains. 2019,. arXiv Google Scholar

[44] Mathieu B, Avery C, Andrey C, et al. State machine replication in the libra blockchain. 2019. https://developers.libra.org/docs/state-machine-replication-paper. Google Scholar

[45] Facebook. The libra blockchain. 2019. https://developers.libra.org/docs/the-libra-blockchain-paper. Google Scholar

[46] Miller A, Xia Y, Croman K, et al. The honey badger of BFT protocols. In: Proceedings of ACM SIGSAC Conference on Computer and Communications Security, 2016. 31--42. Google Scholar

[47] Ben-Or M, Kelmer B, Rabin T. Asynchronous secure computations with optimal resilience. In: Proceedings of the 13th Annual ACM Symposium on Principles of distributed computing, 1994. 183--192. Google Scholar

[48] Xiang F, Huaimin W, Peichang S. Proof of Previous Transactions (PoPT): An Efficient Approach to Consensus for JCLedger. IEEE Trans Syst Man Cybern Syst, 2019, : 1-10 CrossRef Google Scholar

[49] Popov S. The tangle. 2018. http://www.descryptions.com/Iota.pdf. Google Scholar

[50] Bentov I, Lee C, Mizrahi A, et al. Proof of activity: extending bitcoin's proof of work via proof of stake. 2014. https://eprint.iacr.org/2014/452.pdf. Google Scholar

[51] Buchman E. Tendermint: Byzantine fault tolerance in the age of blockchains. Dissertation for Ph.D. Degree. Guelph: University of Guelph, 2016. Google Scholar

[52] Buterin V, Reijsbergen D, Leonardos S, et al. Incentives in ethereum's hybrid casper protocol. 2019,. arXiv Google Scholar

[53] Dinh T T A, Wang J, Chen G, et al. Blockbench: a framework for analyzing private blockchains. In: Proceedings of ACM International Conference on Management of Data, 2017. 1085--1100. Google Scholar

[54] Nguyen G, Kim K. A survey about consensus algorithms used in blockchain. J Inf Process Syst, 2018, 14: 101--128. Google Scholar

[55] Chalaemwongwan N, Kurutach W. State of the art and challenges facing consensus protocols on blockchain. In: Proceedings of International Conference on Information Networking (ICOIN), 2018. 957--962. Google Scholar

[56] Douceur J R. The sybil attack. In: Proceedings of International Workshop on Peer to Peer Systems, 2002. Google Scholar

[57] Singh A, Ngan T W, Druschel P, et al. Eclipse attacks on overlay networks: threats and defenses. In: Proceedings of IEEE International Conference Computer and Communications, 2006. Google Scholar

[58] Kroll J A, Davey I C, Felten E W. The economics of bitcoin mining, or bitcoin in the presence of adversaries. In Proceedings of the 12th Workshop on the Economics of Information Securit, 2013. Google Scholar

[59] Wang H M, Shi P C, Zhang Y M. Jointcloud: a cross-cloud cooperation architecture for integrated internet service customization. In: Proceedings of IEEE International Conference on Distributed Computing Systems, 2017. 1846--1855. Google Scholar

[60] Liang J, Han W, Guo Z. DESC: enabling secure data exchange based on smart contracts. Sci China Inf Sci, 2018, 61: 049102 CrossRef Google Scholar

[61] Wu Y, Fan H, Wang X. A regulated digital currency. Sci China Inf Sci, 2019, 62: 32109 CrossRef Google Scholar

[62] Veronese G S, Correia M, Bessani A N. Efficient Byzantine Fault-Tolerance. IEEE Trans Comput, 2013, 62: 16-30 CrossRef Google Scholar