{"id":"5b973933-5db0-4220-8e4e-e54fa6da3373","arxiv_id":"2504.13757","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"A grid-of-cliques protocol is proven to realize robust distributed arrays: constant-latency store and get with per-node storage of a 1/k2 slice, secure against an unbounded number of malicious nodes.","lead":"This paper defines \"robust distributed arrays,\" a provably secure way to store and retrieve data pieces across a peer-to-peer network, and constructs one whose guarantees need only an absolute minimum number of honest nodes, never an honest majority. It targets the networking layer of Ethereum's data availability sampling, a layer that previously had no formal security definitions.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Join (Figure 3 lines 12–20) waits for join_rsp from every bootstrap node, so one silent malicious bootstrap prevents an honest joiner from ever completing Join; Lemma 1's column claim assumes a step that the pseudocode never reaches.","rationale":"I read the full proof chain Lemmas 1–7 and the probabilistic Lemmas 8–9. Apart from minor denominator typos in Lemma 8's statement and an off-by-one in Lemma 9's interval count that are conservatively absorbed into Theorem 1's final bound, the conditional proof is coherent: if the parties involved are FullyJoined and the good events hold, stores reach the column, data is retained under churn, and gets return the stored symbol within two rounds. The reader's weakest assumption correctly identifies that Definition 8's admissibility contract, especially the requirement of good bootstrap nodes and long overlap, is stronger than the abstract's phrase 'solely the presence of a minimal absolute number of honest nodes.' My main concern is sharper and more internal: even when the admissibility contract is satisfied, the Join pseudocode waits for `join_rsp` from every bootstrap node, including the adversarial additional bootstrap nodes that Definition 1 explicitly permits. A single silent malicious bootstrap therefore blocks every honest joiner from completing Join, so the theorem's proof, which assumes the joiner proceeds at τ_join+2, does not match the protocol as written. This is a liveness/join-completion bug rather than a failure of the probabilistic argument; it should be fixable by adding a timeout or by proceeding on the first valid response, after which the existing lemmas likely go through. Because the fix is straightforward and the theorem's formal statement may still be salvageable for parties that do complete Join, I do not move the verdict to REJECT; the conditional verdict already given is appropriate, with the added condition that the Join procedure must be repaired and the proof aligned with it.","tokens_in":53242,"tokens_out":31376,"duration_ms":294378,"concrete_test":"Run a two-round synchronous simulation of Π_RDA with k1=k2=2, Δ_sub=7: initialize honest parties A and B at time 0; at time 1 schedule an honest party P to join via bootstrap list {A, M}, where M is malicious and sends no messages. Under Figure 3, line 13's guard is never satisfied, so P never executes lines 14–16 (column JoinSubnet calls) or line 20 (terminate Join). Record whether FullyJoined[P, τ] holds at any τ; if it never holds, Lemma 1's column claim fails for this admissible schedule. This isolates the wait-for-all dependency from the rest of the proof and settles whether the pseudocode must be patched (e.g., by proceeding on the first valid join_rsp or after a timeout).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is not in the probabilistic analysis but in the join procedure itself. In Definition 1 (Step 5(c)iv), the adversary is explicitly allowed to add malicious bootstrap nodes to every honest Join call. The Join pseudocode (Figure 3, lines 12–16) sends a `join` message to every such bootstrap node and then blocks on `on receiving (join_rsp, P_c^(i)) from each Pi within 2 rounds` before it can call `JoinSubnet(sid_c, P')` for the column subnet or terminate `Join`. A malicious bootstrap can simply remain silent; the guarded handler never fires, the joining party never becomes `FullyJoined`, and it never reaches the later steps that establish column-subnet membership and data synchronization. Lemma 1's proof assumes that the honest joiner proceeds at time τ_join+2 upon receiving the honest bootstrap's `join_rsp`; with the pseudocode as written, that step is unreachable whenever any supplied bootstrap is adversarial and silent. Consequently Corollary 1, Lemma 3, and Lemma 7 inherit the gap: they are proved for parties that the protocol as specified will not produce in exactly the adversarial runs the theorem must cover. This is an internal inconsistency between the proof and the protocol code, independent of the admissibility contract: the contract guarantees at least one honest bootstrap, but the protocol still requires every adversarial bootstrap to cooperate by responding.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces robust distributed arrays (RDAs), a formal abstraction for the networking layer of data availability sampling, and proposes a concrete construction Π_RDA based on a k1×k2 grid of row and column subnets, random-oracle cell assignment, and a subnet discovery protocol. It defines an admissibility class of join-leave schedules and states Theorem 1, which bounds the failure probability by δ_SD plus union-bound terms over bad columns and bad cells. The proof is organized in two parts: Lemmas 1–7 show deterministically that store/get works when certain good events hold, and Lemmas 8–9 show that admissible schedules make those good events highly likely via Chernoff/union-bound arguments. The paper also provides an example subnet discovery protocol, an efficiency analysis, concrete benchmarks, and simulation code.","tokens_in":53375,"tokens_out":14976,"duration_ms":145056,"significance":"If Theorem 1 held as stated, the contribution would be significant: it would be the first formal robustness treatment of the networking layer for DAS, would avoid any honest-majority assumption, and would achieve constant-round store/get latency with per-node storage m/k2 and roughly sqrt(n) connections. The two-part proof structure is clean, the probabilistic analysis is based on standard Chernoff and union-bound arguments with instantiated parameters rather than fitted constants, and the benchmarks and simulation code are concrete and reproducible. The main obstacle is a blocking flaw in the Join pseudocode that affects the central theorem; I did not find a comparable error in the probabilistic part of the proof.","major_comments":[{"comment":"The Join pseudocode blocks on the guarded handler `on receiving (join_rsp, P(i)_c) from each Pi within 2 rounds` before it calls JoinSubnet(sid_c, ...) or terminates Join. Definition 1, Step 5(c)iv explicitly allows the adversary to add malicious bootstrap nodes P'_1,...,P'_t' to every honest Join call. A malicious bootstrap can simply remain silent, in which case the handler never fires, the joining party never reaches line 15 or line 20, and FullyJoined never holds. Lemma 1's proof assumes that the honest joiner proceeds at time τ_join+2 after receiving the honest bootstrap's join_rsp; that step is unreachable whenever any supplied bootstrap is adversarial and silent. Consequently Corollary 1, Lemma 3, Lemma 4, Lemma 5, Lemma 6, Lemma 7, and Theorem 1 are proved only for parties that the protocol as specified will not produce in exactly the adversarial runs the theorem must cover. This is an internal inconsistency between the pseudocode and the proof, independent of the admissibility contract: Definition 8 guarantees at least one honest bootstrap node, but it does not require adversarial bootstrap nodes to respond. The protocol must be modified (for example, by adding a timeout and processing all responses received within the window, or by explicitly restricting Join inputs to honest bootstrap nodes), and the proof of Lemma 1 must be adjusted accordingly.","section":"§4.3, Figure 3 (lines 12–20); Definition 1 Step 5(c)iv; Lemma 1"}],"minor_comments":[{"comment":"The claim that robustness 'relies solely on the presence of a minimal absolute number of honest nodes' is stronger than Definition 8, which also requires N honest parties to have overlap Δ_overlap at every round and requires each joining party to be given a good honest bootstrap node active Δ_sub before and after the join; please qualify the abstract and introduction accordingly.","section":"Abstract and §1.1"},{"comment":"The proof uses quantities such as |C| = εk2 and the binomial coefficient (k2 choose εk2) for arbitrary real ε ∈ (0,1); either assume εk2 is integral or replace εk2 with floor/ceil so that the union bound over subsets is formally valid.","section":"§4.4.3, Lemma 9"},{"comment":"The benchmarks assume the Appendix B subnet discovery protocol is 'perfectly robust' (δ_SD = 0); please state explicitly that this relies on Theorem 2 and note the dependence on its Δ_sub = 7 assumption in the parameter setting.","section":"§6.1"},{"comment":"The pseudocode for JoinSubnet has a blocking `receive (join_subn_pull_rsp, ...)` with no timeout; for the row-subnet joins in Π_RDA this does not block the main Join thread, but the intended semantics of blocking versus time-bounded receive should be clarified in the model of Section 2.","section":"Appendix B, Figure 9"}],"recommendation":"major_revision","confidential_remarks":"The central proof structure is sound and the paper is a good fit for the venue. The blocking-join issue is the main obstacle; if the authors fix the Join handler and adjust Lemma 1 and its corollaries, I expect the result to be acceptable. The abstract's oversimplification about relying 'solely' on N honest nodes should also be corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know upfront. First, this is the first attempt I know of to give Ethereum-style DAS a formal networking-layer robustness definition and a construction with a real proof, so it deserves attention despite the problems below. Second, there is a load-bearing bug in the Join pseudocode that, as written, makes Theorem 1 false; the proof assumes a step the code never reaches.\n\nWhat is genuinely new: Definition 4 (robust distributed arrays) is a sensible security goal for permissionless storage under adversarial churn, and the row/column subnet decomposition is a clean way to get one-hop queries without global peer lists. The proof structure—separating deterministic correctness from probabilistic good events—is good practice, and the Chernoff/union-bound analysis in Lemmas 8-9 is careful. I did not find an error in the probability part. The self-citations are appropriate, and the related work is honest about PANDAS being a k1=1 special case.\n\nThe soft spot is not the probability; it is the join procedure. Figure 3 lines 12-16 make an honest joiner wait for a join_rsp from every bootstrap node, including the malicious ones that Definition 1 explicitly lets the adversary add to the joiner's bootstrap list. A malicious bootstrap can simply stay silent, the guarded handler never fires, and the joiner never reaches the JoinSubnet or sync steps. Lemma 1's direction for column subnets assumes the joiner receives the honest bootstrap's response at tau_join+2 and calls JoinSubnet then; that step is unreachable in exactly the runs the theorem has to cover. Corollary 1, Lemma 3, and Lemma 7 inherit the gap. The fix is small—proceed on the first valid join_rsp and ignore silent bootstraps—but without that change the central theorem does not hold as stated.\n\nOther issues are minor by comparison: the Section 1.1 example (5000 nodes, 1% storage, 90% availability) is not backed by the theorem's formula as far as I can check; the simulation deliberately omits timing and subnet discovery, so it gives intuition, not evidence; and the admissibility contract quietly assumes long-lived honest bootstrap nodes, which is stronger than the abstract's \"minimal absolute number of honest nodes.\" Also, no concrete comparison with Kelips or PANDAS on bandwidth/latency.\n\nWho this is for: people working on DAS networking or permissionless distributed data structures will want to read it, and the robustness definition may be reusable even if the construction changes. I would not cite the theorem as proven in its current form. It deserves a serious referee—the fix is plausible and the framework is valuable—but the version I read should not be accepted without addressing the Join bug.\n\nRecommendation: send to peer review, with a request for a revised version that fixes Join and reconciles the example numbers. For a reading group, yes.","headline":"Useful formal framework for DAS networking, but a load-bearing bug in the Join pseudocode makes Theorem 1 false as written; the fix is small and the paper deserves review.","tokens_in":54175,"tokens_out":4292,"would_cite":false,"duration_ms":41035,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68M12","68P20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper defines robust distributed arrays and proves a concrete construction that keeps stored data retrievable for data availability sampling even when most participants are malicious.","keywords":["data availability sampling","robust distributed arrays","distributed storage","subnet discovery","random oracle model","permissionless networks","no honest majority","constant-latency storage"],"falsifier":"Run the protocol under a schedule that satisfies the $N$-honest-overlap condition but hands each joining honest party only adversarial bootstrap addresses, so no honest prospective bootstrap node is used; an honest store followed by an honest get of the same predicate-valid symbol should then return $\\bot$ within the allowed delay even though $N$, $T$, $\\varepsilon$, and the honest-overlap condition are all met. Recording such a failure would directly contradict the claim that robustness depends solely on an absolute number of honest parties.","tokens_in":52807,"feed_emoji":"📡","tokens_out":7660,"duration_ms":67164,"temperature":0.7,"pith_summary":"Data availability sampling needs a peer-to-peer layer that actually stores the encoded symbols that clients sample; this paper supplies the first formal security definition for that layer, called a robust distributed array, along with a concrete construction and a proof. The construction splits a file into k2 chunks and assigns every party to one cell of a k1 by k2 grid via a random oracle. A store spreads a symbol within its column subnet, and a get asks every party in the querier's row-and-column cell, so an honest party holding the symbol answers in two rounds. The proof shows that as long as at least N honest parties are online with sufficient overlap, every honest store of a predicate-valid symbol is retrievable by any fully joined honest party, for all but an epsilon-fraction of positions, over a lifetime T, with failure probability delta; the number of malicious parties is irrelevant.","feed_headline":"Distributed storage stays secure even when most nodes are malicious","feed_subtitle":"Arrays spread data across rows and columns so any honest store is retrievable in 2 rounds with no honest majority.","key_machinery":"The load-bearing object is the robust distributed array protocol $\\Pi_{\\mathrm{RDA}}$, instantiated over a $k_1 \\times k_2$ grid of cells. Each party $P$ is placed in cell $\\mathrm{Cell}(P)=H(P)$ by a random oracle, and each row and each column is a subnet maintained by a subnet discovery protocol $\\Pi_{\\mathrm{SD}}$. A store of symbol $i$ first sends to all parties in the caller's cell $(r, \\mathrm{GetColForSymbol}(i))$; each recipient stores it and forwards it into the column subnet. A get asks all parties in the same cell and takes the first response satisfying the position-binding predicate $\\mathrm{Pred}$, meaning a predicate that cannot accept two different symbols for the same handle and index. The security proof separates into a deterministic part, showing that if certain good events hold (subnet discovery works, every column has an honest party with overlap, and every relevant cell has an honest party), then storing and retrieving work, and a probabilistic part, showing that admissible schedules make the bad events unlikely via Chernoff and union bounds together with the binary entropy bound on binomial coefficients.","core_discovery":"On the paper's own terms, the central result is Theorem 1. Fix any position-binding predicate $\\mathrm{Pred}$ and any $(\\delta_{\\mathrm{SD}}, T_{\\mathrm{SD}}, \\Delta_{\\mathrm{sub}}, \\mathcal{S}_{\\mathrm{SD}})$-robust subnet discovery protocol. Then $\\Pi_{\\mathrm{RDA}}$ is $(\\mathrm{Pred}, \\varepsilon, \\delta, T, \\Delta_{\\mathrm{store}}, \\Delta_{\\mathrm{get}}, \\mathcal{S})$-robust under $(N, \\Delta_{\\mathrm{overlap}}, \\mathcal{S}_{\\mathrm{SD}})$-admissible schedules, with $\\Delta_{\\mathrm{store}}=\\Delta_{\\mathrm{get}}=2$, $T=T_{\\mathrm{SD}}-1$, and $\\delta \\le \\delta_{\\mathrm{SD}} + \\lceil (T+2)/(\\Delta_{\\mathrm{overlap}}-\\Delta_{\\mathrm{overlap,min}}+1)\\rceil \\cdot (k_1 2^{h(\\varepsilon)k_2} e^{-\\varepsilon N/k_1} + k_2 e^{-N/k_2})$, where $h(\\varepsilon)$ is the binary entropy function. In plain terms: any honest store of a symbol $x$ satisfying $\\mathrm{Pred}$ at position $i$ by a fully joined party is retrievable by any fully joined honest party within two rounds, for all but an $\\varepsilon$-fraction of positions, over the whole lifetime $T$, with failure probability at most $\\delta$, and this holds no matter how many malicious parties exist. The construction that achieves this is the grid protocol $\\Pi_{\\mathrm{RDA}}$: a $k_1 \\times k_2$ array of cells, each party assigned to one cell by a random oracle, with row and column subnets maintained by the underlying subnet discovery protocol.","pith_inferences":["If the bootstrap-liveness premise is not met in practice, the theorem does not apply; a deployment would need an external way to guarantee honest bootstrap addresses or a fallback like a trusted bootstrap set. This is an editorial consequence the paper leaves implicit.","The paper's discussion of virtual nodes suggests a design lever: letting each party simulate $K$ cells effectively replaces $N$ by $NK$ in the bounds, at the cost of storage, which is an immediate practical extension of the proof's probabilistic argument.","The two-round get hinges on each party maintaining connections to all peers in its own row and column; in very large networks this per-node connection count grows like $n_{\\max}/k_1 + n_{\\max}/k_2$, so the primitive is best suited to systems that prefer bandwidth over polylogarithmic latency.","A natural testable extension is to weaken the good-bootstrap-node requirement to a randomized bootstrap sampling model and measure how the failure probability degrades; the current theorem is all-or-nothing on this condition."],"forward_implications":["If Theorem 1 is right, a data availability sampling deployment can use this construction as its networking layer and keep the guarantee that every honest store of a predicate-valid symbol is retrievable within two rounds by any fully joined honest party, except on an $\\varepsilon$-fraction of positions.","The construction works without any honest-majority assumption: the failure probability depends on the absolute number $N$ of honest parties and the grid parameters, not on the total number of participants.","The benchmarks in the paper show concrete parameter settings, such as 5,000 honest nodes each storing 1% of the data and connected to 10% of peers, provably keeping 90% of the data available.","The underlying subnet discovery protocol can be instantiated with the simple Appendix B protocol, which is perfectly robust ($\\delta_{\\mathrm{SD}}=0$) with $\\Delta_{\\mathrm{sub}}=7$, so the theorem is not vacuous.","Store and get latency are constant: a get returns within two rounds or reports failure at round three, a join completes after $\\Delta_{\\mathrm{sub}}+2$ rounds, and each node stores only $m/k_2$ symbols."],"supporting_citations":[{"why":"Introduced data availability sampling, the application that motivates the robust distributed array model.","marker":"[ASBK21]"},{"why":"Formalized DAS with an oracle model and position-binding predicates, which the robustness definition reuses.","marker":"[HASW23]"},{"why":"PANDAS, the closest prior networking proposal, is described as a one-row special case and supplies the contrast that motivates the grid construction.","marker":"[AKP+24]"},{"why":"Informally identified DAS networking requirements and why classical DHTs fall short, which the formal model is built to address.","marker":"[KAR+23]"}],"fun_headline_variants":["Secure DAS without honest majority","Data retrieval in 2 rounds, even with malicious majority","Robust arrays: no honest majority required","Provably secure networking for data availability","Distributed arrays that survive hostile networks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee collapses if the join-leave schedule does not give every honest joining party an honest bootstrap node that is active for $\\Delta_{\\mathrm{sub}}$ rounds before and $\\Delta_{\\mathrm{sub}}$ rounds after the join, because the joining party then cannot be shown to enter its row and column subnets, and the storage and retrieval lemmas have no purchase; the paper's slogan that only a minimal absolute number of honest nodes is needed hides this stronger bootstrap liveness condition.","fun_headline_variants_meta":{"raw":{"variants":["Secure DAS without honest majority","Data retrieval in 2 rounds, even with malicious majority","Robust arrays: no honest majority required","Provably secure networking for data availability","Distributed arrays that survive hostile networks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000451,"raw_usage":{"total_tokens":2370,"prompt_tokens":1145,"completion_tokens":1225,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":761,"completion_tokens_details":{"reasoning_tokens":1160}},"tokens_in":761,"tokens_out":1225,"duration_ms":8063,"temperature":1.0,"reasoning_tokens":1160,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:03:17.582567+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the protocol under a schedule that satisfies the $N$-honest-overlap condition but hands each joining honest party only adversarial bootstrap addresses, so no honest prospective bootstrap node is used; an honest store followed by an honest get of the same predicate-valid symbol should then return $\\bot$ within the allowed delay even though $N$, $T$, $\\varepsilon$, and the honest-overlap condition are all met. Recording such a failure would directly contradict the claim that robustness depends solely on an absolute number of honest parties.","supporting_citations":[],"review_version":1}