Glossary

Erasure Coding

Erasure coding splits data into redundant fragments so the original can be reconstructed from any sufficient subset.

Key Takeaways

  • Erasure coding encodes k data chunks into n coded chunks (where n > k), allowing the original data to be reconstructed from any k of the n chunks. This provides redundancy far more efficiently than simple replication.
  • In blockchain systems, erasure coding enables data availability sampling: validators download only small random samples and gain statistical confidence that the full data is recoverable, without any single node storing the entire dataset.
  • Reed-Solomon codes are the most widely used type of erasure code in blockchain contexts, powering the two-dimensional encoding scheme planned for full danksharding on Ethereum as well as data availability layers like Celestia.

What Is Erasure Coding?

Erasure coding is a data redundancy technique that transforms a piece of data into a larger set of coded fragments, such that the original data can be perfectly reconstructed from any sufficiently large subset of those fragments. Unlike simple replication (storing three full copies), erasure coding achieves comparable or better fault tolerance with significantly less storage overhead.

The concept was introduced by Irving Reed and Gustave Solomon in 1960 and has since become foundational in storage systems, telecommunications, and satellite communications. In recent years, erasure coding has become critical to blockchain scalability efforts, where it allows networks to verify that block data is available without requiring every node to download every byte.

The core idea is straightforward: given k original data chunks, an erasure code produces n total chunks (n > k) such that any k of them are sufficient to recover the original data. The remaining n - k chunks are parity data, computed from the originals using polynomial algebra over finite fields.

How It Works

Erasure coding is built on a mathematical insight: a polynomial of degree k - 1 is uniquely determined by k points. The encoding process treats each data chunk as a point on a polynomial and evaluates that polynomial at additional points to generate parity chunks.

  1. The original data is split into k equally sized chunks
  2. A polynomial of degree k - 1 is fitted to those k data points
  3. The polynomial is evaluated at n - k additional points, producing n - k parity chunks
  4. All n chunks (k data + n - k parity) are distributed across storage nodes or network participants
  5. Any k of the n chunks can reconstruct the polynomial, and from it, the original data

This property means the system can tolerate the loss of up to n - k chunks and still recover the original data perfectly. The ratio k/n is called the coding rate and determines how much overhead the scheme introduces.

Reed-Solomon Codes

Reed-Solomon (RS) codes are the most common family of erasure codes used in blockchain systems. They operate over Galois fields (finite fields), which provide the algebraic structure needed for exact polynomial interpolation. An RS code is typically written as RS(n, k), where n is the total number of encoded blocks and k is the number of original data blocks.

For example, RS(8, 3) splits a file into 3 original chunks and encodes it into 8 total chunks. Any 3 of the 8 chunks can reconstruct the full file. The trade-off is computational cost: Galois field arithmetic is more expensive than simple XOR operations, though modern hardware and optimized libraries make this practical for most applications.

RS codes are used in production systems ranging from RAID-6 storage on Linux to Apache Hadoop, Microsoft Azure, and cloud storage providers. Their mathematical guarantees make them ideal for systems that require provable data recoverability.

The 2x Blowup Factor

In blockchain data availability designs, the most common configuration doubles the data: k original chunks become 2k total chunks (the coding rate is 1/2). This is called the 2x blowup factor because the total encoded data is twice the size of the original. Any k of the 2k chunks, or equivalently any 50% of the extended data, can reconstruct the original.

This 2x overhead is a deliberate trade-off between storage efficiency and sampling security. A higher blowup factor would make sampling more efficient (fewer random samples needed for confidence) but would increase bandwidth and storage costs for nodes. The 2x factor has emerged as the practical sweet spot for blockchain data availability layers.

Two-Dimensional Reed-Solomon Encoding

Full danksharding on Ethereum uses a two-dimensional Reed-Solomon scheme. The blob data is arranged into a matrix (for example, 256 rows by 256 columns), then each row is extended from 256 to 512 cells using RS coding, and each column is similarly extended. The result is a 512 × 512 matrix where the original data occupies one quadrant.

This 2D structure has a key advantage: if any individual cell is missing, it can be reconstructed from either its row or its column, as long as at least 50% of the cells in that row or column are available. This provides two independent repair paths for every cell, significantly improving resilience. It also means that a fraud proof for incorrect encoding only needs to reference a single row or column (roughly √k data) rather than the full dataset.

Role in Data Availability Sampling

Erasure coding is the foundation that makes data availability sampling (DAS) possible. Without erasure coding, a node would need to download the entire block to confirm that all its data is available. With erasure coding, a node can instead download a small number of random cells and, if all of them are present, become statistically confident that the full data is recoverable.

