Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary

We assume $n$ nodes over an asynchronous network, where a message can be delayed for an arbitrary yet finite amount of time (unless omitted by the message adversary). We assume the existence of $t$ Byzantine nodes and a message adversary capable of omitting up to $d$ messages per node’s broadcast. To be more precise, a node communicates through a comm primitive (or a similar multicast/unicast primitive that targets a dynamically defined subset of nodes), which results in the transmission of $n$ messages, with each node being sent one message, including the sender. The message adversary can omit messages in transit to a subset of at most $d$ correct nodes. The adversary is only limited by the size of that subset. For instance, between different comm invocations, the adversary can modify the set of correct nodes to which messages are omitted. Furthermore, a designated sender node holds a message $m$ that it wishes to broadcast to all the nodes.

An algorithm that satisfies the requirements of reliable broadcast despite Byzantine nodes and a message adversary is called a Message-adversary Byzantine Reliable Broadcast (MBRB) algorithm. The detailed version of MBRB’s requirements was formulated in [4], see Section 2. We informally summarize them here as follows. (1) For any sender invoking the broadcast algorithm, no two correct nodes deliver $m$ and $m^{\prime }$, such that $m^{\prime }\ne m$. (2) For any sender invoking the broadcast algorithm, either zero or at least $\mathrm{\ell }$ correct nodes will deliver $m$. The quantity $\mathrm{\ell }$ might depend on the adversary’s power, i.e., on $t$ and $d$. (3) If a correct node delivers some message $m$ from a correct sender, this correct sender has broadcast $m$ previously and at least $\mathrm{\ell }$ correct nodes will deliver it.

Albouy, Frey, Raynal, and Taïani [4] recently proposed a Message-adversary Byzantine Reliable Broadcast algorithm (denoted AFRT for short) for asynchronous networks that withstands the presence of $t$ Byzantine nodes and a message adversary capable of omitting up to $d$ messages per node’s broadcast. AFRT guarantees the reliable delivery of any message when $n>3$t+$2d$. Moreover, they demonstrate the necessity of this bound on the number of Byzantine nodes and omitted messages, as no reliable broadcast algorithm exists otherwise.

One caveat of AFRT regards its communication efficiency. While it achieves an optimal number of $𝒪\text{(}{n}^2\text{)}$ messages, and an optimal delivery power $\mathrm{\ell }=n-t-d$, each node’s communication requires $𝒪\text{(}n\cdot (|m|+n\kappa )\text{)}$ bits, where $|m|$ represents the number of bits in the broadcast message and $\kappa$ is the length of the digital signatures used in their algorithm. In the current work, we design an algorithm that significantly reduces the communication cost per node while preserving the total number of messages communicated. Our solution features at most $4n$ messages per correct node (corresponding to $4n^2$ messages overall), and only $𝒪\text{(}|m|+n\kappa \text{)}$ bits per correct node. Overall, $𝒪\text{(}n|m|+n^2\kappa \text{)}$ bits are communicated by correct nodes. This bound is tight (up to the size of the signature $\kappa$) for deterministic algorithms using signatures [18, 33], as every correct node must receive the message $m$, and as the reliable broadcast of a single bit necessitates at least $\mathrm{\Omega }$($n^2$) messages [21].

This paper is the first to present an MBRB algorithm able to tolerate a hybrid adversary combining $t$ Byzantine nodes and a Message Adversary of power $d$, while providing optimal Byzantine resilience, near-optimal communication, and near-optimal delivery power $\mathrm{\ell }$.

The above asymptotic communication complexity holds assuming a sufficiently long message $m$. Further, $n-t-d$ is a natural upper bound on the delivery power $\mathrm{\ell }$ of any MBRB algorithm. This bound arises from the power of the message adversary to isolate a subset of the correct parties of size $d$, and omit all messages sent to this subset. Our solution obtains a delivery power $\mathrm{\ell }$ that is as close to the limit as desired, at the cost of increasing communication (through the hidden constants in the asymptotic $𝒪\text{(}\cdot \text{)}$ term, which depends on $\epsilon$). Finally, $n>3t+2d$ is a necessary condition to implement MBRB under asynchrony [3], thus making our solution optimal in terms of Byzantine resilience.

The starting point of our algorithm is the AFRT algorithm [4]. This algorithm achieves all the desired MBRB properties (Definition 2.3), albeit with a large communication cost of at least $n^2|m|$ bits overall. This communication cost stems from the re-emission strategy used by AFRT. In the AFRT algorithm, the sender first disseminates the message $m$ to all nodes. To counter a possibly faulty sender, each node that receives $m$ signs it and forwards it to the entire network, along with its own signature and any other signature observed so far for that message. This re-broadcasting step leads to $n^2|m|$ bits of communication.

In order to reduce the communication costs, we apply a coding technique, inspired by an approach by Alhaddad et al. [5]. Instead of communicating the message $m$ directly, the sender first encodes the message using an error-correction code and “splits” the resulting codeword between the nodes, so that each node receives one fragment of size $𝒪\text{(}|m|/n\text{)}$ bits. Now, each node needs to broadcast only its fragment of the message rather than the entire message. This reduced per-node communication effectively reduces the overall communication for disseminating the message itself to $n|m|$ bits.

