Cryptology ePrint Archive: Report 2017/203

Proofs of Useful Work

Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan

Abstract: We give Proofs of Work (PoWs) whose hardness is based on a wide array of computational problems, including Orthogonal Vectors, 3SUM, All-Pairs Shortest Path, and any problem that reduces to them (this includes deciding any graph property that is statable in first-order logic). This results in PoWs whose completion does not waste energy but instead is useful for the solution of computational problems of practical interest.

The PoWs that we propose are based on delegating the evaluation of low-degree polynomials originating from the study of average-case fine-grained complexity. We prove that, beyond being hard on the average (based on worst-case hardness assumptions), the task of evaluating our polynomials cannot be amortized across multiple~instances.

For applications such as Bitcoin, which use PoWs on a massive scale, energy is typically wasted in huge proportions. We give a framework that can utilize such otherwise wasteful work.

Category / Keywords: Proofs of work, Fine-Grained, Delegation, Blockchain

Date: received 27 Feb 2017, last revised 28 Feb 2017

Contact author: msabin at berkeley edu, marshallball@gmail com, alon rosen@idc ac il, prashantv91@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170301:001609 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]