TCDA: Tunable Coded Distributed Arrays for Data Availability Sampling

1

TCDA: Tunable Coded Distributed Arrays for Data Availability Sampling

arXiv:2610.22508v1 [cs.DC] 15 Oct 2026

Duc A. Tran, Dung Truong, and Duy Le

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 part of a block stores that part in full, so a single good node per group suffices. The price to pay is a PUT load on the critical path to finality that grows with the network and cannot be tuned, hence the data may not reach validators before the attestation deadline. Coding is the natural remedy, but it was not known when a coded layer remains robust against an unbounded adversary, what it costs, or what it gains. We propose TCDA, a coded layer that is provably robust given enough good nodes, wherever they lie, with a tunable knob: how much of its assigned data each node keeps. Turning the knob trades PUT and storage costs against GET cost. It can be set per data type and adjusted as the good-node population changes. At Ethereum’s parameters, our evaluation for a 32 MiB block at the recommended uplink shows that RDA misses the attestation deadline at any network size, 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. Index Terms—Data availability sampling, robust distributed arrays, network coding, Byzantine fault tolerance, peer-to-peer storage, blockchain scalability

I. I NTRODUCTION Rollup-centric blockchains publish large blobs whose only purpose is to be available for a bounded window. Data availability sampling (DAS) [1], [2] lets a node convince itself that a block is available by fetching a few random symbols of its erasure-coded extension, without downloading the block. Ethereum introduced blobs with EIP-4844 [3] and has sampled them with PeerDAS [4], [5] since its Fusaka upgrade [6]. The cryptographic layer of DAS (erasure codes, commitments, samplers) is well understood [2], [7], [8]. The networking layer is harder because it has to do three things while an unknown and possibly large set of peers is Byzantine. First, the PUT protocol must spread every block’s data across the network before validators attest; its bandwidth and latency sit on the critical path to finality. Second, storage must keep each node’s share for the whole retention window; this burden falls on every node for every block and decides who can afford to participate. Third, the GET protocol must let a sampling query reach the requested symbol in a few round-trips. A tradeoff is The authors are with the Department of Computer Science, University of Massachusetts, Boston, MA, USA. Email: duc.tran@umb.edu

inevitable: the redundancy that makes GET trivial is exactly what makes PUT and storage expensive. Robust Distributed Arrays (RDA). RDA [9] is the first provably secure networking layer for DAS, recently proposed by Ethereum Foundation. Nodes are hashed into a K1 × K2 grid and form a clique with every peer in their row and in their column. The extended block is cut into K2 chunks, each fully replicated at an assigned column. Availability is guaranteed provided that every column contains at least one good node. This assumption concerns the good nodes only, so RDA remains robust under any number of Byzantine ones. RDA offers trustless DAS, but it can fail deadline and storage constraints. Consider Ethereum scale: a 12 s slot in which validators attest about 4 s in [10] and an 18-day retention window (131,072 blocks) [3], and a 32 MiB extended object (8 MiB of blob data) on a 15 × 32 grid. First, the PUT misses the attestation deadline. On the smallest network satisfying RDA 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 [11]. Second, storage is expensive: each node needs 128 GiB at any time, twice the amount PeerDAS [4], the current DAS deployment on Ethereum, stores per node. Motivation. The example reflects a pain point of the whole field, not only of RDA. The PUT sits on the critical path to finality, yet no existing DAS design offers both a dissemination load that a deployment can size against its slot and provable robustness against any number of Byzantine peers. Today’s designs that are provably robust fix the load at its maximum and that bound the load give up the proof. Coding is the natural remedy. If each column node keeps coded pieces worth 1/κ of its chunk, the column dissemination and the per-node storage shrink κ-fold, as shown in our earlier work [12], which applies random linear network coding (RLNC) [13]. Coding, however, raises issues that replication never had: 1) The availability guarantee breaks: a good node in every column is no longer enough, since such a node does not hold the whole chunk, and so retrieval is not guaranteed; 2) A network may not meet the new robustness condition: a new condition is needed and a deployment must be able to tell from its design inputs whether it is met; 3) Byzantine nodes gain a new lever: they are unbounded in number and can supply valid but useless pieces, which may degrade what the good nodes keep; and 4) The savings are paid for elsewhere: as no single good node can answer a sampling query, each GET must combine pieces from several good nodes and costs more.

2

RDA

TCDA (κ=4, Q=2) 2 good nodes → rank 4 = κ

every node: whole chunk (κ of κ pieces)

every node: Q coded pieces (Q/κ of the chunk)

GET: one good contact

GET: ⌈κ/Q⌉−1 more good contacts

Fig. 1. RDA vs. TCDA on one column of five nodes, three good. RDA stores the whole chunk at every node, so one good node suffices for a GET. TCDA stores Q of κ coded pieces per node (colors: distinct coefficients), so a GET needs to contact multiple good nodes.

Problem. We address all of these issues and make coding provably robust against an unbounded adversary. We ask: without any good-node assumption, exactly when is a coded array robust, what does it cost, and what does it offer that replication cannot? We break this into three questions. Q1 Under exactly what condition is a coded array robust? The condition must be necessary and sufficient, hold under arbitrarily many bad nodes, and be stated only as the number of good nodes the network needs, wherever they lie. Unlike RDA’s per-column assumption, which no participant can observe, this number is a condition computed from the robustness requirement and the code. Q2 What does coding trade, and is it reasonable for blockchain DAS? The PUT must meet the attestation deadline in every slot and storage burdens every node, while the GET should be as fast as possible. We need to state this trade-off exactly, so that the code can be tuned to different DAS requirements. Q3 Does coding offer anything beyond lower costs? Lower costs are what coding is expected to deliver. Yet storing coded pieces instead of full copies also changes what each node contributes to the system. We ask whether this brings benefits that replication cannot provide by design, while never doing worse. Contributions. We answer these questions with TCDA (Tunable Coded Distributed Array). TCDA keeps RDA’s grid but not its per-column assumption, and changes the PUT and GET protocols. Instead of a full chunk, a column node stores only Q ≤ κ coded pieces. This Q, the retention depth, is the single knob tuning the PUT and storage costs against the GET cost. Fig. 1 contrasts TCDA with RDA. Our key contributions: Novelty: TCDA is the first provably robust coded DAS layer. Its robustness is conditioned only on the number N + of good nodes in the network, whereas RDA’s assumption is made for every column which is harder to enforce. The design is not trivial: with naive coding, one Byzantine relay can make every good node keep the same useless pieces, which is not to mention deadline and storage constraints. • Robustness (Q1): We derive the exact probability that sampling a symbol fails and, from it, the necessary and sufficient condition for a given δ-robustness: N + ≥ Nδ+ (Q), a •

single numbercomputed from δ and the code. We make no assumption where they lie; a column can have no good node. • Tunability (Q2): PUT and storage fall to exactly Q/κ of RDA’s. The price is paid at GET, which takes
a second hop into the column: about log2 (⌈κ/Q⌉−1)/η +1 extra roundtrips, where η is the fraction of good nodes. Bad nodes thus slow a GET only logarithmically and add almost nothing to its traffic. A deployment can tune Q to its deadline and sampling needs, per data type if needed, and is never worse off than with RDA, which is TCDA at Q = κ. • Optimal design (Q2): With the attestation deadline and a storage budget, we choose retention depth Q jointly with the grid (K1 , K2 ) for the fastest GET. On every grid the optimal Q has a closed form, the largest one within the budgets, and so the joint design reduces to a finite scan over grids, which is fast to find a solution. We also give the range of the number of good nodes and the largest object size for which a feasible design exists. • Scalability (Q3): Coding changes how the network responds to growth. In RDA, as every new node adds traffic to PUT load, a growing network will eventually miss the deadline. In TCDA, more good nodes allow a smaller retention depth Q, which absorbs the growth: a grid carries κ/Q times more nodes within the same PUT budget. Each bad node also adds only Q/κ as much PUT load as in RDA, and robustness holds however many of them join. • Validation: We evaluate TCDA at Ethereum’s timing and bandwidth with both static and dynamic networks, against the two most relevant baselines: RDA and PeerDAS [4], the current DAS deployed on Ethereum. At the recommended 25 Mbit/s uplink, for object size of 32 MiB, RDA misses the attestation deadline at every network size, while TCDA can be tuned to meet it from 868 good nodes up to the 40,000 we 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. TCDA stays robust under any number of Sybils, where PeerDAS, in our model, does not. TCDA maintains availability under steady churn, and even after a sudden outage of up to 55% of the good nodes. Section II reviews related work. Sections III and IV give the system model and the TCDA protocol. Sections V to VII analyze its robustness, formulate costs, and derive an optimal design. Section VIII reports evaluation results. Section IX discusses limitations and open problems of TCDA. Section X concludes the paper. II. R ELATED W ORK DAS and its cryptographic layer. Al-Bassam et al. [1] introduced availability checks by random sampling of a 2D Reed–Solomon extension, later deployed by Celestia [14]. Yu et al. [15] use LDPC codes in a coded Merkle tree to shorten the proofs of incorrect coding. Hall-Andersen, Simkin, and Wagner defined DAS as a cryptographic primitive and analyzed tensor-code constructions [2], [7]; ZODA [8] and [16] reduce the commitment overhead. These works decide what is committed and sampled, and treat the network as a black box that returns the symbol at a queried position [9]. We address

3

III. S YSTEM M ODEL The system model has four parts: the data and its coding, the network and its adversary, the robustness requirement, and the condition on the good nodes. A. Data and coding Object and tensor code. An object, e.g., a block, is a D×D matrix whose symbols each consist of κ elements of Fq , the

c=1

c=2

c=3

rows 1..K1

