Efficient and Adaptively Secure Consensus

Abstract

We study the problem of designing consensus protocols with improved latency that are secure when the adversarial conditions change during the course of the protocol. Typically, consensus protocols proceed in a series of communication rounds in which the parties exchange messages with each other or with certain designated parties, and the parties only commit a value at the end of these rounds. Thus, changing adversarial conditions may impede the progress or affect the safety conditions of the underlying consensus protocol. We improve the latency of consensus protocols under two types of adversarial settings.The first adversary is adaptive, in that it can choose which parties to corrupt during the course of the protocol execution and delay any messages for a finite amount of time. We present a simple framework for consensus that is efficient in the number of rounds till termination against such an adversary in an asynchronous network. In addition, we show new lower and upper bounds on the round complexity of some key primitives used for achieving adaptively secure asynchronous agreement.The second adversarial setting, known as dynamic availability, allows parties to join or leave the network at any time. In this setting, it is known that the latency should depend on a known pessimistic network delay, and it cannot depend on the speed of the network. In this setting, we present a protocol that achieves latency better than the pessimistic network delay assumption.