Due to the message adversary and the actions of the Byzantine nodes, some of the fragments might not arrive at their destination. Error-correction codes have the property that the message $m$ can be reconstructed from any sufficiently large subset of the fragments. But Byzantine nodes can do even worse, namely, they can propagate an incorrect fragment. Correct nodes cannot distinguish correct fragments from incorrect ones (at least, not until enough fragments are collected, and the message is reconstructed). Without this knowledge, correct nodes might assist the Byzantine nodes in propagating incorrect fragments, possibly harming the correctness and/or performance of the algorithm. To prevent this, the sender could sign each fragment that it sends. A node receiving a fragment could then verify that it is correctly signed by the sender and ignore it otherwise. The drawback of this solution is that only the sender can generate signatures for fragments.

In our MBRB algorithm, we rely on correct nodes that have already reconstructed the correct message to disseminate its fragments to the nodes that have not received any (say, due to the message adversary). In principle, when a node reconstructs the correct message, it can generate the codeword and obtain all the fragments, even if it did not receive some of them beforehand. However, the node cannot generate the sender’s signature for the fragments it generated by itself. Because of this, the node cannot relay these fragments to the other nodes, potentially leading to a reduced delivery power $\mathrm{\ell }$.

We avert this issue by exploiting vector commitments [15]. This cryptographic primitive generates a unique short digest $C$ for any input vector of elements $V$. Additionally, it generates succinct proofs of inclusion for each element in $V$. In our system, the fragments of the (coded) message $m$ form the vector $V$, and the inclusion proofs replace the need to sign each fragment separately. In more detail, every fragment of the codeword communicated by some node is accompanied by two pieces of information: the commitment $C$ for the vector $V$ containing all fragments of $m$, and a proof of inclusion showing that the specific fragment indeed belongs to $V$ (see Section 2 for a formal definition of these properties). The sender signs only the commitment $C$. This means that Byzantine nodes cannot generate an incorrect fragment and a proof that will pass the verification, since they cannot forge the sender’s signature on $C$. Yet, given the message $m$, generating a proof of inclusion for any specific fragment can be done by any node. The vector commitment on the message $m$ creates the same commitment $C$ and the same proofs of inclusion generated by the sender. These could then be propagated to any other node along with the sender’s signature on $C$.

To complete the description of our MBRB algorithm, we mention that, similar to AFRT, our algorithm tries to form a quorum of signatures on some specific vector commitment $C$. In parallel, nodes collect fragments they verify as part of the message whose vector commitment is $C$. Once a node collects enough signatures (for some $C$) and at the same time obtains enough message fragments that are proven to belong to the same $C$, the node can reconstruct $m$ and deliver (accept) it. At this point, the node also disseminates the quorum of signatures along with (some of) the fragments. This allows other correct nodes to reconstruct the message and verify a quorum has been reached. In fact, the dissemination of fragments, including fragments that this node did not have before reconstructing the message, is a crucial step in amplifying the number of nodes that deliver $m$ to our stated level of $\mathrm{\ell }=n-t-(1+\epsilon )d$. See the full description of the MBRB algorithm in Section 3.

Although our algorithm builds quorums on commitments, it departs substantially from the BRB algorithm proposed by Das, Xiang, and Ren [18], which avoids signatures and relies on hashes only. Their solution provides an overall communication complexity in $𝒪\text{(}n|m|+n^2\kappa \text{)}$ that is optimal up to the $\kappa$ parameter. Following the sender’s initial dissemination of message $m$, their proposal runs Bracha’s algorithm on the hash value of the broadcast message to ensure agreement. Unfortunately, when used with a message adversary, Bracha’s algorithm loses the sub-optimal Byzantine resilience $n>3t+2d$ that AFRT and our solution provide, which is why the solution presented in this paper avoids it. (See Appendix C for a more detailed discussion of why this is so.) Due to the page limit, our algorithm’s complete analysis and proof details appear in the Appendix.

Byzantine reliable broadcast (BRB) can be traced back to Pease, Shostak, and Lamport [34], which considered the particular case of synchronous message-passing systems. Since then, solutions for reliable broadcast, together with the related consensus problem, have been considered for many distributed systems [38]. In asynchronous systems, BRB solutions can be traced back to Bracha and Toueg [11, 12]. Recent advances [30, 27, 9, 23] in Byzantine fault-tolerant (BFT) solutions to the problem of BRB include the above-mentioned AFRT [4], which safeguards also against the message adversary. Our solution features substantially lower communication than AFRT, without harming the other properties, e.g., the number of messages or the delivery power.

Computation in networks with link faults, namely, with Byzantine links was considered by Santoro and Widmayer [41, 42], who discussed various types of Byzantine actions, e.g., omitting messages, corrupting messages, injecting messages, and combinations thereof. The works of [6, 43] focus on the case of reliable broadcast with such faults. In [35], Pelc proved that robust communication is feasible over graphs whose edge-connectivity is more than $2f$, assuming the number of Byzantine links is bounded by $f$. This is also implied by the work of Dolev [20]. Censor-Hillel et al. [16] and Frei et al. [24] show that any computation can be performed when all links suffer arbitrary substitution faults (but no crashes), given that the network is 2-edge connected. When all links suffer corruption, but their overall amount is restricted, any computation can be reliably performed by Hoza and Schulman [28], for synchronous networks where the topology is known, or by Censor-Hillel, Gelles, and Haeupler [17], for asynchronous networks with unknown topology, see also [25].

