Phalanx: A Practical Byzantine Ordered Consensus Protocol

We consider a system of $n=3f+1$ consensus nodes (hereinafter referred to as nodes for short) and any number of proposers (or we can call them clients). In this paper, we focus on the adversary in nodes and ignore the potential malicious behavior of proposers. We assume that an adversary can control up to $f$ nodes.

Taking the partial ordering of each node as the material, Byzantine ordered consensus would make all the trusted nodes obtain a consistent total ordering. The commands would be committed according to the consistent total ordering and would send back reply message to specific proposers.

Let $o$ denotes log. Call that $o\to r$, if and only if $o.d_{r}=r.d$. Let $\prec_{i}$ denote the context in $N_{i}$’s partial ordering. For logs $o_{1}$ and $o_{2}$ from $N_{i}$, there are $r_{1}$ and $r_{2}$ that $o_{1}\to r_{1}$ and $o_{2}\to r_{2}$. There is a context that $r_{1}\prec_{i}r_{2}$ if and only if $o_{1}.n<o_{2}.n$. Although the partial ordering for each node might- be different, every non-faulty node would eventually find the same total ordering to commit commands.

The modular implemented Phalanx component should be combined with a BFT protocol so that the network assumptions should support both Phalanx component itself and the combined original BFT protocol.

The communication in Phalanx component is asynchronous, so that, in addition to the network assumption of the original BFT protocol, we only need to satisfy the messages sent from one participant will reach the recipient(s) eventually. As asynchronous network assumption is the weakest one in BFT protocol groups’ network assumptions, the Phalanx component will not impact the robustness of the original BFT cluster.

Besides, there is another basic assumption called sending-receiving model that messages receiving order should always be the same as their sending order. For instance, $N_{1}$ is trying to send messages toward $N_{2}$. If $N_{1}$ has sent $m_{1}$ before $m_{2}$, $N_{2}$ must receive $m_{1}$ before $m_{2}$. It could be achieved easily with the use of sequence numbers.

In state-of-the-art leader-based BFT consensus protocols, the total ordering is determined by the leader and followers can only detect limited malicious behaviors. It doesn’t respect the collective preferences of each correct participant, and, because a leader has controlled the total ordering, there is a risk of suffering a manipulation attack, which means the adversaries make the transactions more likely to be committed according to their own wishes.

Byzantine ordered consensus protocol is used to tolerate Byzantine faults in ordering manipulation. To achieve it, we believe Byzantine ordered consensus protocol should have two essential properties, free will and fairness.

By using some reasonable ordering strategies, which take every node’s partial ordering into thought, we can always achieve certain free-will characteristics. To achieve better fairness, we need to aggregate the logical clock from each participant. However, the Condorcet Paradox prevents us to find distinct total ordering. Next, we would like to introduce our method to deal with the paradox.

For the reliable context is generated by the non-faulty nodes, selecting it into the total ordering satisfy the free-will. If the context is not reliable, it means the context could be generated by a byzantine node, and might be the will of the adversaries. It is risky to select such a unreliable context into total ordering.

Then we need to commit the anchor commands according to the partial ordering set. Each time when we commit an anchor command $r_{a}$, we need to generate command set $F$ which is constructed with $r_{a}$ and the commands $\{r^{\prime}\}$ with reliable context $r^{\prime}\prec_{r}r_{a}$. After that, the commands would be committed linearly, which has avoided the Condorcet Paradox, and make the ordering process more practical and conducive to implementation.

In the next section, we would like to introduce the protocol we design with the anchor-based ordering strategy.

Phalanx has two types of roles: proposers and nodes. A proposer $P_{i}$ could propose command $c$ with given order. The non-faulty nodes $\{N_{i}\}$ are trying to reach consensus on the total ordering of commands.

