International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions

Authors:
Erica Blum , University of Maryland College Park
Jonathan Katz , University of Maryland College Park
Julian Loss , University of Maryland College Park
Download:
DOI: 10.1007/978-3-030-92075-3_19
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: We study the problem of \emph{atomic broadcast}---the underlying problem addressed by blockchain protocols---in the presence of a malicious adversary who corrupts some fraction of the $n$ parties running the protocol. Existing protocols are either robust for any number of corruptions in a \emph{synchronous} network (where messages are delivered within some known time~$\Delta$) but fail if the synchrony assumption is violated, or tolerate fewer than $n/3$ corrupted parties in an \emph{asynchronous} network (where messages can be delayed arbitrarily) and cannot tolerate more corruptions even if the network happens to be well behaved. We design an atomic broadcast protocol (TARDIGRADE) that, for any $t_s \geq t_a$ with $2t_s + t_a < n$, provides security against $t_s$ corrupted parties if the network is synchronous, while remaining secure when $t_a$ parties are corrupted even in an asynchronous network. We show that TARDIGRADE achieves optimal tradeoffs between $t_s$ and~$t_a$. Finally, we show a second protocol (UPGRADE) with similar (but slightly weaker) guarantees that achieves per-transaction communication complexity linear in~$n$.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31388,
  title={Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92075-3_19},
  author={Erica Blum and Jonathan Katz and Julian Loss},
  year=2021
}