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.