Abstract
We provide the first protocol that solves Byzantine agreement with optimal early stopping (min{f+2,t+1} rounds) and optimal resilience (n>3t) using polynomial message size and computation.
All previous approaches obtained sub-optimal results and used resolve rules that looked only at the immediate children in the EIG (\emph{Exponential Information Gathering}) tree. At the heart of our solution are new resolve rules that look at multiple layers of the EIG tree.