Optimistic Message Dissemination

Our constructions are built in a black-box manner from existing flooding protocols, and impose no additional assumptions on the fraction of honest parties beyond what these underlying protocols require. Additionally, we assume that all parties have access to a PKI infrastructure and access to a randomness beacon, both of which are readily available in most blockchain systems. As our protocols rely on splitting messages into multiple shares and on cryptographic techniques to guarantee the validity of these shares, our constructions are not suitable for disseminating very short messages. Hence, the protocols are better suited for disseminating blocks than individual transactions.

We assume a synchronous network with point-to-point channels between all parties. The protocol as we describe it requires this synchrony (i.e., knowledge of an upper bound on the delivery time of the point-to-point channels) to guarantee that all honest parties receive all messages in the worst case. The protocol can be slightly modified to guarantee delivery to all honest parties in all cases without synchrony, and only require synchrony to achieve better efficiency in the optimistic case at the expense of slightly more communication in the optimistic case. The protocol can thus be adapted to best suit the synchrony assumption and delivery requirements of the application it is used in.

As a first step, we present a simple protocol PushPullFlood that achieves asymptotically optimal per-party communication (but is not optimistic). Instead of only “pushing” messages to all parties, it additionally allows parties to “pull” messages from other parties that have already received the message. We will use this mechanism also in our optimistic protocol.

By instantiating ${\mathrm{\Pi }}_{\text{Flood}}$ and ${\mathrm{\Pi }}_{\text{FracFlood}}$ with appropriate protocols from [24] and [25] respectively, it follows that PushPullFlood can provide flooding with asymptotically optimal per-party communication.

We then strengthen the result above and present the first flooding protocol OptimisticFlood that is asymptotically-optimal in the worst-case, but also has improved efficiency in the optimistic case.

Below we use ${\gamma }_{\text{Actual}}$ to quantify the actual fraction of parties behaving honestly and state an informal version of the theorem we show for OptimisticFlood.

A natural choice is to let both ${\mathrm{\Pi }}_{\text{BC}}$ and ${\mathrm{\Pi }}_{\text{wc}}$ be instantiated with asymptotically optimal flooding protocols with a per-party communication complexity of $O(l\cdot {\gamma }^{-1})$ such as the one from [25] (where it was also shown that this is a lower bound). By instantiating the corresponding honesty-fraction parameters for the best case to be close to $1$, e.g., ${\gamma }_{\text{bc}}=0.95$, our protocol shaves off almost a factor of ${\gamma }_{\text{wc}}^{-1}$ from the communication complexity in the optimistic case. In particular, if ${\gamma }_{\text{wc}}=0.5$, it cuts the per-party communication complexity almost in half in the optimistic case compared to using only the worst-case protocol.

Further note that one can also instantiate the optimistic good-case protocol with protocols that do not provide any guarantees for the safety of the overall protocol to be guaranteed. In particular, this means that algorithms not designed for Byzantine adversaries aiming to build for example minimum spanning trees such as the Plumtree algorithm [22] (as used in Ethereum [35]) may be used optimistically while still having provable worst-case fallback guarantees if the network is under attack.

At a high level, the protocol PushPullFlood works by first “pushing” a message to a large fraction of the parties and then allowing the remaining parties that may not have received the message to “pull” the message from those that have received it, similarly to the seminal work of [10]. The protocol is build modularly by being parametric in two sub protocols: 1) a flooding protocol that must ensure to push a small notification to all parties and 2) a fractional flooding protocol that must guarantee to push the message to at least a constant fraction of the honest parties. Combining these, our construction relies on three key techniques to ensure the efficiency of the pull phase:

1. 1.

   We use a verifiable random function (VRF) to let a party prove that they are allowed to pull the message from another party, similar to [7]. That is, the pulling party will evaluate the VRF to obtain a seed and use this seed to select whom they will pull from. A party receiving such pull requests will then verify that this seed indeed was the output of the VRF to confirm the validity of the pull request. Thereby, we ensure that honest parties do not need to answer an excessive amount of malicious pull requests while still ensuring that all honest pull requests will be answered. To prevent malicious parties from choosing their VRF keys in such a way that many of them can pull from the same honest party, the VRF is evaluated on an unpredictable value obtained from a randomness beacon, which is assumed to be available to all parties.

