Cryptology ePrint Archive: Report 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.
Category / Keywords: cryptographic protocols / Proof of space, graph pebbling
Original Publication (in the same form): IACR-TCC-2016
Date: received 25 Mar 2016, last revised 24 Aug 2016
Contact author: renling at mit edu
Available format(s): PDF | BibTeX Citation
Version: 20160825:041842 (All versions of this report)
Short URL: ia.cr/2016/333
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]