Trebiz: Byzantine Fault Tolerance with Byzantine Merchants

The popularity of blockchain technology has revived interest in Byzantine Fault Tolerance (BFT) consensus protocols. However, existing protocols suffer from high latency, especially when the system is deployed in a worldwide manner. Taking Practical Byzantine Fault Tolerance (PBFT), the best-known and de-facto standard of BFT consensus protocol, as an example, it requires at least three phases to commit a request. Although some works attempt to shorten the number of phases by proposing a fast-path commitment rule, they either sacrifice resilience or subvert security. In this paper, we propose Trebiz, which also absorbs the fast-path commitment rule to reduce the number of phases from three to two, but maintains optimal resilience and strong security. This is achieved based on a re-understanding of the fault model in the blockchain era. Due to the financial benefits in the blockchain system, a replica may strive to keep the system running if it is impossible to tamper with a committed request. Therefore, we divide Byzantine replicas into two categories: Byzantine General (BG) and Byzantine Merchant (BM). BG replicas will strive to break both safety and liveness as traditional Byzantine ones, while BM replicas will only break safety but maintain liveness. Furthermore, we divide BM replicas into two sub-categories: active (ABM) and passive (PBM), according to whether they will forge and send unreceived data to maintain liveness. Given a system consisting of n= replicas, Trebiz enables a request to be committed with prepare messages in the second phase, where na and np represent the numbers of ABM and PBM replicas. During the view-change process, the leader can expect to receive view-change messages, which guarantees safety and liveness. Since up to f Byzantine replicas can be tolerated, Trebiz still achieves the optimal resilience of ⌈n/3⌉-1. Extensive experiments are conducted to demonstrate Trebiz’s feasibility and efficiency.