Paper 2023/1723
Deterministic Byzantine Agreement with Adaptive $O(n\cdot f)$ Communication
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. SODA 2024
- Keywords
- Byzantine AgreementConsensusCommunication Complexity
- Contact author(s)
-
fatima elsheimy @ yale edu
tsimos @ umd edu
charalampos papamanthou @ yale edu - History
- 2023-11-13: revised
- 2023-11-07: received
- See all versions
- Short URL
- https://ia.cr/2023/1723
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/1723,
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{https://eprint.iacr.org/2023/1723}},
url = {https://eprint.iacr.org/2023/1723}
}
