2026/07/15 by Yuval Efron
#cs.DC
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 Ω ((t2)/(nlog(n+1))). This improves upon the seminal Ω((t)/(√(nlog n))) bound of [Bar-Joseph, Ben-Or 98]. Our result matches the recent upper bound of O(min\(t2log n)/(n),(t)/(log n)\) of [Dufoulon, Pandurangan 25], up to a log2 n factor in the t≪ 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(√(nlog(\frac1p))) 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 \frac1nO(R), using a crash schedule involving at most R parties. The combination of these techniques yields the desired bound.