Timothé Albouy

Davide Frey

Michel Raynal

François Taïani

A Modular Approach to Construct Signature-Free BRB Algorithms under a Message Adversary

Keywords: Asynchronous system, Byzantine processes, Communication abstraction, Delivery predicate, Fault-Tolerance, Forwarding predicate, Message adversary, Message loss, Modularity, Quorum, Reliable broadcast, Signature-free algorithm, Two-phase commit

This paper explores how reliable broadcast can be implemented without signatures when facing a dual adversary that can both corrupt processes and remove messages. More precisely, we consider an asynchronous n-process message-passing system in which up to t processes are Byzantine and where, at the network level, for each message broadcast by a correct process, an adversary can prevent up to d processes from receiving it (the integer d defines the power of the message adversary). So, unlike previous works, this work considers that not only can computing entities be faulty (Byzantine processes), but, in addition, that the network can also lose messages. To this end, the paper adopts a modular strategy and first introduces a new basic communication abstraction denoted k2 -cast, which simplifies quorum engineering, and studies its properties in this new adversarial context. Then, the paper deconstructs existing signature-free Byzantine-tolerant asynchronous broadcast algorithms and, with the help of the k2 -cast communication abstraction, reconstructs versions of them that tolerate both Byzantine processes and message adversaries. Interestingly, these reconstructed algorithms are also more efficient than the Byzantine-tolerant-only algorithms from which they originate.

Introduction

Context: reliable broadcast and message adversaries. Reliable broadcast (RB) is a fundamental abstraction in distributed computing that lies at the core of many higher-level constructions (including distributed memories, distributed agreement, and state machine replication). Essentially, RB requires that non-faulty (i.e., correct) processes agree on the set of messages they deliver so that this set includes at least all the messages that correct processes have broadcast.

In a failure-free system, implementing reliable broadcast on top of an asynchronous network is relatively straightforward [START_REF]Distributed algorithms for message-passing systems[END_REF]. If processes may fail, and in particular if failed processes may behave arbitrarily (a failure known as Byzantine [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF]), implementing reliable broadcast becomes far from trivial as Byzantine processes may collude to fool correct processes [START_REF]Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF]. An algorithm that solves reliable broadcast in the presence of Byzantine processes is known as implementing BRB (Byzantine reliable broadcast).

BRB in asynchronous networks (in which no bound is known over message delays) has been extensively studied over the last forty years [START_REF] Abraham | Good-case latency of Byzantine broadcast: a complete categorization[END_REF][START_REF] Abraham | Good-case and bad-case latency of unauthenticated Byzantine broadcast: A complete categorization[END_REF][START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Cachin | Reliable and secure distributed programming[END_REF][START_REF] Guerraoui | Dynamic Byzantine reliable broadcast[END_REF][START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF][START_REF] Maurer | Communicating reliably in multi-hop dynamic networks despite Byzantine failures[END_REF][START_REF] Malkhi | Byzantine quorum systems[END_REF][START_REF] Nayak | Improved extension protocols for Byzantine broadcast and agreement[END_REF][START_REF]Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF]. Existing BRB algorithms typically assume they execute over a reliable point-to-point network, i.e., a network in which sent messages are eventually received. This is a reasonable assumption as most unreliable networks can be made reliable using re-transmissions and acknowledgments (e.g. a timeout-free version of the TCP protocol). This work takes a drastic turn away from this usual assumption and explores how BRB might be provided when processes execute on an unreliable network that might lose point-to-point messages. Our motivation is threefold: First, in volatile networks (e.g., mobile networks or networks under attack), processes might remain disconnected over long periods (e.g., weeks or months), leading in practice to considerable delays (a.k.a. tail latencies) when using re-transmissions. Because most asynchronous Byzantine-tolerant algorithms exploit intersecting quorums, these tail latencies can potentially limit the performance of BRB algorithms drastically, a well-known phenomenon in systems research [START_REF] Chen | Achieving low tail-latency and high scalability for serializable transactions in edge computing[END_REF][START_REF] Didona | Size-aware sharding for improving tail latencies in in-memory keyvalue stores[END_REF][START_REF] Yang | DispersedLedger: high-throughput Byzantine consensus on variable bandwidth networks[END_REF]. Second, re-transmissions require that correct processes be eventually able to receive messages and cannot, therefore, model the permanent disconnection of correct processes. Finally, this question is interesting in its own right, as it opens up novel trade-offs between algorithm guarantees and network requirements, with potential application to the design of reactive distributed algorithms tolerant to both processes and network failures.

The impact of network faults on distributed algorithms has been studied in several works, in particular using the concept of message adversaries (MA). Message adversaries were initially introduced by N. Santoro and P. Widmayer in [START_REF] Santoro | Time is not a healer[END_REF][START_REF] Santoro | Agreement in synchronous networks with ubiquitous faults[END_REF] 1 , and then used (sometimes implicitly) in many works (e.g., [START_REF] Albouy | Asynchronous Byzantine reliable broadcast with a message adversary[END_REF][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] Dwork | Fault tolerance in networks of bounded degree[END_REF][START_REF] Raynal | Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors[END_REF][START_REF]Message adversaries[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]). Initially proposed for synchronous networks, an MA may suppress point-to-point network messages according to rules that define its power. For instance, a tree MA in a synchronous network might suppress any message except those transiting on an (unknown) spanning tree of the network, with this spanning tree possibly changing in each round.

The message losses that an MA causes differ fundamentally from Byzantine faults. This is because an MA can affect the messages sent by any correct process, and can change the processes it targets during an execution, in contrast to Byzantine corruptions that are tied to a set of fixed processes (which is why MA faults are sometimes dubbed transient or mobile). For instance, it may be tempting to think that Byzantine-fault-tolerant (BFT) algorithms inherently tolerate message losses from correct processes because they can only afford to wait for at most n-t messages (where n is the total number of processes, and t the upper bound on Byzantine processes). In an asynchronous network, a BFT algorithm could therefore miss up to t messages from correct processes, if those are delayed by the scheduler. This scenario only applies, however, in the particular circumstance where the t faulty processes send messages that are received and accepted as valid by correct recipients. This caveat is fundamental. If the faulty processes remain silent or send contradicting messages (if they are Byzantine), then a BFT algorithm cannot afford to lose t messages from correct processes.

Content of the paper. This paper combines a Message Adversary with Byzantine processes, and studies the signature-free implementation of Byzantine Reliable Broadcast (BRB) in an asynchronous, fully connected network subject to this MA and to at most t Byzantine faults. The MA models lossy connections by preventing up to d point-to-point messages from reaching their recipient every time a correct process seeks to communicate with the rest of the network. 2 To limit as much as possible our working assumptions, we further assume that the computability power of the adversary is unbounded (except for the cryptography-based algorithm presented in Section 6), which precludes the use of signatures. (We do assume, however, that each point-to-point communication channel is authenticated.) 3 1 Where the terminology communication failure model and ubiquitous faults is used instead of MA. While we consider only message losses, the work of Santoro and Widmayer also considers message additions and corruptions. 2 A close but different notion was introduced by Dolev in [START_REF] Dolev | The Byzantine generals strike again[END_REF], which considers static κ-connected networks. If the adversary selects statically, for each correct sender, d correct processes that do not receive any of this sender's messages, the proposed model includes Dolev's model where κ = n -d. 3 Let us mention that the problem of designing an MA-tolerant BRB has been solved in [START_REF] Albouy | Asynchronous Byzantine reliable broadcast with a message adversary[END_REF] by leveraging digital signatures within a monolithic algorithm. Finding a signature-free counterpart remained, however, an open question, which we answer positively in this paper using a modular strategy. This represents a particularly challenging environment, as the MA may target different correct processes every time the network is used or focus indefinitely on the same (correct) victims. Further, the Byzantine processes may collude with the MA for maximal impact.

For clarity, in the remainder of the paper, we simply call messages the point-to-point network messages used internally by a BRB algorithm. (The MA may suppress these messages.) We distinguish these messages from the messages the BRB algorithm seeks to disseminate, which we call "application messages" (app-messages for short). In such a context, the paper presents the following results.

• It first introduces a new modular abstraction, named k2 -cast, which appears to be a foundational building block to implement BRB abstractions (with or without the presence of an MA). This communication abstraction systematically dissociates the predicate used to forward (network) messages from the predicate that triggers the delivery of an app-message, and lies at the heart of the work presented in the paper. When proving the k2 -cast communication abstraction, the paper presents an in-depth analysis of the power of an adversary that controls at most t Byzantine processes and an MA of power d.

• Then, the paper deconstructs two signature-free BRB algorithms (Bracha's [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] and Imbs and Raynal's [START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF] algorithms) and reconstructs versions of them that tolerate both Byzantine processes and MA. Interestingly, when considering Byzantine failures only, these deconstructed versions use smaller quorum sizes and are, therefore, more efficient than their initial counterparts.

So, this paper is not only the first to present signature-free BRB algorithms in the context of asynchrony and MA but also the first to propose an intermediary communication abstraction that allows us to obtain efficient BRB algorithms. For clarity, we give in Roadmap. The paper is composed of 7 sections and four appendices. Section 2 describes the underlying computing model. Section 3 presents the k2 -cast abstraction and its properties. Section 4 defines the MA-tolerant BRB communication abstraction. Section 5 shows that thanks to the k2 -cast abstraction, existing BRB algorithms can give rise to MA-tolerant BRB algorithms which, when d = 0, are more efficient than the BRB algorithms they originate from. Section 6 presents a signature-based implementation of k2 -cast that possesses optimal guarantees. Finally, Section 7 concludes the paper. Due to page limitations, some contributions are presented in appendices: namely some proofs and a numerical evaluation of the k2 -cast abstraction.

Computing Model

Process model. The system is composed of n asynchronous sequential processes denoted p 1 , ..., p n . Each process p i has a distinct identity, known to other processes. For simplicity and without loss of generality, we assume that i is the identity of p i . In terms of faults, up to t ≥ 0 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]. Byzantine processes may collude to fool non-Byzantine processes (also called correct processes). In this model, the premature stop (crash) of a process is a Byzantine failure. In the following, given an execution, c denotes the effective number of processes that behave correctly in that execution. We always have n -t ≤ c ≤ n. While this number remains unknown to correct processes, it is used to analyze and characterize (more precisely than using its worse value n -t) the guarantees provided by the proposed algorithms.

Finally, the processes have no access to random numbers, and their computability power is unbounded. Hence, the algorithms presented in the paper are deterministic and signature-free (except the signature-based algorithm presented in Section 6).

Communication model. Processes communicate by exchanging messages through a fully connected asynchronous point-to-point network, assumed to be reliable in the sense it neither corrupts, duplicates, nor creates messages. As far as messages losses are concerned, the network is under the control of an adversary (see below) that can suppress messages.

Let MSG be a message type and v the associated value. A process can invoke the best-effort broadcast macro-operation denoted ur_broadcast(MSG(v)), which is a shorthand for "for all j ∈ {1, • • • , n} do send MSG(v) to p j end for". Correct processes are assumed to invoke ur_broadcast to send messages. When they do, we say that the messages are ur-broadcast and received. The operation ur_broadcast(MSG(v)) is not reliable. For example, if the invoking process crashes during its invocation, an arbitrary subset of processes receive the message MSG(v). Moreover, due to its very nature, a Byzantine process can send fake messages without using the macro-operation ur_broadcast.

Message adversary. Let d be an integer constant such that 0 ≤ d < n -t. The communication network is controlled by an MA (as defined in Section 1), which eliminates messages ur-broadcast by correct processes, so these messages are lost. More precisely, when a correct process invokes ur_broadcast(MSG(v)), the MA is allowed to arbitrarily suppress up to d copies of the message MSG(v) intended to correct processes 4 . This means that, although the sender is correct, up to d correct processes may miss the message MSG(v). The extreme case d = 0 corresponds to the case where no message is lost.

As an example, let us consider a set D of correct processes, where 1 ≤ |D| ≤ d, such that during some period of time, the MA suppresses all the messages sent to them. It follows that, during this period of time, this set of processes appears as being input-disconnected from the other correct processes. Note that the size and the content of D can vary with time and are never known by the correct processes.

k2 -Cast Abstraction

