Paper 2017/063

Optimal Extension Protocols for Byzantine Broadcast and Agreement

Chaya Ganesh and Arpita Patra

Abstract

The problem of Byzantine Broadcast (BB) and Byzantine Agreement (BA) are of interest to both distributed computing and cryptography community. Extension protocols for these primitives have been introduced to handle long messages efficiently at the cost of small number of single-bit broadcasts, referred to as seed broadcasts. The communication optimality has remained the most sought-after property of an extension protocol in the literature. In this paper, we prioritize both communication and round optimality. A concrete protocol from an extension protocol is obtained by replacing the seed broadcasts with a BB protocol for single bit. Towards building concrete protocols efficient both in terms of communication and round, we minimize the seed round complexity of the extension protocols, where this measure refers to the number of rounds in which seed broadcasts are invoked in an extension protocol. In a setting with $n$ parties and an adversary controlling at most $t$ parties in Byzantine fashion, we present BB and BA extension protocols with $t<n$, $t < n/2$ and $t<n/3$ that are simultaneously optimal in terms of communication and round complexity. The best communication that an extension protocol can achieve in any setting is $O(l n)$ bits for a message of length $l$ bits. The best achievable round complexity is $O(n)$ for the setting $t< n$ and $O(1)$ in the other two settings $t < n/2$ and $t<n/3$. The existing constructions are either optimal only in terms of communication complexity, or require more rounds as well as seed rounds than our protocols, or achieve optimal round complexity at the cost of sub-optimal communication. Specifically, we construct communication-optimal protocols in the following three settings with the following round and seed round complexities: $t<n/3$: Our protocol requires three rounds and a single seed round. The best known protocol in this setting is only communication optimal and requires a round complexity and a seed round complexity of $\Omega(n^3)$. $t<n/2$: Our protocol provides a round complexity of $5$ and a seed round complexity of one. The best known protocol in this setting requires a round complexity of $6$ and a seed round complexity of $3$. $t<n$: Our protocol has a round as well as a seed round complexity of $O(n)$. The same complexities for the best known protocol in this domain are $O(n^2)$.