2. 2.

   We split the message into multiple shares using erasure correcting codes while ensuring that a constant fraction of these is sufficient to reconstruct the message, similar to [25]. By letting the answer to a pull request be such individual share, we ensure that honest parties can send sufficiently many pull requests to be certain to talk to a fraction of parties answering such pull request honestly, without allowing an adversary to exploit this to induce excessive communication.

3. 3.

   We accompany such shares with membership proofs for a cryptographic accumulator similar to [25]. This ensures that honest parties are able to recognize which shares belong together, allowing honest parties to reconstruct efficiently.

Together, these techniques ensure that the per-party communication complexity of the pulling phase is asymptotically optimal and thereby improves the efficiency of previous protocols with a similar design. Note that while a certain message length is required for the protocol to be asymptotically optimal, the usage of erasure correcting codes and cryptographic accumulators was demonstrated to be concretely advantageous in terms of per-party communication complexity for a push-based protocol with messages of a length as small as 2 kilobytes in [25]. In addition to the cryptographic overhead, it must make sense to first send a small notification instead of the full message, so messages should be substantially larger than such a notification. Overall, the protocol is well suited for disseminating blocks in a blockchain system, where each block contains many transactions.

While the idea of using a push-pull based approach is not new [10, 22], to the best of the authors knowledge, this is the first time a provably secure construction with a formal security proof is presented. Additionally, it is the first time erasure correcting codes are used to obtain asymptotically optimal communication complexity in a protocol utilizing pulling.

We present the first optimistic flooding protocol OptimisticFlood. The protocol is also build modularly and takes two protocols as parameters: 1) A flooding protocol used for the optimistic case and 2) a flooding protocol guaranteed to work even in the worst-case. Using these two, the protocol runs in three phases:

Phase 1:

The message is sent using the optimistic case flooding protocol.

Phase 2:

The sender estimates whether the message has been received by sufficiently many honest parties by asking a committee of parties whether they have received it.

Phase 3:

Depending on the conclusion of Phase 2, one of the following steps is taken:

• $\mathrm{■}$

  If it is concluded that sufficiently many honest parties have received the message, any party that did not receive it is allowed to pull the message from some random peers.

• $\mathrm{■}$

  Otherwise, the sender defaults back to sending the message using the worst-case protocol.

If the protocol is executed in a setting fulfilling the optimistic conditions, then the optimistic case protocol ensures delivery to all honest parties and we set the parameters such that the adversary cannot force defaulting back to the worst-case protocol. Hence, the adversary can only induce additional complexity by pulling, which is ensured to be minimal using the same techniques as for the pull-phase of PushPullFlood.

On the other hand, if the protocol is executed in a setting not fulfilling the optimistic conditions, we do not obtain any guarantees from the optimistic case flooding protocol about how many parties receive the message. This is not a problem if the sender in Phase 3 defaults back to the worst-case protocol. However, an adversary may try to convince the sender that the optimistic protocol succeeded even though it did not. We solve this by carefully tweaking the parameters of the protocol to ensure that if the sender concludes that the protocol succeeded, then it is guaranteed that at least a fraction of the honest parties have received the message. By setting the parameters of the erasure correcting codes correspondingly, we ensure that the remaining honest parties receive the message when pulling.

The work of Abraham, Nayak, Ren and Xiang [2] considers Byzantine fault-tolerant broadcast and optimizes the good-case latency, measured as the number of rounds for all honest parties to commit when the designated broadcaster is honest.

Another traditional line of work investigates protocols that have a number of rounds proportional to the actual number of corruptions $f$, rather than a known upper bound on the number of corruptions $t$. In this case, it is known that deterministic broadcast solutions have $\min \{f+2,t+1\}$ rounds of communication [14, 13]. A long line of works focused on feasibility results, including protocols without setup [12, 33, 36, 3, 13, 5, 18, 1], or protocols with a setup for cryptographic (pseudo-)signatures [31, 27, 9]. A different line of work optimizes the delay of each round (rather than the number of rounds), by making progress as fast as the actual network delay in an optimistic case when the number of corruptions is small [30, 23].

