Paper 2026/1878

On the Round Complexity of Early Stopping

Abstract

A common pipeline of cryptographic research is: a theory paper asks an interesting question which triggers a line of works; then the problem remains dormant until technology catches up and makes the problem potentially relevant for practice; this triggers a renewed interest which at times pushes the originally theoretical ideas to practice. Several highly influential ideas have followed this pipeline: e.g., the original work on Oblivious RAMs by Goldreich and Ostrovsky [STOC'87\&90], polynomial commitments by Kate, Zaverucha, and Goldberg [ASIACRYPT'10], and many others. A problem that shows early signs of this pattern is early-stopping Byzantine Agreement (esBA): esBA protocols whose round complexity depends on the number $f$ of {\em actually} faulty parties rather than on (an upper bound on) the number $t$ of {\em potentially} faulty parties. Although it is fair to say that esBA protocols are not (yet) within the practical realm, their potential to improve large scale distributed systems like blockchain ledgers has fueled a number of recent novel results pushing the envelope in esBA feasibility (e.g., Loss and Nielsen [EUROCRYPT'24] and Elsheimy, Loss, and Papamanthou [ASIACRYPT'24]). The original starting point of this work has been to advance on the above feasibility questions. But as is common for problems following this trajectory, renewed interest often comes with observations about issues in the assumed definitions and models. Interestingly, our investigation revealed an issue with how the existing literature has been computing the round complexity of such protocols, which yields (previously unobserved) inconsistencies in the literature of esBA and more generally of synchronous protocols. In a nutshell, the inconsistencies stem from the fact that the last round of several esBA protocols has parties terminating as soon as they send a message to other parties, i.e., they don't need to wait to receive messages sent to them in that round. So, should we count this as an extra round or not? As we observe, different works give different answers to this question, and the answer one adopts affects the claimed tightness of the corresponding bounds. Building on the above observation, our work proposes a fine-grained manner of counting synchronous rounds that is both intuitive and resolves these inconsistencies. In a nutshell, our counting distinguishes between rounds in which parties might both send and receive messages, and rounds in which parties only need to send messages. Examining the existing literature through the lens of this round-counting methodology exposes gaps and new open questions in the relevant literature. We resolve these gaps and extend the landscape by several new results.