  Consensus is a fundamental building block for constructing reliable and
fault-tolerant distributed services. Many Byzantine fault-tolerant consensus
protocols designed for partially synchronous systems adopt a pessimistic
approach when dealing with adversaries, ensuring safety in a deterministic way
even under the worst-case scenarios that adversaries can create. Following this
approach typically results in either an increase in the message complexity
(e.g., PBFT) or an increase in the number of communication steps (e.g.,
HotStuff). In practice, however, adversaries are not as powerful as the ones
assumed by these protocols. Furthermore, it might suffice to ensure safety and
liveness properties with high probability. In order to accommodate more
realistic and optimistic adversaries and improve the scalability of the BFT
consensus, we propose ProBFT (Probabilistic Byzantine Fault Tolerance). ProBFT
is a leader-based probabilistic consensus protocol with a message complexity of
$O(n\sqrt{n})$ and an optimal number of communication steps that tolerates
Byzantine faults in permissioned partially synchronous systems. It is built on
top of well-known primitives, such as probabilistic Byzantine quorums and
verifiable random functions. ProBFT guarantees safety and liveness with high
probabilities even with faulty leaders, as long as a supermajority of replicas
is correct, and using only a fraction of messages employed in PBFT (e.g.,
$20\%$). We provide a detailed description of ProBFT's protocol and its
analysis.
