Paper 2024/822

Early Stopping Byzantine Agreement in $(1+\epsilon)\cdot f$ Rounds

Abstract

In this paper, we present two early stopping Byzantine agreement protocols in the authenticated setting against a corrupt minority $t < n/2$, where $t$ represents the maximum number of malicious parties. Early stopping protocols ensure termination within a number of rounds determined solely by the actual number of malicious nodes $f$ present during execution, irrespective of $t$. Our first protocol is deterministic and ensures early stopping termination in $ (d+5) \cdot (\lfloor f/d \rfloor +3)$ rounds, where $d$ is a fixed constant. For example, for all $d\ge 6$, our protocol runs in at most $(1+\epsilon )\cdot f$ rounds (where $0<\epsilon<1$), improving (for large $f$) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg, which terminates in $min(2f+4,2t+2)$ rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in $(d+9) \cdot (\lfloor f/d \rfloor +2)$ rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank, which always requires an expected constant number of rounds and $O(t)$ rounds in the worst case, i.e., does not have the early stopping property.