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

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 𝑛 < 3𝑡. We achieve both IC and SMVBA with 𝑂 (1) amortized latency, with a bounded number of slower instances. The SMVBA protocol has 𝑂 (𝑛𝐿 𝑜 + 𝑛𝜅) amortized communication and the IC has 𝑂 (𝑛𝐿 𝑜 +𝑛 2 𝜅) 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.