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\le 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 $$ for some constant $$. 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 $$ corruption regime which achieve a complexity of $$. We then instantiate our generic framework with refined components to obtain a very concretely efficient protocol with a round complexity of only $$ 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 $$, albeit with exponential communication complexity.