The work [6] considered protocols with optimistic communication $O(nf)$ for byzantine agreement, improving upon traditional protocols that achieved $O(nt)$ communication.

Let $𝙷:{\{0,1\}}^{\ast }\to {\{0,1\}}^{\kappa }$ denote a collision-resistant hash-function and let $\{\{a,a,b\}\}$ denote a multiset containing the elements $a,a$, and $b$. In Table 1, we summarize the notation used in this paper. Note that several symbols are used in the context of our protocols and their meaning will become clear later.

We use a property-based definition of flooding as it was shown in [25] that security w.r.t. this definition implies a secure implementation of the flooding functionality in the UC framework [4]. However, unlike previous property based definitions, we include the fraction of parties that must remain honest for the delivery guarantee to apply in the definition. This allows us to capture optimistic protocols that perform better when the actual fraction of honest parties is high.

Additionally, we define the key metric for flooding networks most relevant for this paper namely per-party communication complexity.

Note that the delivery time parameter $\mathrm{\Delta }$ is a crucial metric for flooding protocols. To keep the per-party communication asymptotically optimal and in particular independent of the number of parties $n$, the delivery time must grow at least logarithmically with $n$. Our protocols, however, introduce only a small constant overhead beyond the latency of the underlying protocols we use in a black-box manner.

In our constructions, we will use a VRF to prevent corrupt parties creating excess network traffic. Below, we define an abstraction of VRF as a pair of two algorithms with the standard properties defined in [19].

For simplicity, we will assume all these properties to hold throughout all our executions and disregard the negligible probability that they do not hold. Note that there exist several simple implementation of such a VRF [19].

Our protocols will make use of erasure correcting codes. Below, we recap the definition given in [25].

We will use the notation $\zeta .\mathrm{𝚂𝚑𝚊𝚛𝚎𝚂𝚒𝚣𝚎}(l)$ for a function that bounds the size of each share when a message of length $l$ is encoded.

Note that we here assume the algorithms to be deterministic, which we will exploit in our constructions. While this is not the case for all erasure correcting codes, e.g., Reed-Solomon codes [32] are deterministic. Using Reed-Solomon codes with the same encoding of messages as in [25], we obtain $\zeta .\mathrm{𝚂𝚑𝚊𝚛𝚎𝚂𝚒𝚣𝚎}(l)=O\left(\frac{l}{\mu -\tau }\right)$.

In our protocols, we will make use of a weak form of cryptographic accumulators. Below we recap the definition from [25].

We use the notation $\alpha .\mathrm{𝙰𝚌𝚌𝚂𝚒𝚣𝚎}$ for a bound on the size of the accumulated value and $\alpha .\mathrm{𝙿𝚛𝚘𝚘𝚏𝚂𝚒𝚣𝚎}(\lambda )$ for a function that bounds the size of each proof as a function of the number of messages accumulated $\lambda$.

Note that we here assume deterministic accumulators. Similarly to erasure correcting codes, this is needed for our constructions. One can use Merkle trees [29] to instantiate such a WSCAS, where the accumulated value is the root of the Merkle tree and the proofs are the Merkle proofs for each message. This yields an efficient deterministic scheme with

Consider an honest party $p$ that has not received $(\text{AcceptPull},m)$ as input. We introduce indicator random variables $X_1,\mathrm{\dots },X_{\mu }$ where $X_j$ indicates whether the $j$’th party from which $p$ requests a share is honest and has already received $(\text{AcceptPull},m)$ before time $t$. Since we assume both the erasure correcting code as well as the weak cryptographic accumulator to be deterministic, that party will in this case have generated the same shares and accumulator proofs as other parties. Therefore, $p$ will in this case have received share $j$ and a valid proof by time $t+2\cdot {\mathrm{\Delta }}_{\text{Channel}}$. Further, note that if $p$ has received at least $\mu -\tau$ valid shares by time $t+2\cdot {\mathrm{\Delta }}_{\text{Channel}}$, then $p$ is able to reconstruct the original message timely by the correctness property of the ECCS and the unforgeability of the WSCAS. Therefore, by the assumption that

we have

