Paper 2025/246

Towards Optimal Early Stopping Agreement Protocols

Abstract

Early stopping agreement protocols guarantee termination based on the actual number of malicious parties, $f \leq t$, encountered during execution, rather than assuming the worst-case scenario of $t<n$ many corruptions. The lower bound on the round complexity for such protocols is known to be $\min\{f+2, t+1\}$ many rounds. In this work, we substantially improve the state of the art for cryptographic early stopping protocols in the honest majority setting where $t<n/2$. In this scenario, the best known protocol due to Elsheimy, Loss, and Papamanthou (ASIACRYPT `24) achieves a round complexity of $(1+\epsilon)\cdot f$ for some constant $0<\epsilon<1$. We begin by introducing an improvement to the Elsheimy et al. approach which can be used to obtain the first polynomial-time early stopping agreement protocols in the $t<n/2$ corruption regime which achieve a complexity of $f+O(\sqrt{f})$. We then instantiate our generic framework with refined components to obtain a very concretely efficient protocol with a round complexity of only $f + 6\lceil\sqrt{f}\rceil+6$ and polynomial communication complexity. Finally, we show that it is possible to come within one round of the optimal round complexity by presenting a broadcast protocol based on the exponential information gathering approach, which achieves a round complexity of $\min\{f + 3, t + 1\}$, albeit with exponential communication complexity.