Erasure Coding

Erasure coding is a technique for protecting data against loss by breaking it into fragments, calculating additional redundant fragments from them and storing all the fragments in different places. The mathematics is arranged so that the original data can be reconstructed from any sufficiently large subset of fragments, even if some are lost, corrupted or unavailable. It achieves the same protection as keeping several full copies while using far less storage space.

Erasure codes have been used for decades in CDs, DVDs, QR codes, satellite communications and disk arrays, and they underpin large cloud storage systems. The best-known family, Reed–Solomon codes, was published by Irving Reed and Gustave Solomon in 1960. In crypto, erasure coding has become important for data availability, letting blockchains and layer-2 networks prove that published data can be recovered without every node storing all of it. It also helps decentralized storage networks keep files safe across unreliable providers.

Suppose someone wants to keep an important ten-page document safe. One option is to make three full photocopies and store them in three places, which triples the paper. Erasure coding is cleverer: it adds four special pages, calculated from the original ten, and stores all fourteen pages in fourteen different places. Any ten of the fourteen pages, whichever ones survive, are enough to rebuild the whole document.

This means up to four pages can be lost without harm, while using only 40% extra paper rather than 200%. The catch is that rebuilding the document from a mix of original and special pages takes some calculation, which costs time and computing power.

Data is split into $k$ data fragments, and an encoding function produces $m$ parity fragments, giving $n = k + m$ fragments in total. A well-designed code allows the original data to be recovered from any $k$ of the $n$ fragments. The extra storage required is measured by the overhead ratio:

• $k$ is the number of original data fragments.
• $m$ is the number of parity fragments added.
• $n$ is the total number of fragments stored.

For example, with $k = 10$ and $m = 4$, the overhead is $14 \div 10 = 1.4$, so storing 100 gigabytes requires 140 gigabytes, and any four fragments can be lost. Keeping three full copies, by comparison, needs 300 gigabytes and survives the loss of two copies. Reed–Solomon codes do this by treating the data as values of a polynomial and storing extra evaluation points: any $k$ points are enough to rebuild the polynomial.

• Data availability sampling. Ethereum's scaling roadmap and networks such as Celestia extend each block's data with erasure coding, typically doubling it. Because any half of the extended data suffices to rebuild it, a block producer who wants to hide data must withhold a large share, which light clients can detect by checking a few random pieces, a method described under data availability sampling. This underlies the blob capacity introduced by the Dencun upgrade and its successors.
• Block propagation. Solana breaks blocks into erasure-coded pieces when spreading them across validators, so nodes can rebuild a block even if some packets are dropped.
• Decentralized storage. Storage networks such as Filecoin and other decentralized storage systems can use erasure coding to spread files across many independent providers, so the loss of some providers does not mean the loss of a file.

The approach also links to sharding, the long-standing idea of splitting a blockchain's workload among groups of nodes. Rather than each group storing a different slice of raw data, erasure-coded data can be spread so that no single node needs all of it, while the network as a whole can still recover everything. A full node that wants complete certainty can still download the whole data set, but most participants can rely on sampling instead.

Erasure coding offers high durability with modest storage overhead, which is why large providers of cloud computing use it for archival and object storage. It spreads risk across machines, data centres or independent operators, which suits decentralized systems where any single node may disappear. In blockchains, it makes it practical to verify that large amounts of data are available without each participant downloading everything, helping to ease the tension described in the blockchain trilemma between scale and decentralization.

Encoding and decoding require computation, and rebuilding lost fragments can need data from many other fragments, which uses network bandwidth. Small updates are awkward, because changing part of the data may require recalculating parity fragments. In adversarial settings such as blockchains, the system must also prove that fragments were encoded correctly; designs use cryptographic commitments, such as polynomial commitments, or fraud proofs to catch a producer who encodes data dishonestly. Erasure coding protects against loss and unavailability, not against unauthorized access, so it is usually combined with encryption and other data security measures.