**3**

*Pr*

*o*

*of-of-R*

*eplic*

*ati*

*on*

**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*Pr*

*o*

*of-of-Sp*

*ac*

*etime*

*(PoSt) schemes used in Filecoin.*

##
3.1
Motivation

*Pr*

*o*

*ofs-of-Stor*

*age*

*(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

algorithms:

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.
## Comments

## Post a Comment