Filecoin: A Decentralized Storage Network

Protocol Labs

July 19, 2017

Abstract

The internet is in the middle of a revolution: centralized proprietary services are being replaced with decentralized open ones; trusted parties replaced with veriable computation; brittle location addresses replaced with resilient content addresses; inecient monolithic services replaced with peer-to-peer algorithmic markets. Bitcoin, Ethereum, and other blockchain networks have proven the utility of decentralized transaction ledgers. These public ledgers process sophisticated smart contract applications and transact crypto-assets worth tens of billions of dollars. These systems are the rst instances of internetwide Open Services, where participants form a decentralized network providing useful services for pay, with no central management or trusted parties. IPFS has proven the utility of content-addressing by decentralizing the web itself, serving billions of les used across a global peer-to-peer network. It liberates data from silos, survives network partitions, works oine, routes around censorship, and gives permanence to digital information.

Filecoin is a decentralized storage network that turns cloud storage into an algorithmic market. The market runs on a blockchain with a native protocol token (also called \Filecoin"), which miners earn by providing storage to clients. Conversely, clients spend Filecoin hiring miners to store or distribute data. As with Bitcoin, Filecoin miners compete to mine blocks with sizable rewards, but Filecoin mining power is proportional to active storage, which directly provides a useful service to clients (unlike Bitcoin mining, whose usefulness is limited to maintaining blockchain consensus). This creates a powerful incentive for miners to amass as much storage as they can, and rent it out to clients. The protocol weaves these amassed resources into a self-healing storage network that anybody in the world can rely on. The network achieves robustness by replicating and dispersing content, while automatically detecting and repairing replica failures. Clients can select replication parameters to protect against dierent threat models. The protocol’s cloud storage network also provides security, as content is encrypted end-to-end at the client, while storage providers do not have access to decryption keys. Filecoin works as an incentive layer on top of IPFS [1], which can provide storage infrastructure for any data. It is especially useful for decentralizing data, building and running distributed applications, and implementing smart contracts.

This work:

(a)Introduces the Filecoin Network, gives an overview of the protocol, and walks through several components in detail. (b)Formalizes decentralized storage network (DSN) schemes and their properties, then constructs File-

(c)Introduces a novel class of proof-of-storage schemes called proof-of-replication, which allows proving that any replica of data is stored in physically independent storage. (d)Introduces a novel useful-work consensus based on sequential proofs-of-replication and storage as a

(e)Formalizes veriable markets and constructs two markets, a Storage Market and a Retrieval Market, which govern how data is written to and read from Filecoin, respectively. (f)Discusses use cases, connections to other systems, and how to use the protocol.

(d)Introduces a novel useful-work consensus based on sequential proofs-of-replication and storage as a measure of power. (e)Formalizes veriable markets and constructs two markets, a Storage Market and a Retrieval Market,

(f)Discusses use cases, connections to other systems, and how to use the protocol.

Contents

1 Introduction 4

1.1 Elementary Components 4 1.2 Protocol Overview 4 1.3 Paper organization 4

2 Definition of a Decentralized Storage Network 8

2.1 Fault tolerance 8 2.2 Properties 8

3 Proof-of-Replication and Proof-of-Spacetime 10

3.1 Motivation 10 3.2 Proof-of-Replication 10 3.3 Proof-of-Spacetime 11 3.4 Practical PoRep and PoSt 11 3.5 Usage in Filecoin 14

4 Filecoin: a DSN Construction 16

4.1 Setting 16 4.2 Data Structures 17 4.3 Protocol 17 4.4 Guarantees and Requirements 21

5 Filecoin Storage and Retrieval Markets 24

5.1 Verifiable Markets 24 5.2 Storage Market 24 5.3 Retrieval Market 27

6 Useful Work Consensus 30

6.1 Mot

List of Figures

1 Sketch of the Filecoin Protocol............. . . . . . . . . . . . . . . . . . . . . . . .6 2 Illustration of the Filecoin Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 3 Illustration of the underlying mechanism of PoSt.Prove . . . . ............ . . . . . .14 4 Proof-of-Replication and Proof-of-Spacetime protocol sketches . . ............... .15 5 Data Structures in a DSN scheme . . . . ..............................17 6 Example execution of the Filecoin DSN............................. .21 7 Description of the Put and Get Protocols in the Filecoin DSN............... . . .22 8 Description of the Manage Protocol in the Filecoin DSN.....................23 9 Generic protocol for Veriable Markets . . . ............ . . . . . . . . . . . . . . . .24 10 Orders data structures for the Retrieval and Storage Markets..................26 11 Detailed Storage Market protocol . .......... . . . . . . . . . . . . . . . . . . . . . . .28 12 Detailed Retrieval Market protocol.................................29 13 Leader Election in the Expected Consensus protocol. . . . . . . . . . . . . . . . . . . . . . .32

1 Introduction

Filecoin is a protocol token whose blockchain runs on a novel proof, called Proof-of-Spacetime, where blocks are created by miners that are storing data. Filecoin protocol provides a data storage and retrieval service via a network of independent storage providers that does not rely on a single coordinator, where: (1) clients pay to store and retrieve data, (2) Storage Miners earn tokens by oering storage (3) Retrieval Miners earn tokens by serving data.

1.1 Elementary Components

The Filecoin protocol builds upon four novel components.

1. Decentralized Storage Network (DSN): We provide an abstraction for network of independent storage providers to oer storage and retrieval services (in Section 2). Later, we present the Filecoin protocol as an incentivized, auditable and veriable DSN construction (in Section 4).

2. Novel Proofs-of-Storage : We present two novel Proofs-of-Storage (in Section 3): (1) Proof-of- Replication allows storage providers to prove that data has been replicated to its own uniquely dedicated physical storage. Enforcing unique physical copies enables a verier to check that a prover is not deduplicating multiple copies of the data into the same storage space; (2) Proof-of-Spacetime allows storage providers to prove they have stored some data throughout a specied amount of time.

3. Veriable Markets: We model storage requests and retrieval requests as orders in two decentralized veriable markets operated by the Filecoin network (in Section 5). Veriable markets ensure that payments are performed when a service has been correctly provided. We present the Storage Market and the Retrieval Market where miners and clients can respectively submit storage and retrieval orders.

4. Useful Proof-of-Work : We show how to construct a useful Proof-of-Work based on Proof-of- Spacetime that can be used in consensus protocols. Miners do not need to spend wasteful computation to mine blocks, but instead must store data in the network.

1.2 Protocol Overview

The Filecoin protocol is a Decentralized Storage Network construction built on a blockchain and with a native token. Clients spend tokens for storing and retrieving data and miners earn tokens by storing and serving data.

1.3 Paper organization

The Filecoin DSN handle storage and retrieval requests respectively via two veriable markets : the Storage Market and the Retrieval Market. Clients and miners set the prices for the services requested and oered and submit their orders to the markets.

The remainder of this paper is organized as follows. We present our denition of and requirements for a theoretical DSNscheme in Section 2. In Section 3 we motivate, dene, and present our Proof-of-Replication and Proof-of-Spacetime protocols, used within Filecoin to cryptographically verify that data is continuously

Finally, miners can participate in the creations of new blocks for the underlining blockchain. The inuence of a miner over the next block is proportional to the amount of their storage currently in use in the network.

stored in accordance with deals made. Section 4 describes the concrete instantiation of the Filecoin DSN, describing data structures, protocols, and the interactions between participants. Section 5 denes and describes the concept of Veriable Markets, as well as their implementations, the Storage Market and Retrieval Market. Section 6 motivates and describes the use of the Proof-of-Spacetime protocol for demonstrating and evaluating a miner’s contribution to the network, which is necessary to extend the blockchain and assign the block reward. Section 7 provides a brief description of Smart Contracts within the Filecoin We conclude with a discussion of future work in Section 8.

$$ \mathcal {L}: $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \Delta_ {\mathrm {p r o o f}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \Delta_ {\mathrm {f a u l t}} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \left(p _ {i}\right) $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

Figure 2: Illustration of the Filecoin Protocol, showing an overview of the Client-Miner interactions. The Storage and Retrieval Markets shown above and below the blockchain, respectively, with time advancing from the Order Matching phase on the left to the Settlement phase on the right. Note that before micropayments can be made for retrieval, the client must lock the funds for the microtransaction.

2 Denition of a Decentralized Storage Network

We introduce the notion of a Decentralized Storage Network (DSN) scheme. DSNs aggregate storage oered by multiple independent storage providers and self-coordinate to provide data storage and data retrieval to clients. Coordination is decentralized and does not require trusted parties: the secure operation of theses systems is achieved through protocols that coordinate and verify operations carried out by individual parties. DSNs can employ dierent strategies for coordination, including Byzantine Agreement, gossip protocols, or CRDTs, depending on the requirements of the system. Later, in Section 4, we provide a construction for the Filecoin DSN.

Denition 2.1. A DSN scheme is a tuple of protocols run by storage providers and clients:

(Put; Get; Manage)

Put(data) ! key: Clients execute the Put protocol to store data under a unique identier key.

Get(key) ! data: Clients execute the Get protocol to retrieve data that is currently stored using key.

Manage(): The network of participants coordinates via the Manage protocol to: control the available storage, audit the service oered by providers and repair possible faults. The Manage protocol is run by storage providers often in conjunction with clients or a network of auditors1.

A DSN scheme must guarantee data integrity and retrievability as well as tolerate management and storage faults dened in the following sections.

2.1 Fault tolerance

2.1.1 Management faults

We dene management faults to be byzantine faults caused by participants in the Manage protocol. A DSN scheme relies on the fault tolerance of its underlining Manage protocol. Violations on the faults tolerance assumptions for management faults can compromise liveness and safety of the system. For example, consider a DSN scheme , where the Manage protocol requires Byzantine Agreement (BA)

assumptions for management faults can compromise liveness and safety of the system. For example, consider a DSN scheme , where the Manage protocol requires Byzantine Agreement (BA) to audit storage providers. In such protocol, the network receives proofs of storage from storage providers and runs BA to agree on the validity of these proofs. If the BA tolerates up to f faults out of n total nodes, then our DSN can tolerate f < n=2 faulty nodes. On violations of these assumptions, audits can be compromised.

2.2 Properties

$$ f < n / 2 $$

We describe the two required properties for a DSN scheme and then present additional properties required by the Filecoin DSN.

$$ m = n $$

$$ f = m - 1 $$

$$ f = m - 1? $$

$$ f = m - x $$

2.2.1 Data Integrity

This property requires that no bounded adversary A can convince clients to accept altered or falsied data at the end of a Get execution.

Denition 2.2. A DSN scheme provides data integrity if: for any successful Put execution for some data d under key k, there is no computationally-bounded adversary A that can convince a client to accept d0, for d0 6= d at the end of a Get execution for identier k.

$$ \mathrm {d} ^ {\prime} \neq $$

2.2.2 Retrievability

This property captures the requirement that, given our fault-tolerance assumptions of , if some data has been successfully stored in and storage providers continue to follow the protocol, then clients can eventually retrieve the data.

Denition 2.3. A DSN scheme provides retrievability if: for any successful Put execution for data under 2 key, there exists a successful Get execution for key for which a client retrieves data..

2.2.3 Other Properties

DSNs can provide other properties specic to their application. We dene three key properties required by the Filecoin DSN: public veriability, auditability, and incentive-compatibility.

Denition 2.4. A DSN scheme is publicly veriable if: for each successful Put, the network of storage providers can generate a proof that the data is currently being stored. The Proof-of-Storage must convince any ecient verier, which only knows key and does not have access to data.

Denition 2.5. A DSN scheme is auditable, if it generates a veriable trace of operation that can be checked in the future to conrm storage was indeed stored for the right duration of time.

Denition 2.6. A DSN scheme is incentive-compatible, if: storage providers are rewarded for successfully oering storage and retrieval service, or penalized for misbehaving, such that the storage providers’ dominant strategy is to store data.

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) veries.

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 verier 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 ecient way, more eciently 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 challenge/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 eciently generating on-demand using a small program. If the program is smaller than the purportedly stored data, this inates 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 verier 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 verier 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.

$$ \mathcal {S} _ {\mathcal {P}} $$

(Setup; Prove; Verify)

PoRep:Setup(1; D) !R; SP; SV, where SPand SVare scheme-specic setup variables for P and V, is a security parameter. PoRep:Setup is used to generate a replica R, and give P and V the necessary information to run PoRep:Prove and PoRep:Verify. Some schemes may require the prover or interaction with a third party to compute PoRep:Setup.

Note. For a formal denition, a description of its properties, and an in-depth study of Proof-of-Replication, we refer the reader to [5].

$$ \mathcal {S} _ {\mathcal {V}} $$ c c PoRep:Prove(SP; R;c) !, where c is a random challenge issued by a verier V, and is a proof c that a prover has access to R a specic replica of D. PoRep:Prove is run by P to produce a for V.

$$ \left(\mathcal {S} _ {\mathcal {P}}, \mathcal {R}, c\right)\rightarrow \pi^ {c} $$

$$ \pi^ {c} $$

$$ \mathcal {V}, $$

c PoRep:Verify(SV;c;) !f0; 1g, which checks whether a proof is correct. PoRep:Verify is run by V and convinces V whether P has been storing R.

$$ \pi^ {c} $$

$$ \left(\mathcal {S} _ {\mathcal {V}}, c, \pi^ {c}\right)\rightarrow {0, 1 } $$

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 verier 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.

Denition 3.2. (Proof-of-Spacetime) A PoSt scheme enables an ecient prover P to convince a verier V that P is storing some data D for some time t. A PoSt is characterized by a tuple of polynomial-time algorithms:

$$ (\mathrm {S e t u p}, \mathrm {P r o v e}, \mathrm {V e r i f y}) $$

PoSt:Setup(1; D) !SP; SV, where SPand SVare scheme-specic setup variables for P and V, is a security parameter. PoSt:Setup is used to give P and V the necessary information to run PoSt:Prove and PoSt:Verify. Some schemes may require the prover or interaction with a third party to compute PoSt:Setup.

$$ \mathcal {S} _ {\mathcal {P}} $$

$$ \mathcal {S} _ {\mathcal {V}} $$

$$ \mathcal {P} $$

$$ \mathrm {p o S t . S e t u p} \left(1 ^ {\lambda}, \mathcal {D}\right)\rightarrow \mathcal {S} _ {\mathcal {P}}, \mathcal {S} _ {\mathcal {V}} $$

$$ \mathcal {P} $$

c c PoSt:Prove(SP; D;c;t) !, where c is a random challenge issued by a verier V, and is a proof c that a prover has access to D for some time t. PoSt:Prove is run by P to produce a for V.

$$ \mathrm {e} \left(\mathcal {S} _ {\mathcal {P}}, \mathcal {D}, c, t\right)\rightarrow \pi^ {c} $$

$$ \pi^ {c} $$

$$ \pi^ {c} $$

c PoSt:Verify(SV;c;t;) !f0; 1g, which checks whether a proof is correct. PoSt:Verify is run by V and convinces V whether P has been storing D for some time t.

$$ \left(\mathcal {S} _ {\mathcal {V}}, c, t, \pi^ {c}\right)\rightarrow {0, 1 } $$

$$ {0, 1 } ^ {*} \rightarrow {0, 1 } ^ {O (\lambda)} $$

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 Practical PoRep and PoSt x 2 L for an instance x of her choice. The non-interactive proof is both zero-knowledge and proof-ofknowledge. Anyone can use the verication key vk to verify the proof; in particular zk-SNARK proofs are publicly veriable: anyone can verify, without interacting with the prover that generated. The proof has constant size and can be veried in time that is linear in jxj.

$$ x \in L $$

$$ \pi $$

$$ \pi , $$

A zk-SNARK for circuit satisability is a triple of polynomial-time algorithms

(KeyGen; Prove; Verify)

KeyGen(1;C) ! (pk; vk). On input security parameter and a circuit C, KeyGen probabilistically samples pk and vk. Both keys are published as public parameters and can be used to prove/verify membership in LC.

$$ \cdot \operatorname {K e y G e n} \left(1 ^ {\lambda}, C\right)\rightarrow (\mathrm {p k}, \mathrm {v k}) $$

$$ L _ {C} $$

Prove(pk, x;w) !. On input pk and input x and witness for the NP-statement w, the prover Prove outputs a non-interactive proof for the statement x 2 LC.

$$ \mathrm {e} (\mathrm {p k}, x, w) \rightarrow \pi $$

$$ x \in L _ {C} $$

Verify(vk, x;) ! f0; 1g. On input vk, an input x, and a proof, the verier Verify outputs 1 if x 2 LC.

$$ \operatorname {V e r i f y} (\mathrm {v k}, x, \pi) \rightarrow {0, 1 } $$

$$ x, $$

$$ \pi , $$

$$ x \in L _ {C} $$

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 denition of the Seal operation see [5]. The above operation can be realized with SealAES 256, and such that SealAES 256takes 10-100x longer than the honest challenge-prove-verify sequence. Note that it is important to choose such that running SealBC is distinguishably more expensive than running Prove with random access to R.

$$ \mathrm {S e a l} _ {\mathrm {A E S} - 2 5 6} ^ {\tau}, $$

$$ \mathrm {S e a l} _ {\mathrm {B C}} ^ {\tau} $$

This section describes the construction of the PoRep protocol and includes a simplied protocol sketch in Figure 4; implementation and optimization details are omitted.

3.4.3 Practical PoRep construction

Creating a Replica. The Setup algorithm generates a replica via the Seal operation and a proof that it was correctly generated. The prover generates the replica and sends the outputs (excluding R) to the verier. 2 Setup

6 inputs: 6 6

$$ \left(\mathrm {p k} _ {\mathcal {P}}, \mathrm {s k} _ {\mathcal {P}}\right) $$

outputs: replica R, Merkle root rt of R, proofSEAL

Proving Storage. The Prove algorithm generates a proof of storage for the replica. The prover receives a random challenge, c, from the verier, which determines a specic leaf Rcin the Merkle tree of R with root rt; the prover generates a proof of knowledge about Rcand its Merkle path leading up to rt.

2 Setup 6 inputs:

$$ \mathcal {R} _ {c} $$

2 Prove 6 inputs:

6 inputs: 6 6

{ prover Proof-of-Storage key pkPOS { replica R

{ replica R { random challenge c

{ random challenge c

outputs: a proofPOS

Verifying the Proofs. The Verify algorithm checks the validity of the proofs of storage given the Merkle root of the replica and the hash of the original data. Proofs are publicly veriable: nodes in the distributed system maintaining the ledger and clients interested in particular data can verify these proofs. 2

2 Verify 6 inputs:

6 inputs: 6 6

{ prover public key, pkP { verier SEAL and POS keys vk

{ verier SEAL and POS keys vkSEAL, vkPOS { hash of data D, h

{ hash of data D, hD { Merkle root of replica R, rt

{ Merkle root of replica R, rt

{ random challenge, c { tuple of proofs, (

{ tuple of proofs, (SEAL;POS)

3.4.4 Practical PoSt construction

This section describes the construction of the PoSt protocol and includes a simplied protocol sketch in Figure 4; implementation and optimization details are omitted. The Setup and Verify algorithm are equivalent to the PoRep construction, hence we describe here only Prove.

Proving space and time. The Prove algorithm generates a Proof-of-Spacetime for the replica. The prover receives a random challenge from the verier and generate Proofs-of-Replication in sequence, using the output of a proof as an input of the other for a specied amount of iterations t (see Figure 3). 2

2 Prove 6 6 inputs:

6 6 inputs: 6 6

{ prover PoSt key pkPOST { replica R

{ replica R { random challenge c

{ random challenge c { time parameter t

{ time parameter t

outputs: a proofPOST

Figure 3: Illustration of the underlying mechanism of PoSt.Prove showing the iterative proof to demonstrate storage over time.

3.5 Usage in Filecoin

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

Filecoin PoRep protocol Setup inputs: {prover key pair (pkP; skP) {prover SEAL key pkSEAL {data D outputs: replica R, Merkle root rt of R, proof SEAL 1)Compute hD := CRH(D) 2)Compute R := Seal (D; skP) 3)Compute rt := MerkleCRH(R) 4)Set x := (pkP;hD; rt) 5)Set ~w := (skP; D) 6)ComputeSEAL:= SCIP:Prove(pkSEAL;x; w) 7)Output R, rt,SEAL Prove inputs: {prover Proof-of-Storage key pkPOS {replica R {random challenge c outputs: a proofPOS 1)Compute rt := MerkleCRH(R) 2)Compute path := Merkle path from rt to leaf Rc 3)Set ~x := (rt;c) 4)Set ~w := (path; Rc) 5)ComputePOS:= SCIP:Prove(pkPOS;x; ~w) 6)OutputPOS Verify inputs: {prover public key, pkP {verier SEAL and POS keys vkSEAL, vkPOS {hash of data D, hD {Merkle root of replica R, rt {random challenge, c {tuple of proofs, (SEAL;POS) outputs: bit b, equals 1 if proofs are valid 1)Set ~x1 := (pkP;hD; rt) 2)Compute b1 := SCIP:Verify(vkSEAL; ~x1;SEAL) 3)Set ~x2 := (rt;c) 4)Compute b2 := SCIP:Verify(vkPOS; ~x2;POS) 5)Output b1 ^ b2 Figure 4: Proof-of-Replication and Proof-of-Spacetime

$$ \left(\mathrm {p k} _ {\mathcal {P}}, \mathrm {s k} _ {\mathcal {P}}\right) $$

$$ h _ {\mathcal {D}} := \mathrm {C R H} (\mathcal {D}) $$

Filecoin PoSt protocol Setup inputs: {prover key pair (pkP; skP) {prover POST key pair pkPOST {some data D outputs: replica R, Merkle root rt of R, proof SEAL 1)Compute R, rt,SEAL:= PoRep:Setup(pkP, skP; pkSEAL, D) 2)Output R, rt,SEAL Prove inputs: {prover PoSt key pkPOST {replica R {random challenge c {time parameter t outputs: a proofPOST 1)SetPOST:= ? 2)Compute rt := MerkleCRH(R) 3)For i = 0:::t: 0 a)Set c := CRH(POSTjjcjji) 0 b)ComputePOS:= PoRep:Prove(pkPOS; R;c ) c)Set x := (rt;c;i) d)Set ~w := (POS;POST) e)ComputePOST:= SCIP:Prove(pkPOST;x; ~w) 4)OutputPOST Verify inputs: {prover public key pkP {verier SEAL and POST keys vkSEAL, vkPOST {hash of some data hD {Merkle root of some replica rt {random challenge c {time parameter t {tuple of proofs (SEAL;POST) outputs: bit b, equals 1 if proofs are valid 1)Set ~x1 := (pkP;hD; rt) 2)Compute b1 := SCIP:Verify(vkSEAL; ~x1;SEAL) 3)Set ~x2 := (rt;c;t) 4)Compute b2 := SCIP:Verify(vkPOST; ~x2;POST) 5)Output b1 ^ b2

$$ \left(\mathrm {p k} _ {\mathcal {P}}, \mathrm {s k} _ {\mathcal {P}}\right) $$

$$ b _ {1} := \mathrm {S C I P}. \mathrm {V e r i f y} \left(\mathrm {v k} _ {\mathrm {S E A L}}, \vec {x} _ {1}, \pi_ {\mathrm {S E A L}}\right) $$

$$ c ^ {\prime} := \mathrm {C R H} \left(\pi_ {\mathrm {P O S T}} | | c | | i\right) $$

$$ \mathcal {R} $$

Figure 4: Proof-of-Replication and Proof-of-Spacetime protocol sketches. Here CRH denotes a collisionresistant hash, ~x is the NP-statement to be proven, and ~w is the witness.

$$ \vec {x} $$

4 Filecoin: a DSN Construction

The Filecoin DSN is a decentralized storage network that is auditable, publicly veriable and designed on incentives. Clients pay a network of miners for data storage and retrieval; miners oer disk space and bandwidth in exchange of payments. Miners receive their payments only if the network can audit that their service was correctly provided.

In this section, we present the Filecoin DSN construction, based on the DSN denition and Proof-of- Spacetime.

4.1 Setting

4.1.1 Participants

Any user can participate as a Client, a Storage Miner, and/or a Retrieval Miner.

Clients pay to store data and to retrieve data in the DSN, via Put and Get requests.

Storage Miners provide data storage to the network. Storage Miners participate in Filecoin by oering

Storage Miners provide data storage to the network. Storage Miners participate in Filecoin by oering

Storage Miners provide data storage to the network. Storage Miners participate in Filecoin by oering their disk space and serving Put requests. To become Storage Miners, users must pledge their storage by depositing collateral proportional to it. Storage Miners respond to Put requests by committing to

by depositing collateral proportional to it. store the client’s data for a specied time. them to the blockchain to prove to the Network that they are storing the data through time. In case of invalid or missing proofs, Storage Miners are penalized and loose part of their collateral. Miners are also eligible to mine new blocks, and in doing so they hence receive the mining reward for

by depositing collateral proportional to it. Storage Miners respond to Put requests by committing to store the client’s data for a specied time. Storage Miners generate Proofs-of-Spacetime and submit them to the blockchain to prove to the Network that they are storing the data through time. In case of invalid or missing proofs, Storage Miners are penalized and loose part of their collateral. Storage Miners are also eligible to mine new blocks, and in doing so they hence receive the mining reward for

Miners are also eligible to mine new blocks, and in doing so they hence receive the mining reward for creating a block and transaction fees for the transactions included in the block.

Retrieval Miners provide data retrieval to the Network. Retrieval Miners participate in Filecoin by serving data that users request via Get. Unlike Storage Miners, they are not required to pledge, commit to store data, or provide proofs of storage. It is natural for Storage Miners to also participate as Retrieval Miners. Retrieval Miners can obtain pieces directly from clients, or from the Retrieval Market.

We personify all the users that run Filecoin full nodes as one single abstract entity: The Network. The Network acts as an intermediary that runs the Manage protocol; informally, at every new block in the Filecoin blockchain, full nodes manage the available storage, validate pledges, audit the storage proofs, and repair possible faults.

4.1.4 The Markets

Our protocol is applied on top of a ledger-based currency; for generality we refer to this as the Ledger, L. At any given time t (referred to as epoch), all users have access to Lt, the ledger at epoch t, which is a sequence of transactions. The ledger is append-only3. The Filecoin DSN protocol can be implemented on any ledger that allows for the verication of Filecoin’s proofs; we show how we can construct a ledger based on useful work in Section 6.

$$ ^ {3} t < t ^ {\prime} $$

$$ \mathcal {L} _ {t} ^ {\prime} $$

4.2 Data Structures

Pieces. A piece is some part of data that a client is storing in the DSN. For example, data can be deliberately divided into many pieces and each piece can be stored by a dierent set of Storage Miners.

Sectors. A sector is some disk space that a Storage Miner provides to the network. Miners store pieces from clients in their sectors and earn tokens for their services. In order to store pieces, Storage Miners must pledge their sectors to the network.

AllocationTable. The AllocTable is a data structure that keeps track of pieces and their assigned sectors. The AllocTable is updated at every block in the ledger and its Merkle root is stored in the latest block. In practice, the table is used to keep the state of the DSN, allowing for quick look-ups during proof verication. For more details, see Figure 5.

Orders. An order is a statement of intent to request or oer a service. Clients submit bid orders to the markets to request a service (resp. Storage Market for storing data and Retrieval Market for retrieving data) and Miners submit ask orders to oer a service. The order data structures are shown in Figure 10. The Market Protocols are detailed in Section 5.

Orderbook. Orderbooks are sets of orders. See the Storage Market orderbook in Section 5.2.2 and Retrieval Market orderbook in Section 5.3.2 for details.

Pledge. A pledge is a commitment to oer storage (specically a sector) to the network. Storage Miners must submit their pledge to the ledger in order to start accepting orders in the Storage Market. A pledge consists of the size of the pledged sector and the collateral deposited by the Storage Miner (see Figure 5 for more details).

$$ \mathcal {M} _ {2}..} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} ^ {i} $$

$$ \left(\mathcal {O} ^ {1}.. \mathcal {O} ^ {n}\right) $$

$$ \left{\mathcal {O} _ {\mathrm {d e a l}}.. \mathcal {O} _ {\mathrm {d e a l}} \right} $$

We give a brief overview of the client cycle; an in-depth explanation of the following protocols is given in Section 5.

4.3 Protocol

Figure 5: Data Structures in a DSN scheme

1. Put: Client stores data in Filecoin.

Clients can store their data by paying Storage Miners in Filecoin tokens. The Put protocol is described in detail in Section 5.2.

A client initiates the Put protocol by submitting a bid order to the Storage Market orderbook (by submitting their order to the blockchain). When a matching ask order from miners is found, the client sends the piece to the miner. Both parties sign a deal order and submit it to the Storage Market orderbook.

Clients should be able to decide the amount of physical replicas of their pieces either by submitting multiple orders (or specifying a replication factor in the order). Higher redundancy results in a higher tolerance of storage faults.

2. Get: Client retrieves data from Filecoin.

Clients can retrieve any data stored in the DSN by paying Retrieval Miners in Filecoin tokens. The Get protocol is described in detail in Section 5.3.

A client initiates the Get protocol by submitting a bid order to the Retrieval Market orderbook (by gossiping their order to the network). When a matching ask order from miners is found, the client receives the piece from the miner. When received, both parties sign a deal order and submit it to the blockchain to conrm that the exchange succeeded.

1. Pledge: Storage Miners pledge to provide storage to the Network.

Storage Miners pledge their storage to the network by depositing collateral via a pledge transaction in the blockchain, via Manage:PledgeSector. The collateral is deposited for the time intended to provide the service, and it is returned if the miner generates proofs of storage for the data they commit to store. If some proofs of storage fail, a proportional amount of collateral is lost. Once the pledge transaction appears in the blockchain, miners can oer their storage in the Storage

Once the pledge transaction appears in the blockchain, miners can oer their storage in the Storage Market: they set their price and add an ask order to the market’s orderbook. 2

2 Manage:PledgeSector 6 6 inputs:

6 6 inputs: 6 6

{ current allocation table allocTable { pledge request pledge

2. Receive Orders: Storage Miners get storage requests from the Storage Market.

outputs: bit b, equals 1 if successful

Check if their orders are matched with a corresponding bid order from a client, via Put:MatchOrders.

Once the pledge transaction appears in the blockchain (hence in the AllocTable), miners can oer their storage in the Storage Market: they set their price and add an ask order to the market’s orderbook via Put:AddOrders. 2

{ the current Storage Market OrderBook q { query order to match O

inputs:

outputs: allocTable0

q { query order to match O outputs: matching orders O1

n outputs: matching orders O1..O

Once orders are matched, clients send their data to the Storage Miners. When receiving the piece, miners run Put:ReceivePiece. When the data is received, both the miner and the client sign a deal order and submit it to the blockchain.

2 Put:ReceivePiece 6 inputs:

6 6 inputs: 6

{ signing key for Mj. { current orderbook OrderBook

$$ \mathcal {M} _ {j} $$

{ current orderbook OrderBook { ask order O

{ ask order Oask { bid order O

$$ \mathcal {O} _ {\mathrm {a s k}} $$

{ bid order Obid { piece p

$$ \mathcal {O} _ {\mathrm {b i d}} $$

{ piece p outputs: deal order O

outputs: deal order Odealsigned by Ciand Mj

$$ \mathcal {C} _ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} _ {j} $$

3. Seal: Storage Miners prepare the pieces for future proofs.

Storage Miners’ storage is divided in sectors, each sector contains pieces assigned to the miner. The Network keeps track of each Storage Miners’ sector via the allocation table. When a Storage Miner sector is lled, the sector is sealed. Sealing is a slow, sequential operation that transforms the data in a sector into a replica, a unique physical copy of the data that is associated to the public key of the Storage Miner. Sealing is a necessary operation during the Proof-of-Replication as described in Section 3.4. 2

2 Manage:SealSector 6 inputs:

6 6 inputs: 6

{ miner public/private key pair M { sector index j

{ sector index j { allocation table allocTable

{ sector index j { allocation table allocTable

outputs: a proofSEAL, a root hash rt

4. Prove: Storage Miners prove they are storing the committed pieces.

When Storage Miners are assigned data, they must repeatedly generate proofs of replication to guarantee they are storing the data (for more details, see Section 3). Proofs are posted on the blockchain and the Network veries them. 2

2 Manage:ProveSector 6 6 inputs:

6 6 inputs: 6 { miner public/private key pair M

{ miner public/private key pair M { sector index j

1. Receive Orders: Retrieval Miners get data requests from the Retrieval Market.

Retrieval Miners announce their pieces by gossiping their ask orders to the network: they set their price and add an ask order to the market’s orderbook.

outputs: none

$$ \mathcal {O} ^ {1}.. \mathcal {O} ^ {n} $$

{ sector index j { challenge c

Then, Retrieval Miners check if their orders are matched with a corresponding bid order from a client.

2 Get:MatchOrders 6 inputs:

6 6 inputs: 6

{ the current Retrieval Market OrderBook q { query order to match O

q { query order to match O outputs: matching orders O1

n outputs: matching orders O1..O

2. Send: Retrieval Miners send pieces to the client.

Once orders are matched, Retrieval Miners send the piece to the client (see Section 5.3 for details). When the piece is received, both the miner and the client sign a deal order and submit it to the blockchain. 2

2 Put:SendPiece 6 inputs:

6 6 inputs: 6

{ an ask order Oask { a bid order O

$$ \mathcal {O} _ {\mathrm {a s k}} $$

{ a bid order Obid { a piece p

$$ \mathcal {O} _ {\mathrm {b i d}} $$

{ a piece p outputs: a deal order O

outputs: a deal order Odealsigned by Mi

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} $$

1. Assign: The Network assigns clients’ pieces to Storage Miners’ sectors.

We give an informal overview of the operations run by the network.

Clients initiate the Put protocol by submitting a bid order in the Storage Market4.

When ask and bid orders match, the involved parties jointly commit to the exchange and submit a deal order in the market. At this point, the Network assigns the data to the miner and makes a note of it in the allocation table. 2

2 Manage:AssignOrders 6 6 inputs:

6 6 inputs: 6 6 { deal orders O

1 n { deal orders Odeal..Odeal { allocation table allocTable

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {1} \dots \mathcal {O} _ {\mathrm {d e a l}} ^ {n} $$

deal deal { allocation table allocTable outputs: updated allocation table allocTable0

outputs: updated allocation table allocTable0

2. Repair: The Network nds faults and attempt to repair them.

All the storage allocations are public to every participant in the network. At every block, the Network checks if the required proofs for each assignment are present, checks that they are valid, and acts accordingly:

if any proof is missing or invalid, the network penalizes the Storage Miners by taking part of their collateral,

$$ \Delta_ {\mathrm {f a u l t}}) $$

if every Storage Miner storing this piece is faulty, then the piece is lost and the client gets refunded.

2 Manage:RepairOrders 6 inputs:

6 6 inputs: 6

{ current time t { current ledger L

{ current ledger L { table of storage allocations allocTable

{ table of storage allocations allocTable 1 n

1 n outputs: orders to repair Odeal..Odeal, updated allocation table allocTable

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {1} \dots \mathcal {O} _ {\mathrm {d e a l}} ^ {n} $$

$$ s \left(\therefore , \mathcal {O} _ {\mathrm {b i d}}\right) $$

$$ \left(\therefore , \mathcal {O} _ {\mathrm {a s k}}\right) $$

$$ \operatorname {S e n d P i e c e} \left(\dots , \mathcal {O} _ {\mathrm {b i d}}, p\right) $$

$$ \mathrm {R e c e i v e P i e c e} \left(\dots , \mathcal {O} _ {\mathrm {a s k}}\right) $$

$$ \mathrm {A d d O r d e r s} (\dots , \mathcal {O} _ {\mathrm {d e a l}}) $$

$$ \operatorname {A d d O r d e r s} \left(\mathcal {O} _ {\mathrm {d e a l}}\right) $$

$$ \mathrm {A d d O r d e r} \left(\therefore , \mathcal {O} _ {\mathrm {b i d}}\right) $$

$$ \operatorname {A d d O r d e r} \left(\therefore , \mathcal {O} _ {\mathrm {a s k}}\right) $$

$$ \operatorname {S e n d P i e c e} \left(\therefore , \mathcal {O} _ {\mathrm {a s k}}, p\right) $$

$$ \mathrm {R e c e i v e P i e c e} \left(\dots , \mathcal {O} _ {\mathrm {b i d}}\right) $$

$$ \mathrm {A d d O r d e r s} \left(\therefore , \mathcal {O} _ {\mathrm {d e a l}}\right) $$

$$ \mathrm {A d d O r d e r s} \left(\dots , \mathcal {O} _ {\mathrm {d e a l}}\right) $$

Figure 6: Example execution of the Filecoin DSN, grouped by party and sorted chronologically by row

4.4 Guarantees and Requirements

Achieving Integrity : Pieces are named after their cryptographic hash. After a Put request, clients only need to store this hash to retrieve the data via Get and to verify the integrity of the content received.

Achieving Retrievability : In a Put request, clients specify the replication factor and the type of erasure coding desired, specifying in this way the storage to be (f;m)-tolerant. The assumption is that given m Storage Miners storing the data, a maximum of f faults are tolerated. By storing data in more than one Storage Miner, a client can increase the chances of recovery, in case Storage Miners go oine or disappear.

Achieving Incentive Compatibility : Informally, miners are rewarded for the storage they are providing. When miners commit to store some data, then they are required to generate proofs. Miners that skip proofs are penalized (by losing part of their collateral) and not rewarded for their storage.

Achieving Condentiality : Clients that desire for their data to be stored privately, must encrypt their data before submitting them to the network.

$$ \mathcal {O} ^ {1}.. \mathcal {O} ^ {n} $$

$$ \mathrm {t x} _ {\mathrm {o r d e r}} \mathrm {t o} \mathcal {L} $$

$$ \mathrm {t x} _ {\mathrm {o r d e r}} := \left(\mathcal {O} ^ {1},..,\mathcal {O} ^ {n}\right) $$

$$ \mathcal {L} $$

Put Protocol Get Protocol Market Market AddOrders AddOrders 1 n inputs: list of orders O1..On inputs: list of orders O..O outputs: bit b, equals 1 if successful outputs: none 1 n 1)Gossip O1..Onto the network 1)Set txorder:= (O;::; O) 2)Submit txorderto L 3)Wait for txorderto be included in L MatchOrders 4)Output 1 on success, 0 otherwise inputs: {the current Retrieval Market OrderBook {query order to match Oq MatchOrders outputs: matching orders O1..On inputs: 1)Match each Oiin OrderBook such that: {the current Storage Market OrderBook q a)Check O :piece is equal to Oi q:piece {query order to match O 1 n b)If Oqis an ask order: outputs: matching orders O..O i i)Check if Oiis bid order 1)Match each O in OrderBook such that: q ii)Check O :price Oi q:price a)If O is an ask order: i c)If Oqis a bid order: i)Check if O is bid order i q i)Check if Oiis ask order ii)Check O :price O :price i q ii)Check O :price Oi q:price iii)Check O :size O :space q 2)Output matched orders O1:::On b)If O is a bid order: i)Check if Oiis ask order Exchange ii)Check Oi:price Oq:price i qSendPiece iii)Check O :space O :size 1 ninputs: 2)Output matched orders O :::O {an ask order Oask Exchange {a bid order Obid SendPiece {a piece p inputs: outputs: a deal order Odealsigned by Ci {an ask order O 1)Create Odeal: ask {a bid order O a)Set Odeal.ask := Oask bid {a piece p b)Set Odeal.bid := Odeal outputs: a deal order O signed by M 2)Get identity of Cifrom Obidsignature deal i 1)Get identity of M from O signature 3)Setup a micropayment channel with Ci i ask 2)Send (O,O,p) to M 4)For each block of data pjof p: ask bid i 3)Receive O signed by M a)Setjto be a merkle path from H(p) to pj deal i 4)Check if O is valid according to Denition 5.2 b)Send (Odeal,pj,j) to Ci deal 5)Output O c)Receive hOdeal, j iCi deal 5)Output Odeal ReceivePiece inputs: ReceivePiece {signing key for M. inputs: j {current orderbook OrderBook {a client’s key Cj { ask order O {an ask order Oask ask { bid order O {a bid order Obid bid {piece p {merkle tree hash of p in the orders hp outputs: deal order O signed by C and M outputs: a piece p deal i j 1)Check if O is valid: 1)Create Odeal: bid a)Check if O is in OrderBook a)Set Odeal.ask := Oask bid b)Check if O is not referenced by other active O b)Set Odeal.bid := Obid bid deal c)Check if O.size is equal to jpj 2)Get identity of Mifrom Oasksignature bid d)Check if O is signed by M 3)Set up a micropayment channel with Mi(or re-using i 2)Store p locally an existing one) 3)Set O := hO, O, H(p) i 4)When receiving (Odeal, pj,j) from Mi: deal ask deal Mi 4)Get identity of C from O a)Check if Odealis valid and matches Oaskand Obid j bid 5)Send O to C b)Check ifjis a valid merkle-path with root hash deal j 6)Output O hp deal c)Send hOdeal, j iCi 5)Output p

$$ \mathrm {t x} _ {\mathrm {o r d e r}} $$

$$ \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {1}.. \mathcal {O} ^ {n} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} ^ {1}.. \mathcal {O} ^ {n} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} ^ {i}. \mathrm {p r i c e} \geq \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {i} $$

$$ \leq \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} ^ {q} $$

$$ \leq \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} ^ {1} \dots \mathcal {O} ^ {n} $$

$$ \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {1}.. \mathcal {O} ^ {n} $$

$$ \geq \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {O} ^ {1}.. \mathcal {O} ^ {n} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} := \langle \mathcal {O} _ {\mathrm {a s k}}, \mathcal {O} _ {\mathrm {d e a l}}, \mathcal {H} (p) \rangle_ {\mathcal {M} _ {i}} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} ^ {q} $$

$$ (\mathcal {O} _ {\mathrm {a s k}}, \mathcal {O} _ {\mathrm {b i d}}, p) $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} _ {j} \tag {ook} $$

$$ \mathcal {O} ^ {i} $$

$$ \begin{array}{l} \mathcal {O} _ {\mathrm {b i d}} \ \mathcal {O} _ {\mathrm {b i c}} \ \end{array} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {C} _ {i} $$

$$ \leq \mathcal {O} ^ {q} $$

$$ \mathcal {O} ^ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {C} _ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ p _ {j} $$

$$ p $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ p $$

$$ \mathcal {O} ^ {1} \dots \mathcal {O} ^ {n} $$

$$ := \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {O} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {H} (p) $$

$$ \mathcal {O} _ {\mathrm {d e a l}}. \mathrm {b i d} := \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {C} _ {i} $$

$$ h _ {p} $$

$$ p _ {j} $$

$$ \left(\mathcal {O} _ {\mathrm {d e a l}}, p _ {j}, \pi_ {j}\right) $$

$$ p: $$

$$ \mathcal {C} _ {i} $$

$$ \pi_ {j} $$

$$ \langle \mathcal {O} _ {\mathrm {d e a l}}, \mathrm {j} \rangle_ {\mathcal {C} _ {i}} $$

$$ \mathcal {C} _ {j} $$

Figure 7: Description of the Put and Get Protocols in the Filecoin DSN

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ p $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i}: $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \pi_ {j} $$

$$ \left(\mathcal {O} _ {\mathrm {d e a l}}, p _ {j}, \pi_ {j}\right) $$

Manage Protocol

Manage Protocol Network Miner AssignOrders PledgeSector inputs: inputs: {deal orders O1..On{current allocation table allocTable deal deal

{deal orders O1..On deal deal {allocation table allocTable outputs: updated allocation table allocTable0 1)Copy allocTable in allocTable0 2)For each order Oi: deal a)Check if Oiis valid according to Denition 5.2 deal b)Get M from Oisignature j deal c)Add details from Oito allocTable0 deal 0

{current allocation table allocTable {pledge request pledge outputs: allocTable0 1)Copy allocTable to allocTable0 2)Set txpledge:= (pledge) is valid according to Denition 5.2 3)Submit txpledgeto L 4)Wait for txpledgeto be included in L 5)Add new sector of size pledge:size in allocTable0 6)Output allocTable0

