Proofs of space: simplified and optimized
by Pavel Hubáček, Michal Koucký, and Bruno Loff


A proof of space is a protocol where one player, called the prover, must convince another player, called the verifier, that he has set aside some memory which is free to be used.

During the initialization stage, the prover commits to a certain amount of memory, and at any later time the verifier comes along and asks the prover to convince him that this amount of memory is still available. The protocol is correct if, in order to succeed in convincing the verifier, the prover actually needs to reserve as much memory as he committed to.

Here is an example of a simple protocol: if the prover wishes to commit to N bits of memory, then, during the initialization stage, the verifier sends to the prover a random N-bit string. The verifier remembers this string, and during the verification phase he picks a few random locations, sends them over (at a communication cost of log N bits each), and the verifier returns the bits at those positions.

This works because a random string is incompressible, so if the prover has cheated by storing, say, only half of the string, then he will fail to answer a random query with probability at least 1/2. Then, if the verifier queries the string at 2 × log( 1/ δ ) random locations, this will cause the verifier to catch a cheating prover with probability 1 - δ.

The problem with this scheme is that the initialization stage incurs a communication cost in the order of N, and the verifier must spend as much memory as the prover in order to succeed.

Generally speaking, a proof of space is efficient if the communication in either stage is small, and the verifier needs to remember very little information in order to play his part in the verification stage.

Several asymptotically efficient schemes have been proposed for this task [ABFG'14, DFKP'15], and a blockchain-based mechanism for distributed consensus has been devised to work on top of such proofs of space [PPK+'15]. This would allow, for example, for bitcoin to be based on hard-disk space as a basic resource, instead of CPU cycles, thus making it more energy-efficient.

However, the proposed schemes rely on super-concentrators, graph constructions that are asymptotically efficient but practically unusable due to the large constants involved.

We present a new, much simpler scheme that avoids super-concentrators entirely, and uses only the sparse graphs with many long paths of [EGS'75], which were already used in a more complicated way in a previous construction [DFKP'15].

This already makes our schemes possible to use; to make them actually practical, and potentially applicable and implementable, we present a "local" variant of the sparse graphs with many long paths construction, which will significantly scale down the size of the proof.




[EGS'75] P. Erdös, R.L. Graham, E. Szemerédi. On sparse graphs with dense long paths. Computers & Mathematics with Applications, 1975.

[ABFG'14] Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, and Nicola Galesi. Proofs of Space: When Space is of the Essence. SCN 2014.

[DFKP'15] Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space, CRYPTO 2015.

[PPK+'15] Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Joel Alwen, Georg Fuchsbauer, and Peter Gazi. Spacemint: A Cryptocurrency Based on Proofs of Space. Preprint at https://eprint.iacr.org/2015/528.pdf.