As is shown in Fig. 1, a node is constructed with three main parts: mempool, consensus, and executor. Whenever node $N_{i}$ has received the command sent from proposers, firstly, put them into $N_{i}$’s partial ordering according to FIFO (First-In-First-Out) receiving the ordering. Then, pending logs for $N_{i}$ are created. After the process of order-protocol, verifiable logs are generated to notify others its own partial ordering. The mempool is a container of logs received from each node. In consensus module, using the logs in mempool, we generate order-batch to trigger consensus and get the same log stream for non-faulty nodes with the help of any state-of-the-art BFT protocols. Taking the log stream as material, in executor, the non-faulty nodes eventually find the same total ordering for commands. In particular, we list some basic notations as needed in Table I. As for the sets and vectors, unless otherwise specified, they do not have preset size. If the vector have preset size, every element in it should have a initial value.

We use standard hash function (e.g., SHA256) to generate the digest of messages. Generate the digest of $m$, $d\leftarrow h(m)$, then $d$ could be regarded as the identifier of $m$. If there is another message $m^{\prime}$, we say that $m^{\prime}$ is the same as $m$ if and only if $h(m^{\prime})=h(m)$.

We assume a public key infrastructure (PKI) of each participant in our system including proposers and nodes which means each of them is identified by its own public key. When proposer $P_{i}$ or node $N_{i}$ is trying to send message $m$, the communication transmission will be carried out reliably through $\langle m\rangle_{i}$.

Besides, we make use of ($k,n$)-threshold signature among nodes. There is a single public key and each $N_{i}$ holds a distinct private key. If event $e$ needs to be determined by the vote of the nodes. Sending a vote means approval, and not sending a vote means denial. Each time when $N_{i}$ sends a vote, it generates a partial signature with its private key $\rho_{i}\leftarrow psig_{i}(e)$. We could verify the validation of partial signature with $\rho_{i}$ with $pverify(\rho_{i})$. When there is a set of valid partial signatures $\{\rho_{i}\}_{i\in P}$ and $|P|=k$, generate aggregated signature for $e$, $sig\leftarrow agg(e,\{\rho_{i}\}_{i\in P})$. Every node could verify the aggregated signature with the single public key that $verify(sig)$. If it is a valid aggregated signature, the function should return $true$ value.

The aggregated signature could be regarded as a kind of certificate, denoted as $cert$. If $cert$ is valid, then it means there are $k$ nodes have voted on event $e$. Make use of $(2f+1,n)$-threshold signature to generate $cert$ for $e$ in BFT consensus algorithm, and we could verify the $cert$ to check the quorum agreement on $e$.

Each node $N_{i}$ has its own mempool. Let $\mathrm{mempool}_{i}$ denote it. Whenever $N_{i}$ receives commands from proposers, the $\mathrm{mempool}_{i}$ would receive them and generate $N_{i}$ partial ordering according to FIFO receiving ordering. At the same time, certified logs would be generated with ordering protocol and notify other participants.

Step 1: Pre-Order. If the FIFO queue $\mathbb{R}_{F}$ isn’t empty and there isn’t a pending log that $o_{pending}=\bot$, $N_{i}$ would take the front element $r\leftarrow\mathbb{R}_{F}.front()$ and then try to generate verifiable log for it. $N_{i}$ advances its local logical clock $seq\leftarrow seq+1$, and generates the order tuple without certificate $o\leftarrow\langle i,n,d_{c},d_{pre},d_{cur}\rangle$, $o.n\leftarrow seq$, $o.d_{c}\leftarrow c.d$, $o.d_{pre}\leftarrow H[i].d_{cur}(o.n>1)$. Store the tuple $o$ as a pending log that $o_{pending}\leftarrow o$. Then, $N_{i}$ broadcasts pre-order message $\langle$PRE_ORDER $o\rangle_{i}$ and starts to wait for the responses from $2f+1$ nodes (including itself).

Step 2: Vote. A node $N_{j}$ (including $N_{i}$ itself) receives the pre-order message sent from $N_{i}$ and tries to verify the tuple $o$ with $N_{i}$’s latest verifiable log that $o_{h}\leftarrow H[i]$. First, $o$ should have a valid digest. Next, if $o_{h}$ is $\bot$, then $o.n$ should be equal to 1. If $o_{h}$ is not $\bot$, then $o$ should be the next log of $o_{h}$ that $o.n=o_{h}.n+1$ and $o.d_{pre}=o_{h}.d_{cur}$. If $o$ satisfies these requirements above, it could be regarded as a valid tuple. Then, the node $N_{j}$ would respond with $\langle$VOTE $d,\rho_{j}\rangle_{j}$, where $d$ is the digest of $o$ that $d\leftarrow o.d_{cur}$, and $\rho_{j}$ is a partial signature generated by $N_{j}$ for digest $d$ that $\rho_{j}\leftarrow psig_{j}(d)$. Whenever $N_{j}$ has voted log $o$ from $N_{i}$, $N_{j}$ will not vote for another log $o^{\prime}$ from $N_{i}$ that $o^{\prime}.n=o.n$.

Step 3: Order. Whenever $N_{i}$ receives response $v_{j}$ from $N_{j}$, it verifies the partial signature with $pverify(v_{j}.\rho_{j})$. If it is valid, accept it. When $N_{i}$ has received valid responses from $2f+1$ nodes (including itself), there is a set of valid partial signatures $\{\rho_{j}\}$ and $|\{\rho_{j}\}|$ is equal to $2f+1$. Generate aggregated signature with the set and complete log that $o.cert\leftarrow agg(o.d_{cur},\{\rho_{j}\})$. Next, $N_{i}$ broadcasts partial order message $\langle$ORDER $o\rangle_{i}$ to notify others with its latest verifiable partial order. When node $N_{j}$ receives the log $o$ from $N_{i}$, verify it with $verify(o.cert)$. If it’s valid, then update the latest log of $N_{i}$ in local states that $H[i]\leftarrow o$.

At last, the logs generated by $N_{i}$ is constructed like Fig. 3. The subscript of $o_{k}$ in the figure indicates the log’s serial number. The digests of logs construct a chained structure and the certificate could be used to verify the validation of each log. Besides, $\mathrm{mempool}_{i}$ stores the commands and verifiable logs $N_{i}$ has received. Every time trying to use them, we could get the command $r$ according to its digest and get log $o$ according to tuple $\langle i,n\rangle$, where $i$ is the author of partial order and $n$ is the sequence number.

Let $\mathrm{consensus}_{i}$ denotes the consensus module for node $N_{i}$. It is used to find the same log stream for each non-faulty node. To achieve this goal, Phalanx could employs any state-of-the-art BFT protocols, such as PBFT, HotStuff, and even HoneyBadgerBFT, an asynchronous protocol. The primitive BFT protocol could help the non-faulty node reach consensus on the order of $tx$-batch. Here, in Phalanx, the contents of consensus batch are replaced by the latest logs for each node. We call it order-batch. After the consensus process of primitive BFT protocol, we can find the consistent logs set to generate total ordering in the executor module.

Next, commit the order-batches in $\{b_{m}\}$ one by one. Whenever trying to commit $b_{m}$, a set of logs $S$ would be generated. The steps are as follows.

Step 1. Verify the certificates of logs in $b_{m}.H$. If there is an invalid log, stop the process and change the leader in BFT protocol. If they are valid, initialize an empty log set $S$. For each logs in $b_{m}.H$, we should process it according to step 2.

Step 2. Let $n_{h}\leftarrow b_{m}.H[j].n$ and $n_{c}\leftarrow V[j]$. If $n_{h}\leq n_{c}$, just return. If $n_{h}>n_{c}$, then (1) update $V[i]$ with $n_{h}$, (2) add $b_{m}.H[j]$ into $S$, (3) get the logs generated by $N_{j}$ with sequence number belonging to $(n_{c},n_{h})$ from mempool and add them into $S$. If we cannot find the expected logs from mempool, request other nodes for it and verify the digests and certificates.