Signature-free BRB algorithms [START_REF] Auvolat | Byzantine-tolerant set-constrained delivery broadcast[END_REF][START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF] often rely on successive waves of internal messages (e.g. the ECHO or READY messages of Bracha's algorithm [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]) to provide safety and liveness. Each wave is characterized by a threshold-based predicate that triggers the algorithm's next phase when fulfilled (e.g. enough ECHO messages for the same app-message m).

In this section, we introduce, implement, and prove a new modular abstraction, called k2 -cast, that encapsulates a wave/thresholding mechanism that is both Byzantine-and MA-tolerant. As previously announced, we then use this abstraction to reconstruct MA-tolerant BRB algorithms in Section 5 from two existing BRB algorithms [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF].

Definition

k2 -cast (for k-to--cast) is a many-to-many communication abstraction 5 . Intuitively, it relates the number k of correct processes that send a message m (we say that these processes k2 -cast m) with the number of correct processes that deliver m (we say that they k2 -deliver m). Both k and are subject to thresholding constraints: enough correct processes must k2 -cast a message for it to be k2 -delivered at least once; and as soon as one (correct) k2 -delivery occurs, some minimal number of correct processes are guaranteed to k2 -deliver as well.

More formally, k2 -cast is a multi-shot abstraction, i.e. each app-message m that is k2 -cast or k2delivered is associated with an identity id . (Typically, such an identity is a pair consisting of a process identity and a sequence number.) It provides two operations, k2 _cast and k2 _deliver, whose behavior is defined by the values of four parameters: three integers k , k, , and a Boolean δ. This behavior is captured by the following six properties:

• Safety:

-k2 -VALIDITY. If a correct process p i k2 -delivers an app-message m with identity id , then at least k correct processes k2 -cast m with identity id .

-k2 -NO-DUPLICATION. A correct process k2 -delivers at most one app-message m with identity id .

-k2 -CONDITIONAL-NO-DUPLICITY. If the Boolean δ is true, then no two different correct processes k2 -deliver different app-messages with the same identity id .

• Liveness6 :

-k2 -LOCAL-DELIVERY. If at least k correct processes k2 -cast an app-message m with identity id and no correct process k2 -casts an app-message m = m with identity id , then at least one correct process k2 -delivers the app-message m with identity id .

-k2 -WEAK-GLOBAL-DELIVERY. If a correct process k2 -delivers an app-message m with identity id , then at least correct processes k2 -deliver an app-message m with identity id (each of them possibly different from m).

-k2 -STRONG-GLOBAL-DELIVERY. If a correct process k2 -delivers an app-message m with identity id , and no correct process k2 -casts an app-message m = m with identity id , then at least correct processes k2 -deliver the app-message m with identity id .

This specification is parameterized in the sense that each tuple (k , k, , δ) defines a specific communication abstraction with different guarantees. This versatility explains why the k2 -cast abstraction can be used to produce highly compact reconstructions of existing BRB algorithms, rendering them MAtolerant in the process (using four and three lines of pseudo-code respectively, see Section 5). Despite this versatility, however, we will see in Section 3.2 that k2 -cast can be implemented using a single (parameterized) algorithm, underscoring the fundamental commonalities of MA-tolerant BRB algorithms.

Intuitively, the parameters k , k, and hobble the disruption power of the Byzantine/MA adversary by setting limits on the number of correct processes that are either required or guaranteed to be involved in one communication "wave" (corresponding to one identity id ). k sets the minimal number of correct processes that must k2 -cast for any k2 -delivery to occur: it thus limits the ability of the Byzantine/MA adversary to trigger spurious k2 -deliveries. The role of k is symmetrical. It guarantees that some k2 -delivery will necessarily occur if k correct processes k2 -cast some message. It thus prevents the adversary from silencing correct processes as soon as some critical mass of them participates. Finally, captures a "quite-a-few-or-nothing" guarantee that mirrors the traditional "all-or-nothing" delivery guarantee of traditional BRB. As soon as one correct k2 -delivery occurs (for some identity id ), then correct processes must also k2 -deliver (with the same identity).

The fourth parameter, δ, is a flag that when true enforces agreement between k2 -deliveries. When δ = true, the k2 -CONDITIONAL-NO-DUPLICITY property implies that all the app-messages m involved in the k2 -WEAK-GLOBAL-DELIVERY property are equal to m.

A Signature-Free Implementation of k2 -Cast

Among the many possible ways of implementing k2 -cast, this section presents a quorum-based 7 signaturefree implementation 8 of the abstraction. To overcome the disruption caused by Byzantine processes and message losses from the MA, our algorithm uses the ur-broadcast primitive (cf. our communication model in Sec. 2) to accumulate and forward ENDORSE messages before deciding whether to deliver. Forwarding and delivery are triggered by two thresholds (a pattern also found, for instance, in Bracha's BRB algorithm [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]):

• A first threshold, q d , triggers the delivery of an app-message m when enough ENDORSE messages supporting m have been received.

• A second threshold, q f , which is lower than q d , controls how ENDORSE messages are forwarded during the algorithm's execution.

Forwarding, which is controlled by q f , amplifies how correct processes react to ENDORSE messages, and is instrumental to ensure the algorithm's liveness. As soon as some critical "mass" of agreeing EN-DORSE messages accumulates within the system, forwarding triggers a chain reaction which guarantees that a minimum number of correct processes eventually k2 -deliver the corresponding app-message.

More concretely, our algorithm provides an object (SigFreeK2LCast, Alg. 1), instantiated using the function SigFreeK2LCast(q d , q f , single), using three input parameters:

• q d : the number of matching ENDORSE messages that must be received from distinct processes in order to k2 -deliver an app-message. 7 In this paper, a quorum is a set of processes that (at the implementation level) ur-broadcast the same message. This definition takes quorums in their ordinary sense. In a deliberative assembly, a quorum is the minimum number of members that must vote the same way for an irrevocable decision to be taken. Let us notice that this definition does not require quorum intersection. However, if quorums have a size greater than n+t 2 , the intersection of any two quorums contains, despite Byzantine processes, at least one correct process [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF]Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF]. 8 Another k2 -cast implementation, which uses digital signatures and allows to reach optimal values for k and , is presented in Section 6.

object SigFreeK2LCast(q d , q f , single) is

(1) operation k2 _cast(m, id ) is (2)
if ENDORSE(-, id ) not already ur-broadcast [START_REF] Afek | Asynchrony from synchrony[END_REF] then ur_broadcast(ENDORSE(m, id )) (4) end if.

(5) when ENDORSE(m, id ) is received do % forwarding step [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] if ENDORSE(m, id ) received from at least q f processes ∧ ¬single ∧ ENDORSE(m, id ) not already ur-broadcast ∨ ENDORSE(-, id ) not already ur-broadcast [START_REF] Auvolat | Money transfer made simple: a specification, a generic algorithm, and its proof[END_REF] then ur_broadcast(ENDORSE(m, id )) [START_REF] Auvolat | Byzantine-tolerant set-constrained delivery broadcast[END_REF] end if; % delivery step [START_REF] Baudet | Fastpay: high-performance Byzantine fault tolerant settlement[END_REF] if ENDORSE(m, id ) received from at least q d processes ∧ (-, id ) not already k2 -delivered [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] then k2 _deliver(m, id ) [START_REF] Cachin | Reliable and secure distributed programming[END_REF] end if.

end object.

Algorithm 1: Signature-free k2 -cast (code for p i )

Underlying system n, t, d, c • q f : the number of matching ENDORSE messages that must be received from distinct processes for the local p i to endorse the corresponding app-message (if it has not yet).

sf-k2 -Assumptions 1-4 Implementation q d , q f , single Theorem 1 k2 -cast object k , k, , δ
• single: a Boolean that controls whether a given correct process can endorse different appmessages for the same identity id (single = false), or not (single = true).

The algorithm provides the operations k2 _cast and k2 _deliver. Given an app-message m with identity id , the operation k2 _cast(m, id ) ur-broadcasts ENDORSE(m, id ) provided p i has not yet endorsed any different app-message for the same identity id (lines 2-4). When p i receives a message ENDORSE(m, id ), its executes two steps. If the forwarding quorum q f has been reached, p i first retransmits ENDORSE(m, id ) (Forwarding step, lines 6-8). Then, if the k2 -delivery quorum q d is attained, p i k2 -delivers m (Delivery step, lines [START_REF] Baudet | Fastpay: high-performance Byzantine fault tolerant settlement[END_REF][START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Cachin | Reliable and secure distributed programming[END_REF].

For brevity, we define α = n + q f -t -d -1. Given an execution defined by the system parameters n, t, d, and c, Alg. 1 requires the following assumptions to hold for the input parameters q f and q d of a k2 -cast instance (a global picture linking all parameters is presented in Fig. 1). The prefix "sf" stands for signature-free.

• sf-k2 -Assumption 1: c -d ≥ q d ≥ q f + t ≥ 2t + 1, • sf-k2 -Assumption 2: α 2 -4(q f -1)(n -t) ≥ 0, • sf-k2 -Assumption 3: α(q d -1) -(q f -1)(n -t) -(q d -1) 2 > 0, • sf-k2 -Assumption 4: α(q d -1 -t) -(q f -1)(n -t) -(q d -1 -t) 2 ≥ 0.
In particular, the safety of Alg. 1 algorithm relies solely on sf-k2 -Assumption 1, while its liveness relies on all four of them. sf-k2 -Assumption 2 through 4 constrain the solutions of a second-degree inequality resulting from the combined action of the MA, the Byzantine processes, and the messageforwarding behavior of Alg. 1. We show in Appendix B that, in practical cases, these assumptions can be satisfied by a bound of the form n > λt + ξd + f (t, d), where λ, ξ ∈ N and f (t, 0) = f (0, d) = 0. Together, the assumptions allow Alg. 1 to provide a k2 -cast abstraction (with values of the parameters k , k, , and δ defining a specific k2 -cast instance) as stated by the following theorem.

Theorem 1 (k2 -CORRECTNESS). If sf-k2 -Assumptions 1-4 are verified, Alg. 1 implements k2 -cast with the following guarantees:

• k2 -VALIDITY with k = q f -n + c, • k2 -NO-DUPLICATION, • k2 -CONDITIONAL-NO-DUPLICITY with δ = q f > n + t 2 ∨ single ∧ q d > n + t 2 , • k2 -LOCAL-DELIVERY with k = c(q f -1) c-d-q d +q f + 1, • if single = false, k2 -WEAK-GLOBAL-DELIVERY if single = true, k2 -STRONG-GLOBAL-DELIVERY with = c 1 -d c-q d +1
.

Proof of Algorithm 1

The proofs of the k2 -cast safety properties stated in Theorem 1 (k2 -VALIDITY, k2 -NO-DUPLICATION, and k2 -CONDITIONAL-NO-DUPLICITY) are fairly straightforward. To save space, these proofs (Lemmas 10-13) are provided in Appendix A.1.

The proofs of the k2 -cast liveness properties (k2 -LOCAL-DELIVERY, k2 -WEAK-GLOBAL-DELIVERY, k2 -STRONG-GLOBAL-DELIVERY) are sketched informally below (Lemmas 1-9). Their full development can be found in Appendix A.2.

When seeking to violate the liveness properties of k2 -cast, the attacker can use the MA to control in part how many ENDORSE messages are received by each correct process, thus interfering with the quorum mechanisms defined by q d and q f . To analyze the joint effect of this interference with Byzantine faults, our proofs consider seven well-chosen subsets of correct processes (A, B, C, U , F , NF , and NB , depicted in Fig. 2a).

These subsets are defined for an execution of Alg. 1 in which k I correct processes k2 -cast (m, id ) (the I in k I is for "Initial"), and e correct processes receive at least q d message ENDORSE(m, id ). The first three subsets, A, B, and C, partition correct processes based on the number of ENDORSE(m, id ) messages they receive.

• A contains the e correct processes that receive at least q d ENDORSE(m, id ) messages (be it from correct or from Byzantine processes), and thus k2 -deliver some message.9

• B contains the correct processes that receive at least q f but less than q d ENDORSE(m, id ) messages and thus do not k2 -deliver (m, id ).

• C contains the remaining correct processes that receive less than q f ENDORSE(m, id ) messages. They neither forward nor deliver any message for identity id (since q f ≤ q d ).

In our proofs, we count how many messages ENDORSE(m, id ) ur-broadcast by correct processes are received by the processes of A (resp. B and C). We note these quantities w c A , w c B , and w c C , and use them to bootstrap our proofs using bounds on messages (see below).

The last four subsets intersect with A, B and C, and distinguish correct processes based on the ur-broadcast operations they perform.

• U consists of the correct processes that ur-broadcast ENDORSE(m, id ) at line 3. • F denotes the correct processes of A ∪ B that ur-broadcast ENDORSE(m, id ) at line 7 (i.e., they perform forwarding).

# correct processes

k U +k F e A w c A q d -1 k F +k NF +k NB B w c B q f -1 c C w c C (b)
• NF denotes the correct processes of A ∪ B that ur-broadcast ENDORSE(m, id ) at line 3.

• NB denotes the correct processes of A ∪ B that never ur-broadcast ENDORSE(m, id ), be it at line 3 or at line 7. These processes have received at least q f messages ENDORSE(m, id ), but do not forward ENDORSE(m, id ), because they have already ur-broadcast ENDORSE(m , id ) at line 3 or at line 7 for an app-message m = m.

Proof strategy. We note

k U = |U |, k F = |F |, k NF = |NF |, k NB = |NB |. Observe that k U ≤ k I and k NF ≤ k U , since all (correct) processes in U and NF invoke k2 _cast. Also, (k U + k F )
represents the total number of correct processes that ur-broadcast a message ENDORSE(m, id ). Fig. 2b illustrates how these quantities constrain the distribution of ENDORSE messages across A, B and C.

Our core proof strategy consists in bounding the areas shown in Fig. 2b. (For instance, observe that

w c A ≤ |A| × (k U + k F )
, since each of the e correct processes in A can receive at most one ENDORSE message from each of the (k U + k F ) correct processes that send them.) This reasoning on bounds yields a polynomial involving e = |A|, k I , and k U , whose roots can then be constrained to yield the liveness guarantees required by the k2 -cast specification.

Observation. In the same way we have bounded w c A , we can also bound w c B by observing that there are (k NF + k NB + k Fe ) processes in B and that each can receive at most q d -1 ENDORSE messages. Similarly, we can bound w c C by observing that the (c -k NF -k NB -k F ) processes of C can receive at most q f -1 ENDORSE messages. Thus:

w c A ≤ (k U + k F ) e , (1)
w c B ≤ (q d -1)(k NF + k NB + k F -e ), (2)
w c C ≤ (q f -1)(c -k NF -k NB -k F ). (3)
Moreover, the MA cannot suppress more than d copies of each individual ENDORSE message urbroadcast to the c correct processes. Thus, the total number of ENDORSE messages received by correct processes

(w c A + w c B + w c C ) is such that: w c A + w c B + w c C ≥ (k U + k F )(c -d). ( 4
) Lemma 1. e × (k U + k F -q d + 1) ≥ (k U + k F )(c -d -q d + q f ) -c(q f -1) -k NB (q d -q f ).
Proof sketch. We get this result by combining (1), ( 2), ( 3) and ( 4), and using sf-k2 -Assumption 1 with the fact that k NF ≤ k U . (Full derivations in Appendix A.2.)

Lemma 2. If no correct process k2 -casts (m , id ) with m = m, then no correct process forwards ENDORSE(m , id ) at line 7 (and then k NB = 0). (Proof in Appendix A.2.)

Lemma 3 (k2 -LOCAL-DELIVERY). If at least k = c(q f -1)
c-d-q d +q f + 1 correct processes k2 -cast an app-message m with identity id and no correct process k2 -casts any app-message m with identity id such that m = m , then at least one correct process p i k2 -delivers m with identity id .

Proof sketch. From the hypotheses, Lemma 2 helps us determine that k NB = 0. Then, the property is proved by contraposition, by assuming that no correct process k2 -delivers (m, id ), which leads us to e = 0. Using prior information and sf-k2 -Assumption 1, we can rewrite the inequality of Lemma 1 to get the threshold of k2 -casts above which there is at least one k2 -delivery. (Full derivations in Appendix A.2.)

Lemma 4. (single = false) =⇒ (k NB = 0). (Proof in Appendix A.2.) Lemma 5. If at least one correct process k2 -delivers (m, id ) and x = k U + k F (the number of correct processes that ur-broadcast ENDORSE(m, id ) at line 3 or 7), then x ≥ q d -t and x 2 -x(c -d + q f - 1 -k NB ) ≥ -(c -k NB )(q f -1).
Proof sketch. We prove this lemma by counting the total number of messages (sent by Byzantine or correct processes) that are received by the processes of A, and by using (1), (3) (4), and sf-k2 -Assumption 1. (Full derivations in Appendix A.2.) Lemma 6. If k NB = 0, and at least one correct process k2 -delivers (m, id ), then k U + k F ≥ q d . Proof sketch. Given that k NB = 0, we can rewrite the inequality of Lemma 5, which gives us a seconddegree polynomial (where x = k U + k F is the unknown variable). We compute its roots and show that the smaller one contradicts Lemma 5, and that the larger one is greater than or equal to q d . The fact that x must be greater than or equal to the larger root to satisfy Lemma 5 proves the lemma. (Full derivations in Appendix A.2.)

Lemma 7. If k NB = 0 and k U +k F ≥ q d , then at least c 1 -d c-q d +1
correct processes k2 -deliver some app-message with identity id (not necessarily m).

Proof sketch. From the hypotheses, we can rewrite the inequality of Lemma 1 to get a lower bound on e . Using sf-k2 -Assumption 3, we can determine that this lower bound is decreasing with the number of ur-broadcasts by correct processes (x = k U + k F ). Hence, this lower bound is minimum when x is maximum, that is, when x = c. This gives us the minimum number of correct processes that k2 -deliver under the given hypotheses. (Full derivations in Appendix A.2.) Lemma 8 (k2 -WEAK-GLOBAL-DELIVERY). If single = false, and a correct process k2 -delivers an app-message m with identity id , then at least = c 1 -d c-q d +1 correct processes k2 -deliver an app-message m with identity id (each possibly different from m).

Proof sketch. As single = false and one correct process k2 -delivers (m, id ), Lemmas 4 and 6 apply, and we have k NB = 0 and k U +k F ≥ q d . This provides the prerequisites for Lemma 7, which concludes the proof. (Full derivations in Appendix A.2.) Lemma 9 (k2 -STRONG-GLOBAL-DELIVERY). If single = true, and a correct process k2 -delivers an app-message m with identity id , and no correct process k2 -casts an app-message m = m with identity id , then at least = c 1 -d c-q d +1 correct processes k2 -deliver m with identity id . Proof sketch. As single = true, Lemma 2 holds and implies that k NB = 0. As above, Lemma 6 and Lemma 7 hold, yielding the lemma. (Full derivations in Appendix A.2.)

BRB in the Presence of Message Adversary (MBRB): Definition

Before using the k2 -cast abstraction to reconstruct MA-tolerant BRB algorithms, we first specify what a Byzantine-and MA-tolerant broadcast should precisely achieve. We call such a broadcast an MBRbroadcast (for Message-adversarial Byzantine Reliable Broadcast), or MBRB for short. The MBRB abstraction provides two matching operations, mbrb_broadcast and mbrb_deliver. It is a multishot abstraction, i.e, it associates an identity sn, i (sequence number, sender identity) with each app-message, and assumes that correct processes never reuse the same sequence number for different mbrb_broadcast invocations.

When, at the application level, a process p i invokes mbrb_broadcast(m, sn), where m is the appmessage, we say it "mbrb-broadcasts (m, sn)". Similarly, when the invocation of mbrb_deliver by p i returns the tuple (m, sn, j) to the client application (where p j is the sender process), we say it "mbrbdelivers (m, sn, j)". So, the app-message are mbrb-broadcast and mbrb-delivered. Because of the MA, we cannot always guarantee that an app-message mbrb-delivered by a correct process is eventually received by all correct processes. Hence, in the MBR-broadcast specification, we introduce a variable MBRB (reminiscent of the of k2 -cast) which indicates the strength of the global delivery guarantee of the primitive: if one correct process mbrb-delivers an app-message, then MBRB correct processes eventually mbrb-deliver this app-message 10 . MBRB is defined by the following properties:

• Safety:

-MBRB-VALIDITY. 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 from a process p j with sequence number sn.

-MBRB-NO-DUPLICITY. No two distinct correct processes mbrb-deliver different appmessages 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 MBRB correct processes mbrb-deliver m from p j with sequence number sn.

init: obj E ← SigFreeK2LCast(q d = n+t 2 +1, q f =t+1, single=true); obj R ← SigFreeK2LCast(q d =2t+d+1, q f =t+1, single=true).

(1) operation mbrb_broadcast(m, sn) is ur_broadcast(INIT(m, sn)).

(2) when INIT(m, sn) is received from pj do obj E .k2 _cast(ECHO(m), (sn, j)).

(3) when (ECHO(m), (sn, j)) is obj E .k2 _delivered do obj R .k2 _cast(READY(m), (sn, i)).

(4) when (READY(m), (sn, j)) is obj R .k2 _delivered do mbrb_deliver(m, sn, j).

Algorithm 2: k2 -cast-based reconstruction of Bracha's BRB algorithm (code of p i ) It is implicitly assumed that a correct process does not use the same sequence number twice. Let us observe that, as at the implementation level, the MA can always suppress all the messages sent to a fixed set D of d processes, these mbrb-delivery properties are the strongest that can be implemented. More generally, the best-guaranteed value for MBRB is c -d. So, the previous specification boils down to Bracha's specification [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] for MBRB = c. 5 k2 -Cast in Action: From Classical BRB to MA-Tolerant BRB (MBRB) Algorithms

This section uses k2 -cast to reconstruct two signature-free BRB algorithms [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF] initially introduced in a pure Byzantine context (i.e., without any MA). This reconstruction produces Byzantine-MA-tolerant versions of the initial algorithms that implement the MBRB specification of Section 4. Moreover, when d = 0, our two reconstructed BRB algorithms are strictly more efficient than the original algorithms that gave rise to them (they terminate earlier). More precisely, the original and reconstructed versions of Bracha's BRB are identical in terms of communication cost, time complexity, and t-resilience (when d = 0). The same comparison holds for the original and reconstructed versions of Imbs and Raynal's BRB. However, both reconstructed BRB algorithms use smaller quorums than their original versions, and therefore require fewer messages to progress. In an actual network, this means a lower latency in practice, as practical networks typically exhibit a long tail distribution of latencies (a phenomenon well-studied by system and networking researchers [START_REF] Chen | Achieving low tail-latency and high scalability for serializable transactions in edge computing[END_REF][START_REF] Didona | Size-aware sharding for improving tail latencies in in-memory keyvalue stores[END_REF][START_REF] Yang | DispersedLedger: high-throughput Byzantine consensus on variable bandwidth networks[END_REF]).

To help readers familiar with the initial algorithms, we use the same message types (INIT, ECHO, READY, WITNESS) as in the original publications. It has been shown in [START_REF] Albouy | Asynchronous Byzantine reliable broadcast with a message adversary[END_REF] that the MBRB problem can be solved if and only if n > 3t + 2d.

Bracha's BRB algorithm reconstructed

Reconstructed version. Bracha's BRB algorithm comprises three phases. When a process invokes brb_broadcast(m, sn), it disseminates the app-message m an INIT message (first phase). The reception of this message by a correct process triggers its participation in a second phase implemented by the exchange of messages tagged ECHO. Finally, when a process has received ECHO messages from "enough" processes, it enters the third phase, in which READY messages are exchanged, at the end of which it brb-delivers the app-message m. Alg. 2 is a reconstructed version of the Bracha's BRB, which assumes n > 3t + 2d + 2 √ td. The algorithm requires two instances of k2 -cast, denoted obj E and obj R , associated with the ECHO messages and the READY messages, respectively. For both these objects, the Boolean single is set to true. For the quorums, we have the following:

• obj E : q f = t + 1 and

q d = n+t 2 + 1, • obj R : q f = t + 1 and q d = 2t + d + 1. init: obj W ← SigFreeK2LCast(q d = n+3t 2 + 3d + 1, q f = n+t 2 + 1, single=false).
(1) operation mbrb_broadcast(m, sn) is ur_broadcast(INIT(m, sn)).

(2) when INIT(m, sn) is received from pj do obj W .k2 _cast(WITNESS(m), (sn, j)).

(3) when (WITNESS(m), (sn, j)) is obj W .k2 _delivered do mbrb_deliver(m, sn, j).

Algorithm 3: k2 -cast-based reconstruction of Imbs and Raynal's BRB algorithm (code of p i )

The integer sn is the sequence number of the app-message m mbrb-broadcast by p i . The identity of m is consequently the pair sn, i .

Alg.

2 provides MBRB = c 1 -d c-2t-d
under:

• B87-Assumption:

n > 3t + 2d + 2 √ td;
its proof of correctness can be found in Appendix B.1 (B87 stands for Bracha 1987).

Comparison (Table 2). When d = 0, both Bracha's algorithm and its reconstruction use the same quorum size for the READY phase. The quorums of the ECHO phase are however different (Table 2). As the algorithm requires n > 3t, we define ∆ = n -3t as the slack between the lower bound on n and the actual value of n. When considering the forwarding threshold q f , we have n+t

2 + 1 = 2t + ∆ 2 + 1 > t + 1.
As a result, the reconstruction of Bracha's algorithm always uses a lower forwarding threshold for ECHO messages than the original. It therefore forwards messages more rapidly and reaches the delivery quorum faster.

Threshold

Original version (ECHO phase) k2 -cast-based version (obj E ) . The algorithm requires a single k2 -cast object, denoted obj W , associated with the WITNESS message, and which is instantiated with q f = n+t 2 + 1 and q d = n+3t 2 + 3d + 1, and the Boolean single = false. Similarly to Bracha's reconstructed BRB, an identity of app-message in this algorithm is a pair sn, i containing a sequence number sn and a process identity i.

Forwarding q f n + t 2 + 1 t + 1 Delivery q d n + t 2 + 1 n + t 2 + 1

Alg. 3 provides

MBRB = c 1 - d c-n+3t 2 -3d under: • IR16-Assumption: n > 5t + 12d + 2td t+2d ; (where t + d > 0)
its proof of correctness can be found in Appendix B.2 (IR16 stands for Imbs-Raynal 2016).

Comparison (Table 3). Table 3 compares Imbs and Raynal's original algorithm against its k2 -cast reconstruction for d = 0. Recall that this algorithm saves one communication step with respect to Bracha's at the cost of a weaker t-tolerance, i.e., it requires n > 5t. As for Bracha, let us define the slack between n and its minimum as ∆ = n -5t, we have ∆ ≥ 1.

• Let us first consider the size of the forwarding quorum (first line of the table). We have n -2t = 3t + ∆ and n+t 2 + 1 = 3t + ∆ 2 + 1. When ∆ > 2, we always have ∆ > ∆ 2 + 1, it follows that the forwarding predicate of the reconstructed version is equal or weaker than the one of the original version.

• The same occurs for the size of the delivery quorum (second line of the table). We have n -t = 4t+∆ and n+3t 2 + 1 = 4t+ ∆ 2 + 1. So both reconstructed quorums are lower than those of the original version when ∆ > 2, making the reconstructed algorithm quicker as soon as n ≥ 5t + 3. The two versions behave identically for 5t + 3 ≥ n ≥ 5t + 2 (∆ ∈ {1, 2}).

Threshold

Original version (WITNESS phase) k2 -cast-based version (obj W )

Forwarding q f n -2t n + t 2 + 1 Delivery q d n -t n + 3t 2 + 1
Table 3: Imbs and Raynal's original version vs. k2 -cast-based reconstruction when d = 0

Numerical evaluation of the MBRB algorithms

A Signature-Based Implementation of k2 -Cast

This section presents an implementation of k2 -cast based on digital signatures. The underlying model is the same as that of Section 2 (page 4), except that the computing power of the attacker is now bounded, which allows us to leverage asymmetric cryptography.

Algorithm

The signature-based algorithm is described in Alg. 4. It uses an asymmetric cryptosystem to sign messages and verify their authenticity. Every process has a public/private key pair. Public keys are known to everyone, but private keys are only known to their owner. (Byzantine processes may exchange their private keys.) Each process also knows the mapping between process indexes and associated public keys, and each process can produce a unique, valid signature for a given message, and check if a signature is valid. It is a simple algorithm that ensures that an app-message must be k2 -cast by at least k correct processes to be k2 -delivered by at least correct processes. For the sake of simplicity, we say that a correct process p i "ur-broadcasts a set of signatures" if it ur-broadcasts a BUNDLE(m, id , sigs i ) in which sigs i contains the signatures at hand. A correct process p i ur-broadcasts an app-message m with identity id at line 5 or line 11.

• If this occurs at line 5, p i includes in the message it ur-broadcasts all the signatures it has already received for (m, id ) plus its own signature.

• If this occurs at line 11, p i has just received a message containing a set of signatures sigs for the pair (m, id ). The process p i then aggregates in sigs i the valid signatures it just received with the ones it did know about beforehand (line 10).

This algorithm simply assumes: (the prefix "sb" stands for signature-based)

• sb-k2 -Assumption 1: c > 2d,

• sb-k2 -Assumption 2: c -d ≥ q d ≥ t + 1.

Thanks to digital signatures, processes can relay the messages of other processes in Alg. 4. The algorithm, however, does not use forwarding in the same way Alg. 1 did: there is no equivalent of q f here, that is, the only way to "endorse" an app-message (which, in this case, is equivalent to signing this app-message) is to invoke the k2 _cast operation. Furthermore, only one app-message can be endorsed by a correct process for a given identity (which is the equivalent of single = true in the signature-free version).

Although this implementation of k2 -cast provides better guarantees than Alg. 1, using it to reconstruct signature-free BRB algorithms would be counter-productive. This is because signatures allow for MA-tolerant BRB algorithms that are more efficient in terms of round and message complexity than those that can be constructed using k2 -cast [START_REF] Albouy | Asynchronous Byzantine reliable broadcast with a message adversary[END_REF].

However, a signature-based k2 -cast does make sense in contexts in which many-to-many communication patterns are required [START_REF] Auvolat | Byzantine-tolerant set-constrained delivery broadcast[END_REF], and, we believe, opens the path to novel ways to handle local state resynchronization resilient to Byzantine failures and message adversaries. For instance, we are using the following algorithm in our own work to design churn-tolerant money transfer systems tolerating Byzantine failures and temporary disconnections. Algorithm 4: k2 -cast implementation with signatures (code for p i )

object SigBasedK2LCast(q d ) is (1) operation k2 _cast(m, id ) is (2) if (-,

Guarantees

The proof of the following theorem can be found in Appendix C.

Theorem 2 (k2 -CORRECTNESS). If sb-k2 -Assumption 1 and 2 are verified, Alg. 4 implements k2cast with the following guarantees: (i) k = q d -n+c, (ii) k = q d , (iii) = c-d, and (iv) δ = q d > n+t 2 .

Conclusion

This paper discussed reliable broadcast in asynchronous systems where an adversary can control some Byzantine processes and can suppress messages. Its starting point was the design of generic reliable broadcast abstractions suited to applications that do not require total order on the delivery of application messages (distributed money transfers are such applications [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] Guerraoui | The consensus number of a cryptocurrency[END_REF]). However, the ability to thwart an adversary controlling Byzantine processes and a message adversary is new. This approach can be applied to the design of a wide range of quorum-based distributed algorithms other than reliable broadcast. For instance, we conjecture that k2 -cast could benefit self-stabilizing and self-healing distributed systems [START_REF] Altisen | Introduction to distributed self-stabilizing algorithms[END_REF], where a critical mass of messages from other processes is needed in order to re-synchronize the local state of a given process.

• Case single ∧ q d > n+t 2 . Thanks to the predicate at line 9, we can assert that p i and p j must have respectively received at least q d distinct copies of ENDORSE(m, id ) and ENDORSE(m , id ), from two sets of processes, that we respectively denote A and B, such that |A| ≥ q d > n+t 2 and |B| ≥ q d > n+t 2 . We have |A ∩ B| > 2 n+t 2 -n = t. Hence, at least one correct process p x has ur-broadcast both ENDORSE(m, id ) and ENDORSE(m , id ). But because of the predicates at lines 2 and 6, and as single = true, p x ur-broadcasts at most one message ENDORSE(-, id ), either during a k2 _cast(m, id ) invocation at line 3 or during a forwarding step at line 7. We conclude that m is necessarily equal to m .

A.2 Liveness Proof

Lemma 1. e × (k U + k F -q d + 1) ≥ (k U + k F )(c -d -q d + q f ) -c(q f -1) -k NB (q d -q f ).
Proof. Combining ( 1), ( 2), ( 3) and ( 4) yields:

(k U + k F ) e + (q d -1)(k NF + k NB + k F -e ) + (q f -1)(c -k NF -k NB -k F ) ≥ (k U + k F )(c -d), e × (k U + k F -q d + 1) ≥ (k U + k F )(c -d) -(q d -1)(k NF + k NB + k F ) - (q f -1)(c -k NF -k NB -k F ), ≥ (k U + k F )(c -d) -(q d -q f )(k NF + k NB + k F ) -c(q f -1).
Using sf-k2 -Assumption 1, we have q d -q f ≥ 0. By definition, we also have k NF ≤ k U , which yields:

e × (k U + k F -q d + 1) ≥ (k U + k F )(c -d) -(q d -q f )(k U + k F + k NB ) -c(q f -1), ≥ (k U + k F )(c -d -q d + q f ) -c(q f -1) -k NB (q d -q f ).
Lemma 2. If no correct process k2 -casts (m , id ) with m = m, then no correct process forwards ENDORSE(m , id ) at line 7 (and then k NB = 0).

Proof. Assume there is a correct process that ur-broadcasts ENDORSE(m , id ) at line 7 with m = m. Let us consider the first such process p i . To execute line 7, p i must first receive q f messages ENDORSE(m , id ) from distinct processes. Since q f > t (sf-k2 -Assumption 1), at least one of these processes, p j , is correct. Since p i is the first correct process to forward ENDORSE(m , id ) at line 7, the ENDORSE(m , id ) message of p j must come from line 3, and p j must have k2 -cast (m , id ). We have assumed that no correct process k2 -cast m = m, therefore m = m. Contradiction. We conclude that, under these assumptions, no correct process ur-broadcasts ENDORSE(m , id ) with m = m, be it at line 3 (by assumption) or at line 7 (shown by this proof). As a result, k NB = 0.

Lemma 3 (k2 -LOCAL-DELIVERY). If at least k = c(q f -1)
c-d-q d +q f + 1 correct processes k2 -cast an app-message m with identity id and no correct process k2 -casts any app-message m with identity id such that m = m , then at least one correct process p i k2 -delivers m with identity id .

Proof. Let us assume that no correct process k2 -casts (m , id ) with m = m. No correct process therefore ur-broadcasts ENDORSE(m , id ) with m = m at line 3. Lemma 2 also applies and no correct process forwards ENDORSE(m , id ) with m = m at line 7 either, so k NB = 0. Because no correct process ur-broadcasts ENDORSE(m , id ) with m = m whether at line 3 or 7, a correct process receives at most t messages ENDORSE(m , id ) (all coming from Byzantine processes). As by sf-k2 -Assumption 1, t < q d , no correct process k2 -delivers (m , id ) with m = m at line 10. v We now prove the contraposition of the Lemma. Let us assume no correct process k2 -delivers (m, id ). Since, by our earlier observations, no correct process k2 -delivers (m , id ) with m = m either, the condition at line 9 implies that no correct process ever receives at least q d ENDORSE(m, id ), and therefore e = 0. By Lemma 1 we have c(q f -1) ≥ (k

U +k F )(c-d-q d +q f ). sf-k2 -Assumption 1 implies that c-d-q d ≥ 0 ⇐⇒ c-d-q d +q f > 0 (as q f ≥ t+1 ≥ 1), leading to k U +k F ≤ c(q f -1)
c-d-q d +q f . Because of the condition at line 2, a correct process p j that has k2 -cast (m, id ) but has not ur-broadcast ENDORSE(m, id ) at line 3 has necessarily ur-broadcast ENDORSE(m, id ) at line 7. We therefore have

k I ≤ k U + k F , which gives k I ≤ c(q f -1) c-d-q d +q f . By contraposition, if k I > c(q f -1)
c-d-q d +q f , then at least one correct process must k2 -deliver (m, id ). Hence, we have k = c(q f -1)

c-d-q d +q f + 1. Lemma 4. (single = false) =⇒ (k NB = 0).
Proof. Let us consider a correct process p i ∈ A ∪ B. If we assume p i ∈ F , p i never executes line 7 by definition. Because p i ∈ A ∪ B, p i has received at least q f messages ENDORSE(m, id ), and therefore did not fulfill the condition at line 6 when it received its q f th message ENDORSE(m, id ). As single = false by Lemma assumption, to falsify this condition, p i must have had already urbroadcast ENDORSE(m, id ) when this happened. Because p i never executes line 7, this implies that p i ur-broadcasts ENDORSE(m, id ) at line 3, and therefore p i ∈ NF . This reasoning proves that A ∪ B \ F ⊆ NF . As the sets F , NF and NB partition A ∪ B, this shows that NB = ∅, and k NB = |∅| = 0. Lemma 5. If at least one correct process k2 -delivers (m, id ) and x = k U + k F (the number of correct processes that ur-broadcast ENDORSE(m, id ) at line 3 or 7), then x ≥ q d -t and

x 2 -x(c -d + q f - 1 -k NB ) ≥ -(c -k NB )(q f -1).

Proof. Let us write w b

A the total number of ENDORSE(m, id ) messages from Byzantine processes received by the processes of A, and w A = w c A + w b A the total of number ENDORSE(m, id ) messages received by the processes of A, whether these ENDORSE messages originated from correct or Byzantine senders. By definition, w b A ≤ t e and w A ≥ q d e . By combining these two inequalities with (1) on w c A we obtain:

q d e ≤ w A = w c A + w b A ≤ (k U + k F ) e + t e = (t + k U + k F ) e , q d ≤ t + k U + k F , (as e > 0) q d -t ≤ k U + k F = x. (5)
This proves the first inequality of the lemma. The processes in A ∪ B each receive at most k U + k F distinct ENDORSE(m, id ) messages from correct processes, so we have

w c A + w c B ≤ (k NF + k F + k NB )(k U + k F ).
Combined with the inequalities (3) on w c C and (4) on w c A + w c B + w c C that remain valid in this case, we now have:

(k NF + k F + k NB )(k U + k F ) + (q f -1)(c -k NF -k NB -k F ) ≥ (k U + k F )(c -d), (k NF + k F + k NB )(k U + k F -q f + 1) ≥ (k U + k F )(c -d) -c(q f -1). (6)
Let us determine the sign of (k U + k F -q f + 1). We derive from (5):

k U + k F -q f + 1 ≥ q d -t -q f + 1 ≥ 1 > 0.
(as q d -q f ≥ t by sf-k2 -Assumption 1)

As (k U + k F -q f + 1
) is positive and we have k U ≥ k NF by definition, we can transform (6) into:

(k U + k F + k NB )(k U + k F -q f + 1) ≥ (k U + k F )(c -d) -c(q f -1), (x + k NB )(x -q f + 1) ≥ x(c -d) -c(q f -1), (as x = k U + k F ) x 2 -x(c -d + q f -1 -k NB ) ≥ -(c -k NB )(q f -1).
vi Lemma 6. If k NB = 0, and at least one correct process k2 -delivers (m, id ),

then k U + k F ≥ q d .
Proof. By Lemma 5 we have:

x 2 -x(c -d + q f -1 -k NB ) ≥ -(c -k NB )(q f -1), (7)
As ( 7) holds for all, values of c ∈ [n -t, n], we can in particular consider c = n -t. Moreover, as by hypothesis, k NB = 0, we have.

x 2 -x(n -t -d + q f -1) + (q f -1)(n -t) ≥ 0, x 2 -αx + (q f -1)(n -t) ≥ 0.
(by definition of α)

Let us first observe that the discriminant of the second-degree polynomial in (8) is non negative, i.e. α 2 -4(q f -1)(n -t) ≥ 0 by sf-k2 -Assumption 2. This allows us to compute the two real-valued roots as follows:

r 0 = α 2 - α 2 -4(q f -1)(n -t) 2 and r 1 = α 2 + α 2 -4(q f -1)(n -t) 2 .
Thus ( 8) is satisfied if and only if x ≤ r 0 ∨ x ≥ r 1 .

• Let us prove r 0 ≤ q d -1 -t. We need to show that:

α 2 - α 2 -4(q f -1)(n -t) 2 ≤ q d -1 -t α 2 -(q d -1) + t ≤ α 2 -4(q f -1)(n -t) 2 α 2 -4(q f -1)(n -t) 2 ≥ α 2 -(q d -1) + t α 2 -4(q f -1)(n -t) ≥ α -2(q d -1) + 2t.
The inequality is trivially satisfied if α -2(q d -1) + 2t < 0. For all other cases, we need to verify that:

α 2 -4(q f -1)(n -t) ≥ (α -2(q d -1) + 2t) 2 , α 2 -4(q f -1)(n -t) ≥ α 2 + 4(q d -1) 2 + 4t 2 -4α(q d -1) + 4αt -8t(q d -1), -4(q f -1)(n -t) ≥ 4(q d -1) 2 + 4t 2 -4α(q d -1) + 4αt -8t(q d -1), -(q f -1)(n -t) ≥ (q d -1) 2 + t 2 -α(q d -1) + αt -2t(q d -1), -(q f -1)(n -t) ≥ (q d -1 -t) 2 -α(q d -1 -t),
and thus α(q d -1-t)-(q f -1)(n-t)-(q d -1-t) 2 ≥ 0, which is true by sf-k2 -Assumption 4.

• Let us prove r 1 > q d -1. We want to show that:

α 2 + α 2 -4(q f -1)(n -t) 2 > q d -1
Let us rewrite the inequality as follows:

α + α 2 -4(q f -1)(n -t) > 2(q d -1) α 2 -4(q f -1)(n -t) > 2(q d -1) -α vii
The inequality is trivially satisfied if 2(q d -1) -α < 0. For all other cases, we can take the squares as follows:

α 2 -4(q f -1)(n -t) > (2(q d -1) -α) 2 , α 2 -4(q f -1)(n -t) > 4(q d -1) 2 + α 2 -4α(q d -1), -4(q f -1)(n -t) > 4(q d -1) 2 -4α(q d -1), 4α(q d -1) -4(q f -1)(n -t) -4(q d -1) 2 > 0, α(q d -1) -(q f -1)(n -t) -(q d -1) 2 > 0,
which is true by sf-k2 -Assumption 3.

We now know that r 0 ≤ q d -1 -t and that r 1 > q d -1. In addition, as x ≤ r 0 ∨ x ≥ r 1 , we have x ≤ q d -t -1 ∨ x > q d -1. But Lemma 5 states that x ≥ q d -t, which is incompatible with x ≤ q d -t -1. So we are left with x > q d -1, which implies, as q d and x are integers that x ≥ q d , thus proving the lemma for c = n -t.

Let us now consider the set E 0 of all executions in which t processes are Byzantine, and therefore c = n -t, and a set E c of executions in which there are fewer Byzantine processes, and thus c > n -t correct processes. We show that E c ⊆ E 0 in that a Byzantine process can always simulate the behavior of a correct process. In particular, if the simulated correct process is not subject to the message adversary, the simulating Byzantine process simply operates like a correct process. If, on the other hand, the simulated correct process misses some messages as a result of the message adversary, the Byzantine process can also simulate missing such messages. As a result, the executions that can happen when c > n -t can also happen when c = n -t. Thus our result proven for c = n -t can be extended to all possible values of c.

Lemma 7. If k NB = 0 and k U +k F ≥ q d , then at least c 1 -d c-q d +1
correct processes k2 -deliver some app-message with identity id (not necessarily m).

Proof. As k NB = 0 and k U + k F ≥ q d , we can rewrite the inequality of Lemma 1 into:

e × (k U + k F -q d + 1) ≥ (k U + k F )(c -d -q d + q f ) -c(q f -1).
From k U + k F ≥ q d we derive k U + k F -q d + 1 > 0, and we transform the above inequality into:

e ≥ (k U + k F )(c -d -q d + q f ) -c(q f -1) k U + k F -q d + 1 .
Let us now focus on the case in which c = n -t, we obtain:

e ≥ (k U + k F )(n -t -d -q d + q f ) -(n -t)(q f -1) k U + k F -q d + 1 .
The right side of the inequality is of the form:

e ≥ φx -β x -γ = φ + φγ -β x -γ (9)
with:

x = k U + k F , γ = q d -1, α = n -t -d + q f -1, φ = n -t -d -q d + q f , β = c(q f -1).
viii Since, by hypothesis, x = k U + k F ≥ q d , we have:

x -γ = k U + k F -q d + 1 > 0. (10)
We also have:

φγ -β = (α -γ)γ -c(q f -1) = αγ -γ 2 -c(q f -1), = α(q d -1) -(q d -1) 2 -(n -t)(q f -1) > 0, (by sf-k2 -Assumption 3) φγ -β > 0. (11)
Injecting ( 10) and ( 11) into ( 9), we conclude that φ + φγ-β x-γ is a decreasing hyperbole defined over x ∈]γ, ∞] with asymptotic value φ when x → ∞. As x is a number of correct processes, x ≤ c. The decreasing nature of the right-hand side of (9) leads us to:

e ≥ φ + φγ-β c-γ = φc-β c-γ ≥ c(c-d-q d +q f )-c(q f -1) c-q d +1 ≥ c × c-d-q d +1 c-q d +1 = c 1 -d c-q d +1
. Since e is a positive integer, we conclude that at least min = c 1 -d c-q d +1 correct processes receive at least q d message ENDORSE(m, id) at line 9. As each of these processes either k2 -delivers (m, id ) when this first happens, or has already k2 -delivered another app-message m = m with identity id , we conclude that at least min correct processes k2 -deliver some app-message (whether it be m or m = m) with identity id when c = n -t. The reasoning for extending this result to any value of c ∈ [n -t, n] is identical to the one at the end of the proof of Lemma 6 just above.

Lemma 8 (k2 -WEAK-GLOBAL-DELIVERY). If single = false, and a correct process k2 -delivers an app-message m with identity id , then at least = c 1 -d c-q d +1 correct processes k2 -deliver an app-message m with identity id (each possibly different from m).

Proof. Let us assume single = false, and one correct process k2 -delivers (m, id ). By Lemma 4, k NB = 0. The prerequisites for Lemma 6 are verified, and therefore k U + k F ≥ q d . This provides the prerequisites for Lemma 7, from which we conclude that at least = c 1 -d c-q d +1 correct processes k2 -deliver an app-message m with identity id , which concludes the proof of the lemma.

Lemma 9 (k2 -STRONG-GLOBAL-DELIVERY). If single = true, and a correct process k2 -delivers an app-message m with identity id , and no correct process k2 -casts an app-message m = m with identity id , then at least = c 1 -d c-q d +1 correct processes k2 -deliver m with identity id .

Proof. Let us assume that (i) single = true, (ii) no correct process k2 -casts (m , id ) with m = m, and (iii) one correct process k2 -delivers (m, id ). Lemma 2 holds and implies that k NB = 0. From there, as above, Lemmas 6 and 7 hold, and at least = c 1 -d c-q d +1 correct processes k2 -deliver an app-message for identity id .

By hypothesis, no correct process ur-broadcasts ENDORSE(m , id ) at line 3 with m = m. Similarly, because of Lemma 2, no correct process ur-broadcasts ENDORSE(m , id ) at line 7 with m = m. As a result, a correct process can receive at most receive t messages ENDORSE(m , id ) at line 9 (all from Byzantine processes). As q d > t (by sf-k2 -Assumption 1), the condition of line 9 never becomes true for m = m, and as result no correct process delivers an app-message m = m with identity id . All processes that k2 -deliver an app-message with identity id , therefore, k2 -deliver m, which concludes the lemma.

B Proof of the Signature-Free MBRB Implementations

The proofs that follow use integer arithmetic. Given a real number x and an integer i, let us recall that

x -1 < x ≤ x ≤ x < x + 1, x + i = x + i, x + i = x + i, -x = -x , (i > x) ⇐⇒ (i ≥ x + 1), (i < x) ⇐⇒ (i ≤ x -1).
B.1 Proof of MBRB with Bracha's reconstructed algorithm (Algorithm 2) B.1.1 Instantiating the parameters of the k2 -cast objects In Alg. 2 (page 12), we instantiate the k2 -cast objects obj E and obj R using the signature-free implementation presented in Section 3.2. Let us mention that, given that obj E .single = obj R .single = true, then we use the strong variant of the global-delivery property of k2 -cast (k2 -STRONG-GLOBAL-DELIVERY) for both objects obj E and obj R . Moreover, according to the definitions of k , k, and δ (page 5) and their values stated in Theorem 1, we have:

• obj E .k = obj E .q f -n + c = t + 1 -n + c ≥ t + 1 -t = 1, • obj E .k = c(obj E .q f -1) c -d -obj E .q d + obj E .q f + 1 = c(t + 1 -1) c -d -n+t 2 -1 + t + 1 + 1 = ct c -d -n-t 2 + 1, • obj E . = c 1 - d c -obj E .q d + 1 = c 1 - d c -n+t 2 -1 + 1 = c 1 - d c -n+t 2 , • obj E .δ = obj E .q f > n + t 2 ∨ obj E .single ∧ obj E .q d > n + t 2 = t + 1 > n + t 2 ∨ true ∧ n + t 2 + 1 > n + t 2 = (false ∨ (true ∧ true)) = true, • obj R .k = obj R .q f -n + c = t + 1 -n + c ≥ t + 1 -t = 1, • obj R .k = c(obj R .q f -1) c -d -obj R .q d + obj R .q f + 1 = c(t + 1 -1) c -d -2t -d -1 + t + 1 + 1 = ct c -2d -t + 1, • obj R . = c 1 - d c -obj R .q d + 1 = c 1 - d c -2t -d -1 + 1 = c 1 - d c -2t -d , • obj R .δ = obj R .q f > n + t 2 ∨ obj R .single ∧ obj R .q d > n + t 2 = t + 1 > n + t 2 ∨ true ∧ 2t + d + 1 > n + t 2 ∈ {true, false} x
We recall that parameter δ controls the conditional no-duplicity property. The value for obj E .δ is true, but that of value for obj R .δ may be either true or false depending on the values of n, t, and d. This is fine because, in Bracha's reconstructed algorithm (Alg. 2), it is the first round (obj E ) that ensures no-duplicity. Once this has happened, the second round (obj R ) does not need to provide no-duplicity but only needs to guarantee the termination properties of local and global delivery. This observation allows obj R to operate with lower values of q d and q f . Finally, we observe that for Alg. 2, sf-k2 -Assumption 1 through 4 are all satisfied by B87-Assumption n > 3t + 2d + 2

√

td. We prove this fact in Appendix 14. In the following, we prove that 3t + 2d + 2

√ td ≥ 2t + d + √ t 2 + 6td + d 2 ≥ 3t + 2d.
Observation 1. For d, t ∈ N 0 non-negative integers, we have:

3t + 2d + 2 √ td ≥ 2t + d + t 2 + 6td + d 2 ≥ 3t + 2d.
Proof. Let us start by proving the first inequality.

t 2 + 6td + d 2 + 4 √ td(t + d) ≥ t 2 + 6td + d 2 , t 2 + d 2 + 4td + 4t √ td + 4d √ td + 2td ≥ t 2 + 6td + d 2 , (t + d + 2 √ td) 2 ≥ t 2 + 6td + d 2 , t + d + 2 √ td ≥ t 2 + 6td + d 2 , 3t + 2d + 2 √ td ≥ 2t + d + t 2 + 6td + d 2 .
Let us then prove the second inequality:

t 2 + 6td + d 2 ≥ t 2 + 2td + d 2 = (t + d) 2 , t 2 + 6td + d 2 ≥ t + d, 2t + d + t 2 + 6td + d 2 ≥ 3t + 2d.

B.1.2 Proof of satisfaction of the assumptions of Algorithm 1

In this section, we prove that all the assumptions of the signature-free k2 -cast implementation presented in Alg. 1 (page 7) are well respected for the two k2 -cast instances used in Alg. 2 (obj E and obj R ).

Lemma 14. Alg. 1's assumptions are well respected for obj E .

Proof. Let us recall that q f = t + 1 and q d = n+t 2 + 1 for obj E .

• Proof of satisfaction of sf-k2 -Assumption 1 (c -d ≥ obj E .q d ≥ obj E .q f + t ≥ 2t + 1):

By B87-Assumption and Observation 1, we have the following:

c -d ≥ n -t -d = 2n -2t -2d 2 ,
(by definition of c)

> n + 3t + 2d -2t -2d 2 = n + t 2 , (as n > 3t + 2d) ≥ n + t 2 + 1. (12)
We also have:

n + t 2 + 1 ≥ 3t + 2d + 1 + t 2 + 1, (as n > 3t + 2d) ≥ 2t + d + 1/2 + 1 = 2t + d + 1 ≥ 2t + 1. (13)
xi By combining ( 12) and ( 13), we get:

c -d ≥ n + t 2 + 1 ≥ 2t + 1 ≥ 2t + 1, c -d ≥ obj E .q d ≥ obj E .q f + t ≥ 2t + 1. (sf-k2 -Assumption 1)
• Proof of satisfaction of sf-k2 -Assumption 2 (α 2 -4(obj E .q f -1)(n -t) ≥ 0):

Let us recall that, for object obj E , we have q f = t + 1 and q d = n+t 2 + 1. We therefore have α = n + q f -t -d -1 = n -d. Let us now consider the quantity:

∆ = α 2 -4(q f -1)(n -t) = (n -d) 2 -4t(n -t) = 4t 2 + d 2 + n 2 + n (-4t -2d)
The inequality is satisfied if n > 2

√

td + 2t + d, which is clearly the case as n > 3t + 2d + 2 √ td. This proves sf-k2 -Assumption 2.

• Proof of satisfaction of sf-k2 -Assumption 3 (α(obj E .q d -1) -

(obj E .q f -1)(n -t) -(obj E .q d - 1) 2 > 0):
Let us consider the quantity on the left-hand side of sf-k2 -Assumption 3 and substitute q f = t+1,

q d = n+t 2 + 1: α(q -1) -(q f -1)(n -t) -(q d -1) 2 , = (n + q f -t -d -1)(q d -1) -(q f -1)(n -t) -(q d -1) 2 , = (n -d) n + t 2 -t(n -t) - n + t 2 2 . (14)
We now observe that n+t 2 = n+t- 2 with = 0 if n + t = 2k is even, and = 1 if n + t = 2k + 1 is odd. We thus rewrite [START_REF] Didona | Size-aware sharding for improving tail latencies in in-memory keyvalue stores[END_REF] as follows:

(n -d) n + t - 2 -t(n -t) - n + t - 2 2 , = n + t - 2 × 2n -2d -n -t + 2 -t(n -t), = (n + t -)(n -2d -t + ) -4t(n -t) 4 , = n 2 -t 2 -2td + 2t -2nd + 2d -2 -4nt + 4t 2 4 , = n 2 + 3t 2 -2td -2n(d + 2t) + (2t + 2d -) 4 .
As we want to show that the above quantity is positive, the result will not change if we multiply it by 4:

n 2 + 3t 2 -2td -2n(d + 2t) + (2t + 2d -) > 0. ( 15
)
We now solve the inequality to obtain:

n > 2t + d + t 2 + 6td + d 2 -(2t + 2d -). xii We observe that, for t + d ≥ 1, the quantity -(2t + 2d -) is strictly negative if = 1, therefore if = 1 ∨ t + d ≥ 1: n > 3t + 2d + 2 √ td, ≥ t + d + t 2 + 6td + d 2 ,
(by Observation 1)

≥ 2t + d + t 2 + 6td + d 2 -(2t + 2d -).
This leaves out the case (t = d = 0) ∧ (n = 2k + 1 is odd), for which we can show that ( 15) is positive or null for n ≥ 1:

(15) :

n 2 + 3t 2 -2td -2n(d + 2t) + (2t + 2d -), = n 2 -1 ≥ 0 for n 1.
This completes the proof of sf-k2 -Assumption 3.

• Proof of satisfaction of sf-k2 -Assumption 4 (α

(obj E .q d -1-t)-(obj E .q f -1)(n-t)-(obj E .q d - 1 -t) 2 ≥ 0):
Let us consider the quantity on the left-hand side of sf-k2 -Assumption 4 and substitute

q f = tb + 1, q d = n+t 2 + 1: α(q d -1 -t) -(q f -1)(n -t) -(q d -1 -t) 2 , = (n + q f -t -d -1)(q d -1 -t) -(q f -1)(n -t) -(q d -1 -t) 2 , = (n -d) n + t 2 -t -t(n -t) - n + t 2 -t 2 . (16)
Like before, we observe that n+t 2 = n+t- 2 with = 0 if n + t = 2k is even, and = 1 if n + t = 2k + 1 is odd. We thus rewrite [START_REF] Dwork | Fault tolerance in networks of bounded degree[END_REF] as follows:

(n -d) n + t - 2 -t -t(n -t) - n + t - 2 -t 2 , = (n -d) • n -t - 2 -t(n -t) - n -t - 2 2 , = n -t - 2 • 2n -2d -n + t + 2 -t(n -t), = (n -t -)(n -2d + t + ) -4nt + 4t 2 4 , = -t 2 + 2td -2t + 2d -2dn -2 + n 2 4 .
As we want to show that the above quantity is non-negative, the result will not change if we multiply it by 4:

-t 2 + 2td -2t + 2d -2 -2dn + n 2 .
We then solve the inequality to obtain: n ≥ max(t + , -t + 2d -), which is clearly satisfied as n ≥ 3t + 2d + 2 √ td + 1. This proves all previous inequality and thus sf-k2 -Assumption 4.

Lemma 15. Alg. 1's assumptions are well respected for obj R .

xiii Proof. Let us recall that q f = t + 1 and q d = 2t + d + 1 for obj R . Let us observe that we have then q d -q f -t -d = 0.

• Proof of satisfaction of sf-k2 -Assumption 1 (c -d ≥ obj R .q d ≥ obj R .q f + t ≥ 2t + 1):

From Observation 1, we have:

c -d ≥ n -t -d ≥ 3t + 2d + 1 -t -d ≥ 2t + d + 1, (as n > 3t + 2d) c -d ≥ 2t + d + 1 ≥ 2t + 1 ≥ 2t + 1, c -d ≥ obj R .q d ≥ obj R .q f + t ≥ 2t + 1.
(sf-k2 -Assumption 1)

• Proof of satisfaction of sf-k2 -Assumption 2 (α 2 -4(obj R .q f -1)(n -t) ≥ 0):

Let us recall that, for object obj R , we have q f = t+1 and q d = 2t+d+1. As sf-k2 -Assumption 2 depends on q d but not on q f , and since obj E .q f = obj R .q f , we refer the reader to the proof we gave in Lemma 14 for obj E .

• Proof of satisfaction of sf-k2 -Assumption 3 (α(obj R .q d -1) -

(obj R .q f -1)(n -t) -(obj R .q d - 1) 2 > 0):
Let us consider the quantity on the left-hand side of sf-k2 -Assumption 3:

α(q d -1) -(q f -1)(n -t) -(q d -1) 2 , = (n + q f -t -d -1)(q d -1) -(q f -1)(n -t) -(q d -1) 2 , = (n -d)(2t + d) -t(n -t) -(2t + d) 2 , = 2nt + nd -2td -d 2 -nt + t 2 -4t 2 -d 2 -4td, = n(t + d) -6td -2d 2 -3t 2 , = n(t + d) -(6td + 2d 2 + 3t 2 ). (17)
Then, we observe that we can lower bound the quantity on the left side of ( 17) by substituting B87-Assumption, i.e. n > 3t + 2d + 2

√ td ≥ 2t + d + √ t 2 + 6td + d 2 .
For convenience, in the following we write ρ = t 2 + 6td + d 2 , thus n > 2t + d + √ ρ. We get:

n(t + d) -(3t 2 + 6td + 2d 2 ), > (2t + d + √ ρ)(t + d) -(3t 2 + 6td + 2d 2 ), = √ ρ(t + d) -d 2 -t 2 -3td.
We now want to show that the above quantity is positive or null, i.e.:

√ ρ(t + d) -d 2 -t 2 -3td ≥ 0. (18)
We now rewrite (18) as follows:

√ ρ(t + d) ≥ d 2 + t 2 + 2td + td, √ ρ(t + d) ≥ (d + t) 2 + td, (t 2 + 6td + d 2 )(t + d) 2 ≥ ((d + t) 2 + td) 2 , ( as
(d + t) 2 + td ≥ 0) ((t + d) 2 + 4td)(t + d) 2 ≥ ((d + t) 2 + td) 2 , (t + d) 4 + 4td(t + d) 2 ≥ (d + t) 4 + (td) 2 + 2td(t + d) 2 , 2td(t + d) 2 ≥ (td) 2 , 2td(t 2 + d 2 + 2td) ≥ (td) 2 , 2td(t 2 + d 2 ) + 4(td) 2 ≥ (td) 2 , 2td(t 2 + d 2 ) + 3(td) 2 ≥ 0.
xiv This proves [START_REF] Guerraoui | The consensus number of a cryptocurrency[END_REF] and all previous inequalities and ultimately sf-k2 -Assumption 3.

• Proof of satisfaction of sf-k2 -Assumption 4 (α(obj R .q

d -1-t)-(obj R .q f -1)(n-t)-(obj R .q d - 1 -t) 2 ≥ 0):
Let us consider the quantity on the left-hand side of sf-k2 -Assumption 4:

α(q d -1 -t) -(q f -1)(n -t) -(q d -1 -t) 2 , (19)
= (n + q f -t -d -1)(q d -1 -t) -(q f -1)(n -t) -(q d -1 -t) 2 , = (n + -d)(t + d) -t(n -t) -(t + d) 2 , = (t + d)(n + -2d -t) -t(n -t), = nt + nd -2td -2d 2 -t 2 -td -nt + t 2 , = nd -3td -2d 2 , = nd -3td -2d 2 , = d(n -3t -2d). (20)
Like before, we observe that we can lower bound the quantity on the left side of ( 20) by substituting B87-Assumption, i.e., n > 3t + 2d + 2 √ td ≥ 3t + 2d, so we have:

(20) : d(n -3t -2d) > d(3t + 2d -2d -3t) = 0. (21)
which recursively proves that ( 19) is positive or zero and thus sf-k2 -Assumption 4.

B.1.3 Correctness proof

This section proves the following theorem: Proof. We want to show that:

c -d ≥ ct c -d -n-t 2 + 1 = obj E .k. (22)
As the left-hand side is also an integer, we can rewrite [START_REF] Maurer | Communicating reliably in multi-hop dynamic networks despite Byzantine failures[END_REF] as follows:

c -d > ct c -d -n-t 2 , ( 23
) (c -d)(c -d - n -t 2 ) > ct. (as (c -d -n-t 2 ) > 0)
We now observe that n+t 2 = n+t- 2 with = 0 if n+t = 2k is even, and = 1 if n+t = 2k+1 is odd, which leads us to:

(c -d)(c -d - n -t - 2 ) > ct, (c -d)(2c -2d -n + t + ) > 2ct, (c -d)(2c -2d -n + t + ) -2ct > 0.
xv Like for the proofs of Lemma 6 and Lemma 7, we leverage the fact that the executions that can happen when c > n -t can also occur when c = n -t. We thus rewrite our inequality for c = n -t:

(n -t -d)(n -t -2d + ) -2(n -t)t > 0, (n -t)(n -t -2d + -2t) -d(n -t -2d + ) > 0, (n -t) 2 + (n -t)(-2d + -2t) -d(n -t -2d + ) > 0, n 2 + t 2 -2nt -2nd + n -2nt + 2td -t + 2t 2 -nd + td + 2d 2 -d > 0, n 2 + 3t 2 -4nt -3nd + n + 3td -t + 2d 2 -d > 0, n 2 -n(4t + 3d -) + 3t 2 + 3td + 2d 2 -(t + d) > 0.
We now solve the second-degree inequality with respect to n. It is easy to see that the discriminant is non-negative for non-negative values of t and d. So we obtain:

n > 2t + 3d 2 - 2 + √ 4t 2 + 12td -4t + d 2 -2d + 2 2 , -4t -3d + + 2n -4t 2 + 12td -4t + d 2 -2d + 2 > 0,
which is implied by the following as n ≥ 3t + 2d + 2

√ td + 1: 4 √ td + 2t + d + 2 + -4t 2 + 12td -4t + d 2 -2d + 2 > 0, 4 √ td + 2t + d + 2 + > 4t 2 + 12td -4t + d 2 -2d + 2 .
Taking the squares as both the argument of the square root and the left-hand side are non-negative leads to:

4 √ td + 2t + d + + 2 2 > 4t 2 + 12td -4t + d 2 -2d + 2 , 16t 3
We can then easily observe that the left-hand side of ( 24) is strictly positive, thereby proving all previous inequalities and thus the lemma. Lemma 17. obj E . ≥ obj R .k.

Proof. We need to prove:

obj E . = c 1 - d c -n+t 2 ≥ ct c -2d -t + 1 = obj R .k. ( 25
)
We observe that x ≥ m + 1 if and only if x > m, and that m ≥ m . Therefore [START_REF] Pease | Reaching agreement in the presence of faults[END_REF] is implied by the following:

c 1 - d c -n+t- 2 ≥ ct c -t -2d , c - 2dc 2c -t -n + > ct c -t -2d .
xvi As both denominators are positive, we can solve:

-t (-t + 2c + -n) -2d (-t -2d + c) + (-t -2d + c) (-t + 2c + -n) > 0, -t (-t + 2c + -n) + (-t -2d + c) (-t -2d + 2c + -n) > 0, -t (-2t + c + ) + (-t -2d + c) (-2t -2d + c + ) > 0, (as c ≥ n -t) -t (-2t + c + ) + (-t -2d + c) (-2t -2d + c + ) > 0, -t (-t + 2c -n) + (-3t -2d + c) + (-t -2d + c) 2 > 0, t 2 -2tc + tn + (-3t -2d + c) + (-t -2d + c) 2 > 0, We now consider the two possible values of :

• = 0: 2t 3 2 √ d + 5t 2 + 6td -4tc + + 4d 2 -4dc + c 2 > 0 (26)
We solve the inequality with respect to c to obtain (when the discriminant is positive): In this case, we obtain:

c > 2t + 2d + -2t
2t 3 2 √ d + 5t 2 + 6td -4tc -2t + 4d 2 -4dc -2d + c 2 + c > 0,
which is implied by a negative discriminant or by:

c > 2t + 2d + -2t 3 2 √ d -t 2 + 2td + 1/4 - 1 2 .
Like before, we simply observe that:

2 √ td ≥ √ 2td + 1 2 - 1 2 , ≥ 2td + 1/4 - 1 2 , ≥ -2t 3 2 √ d -t 2 + 2td + 1/4 - 1 2 ,
thereby proving the second case and the lemma. least c -d = , k2 -deliver some app-message for identity id at line 16, whether it be m or any other app-message.

Lemma 38 (k2 -STRONG-GLOBAL-DELIVERY). If a correct process k2 -delivers an app-message m with identity id , and no correct process k2 -casts an app-message m = m with identity id , then at least = c -d correct processes k2 -deliver m with identity id .

Proof. If a correct process k2 -delivers (m, id ) at line 16, then by Lemma 37, we can assert that at least = c -d correct process eventually k2 -deliver some app-message (not necessarily m) with identity id . Moreover, as no correct process k2 -casts (m , id ) with m = m, then Lemma 35 holds, and we conclude that all correct processes k2 -deliver (m, id ). and5b) that is required, resp. guaranteed, by the corresponding k2 -cast object. The two plots show the two roles of the two k2 -cast objects. The first, obj E , needs to provide agreement among the possibly different messages sent by Byzantine processes (Fig. 4). As a result, it can operate in a more limited region of the parameter space. obj R , on the other hand, would, in principle, be able to support larger values of d and t, but it needs to operate in conjunction with obj E (Fig. 5). The extra constraint introduced by chaining the two objects suggests that a single k2 -cast algorithm could achieve better performance. But this is not the case if we examine the performance of the reconstructed Imbs-Raynal algorithm depicted in Fig. 3b. The reason lies in the need for higher quorum values in obj W due to single = false. In the future, we plan to investigate if variants of this algorithm can achieve tighter bounds and explore the limits of signature-free k2 -cast-based broadcast in the presence of an MA and Byzantine processes.

D Numerical Evaluation

Figure 1 :

 1 Figure 1: From the system parameters to a k2 -cast implementation

  Subsets of correct processes based on the number of received ENDORSE messages (A, B and C) and based on their ur-broadcast actions (U , F , NF , and NB ) # received msgs.

Figure 2 :

 2 Figure 2: Subsets of correct processes and distribution of ENDORSE messages among them

Fig. 3

 3 Fig.3provides a numerical evaluation of the delivery guarantees of both k2 -cast-based MBRB algorithms (Algs. 2 and 3) in the presence of Byzantine processes and an MA. Results were obtained for n = 100 and c = n -t, and show the values of MBRB for different values of t and d. For instance, Fig.3ashows that with 6 Byzantine processes and an MA suppressing up to 9 ur-broadcast messages, Alg. 2 ensures the MBRB-GLOBAL-DELIVERY property with MBRB = 83. The figures illustrate that the reconstructed Bracha algorithm performs in a broader range of parameter values, mirroring the bounds on n, t, and d captured by B87-Assumption and IR16-Assumption. Nonetheless, both algorithms exhibit values of MBRB that can support real-world applications in the presence of an MA.

Figure 3 :

 3 Figure 3: Values of MBRB for the reconstructed BRB algorithms when varying t and d (n = 100 and c = n -t) within the ranges that satisfy B87-Assumption and IR16-Assumption

Theorem 3 (

 3 MBRB-CORRECTNESS). If B87-Assumption is verified, then Alg. 2 implements MBRB with the guarantee MBRB = c 1 -d c-2t-d . The proof follows from the next lemmas. Lemma 16. c -d ≥ obj E .k.

t 2 - 2 √ td) 2t 3 2 √ 2 √

 2222 2tc + t 2 √ t √ d + 3t + 2d + 1 + (-3t -2d + c) + (-t -2d + c) 2 > 0, (as n ≥ 3t + 2d + d + 4t 2 + 2td -2tc + t + (-3t -2d + c) + (-t -2d + c) 2 > 0, 2t 3 d + 5t 2 + 6td -4tc + t + 4d 2 -4dc + c 2 + (-3t -2d + c) > 0.

3 2 √ 2 √ td + 1 2 √ td + 1 > 2 √ d -t 2

 32212122 d -t 2 + 2td -t which we prove by observing that c ≥ n -t ≥ 2t + 2d + and that:2t + 2d + 2t + 2d + -2t 3 + 2td -t,as all terms except 2td inside the square root are negative. When the discriminant is negative (e.g. for d = 0), inequality[START_REF]Distributed algorithms for message-passing systems[END_REF] is satisfied for all values of c.• = 1:

  This section presents additional numerical results that complement those of Section 5.3, and provides concrete lower-bound values for the k and parameters of the k2 -cast objects used in the reconstructed Bracha MBRB algorithm (Alg. 2, page 12). Results were obtained by considering a network with n = 100 processes and varying values of t and d. Fig. 4 and Fig. 5 present the values of k and for the obj E and obj R of Alg. 2. The numbers in each cell show the value of k (Figs. 4a and 5a), resp. (Figs. 4b

  Fig. 3b on page 15 already displays the values of provided by obj W in the Imbs-Raynal algorithm. Fig. 6 complements it by showing the required values of k for obj W .

Figure 4 :

 4 Figure 4: Required values of k and provided values of for obj E in the reconstructed Bracha BRB algorithm with varying values of t and d within the ranges that satisfy B87-Assumption

Figure 5 :Figure 6 :

 56 Figure 5: Required values of k and provided values of for obj R in the reconstructed Bracha BRB algorithm with varying values of t and d within the ranges that satisfy B87-Assumption

Table 1 :

 1 Table 1 the list of acronyms and notations used in this paper. Acronyms and notations

	Acronyms	Meaning
	BRB	Byzantine-tolerant reliable broadcast
	MA	Message adversary
	MBRB	Message adversary-and Byzantine-tolerant reliable broadcast
	Notations	Meaning
	n	number of processes in the network
	t	upper bound on the number of Byzantine processes
	d	power of the message adversary

c effective number of correct processes in a run (n -t ≤ c ≤ n) k minimal nb of correct processes that k2 -cast a message minimal nb of correct processes that k2 -deliver a message k minimal nb of correct k2 -casts if there is a correct k2 -delivery δ true iff no-duplicity is guaranteed, false otherwise q d size of the k2 -delivery quorum q f size of the forwarding quorum single true iff only a single message can be endorsed, false otherwise

  Distribution of ENDORSE messages among correct processes of A, B, and C, sorted by decreasing number of ENDORSE messages received

Table 2 :

 2 Bracha's original version vs. k2 -cast-based reconstruction when d = 05.2 Imbs and Raynal's BRB algorithm reconstructedReconstructed version. Imbs and Raynal's BRB is another BRB implementation, which achieves an optimal good-case latency (only two communication steps) at the cost of a non-optimal t-resilience. Its reconstructed version requires n > 5t + 12d + 2td t+2d

  id ) not already signed by pi then[START_REF] Afek | Asynchrony from synchrony[END_REF] sig i ← signature of (m, id ) by pi; (4) sigs i ← {all valid signatures for (m, id ) ur-broadcast by pi} ∪ {sig i };

	(5)	ur_broadcast(BUNDLE(m, id , sigs i ));
	(6)	check_delivery()
	(7)	end if.
	(8) when BUNDLE(m, id , sigs) is received do
	(9)	if sigs contains valid signatures for (m, id ) not already ur-broadcast by pi then
	(10)	sigs i ← {all valid signatures for (m, id ) ur-broadcast by pi}
		∪ {all valid signatures for (m, id ) in sigs};
	(11)	ur_broadcast(BUNDLE(m, id , sigs i ));
	(12)	check_delivery()
	(13)	end if.
	(14) internal operation check_delivery() is
	(15)	if pi ur-broadcast at least q d valid signatures for (m, id )
		∧ (-, id ) not already k2 -delivered
	(16)	then k2 _deliver(m, id )
	(17)	end if.
	end object.

Note that this message adversary is not limited to algorithms that use the ur_broadcast macro-operation. The same adversary can be equivalently defined for an operation ur_multicast that sends a message to a dynamically defined subset of processes (be it multiple recipients or only one in the case of unicast), by stipulating that the MA can still suppress up to d copies of this message. In this case, the most robust way for correct processes to disseminate a message is to send it to all processes, i.e. to fall back on a ur_broadcast operation.

An example of this family is the binary reliable broadcast introduced in[START_REF] Mostéfaoui | Signature-free asynchronous byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF], which is defined by specific delivery properties-not including MA-tolerance-allowing binary consensus to be solved efficiently with the help of a common coin.

