Paper 2026/2954
Concretely Efficient Byzantine Agreement and Interactive Consistency for Honest Majority
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
-
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}
}