Pith. sign in

REVIEW 1 major objections 4 minor 56 references

Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling

T0 review · 1 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2504.13757 v2 pith:BG6CXNKP submitted 2025-04-18 cs.DS cs.DC

Dankrad Feist , Gottfried Herold , Mark Simkin , Benedikt Wagner This is my paper · ORCID
classification cs.DScs.DC MSC 68M1468M1268P20
keywords dataavailabilitysamplingrobustdistributedarraysstoragesubnetdiscoveryrandomoraclemodelpermissionlessnetworksnohonestmajorityconstant-latency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

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.

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 (1)
  1. [§4.3, Figure 3 (lines 12–20); Definition 1 Step 5(c)iv; Lemma 1] 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.
minor comments (4)
  1. [Abstract and §1.1] 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.
  2. [§4.4.3, Lemma 9] 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.
  3. [§6.1] 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.
  4. [Appendix B, Figure 9] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 1's bound follows from random-oracle concentration plus a modular subnet-protocol premise; the self-citations are background DAS framing and are not load-bearing.

full rationale

The derivation chain for Theorem 1 is self-contained. The composition theorem takes the (robust) subnet discovery protocol of Definition 6 as a modular premise and derives the RDA robustness of Definition 4 via an explicit lemma chain (Lemma 1: join; Lemma 3: store; Lemma 4: retention; Lemma 6: get; Lemma 7: combination) that uses only the stated good events and the position-binding property of Pred, the latter applied directly in Lemma 2, which is proven in-paper rather than imported. The probabilistic error terms k1*2^(h(eps)*k2)*e^(-eps*N/k1) (bad cells) and k2*e^(-N/k2) (bad columns) are derived in Lemmas 8-9 from Chernoff and entropy bounds over the random-oracle cell assignment Cell(P)=H(P); N, k1, k2, eps, and Delta_overlap are instantiated environmental/design parameters, not fitted values. Section 6.1 uses the theorem's bound to choose parameters at a target delta <= 1e-9, and Section 6.2's simulation is explicitly labeled intentionally simplified and is not presented as validating the theorem. The self-citations [HASW23], [HASW24], [WZ24] share authors with the present paper (Simkin, Wagner), but they provide DAS background and the position-binding convention (Remark 2); no load-bearing theorem is quoted from them, and Theorem 1 accepts Pred as an arbitrary predicate satisfying a stated property. Appendix B supplies a concrete Pi_SD with delta_SD = 0 and a self-contained proof (Theorem 2), so the end-to-end guarantee does not reduce by construction to any fitted constant or cited result. The abstract's phrase 'relies solely on the presence of a minimal absolute number of honest nodes' oversimplifies Definition 8's stricter admissibility contract (good bootstrap nodes active Delta_sub before and after each join), and the Join pseudocode's blocking wait for join_rsp from every bootstrap node (Figure 3, line 13) can be stalled by one silent malicious bootstrap; both are correctness and framing concerns, not circularity. No prediction stated in the paper is equivalent by construction to its own inputs. Minor self-citation only, hence score 1.

Assumptions & free parameters 7 free parameters · 7 assumptions · 2 invented entities

The central theorem rests on environment axioms rather than fitted constants: random-oracle cell assignment, synchronous authenticated delivery, a position-binding predicate, a robust subnet building block, honest initial parties, and the admissibility contract (N honest parties with Delta_overlap overlap plus good bootstrap nodes). The free parameters (k1, k2, epsilon, N, Delta_overlap, Delta_sub, Delta_sync, delta target) are designer choices instantiated in the benchmarks; the error bound is derived, not fitted. The most fragile premise is the good-bootstrap condition: "solely the absolute number of honest nodes" oversimplifies, because the environment must also supply long-lived honest bootstrap nodes at every join. Appendix B's concrete subnet instantiation (delta_SD = 0, Delta_sub = 7) is the one place the paper independently grounds the modular assumption.