Settings that allow Byzantine nodes in addition to faulty links were considered [7, 8, 19, 26, 36, 46]. Building on [4], the algorithm was also extended to signature-free asynchronous systems [3], albeit with lower delivery guarantees, and a weaker resilience with respect to $d$ and $t$. We consider fully connected asynchronous networks, Byzantine nodes, and omission only link failures. But, our MBRB is the first, to the best of our knowledge, to offer a near-optimal communication (up to the length of the signature, $\kappa$) and delivery power $\mathrm{\ell }$.

Coding techniques are implemented to minimize the dissemination costs associated with message transmission across the network, ensuring the ability to reconstruct data in the event of node failures or adversarial compromises. In the context of Blockchains, significant contributions have been made by Cachin and Tessaro [14] as well as Cachin and Poritz in SINTRA [13], followed by its successors such as HoneyBadgersBFT [32], BEAT [22], DispersedLedger [47] and Alhaddad et al. [5]. These solutions leverage digital signatures and coding techniques to provide a balanced and reliable broadcast. Our work contributes to the advancement of the state of the art in the field of coded reliable broadcast by offering improved fault-tolerance guarantees that are stronger than the aforementioned solutions.

We focus on asynchronous message-passing systems that have no guarantees of communication delay. The system consists of a set, $𝒫=\{p_1,\mathrm{\dots },p_n\}$, of $n$ fail-prone nodes that cannot access a clock or use timeouts. We identify node $i$ with $p_i$.
Communication means. Any ordered pair of nodes $p_i,p_j\in 𝒫$ has access to a communication channel, ${\mathrm{𝑐ℎ𝑎𝑛𝑛𝑒𝑙}}_{i,j}$. Each node can send messages to all nodes (possibly by sending a different message to each node). That is, any node, $p_i\in 𝒫$, can invoke the transmission macro, $\text{comm}(m_1,\mathrm{\dots },m_n)$, that communicates the message $m_j$ to $p_j$ over ${\mathrm{𝑐ℎ𝑎𝑛𝑛𝑒𝑙}}_{i,j}$. The message $m_j$ can also be empty, in which case nothing will be sent to $p_j$. However, in our algorithms, all messages sent in a single comm activation will have the same length. Furthermore, when a node sends the same message $m$ to all nodes, we write $\text{broadcast}(m)=\text{comm}(m,m,\mathrm{\dots },m)$ for shorthand. We call each message $m_j$ transmitted by the protocol an implementation message (or simply, a message) to distinguish such messages from the application-level messages, i.e., the one the sender wishes to broadcast.
Byzantine nodes. Faulty nodes are called Byzantine, and their adversarial behavior can deviate from the proposed algorithm in any manner. For example, they may crash or send fake messages. Their ability to communicate and collude is unlimited. They might perform any arbitrary computation, and we assume their computing power is at least as strong as that of non-faulty nodes, yet not as strong as to undermine the security of the cryptographic signatures we use. We assume that at most $t$ nodes are faulty, where $t$ is a value known to the nodes. Non-faulty nodes are called correct nodes. The set of correct nodes contains $c$ nodes where $n-t\le c\le n$. The value of $c$ is unknown.

Faulty nodes may deviate arbitrarily from the correct implementation of comm($\cdot$). For instance, they may unicast messages to only a subset of the nodes in $𝒫$. As mentioned, each pair of nodes can communicate using ${\mathrm{𝑐ℎ𝑎𝑛𝑛𝑒𝑙}}_{i,j}$. While ${\mathrm{𝑐ℎ𝑎𝑛𝑛𝑒𝑙}}_{i,j}$ is assumed to be a reliable channel that is not prone to message corruption, duplication, or the creation of fake messages that were never sent by nodes; the message adversary [41, 43, 37], which we specify next, has a limited ability to cause message loss.
Message adversary. This entity can remove implementation messages from the communication channels used by correct nodes when they invoke comm($\cdot$). More precisely, during each activation of $\text{comm}(m_1,\mathrm{\dots },m_n)$, the adversary has the discretion to choose up to $d$ messages from the set $\{m_i\}$ and eliminate them from the corresponding communication channels where they were queued. We assume that the adversary has full knowledge of the contents of all messages $\{m_i\}$, and thus it makes a worst-case decision as to which messages to eliminate.

The failures injected by a message adversary differ from those of classical sender and/or receiver omissions in that they are mobile. I.e., they are not pinned to a set of particular nodes but may move between any correct nodes during the same execution since they are defined per invocation of comm($\cdot$). In particular, no node is immune to the message adversary.

Note that for the case of $d=0$, the adversary is as weak as the common settings in which all communication channels are reliable (since no message is ever lost) and $t$ nodes are Byzantine. Assumption 2.1 limits the adversary’s power to avoid network partitions. As mentioned above, this is necessary for any MBRB algorithm [4].

Since the message adversary can omit all implementation messages that are sent to a given set $D\subseteq 𝒫:|D|=d$, we know that $\mathrm{\ell }$, the number of correct nodes that are guaranteed to output the broadcast $m$ correctly, must satisfy $\mathrm{\ell }\le c-d$.

Such a hybrid fault model has been studied in the past in synchronous networks [8], but has remained little studied in an asynchronous setting, except for the work of Schmid and Fetzer [44] that limits itself to round-based algorithms (unlike us) and does not cover full disconnections of correct nodes (which we do). Modeling full disconnections is relevant as this captures correct nodes that remain disconnected for long periods. In addition to bounding the maximal number of outgoing messages that a correct sender might lose (as we do), the model proposed by Schmid and Fetzer [44] also bounds the maximal number of incoming messages that any correct node might miss. This adds an elegant symmetry to the model but poses significant challenges when considering asynchronous networks, as there is no obvious scope on which to limit the number of incoming messages missed by a given node. Schmid and Fetzer [44] therefore restrict the fault model to round-based algorithms. By contrast, our model allows for algorithms that do not follow this structure.

