Proof of space from stacked expanders

Ling Ren, Srinivas Devadas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
EditorsAdam Smith, Martin Hirt
PublisherSpringer
Pages262-285
Number of pages24
ISBN (Print)9783662536407
DOIs
StatePublished - 2016
Externally publishedYes
Event14th International Conference on Theory of Cryptography, TCC 2016-B - Beijing, China
Duration: Oct 31 2016Nov 3 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9985 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Theory of Cryptography, TCC 2016-B
Country/TerritoryChina
CityBeijing
Period10/31/1611/3/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Proof of space from stacked expanders'. Together they form a unique fingerprint.

Cite this