Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity

In this paper we present first ever

error-free, asynchronous

broadcast (called as A-cast) and Byzantine Agreement (called as ABA) protocols with optimal communication complexity and fault tolerance. Our protocols are multi-valued, meaning that they deal with ℓ bit input and achieve communication complexity of

${\mathcal O}(n\ell)$

bits for large enough ℓ for a set of

n

 ≥ 3

t

 + 1 parties in which at most

t

can be Byzantine corrupted. Previously, Patra and Rangan (Latincrypt’10, ICITS’11) reported multi-valued, communication optimal A-cast and ABA protocols

that are only probabilistically correct

.

Following all the previous works on multi-valued protocols, we too follow reduction-based approach for our protocols, meaning that our protocols are designed given existing A-cast and ABA protocols for small message (possibly for single bit). Our reductions invoke less or equal number of instances of protocols for single bit in comparison to the reductions of Patra and Rangan. Furthermore, our reductions run in constant expected time, in contrast to

${\mathcal O}(n)$

of Patra and Rangan (ICITS’11). Also our reductions are much simpler and more elegant than their reductions.

By adapting our techniques from asynchronous settings, we present new

error-free

, communication optimal reduction-based protocols for broadcast (BC) and Byzantine Agreement (BA) in synchronous settings that are constant-round and call for only

$\mathcal O(n^2)$

instances of protocols for single bit. Prior to this, communication optimality has been achieved by Fitzi and Hirt (PODC’06) who proposed

probabilistically correct

multi-valued BC and BA protocols with constant-round and

${\mathcal O}(n(n+\kappa))$

(

κ

is the error parameter) invocations to the single bit protocols. Recently, Liang and Vaidya (PODC’11) achieved the same

without

error probability. However, their reduction calls for round complexity and number of instances that are function of the message size,

${\mathcal O}(\sqrt{\ell} + n^2)$

and

${\mathcal O}(n^2\sqrt{\ell} + n^4)$

, respectively where ℓ = Ω(

n

6

).