The logic works as follows: if a block producer hides even 1% of the extended data, that missing data must be spread across many cells (since any 50% can reconstruct the full dataset, the producer would need to withhold more than 50% to prevent reconstruction). Random sampling quickly detects this withholding. With each additional sample retrieved, the probability that the data is unavailable drops exponentially.

This technique is essential for scaling blockchains because it decouples verification cost from block size. A rollup can post large amounts of data to the base layer, and light clients can still verify data availability by sampling a small constant number of cells, regardless of how large the total dataset is.

From Proto-Danksharding to Full Danksharding

Ethereum's scaling roadmap introduces erasure coding in stages. Proto-danksharding (EIP-4844), already live on Ethereum, introduced blob transactions that attach up to 128 KB of data each, with a target of 3 blobs per block and a maximum of 6. At this stage, all blobs are broadcast in full to every node: no erasure coding or sampling is used yet.

Full danksharding will add the 2D Reed-Solomon encoding and data availability sampling described above. The target is to support up to 32 MB of blob data per block, a dramatic increase that is only feasible because nodes will no longer need to download the full data. PeerDAS, the networking protocol for distributing and sampling erasure-coded cells, is under active development with specifications evolving as of 2025. Each validator node will be assigned custody of specific columns in the extended matrix and will serve those cells to sampling peers.

The KZG commitment scheme works alongside erasure coding in this design. KZG commitments provide succinct proofs that individual cells belong to the encoded polynomial, so a sampler can verify the correctness of each cell it downloads without trusting the data provider.

Use Cases

Blockchain Data Availability

The primary use case in the blockchain context is ensuring data availability for layer-2 rollups. Rollups post their transaction data to the base layer, and validators need to confirm that this data is available so anyone can reconstruct the rollup's state. Erasure coding makes this verification lightweight. This is covered in depth in the EIP-4844 blob fee market analysis.

Distributed Storage Networks

Decentralized storage systems use erasure coding to distribute data across many nodes without trusting any individual node. Projects like Filecoin, Arweave, and Walrus encode data so it can survive node failures and network partitions. The Walrus storage network, for instance, uses RS encoding with a roughly 3x overhead to tolerate up to one-third of nodes being malicious in an asynchronous network model.

Traditional Storage Systems

Outside of blockchain, erasure coding is a mature technology in enterprise storage. RAID-6 arrays use a form of erasure coding to tolerate the failure of any two disks. Cloud providers including Microsoft Azure and Amazon S3 use RS codes to provide high durability (often eleven nines) with lower storage overhead than triple replication.

Polkadot Parachain Validation

Polkadot uses erasure coding for parachain data availability. When a parachain block is produced, the relay chain validators erasure-code the block data and distribute the chunks. Validators assigned to a parachain only need to download and verify their assigned chunk. If any validator challenges the block, the full data can be reconstructed from the distributed chunks.

Risks and Considerations

Computational Overhead

Erasure coding is more computationally expensive than simple replication. Reed-Solomon encoding and decoding require finite field arithmetic (multiplication and inversion over Galois fields), which is slower than the XOR operations used in simpler schemes like RAID-5. For block producers who must encode large datasets on a per-block basis, this computational cost can become a bottleneck. Optimized libraries and hardware acceleration (such as SIMD instructions) help mitigate this in practice.

Incorrect Encoding Attacks

A malicious block producer could publish data that claims to be erasure-coded but is actually encoded incorrectly. If the parity chunks are inconsistent with the data chunks, reconstruction would produce garbage data even if enough chunks are available. Detecting this requires either validity proofs (like KZG proofs per cell) or fraud proofs that demonstrate the inconsistency. The 2D Reed-Solomon scheme reduces fraud proof size to a single row or column, but the attack remains a design concern for any erasure-coded system.

Repair Problem

When nodes go offline and their chunks are lost, the network must repair those chunks to maintain redundancy. Repair requires downloading enough surviving chunks (at least k) to reconstruct the missing ones. In a continuously operating system, this repair bandwidth can be significant. Research published in 2025 by Boneh, Neu, Nikolaenko, and Partap formalized the local repair problem for data availability sampling, noting that efficient repair had not been rigorously studied despite being critical for practical deployments.

Storage and Bandwidth Trade-offs

The 2x blowup factor means every byte of original data requires two bytes of total storage across the network. For systems targeting 32 MB of blob data per block, this means 64 MB of erasure-coded data must be distributed and stored. While this is far more efficient than full replication (which would require every node to store the entire 32 MB), it still represents a meaningful cost, especially for nodes with limited bandwidth or storage capacity.

Sampling Assumptions

Data availability sampling relies on enough independent samplers to collectively request a sufficient fraction of cells. If the total number of sampling nodes is too low, or if an adversary can partition the network so that different samplers see different subsets of cells, the statistical guarantees weaken. This is an active area of research in the Ethereum community, with networking challenges around DHT-based sample distribution being studied as recently as 2024.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.