c)Add details from Odealto allocTable 6)Output allocTable0 3)Output allocTable0 SealSector RepairOrders

RepairOrders inputs: {current time t {current ledger L {table of storage allocations allocTable outputs: orders to repair O1..On, updated allocadeal deal tion table allocTable 1)For each allocEntry in allocTable: a)If t < allocEntry:last + proof: skip b)Update allocEntry:last= t c)Check if is in Ltproof:tand PoSt.Verify( d)On success: update allocEntry:missing= 0 e)On failure: i)update allocEntry:missing++ ii)penalize collateral from Mi’s pledge f)If allocEntry:missing >faultthen set all the orders from the current sector as failed orders 2)Output failed orders O1..Onand allocTable deal deal

SealSector inputs: {miner public/private key pair M {sector index j {allocation table allocTable outputs: a proofSEAL, a root hash rt , updated alloca- 1)Find all the pieces p1..pn in sector Sjin the allocTable 2)Set D := p1jp2j::jpn 3)Compute (R; rt,SEAL) := PoSt:Setup(M; pkSEAL; D) 4)OutputSEAL, rt ) ProveSector inputs: {miner public/private key pair M {sector index j {challenge c then set all the orders outputs: a proofPOS 1)Find R for sector j . 2)ComputePOST:= PoSt:Prove(pkPOST; R;c;proof) 3)OutputPOST

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {1} \dots \mathcal {O} _ {\mathrm {d e a l}} ^ {n} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {i}: $$

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {i} $$

