Paper 2023/1723

Deterministic Byzantine Agreement with Adaptive $O(n\cdot f)$ Communication

Fatima Elsheimy, Yale University
Giorgos Tsimos, University of Maryland, College Park
Charalampos Papamanthou, Yale University

We present a deterministic synchronous protocol for binary Byzantine Agreement against a corrupt minority with adaptive $O(n\cdot f)$ communication complexity, where $f$ is the exact number of corruptions. Our protocol improves the previous best-known deterministic Byzantine Agreement protocol developed by Momose and Ren (DISC 2021), whose communication complexity is quadratic, independent of the exact number of corruptions. Our approach combines two distinct primitives that we introduce and implement with $O(n\cdot f)$ communication, Reliable Voting, and Weak Byzantine Agreement. In Reliable Voting, all honest parties agree on the same value only if all honest parties start with that value, but there is no agreement guarantee in the general case. In Weak Byzantine Agreement, we achieve agreement, but validity requires that the inputs to the protocol satisfy certain properties. Our Weak Byzantine Agreement protocol is an adaptation of the recent Cohen et al. protocol (OPODIS 2022), in which we identify and address various issues.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. SODA 2024
Byzantine AgreementConsensusCommunication Complexity
Contact author(s)
fatima elsheimy @ yale edu
tsimos @ umd edu
charalampos papamanthou @ yale edu
2023-11-13: revised
2023-11-07: received
See all versions
Short URL
No rights reserved


      author = {Fatima Elsheimy and Giorgos Tsimos and Charalampos Papamanthou},
      title = {Deterministic Byzantine Agreement with Adaptive $O(n\cdot f)$ Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1723},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.