Source-linked AI summary
Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity
Thomas Locher, Yvonne-Anne Pignolet
TL;DR
Existing AVID protocols optimize storage and retrieval but give less attention to dispersal and node recovery, which matter in long-running Byzantine storage systems. This paper introduces a two-dimensional encoding scheme and dispersal algorithm, achieving low costs across operations while retaining optimal retrieval communication and supporting tunable trade-offs. The authors report lower storage, dispersal, and recovery costs than prior approaches, with deployment-specific variants.
Problem
Existing AVID protocols achieve optimal storage and retrieval complexity but pay insufficient attention to data dispersal and failed-node recovery.
Method
The paper combines a novel two-dimensional matrix encoding scheme with a bespoke dispersal algorithm using erasure codes and vector commitments.
Results
The main protocol has storage overhead factor 3, improves on Red Stuff by 33%, reduces dispersal communication by 14% and recovery communication by 40%, and retains optimal retrieval overhead.
Takeaways & Limitations
The protocols balance storage, dispersal, retrieval, and recovery costs, while the parameterized variant permits tuning these trade-offs for different use cases.
Takeaways & Limitations
Retrieval may fail before n−t honest nodes have terminated dispersal, requiring the client to drop or resubmit the request after a timeout.
Abstract
from arXiv · showhide
The primary goal of a distributed storage system is to ensure that clients can both write and read data in a reliable and consistent manner, even in the presence of failures. While existing asynchronous verifiable information dispersal (AVID) protocols achieve optimal space complexity for storage and communication complexity for data retrieval in a Byzantine setting, the crucial operations of data dispersal and node recovery have received less attention. We propose an efficient AVID protocol that simultaneously guarantees low complexities for dispersal, storage, retrieval, and recovery. At the core of the proposed protocol lies a novel mechanism to encode data in a two-dimensional matrix and a bespoke dispersal algorithm. The protocol maintains an optimal communication complexity for retrieval while substantially improving upon the state of the art for recovery. Additionally, we describe how the protocol can be modified in order to reduce the space complexity and the communication complexity for dispersal, at the expense of a higher communication complexity for retrieval and recovery. As the proposed protocols strike a balance across all considered metrics, they are suitable for a broad range of real-world use cases.
1 Introduction
Distributed storage workloads require AVID protocols to reduce not only storage and retrieval costs but also dispersal and recovery overheads. The paper proposes protocols balancing these metrics, with concrete savings over prior approaches.
- Motivation: AVID protocols have traditionally emphasized storage and retrieval, while dispersal and node recovery remain operational bottlenecks.Many protocols require a replacement node to download the entire dataset after failure.
- Contributions: The main protocol guarantees optimal retrieval overhead and strictly outperforms Danezis et al. in all other metrics.The protocol therefore combines optimal retrieval with improvements in the remaining listed dimensions.
- Contributions: The parameterized variant trades storage and dispersal cost for retrieval and recovery efficiency, allowing deployment-specific tuning.For γ = 1.8, space complexity is nearly optimal; for γ = 3/2, dispersal complexity is cut in half relative to Alhaddad et al.
- Operational impact: For n = 100 storing a 1 GB item, each node stores 30 MB under the proposed protocol versus 45 MB under Red Stuff.At 1 PB scale, network-wide storage falls from 4.5 PB to 3 PB, while failure recovery falls from 75 TB to 45 TB per replacement node.
2 Model and Preliminaries
The model studies asynchronous storage among nodes tolerating up to t Byzantine faults, with AVID defined by termination, agreement, availability, and correctness. Complexity is measured across storage, communication, rounds, and recovery, using erasure coding and commitments.
- System model: The storage network has n nodes and tolerates up to t = ⌊(n−1)/3⌋ Byzantine nodes that may behave arbitrarily.Communication uses authenticated channels in a static, known topology and an asynchronous network with unbounded message delays.
- AVID properties: AVID requires termination, agreement, availability after ℓ honest nodes terminate, and consistent retrieval results.The protocol uses ℓ = n−t because this minimizes its complexities, while smaller ℓ values are also possible.
- Complexity measures: Space complexity counts long-term bits stored across honest nodes, whereas communication complexity counts total bits transmitted for an operation.Temporary buffering is excluded from space complexity, and recovery required for first retrieval is counted as dispersal.
- Coding primitives: Erasure coding reduces AVID complexity by allowing any k of n encoded fragments to reconstruct the original message.The paper assumes systematic linear erasure codes, with recovery fragments formed as linear combinations over a finite field.
- Two-dimensional primitives: The construction extends erasure coding to matrices, where n−t elements from a row or column suffice to derive that entire row or column.A matrix commitment and proof matrix protect element integrity and support reconstructing proofs for full rows or columns.
3.1 Overview
The proposed protocol encodes data into a two-dimensional matrix and distributes row and column shares with integrity proofs. Retrieval reconstructs the data from row information, while recovery reconstructs a failed node’s shares from encoded elements supplied by other nodes.
- Overview: Each node is assigned row data and column data consisting of the first n−t elements of its corresponding matrix row and column.Membership proofs accompany the stored data, and dispersal disseminates these shares despite Byzantine nodes or clients.
- Encoding: The data item is converted into an (n−t) × (n−t) matrix, expanded column-wise, and then row-wise into an n × 2n matrix.No node or client explicitly stores the entire matrix; operations use only required portions.
- Retrieval: Retrieval gathers row data from storage nodes and decodes the columns of A′ to reconstruct the data item.The client uses the received row elements to obtain enough information from every encoded column.
- Recovery: During recovery, each honest node sends encoded elements from its row and column to the replacement node.Enough replies allow reconstruction of the failed node’s row and column data using elements from A and the auxiliary encoded regions.
- Integrity: Commitments are exchanged alongside the matrix-derived information to detect invalid fragments and preserve integrity under Byzantine behavior.The client verifies the reconstructed matrix commitment before extracting the data item.
3.2 Data Encoding and Integrity
The protocol encodes data into a two-dimensional matrix using row- and column-wise erasure coding, enabling reconstruction from partial rows or columns. Systematic encoding allows the original data to be extracted from designated matrix entries, while commitments and proofs support integrity verification.
- Encoding interface: The client-side encoding and decoding helpers support matrix construction, extraction, and data-integrity checks.These functions are collected in Algorithm 1.
- Matrix construction: The create_matrix function splits m into (n−t)^2 elements, places them in A, and expands both dimensions with recovery elements.The resulting matrix has n×2n dimensions.
- Recovery property: 2n^2 elements result, and any n−t rows or columns containing at least n−t elements each suffice to recover m.Row-wise and column-wise decoding apply erasure decoding in two stages.
- Data extraction: The extract function concatenates M[i,j] for i,j∈[n−t] to reconstruct m because the encoding is systematic.These entries directly contain the data elements of m.
3.3 Dispersal
Dispersal combines direct row-and-column delivery with authenticated acknowledgments, reliable broadcast, and targeted forwarding so honest nodes can obtain their storage data asynchronously. The key communication saving is that acknowledged nodes already hold elements useful for reconstructing missing nodes’ rows and columns.
- Communication insight: The communication saving comes from acknowledged nodes already carrying one row and one column element for every other node, avoiding retransmission of that data.The client only supplies the second half of rows for at most t non-acknowledging nodes, while additional forwarding preserves reconstruction guarantees.
- Initial delivery: The client constructs M, commits to it, creates proofs, and sends each node its row and column data with corresponding proofs.The identifier is the commitment C_M, and nodes validate the tuple before acknowledging receipt.
- Client coordination: After n−t valid acknowledgments, the client reliably broadcasts the acknowledged set S and sends spread payloads containing recovery elements for nodes outside S.These steps address nodes that did not acknowledge the initial disperse message.
- Row reconstruction: Acknowledged nodes forward row elements to missing nodes, which decode rows after receiving enough valid row_info messages and then generate row proofs.A row can be reconstructed from n−2t valid row_info messages.
- Column reconstruction: Nodes send column_info messages so missing nodes can decode columns from n−t valid messages and generate the corresponding column proofs.The reconstructed column data and proofs are then stored.
- Termination: Ready messages trigger termination once nodes have sufficient confirmations, storage data, and column information.Nodes broadcast ready after receiving n−t info_sent or t+1 ready messages, and terminate after n−t ready messages.
3.4 Retrieval
Retrieval collects authenticated row fragments from storage nodes and reconstructs the data item through matrix decoding and commitment verification. Retrieval before sufficient dispersal may fail, because AVID availability is guaranteed only after n−t honest nodes terminate dispersal.
- Client retrieval: The client requests the identifier from all nodes and waits for n−t valid signed responses containing rows and proofs.Each valid response contains n−t row elements with valid proofs.
- Decoding and verification: The client decodes columns of A, reconstructs M through column-wise and row-wise erasure encoding, and checks whether C_M equals the identifier.If verification succeeds, m is extracted; otherwise ⊥ is returned.
- Client cost: Constructing the entire M for commitment recomputation may burden lightweight clients.Robust dispersal could shift validity verification to storage nodes, but the paper omits that optimization because its practical computational savings remain un demonstrated.
- Availability condition: Retrieval is not guaranteed before n−t honest nodes have terminated dispersal.Clients should drop or resubmit requests after a timeout when dispersal is incomplete.
3.5 Recovery
Recovery reconstructs a failed node’s row and column state from authenticated fragments supplied by surviving nodes. After decoding both vectors and regenerating their proofs, the replacement node restores the missing storage state.
- Recovery target: A replacement node must obtain the failed node’s ith row and column data derived from the matrix M.Recovery may wait until the required n−t nodes possess storage data.
- Fragment exchange: Each surviving node re-encodes its row and column and sends the replacement node the corresponding elements with commitment proofs.The row and column element order is swapped because each survivor’s data corresponds to the failed node’s complementary dimension.
- State reconstruction: After receiving and validating messages from at least n−t honest nodes, the replacement node decodes the failed row and column.This yields the first n−t elements of each vector, namely r_i and c_i.
- Proof restoration: The replacement node regenerates missing commitment proofs from the recovered row and column data and their received proofs.The gen_proofs function supplies the proof data needed for the restored state.
- Failure assumption: Recovery remains possible with t′≤t simultaneous failures because at least n−t nodes are assumed not to crash or deviate.This assumption guarantees sufficient recover messages.
3.6 Analysis
Protocol P is proven to satisfy AVID correctness properties and provides explicit bounds for storage, communication, and communication rounds. Its recovery mechanism reconstructs a failed node’s state from distributed row and column information rather than requiring the entire dataset.
- Correctness: Protocol P satisfies all AVID properties specified in Definition 2.1.
- Correctness: Honest-client dispersal terminates at every honest node, and termination by one honest node implies eventual termination by all honest nodes.
- Correctness: If n−t honest nodes terminate dispersal, clients eventually retrieve a data item and all clients retrieve the same item; with an honest writer, it is the original item.
- Recovery: A replacement node recovers a dispersed item’s state from valid row and column elements and their proofs, provided the item reached n−t honest nodes.
- Complexity: 3|m| + O(n^2|π|) is Protocol P’s space complexity for storing m.
- Complexity: 6|m| + O(n^2|π|) is Protocol P’s dispersal communication complexity, while the protocol requires 7 dispersal, 2 retrieval, and 1 recovery round.
- Complexity: Latency can be reduced to 6 rounds without changing communication complexity, or to 5 rounds using either an O(n^3|π|) cost or threshold cryptography with secure setup.
4 Protocol Variant
The protocol variant uses an MSR code and a storage parameter γ to trade lower storage and dispersal costs against higher retrieval and recovery costs. It covers γ∈[3/2,n], while the main protocol has storage overhead factor 3.
- Design: The variant parameterizes storage overhead by γ:=n/ℓ, where ℓ nodes must provide data for retrieval.
- Design: γ∈[3/2,n] is the supported storage-overhead range, while the main protocol achieves storage overhead factor 3.
- Design: The variant combines a simplified dispersal algorithm with an MSR code, whose redundancy supports efficient node recovery using row data and proofs.
- Complexity: Each node stores |m|/ℓ bits, yielding total space complexity γ|m|.
- Complexity: For recovery, a replacement node obtains |m| (d+t)/(ℓ(d−ℓ+1)) bits from d distinct nodes.
- Trade-off: The variant reduces storage and dispersal costs when lower space and dispersal communication are prioritized, but retrieval and recovery costs increase as γ decreases.
5 Related Work
Prior AVID research established strong storage and retrieval guarantees but left dispersal and node recovery as important efficiency gaps. This work bridges storage-optimal, repair-heavy protocols and repair-optimal, storage-heavy designs through co-designed encoding and dispersal mechanisms.
- AVID generalized verifiable information dispersal to asynchronous networks with optimal storage and retrieval complexity.
- Most protocols erasure-code data into fragments, send one fragment per node, and reliably broadcast a commitment for consistency verification.
- O(|m|) dispersal protocols trade off other metrics: Alhaddad et al. achieve 3|m| for dispersal, storage, and retrieval, while a later scheme reaches optimal storage and retrieval but 9|m| dispersal.
- Efficient node repair can reduce downloads below the original data size, but typically increases storage and retrieval complexity.
- Red Stuff uses asymmetric two-dimensional encoding and achieves recovery bandwidth inversely proportional to the number of nodes, but stores 4.5|m|/n bits per node.
- This work uses an n×2n matrix with symmetric encoding, storing 3|m|/n bits per node versus Red Stuff’s 4.5|m|/n.
6 Conclusion
The paper demonstrates that dispersal and recovery can improve while retrieval communication remains optimal. Lower bounds for simultaneous trade-offs across all operations remain an open problem.
- The protocols improve dispersal and recovery operations while achieving optimal communication complexity for retrieval.
- Determining lower bounds for trade-offs across all operations simultaneously remains an open problem for future research.