that black box: where the symbols are stored and how they are fetched. Networking for DAS. Król et al. [17] set out what DAS asks of a P2P network and why classical DHTs such as Kademlia [18] and Chord [19] do not deliver it as they are. A lookup takes several hops, storing the samples in a Kademlia DHT is too heavy for the slot [20], and the robust DHT variants need most nodes to be good [9]. PeerDAS [4], [5], deployed on Ethereum with Fusaka update [6], extends each blob in one dimension, spreads the resulting columns over GossipSub [21] topics, and has each node keep a few of them. PANDAS [22] targets Ethereum’s slot timing with builder-driven dissemination to deterministically assigned nodes. Honeybee [23] samples peers by verifiable random walks and tolerates a Byzantine majority, but it is a peersampling primitive, not a storage layer. These designs bound what a node forwards, yet none proves that sampling succeeds against an arbitrary number of Byzantine peers. In an open network identities are free [24], and Section VIII shows what this does to PeerDAS in our model. RDA [9] is the only design with such a proof. It is the latest development by the Ethereum Foundation as a response to the limitations of multi-hop dissemination (gossip and DHT) in adversarial settings. It, organized as a grid network, is fast for sampling and robust under any number of Byzantine peers provided that every column holds a good node. As pointed out in the previous section, RDA cannot scale as more nodes join and easily violate deadline constraints in today’s blockchains. Coded storage and dispersal. RLNC [13] recovers data from any κ independent coded pieces, and regenerating codes [25] apply network coding to storage, trading storage against repair bandwidth; neither considers Byzantine nodes. Verifiable information dispersal [26] stores an erasure-coded file on n servers, robustly but only up to an 1/3 Byzantine rate; in contrast, our Byzantine model assumes only a minimum number of honest nodes, allowing for any number of Byzantine ones. With Byzantine relays, coding also invites pollution, i.e., forged coded pieces. Homomorphic signatures [27] let a node verify a coded piece without decoding, and in DAS the KZG commitments [28] already serve this purpose. CDA [12], our earlier work, provides evidence that RLNC when applied to RDA’s grid with such a KZG-homomorphic verification layer can cut costs in PUT and storage. To the best of our knowledge, no prior work on coded DAS, including CDA, proves robustness to the unbounded Byzantine model. Our research is the first effort to achieve this, and, especially, we offer a provably robust coded DAS design that can be tuned for different deadline and storage constraints.

c=4

c=5

c=6

bootstrap (one per row; joins every row subnet)

u

+ =1 Nc

+ =0 Nc

good

bad

+ =3 Nc

+ =3 Nc

+ =3 Nc

+ =3 Nc

bootstrap — row links of u — column links of u

Fig. 2. The grid network: Each node u keeps a connection to every peer in its row (blue) and its column (orange). Each row requires a bootstrap nodes. A column may contain no good node; e.g., column c = 2. (Section III-D).

scalar field of BLS12-381 (q ≈ 2255 ). Equivalently, it has κ layers, each a D × D matrix over Fq . Each layer is extended by a 2D Reed–Solomon (tensor) code to an M ×M codeword, typically with M = 2D [2], giving the extended object B̂ = (X1 , . . . , Xκ ). Its M 2 positions (r1 , c1 ) ∈ [M ]2 each hold one symbol, and they are what clients GET and sample. Block B̂ can be fully reconstructed provided that fewer than (M − D + 1)2 symbols are missing; for M = 2D the code tolerates a missing fraction just above 1/4. Commitments. Data column j of layer i is the evaluation vector of a polynomial of degree less than D, committed with KZG [28] as comi,j , and com denotes the hash of allP κM commitments. KZG is additively homomorphic: P Com( g f ) = g Com(f i ), and an opening proof of i i i P Pi i g f at a point is g times the individual proofs. Binding i i i i i holds under q-SDH [29]. A node that holds all M evaluations of a committed polynomial can compute an opening at any point itself (amortized in O(M log M ) by FK20 [30]). B. Network and adversary Like RDA [9], we structure the underlying P2P network as a K1 × K2 grid (Fig. 2). A random oracle maps each node u to a cell Cell(u) = (r, c) ∈ [K1 ] × [K2 ]. Each node keeps a connection to every node in its row or column. For setting up new nodes, public bootstrap nodes are required such that every row must have one. A node is good if it is honest and online for the relevant window; otherwise it is bad. Bad nodes may deviate arbitrarily and collude. They see all messages and their messages can arrive before honest ones. The network has N nodes, N + of them good and N − = N − N + bad. Column c has Nc nodes, Nc+ of them good, and cell (r, c) has Nr,c nodes. For a node in row r, cell (r, c) is its contact cell for column c: its only one-hop route into that column. Node placement is uniform, so the mean column population is N̄c = N/K2 and the mean good count is N̄c+ = N + /K2 . Let η = N + /N denote the good fraction. No bound is placed on N − . Security of TCDA depends on N + alone. C. Requirement: δ-robust sampling The network layer of DAS must respond to a randomposition sampling of a published object with a correct symbol

4

under a failure probability that still enables full reconstruction of the object. We state this requirement as follows. Definition 1 (δ-robustness). A protocol is δ-robust if a GET for any position never returns a wrong symbol and fails with probability at most δ, whatever the bad nodes do. Each random sample must succeed with probability at least 1 − δ for the sampling argument of DAS [2]. The threshold δ is fixed and given by the code: up to δM 2 < (M −D +1)2 are allowed missing, so B̂ can be determined from the successful samples (Section III-A). For the usual M = 2D, any 75% of positions suffice, and we take δ = 1/4. A GET can fail for three reasons: the data may be lost, or unreachable, or incomplete. Unlike full replication where a single good node guards against loss and a single good responder completes a query, a coded design faces a harder task to achieve the same δ-robustness. A node holds only a fraction of its part, so several good nodes must jointly hold enough. An answer must combine pieces from them, and as such a query can stall on bad responders. The adversary can also supply valid but useless pieces.

layers X1 , . . . , Xκ KZG comi,j per data column

B̂ (M × M )

split

2D RS

B D×D

Jc : M/K2 data columns node u of column c keeps Q designated pieces P (c) yu,s = i gu,s,i Xi , gu,s = H(com, c, u, s), s = 1, . . . , Q

Fig. 3. Data preparation: The 2D Reed–Solomon extension B̂ is split into κ layers, one per symbol piece, and each data column of each layer is committed with KZG. Chunk c is the block of M/K2 contiguous data columns Jc (shaded) in all layers. It is stored by column c, where node u keeps the Q designated coded pieces yu,1 , . . . , yu,Q . column c 1 publisher → contact cell (r, c) row r

pub

chunk c

×

IV. T HE TCDA P ROTOCOL We present TCDA in five components: 1) preparation of a data object for publication, 2) how to publish it (PUT), 3) how to sample a symbol (GET), 4) how a node joins the network (JOIN), and 5) how to tune the parameters upon changing requirements (TUNE). A. Data Preparation The input to TCDA is the extended object B̂ = (X1 , . . . , Xκ ). This is the 2D erasure-coded matrix of the original object B and its commitments comi,j are defined as in Section III-A. A position (r1 , c1 ) ∈ [M ]2 represents a symbol of B̂. It is unrelated to the grid coordinates (r, c) ∈ [K1 ]×[K2 ] which represent a cell of nodes in the network.

2 each relay sends every column node u its Q designated pieces P (c) yu,s = i gu,s,i Xi 3 u keeps a piece P iff its commitment is i gu,s,i comi,j

D. Condition on the good nodes Two kinds of adversarial assumption are common: 1) Byzantine protocols typically assume a threshold on the fraction of good nodes in the network, e.g., η = 2/3. No one can enforce this in an open network, since an adversary can add Sybil nodes to lower η arbitrarily, however many good nodes there are; and 2) RDA avoids fractions but assumes, in advance of operation, that every column must hold at least one good node [9]. This is a structural condition on the network grid: no participant can observe it, and a single column without a good node voids or weakens the guarantee. TCDA has a softer rule. It works upon a minimal number, + Nmin , of good nodes in the network, not their fraction and not how they spread over the columns. Therefore, a column + may contain no good node. The threshold Nmin is a bootstrap condition computed at the design phase: given δ-robustness and the design parameters (grid sizing K1 × K2 and retention + depth Q), all fixed before deployment, we derive Nmin = + Nδ (Q) (Section V). A deployment can go live once it has this many good nodes.

chunk c: (c) (c) X1 , . . . , Xκ

κ pieces

good

bad

→ designated pieces

99K × rejected

Fig. 4. PUT path: Every relay in contact cell (r, c) sends each column node exactly its Q designated pieces (Q/κ of the chunk) instead of the full chunk; one good relay suffices. A piece with any other coefficients fails the commitment check and is dropped.

Symbol-to-chunk assignment. Illustrated in Fig. 3, the object is divided into K2 equally-sized chunks (assuming K2 |M ). Chunk nc ∈ [K2 ] consists of the ofollowing data M M columns Jc = (c − 1) K + 1, . . . , c K , taken in all 2 2 κ layers and all Symbol (r1 , c1 ) therefore belongs l M rows. m (c) 2 to chunk c = c1 K . We write Xi for layer i of Jc , an M M ×(M/K2 ) matrix. The chunk size is |X (c) | = σ/K2 , where σ is the size of the extended object B̂. Chunk c is stored by column c according to the PUT protocol (below). Because a chunk contains whole data columns, each being polynomially committed, any node that holds a coded version of a whole data column can compute KZG openings for it on demand (Section III-A). B. PUT Protocol PUT publishes an object B̂. Suppose that the publisher is on grid row r. It disseminates the K2 chunks of B̂ in parallel, chunk c into column c. Each node of column c stores Q ∈ [κ] coded pieces, each a random linear combination of the chunk’s κ layers. The steps for putting each chunk c ∈ [K2 ] are as follows (illustrated in Fig. 4). 1) Row hop: The publisher announces the commitments comi,j and broadcasts chunk c (all κ layers) to all nodes in contact cell (r, c); these nodes are the relays into column c. If the contact cell has no good node, chunk c is considered

5

column c = ⌈c1 K2 /M ⌉ 1 client → cell (r, c) (row hop)

1

row r client

v 4

2 collector v queries 1, 2, 4, . . . fresh peers per round; a good peer returns what is missing 3 once κ are innovative, decode the symbol 4 return symbol + proof

good

bad (silent or rejected)

Fig. 5. GET path for symbol (r1 , c1 ). A good collector v in cell (r, c) starts with its own Q coordinates and queries fresh column peers in rounds of 1, 2, 4, . . . until ⌈κ/Q⌉−1 good peers have supplied the rest. With Q = κ the column hop is skipped.

