# Optimally Efficient Multi-Valued {B}yzantine Agreement

## Matthias Fitzi and Martin Hirt

```
```All known protocols for Byzantine agreement (BA) among $n$ players
require the message to be communicated at least $\Omega(n^2)$ times,
which results in an overall communication complexity of at least
$\Omega(\ell n^2)$ bits for an $\ell$-bit message. We present the first
BA protocol in which the message is communicated only $\O(n)$ times (the
hidden factor is less than $2$). More concretely, for a given
synchronous broadcast protocol which communicates $\BC(\sell)$ bits for
reaching agreement on a $\sell$-bit message with security parameter
$\kappa$, our construction yields a synchronous BA protocol with
communication complexity $\O(\ell n+n\BC(n+\kappa))$ bits. Our reduction
is information theoretically secure and tolerates up to $t<n/2$ corrupted
players, which is optimal for the consensus variant of BA. Although this
resilience is not optimal for the broadcast (Byzantine generals) variant,
it is sufficient for most distributed applications that involve BA
protocols since they typically require $t<n/2$.