Paper 2024/317

Closing the Efficiency Gap between Synchronous and Network-Agnostic Consensus

Giovanni Deligios, ETH Zurich
Mose Mizrahi Erbes, ETH Zurich

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 $2t_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 asymptotic 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 $\ell$-bit inputs, and can be extended to achieve communication complexity $O(n^2\kappa + \ell n)$ under the assumptions for which this is known to be possible for purely synchronous protocols.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
Network-AgnosticConsensusAsynchronous FallbackByzantine Agreement
Contact author(s)
gdeligios @ ethz ch
mmizrahi @ ethz ch
2024-02-29: revised
2024-02-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giovanni Deligios and Mose Mizrahi Erbes},
      title = {Closing the Efficiency Gap between Synchronous and Network-Agnostic Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2024/317},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.