Paper 2009/433

Communication Optimal Multi-Valued Asynchronous Byzantine Agreement with Optimal Resilience

Arpita Patra and C. Pandu Rangan

Abstract

Byzantine Agreement (BA) and Broadcast (BC) are considered to be the most fundamental primitives for fault-tolerant distributed computing and cryptographic protocols. An important variant of BA and BC is Asynchronous Byzantine Agreement (ABA) and Asynchronous Broadcast (called as A-cast) respectively. Most often in the literature, protocols for ABA and A-cast were designed for a single bit message. But in many applications, these protocols may be invoked on long message rather than on single bit. Therefore, it is important to design efficient multi-valued protocols (i.e. protocols with long message) which extract advantage of directly dealing with long messages and are far better than multiple invocations to existing protocols for single bit. In synchronous network settings, this line of research was initiated by Turpin and Coan and later it is culminated in the result of Fitzi et al. who presented the first ever communication optimal multi-valued BA and BC protocols with the help of BA and BC protocols for short message. It was left open by Fitzi et al. to achieve the same in asynchronous settings. Recently Patra et al. presented a communication optimal multi-valued A-cast using existing A-cast of Brach for small message. Here we achieve the same for ABA which is known to be harder problem than A-cast. Specifically, we design a communication optimal, optimally resilient multi-valued ABA protocol, based on the existing ABA protocol for short message.