Closing the Efficiency Gap Between Synchronous and Network-Agnostic Consensus

Closing the Efficiency Gap Between Synchronous and Network-Agnostic Consensus

---

연구 분야: Networking

---

---

학회: Annual International Conference on the Theory and Applications of Cryptographic Techniques

---

초록

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 corrupt parties. Synchronous ones can tolerate 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 corruptions with synchrony and without, under provably optimal assumptions and . 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 -bit inputs, and can be extended to achieve communication complexity under the assumptions for which this is known to be possible for purely synchronous protocols.

---