Composable Byzantine Agreements with Reorder Attacks

In a stateless model where protocols do not have distinguishing IDs, which is also considered by our work, [44] studied the sequential, parallel, and concurrent composition of authenticated BA protocols and presented the impossibility result as mentioned in the introduction. It also constructed secure randomized protocols under sequential composition. Without cryptographic primitives, [3] considered concurrently secure BAs with expected-constant round in both synchronous and asynchronous networks with optimal resiliency in the classical model (i.e., $n>3t$). However, as pointed out by [16], its security proof had some subtle issues regarding, e.g., the use of oblivious leader election.

Both [3] and [16] are not stateless: they assume a unique and common session ID for every execution of the protocol. As pointed out by [44], concurrent composition of any number of executions in this case is possible. Indeed, the focus of [3] and [16] was to construct expected-constant round protocols that are concurrently composible. Similarly, [37] assumed unique session IDs but considered an adversary who can corrupt a player in some but not all parallel executions.

Moreover, [16] followed the Universal Composability (UC) framework [8], which means the protocol is secure under arbitrary composition with itself and other cryptographic protocols in an adversarially controlled manner. Focusing on the asynchronous setting, [16] considered concurrent BA and presented the first information-theoretic multi-valued oblivious common coin (OCC) protocol with optimal resiliency. It further provided a modularized protocol for round-preserving parallel composition of BA that was simpler than the construction in [3].

An important line of work considers the complexity of a single execution of a Byzantine agreement. A body of foundational studies, in particular [19, 20, 9], proposed Byzantine agreement protocols that required a quadratic number of messages. More specifically, the $O(n^2)$ communication complexity necessitates nearly all-to-all communication between parties. Subsequently, for randomized Byzantine protocols, a seminal work [40] proposed a protocol where each party speaks to only $\tilde{O}(1)$ other parties, though their protocol achieved almost-everywhere agreement [21] rather than agreement, where $1-O({\log }^{-1}n)$ fraction of the parties reach agreement. Subsequent studies have sought to bridge this gap by achieving agreement from almost-everywhere agreement. To the best of our knowledge, so far the best communication complexity achievable for agreement in authenticated setting is $\tilde{O}(1)$ rounds with $\tilde{O}(\sqrt{n})$ communication and computation [32]. With enhanced cryptographic primitives such as LWE, this can be improved to $\tilde{O}(1)$ rounds and $poly(\lambda ,\log n)$ communication [5, 25], where $\lambda$ is the security parameter.

However, for deterministic Byzantine protocols, [18] established that achieving agreement inherently requires at least $\mathrm{\Omega }(t^2)$ communication. Furthermore, [14] extended this lower bound to other generalized validity definitions (e.g., weak validity), demonstrating that any well-defined Byzantine agreement variant necessitates $\mathrm{\Omega }(t^2)$ communication. Thus, deterministic Byzantine agreements incur fundamentally more overhead than randomized ones.

Different from this line of works that focused on single-instance executions of BA protocols, our work investigates compositional executions of BA protocols. Although our protocols are not necessarily optimal in terms of their complexity, our black-box compiler protocol achieves polynomial communication and computation. Further improving the complexity of our protocols and proving complexity lower-bounds in our model are interesting open problems.

Many prior works on network security have shown that channel attacks (e.g., man-in-the-middle attacks) without corrupting participating parties exist in a wide range of scenarios and pose a significant threat in real applications. By delaying, forging, dropping, or redirecting, attackers can break SSL/TLS certificate validation in many critical software applications [34, 51], cause security issues for HTTPS and its certificate trust model [15], inflict devastating damage on private and consortium blockchains [22], and so on.

Finally, it’s worth noticing that for transaction messages in DeFi, attackers (miners) can gain Miner Extracted Value (MEV) through transaction reordering attacks such as those studied in [53], while [38] indicated that currently no mitigation schemes can fully solve this problem. For a fully connected large-scale network, [52] analyzed Simple Majority Protocol (SMP) under probabilistic message loss and proved that it can reach consensus in three rounds of communication with probability approaching 1. However, those are within the same consensus protocol and the role of channel attacks in the composition of Byzantine agreements has not been explored yet.

For condition (1), the result follows directly from Theorem 1 in [44].

We prove the result for condition (2) by contradiction. Assume that there exists an authenticated Byzantine Agreement protocol $\mathrm{\Pi }$ that remains secure under two parallel executions against an adversary $𝒜(t,c)$ with $n\le 2c+2t+1$. We assume $c>0$, otherwise we have $2t+1\ge n$ and it can be reduced to condition (1).

