Paper 2025/826
Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement
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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Byzantine AgreementAmortized Complexity
- Contact author(s)
-
pierre civit @ epfl ch
ayaz dzulfikar @ u nus edu
seth gilbert @ comp nus edu sg
rachid guerraoui @ epfl ch
jovan komatovic @ epfl ch
manuel ribeirovidigueira @ epfl ch - History
- 2025-05-09: approved
- 2025-05-09: received
- See all versions
- Short URL
- https://ia.cr/2025/826
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/826, author = {Pierre Civit and Muhammad Ayaz Dzulfikar and Seth Gilbert and Rachid Guerraoui and Jovan Komatovic and Manuel Vidigueira}, title = {Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/826}, year = {2025}, url = {https://eprint.iacr.org/2025/826} }