1Beijing Key Laboratory of Internet Culture and Digital Dissemination Research, Beijing Information Science and Technology University, Beijing 100101, China 2Sunego (Beijing) Technology Limited Company, Beijing 100036, China
[Objective] This paper analyzes the application of Byzantine problem and reviews related research on the consensus mechanisms of consortium blockchain.[Coverage] We searched “consensus mechanisms” as keywords from the titles or topics of WoS, ResearchGate, arXiv and CNKI databases. A total of 74 papers were retrieved.[Methods] We reviewed the consensus mechanism and classification method of the blockchain. Then, we explored the applications of Byzantine problem, and discussed the strong and permissioned consensus mechanisms.[Results] We summarized the developments and ties of Byzantine problem, Brewer’s theorem, Byzantine system and Byzantine fault-tolerant mechanism. We also proposed the basic procedures and evaluation criteria for consensus mechanisms of consortium blockchain. Finally, we divided the consensus mechanism into four categories based on security and time delay.[Limitations] This paper did not cover all consensus mechanisms for consortium blockchain.[Conclusions] The research on consensus mechanism promotes the implementation of blockchain, which could be improved from fault tolerance, communication delay and conversion efficiency in the future studies.
( Zeng Shiqin, Huo Ru, Huang Tao , et al. Survey of Blockchain: Principle, Progress and Application[J]. Journal on Communications, 2020,41(1):134-151.)
[8]
崔锦文 . 基于共识理论的中国网络主流意识形态建设研究[D]. 武汉: 华中科技大学, 2019.
[8]
( Cui Jinwen . Research on the Construction of Network Mainstream Ideology in China Based on Consensus Theory[D]. Wuhan: Huazhong University of Science and Technology, 2019)
[9]
Gilbert S, Lynch N . Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services[J]. ACM SIGACT News, 2002,33(2):51-59.
doi: 10.1145/564585.564601
[10]
Li J R, Wolf T. A One-Way Proof-of-Work Protocol to Protect Controllers in Software-Defined Networks[C]// Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems. 2016: 123-124.
[11]
Ganesh C, Orlandi C, Tschudi D. Proof-of-Stake Protocols for Privacy-Aware Blockchains[C]// Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2019: 690-719.
[12]
Larimer D. Delegated Proof of Stake [EB/OL]. ( 2014 -04-03). [2020-07-31]. https://how.bitshares.works/en/master/technology/dpos.html.
[13]
Castro M, Liskov B . Practical Byzantine Fault Tolerance and Proactive Recovery[J]. ACM Transactions on Computer Systems, 2002,20(4):398-461.
doi: 10.1145/571637.571640
[14]
Bentov I, Lee C, Mizrahi A , et al. Proof of Activity: Extending Bitcoin’s Proof of Work via Proof of Stake[OL]. https://eprint.iacr.org/2014/452.pdf.
[15]
Ongaro D, Ousterhout J. In Search of an Understandable Consensus Algorithm[C]// Proceedings of the 2014 USENIX Annual Technical Conference. 2014: 305-320.
[16]
Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling Byzantine Agreements for Cryptocurrencies[C]// Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 2017: 51-68.
[17]
Kwon J . Tendermint: Consensus without mining [EB/OL]. [2020-08-12].https://tendermint.com/static/docs/tendermint.pdf.
[18]
Androulaki E, Manevich Y, Muralidharan S, et al. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains[C]// Proceedings of the 13th EuroSys Conference. 2018.
( Jin Lu . Between Rules and Technology: Risk Analysis and Legal Regulation of Block Chain Technology Application[J]. Law Science Magazine, 2020,41(7):84-93.)
( Wu Xiyuan, Liu Min, Zheng Qinghua , et al. Quantitative Evaluation Method and Empirical Analysis of User Experience in Web Services[J]. Journal of Computer Applications, 2014,34(S2):154-158.)
[22]
Hanke T, Movahedi M, Williams D , et al. DFINITY Technology Overview Series, Consensus System [OL]. arXiv Preprint, arXiv: 1805. 04548.
[23]
Chan T H, Pass R, Shi E , et al. PaLa: A Simple Partially Synchronous Blockchain[OL]. https://eprint.iacr.org/2018/981.pdf.
[24]
Decker C, Seidel J, Wattenhofer R, et al. Bitcoin Meets Strong Consistency[C]// Proceedings of the 17th International Conference of Distributed Computing and Networking. 2016.
[25]
Kokoris-Kogias E, Jovanovic P, Gailly N , et al. Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing[J]. Applied Mathematical Modelling, 2016,37(8):5723-5742.
doi: 10.1016/j.apm.2012.11.009
[26]
Abraham I, Malkhi D, Nayak K, et al. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus[C]// Proceedings of the 21st International Conference on Principles of Distributed Systems. 2017.
[27]
Pass R, Shi E. Hybrid Consensus: Efficient Consensus in the Permissionless Model[C]// Proceedings of the 31st International Symposium on Distributed Computing. 2017.
[28]
Pass R, Shi E. Thunderella: Blockchains with Optimistic Instant Confirmation[C]// Proceedings of 2018 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2018: 3-33.
[29]
Luu L, Narayanan V, Zheng C D, et al. A Secure Sharding Protocol for Open Blockchains[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016: 17-30.
[30]
Kokoris-Kogias E, Jovanovic P, Gasser L, et al. OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding[C]// Proceedings of 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018: 583-598.
[31]
Al-Bassam M, Sonnino A, Bano S, et al. Chainspace: A Sharded Smart Contracts Platform[C]// Proceedings of the Network and Distributed System Security Symposium. 2018.
[32]
Zamani M, Movahedi M, Raykova M. RapidChain: Scaling Blockchain via Full Sharding[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2018: 931-948.
( Yuan Yong, Ni Xiaochun, Zeng Shuai , et al. Blockchain Consensus Algorithms: The State of the Art and Future Trends[J]. Acta Automatica Sinica, 2018,44(11):2011-2022.)
( Liu Yizhong, Liu Jianwei, Zhang Zongyang , et al. Overview on Blockchain Consensus Mechanisms[J]. Journal of Cryptologic Research, 2019,6(4):395-432.)
( Lu Gehao, Xie Lihong, Li Xiyu . Comparative Research of Blockchain Consensus Algorithm[J]. Computer Science, 2020,47(S1):332-339.)
[38]
Cachin C, Vukolić M. Blockchain Consensus Protocols in the Wild[C]// Proceedings of the 31st Symposium on Distributed Computing. 2017: 1-16.
[39]
Jourenko M, Kurazumi K, Larangeira M , et al. SoK: A Taxonomy for Layer-2 Scalability Related Protocols for Cryptocurrencies[OL]. https://eprint.iacr.org/2019/352.pdf.
[40]
Sharmila K, Kamalakkannan S, Devi R , et al. A Comprehensive Study on Blockchain with Its Components, Taxonomy and Consensus[J]. International Journal of Management, Technology and Engineering, 2019,9(1):971-975.
[41]
Ferdous M S , Chowdhury M J M, Hoque M A, et al. Blockchain Consensus Algorithms: A Survey[OL]. arXiv Preprint, arXiv: 2001. 07091.
[42]
Juan G, Aggelos K. SoK: A Consensus Taxonomy in the Blockchain Era[C]// Proceedings of the Cryptographers’ Track at the RSA Conference 2020. 2020:284-318.
( Liu Hongnan, Wei Kai . Consortiumblockchain Technology Test Observation and Analysis[J]. Information and Communications Technology and Policy, 2020,46(1):35-45.)
[44]
Chen L, Xu L, Shah N, et al. On Security Analysis of Proof-of-Elapsed-Time (PoET)[C]// Proceedings of International Symposium on Stabilization, Safety, and Security of Distributed Systems. Springer, Cham, 2017: 282-297.
( Zhang Jian, Wang Yang, Liu Dandan . Yac: Yet Another Distributed Consensus Algorithm[J]. Journal of Computer Applications, 2017,37(9):2524-2530.)
[46]
Clement A, Wong E, Alvisi L, et al. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults[C]// Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation. 2009: 153-168.
[47]
Lamport L . The Part-Time Parliament[J]. ACM Transactions on Computer Systems, 1998,16(2):133-169.
[48]
Dwork C, Naor M. Pricing via Processing or Combatting Junk Mail[C]// Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. 1992: 139-147.
[49]
Sousa J, Bessani A. From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation[C]// Proceedings of the 9th European Dependable Computing Conference. 2012: 37-48.
[50]
Bessani A, Sousa J, Alchieri E E P. State Machine Replication for the Masses with BFT-SMART[C]// Proceedings of the 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 2014: 355-362.
[51]
Armknecht F, Karame G O, Mandal A, et al. Ripple: Overview and Outlook[C]// Proceedings of 2015 International Conference on Trust and Trustworthy Computing. 2015: 163-180.
Abd-El-Malek M, Ganger G R, Goodson G R , et al. Fault-Scalable Byzantine Fault-Tolerant Services[J]. ACM SIGOPS Operating Systems Review, 2005,39(5):59-74.
[54]
Buterin V . A Next-Generation Smart Contract and Decentralized Application Platform(White Paper)[EB/OL]. ( 2019-06-17). [2020-08-08]. https://github.com/ethereum/wiki/wiki/White-Paper .
[55]
Cowling J A, Myers D S, Liskov B, et al. HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance[C]// Proceedings of the 7th Symposium on Operating Systems Design and Implementation. 2006: 177-190.
[56]
Kotla R, Dahlin M. High Throughput Byzantine Fault Tolerance[C]// Proceedingso of International Conference on Dependable Systems & Networks. IEEE, 2004.
[57]
Kotla R. Zyzzyva: Speculative Byzantine Fault Tolerance[C]// Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles. ACM, 2007: 45-58.
[58]
Sompolinsky Y, Zohar A. Secure High-Rate Transaction Processing in Bitcoin[C]// Proceedings of International Conference on Financial Cryptography and Data Security. 2015: 507-527.
[59]
Kiayias A, Russell A, David B, et al. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol[C]// Proceedings of Annual International Cryptology Conference. 2017: 357-388.
[60]
韩璇, 刘亚敏 . 区块链技术中的共识机制研究, 信息网络安全, 2017(9):147-152.
[60]
( Han Xuan, Liu Yamin . Research on the Consensus Mechanisms of Blockchain Technology, Netinfo Security, 2017(9):147-152.)
[61]
Nelson M . The Byzantine Generals Problem[J]. Dr. Dobb’s Journal: the World of Software Development, 2008,33(4):30.
[62]
闵应骅 . 拜占庭将军问题, 中国传媒科技, 2006(3):35-37.
[62]
( Min Yinghua . Byzantine Generals Problem, Science & Technology for China's Mass Media, 2006(3):35-37.)
Diouf G M, Elbiaze H, Jaafar W . On Byzantine Fault Tolerance in Multi-Master Kubernetes Clusters[J]. Future Generation Computer Systems, 2020,109:407-419.
( Fan Jie, Yi Letian, Shu Jiwu . Research on the Technologies of Byzantine System[J]. Journal of Software, 2013,24(6):1346-1360.)
[66]
Lamport L, Shostak R, Pease M . The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982,4(3):382-401.
doi: 10.1145/357172.357176
( Chen Chun,. Key Technology in Alliance Chain and Challenges in Monitoring Blockchain[J]. Electric Power Equipment Management, 2019(11):20-21, 28.)
[68]
Li X W, Zhou L, Yuan L H. Decoupling Multi-Processors from Congestion Control in Byzantine Fault Tolerance[C]// Proceedings of 2015 International Industrial Informatics and Computer Engineering Conference. 2015: 1824-1827.
[69]
Dwork C, Moses Y . Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures[J]. Information and Computation, 1986,88(2):156-186.
doi: 10.1016/0890-5401(90)90014-9
[70]
Abraham I, Chan T H H, Dolev D, et al. Communication Complexity of Byzantine Agreement, Revisited[C]// Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 2019: 317-326.
( Fang Dingyi, Zhou Xingshe, Kang Jichang . Survey on Distributed Operating Systems and Distributed System Environment[J]. Microelectronics & Computer, 2000,17(6):9-15.)
[72]
Bracha G . Asynchronous Byzantine Agreement Protocols[J]. Information and Computation, 1987,75(2):130-143.
doi: 10.1016/0890-5401(87)90054-X
[73]
Veronese G S, Correia M, Bessani A N, et al. Spin One’s Wheels? Byzantine Fault Tolerance with a Spinning Primary[C]// Proceedings of the 28th IEEE International Symposium on Reliable Distributed Systems. IEEE, 2009: 135-144.
[74]
Ferdous M S, Chowdhury F, Alassafi M O . In Search of Self-Sovereign Identity Leveraging Blockchain Technology[J]. IEEE Access, 2019,7. DOI: 10.1109/ACCESS.2019.2931173.
doi: 10.1109/ACCESS.2019.2935763
pmid: 32754420