eAVID: Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

eAVID: Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

arXiv:2608.15469v1 [cs.DC] 16 Aug 2026

RITHWIK KERUR, University of California, Santa Barbara, USA DAHLIA MALKHI, University of California, Santa Barbara, USA MICHAEL K. REITER, Duke University, USA Asynchronous verifiable information dispersal (AVID) lets a sender spread a message across 𝑁 = 3𝐹 + 1 nodes such that it remains recoverable despite up to 𝐹 Byzantine failures. Because dispersal must complete on 𝑁 − 𝐹 responses, standard AVID protocols fix a (𝐹 +1, 𝑁 ) erasure code and pay a 3× storage blowup, whereas a synchronous system achieves the optimal 3/2×. This cost is paid permanently: the per-node footprint is fixed at dispersal time and does not adapt when the network turns out to be healthy and all 𝑁 nodes respond. We present eAVID, an AVID protocol that decouples the storage a node retains from the fragments it was sent. eAVID encodes the message with a single (2𝐹 +1, 2𝑁 ) Reed–Solomon code, commits to all 2𝑁 fragments under one Merkle root, and sends each node two distinct fragments. This approach uses the same dispersal bandwidth as the standard scheme. Dispersal completes on 𝑁 − 𝐹 responses, as in the original AVID. Our divergence comes post-commit: nodes continue to collect responses asynchronously, and once a node has heard a Done over its adopted root from all 𝑁 nodes, it can safely discard one of its two fragments unilaterally. Because fragments are disjoint across nodes, at least 2𝐹 +1 verified fragments survive. Pruning requires no certificate, no coordination among storage nodes, and no re-encoding. Reconstruction is unchanged as any 2𝐹 +1 verified fragments decode the message regardless of how fragments are distributed. eAVID halves steady-state per-node storage relative to the (𝐹 +1, 𝑁 ) baseline when the network is healthy, and degrades gracefully to the baseline footprint when it is not.

Authors’ Contact Information: Rithwik Kerur, University of California, Santa Barbara, USA, rkerur@ucsb.edu; Dahlia Malkhi, University of California, Santa Barbara, USA, dahliamalkhi@ucsb.edu; Michael K. Reiter, Duke University, USA, michael.reiter@duke.edu.

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

1

1

Introduction

Distributed fault-tolerant algorithms are often designed for a double worst case. First, they wait for only 𝑁 − 𝐹 nodes to participate, since the network may indefinitely delay messages from up to 𝐹 nodes. Second, they assume that up to 𝐹 of the responding nodes may themselves be faulty. As a result, these protocols typically incur suboptimal communication and storage costs. Concretely, suppose a sender 𝑆 wishes to store a block 𝐵 across a system of 𝑁 nodes such that 𝐵 remains recoverable despite up to 𝐹 failures while minimizing communication and storage. This is known as the information dispersal (IDA) problem [18]. In Byzantine settings, where both the sender and storage nodes may behave arbitrarily, additional verification is required to guarantee unique recoverability. This strengthened problem is known as verifiable information dispersal (VID) [6]. A classical approach to VID combines erasure coding with cryptographic verification. The sender encodes 𝐵 using a (𝑘, 𝑘 +𝑚) erasure code and distributes the resulting 𝑘 +𝑚 fragments, one per node (with certain information added for verification), such that any 𝑘 fragments suffice to reconstruct 𝐵. In a synchronous system, where message delivery is guaranteed within a known bound Δ, the sender can use a (𝑘 = 2𝐹 + 1, 𝑘 + 𝑚 = 𝑁 ) encoding and distribute one fragment to every node within Δ. This incurs a communication overhead of 3/2 × |𝐵|, while the total storage consumed across all 𝑁 nodes is likewise 3/2 × |𝐵|, which is optimal for 𝐹 -resilience. Indeed, if exactly 𝐹 nodes fail, the surviving nodes collectively store exactly |𝐵| data. In contrast, asynchronous VID protocols (AVID) [4, 13, 22] resort to a (𝐹 + 1, 𝑁 ) encoding. Consequently, the sender incurs a communication overhead of 3 × |𝐵|, the system stores 3 × |𝐵|, and after 𝐹 failures the surviving nodes still store 2 × |𝐵|. There is a seeming tradeoff: either rely on a strong synchrony assumption for optimal dispersal and storage complexity, or incur a 2× bandwidth and storage increase in practical settings. The natural question is whether it has to be one or the other. In the crash-fault setting, this question was answered by eAID [11], which introduced postdissemination pruning: nodes reclaim storage autonomously once dissemination completes, with no re-encoding and no coordination. Byzantine faults make the same idea considerably harder. A crashfault node can take an acknowledgement at face value, but a Byzantine sender may equivocate about which fragments it dispersed, and faulty nodes may fabricate acknowledgements for fragments they never stored. A node that prunes on such evidence could destroy the last copy of data it believes is safely replicated elsewhere. Extending pruning to this setting therefore requires that a node’s decision rest on verifiable agreement about what was dispersed and on proof that enough correct nodes actually hold it. In this paper, we address this question with eAVID, an elastic AVID protocol where elasticity manifests itself in two complementary ways: (1) eAVID uses a (2𝐹 +1, 2𝑁 ) erasure code, rather than either (𝐹 +1, 𝑁 ) or a (2𝐹 +1, 𝑁 ) encoding. A sender disperses the resulting 2𝑁 fragments in an optimistically informed elastic manner. Specifically, the sender can flexibly assign one or more fragments to each node, subject only to the requirement that at least 2𝐹 + 1 fragments survive despite up to 𝐹 failures. (2) Nodes also manage their local storage elastically. Each node independently detects redundant fragments based on responses from other nodes and may safely discard a portion of its locally stored fragments. For example, the sender may initially distribute one fragment to each of the 𝑁 nodes, achieving the optimal communication overhead of 3/2 × |𝐵|, while the system stores the same optimal amount. If exactly 𝐹 nodes fail, the surviving nodes collectively store exactly |𝐵|. The downside is that dispersal can complete only when 𝑁 nodes have responded. To tolerate network delays, the sender may instead initially distribute two fragments to each node and wait for only 𝑁 − 𝐹 responses. Later,

2

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

once a node learns that responses have been received from all 𝑁 nodes, it may safely discard one of its two local fragments. Other combinations of fragments and responses are possible, including assigning varying amounts of fragments to different nodes, or staggering the dispersal one fragment at a time based on responses. Thus, eAVID enables varying the sender’s communication overhead between 3/2 × |𝐵| and 3 × |𝐵|, while storage is adjusted post-dissemination automatically to the optimal amount. Crucially, the scheme preserves a simple and uniform reconstruction procedure: any 2𝐹 + 1 fragments can recover each data block, requiring neither special bookkeeping nor a specialized reconstruction procedure. 2 2.1

Background Verifiable Information Dispersal

The information dispersal problem, originally formulated in Rabin’s seminal IDA method [18], considers a sender that holds a message 𝑀 of size |𝑀 | and wishes to spread it across a set of 𝑁 nodes while providing both data availability and storage efficiency. Rabin’s formulation targets benign (crash) faults: the dispersal must guarantee that, despite up to 𝐹 < 𝑁 /2 nodes crashing, 𝑀 can be reconstructed from the fragments held by the surviving nodes. Verifiable Information Dispersal (VID), introduced by Garay, Gennaro, Jutla, and Rabin [6], extends IDA to a setting in which the nodes, and even the sender, may be Byzantine. Cachin and Tessaro [4] later extended VID to the asynchronous network model (AVID), and a long line of subsequent work [1, 9, 14, 22] refined its storage and communication trade-offs. The reconstruction challenge: Byzantine faults make reconstruction a two-sided problem. A corrupt node might serve a fabricated fragment during retrieval, and a corrupt sender might disseminate inconsistent fragments to begin with. Reconstruction must therefore tolerate bad fragments from (i) up to 𝐹 corrupt nodes, and (ii) honest nodes holding fragments planted by a corrupt sender. Absent any safeguard, decoding different subsets of 𝐹 + 1 fragments could yield a different message each time, breaking the consistency that essentially every use of VID depends on. Merkle-tree authentication. eAVID authenticates fragments with a Merkle tree, one of three standard fragment authentication mechanisms; the other two (hash vectors and polynomial/homomorphic commitments) are surveyed in Section 6. Like those mechanisms, it provides a binding guarantee: the sender is pinned to a single value and cannot open it to two different values after the fact. AVID-H [4] replaces the hash vector with a Merkle tree over the 𝑁 fragments. The sender publishes only the root 𝑟 𝑀 , and each fragment 𝑓𝑖 travels with a logarithmic-size proof 𝜋𝑖 attesting that 𝑓𝑖 is the 𝑖-th leaf under 𝑟 𝑀 . Each node stores only its fragment, an 𝑂 (log 𝑁 ) proof, and the root. Honest vs. corrupt senders. Authentication certifies only that a fragment is the one the sender committed to, not that the committed fragments lie on a single codeword, so a corrupt sender can plant fragments that each verify yet decode to no consistent message. Two remedies close this gap: prevent equivocation up front with the homomorphic commitments or fingerprints, or detect it after reconstruction. We use the latter. Post-dissemination detect-and-reject. Another option is to catch an inconsistent sender at reconstruction: a candidate 𝑀 is decoded, the Merkle tree recomputed from the re-encoded fragments, and rejected on any mismatch with the committed root. Since the verdict is fixed once the root is fixed at dispersal, every honest retriever reaches the same outcome regardless of which fragments it used, restoring consistency even against a corrupt sender [8, 22]. This approach provides succinct 𝑂 (log 𝑁 ) proofs and an 𝑂 (1) root, and minimal assumptions (only a collision resistant hash is

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

3

required). It forgoes only recovery of data from a corrupt sender which VID does not need. Note that while we mention Merkle trees, this strategy could also be used with hash vectors or polynomial commitments which would have different sized proofs/roots. Fragments, codes, and storage blowup. Storage efficiency comes from erasure coding. An erasure code is parameterized by (𝑘, 𝑛): it encodes 𝑀 into 𝑛 fragments such that any 𝑘 suffice to reconstruct | 𝑀. With a Reed-Solomon code [19], each fragment has size |𝑀 |/𝑘, total storage is |𝑀 𝑘 × 𝑛, and 𝑛 the storage blowup over |𝑀 | is 𝑘 . In the standard asynchronous Byzantine parameterization, one fragment is stored per node, so 𝑛 = 𝑁 , with 𝑁 = 3𝐹 + 1 and 𝑘 = 𝐹 + 1. Each node stores a fragment of size |𝑀 |/(𝐹 + 1) and the blowup is 𝐹𝑁+1 ≈ 3 in the optimal-resilience regime 𝐹 < 𝑁 /3. Dispersal completes once 𝑁 − 𝐹 nodes have responded, while up to 𝐹 corrupt nodes may contribute fabricated or mismatched fragments during retrieval. 2.2

Merkle-Based AVID Solutions

We now describe the Merkle-based AVID schemes on which eAVID builds; the remaining, nonMerkle solutions are surveyed in Section 6. 2.2.1 AVID and AVID-H. The original AVID scheme of Cachin and Tessaro [4] integrates an asynchronous reliable broadcast with erasure coding under optimal Byzantine resilience 𝐹 < 𝑁 /3. The sender encodes 𝑀 using a (𝑘, 𝑁 ) erasure code and computes a vector 𝐷 = [𝐻 (𝑓1 ), . . . , 𝐻 (𝑓𝑁 )] of per-fragment hashes; receivers run a Bracha-style three-phase exchange [3] (send/echo/ready) carrying fragments and the hash vector until 𝑘 + 𝐹 matching ready messages on a common 𝐷 are observed. AVID-H replaces the hash vector with a Merkle tree over the fragments, so each receiver stores only its fragment, a logarithmic-size proof, and the root: yielding communication blowup 𝑂 (𝑁 ) and storage blowup approaching 𝐹𝑁+1 (bounded by 3 + 𝑜 (1)). AVID uses the hash vector 𝐷 for authentication while AVID-H uses the Merkle Root. Neither adds a dedicated corrupt-sender remedy, instead leaning on the inner reliable broadcast to agree on a single 𝐷/root before any fragment is accepted. AVID-H has two structural costs that motivate later work. First, every dispersal pays for an 𝑂 (𝑁 2 )-message reliable broadcast on full fragments, even when the network is healthy. Several later works aim to optimize the echoed payload. Second, the encoding parameters are fixed at 𝑘 = 𝐹 + 1: nodes always store a fragment of size |𝑀 |/𝑘, and there is no mechanism to shed storage when more than 𝑘 honest nodes successfully complete the dispersal. The same paper’s AVID-RBC variant addresses the storage cost by layering an additional round of erasure coding on top of AVID-H’s reliable broadcast, driving storage blowup down toward the optimal 𝑁𝑁−𝐹 at the cost of encoding the message twice [4]. Concretely, the broadcast uses an (𝑁 − 2𝐹, 𝑁 ) code, and after the message has been committed, nodes re-encode it with an (𝑁 − 𝐹, 𝑁 ) code for long-term storage. The reduction is only achieved by a coordinated re-encode, not by anything a node can do on its own. 3

System Model

Parties and network. The system consists of 𝑁 parties, 𝑃1, . . . , 𝑃 𝑁 , connected by pairwise authenticated point-to-point channels. At most 𝐹 < 𝑁 /3 parties may be Byzantine and behave maliciously. The remaining parties are correct and follow the protocol. Any party may act as a sender that initiates a dispersal of a message 𝑀. The sender itself may be Byzantine: a key objective of our protocol is that safety holds against a faulty sender (e.g., one that equivocates), and that honest parties detect equivocation and reject inconsistent dispersals. We assume static membership: the set of parties is fixed once the protocol begins.

4

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

We adopt the classical asynchronous model such that the adversary may delay messages between honest parties arbitrarily but cannot drop them. Cryptographic assumptions. We assume a computationally bounded adversary and the following standard primitives. • Authenticated Channels. We assume authenticated point-to-point links between every pair of parties. If a correct party 𝑗 receives a message 𝑀 on the link from party 𝑖, then 𝑖 indeed sent 𝑀 to 𝑗. The adversary may delay messages arbitrarily, but cannot forge, modify, or replay messages on links between correct parties, nor impersonate a correct sender. Messages between correct parties are eventually delivered. • Collision-resistant hash function. We assume a cryptographic hash function 𝐻 for which it is computationally infeasible to find 𝑥 ≠ 𝑥 ′ with 𝐻 (𝑥) = 𝐻 (𝑥 ′ ). Merkle trees instantiated with 𝐻 are binding: given a root 𝑟 , no polynomial-time adversary can produce two distinct valid openings to the same leaf position. Verifiable Information Dispersal. eAVID realizes a Verifiable Information Dispersal (VID) abstraction with two protocols, Disperse and Retrieve, that satisfy the following properties. • Binding. Once the first honest party completes Disperse for id, there is a unique value 𝑣 ★ ∈ {Done(𝑀 ★), Abort} such that every honest party that completes Disperse for id outputs 𝑣 ★. If 𝑣 ★ = Done(𝑀 ★), then 𝑀 ★ is a unique committed message and every honest party that completes Retrieve on id outputs 𝑀 ★. • Validity. If the sender is honest with input 𝑀, then 𝑣 ★ = Done(𝑀 ★) with 𝑀 ★ = 𝑀. • Agreement. Any two honest parties that complete Retrieve on the same id output the same value. • Termination of dispersal. If the sender is honest with input 𝑀, then every honest party eventually completes Disperse for id with output Done(𝑀). • Totality. If any honest party completes Disperse for id with a Done output, then every honest party eventually completes Disperse for id. • Termination of retrieval. If some honest party has completed Disperse for id with a Done output, then every honest party that invokes Retrieve on id eventually completes it with output 𝑀 ★. Performance measures. With these assumptions as our starting point, we shift our focus to the metric we aim to optimize. Our primary goal is to enhance performance by optimizing storage cost. We define storage cost as the aggregate size of storage used across all nodes to persist the fragments associated with a message. For a baseline, full replication—where a message of size 𝐵 is sent to all 𝑁 nodes—incurs a total storage cost of 𝑂 (𝑁 · 𝐵). We also define per-node storage as the storage required on a responsive node in the system. 4 4.1

Solution Dissemination and Reconstruction

An eAVID sender starts every dissemination by encoding 𝑀 into 2𝑁 fragments using a (2𝐹 +1, 2𝑁 ) Reed-Solomon code, such that any 2𝐹 +1 fragments can reconstruct 𝑀. The sender then constructs a Merkle tree over all 2𝑁 fragments, producing a single Merkle root 𝑟 𝑀 that succinctly commits to the entire set of fragments. For each fragment 𝑓𝑖 , the sender computes the corresponding Merkle proof 𝜋𝑖 , which allows any receiver to verify that 𝑓𝑖 is a genuine fragment of 𝑀 under root 𝑟 𝑀 . The sender employs a similar dissemination strategy to past approaches, except it sends two distinct fragments to each node instead of one. The sender could also use an adaptive strategy that varies the number of fragments it sends to each node, but we reserve this for future work.

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

5

Note that since we use an encoding scheme with 𝑘 = 2𝐹 +1 rather than 𝑘 = 𝐹 +1, our fragments are half the size, so sending two of these smaller fragments uses the same bandwidth as sending one larger fragment under a standard (𝐹 +1, 𝑁 ) scheme. Along with each pair of fragments, the sender transmits the corresponding Merkle proofs and the root 𝑟 𝑀 . Algorithm 1 formalizes the protocol. Upon receiving its Disperse message, a node verifies each Merkle proof against the root 𝑟 𝑀 and stores the fragments. It then broadcasts an Echo carrying those fragments and their proofs to all other nodes. A correct node echoes at most once per dispersal, so it commits to echoing exactly one root. A node that has not yet received a Disperse for its own fragments can still participate: once it has seen Echos for a common root from 𝐹 +1 distinct nodes, it decodes 𝑀 from the echoed fragments, re-encodes and rebuilds the Merkle tree to confirm the root, recovers its own pair, and echoes it and the proofs. This recovery path ensures the protocol makes progress even when a faulty sender selectively withholds Disperse messages. Because a correct node echoes only a single root, and a node adopts a root only after that root has been echoed by an echo quorum of 2𝐹 + 1 nodes, two conflicting roots can never both be adopted: any two such quorums intersect in a correct node, which echoed only one of them. This is what prevents a faulty sender from equivocating about which fragments were disseminated, and it lets each node reach a dispersal-complete decision locally rather than through an acknowledgement from the sender. Unlike a leader-driven protocol where the sender collects acknowledgements and tells everyone when dispersal has committed, eAVID lets each node reach this conclusion on its own from the all-to-all traffic, which both reduces the sender’s role to that of an initiator and gives the protocol its agreement-property guarantees in the face of a Byzantine sender. Concretely, once a node has adopted a root it attempts to reconstruct: if it holds at least 2𝐹 +1 distinct verified fragments, it decodes 𝑀, re-encodes, and rebuilds the Merkle tree. If the rebuilt root matches the adopted root, the node broadcasts Done over that root to all parties. If instead the reconstructed fragments do not re-encode to the adopted root, the node concludes that the dispersal is irrecoverably inconsistent under the agreed root and locally outputs Abort. A node that has 2𝐹 +1 Dones received whose value equals its own adopted root considers the dispersal locally complete and outputs Done: at this point the message 𝑀 is durably stored across the system. In the background, every node continues to collect Dones past its own 2𝐹 +1 threshold. Once a node has Dones from all 𝑁 nodes, and has itself broadcast Done, it prunes its extra fragment. Pruning is safe in every intermediate state: at least 2𝐹 +1 correct nodes stored their assigned pairs before announcing Done, and each discards at most one fragment, so 2𝐹 +1 distinct verified fragments always survive no matter which nodes have pruned (Lemma 4.8). 4.2

Post Dissemination Pruning

eAVID’s primary departure from prior Byzantine works is that every node can prune extra fragments post-dissemination from its own local view of completed Done broadcasts. Pruning does not require coordination among nodes or re-coding of information. Each node decides unilaterally from what it has received, and by Lemma 4.8 that decision is safe regardless of which other nodes have already pruned. It works as follows: (1) Asynchronous Collection: After outputting Done on the initial 2𝐹 +1 Dones received over the adopted root, each node continues to accept Dones in the background, accumulating the set 𝐷 of senders whose Done over the adopted root has been received. (2) Dynamic Storage Optimization: Once a node has received a Done over its adopted root from all 𝑁 nodes, and has itself broadcast Done, it only needs to retain 1 fragment,

6

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

