Improved Byzantine Agreement under an Adaptive Adversary
Fabien Dufoulon, Gopal Pandurangan · 2025
Byzantine agreement is a fundamental problem in fault-tolerant distributed computing that has been studied intensively for the last four decades. Much of the research has focused on a static Byzantine adversary, where the adversary is constrained to choose the Byzantine nodes in advance of the protocol's execution. This work focuses on the harder case of an adaptive Byzantine adversary that can choose the Byzantine nodes adaptively based on the protocol's execution. While efficient O(log n)-round protocols (n is the total number of nodes) are known for the static adversary (Ben-Or, Goldwasser, Vaikuntanathan, FOCS 2006) tolerating up to t < n/(3 + ϵ) Byzantine nodes, [EQUATION] rounds is a well-known lower bound for adaptive adversary [Bar-Joseph and Ben-Or, PODC 1998]. The best-known protocol for adaptive adversary runs in O(t/log n) rounds [Chor and Coan, IEEE Trans. Soft. Engg., 1985].