This article relies too much on references to primary sources. (March 2018) (Learn how and when to remove this template message)
Proof-of-space (PoSpace), also called proof-of-capacity (PoC), is a means of showing that one has a legitimate interest in a service (such as sending an email) by allocating a non-trivial amount of memory or disk space to solve a challenge presented by the service provider. The concept was formulated by Dziembowski et al. in 2015. (Ateniese et al.'s paper, while also titled Proof-of-space, is in fact a memory-hard proof-of-work protocol.)
Proofs of space are very similar to proofs of work, except that instead of computation, storage is used. Proof-of-space is related to, but also considerably different from, memory-hard functions and proofs of retrievability.
After the release of Bitcoin, alternatives to its PoW mining mechanism were researched and PoSpace was studied in the context of cryptocurrencies. Proofs of space are seen as a fairer and greener alternative due to the general-purpose nature of storage and the lower energy cost required by storage. Several theoretical and practical implementations of PoSpace have been released and discussed, such as SpaceMint and Burstcoin.
A proof-of-space is a piece of data that a prover sends to a verifier to prove that the prover has reserved a certain amount of space. For practicality, the verification process needs to be efficient, namely, consumes a small amount of space and time. For soundness, it should be hard for the prover to pass the verification if it does not actually reserve the claimed amount of space. One way of implementing PoSpace is by using hard-to-pebble graphs. The verifier asks the prover to build a labeling of a hard-to-pebble graph. The prover commits to the labeling. The verifier then asks the prover to open several random locations in the commitment.
Proofs of space could be used as an alternative to proofs of work in the traditional client puzzle applications such as anti-spam measures and denial of service attack prevention. Proof-of-Space has also been used for malware detection, by determining whether the L1 cache of a processor is empty (e.g., has enough space to evaluate the PoSpace routine without cache misses) or contains a routine that resisted being evicted.
PoSpace has been used in the Burstcoin cryptocurrency founded in August 2014. Burstcoin claims to have a green algorithm that favors smaller miners by design, making transaction costs cheaper and the network more decentralized. The goal of depending on smaller miners was most typified by the original Android app to mine Burstcoin. However, by December 2017, the estimated network size approached 157,000 terabytes and the average mining payoff was 21 burst per week per terabyte, so participants with disk space measured in gigabytes are no longer likely to receive significant payback from mining.
In 2015, a paper proposed a cryptocurrency called SpaceMint. It attempts to solve some of the practical design problems associated with the pebbling-based PoSpace schemes. In using PoSpace for decentralized cryptocurrency, the protocol has to be adapted to work in a non-interactive protocol since each individual in the network has to behave as a verifier.
Blockchain developed by the creator of Bittorrent, based on proofs of space and time.
- Dziembowski, Stefan; Faust, Sebastian; Kolmogorov, Vladimir; Pietrzak, Krzysztof (2015). "Proofs of Space". 9216: 585–605.
- Ateniese, Giuseppe; Bonacina, Ilario; Faonio, Antonio; Galesi, Nicola (2014). "Proofs of Space: When Space is of the Essence". 8642: 538–557.
- Ren, Ling; Srinivas, Devadas (2016). "Proof of Space from Stacked Expanders" (PDF).
- Jakobsson, Markus; Stewart, Guy (2013). "Mobile Malware: Why the Traditional AV Paradigm is Doomed, and How to Use Physics to Detect Undesirable Routines, BlackHat" (PDF).
- Markus Jakobsson Secure Remote Attestation Cryptology ePrint Archive. Retrieved 8 January 2018.
- "BURSTCOIN Celebrates Birthday With Release Of New Energy Efficient HDD Mining Wallet". NewsBTC. Retrieved 1 November 2016.
- "Burstcoin – An Energy Efficient Cryptocurrency - eCoin4Dummies.com". eCoin4Dummies.com. 2017-12-28. Retrieved 2018-05-01.
- Park et al. SpaceMint: A Cryptocurrency Based on Proofs of Space. Cryptology ePrint Archive. Retrieved 31 October 2016.
- "Energy-saving Bitcoin rival Chia raises from A16Z, plans mini-IPO – TechCrunch". techcrunch.com. Retrieved 2018-05-06.