Monotone Erasure Codes Vivien Bammert∗ University of Bern [email protected]
arXiv:2605.22426v1 [cs.IT] 21 May 2026
Orestis Alpos Common Prefix [email protected]
Annalisa Cimatti∗ University of Bern [email protected] Giuliano Losa Stellar Development Foundation [email protected]
Christian Cachin University of Bern [email protected] 22 May 2026
Abstract Erasure codes are a critical component in reliable storage systems today, and many blockchain systems use consensus protocols that involve erasure codes to reduce their communication cost. Existing erasure codes, such as Reed-Solomon codes, make it easy to design systems that rely on a threshold failure assumption, meaning that at most a fixed threshold of nodes may fail, regardless of which nodes fail. However, recent blockchain systems have departed from this simple model. Instead, they use generalized failure assumptions or general Byzantine quorum systems that allow expressing that, e.g., some nodes may be more trustworthy than others. This paper introduces monotone erasure codes that respect arbitrary trust assumptions on a set of nodes, characterized by a monotone access structure or the related notion of a quorum system. The paper first describes a method for constructing a monotone erasure code from any access structure given by a monotone Boolean formula (MBF). Next, the important notion of a linear monotone erasure code is introduced, which works on vectors over a finite field and where the encoding is a linear operation. A method to build a linear monotone erasure code for any access structure is presented. This method is computationally efficient, but it does not provide an optimal code in general. An alternative algorithm to construct an optimal linear monotone erasure code for an access structure given as an MBF is shown that uses an ordinary, maximum-distance separable erasure code underneath. An important class of non-threshold access structures used in the practice of cryptocurrencies is then examined, and an optimal monotone erasure code for these access structures is constructed. Last but not least, this work also shows how to use monotone erasure codes to obtain a communication-efficient, generalized version of the well-known asynchronous verifiable information dispersal (AVID) primitive, which is a key building block for developing efficient reliable broadcast and consensus protocols.
1
Introduction
As computing systems collect and process more information than ever today, it becomes critical to store and communicate tremendous amounts of information securely, reliably, and economically. An erasure code provides a well-known method to divide large volumes of data into pieces so that some pieces may be lost but the data itself can still be recovered. This has many applications: Distributed storage systems [32] ∗ Contact authors: Institute of Computer Science, University of Bern, Neubrückstrasse 10, 3012 CH-Bern, Switzerland.
1
allocate pieces of information across multiple disks or storage nodes for increased resilience, and in the neighboring field of reliable communication, network coding protocols [16] split large files into blobs that are subsequently transmitted individually for efficiency and can be recombined at the receiver. In the realm of blockchains and cryptocurrencies, transaction data and system state have become so large that erasure codes are used broadly to store and communicate such data efficiently. For example, some so-called data-availability networks use erasure codes to provide transaction data as a service [19], and many recent Byzantine-tolerant consensus protocols disseminate data with erasure codes [36]. Many widely used erasure codes, such as maximum-distance separable (MDS) codes (e.g., Reed– Solomon codes), divide their input data into 𝑘 pieces and encode it into 𝑛 > 𝑘 so-called fragments of equal size such that any 𝑘 of the 𝑛 fragments are sufficient to reconstruct the original data. By allocating each fragment to a distinct node in a set P of cardinality 𝑛 (e.g., disks, storage servers, or consensus nodes) and by using cryptographic authentication (e.g., a Merkle commitment or per-fragment hashes) to filter out invalid fragments, one can recover the original data even if 𝑛 − 𝑘 nodes fail. This is more efficient than replicating the full data 𝑛 − 𝑘 + 1 times. 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 𝑛 to each node – regardless of how likely it may fail or how trustworthy it is – may not guarantee that 𝑘 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 [10] and the Stellar network [25]. In those scenarios, the underlying assumption is typically captured by an access structure [3, 20] or a quorum system [26]. In this paper, we introduce monotone erasure codes that respect arbitrary trust assumptions on a set of nodes P characterized by any access structure A ⊆ 2 P ; such codes assign fragments to nodes and ensure that, for every access set 𝐴 contained in A, the fragments assigned to the members of 𝐴 are sufficient to reconstruct the data. We assume that all access sets are minimal, but every set of nodes in P that extends an access set may also reconstruct the data; this makes the data reconstruction capability monotone on P. In more detail, a monotone erasure code consists of a pair of algorithms called Encode and Decode: Algorithm Encode receives a file as input and outputs a vector of 𝑛 fragments such that each node in P receives one fragment. In contrast to standard erasure codes, the fragments may have different sizes. The Decode algorithm, on input a collection of fragments, outputs some information. The code respects A in the sense that Decode returns the original information whenever it receives the fragments from an access set as input. Analogously to standard coding theory, we focus on the important case of linear monotone erasure codes, where the file and the fragments are vectors over a finite field F𝑞 and the encoding involves only linear operations. Important parameters for monotone erasure codes are the size of the input file, denoted 𝜅, and the combined size of all fragments, called 𝜇. Therefore, the efficiency of a code is measured by its overhead 𝛽 = 𝜇−𝜅 𝜅 , and this should be as small as possible. In other words, an efficient monotone erasure code adds as little redundancy as possible. In Section 3, we first formalize the notion of a monotone erasure code and its overhead. Then we provide a simple but inefficient method to construct monotone erasure codes. It works for any access structure that is given by a monotone Boolean formula (MBF) with threshold operators on P, i.e., from formulas in variables that represent the nodes in P. Such an expression may not be a compact description of the access structure; in this case, the resulting monotone erasure code can have a large overhead. As for other codes, monotone erasure codes that work over finite fields and where encoding is a linear operation are an important notion, as they have a rich mathematical structure. We formalize them in Section 4 and show how they generalize MDS erasure codes. The most prominent MDS erasure codes are Reed-Solomon codes [31, 30]; we also call MDS codes threshold codes because their access structure consists of all subsets of P with cardinality 𝑘. In Section 5, we present an efficient construction of a linear monotone erasure code for any access structure. However, in general, this approach does not always achieve minimal storage overhead. Therefore, in Section 6 we focus on constructing optimal linear monotone erasure codes. An algorithm to
2
generate a linear monotone erasure code for an arbitrary access structure from an MDS erasure code is provided. To optimize the overhead of the monotone erasure code, our algorithm involves solving a rational linear programming problem whose complexity depends on the number of access sets. An important class of non-threshold access structures used in practice are access structures stemming from a hierarchy of domains, and we examine them in Section 7. Such access structures form a hierarchy of entities, where each entity at one level is comprised of multiple entities at a lower level. The Stellar network [25] is a real-world system using this kind of access structures. Formally, these correspond to MBFs where each variable appears at most once. We give an efficient algorithm to construct an optimal monotone erasure code for such a partitioned access structure, and characterize its overhead. In Section 8, we turn to distributed protocols. Erasure codes are found in many Byzantine consensus and broadcast algorithms for blockchains today [6, 33, 24, 22, 36] because they allow for efficient information dispersal, often using protocols in the vein of the protocol of Cachin and Tessaro [5] for asynchronous verifiable information dispersal (AVID). We show how to use monotone erasure codes to generalize this classic protocol to obtain a communication-efficient generalized AVID protocol that works not only for Byzantine quorum systems that tolerate 𝑓 failures out of 𝑛 nodes but also for general Byzantine quorum systems. The key ingredients that allow the generalization are, of course, monotone erasure codes, but also the notion of kernels (generalizing sets of 𝑓 + 1 nodes) and our novel notion of reliable sets. From generalized AVID, or GAVID, 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. Finally, erasure codes for reducing communication complexity in distributed computing have become a prominent topic recently. We review some of the literature and compare our notions to those from related work in Section 9. Contributions.
The four principal contributions of this work are:
• To propose monotone erasure codes that generalize classical erasure codes, which address only threshold access structures; • To provide two methods to build a linear monotone erasure code for any monotone access structure: one that is computationally efficient and one that minimizes the overhead of the code; • To analyze the special case of a partitioned access structure, for which we build a linear monotone erasure code with optimal overhead; and • To formulate a general asynchronous verifiable information dispersal protocol (GAVID) for building communication-efficient Byzantine-tolerant reliable broadcast with non-threshold quorum systems.
2
Access Structures
Let P be a set of 𝑛 nodes {𝑝 1 , . . . , 𝑝 𝑛 }. For each 𝑛 ∈ N, we denote the set {1, . . . , 𝑛} by [𝑛]. In many applications, it is necessary to specify which groups of nodes are able to perform certain actions. For example, in a distributed storage system, we want to ensure resilience against data loss at some nodes. In other words, even if certain nodes lose their stored data, the set of remaining nodes should still be able to recover the original information. The collection of all such sets is called an access structure. Definition 1 (Access structure). An access structure A on P is a collection of subsets of P such that no set is contained in another. Each set 𝐴 ∈ A is called an access set. Note that in the literature, the structure described in Definition 1 is usually called a minimal access structure. However, in our context, if an access set is able to reconstruct the stored data, then all supersets of this set can also reconstruct it. This makes the ability to reconstruct data monotone in P. Thus, it 3
suffices to consider only the minimal collection of access sets and show that these sets can reconstruct the data. It is possible to represent any monotone access structure using a monotone Boolean formula (MBF). An MBF is a formula composed of AND, OR, and threshold operators, along with atoms. In our case, each atom corresponds to a node 𝑝 𝑖 . The threshold operator Θ𝑚 𝑘 (𝑞 1 , . . . , 𝑞 𝑚 ) evaluates to 1 whenever 𝑘 out of the 𝑚 functions 𝑞 1 , . . . , 𝑞 𝑚 evaluate to 1, where each 𝑞 𝑖 can be either an atom or an operator. 𝑚 Notice that Θ𝑚 𝑚 corresponds to the AND operator and Θ1 corresponds to the OR operator evaluated on 𝑚 inputs. An MBF Γ describes a monotone function 𝜑 : 2 P → {0, 1} in the following way: • when Γ consists only of an atom, then the value of Γ on input 𝑆 ⊆ P is 1 if and only if Γ ∈ 𝑆; • when Γ is the threshold operator Θ𝑚 𝑘 (𝑞 1 , . . . , 𝑞 𝑚 ), then Γ(𝑆) = 1 if at least 𝑘 of the 𝑞 1 , . . . , 𝑞 𝑚 are recursively evaluated to 1 on input 𝑆. Note that a monotone access structure A can be described using a monotone function 𝛼 : 2 P → {0, 1} that returns 1 for every access set and 0 otherwise. We can therefore represent the access structure using the MBF that describes 𝛼. We refer to the rooted tree representing such an MBF as the access tree of A. In more detail, an access tree is a rooted, labeled tree in which each internal vertex 𝑣 has a label that is an integer between 1 and the number of children of 𝑣 (inclusive), and each leaf vertex is labeled with a node identifier. An important subclass of access structures is what we call partitioned access structures. Those are access structures that can be described by an MBF where each atom appears at most once. Note that in the access tree of a partitioned access structures each leaf is labeled with a unique node identifier.
3
Monotone Erasure Codes
3.1
Definition
Consider an access structure A on P. Suppose we want to store a file 𝑓 , also called an information vector, among the nodes in P, with the guarantee that every access set 𝐴 is able to reconstruct 𝑓 . Additionally, we seek an efficient storage scheme, meaning that the total amount of information stored across all nodes is as small as possible. To address this need, we propose a new kind of erasure code, called monotone erasure code. Let F be a finite set and let G = G1 × . . . × G𝑛 , where each G𝑖 is a finite set. Definition 2 (Monotone erasure code). Let A be an access structure on P and let 𝑓 be a file from a set F . A monotone erasure code C for A is a scheme that distributes 𝑓 among the nodes in P and assigns to each 𝑝 𝑖 ∈ P a piece of information 𝑔𝑖 ∈ G𝑖 called fragment of 𝑝 𝑖 . Such a code consists of two functions: Encode( 𝑓 ): given a file 𝑓 , returns a fragment vector 𝑔 = (𝑔1 , . . . , 𝑔𝑛 ) ∈ G; Decode(𝑢): given a vector 𝑢 = (𝑢 𝑖 )𝑖 ∈ [𝑛] ∈ G, returns either a file 𝑓 ′ ∈ F or ⊥. A monotone erasure code for A satisfies the following property: Completeness: for all 𝐴 ∈ A, the fragments 𝑔 𝐴 of the nodes in 𝐴 generated by Encode( 𝑓 ) are enough to reconstruct 𝑓 , i.e., 𝑔 𝐴 satisfies Decode(𝑔 𝐴) = 𝑓 . For any 𝐵 ⊆ P, we denote by 𝑔 𝐵 the vector whose 𝑖-th entry equals 𝑔𝑖 if 𝑝 𝑖 ∈ 𝐵, and ⊥ otherwise. Moreover, we assume w.l.o.g. that ⊥ ∈ G𝑖 , for all 𝑖 ∈ [𝑛], and allow that G𝑖 = {⊥}, meaning that the fragment of 𝑝 𝑖 is the constant ⊥. We introduce this constant because, for certain structures, it may be convenient to assign no actual data to some nodes, in which case their fragment is ⊥. Let 𝑔 = Encode( 𝑓 ) for some file 𝑓 . Then, we call a set 𝐵 ⊆ P sufficient if Decode(𝑔 𝐵 ) = 𝑓 . Otherwise, if Decode(𝑔 𝐵 ) ≠ 𝑓 , i.e., Decode(𝑔 𝐵 ) outputs a vector different from 𝑓 or Decode(𝑔 𝐵 ) = ⊥, 4
then 𝐵 is called insufficient. In particular, this means that each access set 𝐴 is sufficient, namely, it is able to reconstruct the original file 𝑓 using the fragments 𝑔 𝐴. However, we do not require all sufficient sets to be in A. As a consequence, it may happen that some sets are able to reconstruct 𝑓 , even though they are not in A. This is an important difference from secret sharing, where sets outside A are only able to recover negligible or no information. A monotone erasure code does not provide integrity, in the sense that a group of nodes 𝐵 does not know if the retrieved file is the original one. In other words, 𝐵 does not know if 𝑓 ′ = 𝑓 , where Decode(𝑔 𝐵 ) = 𝑓 ′ and 𝑓 ′ ≠ ⊥. Nevertheless, this issue can be fixed by employing a verification method, such as a Merkle tree. The efficiency of a monotone erasure code used to store a file 𝑓 ∈ {0, 1} 𝜅 can be measured through a metric called overhead. It measures the amount of redundancy added per information symbol during the encoding phase. Definition 3 (Overhead). Let C be a monotone erasure code that takes as input files of 𝜅 bits and produces fragments of 𝜇 total bits. The overhead 𝛽 of C is 𝛽 = 𝜇−𝜅 𝜅 .
3.2
A basic construction of a monotone erasure code
In this section, we present an algorithm that, given an access structure A described as a MBF, builds a monotone erasure code that is complete for A. For illustration purposes, we assume here that each operator in the MBF is either AND or OR, but note that threshold operators can always be converted into a composition of AND and OR. In other words, the formula can be expressed as (. . .)), . . . , 𝐹ℓ(1) (. . .)) 𝐹 (𝐹1(1) (𝐹1(2) (. . .), . . . , 𝐹ℓ(2) 1 where 𝐹 𝑗(𝑖) is an AND or OR operator at depth 𝑖. The goal is to assign enough information to each node to achieve completeness. In particular, let 𝑓 ∈ {0, 1} 𝜅 be the file we want to store. Then, the construction works as follows. Consider the access tree 𝑇 representing A and let V be the set of all vertices in 𝑇. The first step of the algorithm is to build a function 𝜂 : V → − {0, 1}∗ that assigns a substring of 𝑓 to each vertex. We start by considering the root of the tree, which corresponds to the operator 𝐹, and we set 𝜂(𝐹) = 𝑓 . Then, if 𝐹 is an AND with ℓ arguments, we divide 𝑓 in ℓ different chunks 𝑓1 , . . . , 𝑓ℓ with length ℓ𝜅 , assuming w.l.o.g. that such fractions are integers. We then set 𝜂(𝑣 𝑖 ) = 𝑓𝑖 for each child 𝑣 𝑖 of the root. Otherwise, if 𝐹 is an OR, we set 𝜂(𝑣 𝑖 ) = 𝑓 for each child 𝑣 𝑖 . Next, we move to the first child of 𝐹 and we iterate the procedure until we have visited each leaf of the tree and defined 𝜂 for it. Notice that each node 𝑝 𝑖 ∈ P might correspond to multiple leaves 𝑣 𝑖1 , . . . , 𝑣 𝑖𝑤𝑖 . The fragment of 𝑝 𝑖 is then defined as the list of the chunks 𝜂(𝑣 𝑖1 ), . . . , 𝜂(𝑣 𝑖𝑤𝑖 ). This ensures that each access set has enough information to reconstruct 𝑓 . Example 1. Let P = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒} be the set of nodes and A = {{𝑎, 𝑐, 𝑑, 𝑒}, {𝑏, 𝑐, 𝑑, 𝑒}, {𝑎, 𝑏, 𝑐}, {𝑎, 𝑏, 𝑑}, {𝑎, 𝑏, 𝑒}} be the access structure. Then, the corresponding MBF is Θ21 (Θ22 (Θ21 (𝑎, 𝑏), Θ33 (𝑐, 𝑑, 𝑒)), Θ22 (Θ22 (𝑎, 𝑏), Θ31 (𝑐, 𝑑, 𝑒))). Suppose we want to store the file 𝑓 = (0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1) ∈ {0, 1}12 . Figure 1 shows the access tree that represents A, along with the evaluation of 𝜂 on the nodes, where • 𝑓1 = (0, 1, 1, 1, 0, 0)
• 𝑓2′ = (1, 1)
• 𝑓2 = (1, 0, 1, 1, 0, 1)
• 𝑓3′ = (0, 1)
• 𝑓1′ = (1, 0)
• 𝑓1′′ = (0, 1, 1) 5
• 𝑓2′′ = (1, 0, 0)
∨
𝑓
𝑓
∧
𝑓
𝑓1 ∨
a 𝑓1
𝑓2 ∧
b
c
𝑓1
𝑓1′
∧
𝑓1 ∧
𝑓2 ∨
d
e
a
b
c
d
e
𝑓2′
𝑓3′
𝑓1′′
𝑓2′′
𝑓2
𝑓2
𝑓2
Figure 1. Access tree representing A and 𝜂. △
4
Linear Monotone Erasure Codes
We now consider monotone erasure codes for data represented by symbols that are elements of a finite field F𝑞 . This means the file is a vector 𝑓 ∈ F𝑞𝑘 of length 𝑘. Moreover, we take the fragments (𝑔1 , . . . , 𝑔𝑛 ) from the set G = G1 × · · · × G𝑛 , where G𝑖 = F𝑞𝑚𝑖 ∪ {⊥} or G𝑖 = {⊥}. Then 𝑚 𝑖 ∈ N denotes the size of 𝑝 𝑖 ’s Í𝑛 fragment, and we set 𝑚 𝑖 = 0 whenever G𝑖 = {⊥}. The total size of the stored information is 𝑚 = 𝑖=1 𝑚𝑖 symbols. Definition 4 (Linear monotone erasure code). An [𝑚, 𝑘]-linear monotone erasure code C for A is a monotone erasure code for an access structure A and files of length 𝑘 that produces fragments with combined size 𝑚, where the encoding and decoding algorithms are based on a full-rank matrix 𝐺 ∈ F𝑞𝑘×𝑚 and a function 𝜙 : {1, . . . , 𝑚} → P that assigns each column of 𝐺 to a node in P. Let 𝐺 𝑝𝑖 be the matrix consisting of the columns of 𝐺 assigned to 𝑝 𝑖 by 𝜙, i.e., 𝐺 𝑝𝑖 = (𝐺 𝑗1 | · · · |𝐺 𝑗𝑚𝑖 ) where 𝜙( 𝑗 1 ) = . . . = 𝜙( 𝑗 𝑚𝑖 ) = 𝑝 𝑖 . Then, the algorithms are defined as follows: Encode( 𝑓 ): Given 𝑓 ∈ F𝑞𝑘 , the algorithm outputs the fragments (𝑔1 , . . . , 𝑔𝑛 ), where 𝑔𝑖 ∈ G𝑖 such that 𝑔𝑖 = 𝑓 · 𝐺 𝑝𝑖 is the fragment of 𝑝 𝑖 ∈ P. If there is no 𝑗 ∈ [𝑚] such that 𝜙( 𝑗) = 𝑝 𝑖 , i.e., 𝑚 𝑖 = 0, then 𝑔𝑖 = ⊥. Decode(𝑢): Given a vector 𝑢 ∈ G, the algorithm returns either 𝑓 ′ ∈ F𝑞𝑘 or ⊥. In relation to the classical erasure codes, the matrix 𝐺 is also called the generator matrix of C, 𝑘 is the dimension of C, and 𝑚 is the length of C. According to the earlier definitions, an [𝑚, 𝑘]-linear monotone erasure code is complete if for all 𝐴 ∈ A, the fragments 𝑔 𝐴 of the nodes in 𝐴 contain enough information to reconstruct 𝑓 , i.e., Decode(𝑔 𝐴) = 𝑓 . Moreover, let 𝐺 𝐵 be the matrix given by the columns of 𝐺 assigned to nodes in a set
6
𝐵 ⊆ P. Then, 𝐵 is sufficient if 𝑓 · 𝐺 𝐵 uniquely determines the information vector 𝑓 . Otherwise, 𝐵 is insufficient. By the completeness property of a linear monotone erasure code C, each set 𝐴 ∈ A is sufficient. Moreover, by the following theorem, it follows that the labeling function must assign to the nodes in a set 𝐴 ∈ A at least 𝑘 linearly independent columns of 𝐺 to make C complete. Theorem 1. Let C be an [𝑚, 𝑘]-linear monotone erasure code over F𝑞 for A. A set of nodes 𝐵 ⊆ P is sufficient if and only if the matrix 𝐺 𝐵 has full rank, i.e., rank(𝐺 𝐵 ) = 𝑘. Proof. Assume 𝐺 𝐵 ∈ F𝑞𝑘×𝑙 where 𝑙 ≥ 𝑘. Since rank(𝐺) = 𝑘 it follows that rank(𝐺 𝐵 ) = 𝑘. Let 𝐺ˆ 𝐵 be a matrix containing 𝑘 columns of 𝐺 𝐵 that are linearly independent. Then 𝐺ˆ 𝐵 ∈ F𝑞𝑘×𝑘 is invertible and thus there exists 𝑈 ∈ F𝑞𝑘×𝑘 such that 𝐺ˆ 𝐵 · 𝑈 = 𝐼 𝑘 , where 𝐼 𝑘 is the 𝑘 × 𝑘 identity matrix. Then we have ( 𝑓 · 𝐺ˆ 𝐵 ) · 𝑈 = 𝑓 · 𝐼 𝑘 = 𝑓 . If 𝐺 𝐵 ∈ F𝑞𝑘×𝑙 , with 𝑙 < 𝑘, then rank(𝐺 𝐵 ) = 𝑙. Therefore, there exist 𝑥1 , . . . , 𝑥 𝑘 ∈ F𝑞 not all equal to 0 such that 𝑥1 𝑔1 + 𝑥2 𝑔2 + . . . + 𝑥 𝑘 𝑔 𝑘 = 0 where 𝑔1 , 𝑔2 , . . . , 𝑔 𝑘 are the rows of 𝐺 𝐵 . Let 𝑥 = (𝑥 1 , . . . , 𝑥 𝑘 ) ∈ F𝑞𝑘 . Then, 𝑥 + 𝑓 = (𝑥 1 + 𝑓1 , . . . , 𝑥 𝑘 + 𝑓 𝑘 ) ∈ F𝑞𝑘 and (𝑥 + 𝑓 ) · 𝐺 𝐵 = (𝑥1 + 𝑓1 )𝑔1 + . . . + (𝑥 𝑘 + 𝑓 𝑘 )𝑔 𝑘 = 𝑥 1 𝑔1 + . . . + 𝑥 𝑘 𝑔 𝑘 + 𝑓1 𝑔1 + . . . + 𝑓 𝑘 𝑔 𝑘 = 𝑓1 𝑔1 + . . . + 𝑓 𝑘 𝑔 𝑘 = 𝑓 · 𝐺 𝐵 . Therefore, 𝑓 · 𝐺 𝐵 does not uniquely determine 𝑓 . □ To store an information vector 𝑓 ∈ F𝑞𝑘 among the nodes, we are interested in the efficiency of a linear monotone erasure code C, in the sense of how much more data must be stored compared to 𝑓 . As previously mentioned, this can be measured using the overhead 𝛽 of C. In this case, it holds that 𝜅 = 𝑘 · ⌈𝑙𝑜𝑔2 (𝑞)⌉ and 𝜇 = 𝑚 · ⌈𝑙𝑜𝑔2 (𝑞)⌉, thus 𝛽 = 𝑚−𝑘 𝑘 . If 𝑘 is close to 𝑚, then the overhead 𝛽 is small. This is equivalent to adding only little redundancy, since 𝑚 − 𝑘 is small. Therefore, to efficiently store a file 𝑓 , the goal is to find the optimal parameters of a linear monotone erasure code C, i.e., 𝑘 and 𝑚 of C that minimize the overhead. In this way, for a given access structure A and optimal parameters 𝑘 and 𝑚, we represent 𝑓 as an information vector of length 𝑘 over F𝑞 . For some specific access structures, the optimal parameters 𝑘 and 𝑚 can be found easily. In particular, if A is an access structure such that each set 𝐴 ∈ A consists of exactly 𝑤 nodes, for some 𝑤 ∈ [𝑛], then one can find the optimal parameters as follows, which leads us to the definition of a linear threshold erasure code. This is well-known in the literature on information dispersal [30, 5] where a data bit string is encoded into 𝑛 pieces and stored among 𝑛 nodes such that each node stores exactly one piece. Definition 5 (Linear threshold erasure code). Let P be a set of 𝑛 nodes and let A be an access structure on P such that each 𝐴 in A consists of exactly 𝑤 nodes, i.e., A = { 𝐴 | 𝐴| = 𝑤}. An [𝑚, 𝑘]-linear threshold erasure code C for A is an [𝑚, 𝑘]-linear monotone erasure code over F𝑞 for A, with parameters 𝑘 = 𝑤 and 𝑚 = 𝑛, and the labeling function 𝜙(𝑖) = 𝑝 𝑖 for 𝑖 ∈ [𝑛]. In a linear threshold erasure code, the fragment 𝑔𝑖 of each node 𝑝 𝑖 is made of exactly one field element, which we call threshold fragment. Moreover, the nodes of each set 𝐴 ∈ A have together 𝑘 different columns of 𝐺. This means that the overhead is 𝑛−𝑘 𝑘 , which is the best we can achieve for this specific access structure. The reason is that the nodes do not store more information than is required to reconstruct 𝑓 . We now consider a particular and well-known generator matrix 𝐺 for an [𝑚, 𝑘]-linear threshold erasure code C. Let 𝑞 ≥ 𝑚 ≥ 𝑘 be integers and let 𝛼 = (𝛼1 , . . . , 𝛼𝑚 ) ∈ F𝑞𝑚 where 𝛼𝑖 ≠ 𝛼 𝑗 for all 𝑖 ≠ 𝑗 ∈ [𝑚]. Then, 1 1 ... 1 © ª 𝛼2 . . . 𝛼𝑚 ® 𝛼1 𝑘×𝑚 𝐺 = . .. ®® ∈ F𝑞 . . . ® . 𝑘−1 𝛼 𝑘−1 . . . 𝛼 𝑘−1 𝛼 𝑚 ¬ « 1 2 7
The matrix 𝐺 is called Vandermonde matrix and generates a maximum distance separable (MDS) code, called Reed-Solomon code. Definition 6 (MDS code). A linear code C of length 𝑚 and dimension 𝑘 is called maximum distance separable (MDS) if 𝑑 = 𝑚 − 𝑘 + 1 where 𝑑 = min{𝑑 𝐻 (𝑥, 𝑦) | 𝑥, 𝑦 ∈ C, 𝑥 ≠ 𝑦} with 𝑑 𝐻 (𝑥, 𝑦) = |{𝑖 ∈ [𝑛] | 𝑥𝑖 ≠ 𝑦 𝑖 }| is called minimum distance of C. We refer to an MDS code with length 𝑚 and dimension 𝑘 as an [𝑚, 𝑘]-MDS code. Notice that any [𝑚, 𝑘]-MDS code can be viewed as an [𝑚, 𝑘]-linear threshold erasure code. Indeed, even though the labeling function is not part of the standard definition of an MDS code, it can be naturally added. In particular, one can define a set of 𝑚 virtual nodes V = {𝑉1 , . . . , 𝑉𝑚 } and set 𝜙(𝑖) = 𝑉𝑖 , for all 𝑖 ∈ [𝑚]. We therefore consider MDS codes to be linear threshold erasure codes. In particular, any generator matrix of an MDS code can be chosen for 𝐺. This offers an optimal trade-off between fault-tolerance and storage overhead, as it allows data to be reconstructed from any 𝑘 threshold fragments, derived from 𝑘 different columns of 𝐺. Indeed, for an MDS code it holds that any 𝑘 columns of its generator matrix 𝐺 are linearly independent. Therefore, if the nodes of a set 𝐵 ⊆ P have together at least 𝑘 different columns of 𝐺, then they are able to reconstruct 𝑓 by Theorem 1.
5
Efficient Construction of Linear Monotone Erasure Codes
In this section, we present an efficient algorithm that constructs a linear monotone erasure code C for any given access structure A on P. The encoding matrix of C has a block-wise MDS property that ensures completeness of the code. In the general case, this construction does not deliver a linear monotone erasure code with minimal overhead. We first present the intuition behind the code through its encoding algorithm. Given a file 𝑓 and an access tree 𝑇 with a root node labeled 𝑡 that has 𝑟 children, the algorithm proceeds as follows. First, it encodes 𝑓 using a linear monotone erasure code that generates 𝑟 fragments and such that any 𝑡 of them can reconstruct 𝑓 . Then, it encodes each of the 𝑟 resulting fragments again. Specifically, for each child 𝑣 𝑖 of the root with label 𝑡 𝑖 and 𝑟 𝑖 children, the fragment 𝑔𝑖 assigned to 𝑣 𝑖 is encoded using a linear monotone erasure code that generates 𝑟 𝑖 fragments and such that any 𝑡𝑖 of them are enough to reconstruct 𝑔𝑖 . The encoding function proceeds in this way until it reaches the leaves. This method is inspired by secret-sharing constructions in the literature (e.g., [27]). To build such a code, we use a recursive algorithm. We now illustrate the functioning of the algorithm through an example before describing it in detail. Consider the tree 𝑇 in Figure 2, representing the access structure A = Θ32 (Θ33 ( 𝑝 1 , 𝑝 2 , 𝑝 4 ), Θ32 ( 𝑝 3 , 𝑝 4 , 𝑝 5 ), Θ31 ( 𝑝 6 , 𝑝 7 , 𝑝 8 )). 2
3
𝑝1
𝑝2
2
𝑝4
𝑝3
𝑝4
1
𝑝5
𝑝6
𝑝7
𝑝8
Figure 2. Access tree 𝑇 of A Let 𝑇𝑖 be depth-one subtrees of 𝑇 for 𝑖 ∈ [3] with root labeled 𝑡𝑖 with 𝑟 𝑖 children. We aim to construct an encoding matrix 𝑀 ∈ F𝑞𝑘×𝑚 for a sufficient large 𝑞 and a labeling function 𝜙 for A such that the nodes of each access set yield at least 𝑘 linearly independent columns of 𝑀. To achieve this, the matrix 8
construction guarantees the following. Each node in 𝑇𝑖 yields 𝑘/(2𝑡𝑖 ) linearly independent columns, so that each subtree 𝑇𝑖 collectively contributes a set of 𝑘/2 linearly independent columns. Moreover, the union of columns of any two such sets remains linearly independent. We pick the order of the field 𝑞 as a prime power greater than or equal to the following value: max 2, max {𝑟 𝑖 } = 3 𝑣𝑖 , 𝑡𝑖 ≠1
where each 𝑣 𝑖 is a vertex in 𝑇 labeled 𝑡𝑖 with 𝑟 𝑖 children. To construct a matrix 𝑀 for A that satisfies the property above, we first associate to each 𝑇𝑖 a 𝑡 𝑖 × 𝑟 𝑖 Vandermonde matrix 𝑀𝑖 over F𝑞 . By construction, any 𝑡 𝑖 columns of 𝑀𝑖 are linearly independent. Thus, assigning one column of 𝑀𝑖 to each node in 𝑇𝑖 ensures that any 𝑡 𝑖 nodes contribute sufficiently many linearly independent columns. 1 1 1 ª © 𝑀1 = 0 1 2® «0 1 1 ¬
1 1 1 𝑀2 = 0 1 2
𝑝1 𝑝2 𝑝4
𝑝3 𝑝4 𝑝5
𝑀3 = 1 1 1
𝑝6 𝑝7 𝑝8
To combine 𝑀1 , 𝑀2 and 𝑀3 so that the resulting matrix 𝑀 satisfies the desired property, we have to lift the matrices 𝑀𝑖 to a common number of rows (which we set as the least common multiple). We achieve this by computing the Kronecker product between the matrix 𝑀𝑖 and an appropriate identity matrix, resulting into the following matrices 𝑅𝑖 with corresponding labeling of the columns: 𝐼2 𝐼2 𝐼2 𝐼 𝐼 𝐼3 © ª 𝑅1 = 𝑀1 ⊗ 𝐼2 = 0 𝐼2 2𝐼2 ®, 𝑅2 = 𝑀2 ⊗ 𝐼3 = 3 3 , 𝑅3 = 𝑀3 ⊗ 𝐼6 = 𝐼6 𝐼6 𝐼6 0 𝐼3 2𝐼3 « 0 𝐼2 𝐼2 ¬ 𝑝1 𝑝2 𝑝4
𝑝3 𝑝4 𝑝5
𝑝6 𝑝7 𝑝8
By construction of 𝑅𝑖 , any 𝑡 𝑖 nodes contribute a set of linearly independent columns of equal size, as they are derived from linearly independent columns of 𝑀𝑖 via the Kronecker product. ˜ a To construct the final matrix 𝑀, we embed the matrices 𝑅𝑖 for 𝑖 ∈ [3] into the auxiliary matrix 𝑀, 2 × 3 Vandermonde matrix over F𝑞 : 1 1 1 ˜ 𝑀= 0 1 2
𝑇1 𝑇2 𝑇3 Each column of 𝑀˜ corresponds to a subtree 𝑇𝑖 of 𝑇. We finally obtain 𝑀 by substituting each entry of 𝑀˜ by its Kronecker product with the corresponding matrix 𝑅𝑖 . This results in the following block-structured matrix
𝑅 𝑀= 1 0
𝑅2 𝑅3 𝑅2 2𝑅3
Consequently, each subtree 𝑇𝑖 contributes a set of 𝑘/2 columns, and the sets of columns of any two subtrees 𝑇𝑖 and 𝑇 𝑗 are jointly linearly independent, ensuring that 𝑀 possesses the desired property. 9
5.1
Algorithm
Given the access tree 𝑇 of A, we set the field size 𝑞 as the smallest prime power such that 𝑞 ≥ max 2, max {𝑟 𝑖 } 𝑣𝑖 , 𝑡𝑖 ≠1
where 𝑣 𝑖 is a vertex in 𝑇 labeled 𝑡 𝑖 with 𝑟 𝑖 children. Then, we use a recursive algorithm that takes the tuple (𝑇, 𝑞) as input and returns the tuple (𝑀𝑇 , 𝜈𝑇 , 𝑘 𝑇 , 𝐿 𝑇 ) defining C, where: • 𝑀𝑇 is a 𝑘 𝑇 × 𝜈𝑇 -matrix over F𝑞 • 𝐿 𝑇 is a vector defining the labeling function 𝜙𝑇 of C, i.e., 𝜙𝑇 : [𝜈𝑇 ] → P 𝑖 ↦→ 𝐿 𝑇 (𝑖) The algorithm works as follows. Note that all operations are done in F𝑞 . 1. If 𝑇 has depth zero, i.e., it consists of a single vertex 𝑝 𝑖 , then let (𝜈𝑇 , 𝑘 𝑇 ) = (1, 1), set and 𝐿𝑇 = ( 𝑝𝑖 ) 𝑀𝑇 = 1 1×1 and return the tuple (𝑀𝑇 , 𝜈𝑇 , 𝑘 𝑇 , 𝐿 𝑇 ). 2. If 𝑇 has depth one or more and consists of a root labeled 𝑡 with 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 : (a) Apply the algorithm to each subtree 𝑇𝑎 for 𝑎 ∈ [𝑟] to obtain the tuple (𝑀𝑎 , 𝜈 𝑎 , 𝑘 𝑎 , 𝐿 𝑎 ). (b) Let 𝜆 = 𝑙𝑐𝑚({𝑘 𝑎 | 𝑎 ∈ [𝑟]}). Then set for each 𝑎 ∈ [𝑟] 𝛼𝑎 = 𝜆/𝑘 𝑎
and
𝑅 𝑎 = 𝑀𝑎 ⊗ 𝐼 𝛼𝑎
where 𝐼 𝛼𝑎 is the identity matrix of size 𝛼𝑎 and ⊗ denotes the Kronecker product. Moreover, let 𝐿 ′𝑎 = 𝐿 𝑎 ⊗ 1 𝛼𝑎 where 1 𝛼𝑎 is the all-one row vector of length 𝛼𝑎 and 𝐿 ′𝑎 is therefore the vector obtained by replicating each entry of 𝐿 𝑎 𝛼𝑎 times. (c) Take a 𝑡 × 𝑟 Vandermonde matrix 𝐴 over F𝑞 . Moreover, let 𝑀𝑇 = ( 𝐴 ⊗ 𝐼𝜆 )𝑑𝑖𝑎𝑔(𝑅1 , . . . , 𝑅𝑟 ) where 𝐼𝜆 is the identity matrix of size 𝜆 and 𝐿 𝑇 = 𝑐𝑜𝑛𝑐𝑎𝑡 (𝐿 ′𝑎 ) for all 𝑎 ∈ [𝑟] with concat denoting the concatenation of all vectors 𝐿 𝑎 for 𝑎 ∈ [𝑟]. Finally, let 𝑘 𝑇 = 𝜆𝑡
and
𝜈𝑇 =
𝑟 ∑︁
𝛼𝑎 𝜈 𝑎
𝑎=1
Note that 𝑘 𝑇 is the number of rows and 𝜈𝑇 is the number of columns of 𝑀𝑇 . This algorithm has polynomial complexity in the size of the access tree. Note that the field size 𝑞 needs to be greater or equal than each 𝑟 𝑖 to allow constructing a 𝑡𝑖 × 𝑟 𝑖 Vandermonde matrix at every step. Since each 𝑟 𝑖 is smaller or equal than 𝑛, we could also choose the field size as a prime power 𝑞 ≥ 𝑛. In the general case, this leads to a larger field size, but would not require to visit the tree to compute 𝑞. 10
5.2
Analysis
Completeness of the resulting linear monotone erasure code. In the following, we prove that Algorithm 5.1 provides a linear monotone erasure code for an access structure A given as a tree 𝑇 that is complete. We first state two preliminary lemmas, and then prove the statement in Theorem 4. Lemma 2. Let 𝑀 ∈ F𝑞𝑘×𝜈 and let Γ ⊆ [𝜈] be an index set such that the columns of 𝑀 indexed by Γ are linearly independent. For any 𝑠 ∈ N>0 , define 𝑅 = 𝑀 ⊗ 𝐼𝑠 , where 𝐼𝑠 is the identity matrix of size 𝑠. Then the columns of 𝑅 corresponding to Γ are linearly independent. Proof. Note that by definition of 𝑅, a column 𝑎 𝑖 of 𝑀 corresponds to 𝑠 columns of 𝑅. These columns have the form 𝑎 𝑖 ⊗ 𝑒 𝑗 , where 𝑒 𝑗 is the unit column vector with 1 at position 𝑗, for all 𝑗 ∈ [𝑠]. Now, let 𝑎 𝑖1 , . . . , 𝑎 𝑖𝛾 be 𝛾 columns of 𝑀 that are linearly independent. Assume that 𝛾 ∑︁ 𝑠 ∑︁
𝑐 ℓ, 𝑗 (𝑎 𝑖ℓ ⊗ 𝑒 𝑗 ) = 0
ℓ=1 𝑗=1
where 𝑐 ℓ, 𝑗 ∈ F𝑞 . Note that this can be rewritten as 𝛾 ∑︁
𝑎 𝑖ℓ ⊗ 𝜔ℓ = 0
ℓ=1
Í𝑠
where 𝜔ℓ = 𝑗=1 𝑐 ℓ, 𝑗 𝑒 𝑗 . Since 𝑎 𝑖ℓ for ℓ ∈ [𝛾] are linearly independent, it follows that 𝜔ℓ = 0 for all ℓ ∈ [𝛾] which holds if and only if 𝑐 ℓ, 𝑗 = 0. Thus, the statement follows. □ Lemma 3. Let 𝐴 ∈ F𝑡𝑞×𝑡 and 𝑅𝑖 ∈ F𝑞𝑠×𝑠 for 𝑖 ∈ [𝑡] be invertible. Then the matrix 𝑀 = ( 𝐴 ⊗ 𝐼𝑠 )𝑑𝑖𝑎𝑔(𝑅1 , . . . , 𝑅𝑡 ) ∈ F𝑡𝑞𝑠×𝑡 𝑠 where 𝐼𝑠 is the identity matrix of size 𝑠 is invertible. Proof. Since each 𝑅𝑖 is invertible, the block diagonal matrix 𝑑𝑖𝑎𝑔(𝑅1 , . . . , 𝑅𝑡 ) ∈ F𝑡𝑞𝑠×𝑡 𝑠 is invertible. Thus 𝑀 is invertible if and only if 𝐴 ⊗ 𝐼 𝑠 ∈ F𝑡𝑞𝑠×𝑡 𝑠 is invertible. Since the matrix 𝐴 ⊗ 𝐼𝑠 is invertible by Lemma 2, the statement follows.
□
Theorem 4. For a given access structure A represented as an access tree 𝑇, Algorithm 5.1 provides a monotone erasure code C defined by 𝑀𝑇 and 𝜙𝑇 that is complete. Proof. Let 𝑉 denote the set of vertices in 𝑇 whose children are leaves. Note that each vertex 𝑣 ∈ 𝑉 correspond to a submatrix 𝑃𝑣 of 𝑀𝑇 , i.e., 𝑃𝑣 consists of the columns of 𝑀𝑇 that are generated through vertex 𝑣. Moreover, for a vertex 𝑣 ∈ 𝑉, let 𝐶𝑣 be the set of its leaf children. Let 𝑆 𝑣 ⊆ 𝐶𝑣 be a subset of leaves of 𝑣 chosen to satisfy the threshold condition at 𝑣. Note that 𝑆 𝑣 corresponds to a submatrix 𝑃𝑆𝑣 of 𝑃𝑣 . Now, an access set 𝐴 ∈ A corresponds to a selection of subsets of vertices (𝑆 𝑣 ′ ) 𝑣 ′ ∈𝑉 where 𝑆 𝑣 ′ ⊆ 𝐶𝑣 ′ . Therefore, to show that C is complete it suffices to show that the number of columns of all submatrices 𝑃𝑆𝑣′ for 𝑣 ′ ∈ 𝑉 are at least 𝑘 and that they are jointly linearly independent. 11
We first show that these are exactly 𝑘 𝑇 columns. Without loss of generality, assume that all leaves in 𝑇 have the same depth. By construction, for a subtree of depth one consisting of a root 𝑣 ∈ 𝑉 labeled 𝑡 with 𝑟 children, the resulting matrix 𝑀𝑣 has 𝑡 rows and 𝑟 columns. Moreover, exactly one column of 𝑀𝑣 is assigned to a child of 𝑣. Thus, a subset of 𝑡 children of 𝑣 own together exactly 𝑡 different columns of 𝑀𝑣 . Now, consider a subtree of depth two consisting of a root 𝑣˜ labeled 𝑡˜ with 𝑟˜ children 𝑣 1 , . . . , 𝑣 𝑟˜ . Moreover, let 𝑡𝑖 be the label of each child 𝑣 𝑖 of 𝑣˜ . Note that a column of 𝑀𝑣𝑖 corresponds to 𝜆 columns in 𝑅𝑣𝑖 = 𝑀𝑣𝑖 ⊗ 𝐼𝜆 . Thus, by construction, 𝑡˜ children of 𝑣˜ own together 𝜆 · 𝑡˜ different columns, which is the number of rows of 𝑀𝑣˜ . By continuing this procedure for subtrees with depth greater than two, it follows that the number of columns of all submatrices 𝑃𝑆𝑣′ are exactly 𝑘 𝑇 . It remains to show that these 𝑘 𝑇 columns are linearly independent. Note that each subtree of depth one consisting of a root 𝑣 ′ ∈ 𝑉 labeled 𝑡 has the property that any 𝑡 columns are linearly independent. By the following bottom-up construction to yield the matrices 𝑃𝑆𝑣′ for 𝑣 ′ ∈ 𝑉 and by Lemma 2 and Lemma 3 the statement follows. □ Size of resulting matrix 𝑀𝑇 . Let 𝑇 be the tree of A with root 𝑣 R and let 𝑉 = {𝑣 1 , . . . , 𝑣 𝛿 } be the set of vertices whose children are leaves. Moreover, for each vertex 𝑣 𝑖 ∈ 𝑉, let 𝑅𝑣𝑖 denote the set of vertices on the unique path from 𝑣 R to 𝑣 𝑖 . For a vertex 𝑣, we denote by 𝑥 𝑣 the label (threshold) of 𝑣 and by 𝑦 𝑣 the number of its children in 𝑇. Í𝛿 Theorem 5. The resulting matrix 𝑀𝑇 by Algorithm 5.1 has 𝑘 rows and 𝑖=1 𝜓𝑖 · 𝑘 columns where 𝑦𝑣 𝜓𝑖 = Î 𝑖 𝑥𝑣 for 𝑖 ∈ [𝛿] and 𝑘 = 𝑙𝑐𝑚 𝑑𝑒𝑛(𝜓 𝑗 ) 𝑗 ∈ [ 𝛿 ] . 𝑣 ∈ 𝑅𝑣𝑖
Proof. Without loss of generality, assume that all leaves in 𝑇 have the same depth. First note that for a subtree of depth one consisting of a root 𝑣 ∈ 𝑉 labeled 𝑥 𝑣 with 𝑦 𝑣 children, Algorithm 5.1 returns a matrix with 𝑥 𝑣 rows and 𝑦 𝑣 columns. Moreover, for a subtree of depth two consisting of a root 𝑣 labeled 𝑡 with 𝑟 children 𝑣 1 , . . . , 𝑣 𝑟 , the number of rows of the matrix 𝑀˜ returned by the algorithm is 𝑘 𝑣 = 𝑡 · 𝑙𝑐𝑚(𝑥 𝑣1 , . . . , 𝑥 𝑣𝑟 ) = 𝑙𝑐𝑚(𝑡 · 𝑥 𝑣1 , . . . , 𝑡 · 𝑥 𝑣𝑟 ). This is the least common multiple of the products of vertex labels along the paths from 𝑣 𝑖 to the root 𝑣, for all 𝑖 ∈ [𝑟]. Moreover, the number of columns of 𝑀˜ is 𝜈𝑣 =
𝑟 ∑︁ 𝑙𝑐𝑚(𝑥 𝑣 , . . . , 𝑥 𝑣 ) 𝑟
1
𝑖=1
𝑥 𝑣𝑖
𝑦 𝑣𝑖 =
𝑟 ∑︁ 𝑦 𝑣𝑖 𝑘𝜈. 𝑡 · 𝑥 𝑣𝑖 𝑖=1
Now, consider a subtree of depth three labeled 𝑡˜ consisting of a root 𝑣 with 𝑟˜ children 𝑢 1 , . . . , 𝑢𝑟˜ . Assume each vertex 𝑢 𝑖 is labeled 𝑡𝑖 and has 𝑟 𝑖 children and assume that each child of 𝑢 𝑖 for 𝑖 ∈ [𝑟] ˜ is labeled with 𝑥 𝑖𝑗 and has 𝑦 𝑖𝑗 children for 𝑗 ∈ [𝑟 𝑖 ]. Following the same reasoning as for depth two, the number of rows of the resulting matrix by the algorithm is 𝑡˜ · 𝑙𝑐𝑚 𝑘 𝑢1 , . . . , 𝑘 𝑢𝑟˜ = 𝑡˜ · 𝑙𝑐𝑚 𝑙𝑐𝑚 𝑡1 · 𝑥 11 , . . . , 𝑡 1 · 𝑥𝑟11 , . . . , 𝑙𝑐𝑚 𝑡𝑟˜ · 𝑥 1𝑟˜ , . . . , 𝑡𝑟˜ · 𝑥𝑟𝑟˜𝑟˜ = 𝑙𝑐𝑚 𝑡˜ · 𝑡 1 · 𝑥 11 , . . . , 𝑡˜ · 𝑡 1 · 𝑥𝑟11 , . . . , 𝑡˜ · 𝑡𝑟˜ · 𝑥 1𝑟˜ , . . . , 𝑡˜ · 𝑡𝑟˜ · 𝑥𝑟𝑟˜𝑟˜ This is again the least common multiple of the products of vertex labels along the paths from a child of 𝑢 𝑖 to the root 𝑣, for all 𝑖 ∈ [𝑟], ˜ 𝑗 ∈ [𝑟 𝑖 ]. On the other hand, the number of columns of the resulting matrix is 𝑟˜ ∑︁ 𝑙𝑐𝑚 𝑘 𝑢 , . . . , 𝑘 𝑢 1
𝑖=1
𝑘 𝑢𝑖
𝑟˜
𝑟˜ ∑︁ 𝑙𝑐𝑚 𝑡˜ · 𝑡 1 · 𝑥 11 , . . . , 𝑡˜ · 𝑡 1 · 𝑥𝑟11 , . . . , 𝑡˜ · 𝑡𝑟˜ · 𝑥 1𝑟˜ , . . . , 𝑡˜ · 𝑡𝑟˜ · 𝑥𝑟𝑟˜𝑟˜ · 𝜈𝑢𝑖 = · 𝜈𝑢𝑖 (1) 𝑡˜ · 𝑙𝑐𝑚 𝑡𝑖 · 𝑥 1𝑖 , . . . , 𝑡 𝑖 · 𝑥𝑟𝑖 𝑖 𝑖=1
12
Since 𝜈𝑢𝑖 =
𝑟𝑖 ∑︁ 𝑦 𝑖𝑗
𝑡 · 𝑥 𝑖𝑗 𝑗=1 𝑖
· 𝑙𝑐𝑚(𝑡𝑖 · 𝑥 1𝑖 , . . . , 𝑡 𝑖 · 𝑥𝑟𝑖 𝑖 )
the sum (1) reduces to 𝑟˜ ∑︁
𝑦 𝑖1
𝑖=1
𝑡˜ · 𝑡 1 · 𝑥 1
+...+ 𝑖
𝑦 𝑟𝑖 𝑖 𝑡˜ · 𝑡 1 · 𝑥𝑟𝑖 𝑖
!
· 𝑙𝑐𝑚 𝑡˜ · 𝑡 1 · 𝑥 11 , . . . , 𝑡˜ · 𝑡 1 · 𝑥𝑟11 , . . . , 𝑡˜ · 𝑡𝑟˜ · 𝑥 1𝑟˜ , . . . , 𝑡˜ · 𝑡𝑟˜ · 𝑥𝑟𝑟˜𝑟˜ .
Note that since 𝛿 = 𝑟 1 + . . . + 𝑟 𝑟˜ , this sum is equivalent to 𝛿 ∑︁
𝑦 𝑣ℓ Î
ℓ=1
·𝑘
𝑣 ∈ 𝑅𝑣ℓ 𝑥 𝑣
˜ 𝑗 ∈ [𝑟 𝑖 ] and 𝑘 = 𝑙𝑐𝑚 where 𝑣 ℓ are the vertices labeled 𝑥 𝑣ℓ = 𝑥 𝑖𝑗 for 𝑖 ∈ [𝑟],
Î
𝑣 ∈ 𝑅𝑣ℓ 𝑥 𝑣
.
ℓ∈[ 𝛿]
By continuing this procedure for subtrees with depths greater than three the statement follows. Overhead of resulting linear monotone erasure code. Algorithm 5.1 is given by the following proposition.
□
The overhead of the code C constructed by
Proposition 6. For a given access structure A represented as an access tree 𝑇, Algorithm 5.1 provides Í𝛿 𝑦𝑣 a monotone erasure code C defined by 𝑀𝑇 and 𝜙𝑇 with overhead 𝛽 = 𝑖=1 𝜓𝑖 − 1, where 𝜓𝑖 = Î 𝑖 𝑥𝑣 𝑣∈𝑅𝑣𝑖
for 𝑖 ∈ [𝛿]. Proof. By Theorem 5 it follows that 𝑀𝑇 has 𝑘 rows and 𝑚 =
Í𝛿
𝑖=1 𝜓𝑖 · 𝑘 columns where 𝜓𝑖 =
𝑦𝑣𝑖 Î
𝑣∈𝑅𝑣𝑖 𝑥𝑣
for 𝑖 ∈ [𝛿] and 𝑘 = 𝑙𝑐𝑚(𝑑𝑒𝑛(𝜓 𝑗 ) 𝑗 ∈ [ 𝛿 ] ). Therefore, by definition of the overhead it holds that 𝑚−𝑘 = 𝛽= 𝑘
Í𝛿
𝑖=1 𝜓𝑖 · 𝑘 − 𝑘
=
𝛿 ∑︁
𝑘
𝜓𝑖 − 1
𝑖=1
which concludes the proof.
6
□
Linear Monotone Erasure Codes from Threshold Erasure Codes
In this section, we present an algorithm that, given a set of nodes P = {𝑝 1 , . . . , 𝑝 𝑛 } and an access structure A on P, produces a linear monotone erasure code that is complete for A and has an optimal overhead over all linear monotone erasure codes for A.
6.1
Algorithm details
Our scheme generates an [𝑚, 𝑘]-linear monotone erasure code C for A using an [𝑚, 𝑘]-linear threshold erasure code C ′ as a building block. We refer to C ′ as the base code and we call the fragments generated by it base fragments. In particular, we choose an [𝑚, 𝑘]-MDS code as a base code. The setup phase of our scheme consists of two stages. During the first stage, illustrated in Section 6.1.1, the scheme aims to find the optimal parameters 𝑚 and 𝑘 for C ′ . Then, in the second stage, we use the base code to build our [𝑚, 𝑘]-linear monotone erasure code. Indeed, we know that we can always build an [𝑚, 𝑘]-MDS code for all optimal parameters 𝑚 and 𝑘, and in Section 6.1.2 we show how to derive an [𝑚, 𝑘]-linear monotone erasure code from it. We suppose that the MDS code provides the following two functions: • MDSEncode( 𝑓 ): given 𝑓 ∈ F𝑞𝑘 , it returns a codeword 𝑐 ∈ F𝑞𝑚 ;
13
• MDSDecode(𝑢): given a vector 𝑢 of length 𝑚 whose entries are either a symbol or ⊥, representing an erasure, it returns a vector 𝑓 ′ ∈ F𝑞𝑘 or ⊥. Once the setup phase is completed, the resulting code can be used to encode any number of files. The encoding and decoding procedures are described subsequently. 6.1.1
Setting the parameters
The procedure receives as input a set of nodes P, along with an access structure A = { 𝐴1 , . . . , 𝐴 𝜔 } on P. The goal of this phase is to compute the optimal values for the parameters 𝑚 and 𝑘 of the base code, and thus of the resulting linear monotone erasure code C. By optimal, we mean that they minimize the overhead 𝛽 = 𝑚−𝑘 𝑘 of C over all parameters and labeling functions of linear monotone erasure codes for A. To compute such parameters, we first solve the following linear programming problem to find an optimal solution 𝑦. Then, we derive from 𝑦 the threshold 𝑘 and the number of fragments 𝑚 𝑖 assigned to each 𝑝 𝑖 . Finally, 𝑚 is obtained by summing all the 𝑚 𝑖 values. LPP: Find 𝑦 = (𝑦 1 , . . . , 𝑦 𝑛 ) ∈ R𝑛 such that ∑︁ min 𝑦𝑖 subject to Γ · 𝑦
⊤
𝑖 ∈ [𝑛] ≥ 1⊤𝜔
(LPP)
𝑦≥0 where Γ is a binary 𝜔 × 𝑛 matrix such that Γ𝑖 𝑗 = 1 if and only if 𝑝 𝑗 ∈ 𝐴𝑖 , and 1 𝜔 = (1, . . . , 1) ∈ N 𝜔 . Note that LPP is solvable, as 𝑦 𝑖 = 1 for every 𝑖 ∈ [𝑛] is always a solution. Since LPP has only rational coefficients, it follows that an optimal solution 𝑦 lies in Q𝑛 . Given such a solution of LPP, we set 𝑘 as the lcm of the denominators of all the 𝑦 𝑖 ’s, where each Í𝑛 𝑦 𝑖 is expressed as a reduced fraction, and set 𝑚 𝑖 = 𝑦 𝑖 · 𝑘, for 𝑖 ∈ [𝑛]. We then compute 𝑚 = 𝑖=1 𝑚𝑖 , obtaining the optimal values for 𝑚 and 𝑘. Indeed, notice that Í ∑︁ 𝑖 ∈ [𝑛] 𝑦 𝑖 · 𝑘 − 𝑘 𝛽= = 𝑦𝑖 − 1 𝑘 𝑖 ∈ [𝑛]
Í
so minimizing 𝑖 ∈ [𝑛] 𝑦 𝑖 is equivalent to minimizing 𝛽. Moreover, the vectors 𝑠 = (𝑚 1 , . . . , 𝑚 𝑛 ) ∈ N𝑛 and 𝜅 𝜔 = (𝑘, . . . , 𝑘) ∈ N 𝜔 satisfy the constraint Γ · 𝑠⊤ ≥ 𝜅 𝜔 . This corresponds to requiring that for all 𝐴 ∈ A the nodes in 𝐴 hold at least 𝑘 base fragments together. This way, completeness is guaranteed since each access set has at least 𝑘 fragments, and thus, by Theorem 1, each access set is sufficient. Notice that there is an infinite number of solutions. Indeed, we can take 𝑘 as any multiple of the lcm of the denominators of all the 𝑦 𝑖 ’s, and the corresponding 𝑚 𝑖 ’s would still minimize 𝛽 + 1. Example 2. Let A = {{𝑎, 𝑐, 𝑑, 𝑒}, {𝑏, 𝑐, 𝑑, 𝑒}, {𝑎, 𝑏, 𝑐}, {𝑎, 𝑏, 𝑑}, {𝑎, 𝑏, 𝑒}} be an access structure on P = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}. Then, we have 1 © 0 Γ = 1 1 «1
0 1 1 1 1
1 1 1 0 0
1 1 0 1 0
1 ª 1® ® 0® ∈ F5×5 2 ® 0® 1¬
and the optimal solution of the LP problem min
5 ∑︁
𝑦𝑖
𝑦
𝑖=1
subject to Γ · 𝑦 ⊤ ≥ 1⊤ 5 𝑦≥0 14
is 𝑦 = (𝑦 1 , . . . , 𝑦 5 ) = ( 25 , 52 , 15 , 15 , 15 ) ∈ Q5 . Setting 𝑘 = 5 gives (𝑚 1 , . . . , 𝑚 5 ) = (𝑦 1 · 𝑘, . . . , 𝑦 5 · 𝑘) = (2, 2, 1, 1, 1). This fragment distribution yields the optimal value for the overhead of the corresponding 2 △ linear erasure code, which is 𝑚−𝑘 𝑘 = 5. 6.1.2
Building the code
Once we have determined the optimal parameters 𝑚 and 𝑘 of C for A, together with the values {𝑚 𝑖 }𝑖 ∈ [𝑛] , we choose a prime power 𝑞 such that 𝑞 ≥ 𝑚. We then take an [𝑚, 𝑘]-MDS code over F𝑞 and turn it into an [𝑚, 𝑘]-linear monotone erasure code by building an appropriate labeling function 𝜙. In particular, we partition the set [𝑚] into 𝑛 disjoint subsets Ω1 , . . . , Ω𝑛 of cardinalities 𝑚 1 , . . . , 𝑚 𝑛 , where Ω1 contains the first 𝑚 1 indices, Ω2 the indices from 𝑚 1 + 1 to 𝑚 1 + 𝑚 2 , and so on. Then for each 𝑖 ∈ [𝑚], we set 𝜙(𝑖) = 𝑝 𝑗 iff. 𝑖 ∈ Ω 𝑗 . Encoding. To encode a file 𝑓 , we first give 𝑓 as input to the function MDSEncode() of the base code, which is part of the given implementation. MDSEncode( 𝑓 ) then returns the base fragments (𝑐 1 , . . . , 𝑐 𝑚 ) ∈ F𝑞𝑚 . Finally, we assign to each 𝑝 𝑖 a list of base fragments 𝑔𝑖 = (𝑐 𝑗1 , . . . , 𝑐 𝑗𝑚𝑖 ), where 𝑝 𝑖 = 𝜙( 𝑗ℓ ) for ℓ = 1, . . . , 𝑚 𝑖 . Details of the procedure are given in Algorithm 1. Note that since we are using a linear MDS code, the base fragments are given by (𝑐 1 , . . . , 𝑐 𝑚 ) = 𝑓 · 𝐺, where 𝐺 ∈ F𝑞𝑘×𝑚 is the generator matrix of the MDS code. Moreover, the fragment assigned to 𝑝 𝑖 is 𝑔𝑖 = 𝑓 · 𝐺 𝑝𝑖 . Finally, if 𝑚 𝑖 = 0, then the fragment of 𝑝 𝑖 is ⊥. Algorithm 1 Encode( 𝑓 ) Ð𝑛 Input: file 𝑓 ∈ F𝑞𝑘 , disjoint sets Ω1 , . . . , Ω𝑛 such that 𝑖=1 Ω𝑖 = [𝑚]. Output: fragments (𝑔1 , . . . , 𝑔𝑛 ). 1: (𝑐 1 , . . . , 𝑐 𝑚 ) ← − MDSEncode( 𝑓 ) 2: for 𝑖 ∈ [𝑛] do 3: 𝑔𝑖 ← −[] 4: for 𝑗 ∈ Ω𝑖 do 5: append(𝑔𝑖 , 𝑐 𝑗 ) 6: if 𝑔𝑖 = [ ] then 7: 𝑔𝑖 ← ⊥ 8: return (𝑔1 , . . . , 𝑔𝑛 )
Decoding. The decoding procedure of C corresponds to the decoding procedure MDSDecode of the base code.
6.2
Bounds on linear monotone erasure codes
In this section, we give bounds on the total number of base fragments 𝑚 and the overhead 𝛽 of any linear monotone erasure code C for A built as in Section 6.1. In the computation of such bounds for A, a central role is played by the size of the smallest access set, i.e, min{| 𝐴|, 𝐴 ∈ A}, which we denote by 𝜏. Theorem 7. Let P be a set of nodes with |P | = 𝑛, and let A be an access structure on P. If C is a linear monotone erasure code that encodes files of length 𝑘, then the optimal value for 𝑚 is bounded by 𝑘 𝑘≤𝑚≤ · 𝑛. 𝜏 Proof. The lower bound is straightforward, as at least 𝑘 fragments must be stored to make decoding possible. To prove the upper bound, assume that each node 𝑝 𝑖 ∈ P receives exactly 𝜏𝑘 base fragments. Then, for all 𝐴 ∈ A, i.e., | 𝐴| = |{𝑝 𝑖1 , . . . , 𝑝 𝑖𝑠 }| = 𝑠, we have 𝑘 𝑘 |𝑔𝑖1 ∪ . . . ∪ 𝑔𝑖𝑠 | = 𝑠 · ≥𝑠· ≥𝑘 𝜏 𝜏 15
since 𝑠 ≥ 𝜏. Thus, every set 𝐴 ∈ A is able to reconstruct the information vector. Therefore, 𝜏𝑘 · 𝑛 fragments are sufficient. Moreover, using a higher number of fragments would make the overhead worse, 𝑘 □ so we have 𝑚 ≤ 𝜏 · 𝑛. The upper bound of Theorem 7 means that any set 𝐵 ⊆ P with |𝐵| ≥ 𝜏 is able to reconstruct the ′ ′ information vector 𝑓 . In general, 𝑘 since there is a set 𝐵 ∈ A such that |𝐵 | = 𝜏, there is at least one node ′ 𝑝 ∈ 𝐵 that stores at least 𝜏 base fragments. Moreover, we have the following direct consequence of Theorem 7 that highlights how efficient a linear monotone erasure code for a given access structure A can be. Corollary 8. The overhead 𝛽 of an [𝑚, 𝑘]-linear monotone erasure code for a given access structure A is bounded for large 𝑘 ∈ N by 𝑛−𝜏 𝛽≤ . 𝜏 Proof. From Theorem 7 we have 𝑚 ≤ 𝜏𝑘 · 𝑛. Therefore,
𝛽=
𝑚−𝑘 ≤ 𝑘
𝑘 𝜏
·𝑛−𝑘 < 𝑘
𝑘 𝜏 +1
·𝑛−𝑘 =
𝑘
Now, if 𝑘 tends to infinity, we get the result.
𝑛 𝑛−𝜏 + . 𝑘 𝜏 □
As a consequence of this result, we have that if 𝑘 is large enough and 𝜏 is close to 𝑛, then the overhead is close to zero. In particular, this means that when the size of the smallest access set is close to 𝑛, we add little redundancy. This is not surprising, as this situation goes toward the threshold case with 𝑘 = 𝑛, in which each node stores one base fragment only and the overhead is zero.
7
Partitioned Access Structures
In the previous section, we have shown how to construct a linear monotone erasure code C for an arbitrary access structure A from a threshold erasure code. This works by solving LPP, which is derived from A, and is efficient if A has a compact (e.g., polynomial-size) description in the number of nodes. However, there may be exponentially many (in 𝑛) access sets in A. In this section, we consider a special kind of access structure 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 the set of nodes P. Every node in P appears exactly once in the MBF that describes the access structure. Definition 7. Let P be a set of nodes. A partitioned access structure A on P is given by an access tree 𝑇 with root 𝑣 R , in which every internal vertex 𝑣 with 𝑟 children is labeled with 𝑡 and corresponds to the threshold operator Θ𝑟𝑡 . The leaves correspond to the nodes in P and are partitioned into 𝛿 sets 𝐵𝑖 . In particular, for each 𝑖 ∈ [𝛿], there is a uniquely determined vertex 𝑣 𝑖 such that 𝐵𝑖 consists exactly of the children of 𝑣 𝑖 . An 𝐿-level partitioned access structure A is represented by a tree with 𝐿 levels. We denote the number of vertices on level 𝑗 ∈ [𝐿] by 𝑠 𝑗 , where 𝑠1 = 1 since the root is on level one; the leaves are on level 𝐿 + 1. In the following we always assume that the access tree is balanced, i.e., that the path from the root to each leaf node contains exactly 𝐿 + 1 vertices. Note that an access tree 𝑇 can always be made balanced by adding vertices with label 1 to any path shorter than 𝐿 + 1. We focus on partitioned access structures here because they admit an efficient construction of monotone erasure codes, as shown in the remainder of this section. Example 3. Consider several organizations (universities, governments, companies, etc.) that each run a set of nodes in a distributed system, and an access structure corresponding to the assumption that more than two thirds of the organizations will remain available and, among each organization that remains available, 16
more than half of the organization’s nodes will remain available. The Stellar network [25] is a real-world example of a system using this trust model. Its node set P is partitioned into organizations 𝐵1 , . . . , 𝐵𝑟 , and the access structure can be expressed by an MBF like Θ𝑟𝑡 (Θ𝑏𝑧11 (𝐵1 ), . . . , Θ𝑏𝑧𝑟𝑟 (𝐵𝑟 )), 𝑦
𝑦
where the notation Θ 𝑥 (𝐵𝑖 ) stands for Θ 𝑥 ({𝑝 𝑗 } 𝑝 𝑗 ∈ 𝐵𝑖 ). More generally, one can consider sub-organizations or groups of organizations (e.g. all companies, all universities, etc.) and create hierarchical, partitioned access structures with arbitrarily many levels. 2
1
1
𝑎
𝑏
1
𝑐
𝑑
𝑒
Figure 3. Access tree of Example 4.
7.1
Uniform assignment
Let A be an 𝐿-level partitioned access structure with tree 𝑇 and partition 𝐵1 , . . . , 𝐵 𝛿 . We propose here a fragments assignment, called uniform assignment, that is efficient to compute but not always optimal in terms of overhead. In more detail, the uniform assignment provides parameters (𝑚, 𝑘) for the base code such that the resulting monotone erasure code is complete. Let 𝑅𝑣 be the set of vertices on the unique path from the root to vertex 𝑣. For all 𝑖 ∈ [𝛿], the number of base fragments assigned to each 𝑝 𝑗 ∈ 𝐵𝑖 is 𝑘 𝑚𝑗 = Î
, 𝑥𝑣
𝑣 ∈ 𝑅𝑣𝑖
where 𝑣 𝑖 is the vertex whose set of children is 𝐵𝑖 and 𝑘 = 𝑙𝑐𝑚(𝑑𝑒𝑛(𝑚 𝑗 ) 𝑗 ∈ [𝑛] ). Figure 4 shows a visual representation of the uniform assignment on a two-level partitioned access structure. The idea is that each child of a vertex in the tree gets the same amount of information. In more detail, if the file has size 𝑘, then any child of the root gets an information of size 𝑘/𝑡. In this way, any 𝑘 children of the root have enough information for reconstruction. With the same reasoning, the information is further distributed among all paths until we reach the leaves. This ensures that any set 𝐴 ∈ A holds exactly 𝑘 fragments, and thus it is able to reconstruct the file. Intuitively, giving less fragments to some 𝑝 ∈ P makes some access set insufficient, which violates completeness of the code. Example 4. Consider the following two-level partitioned access structure A = Θ32 (Θ11 (𝑎), Θ11 (𝑏), Θ31 (𝑐, 𝑑, 𝑒)). Figure 3 shows the tree of A. With the uniform assignment to A, each node receives 𝑘2 fragments, and this leads to an overhead of 𝛽 = 23 . Note that nodes in {𝑐, 𝑑, 𝑒} receive more base fragments together compared to 𝑎 and 𝑏. Therefore, the question arises whether the overhead gets smaller if we reduce the number of base fragments given to nodes in {𝑐, 𝑑, 𝑒} and assign more fragments to 𝑎 and 𝑏. For instance, if each node in {𝑐, 𝑑, 𝑒} receives no base fragment, we can consider 𝑐, 𝑑 and 𝑒 as absent. This leads to a new access structure A0 = Θ21 (Θ11 (𝑎), Θ11 (𝑏)) = Θ21 (𝑎, 𝑏). Note that for each 𝐴 ∈ A there exists a set 𝐴0 ∈ A0 such that 𝐴0 ⊂ 𝐴. This implies that A0 contains A. Therefore, 𝑎 and 𝑏 must compensate the loss of the base fragments of the nodes in {𝑐, 𝑑, 𝑒} in order to make each access set 𝐴 ∈ A qualified. To achieve this, we apply the uniform assignment to A0 , which allocates 𝑘 fragments to both 𝑎 and 𝑏. This leads to the overhead 𝛽0 = 1 < 𝛽, which shows that the uniform assignment is not optimal for A. △ 17
1 𝑘
𝑡
𝑘 𝑡
𝑝 1,1
𝑘 𝑡
···
𝑧1 𝑘 𝑡 ·𝑧1
𝑘 𝑡
𝑧𝑟
𝑘 𝑡 ·𝑧1
···
𝑘 𝑡 ·𝑧𝑟
𝑝 1,𝑏1
𝑝 𝑟 ,1
𝑘 𝑡 ·𝑧𝑟
···
𝑝 𝑟 ,𝑏𝑟
Figure 4. Uniform assignment of base fragments.
Example 4 demonstrates that in some cases it is beneficial to disregard nodes from P, i.e., to assign them zero base fragments. Based on this, in Section 7.2, we provide a method that builds an optimal assignment for any partitioned access structure.
7.2
Optimal fragment assignment algorithm
We present here an algorithm that finds an optimal solution to LPP for any partitioned access structure in a way that substantially reduces the computational effort compared to solving the minimization problem directly. The algorithm takes an access tree 𝑇 of a partitioned access structure as input, and returns the optimal parameters (𝜈𝑇 , 𝑘 𝑇 , ℎ𝑇 ) for the base code, where: • 𝜈𝑇 is total number of base fragments held by all nodes in 𝑇; • 𝑘 𝑇 is the reconstruction threshold of the code; • ℎ𝑇 : [𝑛] → N is a function that returns the number of base fragments assigned to node 𝑖 ∈ [𝑛] by the construction. We now give an overview of the algorithm. Recall that each vertex in 𝑇 with 𝑟 children is labeled with a value 𝑡 representing the threshold of the corresponding operator Θ𝑟𝑡 . 1. If 𝑇 has depth zero and consists of only one (leaf) vertex 𝑖, then let (𝜈𝑇 , 𝑘 𝑇 ) = (1, 1), let ℎ𝑇 (𝑖) = 1, and let ℎ𝑇 ( 𝑗) = 0 for 𝑗 ≠ 𝑖. Return (𝜈𝑇 , 𝑘 𝑇 , ℎ𝑇 ). 2. If 𝑇 has depth one or more and consists of a root labeled 𝑡 and 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 : (a) Apply the algorithm to each subtree 𝑇𝑎 for 𝑎 ∈ [𝑟], to obtain (𝜈 𝑎 , 𝑘 𝑎 , ℎ 𝑎 ). Let 𝜌 𝑎 = 𝜈 𝑎 /𝑘 𝑎 . W.l.o.g., assume the subtrees are ordered so that if 𝑎 < 𝑏 then 𝜌 𝑎 ≤ 𝜌 𝑏 . (b) Consider any 𝑠 ∈ {𝑟 − 𝑡 + 1, . . . , 𝑟 − 1} such that 𝜌 𝑠+1 ≥
18
𝑠 ∑︁ 1 𝜌𝑎 𝑠 − 𝑟 + 𝑡 𝑎=1
and let 𝑠∗ be the smallest such 𝑠 or let 𝑠∗ = 𝑟 if no suitable 𝑠 satisfies the condition. Note that if the condition on 𝜌 𝑠 holds for some 𝑠 < 𝑟, then it also holds for any 𝑠′ > 𝑠. Let 𝑆 = {1, . . . , 𝑠∗ } and 𝜆 = lcm({ 𝑘 𝑎 | 𝑎 ∈ 𝑆 }). (c) For each 𝑎 ∈ 𝑆, set 𝛼𝑎 = 𝜆/𝑘 𝑎 (an integer). Then rescale the base fragment counts 𝜈 𝑎 and ℎ 𝑎 returned for each subtree 𝑎 ∈ [𝑟] as ( 𝛼𝑎 𝜈 𝑎 if 𝑎 ∈ 𝑆 ′ 𝜈𝑎 = 0 if 𝑎 ∉ 𝑆 Analogously, for each 𝑎 ∈ [𝑟] and 𝑖 ∈ [𝑛] set ( 𝛼𝑎 ℎ 𝑎 (𝑖) ℎ′𝑎 (𝑖) = 0
if 𝑎 ∈ 𝑆 if 𝑎 ∉ 𝑆
(d) Finally, let 𝜈𝑇 =
𝑟 ∑︁
𝜈 ′𝑎 ,
𝑎=1 ∗
𝑘 𝑇 = (𝑠 − 𝑟 + 𝑡) 𝜆 and the function ℎ𝑇 : [𝑛] → N be such that for 𝑖 ∈ [𝑛] ( ℎ′ (𝑖) if there is some 𝑎 ∈ 𝑆 with ℎ 𝑎 (𝑖) > 0 ℎ𝑇 (𝑖) = 𝑎 0 otherwise. For the definition of ℎ𝑇 , recall that A is partitioned, hence, every node appears in at most one subtree. 3. Return (𝜈𝑇 , 𝑘 𝑇 , ℎ𝑇 ). The resulting code C therefore is a [𝜈𝑇 , 𝑘 𝑇 ]-linear monotone erasure code such that the fragment of each node 𝑖 in C consists of ℎ𝑇 (𝑖) (base) fragments of C ′ . Details of the procedure can be found in function FA(𝑇, 𝐿) in Algorithm 2, which takes as input an access tree 𝑇 with 𝐿 levels. We assume that each leaf is assigned a global index 𝑖 ∈ [𝑛], where 𝑛 is globally known. The time complexity of the algorithm is O (𝑛2 ), which is considerably lower than the complexity required to directly solve LPP. Note that for partitioned access structures, the algorithm discussed in Section 5.1 can be extended with the algorithm presented in this section. In this case, the resulting linear monotone erasure code is optimal. As the encoding matrix has a block-wise MDS property, this leads to a smaller required field size. Example 5. Consider the following partitioned access structure A = Θ32 (Θ33 ( 𝑝 1 , 𝑝 2 , 𝑝 3 ), Θ32 ( 𝑝 4 , 𝑝 5 , 𝑝 6 ), Θ31 ( 𝑝 7 , 𝑝 8 , 𝑝 9 )). Figure 5 shows the access tree 𝑇 of A. Let 𝑇 (1) , 𝑇 (2) and 𝑇 (3) be the depth one subtrees of 𝑇. Note that each subtree 𝑇 (𝑖) is further decomposed into multiple subtrees of depth zero, each consisting of only one
19
Algorithm 2 Fragments assignment // 𝑛 is a global parameter indicating the number of nodes in P 1: function FA(𝑇, 𝐿) 2: 𝑇1 , . . . , 𝑇𝑟 ← subtrees of 𝑇 3: 𝑡 ← label of root 𝑣 of 𝑇 4: ℎ𝑇 ← [ ]: hash map from [𝑛] to N, initially ℎ𝑇 [𝑧] = 0 for 𝑧 ∈ [𝑛] 5: ℎ𝑖 ← [ ] for 𝑖 ∈ [𝑟]: hash maps from [𝑛] to N, initially ℎ𝑖 [𝑧] = 0 for 𝑧 ∈ [𝑛] 6: if 𝐿 = 0 then // base case where 𝑇 is the leaf 𝑣 𝑖 7: for 𝑗 ∈ [𝑛] do 8: ℎ𝑇 [ 𝑗] ← 0 9: ℎ𝑇 [𝑖] ← 1 10: (𝜈𝑇 , 𝑘 𝑇 ) ← (1, 1) 11: else 12: for 𝑣 𝑖 child of 𝑣 do 13: (𝜈𝑖 , 𝑘 𝑖 , ℎ𝑖 ) ← FA(𝑇𝑖 , 𝐿 − 1) 14: 𝜌𝑖 ← 𝜈𝑘𝑖𝑖 15: 𝜋 ← [𝜌𝑖 ] 𝑖 ∈ [𝑟 ] 16: 𝜋 ← SORT(𝜋) Í𝑠 1 17: 𝐼 ← 𝑠 ∈ {𝑟 − 𝑡 + 1, . . . , 𝑟 − 1} | 𝜌 𝑠+1 ≥ 𝑠−𝑟+𝑡 𝑖=1 𝜌𝑖 ∗ 18: 𝑠 ← min{𝐼 ∪ {𝑟 }} 19: 𝜆 ← lcm({𝑘 𝑖 | 𝑖 ≤ 𝑠∗ }) 20: for 𝑖 ∈ [𝑠∗ ] do 21: 𝛼𝑖 ← 𝑘𝜆𝑖 22: 𝜈𝑖 ← 𝛼𝑖 · 𝜈𝑖 23: for 𝑧 ∈ [𝑛] do 24: ℎ𝑖 [𝑧] ← 𝛼𝑖 ℎ𝑖 [𝑧] 25: for 𝑖 = 𝑠∗ + 1, . . . , 𝑟 do 26: 𝜈𝑖 ← 0 27: for 𝑧 ∈ [𝑛] do 28: ℎ𝑖 [𝑧] ← 0 29: for 𝑧 ∈ [𝑛] do 30: if ∃𝑖 ∈ [𝑟] s.t. ℎ𝑖 [𝑧] > 0 then 31: ℎ𝑇 [𝑧] ← ℎ𝑖 [𝑧] 32: else 33: Í ℎ𝑇 [𝑧] ← 0 34: 𝜈𝑇 = 𝑟𝑖=1 𝜈𝑖 35: 𝑘 𝑇 = (𝑠∗ − 𝑟 + 𝑡) · 𝜆 36: return (𝜈𝑇 , 𝑘 𝑇 , ℎ𝑇 )
leaf. For simplicity, we identify each of these subtrees with its root node 𝑝 𝑖 . Then, for each leaf 𝑝 𝑖 , the algorithm first delivers the following tuples (𝜈𝑖 , 𝑘 𝑖 , ℎ𝑖 ) = FA( 𝑝 𝑖 , 0) = (1, 1, ℎ𝑖 ) where ( 1 for 𝑧 = 𝑖 ℎ𝑖 (𝑧) = 0 else Let 𝑇 be the subtree corresponding to 𝑇1(1) . We get 𝜈𝑇 = 1, 𝑘 𝑇 = 1, and ( ℎ𝑇 (𝑧) =
1 0
for 𝑧 = 1 else
Thus, FA 𝑇1(1) , 1 = (1, 1, ℎ1 ), where ℎ1 = ℎ𝑇 . Analogously, we get FA 𝑇2(1) , 1 = (3, 2, ℎ2 ) and 20
FA 𝑇3(1) , 1 = (3, 1, ℎ3 ) where ( ℎ2 (𝑧) = ( ℎ3 (𝑧) =
1 0
if 𝑧 = 4, 5, 6 else
1 0
if 𝑧 = 7, 8, 9 else
Finally, the output is FA(𝑇, 3) = (5, 2, ℎ𝑇 ), where if 𝑧 = 1 if 𝑧 = 4, 5, 6 else
2 ℎ𝑇 (𝑧) = 1 0 2
3
𝑝1
𝑝2
2
𝑝3
𝑝4
1
𝑝5
𝑝6
𝑝7
𝑝8
𝑝9
Figure 5. Access tree 𝑇 of A △
7.3
Analysis
We now show that applying Algorithm 2 to any partitioned access structure A provides an optimal linear monotone erasure code for A. To do that, we first rephrase the problem we want to solve, namely, LPP, in a recursive way, which makes the proof easier. Recall that, given an access structure A = { 𝐴1 , . . . , 𝐴 𝜔 }, LPP is defined as follows: ∑︁ min𝑛 𝑦𝑖 𝑦 ∈R
subject to Γ · 𝑦
⊤
𝑖 ∈ [𝑛] ≥ 1⊤𝜔
(LPP)
𝑦≥0 where Γ is a binary 𝜔 × 𝑛 matrix such that Γ𝑖 𝑗 = 1 if and only if 𝑝 𝑗 ∈ 𝐴𝑖 , and Γ𝑖 𝑗 = 0 otherwise, and 1 𝜔 = (1, . . . , 1) ∈ N 𝜔 . Consider a partitioned access structure A with access tree 𝑇, where the root is labeled 𝑡 and there are 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 . Let us denote by Aℓ the access structure determined by subtree 𝑇ℓ . Notice that, for all access sets 𝐴 ∈ A, there exist sets 𝑆1 , . . . , 𝑆𝑡 and a permutation 𝜎 of {1, . . . , 𝑟} such that Ø 𝐴= 𝑆𝑖 𝑖 ∈ [𝑡 ]
where, for each ℓ ∈ [𝑡], 𝑆ℓ ∈ A 𝜎 (ℓ ) . For simplicity, assume 𝜎(ℓ) = ℓ for each ℓ ∈ [𝑡]. Additionally, let Pℓ be the set of nodes corresponding to the leaves in each subtree 𝑇ℓ . As required by the first inequality in LPP, for each 𝐴 ∈ A it must hold ∑︁ ∑︁ ∑︁ 𝑦 𝑖 ≥ 1 ⇐⇒ 𝑦 𝑖 ≥ 1. 𝑝𝑖 ∈ 𝐴
ℓ ∈ [𝑡 ] 𝑝𝑖 ∈𝑆ℓ
21
Let 𝑦 ′ ∈ R𝑛≥0 and 𝛾 ′ ∈ R𝑟≥0 be such that 𝑦 𝑖 = 𝛾ℓ′ 𝑦 𝑖′ for all 𝑝 𝑖 ∈ 𝑆ℓ , with ℓ ∈ [𝑟]. Then, we can rewrite LPP as follows ∑︁ ∑︁ ′ 𝑦 𝑖′ min 𝛾 ℓ ′ ′ 𝛾 ,𝑦
subject to
ℓ ∈ [𝑟 ]
𝑝𝑖 ∈ Pℓ
∑︁
𝛾ℓ′
∑︁
ℓ∈𝐽 ′ ′
𝑝𝑖 ∈𝑆
𝑦 𝑖′ ≥ 1
(𝑃′ )
for all 𝐽 ⊆ [𝑟], |𝐽 | = 𝑡, 𝑆 ∈ Aℓ
𝛾 ,𝑦 ≥0 Now, define 𝑑ℓ as min{ 𝑝𝑖 ∈𝑆 𝑦 𝑖′ | (𝛾 ′ , 𝑦 ′ ) is a solution to 𝑃′ and 𝑆 ∈ Aℓ }. Then, for each valid 𝑦 ′ and for each 𝑆 ∈ Aℓ it holds ∑︁ ∑︁ 𝑦 𝑖′ ≥ 𝑑ℓ ⇐⇒ 𝑦 𝑖′′ ≥ 1 Í
𝑝𝑖 ∈𝑆
where 𝑦 𝑖′′ =
𝑦𝑖′ 𝑑ℓ
𝑝𝑖 ∈𝑆
for all 𝑝 𝑖 ∈ 𝑆. We can therefore derive the following subproblem for each ℓ ∈ [𝑟]: ∑︁ 𝑦 𝑖′′ min ′′ 𝑦
𝑝𝑖 ∈ Pℓ
∑︁
subject to
𝑦 𝑖′′ ≥ 1
for all 𝑆 ∈ Aℓ
(𝑃ℓ )
𝑝𝑖 ∈𝑆
𝑦 ′′ ≥ 0 which corresponds to LPP instantiated on 𝑇ℓ . As explained in Section 6.1.1, the threshold of subproblem (𝑃ℓ ) is 𝑘 ℓ = 𝑙𝑐𝑚(𝑑𝑒𝑛(𝑦 𝑖′′ )) 𝑝𝑖 ∈ Pℓ , and the number of fragments assigned to each 𝑝 𝑖 is 𝑚 𝑖 = 𝑦 𝑖′′ 𝑘 ℓ . In particular, this means that ∑︁ 𝑦 𝑖′′ · 𝑘 ℓ = 𝜈ℓ 𝑝𝑖 ∈ Pℓ
which leads to the following chain of equalities ∑︁ 𝑖 ∈ [𝑛]
𝑦𝑖 =
∑︁
∑︁
𝛾ℓ′
𝑝𝑖 ∈ Pℓ
ℓ ∈ [𝑟 ]
𝑦 𝑖′ =
∑︁
∑︁
𝛾ℓ′ 𝑑ℓ
𝑦 𝑖′′ =
𝑝𝑖 ∈ Pℓ
ℓ ∈ [𝑟 ]
∑︁ ℓ ∈ [𝑟 ]
𝛾ℓ′ 𝑑ℓ
∑︁ ∑︁ 𝑦 ′′ · 𝑘 ℓ 𝜈ℓ 𝑖 = 𝛾ℓ′ 𝑑ℓ 𝑘ℓ 𝑘ℓ 𝑝 ∈P 𝑖
ℓ
ℓ ∈ [𝑟 ]
Moreover, if 𝛾ℓ = 𝛾ℓ′ 𝑑ℓ , then the constraint in Problem (𝑃′ ) is equivalent to ∑︁
𝛾ℓ
ℓ∈𝐽
which is equivalent to
Í
ℓ ∈ 𝐽 𝛾ℓ ≥ 1 as
min
Í
𝑦 𝑖′′ ≥ 1
𝑝𝑖 ∈𝑆
′′ 𝑝𝑖 ∈𝑆 𝑦 𝑖 ≥ 1.We can therefore rewrite LPP as follows:
𝑟 ∑︁
𝛾, 𝜓
subject to
∑︁
ℓ=1 ∑︁
𝛾ℓ
𝜈ℓ 𝑘ℓ
𝛾𝑗 ≥ 1
for all 𝐽 ⊆ [𝑟], |𝐽 | = 𝑡
(𝑃)
𝑗∈𝐽
𝛾≥0 where 𝜓 = ( 𝜈𝑘ℓℓ )ℓ ∈ [𝑟 ] , with 𝜈𝑘ℓℓ given by a valid (not necessarily optimal) solution of subproblem (𝑃ℓ ) instantiated on 𝑇ℓ , for each ℓ ∈ [𝑟]. We are now ready to state some preliminary lemmas that will be used in the proof of Theorem 11, which ensures that Algorithm 2 provides the optimal parameters of a linear monotone erasure code for any partitioned access structure. Our approach consists in showing that, at each step, the algorithm finds an optimal solution of a subproblem, and then it combines such solutions optimally to build a solution of the main problem. In particular, Lemma 9 shows that an optimal solution on the main problem induces optimal solutions on all subproblems. Then, Lemma 10 shows how to find an optimal solution of a subproblem. 22
Lemma 9. Let 𝑇 be the access tree of a partitioned access structure consisting of a root labeled 𝑡 and 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 . Then, every optimal solution of (𝑃) induces an optimal solution of each subproblem (𝑃ℓ ) for ℓ ∈ [𝑟]. Í Proof. Assume we have a valid solution (𝛾, 𝜓) to (𝑃) corresponding to the objective value 𝑟ℓ=1 𝛾ℓ 𝜈𝑘ℓℓ . ˜ to (𝑃) such that there is some 𝑞 ∈ [𝑟] with 𝜈˜˜𝑞 ≤ 𝜈𝑞 , and Then, assume there exists a valid solution (𝛾, 𝜓) 𝑘𝑞
𝑘𝑞
𝜈˜ℓ = 𝜈𝑘ℓℓ for ℓ ≠ 𝑞. Then we have 𝑘˜ℓ 𝑟 ∑︁
𝛾𝑖
𝑖=1,𝑖≠𝑞
𝑟 𝜈˜𝑞 ∑︁ 𝜈𝑖 𝜈𝑖 + 𝛾𝑞 ≤ 𝛾𝑖 . ˜𝑘 𝑞 𝑘𝑖 𝑘 𝑖 𝑖=1
𝜈
Therefore, minimizing 𝑘𝑞𝑞 reduces the objective value of (𝑃), thus, an optimal solution to (𝑃) must minimize 𝜈𝑘𝑖𝑖 for each 𝑖 ∈ [𝑟], which concludes the proof. □ As a consequence of Lemma 9, (𝑃) reduces to min
𝑟 ∑︁
𝛾ℓ
𝛾
subject to
ℓ=1 ∑︁
𝜈ℓ∗ 𝑘 ℓ∗
𝛾𝑗 ≥ 1
for all 𝐽 ⊆ [𝑟], |𝐽 | = 𝑡
(𝑃∗ )
𝑗∈𝐽
𝛾≥0 𝜈∗
where 𝑘ℓ∗ is given by an optimal solution of subproblem (𝑃ℓ ) instantiated on 𝑇ℓ , for each ℓ ∈ [𝑟]. ℓ Therefore, the solution to each subproblem (𝑃ℓ ) can be seen as a constant 𝑐 ℓ . The next lemma shows how to find an optimal solution to (𝑃∗ ). Lemma 10. Let 𝑟, 𝑡 be integers such that 𝑡 ≤ 𝑟, and let 𝑐 = (𝑐 𝑖 )𝑖 ∈ [𝑟 ] , where 𝑐 𝑖 ∈ Q ≥1 such that 𝑐 𝑖 ≤ 𝑐 𝑗 for 𝑖 < 𝑗. Moreover, let ( ) 𝑠 ∑︁ 1 ∗ 𝑠 = min 𝑠 ∈ {𝑟 − 𝑡 + 1, . . . , 𝑟 − 1} | 𝑐 𝑠+1 ≥ 𝑐𝑖 . 𝑠 − 𝑟 + 𝑡 𝑖=1 If it does not exist, set 𝑠∗ = 𝑟. Then, the optimal solution of the following problem min
𝑟 ∑︁
𝛾𝑖 𝑐 𝑖
𝛾
𝑖=1
∑︁
𝛾 𝑗 ≥ 1 for all 𝐽 ⊆ [𝑟] with |𝐽 | = 𝑡
(𝑃(𝑐))
𝑗∈𝐽
𝛾≥0 1 for all 𝑗 ≤ 𝑠∗ . where 𝛾𝑖 ∈ R ≥0 is given by 𝛾𝑖 = 0 for all 𝑖 ≥ 𝑠∗ + 1 and 𝛾 𝑗 = 𝑠∗ −𝑟+𝑡
Proof. First, note that under the conditions 𝑐 𝑖 ≤ 𝑐 𝑗 and 𝛾𝑖 ≤ 𝛾 𝑗 , where 𝑖 ≠ 𝑗 ∈ [𝑟], swapping 𝛾 𝑗 and 𝛾𝑖 decreases the objective value and does not violate validity of the solution. Therefore, an optimal solution satisfies 𝑐 1 ≤ . . . ≤ 𝑐𝑟 and 𝛾1 ≥ . . . ≥ 𝛾𝑟 . Moreover, note that for a solution to be valid, it must hold that 𝛾𝑟 −𝑡+1 +...+𝛾𝑟 ≥ 1. This means that we can set 𝛾1 = . . . = 𝛾𝑟 −𝑡+1 because it decreases the objective value without violating validity. Furthermore, if 𝛾𝑟 −𝑡+1 + . . . + 𝛾𝑟 = 𝑣 > 1, then setting 𝛾˜ 𝑖 = 𝛾𝑣𝑖 for 𝑟 − 𝑡 + 1 ≤ 𝑖 ≤ 𝑟 leads to a smaller objective value without violating validity. Therefore, we can assume that 𝛾𝑟 −𝑡+1 + . . . + 𝛾𝑟 = 1. If 𝑠∗ < 𝑟, we can 23
Í 𝛾𝑗 reduce 𝛾 𝑗 with 𝑗 > 𝑠∗ and increase 𝛾𝑖 with 𝑖 ∈ [𝑠∗ ]. In particular, setting 𝛾˜ 𝑖 = 𝛾𝑖 + 𝑟𝑗=𝑠∗ +1 𝑠∗ −𝑟+𝑡 , for all 𝑖 ∈ [𝑠∗ ], and 𝛾˜ 𝑗 = 0, for all 𝑗 ≥ 𝑠∗ + 1, decreases the objective value. Indeed, we have 𝑠∗ ∑︁
𝑠∗ 𝑟 𝑟 𝑠∗ 𝑠∗ ∑︁ ∑︁ ∑︁ ∑︁ © 𝛾𝑗 𝑐𝑖 ª ∑︁ 𝛾˜ 𝑖 𝑐 𝑖 = 𝛾 + · 𝛾 𝑐 = 𝛾 𝑐 + ® 𝑖 𝑗 𝑖 𝑖 𝑖 𝑠∗ − 𝑟 + 𝑡 ∗ −𝑟 +𝑡 𝑠 ∗ ∗ 𝑖=1 𝑖=1 « 𝑗=𝑠 +1 𝑗=𝑠 +1 𝑖=1 ¬ 𝑖=1 ! 𝑠∗ 𝑠∗ 𝑟 ∑︁ ∑︁ ∑︁ 1 · 𝑐𝑖 = 𝛾𝑖 𝑐 𝑖 + 𝛾𝑗 · ∗ 𝑠 − 𝑟 + 𝑡 𝑖=1 𝑖=1 𝑗=𝑠 ∗ +1 ≤
𝑠∗ ∑︁ 𝑖=1
𝛾𝑖 𝑐 𝑖 +
𝑟 ∑︁
𝛾𝑗𝑐 𝑗 =
𝑗=𝑠 ∗ +1
𝑟 ∑︁
𝛾𝑖 𝑐 𝑖
𝑖=1
Í𝑠 ∗ 1 · 𝑖=1 𝑐 𝑖 ≤ 𝑐 𝑗 for all 𝑗 ∈ {𝑠∗ + 1, . . . , 𝑟 } and 𝛾 𝑗 ≥ 0. Moreover, this step does not violate since 𝑠∗ −𝑟+𝑡 validity. Indeed, if 𝐽 ⊆ [𝑠∗ ] with |𝐽 | = 𝑠∗ − 𝑟 + 𝑡, then ∑︁ 𝑟 𝑟 𝑟 ∑︁ ∑︁ ∑︁ ∑︁ ∑︁ 𝛾𝑗 𝛾𝑗 ∗ 𝛾˜ 𝑖 = = 𝛾𝑖 + (𝑠 − 𝑟 + 𝑡) = 𝛾𝑖 + 𝛾𝑗 ≥ 1 𝛾𝑖 + 𝑠∗ − 𝑟 + 𝑡 𝑖 ∈ 𝐽 𝑠∗ − 𝑟 + 𝑡 𝑖 ∈ 𝐽 𝑖∈𝐽 𝑖∈𝐽 𝑗=𝑠 ∗ +1 𝑗=𝑠 ∗ +1 𝑗=𝑠 ∗ +1
∑︁
Thus, we can assume that 𝛾𝑟 = . . . = 𝛾𝑠∗ +1 = 0. Otherwise, if 𝑠∗ = 𝑟, then it must hold 𝛾𝑖 > 0 for all 𝑖 ∈ [𝑟]. Similarly to how we reasoned to set some values of 𝛾 zero, observe that if 𝛾𝑟 −𝑡+2 ≠ 0, it is beneficial to set 𝛾˜ ℓ = 𝛾ℓ − 𝜖 with 𝜖 > 0 for all ℓ ∈ [𝑟 − 𝑡 + 1], and 𝛾˜𝑟 −𝑡+2 = 𝛾𝑟 −𝑡+2 + 𝜖. Indeed, 𝑠∗ ∑︁
∑︁ ∑︁ 𝑠∗ ∑︁ 𝑐 𝑖 𝛾𝑖 − 𝑐 𝑖 (𝛾𝑖 − 𝜖) + 𝑐𝑟 −𝑡+2 (𝛾𝑟 −𝑡+2 + 𝜖) + 𝑐 𝑖 𝛾𝑖 = 𝜖 𝑐 𝑖 − 𝑐𝑟 −𝑡+2 𝑖 ∈ [𝑟 −𝑡+1] 𝑖 ∈ [𝑟 −𝑡+1] 𝑖=1 𝑖=𝑟 −𝑡+3 Í 𝑟 −𝑡+2 is greater than zero since 𝑠∗ ≥ 𝑟 −𝑡 +2 and thus 𝑖 ∈ [𝑟 −𝑡+1] 𝑐 𝑖 > 𝑐𝑟 −𝑡+2 . Therefore, setting 𝜖 = 𝛾𝑟 −𝑡+1 −𝛾 2 𝛾˜
− 𝛾˜
𝑗 leads to 𝛾˜ 1 = . . . = 𝛾˜𝑟 −𝑡+2 . This process can be iterated for 𝑠∗ ≥ 𝑗 > 𝑟 − 𝑡 + 2 with 𝜖 = 𝑗𝑗 −1 −𝑟+𝑡 , i.e., set ′ ′ 𝛾𝑖 = 𝛾˜ 𝑖 − 𝜖 for 𝑖 ≤ 𝑗 − 1 and set 𝛾 𝑗 = 𝛾˜ 𝑗 + 𝜖 ( 𝑗 − 𝑟 + 𝑡 − 1). This step preserves validity since
𝑗 −1 ∑︁
( 𝛾˜ 𝑖 − 𝜖) + 𝛾˜ 𝑗 + ( 𝑗 − 𝑟 + 𝑡 − 1)𝜖 =
𝑖=𝑟 −𝑡+1
Moreover, setting 𝜖 =
𝑗 ∑︁
𝛾˜ 𝑖
𝑖=𝑟 −𝑡+1
𝛾˜ 𝑗 −1 − 𝛾˜ 𝑗 ′ ′ ∗ 𝑗 −𝑟+𝑡 ensures that 𝛾𝑖 = 𝛾 𝑗 for 𝑖 < 𝑗 ≤ 𝑠 , since
𝛾˜ 𝑗 −1 − 𝛾˜ 𝑗 − 𝛾 ′𝑗 −1 − 𝛾 ′𝑗 = 𝛾˜ 𝑗 −1 − 𝑗 −𝑟 +𝑡
𝛾˜ 𝑗 −1 − 𝛾˜ 𝑗 𝛾˜ 𝑗 + ( 𝑗 − 𝑟 + 𝑡 − 1) = 𝛾˜ 𝑗 −1 − 𝛾˜ 𝑗 − ( 𝛾˜ 𝑗 −1 − 𝛾˜ 𝑗 ) = 0 𝑗 −𝑟 +𝑡
1 Therefore, we end up with 𝛾𝑖 = 𝑠∗ −𝑟+𝑡 for all 𝑖 ∈ [𝑠∗ ], and 𝛾 𝑗 = 0 for all 𝑠∗ + 1 ≤ 𝑗 ≤ 𝑟. Since the objective function can not be increased further by changing the values of 𝛾, the Lemma is proven. □
Theorem 11. Given an 𝐿-level partitioned access structure A, Algorithm 2 finds the optimal parameters 𝑚 and 𝑘 for an [𝑚, 𝑘]-linear monotone erasure code for A. Proof. The proof is structured as follows. We first show that the solutions provided by the algorithm for each subproblem corresponds to the optimal solution given by Lemma 10. This is done by induction over the depth of the tree. We then conclude the proof by noticing that the algorithm combines subproblem solutions optimally. By Lemma 9, we know that if a solution to (𝑃) is optimal, then all induced subproblems must also be solved optimally. Therefore, if those subproblems further decompose, their subproblems must also be solved optimally. In other words, every optimal solution to (𝑃) induces optimal solutions of all 24
subproblems at every level of the decomposition. Therefore, we first show that Algorithm 2 optimally solves each subproblem of depth ℓ where 0 ≤ ℓ ≤ 𝐿 − 1. We will show this by induction over ℓ. Base cases: ℓ = 0: Consider a subtree 𝑇 ′ consisting of a single leaf node. Note that the minimization ′ problem of 𝑇 ′ is 𝜈𝑘𝑇 ′ = min 𝛾1 with constraint 𝛾1 ≥ 1. Thus, the optimal solution is 𝛾1 = 1. This solution 𝑇
𝛾1
corresponds to the solution given by Algorithm 2, as it returns 𝜈𝑇 ′ = 1 and 𝑘 𝑇 ′ = 1. Therefore, the algorithm solves every subtree problem of depth zero optimally. Case ℓ = 1: Assume a subtree 𝑇 ′ has depth one and its root is labeled 𝑡 with 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 (leaves). Since an optimal solution to 𝑇 ′ must induce optimal solutions of its subproblems by Lemma 9, the algorithm must correspond to the solution given by the following problem 𝑟 ∑︁ 𝜈𝑖 𝜈𝑇 ′ = min 𝛾𝑖 𝛾 ′ 𝑘𝑇 𝑘𝑖 𝑖=1 ∑︁ 𝛾𝑗 ≥ 1 for all 𝐽 ⊆ [𝑟] with |𝐽 | = 𝑡 (1) 𝑗∈𝐽
where 𝛾𝑖 ∈ R ≥0 and (𝜈𝑖 , 𝑘 𝑖 ) is given by the optimal solution for subproblem instantiated on 𝑇𝑖 . Note that 𝜈𝑖 1 𝑘𝑖 = 1. Therefore, if 𝑟 ≠ 𝑡, an optimal solution to problem (1) is given by 𝛾𝑖 = 𝑡 for all 𝑖 ∈ [𝑟], leading to (𝜈𝑇 ′ , 𝑘 𝑇 ′ ) = (𝑟, 𝑡). Otherwise, if 𝑟 = 𝑡, then an optimal solution is 𝛾𝑖 = 1 for some 𝑖 ∈ [𝑟] and 𝛾 𝑗 = 0 for all 𝑖 ≠ 𝑗 ∈ [𝑟]. Therefore, 𝜈𝑇 ′ = 1 and 𝑘 𝑇 ′ = 1. Note that in both cases this corresponds to the solution achieved by Algorithm 2. Indeed, since 𝜈𝑘𝑖𝑖 = 1, we have 𝑠 ∑︁ 1 𝑠 1= . 𝑠 − 𝑟 + 𝑡 𝑗=1 𝑠−𝑟 +𝑡 𝑠 only if 𝑟 = 𝑡. Thus, if 𝑟 ≠ 𝑡, we have 𝑠∗ = 𝑟, Therefore, for all 𝑠 ∈ {𝑟 − 𝑡 + 1, . . . , 𝑟 − 1}, 1 ≥ 𝑠−𝑟+𝑡 implying 𝜆 = 1 and 𝛼𝑖 = 1 for all 𝑖 ∈ [𝑟]. Then, the solution given by the algorithm is also 𝜈𝑇 ′ = 𝑟 and 𝑘 𝑇 ′ = 𝑡. If 𝑟 = 𝑡, then 𝑠∗ = 1 and hence 𝜆 = 1, 𝛼1 = 1 and 𝛼 𝑗 = 0 for all 𝑗 ∈ [𝑟] \ {1}. Thus, (𝜈𝑇 ′ , 𝑘 𝑇 ′ ) = (1, 1), which corresponds to the optimal solution. Induction hypothesis: For all depths Δ such that 2 ≤ Δ ≤ ℓ − 2, the following holds. For all subtrees 𝑇 ′ with depth Δ, labeled 𝑡 and with 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 (depth Δ − 1 subtrees), the algorithm optimally solves the following problem 𝑟 ∑︁ 𝜈𝑇 ′ 𝜈𝑖 = min 𝛾𝑖 𝛾 𝑘𝑇′ 𝑘 𝑖 𝑖=1 ∑︁ 𝛾𝑗 ≥ 1 for all 𝐽 ⊆ [𝑟] with |𝐽 | = 𝑡 𝑗∈𝐽
where 𝛾𝑖 ∈ R ≥0 and (𝜈𝑖 , 𝑘 𝑖 ) is given by the optimal solution for subproblem instantiated on subtree 𝑇𝑖 . Induction step: Consider a subtree 𝑇 ′ with depth Δ + 1, labeled 𝑡 with 𝑟 subtrees 𝑇1 , . . . , 𝑇𝑟 , all with depth Δ. By induction hypothesis, the algorithm delivers (𝜈𝑖 , 𝑘 𝑖 ) given by the optimal solution to each subproblem instantiated on subtree 𝑇𝑖 . Since an optimal solution to 𝑇 ′ induces optimal solutions to each subproblem 𝑃𝑖 , we have to consider the following problem: 𝑟 ∑︁ 𝜈𝑖 𝜈𝑇 ′ = min 𝛾𝑖 𝛾 𝑘𝑇′ 𝑘𝑖 𝑖=1 ∑︁ 𝛾𝑗 ≥ 1 for all 𝐽 ⊆ [𝑟] with |𝐽 | = 𝑡 𝑗∈𝐽
Í𝑠 ∗ ′ 𝜈𝑖 where 𝛾𝑖 ∈ R ≥0 . Moreover, by Lemma 10, we have 𝜈𝑘𝑇 ′ = 𝑖=1 (𝑠 ∗ −𝑟+𝑡 ) ·𝑘𝑖 . Therefore, it holds that 𝑇 Í𝑠 ∗ 𝑘 𝑇 ′ = (𝑠∗ − 𝑟 + 𝑡) · lcm({ 𝑘 𝑖 | 𝑖 ∈ 𝑆 }) and 𝜈𝑇 ′ = 𝑖=1 𝜈𝑖 · 𝜔𝑖 where 𝜔𝑖 = lcm( { 𝑘𝑘𝑖𝑖|𝑖 ∈𝑆 } ) . This corresponds exactly to the solution given by Algorithm 2, proving that the algorithm solves each induced subproblem optimally. As a last step, note that due to the same reasoning, the algorithm combines the subtree solutions of 𝑇 to an optimal solution, concluding the proof. □ 25
8
General Asynchronous Verifiable Information Dispersal
In this section, we propose the novel notion of general asynchronous verifiable information dispersal (GAVID) and implement it efficiently based on monotone erasure codes. GAVID generalizes the asynchronous verifiable information dispersal (AVID) problem, as introduced by Cachin and Tessaro [5], from threshold Byzantine quorum systems to general Byzantine quorum systems. Our implementation also generalizes the algorithms of Cachin and Tessaro. AVID and GAVID are protocols run by servers that communicate with each other by sending messages to each other over an asynchronous network. We assume that every two servers are linked by an asynchronous reliable point-to-point channel, in the sense that all messages are eventually delivered to the recipient and that the message originator is authenticated.
8.1
Byzantine quorum systems and reliable systems
To specify which servers may fail, we assume the presence of an adversary capable of corrupting servers. A fail-prone system F ⊆ 2 P specifies the sets of servers that can be jointly corrupted or be faulty during an execution (F is maximal, in the sense that none of its members is contained in another). Non-faulty servers are called honest. In particular, we consider a Byzantine quorum system [26] Q for a set of 𝑛 servers P and the corresponding canonical fail-prone system F = {P \ 𝑄 | 𝑄 ∈ Q}. Then, a quorum system Q for F on P is a set of subsets of P, called quorums, satisfying consistency, that the intersection of any two quorums contains at least one process that is not faulty, i.e., ∀𝐹 ∈ F , ∀𝑄 1 , 𝑄 2 ∈ Q : 𝑄 1 ∩ 𝑄 2 ⊈ 𝐹; and availability, namely that for any set of processes that may fail together, there exists a disjoint quorum, that is, ∀𝐹 ∈ F : ∃𝑄 ∈ Q : 𝐹 ∩ 𝑄 ≠ ∅. Given a Byzantine quorum system Q, a set 𝐾 ⊆ P that intersects every quorum is called a kernel of Q, that is, when ∀ 𝑄′ ∈ Q : 𝐾 ∩ 𝑄′ ≠ ∅ and 𝐾 is minimal among all such sets, i.e., ∀ 𝐾 ′ ⊊ 𝐾 : ∃ 𝑄 ′ ∈ Q : 𝑄 ′ ∩ 𝐾 ′ = ∅. The kernel system K of Q is defined as the set of all kernels of Q. It follows from the consistency property that for every quorum 𝑄 ∈ Q, there exists a kernel 𝐾 ∈ K such that 𝐾 ⊆ 𝑄: every quorum contains a kernel. Additionally, we introduce the notion of a reliable set, which will play a central role in our scheme. Definition 8. A set 𝑅 ⊆ P is said to be reliable for a fail-prone system F whenever one can remove an arbitrary faulty set from 𝑅 and the difference still contains a kernel, i.e., ∀𝐹 ∈ F , ∃𝐾 ∈ K : 𝐾 ⊆ 𝑅 \ 𝐹. In other words, a reliable set contains a kernel that is disjoint any faulty set in F . The collection of all reliable sets is called the reliable system of the fail-prone system. Note that each quorum is a reliable set, but not all reliable sets are quorums. To see this, just consider a Byzantine quorum system on 𝑛 servers for a fail-prone system that consists of all sets of 𝑓 servers for 𝑓 ≪ 𝑛/3, e.g., when 𝑓 = 1 and 𝑛 = 10.
26
8.2
Definition of general asynchronous dispersal
For extending protocols that involve erasure codes from threshold to general quorum systems, we first note that a quorum system, a kernel system, and a reliable system is each also an access structure in the sense of Definition 1. A GAVID scheme for a quorum system Q uses a suitable kernel system K as access structure for its monotone erasure code. As in the existing notion of AVID, a GAVID scheme for Q consists of two protocols, called Disperse and Retrieve, and relies on a monotone erasure code whose access structure is K, the kernel system of Q. If a server 𝑝ˆ wants to store a file 𝑓 , it starts protocol Disperse with input 𝑓 , and the other servers start the protocol with no input. Every honest server should terminate this protocol and output either stored or abort. We say that a server completes the dispersal if it terminates Disperse and outputs stored and that it aborts the dispersal if it terminates and outputs abort. To ensure storing consistent data, we require that either all honest servers complete the dispersal or no honest server completes the dispersal. This way, we enable any kernel (and consequently also every quorum) to reconstruct the file. If a server 𝑝˜ wants to retrieve a file, it starts Retrieve to obtain enough information from the servers to reconstruct the stored file. Server 𝑝˜ terminates this protocol when it outputs a file or ⊥. More precisely, we define a GAVID scheme for Q as follows. Definition 9. A general asynchronous verifiable information dispersal (GAVID) scheme for a Byzantine quorum system Q and a fail-prone system F consists of a dispersal protocol and a retrieval protocol. For any adversary that corrupts a set 𝐹 ∈ F of servers and for any server 𝑝ˆ that starts the dispersal, the following conditions hold: Termination. If 𝑝ˆ is honest, then all honest servers eventually complete the dispersal. Agreement. If some honest server completes the dispersal, then all honest servers eventually complete the dispersal. Availability. If a kernel of honest servers completes the dispersal, and an honest server starts the retrieval protocol, then it eventually reconstructs some file 𝑓 ′ . Correctness. If a kernel of honest servers completes the dispersal, then there exists a fixed value 𝑓0 such that: 1. If 𝑝ˆ is honest and has dispersed a file 𝑓 , then 𝑓0 = 𝑓 . 2. If an honest server reconstructs 𝑓 ′ , then 𝑓0 = 𝑓 ′ .
8.3
Protocol GAVID
In the following, we present Protocol GAVID that implements GAVID. We assume a collision-resistant hash function 𝐻 and denote the encoding and decoding functions of the monotone erasure code for K by Encode and Decode, respectively. Protocol GAVID consists of two sub-protocols, called Disperse and Retrieve. Algorithm Disperse is instantiated by a server 𝑝ˆ wanting to disperse a file 𝑓 . The first step is to encode 𝑓 using Encode, obtaining fragments (𝑔1 , . . . , 𝑔𝑛 ). Then, 𝑝ˆ builds the verification vector 𝐷 = (𝐻 (𝑔1 ), . . . , 𝐻 (𝑔𝑛 )). At this point, 𝑝ˆ sends 𝑔𝑖 along with 𝐷 to 𝑝 𝑖 , for all 𝑖 ∈ [𝑛]. Each node checks that the received fragment 𝑔𝑖 is valid with respect to 𝐷, i.e., 𝐻 (𝑔𝑖 ) = 𝐷 𝑖 , and, if so, it echoes 𝑔𝑖 . Once a node 𝑝 𝑖 receives valid echo messages from a quorum, it decodes them using Decode and encodes the result again to check if it is valid with respect to 𝐷. In that case, it sends a ready message containing a valid fragment 𝑔¯ 𝑖 to each 𝑝 𝑗 . Otherwise, it means that the sender 𝑝ˆ acted maliciously, so the node aborts. If a node does not receive valid echo messages from a quorum, but receives valid ready messages from a kernel, it can recover its fragment by decoding the received fragments and encoding again, as
27
above. Finally, when a node receives valid ready messages from a reliable set 𝑅[𝐷], it stores 𝐷 and its valid fragment. When a server 𝑝˜ wants to retrieve a file, it runs Retrieve. Here, 𝑝˜ asks the servers to send their stored information, namely, the vector 𝐷 and their fragments. Once 𝑝˜ has received enough fragments that are valid with respect to the same 𝐷, it decodes them to recover the file. The details of Disperse and Retrieve can be found in Algorithm 3 and Algorithm 4, respectively.
8.4
Analysis of Protocol GAVID
In this section, we prove that, given an [𝑚, 𝑘]−linear monotone erasure code for a quorum system Q, GAVID provides a general asynchronous verifiable information dispersal scheme for Q. We show this statement in Theorem 13, building on the following lemma. Lemma 12. In the dispersal protocol of GAVID, if two honest servers 𝑝 𝑖 and 𝑝 𝑗 send ( ready, 𝐷 𝑖 ) and ( ready, 𝐷 𝑗 ), respectively, then 𝐷 𝑖 = 𝐷 𝑗 . Proof. Assume by contradiction that 𝐷 𝑖 ≠ 𝐷 𝑗 . We know that 𝑝 𝑖 and 𝑝 𝑗 send ready messages once they have received either echo messages from a quorum, or ready messages from a kernel. Then, we can have the following three cases. Case 1: Assume both 𝑝 𝑖 and 𝑝 𝑗 receive echo messages from a quorum. Then since any two quorums intersect, at least one honest server 𝑝 𝑟 has sent two different echo messages to 𝑝 𝑖 and 𝑝 𝑗 , which gives a contradiction. Case 2: Assume one of 𝑝 𝑖 and 𝑝 𝑗 has received echo messages from a quorum and the other has received ready messages from a kernel. W.l.o.g, assume 𝑝 𝑖 has received ( echo, 𝐷 𝑖 ) messages from a quorum and 𝑝 𝑗 has received ( ready, 𝐷 𝑗 ) messages from a kernel. Then one honest server must have sent ( ready, 𝐷 𝑗 ) from a quorum. But then it reduces to case 1. Case 3: Assume both 𝑝 𝑖 and 𝑝 𝑗 have received ( ready, 𝐷 𝑖 ), resp. ( ready, 𝐷 𝑗 ) messages from a kernel. Then at least one honest server 𝑝 𝑟 must have sent a ( ready, 𝐷 𝑖 ), and at least one honest server 𝑝 𝑙 must have sent ( ready, 𝐷 𝑗 ). W.l.o.g., we can assume that both 𝑝 𝑟 and 𝑝 𝑙 have received ( echo, 𝐷 𝑖 ), resp. ( echo, 𝐷 𝑗 ) messages from a quorum. But then it reduces again to case 1. □ Theorem 13. Given an [𝑚, 𝑘]−linear monotone erasure code for a quorum system Q, GAVID is a general asynchronous verifiable information dispersal scheme for Q. Proof. Termination. If 𝑝ˆ is honest and starts Disperse with 𝐷 then all honest servers will receive ( send, 𝐷) together with its fragments. Therefore, each honest server will send ( echo, 𝐷) and receive echo messages from a quorum. Thus, each honest server will send ( ready, 𝐷). To see this, assume there is an honest server 𝑝 𝑗 that aborts and an honest server 𝑝 𝑖 that sends ( ready, 𝐷). Therefore, there must exist a vector 𝑔 such that 𝐻 (𝑔ℓ ) = 𝐷 ℓ for all ℓ ∈ [𝑛]. However, since 𝑝 𝑗 aborts, by Lemma 12 there exists (ℓ, 𝑔ℓ′ ) ∈ 𝐴 𝑗 [𝐷] such that 𝐻 (𝑔ℓ′ ) = 𝐷 ℓ and 𝑔ℓ′ ≠ 𝑔ℓ . This means that the adversary has found a collision for 𝐻, which is impossible. Therefore, at the end each honest server will receive valid fragments with the same 𝐷 from a reliable set 𝑅[𝐷]. Thus, each honest server will terminate with 𝐷. Agreement. Assume one honest server has completed the dispersal protocol and has stored the verification vector 𝐷. This means that it has received valid fragments with the same 𝐷 from a reliable set 𝑅[𝐷]. Therefore, some kernel 𝐾 of honest servers has sent valid ready messages with 𝐷, which means that each honest server receives valid ready messages with 𝐷 from 𝐾. This implies that all honest servers send a valid ready message with 𝐷. This can be seen as follows. Assume a server 𝑝 𝑖 completes the dispersal with 𝐷 and there is a server 𝑝 𝑗 that aborts. This means that there exists a value 𝑔 such that 𝐻 (𝑔ℓ ) = 𝐷 ℓ for all ℓ ∈ [𝑛]. However, since 𝑝 𝑗 aborts and by Lemma 12, there exists (ℓ, 𝑔ℓ′ ) ∈ 𝐴 𝑗 [𝐷] such that 𝐻 (𝑔ℓ′ ) = 𝐷 ℓ , but 𝑔ℓ′ ≠ 𝑔ℓ , i.e., the adversary has found a collision for 𝐻. Therefore, in the end, each honest server receives valid ready messages from a reliable set 𝑅 ′ [𝐷]. We prove this fact by contradiction. Suppose that for all 𝑅 ′ [𝐷] ⊆ P there exists 𝐹 ∈ F such that 𝐾 ∈ K : 𝐾 ⊆ 𝑅 ′ [𝐷] \ 𝐹. From the availability property of Byzantine quorum systems, it follows that there is a quorum 𝑄 𝐹 such
28
Algorithm 3 Protocol Disperse (server 𝑝 𝑖 ) 1: initialization 2: 𝐸 ← []: hash map from {0, 1}∗ to sets of nodes 3: // 𝐸 [𝐷] is the set of nodes that have sent valid echo messages for 𝐷 4: 𝑅 ← []: hash map from {0, 1}∗ to sets of nodes 5: // 𝑅[𝐷] is the set of nodes that have sent valid ready messages for 𝐷 6: 𝐴 ← []: hash map from {0, 1}∗ to sets of node-fragment pairs 7: // 𝐴[𝐷] contains nodes and valid fragments for 𝐷 8: stored ← false 9: 10: upon starting dispersal with input a file 𝑓 do // only server 𝑝ˆ 11: [𝑔1 , . . . , 𝑔𝑛 ] ← Encode( 𝑓 ) 12: 𝐷 ← [𝐻 (𝑔1 ), . . . , 𝐻 (𝑔𝑛 )] 13: for 𝑗 ∈ [𝑛] do 14: send message ( send, 𝐷, 𝑔 𝑗 ) to 𝑝 𝑗 15: 16: upon receiving message ( send, 𝐷, 𝑔𝑖 ) from 𝑝ˆ for the first time do 17: if 𝐻 (𝑔𝑖 ) = 𝐷 𝑖 then 18: for 𝑗 ∈ [𝑛] do 19: send message ( echo, 𝐷, 𝑔𝑖 ) to 𝑝 𝑗 20: 21: upon receiving message ( echo, 𝐷, 𝑔 𝑗 ) from 𝑝 𝑗 for the first time do 22: if 𝐻 (𝑔 𝑗 ) = 𝐷 𝑗 then 23: 𝐴[𝐷] ← 𝐴[𝐷] ∪ {( 𝑗, 𝑔 𝑗 )} 24: 𝐸 [𝐷] ← 𝐸 [𝐷] ∪ { 𝑗 } 25: if 𝐸 [𝐷] ∈ Q ∧ 𝑅[𝐷] ∉ K then // ready message not yet sent 26: 𝑓¯ ← Decode((𝑔1 , . . . , 𝑔𝑛 )), where (𝑙, 𝑔𝑙 ) ∈ 𝐴[𝐷] if 𝑙 ∈ 𝐸 [𝐷] ∪ 𝑅[𝐷] and 𝑔𝑙 = ⊥ otherw. 27: [ 𝑔¯ 1 , . . . , 𝑔¯ 𝑛 ] ← Encode( 𝑓¯) 28: if 𝐻 ( 𝑔¯𝑙 ) = 𝐷 𝑙 for all 𝑙 ∈ [𝑛] then 29: for 𝑗 ∈ [𝑛] do 30: send message ( ready, 𝐷, 𝑔¯ 𝑖 ) to 𝑝 𝑗 31: else 32: output abort 33: 34: upon receiving message ( ready, 𝐷, 𝑔 𝑗 ) from 𝑝 𝑗 for the first time do 35: if 𝐻 (𝑔 𝑗 ) = 𝐷 𝑗 then 36: 𝐴[𝐷] ← 𝐴[𝐷] ∪ {( 𝑗, 𝑔 𝑗 )} 37: 𝑅[𝐷] ← 𝑅[𝐷] ∪ { 𝑗 } 38: if 𝐸 [𝐷] ∉ Q ∧ 𝑅[𝐷] ∈ K then // ready message not yet sent 39: 𝑓¯ ← Decode((𝑔1 , . . . , 𝑔𝑛 )), where (𝑙, 𝑔𝑙 ) ∈ 𝐴[𝐷] if 𝑙 ∈ 𝐸 [𝐷] ∪ 𝑅[𝐷] and 𝑔𝑙 = ⊥ otherw. 40: [ 𝑔¯ 1 , . . . , 𝑔¯ 𝑛 ] ← Encode( 𝑓¯) 41: if 𝐻 ( 𝑔¯𝑙 ) = 𝐷 𝑙 for all 𝑙 ∈ [𝑛] then 42: for 𝑗 ∈ [𝑛] do 43: send message ( ready, 𝐷, 𝑔¯ 𝑖 ) to 𝑝 𝑗 44: else 45: output abort 46: else if ¬stored ∧ 𝑅[𝐷] ∈ R then 47: store (𝐷, 𝑔𝑖 ) 48: stored ← true 49: output stored
29
Algorithm 4 Protocol Retrieve (server 𝑝 𝑖 ) 1: initialization 2: (𝐷, 𝑔𝑖 ) ← values retrieved from Disperse 3: 𝑅 ← []: hash map from {0, 1}∗ to sets of nodes 4: // 𝑅[𝐷] is the set of nodes that have sent valid fragment messages for 𝐷 5: 𝐴 ← []: hash map from {0, 1}∗ to sets of node-fragment pairs 6: // 𝐴[𝐷] contains nodes and valid fragments for 𝐷 7: 𝑓¯ ← ⊥ // the retrieved file 8: 9: upon starting retrieval do // only server 𝑝˜ 10: for 𝑗 ∈ [𝑛] do 11: send message ( retrieve) to 𝑝 𝑗 12: 13: upon receiving message ( retrieve) from 𝑝 𝑗 do 14: if 𝐷 ≠ ⊥ then 15: send message ( fragment, 𝐷, 𝑔𝑖 ) to 𝑝 𝑗 16: 17: upon receiving message ( fragment, 𝐷, 𝑔 𝑗 ) from 𝑝 𝑗 for the first time and 𝑓¯ = ⊥ do 18: if 𝐻 (𝑔 𝑗 ) = 𝐷 𝑗 do 19: 𝐴[𝐷] ← 𝐴[𝐷] ∪ {( 𝑗, 𝑔 𝑗 )} 20: 𝑅[𝐷] ← 𝑅[𝐷] ∪ { 𝑗 } 21: if 𝑅[𝐷] ∈ K then 22: 𝑓¯ ← Decode((𝑔1 , . . . , 𝑔𝑛 )), where (𝑙, 𝑔𝑙 ) ∈ 𝐴[𝐷] for 𝑙 ∈ [𝑛] and 𝑔𝑙 = ⊥ otherwise 23: output 𝑓¯
that 𝑄 𝐹 ∩ 𝐹 = ∅. Since every quorum contains a kernel, there exists 𝐾 𝐹 ∈ K such that 𝐾 𝐹 ⊆ 𝑄 𝐹 . Thus, Ð 𝐾 𝐹 ∩ 𝐹 = ∅. We can therefore set 𝑅 ′ [𝐷] = 𝐹 ∈ F 𝐾 𝐹 , obtaining a contradiction. Availability. Since a kernel 𝐾 of honest servers has accepted, servers in 𝐾 also hold the same verification vector 𝐷, and thus any honest server is always able to reconstruct some value. Correctness. Let 𝑅[𝐷] ⊆ P be a kernel of honest servers that have completed the dispersal of 𝑓 . Define 𝑓0 = Decode(𝑔 𝑅[𝐷 ] ). For the first point, we have to show that 𝑓0 corresponds to the file 𝑓 a honest server has started to disperse. Assume an honest server 𝑝ˆ has shared a file 𝑓 and 𝑓 ≠ 𝑓0 . Then every echo message from an honest 𝑝 𝑖 to an honest 𝑝 𝑗 contains 𝐷 and 𝑔𝑖 as computed by 𝑝. ˆ If the servers in 𝑅[𝐷] computed their 𝑔 𝑗 from these echo messages, then 𝑔 𝑗 = 𝑔 𝑗 , i.e., their fragments correspond to the one sent by 𝑝. ˆ However, since 𝑓 ≠ 𝑓0 , there must be an honest server 𝑝 𝑗 with 𝑔 𝑗 ≠ 𝑔 𝑗 . Thus, it must have received a value 𝑔ℓ′ ≠ 𝑔ℓ from a corrupted server 𝑝 ℓ (either in an echo or ready message), which it accepted. Since 𝐻 (𝑔ℓ ) = 𝐻 (𝑔ℓ′ ) holds, the adversary has found a collision for 𝐻, which is impossible. For the second point, we have to show that if an honest server reconstructs a value 𝑓 ′ , then this value corresponds to 𝑓0 . For this, assume an honest server reconstructs a value 𝑓 ′ ≠ 𝑓0 using some kernel 𝑅 ′ [𝐷] ≠ 𝑅[𝐷]. Since 𝑅 ′ [𝐷] is a kernel, the value of 𝐷 the server chooses must be the unique one held by the correct servers by Lemma 12. On the other hand, if 𝑓 ′ ≠ 𝑓0 , there must be some value 𝑔ℓ′ received by some server 𝑝 ℓ , with ℓ ∈ 𝑅 ′ [𝐷] \ 𝑅[𝐷], such that 𝑔ℓ′ ≠ 𝑔ℓ , but 𝐻 (𝑔ℓ′ ) = 𝐷 ℓ . On the other hand, in order for a server 𝑝 𝑗 ∈ 𝑅[𝐷] to accept, it must hold that 𝐻 (𝑔ℓ ) = 𝐷 ℓ . Thus, the adversary must have found a collision for 𝐻 either in the dispersal protocol or in the retrieval protocol. □ Complexity. We use the following complexity measures to analyze GAVID: • message complexity: number of messages associated to an instance of the protocol; • communication complexity: bit length of all messages associated to an instance of the protocol; • storage complexity: overall bit length of the information stored in the memory of the honest servers after they have completed the dispersal protocol. 30
Let us denote by |𝐻| the bit-size of the range of the hash function. The message complexity of Disperse is O (𝑛2 ). Regarding the communication complexity, we know that the bit length of each message is 𝑚 𝑖 · ⌈𝑙𝑜𝑔2 (𝑞)⌉ + 𝑛 · |𝐻|, for some 𝑖 ∈ [𝑛]. Since each party sends the same message 𝑛 times, we have that the communication complexity is ∑︁ O (𝑛 · 𝑚 𝑖 · ⌈𝑙𝑜𝑔2 (𝑞)⌉ + 𝑛2 |𝐻|) = 𝑖 ∈ [𝑛]
O 𝑛 · 𝑚 · ⌈𝑙𝑜𝑔2 (𝑞)⌉ + 𝑛3 |𝐻|) = |𝑓| + 𝑛3 · |𝐻|) = 𝑘 O (𝑛(1 + 𝛽) · | 𝑓 | + 𝑛3 · |𝐻|)
O (𝑛 · 𝑚 ·
where 𝑚 = 𝑘 (1 + 𝛽) and | 𝑓 | = O (𝑘 · ⌈𝑙𝑜𝑔2 (𝑞)⌉). The storage complexity is given by the size of all stored fragments, which is 𝑚 · ⌈𝑙𝑜𝑔2 (𝑞)⌉, together with the size of vector 𝐷 taken 𝑛 times, i.e., 𝑛2 · |𝐻|. The resulting complexity is O (𝑚 · ⌈𝑙𝑜𝑔2 (𝑞)⌉ + 𝑛2 · |𝐻|) = O ((1 + 𝛽) · | 𝑓 | + 𝑛2 · |𝐻|). The message complexity of Retrieve is O (𝑛). For the same reasoning as above, the communication complexity is O ((1 + 𝛽) · | 𝑓 | + 𝑛2 · |𝐻|). GAVID-H. The storage and communication complexities of the protocol can be improved using a Merkle tree instead of the vector 𝐷, following the approach of Cachin and Tessaro in [5]. In particular, the idea is to build the Merkle tree whose leaves are labeled with the hashes of the fragments 𝐻 (𝑔1 ), . . . , 𝐻 (𝑔𝑛 ). Let 𝑙 = ⌈log(𝑛)⌉, and denote by 𝑣 0 , . . . , 𝑣 𝑙 the unique path from the root 𝑣 𝑟 to leaf 𝑖. Assign 𝑙𝑎𝑏𝑒𝑙 (𝑣 𝑖 ) = 𝐻 (𝑙𝑎𝑏𝑒𝑙 (𝑣 ′ ), 𝑙𝑎𝑏𝑒𝑙 (𝑣 ′′ )) to each vertex 𝑣 𝑖 with children 𝑣 ′ and 𝑣 ′′ . Moreover, let 𝑤 𝑗 be the unique sibling of 𝑣 𝑗 for all 𝑗 ∈ [𝑙]. Then, for each 𝑖 ∈ [𝑛], the fingerprint for 𝑔𝑖 is 𝐹𝑃(𝑖) = [𝑙𝑎𝑏𝑒𝑙 (𝑤 1 ), . . . , 𝑙𝑎𝑏𝑒𝑙 (𝑤 𝑙 )]. GAVID can then be modified as follows. Replace 𝐷 with the root hash 𝐻𝑟 in all messages, and let server 𝑝 𝑖 store (𝐹𝑃(𝑖), 𝐻𝑟 ) instead of 𝐷. Moreover, the check 𝐻 (𝑔𝑖 ) = 𝐷 𝑖 is substituted with the following test. Let verify (𝑖, 𝑔𝑖 , 𝐹𝑃, 𝐻𝑟 ) be the function that computes the iterated hash on 𝐻 (𝑔𝑖 ) and 𝐹𝑃, with 𝐹𝑃 a vector of length 𝑙, and then compares the result with 𝐻𝑟 . If they are the same, the function returns 1, otherwise it returns 0. We call the resulting protocol GAVID-H. We now show that GAVID-H is more efficient GAVID. First, notice that the bit length of each message now is 𝑚 𝑖 · ⌈𝑙𝑜𝑔2 (𝑞)⌉ + ( ⌈𝑙𝑜𝑔2 (𝑛)⌉ + 1) · |𝐻|. For the same reasoning as above, this leads to the following communication complexities: • O (𝑛(1 + 𝛽) · | 𝑓 | + 𝑛2 ( ⌈𝑙𝑜𝑔2 (𝑛)⌉ + 1) · |𝐻|) bits in Disperse; • O ((1 + 𝛽) · | 𝑓 | + 𝑛 · ( ⌈𝑙𝑜𝑔2 (𝑛)⌉ + 1) · |𝐻|)) bits in Retrieve. Moreover, the storage complexity of Disperse is O ((1 + 𝛽) · | 𝑓 | + 𝑛 · ( ⌈𝑙𝑜𝑔2 (𝑛)⌉ + 1) · |𝐻|)).
8.5
Communication-efficient general Byzantine reliable broadcast
Byzantine reliable broadcast is a fundamental asynchronous communication primitive, which exists as a building block also in many consensus protocols. It ensures that a sender can transmit a message to all servers such that if one correct server delivers some message, then all correct servers deliver a message. Moreover, they all deliver the same message, and if the sender is correct, then this is the message that the sender has broadcast. Bracha’s [4] celebrated protocol implements this notion in an asynchronous network with an initial message from the sender to all servers followed by two rounds of all-to-all communication. As already observed by Cachin and Tessaro [5], their notion of AVID and the corresponding protocol are closely related to the notion of Byzantine reliable broadcast and Bracha’s protocol. Hence, communication-efficient reliable broadcast for a Byzantine quorum system Q can be implemented with a protocol that is closely related to the dispersal algorithm of Protocol GAVID for Q. Relating to the 31
description of GAVID in Algorithm 3, the broadcast protocol involves the same send message from the sender to all servers, and it runs almost the same two rounds of exchanging echo and ready messages. The only difference occurs in the last step: once a server has received valid fragments from a reliable set 𝑅[𝐷], it immediately decodes the valid fragments and outputs the resulting message. This method extends to related communication-efficient broadcast protocols that use erasure codes [33, 24].
9
Related work
We first review the most commonly used erasure codes. We then discuss storage methods that leverage different properties of erasure codes and present data availability sampling, another key application of erasure codes. Additionally, we mention broadcast and consensus protocols based on erasure coding techniques. Finally, we discuss the possibility of building monotone erasure codes for access structures expressed as monotone span programs (MSPs). Erasure codes. One of the most important classes of erasure codes is given by maximum distance separable (MDS) codes, as they provide an optimal trade-off between fault tolerance and storage overhead. The most widely used MDS codes are Reed–Solomon (RS) codes [31, 30], due to their simplicity and efficiency. Whenever a node fails and needs to recover its fragment, traditional MDS codes repair it by downloading the whole file and encoding it again. To address this issue, Dimakis et al. [13] introduced regenerating codes and characterized the fundamental tradeoff between storage and repair bandwidth. Among them, minimum-storage regenerating (MSR) codes minimize repair bandwidth while maintaining the minimum storage overhead. In particular, they achieve the same storage optimality as Reed–Solomon codes and are therefore MDS. Distributed storage. Erasure codes are typically employed to efficiently store large amount of information in a distributed manner. Redundant Array of Independent Disks (RAID) [28] is an erasure coding technique involving multiple disk arrays, organized in different ways. The most widely used variants are RAID-5 and RAID-6, which give single-disk and double-disk fault tolerance, respectively. Filecoin [29] is a decentralized storage network (DSN) scheme that offers a data storage and retrieval service through a decentralized network of independent storage providers. A flaw of Filecoin is given by slow reads in the absence of a node storing a hot copy of the file. To address this issue, Williams et al. propose Arweave [35]. Their approach, however, leads to replication levels comparable to classic state machine replication, implying a very high overhead. A much more efficient decentralized storage system is Storj [23], which achieves an overhead of 1.75. Nevertheless, a drawback of Storj is its inefficient data recovery process, which requires reconstructing the entire file in order to recover lost parts. A more flexible scheme is Walrus [12], which provides an efficient reconstruction mechanism while ensuring Byzantine Fault Tolerance. However, Walrus is less efficient in terms of overhead, which is 3.5. The state-of-the-art protocol for distributed storage is Shelby [18], which achieves an overhead of less than 1, lower than that of all other distributed storage systems present in the literature. Shelby employs Clay codes [34], a particular kind of MSR codes, to provide hot storage, i.e, an infrastructure that can support low-latency, high-throughput reads. All the distributed storage systems presented here assume a 𝑡-out-of-𝑛 access structure, which makes them less flexible than the scheme proposed in this paper. Data availability sampling. Another relevant application of erasure codes is data availability sampling (DAS). In the context of blockchains, DAS allows light clients to verify that the data of a block has been fully published without downloading the entire block. The idea is that the block is first encoded using erasure codes (typically Reed–Solomon codes). The encoded data is then committed using Merkle trees. Light clients randomly sample fragments and verify them against the commitment. If enough randomly selected fragments are available, the client can conclude with high probability that the entire block is available. Blockchains such as Celestia [7] are built around DAS as a core component. Moreover, a prominent data availability layer is EigenDA [14], which is designed for Ethereum rollups. Communication-efficient broadcast and consensus. Many recent Byzantine-tolerant consensus 32
protocols disseminate data with erasure codes [36]. Indeed, data dissemination based on erasure coding can be leveraged to improve the efficiency of multiple protocols. In particular, such techniques can be used to realize fast validated agreement [9, 15]. Moreover, erasure coding techniques can be leveraged to build efficient broadcast protocols. For example, Shoup [33] builds on AVID to reduce the communication complexity of the Simplex atomic broadcast protocol [8]. Erasure coding using Monotone Span Programs. For threshold access structures, erasure coding schemes can be constructed directly from polynomials. The idea is to embed the information into the coefficients of a degree-𝑡 polynomial. Any set of at least 𝑡 + 1 nodes can later reconstruct the polynomial, thus recovering the information. At the same time, it is known that monotone span programs (MSPs) are a generalization of polynomials [21] – as a matter of fact, access structures can be represented by MSPs [2, 21], and secret-sharing schemes have been described using MSPs [11, 17, 1]. Although it is also possible to build erasure codes from MSPs, doing so would not be efficient. For this reason, in this paper we take a different approach and do not rely on MSPs.
10
Conclusion
In this work, we have introduced monotone erasure codes that respect arbitrary trust assumptions characterized by a monotone access structure. They extend existing erasure codes, which rely on threshold failure models, to applications with more general assumptions, where some nodes are more likely to fail than others or may be more trustworthy. Practical systems that rely on such assumptions can be found in the blockchain and cryptocurrency space. We have shown how to efficiently build a linear monotone erasure code for any given access structure A, without minimizing the overhead. To generate a linear monotone erasure code that is optimal, we have presented an alternative method that uses a threshold erasure code as a building block. An optimal code of this kind results from solving a linear programming problem derived from the access structure. The procedure is efficient if A has a compact (e.g., polynomial-size) description in the number of nodes. We have also provided an efficient construction of monotone erasure codes for partitioned access structures. Monotone erasure codes have also direct applications to Byzantine-tolerant communication protocols: We have extended AVID so that it works not only in scenarios where any 𝑓 out of 𝑛 nodes may fail, but also in the general case of Byzantine quorum systems. The resulting GAVID primitive has led us also to obtain a communication-efficient Byzantine reliable broadcast protocol for an arbitrary Byzantine quorum system. This work points to future work in multiple directions. Perhaps the most interesting open question concerns the efficient construction of an optimal monotone erasure code for an arbitrary monotone access structure, which is expressed as MBF or monotone span program, but that has exponentially many access sets. Furthermore, constructing dynamic monotone erasure codes that can adapt to access structures that evolve over time would be valuable in practical applications. Finally, it would be interesting to determine to which extent other methods from coding theory, such as rateless codes or low-density parity-check codes, can be employed in the setting of monotone erasure codes.
Acknowledgments V.B. and A.C. have been supported by a grant from the Stellar Development Foundation to the University of Bern.
33
References [1]
O. Alpos and C. Cachin. “Do Not Trust in Numbers: Practical Distributed Cryptography with General Trust”. In: Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Jersey City, NJ, USA, October 2-4, 2023, Proceedings. Ed. by S. Dolev and B. Schieber. Lecture Notes in Computer Science. Springer, 2023, pp. 536–551. doi: 10.1007/ 978-3-031-44274-2\_40.
[2]
A. Beimel. “Secure Schemes for Secret Sharing and Key Distribution”. PhD thesis. Technion, 1996. url: https://www.cs.bgu.ac.il/˜beimel/Papers/thesis.pdf.
[3]
J. C. Benaloh and J. Leichter. “Generalized Secret Sharing and Monotone Functions”. In: Advances in Cryptology - CRYPTO ’88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings. Ed. by S. Goldwasser. Lecture Notes in Computer Science. Springer, 1988, pp. 27–35. doi: 10.1007/0-387-34799-2\_3.
[4]
G. Bracha. “Asynchronous Byzantine Agreement Protocols”. In: Inf. Comput. 75.2 (1987), pp. 130– 143. doi: 10.1016/0890-5401(87)90054-X.
[5]
C. Cachin and S. Tessaro. “Asynchronous Veri.able Information Dispersal”. In: 24th IEEE Symposium on Reliable Distributed Systems (SRDS 2005),26-28 October 2005, Orlando, FL, USA. IEEE Computer Society, 2005, pp. 191–202. doi: 10.1109/RELDIS.2005.9.
[6]
J. Camenisch, M. Drijvers, T. Hanke, Y. Pignolet, V. Shoup, and D. Williams. “Internet Computer Consensus”. In: PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022. Ed. by A. Milani and P. Woelfel. ACM, 2022, pp. 81–91. doi: 10.1145/ 3519270.3538430.
[7]
Celestia Labs. Celestia – Fibre Optic Performance for Millisecond Markets. https://celestia. org. 2026.
[8]
B. Y. Chan and R. Pass. “Simplex Consensus: A Simple and Fast Consensus Protocol”. In: Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 December 2, 2023, Proceedings, Part IV. Ed. by G. N. Rothblum and H. Wee. Lecture Notes in Computer Science. Springer, 2023, pp. 452–479. doi: 10.1007/978-3-031-48624-1\_17.
[9]
P. Civit, M. A. Dzulfikar, S. Gilbert, R. Guerraoui, J. Komatovic, M. Vidigueira, and I. Zablotchi. “Efficient Signature-Free Validated Agreement”. In: 38th International Symposium on Distributed Computing, DISC 2024, Madrid, Spain, October 28 - November 1, 2024. Ed. by D. Alistarh. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 14:1–14:23. doi: 10.4230/LIPICS. DISC.2024.14.
[10]
D. Cohen, D. Schwartz, and A. Britto. XRP Ledger Documentation: Consensus Structure. Available online, https : / / xrpl . org / docs / concepts / consensus - protocol / consensus structure. 2025.
[11]
R. Cramer, I. Damgård, and U. M. Maurer. “General Secure Multi-party Computation from any Linear Secret-Sharing Scheme”. In: Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding. Ed. by B. Preneel. Lecture Notes in Computer Science. Springer, 2000, pp. 316–334. doi: 10.1007/3-540-45539-6\_22.
[12]
G. Danezis, G. Giuliari, E. Kokoris-Kogias, M. Legner, J. Smith, A. Sonnino, and K. Wüst. “Walrus: An Efficient Decentralized Storage Network”. In: CoRR abs/2505.05370 (2025). arXiv: 2505.05370. doi: 10.48550/ARXIV.2505.05370.
[13]
A. G. Dimakis, B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran. “Network coding for distributed storage systems”. In: IEEE Trans. Inf. Theory 56.9 (2010), pp. 4539–4551. doi: 10.1109/TIT.2010.2054295.
[14]
Eigen Labs. EigenDA – State of the Art Data Availability. https://www.eigenda.xyz. 2026. 34
[15]
H. Feng, Z. Lu, T. Mai, and Q. Tang. “Faster Hash-based Multi-valued Validated Asynchronous Byzantine Agreement”. In: 55th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2025, Naples, Italy, June 23-26, 2025. IEEE, 2025, pp. 303–316. doi: 10.1109/DSN64029.2025.00040.
[16]
C. Fragouli, J. L. Boudec, and J. Widmer. “Network coding: an instant primer”. In: Comput. Commun. Rev. 36.1 (2006), pp. 63–68. doi: 10.1145/1111322.1111337.
[17]
R. Gennaro. “Theory and practice of verifiable secret sharing”. PhD thesis. Massachusetts Institute of Technology, Cambridge (MA), USA, 1996. url: https://hdl.handle.net/1721.1/11014.
[18]
G. Goren, A. Hariri, T. D. R. Hartley, R. Kappiyoor, A. Spiegelman, and D. Zmick. “Shelby: Decentralized Storage Designed to Serve”. In: CoRR abs/2506.19233 (2025). arXiv: 2506.19233. doi: 10.48550/ARXIV.2506.19233.
[19]
M. Hall-Andersen, M. Simkin, and B. Wagner. “Foundations of Data Availability Sampling”. In: IACR Commun. Cryptol. 1.4 (2024), p. 34. doi: 10.62056/A09QUDHDJ.
[20]
M. Hirt and U. M. Maurer. “Player Simulation and General Adversary Structures in Perfect Multiparty Computation”. In: J. Cryptol. 13.1 (2000), pp. 31–60. doi: 10.1007/S001459910003.
[21]
M. Karchmer and A. Wigderson. “On Span Programs”. In: Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993. IEEE Computer Society, 1993, pp. 102–111. doi: 10.1109/SCT.1993.336536.
[22]
Q. Kniep, J. Sliwinski, and R. Wattenhofer. Solana Alpenglow Consensus. Whitepaper, available online, https://www.anza.xyz/blog/alpenglow-a-new-consensus-for-solana. 2025.
[23]
I. S. Labs. Storj: A decentralized cloud storage network framework. [Online]. 2018.
[24]
T. Locher and V. Shoup. “MiniCast: Minimizing the Communication Complexity of Reliable Broadcast”. In: Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part V. Ed. by S. Fehr and P. Fouque. Lecture Notes in Computer Science. Springer, 2025, pp. 96–115. doi: 10.1007/978-3-031-91092-0\_4.
[25]
M. Lokhava, G. Losa, D. Mazières, G. Hoare, N. Barry, E. Gafni, J. Jove, R. Malinowsky, and J. McCaleb. “Fast and secure global payments with Stellar”. In: Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP 2019, Huntsville, ON, Canada, October 2730, 2019. Ed. by T. Brecht and C. Williamson. ACM, 2019, pp. 80–96. doi: 10.1145/3341301. 3359636.
[26]
D. Malkhi and M. K. Reiter. “Byzantine Quorum Systems”. In: Distributed Comput. 11.4 (1998), pp. 203–213. doi: 10.1007/S004460050050.
[27]
V. Nikov and S. Nikova. New Monotone Span Programs from Old. Cryptology ePrint Archive, Paper 2004/282. 2004. url: https://eprint.iacr.org/2004/282.
[28]
D. A. Patterson, G. A. Gibson, and R. H. Katz. “A Case for Redundant Arrays of Inexpensive Disks (RAID)”. In: Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 1-3, 1988. Ed. by H. Boral and P. Larson. ACM Press, 1988, pp. 109–116. doi: 10.1145/50202.50214.
[29]
Y. Psaras and D. Dias. “The InterPlanetary File System and the Filecoin Network”. In: 50th Annual IEEE-IFIP International Conference on Dependable Systems and Networks, DSN 2020, Valencia, Spain, June 29 - July 2, 2020 - Supplemental Volume. IEEE, 2020, p. 80. doi: 10.1109/DSNS50200.2020.00043.
[30]
M. O. Rabin. “Efficient dispersal of information for security, load balancing, and fault tolerance”. In: J. ACM 36.2 (1989), pp. 335–348. doi: 10.1145/62044.62050.
35
[31]
I. S. Reed and G. Solomon. “Polynomial Codes Over Certain Finite Fields”. In: Journal of the Society for Industrial and Applied Mathematics 8.2 (1960), pp. 300–304. eprint: https://doi. org/10.1137/0108018. doi: 10.1137/0108018.
[32]
Z. Shen, Y. Cai, K. Cheng, P. P. C. Lee, X. Li, Y. Hu, and J. Shu. “A Survey of the Past, Present, and Future of Erasure Coding for Storage Systems”. In: ACM Trans. Storage 21.1 (2025), 4:1–4:39. doi: 10.1145/3708994.
[33]
V. Shoup. “Sing a Song of Simplex”. In: 38th International Symposium on Distributed Computing, DISC 2024, Madrid, Spain, October 28 - November 1, 2024. Ed. by D. Alistarh. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 37:1–37:22. doi: 10.4230/LIPICS.DISC. 2024.37.
[34]
M. Vajha, V. Ramkumar, B. Puranik, G. R. Kini, E. A. Lobo, B. Sasidharan, P. V. Kumar, A. Barg, M. Ye, S. Narayanamurthy, S. Hussain, and S. Nandi. “Clay Codes: Moulding MDS Codes to Yield an MSR Code”. In: 16th USENIX Conference on File and Storage Technologies, FAST 2018, Oakland, CA, USA, February 12-15, 2018. Ed. by N. Agrawal and R. Rangaswami. USENIX Association, 2018, pp. 139–154. url: https : / / www . usenix . org / conference / fast18 / presentation/vajha.
[35]
S. Williams, V. Diordiiev, L. Berman, and I. Uemlianin. Arweave: A protocol for economically sustainable information permanence. Arweave Yellow Paper. 2019.
[36]
C. Yang, K. Chin, J. Wang, X. Wang, Y. Liu, and Z. Zheng. “Scaling Blockchains with Error Correction Codes: A Survey on Coded Blockchains”. In: ACM Comput. Surv. 56.6 (2024), 139:1– 139:33. doi: 10.1145/3637224.
36