Algorithm 1 eAVID Party Require: local id 𝑗 State per id: adopted root 𝑟 (init ⊥); echo tallies Ech[ · ] (root ↦→ set of echoers, init empty); first-echo map src[ · ] (party ↦→ root, init ⊥); leaf buffer 𝐵; fragments F; Done tally Dn[ · ] (party ↦→ announced root, init ⊥); flags echoed, doneSent, decided, pruned (all false) 1: function Disperse(𝑀) ⊲ sender only 2𝑁 ← BuildMerkleTree( 𝑓 , . . . , 𝑓 2: ( 𝑓1 , . . . , 𝑓2𝑁 ) ← Encode(𝑀, 2𝐹 +1, 2𝑁 ); 𝑟 𝑀 , {𝜋𝑖 }𝑖=1 1 2𝑁 ) 3: for each 𝑘 ∈ {1, . . . , 𝑁 }, where 𝑆𝑘 ← {2𝑘 −1, 2𝑘 }: 4: send ⟨Disperse, id, 𝑟 𝑀 , { (𝑖, 𝑓𝑖 , 𝜋𝑖 ) : 𝑖 ∈ 𝑆𝑘 } ⟩ to 𝑘 5: end function 6: upon ⟨Disperse, id, 𝑟 𝑀 , 𝑋 ⟩ from sender, if not echoed: 7: 𝑃 ← { (𝑖, 𝑓𝑖 , 𝜋𝑖 ) ∈ 𝑋 : VerifyMerkle(𝑟 𝑀 , 𝑖, 𝑓𝑖 , 𝜋𝑖 ) and 𝑖 ∈ 𝑆 𝑗 } 8: if 𝑃 ≠ ∅ then echoed ← true; broadcast ⟨Echo, id, 𝑟 𝑀 , 𝑃 ⟩ 9: upon ⟨Echo, id, 𝑟 𝑀 , 𝑃 ⟩ from 𝑘 ∉ Ech[𝑟 𝑀 ]: 10: if src[𝑘 ] ∉ {⊥, 𝑟 𝑀 } then return ⊲ one echo per sender 11: 𝑃 ′ ← { (𝑖, 𝑓𝑖 , 𝜋𝑖 ) ∈ 𝑃 : VerifyMerkle(𝑟 𝑀 , 𝑖, 𝑓𝑖 , 𝜋𝑖 ) and 𝑖 ∈ 𝑆𝑘 } 12: if 𝑃 ′ = ∅ then return ⊲ echo must carry 𝑘’s own verified fragment 13: src[𝑘 ] ← 𝑟 𝑀 ; Ech[𝑟 𝑀 ] ← Ech[𝑟 𝑀 ] ∪ {𝑘 }; if 𝑟 𝑀 = 𝑟 then 𝐵 ← 𝐵 ∪ 𝑃 ′ ; TryFinishFrom 14: if not echoed and |Ech[𝑟 𝑀 ] | ≥ 𝐹 + 1 then 15: 𝑀 ′ ← Decode( { (𝑖, 𝑓𝑖 , 𝜋𝑖 ) echoed under 𝑟 𝑀 }, 2𝐹 +1, 2𝑁 ); re-encode 𝑀 ′ , rebuild Merkle tree 16: if resulting root = 𝑟 𝑀 then 17: 𝑃 𝑗 ← this party’s pair 𝑆 𝑗 from re-encoding 18: echoed ← true; broadcast ⟨Echo, id, 𝑟 𝑀 , 𝑃 𝑗 ⟩ 19: if 𝑟 = ⊥ and |Ech[𝑟 𝑀 ] | ≥ 2𝐹 + 1 then ⊲ adopt the root that reached the echo quorum 20: 𝑟 ← 𝑟 𝑀 ; 𝐵 ← { (𝑖, 𝑓𝑖 , 𝜋𝑖 ) echoed under 𝑟 𝑀 : VerifyMerkle(𝑟, 𝑖, 𝑓𝑖 , 𝜋𝑖 ) }; TryFinishFrom; CheckDone 21: upon ⟨Done, id, 𝑟𝑘 ⟩ from 𝑘 with Dn[𝑘 ] = ⊥: ⊲ one Done per sender 22: Dn[𝑘 ] ← 𝑟𝑘 23: if 𝑟 = ⊥ and | {𝑘 ′ : Dn[𝑘 ′ ] = 𝑟𝑘 } | ≥ 𝐹 + 1 then 24: 𝑟 ← 𝑟𝑘 ; load 𝐵 with all fragments echoed under 𝑟𝑘 that verify against 𝑟 ⊲ may be short of 2𝐹 +1 for now; later Echos top 𝐵 up 25: TryFinishFrom; CheckDone 26: function CheckDone 27: if 𝑟 = ⊥ then return 28: 𝐷 ← {𝑘 : Dn[𝑘 ] = 𝑟 } 29: if |𝐷 | ≥ 2𝐹 + 1 and not decided then 30: decided ← true; output ⟨id, out, Done⟩ 31: if |𝐷 | = 𝑁 and doneSent and not pruned then 32: pruned ← true; discard elements of F until | F | = 1 33: end function 34: function IsCodeword ⊲ deterministic verdict against the adopted root 𝑟 35: if | {𝑖 : (𝑖, ·, ·) ∈ 𝐵 } | < 2𝐹 + 1 then return false 36: 𝑀 ← Decode(𝐵, 2𝐹 +1, 2𝑁 ); re-encode 𝑀, rebuild Merkle tree 37: return (resulting root = 𝑟 ) 38: end function 39: function TryFinishFrom ⊲ Reconstruct → Done/Abort 40: if 𝑟 = ⊥ or doneSent or decided then return 41: if | {𝑖 : (𝑖, ·, ·) ∈ 𝐵 } | < 2𝐹 + 1 then return 42: if IsCodeword then ⊲ codeword under 𝑟 : broadcast Done 43: if | F | < 2 then F ← this party’s pair 𝑆 𝑗 from re-encoding 44: doneSent ← true; Dn[ 𝑗 ] ← 𝑟 ; broadcast ⟨Done, id, 𝑟 ⟩ 45: else ⊲ non-codeword under the agreed root: abort locally 46: decided ← true; output ⟨id, out, Abort⟩ 47: end function

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

7

Algorithm 2 eAVID Retrieval Require: adopted root 𝑟 ★ for id (from Dispersal); retriever 𝑅 State per id: retrieval buffer 𝐵𝑅 (init ∅); flag retDone (init false) 1: function Retrieve(id) 2: if 𝑟 ★ = ⊥ then return ⊥ 3: broadcast ⟨Get, id, 𝑟 ★ ⟩ to all parties 4: end function 5: upon ⟨Get, id, 𝑟 ′ ⟩ from 𝑅: 6: if 𝑟 = 𝑟 ′ and | F | ≥ 1 then send ⟨GetResp, id, F⟩ to 𝑅

⊲ no root adopted for this id

⊲ server 𝑃𝑖 ⊲ answer with whatever fragments survive pruning

7: upon ⟨GetResp, id, 𝑌 ⟩ from 𝑘: 8: if retDone then return 9: 𝐵𝑅 ← 𝐵𝑅 ∪ { (𝑖, 𝑓𝑖 , 𝜋𝑖 ) ∈ 𝑌 : VerifyMerkle(𝑟 ★, 𝑖, 𝑓𝑖 , 𝜋𝑖 ) and 𝑖 ∈ 𝑆𝑘 } server 𝑘 10: if | {𝑖 : (𝑖, ·, ·) ∈ 𝐵𝑅 } | ≥ 2𝐹 + 1 then 11: 𝑀 ← Decode(𝐵𝑅 , 2𝐹 +1, 2𝑁 ) 12: retDone ← true; output ⟨id, ret, 𝑀 ⟩

