Proof-of-space

Last updated

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. [1] in 2015 and with a different formal definition by Ateniese et al. [2] in 2014.

Contents

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.

A Proof-of-Work (PoW) system is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer. The concept was invented by Cynthia Dwork and Moni Naor as presented in a 1993 journal article. The term "Proof of Work" or PoW was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels.

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.

Cryptocurrency digital medium of exchange

A cryptocurrency is a digital asset designed to work as a medium of exchange that uses strong cryptography to secure financial transactions, control the creation of additional units, and verify the transfer of assets. Cryptocurrencies use decentralized control as opposed to centralized digital currency and central banking systems.

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.

Graph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an adjacent vertex. π(G), the pebbling number of a graph G is the lowest natural number n that satisfies the following condition:

Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.

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]

Client Puzzle Protocol

Client Puzzle Protocol (CPP) is a computer algorithm for use in Internet communication, whose goal is to make abuse of server resources infeasible. It is an implementation of a proof-of-work system (POW).

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]

Related Research Articles

Provable security refers to any type or level of security that can be proved. It is used in different ways by different fields.

Double-spending is a potential flaw in a digital cash scheme in which the same single digital token can be spent more than once. Unlike physical cash, a digital token consists of a digital file that can be duplicated or falsified. As with counterfeit money, such double-spending leads to inflation by creating a new amount of copied currency that did not previously exist. 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. Fundamental cryptographic techniques to prevent double-spending, while preserving anonymity in a transaction, are blind signatures and, particularly in offline systems, secret splitting.

Zerocoin is a privacy protocol proposed by Johns Hopkins University professor Matthew D. Green and his graduate students in 2013 as an extension to the Bitcoin protocol that would improve Bitcoin transactions' anonymity.

Proof of stake (PoS) is a type of algorithm by which a cryptocurrency blockchain network aims to achieve distributed consensus. In PoS-based cryptocurrencies the creator of the next block is chosen via various combinations of random selection and wealth or age. In contrast, the algorithm of proof-of-work-based cryptocurrencies such as bitcoin uses mining; that is, the solving of computationally intensive puzzles to validate transactions and create new blocks.

Ethereum is an open-source, public, blockchain-based distributed computing platform and operating system featuring smart contract (scripting) functionality. It supports a modified version of Nakamoto consensus via transaction-based state transitions.

Dash is an open source cryptocurrency and is a form of decentralized autonomous organization (DAO) run by a subset of users, called "masternodes". It is an altcoin that was forked from the Bitcoin protocol. The currency permits fast transactions that can be untraceable.

Blockchain distributed data store for digital transactions

A blockchain, originally block chain, is a growing list of records, called blocks, which are linked using cryptography. Each block contains a cryptographic hash of the previous block, a timestamp, and transaction data.

NEM is a peer-to-peer cryptocurrency and blockchain platform launched on March 29, 2015. Written in Java, with a C++ version in the works, NEM has a stated goal of a wide distribution model and has introduced new features to blockchain technology such as its proof-of-importance (POI) algorithm, multisignature accounts, encrypted messaging, and an Eigentrust++ reputation system. The NEM blockchain software is used in a commercial blockchain called Mijin, which is being tested by financial institutions and private companies in Japan and internationally.

Hyperledger is an umbrella project of open source blockchains and related tools, started in December 2015 by the Linux Foundation, and supported by big industry players like IBM, Intel and SAP Ariba, to support the collaborative development of blockchain-based distributed ledgers.

In computer security, proof of secure erasure (PoSE) or proof of erasure is a remote attestation protocol, by which an embedded device proves to a verifying party, that it has just erased (overwritten) all its writable memory. The purpose is to make sure that no malware remains in the device. After that typically a new software is installed into the device.

Lightning Network

The Lightning Network is a "Layer 2" payment protocol that operates on top of a blockchain-based cryptocurrency. It enables fast transactions between participating nodes and has been touted as a solution to the Bitcoin scalability problem. It features a peer-to-peer system for making micropayments of cryptocurrency through a network of bidirectional payment channels without delegating custody of funds. Lightning Network implementation also simplifies atomic swaps.

Bitcoin scalability problem

The bitcoin scalability problem refers to the discussion concerning the limits on the amount of transactions the bitcoin network can process. It is related to the fact that records in the bitcoin blockchain are limited in size and frequency.

