  Proof-of-work (PoW) is an algorithmic tool used to secure networks by
imposing a computational cost on participating devices. Unfortunately,
traditional PoW schemes require that correct devices perform computational work
perpetually, even when the system is not under attack.
  We address this issue by designing a general PoW protocol that ensures two
properties. First, the network stays secure. In particular, the fraction of
identities in the system that are controlled by an attacker is always less than
1/2. Second, our protocol's computational cost is commensurate with the cost of
an attacker. In particular, the total computational cost of correct devices is
a linear function of the attacker's computational cost plus the number of
correct devices that have joined the system. Consequently, if the network is
attacked, we ensure security with cost that grows linearly with the attacker's
cost; and, in the absence of attack, our computational cost remains small. We
prove similar guarantees for bandwidth cost.
  Our results hold in a dynamic, decentralized system where participants join
and depart over time, and where the total computational power of the attacker
is up to a constant fraction of the total computational power of correct
devices. We demonstrate how to leverage our results to address important
security problems in distributed computing including: Sybil attacks, Byzantine
consensus, and Committee election.