Step 3. After the process of each log in $b_{m}.H$, add $S$ into the end of $\mathbb{S}$.

As for employing leadless BFT protocols, the generation of order-batch depends on the generation strategy of the primitive protocol. For instance, in HoneyBadger-BFT (HB-BFT), each node would generate a slice of the proposal, and the final committed block is constructed by part of them. So that, if we employ Phalanx in HB-BFT, node $N_{i}$ would just propose its latest log to trigger BFT protocol. After each time the BFT protocol consensus process is finished, an order-batch could be constructed. At last, we could find a series of order-batches in the same order and commit them one by one to generate the log sets to update $\mathbb{S}$.

After the process of consensus module, each non-faulty node would find the same FIFO queue $\mathbb{S}$. The FIFO queue $\mathbb{S}$ is going to be used in executor module to generate total ordering.

The executor module aims to get the final ordering (total ordering) according to the log stream in $\mathrm{consensus}_{i}.\mathbb{S}$. To achieve anchor-based ordering, we need to find the anchor commands with specific ordering rules. In this part, we would like to introduce the generation of final ordering.

Step 1. Commit logs in $S$ one by one into executor module. For each log $o$ in $S$, read the command info $c$ from $C$ at first that $c\leftarrow C[o.d_{r}]$ (if there doesn’t exist such a command info, initiate it). Update $c.O[o.i]$ with $o$ and add $o$ into the end of FIFO queue $Q[o.i]$.

Step 2. Find the anchor-set. Initialize an empty anchor-set $F$. Read every FIFO queue in $Q$. While reading $\mathbb{Q}_{i}$, if the front-log $\theta_{i}$ points to a committed command that $\theta_{i}.d_{r}\in D$, then remove it and read the latest front-log. Repeat the process till the front-log $\theta_{i}$ is $\bot$ or points to uncommitted command. Add each $\theta_{i}$ into a vector $\Theta$ that $\Theta[i]$ tracks the front-log $\theta_{i}\leftarrow Q[i].read\_front()$. If there exists commands $\{r\}$ that at least $f+1$ front-logs point to $r$, then put all these command info $c\to r$ into $F$, return the anchor-set $F$. If not, jump into alter path.

alter path. For all the command info with $|c.O|\leq 2f+1$, get the command info $c$ with the lowest trusted timestamp. Then regard the command $c\to r$ as anchor command $r_{a}$. If $c\to r_{a}$, that we can find $c^{\prime}$, $c^{\prime}\to r^{\prime}$, that there is not a reliable context $r_{a}\prec r^{\prime}$, then add $r^{\prime}$ into $F$. Repeat this process until no such a $c^{\prime}$ can be found or the $c^{\prime}$ added into $F$ has $|c^{\prime}.O|<2f+1$.

Step 3. Check the front set. For each command info $c$ in $F$, if $|c.O|<f+1$, then remove $c$ from $F$. If $\exists c\in F$ that there are at least $f+1$ non-empty values in $c.O$ but $|c.O|$ is less than $2f+1$, then directly return an empty anchor-set.

Step 5. Commit the commands according to $F$. First of all, sort the command info {c} in anchor-set $F$ according to the in ascending order by trusted timestamp of $c$. If the trusted timestamps are the same, then sort the command info alphabetically. After that, according to the sorted command info set $\{c\}$, we would commit the command $r$ that $c\to r$ one by one. To obtain the command $r$, we could read the mempool or request it from others.

As is shown in Fig 4, it is the journey for non-faulty nodes to create total ordering after each participant has generated partial ordering in its mempool.

After the commitment of commands, each non-faulty node gets the same total ordering to execute them. After the execution of the command, nodes would feedback the results to proposers. If the proposer has received $f+1$ the same response for one command, accept the execution result for it.

As for the commands belonging to the same anchor-set, the timestamp-based strategy can be taken to decide their ordering. For there are at most $f$ faulty nodes, the $(f+1)$-th largest timestamp is most likely sent from a non-faulty node, when we have received at least $2f+1$ logs pointing to specific command from different nodes.