Parties sample the $\mu$ neighbors with replacement using a random seed $r$ obtained from the VRF given the message hash and a fresh value from the randomness beacon. Since we assume the randomness beacon produces unpredictable values, independent from the VRF keys, the $X_j$ are computationally indistinguishable from independent and identically distributed values. We further note that, up to some negligible distinguishing advantage, the expected value of any $X_j$ is given by $\text{E}[X_j]=\beta$, and there Chernoff implies

Noting that there are at most ${\gamma }_{\text{Actual}}\cdot n$ such parties and using a union-bound together with Equation 3, we get the desired bound

$◀$

Let us now analyze the communication complexity of the pulling protocol. We first concentrate on the communication complexity induced for a party to pull a message. For each party pulling, there will be $\mu$ pulling requests. The pulling requests will each consist of:

1. 1.

   A tag Pull of size $O(1)$,

2. 2.

   the random seed from the VRF to determine whom to pull from of size $O(\kappa )$,

3. 3.

   the proof that this seed has been correctly calculated of size $O(\kappa )$,

4. 4.

   the hash of the message of size $O(\kappa )$,

5. 5.

   and the index of the requested share of size $O\left(\log (\mu )\right)$.

Therefore, each such pull request will have size

and the total communication complexity for such pulling party will be

Next, let us analyze the communication complexity of responding to such valid²²2That is, a pull request where the attached VRF-proof proofs that the share should actually be requested from this specific party. pull requests. A response to such pulling request will consist of:

1. 1.

   A tag Share of size $O(1)$,

2. 2.

   a share of size $\zeta .\mathrm{𝚂𝚑𝚊𝚛𝚎𝚂𝚒𝚣𝚎}(l)$,

3. 3.

   the accumulated value of all shares and indexes with size $\alpha .\mathrm{𝙰𝚌𝚌𝚂𝚒𝚣𝚎}$,

4. 4.

   and the proof that the share is a part of the accumulator with size $\alpha .\mathrm{𝙿𝚛𝚘𝚘𝚏𝚂𝚒𝚣𝚎}(\mu )$.

Therefore, each such response will have size

The total communication complexity for a party having accepted pulls, will therefore be what is given in Equation 8 multiplied with the number of such valid pull requests the party receives.

By the pseudorandomness property of the VRF, a verifying pull requests can only be established by letting the party knowing their secret key evaluate the VRF.³³3To see that this follows from the pseudorandomness, consider for the sake of contradiction an adversary with a non-negligible probability of evaluating a VRF without knowing a corresponding secret key. This can be used to distinguish an output of the VRF from a uniformly random value non-negligibly by using the adversary capable of evaluating such VRF with a non-negligible probability and if the output matches the challenge, guess that it was produced by the VRF. To upper bound the per-party communication complexity let $\eta$ be an upper bound on the number of secret keys that are used to evaluate the VRF for a particular message. Each VRF evaluation gives rise to $\mu$ pull requests. The outputs of each such evaluation from a secret key is guaranteed to be unique by the full uniqueness property which ensures that there are therefore at most $\eta \cdot \mu$ valid pull requests in total for a particular message.

For a particular party $p$, we introduce an indicator random variable $X_i$ for each of the pull requests $i\in \{1,\mathrm{\dots }\eta \cdot \mu \}$ where $X_i=1$ if and only if the $i$’th of these potential pull requests targets $p$ as a valid receiver of the pull request. As the target of a valid pull request is drawn uniformly at random among all parties (up to some negligible distance by the pseudorandomness property of the VRF and the definition of the protocol), we have for any $X_i$ that the expected value is $\text{E}[X_i]=n^{-1}$ and therefore $\text{E}\left[{\sum }_{i=1}^{\eta \cdot n\cdot \mu }{X}_i\right]=\eta \cdot \mu \cdot n^{-1}$. Further, because the sampling is done with replacement, we have as in the proof of Lemma 11 that the values $X_i$ are indistinguishable from independent and identically distributed random variables. We can thus apply the Chernoff bound to obtain (up to negligible distance) for any $\delta \in [0,1]$

Further, using the union bound, we can bound the probability that any party receives more pull requests than what we used in the bound above:

