Deterministic Blockchain BFT Protocol XP for Complete Asynchronous Networks

Abstract

Ethereum Research team has proposed a family of Casper blockchain consensus protocols for Ethereum 2.0. It has been shown in the literature that Casper Friendly Finality Gadget (Casper FFG) for Ethereum 2.0's beacon network cannot achieve liveness property in partially synchronous networks such as the Internet environment. The ``Correct-by-Construction'' family of Casper blockchain consensus protocols (CBC Casper) has been proposed as a finality gadget for the future release of Ethereum 2.0 blockchain. Unfortunately, neither constructive finality rule nor satisfactory liveness property has been obtained for CBC Casper, and it is commonly believed that CBC Casper could not achieve liveness property in asynchronous networks. This paper provides the first probabilistic CBC Casper protocol that achieves liveness property against \(t=\lfloor \frac{n-1}{3}\rfloor\) Byzantine participants in complete asynchronous networks. The seminal work by Fisher, Lynch, and Paterson (FLP) shows that there does not exist a deterministic BFT protocol in complete asynchronous networks against a single failure. Existing BFT protocols for complete asynchronous networks are all probabilistic which are based either on individual coin-flipping or on common coin-flipping. This paper proposes the first secure and deterministic leaderless blockchain BFT protocol XP against \(t=\lfloor \frac{n-1}{3}\rfloor\) Byzantine participants in complete asynchronous networks. This result does not contradict with FLP's impossibility results since XP leverages the total order properties of candidate blocks in blockchains (similar properties may not hold for general BFT application scenarios).