Synchronous Byzantine Agreement With <i>O</i>(<i>n</i>) Messages and <i>O</i>(1) Expected Time

Byzantine agreement is the most fundamental primitive in distributed computing. All known Byzantine agreement protocols achieve quadratic or sub-quadratic messages and communication. We show that surprisingly, by directly assuming a random leader election oracle (that can be built from the verifiable random function), threshold signatures, and the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1/3$ </tex-math></inline-formula> corruption bound, we can build Linear-BA, a binary agreement (BA) that has linear message complexity, constant expected time complexity, and a normal case that has linear communication. We extend Linear-BA to construct Linear-MBA, a multi-valued Byzantine agreement (MBA) protocol also with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n)$ </tex-math></inline-formula> messages and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(1)$ </tex-math></inline-formula> expected time. Finally, we present Linear-MBA-SV, an MBA protocol with the strong validity property via a no-cost transformation from Linear-MBA. All the protocols above are secure under a static adversary, where a static adversary corrupts a set of replicas at the beginning of the protocol. We go on and show an impossibility result that in the adaptive adversary model (in which the adversary can selectively corrupt the replicas while the protocol is running), one cannot build a Byzantine agreement protocol with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n)$ </tex-math></inline-formula> messages and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(1)$ </tex-math></inline-formula> expected time. Accordingly, we revise our protocol to obtain Byzantine agreement protocols with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n)$ </tex-math></inline-formula> messages per round and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n)$ </tex-math></inline-formula> time. Our results offer a fresh view of what is needed for linear Byzantine agreement: by examining the “needed” assumptions, one can identify the performance bottlenecks for Byzantine agreement. Meanwhile, all our protocols are efficient, as all the building blocks have efficient instantiations.