The liveness properties comprise a local delivery property that provides a necessary condition for the k2 -delivery of an app-message by at least one correct process, and two global delivery properties that consider the collective behavior of correct processes.

Because of the condition at line 9, these processes do not necessarily k2 -deliver (m, id ), but all do k2 -deliver an appmessage for identity id .

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

Acknowledgments

This work has been partially supported by the French ANR projects ByBloS (ANR-20-CE25-0002-01) and PriCLeSS (ANR-10-LABX-07-81) devoted to the design of modular distributed computing building blocks. i

A Proof of the Signature-Free k2 -cast Implementation (Algorithm 1)

A.1 Safety Proof Lemma 10. If a correct process p i k2 -delivers (m, id ), then at least (q f -n + c) correct processes have ur-broadcast ENDORSE(m,id ) at line 3.

Proof. If p i k2 -delivers (m, id ) at line 10, then it received q d copies of ENDORSE(m, id ) (because of the predicate at line 9). The effective number of Byzantine processes in the system is n -c, such that 0 ≤ n -c ≤ t. Therefore, p i must have received at least q d -n + c (which is strictly positive because q d ≥ q f > t ≥ n -c by sf-k2 -Assumption 1) messages ENDORSE(m, id ) that correct processes urbroadcast, either during a k2 _cast(m, id ) invocation at line 3, or during a forwarding step at line 7. There are two cases.

