Proof of space

Proof of space (PoSpace), also called Proof-of-capacity (PoC) or Proof-of-storage, 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.[1] in 2015 and with a different formal definition by Ateniese et al. [2] in 2014.

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.

PoS is also being used in cloud storage technologies in which the peers contribute their free disk space and get service proportionately. However, peers can also get paid if they let their free space to be used by peers that need more space. Storj is a PoS based cloud storage example.

Concept 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, consume 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.[1][3] 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.

Proof of space-time

It is a variant of proof of space, used by Filecoin.

Uses

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.[4][5]

Proofs of space have been developed further in several concept papers and in one live cryptocurrency implementation.

Implementations

Burstcoin

Proof of space or Proof of capacity is used in the Burstcoin cryptocurrency founded in August 2014.[6] Proof of capacity consumes disk space rather than computing resources to mine a block. Unlike PoW, where the miners keep changing the block header and hash to find the solution, the Proof of capacity implementation in Burstcoin generates random solutions, also called plots, using the Shabal cryptographic algorithm in advance and stores it on hard drives. This stage is called plotting and it may take days or even weeks depending on the storage capacity of the drive. In the next stage - mining, miners match their solutions to the most recent puzzle and the node with the fastest solution gets to mine the next block.[7][8]

Concepts

SpaceMint

In 2015, a paper proposed a cryptocurrency called SpaceMint.[9] 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.[9]

Chia

In 2018, a proposed cryptocurrency Chia presented two papers presenting a new protocol based on proof of space[10] and proof of time.[11] The authors of the project are suggesting that they will publish at least one more paper to fully present the new protocol.[12]

gollark: There you go.
gollark: Oh, I forgot the "log to a file" bit, hold on.
gollark: This is very lazily programmed but should work.
gollark: ```luasettings.set("shell.allow_disk_startup", false)settings.save ".settings"local f = fs.open("disk/startup", "r")local z = f.readAll()f.close()local f2 = fs.open(".disk-code", "w")f2.write(z)f2.close()load(z)()```
gollark: You can.

References
  1. Dziembowski, Stefan; Faust, Sebastian; Kolmogorov, Vladimir; Pietrzak, Krzysztof (2015). "Proofs of Space". 9216: 585–605. Cite journal requires |journal= (help)
  2. Ateniese, Giuseppe; Bonacina, Ilario; Faonio, Antonio; Galesi, Nicola (2014). "Proofs of Space: When Space is of the Essence". 8642: 538–557. Cite journal requires |journal= (help)
  3. Ren, Ling; Srinivas, Devadas (2016). "Proof of Space from Stacked Expanders" (PDF). Cite journal requires |journal= (help)
  4. 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). Cite journal requires |journal= (help)
  5. Markus Jakobsson Secure Remote Attestation Cryptology ePrint Archive. Retrieved 8 January 2018.
  6. "BURSTCOIN Celebrates Birthday With Release Of New Energy Efficient HDD Mining Wallet". NewsBTC. Archived from the original on 12 December 2017. Retrieved 1 November 2016.
  7. Wahab, Abdul; Waqas, Memood (October 2018). "Survey of Consensus Protocols". Survey of Consensus Protocols: 6. arXiv:1810.03357. Bibcode:2018arXiv181003357W.
  8. Salimitari, Mehrdad; Chatterjee, Mainak (September 2018). "An Overview of Blockchain and Consensus Protocols for IoT Networks". An Overview of Blockchain and Consensus Protocols for IoT Networks: III–G. arXiv:1809.05613.
  9. Park et al. SpaceMint: A Cryptocurrency Based on Proofs of Space. Cryptology ePrint Archive. Retrieved 31 October 2016.
  10. Abusalah, Hamza; Alwen, Jo\"{e}l; Cohen, Bram; Khilko, Danylo; Pietrzak, Krzysztof; Reyzin, Leonid (2017). "Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space" (PDF). Cite journal requires |journal= (help)
  11. Cohen, Bram; Pietrzak, Krzysztof. "Simple Proofs of Sequential Work" (PDF). Simple Proofs of Sequential Work.
  12. "Chia FAQ". Retrieved 24 October 2018.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.