Proof of Space from Stacked Expanders
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
- PDF / 732,588 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 20 Downloads / 196 Views
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.
1
Introduction
Proof of work (PoW) has found applications in spam/denial-of-service countermeasures [13,22] and in the famous cryptocurrency Bitcoin [36]. However, the traditional hash-based PoW does have several drawbacks, most notably poor resistance to application-specific integrated circuits (ASIC). ASIC hash units easily offer ∼ 100 × speedup and ∼ 10, 000 × energy efficiency over CPUs. This gives ASIC-equipped adversaries a huge advantage over common desktop/laptop users. Recently, proof of space (PoS) [11,24] has been suggested as a potential alternative to PoW to address this problem. A PoS is a protocol between two parties, a prover and a verifier. Analogous to (but also in contrast to) PoW, the prover generates a cryptographic proof that it has invested a significant amount of memory or disk space (as opposed to computation), and the proof should be easy for the verifier to check. It is believed that if an ASIC has to access a large external memory, its advantage over a CPU will be small, making PoS more egalitarian than PoW. Somewhat unfortunately, two competing definitions of “proof of space” have been proposed [11,24] with very different security guarantees and applications. Adding to the confusion are other closely related and similar-sounding notions c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part I, LNCS 9985, pp. 262–285, 2016. DOI: 10.1007/978-3-662-53641-4 11
Proof of Space from Stacked Expanders
263
such as memory-hard functions (MHF) [39], proof of secure erasure (PoSE) [40], provable data possession (PDP) [12] and proof of retrievability (PoR) [30]. A first goal of this paper is to clarify the connections and differences between these notions. Section 2 will give detailed comparisons. For now, we give a short summary below
Data Loading...
