CISPA
Browse
cispa_all_3567.pdf (383.17 kB)

Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions

Download (383.17 kB)
conference contribution
posted on 2023-11-29, 18:18 authored by Erica Blum, Jonathan Katz, Julian LossJulian Loss
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. %Although protocols for the latter case give seemingly stronger guarantees, this is not the case since they (inherently) tolerate a lower fraction of corrupted parties. \smallskip We design an atomic broadcast protocol (
ame) 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
ame~achieves optimal tradeoffs between $t_s$ and~$t_a$. Finally, we show a second protocol (
ametwo) with similar (but slightly weaker) guarantees that achieves per-transaction communication complexity linear in~$n$.

History

Preferred Citation

Erica Blum, Jonathan Katz and Julian Loss. Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2021.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

Legacy Posted Date

2022-01-05

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3567, title = "Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions", author = "Blum, Erica and Katz, Jonathan and Loss, Julian", booktitle="{International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC