Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling

Data Availability Sampling (DAS), a central component of Ethereum's roadmap, enables clients to verify data availability without requiring any single client to download the entire dataset. DAS operates by having clients randomly retrieve individual symbols of erasure-encoded data from a peer-to-peer network. While the cryptographic and encoding aspects of DAS have recently undergone formal analysis, the peer-to-peer networking layer remains underexplored, with a lack of security definitions and efficient, provably secure constructions.

In this work, we address this gap by introducing a novel distributed data structure that can serve as the networking layer for DAS, which we call robust distributed arrays. That is, we rigorously define a robustness property of a distributed data structure in an open permissionless network, that mimics a collection of arrays.

Then, we give a simple and efficient construction and formally prove its robustness. Notably, every individual node is required to store only small portions of the data, and accessing array positions incurs minimal latency. The robustness of our construction relies solely on the presence of a minimal absolute number of honest nodes in the network. In particular, we avoid any honest majority assumption. Beyond DAS, we anticipate that robust distributed arrays can have wider applications in distributed systems.

Blockchains are distributed systems that implement replicated state machines, whose states are regularly updated through distributed consensus protocols. In a nutshell, these systems provide two main guarantees called liveness and safety. The former ensures the continuous progression of the machine's state, while the latter guarantees that the machine never transitions into an invalid state.

Popular blockchains, such as Bitcoin and Ethereum, are designed to offer a strong form of safety. They maintain the integrity of their state even when the majority of parties running the consensus protocol are acting maliciously. To achieve such a strong form of safety, all network participants need to individually verify every state transition proposed by the consensus protocol. Invalid state transitions are rejected by the network participants, regardless of whether they have been approved by consensus. While this approach provides strong safety guarantees, it also imposes heavy requirements on all network participants in terms of bandwidth, computing power, and storage, since every participant needs to download and verify every single state transition.

As blockchains grow in popularity and adoption, the size of their state continues to increase and requiring full replication of the state machine among all network participants is becoming a performance bottleneck. Towards building scalable blockchains, we would like to reduce the burden placed on the network participants, while maintaining the strong safety guarantees blockchains currently provide. Ideally, one would like a solution which does not require network participants to download all state related data to verify the validity of each state transition.

At first glance, succinct non-interactive arguments of knowledge (SNARKs) [Kil92, Mic00, Gro16] appear to provide a solution to the above problem. Whenever consensus proposes a new state transition, it can be accompanied by a succinct proof, attesting to the validity of the transition. Network participants can verify the succinct proof, without needing to download all data associated with the state transition itself. While this solution addresses the question of how to ensure the validity of state transitions, it does not address the question of how to ensure availability of all state related data. In addition to succinct proofs, the outlined approach requires a way for network participants to collectively check that all data is in principle available, preferably without requiring them to download the data in full.

have introduced the concept of data availability sampling (DAS), which was subsequently formalized by Hall-Andersen, Simkin, and Wagner [HASW23] and then studied by several other works [HASW24, WZ24, EMA25, EA25]. In the DAS setting, a potentially malicious party encodes a data block and provides oracle access to the encoding. A set of independent verifiers randomly probe the encoding through the provided oracle. If the verifying parties independently accept the responses they receive from the adversarially controlled oracle, then the security properties of DAS ensure that the parties could pool their individual transcripts together to reconstruct some well-defined data.

The works on DAS mentioned above focus only on how to encode the data, but do not study how to store it. In a real-world setting, the encoded data would not be stored inside a hypothetical oracle, but rather within a distributed system. Network participants should be able to store new encodings or individual symbols that they have reconstructed, and query individual symb