[Resource Topic] 2020/142: TARDIGRADE: An Atomic Broadcast Protocol for Arbitrary Network Conditions

Welcome to the resource topic for 2020/142

TARDIGRADE: An Atomic Broadcast Protocol for Arbitrary Network Conditions

Authors: Erica Blum, Jonathan Katz, Julian Loss


We study the problem of 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 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 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.

ePrint: https://eprint.iacr.org/2020/142

Talk: https://www.youtube.com/watch?v=vvoq6JxJcNI

Slides: https://iacr.org/submit/files/slides/2021/asiacrypt/asiacrypt2021/42/slides.pdf

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 .