# Efficient Data Availability Sampling via Coded Distributed Arrays

Crypto.world

> Blockchains cannot scale if every node must download a full block to confirm the data is really there, so Ethereum and others are moving to Data Availability Sampling, where nodes hold only fragments…

**arXiv**: 2606.16200

**Published**: 2026-06-15

**Authors**: Dang Pham Minh, Hung Vuong Huu, Duc A. Tran

## AI summary

## Overview

**Research area:** Blockchain data availability — specifically the peer-to-peer networking and coding layer of Data Availability Sampling (DAS) for Ethereum-style rollup data (blobs under EIP-4844), drawing on erasure coding, KZG polynomial commitments, and Random Linear Network Coding (RLNC).

**Technical level:** Advanced. The paper assumes familiarity with erasure codes, KZG commitments, finite-field linear algebra, and Byzantine-fault P2P models.

**Scope:** The paper proposes CDA (Coded Distributed Array), a grid-based DAS design that replaces RDA's full-column chunk replication with RLNC-coded pieces, and benchmarks it against RDA under identical security constraints.

## What This Paper Is About

Blockchains cannot scale if every node must download a full block to confirm the data is really there, so Ethereum and others are moving to Data Availability Sampling, where nodes hold only fragments and verify availability by random sampling. Prior DAS work concentrates on cryptography, leaving the peer-to-peer layer — how fragments are disseminated, discovered, routed, and stored under Byzantine participants — comparatively underexplored. The paper's goal is a DAS design that keeps the Byzantine robustness of the Ethereum Foundation's RDA grid scheme while sharply cutting storage, propagation, and synchronization costs, by storing small network-coded pieces instead of replicating whole chunks in every node of a column.

## Key Contributions

