Welcome to the resource topic for 2023/1723
Title:
Deterministic Byzantine Agreement with Adaptive O(n\cdot f) Communication
Authors: Fatima Elsheimy, Giorgos Tsimos, Charalampos Papamanthou
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.
ePrint: https://eprint.iacr.org/2023/1723
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .