Filecoin Section 3

3        Proof-of-Replication and Proof-of-Spacetime
In the Filecoin protocol, storage providers must convince their clients that they stored the data they were paid to store; in practice, storage providers will generate Proofs-of-Storage (PoS) that the blockchain network (or the clients themselves) verifies.

In this section we motivate, present and outline implementations for the Proof-of-Replication  (PoRep) and
Proof-of-Spacetime (PoSt) schemes used in Filecoin.

3.1        Motivation

Proofs-of-Storage (PoS) schemes such as Provable Data Possession (PDP) [2] and Proof-of-Retrievability (PoR) [3, 4] schemes allow a user (i.e. the verifier V) who outsources data D to a server (i.e. the prover P) to repeatedly check if the server is still storing D. The user can verify the integrity of the data outsourced to a
server in a very efficient way, more efficiently than downloading the data. The server generates probabilistic proofs of possession by sampling a random set of blocks and transmits a small constant amount of data in a challenge/response protocol with the user.

PDP and PoR schemes only guarantee that a prover had possession of some data at the time of the chal- lenge/response. In Filecoin, we need stronger guarantees to prevent three types of attacks that malicious miners could exploit to get rewarded for storage they are not providing: Sybil attack, outsourcing attacks, generation attacks.
      Sybil Attacks: Malicious miners could pretend to store (and get paid for) more copies than the ones physically stored by creating multiple Sybil identities, but storing the data only once.
      Outsourcing Attacks: Malicious miners could commit to store more data than the amount they can physically store, relying on quickly fetching data from other storage providers.
      Generation Attacks: Malicious miners could claim to be storing a large amount of data which they are instead efficiently generating on-demand using a small program. If the program is smaller than the purportedly stored data, this inflates the malicious miner’s likelihood of winning a block reward in Filecoin, which is proportional to the miner’s storage currently in use.

3.2        Proof-of-Replication

Proof-of-Replication (PoRep) is a novel Proof-of-Storage which allows a server (i.e. the prover P) to convince a user (i.e. the verifier V) that some data D has been replicated to its own uniquely dedicated physical storage. Our scheme is an interactive protocol, where the prover P: (a) commits to store n distinct replicas (physically independent copies) of some data D, and then (b) convinces the verifier V, that P is indeed
storing each of the replicas via a challenge/response protocol. To the best of our knowledge, PoRep improves on PoR and PDP schemes, preventing Sybil Attacks, Outsourcing Attacks, and Generation Attacks.

Note. For a formal definition, a description of its properties, and an in-depth study of Proof-of-Replication, we refer the reader to [5].
Definition 3.1.  (Proof-of-Replication) A PoRep scheme enables an efficient prover P to convince a verifier
V that P is storing a replica R, a physical independent copy of some data D, unique to P. A PoRep protocol
is characterized by a tuple of polynomial-time algorithms:

3.3        Proof-of-Spacetime

Proof-of-Storage schemes allow a user to check if a storage provider is storing the outsourced data at the time of the challenge. How can we use PoS schemes to prove that some data was being stored throughout a period of time? A natural answer to this question is to require the user to repeatedly (e.g. every minute) send challenges to the storage provider. However, the communication complexity required in each interaction can be the bottleneck in systems such as Filecoin, where storage providers are required to submit their proofs to the blockchain network.

To address this question, we introduce a new proof, Proof-of-Spacetime, where a verifier can check if a prover is storing her/his outsourced data for a range of time.  The intuition is to require the prover to (1) generate sequential Proofs-of-Storage (in our case Proof-of-Replication), as a way to determine time (2) recursively compose the executions to generate a short proof.
Definition 3.2.  (Proof-of-Spacetime) A PoSt scheme enables an efficient prover P to convince a verifier
V that P is storing some data D for some time t.  A PoSt is characterized by a tuple of polynomial-time

3.4        Practical PoRep and PoSt
We are interested in practical PoRep and PoSt constructions that can be deployed in existing systems and do not rely on trusted parties or hardware. We give a construction for PoRep (see Seal-based Proof-of-Replication in [5]) that requires a very slow sequential computation Seal to be performed during Setup to generate a replica. The protocol sketches for PoRep and PoSt are presented in Figure 4 and the underlying mechanism of the proving step in PoSt is illustrated in Figure 3.

3.4.1       Cryptographic building blocks

We refer the interested reader to [6, 7, 8] for formal presentation and implementation of zk-SNARK systems. Generally these systems require the KeyGen operation to be run by a trusted party; novel work on Scalable Computational Integrity and Privacy (SCIP) systems [9] shows a promising direction to avoid this initial step, hence the above trust assumption.

3.4.2       Seal operation

The role of the Seal operation is to (1) force replicas to be physically independent copies by requiring provers to store a pseudo-random permutation of D unique to their public key, such that committing to store n
replicas results in dedicating disk space for n independent replicas (hence n times the storage size of a replica) and (2) to force the generation of the replica during PoRep.Setup to take substantially longer than the time expected for responding to a challenge. For a more formal definition of the Seal operation see [5].

3.5   Usage in Filecoin

The Filecoin protocol employs Proof-of-Spacetime to audit the storage offered by miners. To use PoSt in Filecoin, we modify our scheme to be non-interactive since there is no designated verifier, and we want any member of the network to be able to verify. Since our verifier runs in the public-coin model, we can extract randomness from the blockchain to issue challenges.