We consider two independent executions of $\mathrm{\Pi }$: Let $A_1,A_2,\mathrm{\cdots },A_n$ and $B_1,\mathrm{\cdots },B_n$ be independent copies of $n$ parties participating in protocol $\mathrm{\Pi }$. The independent copies mean that for each $i$, $A_i$ and $B_i$ are the same party that runs in two different parallel executions of $\mathrm{\Pi }$. For the purpose of the proof below, we denote the set $T=\{A_2,\mathrm{\cdots },A_{\lfloor \frac{n+1}{2}\rfloor }\}$, $\tilde{T}=\{B_2,\mathrm{\cdots },B_{\lfloor \frac{n+1}{2}\rfloor }\}$, $H=\{A_{\lfloor \frac{n+3}{2}\rfloor },\mathrm{\cdots },A_n\}$, and $\tilde{H}=\{B_{\lfloor \frac{n+3}{2}\rfloor },\mathrm{\cdots },B_n\}$. Note that we have $n\le 2c+2t+1$, so we have $c+t\ge |T|=|\tilde{T}|$ and $c+t\ge |H|=|\tilde{H}|$.

Let $rounds(\mathrm{\Pi })$ denote the maximum number of communication rounds required for protocol $\mathrm{\Pi }$ to achieve termination in any execution. By the termination guarantees of the agreement property of Byzantine Agreement protocols, $rounds(\mathrm{\Pi })$ is finite and well-defined. Furthermore, given the security assumption that $\mathrm{\Pi }$ remains secure under parallel composition, it follows that $\mathrm{\Pi }$ must terminate within $rounds(\mathrm{\Pi })$ rounds even when executed concurrently across multiple protocol instances.

We now introduce an important abstract concept and will instantiate it in different ways in the proof. A system X is a tuple:

• $\mathrm{■}$

  A set $P=\{P_1,\mathrm{\dots },P_n\}$ of $n$ parties, each party $P_j$ runs two copies of ITMs, $A_j$ and $B_j$, for protocol $\mathrm{\Pi }$;

• $\mathrm{■}$

  An adversary $𝒜(t,c)$ controlling $t$ corrupted parties and reordering $c$ channels;

• $\mathrm{■}$

  Initial input values for all ITMs on their input tapes;

• $\mathrm{■}$

  A network topology governing inter-party connectivity.

Intuitively, if the system contains a non-trivial adversary who corrupts some parties and reorders some channels, then the network topology is consistent with the adversary’s reordering of the channels. In some mental games, we may instantiate the system without an adversary, in which case the network topology dictates how the parties’ communication channels are inter-connected crossing the two executions of $\mathrm{\Pi }$.

For any ITM $M$ run by a party in $P$, its view in system X, denoted by ${\mathrm{𝗏𝗂𝖾𝗐}}_X(M)$, consists of the content of $M$’s input tapes and random tape, where the former in particular includes the initial input value and the messages received by $M$ from other parties during the execution of X.

When all parties (including $𝒜(t,c)$) behave deterministically, ${\mathrm{𝗏𝗂𝖾𝗐}}_X(M)$ is uniquely determined by the initial configurations of the tapes and the adversarial behavior. Conversely, under randomized executions (where the content of the random tapes are sampled uniformly at random), ${\mathrm{𝗏𝗂𝖾𝗐}}_X(M)$ constitutes a random variable over the corresponding probability space.

We now instantiate the system S through the following configuration:

• $\mathrm{■}$

  Network Topology: ITM $A_1$ establishes connectivity with the set $\tilde{H}$ (replacing its original link to $H$), while ITM $B_1$ interfaces with $H$ instead of $\tilde{H}$. This structural reconfiguration is illustrated in Figure 2.

• $\mathrm{■}$

  Initial Input Value:

  • –

    ITMs in $\{A_1\}\cup T\cup H$ receive input $0$;

  • –

    ITMs in $\{B_1\}\cup \tilde{T}\cup \tilde{H}$ receive input $1$.

• $\mathrm{■}$

  Adversary: In this system, there is no adversary; formally, we have $t=0$ and $c=0$.

• $\mathrm{■}$

  Protocol Execution: All ITMs in $S$ strictly adhere to the instruction of protocol $\mathrm{\Pi }$, simulating an authenticated Byzantine Agreement environment. Specifically, each party:

  • –

    Generates messages as prescribed by $\mathrm{\Pi }$’s honest execution semantics;

  • –

    Sends these messages via the network topology defined above.

Now we first state the following lemmas and we will prove them afterwards.

By combining Lemma 5 with Lemma 6 we have $Outpu{t}_S(\tilde{H})=Outpu{t}_S(A_1)=0$ and at least one ITM $\tilde{h}\in \tilde{H}$ satisfies $Outpu{t}_S(\tilde{h})=Outpu{t}_S(B_1)=1$. Hence, we derive a contradiction on the output of $\tilde{h}$, thereby completing the proof of the theorem. $◀$

Next, we complete the proofs of Lemma 5 and Lemma 6.

