所需积分/C币:37 2018-08-17 09:54:52 614KB PDF
收藏 收藏

List of Figures 1 Sketch of the Filecoin Protocol. Illustration of the filecoin protocol 3 Illustration of thc underlying mcchanism 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 Description of the manage protocol in the Filecoin dsn Generic protocol for Verifiable Markets 24 10 Orders data structures for the Retrieval and Storage markets 26 11 Detailed Storage Market protocol 28 12 Detailed Retrieval Market protocol 13 Leader Election in the Expected Consensus protocol Introduction Filecoin is a protocol token whose blockchain runs on a novel proof, called Proof-0f-Spacetime, where blocks are created by miners that are storing data. Filecoin protocol provides a data storage and retrieval service via a nctwork of independent storagc providers that docs not rely on a singlc coordinator, whcrc: (1) clients pay to store and retrieve data, (2)Storage Miners earn tokens by offering 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 offer storage and retrieval scrviccs(in Scction 2). Latcr, wc prcscnt thc Filccoin protocol as an incentivized, auditable and verifiable DSN construction (in Section 国 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 verifier to check that a prover is not deduplicating multiplc copics of thc data into the samc storage spacc;(2)Proof-of Spacetime allows storage providers to prove they have stored soime data throughout i specified allout of tiine 3. Verifiable Markets: We model storage requests and retrieval requests as orders in two decentralized verifiable markets operated by the Filecoin network(in Section 5. Verifiable markets ensure that payments are performed when a service has been correctly provided. We present the Storage Market and the Retrieval markct wherc miners and clients can respectively submit storagc 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 The Filecoin DSN handle storage and retrieval requests respectively via two verifiable markets: the Storagc Markct and the Retrieval Markct. Clients and miners sct thc prices for the scrviccs rcqucstcd and offered and submit their orders to the markets The markets are operated by the Filecoin network which employs Proof-of-Spacetime and Proof-of- Replication to guarantee that miners have correctly stored the data they committed to store Finally, miners can participate in the creations of new blocks for the underlining blockchain. The infuence of a miner over the next block is proportional to the amount of their storage currently in use in the network tho Filocoin protocol, using nomenclature dofinod latcr within the papor, is shown in FigurcI accompanied with an illustration in Figure2 1.3 Paper organization The remainder of this paper is organized as follows. We present our definition of and requirements for a theoretical DSNscheme in Section 2. In Section 3 we motivate, define, and present our Proof-of-Replication and Proof-of-Spacetime protocols, used within Filecoin to cryptographically verify that data is continuously 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 defines and de scribes the concept of Verifiable 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 Scction 8 Filecoin protocol sketch Network Storage Mine at each epoch t in the ledger L: at any time 1. for each new block 1. renew expired pledges via Manage Pledge Sector (a) check if the block is in the valid format 2. pledge new storage via Manage. Pledge Sector (b) check if all transactions are valid 3. submit a new ask order via Put Add Order (c) check if all orders are va id d) check if all proofs are valid at each epoch t (e) check if all pledges are valid 1. for each Oosk in the orderbook (f) discard block, if any of the above fails (a) find matched orders via Put Match Orders 2. for each new order O introduced in t D) start a new deal by contacting the matching (a)addo to the Storage Market's orderbook client (b) if O is a bid: lock O funds 2. for cach sector pledged (c) if O is an ask:: lock Ospace (a) generate storage (d) if O is a deal: run Put. AssignOrders Manage. ProveSector 3. for each O in the Storage Market's orderbook (b) if time to post the proof (every Proof (a) check if O has expired(or canceled) epochs, submit it to the blockchain e remove from the orderbook returN unspent O funds on receiving piece p from client C free Ospace from AllocAble 1. check if the piece is of the size specified in the (b) if O is a deal, check if the expected proofs order Bid exist by running Manage. RepairOrders 2. create Deal and sign it and send it to c e if one missing, penalize the M's pledge 3. store the piece in a sector collateral 4. if the sector is full, run Manage. SealSecto if proofs are missing for more than Atault Retrieval mine e I order and re-introduce it to the market at any timc if the piece cannot be retrieved and re- 1. gossip ask orders to the network constructed from the network, cancel or- 2. listen to bid orders from the network der and rc-fund tho on retrieval request from C Client 1. start ent channel with C at any time 2. split data in multiple parts 1. submit new storage orders via Put. AddOrders only send parts if payments are received (a)find matching orders via Put Match Orders (b) send file to the matched miner M 2. submit new retrieval orders via Get. AddOrders (a) find matching orders via Get. Match Orders (b) create a payment channel with M on receiving Deal from Storage Miners M 1. sign Deal 2. submit the signed Deal to the blockchain via Put. AddOrders on receiving(pi) from Retrieval Miners M 1. verify that (p: is valid and it was requested 2. send a micropayment to M Figure 1: Sketch of the Filecoin Protocol Order matching Settlement Biao 回 age Ⅵ arket (On Chain Odea)M challenge 1O-deal)Md Sponse Orderbook Filecoin Transaction Blockchain allocation aDie micropayments o Bid Retrieval Market (Off Chain) NOdeal)M E20 Orders gossiped Data sent Claim off-chai In parts micropayment Lock storage (M Signed by M Transfcr filccoin Mine Client Piece of data Query Order 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 Definition of a Decentralized Storage Network We introduce the notion of a Decentralized Storage Network(DSN) scheme. DSNs aggregate storage offered Dy multiple independent storage providers and self-coordinate to provide data storage and data retrieval to lients. Coordination is dcccntralizcd and docs not rcquirc trusted parties: the sccurc opcration of theses systems is achieved through protocols that coordinate and verify operations carried out by individual parties DSNs can employ different 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 Definition 2.1. A DSN scheme II 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 identifier 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 audit the service offered by providers and repair possible faults. The Manage protocol is run by storage providers often in conjunction with clients or a. net work of aeditor A DSN scheme TI must guarantee data integrity and retrievability as well as tolerate management and storage faults defined in the following sections 2.1 Fault tolerance 2.1.1 Management faults We define management faults to be byzantine faults caused by participants in the Manage protocol. A DSN scheme relies on the fauIlt 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 II, 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 coInprolllised 2.1.2 Storage faults le define storage faults to be by zantine faults that prevent clients from retrieving the data: i.e. Storage Miners lose their pieces. Retrieval Miners stop serving pieces. A successful Put execution is(f, m)-tolerant if it results in its input data being stored in m independent storage providers (out of n total) and it can tolerate up to f byzantine providers. The parameters f and m depend on protocol implementation; protocol designers can fix f and m or leave the choice to the user, extending Put( data) into Put(data, f, m). A Get execution on stored data is successful if there are fewer than f faulty storage providers sx For example, consider a simple scheme, where the Put protocol is designed such that, each storage provider stores all of the data. In this scheme m= n and f=m-1. Is it always f=m-1? No, some schemes can be designed using erasure coding, where each storage providers store a special portion of the data, such that out of m storage providers are required to retrieve the data; in this case f= m-I 2.2 Properties We describe the two required properties for a dSN scheme and then present additional properties required by the filecoin dsN In the case where the Manage protocol relies on a blockchain, we consider the miners as auditors, since they verify and coordinate storage providers 2.2.1 Data Integrity This property requires that no bounded adversary A can convince clients to accept altered or falsified data at the end of a get execution Definition 2.2. A DSN scheme Ii provides data integrity if: for any successful Put execution for some data d under key k, there is no computationally-bounded adversary that can convince a client to accept d. for d't d at the end of a get execution for identifier k 2.2.2 Retrievability This propcrty captures the requirement that, givcn our fault-tolcrancc assumptions of Il, if somc data has been successfully stored in Ii and storage providers continue to follow the protocol, then clients can eventually retrieve the data key,there exists a successful Get execution for key for which a client retrieves daye execution for data under Definition 2.3. A dSN scheme li provides retrievability if: for any successful pu 2.2.3 Other Properties DSNs can provide other properties specific to their application. We define three key properties required by the Filecoin DSN: public verifiability, auditability, and incentive-compatibility Definition 2.4. A dSN scheine II is publicly verifiable 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 efficient verifier, which only knows key and does not have access to data Definition 2.5. A DSN scheme Il is auditable, if it generates a verifiable trace of operation that can be checked in the future to confirm storage was indccd stored for the right duration of timc Definition 2.6. A DSN scheme II is incentive-compatible, if: storage providers are rewarded for successfully offering storage and retrieval service, or penalized for misbehaving, such that the storage providers'dominant strategy is to store data 2This definition does not guarantee every Get to succeed: if every Get eventually returns data, then the scheme is fair 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 thcmsclvcs)verifies In this section we motivate, present and outline implementations for the Proof-of-Replication(PoRep) and Proof-of Spacetime(Post) schemes used in Filecoin 3.1 Motivation Proofs-of-Storage(PoS) schemes such as Provable Data Possession(PDP)2 and Proof-of-Retrievability (PoR)B 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 froln 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 sorver (i.c. thc 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 dcfinition, a dcscription of its propcrtics, and an in-dcpth 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 ce a verifie 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 (Setup, Prove, Verify PoRep Setup(1, D)R, Sp, Sv, where Sp and Sy are scheme-specific setup variables for P and v, X is a security parameter. PoRep. Setup is used to generate a replica R, and give p and y 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

试读 36P filecoin白皮书原版
立即下载 低至0.43元/次 身份认证VIP会员低至7折
  • GitHub

  • 签到达人

  • 分享达人

关注 私信 TA的资源
    filecoin白皮书原版 37积分/C币 立即下载

    试读结束, 可继续读3页

    37积分/C币 立即下载 >