Abstract
Pipelined Byzantine Fault Tolerant (BFT) consensus is fundamental to permissioned blockchains. However, many existing protocols are limited by the requirement for view-consecutive quorum certificates(QCs). This constraint impairs performance and creates liveness vulnerabilities under adverse network conditions. Achieving “certificate decoupling”–committing blocks without this requirement–is therefore a key research goal. While the recent BeeGees algorithm achieves this, our work reveals that it suffers from security and liveness issues. To address this problem, this paper makes two primary contributions. First, we formally define these flaws as the Invalid Block Problem and the Hollow Chain Problem. Second, we propose pBeeGees, a new algorithm that addresses these issues while preserving certificate decoupling with no additional computational overhead. To achieve this, pBeeGees integrates traceback and pre-commit validation to solve the Invalid Block Problem. Further, to mitigate the Hollow Chain Problem, we introduce a prudent validation mechanism, which prevents unverified branches from growing excessively. To summarize, pBeeGees is the first protocol to simultaneously achieve safety, liveness, and certificate decoupling in a pipelined BFT framework. Experiments confirm that our design significantly reduces block commit latency compared to classic algorithms, particularly under frequent stopping faults.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Castro, M., Liskov, B., et al.: Practical byzantine fault tolerance. In: OsDI. 99, 173–186 (1999)
Chan, T.H.H., Pass, R., Shi, E.: PaLa: A Simple Partially Synchronous Blockchain (2018)
Civit, P., et al.: Byzantine consensus is \(\theta \) (n 2): the Dolev-reischuk bound is tight even in partial synchrony! Distrib. Comput. 37(2), 89–119 (2024)
Duan, S., Reiter, M.K., Zhang, H.: BEAT: Asynchronous BFT Made Practical. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 2028–2041. ACM, Toronto Canada (Oct 2018)
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM (JACM) 35(2), 288–323 (1988)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM (JACM) 32(2), 374–382 (1985)
Gao, Y., Lu, Y., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo-ng: fast asynchronous BFT consensus with throughput-oblivious latency. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 1187–1201 (2022)
Giridharan, N., Suri-Payer, F., Ding, M., Howard, H., Abraham, I., Crooks, N.: Beegees: stayin’alive in chained BFT. In: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, pp. 233–243 (2023)
Jalalzai, M.M., Niu, J., Feng, C., Gai, F.: Fast-hotstuff: a fast and resilient hotstuff protocol. arXiv preprint arXiv:2010.11454 (2020)
Lewis-Pye, A.: Quadratic worst-case message complexity for state machine replication in the partial synchrony model. arXiv preprint arXiv:2201.01107 (2022)
Lewis-Pye, A., Abraham, I.: Fever: optimal responsive view synchronisation. arXiv preprint arXiv:2301.09881 (2023)
Lewis-Pye, A., Malkhi, D., Naor, O., Nayak, K.: Lumiere: Making optimal BFT for partial synchrony practical. In: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, pp. 135–144 (2024)
Miller, A., Xia, Y., Croman, K., Shi, E., Song, D.: The honey badger of BFT protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 31–42 (2016)
Resilient Systems Lab.: relab/hotstuff. https://github.com/relab/hotstuff
Team, T.D.: Diembft v4: State machine replication in the diem blockchain (2021). https://api.semanticscholar.org/CorpusID:246607407
Yang, K., Zhang, J., Zheng, J., Liu, Q., Wu, W., Zhou, J.: pBeeGees: A Prudent Approach to Certificate-Decoupled BFT Consensus. arXiv preprint arXiv2509.17496 (Sep 2025)
Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: Hotstuff: BFT consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 347–356 (2019)
Acknowledgments
This research is partially supported by the Guangdong Natural Science Foundation of China (2025A1515011663), The GuangDong Basic and Applied Basic Research Foundation (No.2022A1515110932), and The National Science Foundation for Young Scientists of China (No.62302106).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2026 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Yang, K., Zhang, J., Zheng, J., Liu, Q., Wu, W., Zhou, J. (2026). pBeeGees: A Prudent Approach to Certificate-Decoupled BFT Consensus. In: Liu, H., Ibrahim, S., Rauber, T. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2025. Lecture Notes in Computer Science, vol 16386. Springer, Singapore. https://doi.org/10.1007/978-981-95-8411-6_8
Download citation
DOI: https://doi.org/10.1007/978-981-95-8411-6_8
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-95-8410-9
Online ISBN: 978-981-95-8411-6
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
