所需积分/C币:49 2018-05-09 15:31:48 614KB PDF
收藏 收藏

List of Figurcs 1 Sketch of the Filecoin Protocol. 2 Illustration of the Filecoin protocol 3 Illustration of the underlying mcchanism of PoSt Prove 14 4 Proof-of-Replication and Proof -of-Spacetime protocol sketches 15 5 Data Structures in a dsn schemel 17 6 Example execution of the Filecoin DSN Description of the Manage Protocol in the Filecoin DS OSNI 7 Description of the Put and get Protocols 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 1 2 Detailed ret I Market protocol 13 Leader Election in the Expected Consensus protoco 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 nctwork of indcpcndent storage providers that docs not rely on a single coordinator, whore: (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 servicos(in Scction 2p. Latcr, we prcsont tho 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 multiple copics of the data into the samc storage spacc;(2)Proof-of-Spacetime allows storage providers to prove they have stored some dala throughout a specilied amount of line 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 where miners and clients can respectively submit storagc and retrieval ordcrs 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 Rctricval Markct. Clients and miners sct the 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 influence of a miner over the next block is proportional to the amount of their storage currently in use in the network A skotch of the Filccoin protocol, using nomenclature defined latcr within the papor, is shown in FiguroI accompanied with all illustraTion in Figure 2 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 bet ween 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 Filecoinl Protocol sketch Network Storage Mine at each epoch t in the ledger L ally Lillie 1. for each new block I. 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. AddOrder c) check if all orders are valid (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. MatchOrders 2. for t each n ew order o introduced in t (b) start a new deal by contacting the matching (a)add o to the Storage Markets orderbook client (b)if O is a bid: lock O funds 2. for each sector pledged c if O is an ask: lock C)space (a) generate proof of storage Ⅵ1a (d) if O is a deal: run Put Assign Orders Manage. ProveSector 3. for each O in the Storage markel's orderbook (b) if time to post the proof (every Apre (a) check if O has expired ( or canceled) epochs), submit it to the blockchain remov ve O from the orderbook return unspent O funds on receiving piece p from client C free O space from Alloc Table 1. check if the piece is of the size specified in the (b)if O is a deal, check if the expected proofs exist by running Manage. RepairOrders 2. create Oceal and sign it and send it to C if one missing, penalize the M's pledge 3. store the piece in a sector collateral 4. if the sector is full, run Manage. SealSector if proofs are missing for more than Afault Retrieval mine epochs, cancel order and re-introduce it at any time if the 1. gossip ask orders to the network constructed from the network, cancel or- 2. listen to bid orders from the network der and re-fund the client on retrieval request from C: Client 1. start payment channel with C at any time 2. split data in multiple parts 1. subunit llew storage orders via Put. AddOrders 3. only send parts if payments are received (a)find matching orders via Put Match Orders (b) send file to the matched miner subnit 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 2. submit it to the blockchain via Put Addorders on receiving (pi )from Retrieval Miners M 1. verify th 2. send a micropayment to M Sketch of the filecoin protocol Order matching Settlement Ubid 回 orage ain Deals hallo tOdeal)Md rosson Orderbook Filecoin Transactions Blockchain Allocation e Incremental o micropayments Bid deal Retrieval Market (Off Chain) E20 Orders gossiped Data sent aIIn off-chain In parts micropayment Lock storage (M Signed by M Transfcr filccoin Client Piece of data 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 Dcfinition of a Decentralized Storage Network We introduce the notion of a Decentralized Storage Network(DSN)scheme. DSNs aggregate storage offered by multiple independent storage providers and self-coordinate to provide data storage and data retrieval to clients. Coordination is decentralized 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 ll 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 storage, 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 network of auditor 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 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 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 coMpromised 2.1.2 Storage faults We define storage faults to be byzantine 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 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-l. 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 c out of m storage providers are required to retrieve the data; in this case f= m-3 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 coordinate storage providers 2.2.1 Data Integrity This property requires that no bounded adversary 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 a 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, given 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 Definition 2. 3. A DSN scheme ii provides retrievability if for any successful Put execution for data under ker, there exists a successful Get execution for key for which a client retrieves data 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 slorage 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 II 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 Il is incentive-compatible, if: storage providers are rewarded for successfull 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 n 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 e 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 tha an 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 dala Iroi 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 miners storage currently in use 3.2 Proof-of-Replication Proof-of- Replication(PoRep) is a novel Proof-of-Storage which allows a server(i.c. the prover p) to convince a user(i.e. the verifier v) that some data D has been replicated to its own uniquely dedicated physical storage. Our scheme is an interactive protocol, where the prover P:(a) commits to store n distinct replicas (physically independent copies) of some data D, and then(b) convinces the verifier v, that p is indeed storing each of the replicas via a challenge/response protocol. To the best of our knowledge, PoRep improves on PoR and PDP schemes, preventing Sybil Attacks, Outsourcing Attacks, and Generation Attacks Notc. For a formal dcfinition, a description of its propcrtics, and an in-dcpth study of Proof-of-Replication, we refer the reader to Definition 3.1.(Proof-of-Replication)A PoRep scheme enables an efficient prover p to convince a verifier v that p is storing a replica R, a physical independent copy of some data D, unique to P. A PoRep protocol is characterized by a tuple of polynomial-time algorithms (Setup, Pre ove. ve ify PoRep Setup(1 D)R, Sp, Sv, where Sp and Sy are scheme-specific setup variables for p and v, A 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 10

试读 36P Filecoin白皮书
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    Filecoin白皮书 49积分/C币 立即下载

    试读结束, 可继续读3页

    49积分/C币 立即下载 >