• If no correct process has forwarded ENDORSE(m, id ) at line 7, then at least q d -n+c ≥ q f -n+c (as q d ≥ q f by sf-k2 -Assumption 1) correct processes have ur-broadcast ENDORSE(m, id ) at line 3.

• If at least one correct process forwarded ENDORSE(m, id ), then let us consider p j , the first correct process that forwards ENDORSE(m, id ). Because of the predicate at line 6, p j must have received at least q f distinct copies of the ENDORSE(m, id ) message, out of which at most n -c have been ur-broadcast by Byzantine processes, and at least q f -n + c (which is strictly positive because q f > t ≥ n -c by sf-k2 -Assumption 1) have been sent by correct processes. Moreover, as p j is the first correct process that forwards ENDORSE(m, id ), all of the q f -n + c ENDORSE messages it receives from correct processes must have been sent at line 3.

Lemma 11 (k2 -VALIDITY). If a correct process p i k2 -delivers an app-message m with identity id , then at least k = q f -n + c correct processes have k2 -cast m with id .

Proof. The condition at line 2 implies that the correct processes that ur-broadcast ENDORSE(m, id ) at line 3 constitute a subset of those that k2 -cast (m, id ). Thus, by Lemma 10, their number is at least k = q f -n + c.

Lemma 12 (k2 -NO-DUPLICATION). A correct process p i k2 -delivers an app-message m with identity id at most once.

