Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2) Messages, and Constant Time

This paper presents a new algorithm that reduces multivalued consensus to binary consensus in an asynchronous message-passing system made up of

n

processes where up to

t

may commit Byzantine failures. This algorithm has the following noteworthy properties: it assumes

t

 < 

n

/3 (and is consequently optimal from a resilience point of view), uses

O

(

n

2

) messages, has a constant time complexity, and does not use signatures. The design of this reduction algorithm relies on two new all-to-all communication abstractions. The first one allows the non-faulty processes to reduce the number of proposed values to

c

, where

c

is a small constant. The second communication abstraction allows each non-faulty process to compute a set of (proposed) values such that, if the set of a non-faulty process contains a single value, then this value belongs to the set of any non-faulty process. Both communication abstractions have an

O

(

n

2

) message complexity and a constant time complexity. The reduction of multivalued Byzantine consensus to binary Byzantine consensus is then a simple sequential use of these communication abstractions. To the best of our knowledge, this is the first asynchronous message-passing algorithm that reduces multivalued consensus to binary consensus with

O

(

n

2

) messages and constant time complexity (measured with the longest causal chain of messages) in the presence of up to

t

 < 

n

/3 Byzantine processes, and without using cryptography techniques. Moreover, this reduction algorithm uses a single instance of the underlying binary consensus, and tolerates message re-ordering by Byzantine processes.