Efficient Byzantine Reliable Broadcast
in the Failure Case

Numerous applications require the dissemination of certain messages to all nodes in a distributed system. In contrast to a regular broadcast, where all nodes are only guaranteed to receive the message if the sender does not fail, a reliable broadcast provides stronger guarantees. In particular, only one message may be broadcast and either no honest (i.e., non-faulty) node receives it or all of them eventually do, despite the presence of Byzantine nodes, which may behave in arbitrary ways to interfere with the protocol execution. Applications of reliable broadcast include asynchronous atomic broadcast [14, 17, 19, 24, 28, 29, 31], distributed key generation [2, 11, 20], secure data replication [7], and secret sharing [30]. Reliable broadcast can further be used to improve throughput in Byzantine fault-tolerant consensus protocols that treat message dissemination and ordering separately [9].

In his seminal paper, Bracha showed that the reliable broadcast problem can be solved in an asynchronous network comprising $n$ nodes, out of which at most nodes may be Byzantine [6]. The communication complexity, i.e., the number of bits that need to be exchanged in the worst case, of the proposed algorithm is $O(n^2|m|)$, where $|m|$ denotes the size of the broadcast message. Nearly two decades later, Cachin and Tessaro [8] presented the first reliable broadcast algorithm with an improved communication complexity of $3n|m|+O(\kappa n^2\log (n))$ bits using erasure coding, where $\kappa$ is the output size of a collision-resistant hash function, which is asymptotically optimal for large messages as every node must receive at least $|m|$ bits. Subsequently, several studies have focused on narrowing the gap to the lower bound of $\mathrm{\Omega }(n|m|+n^2)$ [1, 3, 10, 26, 27].

While reliable broadcast algorithms with nearly optimal communication complexity are known, all proposed algorithms effectively exhibit the same complexity whether or not the broadcast is successful. In other words, the nodes may not receive any message as the outcome of the broadcast and yet send almost as many bits as in the worst-case execution where a message is delivered. As shown in §4, a Byzantine sender can cause such wasteful executions, even if all other nodes are honest. In any system where each node has an equal chance of becoming the next sender or where a simple round-robin scheme determines the next sender, up to a third of all consumed bandwidth can be wasted.

This problem is addressed in this paper. In §3, reliable broadcast detectors are introduced, which are distributed algorithms that serve to inform a reliable broadcast algorithm whether or not it is safe to start executing the main routine, with the guarantee that all honest nodes will eventually obtain one and the same message. Apart from specifying the requirements that such a detector must meet, two concrete detectors are presented. The second detector has the advantage that the condition to trigger the main reliable broadcast algorithm is reached faster when the sender is honest but requires a more complex setup due to its use of threshold cryptography. The communication complexity of both detectors is $O(\kappa n^2)$, where $\kappa$ is a security parameter of constant size, and thus independent of the message size.

Reliable broadcast algorithms that make use of detectors are provided in §4. The first algorithm showcases the simplicity of defining a reliable broadcast algorithm when given a detector, which demonstrates the power of this abstraction. The second and main algorithm aims to minimize the communication complexity when a message is delivered, while keeping the communication complexity independent of the message size when no message is delivered. In the former case, the overhead factor is only $2+O(1/n)$, i.e., roughly $2n|m|$ bits are sent in total for large $n$ and $|m|$. This bound is slightly worse than the best known bound of $3/2$, but the algorithm is significantly more efficient in the failure case. We argue that it is quite natural for any algorithm optimizing for the failure case to first have the sender broadcast the message. For any such algorithm, at least $5/3n|m|$ bits must be exchanged in total as shown in Appendix A.2, which implies that the proposed algorithm is nearly optimal. Related work on reliable broadcast is summarized in §5 and §6 concludes the paper.

We consider a network comprising $n\ge 3t+1$ nodes, where $t$ denotes the maximum number of Byzantine nodes, which may exhibit arbitrary faulty behavior, ranging from simple crash failures to malicious behavior including collusion. By contrast, the other $n-t$ nodes, which we call honest, always execute any given protocol correctly and never fail. The set of all $n$ nodes is denoted by $V$. Any pair of nodes can communicate directly by exchanging messages over an authenticated channel. Throughout this paper, we consider the asynchronous communication model, where all messages are guaranteed to be received but after an unbounded delay, i.e., nodes cannot expect that a sent message will arrive, nor can they expect to receive a certain message, after a certain amount of time. When a node $v$ sends a message $m$ to all nodes, including itself, we say that node $v$ broadcasts message $m$. If $v$ is honest, all nodes will eventually receive the broadcast message. However, a Byzantine node may send a message that is to be broadcast only to a subset of the nodes, possibly not sending the message at all.

