Proof of space

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 is closely related to 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 . 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.

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.

...
Wikipedia