Letting $\delta$ be constant, we note that the probability that any party receives more than $O\left(\eta \cdot \mu \cdot n^{-1}\right)$ valid pull requests is negligible in $\kappa$ when $\mu \ge 3\cdot n\cdot (\log (n)+\kappa )\cdot {({\delta }^2\cdot \eta )}^{-1}$. Hence, the per-party communication complexity for a party accepting pull requests with these parameters will be

We here introduce a weakened version of the $(\gamma ,\mathrm{\Delta })$-delivery guarantee, namely a version where it is not required that a message is delivered to all parties, but rather only to a fraction of the parties. The idea is that we will use a protocol with this weaker delivery guarantee to spread out messages to a large fraction of the parties before the pulling phase is initiated. We dub this weakened property fractional delivery and define it formally below.

Sometimes, we will refer to a flooding protocol with this property as a fractional flooding protocol.

The idea of not delivering messages to all parties was also considered in [7].⁴⁴4In particular, the $F_{\text{sync}}$ functionality of [7, p. 7] allows a fraction of the parties to be eclipsed in which case the delivery guarantees will not apply. However, their work builds a custom consensus protocol on top of the weaker message dissemination functionality. In contrast, our work uses the weaker property as a step towards building a flooding protocol that ensures message delivery to all parties.

We now present our flooding protocol that works by first making the parties push out a notification for that a message is about to arrive (the hash of the message) and push out the actual message using a fractional flooding protocol. Afterwards, all parties are allowed to pull for the message if they did not receive the message that they were notified about.

Below, we state and prove the security of PushPullFlood.

Assume there are at least ${\gamma }_{\text{wc}}\cdot n$ honest parties and let $m$ be a message input to some honest party at time $t$. We let

• $\mathrm{■}$

  $A$ be the event that all honest parties have received $m$ by time ${\mathrm{\Delta }}_{\text{Flood}}+{\mathrm{\Delta }}_{\text{FracFlood}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}$,

• $\mathrm{■}$

  $B$ be the event that all honest parties have received $𝙷(m)$ by time $t+{\mathrm{\Delta }}_{\text{Flood}}$,

• $\mathrm{■}$

  and let $C$ be the event that at least a $\beta$ fraction of the honest parties have received $m$ by time $t+{\mathrm{\Delta }}_{\text{FracFlood}}$.

By the law of total probability and the assumptions on ${\mathrm{\Pi }}_{\text{Flood}}$ and ${\mathrm{\Pi }}_{\text{FracFlood}}$, we have that

Further, as $\mathrm{Pr}[A\mid B\cap C]=1-\mathrm{Pr}[\neg A\mid B\cap C]$, it is sufficient to prove that $\mathrm{Pr}[\neg A\mid B\cap C]\le \mathrm{negl}(\kappa )$. Note that $C$ ensures that a $\beta$ fraction of the honest parties, i.e., at least a fraction ${\beta }^{\prime }≔\beta \cdot {\gamma }_{\text{wc}}$, has received $m$ in the protocol ${\mathrm{\Pi }}_{\text{FracFlood}}$ by time $t+{\mathrm{\Delta }}_{\text{FracFlood}}$, and thus has input $(\text{AcceptPull},m)$ to $\text{Pull}(\zeta ,\alpha )$ by then. Further note that $B$ ensures that by time $t+{\mathrm{\Delta }}_{\text{Flood}}+{\mathrm{\Delta }}_{\text{FracFlood}}$, all honest parties either have received $m$ or have input $(\text{Pull},𝙷(m))$ to $\text{Pull}(\zeta ,\alpha )$. Finally note that we have $\tau \ge \mu \cdot (1-(1-\delta )\cdot {\beta }^{\prime })$ by assumption. Hence, the preconditions for Lemma 11 are fulfilled, which gives us that:

$◀$

In the full version [26], we show that the per-party communication complexity of PushPullFlood is bounded by

This implies that the protocol is asymptotically optimal for messages of length $l=\tilde{\mathrm{\Omega }}({\kappa }^2\cdot {(\beta \cdot {\gamma }_{\text{wc}})}^{-1})$ for appropriate instantiations of the underlying protocols.

Our protocol is parameterized by two flooding protocols: 1) a best-case flooding protocol that only works if some best-case conditions are fulfilled, 2) a worst-case flooding protocol that is ensured to work in all remaining cases. The best-case conditions will be that at least a fraction ${\gamma }_{\text{bc}}$ of the parties remain honest throughout the execution.

