Paper 2016/333

Proof of Space from Stacked Expanders

Ling Ren and Srinivas Devadas

Abstract

Recently, proof of space (PoS) has been suggested as a more egalitarian alternative to the traditional hash-based proof of work. In PoS, a prover proves to a verifier that it has dedicated some specified amount of space. A closely related notion is memory-hard functions (MHF), functions that require a lot of memory/space to compute. While making promising progress, existing PoS and MHF have several problems. First, there are large gaps between the desired space-hardness and what can be proven. Second, it has been pointed out that PoS and MHF should require a lot of space not just at some point, but throughout the entire computation/protocol; few proposals considered this issue. Third, the two existing PoS constructions are both based on a class of graphs called superconcentrators, which are either hard to construct or add a logarithmic factor overhead to efficiency. In this paper, we construct PoS from stacked expander graphs. Our constructions are simpler, more efficient and have tighter provable space-hardness than prior works. Our results also apply to a recent MHF called Balloon hash. We show Balloon hash has tighter space-hardness than previously believed and consistent space-hardness throughout its computation.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in TCC 2016
Keywords
Proof of spacegraph pebbling
Contact author(s)
renling @ mit edu
History
2016-08-25: last of 2 revisions
2016-03-25: received
See all versions
Short URL
https://ia.cr/2016/333
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/333,
      author = {Ling Ren and Srinivas Devadas},
      title = {Proof of Space from Stacked Expanders},
      howpublished = {Cryptology ePrint Archive, Paper 2016/333},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/333}},
      url = {https://eprint.iacr.org/2016/333}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.