2017/08/03 by Diksha Gupta, Jared Saia, Gupta, Diksha +3 · 1 voice · 1 citation
Computer Science · #Algorithm #Blockchain #Computational complexity theory #Computer science #Computer security #Distributed computing #Fraction (chemistry) #Function (biology) #Internet Traffic Analysis and Secure E-voting #Leverage (statistics) #Network Security and Intrusion Detection #Proof-of-work system #Protocol (science) #Spam and Phishing Detection #cs.CR #cs.DC
paper · pdf · doi:10.48550/arxiv.1708.01285
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2017/08/03 · arxiv created 2018/02/17 · arxiv updated 2018/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.