⊲ retriever 𝑅 ⊲ verified under 𝑟 ★ ; index attributable to

effectively cutting storage in half. Since fragments are unique across nodes, it does not matter which fragment the node discards (each node retains its accompanying Merkle proof for any fragment it keeps). Through a combination of these approaches, eAVID departs from previous work by: (1) Allowing different numbers of fragments to be stored by different nodes: so long as 2𝐹 + 1 fragments can be collected from correct nodes in the system, 𝑀 will remain available; (2) Not requiring re-encoding of 𝑀 or re-construction of the Merkle tree; (3) Not impacting the recovery computation, which always takes 2𝐹 + 1 verified fragments and reconstructs 𝑀 in the same manner, oblivious to the assignment of fragments to nodes; (4) Not requiring maintaining meta-information per message 𝑀 beyond the Merkle root. Bandwidth and storage trade-off. Standard Byzantine dispersal approaches use an (𝐹 + 1, 𝑁 ) encoding scheme, where each node stores a single fragment of size roughly 𝐹|𝑀+1| . By using a (2𝐹 + 1, 2𝑁 ) encoding scheme and sending two fragments to each node, eAVID maintains the same aggregate bandwidth utilization during dissemination: each fragment is of size roughly 2𝐹|𝑀+1| , and each node receives two of them, so the per-node payload matches the standard scheme. However, if the network is healthy and every node announces Done and those announcements reach a given node,that node can subsequently drop one of its two fragments and retain only a single fragment of size 2𝐹|𝑀+1| , effectively cutting steady-state storage in half compared to the standard (𝐹 +1, 𝑁 ) baseline. In adverse conditions, eAVID gracefully degrades to the standard storage footprint, ensuring that the optimistic case is rewarded without penalizing the pessimistic one. 4.3

Safety and Liveness

Lemma 4.1. No two correct parties adopt distinct roots for the same id. Proof. A correct party adopts a root by one of two rules: an echo quorum of 2𝐹 +1 accepted Echos, or 𝐹 +1 Dones over a common root. Echo-path adoptions. A correct party adopts 𝑟 by this rule only after collecting 2𝐹 + 1 accepted Echo messages for 𝑟 from distinct parties. A correct party records at most one root per source, so no party contributes to the tallies of two roots at the same adopter. Suppose correct parties adopt

8

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

𝑟 and 𝑟 ′ ≠ 𝑟 . The two echo sets each have size 2𝐹 + 1; on 𝑁 = 3𝐹 + 1 parties they intersect in at least 2(2𝐹 + 1) − 𝑁 ≥ 𝐹 + 1 parties, hence in at least one correct party. A correct party sets echoed once and broadcasts Echo for a single root, so it cannot have echoed both 𝑟 and 𝑟 ′ . Thus all correct parties that adopt a root by this rule adopt the same 𝑟 ★. Done-path adoptions. We show by induction on the order in which correct parties broadcast Done that every correct Done is over 𝑟 ★. Consider the first correct party to broadcast Done for id. It adopted via the echo path and therefore announces 𝑟 ★. Now consider any later correct broadcaster. It adopted either via the echo path, giving 𝑟 ★, or on 𝐹 +1 Dones over a common root. The latter set contains at least one Done from a correct party, which by the induction hypothesis is over 𝑟 ★, so the adopted root is 𝑟 ★ and the party announces 𝑟 ★. Hence every correct Done is over 𝑟 ★, and a Done-path adoption never yields any other root. □ Lemma 4.2 (Root uniqeness). At most one root 𝑟 ★ is adopted by correct parties, and any correct party that outputs does so with respect to 𝑟 ★. Proof. Immediate from Lemma 4.1: a correct party adopts 𝑟 ★, evaluates IsCodeword, stores its assigned pair, and only then broadcasts Done or outputs, and all correct adopters share 𝑟 ★. □ Lemma 4.3 (Binding). Once the first correct party outputs for id, there is a unique value 𝑣 ★ ∈ {Done(𝑀 ★), Abort} such that any correct party that outputs for id does so with 𝑣 ★, and any correct party that completes Retrieve outputs 𝑀 ★ (if 𝑣 ★ = Done(𝑀 ★)). Proof. By Lemma 4.2 every correct party that outputs has adopted the same 𝑟 ★, which commits a unique leaf vector. The verdict IsCodeword is a deterministic function of 𝑟 ★, so all correct parties compute the same value. Two cases: Case A: 𝑟 ★ commits a valid (2𝐹 +1, 2𝑁 ) codeword. Any 2𝐹 + 1 leaves verified under 𝑟 ★ interpolate the same degree-≤ 2𝐹 polynomial and re-encode to 𝑟 ★, so IsCodeword returns true at every correct party that reconstructs. No correct party takes the abort branch, and each such party broadcasts Done with value 𝑟 ★. A correct party outputs Done(𝑀 ★) upon 2𝐹 + 1 Dones received over 𝑟 ★, where 𝑀 ★ is the unique decoding. A correct Retrieve gathers 2𝐹 + 1 leaves under 𝑟 ★, decodes, re-encodes (matching), and outputs 𝑀 ★. Thus 𝑣 ★ = Done(𝑀 ★). Case B: 𝑟 ★ commits a non-codeword. No 2𝐹 + 1 leaves verified under 𝑟 ★ re-encode to 𝑟 ★, so IsCodeword returns false at every correct party that reconstructs: no correct party broadcasts Done over 𝑟 ★, and no 2𝐹 + 1 Done quorum can form. No correct party outputs Done. Every correct party that adopts 𝑟 ★ and reconstructs outputs Abort. Thus 𝑣 ★ = Abort. □ Lemma 4.4 (Termination of dispersal). If the sender is correct, then every correct party eventually outputs Done(𝑀). Proof. Step 1 (echo and adopt). The correct sender sends each correct party its verified pair under 𝑟 𝑀 . Each such party echoes 𝑟 𝑀 with its fragment. There are ≥ 2𝐹 + 1 correct parties, so every correct party eventually collects an echo quorum for 𝑟 𝑀 and adopts 𝑟 ★ = 𝑟 𝑀 . No correct party echoes any other root (the sender sends only 𝑟 𝑀 ), so no other root is adopted. Step 2 (reconstruct and Done). Each Echo carries the echoer’s fragment. Since the pairs 𝑆𝑘 are disjoint, the echoes of ≥ 𝐹 + 1 correct parties give every correct party ≥ 2𝐹 + 2 distinct verified leaves in 𝐵. TryFinishFrom finds IsCodeword true, stores the party’s pair, and broadcasts Done with value 𝑟 𝑀 to all parties. Step 3 (output). Every correct party thus broadcasts Done. Correct parties broadcast to all, and messages between correct parties are eventually received, so each correct party eventually receives these ≥ 2𝐹 + 1 Dones over 𝑟 𝑀 = 𝑟 ★. No correct party aborts. □

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

9

Lemma 4.5 (Validity). If the sender is correct with input 𝑀, then every correct party that outputs does so with Done(𝑀). Proof. By Lemma 4.4 every correct party outputs, and by Lemma 4.1 all adopt 𝑟 ★ = 𝑟 𝑀 , which commits the codeword of 𝑀. By Case A of Lemma 4.3, the output is Done(𝑀 ★) with 𝑀 ★ = 𝑀. □ Lemma 4.6 (Agreement). Any two correct parties that complete Retrieve on the same id output the same value. Proof. By Lemma 4.3 both adopt 𝑟 ★ and output the unique 𝑀 ★ (or both are in the Abort case, in which retrieval returns no value). □ Lemma 4.7 (Reconstructability at completion). When the first correct party outputs Done(𝑀 ★) for id, the fragments held by correct parties contain at least 2𝐹 + 1 distinct verified fragments under 𝑟 ★, sufficient to reconstruct 𝑀 ★. Proof. Outputting Done requires 2𝐹 + 1 Dones received over 𝑟 ★ from distinct senders, at least 𝐹 + 1 from correct parties. By authenticity of the channels a Done counted against a correct party 𝑘 was genuinely sent by 𝑘, and the Dn[𝑘] = ⊥ guard admits at most one per sender, so each of these ≥ 𝐹 +1 correct parties executed the Done broadcast in TryFinishFrom. By the |F | < 2 guard in TryFinishFrom no correct party broadcasts Done without holding its verified pair, and before broadcasting it stored its assigned pair. Each correct party accepts only fragments assigned to itself, and the partition is disjoint, so distinct correct parties hold disjoint fragments. The ≥ 𝐹 + 1 correct Done-broadcasters therefore hold ≥ 2(𝐹 + 1) = 2𝐹 + 2 distinct verified fragments, exceeding the (2𝐹 +1) threshold. □ Lemma 4.8 (Pruning safety). If a correct party prunes a fragment for id, then 𝑀 ★ remains reconstructable from the fragments held by correct parties. Proof. A correct party prunes only when |𝐷 | = 𝑁 and doneSent holds. The latter means the pruning party itself found IsCodeword true against 𝑟 ★, so 𝑟 ★ commits a codeword. The former means it received ⟨Done, id, 𝑟 ★⟩ from all 𝑁 parties. Of these 𝑁 senders at most 𝐹 are Byzantine, so at least 2𝐹 + 1 are correct. By channel authenticity each of those announcements was genuinely sent by the correct party it is attributed to, so each of these ≥ 2𝐹 +1 correct parties executed the Done broadcast and, by the |F | < 2 guard, had stored its assigned pair 𝑆𝑘 beforehand. Pruning is performed independently by each party as its own |𝐷 | reaches 𝑁 , so at any point the system may be in a mixed state: some correct parties have pruned and others have not, and each may prune at a different time, and some may never prune at all. We show reconstructability holds in every such state. Fragments are distinct across parties by the disjoint partition, and pruning discards at most one fragment per party, so each of these ≥ 2𝐹 + 1 correct parties retains at least one verified fragment at a distinct index — regardless of which parties have pruned. These ≥ 2𝐹 + 1 distinct verified fragments meet the threshold of the (2𝐹 +1, 2𝑁 ) code, so 𝑀 ★ remains reconstructable (Case A of Lemma 4.3). □ Lemma 4.9 (Totality). If any correct party outputs Done(𝑀 ★) for id, then every correct party eventually outputs Done(𝑀 ★). If any correct party outputs Abort, then no correct party outputs Done, and every correct party that adopts 𝑟 ★ outputs Abort. Proof. A correct party outputs only after adopting a root; let 𝑟 ★ be the root it adopted. By Lemma 4.1 no correct party adopts a different root, so 𝑟 ★ is the unique root adopted by correct parties. By Lemma 4.3, IsCodeword evaluated against 𝑟 ★ is a fixed value, so exactly one of the two cases below holds.

10

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

Case A: 𝑟 ★ commits a codeword. Step 1 (every correct party adopts 𝑟 ★). The outputting party counted 2𝐹 +1 Dones over 𝑟 ★ from distinct senders, of which at most 𝐹 are Byzantine, so at least 𝐹 +1 are from correct parties; call this set 𝑄. Each member of 𝑄 broadcast its Done to all parties, and messages between correct parties are eventually received, so every correct party eventually holds ≥ 𝐹 +1 Dones over 𝑟 ★ in Dn[·]. A correct party that has not already adopted therefore adopts by the amplification rule, and by Lemma 4.1 the root it adopts is 𝑟 ★. Step 2 (every correct party obtains 2𝐹 +1 fragments). By the induction in Lemma 4.1, the first correct party to announce Done for id adopted 𝑟 ★ via an echo quorum of 2𝐹 +1 accepted Echos. At most 𝐹 of those echoers are Byzantine, so at least 𝐹 +1 are correct; call this set 𝑄 ′ . Members of 𝑄 ′ broadcast their Echos to all parties, so every correct party eventually receives ≥ 𝐹 +1 accepted Echos under 𝑟 ★. Each carries its sender’s assigned pair and the pairs partition {1, . . . , 2𝑁 }, so these supply ≥ 2(𝐹 +1) = 2𝐹 +2 ≥ 2𝐹 +1 leaves at distinct indices, all verified under 𝑟 ★. A party that adopted on Dones may hold fewer than 2𝐹 +1 fragments at the instant it adopts. TryFinishFrom is re-invoked on every Echo that extends 𝐵 under the adopted root, so it eventually runs at that party with ≥ 2𝐹 +1 distinct fragments. Step 3 Every correct party finds IsCodeword true, stores its pair, and broadcasts Done with value 𝑟 ★. There are ≥ 2𝐹 + 1 correct parties, so ≥ 2𝐹 + 1 correct Dones over 𝑟 ★ are eventually received by every correct party, and each outputs Done(𝑀 ★). Case B: 𝑟 ★ commits a non-codeword. We show no correct party outputs Done, and every correct party that adopts 𝑟 ★ outputs Abort. Since 𝑟 ★ is a non-codeword, no 2𝐹 +1 leaves verified under 𝑟 ★ re-encode to 𝑟 ★, so IsCodeword is false at every correct party that reconstructs; hence no correct party broadcasts Done, and no correct party outputs Done. It follows that no correct party adopts by the amplification rule either, since that rule requires 𝐹 +1 Dones over a common root. Every correct adopter is therefore an echo-path adopter, and adoption by that rule requires 2𝐹 +1 accepted Echos carrying disjoint full pairs, so such a party holds ≥ 2𝐹 +1 distinct fragments verified under 𝑟 ★; it runs TryFinishFrom, finds IsCodeword false, and outputs Abort. No correct party prunes either, since |𝐷 | = 𝑁 would require 2𝐹 +1 correct parties to have announced Done over 𝑟 ★. □ Lemma 4.10 (Retrieval termination). If dispersal for id completed with a Done output, then every correct party that invokes Retrieve eventually outputs 𝑀 ★. Proof. A Done output required 2𝐹 + 1 Done announcements over 𝑟 ★, at least 𝐹 + 1 from correct parties, each of which stored its assigned pair before broadcasting (Lemma 4.7). No correct party has pruned. The ≥ 𝐹 +1 correct announcers still hold their full pairs, i.e. ≥ 2(𝐹 +1) = 2𝐹 +2 verified fragments; by disjointness of the partition these indices are distinct. Some correct party has pruned. That party pruned only on |𝐷 | = 𝑁 with doneSent set, so by the counting in Lemma 4.8 at least 2𝐹 +1 correct parties had stored their assigned pairs before announcing, and each retains at least one verified fragment at a distinct index after pruning. This bound is independent of which of them have pruned so far, so it holds in every mixed state. In either case the correct parties jointly hold ≥ 2𝐹 + 1 distinct fragments verified under 𝑟 ★. Every such holder 𝑃𝑖 has 𝑟 = 𝑟 ★ and |F | ≥ 1, so on receiving 𝑅’s Get it replies with GetResp. 𝑅 accumulates every correct-held fragment into 𝐵𝑅 , and since these number ≥ 2𝐹 + 1 at distinct indices, 𝑅’s threshold |{𝑖 : (𝑖, ·, ·) ∈ 𝐵𝑅 }| ≥ 2𝐹 + 1 eventually holds. Since dispersal completed Done, 𝑟 ★ commits a codeword (Case A of Lemma 4.3) and 𝑅 outputs its decoding 𝑀 ★. □ We show that our protocol establishes the binding, validity, agreement, termination of dispersal, totality, and termination of retrieval as defined in Section 3. Lemma 4.8 shows that these properties

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

