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. Proofs of space are very similar to proofs of work, except that instead of using CPU-bound functions, memory hard functions are used. Proof-of-space is related also to proof of storage, where a verifier sends a file to a prover and the prover has to later convince the verifier that the file has been stored. Proof of space has also been confused with proof of secure erasure (PoSE) and may be confused with Proof-of-Stake. PoW systems were first proposed by Dwork and Naor as a way to use moderately hard functions to combat junk mail. After the development of moderately hard memory-bound functions by Abadi and Burrows, these types of functions that were then viewed as an alternative for fighting spam. 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 a fairer and greener alternative due to the lower variance of memory access times between machines and the lower energy cost achieved through the reduced number of computations required. Several theoretical and practical implementations of PoSpace have been released and discussed, such as Permacoin, SpaceMint and Burstcoin.
Contents
Description
The concept of PoSpace extends on proof of storage to means the user can both read and write data to storage space. A version called weak proof of space (wPoSpace) has been formalized to define situations where the user can only access space. In interactive proof-of-space systems, a proof-of-space is a piece of data that a prover sends to a verifier to prove that he has reserved a certain amount of space, usually as one file. For the system to be practical there have to be bounds on, most importantly, the computational time and space complexity of verification and the communication complexity so that neither of the parties have all of their bandwidth constantly drained by a PoSpace application. To avoid having to send a very large file to the prover, the prover can generate the file locally. And for verification, it is unfeasible for the prover to send the whole file through the communication channel, so he might be asked to send a random subset of the data. A solution might be to send the prover a pseudorandom function and have him build a table of preimages for the function. Later the verifier can ask for the inverse of random values of the function and the prover can do a table lookup and report back the inverse to prove that he has stored the table. But is important also, for soundness, that the time for generating this file be long enough to prevent dishonest users from deleting the file after sending their proof and then reconstructing it again whenever needed. One of the ways of implementing PoSpace is by using hard-to-pebble graphs. This exploits the time and space tradeoffs of pebbling. The verifier will ask the prover to build a labeling of a graph based on the information given by the verifier. The prover then can commit to the labeling and send a commitment to the verifier (possibly a Merkle hash of all the labels). To make sure that the storage space has been correctly allocated, the verifier will ask the prover to open several random locations in the commitment. The prover then responds with proofs for the locations. A proof of work should also have the property of completeness. Completeness means that the verifier will always accept a proof from an honest prover. One consideration to make is that in most architectures the user has a memory hierarchy who accesses data through a fast cache. In viewing PoSpace as a pricing function, these cache accesses are considered free, and the user is charged for every memory fetch that he has to make.
Motivations
In proof-of-work systems, processing power is used to validate the user's intentions, but the CPU speeds for a fast CPU and a slow CPU are very different. This might be problematic because a well-intentioned user with a poorly performing computer might have some trouble with his requests while attackers with powerful machines may not be affected. Since memory access time varies significantly less than CPU power in different computing platforms, PoSpace might be a fairer approach, even though this fairness might not be desirable in every situation. In the context of cryptocurrencies, this aspect of PoW is very negative. Cryptocurrency designers and developers do not want someone to control a large portion of the network's mining power, since that could lead to problems such as double spend attacks. Therefore a more decentralized scheme for mining is preferred. PoW's constant use of energy is also a worry for some. The Bitcoin mining mechanism uses cryptographic puzzles where the best way to solve them is through brute-forcing through the possible solutions, and those solutions are not useful in itself. All those computations contribute to a large electricity expense for cryptocurrency miners.
Uses
Proofs of work 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. The difference is that the pricing functions used are chosen so that the user has to spend a certain amount of space. In May 2014 the idea for Permacoin was published. Permacoin uses Proofs of Retrievability(PoR), where the miners have monetary incentive to store useful public data in the network. This data can then be later retrieved by other users, similar to a P2P torrenting service. Permacoin's PoR does not solve the problem of perpetual computation, since it requires the miner to compute many proofs of retrievability. PoSpace has been used in the open source 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. In 2015 a paper proposing a cryptocurrency called SpaceMint modified PoW to address some issues such as the nothing-at-stake problem caused by the cheapness of mining. SpaceMint also improved the time and memory efficiency for block mining and verification.
Permacoin
Permacoin is a system that aims to recycle some of the computing efforts in Bitcoin by making miners store archival data for later retrieval. Permacoin could be either built on top of Bitcoin or implemented as a separate Altcoin. The objective of Permacoin is to incentivize modifications of Bitcoin to achieve more sustainable, useful and efficient computing. The process of mining Permacoin involves constructing Proofs of Retrievability (POR) which show to the network that the files stored by the miners can be accessed at a later time. In a POR the prover demonstrates that he holds a file without having to send the entire file by responding to random challenges issued by a verifier. Permacoin proposes a couple of ideas to avoid users on the network outsourcing mining to cloud hosting companies, which would create unwanted centralization. The first idea is to tie the block reward winner's private key to the puzzle solution so that to outsource the mining, the user would have to send the cloud host his private key. A portion of the users would refuse to do this, concerned with the protection of their private key. A variant of the Permacoin PoR scheme also allows for zero-knowledge SNARKs which allow for servers to steal rewards without leaving evidence and therefore without risking damage to their reputation, which further deincentivizes key sharing without adding any overhead to the puzzle-solving scheme. Even with a local private key, the user can still outsource the storage of their assigned blocks, and fetch them as needed to perform computations on them. To deal with this, these computations are designed to be related to the puzzle solution. A delay in this phase lowers the chances of solving the puzzle and receiving the reward. So the requests for blocks happen unpredictably, creating a larger bandwidth latency overhead. Successfully mining a block may require many block fetches, and if the parameters are properly adjusted, the block fetching delay might make it completely impractical to outsource mining because the time taken by the fetches will be larger than the duration of a mining epoch. For such a system to work using the local storage of users, it is important to have some redundancy, so that the files stored by one user are lost forever in case he decides to stop mining or if the network is somehow attacked to block compromise a certain file. If the whole Bitcoin network dedicated it's hashing power and invested on SSD drives instead of ASICs to build a distributed file storage scheme, it is estimated that the network storage capacity could reach several petabytes. An important part of having a distributed storage scheme is supporting the possibility of updating the content, adding to it or removing obsolete data. This also means that there needs to be a way to decide which data should be stored and when data needs to be removed. This could be done by a trusted authority, or perhaps more interestingly by a majority vote. Since the idea is for the data to be publicly available, there is also a concern with privacy, and so users who wish to append data to the network might want to first encrypt it. The Permacoin protocols also do not cover the necessity for file distribution, although the authors of the proposal mention that it might be done voluntarily by an altruistic group of users.
SpaceMint
SpaceMint is a proposed cryptocurrency based in Proofs of Space. It attempts to solve some of the practical design problems associated with the new mining mechanism. 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 makers 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.