Network-Agnostic State Machine Replication
This work addresses the challenge of SMR for blockchain protocols by providing a flexible solution that works across different network types, though it is incremental in improving fault tolerance tradeoffs.
The paper tackles the problem of state machine replication (SMR) in the presence of malicious adversaries by designing a network-agnostic protocol that adapts to network conditions, achieving optimal tradeoffs between tolerating t_s corrupted parties in synchronous networks and t_a ≤ t_s in asynchronous networks.
We study the problem of 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 synchronous network (where all messages are delivered within some known time $Δ$) or an asynchronous network (where messages can be delayed arbitrarily). 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. 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$.