Early Stopping for Any Number of Corruptions

Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to \(t=n-1\) malicious corruptions and terminates in \(\mathcal {O}(\min \{f^2,t+1\})\) rounds for any execution with \(f\le t\) actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to \(t=(1-\epsilon )n\) malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.