$$ \mathcal {M} _ {j} $$

$$ \mathrm {t x} _ {\mathrm {p l e d g e}} := (\mathrm {p l e d g e}) $$

$$ t x _ {\mathrm {p l e d g e}} $$

$$ t x _ {\mathrm {p l e d g e}} $$

$$ \mathcal {L} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {1} \dots \mathcal {O} _ {\mathrm {d e a l}} ^ {n} $$

$$ \mathcal {M} _ {i} $$

$$ \Delta_ {\mathrm {p r o o f}}: $$

$$ r t $$

$$

\Delta_ {\mathrm {f a u l t}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} ^ {1} \dots \mathcal {O} _ {\mathrm {d e a l}} ^ {n} $$

$$ \mathcal {S} _ {j} $$

$$ \mathcal {L} _ {t - \Delta_ {\mathrm {p r o o f}}}: t $$

$$ p _ {1}.. p _ {n} $$

$$ \mathcal {D} := p _ {1} \left| p _ {2} \right|.. \left| p _ {n} \right. $$

Figure 8: Description of the Manage Protocol in the Filecoin DSN

5 Filecoin Storage and Retrieval Markets

Filecoin has two markets: the Storage Market and the Retrieval Market. The two markets have the same structure but dierent design. The Storage Market allows Clients to pay Storage Miners to store data. The Retrieval Market allows Clients to retrieve data by paying Retrieval Miners to deliver the data. In both cases, clients and miners can set their oer and demand prices or accept current oers. The exchanges are run by the Network - a personication of the network of full nodes in Filecoin. The network guarantees that miners are rewarded by the clients when providing the service.

