Optimistic, Signature-Free Reliable Broadcast and Its Applications

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 ƒ < n/3 Byzantine faults, where n is the number of parties. In this work, we propose an optimistic RBC protocol that maintains the ƒ < n/3 fault tolerance but achieves termination in just 2 steps under certain optimistic conditions—when at least ⌉n+2 ƒ-2 over -2 ⌈ non-broadcaster parties behave honestly. We also prove a matching lower bound on the number of honest parties required for 2-step termination.