A central tool used in our algorithm is an error-correction code (ECC) [40]. Intuitively speaking, an ECC takes a message as input and adds redundancy to create a codeword from which the original message can be recovered even when parts of the codeword are corrupted. In this work, we focus on erasures, a corruption that replaces a symbol of the codeword with a special erasure mark $\perp$.

Let $𝔽$ denote a finite field whose size we set later, and let $\perp$ be a special symbol $\perp \notin 𝔽$. Given two strings of the same length, $x,y\in {𝔽}^n$, their Hamming distance is the number of indices where they differ, $\mathrm{\Delta }(x,y)=|\{i\in [n]\mid x_i\ne y_i\}|$. Given a subset $I\subseteq [n]$, we denote by $x_I\in {𝔽}^{|I|}$ the string $x$ restricted to the indices in $I$.

To avoid confusion with global parameters, we denote the ECC-specific parameters by using a bar (e.g., $\overline{x}$). An error-correction code is a function $\text{ECC}:{𝔽}^{\overline{k}}\to {𝔽}^{\overline{n}}$, with rate $\overline{r}=\overline{k}/\overline{n}$, and distance $\overline{d}={\min }_{x,y\in {𝔽}^{\overline{k}},x\ne y}\mathrm{\Delta }(\text{ECC}(x),\text{ECC}(y))$. The Singleton bound determines that $\overline{d}\le \overline{n}-\overline{k}+1$, and when the equality holds, the code is said to be maximum distance separable (MDS). A prominent example of MDS codes is Reed-Solomon (RS) codes [39], which exist for any $\overline{k},\overline{n}$, and $|𝔽|\ge \overline{n}$. Such codes can be efficiently encoded and decoded [40]. The erasure correction capabilities of a code depend on its distance, as given by the following fact.

Our algorithm relies on cryptographic assumptions. We assume that the Byzantine nodes are computationally bounded with respect to the security parameter, denoted by $\kappa$. That is, all cryptographic algorithms are polynomially bounded in the input $1^{\kappa }$. We assume that $\kappa =\mathrm{\Omega }$($\log n$). We further assume the availability of Public Key Infrastructure (PKI), which is the setting that assumes each node is assigned a pair of public/private keys generated according to some standard key-generation algorithm. Further, at the start of the computation, each node holds its own private key and the public key of all other parties. This setting implies private and authenticated channels. In particular, each node has public and private keys to support the following cryptographic primitives.
Threshold signatures. In a $(\tau ,n)$ threshold signature scheme [45], at least $\tau$ out of all $n$ nodes (the threshold) produce individual signatures shares $\sigma$ for the same message $m$, which are then aggregated into a fixed-size threshold signature $\mathrm{\Sigma }$. Verifying $\mathrm{\Sigma }$ does not require the public keys of the signers; one needs to use a single system-wide public key, the same for all threshold signatures produced by the scheme. This system public key, known to everyone, is generated during the system setup phase and distributed through the PKI.

Formally, we define a $(\tau ,n)$ threshold signature scheme as a tuple of (possibly randomized) algorithms $\mathrm{𝖳𝖲𝖨𝖦}=(\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗌𝗂𝗀𝗇}\mathrm{\_}\mathrm{𝗌𝗁𝖺𝗋𝖾},\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗏𝖾𝗋𝗂𝖿𝗒}\mathrm{\_}\mathrm{𝗌𝗁𝖺𝗋𝖾},\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝖻𝗂𝗇𝖾},\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗏𝖾𝗋𝗂𝖿𝗒})$. The signing algorithm executed by node $p_i$ (denoted, $\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗌𝗂𝗀𝗇}\mathrm{\_}{\mathrm{𝗌𝗁𝖺𝗋𝖾}}_i$) takes a message $m$ (and implicitly a private key) and produces a signature $\sigma =\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗌𝗂𝗀𝗇}\mathrm{\_}{\mathrm{𝗌𝗁𝖺𝗋𝖾}}_i(m)$. The share verification algorithm takes a message $m$, a signature share ${\sigma }_i$, and the identity $i$ of its signer $p_i$ (and implicitly $p_i$’s public key), and outputs a single bit, $b=\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗏𝖾𝗋𝗂𝖿𝗒}\mathrm{\_}\mathrm{𝗌𝗁𝖺𝗋𝖾}(m,{\sigma }_i,i)\in \{\text{valid},\text{invalid}\}$, which indicates whether the signature share is valid or not. The combination algorithm takes a set $\mathrm{𝑠𝑖𝑔𝑠}$ of $\tau$ valid signature shares produced by $\tau$ out of $n$ nodes and the associated message $m$ (and implicitly the system public key) and outputs a threshold signature $\mathrm{\Sigma }=\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝖻𝗂𝗇𝖾}(\mathrm{𝑠𝑖𝑔𝑠})$. The threshold signature verification algorithm takes a message $m$ and a threshold signature $\mathrm{\Sigma }$ (and implicitly the system public key) and outputs a single bit $b=\mathrm{𝗍𝗌}\mathrm{\_}\mathrm{𝗏𝖾𝗋𝗂𝖿𝗒}(m,\mathrm{\Sigma })\in \{\text{valid},\text{invalid}\}$, indicating if the threshold signature is valid or not.

