Optimistic, Signature-Free Reliable Broadcast and Its Applications
Shrestha, N; Yu, Q; Kate, A; Losa, G; Nayak, K; Wang, X
Published in: Ccs 2025 Proceedings of the 2025 ACM Sigsac Conference on Computer and Communications Security
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 ⌈n+22 f −2 ⌉ 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 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.
