Welcome to the resource topic for 2017/063
Title:
Optimal Extension Protocols for Byzantine Broadcast and Agreement
Authors: Chaya Ganesh, 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.
ePrint: https://eprint.iacr.org/2017/063
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .