**A common problem in storage systems is guaranteeing that a remote party is storing the data it committed to, with the expected level of redundancy. There is a class of attacks characterized by the storing party pretending to store something $N$ number of times or hold $N$ number of copies, while in reality, storing much less than $N$ and downloading and reconstructing the required pieces on demand from a third party.**

For example, a Sybil attacker would control a large number of identities in the network and pretend to store data with some level of redundancy, while in reality, only storing it once. A generation attack would store a subset of the data and only regenerate it on the fly. Both attacks compromise the redundancy of the data and for the purpose of this note, we will refer to them as **outsourcing attacks**.

The question then is, how do we ensure that the redundancy levels aren't compromised through some version of an outsourcing attack? Or more precisely, how do we ensure that each instance of erasure-coded data is stored in full?

## Proofs of Replication

Proof of Replication (PoRep) is a type of proof of storage that combines Proofs of Space and Proofs of Retrievability. Fundamentally, PoRep attempts to demonstrate that there are $K$ unique instances of the exact same data, thereby **preventing data deduplication**.

However, PoRep is not always suited for erasure-coded systems and arguably has a number of other drawbacks. For example, it relies on complex and computationally heavy mechanisms to achieve its goals.

In Filecoin, this process is called **sealing** and it's intentionally computationally intensive. It also renders the sealed data inaccessible without reversing the process, which makes data access and retrieval a major source of issues in the Filecoin network.

While we could adapt PoReps to an erasure-coded setup, the complexity and overhead don't align well with our focus on a more practical and lightweight approach. Nevertheless, PoReps are a useful model to analyze and understand the underlying problem.

## High-Level Problem Overview

As stated above, we want to prevent cheating nodes from pretending to store data they in fact aren't, either in full or in part. A common way of accomplishing this, used in replicated systems, is to make each instance demonstrably unique, such that there are objectively $K$ out of $K$ distinct instances of the exact same data.

However, one immediately apparent thing, is that uniqueness in erasure-coded systems isn't enough. In an erasure-coded system, there are distinct segments or pieces that can be used to reconstruct another distinct piece or segment on demand, and efficient reconstruction from any $K$ subset of the pieces is a major goal. Thus, any mechanism applied to erasure coded systems, should at the very least allow recovery from a minimal subset of pieces or segments.

More succinctly, we're looking for:

- Demonstrable uniqueness across each instance
- Prevention of on-the-fly reconstruction through controlled reconstruction, but don't disallow it completely

## Data Layout and Distribution

It's worth outlining the different possible ways that erasure-coded datasets can be structured and the data distributed. We assume that all the erasure coding is systematic, that is, the original pieces are in plaintext and don't require decoding.

1. **Fully Replicated EC**: An erasure-coded dataset $D'$ is replicated across $N$ nodes in the network. This is similar to replication, but with the advantage that **any** $K$ pieces from any of the replicas can be used to reconstruct the original datasets. In this case, each erasure-coded dataset needs to be instantiated separately to prevent deduplication, just as in the case of straightforward replication.
2. **Segmented EC**: A dataset $D$ that is erasure-coded into $D' = {d_1, d_2, \ldots, d_n}$, where $d_n$ are segments that are distributed across $N$ distinct nodes and any $dK$ distinct segments can reconstruct $D'$ from which the segment can be derived.
3. **Segmented EC with local redundancy**: A variation of the above case could also additionally erasure code each segment, for example, to enhance recoverability or as part of PoR proving.
4. **Fully Replicated Segmented EC**: The last case is a replicated version of the previous two, where the same erasure-coded dataset $D' = {d_1, d_2, \ldots, d_n}$ and its segments are replicated multiple times across groups of $N$ nodes.

## Attack Strategies

- **Download** - download all the pieces, without reconstructing
- **Reconstruct** - reconstruct all the pieces, without downloading
- **Download and Reconstruct** - download just enough to reconstruct

Under **Fully Replicated EC** (1), an attacker can drop a part of the file and reconstruct from the remaining pieces or download them wholesale; or it can drop the entire file and download all the pieces or download enough and reconstruct. This setup allows the attacker to execute any combination of the available strategies.

In **Segmented EC** (2), the attacker has fewer options. If an attacker intentionally dropped its segment, it would require downloading $K$ segments from $K$ nodes and reconstructing the entire file, before recovering its own segment. This seems to be the least favorable setup for an attacker. However, if the segments are additionally erasure-coded (3), then the attacker could still execute the **Reconstruct** strategy on the local segment.

The last case, **Fully Replicated Segmented EC** (4), allows the attacker to also apply a combination of all three strategies. If there are other nodes with exactly the same segment, the attacker could attempt to drop the entire file and download the full segment; or download enough of it to reconstruct. It could also drop a part of the segment and attempt to reconstruct locally.

## High-Level System Requirements

Of course, the types of attacks described here are only rational under certain conditions, thus it is crucial to understand the system and its requirements before outlining a solution. As mentioned above, we're interested in these types of attacks in the context of Erasure Coded Decentralized Storage Networks (DSN). Specifically, we're interested in public DSNs where both auditability and reconstruction work without possession of private information, such as a private key. In other words, anyone should be able to audit a storage provider and similarly anyone should be able to reconstruct the data, without possession of any private information.

Thus, the high-level requirements are:

- Guarantees uniqueness and thus deduplication
- Doesn't complicate data retrieval
- Has acceptable setup costs
- Keeps erasure coding properties mostly intact

In addition to the above, we also want public auditability and reconstruction.

A common approach in erasure-coded systems is to encrypt the parity bits of the erasure-coded data, this keeps the clear text bits intact allowing for easy retrieval. This type of approach is often used to prevent adversarial erasure attacks, where a malicious node attempts to erase pieces strategically to pass audits and remain undetected.

Encrypting the parity bits is a common way of achieving this, however, without clear timing guarantees, it might still be susceptible to generation attacks. Using a symmetric private key would address this to some extent, but it makes public reconstruction impossible, thus making it inviable in the public setting. Another approach is to use public-key cryptography, but then again, without clear timing guarantees, this makes it vulnerable to generation attacks.

As we can see, in the case of public reconstruction, this is impossible to achieve without clear timing guarantees.

Another important aspect that encryption brings into the fold is the rationality of the attack. Clearly, if the key is much smaller than the stored data, then it would make it rational to try to store only the key, even when the timing guarantees are well defined. On the other hand, if the key is as large as the data, then keeping the key around becomes impractical, even when the timing restrictions can be overcome.

This is an interesting property that can be used to our advantage.

## Solution Sketch

Encrypting the parity bits seems like a viable approach if 2 main conditions are met: a) re-encryption is well-timed, for example by making key generation itself, time-bound as well, and b) discouraging caching of the encryption key.

In PoRep, it isn't uncommon to require many hours of intensive computation to strengthen the system against timing attacks, however, this makes setup often much less practical and undesirably long to complete.

The solution proposed here, on the other hand, attempts to balance the overall safety of the scheme and its practicality, especially in terms of setup costs that might be shared between the client and provider.

In short, we use a key as large as the encrypted data, which is itself generated on demand with well-defined timing assumptions. Making the key as large as the data, makes it irrational to store the key for later re-use and timing the key generation, allows us to prevent regeneration of the key on the fly.

There is a clear tradeoff in favor of making the scheme storage vs computation bound, which avoids the potentially heavy computation required by PoRep-like systems.

## The Solution

The solution proposed consists of encrypting the parity data using a **One-time Pad**-like encryption scheme. An OTP key is at least as large or larger than the encrypted data and is well suited for this case. In OTP, each bit of plaintext is XORed with a bit of a pre-shared key that is completely random, used only once, and then destroyed.

In our case, we do not care about the key being private and single-use, in fact, we want the key to be reusable such that it allows anyone to recover the data, provided they are willing to spend the time and resources to do so. However, the key generation has to be well-timed such that an attacker cannot quickly regenerate it on demand, which would defeat the purpose of the scheme.

The setup described below is assumed to be done by a trusted party, such as the owner of the data, who performs both the key generation and commitment $Com$ to the data. For a setup performed by an untrusted party, a verifiable delay function ($VDF$) might be required to time the key generation, in addition to an outsourceable commitment scheme. In the case of the trusted party, a simple iterative hashing approach should suffice.

At a high level, it works as follows. Take the data $D$, erasure code it with a systematic erasure code that produces parity data $P$ and leaves the original data $D$ in plaintext. Next, we use publicly known but unique entropy $e$ as a seed for a collision-resistant hashing function $H(e)$ that runs iteratively $[N \ge \frac{|P|}{\text{len}(H)}]$ number of steps, such that the output from the previous step is used as the input to the next and each output is concatenated into a file $F_\text{key}$. The process runs until $|F_\text{key}|\ge|P|$. Next, perform a $XOR$ of $P$ and $F_\text{key}$ to produce $P'$, such that $P' = P \oplus F_{\text{key}}$. Once we have $P'$, we commit to both the plaintext $D$ and the encoded parity $P'$, such that $[Com=D||P']$.

This results in three key components, 1) the erasure coded data itself, 2) the encoding key $F_\text{key}$ and 3) a commitment $Com$ to the systematic data $D$ and encrypted parity $P'$.

## Analysis

The advantage of our approach is that it combines both timing assumptions with storage hardness. In contrast to PoRep, where the setup (or sealing) process is extremely resource-intensive to discourage even the most powerful attackers from attempting to repeat it more than once, our approach allows relaxing the computational requirements by making the scheme storage-bound in addition to also being computationally bound. This is achieved by having a key as large as the encoded data, which renders storing the key instead of the actual encrypted data irrational.

One major drawback is the fact that the parity bits need to be as large or larger than the original bits, otherwise, if they're significantly smaller then it would still be rational to only keep the parity bits and attempt to download the original bits on demand. For example, with a rate $r \gt 0.5$, there are fewer parity bits than original bits, which makes it possible to only store the encoded bits and download the clear text ones. This can be avoided by encoding the original and parity bits with the OTP-like key, which could make this scheme a full-fledged PoRep that relies on storage hardness in addition to computational hardness. Of course this would complicate retrieval and recovery, by requiring the encryption key to be always available, thus this approach seems less practical.

## Conclusion

While PoRep attempts to provide reasonable guarantees against some outsourcing attacks in DSNs, they suffer from significant computational overhead and are impractically time-bound. Our proposed solution attempts to overcome this limitations by making the key as large as the encoded data and the key generation reasonably (e.g. more than the verification window) time-bound.

However, it's important to keep in mind that this scheme isn't a direct replacement for PoRep. Although it emulates certain aspects of it, it isn't a complete Proof of Storage (PoSt) mechanism, as is the case with PoReps. In our case, proving storage possession not a direct goal and we focus on preventing outsourcing attacks under the **rational node** assumption and it's thus objectively weaker than PoRep as it is presented here.