FileInsurer: A Scalable and Reliable Protocol for Decentralized File Storage in Blockchain

With the development of blockchain applications, the requirements for file storage in blockchain are increasing rapidly. Many protocols, including Filecoin, Arweave, and Sia, have been proposed to provide scalable decentralized file storage for blockchain applications. However, the reliability is not well promised by existing protocols. Inspired by the idea of insurance, we innovatively propose a decentralized file storage protocol in blockchain, named as FileInsurer, to achieve both scalability and reliability. While ensuring scalability by distributed storage, FileInsurer guarantees reliability by enhancing robustness and fully compensating for the file loss. Specifically, under mild conditions, we prove that no more than 0.1\% value of all files should be compensated even if half of the storage collapses. Therefore, only a relatively small deposit needs to be pledged by storage providers to cover the potential file loss. Because of lower burdens of deposit, storage providers have more incentives to participate in the storage network. FileInsurer can run in the top layer of the InterPlanetary File System (IPFS), and thus it can be directly applied in Web 3.0, Non-Fungible Tokens, and Metaverse.

Abstract-With the development of blockchain applications, the requirements for file storage in blockchain are increasing rapidly. Many protocols, including Filecoin, Arweave, and Sia, have been proposed to provide scalable decentralized file storage for blockchain applications. However, the reliability is not well promised by existing protocols. Inspired by the idea of insurance, we innovatively propose a decentralized file storage protocol in blockchain, named as FileInsurer, to achieve both scalability and reliability. While ensuring scalability by distributed storage, FileInsurer guarantees reliability by enhancing robustness and fully compensating for the file loss. Specifically, under mild conditions, we prove that no more than 0.1% value of all files should be compensated even if half of the storage collapses. Therefore, only a relatively small deposit needs to be pledged by storage providers to cover the potential file loss. Because of lower burdens of deposit, storage providers have more incentives to participate in the storage network. FileInsurer can run in the top layer of the InterPlanetary File System (IPFS), and thus it can be directly applied in Web 3.0, Non-Fungible Tokens, and Metaverse.
Index Terms-Decentralized File Storage, Blockchain application, Mechanism Design, Decentralized System, Insurance

I. INTRODUCTION
File storage is a fundamental issue in distributed systems. Recently, the developments of Web 3.0 [1], Non-Fungible Tokens (NFTs) [9,22], and Metaverse [20] have raised high requirements on reliability and accessibility of file storage. For example, the metadata of NFTs should be verifiable and accessible in NFT markets, as the values of NFTs disappear if the metadata is lost. Billions of metadata generated by blockchain applications are searching for reliable storage services.
Traditionally, people store files in personal storage or cloud storage service. However, personal storage struggles to keep files secure and accessible. Additionally, cloud storage lacks transparency and trust [5]. It is hard for users to recognize how many backups of their files should be stored to guarantee security. Moreover, file loss often occurs in cloud storage.
Due to the defects of personal storage and cloud storage, more and more users choose to store files in the blockchainbased Decentralized Storage Networks (DSNs) such as Sia [21], Filecoin [4], Arweave [24], and Storj [23]. In a DSN, This work has been performed with support from the National Natural Science Foundation of China (No. 11871366), Qing Lan Project of Jiangsu Province, China, and the Algorand Foundation Grants Program * These authors contributed to the work equllly and should be regarded as co-first authors. § Yukun Cheng is the corresponding author.
storage providers contribute their available hard disks to store files from clients and then earn profits. The storing, discarding, and storing state-changing events of files are recorded in the blockchain. Files can be stored by multiple storage providers to enhance security. Additionally, in Filecoin, backups are changed to be replicas, once they have been proved by proofof-replication (PoRep). PoRep well resists Sybil attacks [13] by a storage provider, who may pretend to store multiple backups by forging multiple identities, while she actually only stores one backup. PoRep can also be used to ensure providers cannot cheat on the available storage space. However, the existing DSN protocols do not well promise the reliability. In DSN, there are always files only stored by a small part of storage providers due to the issue of scalability. Therefore, it is impossible to completely avoid loss of files. When files are lost, the owners of these files only receive little compensation.
In this paper, we aim to enhance the reliability of decentralized file storage from the perspective of economic incentive approaches. For the Bitcoin Blockchain [17], the most success is to apply the economic incentive approach, by awarding a certain amount of token to encourage miners to actively mine. Thus, in the era of blockchain, the issue of economic approaches is getting more and more important. We build a decentralized insurance scheme on files stored in DSN to protect the interests of users when their files are lost. Under the insurance scheme, storage providers need to pledge a deposit before storing files. If a file is lost, which means that all providers storing this file are corrupted, the total deposit from these providers can fully compensate for the loss of this file.
We hope that the deposit should be small to incentivize participants to contribute their storage space. Let us denote deposit ratio to be the ratio of the sum of deposits to the total value of files. Chen et. al. [11] firstly studied how to decrease the deposit ratio in the decentralized custody scheme with insurance. However, the methodology in [11] cannot be directly applied in our scenario. The reason is that storage providers and files change over time in DSN, while [11] is only suitable for static setting. Our approach is to achieve provable robustness by ensuring storage randomness. Storage randomness requires the locations of replicas are randomly selected by DSN, such that these locations are uniformly distributed. Consequently, the attackers must corrupt a consid-erable portion of providers even if they only want to destroy all backups of a small portion of files. Therefore, the randomness can promises that only a relatively small deposit needs to be pledged by storage providers to cover the potential file loss.

