Proof of Space

2018-02-07T10:53:08Z

193.147.107.1:

'''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.
<ref name="DziembowskiFaust2015">{{cite journal|last1=Dziembowski|first1=Stefan|last2=Faust|first2=Sebastian|last3=Kolmogorov|first3=Vladimir|last4=Pietrzak|first4=Krzysztof|title=Proofs of Space|volume=9216|year=2015|pages=585–605}}</ref>
in 2015 and independently by Ateniese et al. <ref name="AtenieseBonacina2014">{{cite journal|last1=Ateniese|first1=Giuseppe|title=Proofs of Space: When Space is of the Essence|last2=Bonacina|first2=Ilario|last3=Faonio|first3=Antonio|last4=Galesi|first4=Nicola|volume=8642|year=2014|pages=538–557}}</ref>.
Proofs of space are very similar to [[Proof-of-work system|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 [[cryptocurrency|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]].

== Description ==
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 [[Graph pebbling|hard-to-pebble graphs]].<ref name="DziembowskiFaust2015">{{cite journal|last1=Dziembowski|first1=Stefan|last2=Faust|first2=Sebastian|last3=Kolmogorov|first3=Vladimir|last4=Pietrzak|first4=Krzysztof|title=Proofs of Space|volume=9216|year=2015|pages=585–605}}</ref>
<ref name="Ren2016">{{cite journal|last1=Ren|first1=Ling|last2=Srinivas|first2=Devadas|title=Proof of Space from Stacked Expanders|year=2016}}</ref>
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.

== Uses ==
Proofs of space could be used as an alternative to proofs of work in the traditional [[Client Puzzle Protocol|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.<ref name="JakobssonStewart13">{{cite journal|last1=Jakobsson|first1=Markus|title=Mobile Malware: Why the Traditional AV Paradigm is Doomed, and How to Use Physics to Detect Undesirable Routines, BlackHat|last2=Stewart|first2=Guy|year=2013}}</ref> <ref>Markus Jakobsson [https://eprint.iacr.org/2018/031.pdf Secure Remote Attestation] ''Cryptology ePrint Archive.'' Retrieved January 8, 2018.</ref>

=== Burstcoin ===
PoSpace has been used in the Burstcoin cryptocurrency founded in August 2014.<ref>{{cite news|title=BURSTCOIN Celebrates Birthday With Release Of New Energy Efficient HDD Mining Wallet|url=http://us.newsbtc.com/burstcoin-celebrates-birthday-with-release-of-new-energy-efficient-hdd-mining-wallet/|accessdate=1 November 2016|publisher=NewsBTC}}</ref> Burstcoin claims to have a green algorithm that favors smaller miners by design, making transaction costs cheaper and the network more decentralized.

=== SpaceMint ===
In 2015, a paper proposed a cryptocurrency called SpaceMint.<ref>Park et al. [https://eprint.iacr.org/2015/528 SpaceMint: A Cryptocurrency Based on Proofs of Space.] ''Cryptology ePrint Archive.'' Retrieved 31 October 2016.</ref> 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. The SpaceMint of SpaceCoin also explained their process of designing the source of the puzzle challenge for their PoSpace cryptocurrency. The simplest solution is to assume an unpredictable beacon which broadcasts a random value every minute. The next step is to replace the beacon with a value derived from the blockchain's previous block. That leaves the problem of miners mining on low quality chains without being penalized. A solution is to make it so the value is not derived from the previous block but from a block at a certain depth in the blockchain. There is also a more complicated approach of having miners ask other miners to provide a challenge. This solution is inspired by [[proof-of-stake]] mechanisms, and miners who provide a challenge would get a cut of the block reward. The inventors of SpaceMint also address some problems called the "nothing-at-stake" problems. This is because of the cheaper mining costs of mining with proof-of-space. Malicious users can try to take advantage of this by mining on multiple chains or trying multiple blocks per chain. When miners mine on multiple chains simultaneously it takes longer to achieve consensus and might enable double-spending attacks. SpaceMint tries to avoid this problem by including a punishment transaction that includes a proof of the misbehaviour of a specific miner. The punishment transaction removes some amount of money from the malicious miner and transfers a portion to the publisher of the transaction as a reward for catching the perpetrator. The authors of Spacemint evaluated their cryptocurrency through game theory, which could also be used to analyse other cryptocurrencies. The objective is to model the network as being a game (in this case an extensive game with chance) and the miners as the participants and verify that it has strong equilibrium properties and that the best strategy for miners is to behave according to the rules.

=== Chia ===
https://chia.network/ - blockchain developed by the creator of Bittorrent, based on proofs of space and time

=== Bitcoin Ore ===
http://www.bitcoinore.org/ - Bitcoin Ore aims to be a less wasteful, more environmentally friendly and more egalitarian version of Bitcoin. It is based on proof-of-space (while Bitcoin uses proof-of-work), and will inherit all of Bitcoin’s transaction history.

== References ==

{{reflist}}

{{Cryptocurrencies}}

[[Category:Cryptocurrencies]]
[[Category:Algorithms and data structures]]
[[Category:Cryptography]]

Wikipedia - Benutzerbeiträge [de]

Proof of Space