Paper 2017/063

Optimal Extension Protocols for Byzantine Broadcast and Agreement

Chaya Ganesh and Arpita Patra

Abstract

The problems 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. While the communication optimality has remained the most sought-after property of an extension protocol in the literature, we prioritize both communication and round optimality in this work. 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(\ell n)$ bits for a message of length $\ell$ 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 than our protocols, or achieve optimal round complexity at the cost of sub-optimal communication. Specifically, we construct communication-optimal protocols in the three corruption scenarios with the following round complexities: 1. $t<n/3$: $3$ rounds, improving over $O(\sqrt{\ell} + n^2)$ 2. $t<n/2$: $5$ rounds, improving over $6$ 3. $t<n$: $O(n)$ rounds, improving over $O(n^2)$ A concrete protocol from an extension protocol is obtained by replacing the seed broadcasts with a BB protocol for a single bit. Our extension protocols minimize the seed-round complexity and seed-communication complexity. The former refers to the number of rounds in an extension protocol in which seed broadcasts are invoked and impacts the round complexity of a concrete protocol due to a number of sequential calls to bit broadcast. The latter refers to the number of bits communicated through the seed broadcasts and impacts the round and communication complexity due to parallel instances of single-bit broadcast. In the settings of $t<n/3$, $t<n/2$ and $t<n$, our protocols improve the seed-round complexity from $O(\sqrt{\ell} + n^2)$ to $1$, from $3$ to $2$ and from $O(n^2)$ to $O(n)$ respectively. Our protocols keep the seed-communication complexity independent of the message length $\ell$ and, either improve or keep the complexity almost in the same order compared to the existing protocols.

Note: Minor fix to t<n/2 BA protocol. Earlier version allowed the adversary to make the honest parties communicate more than $O(\ell n)$ bits.