free parameters (7)
  • k1 (number of rows) = Benchmarks explore k1 from 1 to about 10^2; trade-off curves in Figures 5-6
    Design parameter of the grid. Larger k1 cuts per-node connections but tightens the cell-occupancy bound; it is chosen per deployment, not fixed by the derivation.
  • k2 (number of columns) = Benchmarks use k2 up to 10^3; example uses k2 = 100
    Sets per-node storage to m/k2 and the column-failure term k2 * e^(-N/k2); a free design knob.
  • epsilon (corrupted-fraction target) = 0.10 and 0.05 in benchmark plots
    Target bound on corruption-set size; appears in the exponent of the cell term via h(epsilon); chosen by the designer.
  • N (guaranteed honest parties with overlap) = 1,000 to 100,000 in benchmark plots
    Environment guarantee, not a fitted constant; the entire robustness claim is monotone in N.
  • Delta_overlap (honest overlap requirement) = Assumed 6 hours, about 5,400 rounds at 4 s per round
    Assumed honest-churn bound in benchmarks; sets the time-interval union bound in Theorem 1.
  • Delta_sub and Delta_sync (timing constants) = Delta_sub = 7 (Appendix B); Delta_sync >= 2, about 15 minutes in benchmarks (Delta_overlap,min = 450)
    Protocol and subnet timing constants; the guarantee holds for any values, but error and admissibility scale with them.
  • delta target (failure probability) = At most 10^-9 in benchmark plots
    Target failure probability used for the trade-off curves, not a fit; the Section 1.1 example states no delta.
assumptions (7)
  • domain assumption Random oracle H assigns each party a uniform cell in [k1] x [k2], and the join-leave schedule is fixed before the oracle is instantiated
    Section 2 and Figure 2 (Cell(P) = H(P)). All probabilistic content of Lemmas 8-9 is over this assignment; a real hash function does not give uniform independent cells.
  • domain assumption Synchronous network with authenticated point-to-point channels, every message delivered exactly one round later, synchronized clocks
    Section 2, Network Model. Latency claims (get in 3 rounds, Delta_sub = 7) and all join/store timing depend on this; real P2P delivery is asynchronous and lossy. Remark 6 admits the one-round delivery is unrealistic for large sync payloads.
  • domain assumption Pred is position-binding
    Remark 2, inherited from the DAS literature (HASW23). Needed in Lemma 2 (no overwrite) and to guarantee the first valid get-response is the stored symbol rather than a competing valid symbol.
  • domain assumption The underlying subnet discovery protocol is (delta_SD, T_SD, Delta_sub, S_SD)-robust
    Theorem 1 is conditional on this modular assumption. The paper supplies one instantiation (Appendix B, Theorem 2, delta_SD = 0, Delta_sub = 7), but the main theorem is stated for any such Pi_SD.
  • domain assumption All initially active parties are honest
    Definition 1 and Remark 1. Required so CreatedSubnet events (Definition 6) hold at tau = 0. Remark 1 states it can be weakened to "initial honest parties know each other" with an appropriate subnet instantiation.
  • domain assumption Admissibility: the schedule guarantees N honest parties with overlap Delta_overlap, respects bootstrap nodes, and uses good bootstrap nodes
    Definition 8. This is the load-bearing environment contract discussed in weakest_assumption; it is not guaranteed by the protocol and is stronger than a bare honest headcount.
  • standard math Chernoff bound, entropy bound on binomial coefficients, and (1 - x)^N < e^(-xN)
    Appendix A, Lemmas 10-13; used for the union-bound probabilities in Lemmas 8-9.
invented entities (2)
  • Robust distributed arrays with the robustness notion of Definition 4
    purpose: Formal contract for a DAS networking layer: store/get with epsilon-corrupted positions, delays Delta_store and Delta_get, and failure delta over lifetime T
    A new definitional abstraction. Its only evidence is the theorem proving a specific protocol meets it; there is no external benchmark or falsifiable prediction outside the paper.
  • (Robust) subnet discovery protocol abstraction of Definition 5
    purpose: Building block that maintains row and column cliques; separates clique-maintenance from the RDA proof
    A modeling abstraction, but Appendix B gives a concrete instantiation with its own proof (Theorem 2, delta_SD = 0, Delta_sub = 7), so it is not vacuous.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling." pith.science (2026). https://pith.science/paper/BG6CXNKP

@misc{pith2026250413757,
  author       = {Pith},
  title        = {Pith review of: Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BG6CXNKP}},
  note         = {Machine review of arXiv:2504.13757}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2504.13757 by the authors.

Figure 1
Figure 1. Visualization of our protocol ΠRDA with k1 = 4 rows and k2 = 5 columns. Each row and column represents a subnet (i.e., clique) for the subnet discovery protocol ΠSD as per Definition 5. Parties in column j ∈ [k2] store the jth chunk of the data. For simplicity, we assume that the number of symbols is m = k2 in this visualization. Left: node in column subnet 2 and row subnet 3 storing a symbol that must be stored in … view at source ↗
Figure 2
Figure 2. Initialization and helper algorithms for our dist [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Joining instructions for our distributed array pr [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Interfaces Store and Get of ΠRDA with file space Σ m and handle space H, for a predicate Pred: H × [m] × Σ → {0, 1}. It makes use of a subnet discovery protocol ΠSD for M = k1 + k2 and a random oracle H: {0, 1} ∗ → [k1] × [k2]. The party that is executing the instructi…
Figure 5
Figure 5. Figure 5: Trade-off between k1 (number of rows) and k2 (number of columns) and resulting complexities for ε = 0.1. The complexities show the expected total message complexity when an honest party calls the respective interfaces. All plots assume δ ≤ 10−9 , and the given N. Scale…
Figure 6
Figure 6. Figure 6: Trade-off between k1 (number of rows) and k2 (number of columns) and resulting complexities for ε = 0.05. The complexities show the expected total message complexity when an honest party calls the respective interfaces. All plots assume δ ≤ 10−9 and the given N. Scales…
Figure 7
Figure 7. Figure 7: Simulation results for k2 = 100 columns and different number of rows k1. We simulated a join-leave schedule that leads to 2,500 honest parties (after a warmup phase) and each party staying for 50 time steps. 7 More Related Work In this section, we provide a more extens…
Figure 8
Figure 8. Figure 8: Visualization of joining a subnet in our simple sub [PITH_FULL_IMAGE:figures/full_fig_p043_8.png]
Figure 9
Figure 9. Figure 9: A subnet discovery protocol ΠSD for M subnets. The party that is executing the instructions is referred to as Pself. Robustness Analysis. In the next definition, we introduce a shorthand notation to denote that a party P knows another party P ′ as part of a subnet sid …
Figure 10
Figure 10. Figure 10: Table of events used throughout the paper. Events [PITH_FULL_IMAGE:figures/full_fig_p047_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 51 canonical work pages

  1. [1]

    $\scriptstyle{BASALT}$: A Rock-Solid Foundation for Epidemic Consensus Algorithms in Very Large, Very Open Networks

    Alex Auvolat, Y \' e rom - David Bromberg, Davide Frey, and Fran c ois Ta \" ani. BASALT: A rock-solid foundation for epidemic consensus algorithms in very large, very open networks. CoRR , abs/2102.04063, 2021

    work page Pith review arXiv 2021

  2. [2]

    Uniform and ergodic sampling in unstructured peer-to-peer systems with malicious nodes

    Emmanuelle Anceaume, Yann Busnel, and S \' e bastien Gambs. Uniform and ergodic sampling in unstructured peer-to-peer systems with malicious nodes. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings , volume 649...

    work page 2010

  3. [3]

    Locally self-adjusting tree networks

    Chen Avin, Bernhard Haeupler, Zvi Lotker, Christian Scheideler, and Stefan Schmid. Locally self-adjusting tree networks. In 27th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2013, Cambridge, MA, USA, May 20-24, 2013 , pages 395--406. IEEE Computer Society, 2013

    work page 2013

  4. [4]

    P A N D A S : A P ractical A pproach for N ext- G eneration D ata A vailability S ampling

    Onur Ascigil, Michał Król, Matthieu Pigaglio, Sergi Reñe, Etienne Rivière, and Ramin Sadre. P A N D A S : A P ractical A pproach for N ext- G eneration D ata A vailability S ampling. https://ethresear.ch/t/pandas-a-practical-approach-for-next-generation-data-availability-sampling/20426, 2024. [Accessed 21-02-2025]

    work page 2024

  5. [5]

    Skip graphs

    James Aspnes and Gauri Shah. Skip graphs. In 14th SODA , pages 384--393. ACM-SIAM , January 2003

    work page 2003

  6. [6]

    a ki, Arto Lepist \

    Baruch Awerbuch and Christian Scheideler. Group spreading: A protocol for provably secure distributed name service. In Josep D \' az, Juhani Karhum \" a ki, Arto Lepist \" o , and Donald Sannella, editors, Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings , volume 3142 of Lecture ...

    work page 2004

  7. [7]

    Robust random number generation for peer-to-peer systems

    Baruch Awerbuch and Christian Scheideler. Robust random number generation for peer-to-peer systems. In Alexander A. Shvartsman, editor, Principles of Distributed Systems, 10th International Conference, OPODIS 2006, Bordeaux, France, December 12-15, 2006, Proceedings , volume 4305 of Lecture Notes in Computer Science , pages 275--289. Springer, 2006

    work page 2006

  8. [8]

    Towards a scalable and robust DHT

    Baruch Awerbuch and Christian Scheideler. Towards a scalable and robust DHT . In Phillip B. Gibbons and Uzi Vishkin, editors, SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30 - August 2, 2006 , pages 318--327. ACM , 2006

    work page 2006

Show all 56 references
  1. [9]

    Towards scalable and robust overlay networks

    Baruch Awerbuch and Christian Scheideler. Towards scalable and robust overlay networks. In John R. Douceur and Roger Wattenhofer, editors, 6th International workshop on Peer-To-Peer Systems, IPTPS 2007, Bellevue, WA, USA, February 26-27, 2007 , 2007

    2007

  2. [10]

    Fraud and data availability proofs: Detecting invalid blocks in light clients

    Mustafa Al-Bassam , Alberto Sonnino, Vitalik Buterin, and Ismail Khoffi. Fraud and data availability proofs: Detecting invalid blocks in light clients. In Nikita Borisov and Claudia D \'i az, editors, FC 2021, Part II , volume 12675 of LNCS , pages 279--298. Springer, Berlin, ...

    2021

  3. [11]

    The expansion and mixing time of skip graphs with applications

    James Aspnes and Udi Wieder. The expansion and mixing time of skip graphs with applications. Distributed Comput. , 21(6):385--393, 2009

    2009

  4. [12]

    Constructing distributed doubly linked lists without distributed locking

    Kota Abe and Mikio Yoshiday. Constructing distributed doubly linked lists without distributed locking. In Yong Liu, Marinho P. Barcellos, Jay R. Lorch, and Anyi Wang, editors, 2015 IEEE International Conference on Peer-to-Peer Computing, P2P 2015, Boston, MA, USA, September 21...

    2015

  5. [13]

    Brahms: byzantine resilient random membership sampling

    Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, and Alexander Shraer. Brahms: byzantine resilient random membership sampling. In Rida A. Bazzi and Boaz Patt - Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Com...

    2008

  6. [14]

    Better space-time-robustness trade-offs for set reconciliation

    Djamal Belazzougui, Gregory Kucherov, and Stefan Walzer. Better space-time-robustness trade-offs for set reconciliation. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, ICALP 2024 , volume 297 of LIPIcs , pages 20:1--20:19. Schloss Dagstuhl, July 2024

    2024

  7. [15]

    S/kademlia: A practicable approach towards secure key-based routing

    Ingmar Baumgart and Sebastian Mies. S/kademlia: A practicable approach towards secure key-based routing. In 13th International Conference on Parallel and Distributed Systems, ICPADS 2007, Hsinchu, Taiwan, December 5-7, 2007 , pages 1--8. IEEE Computer Society, 2007

    2007

  8. [16]

    Random oracles are practical: A paradigm for designing efficient protocols

    Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, ACM CCS 93 , pages 62--73. ACM Press, November 1993

    1993

  9. [17]

    Skip suffix array: A partial match retrieval method on structured overlay networks

    Ryohei Banno and Kazuyuki Shudo. Skip suffix array: A partial match retrieval method on structured overlay networks. In 2020 International Conference on Information Networking, ICOIN 2020, Barcelona, Spain, January 7-10, 2020 , pages 487--492. IEEE , 2020

    2020

  10. [18]

    Ganesh, Antony I

    Miguel Castro, Peter Druschel, Ayalvadi J. Ganesh, Antony I. T. Rowstron, and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In David E. Culler and Peter Druschel, editors, 5th Symposium on Operating System Design and Implementation (OSDI 2002), B...

    2002

  11. [19]

    N umber of peers you need for peer sampling in P eer D A S ( E I P -7594)

    Suphanat Chunhapanya. N umber of peers you need for peer sampling in P eer D A S ( E I P -7594). https://ethresear.ch/t/number-of-peers-you-need-for-peer-sampling-in-peerdas-eip-7594/20562, 2024. [Accessed 25-02-2025]

    2024

  12. [20]

    Scalability limitations of kademlia dhts when enabling data availability sampling in E thereum

    Mikel Cortes - Goicoechea, Csaba Kir \' a ly, Dmitriy Ryajov, Jose Luis Mu \ n oz - Tapia, and Leonardo Bautista - Gomez. Scalability limitations of kademlia dhts when enabling data availability sampling in E thereum. CoRR , abs/2402.09993, 2024

    2024 arXiv

  13. [21]

    The accidental computer: Polynomial commitments from data availability

    Alex Evans and Guillermo Angeris. The accidental computer: Polynomial commitments from data availability. 2025

    2025

  14. [22]

    ZODA : Zero-overhead data availability

    Alex Evans, Nicolas Mohnblatt, and Guillermo Angeris. ZODA : Zero-overhead data availability. Cryptology ePrint Archive, Paper 2025/034, 2025

    2025

  15. [23]

    Censorship resistant peer-to-peer content addressable networks

    Amos Fiat and Jared Saia. Censorship resistant peer-to-peer content addressable networks. In David Eppstein, editor, 13th SODA , pages 94--103. ACM-SIAM , January 2002

    2002

  16. [24]

    Distributed arrays: A P2P data structure for efficient logical arrays

    Daisuke Fukuchi, Christian Sommer, Yuichi Sei, and Shinichi Honiden. Distributed arrays: A P2P data structure for efficient logical arrays. In INFOCOM 2009. 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications ...

    2009

  17. [25]

    Making chord robust to byzantine attacks

    Amos Fiat, Jared Saia, and Maxwell Young. Making chord robust to byzantine attacks. In Gerth St lting Brodal and Stefano Leonardi, editors, Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings , volume 3669 of Lecture ...

    2005

  18. [26]

    Birman, Prakash Linga, Alan J

    Indranil Gupta, Kenneth P. Birman, Prakash Linga, Alan J. Demers, and Robbert van Renesse. Kelips: Building an efficient and stable P2P DHT through increased memory and background overhead. In M. Frans Kaashoek and Ion Stoica, editors, Peer-to-Peer Systems II, Second Internati...

    2003

  19. [27]

    Highly dynamic distributed computing with byzantine failures

    Rachid Guerraoui, Florian Huc, and Anne - Marie Kermarrec. Highly dynamic distributed computing with byzantine failures. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013 ,...

    2013

  20. [28]

    Gonz \' a lez - Beltr \' a n, Peter Milligan, and Paul Sage

    Alejandra N. Gonz \' a lez - Beltr \' a n, Peter Milligan, and Paul Sage. Range queries over skip tree graphs. Comput. Commun. , 31(2):358--374, 2008

    2008

  21. [29]

    Goodrich, Michael J

    Michael T. Goodrich, Michael J. Nelson, and Jonathan Z. Sun. The rainbow skip graph: a fault-tolerant constant-degree distributed data structure. In 17th SODA , pages 384--393. ACM-SIAM , January 2006

    2006

  22. [30]

    On the size of pairing-based non-interactive arguments

    Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-S \' e bastien Coron, editors, EUROCRYPT 2016, Part II , volume 9666 of LNCS , pages 305--326. Springer, Berlin, Heidelberg, May 2016

    2016

  23. [31]

    Foundations of data availability sampling

    Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner. Foundations of data availability sampling. Cryptology ePrint Archive, Paper 2023/1079, 2023. https://eprint.iacr.org/2023/1079

    2023

  24. [32]

    FRIDA : Data availability sampling from FRI

    Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner. FRIDA : Data availability sampling from FRI . In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VI , volume 14925 of LNCS , pages 289--324. Springer, Cham, August 2024

    2024

  25. [33]

    Locally self-adjusting skip graphs

    Sikder Huq and Sukumar Ghosh. Locally self-adjusting skip graphs. In Kisung Lee and Ling Liu, editors, 37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017, Atlanta, GA, USA, June 5-8, 2017 , pages 805--815. IEEE Computer Society, 2017

    2017

  26. [34]

    Jaiyeola, Kyle Patron, Jared Saia, Maxwell Young, and Qian M

    Mercy O. Jaiyeola, Kyle Patron, Jared Saia, Maxwell Young, and Qian M. Zhou. Tiny groups tackle byzantine adversaries. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018 , pages 1030--1039. IEEE Computer...

    2018

  27. [35]

    Richa, Christian Scheideler, Stefan Schmid, and Hanjo T \"a ubig

    Riko Jacob, Andr \'e a W. Richa, Christian Scheideler, Stefan Schmid, and Hanjo T \"a ubig. A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In Srikanta Tirthapura and Lorenzo Alvisi, editors, 28th ACM PODC , pages 131--140. ACM , August 2009

    2009

  28. [36]

    Data availability sampling in ethereum: Analysis of P2P networking requirements

    Michal Kr \' o l, Onur Ascigil, Sergi Rene, Etienne Rivi \` e re, Matthieu Pigaglio, Kaleem Peeroo, Vladimir Stankovic, Ramin Sadre, and Felix Lange. Data availability sampling in ethereum: Analysis of P2P networking requirements. CoRR , abs/2306.11456, 2023

    2023 arXiv

  29. [37]

    A note on efficient zero-knowledge proofs and arguments (extended abstract)

    Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In 24th ACM STOC , pages 723--732. ACM Press, May 1992

    1992

  30. [38]

    Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S

    David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, and Daniel Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In 29th ACM STOC , pages 654--663. ACM Press, May 1997

    1997

  31. [39]

    Computationally sound proofs

    Silvio Micali. Computationally sound proofs. SIAM J. Comput. , 30(4):1253--1298, 2000

    2000

  32. [40]

    Kademlia: A peer-to-peer information system based on the XOR metric

    Petar Maymounkov and David Mazi \` e res. Kademlia: A peer-to-peer information system based on the XOR metric. In Peter Druschel, M. Frans Kaashoek, and Antony I. T. Rowstron, editors, Peer-to-Peer Systems, First International Workshop, IPTPS 2002, Cambridge, MA, USA, March 7-...

    2002

  33. [41]

    Set reconciliation with nearly optimal communication complexity

    Yaron Minsky, Ari Trachtenberg, and Richard Zippel. Set reconciliation with nearly optimal communication complexity. IEEE Trans. Inf. Theory , 49(9):2213--2218, 2003

    2003

  34. [42]

    Probability and Computing: Randomized Algorithms and Probabilistic Analysis

    Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press, 2005

    2005

  35. [43]

    A simple fault tolerant distributed hash table

    Moni Naor and Udi Wieder. A simple fault tolerant distributed hash table. In M. Frans Kaashoek and Ion Stoica, editors, Peer-to-Peer Systems II, Second International Workshop, IPTPS 2003, Berkeley, CA, USA, February 21-22,2003, Revised Papers , volume 2735 of Lecture Notes in ...

    2003

  36. [44]

    Antony I. T. Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Rachid Guerraoui, editor, Middleware 2001, IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, Germany, No...

    2001

  37. [45]

    Karp, and Scott Shenker

    Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard M. Karp, and Scott Shenker. A scalable content-addressable network. In Rene L. Cruz and George Varghese, editors, Proceedings of the ACM SIGCOMM 2001 Conference on Applications, Technologies, Architectures, and Protocols fo...

    2001

  38. [46]

    P eer D A S -- a simpler D A S approach using battle-tested p2p components

    Danny Ryan. P eer D A S -- a simpler D A S approach using battle-tested p2p components. https://ethresear.ch/t/peerdas-a-simpler-das-approach-using-battle-tested-p2p-components/16541, 2023. [Accessed 25-02-2025]

    2023

  39. [47]

    How to spread adversarial nodes? Rotate ! In Harold N

    Christian Scheideler. How to spread adversarial nodes? Rotate ! In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC , pages 704--713. ACM Press, May 2005

    2005

  40. [48]

    Freedman

    Siddhartha Sen and Michael J. Freedman. Commensal cuckoo: secure group partitioning for large-scale services. ACM SIGOPS Oper. Syst. Rev. , 46(1):33--39, 2012

    2012

  41. [49]

    Karger, M

    Ion Stoica, Robert Tappan Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Rene L. Cruz and George Varghese, editors, Proceedings of the ACM SIGCOMM 2001 Conference on Applications, T...

    2001

  42. [50]

    A documentation of ethereum’s PeerDAS

    Benedikt Wagner and Arantxa Zapico. A documentation of ethereum’s PeerDAS . Cryptology ePrint Archive, Paper 2024/1362, 2024

    2024

  43. [51]

    Practical rateless set reconciliation

    Lei Yang, Yossi Gilad, and Mohammad Alizadeh. Practical rateless set reconciliation. In Proceedings of the ACM SIGCOMM 2024 Conference, ACM SIGCOMM 2024, Sydney, NSW, Australia, August 4-8, 2024 , pages 595--612. ACM , 2024

    2024

  44. [52]

    Towards practical communication in byzantine-resistant dhts

    Maxwell Young, Aniket Kate, Ian Goldberg, and Martin Karsten. Towards practical communication in byzantine-resistant dhts. IEEE/ACM Trans. Netw. , 21(1):190--203, 2013

    2013

  45. [53]

    Kadabra: Adapting kademlia for the decentralized web

    Yunqi Zhang and Shaileshh Bojja Venkatakrishnan. Kadabra: Adapting kademlia for the decentralized web. In Foteini Baldimtsi and Christian Cachin, editors, FC 2023, Part II , volume 13951 of LNCS , pages 327--345. Springer, Cham, May 2023

    2023

  46. [54]

    Honeybee: Decentralized peer sampling with verifiable random walks for blockchain data sharding

    Yunqi Zhang and Shaileshh Bojja Venkatakrishnan. Honeybee: Decentralized peer sampling with verifiable random walks for blockchain data sharding. arXiv preprint arXiv:2402.16201 , 2024

    2024 arXiv

  47. [55]

    , " * write output.state after.block = add.period write

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...

  48. [56]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.