We require the conventional robustness and unforgeability properties for threshold signatures. This scheme is parameterized by a security parameter $\kappa$, and the size of signature shares and threshold signatures, $|\sigma |=|\mathrm{\Sigma }|=𝒪\text{(}\kappa \text{)}$, is independent of the size of the signed message, $m$. In our algorithm, we take $\tau =\lfloor \frac{n+t}{2}\rfloor +1$ (i.e., the integer right above $\frac{n+t}{2}$).
Vector commitments (VC). A vector commitment (VC) is a short digest $C$ for a vector of elements $V$, upon which a user can then generate a proof of inclusion $\pi$ (sometimes called partial opening) of some element in $V$ without disclosing the other elements of $V$ to the verifier: the verifier only needs $C$, $\pi$, the element, and its index in the vector to verify its inclusion in $V$. A Merkle tree [31] is a notable example of vector commitment, although with several sub-optimal properties. For example, for a hash size of $\kappa$, a Merkle proof of inclusion is of $𝒪\text{(}\kappa \log |V|\text{)}$ bits, which is significantly larger than modern schemes such as Catalano-Fiore vector commitments [15], which produce proofs of inclusion with an optimal size of $𝒪\text{(}\kappa \text{)}$ bits. In our construction, we use these optimal VC schemes (such as Catalano-Fiore’s), which provide commitments and proofs in $𝒪\text{(}\kappa \text{)}$ bits. The VC scheme provides two operations, parameterized by the security parameter $\kappa$: $\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝗆𝗂𝗍}(\cdot )$ and $\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝗏𝖾𝗋𝗂𝖿𝗒}(\cdot )$, that work as follows. For any vector of strings $V=(x_1,\mathrm{\dots },x_n)={(x_i)}_{i\in [n]}$, the function $\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝗆𝗂𝗍}(V)\to (C,{\pi }_1,\mathrm{\dots },{\pi }_n)$ returns $C$, the commitment, and every ${\pi }_i$, the proof of inclusion for $x_i$. The following hold.

1. 1.

   Proof of inclusion (Correctness): Let $(C,{({\pi }_i)}_{i\in [n]})=\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝗆𝗂𝗍}((x_1,\mathrm{\dots },x_n))$. Then for any $i\in [n]$, it holds that $\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝗏𝖾𝗋𝗂𝖿𝗒}(C,{\pi }_i,x_i,i)=\text{valid}$.

2. 2.

   Collision-resistance (Binding): For any $j\in [n]$ and any randomized algorithm $A$ taking ${(x_i)}_{i\in [n]}$ and $(C,{({\pi }_i)}_{i\in [n]})=\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝗆𝗂𝗍}(x_1,\mathrm{\dots },x_n)$ as input, . Namely, it is difficult to generate $x_j^{\prime }\ne x_j$ and a valid proof ${\pi }_j^{\prime }$ for the same commitment $C$.

We omit the traditional Hiding property of VC schemes (a commitment does not leak information on the vector [2]) as it is unneeded in our algorithm. We also implicitly assume that the $\mathrm{𝗏𝖼}\mathrm{\_}\mathrm{𝖼𝗈𝗆𝗆𝗂𝗍}$ operation is deterministic: it always returns the same commitment $C$ given the same input vector $V$, no matter the calling node $p_i$. This is the case for Catalano-Fiore’s scheme [15], which does not use random salt.

MBRB’s objective is to guarantee a reliable broadcast, meaning it aims to ensure that a bounded minimum number of correct nodes ultimately deliver the broadcast messages to the application while upholding specific safety and liveness criteria. This assurance holds even when confronted with Byzantine faults and a message adversary capable of selectively suppressing messages.

An MBRB algorithm provides the MBRB-broadcast and MBRB-deliver operations. The following specification is presented in a single-shot, single-sender version, where $p_s$ is the sending node. A multi-sender, multi-shot version can be derived by adding the sender’s identifier and a running sequence number to messages and signatures. Nodes invoke the MBRB-deliver operation to deliver (to the application layer) messages broadcast by $p_s$.

Definition 2.3 specifies the safety and liveness properties of MBRB. Safety ensures that messages are delivered correctly without spurious messages, duplication, or duplicity. Liveness guarantees that if a correct node broadcasts a message, it will eventually be delivered by at least one correct node (MBRB-Local-delivery). If a correct node delivers a message from any specific sender, that message will eventually be delivered by a sufficient number, $\mathrm{\ell }$, of correct nodes (MBRB-Global-delivery), where $\mathrm{\ell }$ is a measure of the delivery power of the MBRB object. The parameter $\mathrm{\ell }$ might depend on the adversary’s power, i.e., on $t$ and $d$. Since the message adversary can omit all implementation messages that are sent to an unknown set $D\subseteq 𝒫:|D|=d$, we know that $\mathrm{\ell }\le c-d$.

