Monotone Erasure Codes
Erasure codes are an important technique for storing and distributing data reliably across multiple nodes. The basic idea is to encode a file into several pieces of equal size and distribute these pieces, also called fragments, among different nodes. Even if some of the nodes become unavailable, the original file can still be reconstructed from the remaining fragments. Classical erasure codes, such as Maximum Distance Separable (MDS) codes – including Reed–Solomon codes – typically implement a k-out-of-n threshold structure. A file is encoded into \(n\geq k\) fragments of equal size and distributed across \(n\) nodes, such that any \(k\) of the \(n\) nodes are sufficient to reconstruct the original file. This is well-known in the literature on information dispersal.
In many contexts, however, some nodes are more likely to fail than others or may be more trustworthy than others. In this case, allocating exactly one fragment out of \(n\) to each node – regardless of how likely it may fail or how trustworthy it is – may not guarantee that \(k\) fragments will be available. This applies, in particular, to specific deployments of distributed cryptography and secure multiparty computation, to voting power in blockchains that rely on stake, and to the trust models of consensus protocols used in the XRP Ledger (see also documentation and this report) and the Stellar network (see also this paper). As a result, a system may require specific combinations of nodes to be available for data reconstruction.
An access structure \(\mathcal{A}\) on a set of nodes \(\mathcal{P}\) defines which subsets of nodes, referred to as access sets, are sufficient to reconstruct the data. A threshold access structure is a special case where each access set contains \(k\) out of \(n\) nodes. To represent such structures, one can use monotone Boolean formulas (MBF) built from AND, OR, and threshold operators \(\Theta\) along with atoms where each atom corresponds to a node. These formulas naturally translate into an access tree of \(\mathcal{A}\): a rooted, labeled tree whose internal vertices correspond to operators and whose leaves are labeled with node identifiers. A special kind of an access structure is called partitioned access structure; such an access structure can be hierarchically decomposed in the sense that the MBF that represents it corresponds to a tree on the inputs, i.e., on \(\mathcal{P}\). Every node in \(\mathcal{P}\) appears at most once in the MBF that describes the access structure.
Example of a partitioned access structure represented by an access tree \(T\), i.e., each node in \(\mathcal{P}\) appears at most once in \(T\).
Given an access structure \(\mathcal{A}\) on a set of nodes \(\mathcal{P}\) and a file \(f\), the goal is to distribute information among the nodes in \(\mathcal{P}\) such that each access set is able to reconstruct \(f\). For this purpose, we introduce monotone erasure codes that extend classical erasure codes and respect arbitrary trust assumptions characterized by \(\mathcal{A}\): fragments are assigned to nodes in such a way that each \(A \in \mathcal{A}\) has sufficient information for reconstruction. All access sets are assumed minimal, but every set of nodes in \(\mathcal{P}\) that extends an access set may also reconstruct the data; this makes the data reconstruction capability monotone on \(\mathcal{P}\). Formally, a monotone erasure code consists of a pair of algorithms: Encode takes a file \(f\) as input and outputs a vector of \(n\) fragments such that each node in \(\mathcal{P}\) receives one fragment, where fragments may vary in size unlike standard erasure codes. Decode takes a collection of fragments and returns the original file whenever it receives the fragments from an access set as input, i.e., the monotone erasure code for \(\mathcal{A}\) must be complete.
Comparison of classical erasure codes and monotone erasure codes.
Linear Monotone Erasure Codes
Linear monotone erasure codes for an access structure \(\mathcal{A}\) are an important type of monotone erasure codes where the file and the fragments are vectors over a finite field \(\mathbb{F}_q\) and the encoding involves only linear operations. In particular, encoding is performed using a full-rank matrix \(G\in \mathbb{F}_q^{k \times m}\) and a labeling function \(\phi:\{1,\ldots,m\}\rightarrow \mathcal{P}\) that assigns each column of \(G\) to a node \(p_i\in \mathcal{P}\). These columns correspond to encoded elements of \(\mathbb{F}_q\), representing the fragment of each node. In more detail, the fragment \(g_i\) of \(p_i\) is given by multiplying the file \(f\) with the matrix \(G_{p_i}\) that consists of the columns of \(G\) that are assigned to \(p_i\). Note that \(g_i\) may equal \(\bot\), which means that \(p_i\) does not receive any information to store. The key requirement is that the matrix must reflect the given access structure \(\mathcal{A}\). The problem of constructing a linear monotone erasure code for \(\mathcal{A}\) can therefore be viewed as finding an encoding matrix and a labeling function such that each access set is sufficient.
Left: Encoding matrix \(G\) and labeling function \(\phi\) of a linear monotone erasure code for an access structure \(\mathcal{A}\). Right: Computation of the fragment \(g_i\) of node \(p_i\).
An important challenge of constructing linear monotone erasure codes is that a more general access structure can require additional redundancy. If the original file is of size \(\kappa\), while the total amount of encoded information stored across all nodes is \(\mu\), the storage overhead can be expressed as
\[\beta=\frac{\mu-\kappa}{\kappa}.\]The goal is therefore not only to construct a linear monotone erasure code that realizes the desired access structure, but also to keep the overhead \(\beta\) as small as possible. Minimizing the storage overhead can be formulated as a linear programming problem (LPP). Solving LPP is only efficient if \(\mathcal{A}\) has a compact (e.g., polynomial-size) description in the number of nodes. However, \(\mathcal{A}\) may contain exponentially many (in \(n\)) access sets.
We now desribe two efficient algorithms that, given an access tree of \(\mathcal{A}\), construct a complete linear monotone erasure code without solving the corresponding LPP. The first algorithm works for arbitrary access structures but does not necessarily guarantee minimal storage overhead. The second algorithm focuses on partitioned access structures and produces a code with minimal overhead.
General Construction
For an access tree \(T\) of an access structure \(\mathcal{A}\) as input, our first algorithm outputs an encoding matrix and a labeling function. The encoding matrix of \(\mathcal{C}\) has a block-wise MDS property that ensures completeness of \(\mathcal{C}\). MDS codes are used as building blocks, while the access structure determines how the encoded information is distributed. The intuition behind the code is given through its encoding algorithm: Given a file \(f\) and an access tree \(T\) with a root node labeled \(t\) that has \(r\) children, i.e., the operator \(\Theta_t^r\), the algorithm proceeds as follows. First, it encodes \(f\) using a linear monotone erasure code that generates \(r\) fragments and such that any \(t\) of them can reconstruct \(f\). Then, it encodes each of the \(r\) resulting fragments again. Specifically, for each child \(v_i\) of the root with label \(t_i\) and with \(r_i\) children, the fragment \(g_i\) assigned to \(v_i\) is encoded using a linear monotone erasure code that generates \(r_i\) fragments and such that any \(t_i\) of them are enough to reconstruct \(g_i\). The encoding function proceeds in this way until it reaches the leaves. In the general case, this construction does not necessarily deliver a linear monotone erasure code with minimal overhead.
Intuition behind the general construction of a linear monotone erasure code for a given access structure.
Construction for Partitioned Access Structures
Our second algorithm focuses on constructing linear monotone erasure codes for partitioned access structures. Recall that, for partitioned access structures, every node in \(\mathcal{P}\) appears at most once in the corresponding MBF. For these kind of access structures, it is possible to determine how much encoded information each node should receive and construct a linear monotone erasure code that realizes the desired access structure with minimal storage overhead without solving LPP. The intuition behind the algorithm is to determine which nodes actually need to store information and how much information each of them should receive. In particular, some nodes can be omitted entirely if this reduces the storage overhead while still respecting the given access structure. An illustrative example is given by the access structure
\[\mathcal{A}=\Theta_2^3(\Theta_1^1(a),\Theta_1^1(b),\Theta_1^3(c,d,e)).\]The construction observes that the nodes c, d, and e do not necessarily need to receive information. Instead, the construction can omit these nodes and allocate sufficient information to a and b. In particular, for a file \(f\) of size \(4\), instead of assigning information of size \(2\) to a and b, we assign information of size \(4\) (hence, the full file) to a and b and change the root from \(\Theta_2^3\) to \(\Theta_1^2\). In this way, the overhead can be reduced from \(5/2-1 = 3/2\) to \(1\), which is the minimum achievable overhead for \(\mathcal{A}\). This illustrates how the construction can simplify the access structure to reduce the storage overhead by removing nodes while preserving the original access structure. As a result, the algorithm always identifies the fragment assignment that minimizes the storage overhead.
Example of a tree reduction and fragment assignment, reducing the storage overhead from 3/2 (left) to its minimum value of 1 (right).
Generalized AVID Protocol
Erasure codes are found in many Byzantine consensus and broadcast algorithms for blockchains today (e.g., Ethereum with PeerDAS, Solana with the Alpenglow upgrade, MonadBFT). The reason is that they allow for efficient information dispersal, often using algorithms in the vein of the protocol of Cachin and Tessaro for asynchronous verifiable information dispersal (AVID). We show how monotone erasure codes generalize this classic approach to obtain a communication-efficient generalized AVID protocol that works not only for Byzantine quorum systems that tolerate \(f\) failures out of \(n\) nodes but also for general Byzantine quorum systems. From generalized AVID – or GAVID, as we call it – one can also obtain a communication-efficient Byzantine reliable broadcast protocol for an arbitrary Byzantine quorum system. This paves the way to integrating monotone erasure codes into other protocols like consensus or into distributed storage systems.
For more information, check out the full research paper.