  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 $\Delta$) 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$.
