Proof of space

Last updated

Proof of space (PoS) is a type of consensus algorithm achieved by demonstrating one's 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 in 2013 by Dziembowski et al. [1] [2] and (with a different formulation) by Ateniese et al.. [3] [4] Proofs of space are very similar to proofs of work (PoW), except that instead of computation, storage is used to earn cryptocurrency. Proof-of-space is different from memory-hard functions in that the bottleneck is not in the number of memory access events, but in the amount of memory required.

Contents

After the release of Bitcoin, alternatives to its PoW mining mechanism were researched, and PoS was studied in the context of cryptocurrencies. Proofs of space are seen as a fairer and greener alternative by blockchain enthusiasts due to the general-purpose nature of storage and the lower energy cost required by storage.

In 2014, Signum (formerly Burstcoin) became the first practical implementation of a PoS (initially as proof of capacity) blockchain technology [5] and is still actively developed. Other than Signum, several theoretical and practical implementations of PoS have been released and discussed, such as SpaceMint and Chia, but some were criticized for increasing demand and shortening the life of storage devices due to greater disc reading requirements than Signum. [6] [7]

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 security, 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 PoS is by using hard-to-pebble graphs. [2] [8] 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 storage

A proof of storage (also proof of retrievability, proof of data possession) is related to a proof-of-space, but instead of showing that space is available for solving a puzzle, the prover shows that space is actually used to store a piece of data correctly at the time of proof.

Cryptocurrencies intended to assign value to store data use some form of this system; examples include Chives, Storj, Sia, Filecoin, and Arweave.

Proof of capacity

A proof of capacity is a system where miners are allowed to pre-calculate ("plot") PoW functions and store them onto the HDD. The first implementation of proof of capacity was Signum (formerly burstcoin). [9]

Conditional proof of capacity

The Proof of Capacity (PoC) consensus algorithm is used in some cryptocurrencies. Conditional Proof of Capacity (CPOC) [10] is an improved version of PoC. It has a work, stake, and capacity system that works like the PoW, PoS, and PoC algorithms. By pledging their digital assets, users receive a higher income as a reward. Additionally, CPOC has designed a new reward measure for top users. In this algorithm, miners add a conditional component to the proof by ensuring that their plot file contains specific data related to the previous block. This additional condition enhances the security and decentralization of the consensus mechanism beyond traditional proof-of-capacity algorithms.

Proof of space-time

A proof of space-time (PoST) is a proof that shows the prover has spent an amount of time keeping the reserved space unchanged. Its creators reason that the cost of storage is inextricably linked not only to its capacity, but to the time in which that capacity is used. It is related to a proof-of-storage (but without necessarily storing any useful data), although the Moran-Orlov construction also allows a tradeoff between space and time. [11] The first implementation of PoST is with the Chia blockchain.

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 PoS routine without cache misses) or contains a routine that resisted being evicted. [12] [13]

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

Signum (formerly Burstcoin)

The first blockchain to use hard disk based blockchain validation, established in 2014. Signum 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, proof of capacity (as implemented by Burstcoin, and developed further by Signum) 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. [14] [15]

SpaceMint

In 2015, a paper proposed a cryptocurrency called SpaceMint. [16] It attempts to solve some of the practical design problems associated with the pebbling-based PoS schemes. In using PoS 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. [16]

Chia

In 2018, a proposed cryptocurrency Chia presented two papers presenting a new protocol based on proof of space [17] and proof of time. [18]

In February 2021, Chia published a white paper outlining its business and has since launched its mainnet and Chia coin (XCH) using the Proof of Space Time concept. The spacetime model of Chia also depends on "plotting" (generation of proof-of-space files) to the storage medium to solve a puzzle. [19]

Unlike many proof-of-storage cryptocurrencies, Chia plots do not store any useful data. Also, Chia's proof-of-time method for plotting has raised concerns over shortened lifespans of solid-state drives due to the intensity of write activity involved in plot generation (typically, plotting occurs on an SSD and then the finished plots are transferred to a hard disk drive for long-term storage). [7]

Spacemesh

In 2019, a paper was released by Tal Moran and Ilan Orlov proposing a new protocol based on proof of space-time.

Spacemesh is unique due to its use of a blockmesh, rather than a blockchain. While a blockchain is a chain of single blocks, a blockmesh makes use of a directed acyclic graph (DAG) composed of layers, with each layer containing many blocks.

See also

Related Research Articles

<span class="mw-page-title-main">Bram Cohen</span> American programmer and author of the BitTorrent protocol

Bram Cohen is an American computer programmer, best known as the author of the peer-to-peer (P2P) BitTorrent protocol in 2001, as well as the first file sharing program to use the protocol, also known as BitTorrent. He is also the co-founder of CodeCon and organizer of the San Francisco Bay Area P2P-hackers meeting, was the co-author of Codeville and creator of the Chia cryptocurrency which implements the proof of space-time consensus algorithm.

