Timothé Albouy

Davide Frey

Michel Raynal

François Taïani

Good-case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case (Extended Version)

Keywords: Byzantine Fault, Deterministic Algorithm, Genericity, Good-Case Latency, Reliable Broadcast, Synchronous System, Weighted Predicate

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 goodcase 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 max(2, t + 3 -c) rounds, where t is the upper bound on the number of Byzantine processes and c the number of effectively correct processes.

Introduction

Introduced in the eighties [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF], Byzantine reliable broadcast (BRB) and Byzantine Broadcast (BB) are two fundamental abstractions of distributed computing [START_REF] Attiya | Distributed computing -fundamentals, simulations, and advanced topics[END_REF][START_REF] Auvolat | Byzantine-tolerant causal broadcast[END_REF][START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Cachin | Introduction to Reliable and Secure Distributed Programming[END_REF][START_REF] Imbs | Trading off t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF][START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF][START_REF] Nayak | Improved extension protocols for Byzantine broadcast and agreement[END_REF][START_REF] Wan | Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions[END_REF][START_REF] Raynal | Fault-Tolerant Message-Passing Distributed Systems -An Algorithmic Approach[END_REF]. BRB assumes that one particular process, the sender, broadcasts a message to the rest of the system and that correct (a.k.a. honest) processes all deliver the value initially broadcast if the sender is correct or that, if it is not, either all agree on some value or none delivers any value. BB further requires that all correct processes always deliver some value. 1 BRB and BB play a crucial role in many practical distributed applications, from state machine replication (SMR) (see, for instance, the discussion in [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF]), to broadcast-based money transfer [START_REF] Auvolat | Money transfer made simple: A specification, a generic algorithm and its proof[END_REF][START_REF] Baudet | FastPay: High-performance Byzantine fault tolerant settlement[END_REF][START_REF] Collins | Online payments by merely broadcasting messages[END_REF][START_REF] Guerraoui | The consensus number of a cryptocurrency[END_REF].

Good-case latency

In broadcast-based money transfer algorithms, for instance, a cryptocurrency is implemented by merely broadcasting the transfer operations originating from one participant (or in some sharded versions [START_REF] Baudet | FastPay: High-performance Byzantine fault tolerant settlement[END_REF] from one authority) to the rest of the system [START_REF] Auvolat | Money transfer made simple: A specification, a generic algorithm and its proof[END_REF][START_REF] Collins | Online payments by merely broadcasting messages[END_REF][START_REF] Frey | Consensus-free ledgers when operations of distinct processes are commutative[END_REF]. These algorithms do not require consensus, and their performance is directly related to the underlying (Byzantine-tolerant) reliable broadcast algorithm they use. Transfers issued by correct participants are guaranteed to terminate and only involve a single broadcast operation invoked by the issuer. As a result, the latency of these algorithms-as experienced by correct participants-solely depends on the good-case latency of the BRB algorithm they use, defined as the time taken for all correct parties to deliver a broadcast message when the initial broadcaster is correct [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF]. The good-case latency of Byzantine-tolerant broadcast algorithms plays a similarly central role in the performance of SMR algorithms, with vast practical consequences for the performance of BFT replication systems, including consortium [START_REF] Abraham | Sync HotStuff: Simple and practical synchronous state machine replication[END_REF][START_REF] Guerraoui | The next 700 BFT protocols[END_REF] and committee-based blockchains [START_REF] Chen | Algorand: A secure and efficient distributed ledger[END_REF].

Synchronous networks In this paper, we focus on the good-case latency of BRB algorithms subject to an arbitrary number of Byzantine failures (i.e., we assume n > t, where n is the number of processes, and t is an upper bound on the number of Byzantine processes). We further assume that processes can use signatures to authenticate messages. We follow in this respect [START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF] and [START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF], and in part [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF]. Since BRB cannot be solved even in a partially synchronous model when t ≥ n/3 [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Marshall | Reaching agreement in the presence of faults[END_REF], we also assume a synchronous network, in which messages are delivered during the same round in which they are sent. Although synchronous wide-area networks are challenging to realize in practice, they can be approximated with high probability by using sufficiently high timeouts. Synchronous algorithms are further intriguing in their own right and can yield insights into the nature of distributed computing that are useful beyond their specific use.

Randomized synchronous BRB algorithms

The study of randomized synchronous BRB and BB algorithms tolerating arbitrary many Byzantine faults has progressed substantially in recent years [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF][START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF]. In particular, the solution proposed by Wan, Xiao, Shi, and Devadas [START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF] and optimized by Abraham, Nayak, Ren, and Xiang [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF] presents sublinear worst-and good-case latency bounds in expectation (boiling down to constant numbers of rounds when t, the maximal number of Byzantine processes, is assumed to be a fraction of n). However, these works all rely on randomization. 2 Further, these works do not leverage a lower number of actual faults to provide an early stopping property [START_REF] Dolev | Early stopping in Byzantine agreement[END_REF]: their latency only involves n, the number of processes, and t, the upper bound on the number of Byzantine processes, but not c, the effective number of correct processes. As a result, they cannot exploit a low number of actual failures to provide better latency performance. This paper's contribution In contrast to randomized solutions, the good-case latency of deterministic synchronous BRB and BB algorithms has been little studied. In the worst case, however, its latency is lower-bounded by t + 1 rounds [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF], and optimal algorithms in this respect have been known since the eighties [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF].

An unsolved question to this date is thus whether a good-case latency lower than t + 1 rounds can be achieved using a deterministic algorithm subject to an arbitrary number of Byzantine faults. This paper answers this question positively and proposes a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of max(2, t + 3 -c) rounds, where t is the upper-bound on the number of Byzantine processes, and c the number of effectively correct processes (c ≥ n -t). The algorithm we propose does not require correct processes to know either n or c. Moreover, and differently from recently proposed solutions to this problem [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF][START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF], our solution:

• is deterministic,

• only relies on signatures, eschewing richer cryptographic primitives (e.g. distributed random coins [START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF], verifiable random functions [START_REF] Micali | Verifiable random functions[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF] or time-lock puzzles [START_REF] Wan | Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions[END_REF]),

• ensures delivery in just 2 rounds in good cases as soon as the effective number of correct processes, c, is at least t + 1, thus improving on all existing solutions.

More generally, our good-case latency is early stopping [START_REF] Dolev | Early stopping in Byzantine agreement[END_REF], in that, in good cases, our algorithm will stop earlier when the effective number of correct processes c increases. This provides a substantial advantage even when c < t+1. For instance, assuming t < 3/4×n, and an intermediate situation where only t/2 processes are effectively Byzantine, the good-case latency of our algorithm outperforms that of the best-known randomized algorithm up to n ≤ 43, and is at least as good up to n ≤ 51, making it competitive in a wide range of small-to medium-scale practical distributed systems.

To construct our solution, we introduce a general family of predicates used to select messages that we have termed weight-based predicates. These predicates exploit patterns in signature chains to help correct processes decide when they can safely deliver a message, thus extending an idea as old as the problem itself [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF]. We formally define this predicate family, and present a generic BRB algorithm that exploits its properties. We then show how Lamport, Shostak and Pease's seminal BRB algorithm [START_REF] Lamport | The Byzantine generals problem[END_REF] can be re-interpreted as a specific instance of our generic construction, and finally present our novel solution as a more advanced example with stronger properties, which yield our much-improved good-case latency.

Background and Related Work

The Synchronous Byzantine Reliable Broadcast problem was first introduced in [START_REF] Marshall | Reaching agreement in the presence of faults[END_REF] by Lamport, Shostak, and Pease, who proposed in [START_REF] Lamport | The Byzantine generals problem[END_REF] a deterministic solution based on signature chains. This solution requires t + 1 rounds (both in good and bad cases), where t < n is an upper bound on the number of Byzantine processes present in the system. This worst-case round complexity was shown by Dolev and Strong [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF] to be optimal for deterministic algorithms. This result was later refined by Dolev, Reischuk, and Strong who showed that min(n -1, n -c + 2, t + 1) rounds are necessary to realize Synchronous Byzantine Broadcast [START_REF] Dolev | Early stopping in Byzantine agreement[END_REF], where c ≥ n -t is the effective number of correct processes in a given run. They also present in the same paper a deterministic signature-free algorithm that achieves this bound provided that n > max(4t, 2t 2 -2t + 2). The salient properties of this algorithm are summarized in the first column of Table 1 and compared to more recent works and to this paper (last column).

In recent years, substantial progress has been achieved to circumvent the hard bound of t + 1 rounds for deterministic BRB and BB algorithm by exploiting randomization. Assuming a majority of Byzantine processes, Fitzi and Nielsen proposed in [START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF] a randomized algorithm that achieves Byzantine Agreement in an expected number of (3t -n)/2 + 7 + O(1) rounds3 , and a good-case latency of (3t -n)/2 + 6 deterministic rounds.

In 2020, Wan, Xiao, Shi, and Devadas presented a randomized algorithm that achieves BB in O ( n n-t ) 2 expected synchronous rounds [START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF]. Last year, in an in-depth study of the good-case latency of BB and BRB algorithms [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF] (extended version in [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF]), Abraham, Nayak, Ren, and Xiang proved a lower bound of n/(n -t) -1 rounds for the good-case latency of synchronous BRB. They then explained how the solution presented in [START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF] can be optimized to deliver a good-case latency of n/(n -t) + n/(n -t) rounds (about 2n/(n -t) ± 1). The properties of these earlier works are summarized in Table 1, together with those of the algorithm we propose. Among these works, only [START_REF] Dolev | Early stopping in Byzantine agreement[END_REF] is deterministic. It imposes, however, a strong constraint on n (n > max(4t, 2t 2 -2t+2)) and does not tolerate a majority of Byzantine processes, which the other algorithms do. Conversely, the algorithms of [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF][START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF] all tolerate an arbitrary number of Byzantine processes, but contrary to the solution we present, they rely on randomization and do not exploit executions in which the number of Byzantine processes is less than the upper bound t. (They are not early stopping.)

4 max(4t, 2t 2 -2t+2) - - - Worst-case latency min(n-c+2, t+1) max(7, 3t-n 2 +7)+O(1) * O ( n n-t ) 2 * t + 1 Good-case latency 2 max(6, 3t-n 2 + 6) n n-t + n n-t max(2, t+3-c)
3 Computing Model and Specification

System Model

Process Model The system consists of n synchronous sequential processes denoted Π = {p 1 , ..., p n }. Each process p i has an identity; all the identities are different and known by all processes. To simplify, we assume that i is the identity of p i .

Regarding failures, up to t processes can be Byzantine, where a Byzantine process is a process whose behavior does not follow the code specified by its algorithm [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Marshall | Reaching agreement in the presence of faults[END_REF]. Let us notice that Byzantine processes can collude to fool non-Byzantine processes (also called correct processes). Let us also notice that, in this model, the premature stop (crash) of a process is a Byzantine failure. The integer c denotes the number of processes that effectively behave correctly in an execution. Both c and n remain unknown to correct processes, but they are used to analyze the properties of our algorithm.

Network Model Processes communicate by exchanging messages through a reliable synchronous network, in which messages are delivered in the round in which they were sent.

Security Model Like earlier works in this area [START_REF] Dolev | Early stopping in Byzantine agreement[END_REF][START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Marshall | Reaching agreement in the presence of faults[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF], we assume a PKI (Public Key Infrastructure) that provides an ideal signature scheme. Processes can sign the messages they send, verify signatures, and forward content signed by other processes.

Byzantine Reliable Broadcast

Following [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF][START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF], we consider a one-shot Byzantine-tolerant reliable broadcast (BRB for short) in which the sending process p sender is known beforehand. The BRB abstraction provides two operations, brb_broadcast and brb_deliver. brb_broadcast(m) is invoked by the sending process p sender . When this happens, we say that p sender brb-broadcasts m. When a process p i invokes brb_deliver(m) we say that p i brb-delivers m. The BRB abstraction is specified by the following five properties.

• Safety:

-BRB-VALIDITY: If a correct process p i brb-delivers a message m and p sender is correct, then p sender has brb-broadcast m.

-BRB-NO-DUPLICATION: A correct process p i brb-delivers at most one message.

-BRB-NO-DUPLICITY: No two different correct processes brb-deliver different messages.

• Liveness:

-BRB-LOCAL-DELIVERY: If p sender is correct and brb-broadcasts a message, then at least one correct process p j eventually brb-delivers some message.

-BRB-GLOBAL-DELIVERY: If a correct process p i brb-delivers a message, then all correct processes brb-deliver a message.

A Generic BRB Algorithm Based on Weight-based Predicates

The BRB algorithm introduced in this paper exploits patterns in sets of signature chains to detect when a (correct) process can safely brb-deliver a message m earlier than the worst-case latency t + 1. We introduce this new algorithm in two steps: in this section, we first present a family of predicates used to select and rank messages and a generic BRB algorithm based on this predicate family that is designed to provide interesting good-case latency values. In the next section, we then define a particular predicate belonging to this family that achieves a good-case latency of max(2, t + 3 -c) rounds when used in the generic algorithm of this section.

The family of predicates we introduce exploits weights to create a hierarchy between potential candidate messages, and relies on two central properties, conspicuity and final visibility, that allow correct processes to brb-deliver a message early yet safely in favorable circumstances. In the following, we define the properties predicates belonging to this family must fulfill, show that these properties are sufficient to implement BRB with our generic algorithm (Theorem 1), and finally illustrate how Lamport, Shostak, and Pease's (BRB-LSP in the following) seminal algorithm can be seen as a specific example of our generic construction.

Underlying intuition

Signature chains The original BRB-LSP algorithm uses signature chains to propagate what each process knows of the system's state [START_REF] Lamport | The Byzantine generals problem[END_REF]. A signature chain (or chain for short) starts with a message m signed by the sending process, e.g. (m, i sender , σ p sender ), where i sender is the identity of the sending process, and σ p sender is a signature of (m, i sender ) with p sender 's private key. Such a chain is of length 1, as it contains one signature. A chain of length is extended by appending the identity i +1 of a process p i +1 not present in the chain, followed by p i +1 's signature of the resulting sequence:

(m, i sender , σ p sender , i 2 , σ p i 2 , .., i , σ p i , i +1 , σ p i +1 ).
As in [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF], we use the compact notation m:p sender :p i 2 :..:p i +1 to represent such a chain.

Valid chains

In BRB-LSP [START_REF] Lamport | The Byzantine generals problem[END_REF], further formalized in [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF], and algorithms based on the same idea [START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF], correct processes only accept valid signature chains, i.e., signature chains that are acyclic and whose length matches the current round. These conditions constrain the disruption power of Byzantine processes by limiting how long they can hide a message from correct processes. In [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF], a message is considered for brb-delivery when backed by at least one chain containing t + 1 signatures: the length of the chain (t + 1) ensures that Byzantine processes cannot reveal some message m to only a subset of correct processes, while hiding it from others, and thus guarantees that all correct processes use the same set of messages to decide which message should be brb-delivered (using a deterministic choice function).

From chains to weight-based predicates The generic algorithm proposed in this paper generalizes this intuition in a simple, albeit non-trivial, way. Instead of single chains, our algorithm detects sets of chains forming a particular pattern to trigger delivery. Ideally, such a pattern should allow correct processes to brb-deliver early in good cases, while remaining safe in bad ones. To fulfill this goal, our algorithm adopts the same sign-and-retransmit strategy as BRB-LSP. This means that, in a good case execution, p sender signs a unique message m, and this message is necessarily repeated in round 2 by the c -1 remaining correct processes, totalling at least c signatures "backing" m by the end of round 2 (that of p sender in round 1, and the other c -1 correct processes in round 2). Although correct processes do not know c (they only know the lower bound n -t), they can thus assign a weight to each message m they observe, depending on the "amount" of backing this message is perceived to enjoy from other processes.

Our intuition consists in combining this notion of weight with the temporal information provided by synchronous rounds to obtain a safe yet good-case-ready weight-based predicate. Such a weight-based predicate serves to select candidate messages for delivery, while the perceived weight of a message serves to discriminate between competing messages when p sender is Byzantine. The crux of the problem lies in ensuring that a message m selected by this predicate and brb-delivered early by a correct process p will trump (thanks to its weight) any other potential competitor m that might surface in later rounds. We solve this difficulty by requiring two properties from a weight-based predicate:

• A weight-based predicate should be conspicuous, in the sense that if a process p observes a predicate of weight w for a message m, m should necessarily have become visible to all correct processes at or before a specific revealing round that only depends on w, and n, t. By contrapositive, this property allows correct processes to conclude to the nonexistence of a predicate of weight w for a message m if they have not heard of m after this revealing round, and is thus instrumental to determining that a message m cannot be beaten by any other.

• A weight-based predicate should also be finally visible, meaning that if p perceives a predicate of weight w for m, all other correct processes should also observe a predicate of weight w for m at the latest by round t + 1.

In good cases, the conspicuity and final visibility of a weight-based predicate make it possible for a process p that envisages to brb-deliver a message m to know that (i) no other message can beat m in terms of weight (by waiting until the corresponding revealing round for m's weight), and (ii) that all correct processes will also assign a weight of w to m at the latest by round t + 1 (thus ensuring that they will also brb-deliver m). In bad cases, conspicuity prevents Byzantine processes from tricking a correct process into delivering early while revealing contradictory information to other correct processes in later rounds, and final visibility guarantees that correct processes observe the same (weight,message) pairs in the final t + 1 round, ensuring agreement.

The rest of this section The remainder of this section, first introduces a few notations that we use to manipulate (sets of) signature chains and messages (Section 4.2). The generic synchronous BRB algorithm (Algorithms 1 and 2) and the weight-based predicates it relies on are described in Section 4.3. We then formalize the properties that weight-based predicates and their revealing functions must fulfill for our generic algorithm to implement BRB (Section 4.4), a connection that is captured by Theorem 1 (Section 4.5). Finally, to illustrate the generality of the proposed algorithm, we show that BRB-LSP can be interpreted as a special case of our generic construction (Section 4.6).

Notations

We use the following notations:

• m:p i 1 :p i 2 : • • • :p i is a chain of signatures (or chain for short) as in [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF][START_REF] Fitzi | On the number of synchronous rounds sufficient for authenticated Byzantine agreement[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF]. We say that the length of the chain is . A valid chain must start with p sender (i.e. p sender = p i 1 ), only contain valid signatures, and be acyclic (a process' signature can only appear once in a given chain). As in [START_REF] Dolev | Authenticated algorithms for Byzantine agreement[END_REF], we assume a filter function removes any invalid chain from the reception queue of correct processes, so that correct processes only receive valid chains. In particular, correct processes will only accept chains of length R during round R. As a shortcut, we might therefore say that a process p i has signed a chain π in round R to mean that p i 's signature is the R th signature in π.

• π being a chain of signatures, message(π) denotes the message at the start of the chain. We therefore have message(m:p sender :p i 2 :

• • • :p i ) = m. By extension, if E is a set of chains, message(E)
is the direct image of E by message().

• M being a set of messages, choice(M ) deterministically returns one of the messages, i.e., the same message m is returned by all correct processes for the same input set M . The function choice() can be implemented in various ways (e.g., the message with the smallest value or smallest timestamp). If M is empty, choice(M ) returns ⊥.

• γ = (p i k ) k∈[1.
. ] ∈ Π being a sequence of processes, for simplicity, we use the notation :γ: as a shorthand for the fragment of signature chain :p i 1 : • • • :p i :. For instance, m:p sender :γ:p i thus means m:p sender :p i 1 : • • • :p i :p i . We similarly equate the sequence γ with its supporting set set(γ)

= {p i k } k∈[1.. ] when unambiguous. Thus q ∈ γ means q ∈ {p i k } k∈[1.. ] , |γ| = |{p i k } k∈[1.. ] | = , X ∪ γ = X ∪ {p i k } k∈[1.. ] .
For simplicity, we extend these notations to chains of signatures. For instance, if π = m:

p i 1 :p i 2 : • • • :p i is a chain and p ∈ Π a process, p ∈ π means p ∈ {p i k } k∈[1.. ] .
• If Γ ⊆ Π * is a set of process sequences (resp. a set of chains), by abuse of notation we note set(Γ) the set of processes that appear in one of the sequences of Γ (resp. whose signature appears in one of the chains of Γ):

set(Γ) = γ∈Γ set(γ). • γ = (p i k ) k∈[1.
. ] ∈ Π being a sequence of processes, we note subchain(γ, k 1 , k 2 ) the subsequence of γ that contains its k 1 th to k 2 th elements (with both p i k 1 and p i k 2 included). The resulting sub-sequence is truncated accordingly if γ does not contain enough elements. Formally, we have:

subchain(γ, k 1 , k 2 ) = (p i k ) k∈[k 1 ..min( ,k 2 )] . If |γ| ≤ k in particular, subchain(γ, 1, k) = γ.
As above, we extend this definition to chains of signatures.

If π = m:p i 1 :p i 2 : • • • :p i is a chain then subchain(π, k 1 , k 2 ) = (p i k ) k∈[k 1 ...min( ,k 2 )] .
• π = m:p i 1 :p i 2 : • • • :p i being a chain of signature, we note truncate k (π) the chain in which only the first k signatures are kept (or all of

π if |π| ≤ k): truncate k (π) = m:p i 1 :p i 2 : • • • :p i min(k, ) .

A generic weight-based synchronous BRB algorithm

Algorithms 1 and 2 describe a general construction for synchronous deterministic broadcast algorithms that lends itself to good-case latency and early-stopping properties. Our approach is modular and hinges Algorithm 1: brb-broadcast operation executed by p sender at round R = 1

1 Init: view i ← ∅; delivered i ← false; to_bcast i,r ← ∅ for all r ∈ [1..t + 1]; 2 In each synchronous round R ∈ [1..t + 1] do Communication step 3 if R ≥ 2 then broadcast MSG(to_bcast i,R ); 4 if delivered i then quit().
Computation step wait that all messages MSG(-) of round R are in received i,R Algorithm 2: Skeleton of a Weight-based Synchronous BRB algorithm (code for p i = p sender ). The use of WBP() and reveal_round() are highlighted using rounded boxes. on two functions: a message-selection predicate (noted WBP, standing for weight-based predicate), and a revealing-round function (noted reveal_round).

5 view i ← view i ∪ {π ∈ chains | MSG(chains ) ∈ received i,R }; 6 to_bcast i,R+1 ← {π:p i | π ∈ view i [R] ∧ p i ∈ π}; 7 known_msgs i,R ← {m | ∃ m:π ∈ view i }; 8 if known_msgs i,R = {m} ∧ ∃ w ∈ N + : § ¦ ¤ ¥ WBP(m, w, view i ) ∧ R ≥ § ¦ ¤ ¥ reveal_round(w) then 9 brb_deliver(m); delivered i ← true; 10 else if R = t + 1 then 11 weights i ← {w ∈ N + | ∃ m ∈ known_msgs i,R : § ¦ ¤ ¥ WBP(m, w, view i ) }; 12 if weights i = ∅ then 13 candidate_msgs i ← {m ∈ known_msgs i,R | § ¦ ¤ ¥ WBP m, max(weights i ), view i };
For readability, Algorithm 1 presents the code for the sending process p sender separately. To brbbroadcast m, p sender simply signs m, produces the signature chain m:p sender , and broadcasts a protocol message MSG({m:p sender }) containing this chain to all correct processes before brb-delivering m locally. Here, and as in the rest of the paper, the operation broadcast(m) is used as a shorthand for "for all p j ∈ Π do send m to p j end for".

Algorithm 2 constitutes the core of the generic BRB algorithm we propose. It uses up to t + 1 synchronous rounds (lines 2-15). R is a global variable containing the current round number. Each round is divided into a communication step (lines 3-4), in which processes broadcast and receive messages exchanged during the round, and a computation step (lines 5-15) in which they handle received messages and prepare the messages to be sent during the next round. The set received i,R represents the messages received by process p i during round R. It is directly updated by the (synchronous) network layer.

The set to_bcast i,R contains the signature chains to be broadcast by p i during round R. In the first round, p i = p sender remains silent. Process p i accumulates in the set view i the signature chains it receives during each round (line 5). The notation view i [R] used at line 6 is a shortcut to denote the chains of view i that contain exactly R signatures and have therefore just been received. More generally we use the notation view i [r] def = {γ ∈ view i : |γ| = r}. The chains of length R that do not already contain p i 's signature are signed by p i and stored for broadcasting in the next round (line 6).

Process p i 's behavior in the computation step is driven by the predicate WBP and the function reveal_round. The function WBP takes three parameters: a message m, a positive weight w ∈ N + , and a set of valid chains, view , which captures a process's current view. It returns a Boolean value, which when true, indicates that m can be considered as a possible message to be brb-delivered with a weight w according to the information contained in view . More formally this can be expressed as

WBP : M × N + × P valid(M × Π * ) → {true, false} (m, w, view ) → WBP(m, w, view ),
where M is the set of possible messages, N + the set of positive integers, and P M × valid(Π * ) the powerset of valid signature chains. In terms of vocabulary, we say that p i observes a predicate of weight w for a message m during round R if WBP(m, w, view i ) = true during the computation step of round R at p i once the new value of view i has been computed (lines 8-15 of Algorithm 2). The function reveal_round is closely linked to WBP, and helps a process decide when a message of weight w (according to the predicate WBP) is safe to brb-deliver.

reveal_round : N + → [1..t + 1] w → reveal_round(w).
How p i uses the information provided by WBP and reveal_round depends on whether p i has reached round t + 1 or not. In earlier rounds, p i uses the conspicuity property of the predicate WBP to detect if a message m is backed by a predicate "heavy enough" that cannot be beaten by any other message m = m (condition at line 8). If this is the case, m is brb-delivered at line 9, and the flag delivered i is toggled to stop the algorithm in the next round. 5 "Heavy enough" means that w, the weight of the predicate observed by p i , should have revealing round reveal_round(w) of at most R. This implies that, by round R, all predicates of weight w or more must have become conspicuous and allows p i to make a safe brb-delivery because it knows that no message m can exhibit a predicate heavier or equal to w, ensuring that m will prevail in case of conflicts possibly detected by other correct processes. Figure 1 illustrates the above mechanism.

If p i reaches round t + 1 without having brb-delivered any message (line 10), it tallies all messages known to it and keeps only messages backed by a predicate WBP with maximal weight max(weights i ). Process p i uses a deterministic function choice() to break any tie between messages. Finally, if no message is known to p i (weights i = ∅), p i brb-delivers a default special value, ⊥ (line 15).

λ good -BRB-robustness and BRB guarantees

The pair (WBP, reveal_round) is said to be λ good -BRB-robust if WBP and reveal_round() exhibit the following properties when used in Algorithm 2, where λ good is an integer that depends on n, t, and c.

The properties are grouped into three blocks. The first block, Monotony and Local Conspicuity, states four intuitive properties on the stability of the WBP predicate and the reveal_round function when their weight and view parameters change. The second block, Safety, formalizes the conspicuity and the final visibility of a weight-based predicate, two properties that are essential to prove the safe termination of Algorithm 2. Finally, the third block, Liveness, contains a single property that describes the behaviour of WBP in good cases, which determines the good-case latency of Algorithm 2.

The tight connection between these properties and BRB broadcast is captured by Theorem 1, described just afterwards. Theorem 1 states that if a pair (WBP, reveal_round) is λ good -BRB-robust (i.e.

p i WBP(m, w, view i ) reveal_round(w) WBP(m =m, w ≥w, view i ) =⇒ p i brb-delivers m p j WBP(m, w, view j ) WBP(m =m, w ≥w, view j ) p k WBP(m, w, view j ) WBP(m =m, w ≥w, view j ) round t + 1
Figure 1: If a correct process p i observes WBP(m, w, view i ) or reaches round reveal_round(w) only with message m as a candidate, then these events are eventually "propagated" to all other correct processes (here p j and p k ), at the latest in round t + 1 in bad cases, and immediately in good cases. fulfills the properties listed below), then Algorithm 2 implements a BRB broadcast that exhibits a goodcase latency of max 2, λ good .

In the following w, w ∈ N + are weights; m ∈ M is a message; and view and view are sets of valid signature chains. -WBP-REVEALING-ROUND-MONOTONY: A heavier predicate should exhibit an earlier revealing round: ∀w > w : reveal_round(w) ≤ reveal_round(w ). -WBP-LOCAL-CONSPICUITY: A message exhibits a weight-1 predicate in a view if and only if it appears in the view: WBP(m, 1, view ) ⇐⇒ m ∈ message(view)

• Monotony and Local Conspicuity

• Safety -WBP-CONSPICUITY: Consider p i , p j two correct processes different from p sender , and w a weight. If p i observes WBP(m, w, view i ) during its execution, and p j executes round reveal_round(w), then m is known to p j at the latest by round reveal_round(w).

-WBP-FINAL-VISIBILITY: Consider p i , p j two correct processes different from p sender . If p sender is Byzantine and p i observes WBP(m, w, view i ) during its execution, and p j executes round t + 1, then p j observes WBP(m, w, view j ) at round t + 1.

• Liveness

-WBP-GOOD-CASE-LIVENESS: If p sender is correct and brb-broadcasts a message m, then all correct processes p i = p sender observe WBP(m, w good , view i ) during round 2, where w good ∈ N + is a weight such that reveal_round(w good ) = λ good .

Theorem 1. If the pair (WBP, reveal_round) is λ good -BRB-robust, where λ good is an integer that depends on n, t, and c, then Algorithm 2 implements a Synchronous Byzantine Reliable Broadcast object with a worst-case latency of t + 1 rounds. Furthermore, if the initial sender p sender is correct, correct processes brb-deliver in at most max 2, λ good rounds.

Proof of Theorem 1

The proof of Theorem 1 follows from Lemmas 1-6, which follow.

Lemma 1. Algorithm 2 verifies the BRB-VALIDITY Property.

Proof. Consider p i a correct process.

• If p i = p sender , the brb-delivery of a message m at line 3 of Algorithm 1 trivially implies that p i has executed Algorithm 1, and hence has brb-broadcast m.

• If p i = p sender , p i may brb-deliver a message m either at lines 9 or 14 of Algorithm 2. In both cases, m belongs to some known_msgs i,R variable computed at line 7, and must therefore appear in a signature chain of the form m:p i 1 Proof. The property trivially follows from the code executed by p sender (Algorithm 1). If p sender is correct it executes Algorithm 1 to broadcast a message m, then brb-delivers its own message at line 3. Proof.

• If p sender is correct, p sender brb-broadcasts one single message m (Algorithm 1), and by BRB-VALIDITY (Lemma 1), all correct processes that do brb-deliver a message only brb-deliver m.

• If p sender is Byzantine, consider two correct processes p i and p j (both necessarily different from p sender ) that each brb-deliver some message: p i brb-delivers m i and p j brb-delivers m j . We distinguish three cases depending on the lines at which p i and p j execute brb_deliver.

-Case 1: Assume p i and p j both deliver their respective message at line 9 of Algorithm 2. Due to the condition at line 8, there exist two rounds R i and R j such that the following holds

known_msgs i,R i = {m i } ∧ ∃ w i ∈ N + : WBP(m i , w i , view i ) ∧ R i ≥ reveal_round(w i ) , and
known_msgs j,R j = {m j } ∧ ∃ w j ∈ N + : WBP(m j , w j , view j ) ∧ R j ≥ reveal_round(w j ) .
Without loss of generality, assume w i ≥ w j . By WBP-REVEALING-ROUND-MONOTONY, reveal_round(w i ) ≤ reveal_round(w j ), which leads by case assumption to R j ≥ reveal_round(w i ). Process p j therefore executes round reveal_round(w i ), and WBP-CONSPICUITY applies to WBP(m i , w i , view i ) that p i observes. We conclude that m i is known to p j by round reveal_round(w i ), i.e. formally m i ∈ known_msgs j,reveal_round(w i ) .

Since view i keeps growing with each passed round, R j ≥ reveal_round(w i ) implies known_msgs j,reveal_round(w i ) ⊆ known_msgs j,R j , and therefore m i ∈ known_msgs j,R j . Since known_msgs j,R j = {m j } by case assumption, this leads to m i = m j , proving the case.

-Case 2: Assume p i and p j both brb-deliver their respective message at line 14 or 15 of Algorithm 2, during round t + 1. Let us consider the two following sets, defined at round t + 1:

weights i = {w ∈ N + | ∃ m ∈ known_msgs i,t+1 : WBP(m, w, view i )},
and

weights j = {w ∈ N + | ∃ m ∈ known_msgs j,t+1 : WBP(m, w, view j )}.
Consider w ∈ weights i , and m ∈ known_msgs i,t+1 a message such that WBP(m, w, view i ).

Because p sender is Byzantine (by assumption), WBP-FINAL-VISIBILITY applies and WBP(m, w, view i ) for p i implies WBP(m, w, view j ) for p j at round t + 1. By WBP-WEIGHT-MONOTONY and WBP-LOCAL-CONSPICUITY, WBP(m, w, view j ) at round t + 1 implies WBP(m, 1, view j ) (since w ≥ 1 by construction), m ∈ known_msgs j,t+1 , and therefore that w ∈ weights j . Inverting p i and p j leads to weights i = weights j , and therefore to max(weights i ) = max(weights j ). Using this last equality, we conclude that either p i and p j both have empty weights i and weights j sets and get to the else branch at line 15 and both brb-deliver ⊥, or they both pass the condition at line 12, in which case they must both obtain the same candidate_msgs i and candidate_msgs j sets, and therefore brb-deliver the same message at line 14.

-Case 3: Assume p i brb-delivers m i at line 9 of Algorithm 2 during some round R i , and p j brb-delivers m j at line 14 or 15 of the same algorithm during round t + 1. Due to the condition at line 8, there exists a weight w i ∈ N + such that the following holds

known_msgs i,R i = {m i } ∧ WBP(m i , w i , view i ) ∧ R i ≥ reveal_round(w i ). (1)
As in Case 2, let us consider the following set defined at round t + 1 at p j :

weights j = {w ∈ N + | ∃ m ∈ known_msgs j,t+1 : WBP(m, w, view j )}.
As in Case 2, WBP-FINAL-VISIBILITY applies and WBP(m i , w i , view i ) = true at p i implies WBP(m i , w i , view i ) = true at p j at round t + 1. This fact and WBP-LOCAL-CONSPICUITY further implies m i ∈ known_msgs j,t+1 , and therefore that w i ∈ weights j (and as weights j is not empty, p j cannot brb-deliver at line 15). This last inclusion yields that max(weights j ) ≥ w i at line 13 of Algorithm 2. Because m j is brb-delivered by p j at line 14, we have by construction WBP(m j , max(weights j ), view j ) = true at line 13 of p j . By WBP-WEIGHT-MONOTONY, WBP(m j , max(weights j ), view j ) and max(weights j ) ≥ w i imply WBP(m j , w i , view j ) = true at p j . Applying WBP-CONSPICUITY, and the fact that R i ≥ reveal_round(w i ), this last statement implies that m j ∈ known_msgs i,R i at round R i at p i . Combined with [START_REF] Abraham | Communication complexity of Byzantine agreement, revisited[END_REF], this leads to m j = m i , proving the case and concluding the lemma.

Lemma 5. If the pair (WBP, reveal_round) is λ good -BRB-robust, where λ good is an integer that depends on n, t, and c, and if p sender is correct, then correct processes brb-deliver the message m brb-broadcast by p sender in at most max 2, λ good rounds.

Proof. If p sender is correct and brb-broadcasts a message m, it brb-delivers its own message in round 1 (Algorithm 1). By WBP-GOOD-CASE-LIVENESS all other correct processes p i = p sender observe WBP(m, w good , view i ) during round 2. By WBP-VIEW-MONOTONY, and given that view i can only grow in Algorithm 2, WBP(m, w good , view i ) remains true during all subsequent rounds R ≥ 2 that p i executes. In addition, as p sender is correct and signatures are secure, known_msgs i,R does not contain any other message than m. As a result, at the latest in round max(2, reveal_round(w good )) = max(2, λ good ), the condition of line 8 becomes true for the message m and the weight w good , and p i delivers m.

Lemma 6. In the worst case, a correct process executing Algorithm 2 brb-delivers a message in t + 1 rounds.

Proof. By construction of Algorithm 2, processes are guaranteed to brb-deliver at the latest in round t + 1 (through the condition at line 10), either at line 14 or 15 (if they have not brb-delivered early at line 9).

Lemma 7. Algorithm 2 verifies the BRB-GLOBAL-DELIVERY property.

Proof. This property derives trivially from Lemma 6: all correct processes brb-deliver a message at the latest in round t + 1.

Revisiting Lamport, Shostak, and Pease's algorithm (BRB-LSP)

BRB-LSP [START_REF] Lamport | The Byzantine generals problem[END_REF] can be expressed in the framework of Algorithm 2 by choosing the following definitions and values for WBP, reveal_round, and λ good :

WBP LSP (m, w, view ) def = m ∈ message(view ) , reveal_round LSP (w) def = t + 1, λ LSP good def = t + 1.
With the above definition of WBP and reveal_round, Algorithm 2 systematically brb-delivers in round t + 1 (since the condition at line 8 can only become true in round t + 1). Furthermore, when p i only knows one message m in round t+1, the first branch of the "delivery" if block at line 9 is equivalent to its else branch at lines 11-15. In all cases, p i therefore collects in round t + 1 all the messages it has received, and chooses one of them in a deterministic manner, thus reproducing BRB-LSP.

WBP LSP and reveal_round LSP correspond to a border example of the use of our generic algorithm, since the weight w plays no part in their definition. However, the pair (WBP LSP , reveal_round LSP ) does fulfill the prerequisites of (t+1)-BRB-robustness required to apply Theorem 1, as the following theorem shows.

Theorem 2. The pair (WBP LSP , reveal_round LSP ) is (t + 1)-BRB-robust.

Proof. WBP-WEIGHT-MONOTONY and WBP-REVEALING-ROUND-MONOTONY trivially follow from the fact that neither WBP LSP nor reveal_round LSP depend on w. Similarly, WBP-VIEW-MONOTONY and WBP-LOCAL-CONSPICUITY directly result from the definition of WBP LSP .

WBP-CONSPICUITY and WBP-FINAL-VISIBILITY hinge on the central intuition underpinning BRB-LSP. First note that WBP LSP (m, w, view i ) = true for some process p i , message m, and weight w is equivalent to stating that p i knows message m, or equivalently that p i has received some valid chain containing m.

Consider a correct process p i = p sender that has received some chain containing m. If p i received m for the first time before round t + 1, then by construction of Algorithm 2, it has sent it to all other correct processes, which must therefore also know m. If p i received m for the first time during round t + 1, then the chain carrying m must contain t + 1 distinct processes (to be valid), and must therefore contain at least one correct process p k that must have sent m to all other correct processes. These observations yield the WBP-CONSPICUITY and WBP-FINAL-VISIBILITY properties.

Finally, WBP-GOOD-CASE-LIVENESS is trivially fulfilled by definition of WBP LSP .

5 A Deterministic Good-Case BRB Latency in max 2, t + 3 -w Rounds

Overview

Theorem 1 states that a deterministic synchronous BRB algorithm that exhibits a good case latency of max 2, t+3-w can be obtained simply by finding a weight-base predicate and revealing round function that are max 2, t + 3 -w -BRB-robust. Constructing such a pair is however not immediately obvious. We present such a predicate in this section (called weight-based predicate with good-case latency, or WBP GCL for short) by exploiting a pattern revolving around what we have called a "revealing chain".

Weights and revealing chains

The weight-based predicate we propose counts the number of processes whose signature appears within the first two positions of the valid chains a process p i has received. These processes are said to be backing m in p i 's view, and their number is the predicate's weight, w.

Just counting and propagating the round-1 or -2 signatures that correct processes observe is, however, not enough, as it does not prevent Byzantine processes from selectively revealing some round-2 signatures at the very last moment (round t + 1 in our case), thus preventing correct processes from brb-delivering earlier using this information only. The predicate we use therefore adds an additional constraint that limits the disruption power of Byzantine processes, and provides the conspicuity property required by Algorithm 2: a predicate of weight w must contain a "revealing chain" m::γ whose makeup must "differ sufficiently" from the backing processes documented by the predicate. "Differ sufficiently" means that the processes from position 3 until position t + 3 -w of this revealing chain (shown in red in Figure 2) should not be backing processes.

This constraint limits what Byzantine processes can do when the sender is Byzantine and ensure this predicate is both conspicuous and finally visible, and thus usable within Algorithm 2. The revealing chain does not prevent Byzantine processes from colluding to forge competing predicates for different messages in bad cases (i.e. when p sender is Byzantine). However, Byzantine processes can only use up to t signatures and must decide whether to invest these t signatures in the backing part of each predicate (thus increasing the predicate's weight) or in their revealing chain (thus delaying the time at which the message of a forged predicate must be revealed to correct processes, but reducing the predicate's weight).

Predicate conspicuity

The position t + 3 -w of the revealing chain enforces the conspicuity of the predicate and yields the good-case latency max(2, t+3-c). This is because the signatures from positions 3 to t + 3 -w correspond to (t + 3 -w) -3 + 1 = t + 1 -w processes. Added to the w processes backing the predicate (W i,R in Figure 2), this represents t + 1 -w + w = t + 1 processes. These t + 1 processes must contain a correct process; therefore, Byzantine processes that seek to forge a predicate for a message m must include the signature of a correct process at the latest in round t + 3 -w. This ensures m become visible to all other correct processes by round t + 3 -w, the revealing round of the predicate in the terms of Section 4. An example of WBP GCL Figure 2 shows a WBP GCL predicate of weight w = 6 for a message m observed by p i at round R in a setting with t = 8: each horizontal line represents a chain of signatures that starts with m:p sender , the green rectangle (W ) represents processes that have signed m in round 1 or 2 (and are therefore backing m), and m:γ is the revealing chain, such that the process appearing from position 3 to t + 3 -w (= t -3 here) in m:γ do not appear in W . The corresponding revealing round is defined as reveal_round GCL (w) = max(2, t + 3 -w). Because w = 6 and t = 8, the revealing round is 5 in this example. This function is discussed in more detail in Section 5.2.

It is important to distinguish the round upon which the WBP GCL is observed, from the revealing round and the round where the message is brb-delivered. These can be three entirely different rounds. In this example, the WBP GCL is observed at round 8 when p i learns about the second chain from the top, but the revealing round is reveal_round GCL (6) = t + 3 -6 = 5. However, it is possible to have the inverse scenario, where the WBP GCL is observed before the revealing round, in which case the process must wait in order to brb-deliver the message. And in the case where multiple distinct messages are observed before the revealing round is attained, the process must wait for round t + 1 to brb-deliver one of these messages.

A special case: delivery in round 2 A special case occurs when the weight of a predicate reaches w = t + 1. When this happens, any process p i observing the predicate knows that one of the processes of W is correct and, therefore, that all correct processes must have received a chain containing m by the end of round 2 (the revealing round for the weight t + 1). Conversely, if p i has not received any chain containing a message m by round 2, p i knows that a predicate of weight t + 1 cannot possibly exist for m . As a result, a correct process that observes a predicate a weight t + 1 for m and is not aware of any other message m = m by round 2 can safely brb-deliver m, as no other message will be able to "beat" m with a heavier predicate, even if the sender p sender is Byzantine.

Weak non-intersecting quorums The reasoning for w = t + 1 mirrors the mechanism of intersecting quorums used in asynchronous systems and requires a majority of correct processes (or n > 2t) to be guaranteed to occur when the sender is correct. The proposed predicate mechanism leverages the additional guarantees that a synchronous system brings to generalize this idea to weaker non-intersecting "quorums", whose ability to trigger a brb-delivery decision requires additional temporal information (waiting until the revealing round t + 3 -w).

The WBP GCL Predicate

This paper's main contribution, a synchronous deterministic Byzantine Reliable Broadcast algorithm with a good case latency of max 2, t + 3 -w , is obtained by injecting into the generic code of Algo-

1 WBP GCL (m, w, view ) def = 2
∃ m:γ ∈ view such that, when noting m:γ is the revealing chain. WBP GCL (m, w, view ) first considers S, the set of all processes that have signed 6 the message m either during round 1 or 2. WBP GCL (m, w, view ) is true if view contains a "revealing chain" backing m, (noted m:γ) such that after removing from S all processes appearing between the position 3 and t + 3 -w of γ, the resulting set W contains at least w distinct processes that have signed m in round 1 or 2 (see Figure 2 and Section 5.1.)

The existence of γ (the revealing chain) is essential to provide the WBP-CONSPICUITY property of (WBP GCL , reveal_round GCL ). Intuitively, the reason lies in the choice of the boundaries of the subchain subchain(γ, 3, t + 3 -w).

• If γ contains strictly less than t + 3 -w processes and appears in the view view i of a correct process p i , then p i must have known m before round t + 3 -w, and will have informed all other correct processes of m's existence at the latest by round t + 3 -w.

• If, on the other hand, γ contains t + 3 -w processes or more, then subchain(γ, 3, t + 3 -w) will contain (t + 3 -w) -3 + 1 = t + 1 -w distinct processes. In that case, line 5 ensures that W ∪ subchain(γ, 3, t + 3 -w) contains more than w + (t + 1 -w) = t + 1 processes, i.e. does contain at least one correct process. By construction, this correct process will have signed and propagated a chain backing m at the latest by round t + 3 -w.

Proof of Correctness

This Section proves the following Theorem and Corollary.

Theorem 3. The pair (WBP GCL , reveal_round GCL ) is max(2, t + 3 -c)-BRB-robust, where c is the effective number of correct processes.

Corollary 1. The use of (WBP GCL , reveal_round GCL ) in Algorithm 2 implements a synchronous deterministic Byzantine Reliable Broadcast algorithm with a worst-case latency of t + 1 and a good case latency of max 2, t + 3 -w .

Remark Note that if n > 2t, then because c ≥ n -t, we have c ≥ t + 1, and max(2, t + 3 -c) = 2, all correct processes deliver in at most 2 rounds when the sender is correct.

Preliminary lemmas

Lemma 8. The predicate WBP GCL fulfills the WBP-WEIGHT-MONOTONY property defined in Section 4.4.

Proof overview. (Detailed proof below.) The lemma follows from the fact that the weight w of a predicate WBP GCL (m, w, view ) counts processes that back m in round 1 or 2. A (small) technical difficulty is caused by the revealing chain (m:γ in Algorithm 3), which grows when considering a smaller weight w ≤ w. This growth is, however, bounded by the weight difference w -w , which yields the lemma.

Detailed proof. Assume WBP GCL (m, w, view ) holds, and consider γ, S and W the chain and the sets of processes that render WBP GCL (m, w, view ) true according to Algorithm 3. Consider w ∈ N + such that w ≤ w. Let us note

γ w = subchain(γ, 3, t + 3 -w), γ w = subchain(γ, 3, t + 3 -w ).
By definition of subchain, and because w ≤ w, γ w is a prefix of γ w , which implies

set(γ w ) ⊇ set(γ w ), (2)
set(γ w ) \ set(γ w ) ≤ (w -w ). (3)
Define W def = S \ set(γ w ). The following holds

W = S \ set(γ w ) \ set(γ w ) \ set(γ w ) , (using (2)
) (since WBP GCL (m, w, view ) holds)

|W | ≥ S \ set(γ w ) -(w -w ), (using (3)
This last equation shows that WBP GCL (m, w , view ) holds using γ, S, and W in Algorithm 3, concluding the proof.

Lemma 9. The pair (WBP GCL , reveal_round GCL ) fulfills the WBP-VIEW-MONOTONY, WBP-REVEALING-ROUND-MONOTONY, and WBP-LOCAL-CONSPICUITY properties defined in Section 4.4.

Proof.

• WBP-VIEW-MONOTONY: Assume WBP GCL (m, w, view ) holds, and consider γ, S and W the chain and the sets of processes that render WBP GCL (m, w, view ) true according to Algorithm 3. If view ⊇ view , then we still have m:γ ∈ view . If we note

S def = q ∈ Π | q backs m in round 1 or 2 in view , W def = S \ set subchain(γ, 3, t + 3 -w) ,
view ⊇ view implies that S ⊇ S and W ⊇ W , and therefore |W | ≥ |W | ≥ w, proving the WBP-VIEW-MONOTONY property of WBP GCL .

• WBP-REVEALING-ROUND-MONOTONY is trivially fulfilled by the definition of reveal_round GCL .

• WBP-LOCAL-CONSPICUITY: Assume WBP GCL (m, 1, view ) holds, and consider γ, S and W the chain and the sets of processes that render WBP GCL (m, 1, view ) true according to Algorithm 3. Trivially, m:γ ∈ view implies m ∈ message(view).

Conversely, assume m ∈ message(view). There exists a chain γ m such that m:γ m ∈ view . As all chains of view are valid by assumption, γ m must start with p sender 's signature. Define the sets S and W as in Algorithm 3, but using γ m . By construction, p sender ∈ S. As valid chains are acyclic, p sender ∈ set subchain(γ m , 3, t + 3 -w) , and therefore p sender ∈ W , and |W | ≥ 1. This last statement implies that WBP GCL (m, 1, view ) holds. With the previous paragraph, this proves that WBP GCL fulfills the WBP-LOCAL-CONSPICUITY, and concludes the lemma.

Lemma 10. The pair (WBP GCL , reveal_round GCL ) fulfills the WBP-CONSPICUITY property.

Proof overview. (Detailed proof below.) Let us note γ i the chain that renders true WBP GCL (m, w, view i ) for p i (Alg. 3). The proof depends on whether |γ i | = r i (the round in which p i observes the revealing chain m:γ i , cf. Alg. 3) occurs before or after the round reveal_round GCL (w) def = max(2, t+3-w), the round during which we seek to prove that all correct processes that have not stopped earlier are aware of m. If r i < max(2, t + 3 -w), because p i forwards all chains it has not signed yet, all correct processes observe a chain containing m at the latest by round r i + 1 ≤ max(2, t + 3 -w). If r i ≥ max(2, t + 3 -w), the construction of reveal_round GCL implies that at least t + 1 processes have signed chains containing m during the first max(2, t + 3 -w) rounds of the protocol. One of them must be correct, yielding the lemma.

Detailed proof. Assume a correct process p i observes WBP GCL (m, w, view i ) = true during its execution. In the following, γ i denotes a chain that renders WBP GCL true in Algorithm 3, and r i = |γ i | its length. As p i is correct, m:γ i ∈ view i (line 2 of Algorithm 3) implies that p i receives m:γ i during round r i = |γ i |. The remainder of the proof distinguishes two cases, depending on whether

r i < reveal_round GCL (w) def = max(2, t + 3 -w) or not.
• Case r i < max(2, t + 3 -w): As just mentioned, p i receives m:γ i during the communication step of round r i (line 5 of Algorithm 2). If p i ∈ γ i , p i signs the chain (line 6, Alg. 2), and broadcasts it during the communication step of round r i +1 ≤ max(2, t+3-w) (line 3 of the same algorithm). If p i ∈ γ i , p i has signed a chain m:γ earlier, and broadcast the result before or during round r i .

In both cases, any correct process p j that executes round max(2, t + 3 -w) receives some chain m:γ i :p i either during or before round max(2, t + 3 -w), and therefore m is known to p j at the latest by round max(2, t + 3 -w).

• Case r i ≥ max(2, t + 3 -w): Let us note S and W the set of processes which together with γ i render WBP GCL (m, w, view i ) true in Algorithm 3.

Let us note γ 3..t+3-w def = subchain(γ i , 3, t+3-w). Since |γ i | = r i ≥ max(2, t+3-w) ≥ t+3-w, γ i contains more than t + 3 -w processes. As a result, by definition of the function subchain, and because γ i is valid, and hence acyclic, γ 3..t+3-w contains exactly max(0, (t + 3 -w) -3 + 1) = max(0, t + 1 -w) distinct processes:

set(γ 3..t+3-w | = max(0, t + 1 -w). (4)
By construction, W and set(γ 3..t+3-w ) have no element in common, which yields

|W ∪ set(γ 3..t+3-w )| = |W | + |set(γ 3..t+3-w )|, (5)
= |W | + max(0, t + 1 -w), (using (4)) ≥ max(w, w + t + 1 -w), (by definition of WBP GCL ) |W ∪ set(γ 3..t+3-w )| ≥ max(w, t + 1) ≥ t + 1. (6)
The set W ∪ set(γ 3..t+3-w ) therefore contains at least one correct process p k . If p k ∈ W , p k 's signature appears in the first or second position of one of the chains of view i . If p k ∈ set(γ 3..t+3-w ), p k 's signature appears before position t + 3 -w in γ i ∈ view i . Both cases imply that p k has signed a chain with message m and has broadcast this chain to all processes that have not stopped earlier during or before round max(2, t + 3 -w), proving the lemma.

In the following, we use the notation view i [r 1 ..r 2 ] the chains of view 1 that contain signatures between r 1 and r 2 . In the same way view i [r] represents the chains received by p i during round r, view i [r 1 ..r 2 ] contains the chains received between rounds r 1 and r 2 :

view i [r 1 ..r 2 ] def = {γ ∈ view i : r 1 ≤ |γ| ≤ r 2 }.
Building upon the notation view i [r 1 ..r 2 ], we introduce the quantity T 2,i [R] to prove the WBP-FINAL-VISIBILITY of (WBP GCL , reveal_round GCL ) (Lemma 13). T 2,i [R] is defined using process p i 's view view i at round R as follows

T 2,i [R] def = truncate 2 view i [2..R] . (7)
T 2,i [R] contains all length-2 prefixes m:p sender :q observed by p i by round R, i.e. p i 's knowledge during round R of the processes that have signed m by the end of round 2.

The following lemma states that all length-2 prefixes known at round R by a correct process p i = p sender executing Algorithm 2 are known by all other correct processes by round R + 1. Lemma 11. Let p i and p j = p i be two correct processes, such that p i executes the computation step (lines 3-4) of at least the R ≤ t first rounds, and p j executes the communication step of at least the first R + 1 rounds. Then we have ∀R ∈

[1..t], T 2,i [R] ⊆ T 2,j [R + 1].
Proof. Note that since p i and p j execute Algorithm 2, they are both different from p sender . We prove the lemma by induction.

• Case R = 1: view i [2..1] = ∅, and therefore T 2,i [START_REF] Abraham | Communication complexity of Byzantine agreement, revisited[END_REF] = ∅, trivially proving the case.

• Induction case: Let us assume

T 2,i [R] ⊆ T 2,j [R + 1] for some R ∈ [1..t -1]. T 2,i [R + 1] = truncate 2 view i [2..R + 1] , = truncate 2 view i [2..R] ∪ view i [R + 1] , = truncate 2 view i [2..R] ∪ truncate 2 view i [R + 1] , = T 2,i [R] ∪ truncate 2 view i [R + 1] , ⊆ T 2,j [R + 1] ∪ truncate 2 view i [R + 1] ,
(by case assumption)

⊆ T 2,j [R + 2] ∪ truncate 2 view i [R + 1] . (as T 2,j [R + 1] ⊆ T 2,j [R + 2])
We now need to show that truncate

2 view i [R+1] ⊆ T 2,j [R+2] to complete the proof. Consider m:p sender :γ ∈ view i [R + 1], with γ ∈ Π R .
By assumption, p i = p sender , we must therefore distinguish two cases depending whether p i appears in γ or not.

-

∈ truncate 2 (view j [R + 2]) ⊆ T 2,j [R + 2].
These two cases show that truncate

2 view i [R + 1] ⊆ T 2,j [R + 2],
which concludes the proof of the lemma.

The following lemma shows that if p sender is Byzantine then all correct processes agree on the length-2 prefixes they have observed by round t + 1.

Lemma 12. Let p sender be Byzantine, and p i and p j be two correct processes that execute the communication step of round t + 1, then

T 2,i [t + 1] = T 2,j [t + 1].
Proof overview. (Detailed proof below.) The proof uses the fact that the length-2 prefixes that p i receives in round t + 1 have been propagated by t + 1 processes. One of these processes must be correct, and because p sender is Byzantine, it must be a process that signed the chain at the earliest in round 2, implying that the length-2 prefix is also known to p j . This observation, together with Lemma 11 yields the proof.

Detailed proof. By definition

T 2,i [t + 1] = truncate 2 (view i [2..t + 1]) = truncate 2 (view i [2..t] ∪ view i [t + 1]) , = T 2,i [t] ∪ truncate 2 view i [t + 1] .
Applying Lemma 11 we have T 2,i [t] ⊆ T 2,j [t + 1], which with the previous equality yields

T 2,i [t + 1] ⊆ T 2,j [t + 1] ∪ truncate 2 view i [t + 1] . (8)
We Proof. The proof follows either from Lemma 12 or 11, depending on whether r = t + 1 or not.

• If r = t + 1, the corollary follows trivially from Lemma 12.

• If r < t + 1, this follows from Lemma 11, and observing that T 2,j [r + 1] ⊆ T 2,j [t + 1].

Lemma 13. The pair (WBP GCL , reveal_round GCL ) fulfills the WBP-FINAL-VISIBILITY property.

Proof overview. (Detailed proof below.) Consider p i , p j two correct processes, and assume p sender is Byzantine. The proof focuses on the sets of processes S and W , and on the revealing chain γ used in the predicate WBP GCL (Algorithm 3). First, the proof shows that the set S perceived by p i is propagated to all other correct processes at the latest by round t + 1. More concretely, if p i perceives a process p k as backing m, then all correct processes also perceive p k as backing m by round t + 1. The proof then shows that any revealing chain γ i that renders WBP GCL true for p i implies the existence of a revealing chain γ j is p j 's view at round t + 1 that is no more "constraining" than γ i .

Detailed proof. Assume p sender is Byzantine. Assume a correct process p i observes WBP GCL (m, w, view i ) = true during some round R of its execution. Consider p j another correct process that reaches round t + 1. Without loss of generality, assume p j = p i (as the case p i = p j is trivial).

In the following, for clarity, we note view y x the value of the view variable in Algorithm 2 for the process p x at round y (or more precisely, after view has been updated in round y at line 5 of Algorithm 2). Consider γ i , S i,R and W i,R the chain and the sets of processes that render true WBP GCL for p i in Algorithm 3 during round R.

By definition of WBP GCL , |W i,R | ≥ w. Using T 2,i [R] (7), we can express S i,R as follows

S i,R = {set(γ) | m:γ ∈ view R i [1] ∪ T 2,i [R]}.
The set view R i [START_REF] Abraham | Communication complexity of Byzantine agreement, revisited[END_REF] contains the chains received by p i in round 1, while T 2,i [R] contains the length-2 prefixes of chains received by p i in rounds

2 to R. If m:γ ∈ view R i [1] ∪ T 2,i [R]
, the processes whose signature appears in γ have therefore backed m in round 1 or 2 in view R i . Let us define γ i 3..t+3-w def = subchain(γ i , 3, t + 3 -w). We can express W i,R as

W i,R = S i,R \ set γ i 3..t+3-w = set(γ) | m:γ ∈ view R i [1] ∪ T 2,i [R] \ set γ i 3..t+3-w .
In the following, we will consider p j 's perception at round t + 1 of the processes that have backed m in round 1 or 2. The set of these processes can be defined as:

S j,t+1 = {set(γ) | m:γ ∈ view t+1 j [1] ∪ T 2,j [t + 1]}. Sublemma 13.1. S i,R ⊆ S j,t+1 .
Proof. Consider q ∈ S i,R . There exists a chain γ q such that q ∈ γ q and m:γ

q ∈ view R i [1] ∪ T 2,i [R]. • If m:γ q ∈ T 2,i [R], by Corollary 2, T 2,i [R] ⊆ T 2,j [t + 1]
, and γ q ∈ T 2,j [t + 1], which leads to q ∈ S j,t+1 .

• If m:γ q ∈ view R i [START_REF] Abraham | Communication complexity of Byzantine agreement, revisited[END_REF], then because p i is correct, m:γ q is a valid chain of length 1. As a result, γ q = (p sender ) and q = p sender . Since p i = p sender , p i signs m:p sender at line 6 of Alg. 2, and broadcasts m:p sender :p i to all correct processes in round 2. We therefore have m:p sender :p i ∈ T 2,j [2] ⊆ T 2,j [t + 1] (assuming t ≥ 1, and t + 1 ≥ 2). As a result, q = p sender ∈ S j,t+1 , which concludes the lemma.

To conclude the proof, we need to find a chain m:γ j ∈ view t+1 j that, when "removed" from S j,t+1 , produces a set W j,t+1 containing at least w processes. Once this happens, m:γ j , S j,t+1 and W j,t+1 will render WBP GCL (m, w, view t+1 j ) true in round t + 1. The existence of m:γ j comes from the following sublemma. Sublemma 13.2. ∃ m:γ j ∈ view t+1 j , set subchain(γ j , 3, t + 3 -w) ∩ S i,R ⊆ set(γ i 3..t+3-w ).

Proof. The proof distinguishes three cases:

i , 3, t + 3 -w) ∩ S i,R , ⊆ set(γ i 3..t+3-w ) ∩ S i,R ∪ {p i } ∩ S i,R , ⊆ set(γ i 3..t+3-w ) ∩ S i,R . (since p i ∈ S i,R by case assumption)
This last inclusion concludes Case 3 and therefore the sublemma.

In the following, we will note m:γ j the chain whose existence is given by Sublemma 13.2. Consider W j,t+1 = S j,t+1 \ set subchain(γ j , 3, t + 3 -w) .

The following holds

W i,R = S i,R \ set γ i 3..t+3-w ⊆ S i,R \ set subchain(γ j , 3, t + 3 -w) ∩ S i,R (using Sublemma 13.2) ⊆ S i,R \ set subchain(γ j , 3, t + 3 -w)
⊆ S j,t+1 \ set subchain(γ j , 3, t + 3 -w) (using Sublemma 13.1) ⊆ W j,t+1 .

Because |W i,R | ≥ w by definition, this last inclusion yields |W j,t+1 | ≥ w. This inequality shows that WBP GCL (m, w, view j ) is rendered true at p j at round t + 1 by using γ j , S j,t+1 , and W j,t+1 in Algorithm 3, thus proving the lemma. Lemma 14. The pair (WBP GCL , reveal_round GCL ) fulfills the WBP-GOOD-CASE-LIVENESS property.

Proof. When the initial sender, p sender , is correct, and brb-broadcast a message m, all remaining correct processes p i = p sender receive m:p sender in round 1, and broadcast m:p sender :p i in round 2. As a result, every correct process p i = p sender receives at least c -1 distinct chains backing m of the form m:p sender :p k in round 2.

These chains imply that the set S at line 3 of Algorithm 3 contains at least c processes (p sender and the remaining c -1 correct processes). Using any of the length-2 chains m:p sender :p k , a set W can be constructed equal to S, rendering WBP GCL (m, c, view i ) true for all correct processes other than p sender .

The observation that reveal_round GCL (c) = max(2, t + 3 -c) concludes the lemma.

Proof of Theorem 3 and Corollary 1

The proof of Theorem 3 follows from Lemmas 8, 9, 10, 13, and 14. The proof of Corollary 1 follows from Theorems 1 and 3.

Conclusion

Considering n-process synchronous distributed systems where up to t < n processes can be Byzantine, this paper explored the good-case latency of deterministic Byzantine reliable broadcast (BRB) algorithms, namely the time taken by correct processes to deliver a message when the initial sender is correct.

In contrast to their randomized counterparts, no deterministic BRB algorithm was known that exhibits a good-case latency better than t + 1 (the worst-case bound) under a majority of Byzantine processes. This paper has proposed a novel deterministic synchronous BRB algorithm that substantially improves on this earlier bound and provides a good case latency of max(2, t + 3 -c) rounds, where t is the upper bound on the number of Byzantine processes, and c the number of effectively correct processes in the considered run.

The proposed algorithm has been presented as an instance of a generic BRB algorithm (from which the classical BRB algorithm from Lamport, Shostak and Pease [START_REF] Lamport | The Byzantine generals problem[END_REF] can also be derived). This generic algorithm extends the "signature chain mechanism" first proposed four decades ago. It exploits a family of weight-based predicates to identify patterns in sets of signature chains and help correct processes decide when they can safely deliver a message. A judicious choice for these patterns delivers a concrete BRB algorithm that allows correct processes to brb-deliver much earlier than earlier proposals when the context is favorable. In particular, when the sender is correct, and there are enough effectively correct processes (c > t), the resulting algorithm delivers in 2 rounds, thus outperforming all known dishonestmajority BRB algorithms (whether deterministic or randomized).

Several crucial open questions remain, in particular, whether the upper bound of max(2, t + 3c) rounds can be further improved (for instance, using techniques employed in sub-linear randomized algorithms [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF][START_REF] Wan | Expected constant round Byzantine broadcast under dishonest majority[END_REF]). In terms of lower bounds, one might ask whether the lower bound of n/(n-t) -1 shown in [START_REF] Abraham | Good-case latency of Byzantine broadcast: A complete categorization[END_REF] can be refined to include the effective number of correct processes c, and whether this same lower bound can be strengthened in the deterministic case, for instance by observing Byzantine Agreement cannot be solved in a (worst-case) sub-linear communication complexity using algorithms that tolerate a strongly adaptive adversary (which include deterministic algorithms) [START_REF] Abraham | Communication complexity of Byzantine agreement, revisited[END_REF].

Finally, this paper did not consider the problem of communication complexity. Signature chains can be quite costly in a practical implementation, as each new signature adds hundreds or even thousands of bits to each network message. We conjecture that multi-signatures could help to significantly reduce this overhead by aggregating all non-backing signatures into a fixed-size structure [START_REF] Boneh | Short signatures from the Weil pairing[END_REF]. Furthermore, an interesting follow-up would then be to study the tension between time complexity and communication complexity and how favoring one metric may hinder the other.

A.2 Metric 2: Size of messages

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" by 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 our algorithm, message size contributes heavily to communication costs. This is because messages keep growing in size at every round, as both 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. A process p i can have no more than C R-2 n-2 (the binomial coefficient "n -2 choose R -2") such chains that need to be disseminated (since these chains must start by p sender 's signature, must end with p i 's signature, and are acyclic).

A.2.1 Good case (correct sender)

In a good case, in round R ≥ 2, the chains of length R that a correct process needs to disseminate contain no more than R × C R-2 n-2 signatures, and correct processes collectively cannot send more than (c -1) × n × R × C R-2 n-2 signatures, which is upper bounded by (c -1) × n × R × (n -2) R-2 . 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 7), this adds up to no more than n + 2n(n -1) + 3n(n -1)(n -2) = O(n 3 ) signatures.

A.2.2 Bad case (Byzantine sender)

In a bad case, given that the 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 signature cost is essentially unbounded.

A.3 Possible improvements A.3.1 Sets instead of chains of signatures

The weight-based predicate WBP GCL (Algorithm 3, Section 5.2) does not use the order of the signatures in chains from position 3 to the end. 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. 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 instead of chains would greatly reduce the size of the messages in good and bad cases (Metric 2), as currently, a single message that is exchanged in this algorithm can contain multiple chains that possess exactly the same signatures, but not in the same order, which creates a significant amount of redundant information in each message.

Moreover, using sets of signatures would enable the use of multisignature schemes (such as BLS [START_REF] Boneh | Short signatures from the weil pairing[END_REF]), 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" [START_REF] Abraham | Sync HotStuff: Simple and practical synchronous state machine replication[END_REF] is reduced, the number of "information items" remains the same.

A.3.2 Filtering received messages

To limit the size of the message when the sender is Byzantine, we conjecture that a filtering mechanism precluding multiple conflicting application messages from being backed by correct processes could help to obtain a finite value for Metric 2 in a bad case. This improvement may also lead to a decrease of Metric 1.

A.3.3 Not sending "useless" messages

There is a strong possibility that some messages of the algorithm that we present are not required to ensure its correctness. For instance, in our algorithm, a correct process signs and rebroadcasts every signature chain it receives that does not already contain its signature. However, the set of chains that it broadcasts may be a version with more signatures of an old set of chains that it has already broadcast in a previous round. As a result, broadcasting this new set of chains to the network may not decrease the revealing round for the message for any process, and not broadcasting this new "useless" message may very well have no consequence on the correct termination of the algorithm. This would reduce Metric 1 (the number of messages) in both good and bad cases.

1

  In synchronous round R = 1 do 2 broadcast(MSG({m:p sender })); 3 brb_deliver(m).

-

  WBP-WEIGHT-MONOTONY: If WBP holds for a given weight, it should also hold for any smaller weight: ∀w ≥ w : WBP(m, w, view ) =⇒ WBP(m, w , view ). -WBP-VIEW-MONOTONY: If WBP holds for a given view, it should also hold for any larger view (in the sense of set inclusion): ∀view ⊆ view , WBP(m, w, view ) =⇒ WBP(m, w, view ).

Lemma 4 .

 4 If the pair (WBP, reveal_round) is λ good -BRB-robust, then, Algorithm 2 verifies the BRB-NO-DUPLICITY Property.

Figure 2 :

 2 Figure 2: The pattern of signature chains forming a WBP GCL predicate of weight |W | = 6 at round R for message m at p i in a setting with t = 8. The predicate must verify subchain(γ, 3, t + 3 -|W |) ∩ W = ∅, which ensures its conspicuity (Lemma 10).

3 SAlgorithm 3 :

 33 def = q ∈ Π | q backs m in round 1 or 2 in view , and 4 W def = S \ set subchain(γ, 3, t + 3 -w) , the following holds 5 |W | ≥ w.At least w processes back m in the first 2 rounds in view .6 reveal_round GCL (w) def = max(2, t + 3 -w). The weight-based predicate WBP GCL and its associated revealing function reveal_round GCL . The pair (WBP GCL , reveal_round GCL ) ensures delivery in max 2, t + 3 -w rounds in good cases when used in Algorithm 2. rithm 2 the predicate and reveal function (WBP GCL , reveal_round GCL ) shown in Algorithm 3.

  ) |W | ≥ W -(w -w ), (by definition of W ) |W | ≥ w -(w -w ) = w .

Table 1 :

 1 Assumptions, guarantees, and latencies of synchronous signature-based BRB algorithms (

*

indicates an expected number of rounds)

  : • • • :p i received by p i at line 5. As p i is correct, it only accepts and processes valid chains of signatures by assumption, in which m is first signed by p sender (i.e. p i 1 = p sender ). Since p sender is correct, and we have assumed signatures to be secure, for m to be signed by p sender , p sender must have executed line 2 of Algorithm 1, and must therefore have brb-broadcast m. Lemma 2. Algorithm 2 verifies the BRB-NO-DUPLICATION Property.Proof. Trivially, this is because once a correct process executes a brb_deliver operation (either at line 3 of Algorithm 1, or lines 9 or 14 of Algorithm 2), it terminates its execution, either immediately or at line 4 in the next round, without invoking brb_deliver.

Lemma 3. Algorithm 2 verifies the BRB-LOCAL-DELIVERY property.

  Case 1: If p i ∈ γ, p i has signed a chain m:p sender :γ at line 6 of Alg. 2 during a round R < R + 1 (where γ :p i is a prefix of γ), and p i has broadcast the chain m:p sender :γ :p i to all processes (since p i is correct) at line 3 during the communication step of the following round R + 1 ≤ R + 1. Therefore m:p sender :γ :p i ∈ view j [R + 1], which implies truncate 2 (m:p sender :γ) = truncate 2 (m:p sender :γ :p i )∈ truncate 2 (view j [R + 1]) ⊆ T 2,j [R + 2].-Case 2: If p i ∈ γ, p i signs m:p sender :γ during round R + 1 and as above broadcasts m:p sender :γ:p i at round R + 2 to all processes. (By construction, the fact that p i executes the computation step of round R + 1 ≤ t implies that it executes the communication step of round R + 2.) This similarly implies truncate 2 (m:p sender :γ) = truncate 2 (m:p sender :γ:p i )

  now prove that truncate 2 view i [t+1] ⊆ T 2,j [t+1]. Consider m:p sender :γ ∈ view i [t+1]. As p i is correct, it only accepts acyclic signature chains, and p sender ∈ γ. This implies |{p sender } ∪ set(γ)| = |{p sender }| + |set(γ)| = 1 + t. So {p sender } ∪ set(γ) therefore contains at least one correct process, p k . As p sender is Byzantine by lemma assumption, p k ∈ γ, and p k therefore has signed a chain m:p sender :γ at line 6 of Alg. 2 before or during round t, where γ :p k is a prefix of γ. As a result, p k has broadcast the resulting chain m:p sender :γ :p k to all other processes during the following round R ≤ t + 1. This implies m:p sender :γ :p k ∈ view j [R ], and hence truncate 2 (m:p sender :γ) = truncate 2 (m:p sender :γ :p k )∈ truncate 2 (view j [R ]) ⊆ T 2,j [t + 1].This last equation shows that truncate 2 (viewi [t + 1]) ⊆ T 2,j [t + 1], which injected in (8) yields T 2,i [t + 1] ⊆ T 2,j [t + 1]. By inverting p i and p j , by the same reasoning we obtain T 2,j [t + 1] ⊆ T 2,i [t + 1], which concludes the Lemma's proof.Corollary 2. Let p sender be Byzantine, p i and p j be two correct processes, such that p i executes the computation step of at least the first r ∈ [1..t + 1] rounds, and p j executes the communication step of all t + 1 rounds. Then we have T 2,i [r] ⊆ T 2,j [t + 1].

•

  Case 1: p i ∈ S i,R . Because p i = p sender and p i is correct, if p i ∈ S i,R , then p i has signed a chain m:p sender :p i , and broadcast this chain in round 2 to all other correct processes, including p j . As a result, m:p sender :p i ∈ view t+1 In this case, because γ i is acyclic, it contains at least one correct process p k . Since p k is correct, it has signed and then broadcast a chain m:γ k :p k to all processes including p j at the latest by round t + 1. As a result, m:γ k :p k ∈ view t+1 j . Furthermore, by construction, γ k :p k is a prefix of γ i , which implies set subchain(γ k :p k , 3, t + 3 -w) ⊆ set(γ i 3..t+3-w ), which proves the sublemma.• Case 3:p i ∈ S i,R ∧ |γ i | < t + 1. If p i ∈ γ i ,then we can reuse the reasoning of Case 2 with p :p i , 3, t + 3 -w) ⊆ set subchain(γ i , 3, t + 3 -w) ∪ {p i },

	Furthermore, since m:p sender :p i only contains 2 processes,
	set subchain(p sender :p i , 3, t + 3 -w) = ∅,
	which proves the sublemma.
	⊆ set(γ i 3..t+3-w ) ∪ {p i }.	(by definition of γ i 3..t+3-w )
	As a result
	set subchain(γ

j

(assuming t ≥ 1).

• Case 2: |γ

i | = t + 1. k = p i , which proves the sublemma. If p i ∈ γ i , since |γ i | < t + 1, p i has received γ i in a round r i = |γ i |,

and because it is correct, p i has signed and broadcast the chain m:γ i :p i in round r i + 1 ≤ t + 1 to all processes, including p j . As a result m:γ i :p i ∈ view t+1 j . Furthermore set subchain(γ i i :p

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[START_REF] Wan | Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions[END_REF], 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".

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.

Although correct processes can deliver their message in about 2 × 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 × n/(n -t) rounds in good-cases.

The extra round of communication induced by delivered i is needed to ensure all correct processes observe the same predicate WBP as pi. 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.

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.

When R end ≤ t, Algorithm 2 brb-delivers in round R 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 end + 1 rounds of communication: the first round followed by R end subsequent rounds.

Declarations

Funding. 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).

Competing Interests. 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.

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

A Communication Complexity

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, as Byzantine processes can 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 useful to consider these 2 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 this respect, Metric 3 does not allow a fine-grained analysis of communication complexity.

In the following, "the algorithm" refers to Algorithm 2 in which we use the WBP GCL predicate described in Algorithm 3.

A.1 Metric 1: Number of messages

Currently, the 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 × n messages in each later round, which adds up to n + c × n × R end messages (at most), where R end is the maximum number of rounds needed for the algorithm to brb-deliver messages at correct processes. 7 This upper bound can be further refined depending on whether the execution occurs in a good or bad case.

A.1.1 Good case (correct sender)

In a good case, we have R end = 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) × n × max(2, t + 3 -c) messages sent by correct processes, which boils down to n + 2 × n × (n -1) = O(n 2 ) messages when all processes are correct (c = n, assuming n > t).

A.1.2 Bad case (Byzantine sender)

In a bad case, we have at worst R end = t + 1. When R end = t + 1, however, correct processes do not execute any extra round of communication (see Footnote 7). This, therefore, leads to at most n + (c -1) × n × (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 ).