Early Stopping for Any Number of Corruptions

ePrint Report: Early Stopping for Any Number of Corruptions

Julian Loss, Jesper Buus Nielsen

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 $O(\min\{f^2,t+1\})$ rounds for any execution with $f\leq t$ actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all …

broadcast complexity computing cryptography distributed distributed computing eprint report loss malicious protocol question report work