A reliable broadcast protocol ensures that either all honest nodes eventually deliver the sender’s message, i.e., accept the message as the outcome of the reliable broadcast, or no honest node delivers it. Formally, reliable broadcast is defined as follows.

Naturally, there can be multiple instances of reliable broadcast executions running in parallel, each with a specific sender that is known a priori to all nodes. We assume that every message carries information that identifies a particular instance but do not explicitly specify such unique identifiers as we focus on a single execution.

The sender has a message $m$ that it aims to disseminate to all nodes. The size of $m$ in bits is denoted by $|m|$. In addition to the message itself, nodes can send other pieces of data such as hashes, signatures, and the aforementioned identifiers. The used hash functions and signature schemes are assumed to be cryptographically strong in that it is infeasible to find hash collisions or spoof signatures, except with negligible probability. Since hashes and signatures are considered secure for a certain minimum length, we introduce the security parameter $\kappa$, upper bounding the size of hashes and signatures by $O(\kappa )$.

State-of-the-art reliable broadcast algorithms make extensive use of erasure codes, which can handle missing data, or error-correcting codes, which can correct erroneous data. The novel algorithm introduced in §4.2 employs $(n,k)$-erasure codes with parameters defined in that section.

An execution $ℰ$ of a reliable broadcast algorithm is characterized by the send and receive events occurring at all nodes. If the execution results in a message being delivered, we call the execution successful. On the contrary, an execution where no message is delivered is called a failed execution. The validity property implies that all executions where the sender is honest must be successful. In other words, an execution may only fail if the sender is Byzantine. A Byzantine sender, together with other Byzantine nodes, may also prevent the delivery of a message for some time and then transmit more messages which will cause the honest nodes to deliver a message after all. Formally, we can define the point of guaranteed eventual delivery as the inflection point ${\tau }^{\ast }$ for which it holds that there must eventually be an honest node that delivers a message at some time $\tau \ge {\tau }^{\ast }$ but delivery is not guaranteed at any time . If there is such a point in time ${\tau }^{\ast }$, the agreement and totality property together imply that all honest nodes will eventually deliver the same message. Thus, a successful (failed) execution $ℰ$ is an execution for which it holds that (${\tau }^{\ast }=\mathrm{\infty }$). As argued before, the validity property implies that for any execution $ℰ$ with an honest sender starting at time ${\tau }_0$ it must hold that ${\tau }_0={\tau }^{\ast }$.

The primary complexity measure for reliable broadcast algorithms is their communication complexity, which is the maximum number of bits exchanged by all honest nodes together over all possible executions. When defining ${𝒞}^{ℰ}(n,\mathrm{\ell })$ as the communication complexity in a network of $n$ nodes, disseminating a message of size $\mathrm{\ell }$ in execution $ℰ$ when running algorithm $𝒜$, the communication complexity of algorithm $𝒜$ is $𝒞(n,\mathrm{\ell })≔{\max }_{ℰ\in 𝔈}{𝒞}^{ℰ}(n,\mathrm{\ell })$, where $𝔈$ denotes the set of all possible executions. If a Byzantine sender happens to send messages with different sizes – or parts of messages with different sizes – in some execution, we define $\mathrm{\ell }$ as the maximum size of all sent messages.

Since all nodes must receive the sender’s message in a successful execution, at least $n\mathrm{\ell }$ bits must be transmitted overall.¹¹1Technically, $(n-1)\mathrm{\ell }$ bits suffice, not counting the sender itself, but the relative difference tends to zero as $n\to \mathrm{\infty }$. The overhead factor of a reliable broadcast algorithm is defined as $ℒ(n)≔{lim}_{\mathrm{\ell }\to \mathrm{\infty }}\frac{𝒞(n,\mathrm{\ell })}{\mathrm{\ell }n}$. The goal is to get $ℒ(n)$ as close as possible to $1$. However, we distinguish between successful and failed executions: While ${ℒ}^{ℰ}(n)\approx 1$ is the best possible result for any successful execution $ℰ$, it should hold that ${ℒ}^{\overline{ℰ}}(n)=0$ for any failed execution $\overline{ℰ}$ because no message is delivered at all. Rather than specifying ${ℒ}^{ℰ}(n)$ with respect to an execution $ℰ$ that may be successful or failed, we slightly abuse our notation and simply state the goal as minimizing $ℒ(n)$ for successful executions while ensuring that $ℒ(n)=0$ for all failed executions. Note that for any reliable broadcast algorithm that meets these requirements it holds that ${ℒ}^{ℰ}(n)=0$ at any time for any execution $ℰ$.

The second relevant complexity measure is an algorithm’s time complexity, defined as the maximum duration of any execution, i.e., the time between the start of the execution and the time when the last honest node delivers the message, normalizing the maximum message delay to $1$ and defining that all local computation takes $0$ time. As an execution may never terminate given a Byzantine sender, we specify the time complexity for the good case with an honest sender. It is easy to see that honest nodes also engage in only a few rounds of communication for successful executions with a Byzantine sender for all considered algorithms.

As discussed in §1, Bracha presented the first reliable broadcast algorithm with a communication complexity of $O(n^2|m|)$ [6]. While the communication complexity is high, the algorithm is error-free, i.e., it does not depend on any cryptographic assumptions. The algorithm based on erasure coding by Cachin and Tessaro improved the communication complexity to $O(n|m|+\kappa n^2\log (n))$, which is asymptotically optimal for $|m|\in \mathrm{\Omega }(\kappa n\log (n))$ [8]. However, it is not error-free as it uses cryptographically strong hash functions.

With respect to error-free reliable broadcast, the time complexity has been reduced successively from $O(n|m|+n^4\log (n))$ [27] to $O(n|m|+n^3\log (n))$ [26] and then to $O(n|m|+n^2\log (n))$ [3]. It has further been shown how to achieve the bound $O(n|m|+n^2\log (n^3/\epsilon ))$ using a probabilistic algorithm, guaranteeing validity but agreement and totality only hold with probability $1-\epsilon$ [1].

As far as algorithms are concerned that make use of cryptographic primitives, an algorithm has been presented with a communication complexity of $O(n|m|+\kappa n^2)$ using only collision-resistant hash functions [10], improving upon the algorithm by Cachin and Tessaro. The downside of this algorithm is that it has a higher computational cost and is not balanced. As stated in §4.2, when using a commitment scheme such as KZG [18] instead of Merkle proofs in the algorithm by Cachin and Tessaro, the same communication complexity can be attained without sacrificing the balanced nature of the algorithm and without inducing a higher computational cost. The downside is that a trusted setup and an additional cryptographic assumption is required. Alternatively, the same bound can be achieved using a public key infrastructure and cryptographic accumulators [26]. Threshold signatures can be used to obtain an improved bound on the communication complexity of $O(n|m|+\kappa n+n^2)$ [3].

The constant in the $O(n|m|)$ term is at least $3$ in all of these algorithms. In an effort to improve efficiency for large messages, algorithms have been proposed to bring this constant down, first to $2$ [21] and then to $3/2$ [22, 23], which is conjectured to be optimal. Thus, the best known algorithms come close to the lower bound of $\mathrm{\Omega }(n|m|+n^2)$ [13].

The reliable broadcast problem has been studied in a variety of models. It has been shown how stochastic sampling can be used to obtain a probabilistic algorithm violating each property with a fixed probability [16]. Moreover, reliable broadcast has also been considered in a model with dynamic membership [15]. The efficacy when combining Bracha’s algorithm with Dolev’s reliable communication protocol [12] to broadcast messages reliably in partially connected networks has been analyzed using simulations [5]. Lastly, the problem that composing $n$ parallel reliable broadcast instances can lead to non-termination has also been addressed, proposing quit-resistant reliable broadcast enabling parties to quit early [25].

Existing reliable broadcast algorithms are not efficient in failed executions in the worst case. In this paper, the concept of detectors is introduced, supporting reliable broadcast algorithms in keeping the communication complexity low in the failure case. Detectors further have powerful properties that facilitate the design of reliable broadcast algorithms. Moreover, they can reduce or even eliminate redundant transmissions in the absence of faults, which may prove to be relevant in practice. A reliable broadcast algorithm has been presented that makes use of a detector, achieving an overhead factor of $2+O(1/n)$, which is nearly optimal when considering algorithms where the sender broadcasts the message first. However, there is still a gap between the achieved bound and the lower bound of $5/3$ that can be explored. Another open question is whether a lower overhead factor can be obtained when the sender disperses the message to a strict subset of the nodes. Since fewer nodes obtain the message in this step, this modification increases the onus on the honest nodes to ensure that every node obtains the message eventually. These questions may be addressed in future research.