  Byzantine agreement enables n processes to agree on a common L-bit value,
despite up to t > 0 arbitrary failures. A long line of work has been dedicated
to improving the bit complexity of Byzantine agreement in synchrony. This has
culminated in COOL, an error-free (deterministically secure against a
computationally unbounded adversary) solution that achieves O(nL + n^2 logn)
worst-case bit complexity (which is optimal for L > n logn according to the
Dolev-Reischuk lower bound). COOL satisfies strong validity: if all correct
processes propose the same value, only that value can be decided.
  Strong validity is, however, not appropriate for today's state machine
replication (SMR) and blockchain protocols. These systems value progress and
require a decided value to always be valid, excluding default decisions (such
as EMPTY) even in cases where there is no unanimity a priori. Validated
Byzantine agreement satisfies this property (called external validity). Yet,
the best error-free (or even signature-free) validated agreement solutions
achieve only O(n^2L) bit complexity, a far cry from the Omega(nL + n^2)
Dolev-Reishcuk lower bound. In this paper, we present two new synchronous
algorithms for validated Byzantine agreement, HashExt and ErrorFreeExt, with
different trade-offs. Both algorithms are (1) signature-free, (2) optimally
resilient (tolerate up to t < n / 3 failures), and (3) early-stopping
(terminate in O(f+1) rounds, where f <= t is the actual number of failures). On
the one hand, HashExt uses only hashes and achieves O(nL + n^3 kappa) bit
complexity, which is optimal for L > n^2 kappa (where kappa is the size of a
hash). On the other hand, ErrorFreeExt is error-free, using no cryptography
whatsoever, and achieves O( (nL + n^2) logn ) bit complexity, which is
near-optimal for any L.
