Technical Summary: Monotone Erasure Codes

1. Problem Statement

Traditional erasure codes, such as Reed-Solomon (MDS) codes, operate under a threshold failure assumption. In these systems, data is divided into $k$ pieces and encoded into $n$ fragments such that any $k$ fragments suffice for reconstruction. This model assumes that any subset of $k$ nodes is equally likely to be available or fail, regardless of the specific identity of the nodes.

However, modern distributed systems, particularly in blockchain and cryptocurrency (e.g., Stellar, XRP Ledger), utilize generalized failure assumptions or Byzantine quorum systems. In these contexts, trust is not uniform; some nodes are more trustworthy than others, and failure patterns are not purely random but depend on specific subsets of nodes. Existing threshold-based codes cannot efficiently accommodate these arbitrary trust assumptions without significant overhead or structural mismatch. The paper addresses the need for erasure codes that respect arbitrary monotone access structures, where specific subsets of nodes (access sets) are guaranteed to reconstruct data, while others may not.

2. Methodology

The paper introduces Monotone Erasure Codes, a generalization of classical erasure codes designed to work with arbitrary access structures $\mathcal{A} \subseteq 2^{\mathcal{P}}$, where $\mathcal{P}$ is the set of nodes.

2.1 Definitions and Formalism

• Monotone Erasure Code: A scheme consisting of Encode and Decode algorithms. Encode maps a file $f$ to a vector of fragments $(g_1, \dots, g_n)$, where fragments may have different sizes. Decode reconstructs $f$ from any subset of fragments corresponding to an access set $A \in \mathcal{A}$.
• Efficiency: Measured by overhead $\beta = (\mu - \kappa) / \kappa$, where $\kappa$ is the input file size and $\mu$ is the total size of all fragments. The goal is to minimize $\beta$.
• Linear Monotone Erasure Codes: A specific class where encoding and decoding are linear operations over a finite field $\mathbb{F}_q$. The encoding is defined by a generator matrix $G$ and a labeling function $\phi$ that maps columns of $G$ to nodes. A set of nodes is sufficient if the submatrix of $G$ corresponding to those nodes has full rank ($k$).

2.2 Construction Approaches

The paper presents three distinct methods for constructing these codes:

1. Basic Construction (Non-Optimal):

   • Based on a Monotone Boolean Formula (MBF) representing the access structure.
   • The algorithm recursively traverses the access tree. For an AND node, the file is split into chunks; for an OR node, the file is replicated.
   • Result: Guarantees completeness but often results in high overhead due to redundant replication in the tree structure.

2. Efficient Linear Construction (Sub-Optimal):

   • Uses a recursive algorithm that builds a block-wise MDS matrix.
   • It constructs the encoding matrix by combining Vandermonde matrices (for threshold operators) using Kronecker products and identity matrices to align dimensions.
   • Result: Computationally efficient (polynomial in the size of the access tree) but does not guarantee minimal overhead.

3. Optimal Linear Construction (via Linear Programming):

   • General Case: Formulates the problem of finding the optimal fragment distribution as a Linear Programming Problem (LPP). The objective is to minimize the sum of fragment weights assigned to nodes, subject to constraints that every access set holds at least $k$ "base" fragments (derived from an underlying MDS code).
   • Partitioned Access Structures: For a specific class of structures (hierarchical, where each node appears exactly once in the MBF, e.g., Stellar's trust model), the paper provides a specialized recursive algorithm (Algorithm 2). This algorithm solves the LPP efficiently ($O(n^2)$) by identifying which subtrees to include or exclude to minimize overhead, effectively determining an optimal assignment of base fragments.

2.3 Protocol Application: GAVID

The paper integrates these codes into a distributed protocol called General Asynchronous Verifiable Information Dispersal (GAVID).

• Generalization: Extends the classic AVID protocol (Cachin and Tessaro) from threshold systems to general Byzantine quorum systems.
• Mechanism: Uses the kernel system of the quorum system as the access structure for the monotone erasure code.
• Key Concepts: Introduces Reliable Sets (sets that contain a kernel disjoint from any faulty set) to ensure availability and consistency in the asynchronous setting.
• Optimization: Proposes GAVID-H, which replaces the full verification vector with a Merkle tree root, reducing communication complexity.

3. Key Contributions

1. Definition of Monotone Erasure Codes: The paper formally defines a new coding primitive that generalizes classical erasure codes to arbitrary monotone access structures, allowing for non-uniform trust assumptions.
2. Construction Algorithms:
   • Provides a computationally efficient method to build linear monotone erasure codes for any access structure (though not always optimal in overhead).
   • Provides a method to construct optimal linear monotone erasure codes by solving a linear programming problem derived from the access structure.
3. Partitioned Access Structures: Analyzes the specific case of partitioned access structures (common in practice) and presents an efficient algorithm to construct optimal codes for them, characterizing their overhead.
4. GAVID Protocol: Formulates a general asynchronous verifiable information dispersal protocol (GAVID) that utilizes monotone erasure codes to achieve communication-efficient Byzantine reliable broadcast for arbitrary quorum systems.

4. Results and Analysis

• Overhead Bounds: For a general access structure with minimum access set size $\tau$, the overhead $\beta$ of an optimal linear monotone erasure code is bounded by $\beta \le (n - \tau)/\tau$ for large $k$. This implies that if the smallest access set is close to the total number of nodes, the overhead approaches zero.
• Efficiency of Partitioned Construction: The specialized algorithm for partitioned access structures runs in $O(n^2)$ time, which is significantly faster than solving the general LPP directly when the number of access sets is exponential.
• Protocol Complexity:
  • GAVID Disperse: Message complexity $O(n^2)$; Communication complexity $O(n(1+\beta)|f| + n^3|H|)$.
  • GAVID-H (Merkle optimized): Reduces communication complexity to $O(n(1+\beta)|f| + n^2(\log n)|H|)$ and storage complexity to $O((1+\beta)|f| + n(\log n)|H|)$.
• Correctness: The paper proves that GAVID satisfies Termination, Agreement, Availability, and Correctness properties for any Byzantine quorum system, provided a monotone erasure code exists for the system's kernel structure.

5. Significance and Claims

The paper claims that monotone erasure codes are a critical enabler for trust-aware distributed systems. By moving beyond the rigid "any $k$ out of $n$" threshold model, these codes allow systems to:

• Reduce Redundancy: Optimize storage and communication overhead by assigning more data to trustworthy nodes and less to risky ones, rather than treating all nodes equally.
• Support Complex Trust Models: Directly implement the trust assumptions found in real-world blockchain networks (like Stellar) where trust is hierarchical and non-uniform.
• Generalize Protocols: Provide a foundational primitive (GAVID) that allows existing efficient broadcast and consensus protocols to function under general Byzantine quorum systems, not just simple threshold models.

The authors note that while they provide an efficient construction for partitioned structures, the problem of constructing an optimal monotone erasure code for an arbitrary access structure (given as an MBF with exponentially many sets) remains an open question. They also suggest future work in dynamic codes and the application of other coding theory techniques (e.g., rateless codes) to this setting.