failed. TCDA does not detect or repair this: such misses are allowed by the threshold of δ-robustness (Definition 1). 2) Column hop: Each relay in contact cell (r, c) computes, for every node u in column c, Q random coded pieces {yu,s }s∈[Q] using designated coefficients for u, gu,s = H(com, c, u, s) ∈ Fκq ,

yu,s =

κ X

(c)

gu,s,i Xi

i=1

and sends them to u. The relay itself keeps its own Q designated pieces. 3) Retention: Each recipient node u recomputes the commitment of each received coded data column (one multi-scalar multiplication P of size M ) and keeps yu,s iff it matches Cu,s,j = i gu,s,i comi,j for all j ∈ Jc . Node u ignores subsequent pieces after receiving its Q valid pieces. Because a coded data column is stored wholly, no opening proofs are transmitted or stored at PUT time. They are computed on demand at GET time (Section III-A). Why designated coefficients. If relays chose the coding coefficients by themselves, one bad relay that reaches the column first could broadcast the same Q pieces to every node. Each piece would pass verification, yet the good nodes would jointly hold rank at most Q < κ, and the chunk would be lost. TCDA therefore fixes each node’s coefficients in advance by the random oracle, so exactly one piece is acceptable per slot and any other is rejected. For node u of column c and slot s ∈ [Q], since the Reed-Solomon code is linear, every data column of yu,s is again P a Reed-Solomon codeword, with commitment Cu,s,j = i gu,s,i comi,j for j ∈ Jc . Anyone can compute these commitments from public data alone, which is what the retention check of step 3 uses. C. GET Protocol GET samples a symbol at some random position (r1 , c1 ) ∈ [M ]2 . Suppose that the sampling client is on grid row r. It computes the symbol’s chunk c = ⌈c1 K2 /M ⌉ ∈ [K2 ], so it knows to find the symbol in column c. The data row r1 plays no part in routing; it only selects which coordinates are decoded. GET has the following steps (illustrated in Fig. 5). 1) Row hop: The client queries every node in the contact cell (r, c) for column c. Each good node of the cell acts as a

collector and starts with its own Q coordinates yv,s [r1 , c1 ] for the symbol. If Q = κ, this collector already holds κ independent coordinates; it decodes and returns the symbol to the client. Else, the next step. 2) Column hop: Each collector queries its column peers in incremental rounds. In round t = 1, 2, . . . , it sends a request to 2t−1 peers not yet asked, chosen uniformly at random, for min{Q, κ−k} of their coordinates yu,s [r1 , c1 ], where k is the number of innovative coordinates it holds at the start of the round. A node u returns them, each with a KZG opening against Cu,s,c1 that u computes itself. The collector stops querying the column after the round in which it has obtained κ linearly-independent pieces. 3) Decode and reply: The collector reconstructs the symbol given these κ pieces, derives their openings by the same linear combination of the received proofs (KZG homomorphism), and returns the symbol with one aggregated proof. The client verifies it against the commitments comi,c1 . D. JOIN Protocol Nodes leave and join continually. Node departures would erode the number of good pieces. Therefore, when a new node joins (returning is considered new), it counts toward the column’s good nodes only once it stores its designated pieces for every object still in the retention window. Syncing these pieces is therefore what keeps TCDA correct under churn. A new node u syncs each object in the following steps. 1) Placement: The random oracle places u in cell (r, c), and a bootstrap node connects it to its row and column peers. 2) Fetch: Node u queries its column peers in random order for their pieces, each verified against its public commitment, until receiving κ pieces with linearly-independent coefficient vectors. Since each piece is 1/κ of the chunk, u downloads one chunk’s worth of data per object. 3) Derive: For each slot s ∈ [Q], node P u writes its designated vector gu,s as a combinationP j λj gj of the fetched coefficient vectors, sets yu,s = j λj yj , verifies it against Cu,s,· , and discards the fetched pieces. Fetch succeeds whenever column c holds ⌈κ/Q⌉ synced good nodes. Until successfully synced, u retries and does not count toward the column’s good nodes. E. TUNE Protocol The retention depth Q is a public protocol parameter per data type. It is set by the design rule (later proposed in Section VII). The feasibility range of Q is bounded by δrobustness from below and the PUT and storage budgets from above. An adjustment of Q is needed when: • Safety (raise): the lower bound on number of good nodes N + falls and Q no longer meets δ-robustness. • Deadline (lower): network size N grows, pushing the PUT load over the budget; if Q cannot decrease further, the grid must be widened. • Margin (raise, optional): the budgets leave slack, so a larger Q widens the safety margin against good-node departures. • Cost (lower, optional): good-node growth lets a smaller Q meet δ-robustness and so lowering Q cuts PUT and storage.

6

Upon a change in retention depth Q, nodes adjust stored objects without republishing, simply as follows: 1) Raise Q to Q′ > Q. Every node runs the Fetch and Derive steps of JOIN for the new slots s = Q + 1, . . . , Q′ only. 2) Lower Q to Q′ < Q. Every node deletes its slots s = Q′ + 1, . . . , Q. No communication is needed. V. ROBUSTNESS C ONDITIONS A chunk c is retrievable if, once it has entered column c through a good relay, (i) the pieces held by the good nodes of column c can determine chunk c, and (ii) every GET for a symbol of chunk c that reaches a good node of column c returns the correct symbol. Lemma 1 (Chunk retrievability). Chunk c is retrievable iff Nc+ ≥ hQ ≜ ⌈κ/Q⌉, where at most
the “if” direction holds except with probability Nc+ 255 /(q − 1), which is negligible for q ≈ 2 (the field size). hQ Moreover, every GET then completes within ⌈log2 (Nc −Nc+ + hQ )⌉ rounds of column queries. Necessity. Suppose Nc+ < hQ . We have only Nc+ Q <

Proof. κ coefficient vectors of the good nodes, not enough to recover chunk c. Sufficiency. Suppose Nc+ ≥ hQ . A good node keeps a piece only if it matches the public commitment, so by KZG binding each good node holds exactly its Q designated pieces. Their coefficient vectors are random-oracle outputs of the fixed node identities, uniform in Fκq and beyond the adversary’s control. Any hQ good nodes thus hold hQ Q ≥ κ pieces, which have rank κ except with probability < 1/(q − 1). By a union bound +
c over the N such subsets, every one of them can reconstruct hQ +
c chunk c except with probability < N /(q −1). The returned hQ symbol is correct, since every coordinate is checked against the commitment: a bad responder can only send coordinates that are rejected, or valid ones that do no harm. After ⌈log2 (Nc − Nc+ + hQ )⌉ doubling rounds, the collector has queried at least (Nc −Nc+ +hQ −1) peers, hence (hQ −1) good ones, and holds rank κ, whatever the bad peers send or withhold. Decoding and proof derivation follow from linearity and KZG homomorphism. Next, we will derive the sampling failure rate. A GET for a symbol fails due to access failure or decoding failure. Access failure means that we cannot get to the custody column, happening if the publisher’s contact cell or the client’s contact cell has no good node. Decoding fails if the custody column c holds fewer than hQ good nodes, Nc+ < hQ (Lemma 1). Fix a good publisher and a good client in different rows, the worst placement, and a column c that is neither’s; the other N + good nodes are placed uniformly. Lemma 2 (Access failure). The publisher’s or the client’s contact cell holds no good node with probability + +   1 N 2 N P1 := 2 1 − − 1− . K1 K2 K1 K2

Proof. Each good node misses a given cell with probability 1− 1/(K1 K2 ) and both cells with 1 − 2/(K1 K2 ), independently of the others. Inclusion–exclusion gives P1 . +
Lemma 3 (Decoding failure). Let πn = Nn K2−n (1 − + 1/K2 )N −n and fn = 1 − 2(1 − 1/K1 )n + (1 − 2/K1 )n . Given that both contact cells hold a good node, the custody column holds fewer than hQ good nodes with probability P2 =

hQ −1 X 1 πn fn . 1 − P1 n=0

Proof. Given uniform placement of the good nodes, the good count in the column is binomially distributed, Nc+ ∼ Bin(N + , 1/K2 ), and so Pr[Nc+ = n] = πn . Given Nc+ = n, the n good nodes of the column are uniformly placed into its K1 cells, so both contact cells are hit with probability fn , by inclusion-exclusion. Decoding fails for every n < hQ PhQ −1 (Lemma 1), hence probability n=0 πn fn for decoding failure. Conditioned on a successful access (probability 1 − P1 from Lemma 2), we obtain P2 . Because a GET fails due to failure of either access or decoding, the probability of sampling failure is P1 + (1 − P1 )P2 . Hence, we obtain the result below. Corollary 1 (Sample failure). Against the worst-case adversary, and up to the negligible rank failure of Lemma 1, a sampling fails with probability exactly +

+

hQ −1

 X 1 N 2 N − 1− + πn fn P =2 1− K1 K2 K1 K2 n=0 {z } | 

≜pfail (N + ,K1 ,K2 ,Q)

This probability increases in K1 and decreases in Q. The following inequality is useful for closed-form bounding: +

P ≤ 2 e−N /(K1 K2 ) +   0 if hQ = 1    + hQ −1 −N̄c+ e N̄c if hQ ≥ 2, N̄c+ > hQ − 1 e hQ −1    1 otherwise.

(1)

