Asynchronous Byzantine Reliable Broadcast
With a Message Adversary

If a correct process $p_{i}$ mbrb-delivers $(m,\mathit{sn},j)$ (where $p_{j}$ is correct) at line 1, then it has passed the condition at line 1, which means that it must have witnessed a valid signature for $(m,\mathit{sn},j)$ by $p_{j}$. Since signatures are secure, the only way to create this signature is for $p_{j}$ to execute the instruction at line 1, during the $\mathsf{mbrb\_broadcast}(m,\mathit{sn})$ invocation. ∎

This property derives trivially from the condition at line 1. ∎

Let us consider two correct processes $p_{a}$ and $p_{b}$ which respectively mbrb-deliver $(m,\mathit{sn},i)$ and $(m^{\prime},\mathit{sn},i)$. Due to the condition at line 1, $p_{a}$ and $p_{b}$ must have saved (and thus received) two sets $Q_{a}$ and $Q_{b}$ containing strictly more than $\frac{n+t}{2}$ signatures for $(m,\mathit{sn},i)$ and $(m^{\prime},\mathit{sn},i)$, respectively. We thus have $|Q_{a}|>\frac{n+t}{2}$ and $|Q_{b}|>\frac{n+t}{2}$.

As we have $|A\cap B|=|A|+|B|-|A\cup B|\geq|A|+|B|-n>2\times\frac{n+t}{2}-n=t$, $A$ and $B$ have at least one correct process $p_{k}$ in common, which must have signed both $(m,\mathit{sn},i)$ and $(m^{\prime},\mathit{sn},i)$. But before signing $(m,\mathit{sn},i)$ at line 1 or 1, $p_{k}$ checks that it did not sign a different app-message from the same sender and with the same sequence number, whether it be implicitly during a $\mathsf{brb\_broadcast}(m,\mathit{sn})$ invocation or at line 1. Thereby, $m$ is necessarily equal to $m^{\prime}$. ∎

If a correct process $p_{i}$ mbrb-broadcasts $(m,\mathit{sn})$, then it broadcasts its own signature $\mathit{sig}_{i}$ for $(m,\mathit{sn},i)$ in a $\textsc{bundle}(m,\mathit{sn},i,\{\mathit{sig}_{i}\})$ message at line 1. As $p_{i}$ is correct, it does not sign another triplet $(m^{\prime},\mathit{sn},i)$ where $m^{\prime}\neq m$, therefore it is impossible for a correct process to mbrb-deliver $(m^{\prime},\mathit{sn},i)$ at line 1, because it cannot pass the condition at line 1.

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

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

From mbrb-Assumption, we have $3t+2d<n\iff n+3t+2d<2n\iff n+t<2n-2t-2d\iff\frac{n+t}{2}<n-t-d\leq c-d$ (as $n-t\leq c$). As a result, at least one process $p_{j}$ of $K$ (ergo one correct process) receives a set $S$ (in possibly multiple bundle messages) of strictly more than $\frac{n+t}{2}$ valid distinct signatures for $(m,\mathit{sn},i)$. When $p_{j}$ receives the last signature of $S$, there are two cases:

• •

  Case if $p_{j}$ does not pass the condition at line 1.

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

• •

  Case if $p_{j}$ passes the condition at line 1.

  Process $p_{j}$ then saves all signatures of $S$ at line 1, and after it passes the condition at line 1 (as $|S|>\frac{n+t}{2}$) and finally mbrb-delivers $(m,\mathit{sn},i)$ at line 1. ∎

If a correct process $p_{i}$ mbrb-delivers $(m,\mathit{sn},j)$ at line 1, it must have saved a set $\mathit{sigs}$ of strictly more than $\frac{n+t}{2}$ valid distinct signatures because of the condition at line 1. Let us remark that $\mathit{sigs}$ necessarily contains the signature for $(m,\mathit{sn},i)$ by $p_{i}$ because of the condition at line 1. Additionally, $p_{i}$ must also have broadcast $\textsc{bundle}(m,\mathit{sn},i,\mathit{sigs})$ at line 1, that, by definition of the message adversary, is received by a set $K$ of at least $c-d$ correct processes. For each process $p_{k}$ of $K$:

• •

  If $p_{k}$ does not pass the condition at line 1, it is necessarily because it has already mbrb-delivered some $(-,\mathit{sn},j)$ at line 1. But because of MBRB-No-duplicity, $p_{k}$ has necessarily mbrb-delivered $(m,\mathit{sn},j)$.

• •

  If $p_{k}$ passes the condition at line 1, then it saves all signatures of $\mathit{sigs}$ at line 1 and then passes the condition at line 1 and finally mbrb-delivers $(m,\mathit{sn},j)$ at line 1.

Therefore, all processes of $K$ (which, as a reminder, are at least $c-d=\ell$) necessarily mbrb-deliver $(m,\mathit{sn},j)$ at line 1. ∎

We have the following:

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

Let $A$ and $B$ define two partitions of the set of all correct processes ($A\cup B$ is the set of all correct processes, and $A\cap B=\varnothing$). $A$ denotes the set of correct processes that receive strictly more than $\frac{n+t}{2}$ signatures for $(m,\mathit{sn},i)$ from processes of $K$ two communication steps after $p_{i}$ mbrb-broadcast $(m,\mathit{sn})$, while $B$ denotes the set of remaining correct processes of $K$ that receive at most $\frac{n+t}{2}$ signatures for $(m,\mathit{sn},i)$ from processes of $K$ two communication steps after $p_{i}$ mbrb-broadcast $(m,\mathit{sn})$. Let $\ell_{2}$ be the size of $A$: $\ell_{2}=|A|$. By construction, $|B|=c-\ell_{2}$. Let $s_{A}$ and $s_{B}$ respectively denote the number of signatures for $(m,\mathit{sn},i)$ from processes of $K$ received by processes of $A$ and $B$ at most two communication steps after $p_{i}$ mbrb-broadcast $(m,\mathit{sn})$. Figure 1 represents the distribution of such signatures among processes of $K$, sorted by decreasing number of signatures received. Each processes of $A$ can receive at most $k$ signatures (that is, all signatures) from processes of $K$, while each process of $B$ can receive at most $\lfloor\frac{n+t}{2}\rfloor$ signatures from processes of $K$ two communication steps after $p_{i}$ mbrb-broadcasts $(m,\mathit{sn})$. For the sake of simplicity, we use $q$ in the place of $\lfloor\frac{n+t}{2}\rfloor$ in some parts of this proof.

By the definition of the message adversary, a $\textsc{bundle}(m,\mathit{sn},i,\{\mathit{sig}_{x},\mathit{sig}_{i}\})$ imp-message broadcast by a correct process $p_{x}$ is eventually received by at least $c-d$ correct processes. As a consequence, in total, the minimum number of signatures for $(m,\mathit{sn},i)$ collectively received by correct processes as a result of broadcasts by processes in $K$ in the first two asynchronous communication steps is $k(c-d)$. We thus have:

By combining the previous inequalities, we obtain:

By Lemma 6, we know that $k\geq c-d>\big{\lfloor}\frac{n+t}{2}\big{\rfloor}=q$, so we can rewrite (1) into:

Let us define a function $f$ such that $f(k)=\frac{k(c-d)-cq}{k-q}$. As we seek the lowest guaranteed value for $\ell_{2}$, we want to find the minimum of $f$ on $k\in[c-d,c]$. To this end, let us first study the derivative of $f$. The image $f(k)$ is of the form $\frac{u}{v}$, so we have:

As $q$ and $d$ are by definition positive, we know that $f^{\prime}(k)=\frac{qd}{(k-q)^{2}}$ is positive, or null when $d=0$. Therefore, $f$ is monotonically increasing on $k\in[c-d,c]$, and the minimum value for $\ell_{2}$ can be found when $k$ is also minimum, that is, when $k=c-d$. Thus, when we replace $k$ by $c-d$ in (2), we obtain:

