Optimistic, Signature-Free Reliable Broadcast and Its Applications
For fault-tolerant distributed systems, this work reduces latency of reliable broadcast and related primitives under optimistic conditions, offering practical efficiency gains for applications like blockchain consensus.
This paper proposes an optimistic signature-free reliable broadcast protocol that achieves 2-step termination under optimistic conditions (when enough non-broadcaster parties are honest), improving upon the optimal 3 steps of existing protocols. The technique is generalized to other primitives and integrated into a DAG-based BFT consensus protocol (Sailfish++), which under optimistic conditions achieves 3-step commit latency, outperforming existing post-quantum secure and signature-based protocols in experiments.
Reliable broadcast (RBC) is a key primitive in fault-tolerant distributed systems, and improving its efficiency can benefit a wide range of applications. This work focuses on signature-free RBC protocols, which are particularly attractive due to their computational efficiency. Existing protocols in this setting incur an optimal 3 steps to reach a decision while tolerating up to $f < n/3$ Byzantine faults, where $n$ is the number of parties. In this work, we propose an optimistic RBC protocol that maintains the $f < n/3$ fault tolerance but achieves termination in just 2 steps under certain optimistic conditions--when at least $\lceil \frac{n+2f-2}{2} \rceil$ non-broadcaster parties behave honestly. We also prove a matching lower bound on the number of honest parties required for 2-step termination. We show that our latency-reduction technique generalizes beyond RBC and applies to other primitives such as asynchronous verifiable secret sharing (AVSS) and asynchronous verifiable information dispersal (AVID), enabling them to complete in 2 steps under similar optimistic conditions. To highlight the practical impact of our RBC protocol, we integrate it into Sailfish++, a new signature-free, post-quantum secure DAG-based Byzantine fault-tolerant (BFT) consensus protocol. Under optimistic conditions, this protocol achieves a commit latency of 3 steps--matching the performance of the best signature-based protocols. Our experimental evaluation shows that our protocol significantly outperforms existing post-quantum secure and signature-based protocols, even on machines with limited CPU resources. In contrast, signature-based protocols require high CPU capacity to achieve comparable performance. We have open-sourced our Rust implementation of Sailfish++ to facilitate reproducible results.