To prove the lemma, we define a new system 2PBA as follows and as shown in Figure 3:

• $\mathrm{■}$

  Network Topology: The system consists of two parallel executions of protocol $\mathrm{\Pi }$, denoted ${\mathrm{\Pi }}_0$ (consisted of $A_1$, $T$ and $H$) and ${\mathrm{\Pi }}_1$ (consisted of $B_1$, $\tilde{T}$ and $\tilde{H}$).

• $\mathrm{■}$

  Initial Input Value:

  • –

    ITMs in $\{A_1\}\cup T\cup H$ receive input $0$;

  • –

    ITMs in $\{B_1\}\cup \tilde{T}\cup \tilde{H}$ receive input $1$.

• $\mathrm{■}$

  Adversary: The adversary $𝒜(t,c)$ chooses an arbitrary subset of parties $\{P_{\lfloor \frac{n+3}{2}\rfloor },\mathrm{\cdots },P_n\}$, denoted by $C$, which satisfies $|C|=\min \{c,n-\lfloor \frac{n+3}{2}\rfloor +1\}$. Then the adversary reorders all the channels between $C$ and $P_1$, and corrupts the parties in $\{P_{\lfloor \frac{n+3}{2}\rfloor },\mathrm{\cdots },P_n\}\setminus C$. As we have $2c+2t+1\ge n$, the adversary can indeed corrupt all these parties. In the following proof, we denote $IT{M}_0^C=\{IT{M}_0^j:j\in C\}$ as the set of ITMs run by $C$ in the protocol ${\mathrm{\Pi }}_0$, and as the same, we denote $IT{M}_1^C=\{IT{M}_1^j:j\in C\}$.

• $\mathrm{■}$

  Protocol Execution:

  • –

    All honest parties in $S$ strictly adhere to the instruction of protocol $\mathrm{\Pi }$;

  • –

    The corrupted parties reorder their channels between $P_1$, and besides this action, they adhere to the instruction of protocol $\mathrm{\Pi }$.

We then prove ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(A_1)={\mathrm{𝗏𝗂𝖾𝗐}}_S(A_1)$, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(T)={\mathrm{𝗏𝗂𝖾𝗐}}_S(T)$, and ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(H)={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{H})$.

We proceed by induction on the round counter $j\ge 1$.

• $\mathrm{■}$

  Message Generation: All parties in both $\mathrm{𝟤}𝖯𝖡𝖠$ and $𝖲$ generate identical message sets due to protocol $\mathrm{\Pi }$ strictly.

• $\mathrm{■}$

  Message Routing:

  • –

    In $S$: Messages propagate through the hexagonal graph.

  • –

    In $\mathrm{𝟤}𝖯𝖡𝖠$: The adversary $𝒜(t,c)$ enforces the following redirections:

    	$A_1\to H\stackrel{\text{reorder}}{\mapsto }\tilde{H}$	$,\tilde{H}\to B_1\stackrel{\text{reorder}}{\mapsto }{A}_1,$
    	$A_1\to T$	$,T\to H$
    	$H\to T$	$,T\to A_1$
    	$H\to A_1\stackrel{\text{reorder}}{\mapsto }{B}_1$	$,B_1\to \tilde{H}\stackrel{\text{reorder}}{\mapsto }H.$

  After reordering, $B_1$ communicates with $H$ rather than $\tilde{H}$, $A_1$ communicates with $\tilde{H}$ rather than $H$. Other than that, all the ITMs strictly adhere to the instruction of $\mathrm{\Pi }$. It is easy to see that the actual message routing is the hexagonal graph the same as in S.

• $\mathrm{■}$

  View Equivalence: The above routing rules induce identical message distributions at all parties’ interfaces. Thus, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(A_1)={\mathrm{𝗏𝗂𝖾𝗐}}_S(A_1)$, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(T)={\mathrm{𝗏𝗂𝖾𝗐}}_S(T)$, and ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(H)={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{H})$.

Assume equivalence holds through step $j$. For step $j+1$:

• $\mathrm{■}$

  Message Generation: Identical message distributions emerge from equivalent historical views (by inductive hypothesis).

• $\mathrm{■}$

  Message Routing: The hexagonal routing in $S$ and adversarial redirection in $\mathrm{𝟤}𝖯𝖡𝖠$ preserve the same correspondence as $j=1$.

• $\mathrm{■}$

  View Update: Therefore, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}^{(j+1)}(A_1)={\mathrm{𝗏𝗂𝖾𝗐}}_S^{(j+1)}(A_1)$ and ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}^{(j+1)}(T)={\mathrm{𝗏𝗂𝖾𝗐}}_S^{(j+1)}(T)$ maintain for the $j+1$ rounds.