Ethash is the proof-of-work function in Ethereum-based blockchain currencies. It uses Keccak, a hash function eventually standardized to SHA-3. These two are different, and should not be confused. Since version 1.0, Ethash has been designed to be ASIC-resistant via memory-hardness and easily verifiable. It also uses a slightly modified version of earlier Dagger and Hashimoto hashes to remove computational overhead. Previously referred to as Dagger-Hashimoto, the Ethash function has evolved over time. Ethash uses an initial 1 GB dataset known as the Ethash DAG and a 16 MB cache for light clients to hold. These are regenerated every 30,000 blocks, known as an epoch. Miners grab slices of the DAG to generate mix-hashes using transaction and receipt data, along with a cryptographic nonce to generate a hash below a dynamic target difficulty.

Steem Cryptocurrency

STEEM is a cryptocurrency based on the social media and content-focused Steem blockchain, which was created on March 24, 2016 by Ned Scott and the blockchain developer Dan Larimer. With over 1.2 million registered accounts and a daily volume of more than a million signed operations, Steem is amongst the five blockchains with the highest level of activity. In terms of total market capitalization, STEEM is currently ranked at place 40. with a market capitalization of more than 159 million USD..

EOS.IO is a blockchain protocol powered by the native cryptocurrency EOS. The protocol emulates most of the attributes of a real computer including hardware with the computing resources distributed equally among EOS cryptocurrency holders. EOSIO operates as a smart contract platform and decentralized operating system intended for the deployment of industrial-scale decentralized applications through a decentralized autonomous corporation model. The smart contract platform claims to eliminate transaction fees and also conduct millions of transactions per second.

Proof-of-authority (PoA) is an algorithm used with blockchains that delivers comparatively fast transactions through a consensus mechanism based on identity as a stake.

Royal Mint Gold is a digital gold currency and a cryptocurrency backed by gold reserves in the UK Royal Mint. The Royal Mint began testing blockchain transactions in April 2017. The first test transaction was in August 2017. The rollout was originally scheduled to occur by the end of 2017. US-based CME Group is administering the trading. The Daily Telegraph said it "appears somewhat similar to an exchange-traded fund such as ETF Securities Physical Gold".

A blockchain is a public, shared database that records transactions between two parties. Specifically, blockchains document and confirm who owns what at a particular time through cryptography. After a particular transaction is validated and cryptographically verified by other participants, or nodes in the network, it is then made into a "block" on the blockchain. A block contains information about when the transaction occurred, previous transactions, and details about the transaction. Once recorded as a block, transactions are ordered chronologically and cannot be altered or changed. This technology rose to popularity after the creation of Bitcoin—the first application built on using blockchain technology—and has furthermore catalyzed other cryptocurrencies and applications. Due to its nature of decentralization, transactions and data are not verified and owned by one singular, overpowering entity as they are in typical systems. Rather, the validity of transactions are able to be confirmed by any node, or computer, that has access to the network. Additionally, blockchain technology secures and authenticates transactions and data through cryptography. With the rise and widespread adoption of technology, data breaches have become rampant and frequent. User information and data are often stored, mishandled, and misused, causing a threat to personal privacy. Currently, many are pushing for the widespread adoption of blockchain technology for its ability to increase user privacy, data protection, and data ownership.

References

  1. 1 2 Dziembowski, Stefan; Faust, Sebastian; Kolmogorov, Vladimir; Pietrzak, Krzysztof (2015). "Proofs of Space". 9216: 585–605.
  2. ↑ Ateniese, Giuseppe; Bonacina, Ilario; Faonio, Antonio; Galesi, Nicola (2014). "Proofs of Space: When Space is of the Essence". 8642: 538–557.
  3. ↑ Ren, Ling; Srinivas, Devadas (2016). "Proof of Space from Stacked Expanders" (PDF).
  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).
  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. Retrieved 1 November 2016.
  7. ↑ Wahab, Abdul; Waqas, Memood (October 2018). "Survey of Consensus Protocols" (PDF). Survey of Consensus Protocols: 6.
  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.
  9. 1 2 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).
  11. ↑ Cohen, Bram; Pietrzak, Krzysztof. "Simple Proofs of Sequential Work" (PDF). Simple Proofs of Sequential Work.
  12. ↑ "Chia FAQ" . Retrieved 2018-10-24.

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.