Main Contributions
We propose FileInsurer, a novel design for blockchain-based Decentralized Storage Network, to achieve both scalability and reliability of file storage. In our protocol, storage providers are required to pledge deposits to registered sectors and the locations of files are randomly selected. To further ensure storage randomness, locations of files' replicas shall change from time to time because the list of sectors is dynamic.
Our protocol advances the technology of decentralized file storage in the following three aspects.
• Firstly, FileInsurer supports dynamic content stored in sectors with low cost, which is necessary to ensure storage randomness. FileInsurer deploys Dynamic Replication (DRep) to support adding and refreshing stored files. DRep is also able to resist Sybil attacks and make sure the free space of sectors is indeed available. • Secondly, FileInsurer can achieve provable robustness.
In FileInsurer, files are stored as replicas in sectors. Naturally, a file is missing, if and only if all replicas of this file have been destroyed. A sector is collapsed, as long as any bit in this sector is lost. Under mild conditions, we prove that no more than 0.1% value of all files are lost even if half of the storage collapses. • Thirdly, FileInsurer implements an insurance scheme on DSN that can provide full compensation for the loss of those missing files. The compensation is covered by the deposit of all crashed storage sectors. Our theoretical analysis indicates that only a small deposit ratio is needed to cover all of the file loss in FileInsurer. To the best of our knowledge, FileInsurer is the first DSN protocol that can provide full compensation for the file loss and has provable robustness.

Paper Organization
The rest of this paper is organized as follows. Section II introduces the related works of decentralized storage protocols. In Section III, we describe the structure and components of FileInsurer protocol. Then, we continue to introduce the protocol design of FileInsurer in Section IV. In Section V, we propose the theoretical analysis on the scalability, robustness, and deposit issue of our protocol. We also compare FileInsurer with other blockchain-based decentralized storage protocols. In addition, some practical problems in FileInsurer are detailedly discussed in Section VI. Finally, we summarize our protocol and raise some open problems in Section VII.

II. RELATED WORKS A. InterPlanetary File System (IPFS)
The InterPlanetary File System (IPFS) is a peer-to-peer distributed file system that seeks to connect all computing devices with the same system of files [2]. Files, identified by their cryptographic hashes, are stored and exchanged by nodes in IPFS. Nodes also provide the service of retrieving files to earn profits through BitSwap protocol. The routing of IPFS is achieved by Distributed Hash Tables (DHTs), which is an efficient way to locate data among IPFS nodes. Based on BitSwap and DHTs, IPFS builds an Object Merkle DAG which allows participants to address files through IPFS paths.

B. FileCoin
Filecoin builds a blockchain-based Decentralized Storage Network which runs in the top layer of IPFS [4]. There are three types of participants in Filecoin, which are clients, storage miners, and retrieval miners. Specifically, clients pay to store and retrieve files, storage miners earn profits by registering sectors to offer storage, and retrieval miners earn profits by serving data to clients.
1) Proof-of-Replication (PoRep): PoRep [3] is a kind of proof-of-storage scheme deployed in Filecoin. In the PoRep scheme, the prover firstly generates a replica of file D, denoted by R D ek , through the process of PoRep.setup(D,ek). ek is a randomly chosen encryption key that with ek, R D ek can be encrypted from D, and D can be decrypted from R D ek . The prover then submits the hash root of R D ek to the DSN. Finally, the prover proves that R D ek is a replica of D with encryption key ek via SNARK.
The verification of SNARK is very efficient. However, the calculation of R D ek would take a lot of time because it can't be parallelized. Additionally, the calculation of SNARK would consume lots of computation resources.
2) Filecoin Sectors: In Filecoin, sectors are divided into sealed ones and unsealed ones 1 . Only sealed sectors are part of the Filecoin network and can get rewards of storage. Unsealed sectors only contain raw data, and a sealed sector can be registered from an unsealed sector by PoRep. Storage miners would pledge deposits when registering a sector, but when the sector crashes, that deposit is burnt other than used for compensating the file loss to clients.
When registering an unsealed sector, if the sector is not full, the rest space of the sector would be filled with zeros before encoding by PoRep. If a sealed sector doesn't contain any files, which means the contents of that sector are all zeros when registering, it's called a committed capacity (CC). Other sealed sectors are called regular sectors. A CC sector can be upgraded to a regular sector by discarding the CC sector and registering a new regular sector. However, the content of a regular sector can be no longer changed.
3) Proof-of-Spacetime: PoSt is another kind of proof-ofstorage scheme for storage miners to prove that they are indeed actually storing a replica. There are two kinds of PoSt in Filecoin. WinningPoSt serves as a part of the Expected Consensus of Filecoin, while WindowPoSt guarantees that the miner continuously maintains a replica over time. Therefore, Sybil attacks are prevented by the combination of WindowPoSt and PoRep because storage miners should actually store all replicas. 4) Storage Market and Retrieval Market: There are two markets in Filecoin, the Storage Market and the Retrieval Market. In the Storage Market, storage miners and clients negotiate on the price and length of storage. Similarly, retrieval miners and clients would negotiate on the price of file retrieving.
C. Other Solutions to Decentralized File Storage 1) Storj: Storj [23] is a sharding [16,26] based protocol to archive a peer-to-peer cloud storage network implementing end-to-end encryption. It stores files in encrypted shards to ensure that the file itself cannot be recovered by anyone other than the owner. Moreover, it uses erasure code to ensure file availability in case some shards are lost.
2) Sia: Sia [21] is a platform for decentralized storage enabling the formation of storage contracts between peers. The Sia protocol provides an algorithm of storage proof in order to build storage contracts. According to the file contract, storage providers need to generate proof-of-storage periodically. The client needs to pay for each valid storage proof.
3) Arweave: Arweave [24] is a mechanism design-based approach to achieving a sustainable and permanent ledger of knowledge and history. Storing files on Arweave only requires a single upfront fee, after which the files become part of the consensus. Arweave uses the mechanism of Proof of Access in consensus to ensure that miners need to store as many files as possible to participate in mining.

III. PRELIMINARIES
FileInsurer is a protocol to build a blockchain-based Decentralized Storage Network (DSN) [5]. The structure of DSN could be an independent blockchain or a decentralized application (DApp) parasitic on existing blockchains or other distributed network types. In DSN, a group of participants, called storage providers, are willing to rent out their unused hardware storage space to store the clients' files, and then the distributed file storage is realized.
In this section, we introduce the structure and components of FileInsurer protocol. Particularly, we deploy Dynamic Replication (DRep) to support dynamic content in sectors with low cost, which is important to ensure storage randomness. Additionally, we also explain why compensation is necessary for DSN.

A. Participants
There are two kinds of participants in DSN that are clients and storage providers. 1) Client: Clients are the participants who have the demand to store files in the network. They propose a request to declare which file needs to be stored, via File Add request. Once her file is stored, the client shall pay the rent for the storage service at periodic intervals (introduced in Section IV-A), which depends on the file's value and size. They also can ask DSN to discard their files stored before, via File Discard request. Besides, clients can retrieve any file stored in DSN, via File Get request, by paying the retrieving payment. As the uploaded files are public in DSN, clients can encrypt their files before uploading if she concerns about privacy.
2) Storage Providers: Storage Providers are the participants who rent out their hard disks to store clients' files and offer the service of retrieving files in exchange for payments. When receiving the File Add request from a client, DSN automatically selects several independent storage providers to store this file, so that the robustness could be guaranteed by replicating files. After receiving a file from a client, providers need to declare that they have obtained this file by File Confirm request. In addition, after storing a file, it is necessary for providers to repeatedly submit the proofs of file storage to DSN at each specified checkpoint, to show that they are storing this file, via File Prove request. In order to guarantee security, each storage provider must pledge a deposit, so that her deposit could be liquidated to compensate for the loss of clients once her disk is corrupted. When a client requests retrieval of a specified file, the providers, who store this file, compete to respond to the request for the corresponding payment. Hence a Retrieval Market is formed, in which the clients and providers exchange the file without the witness of DSN. Figure 1 shows a brief description of the data structures of the FileInsurer. There are four main data structures, which are sector, file descriptor, allocation table, and pending list.

B. Data Structures
1) Sector: A disk sector is the smallest unit that a provider rents out to store files. Sector sizes vary but are required to be an integer multiple of a minimum value of minCapacity. minCapacity can be set to 64GB or other deterministic value. A sector is considered to be corrupted, as long as any bit in this sector is destroyed. A file is missing, if and only if the sectors storing this file are all corrupted. In FileInsurer protocol, providers could divide their storage spaces into multiple sectors, and are not allowed to register multiple disks as the same sector. In addition, FileInsurer requires that a file is integratedly stored in a sector, instead of being dispersed into multiple sectors. Such a requirement ensures the owner of a lost file obtains the compensation, which can completely make up for her loss.
2) File descriptor: The file descriptor f describes a file stored in the network, including its size, value, Merkle root, the number of copies, and other necessary information. When a file is stored, the following two conditions must be satisfied.
• The total size of the files stored in a sector must not exceed the capacity of this sector. • If a file f is lost, meaning all sectors storing it are all corrupted, then the deposits from these sectors are at least f.value to make up the loss of the file's owner.

3) Allocation table:
FileInsurer selects some feasible sectors to store a file and makes a note of it recorded in the allocation table. The allocation table will be updated when a file is stored in the network, a file is discarded, or the storage location of a file is transferred. The allocation table is a part of the network consensus and can support fast random access. 4) Pending list: In the design of FileInsurer, some tasks need to be automatically executed at a specific time in the future, such as regularly checking whether a file is saved correctly. Therefore FileInsurer needs to maintain a pending list to save these tasks and their corresponding execution time. When a new time point t is reached, the tasks in the pending list whose timestamp is t will be automatically executed by the network. As the gas fee for these tasks should be paid in advance, tasks that are placed in the pending list must have a clear gas used upper bound. In the basic design of FileInsurer, these tasks are only generated through network consensus.

Data structures
Sector sector : (owner, id, capacity, freeCap, state) • owner: the provider who owns the sector.
• id: the id of the sector, a provider cannot have two sectors with the same id. • capacity: the storage capacity of the sector. • freeCap: current free capacity of the sector. • state: normal means this sector has capacity to accept new files, disable means the sector no longer accepts new files. File descriptor fileDescriptor : (size, value, merkleRoot, cp, cntdown, state) • size: the size of the file.
• value: the value of the file.
• merkleRoot: merkle root of the file.
• cp: the number of replicas to be stored in the network, determined by the file value. • cntdown: the number of checkpoints until the next refresh of the file store. • state: normal means this file needs to be stored, discard means this file is discarded. Allocation table allocTable : {(fileDescriptor, index) → allocEntry} allocEntry : (prev, next, last, state) • prev: the current sector storing the file. • next: the next sector to store the file.
• last: time of the last proof of storage.
• state: alloc means the file is being (re)allocated to a sector, confirm means that the file is confirmed by the next sector to store, normal means the current sector is storing the file, corrupted means the current sector is corrupted. Pending list pendingList : {time → [task,task,...]} • time: time point when the tasks need to be automatically executed. • task: description and parameters of the task to be executed.

C. Interactions between Participants and Network
This subsection introduces the abovementioned operations performed by clients and storage providers in detail.
1) Client requests: • File Add: Client stores a file in DSN.
A client submits an order through a File Add request to inform DSN of the file's description f , containing size f.size, value f.value, Merkle root f.merkleRoot, the number of replicas f.cp, and other necessary information.
DSN automatically allocates feasible f.cp sectors. When these sectors are found, the client transmits the file to these sectors.
• File Discard: Client discards a file stored in DSN. It is not necessary for clients to specify how long to store the file in advance. As an alternative, the client can discard the file at any time by submitting File Discard request, which contains the description f of this file, to DSN. • File Get: Client retrieves a file from DSN.
Each client can request any file in DSN, via File Get request, by paying a certain amount of tokens. Because this requested file is available in multiple providers' sectors, the retrieve request can be satisfied by receiving one of the copies from these providers.
2) Provider requests: • Sector Register: Provider registers a new sector in DSN.
When providers launch a new storage space, they have two options. One is to register the whole storage space as one sector. The other is to divide this space into several parts and each part is registered as one sector. When a sector is registered, the provider shall pledge a deposit proportional to the capacity of this sector. • Sector Disable: An operation to affirm that a sector no longer accepts new files.
In the design of FileInsurer protocol, providers are not allowed to revoke the sectors they leased on the network before. Instead, when a provider decides not to provide storage service from a sector, she shall declare that the sector is disabled, that it is no longer accepts any new file. After all files stored in this sector are allocated to other sectors by the network, the sector is removed from the network. • File Confirm: The provider confirms to the network that a file has been received.
The network automatically specifies the storage sector for files, and the provider of the sector needs to confirm to the network after receiving the client's file. • File Prove: The provider submits the certificate to the network of its correct storage of files. When providers store the files, they must repeatedly submit proofs of replication to ensure they are storing the files. Proofs are posted on and verified by DSN. • File Supply: The provider responds a File Get request from a client.
Once the supply and demand relationship of one file has been established, the transmission of this file would be carried off-chain.

D. Dynamic Content in Sectors
In FileInsurer, the content of a sector needs to be dynamic from time to time, which is supported by ensuring storage randomness. FileInsurer can resist Sybil attack by storing the files as multiple replicas. In FileInsurer, these replicas are generated by PoRep, and the free capacity of a sector needs to be proven that it is indeed available. A trivial idea is to make a new replica of the sector whenever the content is changed by PoRep. However, it is not a wise solution because it would lead to an extremely high burden on providers and much more verification of PoRep.
We propose a novel solution called Dynamic Replication (DRep) to solve this problem. Different from Filecoin, we don't encode a whole sector into a replica, but make each file in a sector to be a unique replica. We define a Capacity Replica (CR) as a replica of zeros bits generated by the PoRep process. When a sector is registered, it should be just filled with l unique CRs. The sector is requested to contain as many CRs as possible while storing files. Therefore, the unsealed space of a sector is smaller than the size of a CR. Figure 2 shows some examples of DRep.  (b)). When the total size of files decreases, the provider regenerates the CR3 (as shown in (c)).
Ensuring free space of sectors is indeed available by CRs is an efficient way. All CRs only need to be generated by PoRep once and then verified continuously stored via WindowPoSt [4]. If a CR has been thrown, the provider can recover it by PoRep.setup because the raw data of a CR are zeros. It doesn't need to go through the whole PoRep process because the Merkle roots of CRs have been previously verified. Therefore, DRep won't bring an extra verification burden on the DSN and providers don't need to generate SNARK of PoRep again.
Additionally, FileInsurer changes the location of replicas at a low cost. Consider that a replica of a file f needs to be transferred to another sector. The provider do not need to generate new replicas of f by PoRep, but just transfer the old ones. Liveness issue occurs that a provider may not transfer the replica of f to the successor provider. However, it doesn't bother because the successor provider can fetch the source data of f from other providers and recover the replica via PoRep.Setup. Similar to CRs, these replicas don't need to be verified again, and they can be recovered from the raw file. Therefore, the movement of replicas is efficient.

E. Storage Market and Retrieval Market
Similar to Filecoin, there are two markets in FileInsurer, the Storage Market and the Retrieval Market. The Retrieval Market in FileInsurer is the same as that in Filecoin. In the DSN, clients can send the request to retrieve any file f . Any participant with f or a replica of f can answer that request. The process of retrieving is accomplished by BitSwap of IPFS. However, the Storage Market in FileInsurer is quite different from the one in Filecoin. In FileInsurer, the price of storing a file is decided by the size and the value of that file. Clients do not need to negotiate prices of storage with providers and even do not need to specify who to store their files. Prices for storage services may change over time, which will be discussed in Section IV-A.

F. Source of Randomness
Just like other DSN protocols, FileInsurer needs a huge amount of on-chain random bits. To achieve this with low expense, we use a pseudorandom number generator [15,18] to generate long pseudo-random bits based on a short random beacon. Additionally, the issue of generating an unbiased and unpredictable public random beacon in blockchain has been well studied [6,7,12]. Combining the abovementioned two technologies, we can cheaply get enough public pseudorandom bits. In this paper, we omit the implementation of generating and using random bits because it is too detailed and not our main contribution.

G. Necessity of Compensation in DSN
Compensation is needed in DSN because the scalability of DSN would lead to an unavoidable risk of missing data. Necessarily, the scalability of storage means that a participant in DSN only needs to store a very small part of all data in DSN. Therefore, many data of DSN must only be stored by a small part of participants. However, if a constant ratio, for example, 0.1, of sectors (or storage capacity) crash instantaneously, some data may be lost. So DSN brings a huge risk of file loss.
To demonstrate more clearly, let us provide some other concrete examples. In Storj, a file is lost if enough shards of the file are not available beyond what can be recovered by erasure code. In Filecoin, a file is lost, if and only if all sectors storing replicas of this file crash down.
To balance the safety and the scalability of DSN, compensation is an effective method to motivate users to take part in the distributed file storage. The reasonable deposit shall compensate the users' loss from missing data.

IV. PROTOCOL DESIGN OF FILEINSURER
In this section, we introduce the protocol design of FileInsurer in detail. The insurance scheme is introduced into the protocol design so that the storage providers are responsible for file loss and their deposit can fully compensate the clients whose files are lost. To support the dynamical file storing in sectors, storage randomness is needed to randomly distribute the locations of replicas in DSN, which can be realized by randomly selecting and refreshing the locations of replicas. Additionally, files with higher values have more replicas so it is harder to destroy all replicas of these files.
In FileInsurer, all file replicas and Capacity Replicas are generated by PoRep, which means that WinningPoSt can be easily achieved. Therefore, the Expected Consensus deployed by Filecoin can be directly applied to our consensus algorithm. Additionally, FileInsurer protocol can be deployed as a smart contract or sidechain in other blockchain protocols such as Ethereum [25] and Algorand [10,14].

A. Fee mechanism
In our DSN design, clients need to pay a fee when they obtain the storage service and retrieval service. Moreover, there are three kinds of fees in FileInsurer, which are the traffic fee, storage rent, and prepaid gas fee.
1) Traffic fee: The traffic fee needs to be paid when a client occupies the network bandwidth of providers by transmitting files, retrieving files, or other interactions. The mechanism to pay a traffic fee is necessary because malicious clients may transmit files but pay nothing to block the providers' network. The operation to upload traffic fee must be committed to the storage provider before the file transmission, and the provider obtains the fee only when it has confirmed the file.
2) Storage rent: Clients need to pay the storage rent for the used storage space, which is proportional to the size of the file times the number of replicas. The unit rent is the same for all files, and the network informs the client how much rent it should pay. The client will be automatically charged storage rent in the task Auto CheckAlloc which will be introduced in section IV-C. In particular, the network distributes revenue by time period. In a time period, all storage rent is stored in the network at first. At the end of the period, the network distributes the rent to owners of proper functioning sectors during this period. Storage providers are paid proportionally according to their total storage capacity, without paying attention to which file is stored in which sector.
3) Prepaid gas fee: After a client stores files on the network, the network needs to periodically check the proof and refresh the file storage locations. These operations use the consensus space and thus incur a gas fee. The gas fee for these operations should be prepaid by the user as these operations are performed automatically. The prepaid gas fee shall be collected together with storage rent through Auto CheckAlloc.
In addition, anyone who submits requests to the network must pay a gas fee to avoid wasting valuable consensus space. The design of the gas fee mechanism is part of the network design. As our DSN design does not focus on the network design, we can use other existing gas fee mechanisms and do not detailedly address it in this work.

B. Deposit and Compensation
When registering a sector, the storage provider should pledge to DSN with a certain amount of deposit. The deposit is locked until the sector safely quits the system or is corrupted. If the sector safely quits, the deposit would be withdrawn to the storage provider. If the sector is corrupted, the deposit must be confiscated.
When the deposit of a sector is confiscated, it shall be stored in the network to compensate for lost files. File loss in a network means that all its copies are no longer available, i.e. those storage sectors storing the copies are all corrupted. When a file is lost, the network shall provide users with compensation equal to the value of the file. Values of files are given by users when storing their files. If a user reports a higher value than the value of her file, she would pay a higher storage rent, and if she reports a lower value, the compensation would be lower once her file gets lost.
The deposit ratio γ deposit of FileInsurer is defined as the ratio that the sum of deposits compared to the maximal value of files stored in the network. It can be understood as how much deposit is required for each unit of value stored in the network. Thus, the lower the deposit ratio makes the providers have more incentives to participate in the distributed storage network, and thus make our protocol more competitive. Now we show how to calculate the deposit by γ deposit while registering a sector. Assume that the total size of sectors in FileInsurer is N s × minCapacity and the maximal total value of stored files are N m v ×minV alue. For a sector s with capacity s.capacity, the deposit should be the proportion of s.capacity in the network multiplied by the total deposit, which is Ns be a constant and the deposit becomes s.capacity × γ deposit × capP ara×minV alue minCapacity , which can be calculated only by s.capacity, γ deposit , and some constants. The setting of γ deposit are discussed in Theorem 4.

Notation Description
RandomSector() Sample a random sector. The probability of selecting each sector is proportional to its capacity.

SampleExp(x)
Sample from an exponential distribution with mean x.
RandomIndex(f ) Sample a number between 1 and f.cp uniformly at random.

DelayP erSize
The maximum transmit time allowed per unit file size. This constant multiplied by the file size is the upper limit of the file transfer time allowed by the network.

AvgRef resh
The number of P roof Cycles to refresh the file storage on average P roof Cycle Time interval between each inspection proof.

P roof Due
The specified upper limit of the time the last proof until now.

P roof Deadline
The tolerable upper limit of the time the last proof until now.
FileInsurer mainly includes three parts: • File : protocols with File prefix handles the storage of data on the network, • Sector : protocols with Sector prefix handles the sector registration and revocation, • Auto : protocols with Auto prefix are mainly used for the maintenance of network. They are special because they cannot be called by anyone and will be executed automatically at a specific time. Figure 3 proposes a brief overview of the protocol of FileInsurer by explaining how files and sectors interact with      Figure 4 shows the network response for the clients' File requests. When a client makes a File Add request, the network first generates a file descriptor and samples f.cp sectors for storage. The probability of each sector being selected is proportional to the capacity of this sector. The number of backup files that need to be stored is calculated by f.cp = f.value minV alue k, where minV alue is a parameter representing the lower limit of the file value of network storage and each f.value must be integer multiple of minV alue. Next, the waiting time is calculated and the user needs to transfer the file to the owner of the selected sectors before the waiting time expires. Once the waiting time expires, a task named as Auto CheckAlloc is performed automatically to confirm whether the file is successfully stored on the network. When a client submits a File Discard request, the network simply sets the state of the corresponding file descriptor to discard.   2) Sector : It is simple for the network to respond to Sector requests. The pseudo-code is shown in Figure 6. A new sector is registered when a Sector Register request is received and the state of a sector will be set to disable when a request of Sector Disable is received. When all files in a disabled sector are swapped out, then it can be removed.
3) Auto : Note that the tasks with Auto prefix cannot be called by anyone and shall be executed at a specific time automatically. In the design of the FileInsurer protocol, the network needs to maintain a pending list to ensure that these tasks are executed at a specific time. There are 4 kinds of tasks with Auto prefix, which are Auto CheckAlloc, Auto CheckProof, Auto Refresh, and Auto CheckRefresh. In simple terms, Auto CheckAlloc is used to check that the file has been correctly stored on the network, Auto CheckProof is periodically proof checking, while Auto Refresh and Auto CheckRefresh are the processes of file storage refreshing in order to ensure the randomness of storage. Therefore, the period of proof checking should be short, and thus the frequency of the file storage location refreshing could be very low.
Auto CheckAlloc will be executed automatically at some time after a File Add request is responded by the network. The network shall confirm if all f.cp sectors have received the file described by f . If so, the network goes to change the state of the file descriptor to normal; otherwise, it shall inform the client that it failed to upload the file.
Every file needs to be checked at some specific time whether it is stored properly. In each specific time period, a task named Auto CheckProof automatically runs to check whether each proof to the file is timely. We provide the pseudo-code of Auto CheckProof in Figure 8. We use WindowPoSt of Filecoin [4] to implement the proof process. A sector will be punished if it cannot submit the proof of storage of its files within P roof Due time, and then its  Whenever a random number 2 of checkpoints are passed, a task named Auto Refresh will be called to randomly refresh one of the storage places of the file. Figure 9 shows the details of Auto Refresh and another corresponding task Auto CheckRefresh. The probability of sampling the new storage sector is proportional to the capacity of the  sector. The network then calculates a waiting time and the current sectors that store this file need to transfer it to the selected sector before the waiting time expires. Once the waiting time expires, the task named Auto CheckRefresh will be executed automatically to confirm whether the file is successfully stored in the new sector.

V. ANALYSIS
In this section, we analyze the performance of our protocol and compare FileInsurer with other DSN protocols in detail.

A. Notation and Assumption
Before the analysis, we list notations in Table II which are necessary for our theoretical analysis. Additionally, The following assumptions are necessary for our theoretical analysis.
• Consensus security: FileInsurer requires that the network consensus itself is secure. The issue of consensus security is not the target of this paper. • Adversary ability: FileInsurer allows an adversary to corrupt λ proportion of network capacity immediately. • Redundant capacity: FileInsurer requires that the total capacity in the network is no less than twice the total size of all files' replicas. This assumption is deployed to ensure storage randomness.
B. Performance of FileInsurer 1) Analysis for Capacity Scalability: We consider the capacity scalability of FileInsurer as the maximal size of stored files. The following theorem indicates that FileInsurer is scalable in capacity. The minimum capacity of a sector. The capacity of each sector is an integer multiple of minCapacity.

minV alue
The minimum value of a file. The value of each file is an integer multiple of minV alue. N f The number of files.

Ns
The "weighted" number of sectors. Ns ×minCapacity indicates the total capacity of the network.

Nv
The "weighted" number of files. Nv × minV alue indicates the total value of files stored on the network.
The maximum "weighted" number of files the network is designed to carry. N m v ×minV alue is the maximum value the network can carry.
is the ratio that the total value stored in FileInsurer compared to the maximal value.
The deposit ratio. γ deposit is the ratio that the sum of deposits compared to the maximal value of files stored in the network.
capP ara capP ara is defined as Security parameter. We set it to be 10 −18 . k The number of backups should be stored of a file whose value is minV alue. where r1 = f f.size×f.value minV alue× f f.size , The proof of Theorem 1 is provided in Appendix A. We claim that each of r 1 and r 2 is bounded by a constant in Section VI-A. Then the total size of raw files can be stored in FileInsurer isÕ(N s ×minCapacity), which is almost linear to the total size of sectors.
2) Storage Randomness: Storage randomness is an important issue in FileInsurer. Storage randomness can ensure the locations of replicas are evenly distributed. Therefore, the adversaries must corrupt a huge number of sectors even if they only want to destroy all replicas of a small portion of files. In FileInsurer, replicas are stored by randomly selected sectors in File Add and their locations are randomly refreshed by Auto Refresh. Such operations make the locations of all replicas are independent and identically distributed.
However, when the total used space is close to the capacity of DSN, the process of File Add and Auto Refresh faces the trouble that the free space of selected sectors is not enough for the storage of a replica. We call this event a collision. Although sectors can be reselected to store these replicas, Storage randomness would be influenced. Therefore, redundant capacity is required to avoid collisions. We claim that the frequency of collisions is ignorant by preliminary theoretical proof and further experiments.
We first consider a trivial case that all files have the same size. The following theorem indicates that a collision happens with an extremely low probability. We further consider the general case that the size of files follows a certain distribution. We conduct a series of numerical experiments in two different settings. In the first setting, we reallocate all file backups in one go for 100 times. In the second setting, we allocate each file backup and then randomly refresh the location of a file backup 100N cp times. Recall that N cp = kN v is the number of file backups and each file f needs to store f.cp backups on the network.
In the experiments, we test several distributions for the size of file backups. We focus on the maximum ratio of capacity usage. If the ratio is less than 1, no file backups are allocated to sectors with insufficient capacity. Table III shows the results of our experiments. We can find that the maximum ratios of capacity usage never exceed 0.64 under all tested distributions, which means that the probability that file backups are allocated to sectors with insufficient capacity is very small. Therefore, the results of our experiments indicate that collisions would hardly occur when the average size of file backups is much smaller than the sector capacity.
We also discuss how to maintain storage randomness when the list of sectors changes in section VI-B. These results show that storage randomness is easy to be promised in practice. Therefore, each allocation of replicas is assumed to be independent and identically distributed in the following analyses.
3) Analysis of Robustness: We consider the robustness of FileInsurer as the ability of resisting corruptions of sectors. The following theorem indicates that FileInsurer is quite robust. The proof is left in Appendix C.
Theorem 3 Assume that the total size of corrupted sectors is λN s ×minCapacity. Denote the total value of lost files to be V lost , and γ v lost = V lost Sv×minV alue represents the ratio of the value of lost files to the total value of all files. Then with a probability of not less than 1−c, γ v lost satisfies  When γ m v ≥ 0.005, γ v lost ≤ 0.001. It means that in this case, even when half of the capacity of FileInsurer is corrupted, the value of lost files is no more than 0.1% of the value of all stored files. 4) Deposit Ratio: The following theorem indicates that only a small deposit ratio is needed for full compensation.
Theorem 4 Assume that the total size of corrupted sectors is no more than λN s × minCapacity. If the deposit ratio satisfies then full compensation can be achieved with a probability of not less than 1−c.
The proof of theorem 4 is in Appendix D. Set k = 20, N s = 10 6 , capP ara = 10 3 and λ = 0.5. Then γ deposit = 0.0046 is enough to ensure full compensation, which is relatively small.   [1] No No No [1] Provides only limited file loss compensation that has provable robustness and gives full compensation for file loss.

C. Comparison with Existing Protocols
VI. DISCUSSION In previous sections, we have proposed the general framework of FileInsurer and theoretically proved the excellent performance of FileInsurer. Besides, some practical issues exist and we explore the corresponding solutions for them under FileInsurer in this section.

A. Distributions and Parameters
The value and size of a file follows a certain distribution in DSN. We have the following reasonable assumptions about the distribution.
• The maximal value of a file is bounded by a constant. Therefore, r 1 (defined in eq. (1)) is bounded by a constant. • The average value of a unit size is a bounded constant.
Then it's reasonable to assume that f f.value f f.size is bounded by a constant. Therefore, r 2 (defined in eq. (2)) is bounded by a constant. The parameters of FileInsurer should be properly set according to the distribution of files. For example, we should set parameters to make 2r 1 k is not far away from r 2 to further improve scalability bound in theorem 1. It also helps to avoid the bad situation that the total value of files is far below the maximal, but the used space has reached its limit.

B. Storage Randomness When Adding or Removing Sectors
In our analysis of storage randomness, we ignore the case that the network may add or remove sectors online. When a new sector s is registered in the network, in order to maintain the independently and identically distributed property of the allocations, the network should traverse each allocation and swap out the allocation to that sector with the probability of s.capacity Ns×minCapacity . Such an operation is impossible because traversing over files is too expensive. One good approximation method is that the network first calculates how many files backups need to be swapped into the sector by sampling from a Poisson distribution, and then randomly select the file backups to swap into the sector.
If a sector is disabled, We can request it to keep storing all replicas it currently stores even if they are slowly being swapped out. As a result, it does not get easier to attack the corresponding files. When all of its files are swapped out, this sector no longer exists in the network so the storage randomness can guarantee.