TCDA is δ-robust iff P ≤ δ. We thus immediately obtain the following condition for TCDA to safely bootstrap. Theorem 1 (Bootstrap condition). Given a design (K1 , K2 , Q), TCDA is δ-robust iff the network has at least this many good nodes: N + ≥ Nδ+ (Q) = min{N + : pfail (N + , K1 , K2 , Q) ≤ δ}. The minimum Nδ+ (Q) is non-increasing in Q and nondecreasing in K1 . Furthermore, we can upper-bound it: ( K1 K2 ln(2/δ) if hQ = 1 +  Nδ (Q) ≤ max K1 K2 ln(4/δ), K2 xQ otherwise. (2) where xQ is the root x > hQ − 1 of equation ex x − (hQ − 1) ln = L := ln(2/δ). hQ − 1

7

This xQ satisfies hQ − 1 < xQ ≤

p

q 2 L/2 + hQ − 1 + L/2 .

(3)

Proof. The bootstrap condition is obvious and the monotonicity in K1 and Q is easy to derive. Let us focus on the closedform inequality. By Inequality (1), it suffices that its closedform bound be at most δ. + For hQ = 1, letting 2e−N /(K1 K2 ) ≤ δ, we have N + ≥ K1 K2 ln(2/δ). For hQ ≥ 2, bounding each term by δ/2, we have −N + /(K1 K2 ) • The first term: 2e ≤ δ/2 ⇒ N + ≥ K1 K2 ln(4/δ). • The second term: +

e−N̄c (eN̄c+ /(hQ − 1))hQ −1 ≤ δ/2 . |{z} {z } | ≜g(N̄c+ )

=g(xQ )

Since g decreases for N̄c+ > hQ − 1 and xQ > hQ − 1, we get N̄c+ ≥ xQ ⇒ N + ≥ K2 xQ . For the upper bound on xQ ,plet µ0 be the value at p which √ 2L/µ , i.e., µ = L/2 + h − 1 = (1 − t)µ with t = 0 0 0 pQ 2 hQ − 1 + L/2. Since (1−t) ln(1−t) ≥ −t+t /2, g(µ0 ) = 2 e−µ0 [t+(1−t) ln(1−t)] ≤ e−t µ0 /2 = δ/2, so xQ ≤ µ0 .

By Eq (3), we have xQ ≤ N̄c+ if hQ ≥ 2, and together with N + ≥ K1 K2 ln(4/δ) this gives N + ≥ Nδ+ (Q); if hQ = 1, N + ≥ K1 K2 ln(2/δ) suffices. Hence Qδ ≤ Q = ⌈κ/h⌉. Together, Theorem 1 and Corollary 2 show what the bootstrap is made of. Parameter Q allows TCDA to tune priorities in terms of PUT, GET, and storage costs. Note that, at Q = κ, every node keeps all κ pieces, the size of full replication, and TCDA has the same storage and dissemination protocol as that of RDA. However, our bootstrap requirement is less demanding because we allow for columns to be empty of good nodes, whereas RDA requires every column to contain one. Example. Take (15, 32) grid, erasure-coding granularity κ = 64, and robustness requirement δ = 1/4. Table I lists for each Q the smallest number of good nodes, Nδ+ (Q), that makes TCDA δ-robust, computed exactly and from the closed form according to Theorem 1, which shows a close approximation (at most 38% over). TABLE I TCDA: BOOTSTRAP SIZE FOR (15, 32) GRID , κ = 64, 1/4- ROBUSTNESS .

Corollary 2 (Safe range of the knob). Consider a network with N + good nodes placed uniformly. Let N̄c+ = N + /K2 and L = ln(2/δ). (i) Tunability. TCDA is δ-robust iff Q ≥ Qδ := min{Q ∈ [κ] : pfail (N + , K1 , K2 , Q) ≤ δ}. (ii) Existence. Qδ exists iff N + ≥ Nδ+ (κ), the bootstrap of full replication, and 2 1 √ ≤ Nδ+ (κ) ≤ K1 K2 ln . (K1 K2 − 1) ln δ 1− 1−δ (iii) Closed form. If N + ≥ K1 K2 ln(4/δ) and N̄c+ ≥ 2L, then p     Qδ ≤ κ/h , h = N̄c+ − 2LN̄c+ + 1. Proof. (i) Since pfail decreases in Q, the tunability range is an immediate consequence of the bootstrap condition in Theorem 1. (ii) Also, thanks to Theorem 1, Nδ+ (Q) is non-increasing in Q and so Nδ+ (κ) ≤ Nδ+ (Q) ≤ Nδ+ (Qδ ) for all Q ∈ [Qδ , κ]. Therefore, Qδ exists iff N + ≥ Nδ+ (κ). The upper bound of Nδ+ (κ) is according to Eq (2) by setting Q = κ (i.e., hQ = 1). For the lower bound, according to Corollary 1, by setting Q = κ and N + = Nδ+ (κ), we have pfail = P = 2p − p2 where + + p = (1 − 1/(K1 K2 ))N and p2 = (1 − 2/(K1 K2 ))N ≤ p2 . Hence √ pfail ≤ δ ⇒ 1 − (1 − p)2 ≤ δ ⇒ p ≤ δc := 1 − 1 − δ. Applying inequality − ln(1 − x) ≤ x/(1 − x), we obtain Nδ+ (κ) = N + ≥ (K1 K2 − 1) ln(1/δc ). (iii) Let Q = ⌈κ/h⌉. Then κ/Q ≤ h, so hQ ≤ h and so p hQ − 1 ≤ h − 1 ≤ N̄c+ − 2LN̄c+ q p p ⇒ N̄c+ ≥ L/2 + hQ − 1 + L/2.

Q

hQ

Nδ+ (Q) exact

closed form

64 16 8 4 2 1

1 4 8 16 32 64

965 965 965 966 1222 2221

999 1331 1331 1331 1401 2580

TABLE II TCDA VS . RDA: ON SAME (15, 32) GRID , κ = 64, SAME δ- ROBUSTNESS . ϵ

N+

δRDA

RDA’s Q

TCDA’s Q

1/4 10−3 10−6 10−9

150 327 545 762

0.93 0.76 0.54 0.37

64 64 64 64

32–64 22–64 11–64 7–64

Table II compares TCDA to RDA. Given the same network sized by RDA under various failing rates (ϵ) of enforcing its good-node assumption, each failing rate leading to a corresponding degree of robustness, δRDA . For the same robustness, TCDA offers a free choice of Q in the listed range, whereas RDA is fixed at Q = κ. Not only that, the larger N + (more good nodes), the more freedom to tune Q. VI. C OST M ODEL Storage and PUT traffic scale with the object, so we measure them in units of its size σ. A GET returns one symbol whatever the object’s size, so we measure it in units of the symbol size σs = σ/M 2 . Let σpf be the size of a KZG proof (48 B) and β = σpf /σs . The sync of JOIN costs the same in both TCDA and RDA; it does not depend on Q. A. Storage Cost Let Φstore be the amount of storage required at a node per object. Objects are retained for an availability window of W blocks, one object per block, so a node holds W Φstore at any

8

time. A node keeps Q designated pieces, each a combination of the chunk’s κ layers and hence of size σ/(κK2 ):   Q Φstore = σ. κK2 B. PUT Cost Let Φput be the amount of data a good relay sends in the column hop of PUT, per object. This is the per-node load that the attestation deadline caps. There are K2 chunks per object, each published in a separate column. Suppose that the publisher is in row r. It sends these K2 chunks to their respective cells in row r. For each chunk c, every good relay in cell (r, c) sends Q pieces to each of the Nc nodes in column c, so a relay of column c sends Qσ Nc . (4) κK2 The total PUT traffic per object, the publisher’s row hop included, is Φput (c) =

K2 Nr σ X + + Nr,c Φput (c) K2 c=1 N  Q X + r = + Nr,c Nc σ, K2 κK2 c

Φnet put (r) =

+ where Nr is the population of row r and Nr,c the good count of cell (r, c). Assuming uniform distributions of good nodes and publishers in the network, its mean is  N Q N +N  net · σ. Φnet := E[Φ (r)] ≈ + put put K1 K2 κ K1 K22

C. GET Cost In GET, each collector node already holds Q coordinates of the symbol. By Lemma 1, it must obtain the remaining (κ−Q) from m := hQ − 1 = ⌈κ/Q⌉ − 1 good column peers. These peers are queried in rounds, each round doubling the contact size: 1, 2, 4, ... Latency (successful GET). The collector stops after t = ⌈log2 (X + 1)⌉ rounds where X is the position, in the collector’s random order of its Nc − 1 peers, of the m-th good one contacted. The expectation notation in the following is over randomness of X. Suppose that the symbol belongs to chunk c. We have m N+ E[X] = , ηc = c , (5) ηc Nc the negative hypergeometric mean. Counting the one roundtrip from the sampling client to its contact cell, the latency of a successful GET attempt is quantified by the following number of round-trips  m + 1 . Λsucc (c) := E[1 + t] ≤ 2 + log 2 get ηc The adversary can worsen the good fraction ηc of a column by adding arbitrarily many bad nodes, but the impact on latency is only logarithmic because t ≤ ⌈log2 (Nc − Nc+ + hQ )⌉.

The collector has then queried Γget = 2t − 1 < 2X column peers, so E[Γget ] < 2m/ηc . Traffic (successful GET). Let Φsucc get denote the expected amount of data all good nodes send for one successful GET attempt. Per collector, the good peers collectively send at least the (κ − Q) coordinates. Each coordinate carries a proof, and the collector returns the symbol with one aggregate proof. + Summing over the Nr,c collectors, we have a lower bound:  i h 1 + + β + (1 + β) σs . (κ − Q) Φsucc (r, c) ≥ N get r,c κ Also, we know that each good column node returns at most Q coordinates for the symbol. The number of good nodes contacted is at most Γget < 2X. Applying Eq (5), we obtain an upper bound:   i h + 2mQ 1 + β + (1 + β) σs . Φsucc get (r, c) < Nr,c ηc κ Latency and traffic per GET, failures included. The above formulation applies to a successful GET attempt. In general, an attempt can fail, which incurs wasted costs. A failure is for one of two reasons: i) access failure: a contact cell holds no good node (probability P1 , Lemma 2) or ii) decoding failure: access is successful but the column is not decodable (probability P2 , Lemma 3). Let Λ1 , Φ1 and Λ2 , Φ2 be the latency-traffic costs of an attempt that fails due to these reasons, respectively. Then, the expected latency and traffic costs to get a verified symbol, in terms of round-trips, are P2 Λ2 P1 Λ1 Λget = Λsucc + (6) get + (1 − P1 )(1 − P2 ) 1 − P2 P1 Φ1 P2 Φ2 Φget = Φsucc + (7) get + (1 − P1 )(1 − P2 ) 1 − P2 Here, the row/column index of Φ, Λ is omitted for clarity. • Access failure: If the client’s contact cell has no good node, the sampling query stops there. If the publisher’s contact cell has no good node, the chunk never entered the column, and as such no good node of the client’s contact cell holds any piece. Therefore, Λ1 = 1 and Φ1 = 0. • Decoding failure. Each collector doubles its contact size until it has queried its whole column; hence Λ2 = 1 + ⌈log2 Nc ⌉. The collector has Nc+ − 1 ≤ hQ − 2 good peers, each sending at most Q coordinates, with no reply to the client. So  1 + + β σs Φ2 ≤ Nr,c (Nc+ − 1) Q κ 1  + < Nr,c (κ − Q) + β σs . κ Substituting the above, TCDA needs
P1 P2 Λget = Λsucc + 1 + ⌈log2 Nc ⌉ get + (1 − P1 )(1 − P2 ) 1 − P2 P2 Φ2 . Φget = Φsucc get + 1 − P2 Remark 1. The formulation of the costs is summarized in Table III. Compared to RDA, storage and PUT costs fall by Q/κ. In exchange, every GET takes a second hop, of about log2 (m/ηc ) + 1 round-trips, fewer as Q grows, and moves at least (κ − Q)/κ of a symbol more.

9

TABLE III + + C OST MODEL (Φnet put AT MEAN POPULATIONS ). m = ⌈κ/Q⌉ − 1, ηc = Nc /Nc , β = σpf /σs ; Nr,c , THE GOOD COUNT OF THE CLIENT ’ S CONTACT CELL , IS COMMON TO BOTH DESIGNS AND ABOUT N + /(K1 K2 ) ON A TYPICAL CELL ; P1 AND P2 ARE GIVEN BY L EMMAS 2 AND 3. AT Q = κ, TCDA COINCIDES WITH RDA. S HADED IN GREEN : THE COSTS IN THE DESIGN PROBLEM (8) OF S ECTION VII, NAMELY THE STORAGE AND PUT BUDGETS AND THE GET LATENCY TO MINIMIZE .

Cost

RDA

TCDA(Q < κ)

Per object

Φstore /σ Φput /σ Φnet put /σ (column hop)

1/K2 Nc /K2 N + N/(K1 K22 )

Q /K2 κ Q Nc /K2 κ Q N + N/(K1 K22 ) κ

Per successful attempt

Λsucc get (round-trips) E[Γget ] (column queries) Φsucc get /σs

1 0 + Nr,c (1 + β)

≤ 2 + log2 ( ηmc + 1) < 2m/ηc   + ≥ Nr,c (κ − Q)( κ1 + β) + 1 + β

Per sample

Λget (round-trips) Φget /σs

P2 P1 + 1 + ⌈log2 Nc ⌉ (1 − P1 )(1 − P2 ) 1 − P2
P2 + ≤ Φsucc Nr,c (Nc+ − 1) Q κ1 + β get /σs + 1 − P2

1 1 − P1

Λsucc get +

+ Nr,c (1 + β)

VII. O PTIMAL D ESIGN In blockchain DAS, the costs of storage, PUT, and GET weigh differently. Storage must fit the disk space a node gives to DAS, which holds the objects of the last W blocks, so W Φstore ≤ BS , where BS is the storage budget per node. The PUT protocol sits on the path to finality: every relay must finish the column hop of each block before validators attest, so the per-relay PUT cost should be capped by a budget, Φput ≤ BP : the uplink rate times the part of the attestation deadline left once the publisher has reached the relays. The GET protocol has no such cap: clients sample continually, and every round-trip saved shortens every sample. However, we want to make GET as fast as possible, i.e., min Λget . Example (Ethereum). A slot lasts 12 s, validators attest about 4 s into it [10], and an attesting node is recommended 25 Mbit/s of uplink [11]. A publisher with a 1 Gbit/s uplink reaches the relays of every column within about 0.87 s, which leaves BP = 9.3 MiB per relay per object. Blobs are retained for W = 131,072 blocks, about 18 days [3], and we give DAS BS = 32 GiB per node, half of what PeerDAS [4] stores per node, i.e., BS /W = 0.25 MiB per object. For σ = 32 MiB, the budgets are 0.29σ and σ/128. On the (15, 32) grid with 965 good nodes and as many bad ones, a column holds 60 nodes on average and up to 79 at the 99th percentile, so RDA’s relay load reaches Φput = 79σ/K2 = 2.47 σ, 8.5 times the PUT budget, and each node stores σ/K2 , four times the storage budget. RDA thus fails both budgets. A. Design Problem Once PUT and storage fit their budgets, the goal is to achieve the fastest GET. All this is subject to δ-robustness. Speaking of constraints, PUT is more important than storage. Storage can be cheap today, but PUT must meet the attestation deadline. So, optionally, we can drop the storage constraint to have more search space to minimize GET, but PUT is a hard constraint. The costs, as defined in the previous sections, depend on the network size N , good and bad, which is not known in the design phase. If we allow N to grow any large, the adversary

can add arbitrarily many Sybil nodes to increase the costs boundlessly. Therefore, we must set a maximum network size, N ≤ Nmax . This worst-case sizing does not affect robustness: δ-robustness depends only on the good nodes, N + ≥ Nδ+ (Q) (Theorem 1). If the network grows beyond Nmax nodes, only the PUT load and GET latency go beyond the budget, but it remains as robust. The inputs to our design problem are: lower bound N + on the good nodes, upper bound Nmax on the total population, robustness δ, object parameters (σ, M , κ), budgets (BP , BS , W ), and peer-degree bound dmax . The design is the following optimization: min

K1 , K2 , Q

s.t.

Λget (N + , Nmax ; K1 , K2 , Q)

(latency)

pfail (N + ; K1 , K2 , Q) ≤ δ,

(robustness)

Φput (Nmax ; K2 , Q) ≤ BP ,

(deadline)

W Φstore (K2 , Q) ≤ BS , Q ∈ [κ],

K2 | M,

(8)

(storage)

1/K1 + 1/K2 ≤ dmax .

The last constraint is to keep a low overhead for a node to maintain peer connections in the network, about N (1/K1 + 1/K2 ) of them. For example, dmax = 0.05 keeps the overhead below 5% of the network size. Without this constraint, K1 = 1 is optimal, i.e., a node needs to maintain connections with every other node, practically unreasonable. The costs in the design problem are exactly formulated as follows: Columns differ in size, and the PUT must finish in every column, not only in a typical one, so we size the PUT on N̂c , the (1 − ϵP )-quantile of the column population Bin(Nmax , 1/K2 ); we take ϵP = 0.01 (99%-quantile). • The GET cost is a mean over samples, so it uses the typical column, Nc = N̄c = Nmax /K2 and Nc+ = N̄c+ = N + /K2 , and ηc = η = N + /Nmax . •

The constraints then are equivalent to N + ≥ Nδ+ (Q),

Q N̂c σ ≤ BP , κ K2

Q σ W ≤ BS , κ K2

(9)

10

and the objective is

In particular, a feasible design exists only if

Λget = Λsucc get +

P2 1 + ⌈log2 N̄c ⌉ P1 + , (1 − P1 )(1 − P2 ) 1 − P2 (10)

with Λsucc get ≤ 2 + log2 (m/η + 1) at Q < κ and = 1 at Q = κ.

σ ≤ σmax :=

κK22 BP . ρ (K1 K2 − 1) ln(1/δc )

Proof. Replacing N = ρN + in Corollary 4, the PUT budget requirement becomes

κ K22 BP Q ρN + σ + ≤ B ⇐⇒ N ≤ . P κ K22 Q rσ B. Solution Approach Necessity (i) The above inequality immediately implies the Our solution is guided by the following results. First, on upper bound N + ≤ κK 2 B /(ρσ) because Q ≥ 1. The 2 P each grid, the optimal Q has a closed form. lower bound is resulted from the δ-robustness, as follows. Corollary 3 (Optimal retention depth Q). Fix the grid Because robustness is achieved by some Q ≤ κ, it must also be achieved if Q = κ (because more pieces are stored, (K1 , K2 ). Problem (8) is feasible iff  hence improving robustness). Applying this case to Theorem  1, we have N + ≥ Nδ+ (κ) ≥ (K1 K2 − 1) ln(1/δc ). The latter Qδ ≤ Qmax := min κ, ⌊κBP K2 /(N̂c σ)⌋, ⌊κBS K2 /(W σ)⌋ {z } | {z } | inequality is from Corollary 2(ii). ≜QP ≜QS Sufficiency (ii) Take Q = 1. The upper bound puts it within the PUT budget, as above. For robustness, hQ = κ ≥ 2 at Q = and then, Q = Qmax is the optimal. 1, so Eq. (2) gives N + (1) ≤ max{K1 K2 ln(4/δ), K2 x1 } ≤ Proof. δ-robustness bounds Q from below by Qδ (Corol- N + . Applying Q = 1 δin Theorem 1, TCDA is δ-robust. Thus lary 2(i)). We need Q ≤ QP and Q ≤ QS because of the Q = 1 is feasible. constraints involving Q in Eq (9). Hence the feasible values Bound on object size σ. The range in (i) is non-empty iff on the grid form the window Qδ ≤ Q ≤ Qmax , which is (K K − 1) ln(1/δ ) ≤ κK 2 B /(ρσ). Solving for σ gives 1 2 c 2 P non-empty iff Qδ ≤ Qmax . the bound. This bound caps the object size for every N + . Within [Qδ , Qmax ], a larger Q means each good node holds more pieces, so a client needs to query fewer good nodes, Example. With δ = 1/4, κ = 64, ρ := N/N + = 2, and hQ = ⌈κ/Q⌉, thus fewer round-trips (smaller Λsucc get ). So is the decoding failure probability P2 . P1 does not depend on BP = 9.3 MiB, the (15, 32) grid has σmax ≈ 318 MiB for Q. The latency Λget (Eq (10)) is smaller as Q increases. This TCDA but only σmax = 5 MiB for full replication (RDA). Ethereum’s 32 MiB object therefore fits TCDA, for any N + ∈ makes Q = Qmax the optimal choice. [965, 9566], but not RDA on this grid at any network size. Based on the above corollary, different object types on the same grid may choose different Q in the window indepen- C. Solution Algorithm dently, since the network is untouched. If monitoring shows The steps of our design are sketched in Algorithm 1. For N + falling, nodes raise Q in place (Section IV-E). The next each K2 , the number of rows ranges over K1,min ≤ K1 ≤ corollaries are scaling laws assuming typical columns, with K1,max , where K1,min := ⌈1/(dmax − 1/K2 )⌉ is the degree column size Nc = N/K2 . constraint and K1,max := ⌊(N + / ln(1/δc ) + 1)/K2 ⌋ follows + + Corollary 4 (Population limit). On a grid with K2 columns from robustness, N ≥ Nδ (κ) ≥ (K1 K2 − 1) ln(1/δc ) of N̄c = N/K2 nodes, TCDA at retention depth Q meets the (Corollary 2(ii)). On each grid, Corollary 3 gives the optimal Q in closed form, so problem (8) is solved by a finite scan PUT budget iff network size N ≤ (κ/Q) K22 BP /σ. over (K1 , K2 ). A scan is needed because Λget need not be Proof. On a typical column c, Nc = N̄c = N/K2 , and so, monotone in K1 or K2 . On each grid, the robustness test is applying Eq 4, a relay in this column incurs a PUT cost of a single evaluation of pfail at Qmax , which suffices because pfail is non-increasing in Q (Corollary 3), so Qδ ≤ Qmax iff Qσ Q Nσ Φput = Nc = . p 2 fail (Qmax ) ≤ δ. The objective Λget is evaluated by simulating κK2 κ K2 the GET, about one second per grid, or in closed form by the The PUT budget constraint Φput ≤ BP is thus equivalent to formula of Section VI-C with Λsucc at its bound. get N ≤ (κ/Q)K22 BP /σ. Complexity. We count arithmetic operations, taking a power √ The loop in line 2 Corollary 5 (Good-node range and object size limit). Let N = and a binomial CDF value as O(1) each. √ runs over the divisors of M : at most 2 M of them, found + √ ρN , δc := 1 − 1 − δ, and x1 as in Theorem 1 for Q = 1. in O( M ) time. Per K , line 3 takes O(log Nmax ) CDF 2 TCDA can be both δ-robust and within the PUT budget with evaluations by bisection, and lines 4–6 take O(1). The loop in + N good nodes line 7 runs at most K1,max times. Per (K1 , K2 ), line 8 costs (i) only if (necessity) O(hQ )P= O(κ), the sum in P2 , and lines 9–11 cost O(1). Since K2 |M 1/K2 = O(log log M ), Algorithm 1 runs in (K1 K2 − 1) ln(1/δc ) ≤ N + ≤ κK22 BP /(ρσ). √ 
O M log Nmax + κ N + / ln(1/δ) + 1 log log M (ii) if (sufficiency) Φput (Q) =