Proof of work (PoW) is a form of cryptographic proof in which one party proves to others that a certain amount of a specific computational effort has been expended. Verifiers can subsequently confirm this expenditure with minimal effort on their part. The concept was invented by Moni Naor and Cynthia Dwork in 1993 as a way to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from a service requester, usually meaning processing time by a computer. The term "proof of work" was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

A Sybil attack is a type of attack on a computer network service in which an attacker subverts the service's reputation system by creating a large number of pseudonymous identities and uses them to gain a disproportionately large influence. It is named after the subject of the book Sybil, a case study of a woman diagnosed with dissociative identity disorder. The name was suggested in or before 2002 by Brian Zill at Microsoft Research. The term pseudospoofing had previously been coined by L. Detweiler on the Cypherpunks mailing list and used in the literature on peer-to-peer systems for the same class of attacks prior to 2002, but this term did not gain as much influence as "Sybil attack".

Non-interactive zero-knowledge proofs are cryptographic primitives, where information between a prover and a verifier can be authenticated by the prover, without revealing any of the specific information beyond the validity of the statement itself. This function of encryption makes direct communication between the prover and verifier unnecessary, effectively removing any intermediaries. The core trustless cryptography "proofing" involves a hash function generation of a random number, constrained within mathematical parameters determined by the prover and verifier.

Double-spending is a fundamental flaw in a digital cash protocol in which the same single digital token can be spent more than once. Due to the nature of information space, in comparison to physical space, a digital token is inherently almost infinitely duplicable or falsifiable, leading to ownership of said token itself being undefinable unless declared so by a chosen authority. As with counterfeit money, such double-spending leads to inflation by creating a new amount of copied currency that did not previously exist. Like all increasingly abundant resources, this devalues the currency relative to other monetary units or goods and diminishes user trust as well as the circulation and retention of the currency.

Zerocoin is a privacy protocol proposed in 2013 by Johns Hopkins University professor Matthew D. Green and his graduate students, Ian Miers and Christina Garman. It was designed as an extension to the Bitcoin protocol that would improve Bitcoin transactions' anonymity by having coin-mixing capabilities natively built into the protocol. Zerocoin is not currently compatible with Bitcoin.

Proof-of-stake (PoS) protocols are a class of consensus mechanisms for blockchains that work by selecting validators in proportion to their quantity of holdings in the associated cryptocurrency. This is done to avoid the computational cost of proof-of-work (POW) schemes. The first functioning use of PoS for cryptocurrency was Peercoin in 2012, although the scheme, on the surface, still resembled a POW.

A distributed ledger is the consensus of replicated, shared, and synchronized digital data that is geographically spread (distributed) across many sites, countries, or institutions. In contrast to a centralized database, a distributed ledger does not require a central administrator, and consequently does not have a single (central) point-of-failure.

<span class="mw-page-title-main">Ethereum Classic</span> Blockchain computing platform

Ethereum Classic is a blockchain-based distributed computing platform which offers smart contract (scripting) functionality. It is open source and supports a modified version of Nakamoto consensus via transaction-based state transitions executed on a public Ethereum Virtual Machine (EVM).

<span class="mw-page-title-main">Cardano (blockchain platform)</span> Public blockchain platform

Cardano is a public blockchain platform. It is open-source and decentralized, with consensus achieved using proof of stake. It can facilitate peer-to-peer transactions with its internal cryptocurrency, ADA.

<span class="mw-page-title-main">IOTA (technology)</span> Open-source distributed ledger and cryptocurrency

IOTA is an open-source distributed ledger and cryptocurrency designed for the Internet of things (IoT). It uses a directed acyclic graph to store transactions on its ledger, motivated by a potentially higher scalability over blockchain based distributed ledgers. IOTA does not use miners to validate transactions, instead, nodes that issue a new transaction on the network must approve two previous transactions. Transactions can therefore be issued without fees, facilitating microtransactions. The network currently achieves consensus through a coordinator node, operated by the IOTA Foundation. As the coordinator is a single point of failure, the network is currently centralized.

A blockchain is a shared database that records transactions between two parties in an immutable ledger. Blockchain documents and confirms pseudonymous ownership of all transactions in a verifiable and sustainable way. After a transaction is validated and cryptographically verified by other participants or nodes in the network, it is made into a "block" on the blockchain. A block contains information about the time the transaction occurred, previous transactions, and details about the transaction. Once recorded as a block, transactions are ordered chronologically and cannot be altered. This technology rose to popularity after the creation of Bitcoin, the first application of blockchain technology, which has since catalyzed other cryptocurrencies and applications.

<span class="mw-page-title-main">Tron (cryptocurrency)</span> Blockchain computing platform

TRON is a decentralized, blockchain-based operating system with smart contract functionality, proof-of-stake principles as its consensus algorithm and a cryptocurrency native to the system, known as Tronix (TRX). It was established in March 2014 by Justin Sun and since 2017 has been overseen and supervised by the TRON Foundation, a non-profit organization in Singapore, established in the same year. It is open-source software.