MBRB-broadcast$(m)$ allows the sender $p_s$ to start disseminating the application message, $m$ (line 17). The sender (line 18) starts by invoking $\text{computeFragVecCommit}(m)$ (Algorithm 1). This function encodes the message $m$ using an error-correction code, divides it into $n$ fragments and constructs a vector commitment with an inclusion proof for each fragment. The function returns several essential values: the commitment $C$, and the fragment details $({\tilde{m}}_j,{\pi }_j,j)$, which contain the fragment data itself ${\tilde{m}}_j$ (the $j$-th part of the codeword $\text{ECC}(m)$; see below for detail), a proof of inclusion ${\pi }_j$ for that part, and each fragment’s respective index $j$. For ease of reference, let $\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍𝗆𝖾𝗇𝗍}(m)$ represent the commitment $C$ obtained from $\text{computeFragVecCommit}(m)$. This commitment serves as a compact representation of the entire message $m$. The sender node $p_s$ is responsible for signing the computed commitment $C$ and generating a signature share ${\mathrm{𝑠𝑖𝑔}}_s$ (line 19) which includes $p_s$’s identifier. The sender then initiates $m$’s propagation by employing the operation comm (line 20), which sends to each node, $p_j$, an individual message, $v_j$. The message $v_j$ includes several components: the message type (send), the commitment $C$, the $j$-th fragment details $({\tilde{m}}_j,{\pi }_j,j)$, and the signature share ${\mathrm{𝑠𝑖𝑔}}_s$ (line 19) for $C$.

The rest of the algorithm progresses in two phases, which we describe in turn. The first phase is responsible for message dissemination, which forwards message fragments received by the sender. The other role of this phase is reaching a quorum of nodes that vouch for the same message. A node vouches for a single message by signing its commitment. Nodes collect and store signature shares until it is evident that sufficiently many nodes agree on the same message. The subsequent phase focuses on disseminating the quorum of signature shares so that it is observed by at least $\mathrm{\ell }$ correct nodes, and on successfully terminating while ensuring the delivery of the reconstructed message.

Upon receiving a $⟨\text{send},C^{\prime },$ $({\tilde{m}}_i,{\pi }_i,i),{\mathrm{𝑠𝑖𝑔}}_s⟩$ message from $p_s$, the recipient $p_i$ validates the incoming message (line 22). $p_i$ then determines whether it had previously broadcast a forward message at line 25 or signed a commitment $C^{\prime \prime }$ from $p_s$ distinct from the currently received $C^{\prime }$, in which case the incoming message is discarded (line 23). Otherwise, $p_i$ proceeds to store the received information (line 24), encompassing the fragment ${\tilde{m}}_i$ and the associated signature share ${\mathrm{𝑠𝑖𝑔}}_s$, linked to the specific commitment $C^{\prime }$. We clarify that $p_i$ never stores multiple copies of the same information, i.e., all store operations are to be read as adding an item to a set. Subsequently, $p_i$ generates its own signature share ${\mathrm{𝑠𝑖𝑔}}_i$ for the commitment $C^{\prime }$, storing it for later utilization (line 24). Node $p_i$ then disseminates all the relevant information, by broadcasting the message $⟨\text{forward},C^{\prime },({\tilde{m}}_i,{\pi }_i,i),\{{\mathrm{𝑠𝑖𝑔}}_s,{\mathrm{𝑠𝑖𝑔}}_i\}⟩$.

The broadcast of a forward message is instrumental in disseminating information for several reasons. First, up to $d$ nodes might not receive the sender’s send message. Second, this is the node’s way to disseminate its own fragment and signature share for that specific $C^{\prime }$.

Upon the arrival of a $⟨\text{forward},C^{\prime },{\mathrm{𝑓𝑟𝑎𝑔𝑡𝑢𝑝𝑙𝑒}}_j,{\mathrm{𝑠𝑖𝑔𝑠}}_j⟩$ message from $p_j$ (line 26), the recipient $p_i$ validates the incoming message using the isValid function (Algorithm 1), discarding invalid messages (line 27). As for send messages, $p_i$ checks if it already signed a message from $p_s$ with a different commitment $C^{\prime \prime }$, in which case it discards the message (line 28). Subsequently, $p_i$ stores the set of signature shares ${\mathrm{𝑠𝑖𝑔𝑠}}_j$ linked to the specific commitment $C^{\prime }$ (line 29) and ${\mathrm{𝑓𝑟𝑎𝑔𝑡𝑢𝑝𝑙𝑒}}_j$ contained in this message, if any (line 31). Also, $p_i$ assesses whether a forward message has been previously dispatched. If it has already done so, there is no reason to re-send it, and the processing ends here. Otherwise, similar to above, $p_i$ generates its own signature share ${\mathrm{𝑠𝑖𝑔}}_i$ for the commitment $C^{\prime }$, and broadcasts the message $⟨\text{forward},C^{\prime },\perp ,{\mathrm{𝑠𝑖𝑔}}_s,{\mathrm{𝑠𝑖𝑔}}_i⟩$. Note that, in this case, $p_i$ is unaware of his own fragment (i.e., it has not received a send message, or otherwise it would have already sent a forward message in line 25); therefore it sends the sentinel value $\perp$ instead.
Phase II: Reaching quorum and termination. This phase relies on the getThreshSig function described in Algorithm 1, which, given a commitment $C$, either returns a threshold signature for $C$ (received beforehand or aggregating $\tau =\lfloor \frac{n+t}{2}\rfloor +1$ signature shares stored for $C$) if it exists, or $\perp$ otherwise. This phase focuses on ensuring that, once a Byzantine quorum (represented by the threshold signature returned by getThreshSig) and enough message fragments for reconstructing the original message $m$ are gathered, at least $\mathrm{\ell }$ correct nodes deliver $m$ and terminate. Node $p_i$ enters Phase II only when there is a commitment $C^{\prime }$ for which getThreshSig returns a valid threshold signature, and $p_i$ stores at least $k$ message fragments. As long as no application message from $p_s$ was delivered (line 35), $p_i$ reconstructs the application message $m_i$ (line 36) using the stored message fragments, and use this message as an input to computeFragVecCommit (line 37), which outputs its commitment $C=\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍𝗆𝖾𝗇𝗍}(m_i)$ along with coded message fragments and proofs of inclusion, $({\tilde{m}}_j^{\prime },{\pi }_j^{\prime },j)$. Node $p_i$ then ensures that the computed commitment $C$ matches the stored commitment $C^{\prime }$ (line 38). If this condition holds true, then $m_i=m$ is the message sent by the sender¹¹1To see why this is needed, consider a Byzantine sender that disseminates fragments ${\tilde{m}}_1,\mathrm{\dots },{\tilde{m}}_n$, that do not form a proper codeword., and in particular, $p_i$ now holds all the possible fragments for $m$ along with their valid proof of inclusion, including fragments it has never received before! Node $p_i$ then retrieves the threshold signature ${\mathrm{\Sigma }}_C$ of $C$ using the getThreshSig function (line 39), and disseminates it along with the message fragments to the rest of the network. In particular, to each $p_j$ in the network, $p_i$ sends a bundle message (line 40) that includes the commitment $C$, fragment details $({\tilde{m}}_i^{\prime },{\pi }_i^{\prime },i)$ and $({\tilde{m}}_j^{\prime },{\pi }_j^{\prime },j)$, and the associated threshold signature ${\mathrm{\Sigma }}_C$. After these transmissions, $p_i$ can MBRB-deliver the reconstructed message $m_i$ (line 41).

