Paper 2018/1028 Original: eprint.iacr.org/2018/1028 ↗
Synchronous Byzantine Agreement with Expected $O(1)$ Rounds, Expected $O(n^2)$ Communication, and Optimal Resilience
Abstract
We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of $f$ faults among $n=2f+1$ parties. Our protocols achieve an expected $O(1)$ round complexity and an expected $O(n^2)$ communication complexity. The exact round complexity in expectation is 10 for a static adversary and 16 for a strongly rushing adaptive adversary. For comparison, previous protocols in the same setting require expected 29 rounds.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2019-03-06: last updated
- 2018-10-26: published
- Short URL
- https://ia.cr/2018/1028
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2018/1028,
author = {Ittai Abraham and Srinivas Devadas and Danny Dolev and Kartik Nayak and Ling Ren},
title = {Synchronous Byzantine Agreement with Expected $O(1)$ Rounds, Expected $O(n^2)$ Communication, and Optimal Resilience},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/1028},
year = {2018},
url = {https://eprint.iacr.org/2018/1028}
}