max{K1 K2 ln(4/δ), K2 x1 } ≤ N + ≤ κK22 BP /(ρσ).

operations, ≈ 15, 000 for M = 128, κ = 64, and N + = 5000.

11

Algorithm 1 Joint design of grid and retention depth Require: Object: size σ, width M , layers κ Network: good nodes N + , all nodes Nmax , degree dmax Budgets: PUT BP (quantile ϵP ), storage BS , retention W Robustness: target δ Ensure: an optimal (K1 , K2 , Q) of (8), or INFEASIBLE 1: D ← INFEASIBLE; Λ⋆ ← ∞ 2: for each divisor K2 of M with 1/K2 < dmax do 3: N̂c ← (1 − ϵP )-quantile of Bin(Nmax , 1/K2 ) 4: QP ← ⌊κBP K2 /(N̂c σ)⌋; QS ← ⌊κBS K2 /(W σ)⌋ 5: Q ← min{κ, QP , QS } ▷ Cor. 3 6: if Q < 1 then continue 7: for K1 = K1,min , . . . , K1,max do 8: if pfail (K1 , K2 , Q) > δ then continue ▷ Cor. 1 9: Λ ← Λget (K1 , K2 , Q) ▷ Sec. VI-C 10: if Λ < Λ⋆ then 11: D ← (K1 , K2 , Q); Λ⋆ ← Λ 12: return D VIII. N UMERICAL E VALUATION We evaluate TCDA at Ethereum’s parameters for two purposes: validate its theoretical results and compare it to RDA and PeerDAS, the DAS design deployed on Ethereum. PeerDAS also represents the gossip-based approach, as opposed to the grid approach of TCDA and RDA. As in RDA, we report the GET cost at protocol level, in round-trips and bytes, and use wall-clock time only for the PUT, which has a deadline. The evaluation’s source codes are available at https://github.com/UMB-NCLab/tcda-sim. Adversary. Nodes, including publishers and clients, are placed uniformly at random on the grid, and so are the sampled positions. A bad node is a Sybil, a dishonest node, or an offline honest node, and behaves in the worst case: a bad relay drops the chunk or forwards pieces with other coefficients, which the commitment check rejects; a bad collector returns nothing; and a queried bad node stays silent. In some scenarios, a mass of the good nodes also goes offline at once. A. Theoretical results at Ethereum’s parameters We validate the results that rest on assumptions or give bounds; the others, such as Theorem 1 and the corollaries of Section VII, are exact. The objectives are: (O1) Growth of the GET cost with bad nodes. PUT and storage stay within budget by design, so only the GET cost grows with bad nodes. We measure how, against the theoretical derivations. (O2) Feasibility and latency of the optimal design. Does Algorithm 1 find a feasible design, how fast is its GET, and does the closed-form bound pick the same design as simulation? (O3) Choosing the design inputs. How do N + , Nmax , and dmax change the design? Settings. Table IV lists the parameters and their justification. They follow Ethereum and the baselines’ own evaluations, e.g., M = 128 as in PeerDAS and dmax = 1/10

TABLE IV E VALUATION PARAMETERS . Parameter Object and coding Field element; proof Symbol, κ Object width M Object size σ Robustness Target δ

Value

Justification

32 B; σpf = 48 B

BLS12-381, as in EIP-4844 [3]

64 elements (2 KiB) 128 32 MiB

a PeerDAS cell [31] PeerDAS columns [31] 64 blobs of 128 KiB, 2D-extended

1/4

M = 2D (Section III-C)

Network Population N , 2N + (also N + to Nmax 16N + ) Degree limit dmax 1/10 (also 1/6) Timing and budgets Slot; attestation deadline Relay uplink PUT budget BP PUT sizing ϵP Retention W ; storage BS

12 s; 4 s

half bad; no effect on robustness (Thm. 1) RDA’s example [9] Ethereum [10]

25 Mbit/s (also 50, 100) attesting node [11] 9.3 MiB 4 s at 25 Mbit/s minus the publisher’s 0.87 s 0.01 99th-percentile column (Section VII-A) 131,072 blocks; 32 GiB 18 days [3]; half of PeerDAS’s per-node storage

Fig. 6. (O1) GET cost per sample, failed attempts included, as bad nodes join, measured (solid) and the bounds of Section VI-C (dashed): (a) roundtrips, with Λsucc get at its bound; (b) traffic sent by good nodes per collector, against its minimum (κ − Q)(1/κ + β) + 1 + β. (15, 32) grid, N + = 2500.

as in RDA. The storage budget, 32 GiB per node, is half of PeerDAS’s (0.5 MiB per object); it caps Q at K2 /2. 1) Objective O1 - Growth of the GET cost with bad nodes: Figure 6 shows the GET cost as bad nodes join: 4000 samples per point, failed attempts included, on the (15, 32) grid with N + = 2500, which is δ-robust for every tested Q, and 0 to 15 bad nodes per good one. The latency grows logarithmically, as derived (Figure 6a). At Q = 4, each doubling of N/N + adds one round-trip (5.0, 6.1, 7.0, 8.0, and 9.0 at N/N + = 1 to 16), the slope of the formula, which stays about one roundtrip above. At large Q the growth is slower than the formula, which is per collector, while a client takes the fastest of its cell’s collectors, about five here. The traffic per collector does not grow (Figure 6b): it stays within 31% of its minimum, since silent bad peers send nothing. 2) Objective O2 - Feasibility and latency of the optimal design: We apply Algorithm 1 at uplinks of 25, 50, and 100 Mbit/s, N + up to 40,000, and Nmax = 2N + . The PUT

12

TABLE V (O2, O3) G OOD - NODE RANGES WITH A FEASIBLE DESIGN , AND ITS ROUND - TRIPS PER SAMPLE Λget (A LGORITHM 1, Nmax = 2N + , ϵP = 0.01, σ = 32 M I B, δ = 1/4, N + ≤ 40,000). dmax = 1/10 Uplink Feasible N + 25 Mbit/s 50 Mbit/s 100 Mbit/s

≥868 ≥868 ≥868

dmax = 1/6

Λget

Feasible N +

Λget

2.5–7.7 1.2–6.6 1.0–5.5

≥330 ≥321 ≥321

2.2–7.3 1.0–5.6 1.0–5.5

Fig. 8. (O3) GET latency Λget of the design chosen by Algorithm 1 over both inputs, the good nodes N + and the ratio Nmax /N + , at 25 Mbit/s (dmax = 1/10). Grey: no feasible design. White lines: the chosen grid changes, to 32, 64, and 128 columns.

Fig. 7. (O2, O3) The design chosen by Algorithm 1 at 25 Mbit/s, colored by its grid (K1 , K2 ) (dmax = 1/10, Nmax = 2N + , ϵP = 0.01, σ = 32 MiB, δ = 1/4): (a) round-trips per sample, with Q written next to selected points; (b) failure probability per sample. No design fits below 868 good nodes.

The fastest designs lie at about 3000 to 7000 good nodes and a ratio of at most 2: the best N + is at neither end of its range, while a smaller ratio is faster but leaves less room for growth and bad nodes. Degree limit. With dmax = 1/6, the bootstrap drops from 868 to about 330 good nodes, since fewer, larger cells rarely lack a good node. The GET is faster by up to four roundtrips below 3000 good nodes and by at most 0.3 above. The degree limit trades a node’s connections against the bootstrap, not against feasibility. B. Comparison with the baselines

