Publication
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 + n2 log n) worst-case bit complexity (which is optimal for L ≥ n log n according to the Dolev-Reischuk lower bound). COOL satisfies strong unanimity: if all correct processes propose the same value, only that value can be decided. Whenever correct processes do not agree a priori (there is no unanimity), they may decide a default value ⊥ from COOL. Strong unanimity is, however, not sufficient for today’s state machine replication (SMR) and blockchain protocols. These systems value progress and require a decided value to always be valid (according to a predetermined predicate), excluding default decisions (such as ⊥) 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(n2L) bit complexity, a far cry from the Ω(nL + n2) Dolev-Reischuk lower bound. Is it possible to bridge this complexity gap? We answer the question affirmatively. Namely, 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 denotes the actual number of failures). On the one hand, HashExt uses only hashes and achieves O(nL + n3κ) bit complexity, which is optimal for L ≥ n2κ (where κ is the size of a hash). On the other hand, ErrorFreeExt is error-free, using no cryptography whatsoever, and achieves O((nL + n2) log n) bit complexity, which is near-optimal for any L.