Proof. This property derives trivially from the predicate at line 9.

Lemma 13 (k2 -CONDITIONAL-NO-DUPLICITY).

) is true, then no two different correct processes k2 -deliver different app-messages with the same identity id .

Proof. Let p i and p j be two correct processes that respectively k2 -deliver (m, id ) and (m , id ). We want to prove that, if the predicate

) is satisfied, then m = m . There are two cases.

• Case q f > n+t 2 . We denote by A and B the sets of correct processes that have respectively ur-broadcast ENDORSE(m, id ) and ENDORSE(m , id ) at line 3. By Lemma 10, we know that |A| ≥ q f -n+c

Hence, at least one correct process p x has ur-broadcast both ENDORSE(m, id ) and ENDORSE(m , id ) at line 3. But because of the predicate at line 2, p x ur-broadcasts at most one message ENDORSE(-, id ) at line 3. We conclude that m is necessarily equal to m . Lemma 18 (MBRB-VALIDITY). 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.

Proof. If p i mbrb-delivers (m, sn, j) at line 1, then it k2 -delivered (READY(m), (sn, j)) using obj R . From k2 -VALIDITY, and as obj R .k = 1, we can assert that at least one correct process p x k2 -cast (READY(m), (sn, j)) at line 3, after having k2 -delivered (ECHO(m), (sn, j)) using obj E . Again, from k2 -VALIDITY, we can assert that at least obj E .k = 1 correct process p y k2 -cast (ECHO(m), (sn, j)) at line 2, after having received an INIT(m, sn) message from p j . And as p j is correct and the network channels are authenticated, then p j has ur-broadcast INIT(m, sn) at line 1, during a mbrb_broadcast(m, sn) invocation.

