Need update.
Generally, a BFT (Byzantine Fault Tolerance) consensus algorithm concentrates on two properties, safety and liveness. Well, in the system on reality, we should also pay attention to the order of transactions, in which an incorrect order may make the tasks failed. For instance, here is an instant commodity trading system. In such a system, we should send a trading-transaction for it if we would like to buy something. After the process of this transaction, the commodity you prefer would be locked. When only one consumer is trying to buy one commodity and sending trading-transaction, it is easy to process. But if there are several people trying to buy one thing at the same time, a concurrency problem will occur, and the order of trading-transactions could decide who the commodity belongs to. In this situation, the order of transactions would be important for trading fairness.
With most BFT algorithm, especially the partially synchronous protocols, such as PBFT[1] [2] and HotStuff[3], we cannot deal with the problem about fairness of transaction order because of the proposal generation process. In most BFT protocols, a proposal is usually generated by one specific node, and the participants could only detect limited malicious manners of proposer, such as fork-attack or silence-attack. As the proposer could make a decision on the content of proposals, it could decide the order the transactions on purpose to make some of them failed, which cannot be detected as normal.
So that, in CRYPTO2020, [4] introduced a new kind of property for BFT called order-fairness, which indicates a trusted order for transactions. The author has also proposed a new class of consensus protocols called Aequitas, which are the first to achieve order-fairness in both synchronous and "asynchronous" situations. However, the Aequitas are difficult to implement, and there are not any experiments for the performance of them. To make it more practical, in OSDI2020, [5] proposed a consensus protocol called Pompe, which could also achieve the order-fairness under the partially synchronous BFT protocols, and did some experiments on it. But it is difficult for us to use Pompe in asynchronous situation, as the order of commands in it is decided by trusted-timestamp.
So that, we propose a brand-new protocol called Phalanx. It is an order-fairness byzantine fault tolerance protocol to achieve order-fairness property. It could become a plugin for most kinds of BFT protocol, which means a traditional BFT protocol could complete the order-fairness property easily with the accession of Phalanx. Besides, Phalanx has a higher maximum throughput and has lower latency while processing blocks with large size. We find that Phalanx has a more stable throughput if the cluster changes leader frequently.
[1] Castro M, Liskov B. Practical byzantine fault tolerance[C]//OSDI. 1999, 99(1999): 173-186. [2] Castro M, Liskov B. Practical Byzantine fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002, 20(4): 398-461. [3] Yin M, Malkhi D, Reiter M K, et al. Hotstuff: Bft consensus with linearity and responsiveness[C]//Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 2019: 347-356. [4] Kelkar M, Zhang F, Goldfeder S, et al. Order-fairness for byzantine consensus[C]//Annual International Cryptology Conference. Springer, Cham, 2020: 451-480. [5] Zhang Y, Setty S, Chen Q, et al. Byzantine Ordered Consensus without Byzantine Oligarchy[C]//14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20). 2020: 633-649.The development of BFT protocols, the importance for order-fairness property, and some research on it.
The proposer would like to generate command with the transactions it has received.
Each replica in phalanx cluster has a private-order for the commands. The private-order could be different from each other.
We can regard it as a fixed-leader BFT cluster in which we use a byzantine quorum system here to detect fork-attack.
While receiving a command from clients, the replica will assign a specific sequence number for it and generate pre-order to notify other participants.
- <PRE-ORDER i, n, d, command-d, pre-d, t>
While receiving a pre-order from other replica, verify it according to sequence number. We should make sure that the sequence number is increasing one by one, and then, send a signed vote back if the pre-order is valid.
- <VOTE i, d, sig>
The node waiting for quorum votes about its pre-order. If the votes has reached quorum size, aggregate them and generate a quorum-cert (QC) for pre-order, and broadcast order message. The node received order message would store it by order.
- <ORDER i, n, d, command-d, t, QC>
Interfaces for phalanx protocol that we could use them to make a traditional synchronous BFT protocol achieve order-fairness property.
It is used to generate a phalanx-proposal. The proposal here has a determined size.
It could be used to verify the validation of each proposal, including the aggregated signature and the sequential order the global consensus has found.
It is used to execute the phalanx-proposal after the BFT consensus. We should find the query stream at first which indicates the partial orders we should commit. When we execute phalanx proposals, we would generate a fairness order for the commands.
Proof for properties, safety, liveness and order-fairness.