1. **Cell-level RLNC coding.** Instead of replicating an entire chunk across a column of nodes, CDA splits each cell symbol into *k* pieces and disseminates random linear combinations of them. Each stored coded chunk is only 1/*k* the size of the raw chunk, which the authors state makes per-node storage *k* times less than RDA.
2. **A homomorphic KZG commitment scheme for coded pieces.** Because RLNC pieces are linear combinations of raw pieces, CDA requires an additively homomorphic commitment. The paper shows how a commitment and opening for a coded piece can be computed as the same linear combination of the per-piece commitments and openings, so a verifier can check a coded piece against the commitment without reconstructing the original symbol. Security is argued to reduce to the *t*-Strong Diffie-Hellman assumption, preserving code binding and position binding.
3. **A Byzantine-tolerant P2P grid network layer with STORE and GET mechanisms.** Nodes sit in a k₁ × k₂ grid (custody cells), maintain contacts with all nodes in their row or column, and use bootstrap nodes for joining and fallback. Publication broadcasts chunks to a custody cell, whose members re-code and push coded chunks down the custody column; sampling broadcasts a request to a cell, whose members fetch and decode pieces from the column.
4. **An evaluation against RDA** using the RDA paper's benchmark settings, with a churn simulation 10× larger than the RDA benchmark, measuring commitment overhead, replication factor, propagation cost, and synchronization cost.

## Main Findings

- **Storage / replication factor:** At M = 5,000 nodes, CDA's feasible column dimension ranges from k₂ = 1 to k₂ = 25, giving a replication factor falling from 156.25 to 6.25, whereas RDA's feasible k₂ ranges from 1 to 72 with replication factor from 2,500 down to approximately 34.7. Choosing the largest feasible k₂, CDA's replication factor is about 5.5× smaller than RDA's. At M = 10,000 the reduction factor is approximately 5.7×. The abstract and conclusion summarize this as more than 5× better in storage.
- **Propagation cost:** At M = 5,000, CDA ranges from 2.07×10¹³ bytes (19,286 GiB) down to 4.30×10¹⁰ bytes (40.05 GiB), while RDA ranges from 228,200 GiB down to 79.4 GiB. At the minimum-cost operating point CDA reduces propagation cost by approximately 2×. At M = 10,000, CDA's minimum is 24 GiB versus RDA's 55.1 GiB, a reduction factor of about 2.3×.
- **Synchronization cost:** At M = 5,000, CDA ranges from 1.13×10⁸ bytes down to 1.80×10⁵ bytes, versus RDA's 1.34×10⁹ down to 2.59×10⁵ bytes, a reduction of about 1.44× at the optimal operating point. At M = 10,000, CDA's minimum is about 1.5× lower. The abstract and conclusion cite 1.4× as the headline figure.
- **Honest-node availability:** In a join-leave simulation with 50 nodes joining and 50 leaving at every step over 50,000 time steps, each column consistently held significantly more than one honest node — at least 12 honest nodes per column in both CDA and RDA — stable across the whole simulation horizon. This supports CDA's "optimistic" assumption that multiple honest nodes exist per column, versus RDA's worst-case reliance on a single honest node.
- **Commitment overhead is negligible:** For fragment sizes k ∈ {8, 16, 32}, the ratio of commitment size to block size is negligible and decreases rapidly with increasing block dimension, even though CDA adds multiple commitments per cell (k = 1 corresponds to RDA).
- **Acknowledged tradeoff:** CDA must download several coded pieces from different sources to reconstruct one symbol, whereas RDA downloads a single symbol from one source holding the full chunk. The paper states this is an inevitable tradeoff and leaves quantification of its effect on sampling latency to future work.

## Methodology in Plain English

The starting point is RDA, which arranges nodes in a grid, slices the block into chunks assigned to columns, and has every node in a column store the whole chunk. CDA keeps the grid but changes what is stored. A block is first expanded with 2D Reed–Solomon coding (the "Tensor Codes" structure used by PeerDAS), so a 32MB block becomes a 256 × 256 matrix of 2KB cells, i.e. 128MB. Each cell is then split into *k* pieces, and a random linear combination of those pieces — an RLNC piece — stands in for the cell. Because random combinations can be recombined locally, a cell can be rebuilt once enough independent coded pieces are gathered, and each individual piece is small.

Verification uses KZG commitments over BLS12-381. Commitments are made per piece-column, and the commitment for a coded piece is computed as the same random linear combination of those commitments; the same holds for openings. So a node that receives a coded piece can verify it directly against the block's published commitments, with no need to reconstruct anything. Publication then works in two hops: the publisher broadcasts a chunk to its destination cell, each node in that cell independently re-codes the chunk with its own random vector and pushes a coded chunk down the column, and receivers verify and store. Sampling asks a cell for a symbol; honest nodes in that cell pull coded pieces from the column, decode, and return the symbol, with bootstrap nodes as fallback if the cell is bad.

Evaluation follows RDA's published setup: 4-second synchronous rounds, a 10-year system lifetime, Δ_overlap = 6 hours and Δ_sync = 15 minutes, fragment size k = 16 yielding 128B pieces, 512KB chunks, and 32KB coded chunks, with a 12KB KZG overhead per chunk (256 coded pieces × 48B). The adversarial regime fixes ε = 10% bad cells per row with an overall failure probability of at most 10⁻⁹, and grid dimensions are chosen for each system to meet that bound. Both systems are simulated under the same anonymous join-leave churn model.

## Why This Matters

**Impact on research.** The paper argues that DAS research has been dominated by cryptography while the network layer — dissemination delay, retrieval latency, and adversarial routing — determines finality and availability guarantees in practice. CDA shows that a coding layer inserted between the cryptographic commitment layer and the P2P topology can change the cost profile substantially, and it provides a concrete construction in which a homomorphic commitment makes coded fragments verifiable without decoding. It also supplies a direct, same-model comparison against RDA, which is useful as a baseline for future DAS work.

**Real-world applications:**

- Ethereum layer-2 rollups publishing blob data under EIP-4844, where the retention window is bounded but per-node storage and bandwidth costs are not.
- Modular blockchain data availability layers (in the lineage of Celestia) that need light clients to verify availability without downloading full blocks.
- Rollup fraud-proof and validity-proof pipelines, which depend on data being verifiably retrievable within strict time limits.
- Node onboarding and recovery under churn, where the synchronization cost of a joining node directly affects how quickly it can serve sampling requests.

**Industry relevance.** PeerDAS has already been integrated into Ethereum's Fusaka upgrade (December 2025 per the paper), and RDA is the Ethereum Foundation's newest DAS direction, so a design that keeps RDA's provable Byzantine security while cutting replication by roughly 5× and propagation by roughly 2× addresses costs that operators and builders pay directly. CDA is presented as compatible with existing builder-proposer workflows and erasure-coded blob structures, and it is positioned as blockchain-agnostic rather than tuned to Ethereum's specific architecture.

## Future Directions

- **Quantifying the sampling-latency tradeoff.** CDA downloads multiple small coded pieces from multiple sources rather than one full symbol from one source; the paper explicitly leaves evaluation of how this affects sampling latency — and whether the effect is negligible on a real blockchain network — to future work.
- **Real-network experimentation.** The current study uses simulation and benchmarks; testing on a deployed network would show whether the modeled latency-free churn assumptions hold.
- **Field-size and coding-parameter tuning.** The choice of k, the finite field, and the k₁ × k₂ grid dimensions jointly determine storage, overhead, and security; the paper reports commitments for k ∈ {8, 16, 32} but does not explore the full tradeoff space.
- **Extending beyond the homogeneous-churn model.** The simulation uses anonymous nodes with an exogenous churn schedule and no timing delays or network overlap; behavior under correlated failures, targeted attacks, or Sybil-heavy joins is not modeled.

## Target Audience

Researchers and protocol engineers working on blockchain data availability, Ethereum consensus and blob-layer design, and erasure-coding or network-coding systems; graduate students in distributed systems or applied cryptography who want a worked example of combining RLNC with homomorphic polynomial commitments; and practitioners evaluating storage and bandwidth costs of DAS deployments who want a rigorous comparison against the RDA baseline. Readers without background in KZG commitments and finite-field coding will find the middle sections demanding.

## Authors’ abstract

Data availability is a fundamental bottleneck in modern blockchain networks. Most blockchain systems rely on a full-replication model, which requires downloading of a full block to verify its availability. This model does not scale with block size because every node must handle large volumes of data, leading to slower block propagation, duplicated data transfer, and longer consensus agreement. This issue is well-known in Ethereum, where layer-2 rollups publish data directly…

[The full abstract on arXiv](https://arxiv.org/abs/2606.16200)

[Read the original paper](https://arxiv.org/abs/2606.16200)

---

Canonical: https://crypto.world/paper/efficient-data-availability-sampling-via-coded-distributed-arrays-2606.16200