A first skeleton of an optimistic flooding protocol relying on two such existing flooding protocols could look like the following:

1. 1.

   Run a best-case protocol to disseminate the actual message.

2. 2.

   Check if the best-case protocol succeeds. If not, default to sending the entire message using the worst-case protocol.

While the skeleton reads fairly straightforward, it is easier said than done to reliably detect if the best-case protocol fails while still tolerating a small fraction of corrupted parties. Because flooding protocols only ensure the delivery of the message when the initial sender is honest, a first step towards this could be to let the initial sender ask all parties if they have received the message. We refer to a party reporting that they have not received the message as a complaint. Based on the answers given by the parties, a decision must be taken on whether we default back to use the worst-case flooding protocol and use this to send the entire message. The decision procedure and the following actions should account for the following two cases depending on the actual fraction of parties being honest ${\gamma }_{\text{Actual}}$:

${\gamma }_{\text{bc}}\le {\gamma }_{\text{Actual}}$:

In this case, the best-case protocol is guaranteed to deliver the message to all honest parties and therefore the worst-case protocol should not be executed, independently of the actions of the malicious parties. In particular, these up to $n\cdot (1-{\gamma }_{\text{bc}})$ malicious parties may complain about not having received the message even though they have.

:

In this case, we have no guarantees from the best-case flooding protocol about how many parties have received the message and the adversary can choose this arbitrarily (by delivering the message to specific parties). In particular, it may be that the adversary does not deliver the message to $n\cdot (1-{\gamma }_{\text{bc}})$ parties.

Note that from the sender’s point of view, it will be impossible to distinguish which of the two above cases they are in as an adversary can make the views appear exactly the same for the sender. So how do we ensure that $n\cdot (1-{\gamma }_{\text{bc}})$ parties cannot force the execution of the worst-case protocol in the first case while ensuring that all honest parties receive the message in the second case?

To balance this we introduce a subsequent pull-phase in case we decide that the best-case protocol “succeeded” allowing parties not having received the message to pull similar to the pull-phase from the protocol PushPullFlood presented in Section 3. That is, instead of requiring that no honest party complains to conclude a success, we only require that not more than a fraction of the parties complain in order to conclude that the best-case protocol succeeded. Concretely, we introduce a threshold $T$ for how many complaints we will accept and still conclude that the best-case protocol “succeeded”. We will set this threshold such that $(1-{\gamma }_{\text{bc}})\cdot n$ parties cannot produce enough complaints to conclude that the protocol failed if it did not, but still it should ensure that a sufficient fraction of the honest parties have received the message to ensure that pull requests will be responded to appropriately. Thereby, we can use the protocol Pull without prohibitively high communication.

What is left is only to combat the impracticality of letting the sender ask all parties. We do this by letting the sender sample a subset of the parties and ask this subset of parties about whether or not they have received the message. This allows the sender to statistically conclude whether or not the best-case protocol succeeded.

Below, we present our protocol for optimistic flooding.

Note that for the provably secure protocols, we often have ${\mathrm{\Delta }}_{\text{BC}},{\mathrm{\Delta }}_{\text{WC}}=O\left(\log (n)\cdot {\mathrm{\Delta }}_{\text{Channel}}\right)$. Hence, the direct communication steps that happen using a channel are comparatively “cheap” time-wise.

It is also worth noting that instead of using just two different flooding protocols, one could consider using three different protocols. A natural example of this would be to use one worst-case protocol for short messages (notifications), one worst-case protocol for long-messages, and one best-case protocol for long messages.

The described version of the protocol requires a synchrony assumption on the channels for safety (i.e., guaranteeing message delivery) in the worst case to ensure that sufficiently many complaints reach the sender in time. In the optimistic case, it does not require synchrony. However, if we instead changed the protocol to require a certain number of “confirmations” from parties having received the message instead of complaints, the protocol would achieve safety without relying on synchrony. On the other, it would still only achieve the best-case communication complexity under synchronous conditions and require slightly more communication in the optimistic case to send the confirmations. This allows fine-tuning the protocol for the specific settings it is deployed in.