<span class="mw-page-title-main">Ouroboros (protocol)</span> Blockchain protocol

Ouroboros is a family of proof-of-stake consensus protocols used in the Cardano and Polkadot blockchains. It can run both permissionless and permissioned blockchains.

Proof of personhood (PoP) is a means of resisting malicious attacks on peer to peer networks, particularly, attacks that utilize multiple fake identities, otherwise known as a Sybil attack. Decentralized online platforms are particularly vulnerable to such attacks by their very nature, as notionally democratic and responsive to large voting blocks. In PoP, each unique human participant obtains one equal unit of voting power, and any associated rewards.

Aggelos Kiayias FRSE is a Greek cryptographer and computer scientist, currently a professor at the University of Edinburgh and the Chief Science Officer at Input Output Global, the company behind Cardano.

Algorand is a cryptocurrency protocol providing proof-of-stake on a blockchain. Algorand's native cryptocurrency is called ALGO.

Proof of identity (PoID) is a consensus protocol for permission-less blockchains, in which each uniquely identified individual receives one equal unit of voting power and associated rewards. The protocol is based on biometric identification, humanity identification parties and additional verification parties.

Chia Network Inc. is a US-based blockchain technology company. The company built the Chia blockchain that uses proof of space and proof of time consensus protocols and issues the digital currency Chia (XCH). Chia Network was founded in 2017 by Bram Cohen, the creator of BitTorrent, and Ryan Singer. Its headquarters are in South San Francisco, California.

References

  1. ↑ Dziembowski, Stefan; Faust, Sebastian; Kolmogorov, Vladimir; Pietrzak, Krzysztof (2013). "Proofs of Space". Cryptology Eprint Archive https://eprint.iacr.org/2013/796
  2. 1 2 Dziembowski, Stefan; Faust, Sebastian; Kolmogorov, Vladimir; Pietrzak, Krzysztof (2015). Proofs of Space. Advances in Cryptology – CRYPTO 2015 - 35th Annual Cryptology Conference. Vol. 9216. pp. 585–605.
  3. ↑ Ateniese, Giuseppe; Bonacina, Ilario; Faonio, Antonio; Galesi, Nicola (2014). "Proofs of Space: When Space is of the Essence". https://eprint.iacr.org/2013/805
  4. ↑ Ateniese, Giuseppe; Bonacina, Ilario; Faonio, Antonio; Galesi, Nicola (2014). "Proofs of Space: When Space is of the Essence". 8642: 538–557.{{cite journal}}: Cite journal requires |journal= (help)
  5. ↑ Natoli, C., Yu, J., Gramoli, V., Esteves-Verissimo, P. (22 August 2019). "Deconstructing Blockchains: A Comprehensive Survey on Consensus, Membership and Structure". arXiv: 1908.08316 [cs.DC].
  6. ↑ Hern, A., editor, A. H. U. technology (2021). "New cryptocurrency Chia blamed for hard drive shortages". TheGuardian.com . Retrieved 19 October 2022.
  7. 1 2 Lilly, Paul (11 May 2021). "Chia mining can wreck a 512GB SSD in as little as 6 weeks". PC Gamer. Archived from the original on 17 May 2021. Retrieved 19 May 2021.
  8. ↑ Ren, Ling; Srinivas, Devadas (2016). "Proof of Space from Stacked Expanders" (PDF).{{cite journal}}: Cite journal requires |journal= (help)
  9. ↑ "Proof of capacity (PoC)".
  10. ↑ Evertise Digital via COMTEX (17 March 2023). "Sustainable Mining Made Easy: Using CPoC for Eco-Friendly Cryptocurrency Mining".
  11. ↑ Moran, Tal; Orlov, Ilan (2019). "Simple Proofs of Spacetime and Rational Proofs of Storage" (PDF).
  12. ↑ 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). S2CID   16726066. Archived from the original (PDF) on 18 March 2018.{{cite journal}}: Cite journal requires |journal= (help)
  13. ↑ Markus Jakobsson Secure Remote Attestation Cryptology ePrint Archive. Retrieved 8 January 2018.
  14. ↑ Wahab, Abdul; Waqas, Memood (October 2018). "Survey of Consensus Protocols". Survey of Consensus Protocols: 6. arXiv: 1810.03357 . Bibcode:2018arXiv181003357W.
  15. ↑ 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 .
  16. 1 2 Park et al. SpaceMint: A Cryptocurrency Based on Proofs of Space. Cryptology ePrint Archive. Retrieved 31 October 2016.
  17. ↑ 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}}: Cite journal requires |journal= (help)
  18. ↑ Cohen, Bram; Pietrzak, Krzysztof (2018). "Simple Proofs of Sequential Work" (PDF). Simple Proofs of Sequential Work.
  19. ↑ Hoffman, Gene (10 February 2021). "The Chia Business Whitepaper". Chia Network. Chia. Retrieved 1 May 2021.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.