Timothé Albouy
email: timothe.albouy@irisa.fr

Davide Frey
email: davide.frey@inria.fr

Michel Raynal
email: michel.raynal@irisa.fr

François Taïani
email: francois.taiani@irisa.fr

Asynchronous Byzantine Reliable Broadcast With a Message Adversary

Keywords: Asynchronous system, Byzantine processes, Churn, Message adversary, Message losses, Message-passing, Message signatures, Reliable broadcast, Transient disconnection

This paper considers the problem of reliable broadcast in asynchronous authenticated systems, in which n processes communicate using signed messages and up to t processes may behave arbitrarily (Byzantine processes). In addition, for each message m broadcast by a correct (i.e., non-Byzantine) process, a message adversary may prevent up to d correct processes from receiving m. (This message adversary captures network failures such as transient disconnections, silent churn, or message losses.) Considering such a "double" adversarial context and assuming n > 3t + 2d, a reliable broadcast algorithm is presented. Interestingly, when there is no message adversary (i.e., d = 0), the algorithm terminates in two communication steps (so, in this case, this algorithm is optimal in terms of both Byzantine tolerance and time efficiency). It is then shown that the condition n > 3t + 2d is necessary for implementing reliable broadcast in the presence of both Byzantine processes and a message adversary (whether the underlying system is enriched with signatures or not).

Introduction

Reliable broadcast Introduced in the mid-eighties, Reliable Broadcast is a fundamental communication abstraction that lies at the center of fault-tolerant asynchronous distributed systems. Formally defined in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF], it allows each process to broadcast messages in the presence of process failures, with well-defined delivery properties 1 . In turn, these properties make it possible to design provably correct distributed software for upper-layer applications based on such a broadcast abstraction.

Intuitively, reliable broadcast guarantees that the non-faulty processes deliver the same set of messages, which includes at least all the messages they broadcast. This set may also contain messages broadcast by faulty processes. The fundamental property of reliable broadcast lies in the fact that no two non-faulty processes deliver different sets of messages [START_REF] Ch | Reliable and secure distributed programming[END_REF][START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF].

When some processes may suffer from Byzantine failures [START_REF] Lamport | The Byzantine generals problem[END_REF], designing a reliable broadcast communication abstraction that tolerate such failures is far from trivial. Such an algorithm is called Byzantinetolerant reliable broadcast (BRB) and we say that a process brb-broadcasts and brb-delivers messages. The most famous BRB algorithm is due to Bracha [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] (1987). For an application message, this algorithm gives rise to three sequential communication steps and up to (n -1)(2n + 1) implementation messages sent by correct processes. This algorithm requires n > 3t, which is optimal in terms of fault tolerance.

Recent works related to reliable broadcast Due to its fundamental nature, BRB has been addressed by many authors. Here are a few recent results. Similarly to Bracha's algorithm, all these algorithms assume an underlying fully connected reliable network.

• The versatility dimension of Bracha's algorithm has been analyzed in [START_REF] Hirt | Multi-threshold asynchronous reliable broadcast and consensus[END_REF][START_REF] Raynal | On the versatility of Bracha's Byzantine reliable broadcast algorithm[END_REF].

• Addressing efficiency issues, the BRB algorithm presented in [START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF] implements the reliable broadcast of an application message with only two communication steps and up to n2 -1 implementation messages sent by correct processes. The price to pay for this gain in efficiency is a weaker t-resilience, namely t < n/5. Hence, this algorithm and Bracha's algorithm differ in their tradeoff between t-resilience and message/time efficiency.

• Scalable BRB is addressed in [START_REF] Guerraoui | Scalable Byzantine reliable broadcast[END_REF]. The goal of this work is to avoid paying the O(n 2 ) message complexity price. To this end, the authors use a non-trivial message-gossiping approach which allows them to design a sophisticated BRB algorithm satisfying probability-dependent properties.

• BRB in dynamic systems is addressed in [START_REF] Guerraoui | Dynamic Byzantine reliable broadcast[END_REF] (dynamic means that a process can enter and leave the system at any time). In their article, the authors present an efficient BRB algorithm for such a context. This algorithm assumes that, at any time, there are at least two times more correct processes than Byzantine ones in the system.

• An efficient algorithm for BRB with long inputs of b bits using lower costs than b single-bit instances is presented in [START_REF] Nayak | Improved extension protocols for Byzantine broadcast and agreement[END_REF]. This algorithm, which assumes t < n/3, achieves the best possible communication complexity of Θ(nb) input sizes. This article also presents an authenticated extension of this solution.

The work presented in this paper 2 goes beyond the previous proposals by considering the conjunction of two types of adversary: as in the above works, processes may be Byzantine, but in addition a message adversary may also remove implementation messages between correct processes. More precisely, this work addresses the problem of fault-tolerant reliable broadcast in asynchronous n-process message-passing systems enriched with message signatures, in which up to t processes are Byzantine, and a message adversary that may prevent up to d non-Byzantine processes from delivering an implementation message broadcast by a non-Byzantine process. This dual fault model originated from our research on the reconciliation of local process states in distributed Byzantine-tolerant money transfer systems (a.k.a. cryptocurrencies), in which processes become temporarily disconnected. Several researchers have indeed pointed out the fundamental role that broadcast abstractions play in Byzantine money transfer systems (see, for instance, [START_REF] Auvolat | Money Transfer Made Simple: a Specification, a Generic Algorithm, and its Proof[END_REF][START_REF] Cohen | Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer[END_REF][START_REF] Collins | Online Payments by Merely Broadcasting Messages[END_REF][START_REF] Danezis | Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus[END_REF][START_REF] Guerraoui | The Consensus Number of a Cryptocurrency[END_REF][START_REF] Guerraoui | Dynamic Byzantine reliable broadcast[END_REF]). This crucial role naturally leads to considering how Byzantine broadcast can be expanded to more volatile and dynamic settings, thus motivating our proposal to combine traditional Byzantine faults with a message adversary.

