Skip to content
Crypto.world

Research

TCDA: Tunable Coded Distributed Arrays for Data Availability Sampling

Settles when a coded data-availability layer stays robust against an unbounded Byzantine adversary, making PUT load tunable rather than forcing full replication before attestation deadlines.

TCDA: Tunable Coded Distributed Arrays for Data Availability Sampling
arXiv
2610.22508
Published
2026-10-15
Authors
Duc A. Tran, Dung Truong, Duy Le

AI summary

Overview

  • Research area: Blockchain data availability sampling (DAS), peer-to-peer storage and dissemination networks, network coding (random linear network coding over a grid), and Byzantine fault tolerance.
  • Technical level: Advanced. The paper combines a protocol design with probabilistic robustness analysis, Reed–Solomon tensor codes, and KZG commitment algebra.
  • Scope: The paper proposes TCDA, a coded networking layer for DAS whose per-node retention depth can be tuned so that block dissemination meets Ethereum's attestation deadline and storage budgets while remaining provably robust against any number of Byzantine peers.

What This Paper Is About

Data availability sampling lets blockchain nodes check that a block's data is really available by downloading only a few random symbols, but the underlying network must still spread each block before validators attest, store each node's share for the retention window, and answer sampling queries quickly. The only existing design with a proof against an unbounded Byzantine adversary, Robust Distributed Arrays (RDA), achieves this by full replication, which makes the dissemination load on the critical path to finality grow with the network and become untunable. The paper asks when a coded array remains robust, what it costs, and what it gains, and answers with TCDA, whose single knob (the retention depth Q, the number of coded pieces each node keeps out of κ) trades PUT and storage cost against GET cost.

Key Contributions

  1. First provably robust coded DAS layer. TCDA keeps RDA's K₁×K₂ grid but drops RDA's per-column assumption that every column contains at least one good node. Its robustness is conditioned only on the total number N⁺ of good nodes in the network, wherever they lie; a column may contain no good node at all. The authors note the design is non-trivial: with naive coding, one Byzantine relay could make every good node keep the same useless pieces.
  2. Exact robustness condition (Q1). They derive the exact probability that sampling a symbol fails, p_fail(N⁺, K₁, K₂, Q), and from it a necessary and sufficient condition for δ-robustness: N⁺ ≥ N⁺_δ(Q), a single number computed from δ and the code, together with closed-form upper bounds on N⁺_δ(Q).
  3. Tunability and cost model (Q2). PUT and storage fall to exactly Q/κ of RDA's, paid for at GET by roughly log₂((⌈κ/Q⌉−1)/η)+1 extra round-trips, where η is the fraction of good nodes. They also give an optimal design rule: with an attestation deadline and a storage budget, the optimal Q has a closed form on every grid (the largest one within the budgets), so joint design over (K₁, K₂) reduces to a finite scan over grids.
  4. Scalability argument and validation (Q3). Coding changes how the network responds to growth: a grid carries κ/Q times more nodes within the same PUT budget, and each bad node adds only Q/κ as much PUT load as in RDA. They evaluate at Ethereum's timing and bandwidth against RDA and PeerDAS with static and dynamic networks.

Main Findings

  • RDA misses the deadline at Ethereum scale. In the paper's example of a 12 s slot with attestation about 4 s in, an 18-day retention window (131,072 blocks), a 32 MiB extended object (8 MiB of blob data) on a 15×32 grid, and the smallest network satisfying RDA's robustness assumption (965 good nodes and as many Byzantine ones), each relay must forward about 60 MiB per object, i.e., 127 Mbit/s over 4 s, five times the 25 Mbit/s recommended for an attesting node.
  • RDA storage is expensive. The same example requires 128 GiB per node at any time, twice what PeerDAS stores per node.
  • Retrievability threshold. A chunk is retrievable if and only if its column holds at least h_Q = ⌈κ/Q⌉ good nodes; the "if" direction can fail only with probability at most a binomial term over (q−1), negligible for q ≈ 2^255. Every GET then completes within ⌈log₂(N_c − N⁺_c + h_Q)⌉ rounds of column queries.
  • Failure decomposes into access plus decoding. A GET fails if the publisher's or the client's contact cell has no good node (probability P₁, given by an inclusion–exclusion expression) or if the custody column holds fewer than h_Q good nodes (probability P₂, a sum of binomial and placement terms). Corollary 1 gives the exact total, p_fail, which increases in K₁ and decreases in Q.
  • Bootstrap condition. TCDA is δ-robust iff N⁺ ≥ N⁺_δ(Q) = min{N⁺ : p_fail(N⁺, K₁, K₂, Q) ≤ δ}; this threshold is non-increasing in Q and non-decreasing in K₁, and is upper-bounded by K₁K₂ ln(2/δ) when h_Q = 1, and by max{K₁K₂ ln(4/δ), K₂ x_Q} otherwise, where x_Q solves x − (h_Q−1) ln(ex/(h_Q−1)) = ln(2/δ).
  • Tuning is exact, not approximate. PUT and storage drop to exactly Q/κ of RDA's, and RDA is recovered as the special case Q = κ (where the column hop of GET is skipped). Raising or lowering Q later needs no republishing: nodes fetch the new slots or simply delete slots.
  • Bad nodes slow GET only logarithmically. The extra round-trips scale as about log₂((⌈κ/Q⌉−1)/η)+1 and add almost nothing to GET traffic.
  • Evaluation at 25 Mbit/s uplink, 32 MiB object. RDA misses the attestation deadline at every network size tested, whereas TCDA can be tuned to meet it from 868 good nodes up to the 40,000 tested, storing 1.7 to 32 times less per node than replication, at the price of 2.5 to 7.7 round-trips per sample instead of about one.
  • Adversarial and churn behaviour. TCDA stays robust under any number of Sybils, where PeerDAS in the paper's model does not; it maintains availability under steady churn and even after a sudden outage of up to 55% of the good nodes.
  • Sybil resistance comes from designated coefficients. Each node's coding coefficients are fixed in advance by a random oracle as H(com, c, u, s), so exactly one piece is acceptable per slot; a node keeps a received piece only if it matches the corresponding homomorphically computed KZG commitment, which blocks valid-but-useless pieces from degrading what good nodes hold.

