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 and expected Ω(n^4) communication. We also give a lower bound showing that expected Ω(n^2) communication is necessary against a strongly rushing adaptive adversary.