For each datacenter, we use the default batch size $b=200$ and the ordering interval $\Delta_{o}=50$ms. The results are shown in Table VIII. If there is only 1 proposer ($p=1$) to propose commands in Phalanx-HS, the throughput of it is almost the same as HS while the latency of Phalanx-HS is 15.3% higher than HS. If we increase the number of proposers from 1 to 4, the throughput of Phalanx-HS increases in direct proportion to the number of proposers, while the latency of Phalanx-HS has barely changed. Then, we evaluate the performance of HS with $b=800$, and we found that its performance is almost the same as Phalanx-HS with $b=200$ and $p=4$.

For each geo-distributed node, we use the default batch size $b=200$ and the ordering interval $\Delta_{o}=200$ms. The results are as shown in Table IX. If there is only 1 proposer ($p=1$) to propose commands in Phalanx-HS, the throughput of it is almost the same as HS. However, the latency of Phalanx-HS is 5.57% lower than HS, which is satisfying. It is mainly because that the main bottleneck of geo-distributed system is network communication and the order-batch which only contains the latest logs of each participant has reduced the volume of HS consensus proposal. Besides, each part of Phalanx (mempool, consensus, and executor) are running concurrently, which can make full use of computing resources. Then, we increase the number of proposers from 1 to 4, and also find that the throughput of Phalanx-HS increases in direct proportion to the number of proposers with barely changed latency in geo-distributed environment.

Table X shows the change of reordered commands ratio with the number of Byzantine nodes. If there is no adversary that $f=0$, no intuitively distinct context is broken. If there is one Byzantine node and follow the attacker’s ordering, then almost all the intuitively distinct contexts are destroyed. However, after the activation of Phalanx strategy, only almost every intuitively distinct context has been resisted. If the number of adversarial nodes is larger than the fault-tolerance threshold, we can find there are part of command pairs with intuitively distinct context have been reordered.

In this part, we compare the adversarial attack resistance ability between timestamp-based strategy and Phalanx. For Byzantine fault tolerance protocols, if the number of Byzantine nodes is no larger than the fault-tolerance threshold, we expect the intuitively distinct contexts should be preserved. Here, we do not implement a timestamp-based protocol[12][13]. We compare the Phalanx with timestamp-based strategy directly.

We deployed our evaluation on 16 nodes. Each Phalanx node ran on Aliyun ECS c7 with 8vCPU (Intel Xeon 8369B) and 16GiB memory. We inject codes to make some of them malicious and set 2 proposers. Increase the byzantine node number from 0 to threshold ($f=5$) and detect the ratio of commands which have been reordered. Here, let us consider that the system has resisted manipulation attack if the ratio of reordered commands is less than 0.5%. As is shown in Table XI, both Phalanx and timestamp-based strategy could reserve the intuitively distinct context without any Byzantine nodes. However, if there exists Byzantine nodes in current situation, the timestamp-based strategy sometimes cannot prevent manipulation attack, while Phalanx could still reverse intuitively distinct contexts.

To take further evaluation on adversary resistance, we deployed our evaluation on 34 nodes. Each Phalanx node ran on Aliyun ECS c7 with 4vCPU (Intel Xeon 8369B) and 8GiB memory. We also inject codes to make some of them malicious and set 2 proposers. Increase the byzantine node number from 0 to threshold ($f=11$) and detect the reordered commands ratio. As is shown in Fig 5, the probability of timestamp-based strategy causing command reordered which has destroyed intuitively distinct context is significantly higher than Phalanx. As the number of Byzantine nodes increases within the threshold, the commands ordered by timestamp-based strategy will be much easier to be attacked, while the reordered commands ratio through Phalanx does not increase rapidly. We found that the Phalanx performs better in resisting ordering manipulation than timestamp-based strategy.

Besides, we find that, whenever reordered commands ratio of Phalanx goes up, there are more anchor-sets selected through alter path. It is an attention-worth problem that can be further studied in the future.