Paper 2025/826

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

Pierre Civit, École Polytechnique Fédérale de Lausanne
Muhammad Ayaz Dzulfikar, National University of Singapore
Seth Gilbert, National University of Singapore
Rachid Guerraoui, École Polytechnique Fédérale de Lausanne
Jovan Komatovic, École Polytechnique Fédérale de Lausanne
Manuel Vidigueira, École Polytechnique Fédérale de Lausanne
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.