Paper 2025/826

Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement

Abstract

Byzantine Agreement (BA) allows $$ processes to propose input values to reach consensus on a common, valid $$-bit value, even in the presence of up to $$ 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 $$ represent the size of the cryptographic objects needed to solve Byzantine agreement when $$. We achieve both IC and SMVBA with $$ amortized latency, with a bounded number of slower instances. The SMVBA protocol has $$ amortized communication and the IC has $$ amortized communication. For input values larger than $$, our protocols are asymptotically optimal. These results mark a substantial improvement—up to a linear factor, depending on $$—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.