Proof-of Work Without All the Work

When: Monday February 5, 2018
Where: PGH 232
Time: 11:00 AM – 12:00 PM

Speaker: Prof. Jared Saia

Host: Dr. Gopal Pandurangan

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.

Bio:

Jared Saia obtained his PhD from the University of Washington, and is now a professor at the University of New Mexico. His broad research interests are in theory and algorithms with strong interests in distributed computing, cybersecurity, game theory, and spectral methods. A general interest is determining how large groups can perform better than any of their members. He is the recipient of the NSF CAREER Award, the UNM School of Engineering Junior and Senior Faculty Research Excellence Awards, and several best paper awards.