Byzantine atomic broadcast (ABC) is at the heart of permissioned blockchains and various multi-party computation protocols. We resolve a long-standing open problem in ABC, presenting the first signature-free asynchronous ABC protocol that achieves optimal$O(n^{2})$messages and$O(1)$expected time, where$n$is the total number of replicas. Our ABC protocol adopts a new design, relying on a reduction from-perhaps surprisingly-a somewhat neglected primitive called multivalued Byzantine agreement (MBA).

State-of-the-art Byzantine fault-tolerant (BFT) protocols assuming partial synchrony such as SBFT and HotStuff use regular certificates obtained from 2f + 1 (partial) signatures. We show that one can use weak certificates obtained from only f + 1 signatures to assist in designing more robust and more efficient BFT protocols. We design and implement two BFT systems: Dashing (a family of two HotStuff-style BFT protocols) and Star (a parallel BFT framework).

We provide an expressive framework that allows analyzing and generating provably secure, state-of-the-art Byzantine fault-tolerant (BFT) protocols over graph of nodes, a notion formalized in the HotStuff protocol. Our framework is hierarchical, including three layers. The top layer is used to model the message pattern and abstract core functions on which BFT algorithms can be built. The intermediate layer provides the core functions with high-level properties sufficient to prove the security of the top-layer algorithms. The bottom layer presents operational realizations for the core functions. Using our framework, designing a BFT protocol is reduced to instantiating two core functions together with their specific properties. Unlike prior BFT frameworks, our framework can analyze and recast BFT protocols in an exceedingly fine-grained manner. More importantly, our framework can readily generate new BFT protocols. In this paper, we show that the framework allows us to fully specify and formally prove the security for a family of BFT protocols, including known protocols such as HotStuff, Fast-HotStuff, and SBFT. Additionally, we show that our framework can generate four new protocols outperforming existing ones, including 1) two protocols with$5f+1$replicas achieving optimal message complexity; 2) the first BFT protocol achieving optimal message complexity with$4f+1$replicas; and 3) a two-phase protocol with$3f+1$replicas achieving linear authenticator complexity in the fast path.

As the first Byzantine fault-tolerant (BFT) protocol with linear communication complexity, HotStuff (PODC 2019) has received significant attention. HotStuff has three round-trips for both normal case operations and view change protocols. Follow-up studies attempt to reduce the number of phases for HotStuff. These protocols, however, all give up of one thing in return for another.This paper presents Marlin, a BFT protocol with linearity, having two phases for normal case operations and two or three phases for view changes. Marlin uses the same cryptographic tools as in HotStuff and introduces no additional assumptions. We implement a new and efficient Golang library for Marlin and HotStuff, showing Marlin outperforms HotStuff for both the common case and the view change.