Good-case early-stopping latency of synchronous byzantine reliable broadcast: the deterministic case

This paper considers the good-case latency of Byzantine Reliable Broadcast (BRB), i.e., the time taken by correct processes to deliver a message when the initial sender is correct. This time plays a crucial role in the performance of practical distributed systems. Although significant strides have been made in recent years on this question, progress has mainly focused on either asynchronous or randomized algorithms. By contrast, the good-case latency of deterministic synchronous BRB under a majority of Byzantine faults has been little studied. In particular, it was not known whether a good-case latency below the worst-case bound of \(t+1\) rounds could be obtained. This work answers this open question positively and proposes a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of \(\textsf{max} (2,t+3-c)\) rounds (or equivalently \(\textsf{max} (2,f+t+3-n)\)), where t is the upper bound on the number of Byzantine processes, \(f\le t\) the number of effectively Byzantine processes, and \(c=n-f\) the number of effectively correct processes. The proposed algorithm does not put any constraint on t, and assumes an authenticated setting, in which individual processes can sign the messages they send, and verify the authenticity of the signatures they receive.

Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.

1. In this paper, we will tend to conflate the two problems, as the protocols we discuss solve both BB and BRB.

2. In addition, these randomized solutions generally assume a weakly adaptive adversary an adversary that cannot erase messages sent “just before” a process becomes Byzantine, where “just before” means in the same round. A notable exception is the solution presented in [33], which tolerates a strongly-adaptive adversary by exploiting time-lock puzzles. By contrast, a deterministic algorithm that tolerates Byzantine processes inherently tolerates a strongly-adaptive adversary, i.e., an adversary which can remove messages “after the fact”.

3. f and c are equivalent, as \(c=n-f\). This paper tends to use c as it leads to more compact formulas.

4. ‘Deterministic’ is used here with the meaning usually accepted in the distributed algorithm community, i.e. to indicate that the local behavior of processes can be modeled by a deterministic input/outpout automaton, where input and output correspond to the sending and receiving of messages and (in the context of synchronous algorithms) to the progress of rounds. This work also assumes, however, a perfect signature scheme. The notion of determinism does not cover the concrete working of this scheme, which, in practice, would generally rely on some source of randomness to provide encryption and signatures.

5. More precisely, this expected number of rounds can be broken down into a deterministic number of synchronous rounds followed by an expected number of asynchronous rounds. The exact breakdown depends, in turn, on the choice of shared random coin used in the algorithm.

6. Although correct processes can deliver their message in about \(2\times n/(n-t)\) rounds in this optimized algorithm, they must continue to participate in the algorithm for about the same amount of time, leading to an overall execution time of circa \(4\times n/(n-t)\) rounds in good-cases.

7. The extra round of communication induced by \({ delivered}_i\) is needed to ensure all correct processes observe the same predicate \(\textsf{WBP} \) as \(p_i\). However, by delivering as soon as the condition of line 8 is true, the algorithm does not ensure that crashed processes benefit from the brb-No-duplicity and brb-Global-delivery properties. These additional guarantees can be provided at the cost of one extra round by postponing the brb-delivery of m by one round from line 9 to line 4.

8. Taking into account the worst case latency, the algorithm’s good-case latency can be written as \(\textsf{min} \big (t+1,\textsf{max} (2,\lambda _\textsf{good})\big )\).

9. Detailed examples that illustrate the importance of this revealing chain can also be found in Appendix A.3, where we discuss possible optimization to reduce the communication complexity of the algorithm.

10. For simplicity, we say that a process p signed m during round r in \({ view}\) to mean that \({ view}\) contains a chain backing m in which p’s signature appears in r^th position. Formally, both formulations are equivalent for correct processes, but they are not for Byzantine processes, as they can sign chains whenever they wish or even use the signature of other Byzantine processes.

11. For instance, some works limit the communication power of Byzantine nodes using a Proof-of-Work mechanism under the assumption that individual processes can solve cryptographic puzzles at a limited rate [6, 25].

12. When \(R_{\textrm{end}} \le t\), Algorithm 2 brb-delivers in round \(R_{\textrm{end}}\), but also executes one extra round of communication (through the \({ delivered}_i\) variable). This extra round leads to a total of at most \(R_{\textrm{end}} +1\) rounds of communication: the first round followed by \(R_{\textrm{end}} \) subsequent rounds.

13. The width of a partially order set (or poset) \((S,<_s)\) is the largest antichain of S, i.e. the largest subset \(X\subseteq S\), such that no pair of elements of X can be compared using \(<_s\).

The authors would like to warmly thank the anonymous reviewers who commented on earlier versions of this work. Their thoughtful and constructive feedback has helped us improve this paper’s presentation and content.

This work was partially funded by the French ANR project ByBLoS (ANR-20-CE25-0002-01), and by the PriCLeSS project granted by the Labex CominLabs excellence laboratory of the French ANR (ANR-10-LABX-07-01).

Authors and Affiliations

1. Univ Rennes, IRISA, CNRS, Inria, 35042, Rennes, France

   Timothé Albouy, Davide Frey, Michel Raynal & François Taïani

Corresponding author

Correspondence to François Taïani.

Conflict of interest

The authors have no competing interests to declare that are relevant to the content of this article, apart from those possibly resulting from the funding sources mentioned above.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A first version of this paper was initially published at the 36th Int. Symposium on Distributed Computing (DISC 2022) [5].

A communication complexity: analysis and improvements

Because our algorithm focuses on latency, we have left aside communication complexity so far, but this would be the next aspect to consider. First off, it should be noted that the communication cost of a distributed algorithm can be approached from two perspectives, by considering two distinct metrics:

• Metric 1: The number of messages sent by correct processes,

• Metric 2: The size of individual messages sent by correct processes.

These two metrics only measure the communication cost of correct processes. This is because, without further assumptions,^{Footnote 11} Byzantine processes may send a potentially infinite amount of messages with a potentially infinite amount of information. The two metrics can be combined in one single metric: the total amount of information sent in the network by correct processes (Metric 3). But to approach the problem in a more granular manner, it is helpful to consider these two metrics separately. Moreover, in a practical implementation, it is often more desirable to reduce the number of messages (Metric 1) than the size of messages (Metric 2), as each new message often necessitates negotiating a new network connection (e.g., a TCP session between two endpoints) which entails a significant communication overhead. In other words, having a few large messages is often better than having a lot of small messages.

In the following, “the algorithm” refers to Algorithm 2 in which we use the \({\textsf{WBP}}_{\textsf{GCL}}\) predicate described in Algorithm 3.

1.1 A.1 Metric 1: Number of messages

The proposed algorithm follows the original BRB algorithm of Lamport, Shostak, and Pease and adopts a full-knowledge dissemination strategy: correct processes forward any signature chain they have not signed yet. This is not very efficient, and as a result, in each round, each correct process sends n messages (1 unreliable broadcast). For simplicity’s sake, we will ignore the border case where a process cannot sign any new chain. This assumption leads to a worst-case collective message cost for correct processes of n messages in round 1, and \(c \times n\) messages in each later round, which adds up to \(n+ c \times n \times R_{\textrm{end}} \) messages (at most), where \(R_{\textrm{end}}\) is the maximum number of rounds needed for the algorithm to brb-deliver messages at correct processes.^{Footnote 12} This upper bound can be further refined depending on whether the execution occurs in a good or bad case.

1.1.1 A.1.1 Good case (correct sender)

In a good case, we have \(R_{\textrm{end}} = \textsf{max} (2,t+3-c)\), but the initial sender (which is correct) only participates in the first round. These two observations lead to at most \(n + (c-1) \times n \times \textsf{max} (2,t+3-c)\) messages sent by correct processes, which boils down to \(n + 2\times n \times (n-1) = O(n^2)\) messages when all processes are correct (\(c=n\), assuming \(n>t\)).

1.1.2 A.1.2 Bad case (Byzantine sender)

In a bad case, we have at worst \(R_{\textrm{end}} =t+1\). When \(R_{\textrm{end}} =t+1\), however, correct processes do not execute any extra round of communication (see Footnote 12). This leads to at most \(n + (c-1) \times n \times (t+1)\) messages sent by correct processes. If one assumes c and t are of the order of n, the overall message complexity is thus in \(O(n^3)\).

1.2 A.2 Metric 2: Size of messages, and Metric 3: Overall communication cost

We capture the size of a message by counting how many “information items” it contains. Because the size of the fixed-size fields of a message (e.g., its application payload) becomes asymptotically negligible compared to its fields of variable size (e.g., a set of signatures), we equate this number of “information items” with the number of elements in the fields of variable size. In the case of our algorithm, this number of “information items” would be the number of signatures in all of the chains contained in a message.

In the proposed algorithm, message size contributes heavily to communication costs. If we assume the application payload (the application message m that is brb-broadcast and brb-delivered) is fixed in size, the size of the network messages the algorithm sends is dominated by the number of signatures they contain. This is because messages keep growing in size at every round, as the number of chains in each message and the length of each chain keep increasing.

Let us, therefore, count the number of signatures exchanged in each round. A chain exchanged in round R must contain R signatures. In round \(R\ge 2\), a process \(p_i\) can have no more than

such chains that need to be disseminated (since these chains must start by \(p_{\textrm{sender}}\) ’s signature, must end with \(p_i\)’s signature, and are acyclic).

1.2.1 A.2.1 Good case (correct sender)

In a good case, in round \(R \ge 2\), the chains of length R that a correct process needs to disseminate contain no more than \(R \times \frac{(n-2)!}{(n-R)!}\) signatures. As a correct process sends this set to all other processes during round \(R\ge 2\), collectively, correct processes cannot send more than \((c-1) \times n \times R \times \frac{(n-2)!}{(n-R)!}\) signatures during a round, which is upper bounded by \((c-1) \times n \times R \times (n-2)^{R-2}\), yielding an upper bound on the overall signature complexity for the algorithm of

In the general case, if one assumes \(t=\alpha n\) and \(c=(1-\alpha )n\) for some \(\alpha \in ]0.5,1[\), the above expression yields a loose upper bound on the overall signature complexity of the algorithm (Metric 3) in \(O\big (n^{(2\alpha -1)n+5}\big )\), which is over-exponential, and very costly.

When all processes are correct (\(c=n\), which implies that the algorithm terminates in 3 rounds: 2 for all processes to brb-deliver, plus one for broadcasting a final message, see Footnote 12), Eq. (10) adds up to an overall communication complexity of no more than \(n + 2n(n-1) + 3n(n-1)(n-2) = O(n^3)\) signatures. Assuming that signatures are of size \(O(\kappa )\), where \(\kappa \) is some security parameter, and considering that the identifier of individual signatories needs to be transmitted with each signature, the above signature complexity yields an overall communication complexity measured in bits of \(O(\kappa n^3\log n)\).

1.2.2 A.2.2 Bad case (Byzantine sender)

In a bad case, and without any further protection (see the next section), a Byzantine sender may spam the system with an arbitrary number of application messages (the BRB’s payload), with each message incurring its own cost in signatures, the communication cost of the algorithm as presented is essentially unbounded.

1.3 A.3 Optimizations

1.3.1 Partition-based filtering

Because the \({\textsf{WBP}}_{\textsf{GCL}}\) predicate revolves around the number of processes that back an application message m in round 1 or 2, one could be tempted to limit the number of chains that each correct process disseminates by partitioning the chains received at line 5 and 6 according to the message m and the process q backing m at round 2, and to propagate only one representative of each partition. We call this approach partition-based filtering in the following discussion.

Unfortunately, partition-based filtering cannot be applied to the algorithm in its current form. This is because it compromises the WBP-Final-Visibility property, which is required to ensure brb-No-duplicity of the BRB primitive. In the following, we illustrate these two points using example executions.

An example execution represented as a DAG of signature chains. \(p_s\) and \(b_{1,2,3}\) are Byzantine, \(c_{1,2}\) are correct. The paths of the DAG represent chains as they propagate among processes. For instance, the path means that \(c_1\) receives the chain \(m: p_s: b_1: b_2 \) in round 3. The chains signed and propagated by \(c_1\) and \(c_2\) are not shown for clarity. In this example, \(c_2\) must propagate \(m: p_s: b_2: b_3: b_4\) in round 5 for \(c_1\) to eventually observe a certificate of weight 3 for m

Full size image

Partition-based filtering compromises WBP-Final-Visibility Fig. 3 represents an execution of the algorithm as a DAG (Direct Acyclic Graph) in a system with 7 processes, \(p_s\), \(b_1\), \(b_2\), \(b_3\), \(b_4\), \(c_1\), and \(c_2\). The processes \(p_s\), \(b_1\), \(b_2\), \(b_3\), and \(b_4\) are Byzantine (\(t=5\)), while \(c_1\), and \(c_2\) are correct (\(c=2\)). A path in the DAG represents the signing and propagation of chains between processes. For instance, the path indicates that the sending process \(p_s\) signed m and propagated the resulting chain \( m: p_s\) to \(b_1\) in round 1, that \(b_1\) signed this chain and propagated it to \(b_2\) and round 2, and that \(b_2\) signed and propagated it to \(c_1\) in round 3.

The sets \({ view} _{c_{1}}^4\) and \({ view} _{c_{2}}^4\) on the right indicate the local views of the processes \(c_1\) and \(c_2\), respectively, after updating the local variable \({ view} \) at line 5 of Algorithm 2 during round 4. For simplicity, the chains signed and propagated by \(c_1\) and \(c_2\) in round 4 are not shown, as those extend \(m: p_s: b_1: b_2\) and \(m: p_s: b_2: b_1\), and do not influence the weight observed by \(c_1\) and \(c_2\) for m.

In this execution, \(c_1\) and \(c_2\) both hear of m for the first time in round 3, and both receive the same two chains containing m during this third round: \(m: p_s: b_1: b_2\) and \(m: p_s: b_2: b_1\). These two chains only yield a weight of 2 for m, as the largest set W that \(c_1\) and \(c_2\) can construct (either \(\{p_s,b_1\}\) or \(\{p_s,b_2\}\) depending on which revealing chain is picked) only contains 2 processes.

During round 4, however, \(c_2\) receives a third chain (in addition to those disseminated by \(c_1\), not shown, which do not impact the situation) made up of \(\gamma _4 = m: p_s: b_2: b_3: b_4\). This chain is not received by \(c_1\) (as \(b_2\), \(b_3\), \(b_4\) are Byzantine and can choose which correct process they target). As a result, \(c_2\) now observes a weight of 3 for m, by picking this new chain as revealing chain, and constructing a set \(W=\{p_s,b_1,b_2\}\), but \(c_1\) continues to observe a weight of 2 (since the chains forwarded by \(c_2\) during round 4 do not change the maximal weight set it can construct.)

If we assume that correct processes only propagate one representative of each pair (m, q) where q is backing m in round 2, \(c_2\) will unfortunately not propagate the new chain \(\gamma _4: c_2\) to \(c_1\) in round 5 (as it already disseminated \(m: p_s: b_2: b_1: c_2\) in round 4), and \(c_1\) will not able to observe the same weight as \(c_2\) for m, defeating the WBP-Final-Visibility property.

WBP-Final-Visibility is required to ensure brb-No-duplicity The property WBP-Final-Visibility is used in the proof of Lemma 2 (brb-No-duplicity) in order to prevent correct processes from brb-delivering different messages in case of equivocation by the designated sender (i.e., when the sender propagates different messages to different processes.) Equivocation remains, however, detectable in round \(t+1\) even if correct processes only propagate one representative of each pair (m, q) where q is backing m in round 2. One could therefore imagine brb-delivering a non-value in round \(t+1\) (e.g., \(\bot \)) when equivocation is detected to circumvent the need for the WBP-Final-Visibility property in the proof of Lemma 2, and make it possible to apply partition-based filtering.

Unfortunately, even in the case of equivocation, some correct processes might be tricked into brb-delivering early. Such ‘adversarial’ early deliveries make it necessary to propagate the weight associated with each message to other correct processes (which is, in essence, what WBP-Final-Visibility provides), to guarantee that early brb-deliveries remain consistent with the choices made by other correct processes later on. Such a situation is illustrated in Fig. 4.

An example of equivocation in which a first correct process, \(c_1\), brb-delivers some message m early, while the second correct process \(c_2\), detects the equivocation and brb-delivers in round \(t+1\). \(p_s\) and \(b_3\) are Byzantine (\(t=2\)), \(c_1\) and \(c_2\) are correct. The figure uses the same DAG representation of signature chains as in Fig. 3 above

Full size image

Figure 4 uses the same DAG representation as Fig. 3, and involves four processes: \(p_s\) (the designated sender) and \(b_3\) are Byzantine, while \(c_1\) and \(c_2\) are correct (\(t=2\), \(c=2\)). In round 1, \(p_s\) disseminate a first message m to \(c_1\) and \(c_2\), and a message \(m'\) to \(b_3\). \(c_1\) and \(c_2\) continue signing and propagating the chain \(m: p_s\) in round 2, producing and observing the chains \(m: p_s: c_1\) and \(m: p_s: c_2\). As a result, both \(c_1\) and \(c_2\) observe a weight of 3 for m in round 2 (with a weight set of \(W_m=\{p_s,c_1,c_2\}\), shown in green in the figure, using any of the two previous chains as revealing chain). Because \(c_1\) does not detect any other message than m, and because \(\mathsf {reveal\_round} _{\textsf{GCL}} (3)=t+3-3=2\), it brb-delivers m, as the condition of line 8 of Algorithm 2 is met.

\(c_2\) by contrast also receives the chain \(m': p_s: b_3\) in round 2 (as \(b_3\) is Byzantine, it does not send this chain to \(c_1\)). As a result, \(c_2\) detects an equivocation and does not deliver m in round 2. \(c_2\) resolves the conflict between m and \(m'\) at round \(t+1=3\) (not shown). When it does however, \(c_2\) cannot deliver \(\bot \), or use a deterministic choice function on \(\{m,m'\}\) (which might return \(m'\).) Instead, \(c_2\) must use the weight of m (3) to prioritize it over \(m'\) and brb-deliver the same message as \(c_1\).

1.3.2 A.3.2 Conflict-based filtering

When the sender is Byzantine, correct processes can limit the chains they propagate for conflicting messages when they receive two messages backed by the same sequence of processes, \(m:\gamma \) and \(m':\gamma \), in the same round. In such a case, correct processes can systematically drop both chains. With this change, any correct process receiving \(m:\gamma \) and \(m':\gamma \) would know that all processes contained in \(\gamma \) are Byzantine (since they all have forwarded two different messages backed by the same sequence of processes, starting with \(m:p_{\textrm{sender}} \) and \(m':p_{\textrm{sender}} \) received in round 1). Using this optimization, even in bad cases (i.e., when the sender is Byzantine), the number of chains re-transmitted in round R by a correct process is upper bounded by \(\frac{(n-1)!}{(n-R)!}\). The algorithm’s communication complexity falls back to that discussed in Sect. A.2.1, except the bound of \(O\big (n^{(2\alpha -1)n+5}\big )\) signatures now holds in both good and bad cases.

1.3.3 A.3.3 Set-based filtering

The partition-based filtering introduced in Sect. A.3.1 seeks to limit the dissemination of redundant information. Although partition-based filtering is too aggressive for the proposed algorithm, this intuition can be applied to chains that can be safely shown to have no impact on the behavior of other correct processes.

More precisely, a correct process \(p_i\) can ignore a chain \(m:p_{\textrm{sender}}: p_k:\gamma \) if it has already received a chain \(m:p_{\textrm{sender}}: p_k:\gamma '\) with \(\textsf{set} (\gamma ')\subseteq \textsf{set} (\gamma )\). This optimization works because \(m:p_{\textrm{sender}}: p_k:\gamma \) cannot improve any weight predicate observed by \(p_i\) for m. \(p_k\) has already been observed by \(p_i\) as signing m in round 2, and \(m:p_{\textrm{sender}}: p_k:\gamma \) will always be a worse revealing chain than \(m:p_{\textrm{sender}}: p_k:\gamma '\) when computing the \({\textsf{WBP}}_{\textsf{GCL}}\) predicate.

This intuition can be formalized by introducing the order relation \(\prec \) between chains that back a message m, defined as follows

Using this optimization, the number of distinct chains that a correct process might propagate during an execution for a pair \((m,p_k)\) where \(p_k\) is backing m in round 2 is bounded by the size of the largest set of subsets of processes of size at most \(n-2\) that cannot be compared by inclusion, i.e., the width of the partially order set^{Footnote 13}\((\{0,1\}^{n-2},\subseteq )\), where \(\{0,1\}^{n-2}\) represents the power set of \(\Pi \setminus \{p_{\textrm{sender}},p_k\}\).

Using Sperner’s theorem [32], the width of \((\{0,1\}^{n-2},\subseteq )\) is \({n-2 \atopwithdelims ()\lfloor n/2 \rfloor -1}=O\big (2^{n}/\sqrt{n}\big )\). For a given message m, as there are \(n-1\) possible backers in round 2, the total number of chains propagated by a correct process \(p_i\) for a given message m during an execution becomes \(O\big (\sqrt{n}2^{n}\big )\). As individual chains contain no more than n signatures, the number of signatures disseminated for each application message m by a correct process \(p_i\) is bounded by \(O\big (n^{\frac{3}{2}}2^{n}\big )\), yielding a bound on the overall communication cost of the algorithm (Metric 3) of \(O\big (n^{\frac{5}{2}}2^{n}\big )\) signatures.

If we assume Byzantine processes are rate limited in the number of application messages, they can produce [6, 25], or if we assume the size of the space \(\mathcal {M}\) of application messages is bounded, this becomes an upper bound on the overall communication cost of the protocol in both good and bad cases.

1.3.4 A.3.4 Sets instead of chains of signatures

The weight-based predicate \({\textsf{WBP}}_{\textsf{GCL}}\) (Algorithm 3, Sect. 5.2) does not use the order of the signatures in chains from position 3 to the end, and neither does the Set-based Filtering presented in Sect. A.3.3. (Conflict-based Filtering from Sect. A.3.2, however, does require order information.)

Indeed, the predicate hinges on the cardinality of the set of signatures W (rather than some sequence of signatures), and the construction of W depends on the interplay of signatures present in the first two rounds and those present from round 3 and later. Similarly, the \(\prec \) relation defined in Eq. (11) compares sets rather than sequences. As a result, instead of a chain, every signature from position 3 to the end could be bundled in a set that does not preserve the order.

Using sets of signatures would enable multisignature schemes (such as BLS [12]), which make it possible to aggregate multiple digital signatures in one single fixed-size structure, thus further reducing message sizes. An important caveat is that, even with multisignatures, the message must still contain the identity of all signatories to verify its authenticity. As a result, although the number of “authenticators” [2] is reduced, the number of “information items” remains the same.

1.4 A.4 Security implication of the communication complexity

The algorithm proposed in this paper assumes a perfect signature scheme that cannot be forged. However, practical signature schemes typically require that the computing power of (Byzantine) processes be \(\textrm{poly}(\kappa )\)-bounded to ensure that signatures remain secure with high probability, where \(\kappa \) is some security parameter that captures the strength of the signature scheme (and in terms of information complexity usually translates into signatures of size \(O(\kappa )\)).

Unfortunately, the need for \(\textrm{poly}(\kappa )\)-bounded processes does not sit well with the fact that individual processes need to handle a number of signatures that are either over-exponential (using conflict-based filtering, Sect. A.3.2) or exponential in O(n) (using set-based filtering, Sect. A.3.3). In practice, this implies that \(\kappa \) and n must be chosen so that processes are \(\textrm{poly}(\kappa )\)-bounded while remaining able to process a number of signatures in \(O\big (n^{\frac{3}{2}}2^{n}\big )\) (assuming the set-based filtering optimization is used). This is unsatisfactory, and it might be possible to further optimize the communication complexity while retaining the key properties of our algorithm. How this can done, and whether some tight bound on the communication complexity can be obtained remain open problems.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions