Paper 2020/142
Network-Agnostic State Machine Replication
Erica Blum and Jonathan Katz and Julian Loss
Abstract
We study the problem of $\textit{state machine replication}$ (SMR) -- the underlying problem addressed by blockchain protocols -- in the presence of a malicious adversary who can corrupt some fraction of the parties running the protocol. Existing protocols for this task assume either a $\textit{synchronous network}$ (where all messages are delivered within some known time $\Delta$) or an $\textit{asynchronous network}$ (where messages can be delayed arbitrarily). Although protocols for the latter case give seemingly stronger guarantees, in fact they are incomparable since they (inherently) tolerate a lower fraction of corrupted parties. We design an SMR protocol that is network-agnostic in the following sense: if it is run in a synchronous network, it tolerates $t_s$ corrupted parties; if the network happens to be asynchronous it is resilient to $t_a\leq t_s$ faults. Our protocol achieves optimal tradeoffs between $t_s$ and $t_a$.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Published elsewhere. arxiv.org
- Keywords
- consensusblockchain
- Contact author(s)
- erblum @ cs umd edu,jkatz2 @ gmail com,lossjulian @ gmail com
- History
- 2021-09-23: last of 7 revisions
- 2020-02-10: received
- See all versions
- Short URL
- https://ia.cr/2020/142
- License
-
CC BY