Welcome to the resource topic for 2024/317
Title:
Closing the Efficiency Gap between Synchronous and Network-Agnostic Consensus
Authors: Giovanni Deligios, Mose Mizrahi Erbes
Abstract: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 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 \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.
ePrint: https://eprint.iacr.org/2024/317
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .