Byzantine Reliable Broadcast with
Low Communication and Time Complexity

The goal of Byzantine reliable broadcast is to disseminate a message efficiently and reliably despite the presence of Byzantine nodes that may interfere with the protocol execution in arbitrary ways. A reliable broadcast routine is a powerful primitive with a broad range of applications including asynchronous atomic broadcast [15, 19, 18, 21, 27], distributed key generation [2, 12, 20], secure data replication [8], and secret sharing [26]. Moreover, Byzantine reliable broadcast plays a pivotal role in Byzantine fault-tolerant consensus protocols where message dissemination is treated separately from message ordering to improve throughput [10].

The first Byzantine reliable broadcast algorithm is due to Bracha [6]. While it is elegant in its simplicity, its main drawback is that the message $m$ is broadcast by every node during the execution of the algorithm, i.e., $O(|m|n^2)$ bits are sent overall, where $|m|$ denotes the size of $m$ in bits and $n$ is the number of nodes in the network. In the seminal paper by Cachin and Tessaro [9], this bound was improved to $O(|m|n+\kappa n^2\log (n))$ bits using erasure coding, where $\kappa$ is the output size of a collision-resistant hash function. Since each node must receive the message in a successful broadcast, this result is asymptotically optimal if $|m|\in \mathrm{\Omega }(\kappa n\log (n))$. Subsequent work has primarily focused on getting closer to the lower bound of $\mathrm{\Omega }(|m|n+n^2)$ [1, 4, 11, 22, 23]. These pieces of work follow the blueprint laid out by Cachin and Tessaro and augment it with error-correction and cryptographic primitives to achieve better asymptotic bounds.

Curiously, there is little work on minimizing the constant in the $O(|m|n)$ term, although it likely dominates the actual bandwidth consumption in practice and is therefore crucial for real-world applications. The design by Cachin and Tessaro is based on a $(n,t+1)$-erasure code, where is the largest number of nodes that may exhibit Byzantine behavior. In this design, nodes broadcast encoded fragments of size $|m|/(t+1)\approx 3|m|/n$ instead of broadcasting $m$, sending at least $3|m|n$ bits altogether. An overhead factor of $3$ – compared to the ideal scenario where each node receives exactly $|m|$ bits – may already prove too costly for applications with strict bandwidth constraints. All schemes that follow this approach naturally inherit the overhead inherent in this design.

In this paper, a mechanism is introduced that departs from this blueprint in order to reduce the communication complexity, i.e., the number of bits that need to be exchanged in the worst case, for large messages. The core idea is quite simple: a $(n,2t+1)$-erasure code is used instead, reducing the fragment size to $|m|/(2t+1)\approx \frac{3}{2}|m|/n$. This modification obviously reduces the cost of broadcasting fragments; however, correctness is no longer given without additional changes because some nodes may receive $2t+1$ fragments whereas others merely obtain $t+1$ fragment, which is not enough to recover the message. This problem is addressed by introducing the following step. If a node with $2t+1$ fragments manages to reconstruct the message, it disseminates fragments again but only to the $t$ nodes from which no fragment was received. As we will see, this step is sufficient to ensure correctness while keeping the communication complexity low.

As an added benefit, the transition from a $(n,t+1)$-erasure code to a $(n,2t+1)$-erasure code results in substantial performance improvements, both with respect to the encoding and decoding of fragments. Figure 1 shows performance numbers when encoding/decoding an input of size 1 MiB for various network sizes and the two different parameterizations. The experiments were conducted on an Intel Core i7 CPU with 6 cores and 32 GB of memory using an optimized library¹¹1See https://github.com/AndersTrier/reed-solomon-simd. for Reed-Solomon codes [24]. The figure confirms the practicality of erasure coding due to its efficiency, exhibiting encoding and decoding times in the millisecond range, and scalability with respect to the network size. Moreover, the figure reveals that the encoding (decoding) time is lower by a factor of 2.2–2.4 (1.8–2.0) for all network sizes when using an $(n,2t+1)$-erasure code. Another interesting property is that the variance is also significantly lower, leading to more predictable encoding and decoding times.

The paper is organized as follows. The model is formally introduced in §2. A concrete algorithm that makes use of the novel mechanism is presented in §3. Its communication complexity is $2|m|n$ plus a term independent of $|m|$. Given an honest (i.e., non-faulty) sender, each honest node obtains the message after $3$ rounds of communication. A natural question is whether there is an algorithm with an overhead factor lower than $3$ and that terminates in an optimal $2$ rounds given an honest sender. In §4, this question is answered in the affirmative by presenting an algorithm with this property and the same overhead factor if the sender does not equivocate. Otherwise, the worst-case overhead factor is $\frac{5}{2}$ with respect to the largest fragment size transmitted by honest nodes. While the first algorithm only requires collision-resistant hash functions, the second algorithm makes use of threshold signatures. Both algorithms further bound the number of bits that are stored at each node in the worst case to a small multiple of a predetermined maximum message size. Practical considerations with the goal of reducing the communication complexity further in real-world deployments and simplifying the implementation are discussed in §5. A key observation is that the overhead can be reduced to $\frac{3}{2}$ during periods of synchrony and in the absence of failures. As shown in §6, a lower overhead factor than $\frac{3}{2}$ cannot be guaranteed for a particular class of algorithms. Related work is summarized in §7 before the paper concludes in §8.

The considered network comprises $n=3t+1$ nodes, where $t$ denotes the maximum number of Byzantine nodes, which may deviate arbitrarily from any given protocol. The other $2t+1$ nodes faithfully execute the given protocol and are called honest. Any two nodes can communicate directly over an authenticated channel by exchanging messages. Communication is assumed to be asynchronous in the sense that the delivery of messages, while guaranteed, may be delayed indefinitely. In this communication model, nodes cannot make any assumption about message delays, neither about the time required until sent message arrive at their destinations nor about the time that elapses until certain (expected) messages are received.

A node may send a message to a single node or to multiple nodes. When a node $v$ sends a message to all nodes, we say that $v$ broadcasts this message. A faulty node may fail to send messages as specified in the protocol. The goal of reliable broadcast is to ensure, under some conditions, that all honest nodes eventually deliver a certain message, i.e., mark it as the accepted outcome of the reliable broadcast. The required properties of a reliable broadcast protocol are stated formally in the following definition.

In general, nodes may engage in multiple reliable broadcasts in parallel. In this case, the integrity condition effectively requires that messages are attributable to a uniquely identifiable execution context. In the following, we assume that every message implicitly contains an identifier and that each node runs a separate instance of the protocol for each identifier. The sender for a particular execution context is assumed to be globally known.

As mentioned above, the objective is to reliably broadcast some message $m$, where the notation $|m|$ is used to denote the size of the message in bits. Instead of sending $m$, the algorithms introduced in §3 and §4 send fragments of $m$, which can be either chunks of $m$ itself or encoded data derived from $m$. Without loss of generality, we assume that there is some upper bound ${\mathrm{\ell }}_{max}$ on the message size, which in turn limits the fragment size. State-of-the-art algorithms use either erasure codes, which can handle missing data, or error-correcting codes, which support the correction of erroneous data. The algorithms in this paper exclusively use an $(n,k)$-erasure codes with optimal reception efficiency, i.e., exactly $k$ out of $n$ symbols are sufficient to reconstruct a message of $k$ symbols. Throughout this paper, the parameters $n$ and $k$ correspond to the total number of nodes and the number of honest nodes, i.e., $k≔2t+1$. We assume that each node has access to the routine get_fragments that takes a message $m$ as input and returns a list of $n$ fragments of size each. Furthermore, the nodes use the routine recover_message to recover $m$ given any subset $F$ of the $n$ fragments of size $|F|\ge k=2t+1$. This routine is assumed to always return some message, which may simply be a bit string of zeroes in case of an error, e.g., when the input contains fragments of different sizes.

In addition to fragments, the nodes also send hashes, identifiers, and, in the case of the algorithm presented in §4, also signatures and signature shares. The hashes are assumed to be cryptographically strong in the sense that it is infeasible to find hash collisions (except with negligible probability). Naturally, it is also assumed that it is computationally infeasible to spoof signatures or signature shares. Since the cryptographic properties only hold for hashes, signatures, and shares of a certain minimum size, we introduce a security parameter $\kappa$ and define that the size of all data types other than fragments is bounded by $O(\kappa )$.

Reliable broadcast algorithms are evaluated against multiple complexity measures. For a specific number $n$ of nodes and message size $\mathrm{\ell }$, the communication complexity $𝒞(n,\mathrm{\ell })$ of an algorithm is the total number of bits sent by all honest nodes in the worst case assuming fewer than $n/3$ Byzantine nodes. If the sender is Byzantine, we define that $\mathrm{\ell }$ is the message size corresponding to the largest fragment sent by an honest node. Given that at least $n\mathrm{\ell }$ bits need to be transferred and we are concerned with the overhead for large messages, the primary goal is to minimize $ℒ(n)≔{lim}_{\mathrm{\ell }\to \mathrm{\infty }}\frac{𝒞(n,\mathrm{\ell })}{\mathrm{\ell }n}$. Additionally, the time complexity of an algorithm is of great practical importance, measuring the duration of an execution when normalizing the maximum message delay to $1$ time unit. According to Definition 2, an execution with a Byzantine sender may never terminate. Therefore, we restrict our attention to the case where the sender is honest. Due to the validity condition, this good-case time complexity must be bounded. Note that both presented algorithms ensure that the number of communication rounds is also bounded given a Byzantine sender. Lastly, the space complexity is considered as well, which is defined as the number of bits that any honest node stores during the execution of the algorithm in the worst case.

In this section, optimizations that may be relevant for practical applications are discussed.

The preceding section showed that an overhead factor of $\frac{3}{2}$ for large messages can be attained in practice under normal network conditions and in the absence of faults. In this section, we shed light on the question whether we can hope to further improve upon this bound. The question is answered in the negative, at least for a specific but relevant class of algorithms.

The lower bound holds in the synchronous communication model where all nodes perform some computation, send messages, and receive the sent messages within the same round of a bounded and known duration. Furthermore, the lower bounds holds in the crash failure model where a faulty node stops executing at any point during the execution but it never deviates from the correct protocol execution until it fails. In order to utilize the available bandwidth efficiently, it is beneficial to minimize the maximum bandwidth consumption over all nodes. If each node sends the same amount of data up to a constant factor, the algorithm is called balanced [4]. Any imbalance beyond a constant factor is usually due to the sender transmitting more data, typically in the first round. We focus on a broader class of “weakly balanced” algorithms where the sender can send arbitrarily sized messages to other nodes but at most $o(|m|n)$ bits overall in the first round. Note that each node sends $O(|m|+\kappa n\log (n))$ bits in both ${𝒜}_{bit}$ and ${𝒜}_{sig}$.

We further restrict our attention to reliable broadcast algorithms that, given an honest sender, guarantee that all honest nodes deliver $m$ after at most $3$ (synchronous) rounds. This class of algorithms is interesting because it covers ${𝒜}_{bit}$, ${𝒜}_{sig}$, as well as other algorithms in the literature including the algorithm by Cachin and Tessaro.

Formally, a $(b,r)$-reliable broadcast algorithm is defined as a reliable broadcast algorithm that sends messages of size at most $b$ bits in the first round and delivers the message of an honest sender at all honest nodes within at most $r$ rounds. Let $b_j$ denote the bits (of entropy) that the sender sends to $v_j$ in the first round according to the given algorithm in some execution without any failures. As mentioned before, we assume that ${\sum }_{j=1}^n{b}_j\in o(|m|n).$ (1) Let $b_{ij}$ further denote the bits that $v_i$ sends to $v_j$ in rounds $2,\mathrm{\dots },r$ in the same execution. Due to the validity condition and the fact that we consider algorithms with a good-case time complexity of at most $r$, all honest nodes must receive $m$ by the end of round $r$. Let $S_j$ denote the set $\{v_i\in V|b_{ij}>0\}$, i.e., the set of nodes that send some bits to $v_j$. Moreover, let $R≔\{v_j\in V|b_j\ge |m|\}$ denote the set of nodes that receive at least $|m|$ bits in round $1$. Since ${\sum }_{j=1}^n{b}_j\in o(|m|n)$, it must hold that $|R|\in o(n)$. Let ${\overline{b}}_j≔\frac{1}{|S_j|}{\sum }_{i=1}^n{b}_{ij}$ denote the average number of bits sent to $v_j$ from the nodes in $S_j$ in rounds $2,\mathrm{\dots },r$.

In the following, we consider the case $r=3$, which permits a simple strategy to derive a lower bound because a node failing to receive expected messages in the second round can only inform other nodes about the failure in the third round. Requiring a fourth round to send the missing bits violates the requirement that all honest nodes deliver the message by round $3$ in case of a non-faulty sender. Therefore, the strategy is simply to mark those nodes as faulty that send many bits in rounds $2$ and $3$. Given this strategy, it is easy to see that $|S_j|>t$ and ${\overline{b}}_j>0$ must hold for any $v_j\in V\setminus R$ as otherwise $v_j$ may not receive $m$ by the end of round $3$. The following lemma provides a lower bound on ${\overline{b}}_j$ for the case $|S_j|>t$.

As mentioned in §1, the first reliable broadcast algorithm, achieving a communication complexity of $O(|m|n^2)$, was presented by Bracha [6]. An algorithm with a much improved bound of $O(|m|n+\kappa n^2\log (n))$, making use of erasure codes, was published 18 years later by Cachin and Tessaro [9], making use of collision-resistant hash functions of size $\kappa$. By contrast, Bracha’s algorithm is error-free, i.e., it does not rely on any cryptographic assumptions.

Subsequently, error-free reliable broadcast algorithms with lower communication complexity were proposed, guaranteeing bounds of $O(n|m|+n^4\log (n))$ [23] and $O(n|m|+n^3\log (n))$ [22]. While the latter algorithm achieves a lower asymptotic communication complexity, it is not balanced in that a single node, the sender, must transmit more bits than the other nodes. A reliable broadcast algorithm is said to be balanced if all nodes send the same number of bits up to a constant factor [4]. Note that the algorithms presented in §3 and §4 are both balanced. The best known bound for error-free algorithms is $O(n|m|+n^2\log (n))$ [4]. Abraham and Asharov proposed a probabilistic algorithm with a similar bound of $O(n|m|+n^2\log (n^3/\epsilon ))$, guaranteeing validity but the agreement and totality properties only hold with probability $1-\epsilon$ [1].

It has also been shown how to achieve a communication complexity of $O(n|m|+\kappa n^2)$ using only collision-resistant hash functions [11], improving upon the algorithm by Cachin and Tessaro. The downside of this algorithm is that it is not balanced and it has a higher computational cost. Algorithm ${𝒜}_{bit}$ introduced in §3 falls into the category of reliable broadcast algorithms that rely on collision-resistant hash functions as well. There are reliable broadcast algorithms that require other cryptographic primitives. For example, an algorithm has been proposed that achieves a communication complexity of $O(n|m|+\kappa n^2)$ but requires a trusted setup for a public key infrastructure and cryptographic accumulators [22]. This bound has been improved to $O(n|m|+\kappa n+n^2)$ using threshold signatures [4]. The algorithm ${𝒜}_{sig}$ defined in §4 uses threshold signatures to achieve an optimal (good-case) time complexity.