C. Adjusting to Extremely Large Files
In some special cases, very few huge files, whose sizes are comparable to the capacity of sectors, need to be stored in the network. These very large files might break storage randomness because their allocations might fail to find enough space in one turn. To address this problem from the extremely large files, the network needs to specify an upper limit sizeLimit on the size of a single file. For a file with a size greater than sizeLimit, we can convert it to a collection of segments by the erasure code, such that each segment's size is upper bounded by sizeLimit. By this operation, the file can still be recovered even if half of the segments are lost. Therefore, we can simply regard each segment as an individual file with value 2value k . In practice, we can apply the common erasure code such as Reed-Solomon code [19] to archive this.

D. Storing Files with Widely Varying Values
In FileInsurer protocol, the value of each file is required to be an integer multiple of minV alue. Thus a file with a value of v can be treated as v minV alue documents worth of minV alue. This means that a high-value file needs to have many replicas in the system, and the number of replicas is linearly related to this file's value. A compromise solution is to pre-divide the value levels of files and to establish a storage subnetwork corresponding to each level. Then the clients can choose which subnetwork to store files based on the value level of their files.

E. Avoiding Selfish Storage Providers
Selfish storage providers refer to these providers who store files but do not normally provide retrieval services. Assume the ratio of the number of selfish storage providers to the number of all providers is α in the network. Then it is expected that α k proportion of files suffer from the threat of the selfish providers' collusion. Here k is just the number of copies of a stored file. As a result, any protocol that fixes file storage locations cannot fundamentally solve the problem of selfish storage providers. However, a natural advantage of FileInsurer is that its file refresh mechanism can fundamentally eliminate the threat from selfish storage providers. Because of the existence of refreshing file storage location, no single file will be completely controlled by the selfish storage provider for a long time.

F. Supports for IPFS
Filecoin has shown how to support IPFS in a blockchainbased DSN, and FileInsurer has a similar approach. In FileInsurer, the hashes and locations of files are all stored in blockchain. Therefore, it's easy to build and update DHTs and Merkle DAGs on FileInsurer so that anyone can address files stored in FileInsurer through IPFS paths. The retrieval of files can be also realized through BitSwap protocol.

VII. CONCLUSION
In this paper, we propose FileInsurer, a novel design for blockchain-based Decentralized Storage Network, which achieves both scalability and reliability. FileInsurer is the first DSN protocol that gives full compensation to file loss and has provable robustness. Our work also raises many open problems. First, are there other approaches to enhance the reliability of Decentralized Storage Networks? For example, a reputation mechanism [8] on storage providers may be also helpful to reduce the loss of files. Second, are there other ways to support dynamic content in sectors other than DRep? Furthermore, can the idea of FileInsurer be extended to decentralized insurance in other scenarios?
x(1−x) ≥ 0 and g(p) = 0. Finally, we obtain h(x) is monotonically increasing because . We can find that d dp Lemma 3 Assume that the total size of corrupted sectors is λN s × minCapacity. Denote the total value of lost files to be V lost . Then, with a probability of not less than 1−c, V lost satisfies V lost ≤ minV alue×max 5Nvλ k ,Nvλ Proof: Because of lemma 1, we can make the relaxation of that each file has value minV alue in subsequent analysis. Under the relaxations, the setting of the problem can be simplified as follow: there are N v files, each file has the same value minV alue and needs to be stored in k sectors. Each storage location of each file is generated independent and identically distributed.
For any certain scheme that the adversary corrupts λ ratio of capacity, which means that the total size of corrupted sectors is λN s ×minCapacity, define random variable X i as the indicator variable of that the file f i is lost. Recall storage randomness indicates that all replicas are evenly and randomly distributed.
Then all X i are independent events and Pr[X i ] = λ k when any sectors with total space of λN s ×minCapacity are corrupted.
Denote γ = V v lost minV alue . By Chernoff bound and lemma 2, when γ ≥ 5N v λ k , we obtain Consider the number of scenarios in which an adversary can corrupt sectors with capacity λN s ×minCapacity. Here we do a simple scaling that treat a sector with s.capacity capacity as s.capacity minCapacity sectors with capacity minCapacity. After this scaling, the adversary has Ns λNs options to corrupt sectors. Therefore, for the original situation, the number of scenarios in which an adversary can corrupt sectors with capacity λN s ×minCapacity does not exceed Ns λNs . By union bound, when γ ≥ 5N v λ k , the probability it cannot manufacture γ lost files is at least This shows that when γ meets the above three conditions, the probability that an adversary can make γ lost files does not exceed 1−c, that is, γ needs to satisfy γ ≤ max 5λ k N v ,λ then full compensation can be achieved with a probability of not less than 1−c.
Proof: By assumption, the total size of corrupted sectors is no more than λN s ×minCapacity. Because the deposit of corrupted sectors should always cover the file loss, for all 1 Ns ≤ λ ≤ λ we shall have λ γ deposit N m v ≥ γ, which is equivalent to γ deposit ≥ max Then with probability no less than 1−c, the following γ deposit is enough for full compensation γ deposit ≥ max