Closing The Efficiency Gap Between Synchronous and Network-Agnostic Consensus

Giovanni Deligios and Mose Mizrahi Erbes

Eurocrypt, May 2024.

In the consensus problem, $n$ parties want to agree on a common value, even if some of them are corrupt and arbitrarily misbehave. If the parties have a common input $m$ , then they must agree on $m$ .

Protocols solving consensus assume either a synchronous communication network, where messages are delivered within a known time, or an asynchronous network with arbitrary delays. Asynchronous protocols only tolerate $t_{a} < n / 3$ corrupt parties. Synchronous ones can tolerate $t_{s} < n / 2$ corruptions with setup, but their security completely breaks down if the synchrony assumptions are violated.

Network-agnostic consensus protocols, as introduced by Blum, Katz, and Loss [TCC'19], are secure regardless of network conditions, tolerating up to $t_{s}$ corruptions with synchrony and $t_{a}$ without, under provably optimal assumptions $t_{a} \leq t_{s}$ and $2 t_{s} + t_{a} < n$ . Despite efforts to improve their efficiency, all known network-agnostic protocols fall short of the asymptotic complexity of state-of-the-art purely synchronous protocols.

In this work, we introduce a novel technique to compile any synchronous and any asynchronous consensus protocols into a network-agnostic one. This process only incurs a small constant number of overhead rounds, so that the compiled protocol matches the optimal round complexity for synchronous protocols. Our compiler also preserves under a variety of assumptions the asymptomatic communication complexity of state-of-the-art synchronous and asynchronous protocols. Hence, it closes the current efficiency gap between synchronous and network-agnostic consensus.

As a plus, our protocols support $ℓ$ -bit inputs, and can be extended to achieve communication complexity $O (n^{2} k + ℓ n)$ under the assumptions for which this is known to be possible for purely synchronous protocols.

BibTeX Citation

@inproceedings{DeEr24,
    author       = {Giovanni Deligios and {Mose Mizrahi} {Erbes}},
    title        = {Closing The Efficiency Gap Between Synchronous and Network-Agnostic Consensus},
    booktitle    = {Eurocrypt},
    year         = {2024},
    month        = {5},
}