5.1 Veriable Markets

Exchange Markets are protocols that facilitate exchange of a specic good or service. They do this by enabling buyers and sellers to conduct transactions. For our purposes, we require exchanges to be veriable: a decentralized network of participants must be able to verify the exchange between buyers and sellers.

We present the notion of Veriable Markets, where no single entity governs an exchange, transactions are transparent, and anybody can participate pseudonymously. Veriable Market protocols operate the exchange of goods/services in a decentralized fashion: consistency of the orderbooks, orders settlements and correct execution of services are independently veried via the participants - miners and full nodes in the case of Filecoin. We simplify veriable markets to have the following construction:

Denition 5.1. A veriable Market is a protocol with two phases: order matching and settlement. Orders are statements of intent to buy or sell a security, good or service and the orderbook is the list of all the available orders.

Figure 9: Generic protocol for Veriable Markets

We design the Storage Market protocol accordingly to the following requirements:

The Storage Market is a veriable market which allows clients (i.e. buyers) to request storage for their data and Storage Miners (i.e. sellers) to oer their storage.

In-chain orderbook: It is important that: (1) Storage Miners orders are public, so that the lowest price is always known to the network and clients can make informed decision on their orders, (2) client orders must be always submitted to the orderbook, even when they accept the lowest price, in this way the market can react to the new oer. Hence, we require orders to be added in clear to the Filecoin blockchain in order to be added to the orderbook.

