eAVID: Asynchronous Verifiable Information Dispersal with Post-Dissemination Pruning

Abstract

Asynchronous verifiable information dispersal (AVID) lets a sender spread a message across $N=3F+1$ nodes such that it remains recoverable despite up to $F$ Byzantine failures. Because dispersal must complete on $N-F$ responses, standard AVID protocols fix a $(F+1,N)$ erasure code and pay a $3\times$ storage blowup, whereas a synchronous system achieves the optimal $3/2\times$. 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 $N$ 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 $(2F+1,2N)$ Reed-Solomon code, commits to all $2N$ 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 $N-F$ 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 $N$ nodes, it can safely discard one of its two fragments unilaterally. Because fragments are disjoint across nodes, at least $2F+1$ verified fragments survive. Pruning requires no certificate, no coordination among storage nodes, and no re-encoding. Reconstruction is unchanged as any $2F+1$ verified fragments decode the message regardless of how fragments are distributed. eAVID halves steady-state per-node storage relative to the $(F+1,N)$ baseline when the network is healthy, and degrades gracefully to the baseline footprint when it is not.