Paper 2013/805

Proofs of Space: When Space is of the Essence

Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, and Nicola Galesi

Abstract

Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO ’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPU-bound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses. In this paper we put forward a new concept dubbed proof of space. To compute such a proof, the prover must use a specified amount of space, i.e., we are not interested in the number of accesses to the main memory (as in memory-bound proof of work) but rather on the amount of actual memory the prover must employ to compute the proof. We give a complete and detailed algorithmic description of our model. We develop a comprehensive theoretical analysis which uses combinatorial tools from Complexity Theory (such as pebbling games) which are essential in studying space lower bounds.

Note: -

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. SCN 2014
Keywords
Space ComplexityProof of WorkPebbling GameRandom Oracle Model
Contact author(s)
afaonio @ gmail com
History
2014-07-03: last of 9 revisions
2013-12-03: received
See all versions
Short URL
https://ia.cr/2013/805
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/805,
      author = {Giuseppe Ateniese and Ilario Bonacina and Antonio Faonio and Nicola Galesi},
      title = {Proofs of Space: When Space is of the Essence},
      howpublished = {Cryptology ePrint Archive, Paper 2013/805},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/805}},
      url = {https://eprint.iacr.org/2013/805}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.