Byzantine Fault Tolerance Consensus Protocols: A Review
Abstract
Distributed consensus systems are an innovative means of establishing consensus between multiple parties concerning some piece of information, such as ownership of an asset. Consensus is recorded by cryptographically signing data, thus proving its authenticity. Blocks of signed data can be linked to previous blocks, thereby enforcing a temporal chain of blocks, giving rise to the term blockchain. A Byzantine Fault Tolerant (BFT) based consensus ensures that the blockchain network will continue to operate even in the presence of malicious or failure nodes. BFT consensus has received considerable attention in the last decade due to its promising application in blockchains where classic BFT-based protocols suffer from the scalability and network throughput issues despite its great potentials. Several researches were conducted to improve on BFT to address these shortcomings but still there is more to be done. In this paper, we present a review and analysis of structure, strengths and limitations of the Byzantine Fault Tolerant consensus used in blockchain systems, with a specific focus on how these protocols establish consensus. Despite the attempts to improve on the BFT, this review reveals that the existing BFTs still didn’t meet certain performance requirement needed for developing scalable and adaptable BFT based consensus mechanism.
Full Text:
PDFReferences
Abraham, I., Gueta, G., and Malkhi, D. 2018. Hot-Stuff the Linear, Optimal-Resilience, One-
Message BFT Devil. In: CoRR abs/1803.05069. arXiv: 1803.05069. url: http://arxiv.org/abs/1803.05069.
Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Tamir, O., and Tomescu, A. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In: 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). P. 568–580.
Amir, Y., Danilov, C., Dolev, D., Kirsch, J., Lane, J., Nita-Rotaru, C., Olsen, J., and Zage, D. 2010. Steward: Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks. In: IEEE Transactions on Dependable and Secure Computing 7.1 (2010), P. 80–93.
Amsden, Z. 2020. The Diem Blockchain. url: https://developers.diem.com/docs/technical-papers/the-diem-blockchain-paper/ (visited on 07/02/2023).
Artur, B., Ermol’ev, Y. M. and Kaniovskii, Y. M. (1983). A Generalized Urn Problem and its Applications. In: Cybernetics 19.1 (1983), pp. 61–71.
Baliga, A. 2017. Understanding Blockchain Consensus Models. In: Persistent 4 (2017), P. 1–14. url: https://www.persistent.com/wp-content/uploads/2017/04/WP-Understanding-Blockchain-Consensus-Models.pdf (visited on 08/02/2023).
Block’tivity Team. 2022. Block’tivity. In: (2022). url: https://blocktivity.info/ (visited on 08/02/2023).
Boneh, D., Lynn, B., and Shacham, H. (2004). Short signatures from the Weil pairing. In: Journal of cryptology 17.4 (2004), P. 297–319
Brown, R. G., Carlyle, J., Grigg, I., and Hearn, M. 2016. Corda: an Introduction. In: R3 CEV, August 1 P. 15. url: https://blockchainlab.com/pdf/cordaintroductory-whitepaper-final.pdf (visited on 09/02/2023).
Buchman, E. 2016. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. PhD thesis. (cit. on P. 1, 19).
Cachin, C., Guerraoui, R., and Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming. 2nd. Springer, 2011 P. 16 and 34.
Castro, M., and B. Liskov, B. 1999. Practical Byzantine Fault Tolerance. In: Proceedings of the Third Symposium on Operating Systems Design and Implementation. OSDI ’99. New Orleans, Louisiana, USA: USENIX Association, 1999, P. 173–186.
Cebe,M. (2018). Block4forensic: An Integrated Lightweight Blockchain Framework for Forensics Applications of Connected Vehicles. IEEE Commun. Mag. 56(10), 50–57 (2018)
Clement, A., Wong, E., Alvisi, L., Dahlin, M., and Marchetti, M. 2009. Making Byzantine Fault
Tolerant Systems Tolerate Byzantine Faults. In: Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation. NSDI’09. Boston, Massachusetts: USENIX Association, 2009, P. 153–168.
Cohen, B. and Pietrzak, K. (2020). The chia network blockchain. 2020. url:https://www.chia.net/assets/ChiaGreenPaper.pdf (visited on 15/02/2023).
Dwork, C., Lynch, N., and Stockmeyer, L. 1988. Consensus in the Presence of Partial Synchrony. In: Journal of the ACM 35.2 (Apr. 1988), P. 288–323.
Eischer, M., and Distler, T. 2018. Latency-Aware Leader Selection for Geo-Replicated Byzantine Fault-Tolerant Systems. In: 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and NetworksWorkshops (DSN-W). 2018, P. 140–145.
Ferdous, M.S. (2020). Blockchain consensus algorithms: a survey. arXiv (2020)
Fischer, M. J., Lynch, N. A., and Paterson, M. S. 1985. Impossibility of Distributed Consensus with One Faulty Process. In: Journal ACM 32.2 (Apr. 1985), P. 374–382.
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., and Zeldovich, N. (2017). Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles. SOSP ’17. Shanghai, China: Association for Computing Machinery, 2017, P. 51–68.
Golan, G., Gueta, I. A., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Seredinschi, D.A., Tamir, O., & Tomescu, A. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In: 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 2019, P. 568–580.
Gramoli,V. (2020): From blockchain consensus back to Byzantine consensus. Futur. Gener. Comput. Syst. 107, 760–769 (2020). https://doi.org/10.1016/j.future.2017.09.023
Grigg, I. 2017. EOS, An Introduction. In: (2017). url:https://iang.org/papers/EOS_Una_Introduccio%5C%CC%5C%81n-IanGrigg-Trad_MAM+AIH-20180717.pdf (visited on 07/02/2023).
Herlihy, M. (2019) Blockchains from a distributed computing perspective. Commun. ACM 62(2), 78–85 (2019)
Kiayias, A., Russell, A., David, B., and Oliynykov, R. 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In: Advances in Cryptology – CRYPTO 2017. Springer International Publishing, 2017, P. 357–388.
Kokina, J. (2017). Blockchain: emergent industry adoption and implications for accounting. J. Emerging Technol. Account. 14(2), 91–100 (2017)
Kokoris-Kogias, E., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., and Ford, B. 2016. Enhancing
Bitcoin Security and Performance with Strong Consistency via Collective Signing. In: USENIX Security. Austin (TX), USA, 2016, P. 279–296.
Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., and Ford, B. 2018. OmniLedger: A
Secure, Scale-Out, Decentralized Ledger via Sharding. In: 2018 IEEE Symposium on Security and Privacy (SP). P. 583–598.
Kokoris-Kogias, E. 2019. Robust and Scalable Consensus for Sharded Distributed Ledgers. In: IACR Cryptology ePrint Archive 2019 (2019), P. 676.
Kotla, R., Alvisi, L., Dahlin, M., Clement, A., and Wong, E. 2010. Zyzzyva: Speculative Byzantine Fault Tolerance. In: ACM Transactions on Computer Systems 27.4 (2010), P. 1–39.
Lamport, L., Shostak, R., and Pease, M. 1982. The Byzantine Generals Problem. In: ACM Transactions on Programming Languages and Systems 4.3 (1982), P. 382–401.
Larimer, D., Scott, N., Zavgorodnev, V., Johnson, B., Calfee, J., and Vandeberg, M.2016. Steem: An Incentivized, Blockchain-Based Social Media Platform. In: March. Self-published (2016). url: https://steem.com/SteemWhitePaper.pdf (visited on 07/02/2023).
Leonardos, S. (2020). PREStO: A Systematic Framework for Blockchain Consensus Protocols. IEEE Trans. Eng. Manage. 67(4), 1028–1044 (2020)
Li, P., Wang, G., Chen, X., Long, F., and Xu, W. (2020). Gosig: A Scalable and High- Performance Byzantine Consensus for Consortium Blockchains. In: Proceedings of the 11th ACM Symposium on Cloud Computing. SoCC ’20. Virtual Event, USA: Association for Computing Machinery, 2020, P. 223–237.
Li, W., Feng, C., Zhang, L., Xu, H., Cao, B., & Imran, M. 2021. A Scalable Multi-Layer PBFT Consensus for Blockchain. In: IEEE Transactions on Parallel and Distributed Systems 32.5 (2021), P. 1146–1160.
Lina A., Noureddine L., & Mohamed A. 2020. Local bitcoin network simulator for performance evaluation using lightweight virtualization. In 2020 IEEE International Conference on Informatics, IoT, and Enabling Technologies (ICIoT), P. 355–360. IEEE, 2020.
Liu, Y., Liu, J., Zhang, Z., Xu, T., and Yu, H. (2019). Overview on consensus mechanism of blockchain technology, J. Cryptol. Res. 6 (4) (2019) P. 395–432.
Michael M., Maria L. P., and Robert D. L. 2009. Performance of t12 and t8 fluorescent lamps and troffers and led linear replacement lamps caliper benchmark report. Technical report, Pacific Northwest National Lab.(PNNL), Richland, WA (United States).
Miller, A., Xia, Y., Croman, K., Shi, E., and Song, D. 2016. The Honey Badger of BFT Protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. CCS ’16. Vienna, Austria: Association for Computing Machinery, 2016, P. 31–42.
Moon, J. W. (1983). On level numbers of t-ary trees. In: SIAM Journal on Algebraic Discrete Methods 4.1 (1983), P. 8–13.
Neiheiser, R., Presser, D., Rech, L., Bravo, M., Rodrigues, L., and Correia, M. 2018. Fireplug: Flexible and Robust N-Version Geo-Replication of Graph Databases. In: 2018 International Conference on Information Networking (ICOIN). 2018, P. 110–115. doi: 10.1109/ICOIN.2018.8343095.
Neiheiser, R., Matos, M., and Rodrigues, L. 2021. Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation. In: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. SOSP ’21. Virtual Event, Germany: Association for Computing Machinery, 2021, P. 35-48.
Nicholson, W. L. (1956). On the Normal Approximation to the Hypergeometric Distribution. In: The Annals of Mathematical Statistics 27.2 (1956), P. 471–483. url:http://www.jstor.org/stable/2237005
Panda, S. (2019). Study of blockchain based decentralized consensus algorithms. In: TENCON 2019 - 2019 IEEE Region 10 Conference (TENCON), pp. 908–913 (2019). https://doi. org/10.1109/TENCON.2019.8929439
Pilkington, M. 2016. 11 Blockchain technology: principles and applications. In: Research Handbook on Digital Transformations. P. 3-5.
Rahnama, S., Gupta, S., Qadah, T. M., Hellings, J., and Sadoghi, M. 2020. Scalable, Resilient, and Configurable Permissioned Blockchain Fabric. In: Proc. VLDB Endow. 13.12 (Aug. 2020), P. 2893–2896.
Sousa, J. and Bessani, A. 2015. Separating the WHEAT from the Chaff: An Empirical Design for Geo-Replicated State Machines. In: 2015 IEEE 34th Symposium on Reliable Distributed Systems (SRDS). 2015, P. 146–155.
Stathakopoulou, C., David, T., and Vukolic, M. 2019. Mir-BFT: High-Throughput BFT for Blockchains. In:CoRR abs/1906.05552. arXiv: 1906.05552.
Steinbeck, D. 2019. Crypto Snippets: The Stellar Blockchain just Crashed—This is why Nodes Matter. In: Cryptolawinsider. url: https://cryptolawinsider.com/stellar-crash/ (visited on 08/02/2023).
Veronese, G. S., Correia, M., Bessani, A. N., and Lung, L. C. 2009. Spin One’s Wheels? Byzantine Fault Tolerance with a Spinning Primary. In: 2009 28th IEEE International Symposium on Reliable Distributed Systems. 2009, P. 135–144.
Veronese, G. S., Correia, M., Bessani, A. N., and Lung, L. C. 2010. EBAWA: Efficient Byzantine Agreement for Wide-Area Networks. In: 2010 IEEE 12th International Symposium on High Assurance Systems Engineering. 2010, P. 10–19.
Wan, S., Li, M., Liu, G., and Wang, C. (2019). Recent Advances in Consensus Protocols for Blockchain: A Survey. Wireless Netw. 26(8), 5579–5593 (2019). https://doi.org/10.1007/s11276-019-021 95-0
Wood, G. 2014. Ethereum: A Secure Decentralised Generalised Transaction Ledger. In: Ethereum project yellow paper 151, P. 1–32. url: https://files.gitter.im/ethereum/yellowpaper/VIyt/Paper.pdf (visited on 06/02/2023).
Wu, W., and Gao, Z. (2020). An Improved Blockchain Consensus Mechanism Based on Open Business Environment. In: IOP Conference Series: Earth and Environmental Science, p. 012043. IOP Publishing (2020)
Xiao, Y. (2020): A Survey of Distributed Consensus Protocols for Blockchain Networks. IEEE Commun. Surv. Tutor. 22(2), P. 1432–1465 (2020). https://doi.org/10.1109/COMST.2020.296 9706
Yin, M., Malkhi, D., Reiter, M. K., Golan-Gueta,G., and Abraham, I. 2019. HotStuff: BFT consensus with linearity and responsiveness, in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, on, Canada, July 29 - August 2, 2019, 2019, P. 347–356.
Zhang, C. (2020). Overview of Blockchain Consensus Mechanism. In: Proceedings of the 2020 2nd International Conference on Big Data Engineering, New York, NY, USA, pp. 7–12. Association for Computing Machinery (2020). https://doi.org/10.1145/3404512.3404522
Zhao, W. (2019). On Consensus in Public Blockchains. In: Proceedings of the 2019 International Conference on Blockchain Technology, New York, NY, USA, pp. 1–5. Association for Computing Machinery (2019). https://doi.org/10.1145/3320154.3320162.
Refbacks
- There are currently no refbacks.