Methodology in Plain English

The authors start from the observation that RDA's guarantee rests on a condition nobody can observe in an open network (a good node in every column) and that its full replication makes the dissemination load unadjustable. They keep RDA's grid topology — each node connects to every peer in its row and column — but change what a node stores: instead of a whole chunk, each column node keeps Q coded pieces, each a random linear combination of the chunk's κ layers, with coefficients derived from public commitments and the node's identity rather than chosen by the sender. Receivers check each piece against a commitment computed from public data, so a bad sender can only produce rejected pieces. A sampling client routes to the column owning the symbol, and a good node there acts as a collector that queries column peers in doubling rounds (1, 2, 4, …) until it has κ linearly independent pieces, then decodes and returns the symbol with an aggregated KZG proof. The authors then compute, under uniform node placement and a worst-case adversary, the exact probability that such a GET fails, invert it into the minimum number of good nodes needed for a given δ, and use the resulting cost formulas to select Q and the grid jointly under deadline and storage budgets. Finally they simulate at Ethereum's parameters, comparing against RDA and PeerDAS in static and dynamic networks.

Why This Matters

Impact on research. The paper closes a gap the authors identify across the field: designs that are provably robust fix the dissemination load at its maximum, and designs that bound the load give up the proof. TCDA is presented as the first coded DAS layer with a proof against an unbounded Byzantine adversary, and it shifts the robustness assumption from an unobservable per-column structural property to a single network-level count of good nodes that a deployment can check at bootstrap.

Real-world applications:

  • Ethereum rollup blobs. The evaluation is parameterized by EIP-4844 blob sizes (8 MiB of blob data, 32 MiB extended object), 12 s slots, and the 18-day / 131,072-block retention window, making the design directly comparable to the PeerDAS deployment introduced with the Fusaka upgrade.
  • Validator and attester participation. Because per-node storage and PUT load are the barriers to participation, a tunable Q/κ reduction decides which node classes can afford to serve a block within the attestation window.
  • Modular data availability layers. Designs such as Celestia's sampling of a 2D Reed–Solomon extension face the same networking black box; the coded-grid layer is a candidate substitute for gossip- or DHT-based dissemination.
  • Churn-tolerant storage networks. The JOIN protocol, where a new node counts toward a column's good nodes only after syncing its designated pieces for every object still in the retention window, is a concrete recipe for keeping availability under node turnover.

Industry relevance. The paper targets deployment-time constraints rather than asymptotic ones: a 25 Mbit/s recommended uplink, a 4 s attestation budget, and GiB-scale per-node storage. The reported ability to meet the deadline from 868 good nodes up to the 40,000 tested, and the claim that each bad node adds only Q/κ as much PUT load as in RDA, are arguments aimed at operators sizing a real network.

Future Directions

  • Making TCDA the default parameterization versus RDA. The paper treats RDA as TCDA at Q = κ; an open question is how deployments should set Q per data type as the good-node population changes, given the TUNE triggers listed (safety, deadline, margin, cost).
  • Grid and bootstrap provisioning. Every row requires a public bootstrap node, and the paper's feasibility analysis yields a range of good-node counts and a largest object size for which a feasible design exists; operating beyond those bounds, or with skewed rather than uniform node placement, is not resolved in the reported content.
  • Behaviour under more severe failures than tested. Availability is demonstrated under steady churn and a sudden outage of up to 55% of good nodes; whether the guarantees hold under larger correlated outages, and how JOIN syncing (which downloads one chunk's worth of data per object) behaves under mass rejoining, remain open.
  • Adversarial modelling of deployed systems. The paper shows PeerDAS does not stay robust under any number of Sybils in its model; reconciling that model with real gossip behaviour, and integrating the designated-coefficient and KZG-verification machinery with existing commitment pipelines, are natural next steps.

Target Audience

Researchers and protocol engineers working on blockchain data availability, erasure and network coding, and Byzantine-fault-tolerant peer-to-peer storage. It suits readers who already understand DAS sampling arguments and KZG commitments and want the networking layer's cost and robustness trade-off stated precisely; the exact failure-probability derivation and design rule also make it useful to engineers sizing validator bandwidth and storage budgets for an Ethereum-scale deployment.

Authors’ abstract

Data availability sampling (DAS) lets blockchain nodes verify a block's data availability by downloading only a few random pieces of it. Its network layer must disseminate each block in time for validators to attest (PUT), store it, and serve any piece on request (GET). A trustless DAS must sustain any number of Byzantine peers. The only known design with this guarantee, Robust Distributed Arrays (RDA), achieves it by full replication: each group of nodes responsible for…

The full abstract on arXiv
Read the original paper