← Back to Research

Decentralized Storage with Provable Deletion

1. The gap: proof of storage, but not proof of deletion

Existing decentralized storage systems (Filecoin, Storj, Arweave) center on proving that data continues to exist: a node periodically demonstrates it still holds the bytes it was paid to keep. This is proof of storage. The inverse problem — proving that specific data no longer exists anywhere in the network — has received little attention, yet it is precisely what erasure-rights regulation demands. A user who invokes the right to be forgotten needs assurance not that data is stored, but that it is gone. We treat provable deletion as a first-class operation.

2. Method

Each file is split with a systematic Reed-Solomon code over GF(256) into n fragments, any k of which reconstruct the original, tolerating the loss of n-k fragment holders. Fragments are placed on n distinct nodes. The on-chain commitment is compact: a Merkle root over the fragment hashes plus the placement map — hundreds of bytes regardless of file size. Possession is verified by challenge: a fresh nonce is issued and each node must return a hash of the nonce concatenated with its fragment, which cannot be precomputed. Deletion removes every fragment from every holder and then issues a post-deletion challenge; a deletion proof records the prior Merkle root, the count of fragments removed, and cryptographic confirmation that no fragment survives the challenge.

3. Durability results

We measured recovery rate as a function of independent per-node failure probability, k = 3 and n = 5, 200 trials per point:

At realistic failure rates (10–20%), durability is high without any single node being trusted. The curve is governed by the k/n ratio: lower ratios (more parity) raise durability at the cost of storage overhead. The 5/3 configuration here carries 67% overhead; production cold storage would tune this per durability target.

4. Provable deletion results

Across all deletion trials, every fragment was removed and zero fragments survived the post-deletion challenge, yielding a deletion proof whose validity rests on the same challenge mechanism used for storage proofs. Because the pre-deletion Merkle root is retained in the proof, an auditor can confirm both that the data existed and that it was subsequently erased — a complete, tamper-evident erasure record. Anchoring this proof to a blockchain makes the fact and time of deletion permanently auditable, which is the property regulation actually requires.

5. Honest limitations

• The results are from a controlled simulation of the protocol, not a live wide-area network; real deployments face network partitions, adversarial nodes, and timing attacks not modeled here.
• The proof-of-storage challenge shown demonstrates possession but a production system needs the full challenge-response verification re-derived from committed fragment samples to resist a node that discards data yet fabricates proofs; our simulation marks possession rather than fully re-verifying it.
• Provable deletion assumes honest execution of the delete command by nodes; a malicious node that secretly retains a copy cannot be detected by challenge alone — defeating this requires encryption of fragments with keys destroyed on deletion, so that a retained fragment is useless. We regard fragment-level encryption with key-destruction as the necessary complement to this protocol and the subject of future work.