Lemma 19 (MBRB-NO-DUPLICATION).

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

Proof. By k2 -NO-DUPLICATION, we know that a correct process p i can k2 -deliver at most one READY(-) with identity (sn, j). Therefore, p i can mbrb-deliver only one app-message from p j with sequence number sn.

Lemma 20 (MBRB-NO-DUPLICITY). No two different correct processes mbrb-deliver different appmessages from a process p i with the same sequence number sn.

Proof. We proceed by contradiction. Let us consider two correct processes p w and p x that respectively mbrb-deliver (m, sn, i) and (m , sn, i) at line 4, such that m = m . It follows that p w and p x respectively k2 -delivered (READY(m), (sn, i)) and (READY(m ), (sn, i)) using obj R .

From k2 -VALIDITY, and as obj R .k ≥ 1, we can assert that two correct processes p y and p z respectively k2 -cast (READY(m), (sn, i)) and (READY(m ), (sn, i)) at line 3, after having respectively k2 -delivered (ECHO(m), (sn, i)) and (ECHO(m ), (sn, i)) using obj E . But as obj E .δ = true, then, by k2 -CONDITIONAL-NO-DUPLICITY, we know that m = m . There is a contradiction.

Lemma 21 (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.

Proof. If p i mbrb-broadcasts (m, sn) at line 1, then it invokes ur-broadcasts INIT(m, sn). By the definition of the MA, the message INIT(m, sn) is then received by at least c -d correct processes at line 2, which then k2 -cast (ECHO(m), sn, i). As p i is correct and ur-broadcasts only one message INIT(-, sn), then no correct process k2 -casts any different (ECHO(-), sn, i). Moreover, thanks to Lemma 16, we know that:

Hence, from k2 -LOCAL-DELIVERY and k2 -STRONG-GLOBAL-DELIVERY, at least obj

correct processes eventually k2 -deliver (ECHO(m), (sn, i)) using obj E and then k2 -cast (READY(m), (sn, i)) using obj R at line 3. By k2 -VALIDITY, and as obj R .k ≥ 1, then no correct process can k2 -cast a different (READY(-), (sn, i)), because otherwise it would mean that at least one correct process would have k2 -cast a different (ECHO(-), (sn, i)), which is impossible (see before). Moreover, thanks to Lemma 17, we know that:

Therefore, k2 -LOCAL-DELIVERY applies and we know that at least one correct processes eventually k2 -delivers (READY(m), (sn, i)) using obj R and then mbrb-delivers (m, sn, i) at line 4.

xviii Lemma 22 (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.

Proof. If p i mbrb-delivers (m, sn, j) at line 4, then it has k2 -delivered (READY(m), (sn, j)) using obj R . From k2 -VALIDITY, we know that at least obj R .k ≥ 1 correct process k2 -cast (READY(m), (sn, j)) using obj R at line 3 and thus k2 -delivered (ECHO(m), (sn, j)) using obj E . From k2 -CONDITIONAL-NO-DUPLICITY, and as obj E .δ = true, we can state that no correct process k2delivers any (ECHO(m ), (sn, j)) where m = m using obj E , so no correct process k2 -casts any (READY(m ), (sn, j)) where m = m using obj R at line 3. It means that k2 -STRONG-GLOBAL-DELIVERY applies, and we can assert that at least obj

processes eventually k2 -deliver (READY(m), (sn, j)) using obj R and thus mbrb-deliver (m, sn, j) at line 4.

B.2 Proof of MBRB with Imbs and Raynal's reconstructed algorithm (Algorithm 3) B.2.1 Instantiating the parameters of the k2 -cast object

In Alg. 3 (page 13), we instantiate the k2 -cast object obj W using the signature-free implementation presented in Section 3.2 with parameters q d = n+3t 2 + 3d + 1, q f = n+t 2 + 1, and single = false. Based on Theorem 1 (page 8), these parameters lead to the following values for k , k, and δ.

Finally, we observe that for Alg. This section proves that all the assumptions of the signature-free k2 -cast implementation presented in Alg. 1 (page 7) are well respected for the k2 -cast instance used in Alg. 3 (obj W ).

Lemma 23. Alg. 1's sf-k2 -Assumptions are well respected for obj W .

Proof. Let us recall that q f = n+t 2 + 1 and q d = n+3t 2 + 3d + 1 for object obj W .

• Proof of satisfaction of sf-k2 -Assumption 1 (c -d ≥ obj W .q d ≥ obj W .q f + t ≥ 2t + 1):

From IR16-Assumption (n > 5t + 12d + 2td t+2d ), we get that n > 5t + 8d, which yields:

(by definition of c)

We also have:

By combining ( 27) and ( 28), we obtain:

• Proof of satisfaction of sf-k2 -Assumption 2 (α 2 -4(obj W .q f -1)(n -t) ≥ 0):

Let us recall that for object obj W we have q f = n+t 2 +1 and q d = n+3t 2 +3d+1. We therefore have α = 3n-t 2 -d. Let us now consider the following quantity:

We now observe that m

We thus rewrite (29) as follows:

We now multiply by 4 and solve the inequality:

By IR16-Assumption we have n > 5t + 12d + 2td t+2d . To prove [START_REF] Santoro | Time is not a healer[END_REF], we therefore show that 5t + 12d + 2td t+2d ≥ 3t + 4

We observe that (31) holds as 144d 4 ≥ 64d 3 , 288td 3 ≥ 96td 2 , and 192t 2 d 2 ≥ 32t 2 d, therefore proving sf-k2 -Assumption 2.

• Proof of satisfaction of sf-k2 -Assumption 3 (α(obj W .q d -1)-(obj

Let us consider the quantity on the left-hand side of sf-k2 -Assumption 3 and substitute

xxi

We now observe that m 2 = m- 2 with = 0 if m = 2k is even, and = 1 if m = 2k + 1 is odd, and rewrite the expression accordingly:

As the coefficients of n are all positive, we can lower-bound the quantity using n > 5t + 12d + 2td t+2d :

which proves all previous inequalities and thus sf-k2 -Assumption 3.

• Proof of satisfaction of sf-k2 -Assumption 4 (α(obj

Let us consider the quantity on the left-hand side of sf-k2 -Assumption 4 and substitute

We now observe that m 2 = m- 2 with = 0 if m = 2k is even, and = 1 if m = 2k + 1 is xxii odd, and rewrite the expression accordingly:

As the coefficients of n are all positive, we can lower bound using n > 5t+12d+ 2td t+2d > 5t+12d to obtain:

which proves sf-k2 -Assumption 4.

B.2.3 Correctness proof

This section proves the following theorem:

Theorem 4 (MBRB-CORRECTNESS). If IR16-Assumption is verified, then Alg. 3 implements MBRB with the guarantee MBRB = c 1 -

.

The proof follows from the next lemmas.

Proof. This proof is presented in reverse order: we start with the result we want to prove and finish with a proposition we know to be true. In this manner, given two consecutive propositions, we only need that xxiii the latter implies the former and not necessarily the converse. We want to show that:

The left-hand side of the above inequality is a second-degree polynomial, whose roots we can solve:

We now need to show that:

By IR16-Assumption, we know that:

and thus that:

So we want to show that:

It is easy to see that the right-hand side of the above inequality is non-negative, so we get:

This concludes the proof.

xxiv Lemma 25 (MBRB-VALIDITY). 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.

Proof. If p i mbrb-delivers (m, sn, j) at line 1, then it k2 -delivered (WITNESS(m), (sn, j)) using obj W . From k2 -VALIDITY, and as obj R .k ≥ 1, we can assert that at least one correct process p i k2 -cast (WITNESS(m), (sn, j)) at line 2, after having received an INIT(m, sn) message from p j . And as p j is correct and the network channels are authenticated, then p j has ur-broadcast INIT(m, sn) at line 1, during a mbrb_broadcast(m, sn) invocation.

Lemma 26 (MBRB-NO-DUPLICATION). A correct process p i mbrb-delivers at most one app-message from a process p j with sequence number sn.

Proof. By k2 -NO-DUPLICATION, we know that a correct process p i can k2 -deliver at most one READY(-) with identity (sn, j). Therefore, p i can mbrb-deliver only one app-message from p j with sequence number sn.

Lemma 27 (MBRB-NO-DUPLICITY). No two distinct correct processes mbrb-deliver different appmessages from a process p i with the same sequence number sn.

Proof. As obj W .δ = true, then, by k2 -CONDITIONAL-NO-DUPLICITY, we know that no two correct processes can k2 -deliver two different app-messages with the same identity using obj W at line 3. Hence, no two correct processes mbrb-deliver different app-messages for a given sequence number sn and sender p i .

Lemma 28 (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.

Proof. If p i mbrb-broadcasts (m, sn) at line 1, then it invokes ur-broadcasts INIT(m, sn). By the definition of the MA, the message INIT(m, sn) is then received by at least c -d correct processes at line 2, which then k2 -cast (WITNESS(m), sn, i). But thanks to Lemma 24, we know that:

As p i is correct and ur-broadcasts only one message INIT(-, sn), then no correct process k2 -casts any different (WITNESS(-), sn, i), k2 -LOCAL-DELIVERY applies and at least one correct processes eventually k2 -delivers (WITNESS(m), (sn, i)) using obj W and thus mbrb-delivers (m, sn, i) at line 3.

Lemma 29 (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.

Proof. If p i mbrb-delivers (m, sn, j) at line 3, then it has k2 -delivered (WITNESS(m), (sn, j)) using obj W . As obj W .δ = true, we can assert from k2 -WEAK-GLOBAL-DELIVERY and k2 -CONDITIONAL-NO-DUPLICITY that at least obj W . = c 1 -d c-q d +1 correct processes eventually k2 -deliver (WITNESS(m), (sn, j)) using obj W and thus mbrb-deliver (m, sn, j) at line 3. By substituting the values of q f and q d , we obtain obj W . = c 1 - For the proofs provided in this section, let us remind that, given two sets A and B, we have |A ∩ B| = |A| + |B| -|A ∪ B|. Moreover, the number of correct processes c is superior or equal to n -t. Additionally, if A and B are both sets containing a majority of correct processes, we have |A ∪ B| ≤ c, which implies that |A ∩ B| ≥ |A| + |B| -c. Furthermore, let us remind the assumptions of Alg. 4:

C.1 Safety Proof

Lemma 30. If a correct process p i k2 -delivers (m, id ), then at least q d -n + c correct processes have signed (m, id ) at line 3.

Proof. If p i k2 -delivers (m, id ) at line 16, then it sent q d valid signatures for (m, id ) (because of the predicate at line 15). The effective number of Byzantine processes in the system is n -c, such that 0 ≤ n -c ≤ t. Therefore, p i must have sent at least q d -n + c (which, due to sb-k2 -Assumption 2, is strictly positive because q d > t ≥ n -c) valid distinct signatures for (m, id ) that correct processes made at line 3, during a k2 _cast(m, id ) invocation.

Lemma 31 (k2 -VALIDITY). If a correct process p i k2 -delivers an app-message m with identity id , then at least k = q d -n + c correct processes k2 -cast m with identity id .

Proof. The condition at line 2 implies that the correct processes that k2 -cast (m, id ) constitute a superset of those that signed (m, id ) at line 3. Thus, by Lemma 30, their number is at least k = q d -n+c.

Lemma 32 (k2 -NO-DUPLICATION). A correct process k2 -delivers at most one app-message m with identity id .

Proof. This property derives trivially from the predicate at line 15.

Lemma 33 (k2 -CONDITIONAL-NO-DUPLICITY). If the Boolean δ = q d > n+t 2 is true, then no two different correct processes k2 -deliver different app-messages with the same identity id .

Proof. Let p i and p j be two correct processes that respectively k2 -deliver (m, id ) and (m , id ). We want to prove that, if the predicate (q d > n+t

2 ) is satisfied, then m = m . Thanks to the predicate at line 15, we can assert that p i and p j must have respectively sent at least q d valid signatures for (m, id ) and (m , id ), made by two sets of processes, that we respectively denote A and B, such that |A| ≥ q d > n+t 2 and |B| ≥ q d > n+t 2 . We have |A ∩ B| > 2 n+t 2 -n = t. Hence, at least one correct process p x has signed both (m, id ) and (m , id ). But because of the predicates at lines 2, p x signed at most one couple (-, id ) during a k2 _cast(m, id ) invocation at line 3. We conclude that m is necessarily equal to m .

C.2 Liveness Proof

Lemma 34. All signatures made by correct processes at line 3 are eventually received by at least c -d correct processes at line 8.

Proof. Let {s 1 , s 2 , ...} be the set of all signatures for (m, id ) made by correct processes at line 3. We first show by induction that, for all z, at least c-d correct processes receive all signatures {s 1 , s 2 , ..., s z } at line 8.

Base case z = 0. As no correct process signed (m, id ), the proposition is trivially satisfied.

xxvi Induction. We suppose that the proposition is verified at z: signatures s 1 , s 2 , ..., s z are received by a set of at least c -d correct processes that we denote A. We now show that the proposition is verified at z + 1: at least c -d correct processes eventually receive all signatures s 1 , s 2 , ..., s z+1 .

The correct process that makes the signature s z+1 ur-broadcasts a BUNDLE(m, id , sigs) message (at line 5) where sigs contains s z+1 . From the definition of the MA, BUNDLE(m, id , sigs) is eventually received by a set of at least c -d correct processes that we denote B. We have |A ∩ B| = 2(c -d) -c = c -2d > 2d -2d = 0 (from sb-k2 -Assumption 1). Hence, at least one correct process p j eventually receives all signatures s 1 , s 2 , ..., s z+1 , and thereafter ur-broadcasts BUNDLE(m, id , sigs ) where {s 1 , s 2 , ..., s z+1 } ⊆ sigs . Again, from the definition of the MA, BUNDLE(m, id , sigs ) is eventually received by a set of at least c -d correct processes at line 8.

Lemma 35. If no correct process k2 -casts (m, id ) at line 1, then no correct process k2 -delivers (m, id ) at line 16.

Proof. Looking for a contradiction, let us suppose that a correct process p i k2 -delivers (m, id ) while no correct process k2 -cast (m, id ). Because of the condition at line 15, p i must have ur-broadcast at least q d valid signatures for (m, id ), out of which at most t are made by Byzantine processes. As q d > t (sb-k2 -Assumption 2), we know that q d -t > 0. Hence, at least one correct process must have k2 -cast (m, id ). Contradiction.

Lemma 36 (k2 -LOCAL-DELIVERY). If at least k = q d correct processes k2 -cast an app-message m with identity id and no correct process k2 -casts an app-message m = m with identity id , then at least one correct process p i k2 -delivers the app-message m with identity id .

Proof. As no correct process k2 -casts an app-message m = m with identity id , then Lemma 35 holds, and no correct process can k2 -deliver (m , id ) where m = m. Moreover, no correct process can sign (m , id ) where m = m at line 3, and thus all k = q d correct processes that invoke k2 _cast(m, id ) at line 1 also pass the condition at line 2, and then sign (m, id ) at line 3. From Lemma 34, we can assert that all q d signatures are received at line 8 by a set of at least c -d correct processes, that we denote A. Let us consider p j , one of the processes of A. There are two cases:

• If p j passes the condition at line 9, then it sends all q d signatures at line 11, then invokes check_delivery() at line 12, passes the condition at line 15 (if it was not already done before) and k2 -delivers (m, id ) at line 16;

• If p j does not pass the condition at line 9, then it means that it has already sent all q d signatures before, whether it be at line 5 or 11, but after that, it necessarily invoked check_delivery() (at line 6 or 12, respectively), passed the condition at line 15 (if it was not already done before) and k2 -delivered (m, id ) at line 16.

Lemma 37 (k2 -WEAK-GLOBAL-DELIVERY). If a correct process k2 -delivers an app-message m with identity id , then at least = c -d correct processes k2 -deliver an app-message m with identity id (each of them possibly different from m).

Proof. If p i k2 -delivers (m, id ) at line 16, then it has necessarily ur-broadcast the BUNDLE(m, id , sigs) message containing the q d valid signatures before, whether it be at line 5 or 11. From the definition of the MA, a set of at least c -d correct processes, that we denote A, eventually receives this BUNDLE(m, id , sigs) message at line 8. If some processes of A do not pass the condition at line 9 upon receiving this BUNDLE(m, id , sigs) message, it means that they already ur-broadcast all signatures of sigs. Thus, in every scenario, all processes of A eventually ur-broadcast all signatures of sigs at line 5 or 11. After that, all processes of A necessarily invoke the check_delivery() operation at line 6 or 12, respectively, and then evaluate the condition at line 15. Hence, all correct processes of A, which are at