Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908333968982016 |
|---|---|
| author | Feist, Dankrad Herold, Gottfried Simkin, Mark Wagner, Benedikt |
| author_facet | Feist, Dankrad Herold, Gottfried Simkin, Mark Wagner, Benedikt |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13757 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling Feist, Dankrad Herold, Gottfried Simkin, Mark Wagner, Benedikt Data Structures and Algorithms Distributed, Parallel, and Cluster Computing 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. |
| title | Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.13757 |