(2021) Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions.
|
Text
proceedings.pdf Download (392kB) | Preview |
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. %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 (\name) 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 \name~achieves optimal tradeoffs between $t_s$ and~$t_a$. Finally, we show a second protocol (\nametwo) with similar (but slightly weaker) guarantees that achieves per-transaction communication complexity linear in~$n$.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Julian Loss (JL) |
| Conference: | ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security |
| Depositing User: | Julian Loss |
| Date Deposited: | 05 Jan 2022 09:23 |
| Last Modified: | 05 Jan 2022 09:23 |
| Primary Research Area: | NRA2: Reliable Security Guarantees |
| URI: | https://publications.cispa.saarland/id/eprint/3567 |
Actions
Actions (login required)
 |
View Item |