Welcome to the resource topic for 2025/826
Title:
Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement
Authors: Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira
Abstract:Byzantine Agreement (BA) allows n processes to propose input values to reach consensus on a common, valid L_o-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from the protocol. Although strategies like randomization, adaptiveness, and batching have been extensively explored to mitigate the inherent limitations of one-shot agreement tasks, there has been limited progress on achieving good amortized performance for multi-shot agreement, despite its obvious relevance to long-lived functionalities such as state machine replication.
Observing that a weak form of accountability suffices to identify and exclude malicious processes, we propose new efficient and deterministic multi-shot agreement protocols for multi-value validated Byzantine agreement (MVBA) with a strong unanimity validity property (SMVBA) and interactive consistency (IC). Specifically, let \kappa represent the size of the cryptographic objects needed to solve Byzantine agreement when n<3t. We achieve both IC and SMVBA with O(1) amortized latency, with a bounded number of slower instances. The SMVBA protocol has O(nL_o +n\kappa) amortized communication and the IC has O(nL_o + n^2\kappa) amortized communication. For input values larger than \kappa, our protocols are asymptotically optimal. These results mark a substantial improvement—up to a linear factor, depending on $L_o$—over prior results. To the best of our knowledge, the present paper is the first to achieve the long-term goal of implementing a state machine replication abstraction of a distributed service that is just as fast and efficient as its centralized version, but with greater robustness and availability.
ePrint: https://eprint.iacr.org/2025/826
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 .