Proof of Work Without All the Work

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. That is, 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 is 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 show how to leverage our results to address important security problems in distributed computing including: Sybil attacks, Byzantine Consensus, and Committee Election.