The parameter $k$ used at line 35 is the number of (valid) fragments sufficient to reconstruct the application message $m$ by the error-correction code ECC. This parameter should be practically selected by the desired $\mathrm{\ell }$ given in Lemma A.12. That is, one needs to set $\epsilon >0$ for $\mathrm{\ell }=n-t-(1+\epsilon )d$ and then choose $k\le 1+\frac{\epsilon }{1+\epsilon }(n-t-d)$. See details in Appendix A.

Upon the arrival of a bundle message, i.e., $⟨\text{bundle},C^{\prime },({\tilde{m}}_j^{\prime },{\pi }_j^{\prime },j),{\mathrm{𝑓𝑟𝑎𝑔𝑡𝑢𝑝𝑙𝑒}}_i^{\prime },\mathrm{\Sigma }⟩$ arriving from $p_j$ (line 42), the recipient $p_i$ validates the received message using the isValid function (with the $\mathrm{𝑖𝑠𝑇ℎ𝑟𝑒𝑠ℎ𝑆𝑖𝑔}$ parameter set to $\mathrm{𝖳𝗋𝗎𝖾}$ to indicate that we verify a threshold signature) and discards invalid messages (line 43). Node $p_i$ proceeds to store the arriving information regarding the message segments $({\tilde{m}}_j^{\prime },{\pi }_j^{\prime },j)$ and threshold signature $\mathrm{\Sigma }$ for the specific commitment $C^{\prime }$ (line 44). In the case that no bundle message was sent by $p_i$ and the received ${\mathrm{𝑓𝑟𝑎𝑔𝑡𝑢𝑝𝑙𝑒}}_i^{\prime }$ is nonempty (so $p_i$ learns its fragment, which it stores at line 47, unless already known), $p_i$ broadcasts a $⟨\text{bundle},C^{\prime },({\tilde{m}}_i^{\prime },{\pi }_i^{\prime },i),\perp ,\mathrm{\Sigma }⟩$ message (line 48).

The use of $\perp$ values appears also in bundle messages (lines 40 and 48). A bundle message might contain up to two fragments: the sender’s fragment (${\tilde{m}}_i^{\prime }$ in the pseudo-code), which is always included, and the receiver’s fragment (${\tilde{m}}_j^{\prime }$), which is included only when the sender was able to reconstruct the message $m$ (at line 36). The sender’s fragments are collected by the receivers and allow reconstruction of the message once enough bundle messages are received. The receiver’s fragment allows the receiver to send bundle messages (with its fragment), facilitating the dissemination of both threshold signatures and fragments.

computeFragVecCommit (Algorithm 1) uses an error-correction code at line 2 to encode the application message $m$, before it is split into $n$ fragments that will be disseminated by the parties. The code uses a fixed parameter $k$, that can be set later. Our algorithm requires that the ECC will be able to decode the message $m$ from any subset of $k$ fragments out of the $n$ fragments generated at line 3. That is, we need an ECC that can deal with erasures, where the erased symbols are those contained in the $n-k$ missing fragments. To that end, we use a Reed-Solomon code $\text{ECC}:{𝔽}^{\overline{k}}\to {𝔽}^{\overline{n}}$ with $\overline{k}>|m|/\log |𝔽|$. Each fragment contains $\overline{n}/n$ symbols of the codeword, and to be able to recover from $(n-k)\cdot \overline{n}/n$ erased symbols by ˜2.2, we can set the code’s distance to be $\overline{d}>(n-k)\cdot \overline{n}/n$. Since a Reed-Solomon code is MDS (see Section 2), $\overline{d}\le \overline{n}-\overline{k}+1$, and we can set $\overline{n}>\frac{n}{k}(\overline{k}-1)$. The code will have a constant rate, i.e., $|\text{ECC}(m)|=𝒪\text{(}|m|\text{)}$, as long as $m$ is sufficiently long, i.e., $|m|=\mathrm{\Omega }$($n\log |𝔽|$), which implies that $\overline{k}=\mathrm{\Omega }$($n$), and as long as $k=\mathrm{\Omega }$($n$). Recall also that $|𝔽|\ge \overline{n}$ is in a Reed-Solomon code.

