  Authorization is challenging in distributed systems that cannot rely on the
identification of nodes. Proof-of-work offers an alternative gate-keeping
mechanism, but its probabilistic nature is incompatible with conventional
security definitions. Recent related work establishes concrete bounds for the
failure probability of Bitcoin's sequential proof-of-work mechanism. We propose
a family of state replication protocols using parallel proof-of-work. Our
bottom-up design from an agreement sub-protocol allows us to give concrete
bounds for the failure probability in adversarial synchronous networks. After
the typical interval of 10 minutes, parallel proof-of-work offers two orders of
magnitude more security than sequential proof-of-work. This means that state
updates can be sufficiently secure to support commits after one block (i.e.,
after 10 minutes), removing the risk of double-spending in many applications.
We offer guidance on the optimal choice of parameters for a wide range of
network and attacker assumptions. Simulations show that the proposed
construction is robust against violations of design assumptions.