We note that because the entire message is immediately input to ${\mathrm{\Pi }}_{\text{bc}}$, the delivery guarantees for ${\mathrm{\Pi }}_{\text{bc}}$ directly apply and hence $\text{OptimisticFlood}({\mathrm{\Pi }}_{\text{bc}},{\mathrm{\Pi }}_{\text{wc}},c,T,\zeta ,\alpha )$ has $({\gamma }_{\text{bc}},{\mathrm{\Delta }}_{\text{BC}})$-delivery.

We now bound the probability that Item 3a is activated for an honest sender. Let the time that the honest sender sends a message $m$ be denoted $t_{\text{Init}}$ and note that by the above, all honest parties have received the message at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}$. Hence, no honest party will send back $(\text{Complaint},𝙷(m))$ to the sender. It is therefore sufficient to show that the number of corrupted parties in the committee is at most $T$ with overwhelming probability.

To do so, we let $X_1,\mathrm{\dots },X_c$ denote indicator variables s.t. $X_i=1$ if and only if party $p_i$ of the committee $C$ in Item 2 is corrupted and note that for the actual number of complaints $k$, it holds that ${\sum }_{i=1}^c{X}_i\ge k$. Further, note that

and that the variables are identically and independently distributed as the honest sender samples the committee at random with repetition. Hence, using the Chernoff bound, we conclude that

Therefore, by Item 2, we have $\mathrm{Pr}\left[k>T\right]\le e^{-\frac{{\delta }^2\cdot (1-{\gamma }_{\text{bc}})\cdot c}{3}}$. $◀$

Next, we state that when the parameters of the protocol are instantiated carefully, then the protocol also ensures delivery assuming just the worst-case bound on the number of honest parties. It is worth noting that the theorem only makes assumptions about the worst-case protocol. Hence, message delivery is ensured independently of which best-case protocol is deployed. In particular, this allows to use protocols that based on for example heuristics about practice.

The intuition for $\beta$ is that it corresponds to a threshold for the fraction of parties that are honest and must have had the message delivered in case the sender does not receive sufficiently many complaints to default back to the worst-case protocol.

Let $s$ be an honest sender that sends a message $m$ at time $t_{\text{Init}}$. Further, let $\theta \in [0,{\gamma }_{\text{Actual}}]$ be the fraction of parties that are honest and have received the message $m$ at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}$. Because we have no guarantees about how the best-case protocol performs assuming only ${\gamma }_{\text{Actual}}\ge {\gamma }_{\text{wc}}$, we have no guarantees about the value of $\theta$. Instead, we make a case distinction whether $\theta >\beta$ or not:

$𝜽\mathbf{>}𝜷$:

For this case, we again make a case distinction based upon whether or not the actual number of complaints collected by the sender $k$ is above the threshold $T$:

$𝒌\mathbf{>}𝑻$:

In this case the sender will enter Item 3a at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}$ and flood the entire message using the worst-case protocol ${\mathrm{\Pi }}_{\text{wc}}$. Hence, by Item 1, it is guaranteed that with overwhelming probability, all parties have learned the message at the latest at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}+{\mathrm{\Delta }}_{\text{WC}}$.

$𝒌\mathbf{\le }𝑻$:

In this case the sender enters Item 3b at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}$. Hence, the delivery guarantees of the worst-case flooding protocol ${\mathrm{\Pi }}_{\text{wc}}$ ensures that with overwhelming probability, all parties will have received $(\text{PullPhaseBegun},𝙷(m))$ before time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}+{\mathrm{\Delta }}_{\text{WC}}$. Now, this implies that more than $\beta \cdot n$ parties are honest and have input $(\text{AcceptPull},𝙷(m))$ to $\text{Pull}(\zeta ,\alpha )$ by this time. Furthermore, it is guaranteed that all remaining honest parties will have input $(\text{Pull},𝙷(m))$ before time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}+2\cdot {\mathrm{\Delta }}_{\text{WC}}$. Additionally, Items 5 and 6 ensure that the final precondition for Lemma 11 is fulfilled. Hence, using Item 3, the probability that at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+4\cdot {\mathrm{\Delta }}_{\text{Channel}}+2\cdot {\mathrm{\Delta }}_{\text{WC}}$, there is some party who has not received the message is less than