and storage costs are exact, so only Λget is simulated, with 1500 samples, about one second per grid. The closed-form bound picks the same design as simulation in all 69 cases, so a deployment can choose its design without simulation. Feasibility. A feasible design exists for every N + ≥ 868 at all three uplinks, and for every N + ≥ 330 at dmax = 1/6 (Table V). Storage binds only at the faster uplinks. Latency. Figure 7a shows the latency of the chosen design at 25 Mbit/s. As predicted, once N + grows enough, the design moves to a grid with twice as many columns, where the PUT budget allows a larger Q and a faster GET: the latency falls from 7.7 to 2.6 round-trips up to about 3000 good nodes. Beyond that, K2 = M = 128, so the columns fill and the latency grows logarithmically. 3) Objective O3 - Choosing the design inputs: Algorithm 1 takes N + , Nmax , and dmax as inputs. A deployment prefers a small N + , which is easier to reach, a pfail safely below δ to tolerate churn, and a fast GET. Bootstrap size. With Nmax /N + = 2, the fastest size, about 3000 to 3500 good nodes, has a thin margin: pfail is 0.16 to 0.22 against δ = 0.25 (Figure 7b). A little above, the margin grows quickly at a small cost: at 5000 good nodes, pfail = 0.056, four times below δ, for 3.2 round-trips instead of 2.5. Population bound. Figure 8 varies Nmax /N + . The pattern of Figure 7a holds at every ratio, and a larger ratio costs twice. The GET is slower, by about two round-trips per doubling: 2.6, 4.9, 7.1, and 9.2 at 3000 good nodes and ratios 2, 4, 8, and 16. The smallest feasible network is larger: 868, 1200, 1800, and 3000 good nodes. No design exists beyond about 300,000 nodes in total, where even Q = 1 exceeds the PUT budget.

Table VI summarizes the comparison at N + = 2000 in the default setting. PeerDAS has the lightest per-node load but no robustness guarantee, and fails against Sybils. RDA has the fastest GET but misses the PUT deadline. TCDA is δ-robust once it has enough good nodes, whatever the number of bad ones, and within budget while the network stays within Nmax . The objectives are: (O4) Feasibility and robustness. At which network sizes does each design meet the budgets, and does it stay δ-robust under Sybils? (O5) PUT time with coding included. With the publisher’s row hop and the relays’ coding time, is the deadline still met? (O6) Dynamic network. Our analysis is static. Is δ-robustness kept as nodes join and leave, or as many leave at once? Settings. The parameters are those of Table IV. PeerDAS [4], [6], [31]: blobs are 1D-erasure-coded into M = 128 columns, its chunks. Each node stores at least 4 and samples at least 8 by subscribing to their gossip subnets. Custody is self-advertised, so any node can claim any chunk. RDA [9] is TCDA at Q = κ, except for the condition on the good nodes. We count an RDA grid as feasible if N + ≥ Nδ+ (κ), which is less demanding than RDA’s own per-column assumption at ϵ = 10−9 and so favors RDA. 1) Objective O4 - Feasibility and robustness: Figure 9 shows the network sizes at which each design meets the budgets. TCDA meets them at every size from its bootstrap on, at every uplink. At 25 Mbit/s, RDA fails on every grid; a looser degree limit lowers its bootstrap but not its load. At faster uplinks, RDA is feasible only on 128 columns, where a full chunk fits the storage budget, and only until its load, which

13

TABLE VI (O4, O5) OVERALL COMPARISON OF THE THREE DESIGNS AT N + = 2000 GOOD NODES AND AS MANY BAD ONES , σ = 32 M I B (8 M I B OF BLOB DATA ), δ = 1/4, 25 M BIT / S UPLINK , 4 S DEADLINE , dmax = 1/10. PUT SIZED ON THE 99TH - PERCENTILE COLUMN ; PUT IN TIME FROM S ECTION VIII-B2; GET ROUND - TRIPS PER SAMPLE , FAILED ATTEMPTS INCLUDED . Design

Robust iff

PeerDAS no guarantee RDA N + ≥ Nδ+ (κ) TCDA N + ≥ Nδ+ (Q)

pfail , 0 → 10N + Sybils Min. N + for 4 s Grid, Q 0 → 0.91 0.14 → 0.14 0.14 → 0.14

PUT in time Storage/node GET round-trips

load indep. of N 128 columns none (12, 64), 64 868 (12, 64), 14

0.5 MiB 0.5 MiB 112 KiB

— 0% 99.6%

1 (req./resp.) 1.2 4.4

TABLE VII (O5) PUT TIME WITH CODING INCLUDED : N = 2N + , σ = 32 M I B, 25 M BIT / S , dmax = 1/10: 99TH PERCENTILE OVER COLUMNS OF THE TIME TO SERVE A COLUMN ( S ), AND THE FRACTION OF COLUMNS SERVED WITHIN 4 S , RELAY CODING INCLUDED . TCDA N+

Grid

Q p99

2000 (12, 64) 14 6000 (11, 128) 20 20,000 (11, 128) 6

Fig. 9. (O4) Network sizes at which a design meets the PUT and storage budgets and is δ-robust (Nmax = 2N + , σ = 32 MiB, δ = 1/4, N + ≤ 40,000). The bars for dmax = 1/6 show only the sizes it adds to those of dmax = 1/10.

Fig. 10. (O4) Per-sample failure probability at N + = 2000 as Sybils join. PeerDAS: Sybils advertise custody of every chunk; a node contacts C advertisers. The grid designs (RDA and TCDA on (12, 64), Table VI) are unaffected: their failure probability depends on the good nodes only. Thin line: δ = 1/4.

grows with the network, exceeds the PUT budget. PeerDAS meets the budgets at every size, as its per-node load does not depend on the network, but it fails robustness. Sybil attack. In PeerDAS, each node advertises the chunks it stores, and a node that samples a chunk receives it from its 8 gossip peers for that chunk. We let the Sybils advertise every chunk and, optimistically for PeerDAS, let every good custodian hold its chunks. A sample contacts C ∈ {8, 16} distinct advertisers, drawn uniformly, and fails if all of them are Sybils. Figure 10 shows the result at N + = 2000. PeerDAS loses robustness from 0.33 Sybils per good node with C = 8 and 0.7 with C = 16, and worsens as more join, while TCDA and RDA keep their exact pfail at every Sybil count. Peer rating and IP limits raise the cost of a Sybil attack but do not bound its effect, so PeerDAS is not fit where robustness comes first. Targeted attack. Suppose the adversary can put bad nodes in a chosen column. We take the two grid designs of Table VI and move all 2000 bad nodes into one column. Robustness is

RDA met

p99 met

3.8 99.6% 12.8 4.2 98% 9.4 4.3 99% 20.3

0% 2% 0%

unaffected: the failure rates are 0.145 for TCDA and 0.144 for RDA, against the exact 0.142. RDA’s GET stays at one hop, and TCDA’s slows only logarithmically, from 4.3 to 8.9 round-trips per attempt. The attacker gains load: the relays of that column must serve all its 2031 nodes, 32 times the usual, and miss the deadline in both designs. This cannot be avoided, but breaking TCDA’s deadline guarantee takes κ/Q times more bad nodes in one column than breaking RDA’s. In practice, cells should be assigned from randomness unknown when node IDs are created, to prevent the attack. 2) Objective O5 - PUT time with coding included: We now time the whole PUT, with the publisher’s row hop and the relays’ coding included. The publisher sends the chunks at 1 Gbit/s in total. Each good relay computes the coded pieces for each column node, at 64 ns per multiply-add in the scalar field of BLS12-381 (Montgomery arithmetic, measured on a virtual machine with 2 cores of a 2.8 GHz Intel Xeon), and uploads them at 25 Mbit/s in random order. Coding runs ahead of the upload, since one core codes at about 60 Mbit/s. For each design and size, we time one random column in each of 300 random networks. Table VII gives the 99th percentile of that time and the fraction of columns served within 4 s, on the same grid for both designs. TCDA meets the deadline in 98% or more of the columns, and its 99th percentile, 3.8 to 4.3 s, misses it by at most a few tenths of a second. RDA meets it in at most 2%: its relays need 9 to 20 s. We do not time PeerDAS: it has no coding, and its load does not depend on the network size, so neither effect applies. 3) Objective O6 - Dynamic network: We consider steady churn and a sudden mass departure of good nodes. For churn, we follow RDA’s simulation: the network grows from 20 good nodes by one per step to NH+ ; then, at every step, the 50 oldest nodes leave and 50 new ones join, so a node stays NH+ /50 steps, one lifetime. At the end of this warm-up, we publish one object and follow its availability for 72 lifetimes, Ethereum’s retention window of 18 days with a node online for 6 hours [9].

14

TABLE VIII (O6) A STORED OBJECT UNDER RDA’ S CHURN SCHEDULE , (12, 64) GRID , δ = 1/4, 72 LIFETIMES , 5 SEEDS . “ROBUST ”: FRACTION OF THE WINDOW IN WHICH ITS FAILURE RATE IS AT MOST δ; “ WORST ”: THE LARGEST FAILURE RATE ; “ LOST ”: COLUMNS WITHOUT hQ HOLDERS AT THE END , OF 64. + NH Design

hQ Robust Worst

Lost

1600 RDA TCDA/Q=17 (optimal) TCDA/Q=4 (Qδ )

1 4 16

60% 60% 0%

0.32 4–12 0.32 4–12 1.00 64

2500 RDA TCDA/Q=12 (optimal) TCDA/Q=2 (Qδ )

1 6 32

100% 100% 0%

0.12 0.12 1.00

1–4 1–4 64

4000 RDA TCDA/Q=7 (optimal) TCDA/Q=2 (Qδ )

1 10 32

100% 100% 100%

0.06 0.06 0.06

0–3 0–3 0–3

