Paper 2026/2954

Concretely Efficient Byzantine Agreement and Interactive Consistency for Honest Majority

Michele Ciampi, University of Edinburgh
Pouyan Forghani, Georgia Institute of Technology
Yun Lu, University of Victoria
Vassilis Zikas, Georgia Institute of Technology
Abstract

We consider two of the main notions of round-efficient Byzantine agreement (BA): expected constant rounds and early stopping. Randomized protocols can terminate in an expected constant number of rounds, while early-stopping protocols terminate in a number of rounds that depends only on the actual number $f\le t$ of corrupted parties. Recent works achieve both guarantees at once, but at a high concrete cost: assuming PKI, for the optimal threshold $t<n/2$, the previous protocol with the smallest expected round complexity needs $37$ rounds in expectation and $15f+29$ in the worst case. In this work, we present a BA protocol for $t<n/2$, secure against an adaptive adversary assuming a PKI, that terminates in $18$ rounds in expectation and in at most $8f+18$ rounds in the worst case. Moreover, our protocol has the following optimistic feature: if no party is corrupted and all inputs agree, every party outputs after a single round. Our protocol is natively multi-valued and does not rely on random oracles. At the core of our result is a new randomized BA protocol in which a successful leader election leads to agreement within the same phase. We extend our results to Byzantine broadcast, obtaining a protocol that has $19$ rounds in expectation and $8f+19$ in the worst case, and to interactive consistency (IC), retaining the same round complexity while providing an optimistic fast path in which all parties output after only 2 rounds when everyone is honest. We do so by directly parallelizing our BB protocol, instead of using a generic IC compiler, for which, at $t<n/2$, the best known bounds are more than $4000$ rounds in expectation and $184f+730$ in the worst case.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Byzantine AgreementInteractive ConsistencyBroadcast
Contact author(s)
mciampi @ ed ac uk
pforghani3 @ gatech edu
yunlu @ uvic ca
vzikas @ gatech edu
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2954
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2954,
      author = {Michele Ciampi and Pouyan Forghani and Yun Lu and Vassilis Zikas},
      title = {Concretely Efficient  Byzantine Agreement and Interactive Consistency for Honest Majority},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2954},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2954}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.