TY - GEN
T1 - Proof of space from stacked expanders
AU - Ren, Ling
AU - Devadas, Srinivas
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84994404386&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994404386&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-53641-4_11
DO - 10.1007/978-3-662-53641-4_11
M3 - Conference contribution
AN - SCOPUS:84994404386
SN - 9783662536407
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 262
EP - 285
BT - Theory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
A2 - Smith, Adam
A2 - Hirt, Martin
PB - Springer
T2 - 14th International Conference on Theory of Cryptography, TCC 2016-B
Y2 - 31 October 2016 through 3 November 2016
ER -