Paper 2017/203

Proofs of Useful Work

Marshall Ball, Alon Rosen, 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. Note: An updated version of this paper is available at https://eprint.iacr.org/2018/559. The update is to accommodate the fact (pointed out by anonymous reviewers) that the definition of Proof of Useful Work in this paper is already satisfied by a generic naive construction.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2018
Keywords
Proofs of workFine-GrainedDelegationBlockchain
Contact author(s)
marshallball @ gmail com
alon rosen @ idc ac il
msabin @ berkeley edu
prashantv91 @ gmail com
History
2021-02-26: last of 2 revisions
2017-03-01: received
See all versions
Short URL
https://ia.cr/2017/203
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/203,
      author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan},
      title = {Proofs of Useful Work},
      howpublished = {Cryptology ePrint Archive, Paper 2017/203},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/203}},
      url = {https://eprint.iacr.org/2017/203}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.