arXiv:2606.16200v1 [cs.DC] 15 Jun 2026
Efficient Data Availability Sampling via Coded Distributed Arrays Dang Pham Minh*
Hung Vuong Huu*
Duc A. Tran
Independent Researcher Hanoi, Vietnam
Independent Researcher Hanoi, Vietnam
University of Massachusetts Boston, USA
of Data Availability Sampling (DAS). DAS allows nodes to keep only small fragments of blob data such that availability can be verified probabilistically by sampling random positions and cross checking them with peers. Specifically, to publish a blob, the block proposer (or an external builder acting on its behalf) erasure encodes the blob data and disseminates the resulting fragments to the network. A verifier node only needs to successfully retrieve sufficient fragments in order to conclude that the entire blob is reconstructible. To realize DAS effectively, challenges are due to not only cryptographic guarantees but also how to make block production and data propagation fast and efficient. Delays in fragment dissemination result in longer confirmation finality and weaker availability guarantees. If availability is not established within time limits, rollup systems cannot reliably validate state transitions and generate fraud proofs. Today’s limitations. Existing DAS developments on the cryptographic layer are usually built upon erasure codes, polynomial commitments, and sampling guarantees [2]–[6]. They operate under abstract models assuming that sampling queries are resolvable without considering factors in dissemination delay, retrieval latency, and network dynamics. To improve block production latency, one way is to reconstruct the block building workflow [7] via centralized or semi-centralized builders. This approach does not consider the network-layer aspects of P2P dissemination or sampling protocols. Most recently, in 2025, a Byzantine-tolerant and samplingefficient P2P layer for DAS based on the concept of robust distributed arrays (RDA) was introduced by Ethereum Foundation (Feist et al. [8]). The idea is 1) to organize the nodes as a grid, 2) divide the data block into chunks, each mapped to a grid column, and 3) replicate each chunk in all nodes in the assigned column. RDA offers excellent sampling efficiency and provable Byzantine security. However, the full-column replication requirement is too strong, incurring excessive storage and communication costs. Contributions. Our main problem is to design a DAS solution that jointly optimizes storage efficiency, communication overhead, Byzantine robustness, and end-to-end DAS correctness. This is a gap in the literature. We propose a solution called CDA (shorthand for Coded Distributed Array), which also organizes nodes into a P2P grid as RDA but differentiates in how a block is coded, published, and verified. CDA is scalable, provably secure, and compatible with existing
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 into the chain. To overcome, Ethereum adopts Data Availability Sampling (DAS) to let nodes keep only a small fragment of the data while still ensuring availability. Prior work on DAS has focused on cryptographic foundations. Meanwhile, the peer-to-peer network layer that provides Byzantine-tolerant and scalable mechanisms for discovery and routing of DAS fragments is underexplored. We propose CDA, a new design for DAS based on coded distributed arrays that leverages network coding to ensure both robustness and efficiency. Our evaluation study compares CDA to RDA, the latest DAS development of Ethereum, showing an improvement of several times better. Index Terms—Blockchain, Data Availability Sampling, Network Coding, Peer-to-Peer Networks.
I. I NTRODUCTION Blockchain networks face the trilemma of scalability, security, and decentralization. In Ethereum, scalability is primarily pursued through Layer-2 (L2) rollup systems. In a typical rollup design, a sequencer aggregates off-chain transactions, computes the updated rollup state, and publishes the data required for state verification to the base chain. This data is only needed for a limited time window, during which nodes can verify state transitions and generate validity proofs. Yet this data is stored permanently as part of block data, imposing long-term storage and processing overhead on full nodes despite ephemeral relevance. EIP-4844 [1] introduces a solution for this by defining blobs. Large data objects are processed exclusively by the Consensus Layer, which handles block propagation and consensus, rather than the Execution Layer. Blobs exist only for a bounded retention window sufficiently long for L2 verification; after that they may be discarded. The objective is to increase the number of blobs that can fit into each block, enabling higher L2 throughput. However, if every node in the network were required to store all blobs in full, increasing blob count would quickly become infeasible. As full data replication cannot scale, Ethereum recently (and other blockchain networks follow similarly) adopts the method * Both authors contributed equally to this work.
1
builder-proposer workflows and erasure-coded blob structures. Specifically, we make the following contributions: • Rather than fully replicate an entire chunk across a column, we encode the data using Random Linear Network Coding (RLNC) [9] such that only coded-pieces of the chunk are disseminated to the column. This results in multi-time improvements in both storage and dissemination overheads. • The way that a chunk is encoded using RLNC needs a new commitment scheme. We propose one based on KZG offering small commitment size and efficient verification of data validity. Combining this with a robust structure for the P2P network layer, our DAS system is provably secure against Byzantine attacks. • An evaluation study is conducted through realistic benchmarks and simulations. Numerical results confirms our theoretical properties and demonstrate CDA’s multi-time superiority to RDA. For example, CDA is more than 5× better in storage, 2× in dissemination cost, and 1.4× in data-synchronization cost when new nodes join. The remainder of this paper is organized as follows. Section II reviews related work. Section III introduces essential background on DAS and RLNC necessary for our research development. Section IV presents the details of CDA. Numerical results of evaluation is discussed in Section V. The paper is concluded in Section VI.
Subsequently, the Ethereum ecosystem has explored alternative DAS designs that avoid centralized reliance on the super nodes. One such proposal is PeerDAS [4], which has been integrated into the Fusaka [16] integration in December 2025. PeerDAS relies on DHT-based retrieval and gossipbased dissemination, assigning columns of the erasure-coded data matrix to dedicated GossipSub [17] channels. Both mechanisms rely on multi-hop communication, hence incurring high latency for sampling requests and data propagation. This is worsened by the presence of Byzantine participants, leading to failure of availability verification. PANDAS [18] was proposed to address this multi-hop inefficiency of PeerDAS. In PANDAS, the responsibility of block dissemination is delegated to block builders (not block proposers) and instead of gossips, the dissemination is direct from a block builder and the receiving peers based on a deterministic data-to-peer assignments. PANDAS is tailormade for Ethereum with its specific architectural assumptions and not generalizable to other systems. In contrast, our DAS design aims to work universally as a data availability layer. RDA [8] is the latest development by the Ethereum Foundation as a response to the limitations of multi-hop dissemination (gossip and DHT) in adversarial settings. RDA can work for any blockchain network. To avoid multi-hop routing, RDA organizes the nodes into a grid P2P network where a node knows every other in the same row or column. Then RDA divides the data block into equally-sized chunks of symbols, assigning each chunk to a column of nodes, all of which will fully store this chunk. The sampling of an arbitrary symbol is simple: find the destination column of the containing chunk and query every node in this column. It is assumed that each column contains at least an honest node, and so this node will return the symbol. RDA is provably secure against all Byzantine attacks. However, RDA incurs substantial data duplication due to full-column replication. Because a chunk has to be broadcast to all column-wise nodes, the communication cost is also expensive. To compare, our aim is for a solution that is as provably secure as RDA but more scalable with better efficiency in both storage and communication.
II. R ELATED W ORK Distributed Hash Tables (DHT), via methods such as Kademlia [10] and Chord [11], are often discussed as a plausible substrate for DAS thanks to their distributed-indexing efficiency. For example, Cortés-Goicoechea et al. [12] studied the feasibility of integrating a Kademlia DHT into Ethereum’s DAS. Their results indicate that while DHT can support data sampling, disseminating large data structures incurs substantial latency. Also, DHT assumes honest participation; making it robust against adversaries, including data fabrication and Sybil attacks, remains a difficult challenge due to multi-hop routing and neighborhood structure. Efforts such as Honeybee [13] aim to mitigate these issues, but still relying on honestmajority assumptions. In contrast, we seek a design that can work with any small honesty fraction (provided a minimal number of honest nodes are active). For blockchain networks, the idea of verifying transaction data’s availability through sampling of erasure-coded data was first introduced by Al-Bassam et al. [14] and later adopted by LazyLedger and evolved into Celestia [15]. Celestia is a data availability layer to enable modular blockchain networks, ensuring that data published to the chain remains available and cannot be withheld by any validator. Celestia allows validators to collectively guarantee data availability without requiring every validator to download the full block data. Celestia has two types of nodes, super and light. The set of super nodes serves as a centralized servicer for storing and retrieving complete blob data. Light clients verify data availability by issuing sampling queries to these super nodes.
III. P RELIMINARIES We present some background about DAS, cryptographic commitment, and random linear network coding (RLNC) which are needed for presenting our proposed solution later. Notation. A raw data block is a sequence of symbols, m = (m1 , . . . , mK ) ∈ ΓK , from some alphabet Γ. An 1D erasure code is a function, C : ΓK → ΛN , that encodes a block m into an extended sequence m̂ = (m̂1 , . . . , m̂N ) ∈ ΛN from some alphabet Λ, such that any t (reconstruction threshold) correct positions of m̂ suffice to reconstruct the original block. For verification purposes, each symbol m̂i at position i ∈ [N ] has a corresponding opening τi ∈ Ξ which is generated to certify that the symbol m̂i is consistent with a public commitment. The codeword exposed to verifiers is π = (m̂1 , τ1 ), . . . , (m̂N , τN ) ∈ (Λ × Ξ)N .
2
A. Data Availability Sampling (DAS) 1) Erasure Code Commitment (ECC): ECC is a core component of any DAS scheme. This enables a publisher to commit to erasure-coded data and later provide verifiable openings for individual positions. With this, every symbol of the encoded sequence can be checked for consistency with a single committed codeword; this is the cryptographic foundation for sampling-based verification [2]. Formally, for an erasure code C : ΓK → ΛN , an ECC scheme is a quadruple of algorithms, CC = (CC.Setup, CC.Com, CC.Open, CC.Ver). The setup algorithm generates public parameters, CC.Setup(1λ ) → ck. To commit to a message m ∈ ΓK , the committer executes (com, St) ← CC.Com(ck, m̂), producing a succinct commitment and internal state. For each position i ∈ [N ], an opening is computed by τi ← CC.Open(ck, St, i), allowing any verifier to check consistency with the committed codeword. Verification is deterministic, given by CC.Ver(ck, com, i, m̂i , τi ) → b ∈ {0, 1}. 2) Index Sampler: The index sampler specifies which positions of the encoded sequence to be queried by independent samplers for verification purposes, such that a sufficiently large and diverse set of fragments is collectively observed. Formally, an index sampler with quality function ν is a probabilistic algorithm, Sample(1Q , 1N ) → (ij )j∈[Q] , that outputs Q indices in [N ]. Its quality is characterized by the probability that ℓ independent samplers collectively observe at most ∆ distinct positions: Pr ∪r∈[ℓ] { ir,j | j ∈ [Q] } ≤ ∆ ≤ ν(∆, N, Q, ℓ),
Fig. 1: Tensor Codes: 2D Reed Solomon for data encoding. Sampling at the cell level. KZG commitment for each column.
covers at least t distinct positions with high probability. Soundness ensures that no adversary can produce accepting transcripts inconsistent with the committed data. Consistency guarantees that all accepting reconstructions yield the same message. To achieve these properties, the sampler must provide sufficient coverage and the commitment scheme must satisfy position binding and code binding. Since practical samplers with negligible coverage error exist [2], these two binding properties suffice for secure DAS. B. Tensor Codes for Secure DAS So far we have assumed an 1D erasure code. PeerDAS [4] is the first formally specified and deployed solution for secure DAS in blockchain networks following this approach. Tensor Codes [2] extends from PeerDAS by applying 2D Reed-Solomon erasure coding. Here, the original block and extended block are seen as K × K and N × N matrices of symbols, respectively. The sampling is at the cell level. Each cell corresponds to a single polynomial evaluation and admits a succinct KZG opening, allowing light clients to sample arbitrary cells. This finer granularity significantly improves sampling efficiency. A few dozen random cell samples per client already provide strong availability guarantees for practical blob sizes [7]. As illustrated in Figure 1, each encoded m̂i , a column in the 2D extended block, is interpolated into a polynomial and committed via a Zaverucha-Goldberg scheme (KZG) [19] commitment comi . Separate openings τi are computed for individual cell evaluations within the column. Given a randomly sampled cell (symbol) at any position and the commitment vector (com1 , com2 , . . . ), a light client can verify both its content and cell position using the corresponding opening and standard KZG verification. We leverage this Tensor Codes structure in our ECC scheme.
where each tuple (ir,j )j∈[Q] is sampled independently. The sampler therefore quantifies the risk that multiple participants fail to cover enough positions for reconstruction. 3) DAS Scheme: A DAS scheme combines an ECC scheme with an index sampler. The goal is to ensure that, from accepting sampling transcripts, the original message can be uniquely reconstructed. Let C : ΓK → ΛN be an erasure code with reconstruction threshold t and reconstruction algorithm Reconst. Let CC = (CC.Setup, CC.Com, CC.Open, CC.Ver) be an erasure code commitment scheme for C, and let Sample be an index sampler with quality function ν. The resulting DAS scheme is the tuple DAS[CC, Sample] = (Setup, Encode, V, Ext), defined as follows. λ • The setup algorithm runs ck ← CC.Setup(1 ); • The encoding algorithm computes m̂ := C(m), generates a commitment (com, St) ← CC.Com(ck, m̂), and for each i ∈ [N ] computes the opening τi := CC.Open(ck, St, i), producing π = ((m̂i , τi ))i∈[N ] ; Q N • A verifier samples indices (ij )j∈[Q] ← Sample(1 , 1 ), retrieves the corresponding pairs, and accepts if CC.Ver(ck, com, ij , m̂ij , τij ) = 1 for all j; • Given ℓ accepting transcripts, the extractor computes the union I of all queried indices; if |I| ≥ t, it reconstructs m = Reconst((m̂i )i∈I ), else outputs ⊥ (failure); 4) DAS Security: A DAS scheme is secure when it satisfies three properties. Completeness requires that honest sampling
C. Random Linear Network Coding (RLNC) RLNC is a coding technique based on the idea that we can recover the original data given a sufficient number of random linear combinations of its pieces. RLNC-based storage systems
3
exhibit strong robustness under node churn, since a newly joined node can generate valid coded fragments directly from existing ones without reconstructing the original data [20]. Encoding. Consider a data object consisting of L symbols over a finite field Fq . We decompose it into k equally-sized k×(L/k) pieces X = (x1 , . . . , xk )⊤ ∈ Fq . An encoded fragment, or encoded piece, is a random linear combination of these k Pk raw pieces, c = gX = i=1 gi xi , with coding vector g = (g1 , . . . , gk ) ∈ Fkq . The size of an encoded piece equals the raw-piece size (1/k of object size). Decoding. To represent m coded pieces, we write C = GX, with coding matrix G ∈ Fm×k . Given C, we can reconstruct q X = G−1 C if rank(G) = k. This happens almost surely with sufficiently large k and m if the coding vectors are independently generated at random. Re-coding. New coded pieces can be produced from existing ones without decoding. This is useful for message forwarding in a network. Suppose that a node receivesPa coded piece k (c, g), it can generate a new coded piece c′ = i=1 αi gi xi = g′ X with corresponding coding vector g′ = (α1 g1 , . . . αk gk ) using any random vector (α1 , α2 , . . . , αk ) ∈ Fkq . This property allows new coded pieces to be generated, replaced, or propagated using only locally available pieces. RLNC will be used in the storage and retrieval tasks of our DAS system.
Fig. 2: RLNC encoding at the cell level of a data block. cell is the RLNC piece of the symbol at the original cell. Our key novelty is the additional RLNC layer at the cell level. In CDA, each raw block m has one extended block m̂ and many coded versions, m̂′1 , m̂′2 , . . . , generated using different random coding vectors. The availability of m is determined by successful sampling of random symbols in m̂. Recovering such a symbol requires sampling enough RLNC pieces from m̂′1 , m̂′2 , . . . . Since each RLNC piece is only 1/k the size of a raw symbol, CDA reduces the sampling size by a factor of k compared to conventional methods.
IV. CDA: O UR DAS S OLUTION
B. Commitment Scheme Since RLNC pieces are linear combinations of raw pieces, the ECC scheme must be additively homomorphic over Fq :
We propose a new DAS design called Coded Distributed Array (CDA). This name comes from observing that DAS resembles a robust distributed array problem. The data block to distribute is a 2D array and quick sampling of arbitrary cells is needed for availability verification. We present the details of CDA below in terms of three key components: 1) Data encoding: how an original block is encoded and broken into encoded pieces such that the block can be verified of availability by random sampling of these pieces; 2) Commitment generation: how commitment proofs are generated such that a cell/symbol can be verified of its correctness in terms of both content and matrix position; and 3) Networking layer: how the nodes in the system maintain connectivity and communicate to serve the task of data storage and sampling for verification purposes.
CC.Com(a + b) = CC.Com(a) + CC.Com(b), CC.Com(αa) = α · CC.Com(a), for all a, b, α ∈ Fq . This lets us verify any RLNC piece directly from the same linear combination of committed coded pieces, without reconstructing the underlying symbol. We use KZG, which is additively homomorphic and supports position-wise openings. Symbol verifiability. Verification of a symbol requires a block commitment key ck, a commitment to the symbol cell, and an opening that proves the value at the queried position. Consider a symbol at matrix position [r, c]. Its value in the extended block is X = m̂[r, c] = (x1 , . . . , xk ) (a partitioned vector of k pieces). The corresponding value in a coded ′ ′ block m̂ Pk(with coding vector g) is coded piece m̂ [r, c] = gX = i=1 gi xi . Let each piece xi have its own commitment comi = CC.Com(xi ), opening τi = CC.Open(xi ). KZG is additively homomorphic and so
A. Data Encoding The process of encoding a block is illustrated in Figure 2. Consider a data block m (a matrix of K × K symbols). To produce an encoded version of this block, there are three steps. First, 2D Reed-Solomon erasure coding is applied resulting in an extended block m̂ (a matrix N × N of symbols). Second, each symbol at cell [r, c] is horizontally divided into k equallysized pieces:
CC.Com(
k X
gi xi ) =
i=1
| m̂[r, c] = (m̂[r, c, 1], m̂[r, c, 2], . . . , m̂[r, c, k]).
{z
k X
gi CC.Com(xi ) =
i=1
k X
gi comi
i=1
}
com∗
k k k X X X CC.Open( gi xi ) = gi CC.Open(xi ) = gi τi .
Third, a RLNC piece is generatedP using some random coding k vector g, m̂′ [r, c] = g · m̂[r, c] = i=1 gi m̂[r, c, i]. Hence we obtain a coded block m̂′ that is a N × N matrix where each
i=1
|
4
{z τ∗
i=1
}
i=1
Fig. 3: KZG commitment computation per coded column. These algebraic operations preserve binding under the underlying t-Strong Diffie-Hellman assumption [21]. Consequently, a verifier can check the RLNC piece (g, D[r, c], τ ∗ ) directly against com∗ using the standard commitment verification algorithm, without reconstructing the original symbol. Because KZG is linear and position-wise verifiable, these derived commitments and openings preserve both properties of code binding and position binding as an ECC scheme. The security of CDA thus follows. Commitment computation. We now list the steps to compute the necessary commitments given a data block; see illustration in Figure 3. 1) Extended block m̂: because each symbol is horizontally divided into k pieces, we can think of m̂ as a piecematrix m̂k of size N k × N where each cell is piece. Each column in m̂ is a k-supercolumn in matrix m̂k (spanning k piece-columns). 2) Piece matrix m̂k : apply Tensor Codes to compute a KZG commitment for each column. Totally, there are N k percolumn commitments. 3) Coded block m̂′ with coding vector g: each column i has KZG commitment comi that is the linear combination of the commitments of the piece-columns i, i + 1, ..., i + k − 1, using the same coding vector g as coefficients. A block’s publication contains the block commitment ck and N KZG commitments com1 , . . . , comN . Given this information, a coded piece under sampling can be verified to be valid.
Fig. 4: CDA: Assignment of chunks to network columns.
Fig. 5: STORE mechanism of each chunk m̂c : step 1) publisher node broadcasts m̂c to peers in destination cell [r, c] (node 1, ...); step 2) Each node in this cell (node 1, ...) generates a random RLNC version, m̂′c , to send to each peer in column c (node 2, 3, ...).
its peer list by contacting bootstrap nodes. Nodes can behave Byzantine, but there requires at least one honest node in every column; this is achieved when sufficient Ω(k1 k2 ) good nodes join the network. When a new node joins and gets its peer list, it obtains historical data from the peers. This synchronization phase lasts for a bounded period ∆sync , after which the new node is considered fully joined at the network layer. 2) STORE Mechanism: The idea is to divide the data block into k2 chunks and distribute each to a corresponding network column (called the custody column, Figure 4). Consider an original block m with its extended m̂. RLNC is applied independently to the cells of m̂, resulting in a coded block m̂′ . Note that this is a N × N matrix where each cell has size of a piece. The dissemination is as follows; see Figure 5:
C. Network Layer We have established CDA’s security properties and now consider the network layer. As discussed in Section II, DHT/Skiplist approaches cannot guarantee availability under malicious participants, while unstructured gossip topologies incur high dissemination and retrieval latency. RDA [8] balances these extremes with a grid topology, which CDA also adopts. 1) P2P Topology: Define a grid of size k1 × k2 ; see Figure 4. Nodes are assigned to random cells, called custody cells. Each node maintains contact with peers that are all the nodes in the same row or column. The network requires a globallyknown set of bootstrap nodes such that each row has at least one bootstrap node. A new node joins the network and gets
5
The sampling success of CDA depends on the existence of sufficient RLNC pieces, which are of small size, collectively held by honest nodes in the destination column. In contrast, RDA, without RLNC coding, requires at least one big full chunk held by an honest node. Due to randomness nature of nodes joining the network, for RDA to get to the time when at least one honest node exists in each column, it is highly likely that a column also contains other honest nodes. Therefore, CDA takes advantage of this redundancy. V. E VALUATION We evaluated CDA by comparing directly to RDA, the latest DAS development from Ethereum Foundation. The benchmark setting and parameter value choices follow closely the experimental setup in its published paper [8]. Our evaluation source code is publicly available on Github: https://github. com/Coded-Distributed-Array/benchmarks
Fig. 6: GET mechanism for a symbol at data position [r1 , c1 ]: sufficient RLNC pieces can be found in honest nodes in custody column c. An honest node in custody cell [r, c] will retrieve and decode these pieces to reconstruct and send the symbol to the sampling node.
A. Evaluation Setup Time and churn parameters. Time is divided into synchronous rounds of 4 seconds. The system lifetime of 10 years. In other words, each honest must stay continuously online for ∆overlap = 6 hours, and it gives ∆sync = 15 minutes for a newly joined node to be synchronized into the network. Data parameters. A data block is of size B = 32MB. After 2D erasure coding, the extended block is a 256 × 256 matrix of size 4B = 128MB. Each cell is thus 2 KB, matching the size granularity used in PeerDAS [4]. The cryptographic proof overhead for each cell is 48 B. In the RLNC application in CDA, each cell is split with fragment size k = 16 and size of a piece 128 B. Each chunk of the extended block has size 512 KB. The size of a coded chunk is 32 KB. Our KZG commitment is based on the BLS12-381 curve, where a compressed G1 element occupies 48 bytes. A chunk contains 256 coded pieces, each accompanied by one KZG proof, hence incurring a total KZG overhead of 256 × 48 B = 12 KB. Security parameters. We consider an adversarial regime with ε = 10%, which bound the fraction of bad cells in each row. The overall failure probability over the entire system lifetime is at most 10−9 . For RDA, the network dimensions (k1 , k2 ) are selected to satisfy this security setting. Similarly, we can also compute the necessary k1 , k2 for our CDA. Evaluation Metrics. There are four metrics: 1) Commitment overhead: The total size of commitments and cryptographic proofs, normalized by the original block size; 2) Replication factor: The ratio of the total amount of data stored by all honest nodes to the original block size; 3) Propagation Cost: The total amount of data transmitted during the publication of a block in the average case; and 4) Synchronization cost: The amount of data a newly joining honest node must download to synchronize historical data from the custody column.
1) Publisher node P , say on row r: partition extended block m̂ horizontally into k2 chunks, m̂ = (m̂1 , m̂2 , . . . , m̂k2 ). Then broadcast each chunk m̂c to all nodes in cell [r, c]. 2) Each node Q in cell [r, c]: independently apply RLNC on m̂c to produce a coded chunk m̂′c to send to each peer R in column c. Different coding vectors are used for different nodes. Node Q also generates a coded chunk for itself to save locally. 3) Each node R in column c: verify the received coded chunk and save it if valid. Duplicate chunks (having the same data-matrix position) are ignored. The verification is done per piece in the chunk, following the commitment flow described in Section IV-B. As a result, for each original chunk m̂c , different RLNC versions, m̂′c , are stored at nodes in destination column c. Each node holds a version with size only 1/k of m̂c . Hence, the storage overhead per node in CDA is k times less than RDA. 3) GET Mechanism: To verify availability of a raw block m, random symbols of its extended block m̂ will be sampled. Consider a symbol at position [r1 , c1 ] of the N × N matrix of m̂. This symbol is inside chunk m̂c where c = ⌊c1 /k2 ⌋. We thus need to get a sufficient number of RLNC pieces for the symbol from the nodes in custody column c. A sampling node P (on row r) processes as follows: 1) Node P broadcasts the request to its peers in cell [r, c]. 2) Each node Q in cell [r, c]: a) Request each peer R in column c for a RLNC piece (corresponding to the requested symbol). b) Decode the symbol from sufficient RLNC pieces. c) Return the symbol to sampling node P . It is possible that the destination cell [r, c] is bad without any honest node. In this case, the sampling node P will retry via bootstrap nodes to request RLNC pieces directly from nodes in column c. This fallback method resorting to bootstrap nodes is also employed in RDA [8].
B. Security Requirement on Honest Nodes Since CDA and RDA share the same network layer and join-leave dynamics, we simulate both systems using exactly
6
(a)
(b)
(a) M = 5000
Fig. 7: Commitment size and honest-node requirements across configurations.
(b) M = 10000
Fig. 8: Replication factor: CDA vs. RDA.
the largest feasible value of k2 to minimize replication. Under this choice, CDA achieves a replication factor approximately 5.5× smaller than that of RDA. The same trend persists for larger network sizes, as shown in Fig. 8b. When the network size increases to M = 10,000 nodes, CDA continues to maintain a strictly lower replication factor than RDA, with the reduction factor approximately 5.7×.
the same model to ensure direct comparability. As in the RDA simulation model, the network is a dynamic system of anonymous nodes that join and leave the system according to an exogenously defined churn schedule, without modeling timing delays or network overlap. The schedule begins with a small initial set of active nodes, after which new nodes join one-by-one during a warm-up phase until the target population is reached. Once the system stabilizes, churn proceeds in steady state: in every round, a fixed number of nodes leave in FIFO order and the same number of new nodes join, so that all nodes remain active for an equal number of rounds. Figure 7a presents the join-leave simulation where 50 nodes join and 50 nodes leave at every step, for a total of 50,000 time steps. This setting is 10× larger than the RDA benchmark and is intended to stress-test the system and reveal any potential worst-case behavior. The results show that each column consistently contains significantly more than one honest node; at least 12 honest nodes per column in both CDA and RDA. This behavior is stable across the entire simulation horizon. This substantiates the optimistic approach of CDA that there should be multiple honest nodes in a column (the expected case), versus the pessimistic approach of RDA that takes advantage of only one honest node (the worst-case).
E. Propagation Cost
(a) M = 5000
(b) M = 10000
Fig. 9: Propagation cost: CDA vs. RDA. As shown in Fig. 9a, when the network has M = 5000 nodes, CDA achieves a propagation cost ranging from 2.07 × 1013 byte (19, 286 GiB) down to 4.30 × 1010 byte (40.05 GiB), whereas RDA ranges from 228, 200 GiB down to 79.4 GiB. At the optimal operating point, corresponding to the minimum propagation cost, CDA reduces the propagation cost by approximately 2× compared to RDA. For larger networks, Figure 9b shows that when M = 10,000, the minimum propagation cost of CDA is 24 GiB, while RDA reaches 55.1 GiB, yielding a reduction factor of about 2.3×. These results demonstrate that CDA consistently incurs a lower propagation cost than RDA under identical security constraints. This is particularly important for DAS, where block broadcast efficiency directly affects network load and scalability.
C. Commitment Overhead Figure 7b illustrates the ratio between commitment size and block size for different fragment sizes (k). The setting fragment size k = 1 corresponds to RDA, where each cell carries a single commitment, while larger fragment sizes in CDA introduce multiple commitments per cell. Nevertheless, even for k ∈ {8, 16, 32}, the commitment overhead is negligible and decreases rapidly with increasing block dimension, indicating that CDA’s additional commitments incur no practical cost relative to the encoded data. D. Replication Factor Figure 8a shows the replication factor under the security constraint M = 5,000 nodes. For CDA, the feasible column dimension ranges from k2 = 1 to k2 = 25, corresponding to a replication factor decreasing from 156.25 to 6.25. In contrast, the feasible range of k2 in RDA is from 1 to 72, hence replication factor in the range from 2,500 to approximately 34.7, a much higher range. In practice, we will want to select
F. Synchronization Cost As shown in Fig. 10a, when the network size is M = 5,000, CDA achieves a historical synchronization cost ranging from 1.13 × 108 byte down to 1.80 × 105 byte, whereas RDA ranges from 1.34 × 109 byte down to 2.59 × 105 byte. At the optimal operating point, corresponding to the minimum
7
(a) M = 5000
[5] A. Evans, N. Mohnblatt, and G. Angeris, “ZODA: Zero-overhead data availability,” Cryptology ePrint Archive, Paper 2025/034, 2025. [Online]. Available: https://eprint.iacr.org/2025/034 [6] A. Evans and G. Angeris, “The accidental computer: Polynomial commitments from data availability,” Cryptology ePrint Archive, Paper 2025/918, 2025. [Online]. Available: https://eprint.iacr.org/2025/918 [7] M. Pigaglio, O. Ascigil, M. Król, F. Lange, K. Peeroo, S. Rene, R. Sadre, V. Stankovic, and E. Rivière, “PANDAS: Peer-to-peer, adaptive networking allowing data availability sampling within ethereum consensus timebounds,” in Proceedings of the 26th International Middleware Conference, ser. Middleware ’25. New York, NY, USA: Association for Computing Machinery, 2025, p. 167–179. [Online]. Available: https://doi.org/10.1145/3721462.3770769 [8] D. Feist, A. Dietrichs, and A. Manning, “Robust distributed arrays,” arXiv preprint arXiv:2504.13757, 2023. [Online]. Available: https://arxiv.org/abs/2504.13757 [9] T. Ho, M. Medard, R. Koetter, D. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413– 4430, 2006. [10] P. Maymounkov and D. Mazières, “Kademlia: A peer-to-peer information system based on the XOR metric,” in Revised Papers from the First International Workshop on Peer-to-Peer Systems, ser. IPTPS ’01. Berlin, Heidelberg: Springer-Verlag, 2002, p. 53–65. [11] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for internet applications,” SIGCOMM Comput. Commun. Rev., vol. 31, no. 4, p. 149–160, Aug. 2001. [Online]. Available: https://doi.org/10.1145/964723.383071 [12] M. Cortes-Goicoechea, C. Kiraly, D. Ryajov, J. L. MuNoz-Tapia, and L. Bautista-Gomez, “Scalability limitations of kademlia dhts when enabling data availability sampling in ethereum,” in Proceedings of the 2024 6th Blockchain and Internet of Things Conference, ser. BIOTC ’24. New York, NY, USA: Association for Computing Machinery, 2024, p. 83–91. [Online]. Available: https://doi.org/10.1145/3688225.3688236 [13] Y. Zhang and S. Bojja Venkatakrishnan, “Honeybee: Byzantine tolerant decentralized peer sampling with verifiable random walks,” in Proceedings of the Twenty-Sixth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, ser. MobiHoc ’25. New York, NY, USA: Association for Computing Machinery, 2025, p. 321–330. [Online]. Available: https://doi.org/10.1145/3704413.3764424 [14] M. Al-Bassam, A. Sonnino, V. Buterin, and I. Khoffi, “Fraud and data availability proofs: Detecting invalid blocks in light clients,” in Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part II. Berlin, Heidelberg: Springer-Verlag, 2021, p. 279–298. [Online]. Available: https://doi.org/10.1007/978-3-662-64331-0 15 [15] M. Al-Bassam, “LazyLedger: A distributed data availability ledger with client-side smart contracts,” arXiv preprint arXiv:1905.09274, 2019. [Online]. Available: https://arxiv.org/abs/1905.09274 [16] Ethereum Foundation, “Ethereum upgrade on Fusaka version,” ethereum.org, 2025. [Online]. Available: https://ethereum.org/roadmap/ fusaka/ [17] D. Vyzovitis, Y. Napora, D. McCormick, D. Dias, and Y. Psaras, “Gossipsub: Attack-resilient message propagation in the Filecoin and ETH2.0 networks,” arXiv preprint arXiv:2007.02754, 2020. [Online]. Available: https://arxiv.org/abs/2007.02754 [18] Ethereum Foundation, “Proposer-builder separation (PBS) – Ethereum roadmap,” Ethereum.org, 2024. [Online]. Available: https://ethereum. org/roadmap/pbs/ [19] A. Kate, G. M. Zaverucha, and I. Goldberg, “Constant-size commitments to polynomials and their applications,” in Advances in Cryptology ASIACRYPT 2010, M. Abe, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 177–194. [20] F. H. Fitzek, T. Toth, A. Szabados, M. V. Pedersen, D. E. Lucani, M. Sipos, H. Charaf, and M. Medard, “Implementation and performance evaluation of distributed cloud storage solutions using random linear network coding,” in 2014 IEEE International Conference on Communications Workshops (ICC), 2014, pp. 249–254. [21] D. Boneh and X. Boyen, “Short signatures without random oracles,” Cryptology ePrint Archive, Paper 2004/171, 2004. [Online]. Available: https://eprint.iacr.org/2004/171
(b) M = 10000
Fig. 10: Synchronization cost: CDA vs. RDA.
synchronization cost, CDA reduces the historical synchronization cost by about 1.44× compared to RDA. A similar trend is observed for larger networks. When the network grows to M = 10,000 nodes (Fig. 10b), CDA continues to outperform RDA, achieving a minimum historical synchronization cost that is about 1.5× lower. These results indicate that CDA consistently enables faster synchronization of historical state under churn. Lower synchronization cost directly improves join–leave robustness, allowing new nodes to fetch historical data more efficiently and reducing recovery latency in practice. VI. C ONCLUSION We have proposed CDA, a novel design for DAS by jointly addressing coding, verification, and P2P networking. By applying random linear network coding during data dissemination, CDA increases the efficiency of storage and dissemination. The homomorphic structure of polynomial commitments enables direct verification of coded pieces without reconstructing original data. CDA is provably secure as long as a minimal number of honest nodes joins the network. Our evaluation study has shown CDA substantially outperform RDA, the latest DAS development, in storage (5× better), dissemination (2×), and synchronization costs (1.4×) without weakening availability. A potential limitation of CDA is in the amount of coded pieces downloaded for symbol reconstruction. This is an inevitable tradeoff because instead of replicating a full (big) chunk everywhere in the destination column, which results in only one download of the symbol from one source, CDA has to pull different pieces from different places. In the future work, we will evaluate how this tradeoff affects sampling latency and whether this effect can be negligible in experimental settings with a real blockchain network. R EFERENCES [1] Ethereum Foundation, “EIP-4844: Shard Blob Transactions (ProtoDanksharding),” Ethereum Improvement Proposal, 2024. [Online]. Available: https://eips.ethereum.org/EIPS/eip-4844 [2] M. Hall-Andersen, M. Simkin, and B. Wagner, “Foundations of data availability sampling,” Cryptology ePrint Archive, Paper 2023/1079, 2023. [Online]. Available: https://eprint.iacr.org/2023/1079 [3] ——, “FRIDA: Data availability sampling from FRI,” Cryptology ePrint Archive, Paper 2024/248, 2024. [Online]. Available: https: //eprint.iacr.org/2024/248 [4] B. Wagner and A. Zapico, “A documentation of ethereum’s PeerDAS,” Cryptology ePrint Archive, Paper 2024/1362, 2024. [Online]. Available: https://eprint.iacr.org/2024/1362
8