The following main theorem states that our algorithm is correct.

Due to the page limit, the complete proof appear in Appendices A and B. Here, we sketch the proof of the MBRB-Global-delivery property in Lemma 3.2 (assuming the other properties hold) and the communication analysis in Lemma 3.3.

Let $C_m=\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍𝗆𝖾𝗇𝗍}(m)$. The proof counts the bundle messages disseminated by correct nodes. If a correct node disseminates a bundle message both at lines 40 and 48, we only consider the one from line 40. Let $B_{\mathrm{𝗌𝖾𝗇𝖽}}$ be the set of correct nodes that disseminate at least one bundle message, let $B_{\mathrm{𝗋𝖾𝖼𝗏}}$ be the set of correct nodes that receive at least one valid bundle message from a correct node during their execution, and let $B_{k,\mathrm{𝗋𝖾𝖼𝗏}}$ be the set of correct nodes that receive bundle messages from at least $k$ distinct correct nodes. The following holds.

Since $B_{\mathrm{𝗌𝖾𝗇𝖽}}$ and $B_{\mathrm{𝗋𝖾𝖼𝗏}}$ contain only correct nodes, trivially $c\ge |B_{\mathrm{𝗌𝖾𝗇𝖽}}|$ and $c\ge |B_{\mathrm{𝗋𝖾𝖼𝗏}}|$. $|B_{\mathrm{𝗋𝖾𝖼𝗏}}|\ge c-d$ and $|B_{\mathrm{𝗌𝖾𝗇𝖽}}|\ge c-d$ follow from the definition of the message adversary, and the way the algorithm chains bundle messages. $◀$

The inequality follows from a counting argument on the overall number of valid bundle messages received by correct nodes from distinct correct senders. In particular, we use the fact that nodes in $B_{\mathrm{𝗋𝖾𝖼𝗏}}\setminus B_{k,\mathrm{𝗋𝖾𝖼𝗏}}$ each receives at most $k-1$ valid bundle messages from distinct correct senders. $◀$

The observation is obtained by isolating $B_{k,\mathrm{𝗋𝖾𝖼𝗏}}$ in Observation 3.2.2, and minimizing the right-hand side to remove the dependence on $|B_{\mathrm{𝗌𝖾𝗇𝖽}}|$. $◀$

The observation results from the properties of the vector commitment scheme, the unforgeability of signatures, and the ability of the ECC scheme to reconstruct $m$ from $k$ distinct valid fragments for $m$. $◀$

As all nodes in $B_{k,\mathrm{𝗋𝖾𝖼𝗏}}$ are correct, the above observations yield the lemma. (The full proof of this lemma can be found in Appendix A, page A.12.) $◀$

For concision, we use in the following the verb disseminate for referring to a correct node that sends a message to all $n$ nodes of the system, whether it be using the broadcast operation or the comm operation.

Let us first consider message complexity. If the sender $p_s$ is correct, it disseminates one send message to all nodes at line 20, receives it immediately at line 21, and disseminates one forward message at line 25 (as $p_s$ cannot not pass line 32 afterward). Every other correct node disseminates at most two forward messages at lines 25 and 34. Moreover, each correct node disseminates at most two bundle messages at lines 40 and 48. This amounts to at most $4n^2$ messages sent by correct nodes.

Let us now analyze the bit complexity of the algorithm. If the sender $p_s$ is correct, it disseminates a send message (line 20) including a fragment of $m$ ($𝒪\text{(}|m|/n\text{)}$ bits) with its proof of inclusion ($𝒪\text{(}\kappa \text{)}$ bits), a commitment ($𝒪\text{(}\kappa \text{)}$ bits), and a signature share ($𝒪\text{(}\kappa \text{)}$ bits). Thus, $p_s$ communicates at most $𝒪\text{(}|m|+n\kappa \text{)}$ bits in send messages. Moreover, a forward message contains a commitment ($𝒪\text{(}\kappa \text{)}$ bits), at most one message fragment with its proof of inclusion ($𝒪\text{(}|m|/n+\kappa \text{)}$ bits), and two signature shares ($𝒪\text{(}\kappa \text{)}$ bits). Hence, every correct node communicates at most $𝒪\text{(}|m|+\kappa n\text{)}$ bits in forward messages (line 25 or 34). Additionally, a bundle message contains a commitment ($𝒪\text{(}\kappa \text{)}$ bits), at most two message fragments with their proof of inclusion ($𝒪\text{(}|m|/n+\kappa \text{)}$ bits), and one threshold signature ($𝒪\text{(}\kappa \text{)}$ bits). Therefore, every correct node communicates at most $𝒪\text{(}|m|+\kappa n\text{)}$ bits in bundle messages (line 25 or 34). This amounts to a total communication of $𝒪\text{(}|m|+n\kappa \text{)}$ bits sent per correct node, and $𝒪\text{(}n|m|+n^2\kappa \text{)}$ bits sent overall.

Let us remark that the above analysis also holds in the presence of Byzantine nodes, even if $p_s$ is Byzantine. (The full proof of this lemma can be found in Appendix B, page B.1.) $◀$