The paper is made up of 5 sections.

• Section 2 defines the computing model and the Message Adversary-Tolerant Byzantine Reliable Broadcast communication abstraction (or MBRB for short).

• Section 3 presents a signature-based algorithm implementing the MBRB abstraction, proves it is correct, and evaluates its cost. When there is no message adversary, this algorithm is optimal from both Byzantine resilience and the number of communication steps • Section 4 shows that the condition n > 3t + 2d is necessary and sufficient for implementing the MBRB communication abstraction (be the underlying system enriched with signatures or not).

• Finally, Section 5 concludes the article.

2 Computing Model and MBRB Abstraction

Computing Model

Process model The system is composed of n asynchronous sequential processes denoted p 1 , ..., p n . Each process p i has an identity, and 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] Pease | Reaching agreement in the presence of faults[END_REF]. Let us notice that Byzantine processes can collude to fool the 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.

Moreover, given an execution, c denotes the number of processes that effectively behave correctly in that execution. We always have n -t ≤ c ≤ n. While this number remains unknown to correct processes, it is used in the following to analyze and characterize (more precisely than using its worse value n -t) the guarantees provided by the proposed algorithms.

Communication model

The processes communicate through a fully connected asynchronous pointto-point communication network. Although this network is assumed to be reliable-in the sense that it neither corrupts, duplicates, nor creates messages-it may nevertheless lose messages due to the actions of a message adversary (defined below).

Let MSG be a message type and v the associated value. A process can invoke the unreliable operation broadcast MSG(v), which is a shorthand for "for all i ∈ {1, • • • , n} do send MSG(v) to p j end for". It is assumed that all the correct processes invoke broadcast to send messages. As we can see, the operation broadcast MSG(v) is not reliable. As an example, if the invoking process crashes during its invocation, an arbitrary subset of processes receive the message implementation message MSG(v). Moreover, due to its very nature, a Byzantine process can send messages without using the macro-operation broadcast.

From a terminology point of view, at the system/network level, we say that messages are broadcast and received. Moreover, a message generated by the algorithm is said to be an implementation message (imp-message in short), while a message generated by the application layer is said to be an application message (app-message in short).

Message adversary

The notion of a message adversary (MA) was implicitly introduced in [START_REF] Santoro | Time is not a healer[END_REF] (under the name transient faults and ubiquitous faults) and then used (sometimes implicitly) in many works (e.g., [START_REF] Afek | Asynchrony from synchrony[END_REF][START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF][START_REF] Raynal | Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors[END_REF][START_REF] Santoro | Agreement in synchronous networks with ubiquitous faults[END_REF][START_REF] Tseng | Exact Consensus under Global Asymmetric Byzantine Links[END_REF]). A short tutorial on message adversaries is presented in [START_REF] Raynal | Message adversaries. Encyclopedia of Algorithms[END_REF].

Let d be an integer constant such that 0 ≤ d < c. The communication network is under the control of an adversary which eliminates imp-messages sent by processes, so that these imp-messages appear as being lost. More precisely, when a correct process invokes broadcast MSG(v), the message adversary is allowed to arbitrarily suppress up to d copies of the imp-message MSG(v) that were intended to correct processes. This means that, despite the fact the sender is correct, up to d correct processes may miss the imp-message MSG(v) 4 .

As an example, consider a set D of correct processes, where 1 ≤ |D| ≤ d, such that during some period of time, the adversary suppresses all the imp-messages sent to them. It follows that, during this period of time, this set of processes appears as a set of correct processes that are (unknowingly) inputdisconnected from the other correct processes. Depending on the message adversary, the set D may vary with time. Let us notice that d = 0 corresponds to the weakest possible message adversary: it corresponds to a classical static system where some processes are Byzantine but no imp-message is lost (the network is fully reliable).

Let us remark that this type of message adversary is stronger, and therefore covers, the more specific case of silent churn, in which processes (nodes) may decide to disconnect from the network. While disconnected, such a process silently pauses its algorithm (a legal behavior in our asynchronous model), and is implicitly moved (by the adversary) to the D adversary-defined set. Upon coming back, the node resumes its execution, and is removed from D by the adversary. 5Informally, in a silent churn environment, a correct process may miss imp-messages sent by other processes while it is disconnected from the network. The adjective "silent" in silent churn expresses the fact that no notification is sent on the network by processes whenever they leave or join the system: there is no explicit "attendance list" of connected processes, and processes are given no information on the status (connected/disconnected) of their peers. In this regard, the silent churn model diverges from the classical approach when designing dynamic distributed systems, in which processes send imp-messages on the network notifying their connection or disconnection [START_REF] Guerraoui | Dynamic Byzantine reliable broadcast[END_REF]. The silent churn model is a good representation of real-life large-scale peer-to-peer systems, where peers leaving the network typically do so in a completely silent manner (i.e., without warning other peers).

Let us also observe that silent churn allows us to model input-disconnections due to process mobility. When a process moves from one location to another, the sender's broadcasting range may not be large enough to ensure that the moving process remains input-connected. An even more prosaic example would be one where a user simply turns off their device, or disable its Internet connection, preventing it from receiving or sending any further imp-messages. In this context, we consider that the message adversary removes all the incoming imp-messages from the corresponding process until the device reconnects.

Let us mention that the loss of imp-messages caused by a message adversary may be addressed using a reliable unicast protocol. These protocols were originally introduced to provide reliable channels on top of an unreliable network subject to imp-message losses. The principle is simple: the sender keeps sending idempotent imp-messages at regular intervals through an unreliable channel until it receives an acknowledgement from the receiver. This principle notoriously lies at the core of the Transmission Control Protocol (TCP), although with important practical adaptations, as TCP uses timeouts to close a malfunctioning or otherwise idle connection, typically after a few minutes.

But because there is no way to detect that a process has crashed or disconnected in an asynchronous environment, an ideal reliable unicast protocol (i.e. one that keeps on re-transmitting until success) needs to treat disconnected processes the same way as slow processes or as if there were packet losses in the network: the sender will thus potentially send infinitely many imp-messages to a disconnected receiver.

To overcome this issue, some works leverage causal dependencies to avoid resending old imp-messages: if an acknowledgement is received by the sender for a given imp-message, then it can stop resending the imp-messages that causally precede this imp-message and that have not been acknowledged yet (e.g. [START_REF] Danezis | Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus[END_REF]). However, this approach still assumes that eventually, every communication channel lets some imp-messages pass, which is not always the case in our model, where the message adversary can permanently sever up to d channels.

Digital signatures We assume the availability of an asymmetric cryptosystem to sign data (in practice, imp-messages) and verify its authenticity. We assume signatures are secure, and therefore that the computing power of the adversary is bounded. Every process in the network has a public/private key pair. We suppose that the public keys are known to everyone, and that the private keys are kept secret by their owner. Everyone also knows the mapping between any process' identity i and its public key. Additionally, we suppose that each process can produce at most one signature per imp-message.

The signatures are used to cope with the net effect of the Byzantine processes and the fact that impmessages broadcast (sent) by correct processes can be eliminated by the message adversary. A noteworthy advantage of signatures is that, despite the unauthenticated nature of the point-to-point communication channels, signatures allow correct processes to verify the authenticity of imp-messages that have not been directly received from their initial sender, but rather relayed through intermediary processes. Signatures provide us with a network-wide non-repudiation mechanism: if a Byzantine process issues two conflicting imp-messages to two different subsets of correct processes, then the correct processes can detect the malicious behavior by disclosing to each other the Byzantine signed imp-messages. 6

Message Adversary-Tolerant Byzantine Reliable Broadcast (MBRB)

This paper introduces a new broadcast abstraction we have called Message Adversary-Tolerant Byzantine Reliable Broadcast (MBRB for short.) The MBRB communication abstraction is composed of two matching operations, denoted mbrb_broadcast and mbrb_deliver. It considers that an identity (i, sn) (sender identity, sequence number) is associated with each app-message, and assumes that any two app-messages mbrb-broadcast by the same correct process have different sequence numbers. Sequence numbers are one of the most natural ways to design "multi-shot" reliable broadcast algorithms, that is, algorithms where the broadcast operation can be invoked multiple times with different app-messages.

When, at the application level, a process p i invokes mbrb_broadcast(m, sn), where m is the appmessage and sn the associated sequence number, we say p i "mbrb-broadcasts (m, sn)". Similarly, when p i invokes mbrb_deliver(m, sn, j), where p j is the sender process, we say p i "mbrb-delivers (m, sn, j)". We say that the app-messages are mbrb-broadcast and mbrb-delivered (while, as said previously, the imp-messages algorithm are broadcast and received).

Correctness specification Because of the message adversary, we cannot always guarantee that an app-message mbrb-delivered by a correct process is eventually mbrb-delivered by all correct processes. Hence, in the MBRB specification, we introduce a variable ℓ which indicates the strength of the global delivery guarantee of the primitive: if one correct process mbrb-delivers an app-message then ℓ correct processes eventually mbrb-deliver this app-message. 7 The MBRB-broadcast abstraction is defined by the following properties:

• Safety:

-MBRB-Validity (no spurious message). If a correct process p i mbrb-delivers an app-message m from a correct process p j with sequence number sn, then p j mbrb-broadcast m with sequence number sn. -MBRB-No-duplication. A correct process p i mbrb-delivers at most one app-message m from a process p j with sequence number sn. -MBRB-No-duplicity. No two different correct processes mbrb-deliver different app-messages from a process p i with the same sequence number sn.

• Liveness:

-MBRB-Local-delivery. If a correct process p i mbrb-broadcasts an app-message m with sequence number sn, then at least one correct process p j eventually mbrb-delivers m from p i with sequence number sn. -MBRB-Global-delivery. If a correct process p i mbrb-delivers an app-message m from a process p j with sequence number sn, then at least ℓ correct processes mbrb-deliver m from p j with sequence number sn.

It is implicitly assumed that a correct process does not use the same sequence number twice. Let us observe that, since at the implementation level the message adversary can always suppress all the imp-messages sent to a fixed set D of d processes, the best-guaranteed value for ℓ is c -d. Furthermore, let us notice that the constraint n > 2d prevents the message adversary from partitioning the system.

Performance metrics In addition to the correctness specification, we define two metrics that capture the performance of an algorithm implementing the MBRB specification: λ and µ, which respectively denote the communication step complexity and the imp-message complexity of the algorithm. They are defined as follows:

• MBRB-Time-cost. If a correct process p i mbrb-broadcasts an app-message m with sequence number sn, then ℓ correct processes mbrb-deliver m from p i with sequence number sn in at most λ communication steps.

• MBRB-Message-cost. The mbrb-broadcast of an app-message by a correct process p i entails the sending of at most µ imp-messages by correct processes.

Byzantine Reliable Broadcast (BRB) If ℓ = c (obtained when d = 0), the previous specification boils down to Bracha's seminal specification [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF], which defines the Byzantine reliable broadcast (BRB) communication abstraction. Hence, the BRB abstraction is a sub-case of MBRB.

A Signature-based Algorithm Implementing the MBRB Abstraction

This section presents Algorithm 1, which implements the MBRB communication abstraction in an asynchronous setting under the constraint n > 3t+2d > 0. When considering d = 0, this algorithm provides both t-tolerance optimality (as in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]) and step optimality (as in [START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF]): it only assumes n > 3t, and guaranteed mbrb-delivery of an app-message in only two communication steps 8 . It follows that signatures can help save one communication step compared to classical signature-free BRB algorithms that assume t < n/3. Algorithm 1 fulfills the MBRB-Global-delivery property with ℓ = c -d under the following assumption:

• mbrb-Assumption: n > 3t + 2d.

Preliminaries