Participants committing their resources: We require both parties to commit to their resources as a way to avoid disservice: to avoid Storage Miners not providing the service and to avoid clients not having available funds. In order to participate to the Storage Market, Storage Miners must pledge, depositing a collateral proportional to their amount of storage in DSN (see Section 4.3.3 for more details). In this way, the Network can penalize Storage Miners that do not provide proofs of storage for the pieces they committed to store. Similarly, clients must deposit the funds specied in the order, guaranteeing in this way commitment and availability of funds during settlement.

Self-organization to handle faults: Orders are only settled if Storage Miners have repeatedly proved that they have stored the pieces for the duration of the agreed-upon time period. The Network must be able to verify the existence and the correctness of these proofs and act according to the rules outlined in the Repair portion of Subsection 4.3.4.

5.2.2 Datastructures

Put Orders. There are three types of orders: bid orders, ask orders and deal orders. Storage Miners create ask orders to add storage, clients create bid orders to request storage, when both parties agree on a price, they jointly create a deal order. The data structures of the orders are shown in detail in Figure 10, and the parameters of the orders are explicitly dened.

Put Orderbook. The Orderbook in the Storage Market is the set of currently valid and open ask, bid and deal orders. Users can interact with the orderbook via the methods dened in the Put protocol: AddOrders, MatchOrders as described in Figure 7.

The orderbook is public and every honest user has the same view of the orderbook. At every epoch, new orders are added to the orderbook if new order transactions (txorder) appear in new blockchain blocks; orders are removed if they are cancelled, expired or settled. Orders are added in blockchain blocks, hence in the orderbook, if they are valid:

$$ \left(\mathrm {t x} _ {\mathrm {o r d e r}}\right) $$

Denition 5.2. We dene the validity of bid, ask, deal orders:

(Valid bid order): A bid order from client Ci, Obid:= hsize; funds[; price; time; coll; coding]iCiis valid if:

$$ \mathcal {C} _ {i}, \mathcal {O} _ {\mathrm {b i d}} := $$

Cihas at least the amount of funds available in their account.

$$ \mathcal {C} _ {i} $$

time is not set in the past The order must guarantee at least a minimum amount5

The order must guarantee at least a minimum amount5 of epochs of storage.

$$ \mathcal {M} _ {i}, \mathcal {O} _ {\mathrm {a s k}} := \langle \mathrm {s p a c e}, \mathrm {p r i c e} \rangle_ {\mathcal {M} _ {i}} $$

Mihas pledged to be a miner and the pledge will not expire before time epochs. space must be less than M ’s available storage: M pledged storage minus the storage committed

$$ \mathcal {M} _ {i} $$

Remark. If a malicious client receives a signed deal from a Storage Miner, but never adds it to the orderbook, then the Storage Miner cannot re-use the storage committed in the deal. The eld ts prevents this attack because, after ts, the order becomes invalid and cannot be submitted in the orderbook.

$$ \mathcal {O} _ {\mathrm {d e a l}} := \langle \mathrm {a s k}, \mathrm {b i d}, \mathrm {t s} \rangle_ {\mathcal {C} _ {i}, \mathcal {M} _ {j}} $$

space must be less than Mi’s available storage: Mipledged storage minus the storage committed in the orderbook (in ask and deal orders).

$$ \mathcal {M} _ {i} $$

bid references an order Obidsuch that: it is in the Storage Market OrderBook, no other deal orders in the Storage Market OrderBook mention it, it is signed by Mj. ts is not set in the future or too far in the past.

ask references an order Oasksuch that: it is in the Storage Market OrderBook, no other deal orders in the Storage Market OrderBook mention it, it is signed by Ci. bid references an order O such that: it is in the Storage Market OrderBook, no other deal orders

$$ \mathcal {C} _ {i} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {M} _ {j} $$

ts is not set in the future or too far in the past.

Storage Market Orders bid order Obid:= hsize; funds[; price; time; coll; coding]iCi size, the size of the piece to be stored funds, the total amount that client Ci is depositing time, the maximum epoch time for which the le a should be stored b price, the spacetime price in Filecoin coll, the collateral specic to this piece that the miner is required to deposit coding, the erasure coding scheme for this piece ask order Oask: h space, price iMi space, amount of space Storage Miner Mi is providing in the order price, the spacetime price in Filecoin deal order Odeal: h ask, bid, ts, hash iCi;Mj ask, a cryptographic reference to Oaskfrom Ci order, a cryptographic reference to Obidfrom Mi ts, timestamp epoch in which the order has been signed by Mi hash cryptographic hash of the piece that Mj will store aIf not specied, the piece will be stored until expiration of funds. bIf not specied, when a Storage Miner is faulty, the network can re-introduce the order at the current best price.

$$ \mathcal {O} _ {\mathrm {b i d}} := $$

$$ \mathcal {C} _ {i} $$

$$ \rangle \mathcal {M} _ {i} $$

Retrieval Market Orders bid order Obid: h piece, price iCi a piece, the index of the piece requested price, the price at which Ciis paying for one retrieval ask order Oask: h piece, price iMi piece, the index of the piece requested price, the price at which Mjis serving the piece for deal order Odeal: h ask, order iCi;Mj ask, a cryptographic reference to Oaskfrom Ci order, a cryptographic reference to Oask from Ci aOnly pieces stored in Filecoin can be requested

$$ \mathcal {O} _ {\mathrm {a s k}}: $$

$$ \mathcal {M} _ {i} $$

$$ \rangle \mathcal {C} _ {i}, \mathcal {M} _ {j} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {M} _ {j} $$

$$ \mathcal {C} _ {i} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}}: \langle $$

$$ \rangle \mathcal {C} _ {i} $$

$$ \mathcal {C} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {j} $$

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \rangle \mathcal {M} _ {i} $$

$$ \rangle \mathcal {C} _ {i}, \mathcal {M} _ {j} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {O} _ {\mathrm {a s k}}: $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {C} _ {i} $$

$$ \mathcal {C} _ {i} $$

Figure 10: Orders data structures for the Retrieval and Storage Markets

5.2.3 The Storage Market Protocol

In brief, the Storage Market protocol is divided in two phases: order matching and settlement :

Order Matching : Clients and Storage Miners submit their orders to the orderbook by submitting a transaction to the blockchain (step 1). When orders are matched, the client sends the piece to the Storage Miner and both parties sign a deal order and submit it to the orderbook (step 2).

Settlement : Storage Miners seal their sectors (step 3a), generate proofs of storage for the sector containing the piece and submit them to the blockchain regularly (step 3b); meanwhile, the rest of the network must verify the proofs generated by the miners and repair possible faults (step 3c).

The Storage Market protocol is explained in detail in Figure 11.

5.3 Retrieval Market

The Retrieval Market allows clients to request retrieval of a specic piece and Retrieval Miners to serve it. Unlike Storage Miners, Retrieval Miners are not required to store pieces through time or generate proofs of storage. Any user in the network can become a Retrieval Miner by serving pieces in exchange for Filecoin tokens. Retrieval Miners can obtain pieces by receiving them directly from clients, by acquiring them from the Retrieval Market, or by storing them from being a Storage Miner.

We design the Retrieval Market protocol accordingly to the following requirements:

O-chain orderbook: Clients must be able to nd Retrieval Miners that are serving the required pieces and directly exchange the pieces, after settling on the pricing. This means that the orderbook cannot be run via the blockchain - since this would be the bottleneck for fast retrieval requests - instead participant will have only partial view of the OrderBook. Hence, we require both parties to gossip their orders.

5.3.2 Data Structures

$$ \mathcal {O} _ {\mathrm {b i d}} $$

$$ \mathcal {O} _ {\mathrm {a s k}} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

Payments channels: Clients are interested in retrieving the pieces as soon as they submit their payments, Retrieval Miners are interested in only serving the pieces if they are sure of receiving a payment. Validating payments via a public ledger can be the bottleneck of a retrieval request, hence we must rely on ecient o-chain payments. The Filecoin blockchain must support payment channels

we must rely on ecient o-chain payments. The Filecoin blockchain must support payment channels which enable rapid, optimistic transactions and use the blockchain only in case of disputes. In this way, Retrieval Miners and Clients can quickly send the small payments required by our protocol. work includes the creation of a network of payment channels as previously seen in [11, 12].

we must rely on ecient o-chain payments. The Filecoin blockchain must support payment channels which enable rapid, optimistic transactions and use the blockchain only in case of disputes. In this way, Retrieval Miners and Clients can quickly send the small payments required by our protocol. Future work includes the creation of a network of payment channels as previously seen in [11, 12].

Get Orderbook. The Orderbook in the Retrieval Market is the set of valid and open ask, bid and deal orders. Unlike the Storage Market, every user has a dierent view of the orderbook, since the orders are gossiped in the network and each miner and client only keep track of the orders they are interested in.