11

continue to hold after post-dissemination pruning, in every state reachable by any subset of correct parties having pruned. 5

Implementation and Evaluation

To demonstrate the agility and generic nature of eAVID, we are integrating it into several Byzantine replication and decentralized storage systems, including Autobahn [7], Walrus [5], Bullshark [21], and Alpenglow [12], and instrumenting each to measure dispersal bandwidth, per-node storage, and end-to-end latency under both healthy and adversarial network conditions. Preliminary results show that eAVID matches the throughput and latency of the dispersal each system uses today, while halving steady-state per-node storage whenever the network is healthy enough for every node to complete dispersal. Because pruning is optimistic and taken independently by each node, the storage saving degrades gracefully rather than abruptly. Under adverse conditions eAVID falls back to the same footprint as the baseline, so the optimistic case is rewarded without penalizing the pessimistic one. A full implementation and evaluation is deferred to the full paper. 6 6.1

Related Work Fragment Authentication Beyond Merkle Trees

Besides the Merkle tree used by eAVID, solutions typically authenticate fragments in one of two other ways. As with the Merkle tree, each provides a binding guarantee. (i) Hash vector. The sender publishes a vector 𝐷 = [𝐻 (𝑓1 ), . . . , 𝐻 (𝑓𝑁 )] of per-fragment hashes, and a fragment is accepted only if it matches its entry in 𝐷. This is the mechanism of the original AVID [4]; it requires 𝑂 (𝑁 ) authentication data per node. (ii) Polynomial / homomorphic commitments. The most recent family attaches a constant-size or aggregatable cryptographic opening that binds a fragment directly to 𝑀. Two schemes anchor this family: • Pedersen commitments [17] have the form 𝑐 = 𝑔𝑚 ℎ𝑟 in a prime-order group; they are computationally binding, and additively homomorphic. Pedersen commitments also provide the hiding property, which is not needed in VID. The additive homomorphism lets a verifier combine per-fragment commitments exactly as the linear erasure code combines fragments, so a fragment can be checked against an aggregate commitment to 𝑀. Pedersen needs no trusted setup: its parameters are two generators with unknown relative discrete logarithm, which can be sampled transparently in any prime-order group. It is, however, not succinct: a single commitment binds one value, so authenticating a coded message uses a vector of 𝑂 (𝑁 ) commitments, and checking a fragment is an 𝑂 (𝑁 ) multi-exponentiation over that vector. • KZG polynomial commitments [10] treat the encoded fragments as evaluations 𝜙 (1), . . ., 𝜙 (𝑁 ) of a single low-degree polynomial 𝜙. The sender commits to 𝜙 with one constant-size group element, and each fragment ships with a constant-size opening proof verified by a single pairing check. Both are independent of the number of fragments, unlike a Merkle root’s Θ(log 𝑁 ) authentication path, and the commitment is additively homomorphic, so a commitment to a linear combination of fragments can be derived from the underlying commitments. This succinctness rests on a trusted setup: the structured reference string (SRS) is generated from secret randomness that must be destroyed, and should it leak, binding fails. KZG further requires pairing-friendly groups and more expensive proof generation, and the trusted-setup assumption is undesirable or unavailable in some deployments, motivating transparent alternatives.

12

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

Up-front prevention. A homomorphic commitment or fingerprint lets a verifier reject any offcodeword fragment on receipt. A linear-sized one — the Pedersen commitment vector, or the homomorphic fingerprints of AVID-FP [9] — binds the whole codeword and prevents equivocation outright, at 𝑂 (𝑁 ) per fragment. Constant-sized KZG commitments require additional machinery to match this guarantee: prior work either adds an explicit degree proof [15] or restructures the commitment with column commitments and row-wise encoding [16], both of which reintroduce an 𝑂 (𝑁 ) vector. 6.2

Existing AVID Solutions

We now survey representative AVID solutions and discuss how each one trades off storage, communication, and protocol complexity. Across the landscape, AVID schemes differ primarily along three axes: (i) the encoding parameters and the consequent storage blowup, (ii) the authentication mechanism that provides binding (one of the three techniques above), and (iii) how dispersal is coordinated — in particular, whether it relies on an inner reliable broadcast, on signatures, or on multi-round gossip among storage nodes. 6.2.1 Fingerprint-Based AVID (AVID-FP). Hendricks, et al. (AVID-FP) [9] optimize the original AVID protocol by replacing the plain cross-checksum with homomorphic fingerprints. The sender erasure-codes 𝑀 and computes a fingerprinted cross-checksum, sending each receiver its fragment together with this checksum. Because the fingerprints preserve the algebraic constraints of the erasure code, each receiver can independently verify that its fragment corresponds to the original data block. This removes the need for receivers to echo their large, full fragments to one another; instead, receivers reach agreement by reliably broadcasting only the succinct fingerprinted crosschecksum. This approach prevents equivocation upfront. The fingerprints are the homomorphic openings, so binding and corrupt-sender prevention coincide and neither detect-and-reject nor a fragment-level reliable broadcast is needed. AVID-FP’s contribution is therefore largely on the coordination axis as nodes agree on the succinct checksum rather than echoing full fragments. 6.2.2 Polynomial-Commitment AVID. A more recent line [2] uses polynomial commitments (e.g., KZG) in place of homomorphic fingerprints to compress per-fragment authentication data from 𝑂 (𝑁 ) to 𝑂 (1). The sender commits to a polynomial whose evaluations are the fragments, distributes per-fragment openings, and each receiver verifies its share against the single commitment. With the standard 𝑘 = 𝐹 + 1 parameterization, each node still stores a fragment of size |𝑀 |/(𝐹 + 1), so the dispersal-time storage blowup is 𝐹𝑁+1 ≈ 3 like the hash- and Merkle-based schemes; what these schemes gain is 𝑂 (1) authentication data and communication blowup that asymptotically matches lower bounds [1]. Variants that re-encode for long-term storage can approach the optimal blowup 𝑁 𝑁 −𝐹 . The trade-off is a heavier cryptographic setup — trusted or transparent SRS, pairing-based verification, and more expensive proof generation — and, as with the schemes above, a static post-dispersal storage profile: the per-node fragment size is fixed at dispersal time and does not adapt as additional honest nodes acknowledge. 6.2.3 Dispersal in Production BFT. Several recent BFT protocols integrate erasure-coded dispersal with consensus as a way to amortize the cost of broadcasting large transaction batches. DispersedLedger [22] decouples consensus on a small header from later retrieval of the full payload, allowing the payload to remain dispersed across replicas until needed. The dispersal layer uses a fixed (𝑘, 𝑁 ) AVID instantiation with 𝑘 = 𝐹 + 1; nodes store a single fragment of size |𝑀 |/(𝐹 + 1) and the storage profile is invariant to network conditions. Its dispersal layer is a Merkle-based AVID paired with the detect-and-reject remedy.

eAVID : Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

13

Kudzu [20] pursues a different point in the design space: a leader-based BFT atomic broadcast protocol that integrates erasure-coded dispersal directly into its voting path. The leader sends erasure-coded fragments of each proposed block to all other replicas, which in turn re-broadcast their fragments together with first-round votes; by combining fragments received from a sufficient number of replicas, every replica can reconstruct and finalize the block in just 2𝛿 network delays, where 𝛿 bounds the network delay, on the fast path. Kudzu uses a parameterized resilience regime 𝑁 = 3𝐹 + 2𝑃 + 1 (where 𝐹 is the worst-case Byzantine threshold and 𝑃 controls the fast-path quorum) and chooses its encoding parameters to match worst-case dispersal needs across this regime; as with DispersedLedger, the per-replica storage footprint is fixed at dispersal time and does not adapt to runtime network behavior. Kudzu’s distinguishing choice is on the coordination axis: rather than a standalone reliable broadcast or signature gather, dispersal is folded into the consensus voting path. The common thread across these schemes is that the per-node storage profile is fixed at dispersal time. AVID-RBC is the partial exception: it does drive storage down toward the optimal 𝑁𝑁−𝐹 , but only by encoding the message a second time after it has been committed and re-distributing the fragments. This requires a coordinated re-encode, and isn’t something individual nodes can perform autonomously. In every case, once the network turns out to be healthy and all 𝑁 nodes acknowledge, no node can safely shed its fragment, because doing so requires verifiable agreement on which fragments are held where. eAVID closes this gap using a single, static (2𝐹 + 1, 2𝑁 ) encoding with a single Merkle root per message. Every correct node adopts that same root, and a node’s Done announcement over it attests that the sender stored the fragments the root commits to. A node that has heard from all 𝑁 nodes can therefore decide on its own to discard a fragment. Because fragments are disjoint across nodes, at least 2𝐹 + 1 verified fragments survive whichever nodes prune and whichever do not, so no node’s decision depends on what the others chose. Pruning needs no certificate, no re-encoding, and no coordination among storage nodes.

14

Rithwik Kerur, Dahlia Malkhi, and Michael K. Reiter

References [1] Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. Asynchronous verifiable information dispersal with near-optimal communication. Cryptology ePrint Archive, Paper 2022/775, 2022. [2] Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang. Succinct erasure coding proof systems. Cryptology ePrint Archive, Paper 2021/1500, 2021. [3] Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987. [4] Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS), pages 191–201, 2005. Earlier IBM Research Report ZUR-1115 (2004). [5] George Danezis, Giacomo Giuliari, Eleftherios Kokoris Kogias, Markus Legner, Jean-Pierre Smith, Alberto Sonnino, and Karl Wüst. Walrus: An efficient decentralized storage network, 2025. [6] Juan A. Garay, Rosario Gennaro, Charanjit Jutla, and Tal Rabin. Secure distributed storage and retrieval. Theoretical Computer Science, 243(1–2):363–389, 2000. [7] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. Autobahn: Seamless high speed BFT. In Proceedings of the 30th ACM Symposium on Operating Systems Principles (SOSP), pages 1–23, 2024. arXiv:2401.10369. [8] G.R. Goodson, J.J. Wylie, G.R. Ganger, and M.K. Reiter. Efficient Byzantine-tolerant erasure-coded storage. In International Conference on Dependable Systems and Networks, 2004, pages 135–144, 2004. [9] James Hendricks, Gregory R. Ganger, and Michael K. Reiter. Verifying distributed erasure-coded data. In 26th ACM Symposium on Principles of Distributed Computing (PODC), pages 139–146, 2007. [10] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, Advances in Cryptology — ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 177–194, Berlin, Heidelberg, 2010. Springer. [11] Rithwik Kerur, Divyakant Agrawal, Dahlia Malkhi, Michael K. Reiter, and Amit Weider. eAID: Elastic asynchronous information dispersal with post-dissemination pruning. To appear in DISC 2026 https://arxiv.org/abs/2603.24761, 2026. [12] Quentin Kniep, Jakub Sliwinski, and Roger Wattenhofer. Solana alpenglow consensus: Increased bandwidth, reduced latency. White paper v1.1, Anza, 2025. [13] Thomas Locher and Yvonne-Anne Pignolet. Asynchronous verifiable information dispersal with low space and communication complexity. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’26, page 143–154, New York, NY, USA, 2026. Association for Computing Machinery. [14] Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. Dumbo-MVBA: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In 39th ACM Symposium on Principles of Distributed Computing (PODC), pages 129–138, 2020. [15] Atsuki Momose, Sourav Das, and Ling Ren. On the security of KZG commitment for VSS. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 2561–2575. ACM, 2023. Cryptology ePrint Archive, Paper 2023/1350. [16] Kamilla Nazirkhanova, Joachim Neu, and David Tse. Information dispersal with provable retrievability for rollups. In Proceedings of the 4th ACM Conference on Advances in Financial Technologies (AFT). ACM, 2022. Cryptology ePrint Archive, Paper 2021/1544; arXiv:2111.12323. [17] Torben Pryds Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Joan Feigenbaum, editor, Advances in Cryptology — CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 129–140, Berlin, Heidelberg, 1992. Springer. CRYPTO ’91, Santa Barbara, CA, USA. [18] Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335–348, 1989. [19] Irving S. Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960. [20] Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen. Kudzu: Fast and simple high-throughput BFT. arXiv:2505.08771, 2025. [21] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 2705–2718, 2022. Full version: arXiv:2201.05677. [22] Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. DispersedLedger: High-throughput byzantine consensus on variable bandwidth networks. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’22), pages 493–512, 2022.

Related documents

• eAVID: Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning#616633
• eAVID: Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning#616133
• MultiBallot: Verifiable and privacy-preserving E-Collecting in the Swiss setting#204724
• Discard Protocol#262404
• 14 CFR Part 193 — Protection of Voluntarily Submitted Information#505755