Implementation message types The algorithm uses only one imp-message type, BUNDLE, that carries the signatures backing a given app-message m, along with m's content, sequence number, and emitter. BUNDLE imp-messages propagate through the network using controlled flooding.

Local data structures Each (correct) process saves locally the valid signatures (i.e., the signed fixedsize digests of a certain data) that it has received from other processes using BUNDLE imp-messages. Each signature "endorses" a certain app-message (m, sn, j). When certain conditions are met (described below), a process further broadcasts in a BUNDLE imp-message all signatures it knows for a given triplet (m, sn, j). A correct process p i saves at most one signature for a given triplet (m, sn, j) per signing process p k .

Time measurement For the proofs related to MBRB-Time-cost (Lemmas 7-10), we assume that the duration of local computations is negligible compared to that of imp-message transfer delays, and consider them to take zero time units. As the system is asynchronous, the time is measured under the traditional assumption that all the imp-messages have the same transfer delay.

Algorithm

At a high level, Algorithm 1 works by producing, forwarding, and accumulating witnesses of an initial mbrb-broadcast operation, until a large-enough quorum is observed by at least one correct process, at which point this quorum is propagated in one final unreliable broadcast operation.

Witnesses take the form of signatures for a given triplet (m, sn, i), where m is the app-message, sn its associated sequence number and i the identity of the sender p i (which also produces a signature for (m, sn, i)). Signatures serve to ascertain the provenance and authenticity of these propagated BUN-DLE imp-messages, thus providing a key ingredient to tolerate the limited reliability of the underlying network. They also authenticate the invoker of the mbrb_broadcast operation, and finally, in the last phase of the algorithm, they allow the propagation of a cryptographic proof that a quorum has been reached, thereby ensuring that enough correct processes eventually mbrb-deliver the app-message that was mbrb-broadcast.

operation mbrb_broadcast(m, sn) is (1) save signature for (m, sn, i) by pi;

(2) broadcast BUNDLE(m, sn, i, {all saved signatures for (m, sn, i)}).

when BUNDLE(m, sn, j, sigs) is received do (3) if (-, sn, j) not already mbrb-delivered ∧ sigs contains the valid signature for (m, sn, j) by pj then (4) save all unsaved valid signatures for (m, sn, j) of sigs; [START_REF] Auvolat | Money Transfer Made Simple: a Specification, a Generic Algorithm, and its Proof[END_REF] if (-, sn, j) not already signed by pi then [START_REF] Bonomi | Practical Byzantine Reliable Broadcast on Partially Connected Networks[END_REF] save signature for (m, sn, j) by pi; [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] broadcast BUNDLE(m, sn, j, {all saved signatures for (m, sn, j)}) [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] end if; [START_REF] Ch | Reliable and secure distributed programming[END_REF] if strictly more than n+t 2 signatures for (m, sn, j) are saved then [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF] broadcast BUNDLE(m, sn, j, {all saved signatures for (m, sn, j)}); [START_REF] Cohen | Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer[END_REF] mbrb_deliver(m, sn, j) [START_REF] Collins | Online Payments by Merely Broadcasting Messages[END_REF] end if (13) end if.

Algorithm 1: A signature-based implementation of the MBRB communication abstraction (code for p i )

In more detail, when a (correct) process p i invokes mbrb_broadcast(m, sn), it builds and signs the triplet (m, sn, i) to guarantee its non-repudiation, and saves locally the resulting signature (line 1). Next, p i broadcasts the BUNDLE imp-message containing the signature that it just produced (line 2). When a correct process p i receives a BUNDLE(m, sn, j, sigs) imp-message, it first checks if no appmessage has already been mbrb-delivered for the given sequence number sn and sender p j , and if p j signed the app-message (line 3). If this condition is satisfied, p i saves all the new valid signatures inside the sigs set (line 4). Next, p i creates and saves its own signature for (m, sn, j) and then broadcasts it in a BUNDLE imp-message, if it has not already done so previously (line 5-8). Finally, if p i has saved a quorum of strictly more than n+t 2 signatures for the same triplet (m, sn, j), it broadcasts a BUNDLE imp-message containing all these signatures and mbrb-delivers the triplet (lines 9-12). 9Remark The reader can notice that the system parameters n and t appear in the algorithm, whereas the system parameter d does not. Naturally, they all explicitly appear in the proof.

Algorithm proof

This section proves the correctness and performance properties of MBRB.

Theorem 1. If the mbrb-Assumption is satisfied, Algorithm 1 implements the mbrb-broadcast of an app-message by a correct process with the following guarantees:

• ℓ = c -d correct processes, • λ =        2 if d < c-⌊ n+t 2 ⌋ ⌊ n+t 2 ⌋+1 3 if d < c -c × n+t 2 > 3 otherwise        communication steps,
• µ = 2n 2 imp-messages.

The proof follows from the next lemmas.

Lemma 1 (MBRB-Validity). If a correct process p i mbrb-delivers m from a correct process p j with sequence number sn, then p j has previously mbrb-broadcast m with sequence number sn.

Proof. If a correct process p i mbrb-delivers (m, sn, j) (where p j is correct) at line 11, then it has passed the condition at line 3, which means that it must have witnessed a valid signature for (m, sn, j) by p j . Since signatures are secure, the only way to create this signature is for p j to execute the instruction at line 1, during the mbrb_broadcast(m, sn) invocation.

Lemma 2 (MBRB-No-duplication).

A correct process p i mbrb-delivers at most one app-message from a process p j with a given sequence number sn.

Proof. This property derives trivially from the condition at line 3.

Lemma 3 (MBRB-No-duplicity).

No two different correct processes mbrb-deliver different app-messages from a process p i with the same sequence number sn.

Proof. Let us consider two correct processes p a and p b which respectively mbrb-deliver (m, sn, i) and (m ′ , sn, i). Due to the condition at line 9, p a and p b must have saved (and thus received) two sets Q a and Q b containing strictly more than n+t 2 signatures for (m, sn, i) and (m ′ , sn, i), respectively. We thus have

|Q a | > n+t 2 and |Q b | > n+t 2 . As we have |A∩ B| = |A|+ |B|-|A∪ B| ≥ |A|+ |B|-n > 2× n+t
2 -n = t, A and B have at least one correct process p k in common, which must have signed both (m, sn, i) and (m ′ , sn, i). But before signing (m, sn, i) at line 1 or 6, p k checks that it did not sign a different app-message from the same sender and with the same sequence number, whether it be implicitly during a brb_broadcast(m, sn) invocation or at line 5. Thereby, m is necessarily equal to m ′ . Lemma 4 (MBRB-Local-delivery). If a correct process p i mbrb-broadcasts an app-message m with sequence number sn, then at least one correct process p j mbrb-delivers m from p i with sequence number sn.

Proof. If a correct process p i mbrb-broadcasts (m, sn), then it broadcasts its own signature sig i for (m, sn, i) in a BUNDLE(m, sn, i, {sig i }) message at line 2. As p i is correct, it does not sign another triplet (m ′ , sn, i) where m ′ = m, therefore it is impossible for a correct process to mbrb-deliver (m ′ , sn, i) at line 11, because it cannot pass the condition at line 3.

Let us denote by K the set of correct processes that receive a message BUNDLE(m, sn, i, {sig i , ...}) at least once. The first one of such BUNDLE messages that a process of K receives can be the one p i initially broadcast at line 2, but it can also be a BUNDLE message broadcast by a correct process at lines 7 or 10, or it can even be a BUNDLE message sent by a Byzantine process. In any case, the first time the processes of K receive such a BUNDLE message, they pass the condition at line 3, and they also pass the condition at line 5, except for p i if it belongs to K. Consequently, each process p k of K necessarily broadcasts its own signature sig k for (m, sn, i) in a BUNDLE(m, sn, i, {sig k , sig i , ...}) message.

By construction of the algorithm, the set K of correct processes that receive a BUNDLE(m, sn, i, {sig i , ...}) message is equal to the set of correct processes p k that broadcast a BUNDLE(m, sn, i, {sig k , sig i , ...}). By the definition of the message adversary, a message BUNDLE(m, sn, i, {sig k , sig i , ...}) broadcast by a correct process p k is eventually received by at least c -d correct processes. Hence, the minimum number of signatures for (m, sn, i) made by processes of K that is also received by processes of K globally is |K|(c -d). It follows that a given process of K individually receives on average the distinct signatures of at least |K|(c -d)/|K| = c -d processes of K.

From mbrb-Assumption, we have 3t + 2d

< n ⇐⇒ n + 3t + 2d < 2n ⇐⇒ n + t < 2n -2t -2d ⇐⇒ n+t 2 < n -t -d ≤ c -d (as n -t ≤ c).
As a result, at least one process p j of K (ergo one correct process) receives a set S (in possibly multiple BUNDLE messages) of strictly more than n+t 2 valid distinct signatures for (m, sn, i). When p j receives the last signature of S, there are two cases:

• Case if p j does not pass the condition at line 3.

As processes of K are correct, then when they broadcast a BUNDLE(m, sn, i, sigs) message, they necessarily include sig i in sigs, which implies that sig i is necessarily in S. Therefore, if p j does not pass the condition at line 3, it is because p j already mbrb-delivered some (-, sn, i). But let us remind that, as p i is correct, it is impossible for p j to mbrb-deliver anything different from (m, sn, i). Therefore, p j has already mbrb-delivered (m, sn, i).

• Case if p j passes the condition at line 3. Process p j then saves all signatures of S at line 4, and after it passes the condition at line 9 (as |S| > n+t

2 ) and finally mbrb-delivers (m, sn, i) at line 11.

Lemma 5 (MBRB-Global-delivery). If a correct process p i mbrb-delivers an app-message m from p j with sequence number sn, then at least ℓ = c -d correct processes mbrb-deliver m from p j with sequence number sn.

Proof. If a correct process p i mbrb-delivers (m, sn, j) at line 11, it must have saved a set sigs of strictly more than n+t 2 valid distinct signatures because of the condition at line 9. Let us remark that sigs necessarily contains the signature for (m, sn, i) by p i because of the condition at line 3. Additionally, p i must also have broadcast BUNDLE(m, sn, i, sigs) at line 10, that, by definition of the message adversary, is received by a set K of at least c -d correct processes. For each process p k of K:

• If p k does not pass the condition at line 3, it is necessarily because it has already mbrb-delivered some (-, sn, j) at line 11. But because of MBRB-No-duplicity, p k has necessarily mbrb-delivered (m, sn, j).

• If p k passes the condition at line 3, then it saves all signatures of sigs at line 4 and then passes the condition at line 9 and finally mbrb-delivers (m, sn, j) at line 11.

Therefore, all processes of K (which, as a reminder, are at least c -d = ℓ) necessarily mbrb-deliver (m, sn, j) at line 11.

Lemma 6. c -d > n+t 2 .
Proof. We have the following:

c -d ≥ n -t -d = 2n -2t -2d 2 , (by definition of c) > n + 3t + 2d -2t -2d 2 , ( by mbrb-Assumption)
> n + t 2 ≥ n + t 2 .
Lemma 7. If a correct process p i mbrb-broadcasts (m, sn), then at least c -d -

d⌊ n+t 2 ⌋ c-d-⌊ n+t
2 ⌋ correct processes mbrb-deliver (m, sn, i) at most two communication steps later.

Proof. If a correct process p i mbrb-broadcasts (m, sn), then it broadcasts its own signature sig i for (m, sn, i) in a BUNDLE(m, sn, i, {sig i }) imp-message at line 2. Let us denote by K the set of correct processes that receive this BUNDLE(m, sn, i, {sig i }) imp-message from p i during the same communication step, and let k be the number of processes in K, such that c -d ≤ k = |K| ≤ c (by definition of the message adversary). By construction of the algorithm, every process p x of K passes the condition at line 3, and therefore broadcasts a BUNDLE(m, sn, i, {sig x , sig i }) imp-message, whether it be at line 2 for p i , or at line 7 for any other process of K.

Let A and B define two partitions of the set of all correct processes (A ∪ B is the set of all correct processes, and A ∩ B = ∅). A denotes the set of correct processes that receive strictly more than n+t 2 signatures for (m, sn, i) from processes of K two communication steps after p i mbrb-broadcast (m, sn), while B denotes the set of remaining correct processes of K that receive at most n+t 2 signatures for (m, sn, i) from processes of K two communication steps after p i mbrb-broadcast (m, sn). Let ℓ 2 be the size of A: ℓ 2 = |A|. By construction, |B| = c -ℓ 2 . Let s A and s B respectively denote the number of signatures for (m, sn, i) from processes of K received by processes of A and B at most two communication steps after p i mbrb-broadcast (m, sn). Figure 1 represents the distribution of such signatures among processes of K, sorted by decreasing number of signatures received. Each processes of A can receive at most k signatures (that is, all signatures) from processes of K, while each process of B can receive at most ⌊ n+t 2 ⌋ signatures from processes of K two communication steps after p i mbrbbroadcasts (m, sn). For the sake of simplicity, we use q in the place of ⌊ n+t 2 ⌋ in some parts of this proof. From these observations, we infer the following inequalities:

# received signatures # correct processes k ℓ 2 A s A n+t 2 = q c B s B
ℓ 2 k ≥ s A , (c -ℓ 2 )q ≥ s B .
By the definition of the message adversary, a BUNDLE(m, sn, i, {sig x , sig i }) imp-message broadcast by a correct process p x is eventually received by at least c -d correct processes. As a consequence, in total, the minimum number of signatures for (m, sn, i) collectively received by correct processes as a result of broadcasts by processes in K in the first two asynchronous communication steps is k(c -d).

We thus have:

s A + s B ≥ k(c -d).
By combining the previous inequalities, we obtain:

ℓ 2 k + (c -ℓ 2 )q ≥ k(c -d), ℓ 2 k + cq -ℓ 2 q ≥ k(c -d), ℓ 2 k -ℓ 2 q ≥ k(c -d) -cq, ℓ 2 (k -q) ≥ k(c -d) -cq. (1)
By Lemma 6, we know that k ≥ c -d > n+t

2

= q, so we can rewrite (1) into:

ℓ 2 ≥ k(c -d) -cq k -q . ( 2
)
Let us define a function

f such that f (k) = k(c-d)-cq k-q
. As we seek the lowest guaranteed value for ℓ 2 , we want to find the minimum of f on k ∈ [c -d, c]. To this end, let us first study the derivative of f . The image f (k) is of the form u v , so we have:

f ′ (k) = u ′ v -uv ′ v 2 = (c -d)(k -q) -(k(c -d) -qc) (k -q) 2 , = (c -d)(k -q) -k(c -d) + qc (k -q) 2 = qc -q(c -d) (k -q) 2 = qd (k -q) 2 .
As q and d are by definition positive, we know that f ′ (k) = qd (k-q) 2 is positive, or null when d = 0. Therefore, f is monotonically increasing on k ∈ [c -d, c], and the minimum value for ℓ 2 can be found when k is also minimum, that is, when k = c -d. Thus, when we replace k by c -d in (2), we obtain:

ℓ 2 ≥ (c -d)(c -d) -cq c -d -q = (c -d)(c -d -q) -qd c -d -q , ≥ c -d - qd c -d -q . ( 3
)
Let us denote by ℓ 2,min the minimum number of correct processes that receive a quorum of strictly more than n+t 2 valid distinct signatures for (m, sn, i) two communication steps after p i mbrb-broadcast (m, sn), such that ℓ 2,min ≤ ℓ 2 = |A|. As the right hand side of (3) is not always an integer, we have:

ℓ 2,min = c -d - qd c -d -q = c -d + - qd c -d -q , = c -d - qd c -d -q , (as ∀ x ∈ R, ⌈-x⌉ = -⌊x⌋) = c -d - d⌊ n+t 2 ⌋ c -d -⌊ n+t 2 ⌋
.

(by definition of q)

Hence, at least ℓ 2,min = c -d -

d⌊ n+t 2 ⌋ c-d-⌊ n+t
2 ⌋ processes of K receive strictly more than n+t 2 valid distinct signatures for (m, sn, i) two communication steps after p i mbrb-broadcasts (m, sn). For every process p a of A:

• If p a does not pass the condition at line 3 after receiving the last signature of the quorum in a BUNDLE imp-message, it is necessarily because p a already mbrb-delivered some (-, sn, i), because processes of K are correct and all their BUNDLE imp-messages include the signature for (m, sn, i) by p i . But let us remind that, as the sender p i is correct, it is impossible for p a to mbrbdeliver anything different from (m, sn, i). Therefore, p a has already mbrb-delivered (m, sn, i) at line 11.

• If p a passes the condition at line 3 after processing the last BUNDLE(m, sn, i, {sig i , sig x }) impmessage of the quorum from a process p x , then p a saves the signature sig x at line 4, and after it passes the condition at line 9 (as it has saved strictly more than n+t 2 signatures) and finally mbrb-delivers (m, sn, i) at line 11.

Therefore, all processes of A, which are at least ℓ 2,min = c -d - Proof. Let us assume that a correct process p i mbrb-broadcasts (m, sn) and that d < c -c × n+t 2 . Process p i must unreliably broadcast a first BUNDLE(m, sn, i, {sig i }) imp-message (where sig i is the signature of (m, sn, i) by p i ) at line 2. This initial imp-message is received by at least (c -d -1) other correct processes, due to our assumption on the message adversary. This counts for a first communication step.

d⌊ n+t 2 ⌋ c-d-⌊ n+t
In the second communication step, each process p j of these (c -d -1) correct processes unreliably broadcasts its own BUNDLE(m, sn, i, {sig j , sig i }) imp-message (where sig j is the signature of (m, sn, i) by p j ) at line 7. At the end of the second communication step, in total, at least (c -d) distinct Lemma 10 (MBRB-Message-cost). The mbrb-broadcast of an app-message by a correct process p i entails the sending of at most µ = 2n 2 imp-messages by correct processes.

Proof. The broadcast of an imp-message by a correct process at line 2 entails its forwarding by at most n -1 other correct processes at line 7. As each broadcast by correct process corresponds to the sending of n imp-messages, then at most n 2 imp-messages are sent in a first step.

In a second step, at least one correct process reaches a quorum of signatures and passes the condition at line 9, and then broadcasts this quorum of signatures at line 10. Upon receiving this quorum, every correct process also passes the condition at line 9 (if it has not done it already) and broadcasts the impmessage containing the quorum at line 10. Hence, at most n 2 imp-messages are also sent in this second step, which amounts to a maximum of µ = 2n 2 imp-messages sent in total.

An additional property The reader can check from the previous proofs that the algorithm satisfies the following MBRB-delivery property. If there is a set K of k correct processes, 1 ≤ k ≤ d, such that there is a finite time τ after which the message adversary never eliminates the imp-messages sent to them, then, after τ , each process of K mbrb-delivers all the app-messages mbrb-broadcast by correct processes.

A Tightness Bound

Definition An algorithm implementing a broadcast communication abstraction is event-driven if, as far as the correct processes are concerned, only (i) the invocation of the broadcast operation that is provided to the application by the broadcast communication abstraction, or (ii) the reception of an impmessage-sent by a correct or a Byzantine process-can generate the sending of imp-messages (using the underlying unreliable network-level broadcast operation).

Theorem 2 (MBRB-Necessary-condition). When n ≤ 3t + 2d, there is no event-driven (signaturefree or signature-based) algorithm implementing the MBRB communication abstraction on top of an n-process asynchronous system in which up to t processes may be Byzantine and where a message adversary may suppress up to d copies of each imp-message broadcast by a correct process. 10Proof. Without loss of generality the proof considers the case n = 3t + 2d. Let us partition the n processes into five sets Q 11 So, when considering the sets Q 1 , Q 2 , and Q 3 , there are executions in which all the processes of either Q 1 or Q 2 or Q 3 can be Byzantine, while the processes of the two other sets are not.

1 , Q 2 , Q 3 , D 1 , and D 2 , such that |D 1 | = |D 2 | = d and |Q 1 | = |Q 2 | = |Q 3 | = t.
The proof is by contradiction. So, assuming that there is an event-driven algorithm A that builds the MBRB-broadcast abstraction for n = 3t + 2d, let us consider an execution E of A in which the processes of Q 1 , Q 2 , D 1 , and Q 2 are not Byzantine while all the processes of Q 3 are Byzantine.

Let us observe that the message adversary can isolate up to d processes by preventing them from receiving any imp-messages. Without loss of generality, let us assume that the adversary isolates a set of d correct processes not containing the sender of the app-message. As A is event-driven, these d isolated processes do not send imp-messages during the execution E of A. As a result, no correct process can expect imp-messages from more than (n -t -d) different processes without risking being blocked forever. Thanks to the mbrb-Assumption n = 3t + 2d, this translates as "no correct process can expect imp-messages from more than (2t + d) different processes without risking being blocked forever".

In the execution E, the (Byzantine) processes of Q 3 simulate the mbrb-broadcast of an app-message such that this app-message appears as being mbrb-broadcast by one of them and is mbrb-delivered as the app-message m to the processes of Q 1 (hence the processes of Q 3 appear, to the processes of Q 1 , as if they were correct) and as the app-message m ′ = m to the processes of Q 2 (hence, similarly to the previous case, the processes of Q 3 appear to the processes of Q 2 as if they were correct). Let us call m-messages (resp., m ′ -messages) the imp-messages generated by the event-driven algorithm A that entails the mbrb-delivery of m (resp., m ′ ). Moreover, the execution E is such that:

• concerning the m-messages: the message adversary suppresses all the m-messages sent to the processes of D 2 , and asynchrony delays the reception of all the m-messages sent to Q 2 until some time τ defined below. 12 So, as |Q 1 ∪ D 1 ∪ Q 3 | = n -t -d = 2t + d, Algorithm A will cause the processes of Q 1 and D 1 to mbrb-deliver m. 13• concerning the m ′ -messages: the message adversary suppresses all the m ′ -messages sent to the processes of D 1 , and the asynchrony delays the reception of all the m ′ -messages sent to Q 1 until time τ . As previously, as |Q 2 ∪ D 2 ∪ Q 3 | = n -t -d = 2t + d, Algorithm A will cause the processes of Q 2 and D 2 to mbrb-deliver m ′ .

• Finally, the time τ occurs after the mbrb-delivery of m by the processes of D 1 and Q 1 , and after the mbrb-delivery of m ′ by the processes of D 2 and Q 2 .

It follows that different non-Byzantine processes mbrb-deliver different app-messages for the same mbrb-broadcast (or a fraudulent simulation of it) issued by a Byzantine process (with possibly the help of other Byzantine processes). This contradicts the MBRB-No-Duplicity property, which concludes the proof of the theorem.

Theorem 3 (Algorithm optimality). Considering an asynchronous n-process system in which up to t processes can be Byzantine and where a d-message adversary can suppress imp-messages, Algorithm 1 is optimal with respect to the pair of values t, d . Proof. Theorem 2 has shown that the condition n > 3t + 2d is necessary, while Algorithm 1 has shown that this condition is sufficient (Theorem 1).

Conclusion