$$ \mathcal {C} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} _ {\mathrm {a s k}} ^ {1}, \mathcal {O} _ {\mathrm {a s k}} ^ {2}, $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {O} _ {\mathrm {b i d}} ^ {1}, \mathcal {O} _ {\mathrm {b i d}} ^ {2}, $$

$$ s \left(\mathcal {O} ^ {1}, \mathcal {O} ^ {2},..\right) $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {M} _ {i} $$

$$ \left(\mathcal {O} _ {\mathrm {b i d}}, \mathcal {O} _ {\mathrm {a s k}}, p\right) $$

$$ \mathcal {M} _ {i} $$

$$ \left(\mathcal {O} _ {\mathrm {b i d}}, \mathcal {O} _ {\mathrm {a s k}}, p\right) $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

3.The Network checks if the Storage Miners are correctly storing the pieces:

$$ \pi_ {\mathrm {S E A L}} $$

$$ \Delta_ {\mathrm {p r o o f}} $$

if any proofs are missing or invalid, it penalizes the Storage Miners by taking part of their collateral, if a large amount of proofs are missing or invalid for more than epochs, it

$$ \Delta_ {\mathrm {f a u l t}} $$

4.When the time of the order is expired or funds run out, if the service was correctly provided, the Network processes the payments, and removes the orders.

Figure 11: Detailed Storage Market protocol

5.3.3 The Retrieval Market Protocol

In brief, the Retrieval Market protocol is divided in two phases: order matching and settlement :

Order Matching : Clients and Retrieval Miners submit their orders to the orderbook by gossiping their orders (step 1). When orders are matched, the client and the Retrieval Miners establish a micropayment channel (step 2).

Settlement : Retrieval Miners send a small parts of the piece to the client and for each piece the client sends to the miner a signed receipt (step 3). The Retrieval Miner presents the delivery receipts to the blockchain to get their rewards (step 4).

The protocol is explained in details in Figure 12.

Retrieval Market Protocol Order Matching: 1.Retrieval Miners and Clients add orders to the Get.OrderBook: (a)Retrieval Miners Micreates ask orders (Oask1; Oask2;::) and Client Cjcreates bid orders (Obid1; Obid2;::). (b)Both Miand Cjgossip their orders in the Filecoin network via Get.addOrders (c)Since there is no commonly shared orderbook, when users receive orders, they add them to their own orderbook’s view. Dierently from the Storage Market, these orders are not binding and no resource is committed (e.g. clients don’t do any deposit). 2.When orders match, involved parties jointly create Odealand add it to the Get.OrderBook: (a)Retrieval Miner Miand Client Cjindependently run Get.matchOrders that queries their own current Get.OrderBook view. (b)Both Miand Cjsign Odealand add it to their Get.OrderBook via Get.addOrders (as described before) (c) Ciand Mjsetup a micropayment channel for Odeal Settlement: 3.Both parties check whether the piece has been delivered: (a) Misends the piece p in parts via Get.SendPiece (b) Cjreceives the p in parts and for each part, Cjacknowledges delivery by sending a micropayment via Get.ReceivePiece 4.When the p has been received by Cj, Mjcan present the micropayments to the network and retrieve the payment, both parties remove their orders from the orderbooks.

$$ \mathcal {M} _ {i} $$

$$ \left(\mathcal {O} _ {\mathrm {a s k}} ^ {1}, \mathcal {O} _ {\mathrm {a s k}} ^ {2},..\right) $$

$$ \mathcal {C} _ {j} $$

$$ \left(\mathcal {O} _ {\mathrm {b i d}} ^ {1}, \mathcal {O} _ {\mathrm {b i d}} ^ {2},..\right) $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {C} _ {i} $$

$$ \mathcal {M} _ {j} $$

$$ \mathcal {O} _ {\mathrm {d e a l}} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {C} _ {j} $$

$$ \mathcal {C} _ {j}, \mathcal {M} _ {j} $$

Figure 12: Detailed Retrieval Market protocol

6 Useful Work Consensus

The Filecoin DSN protocol can be implemented on top of any consensus protocol that allows for verication of the Filecoin’s proofs. In this section, we present how we can bootstrap a consensus protocol based on useful work. Instead of wasteful Proof-of-Work computation, the work Filecoin miners do generating Proofof-Spacetime is what allows them to participate in the consensus.

Useful Work. We consider the work done by the miners in a consensus protocol to be useful, if the outcome of the computation is valuable to the network, beyond securing the blockchain.

6.1 Motivation

While securing the blockchain is of fundamental importance, Proof-of-Work schemes often require solving puzzles whose solutions are not reusable or require a substantial amount wasteful computation to nd.

Non-reusable Work: Most permissionless blockchains require miners to solve a hard computational puzzle, such as inverting a hash function. Often the solutions to these puzzles are useless and do not have any inherent value beyond securing the network. Can we re-purpose this work for something useful?

Attempts to re-use work: There have been several attempts to re-use mining power for useful computation. Some eorts require miners to perform a special computation alongside the standard Proofof-Work. Other eorts replace Proof-of-Work with useful problems that are still hard to solve. For example, Primecoin re-uses miners’ computational power to nd new prime numbers, Ethereum requires miners to execute small programs alongside with Proof-of-Work, and Permacoin oers archival services by requiring miners to invert a hash function while proving that some data is being archived. Although most of these attempts do perform useful work, the amount of wasteful work is still a prevalent factor in these computations.

Wasteful Work: Solving hard puzzles can be really expensive in terms of cost of machinery and energy consumed, especially if these puzzles solely rely on computational power. When the mining algorithm is embarrassingly parallel, then the prevalent factor to solve the puzzle is computational power. Can we reduce the amount of wasteful work? Attempts to reduce waste : Ideally, the majority of a network’s resources should be spent on useful work.

Power Fault Tolerance. In our technical report [13], we present Power Fault Tolerance, an abstraction that re-frames byzantine faults in terms of participants’ inuence over the outcome of the protocol. Every participant controls some power of which n is the total power in the network, and f is the fraction of power

We set out to design a consensus protocol with a useful work based on storing users’ data.

controlled by faulty or adversarial participants.

ti Power in Filecoin. In Filecoin, the power p of miner Miat time t is the sum of the Mi’s storage assignments. The inuence Iitof Miis the fraction of Mi’s power over the total power in the network.

$$ p _ {i} ^ {t} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ I _ {i} ^ {t} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} \mathrm {' s} $$

In Filecoin, power has the following properties:

Public: The total amount of storage currently in use in the network is public. By reading the blockchain, anyone can calculate the storage assignments of each miner - hence anyone can calculate the power of each miner and the total amount of power at any point in time.

Publicly Veriable : For each storage assignment, miners are required to generate Proofs-of-Spacetime, proving that the service is being provided. By reading the blockchain, anyone can verify if the power claimed by a miner is correct.

Variable: At any point in time, miners can add new storage in the network by pledging with a new sector and lling the sector. In this way, miners can change their amount of power they have through time.

6.2.2 Accounting for Power with Proof-of-Spacetime

Everyproofblocks6, miners are required to submit Proofs-of-Spacetime to the network, which are only successfully added to the blockchain if the majority of power in the network considers them valid. At every block, every full node updates the AllocTable, adding new storage assignments, removing expiring ones and marking missing proofs.

$$ \Delta_ {\mathrm {p r o o f}} $$

The power of a miner Mican be calculated and veried by summing the entries in the AllocTable, which can be done in two ways:

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} $$

Simple Storage Verication: Assume a light client has access to a trusted source that broadcasts the latest block. A light client can request from nodes in the network: (1) the current AllocTable entry for miner Mi, (2) a Merkle path that proves that the entry was included in the state tree of the last block, (3) the headers from the genesis block until the current block. In this way, the light client can delegate the verication of the Proof-of-Spacetime to the network.

Expected Consensus. The basic intuition of Expected Consensus EC is to deterministically, unpredictably, and secretly elect a small set of leaders at each epoch. On expectation, the number of elected leaders per

$$ \mathcal {M} _ {i} $$

6.2.3 Using Power to Achieve Consensus

$$ ^ {6} \Delta_ {\mathrm {p r o o f}} $$ epoch is 1, but some epochs may have zero or many leaders. Leaders extend the chain by creating a block and propagating it to the network. At each epoch, the chain is extended with one or multiple blocks. In case of a leaderless epoch, an empty block is added to the chain. Although the blocks in chain can be linearly ordered, its data structure is a direct acyclic graph. EC is a probabilistic consensus, where each epoch introduces more certainty over previous blocks, eventually reaching enough certainty that the likelihood of a dierent history is suciently small. A block is committed if the majority of the participants add their weight on the chain where the block belongs to, by extending the chain or by signing blocks.

Electing Miners. At every epoch, each miner checks if they are elected leader, this is done similarly to previous protocols: CoA [15], Snow White [16], and Algorand [17].

Denition 6.1. (EC Election in Filecoin) A miner Miis a leader at time t if the following condition is met:

$$ \mathcal {M} _ {i} $$

$$ \mathcal {H} \left(\left\langle t \right| \left| \operatorname {r a n d} (t) \right\rangle_ {\mathcal {M} _ {i}}\right) / 2 ^ {L} \leq \frac {p _ {i} ^ {t}}{\Sigma_ {j} p _ {j} ^ {t}} $$

ti Where rand(t) is a public randomness available that can be extracted from the blockchain at epoch t, p is the power of Mi. Consider the size of H(m) to be L for any m, H to be a secure cryptographic hash function and hmiMito be a message m signed by Mi, such that:

$$ t, p _ {i} ^ {t} $$

$$ L $$

$$ \mathcal {M} _ {i} $$

$$ \mathcal {M} _ {i} $$

$$ \langle m \rangle_ {\mathcal {M} _ {i}} $$

