Data Modeling
Mathematical and Computational Data Modeling
1
Citations
5.2k
Views
34
Articles
Volume 5 Number 1 2024
RESEARCH ARTICLE (Open Access)
Optimizing Byzantine Fault Tolerance: O(1) Message Complexity Through BLS Signature Aggregation and Pipelined Consensus
Kamruzzaman Mithu 1*,
Data Modeling 5 (1) 1-8 https://doi.org/10.25163/data.5110852
Submitted: 18 October 2024 Revised: 18 October 2024 Accepted: 18 October 2024 Published: 18 October 2024
Abstract
Byzantine fault tolerant consensus underpins permissioned distributed systems, yet the classical protocol most deployments still lean on carries a stubborn flaw: its messaging overhead grows quadratically as validator sets expand, even though it offers proven safety and deterministic finality that few alternatives can match. That trade-off has, for years, pushed larger networks toward designs that sacrifice finality guarantees in exchange for speed—a compromise not every regulated environment can accept. This work presents O-PBFT, a protocol that instead builds on the classical design rather than replacing it, layering in three complementary mechanisms: signature aggregation that compresses per-round broadcasts into a single compact payload, pipelined execution that lets consensus phases overlap under careful ordering constraints, and an adaptive controller that widens or narrows pipeline depth—somewhere between one and three stages—based on live round-trip time, queue pressure, and timeout behavior. A working Go prototype was tested across workloads spanning 100 to 15,000 transactions per block, on both local hardware and a three-zone cloud deployment. Results showed close to a 90% reduction in per-phase traffic at ten validators, steady-state throughput in the range of 66 to 84 transactions per second at medium enterprise load, corresponding block latencies under 160 milliseconds, and no observed consensus failures across stress-tested conditions. Throughput improved by roughly 2.3-fold over sequential classical baselines. Altogether, these findings suggest meaningful bandwidth savings are achievable without abandoning deterministic finality or the underlying Byzantine fault threshold—an incremental, rather than radical, step toward scalability.
Keywords: Byzantine Fault Tolerance; signature aggregation; pipelined consensus; permissioned blockchains; distributed systems
References
Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., De Caro, A., Enyeart, D., Ferris, C., Laventman, G., Manevich, Y., Muralidharan, S., Murthy, C., Nguyen, B., Sethi, M., Singh, G., Smith, K., Sorniotti, A., Stathakopoulou, C., Vukolic, M., … Yellick, J. (2018). Hyperledger Fabric: A distributed operating system for permissioned blockchains. In Proceedings of the 13th EuroSys Conference (pp. 1–15). ACM.
Boneh, D., Lynn, B., & Shacham, H. (2004). Short signatures from the Weil pairing. In Advances in Cryptology—ASIACRYPT 2004 (Lecture Notes in Computer Science, Vol. 3329, pp. 514–532). Springer.
Buchman, E. (2016). Tendermint: Byzantine fault tolerance in the age of blockchains [Doctoral dissertation, University of Guelph].
Castro, M., & Liskov, B. (1999). Practical Byzantine Fault Tolerance. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (pp. 173–186). USENIX.
Herlihy, M. P., & Wing, J. M. (1990). Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3), 463–492.
Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), 382–401.
Micali, S., Rabin, M., & Vadhan, S. (1999). Verifiable random functions. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (pp. 120–130). IEEE.
Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf
Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm. In Proceedings of the USENIX Annual Technical Conference (pp. 305–320). USENIX.
Pass, R., Seeman, L., & Shelat, A. (2017). Analysis of the blockchain protocol in asynchronous networks. In Advances in Cryptology—EUROCRYPT 2017 (Lecture Notes in Computer Science, Vol. 10211, pp. 643–673). Springer.
Saxena, A., et al. (2018). Towards scalable and private industrial blockchains. In Proceedings of the ACM Workshop on Blockchain, Cryptocurrencies and Contracts (pp. 9–16). ACM.
Stathakopoulou, C., David, T., & Vukolic, M. (2021). Keeping PBFT in order. In Proceedings of the ACM Asia-Pacific Workshop on Systems (pp. 1–8). ACM.
Sundaramurthy, S., Garg, V. K., & Kalyanaraman, S. (2016). Revisiting Byzantine Fault Tolerance. In Proceedings of the IEEE International Conference on Distributed Computing Systems (pp. 428–437). IEEE.
Swanson, L., Libert, B., & Naya-Plasencia, M. (2019). Signature aggregation from symmetric key cryptography (IACR Cryptology ePrint Archive, Report 2019/1175). https://eprint.iacr.org/2019/1175
Tanenbaum, A. S., & Van Steen, M. (2017). Distributed systems: Principles and paradigms (3rd ed.). Pearson.
Yin, M., Malkhi, D., Reiter, M. K., Golan Gueta, G., & Abraham, I. (2019). HotStuff: BFT consensus with linearity and responsiveness. In Proceedings of the ACM Symposium on Principles of Distributed Computing (pp. 347–356). ACM.
Article metrics
View details
0
Downloads
0
Citations
9
Views
0
Save
Save
0
Citation
Citation
9
View
View
0
Share
Share