Let us denote by $\ell_{2,\mathsf{min}}$ the minimum number of correct processes that receive a quorum of strictly more than $\frac{n+t}{2}$ valid distinct signatures for $(m,\mathit{sn},i)$ two communication steps after $p_{i}$ mbrb-broadcast $(m,\mathit{sn})$, such that $\ell_{2,\mathsf{min}}\leq\ell_{2}=|A|$. As the right hand side of (3) is not always an integer, we have:

Hence, at least $\ell_{2,\mathsf{min}}=c-d-\Big{\lfloor}\frac{d\lfloor\frac{n+t}{2}\rfloor}{c-d-\lfloor\frac{n+t}{2}\rfloor}\Big{\rfloor}$ processes of $K$ receive strictly more than $\frac{n+t}{2}$ valid distinct signatures for $(m,\mathit{sn},i)$ two communication steps after $p_{i}$ mbrb-broadcasts $(m,\mathit{sn})$. For every process $p_{a}$ of $A$:

• •

  If $p_{a}$ does not pass the condition at line 1 after receiving the last signature of the quorum in a bundle imp-message, it is necessarily because $p_{a}$ already mbrb-delivered some $(-,\mathit{sn},i)$, because processes of $K$ are correct and all their bundle imp-messages include the signature for $(m,\mathit{sn},i)$ by $p_{i}$. But let us remind that, as the sender $p_{i}$ is correct, it is impossible for $p_{a}$ to mbrb-deliver anything different from $(m,\mathit{sn},i)$. Therefore, $p_{a}$ has already mbrb-delivered $(m,\mathit{sn},i)$ at line 1.

• •

  If $p_{a}$ passes the condition at line 1 after processing the last $\textsc{bundle}(m,\mathit{sn},i,\{\mathit{sig}_{i},\mathit{sig}_{x}\})$ imp-message of the quorum from a process $p_{x}$, then $p_{a}$ saves the signature $\mathit{sig}_{x}$ at line 1, and after it passes the condition at line 1 (as it has saved strictly more than $\frac{n+t}{2}$ signatures) and finally mbrb-delivers $(m,\mathit{sn},i)$ at line 1.

Therefore, all processes of $A$, which are at least $\ell_{2,\mathsf{min}}=c-d-\Big{\lfloor}\frac{d\lfloor\frac{n+t}{2}\rfloor}{c-d-\lfloor\frac{n+t}{2}\rfloor}\Big{\rfloor}$, mbrb-deliver $(m,\mathit{sn},i)$ at line 1 at most two communication steps after $p_{i}$ mbrb-broadcast $(m,\mathit{sn})$. ∎

Let us assume that a correct process $p_{i}$ mbrb-broadcasts $(m,\mathit{sn})$ and that $d<c-\sqrt{c\times\frac{n+t}{2}}$. Process $p_{i}$ must unreliably broadcast a first $\textsc{bundle}(m,\mathit{sn},i,\{\mathit{sig}_{i}\})$ imp-message (where $\mathit{sig}_{i}$ is the signature of $(m,\mathit{sn},i)$ by $p_{i}$) at line 1. This initial imp-message is received by at least $(c-d-1)$ other correct processes, due to our assumption on the message adversary. This counts for a first communication step.

In the second communication step, each process $p_{j}$ of these $(c-d-1)$ correct processes unreliably broadcasts its own $\textsc{bundle}(m,\mathit{sn},i,\{\mathit{sig}_{j},\mathit{sig}_{i}\})$ imp-message (where $\mathit{sig}_{j}$ is the signature of $(m,\mathit{sn},i)$ by $p_{j}$) at line 1. At the end of the second communication step, in total, at least $(c-d)$ distinct signatures for $(m,\mathit{sn},i)$ have been created and unreliably broadcast by correct processes (counting that of $p_{i}$), resulting in at least $(c-d)^{2}$ receptions of said signatures by correct processes. As there are $c$ correct processes, this means that, on average, each correct process has received at least $\frac{(c-d)^{2}}{c}$ signatures by the end of the second communication step, and that at least one correct process, $p_{k}$, receives (and saves at line 1) at least this number of signatures.

From the Lemma hypothesis $d<c-\sqrt{c\times\frac{n+t}{2}}$ and using simple algebraic transformations, we can derive $\frac{(c-d)^{2}}{c}>\frac{n+t}{2}$. Therefore, $p_{k}$ reaches a quorum of signatures, that is, it passes the condition at line 1 and unreliably broadcast this quorum of signatures at line 1, two communication steps after the mbrb-broadcast of $(m,\mathit{sn})$ by $p_{i}$. By definition of the message adversary, this quorum of signatures is received by $c-d$ correct processes, which save it at line 1 and thus pass the condition at line 1 and finally mbrb-deliver $(m,\mathit{sn},i)$ at line 1, three communication steps after the mbrb-broadcast of $(m,\mathit{sn})$ by $p_{i}$. ∎

Let us consider a correct process $p_{i}$ that mbrb-broadcasts $(m,\mathit{sn})$. By exhaustion:

• •

  Case where $d<\frac{c-\lfloor\frac{n+t}{2}\rfloor}{\lfloor\frac{n+t}{2}\rfloor+1}$.

  By Lemma 7, at least $c-d-\Big{\lfloor}\frac{d\lfloor\frac{n+t}{2}\rfloor}{c-d-\lfloor\frac{n+t}{2}\rfloor}\Big{\rfloor}$ correct processes mbrb-deliver $(m,\mathit{sn},i)$ two communication steps after $p_{i}$ has mbrb-broadcast $(m,\mathit{sn})$. We have:

  	$\displaystyle d$	$\displaystyle<\frac{c-\lfloor\frac{n+t}{2}\rfloor}{\lfloor\frac{n+t}{2}\rfloor+1},$		(case assumption)
  	$\displaystyle d\Big{\lfloor}\frac{n+t}{2}\Big{\rfloor}+d$	$\displaystyle<c-\Big{\lfloor}\frac{n+t}{2}\Big{\rfloor},$		(as $\lfloor\frac{n+t}{2}\rfloor+1>0$)
  	$\displaystyle d\Big{\lfloor}\frac{n+t}{2}\Big{\rfloor}$	$\displaystyle<c-d-\Big{\lfloor}\frac{n+t}{2}\Big{\rfloor},$
  	$\displaystyle\frac{d\lfloor\frac{n+t}{2}\rfloor}{c-d-\lfloor\frac{n+t}{2}\rfloor}$	$\displaystyle<1,$		(as $c-d>\lfloor\frac{n+t}{2}\rfloor$ by Lemma 6)
  	$\displaystyle\left\lfloor\frac{d\lfloor\frac{n+t}{2}\rfloor}{c-d-\lfloor\frac{n+t}{2}\rfloor}\right\rfloor$	$\displaystyle\leq 0,$
  	$\displaystyle c-d-\left\lfloor\frac{d\lfloor\frac{n+t}{2}\rfloor}{c-d-\lfloor\frac{n+t}{2}\rfloor}\right\rfloor$	$\displaystyle\geq c-d=\ell.$

  Hence, $\ell$ correct processes mbrb-deliver $(m,\mathit{sn},i)$ at most two communication steps after $p_{i}$ has mbrb-broadcast $(m,\mathit{sn})$.

• •

  Case where $d<c-\sqrt{c\times\frac{n+t}{2}}$.

  Lemma 8 applies and at least $c-d=\ell$ correct processes mbrb-deliver $(m,\mathit{sn},i)$ at most three communication steps after $p_{i}$ has mbrb-broadcast $(m,\mathit{sn})$. ∎

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

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