Search papers, labs, and topics across Lattice.
The paper introduces eAVID, an innovative protocol for asynchronous verifiable information dispersal that reduces the per-node storage requirement by half compared to traditional methods when the network is healthy. By employing a single Reed-Solomon code and allowing nodes to prune unnecessary fragments post-dissemination, eAVID maintains the same dispersal bandwidth while ensuring that at least \(2F+1\) verified fragments remain recoverable despite Byzantine failures. This approach not only optimizes storage efficiency but also preserves the integrity of message reconstruction without the need for additional coordination or certificates.
eAVID cuts per-node storage in half during healthy network conditions while ensuring robust recovery against Byzantine failures.
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.