Owing to the termination property of Byzantine Agreement, which mandates that the protocol $\mathrm{\Pi }$ halts within $rounds(\mathrm{\Pi })$, the aforementioned procedure completes in at most $rounds(\mathrm{\Pi })$ rounds. Consequently, we derive that ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(A_1)={\mathrm{𝗏𝗂𝖾𝗐}}_S(A_1)$, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(T)={\mathrm{𝗏𝗂𝖾𝗐}}_S(T)$, and ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(H)={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{H})$.

Given the equivalence of views, the parties $A_1$, $T$ and $H$ in both systems 2PBA and S must yield identical final outputs. By the validity property of Byzantine Agreement, since $A_1$, $T$, and $H$ in ${\mathrm{\Pi }}_0$ are initialized with input 0 and $A_1$, $T$, $IT{M}_0^C\subset H$ are honest, then $Outpu{t}_{2PBA}(A_1)=Outpu{t}_{2PBA}(T)=Outpu{t}_{2PBA}(IT{M}_0^C)=0$. Consequently, system S inherits this outcome, we have $Outpu{t}_S(A_1)=Outpu{t}_S(T)=Outpu{t}_S(IT{M}_0^C)=0$.

Analogously, through the system 2PBA, we can rigorously demonstrate ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(B_1)={\mathrm{𝗏𝗂𝖾𝗐}}_S(B_1)$, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(\tilde{T})={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{T})$ and ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PBA}(\tilde{H})={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{H})$, thereby establishing $Outpu{t}_S(B_1)=Outpu{t}_S(\tilde{T})=Outpu{t}_S(IT{M}_1^C)=1$. $◀$

Similarly, we construct system 2PBA’ as instantiated below, shown in Figure 4:

• $\mathrm{■}$

  Network Topology: The system consists of two parallel executions of protocol $\mathrm{\Pi }$, denoted ${\mathrm{\Pi }}_0^{\prime }$ (consisted of $A_1$, $\tilde{H}$ and $\tilde{T}$) and ${\mathrm{\Pi }}_1^{\prime }$ (consisted of $B_1$, $H$ and $T$).

• $\mathrm{■}$

  Initial Input Value:

  • –

    ITM $\{A_1\}$ receives input $0$ and ITMs in $\tilde{H}\cup \tilde{T}$ receive input $1$;

  • –

    ITM $\{B_1\}$ receives input $0$ and ITMs in $H\cup T$ receive input $1$.

• $\mathrm{■}$

  Adversary: The adversary $𝒜(t,c)$ chooses an arbitrarily subset of parties $\{P_2,\mathrm{\cdots },P_{\lfloor \frac{n+1}{2}\rfloor }\}$, denoted by $C^{\prime }$, which satisfies $|C^{\prime }|=\min \{c,\lfloor \frac{n+1}{2}\rfloor -1\}$. Then the adversary reorders all the channels between $C^{\prime }$ and $P_1$, and corrupts the parties in $\{P_2,\mathrm{\cdots },P_{\lfloor \frac{n+1}{2}\rfloor }\}\setminus C^{\prime }$. As we have $2c+2t+1\ge n$, the adversary can indeed corrupt all these parties. In the following proof, we denote $IT{M}_0^{C^{\prime }}=\{IT{M}_0^j:j\in C^{\prime }\}$ as the set of ITMs run by $C^{\prime }$ in the protocol ${\mathrm{\Pi }}_0$, and as the same, we denote $IT{M}_1^{C^{\prime }}=\{IT{M}_1^j:j\in C^{\prime }\}$.

• $\mathrm{■}$

  Protocol Execution:

  • –

    All honest parties in $S$ strictly adhere to the instruction of protocol $\mathrm{\Pi }$;

  • –

    The corrupted parties reorder their channels between $P_1$, and besides this action, they adhere to the instruction of protocol $\mathrm{\Pi }$.

The subsequent proof by mathematical induction is analogous to the reasoning in system 2PBA of the preceding proof; therefore it is omitted here. It is noteworthy that after we get ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PB{A}^{\prime }}(A_1)={\mathrm{𝗏𝗂𝖾𝗐}}_S(A_1)$, ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PB{A}^{\prime }}(\tilde{H})={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{H})$, and ${\mathrm{𝗏𝗂𝖾𝗐}}_{2PB{A}^{\prime }}(\tilde{T})={\mathrm{𝗏𝗂𝖾𝗐}}_S(\tilde{T})$, we use the Agreement property instead of the Validity property of Byzantine agreement to deduce that $Outpu{t}_S(A_1)=Outpu{t}_S(\tilde{H})=Outpu{t}_S(IT{M}_1^{C^{\prime }})$. Similarly, we have $Outpu{t}_S(B_1)=Outpu{t}_S(H)=Outpu{t}_S(IT{M}_0^{C^{\prime }})$. $◀$