Optimally Efficient Multi-Valued Byzantine Agreement

Matthias Fitzi and Martin Hirt

Proc. 25th ACM Symposium on Principles of Distributed Computing — PODC 2006, ACM, Jul 2006.

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 $\mathcal{BC}(\ell)$ bits for reaching agreement on a $\ell$-bit message with security parameter $\kappa$, our construction yields a synchronous BA protocol with communication complexity $\O(\ell n+n\mathcal{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$.

BibTeX Citation

@inproceedings{FitHir06,
    author       = {Matthias Fitzi and Martin Hirt},
    title        = {Optimally Efficient Multi-Valued {B}yzantine Agreement},
    editor       = {Dahlia Malkhi},
    booktitle    = {Proc.~25th {ACM} Symposium on Principles of Distributed Computing --- PODC 2006},
    year         = {2006},
    month        = {7},
    publisher    = {ACM},
}