In [13], Miller et al. proposed Permacoin, a modification to Bitcoin that aims at repurposing its mining resources toward a more useful goal: decentralized storage. Permacoin’s mining process requires investment in computational and storage resources. More specifically, Permacoin relies on a puzzle for Bitcoin based on Proofs of Retrievability (POR) [14,15]. To mine coins, users need to prove access to a given copy of a file. By doing so, Permacoin motivates the construction of a highly decentralized storage system.

We start with a brief refresher on POR. Proofs of Retrievability (POR) are interactive protocols that cryptographically prove the retrievability of outsourced data. More precisely, POR consider a model comprising of a single user (or tenant) and a service provider that stores a file pertaining to the user. POR basically consist of a challenge-response protocol in which the service provider proves to the tenant that its file is still intact and retrievable. Note that POR only provide a guarantee that a fraction p of the file can be retrieved. For that reason, POR are typically performed on a file that has been erasure-coded in such a way that the recovery of any fraction p of the stored data ensures the recovery of the file [15]. A POR scheme consists of four procedures [14], setup, store, verify, and prove. The latter two algorithms define a protocol for proving file retrievability. We refer to this protocol as the POR protocol (in contrast to a POR scheme that comprises all four procedures).

setup. This randomized algorithm generates the involved keys and distributes them to the parties. In case public keys are involved in the process, these are distributed among all parties.

store. This randomized algorithm takes as input the keys of the user and a file f e {0,1}*. The file is processed and store outputs f *, which will be stored on the server. store also generates a file tag т, which contains additional metadata information about f.

prove. The prover algorithm takes as input the public key and the file tag т and f that is output by store.

verify. The randomized verification algorithm takes the secret key, the public key, and the file tag т outputted by store during protocol execution. Algorithm verify outputs at the end of the protocol run TRUE if the verification succeeds, meaning that the file is being stored on the server, and FALSE otherwise.

In Permacoin, mining is associated with the effort of performing a POR. This is achieved as follows:

  • • Each participant pseudorandomly samples the data segments to store. The seed of the pseudorandom function is based on the miner's public key. This also allows other participants in the network to verify that the participant is indeed storing the correct segments.
  • • Unlike existing POR schemes, the challenge/response protocol needs to be made noninteractive. This is achieved by publicising epoch-dependent unpredictable puzzle instances puz. The challenge is then simply H(puz, s), where H(.) is a cryptographic hash function, and s is a random seed selected by the participant. By doing so, each participant basically pseudorandomly challenges a number of segments that it is storing.
  • • The participant finally broadcasts a (POR) proof (based on Merkle trees) of possession of the challenged segments. Any participant in the network can simply check that the response is correct and that H(puz, s) conforms with the current difficulty in the network. Only correct responses are broadcast in the network.
< Prev   CONTENTS   Source   Next >