Byzantine Consensus based on an Intrusion-Tolerant In-Network Message Ordering

• Gabriel Faustino Lima da Rocha UnB
• Eduardo A. P. Alchieri UnB https://orcid.org/0000-0002-6022-3631
• Giovanni Venâncio UFPR
• Vinicius Fulber-Garcia UFPR
• Elias P. Duarte Jr. UFPR

DOI: https://doi.org/10.5753/sbrc.2025.6309

Abstract

Recent work proposes consensus protocols that divide the tasks of ensuring agreement and termination properties between the network and application layers, respectively. The network layer must deliver ordered messages to ensure agreement. To achieve this, these solutions use a sequencer. However, tolerating a malicious sequencer brings new challenges, since it can assign the same sequence number to different messages and send them to different replicas. To circumvent this problem, NeoBFT employs an additional communication step between replicas. Although this approach mitigates the problem, it affects system performance by requiring additional synchronization between replicas before requests are executed. This work proposes NsoBFT (Network Secure Ordered BFT), a consensus protocol that uses a network layer with a secure message ordering service implemented by the secure component USIG (Unique Sequential Identifier Generator). Thus, it is not necessary to perform additional synchronizations among the replicas before executing requests. Experimental results compare NsoBFT with related work, and show that this feature allows NsoBFT to surpass the performance of NeoBFT.

Keywords: Consensus, Distributed Algorithms, Intrusion Tolerance

References

Alchieri, E. A. P., Bessani, A., Greve, F., and Fraga, J. d. S. (2018). Knowledge connectivity requirements for solving Byzantine consensus with unknown participants. IEEE Transactions on Dependable and Secure Computing, 15(2), 246–259.

Bessani, A., Sousa, J., and Alchieri, E. E. P. (2014). State machine replication for the masses with BFT-SMaRt. In International Conference on Dependable Systems and Networks (pp. 355–362). IEEE.

Bravo, M., Chockler, G., and Gotsman, A. (2022). Making Byzantine consensus live. Distributed Computing, 35(6).

Castro, M. and Liskov, B. (1999). Practical Byzantine fault tolerance. In Symposium on Operating Systems Design and Implementation (pp. 173–186). Berkeley, CA, USA: USENIX.

Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4), 398–461.

Douceur, J. R. (2002). The Sybil attack. In International Workshop on Peer-to-Peer Systems (pp. 251–260). Springer.

Dwork, C., Lynch, N. A., and Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of ACM, 35(2), 288–322.

Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), 374–382.

Hadzilacos, V. and Toueg, S. (1994). A modular approach to the specification and implementation of fault-tolerant broadcasts. Technical report, Department of Computer Science, Cornell University, New York, USA.

Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2), 133–169.

Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), 382–401.

Li, C., Qiu, W., Li, X., Liu, C., and Zheng, Z. (2024). A dynamic adaptive framework for practical Byzantine fault tolerance consensus protocol in the Internet of Things. IEEE Transactions on Computers, 73(7), 1669–1682.

Li, J., Michael, E., Sharma, N. K., Szekeres, A., and Ports, D. R. (2016). Just say {NO} to Paxos overhead: Replacing consensus with network ordering. In Symposium on Operating Systems Design and Implementation (pp. 467–483). USENIX.

Liu, X. and Yu, W. (2024). A review of research on blockchain consensus mechanisms and algorithms. In International Conference on Intelligent Informatics and Biomedical Sciences, 9, 1–10.

Saramago, R. Q., Alchieri, E. A., Rezende, T. F., and Camargos, L. (2018). On the impossibility of Byzantine collision-fast atomic broadcast. In International Conference on Advanced Information Networking and Applications (pp. 414–421). IEEE.

Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4), 299–319.

Singh, A., Kumar, G., Saha, R., Conti, M., Alazab, M., and Thomas, R. (2022). A survey and taxonomy of consensus protocols for blockchains. Journal of Systems Architecture, 127, 102503.

Sun, G., Jiang, M., Khooi, X. Z., Li, Y., and Li, J. (2023). NeoBFT: Accelerating Byzantine fault tolerance using authenticated in-network ordering. In ACM Special Interest Group on Data Communications Conference (pp. 239–254). New York, NY, USA: ACM.

Vassantlal, R., Alchieri, E., Ferreira, B., and Bessani, A. (2022). Cobra: Dynamic proactive secret sharing for confidential BFT services. In Symposium on Security and Privacy (pp. 1335–1353). IEEE.

Venâncio, G., Fulber-Garcia, V., Flauzino, J., Alchieri, E. A., and Duarte, E. P. (2024). Dependable virtual network services: An architecture for fault-and intrusion-tolerant SFCS. In Conference on NFV and SDN (pp. 1–6). IEEE.

Venâncio, G., Turchetti, R. C., and Duarte Jr, E. P. (2022). NFV-Coin: Unleashing the power of in-network computing with virtualization technologies. Journal of Internet Services and Applications, 13(1), 46–53.

Veronese, G. S., Correia, M., Bessani, A. N., Lung, L. C., and Verissimo, P. (2013). Efficient Byzantine fault-tolerance. IEEE Transactions on Computers, 62(1), 16–30.

Vukolić, M. (2015). The quest for scalable blockchain fabric: Proof-of-work vs. BFT replication. In IFIP WG 11.4 International Workshop Open Problems in Network Security (pp. 112–125). Springer.

White, B., Lepreau, J., Stoller, L., Ricci, R., Guruprasad, S., Newbold, M., Hibler, M., Barb, C., and Joglekar, A. (2002). An integrated experimental environment for distributed systems and networks. ACM SIGOPS Operating Systems Review, 36(SI), 255–270.

Zou, Y., Yang, L., Jing, G., Zhang, R., Xie, Z., Li, H., and Yu, D. (2024). A survey of fault tolerant consensus in wireless networks. High-Confidence Computing, 4(2), 100202.