TraceBFT: Backtracking-Based Pipelined Asynchronous BFT Consensus for High-Throughput Distributed Systems

Asynchronous Byzantine fault tolerant (BFT) protocols are critical for robust decentralized systems, as they tolerate arbitrary network delays and resist adversarial attacks. However, existing asynchronous BFT protocols, such as those based on asynchronous binary agreement (ABA) or speeding multi-Valued Byzantine agreement (MVBA), face two key limitations: (1) additional communication costs due to repeated coin-flipping in ABA or leader crashes in sMVBA, and (2) insufficient throughput caused by serial transaction processing. For instance, sMVBA incurs re-execution overhead when leaders fail, while ABA introduces unpredictable rounds of coin-tossing to resolve conflicts. To addresses these inefficiencies, this paper proposes TraceBFT, a pipelined asynchronous BFT protocol. At its core lies trackMVBA, a novel backtracking-based MVBA protocol that reduces consensus latency to seven communication steps in the best case. By leveraging provable broadcast (PB) and a vector-linking mechanism, trackMVBA enables nodes to commit transactions via backtracking without restarting failed views. Building on this, TraceBFT introduces parallel execution of multiple views, allowing transactions from different views to be processed concurrently. This pipelined design eliminates redundant communication steps caused by leader failures or ABA’s coin inequality, significantly improving throughput. Theoretical analysis proves TraceBFT’s safety, liveness, and total order guarantees. Experimental evaluations against state-of-the-art protocols (e.g., HoneyBadgerBFT, Dumbo2, sDumbo) demonstrate its superior throughput under both favorable and adversarial conditions, while maintaining competitive latency. By decoupling view execution and minimizing rework, TraceBFT advances asynchronous BFT protocols toward practical high-throughput decentralized systems.