Paper 2018/678

PoReps: Proofs of Space on Useful Data

Ben Fisch

Abstract

A proof-of-replication (PoRep) is an interactive proof system in which a prover defends a publicly verifiable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data file. In this sense a PoRep is both a proof of space (PoS) and a proof of retrievability (PoR). This paper is a foundational study of PoReps, exploring both their capabilities and their limitations. While PoReps may unconditionally demonstrate possession of data, they fundamentally cannot guarantee that the data is stored redundantly. Furthermore, as PoReps are proofs of space, they must rely either on rational time/space tradeoffs or timing bounds on the online prover's runtime. We introduce a rational security notion for PoReps called epsilon-rational replication based on the notion of an epsilon-Nash equilibrium, which captures the property that a server does not gain any significant advantage by storing its data in any other (non-redundant) format. We apply our definitions to formally analyze two recently proposed PoRep constructions based on verifiable delay functions and depth robust graphs. Lastly, we reflect on a notable application of PoReps---its unique suitability as a Nakamoto consensus mechanism that replaces proof-of-work with PoReps on real data, simultaneously incentivizing and subsidizing the cost of file storage.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
proofs of storageproofs of spaceproofs of retrievabilityformal modelingfoundationsrational securityinteractive protocols
Contact author(s)
benafisch @ gmail com
History
2018-07-18: revised
2018-07-16: received
See all versions
Short URL
https://ia.cr/2018/678
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/678,
      author = {Ben Fisch},
      title = {PoReps: Proofs of Space on Useful Data},
      howpublished = {Cryptology ePrint Archive, Paper 2018/678},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/678}},
      url = {https://eprint.iacr.org/2018/678}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.