Settling The Round Complexity of Byzantine Agreement Against a Full-Information, Adaptive Adversary

Abstract

We prove that every randomized synchronous Byzantine Agreement protocol in the full-information, strongly adaptive adversary model, secure against $t$ corrupt parties, has worst-case expected round complexity \[ Ω\!\left(\frac{t^2}{n\log(n+1)}\right). \] This improves upon the seminal $\hat{I}\text{c◯}(\frac{t}{\sqrt{n\log n}})$ bound of [Bar-Joseph, Ben-Or 98]. Our result matches the recent upper bound of $O\left(\min \left\{\frac{t^2\log n}{n},\frac{t}{\log n}\right\}\right)$ of [Dufoulon, Pandurangan 25], up to a ${\log }^{2}n$ factor in the $t\ll n$ regime. Our proof takes inspiration from the recent works of [Etesami, Mahloujifar, Mahmoody 20] and [Haitner, Karidi-Heller 26]. Specifically, we prove a multi-round concentration lemma showing that any transcript event of probability $p$ can be forced with probability one by corrupting $O(\sqrt{n\log (\frac{1}{p})})$ parties in expectation. From there, tools from [Chor, Merritt, Shmoys 89] allow us to lower-bound the probability of the protocol not concluding in $R$ rounds by $\frac{1}{n^{O(R)}}$, using a crash schedule involving at most $R$ parties. The combination of these techniques yields the desired bound.

Topics & keywords