$${\gamma }_{\text{Actual}}\cdot n\cdot e^{-\frac{{\delta }_2^2\cdot \mu \cdot \beta }{2}}\le n\cdot e^{-\frac{{\delta }_2^2\cdot \mu \cdot \beta }{2}}\le n\cdot e^{-\frac{\log (n)+\kappa }{2}}\le \mathrm{negl}(\kappa ).$$

(17)

$𝜽\mathbf{\le }𝜷$:

First, note (similarly to the previous case) that if for the actual number of complaints $k$ it holds that $k>T$, then the sender enters Item 3a in which case the probability that all parties have received the message at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+2\cdot {\mathrm{\Delta }}_{\text{Channel}}+{\mathrm{\Delta }}_{\text{WC}}$ is overwhelming in the security parameter (by Item 1). Therefore, it is sufficient to show that the probability that $k\le T$ is negligible in the security parameter. To show this, let $X_1,\mathrm{\dots },X_c$ be indicator variables s.t. $X_i$ indicates if the committee member $i$ is honest and has not received the message by time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}$. Now, note that any honest party that is part of the committee and has not received the message by time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}$ will send $(\text{Complaint},𝙷(m))$ at latest at time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+{\mathrm{\Delta }}_{\text{Channel}}$, which means that the sender will receive it at most ${\mathrm{\Delta }}_{\text{Channel}}$ time later. Hence, we have that ${\sum }_{i=1}^c{X}_i\le k$. By Item 2, it is therefore to sufficient to show that

$$\mathrm{Pr}\left[\sum _{i=1}^c{X}_i\le (1-{\delta }_1)\cdot ({\gamma }_{\text{wc}}-\beta )\cdot c\right]\le \mathrm{negl}(\kappa ).$$

(18)

Now note that for any $i$

$$\mathrm{Pr}[X_i=1]={\gamma }_{\text{Actual}}-\theta \ge {\gamma }_{\text{wc}}-\theta \ge {\gamma }_{\text{wc}}-\beta .$$

(19)

Hence, we have $\text{E}\left[{\sum }_{i=1}^c{X}_i\right]\ge ({\gamma }_{\text{wc}}-\beta )\cdot c.$ Further, because the sampling of the committee is done with replacement, we can apply the Chernoff bound, which when using $c\ge \frac{\kappa }{{\delta }_1^2\cdot ({\gamma }_{\text{wc}}-\beta )}$ (Item 4) gives us:

$$\mathrm{Pr}\left[\sum _{i=1}^c{X}_i\le (1-{\delta }_1)\cdot ({\gamma }_{\text{wc}}-\beta )\cdot c\right]\le e^{-\frac{{\delta }_1^2\cdot ({\gamma }_{\text{wc}}-\beta )\cdot c}{2}}\le e^{-\frac{\kappa }{2}}\le \mathrm{negl}(\kappa ).$$

(20)

Hence, the total failure probability will be bounded by the three negligible probabilities from above. Therefore, with overwhelming probability all parties will have received the message before time $t_{\text{Init}}+{\mathrm{\Delta }}_{\text{BC}}+4\cdot {\mathrm{\Delta }}_{\text{Channel}}+2\cdot {\mathrm{\Delta }}_{\text{WC}}$. $◀$ Finally, combining Lemmas 14 and 15, we can conclude that for suitable parameters the protocol OptimisticFlood performs well in both the best-case and the worst-case.

Finally, we state the per-party communication of OptimisticFlood. Due to space constraints we postpone the analysis to the full version [26].

For the best-case, we emphasize that there is only an asymptotic overhead compared to running only the best-case protocol that is directly linear in the message length for messages of length $l=\tilde{\mathrm{\Omega }}({\kappa }^2\cdot {\gamma }_{\text{wc}}^{-1})$. Hence, as noticed in Section 1.2, this allows the protocol to shave off a factor of ${\gamma }_{\text{wc}}$ when instantiated with asymptotically optimal flooding protocols.

Finally, we note that this protocol is also optimistically responsive in the network delay if the best case protocol is optimistically responsive. I.e. if there is a high fraction of honest parties, then OptimisticFlood propagates the message with the actual delivery time of the best-case protocol.