Fair transaction ordering protocols that guarantee γ-Batch-Order-Fairness are a leading defense against Maximal Extractable Value (MEV) attacks in Byzantine consensus and blockchain systems. All existing such protocols build a tournament dependency graph among transactions, incurring Θ(|T|2) comparator queries per round on a transaction set T, which becomes the dominant performance bottleneck.

We present Carry-the-Tail, the first deterministic atomic broadcast protocol in partial synchrony that, after GST, simultaneously guarantees two desirable properties: (i) a constant fraction of commits are proposed by non-faulty leaders against tail-forking attacks, and (ii) optimal, worst-case quadratic communication under a cascade of faulty leaders. The solution also guarantees linear amortized communication, i.e., the steady-state is linear. Combining these two desirable properties was not simultaneously achieved previously: on one hand, prior atomic broadcast solutions achieve per-view linear word communication complexity. However, they face a significant degradation in throughput under tail-forking attack. On the other hand, existing solutions to tail-forking attacks require either quadratic communication steps or computationally-prohibitive SNARK generation. The key technical contribution is Carry, a practical drop-in mechanism for streamlined protocols in the HotStuff family. Carry guarantees good performance against tail-forking and removes most leader-induced stalls, while retaining linear traffic and protocol simplicity. Carry-the-Tail implements the Carry mechanism on HotStuff-2.

This paper introduces HotStuff-1, a BFT consensus protocol that improves the latency of HotStuff-1 by two network hops while maintaining linear communication complexity against faults. Furthermore, HotStuff-1 incorporates an incentive-compatible leader rotation design that motivates leaders to propose transactions promptly. HotStuff-1 achieves a reduction of two network hops by speculatively sending clients early finality confirmations, after one phase of the protocol. Introducing speculation into streamlined protocols is challenging because, unlike stable-leader protocols, these protocols cannot stop the consensus and recover from failures. Thus, we identify prefix speculation dilemma in the context of streamlined protocols; HotStuff-1 is the first streamlined protocol to resolve it. HotStuff-1 embodies an additional mechanism, slotting , that thwarts delays caused by (1) rationally-incentivized leaders and (2) malicious leaders inclined to sabotage others' progress. The slotting mechanism allows leaders to dynamically drive as many decisions as allowed by network transmission delays before view timers expire, thus mitigating both threats.

The emergence of blockchain technology has renewed the interest in consensus-based data management systems that are resilient to failures. To maximize the throughput of these systems, we have recently seen several prototype consensus solutions that optimize for throughput at the expense of overall implementation complexity, high costs, and reliability. Due to this, it remains unclear how these prototypes will perform in real-world environments. In this paper, we present SpotLess, a novel concurrent rotational consensus protocol made practical. Central to SpotLess is the combination of (1) a chained rotational consensus design for replicating requests with a reduced message cost and low-cost failure recovery that eliminates the traditional complex, error-prone view-change protocol; (2) the novel Rapid View Synchronization protocol that enables SpotLess to work in more general network assumptions, without a need for a Global Synchronization Time to synchronize view, and recover valid earlier views with the aid of non-faulty replicas without the need to rely on the primary; (3) a high-performance concurrent consensus architecture in which independent instances of the chained consensus operate concurrently to process requests with high throughput, thereby avoiding the bottlenecks seen in other rotational protocols. Due to the concurrent consensus architecture, SpotLess greatly outperforms traditional primary-backup consensus protocols such as Pbft (by up to 430%), Narwhal-HS (by up to 137%), and HotStuff (by up to 3803%). Due to its reduced message cost, SpotLess is even able to outperform RCC, a state-of-the-art high-throughput concurrent consensus protocol, by up to 23%. Furthermore, SpotLess is able to maintain a stable and low latency and consistently high throughput even during failures.