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, 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 <= t_s faults. Our protocol achieves optimal tradeoffs between t_s and t_a.