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 the best-known and de-facto standard of BFT consensus, namely Practical Byzantine Fault Tolerance (PBFT), as an example, it requires at least three phases to commit a request. Although there are already some works attempting to shorten the number of phases from three to two, 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, but achieves optimal resilience and strong security. This is done based on a re-understanding of the fault model in the blockchain era. Due to the financial benefits on the blockchain system, replicas will strive to keep the system running if it is impossible to tamper with a committed request. In this regard, we divide Byzantine replicas into two categories: Byzantine General (BG) and Byzantine Merchant (BM). BM replicas will try to 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 3𝑓 +1 replicas, Trebiz enables a request to be committed with 3𝑓 +1-𝑛𝑎 -⌊𝑛𝑝 /2⌋ prepare messages in the second phase, where 𝑛𝑎 and 𝑛𝑝 represent the numbers of ABM and PBM replicas respectively. During the process of view change, a replica in Trebiz can expect to receive 2𝑓 +1+𝑛𝑎 +𝑛𝑝 view-change messages, which guarantees safety and liveness. Since at most 𝑓 Byzantine replicas can be tolerated, Trebiz still achieves the optimal resilience of ⌈𝑛/3⌉ − 1. Extensive experiments are conducted to compare the performance between Trebiz and PBFT, whose results demonstrate Trebiz’s feasibility and efficiency.

Paper (ACM DL)

Slides