The grid is (12, 64), with NH+ ∈ {1600, 2500, 4000}, above its bootstrap of 1543, and 5 seeds. We test the optimal Qmax (Corollary 3) and the smallest δ-robust Qδ (Corollary 2), which has the lowest PUT and storage costs but barely enough good nodes, so little margin against churn. Sustainability of δ-robustness. TCDA at the optimal Q behaves like RDA in every case (Table VIII). At NH+ = 2500 and 4000, both stay δ-robust over the whole window, with worst failure rates of 0.12 and 0.06. At 1600, just above the bootstrap, both are δ-robust 60% of the time, with a worst rate of 0.32; in practice, both need some distance from the bootstrap. With Qδ instead, at 1600 (TCDA/Q=4) and 2500 (TCDA/Q=2), the failure rate exceeds δ within 0.6 lifetimes and every column loses the object; at 4000, TCDA/Q=2 stays robust, with a worst rate of 0.06. The optimal Q thus gives a safe margin that Qδ lacks. Mass departures of good nodes. After 5 lifetimes, 25% to 90% of the good nodes, chosen at random, leave at once, and the network then refills by 50 nodes per step (Figure 11a). Figure 11b shows the failure rate of the stored object at NH+ = 2500, right after the outage and after recovery. Up to 55%, TCDA and RDA degrade but remain δ-robust, and recover fully. At 75%, TCDA keeps a permanent loss but stays below δ after recovery, at 0.20. Near 90%, it loses the object for good, while RDA recovers: one surviving good holder suffices for RDA, whereas TCDA needs several to decode. IX. D ISCUSSION TCDA has limitations. Some cannot be avoided but are justified, and some can be addressed. We also see room for extensions beyond this work. A. Limitations A GET in TCDA takes a second hop into the column: a few round-trips, where RDA needs about one. This is the price of coding and cannot be avoided. We accept it because the PUT, not the GET, is on the critical path: a late PUT delays attestation and slows the whole blockchain, while a slow sample delays only the node that takes it. Also, after a mass departure of more than about 75% of the good nodes, TCDA does not recover its robustness, whereas RDA does. We

+ Fig. 11. (O6) An outage under churn, (12, 64) grid, NH = 2500: (a) network size when 25 to 90% of the good nodes leave at once after 5 lifetimes; (b) failure rate of the stored object, mean of 10 seeds, after recovery (solid, filled marks) and right after the outage (dashed, open marks). Thin line: δ = 1/4.

expect such an outage to be rare in practice. Finally, TCDA’s design needs a bound on the largest network size as input. RDA is limited in the same way, but its bound is much tighter than ours.

B. Open problems A faster GET. The second hop is what slows sampling, so shortening it is the first priority. A collector could query more nodes at once, trading traffic for round-trips, or remember which nodes answered earlier samples and ask those first. We have not studied these options. Repair in mass outage. To address the outage limitation, we can extend TCDA such that good nodes in an affected column can rebuild pieces from the other columns, using the two-dimensional erasure code. This would give TCDA the same tolerance to severe outages as RDA. Beyond the worst case. TCDA sends to every node of a column because it assumes nothing about where the good nodes are. A mild assumption on each column would allow sending to only part of it, and make the PUT cost independent of the network size. Network size as a design choice. Our design takes the number of good nodes and the largest network size as given. Our evaluation suggests that both can be chosen as design variables to make sampling faster; choosing them jointly is an open problem. More routes into a column. A GET fails if its contact cell has no good node. Through a bootstrap node, present in every row and good by assumption, the sampling node could instead use the contact cell of another row. This lowers the failure rate at no cost to the PUT, hence fewer good nodes needed to start. Realistic dynamics. Our dynamic-network model can be made more realistic by studying real session times, targeted departures, and the wall-clock time of sampling. A real-world prototype would be ideal.

15

X. C ONCLUSION A trustless DAS layer must stay robust against any number of Byzantine peers and still deliver each block before validators attest. RDA, the only design with this guarantee, obtains it by full replication, but its PUT cost cannot be tuned, grows with the network, and misses Ethereum’s attestation deadline at the block size we study. This paper shows that coding can replace replication. We have proposed TCDA, the first provably robust coded DAS layer, together with the exact condition under which it is robust. TCDA trades the PUT and storage costs against the GET cost on the same network. At Ethereum’s parameters, this tuning covers a 64-fold range of costs, which serves a wide range of deployment constraints, and TCDA meets the attestation deadline where RDA does not. It maintains availability through an outage of up to about 55% of the good nodes and regains robustness once the network refills after an outage of up to 75%. TCDA stays robust under any number of Sybils, where PeerDAS, in our model, does not. The price is a slower GET than RDA’s. Speeding it up is the first item of our future work, followed by extensions that lower the bootstrap size and relax the bound on the network size, and by real-world experiments. R EFERENCES [1] 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 – FC 2021. Berlin, Heidelberg: Springer-Verlag, 2021, pp. 279–298. [Online]. Available: https://doi.org/10.1007/978-3-662-64331-0 15 [2] M. Hall-Andersen, M. Simkin, and B. Wagner, “Foundations of data availability sampling,” IACR Communications in Cryptology, vol. 1, no. 4, 2025. [3] V. Buterin et al., “EIP-4844: Shard blob transactions,” Ethereum Improvement Proposals, Feb. 2022, no. 4844. [Online]. Available: https://eips.ethereum.org/EIPS/eip-4844 [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 [5] Ethereum Foundation, “PeerDAS,” ethereum.org, 2025. [Online]. Available: https://ethereum.org/roadmap/fusaka/peerdas [6] Ethereum Foundation, “Fusaka mainnet announcement,” Ethereum Foundation Blog, Nov. 2025. [Online]. Available: https://blog.ethereum. org/2025/11/06/fusaka-mainnet-announcement [7] M. Hall-Andersen, M. Simkin, and B. Wagner, “FRIDA: Data availability sampling from FRI,” in Advances in Cryptology – CRYPTO 2024. Berlin, Heidelberg: Springer-Verlag, 2024, pp. 289–324. [Online]. Available: https://doi.org/10.1007/978-3-031-68391-6 9 [8] 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 [9] D. Feist, G. Herold, M. Simkin, and B. Wagner, “Robust distributed arrays: Provably secure networking for data availability sampling,” arXiv:2504.13757, 2025. [Online]. Available: https://arxiv.org/abs/2504. 13757 [10] G. Konstantopoulos and M. Neuder, “Time, slots, and the ordering of events in Ethereum proof-of-stake,” Paradigm, Apr. 2023. [Online]. Available: https://www.paradigm.xyz/writing/ mev-boost-ethereum-consensus [11] P. Jayanthi et al., “EIP-7870: Hardware and bandwidth recommendations,” Ethereum Improvement Proposals, Jan. 2025, no. 7870. [Online]. Available: https://eips.ethereum.org/EIPS/eip-7870 [12] D. P. Minh, H. V. Huu, and D. A. Tran, “Efficient data availability sampling via coded distributed arrays,” in 2026 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2026, pp. 1– 8. [13] 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.

[14] M. Al-Bassam, “LazyLedger: A distributed data availability ledger with client-side smart contracts,” arXiv:1905.09274, 2019. [Online]. Available: https://arxiv.org/abs/1905.09274 [15] M. Yu, S. Sahraei, S. Li, S. Avestimehr, S. Kannan, and P. Viswanath, “Coded Merkle tree: Solving data availability attacks in blockchains,” in Financial Cryptography and Data Security – FC 2020. Berlin, Heidelberg: Springer-Verlag, 2020, pp. 114–134. [Online]. Available: https://doi.org/10.1007/978-3-030-51280-4 8 [16] 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 [17] M. Król, O. Ascigil, S. Rene, E. Rivière, M. Pigaglio, K. Peeroo, V. Stankovic, R. Sadre, and F. Lange, “Data availability sampling in Ethereum: Analysis of P2P networking requirements,” arXiv:2306.11456, 2023. [Online]. Available: https://arxiv.org/abs/2306.11456 [18] P. Maymounkov and D. Mazières, “Kademlia: A peer-to-peer information system based on the XOR metric,” in Peer-to-Peer Systems – IPTPS 2002. Berlin, Heidelberg: Springer-Verlag, 2002, pp. 53–65. [19] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for internet applications,” SIGCOMM Computer Communication Review, vol. 31, no. 4, pp. 149– 160, Aug. 2001. [Online]. Available: https://doi.org/10.1145/964723. 383071 [20] M. Cortes-Goicoechea, C. Kiraly, D. Ryajov, J. L. Muñoz-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, pp. 83–91. [Online]. Available: https://doi.org/10.1145/3688225.3688236 [21] D. Vyzovitis, Y. Napora, D. McCormick, D. Dias, and Y. Psaras, “GossipSub: Attack-resilient message propagation in the Filecoin and ETH2.0 networks,” arXiv:2007.02754, 2020. [Online]. Available: https://arxiv.org/abs/2007.02754 [22] 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, pp. 167–179. [Online]. Available: https://doi.org/10.1145/3721462.3770769 [23] 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, pp. 321–330. [Online]. Available: https://doi.org/10.1145/3704413.3764424 [24] J. R. Douceur, “The Sybil attack,” in Peer-to-Peer Systems – IPTPS 2002. Berlin, Heidelberg: Springer-Verlag, 2002, pp. 251–260. [25] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Transactions on Information Theory, vol. 56, no. 9, pp. 4539–4551, 2010. [26] C. Cachin and S. Tessaro, “Asynchronous verifiable information dispersal,” in 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05), 2005, pp. 191–201. [27] D. Boneh, D. Freeman, J. Katz, and B. Waters, “Signing a linear subspace: Signature schemes for network coding,” in Public Key Cryptography – PKC 2009. Berlin, Heidelberg: SpringerVerlag, 2009, pp. 68–87. [Online]. Available: https://doi.org/10.1007/ 978-3-642-00468-1 5 [28] 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. [29] D. Boneh and X. Boyen, “Short signatures without random oracles,” in Advances in Cryptology – EUROCRYPT 2004, C. Cachin and J. L. Camenisch, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 56–73. [30] D. Feist and D. Khovratovich, “Fast amortized KZG proofs,” Cryptology ePrint Archive, Paper 2023/033, 2023. [Online]. Available: https://eprint.iacr.org/2023/033 [31] Ethereum Foundation, “Fulu: Data availability sampling core and networking specifications,” consensus-specs, 2025. [Online]. Available: https://ethereum.github.io/consensus-specs/specs/fulu/

Related documents

• Efficient Data Availability Sampling via Coded Distributed Arrays#280167
• Enhanced Dynamic Beamwidth Selection-based THz MAC Protocol for Wireless Data Center Networks#984201
• Defending the Data Access Spectrum.#423127
• A survey on reliability in distributed systems#419790
• Distributed Node Consensus Protocol#502046