Network agnostic consensus in constant time

Simon Holmgaard Kamp; Julian Loss; Jesper Buus Nielsen

Paper 2025/228

Network agnostic consensus in constant time

Simon Holmgaard Kamp, Helmholtz Center for Information Security

Julian Loss, Helmholtz Center for Information Security

Jesper Buus Nielsen, Aarhus University

Abstract

Network agnostic protocols (Blum, Katz, Loss TCC `19) are consensus or MPC protocols that strike a balance between purely synchronous and asynchronous protocols. Given thresholds $t_{a}, t_{s}$ that satisfy $t_{a} < n / 3 < t_{s} < n / 2$ and $2 t_{s} + t_{a} < n$ , they have the unique property of remaining secure against an adversary that either (1) corrupts up to $t_{s}$ parties in a synchronous execution where all messages are delivered within a known bound $Δ$ or (2) corrupts up to $t_{a}$ in an asynchronous execution where messages can be delayed arbitrarily. All existing network agnostic protocols follow a design pattern which first attempts to run a synchronous path, and then switches to an asynchronous path as a fallback option if the synchronous path times out after some time due to the network being asynchronous. Unfortunately, has to be set conservatively to account for the possibility that the synchronous path might take an unusually long time even when the network is synchronous. As a result, for various basic tasks including Byzantine Agreement or MPC, no existing network agnostic protocol is able to terminate for all honest parties within constant expected time in \emph{all possible executions}. In this work, we introduce a new paradigm to construct network agnostic consensus that, for the first time, overcome this barrier. Using this new design pattern we first present simple protocols for reliable broadcast (RB) and binary agreement (BA) that are \emph{responsive} when no more than parties are corrupted and run in expected constant time regardless of the network conditions.\footnote{The latter was already possible for RB, which by design requires only constantly many constant rounds, but is not guaranteed to terminate for all parties.} We then extend our results to asynchronous common subset (ACS) and MPC. Notably, our approach \emph{reverses the order} of the synchronous and asynchronous path by designing protocols that are first and foremost asynchronous and only fall back to the synchronous execution path when more than parties are corrupted.

Note: This paper subsumes some of the results in 2023/1738.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Contact author(s): simon kamp @ cispa de
lossjulian @ gmail com
jbn @ cs au dk
History: 2025-02-19: revised; 2025-02-14: received; See all versions
Short URL: https://ia.cr/2025/228
License: CC BY

BibTeX

@misc{cryptoeprint:2025/228,
      author = {Simon Holmgaard Kamp and Julian Loss and Jesper Buus Nielsen},
      title = {Network agnostic consensus in constant time},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/228},
      year = {2025},
      url = {https://eprint.iacr.org/2025/228}
}