$$ \langle m \rangle_ {\mathcal {M} _ {i}} := \left((m), \mathrm {S I G} _ {\mathcal {M} _ {i}} \left(\mathcal {H} (m)\right)\right) $$

This election scheme provides three properties: fairness, secrecy and public veriability.

Fairness : each participant has only one trial for each election, since signatures are deterministic and t L and rand(t) are xed. Assuming H is a secure cryptographic hash function, then H(htjjrand(t)iMi)=2 must be a real number uniformly chosen from (0, 1). Hence, the probability for the equation to be ti tj true must be p =jp, which is equal to the miner’s portion of power within the network. Because this probability is linear in power, this likelihood is preserved under splitting or pooling power. Note that the random value rand(t) is not known before time t. Secret : an ecient adversary that does not own the secret key M can compute the signature with

$$ \mathcal {H} \left(\langle t | | \operatorname {r a n d} (t) \rangle_ {\mathcal {M} _ {i}}\right) / 2 ^ {L} $$

$$ p _ {i} ^ {t} / \Sigma_ {j} p _ {j} ^ {t} $$

Secret : an ecient adversary that does not own the secret key Mican compute the signature with negligible probability, given the assumptions of digital signatures.

t Public Veriability : an elected leader i 2 L can convince a ecient verier by showing t, rand(t), L H(htjjrand(t)ii)=2; given the previous point, no ecient adversary can generate a proof without having a winning secret key.

$$ i \in L ^ {t} $$

$$ : (r, t, \mathcal {M} _ {i}) \rightarrow {\perp , \pi_ {i} ^ {t} } $$

$$ \mathcal {H} \left(\langle t | | r \rangle_ {i}\right) / 2 ^ {L} \leq \frac {p _ {i} ^ {t}}{\Sigma_ {j} p _ {j} ^ {t}} $$

Figure 13: Leader Election in the Expected Consensus protocol

$$ \mathcal {M} _ {i} $$

7 Smart Contracts

Filecoin provides two basic primitives to the end users: Get and Put. These primitives allow clients to store data and retrieve data from the markets at their preferred price. While the primitives cover the default use cases for Filecoin, we enable for more complex operations to be designed on top of Get and Put by supporting a deployment of smart contracts. Users can program new ne-grained storage/retrieval requests that we classify as File Contracts as well as generic Smart Contracts. We integrate a Contracts system (based on [18]) and a Bridge system to bring Filecoin storage in other blockchain, and viceversa, to bring other blockchains’ functionalities in Filecoin.

We expect a plethora of smart contracts to exist in the Filecoin ecosystem and we look forward to a community of smart-contract developers.

7.1 Contracts in Filecoin

Smart Contracts enable users of Filecoin to write stateful programs that can spend tokens, request storage/retrieval of data in the markets and validate storage proofs. Users can interact with the smart contracts by sending transactions to the ledger that trigger function calls in the contract. We extend the Smart Contract system to support Filecoin specic operations (e.g. market operations, proof verication).

Filecoin supports contracts specic to data storage, as well as more generic smart contracts:

File Contracts: We allow users to program the conditions for which they are oering or providing storage services. There are several examples worth mentioning: (1) contracting miners: clients can specify in advance the miners oering the service without participating in the market, (2) payment strategies: clients can design dierent reward strategies for the miners, for example a contract can pay the miner incresignly higher through time, another contract can set the price of storage informed by a trusted oracle, (3) ticketing services: a contract could allow a miner to deposit tokens and to pay for storage/retrieval on behalf of their users, (4) more complex operations: clients can create contracts that allow for data update.

Smart Contracts: Users can associate programs to their transactions like in other systems (as in Ethereum [18]) which do not directly depend on the use of storage. We foresee applications such as: decentralized naming systems, asset tracking and crowdsale platforms.

7.2 Integration with other systems

Bridges are tools that aim at connecting dierent blockchains; while still work in progress, we plan to support cross chain interaction in order to bring the Filecoin storage in other blockchain-based platforms as well as bringing functionalities from other platforms into Filecoin.

Other platforms in Filecoin: We plan to provide bridges to connect other blockchain services with Filecoin. For example, integration with Zcash would allow support for sending requests for storing data in privacy.

8 Future Work

This work presents a clear and cohesive path toward the construction of the Filecoin network; however, we also consider this work to be a starting point for future research on decentralized storage systems. In this section we identify and populate three categories of future work. This includes work that has been completed and merely awaits description and publication, open questions for improving the current protocols, and formalization of the protocol.

8.1 On-going Work

The following topics represent ongoing work.

A specication of the Filecoin state tree in every block.

Detailed performance estimates and benchmarks for Filecoin and its components.

A full implementable Filecoin protocol specication.

A sponsored-retrieval ticketing model where any client C1 can sponsor the download of another client C2 by issuing per-piece bearer-spendable tokens.

A Hierarchical Consensus protocol where Filecoin subnets can partition and continue processing transactions during temporary or permanent partitions.

Incremental blockchain snapshotting using SNARK/STARK

Filecoin-in-Ethereum interface contracts and protocols.

Blockchain archives and inter-blockchain stamping with Braid.

Only post Proofs-of-Spacetime on the blockchain for conict resolution.

Formally prove the realizations of the Filecoin DSN and the novel Proofs-of-Storage.

8.2 Open Questions

There are a number of open questions whose answers have the potential to substantially improve the network as a whole, despite the fact that none of them have to be solved before launch.

New strategies for retrieval in the Retrieval Market (e.g. based on probabilistic payments, zero knowledge contingent payments)

A better secret leader election for the Expected Consensus, which gives exactly one elected leader per epoch.

A transparent, publicly-veriable Proof-of-Retrievability or other Proof-of-Storage.

A better trusted setup scheme for SNARKs that allows incremental expansion of public parameters (schemes where a sequence of MPCs can be run, where each additional MPC strictly lowers probability of faults and where the output of each MPC is usable for a system).

8.3 Proofs and Formal Verication

Because of the clear value of proofs and formal verication, we plan to prove many properties of the Filecoin network and develop formally veried protocol specications in the coming months and years. A few proofs are in progress and more in mind. But it will be hard, long-term work to prove many properties of Filecoin (such as scaling, oine).

Proofs of correctness for Expected Consensus and variants.

Proof of correctness for Power Fault Tolerance asynchronous 1/2 impossibility result side-step.

Formulate the Filecoin DSN in the universal composability framework, describing Get, Put and Manage as ideal functionalities and prove our realizations.

Formal model and proofs for automatic self-healing guarantees.

Formally verify protocol descriptions (e.g. TLA+ or Verdi).

Formally verify implementations (e.g. Verdi).

Game theoretical analysis of Filecoin’s incentives.

Acknowledgements

This work is the cumulative eort of multiple individuals within the Protocol Labs team, and would not have been possible without the help, comments, and review of the collaborators and advisors of Protocol Labs. Juan Benet wrote the original Filecoin whitepaper in 2014, laying the groundwork for this work. He and Nicola Greco developed the new protocol and wrote this whitepaper in collaboration with the rest of the team, who provided useful contributions, comments, review and conversations. In particular David \davidad" Dalrymple suggested the orderbook paradigm and other ideas, Matt Zumwalt improved the structure of the paper, Evan Miyazono created the illustrations and nalized the paper, Jeromy Johnson provided insights while designing the protocol, and Steven Allen contributed insightful questions and clarications. We also thank all of our collaborators and advisor for useful conversations; in particular Andrew Miller and Eli Ben-Sasson.

Previous version: QmYcf7X6ygKisoVS7EApqY3gxcKW1MigF57zc1cdXjZWrQ

References

[1]Juan Benet. IPFS - Content Addressed, Versioned, P2P File System. 2014.

[2]Giuseppe Ateniese, Randal Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary Peterson, and Dawn Song. Provable data possession at untrusted stores. In Proceedings of the 14th ACM conference on Computer and communications security, pages 598{609. Acm, 2007.

[3]Ari Juels and Burton S Kaliski Jr. Pors: Proofs of retrievability for large les. In Proceedings of the 14th ACM conference on Computer and communications security, pages 584{597. Acm, 2007.

[4]Hovav Shacham and Brent Waters. Compact proofs of retrievability. In International Conference on the Theory and Application of Cryptology and Information Security, pages 90{107. Springer, 2008.

[5]Protocol Labs. Technical Report: Proof-of-Replication. 2017.

[6]Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct nizks without pcps. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 626{645. Springer, 2013.

[7]Nir Bitansky, Alessandro Chiesa, and Yuval Ishai. Succinct non-interactive arguments via linear interactive proofs. Springer, 2013.

[8]Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. Snarks for c: Verifying program executions succinctly and in zero knowledge. In Advances in Cryptology{CRYPTO 2013, pages 90{108. Springer, 2013.

[9]Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, et al. Computational integrity with a public random string from quasi-linear pcps. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 551{579. Springer, 2017.

[11]Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable o-chain instant payments. 2015.

[12]Andrew Miller, Iddo Bentov, Ranjit Kumaresan, and Patrick McCorry. Sprites: Payment channels that go faster than lightning. arXiv preprint arXiv:1702.05812, 2017.

[16]Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Provably secure proofs of stake. 2016.

[13]Protocol Labs. Technical Report: Power Fault Tolerance. 2017.

[17]Silvio Micali. Algorand: The ecient and democratic ledger. arXiv preprint arXiv:1607.01341, 2016.

[15]Iddo Bentov, Charles Lee, Alex Mizrahi, and Meni Rosenfeld. Proof of activity: Extending bitcoin’s proof of work via proof of stake [extended abstract] y. ACM SIGMETRICS Performance Evaluation Review, 42(3):34{37, 2014.

[19]Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.

[20]Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In Security and Privacy (SP), 2014 IEEE Symposium on, pages 459{474. IEEE, 2014.