This article has presented a new communication abstraction (denoted MBRB) that extends Byzantine reliable broadcast (as defined by Bracha and Toueg [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF]) to systems where, at the underlying implementation level, an adversary may suppress some subset of implementation messages used by the processes to co-operate. From a practical point of view, this kind of message loss captures phenomena such as silent churn, input-disconnection, etc. A signature-based algorithm implementing the corresponding Byzantine-tolerant reliable broadcast in the presence of a message adversary has been presented and proven correct. This algorithm assumes n > 3t + 2d (where n is the number of processes, t is the maximum number of Byzantine processes, and d is an upper bound on the power of the message adversary), which has been shown to be a necessary and sufficient condition. message adversary), When there is no message adversary, this algorithm is optimal from both Byzantine resilience and the number of communication steps. These properties are also satisfied in other circumstances including a message adversary whose power d is restricted to some well-defined threshold.

Figure 1 :

 1 Figure 1: Distribution of signatures among processes of A and B two communication steps after p i mbrb-broadcast (m, sn)

2 ⌋Lemma 8 .

 28 , mbrb-deliver (m, sn, i) at line 11 at most two communication steps after p i mbrb-broadcast (m, sn). If a correct process p i mbrb-broadcasts (m, sn) and d < c -c × n+t 2 , then at least c -d correct processes mbrb-deliver (m, sn, i) at most three communication steps later.

  3

Table 1 :

 1 Acronyms and notations

The term delivery refers here to the application layer where a process receives and processes the content of an application message (see Section

2.1).

A very preliminary version of this work appeared in[START_REF] Albouy | Byzantine-tolerant reliable broadcast in the presence of silent churn[END_REF].

The signature-free BRB algorithm described in[START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] is optimal with respect to Byzantine resilience (t < n/3), but requires three communication steps, while the signature-free BRB algorithm described in[START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF] is optimal with respect to the number of communication steps (2) but is not with respect to Byzantine resilience (it requires t < n/5).

A close but different notion was introduced by Dolev in[START_REF] Dolev | The Byzantine generals strike again[END_REF] (and explored in subsequent works, such as[START_REF] Bonomi | Practical Byzantine Reliable Broadcast on Partially Connected Networks[END_REF]) which considers static k-connected networks. If the adversary selects statically for each correct sender d correct processes that do not receive this sender's imp-messages, the proposed model includes Dolev's model with k = n -d.

So the notion of a message adversary implicitly includes the notion of imp-message omission failures.

The fact that the algorithm uses signed imp-messages does not mean that MBRB-broadcast requires signatures to be implemented, see[START_REF] Albouy | kℓ-cast: on the foundations of Byzantine reliable broadcast in the presence of message adversaries[END_REF].

If there is no message adversary (i.e., d = 0), we should have ℓ = c ≥ n -t.

Signature-based BRB in only two communication steps is a known result[START_REF] Abraham | Good-case latency of Byzantine broadcast: a complete categorization[END_REF], however, to the best of our knowledge, no existing BRB algorithm tolerates message adversaries as well as ours.

The pseudo-code presented in Algorithm 1 favors readability, and is therefore not fully optimized. For instance, in some cases, a process might unreliably broadcast exactly the same content at lines 7 and

This could be avoided by either using an appropriate flag, or by tracking and preventing the repeated broadcast of identical BUNDLE imp-messages.

Let us recall that the underlying communication operation offered by the system is an unreliable broadcast defined in Section 2.1.

For the case n < 3t + 2d, the partition is such that min(|Q1|, |D2|) ≤ d and min(|Q1|, |Q2|, |Q3|) ≤ t.

Equivalently, we could also say that asynchrony delays the reception of all the m-messages sent to D2 ∪ Q2 until time τ . The important point is here that, due to the assumed existence of Algorithm A, the processes of Q1 and and D1 mbrb-deliver m with m-messages from at most 2t + d different processes.

Let us notice that this is independent from the fact that the processes in Q3 are Byzantine or not.

Acknowledgments

This work was partially supported by the French ANR projects ByBloS (ANR-20-CE25-0002-01) and PriCLeSS (ANR-10-LABX-07-81) devoted to the modular design of building blocks for large-scale Byzantine-tolerant multi-users applications. The authors want to thank Colette Johnen, Elad Schiller, and Stefan Schmid for their kind invitation to participate in the SSS 2021 conference.

signatures for (m, sn, i) have been created and unreliably broadcast by correct processes (counting that of p i ), resulting in at least (c -d) 2 receptions of said signatures by correct processes. As there are c correct processes, this means that, on average, each correct process has received at least (c-d) 2 c signatures by the end of the second communication step, and that at least one correct process, p k , receives (and saves at line 4) at least this number of signatures.

From the Lemma hypothesis d < c -c × n+t 2 and using simple algebraic transformations, we can derive (c-d) 2 c > n+t 2 . Therefore, p k reaches a quorum of signatures, that is, it passes the condition at line 9 and unreliably broadcast this quorum of signatures at line 10, two communication steps after the mbrb-broadcast of (m, sn) by p i . By definition of the message adversary, this quorum of signatures is received by c-d correct processes, which save it at line 4 and thus pass the condition at line 9 and finally mbrb-deliver (m, sn, i) at line 11, three communication steps after the mbrb-broadcast of (m, sn) by p i .

Lemma 9 (MBRB-Time-cost). If a correct process p i mbrb-broadcasts an app-message m with sequence number sn, then ℓ = c -d correct processes mbrb-deliver m from p i with sequence number sn at most

Proof. Let us consider a correct process p i that mbrb-broadcasts (m, sn). By exhaustion:

• Case where d <

2 ⌋ correct processes mbrb-deliver (m, sn, i) two communication steps after p i has mbrb-broadcast (m, sn). We have:

, (case assumption)

Hence, ℓ correct processes mbrb-deliver (m, sn, i) at most two communication steps after p i has mbrb-broadcast (m, sn).

• Case where d < c -c × n+t 2 . Lemma 8 applies and at least c -d = ℓ correct processes mbrb-deliver (m, sn, i) at most three communication steps after p i has mbrb-broadcast (m, sn).