# Probabilistic Byzantine Fault Tolerance (Extended Version)

Diogo Avelãs  LASIGE, Faculdade de Ciências, Universidade de LisboaPortugal
<EMAIL_ADDRESS>https://orcid.org/0009-0004-5838-1667 ,  Hasan Heydari
LASIGE, Faculdade de Ciências, Universidade de LisboaPortugal
<EMAIL_ADDRESS>https://orcid.org/0000-0003-2309-2457 ,  Eduardo
Alchieri  Universidade de BrasiliaBrasil<EMAIL_ADDRESS>https://orcid.org/0000-0002-6022-3631 ,  Tobias Distler  Friedrich-Alexander-
Universität Erlangen-NürnbergGermany<EMAIL_ADDRESS>https://orcid.org/0000-0002-2440-5366 and  Alysson Bessani  LASIGE, Faculdade
de Ciências, Universidade de LisboaPortugal<EMAIL_ADDRESS>https://orcid.org/0000-0002-8386-1628

(2024)

###### Abstract.

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 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. To accommodate more realistic and optimistic
adversaries and improve the scalability of 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 probability
even with faulty leaders, as long as a supermajority of replicas is correct
and using only a fraction (e.g., $20\%$) of messages exchanged in PBFT. We
provide a detailed description of ProBFT’s protocol and its analysis.

Byzantine fault-tolerance, Consensus, Probabilistic protocols, Byzantine
quorum systems

††journalyear: 2024††copyright: rightsretained††conference: ACM Symposium on
Principles of Distributed Computing; June 17–21, 2024; Nantes,
France††booktitle: ACM Symposium on Principles of Distributed Computing (PODC
’24), June 17–21, 2024, Nantes, France††doi: 10.1145/3662158.3662810 ††isbn:
979-8-4007-0668-4/ 24/06††ccs: Computing methodologies Distributed
algorithms††ccs: Computer systems organization Dependable and fault-tolerant
systems and networks

##  1\. Introduction

#### Context

Consensus is a fundamental building block for constructing reliable and fault-
tolerant distributed services, where participants agree on a common value from
the initially proposed values. This problem is primarily used to implement
state machine replication (Schneider, 1990; Sousa and Bessani, 2012; Distler,
2021) and atomic broadcast (Luan and Gligor, 1990; Hadzilacos and Toueg, 1994;
Pedone and Schiper, 1998), and attracted considerable attention in the last
few years, mainly due to its significant role in blockchains (Vukolić, 2015;
Nakamoto, 2008; Bessani et al., 2020) and decentralized payment systems (e.g.,
(Lokhava et al., 2019)). Due to its importance and widespread applicability,
consensus has been extensively studied in diverse system models, considering
various synchrony assumptions and a spectrum of failure models, ranging from
fail-stop to Byzantine, across permissioned and permissionless settings (Pass
and Shi, 2017; Li et al., 2023; Cachin et al., 2022; Vassantlal et al., 2023).

Many Byzantine fault-tolerant (BFT) consensus protocols (e.g., PBFT (Castro
and Liskov, 1999) and HotStuff (Yin et al., 2019)111Strictly speaking, PBFT
(Castro and Liskov, 1999) and HotStuff (Yin et al., 2019) are state machine
replication protocols, not consensus protocols. In this paper, when we refer
to PBFT and HotStuff, we specifically discuss the single-shot versions of
these protocols presented in (Bravo et al., 2022), which address the consensus
problem.) adopt a pessimistic approach when dealing with Byzantine
participants and adversaries, ensuring the safety of protocols even when
Byzantine participants behave completely arbitrarily under the worst-case
scenarios that corruption and scheduling adversaries can create. That is, they
typically consider adversaries that choose a corruption strategy and
manipulate the delivery time of messages based on the entire history of the
system, including the past and current states of replicas, as well as their
exchanged messages.

Protocols following the pessimistic approach are built on the idea of  (1)
making non-revocable decisions by considering the opinions of a quorum of
replicas, as opposed to relying solely on a single replica, and  (2) requiring
the quorums used for making decisions to intersect in at least one correct
replica.  Although effective, ensuring deterministic quorum overlaps poses
inherent challenges in achieving both resource efficiency and high
performance. Some protocols (e.g., PBFT) approach this conflict by opting for
low latency and applying message-exchange patterns with quadratic message
complexity. However, this can be prohibitively expensive, especially for BFT
systems with a large number of replicas. Other protocols (e.g., HotStuff) aim
at reducing message complexity at the cost of adding extra communication
steps. Unfortunately, this approach leads to increased end-to-end response
times.

In practice, however, implementing punishment mechanisms, like those used in
existing Proof-of-Stake blockchains (e.g., (Buterin and Griffith, 2019; Cason
et al., 2021)), can make it costly for Byzantine participants to deviate from
its specification, knowing that their actions may lead to detection and
subsequent punishment. Besides, adversaries are not as powerful as the ones
assumed by protocols following the pessimistic approach. Accordingly, in many
real-world applications, it is sufficient to assume a static corruption
adversary, which chooses a corruption strategy at the beginning of the
execution of a consensus instance, as well as an adversarial scheduling that
manipulates the delivery time of messages independently of the sender’s
identifier and if it is faulty or not. Given this, ensuring safety and
liveness with a high probability might be acceptable in many practical
scenarios. This paper describes a new protocol for these less pessimistic
practical scenarios that requires less message exchanges and still keeps
optimal latency. This protocol is called ProBFT (Probabilistic Byzantine Fault
Tolerance).

#### Overview of ProBFT

ProBFT is a BFT leader-based consensus protocol that operates in permissioned
partially synchronous systems and probabilistically ensures liveness and
safety properties. It achieves the optimal _good-case latency_ of three
communication steps (Abraham et al., 2021), just like PBFT, albeit with a
message complexity of $O(n\sqrt{n})$. Figure 1(b) compares ProBFT, PBFT, and
HotStuff in terms of the number of communication steps and exchanged messages
for different numbers of replicas. ProBFT’s resource efficiency and
scalability improvements are enabled by a unique combination of building
blocks that are usually not employed in traditional BFT protocols, including
probabilistic quorum systems (Malkhi et al., 2001), a mechanism to configure
the degree of communication redundancy, and a verifiable random function (VRF)
(Micali et al., 1999).

(a) Message pattern and number of communication steps.

(b) Number of exchanged messages.

Figure 1. Comparing the normal case of three consensus protocols – PBFT,
ProBFT, and HotStuff – regarding the number of communication steps and message
complexity.

[]

Like PBFT and HotStuff, ProBFT operates in a sequence of views, each having a
designated leader responsible for proposing a value. The protocol consists of
two modes of execution – normal case and view-change. The normal case starts
when the leader broadcasts its proposal through a Propose message. Since the
leader might be Byzantine and send distinct proposals to different replicas,
non-Byzantine replicas need to communicate with each other to check that they
received the same proposal. With this aim, upon receiving a Propose message, a
correct replica multicasts the proposal to a sample of $o\times q$ distinct
replicas taken uniformly at random from the set of replicas, where
$q=O(\sqrt{n})$ and $o>1$ is a real constant. Upon receiving Prepare messages
from a probabilistic quorum with size $q$, a correct replica multicasts a
Commit message to another random sample composed of $o\times q$ distinct
replicas. Upon receiving Commit messages from a probabilistic quorum with size
$q$, a correct replica decides on the proposed value.

ProBFT’s normal case execution relies on probabilistic quorums to solve
consensus. That is, in contrast to traditional BFT protocols (e.g., PBFT,
HotStuff, and randomized protocols like (Cachin et al., 2000; Mostéfaoui et
al., 2015)), we abandon the requirement of quorums strictly having to
intersect and instead only aim at quorums overlapping with high probability.
As a key benefit, this strategy enables us to keep the number of communication
steps at a minimum while significantly reducing quorum sizes, thereby
improving resource consumption and scalability. Specifically, for a system
with $n$ replicas, ProBFT employs probabilistic quorums of size $q=l\sqrt{n}$,
with $l\geq 1$ being a configurable, typically small constant (Malkhi et al.,
2001). For example, for $l=2$ and $n=100$, a replica can make progress after
receiving $20$ matching messages from different replicas, which is a
significant reduction when compared with the $67$ messages necessary in PBFT.

Since a comparably small number of messages is sufficient to advance a phase
in ProBFT, to offer resilience against Byzantine behavior, it is crucial to
prevent faulty replicas from manipulating the decisions in probabilistic
quorums (e.g., by flooding the system with their own messages). In ProBFT,
this is achieved by delegating the selection of message recipients to a
globally known VRF. That is, in the protocol phases relying on probabilistic
quorums, replicas do not freely pick the destinations of their messages but
instead are required to send the messages to the specific group of recipients
determined by the VRF.

Although novel, ProBFT is heavily based on PBFT, being thus somewhat simple to
understand and implement. Nonetheless, the probabilistic nature of the
protocol makes its analysis far from trivial. More specifically, the main
challenges encountered in analyzing ProBFT are:

  * –

In the analysis of probabilistic algorithms, we often deal with _independent_
events, enabling the application of powerful and more straightforward bounds
like the Chernoff bounds (Motwani and Raghavan, 1995). However, in ProBFT, the
probability of forming probabilistic quorums by replicas is _dependent_. That
is, as replicas multicast their Prepare (resp., Commit) messages to random
samples, knowing that a replica has received Prepare (resp., Commit) messages
from a probabilistic quorum decreases the chance of other replicas to receive
Prepare (resp., Commit) messages from a probabilistic quorum. This dependency
complicates ProBFT’s analysis.

  * –

The probability of deciding a value by a replica depends on the number of
replicas that multicast matching Commit messages. Additionally, the number of
replicas that multicast their Commit messages depends on the number of
replicas that multicast their Prepare messages. This dual dependency layer for
computing the probability of deciding a value by a replica adds complexity to
the analysis of ProBFT.

  * –

A Byzantine leader might send multiple proposals to violate safety. Rather
than examining each possible case individually, we find the optimal behavior
for a Byzantine leader, considering that it intends to maximize the
probability of safety violation.

In summary, besides the design of ProBFT, the main technical contribution of
this paper is the analysis of the protocol, represented by the following
theorem:

###### Theorem 1 (Informal main result).

ProBFT guarantees liveness with probability $1$ and safety with a probability
of $1-\mathit{exp}(-\Theta(\sqrt{n}))$.

#### Paper organization

The remainder of the paper is organized as follows. Section 2 introduces our
system model and describes the key techniques employed in ProBFT. Section 3
describes the ProBFT protocol. Section 4 presents the correctness proofs of
ProBFT. Section 5 presents a numerical analysis of the protocol. Finally,
Sections 6 and 7 discuss related work and conclude the paper, respectively.

##  2\. Preliminaries

###  2.1. System Model

We consider a distributed system composed of a finite set $\Pi$ of $n$
processes, which we call replicas, among which up to $f<n/3$ might be subject
to Byzantine failures (Lamport et al., 1982) and not behave according to the
protocol specification. A non-faulty replica is said to be correct. During
execution, we denote by $\Pi_{C}$ and $\Pi_{F}$ the sets of correct and faulty
replicas, respectively. The system is partially synchronous (Dwork et al.,
1988; Bravo et al., 2022) in which the network and replicas may operate
asynchronously until some _unknown global stabilization time_ GST, after which
the system becomes synchronous, with unknown time bounds for communication and
computation.

We assume that each replica has a unique ID, and it is infeasible for a faulty
replica to obtain additional IDs to launch a _Sybil attack_ (Douceur, 2002).
We consider a _static corruption adversary_ , i.e., $\Pi_{F}$ is fixed at the
beginning of execution by the adversary. Byzantine replicas may collude and
coordinate their actions. It is important to note that while Byzantine
replicas may be aware of $\Pi_{F}$, the correct replicas are unaware of
$\Pi_{F}$ and only know the value of $f$. Furthermore, we assume an
adversarial scheduler that manipulates the delivery time of messages
independent of the sender’s identifier, its past and current states, and
whether it is Byzantine or not.

Each replica signs outgoing messages with its private key and only processes
an incoming message if the message’s signature can be verified using the
sender’s public key. We denote $\langle\textsc{T},m\rangle_{i}$ as a message
of type T with content $m$ signed by replica $i$. We assume that the
distribution of keys is performed before the system starts. At run-time, the
private key of a correct replica never leaves the replica and, therefore,
remains unknown to faulty replicas. In contrast, faulty replicas might learn
the private keys of other faulty replicas. In practical settings, it is a
standard assumption that the adversary does not have unlimited computational
resources; therefore, they cannot break cryptographic primitives.

###  2.2. Consensus

We assume there is an application-specific $\mathtt{valid}$ predicate to
indicate whether a value is acceptable (Bravo et al., 2022; Cachin et al.,
2001; Sousa and Bessani, 2012). Assuming that each correct replica proposes a
valid value, any protocol that solves probabilistic consensus satisfies the
following properties:

  * –

Validity. The value decided by a correct replica satisfies the application-
defined valid predicate.

  * –

Probabilistic Agreement. Any two correct replicas decide on different values
with probability $\rho$ depending on the number of existing Byzantine replicas
and quorum/sample sizes.

  * –

Probabilistic Termination. Every correct replica decides with probability $1$.

The first two properties are safety properties, while the last one is a
liveness property.

###  2.3. Single-shot PBFT

Since ProBFT follows a structure very similar to PBFT (Castro and Liskov,
1999), we briefly review the single-shot version of the latter considering the
use of a _synchronizer_ (Bravo et al., 2022). This version is a leader-based
consensus protocol that operates in a succession of views produced by the
synchronizer, each having a designated leader defined in a round-robin way.
Each protocol view consists of three steps and works as follows (see Figure
2):

  * –

Propose (or pre-prepare) phase. The leader of view $v$ is responsible for
proposing a value to the other replicas. With this aim, the leader broadcasts
a value through a Propose message. A correct leader must carefully choose the
value to ensure that if a correct replica has decided on a value in a previous
view, it will propose the same value.

  * –

Prepare phase. Upon receiving a Propose message from a replica $i$ in view
$v$, a correct replica broadcasts a Prepare message if $i$ is the leader of
$v$, and the proposed value is a valid proposal.

  * –

Commit phase. Upon receiving Prepare messages from a quorum of replicas, a
correct replica broadcasts a Commit message.

A replica decides the value proposed by the leader upon receiving Commit
messages from a quorum of replicas. There are multiple scenarios where
replicas cannot decide a value in a view $v$, like when the leader is
Byzantine and remains silent. In those scenarios, the synchronizer transitions
the view from $v$ to $v+1$, changing the designated leader.

###  2.4. Verifiable Random Function

A _verifiable random function_ (VRF) (Gilad et al., 2017; Goldberg et al.,
2022) enables the random selection of a subset from a given set, ensuring that
the selection process is verifiable and secure. We assume a globally known VRF
that provides the following two operations:

Figure 2. Overview of PBFT. Each correct replica broadcasts its Prepare and
Commit messages. The size of any quorum is $|Q|=\lceil{(n+f+1)/2}\rceil$. The
set of replicas $I$ in the intersection of two quorums contains at least one
correct replica.

[]Overview of PBFT. Each correct replica broadcasts its Prepare and Commit
messages. The size of any quorum is $|Q|=\lceil{(n+f+1)/2}\rceil$. The set of
replicas $I$ in the intersection of two quorums contains at least one correct
replica.

  * –

VRF_prove($K_{p,i}$, $z$, $s$) $\Rightarrow$ $S_{i}$, $P_{i}$. Given the
private key $K_{p,i}$ for a replica $i$, a seed $z$, and a positive integer
$s$, VRF_prove selects a sample $S_{i}$ containing the IDs of $s$ distinct
replicas uniformly at random. Along with $S_{i}$, this operation returns a
proof $P_{i}$, enabling other replicas to verify whether the sample was
obtained using this operation.

  * –

VRF_verify($K_{u,i}$, $z$, $s$, $S_{i}$, $P_{i}$) $\Rightarrow$ bool. Given
the public key $K_{u,i}$ of replica $i$, a seed $z$, a positive integer $s$, a
sample $S_{i}$, and its associated proof $P_{i}$, VRF_verify determines
whether $S_{i}$ is a valid sample generated using VRF_prove with the given
parameters. It returns true if the sample and proof are valid and false
otherwise.

The VRF should provide the following guarantees (Goldberg et al., 2022):

  * –

Uniqueness. A computationally limited adversary must not be able to produce
two different proofs $P_{i}$ and $P_{i}^{\prime}$ for the same input
parameters $K_{u,i}$, $z$, and $s$.

  * –

Collision resistance. Even when a private key is compromised, it should be
infeasible for an adversary to find two distinct seeds $z$ and $z^{\prime}$
for which the VRF_prove returns the same sample.

  * –

Pseudorandomness. For an adversarial verifier without knowledge of the proof,
the corresponding sample should be indistinguishable from a randomly selected
set of replica IDs.

##  3\. ProBFT

Figure 3. Overview of ProBFT. The size of any probabilistic quorum is
$q=|Q|=O(\sqrt{n})$. Each correct replica multicasts its Prepare and Commit
messages to random samples of sizes $o\times q$, where $o$ is a constant. The
set of replicas $\bar{I}$ in the intersection of two probabilistic quorums
contains at least one correct replica with high probability.

[]Overview of ProBFT. The size of any probabilistic quorum is
$q=|Q|=O(\sqrt{n})$. Each correct replica multicasts its Prepare and Commit
messages to random samples of sizes $o\times q$, where $o$ is a constant. The
set of replicas $\bar{I}$ in the intersection of two probabilistic quorums
contains at least one correct replica with high probability.

###  3.1. Overview

ProBFT is a leader-based probabilistic consensus protocol that operates in a
succession of views produced by the synchronizer. In ProBFT, illustrated in
Figure 3, one of the replicas is assigned the role of _leader_ in each view,
meaning that this replica is in charge of proposing a value. ProBFT’s
consensus process comprises three phases of message exchange between replicas
– _propose_ , _prepare_ , and _commit_ , just like in PBFT. In the _propose_
phase, the leader proposes a value by broadcasting it to other replicas, which
is then agreed on in the subsequent _prepare_ and _commit_ phases.

Given the linear message complexity of the _propose_ phase, we restrict the
utilization of probabilistic quorums to the two remaining phases. That is, in
each of the _prepare_ and _commit_ phases, any replica relies on the VRF to
determine a subset of replicas with size $o\times q$ to whom its messages
should be sent, where $o>1$ is a constant. Any replica progresses by receiving
messages from a probabilistic quorum with size $q=l\sqrt{n}$, being $l$ also a
small constant (e.g., $2$). The constant $o$ defines how large the random
subset of replicas contacted on each phase by each replica is when compared
with the probabilistic quorum size. Bigger values of $o$ increase the
probability of forming a probabilistic quorum (with $q$ replicas), increasing
the chance of the protocol to terminate (see Section 4), albeit generating
more messages (see Figure 1(b)). As a result, in contrast to the $O(n^{2})$
communication complexity associated with traditional protocols such as PBFT,
ProBFT’s message complexity for the _prepare_ and _commit_ phases is
$O(n\sqrt{n})$.

As seed for computing its recipient sample with the VRF, a replica is required
to use $v$ $||$ T, which is a concatenation of the current view $v$, and an
identifier T representing the phase/message type (“prepare” for Prepare and
“commit” for Commit). Each replica starts a _prepare_ phase upon receiving the
leader’s proposal and a _commit_ phase upon forming a probabilistic quorum,
i.e., receiving $q$ matching messages. Forcing replicas to involve the VRF
this way and thereby apply deterministic seeds has the following key benefits:

  1. (1)

With the inputs of VRF_prove being dictated by the protocol, faulty replicas
cannot control their recipient sample for a particular view and phase.
Consequently, a faulty replica cannot deliberately favor a certain subset of
replicas, for example, in support of a faulty leader trying to trick these
replicas into forming a probabilistic quorum for a specific value.

  2. (2)

Since a replica’s recipient samples are computed from its private key (see
Section 2.4), faulty replicas cannot predict the individual samples of correct
replicas in advance. That is, at the start of a view, faulty replicas do not
know the upcoming _prepare_ and _commit_ phase message-exchange patterns
between correct replicas, thereby making it inherently difficult for them to
identify promising attack targets (e.g., correct replicas that are included in
none or only in a few recipient samples of other correct replicas).

  3. (3)

With the _prepare_ and _commit_ phase recipient samples usually differing (due
to the use of the phase parameter in the seed), correct replicas are more
likely to observe the misbehavior of a faulty leader. For example, if a faulty
leader performs equivocation by proposing different values to different
subsets of replicas, then the phase-specific recipient samples increase the
probability of a correct replica learning about the existence of contradictory
proposals.

In summary, the use of the VRF for selecting recipient samples in the
_prepare_ and _commit_ phases significantly strengthens ProBFT’s resilience
against malicious behaviors.

###  3.2. Protocol Specification

Algorithm 1 presents ProBFT specification. This description assumes a
synchronizer exactly like the one presented in (Bravo et al., 2022).

Algorithm 1 ProBFT – replica $i$.

1:upon newView($v$)

2:$\mathit{curView},\mathit{curVal},\mathit{voted},\mathit{blockView},\mathit{proposal}\leftarrow
v,\bot,\mathtt{false},\mathtt{false},\perp$

3:if $\mathit{curView}=1\land i=\mathtt{leader}(\mathit{curView})$

4: broadcast
$\langle\textsc{Propose},\langle\mathit{curView},\mathtt{myValue}()\rangle_{i},\perp\rangle_{i}$

5:else if $\mathit{curView}>1$

6: send
$\langle\textsc{NewLeader},\mathit{curView},\mathit{preparedView},\mathit{preparedVal},\mathit{cert}\rangle_{i}$
to $\mathtt{leader}(\mathit{curView})$

7: upon receiving
$\\{\langle\textsc{NewLeader},v,\mathit{view}_{j},\mathit{val}_{j},\mathit{cert}_{j}\rangle_{j}:j\in
Q\\}=M$ from a deterministic quorum $Q$

8:pre: $\mathit{curView}=v\land i=\mathtt{leader}(v)\land(\forall m\in
M:\mathtt{validNewLeader}(m))$

9:$v_{\mathit{max}}\leftarrow\mathtt{max}\\{\mathit{view}_{j}:\langle\textsc{NewLeader},v,\mathit{view}_{j},\\_,\\_\rangle_{j}\in
M$}

10:$\mathit{val}_{\mathit{max}}=\mathtt{mode}\\{\mathit{val}_{j}:\langle\textsc{NewLeader},v,v_{\mathit{max}},\mathit{val}_{j},\\_\rangle_{j}\in
M\\}$

11:if $\mathit{val}_{\mathit{max}}\neq\bot$

12: broadcast $\langle\textsc{Propose},\langle
v,\mathit{val}_{\mathit{max}}\rangle_{i},M\rangle_{i}$

13:else

14: broadcast $\langle\textsc{Propose},\langle
v,\mathtt{myValue}()\rangle_{i},M\rangle_{i}$

15: upon receiving $\langle\textsc{Propose},\langle
v,x\rangle_{j},\\_\rangle_{j}=m$

16:pre:
$\mathit{blockView}=\mathtt{false}\land\mathit{curView}=v\land\mathit{voted}=\mathtt{false}\land\mathtt{safeProposal}(m)$

17:$\mathit{curVal},\mathit{voted},\mathit{proposal}\leftarrow
x,\mathtt{true},m$

18:$S_{p},P_{p}\leftarrow\mathtt{VRF\\_prove}(K_{p,i},v\;||\;``\text{prepare}",o\times
q)$

19:send $\langle\textsc{Prepare},\langle
v,x\rangle_{j},S_{p},P_{p}\rangle_{i}$ to $S_{p}$

20: upon receiving $\\{\langle\textsc{Prepare},\langle
v,x\rangle_{*},S,P\rangle_{j}:j\in Q\\}=C$ from a probabilistic quorum $Q$

21:pre:
$\mathit{blockView}=\mathtt{false}\land\mathit{curView}=v\land\mathit{curVal}=x\land\mathit{voted}=\mathtt{true}\
\land$

22:$(\forall\langle\\_,\\_,S,P\rangle_{j}\in C:i\in
S\land\mathtt{VRF\\_verify}(K_{u,j},v\ ||\ ``\text{prepare}",o\times q,S,P))$

23:$\mathit{preparedVal},\mathit{preparedView},\mathit{cert}\leftarrow\mathit{curVal},\mathit{curView},C$

24:$S_{c},P_{c}\leftarrow\mathtt{VRF\\_prove}(K_{p,i},v\ ||\
``\text{commit}",o\times q)$

25:send $\langle\textsc{Commit},\langle v,x\rangle_{*},S_{c},P_{c}\rangle_{i}$
to $S_{c}$

26: upon receiving $\\{\langle\textsc{Commit},\langle
v,x\rangle_{*},S,P\rangle_{j}:j\in Q\\}=M$ from a probabilistic quorum $Q$

27:pre:
$\mathit{blockView}=\mathtt{false}\land\mathit{preparedVal}=x\land\mathit{curView}=\mathit{preparedView}=v\
\land$

28:$(\forall\langle\\_,\\_,S,P\rangle_{j}\in M:i\in
S\land\mathtt{VRF\\_verify}(K_{u,j},v\ ||\ ``\text{commit}",o\times q,S,P))$

29:$\mathtt{decide}(\mathit{\mathit{curVal}})$

30: upon receiving $\langle\\_,\langle v,x\rangle_{j},\dots\rangle_{*}=m$

31:pre: $\mathit{blockView}=\mathtt{false}\land\mathit{curView}=v\land
j=\mathtt{leader}(v)\land\mathit{voted}=\mathtt{true}\land\mathit{curVal}\neq
x$

32:$\mathit{blockView}\leftarrow\mathtt{true}$

33:broadcast $m$, broadcast $\mathit{proposal}$

The protocol proceeds in a series of views, with each new view having a fixed
leader responsible for proposing a value to be decided. Every replica in the
system can determine the leader for a view $v$ with the $\mathtt{leader}$
predicate.

$\displaystyle\begin{split}\mathtt{leader}(v)=(v-1\ \mathit{mod}\
n)+1\end{split}$

Upon receiving a notification from the synchronizer to transition to view $v$,
a replica stores $v$ in a variable $\mathit{curView}$ and sets a flag
$\mathit{voted}$ to false to record that it has not yet received any proposal
from the leader in the current view. If $v=1$, the leader is free to broadcast
its proposal (line 4). However, for other views, a correct leader must be
careful in choosing its proposal because if a correct replica has already
decided on a value in a prior view, the leader is obligated to propose the
same value. To facilitate this, upon entering a view $v>1$, a correct replica
sends a NewLeader message to the leader of $v$, providing information about
the latest value it accepted in a prior view (line 6). Any message exchanged
in the protocol is tagged with the sender’s view. A receiver will only accept
a message if its own view stored in the $\mathit{curView}$ variable matches
the view of the sender.

For any view $v>1$, the leader of $v$ waits until it receives NewLeader
messages from a _deterministic quorum_ of replicas. After computing its
proposal, the leader broadcasts the proposal, along with some supporting
information, in a Propose message (lines 9-14). After presenting the rest of
the protocol, we will describe the process for computing the proposal. Since a
Byzantine leader may send different proposals to different replicas, correct
replicas need to communicate with others to ensure they have received the same
proposal. With this aim, correct replicas process the leader’s proposal in two
phases –  _prepare_ and _commit_.

Upon receiving a Propose message $m$ containing a proposal $x$ from a replica
$j$ in view $v$, a correct replica $i$ starts the _prepare_ phase if it is
currently in view $v$, it has not processed a Propose message in this view,
and message $m$ satisfies the $\mathtt{safeProposal}$ predicate (also
explained later), which ensures that a Byzantine leader cannot reverse
decisions reached in a prior view (with high probability). The replica then
stores $x$ in $\mathit{curVal}$ and sets voted to true (line 17). Afterward,
replica $i$ uses the VRF to select a random sample $S_{P}$ to which it sends a
Prepare message.

A correct replica waits until receiving a set $C$ of Prepare messages from a
probabilistic quorum. We call this set of messages a prepared certificate for
a proposed value $x$ in a view $v$ if it satisfies the following predicate:

$\displaystyle\mathtt{prepared}\left(C,v,x,j\right)\iff$
$\displaystyle\quad\exists Q:|Q|=q\land C=\\{\langle\textsc{Prepare},\langle
v,x\rangle_{i},S_{k},P_{k}\rangle_{k}:k\in Q\\}\ \land$ $\displaystyle\quad
i=\mathtt{leader}(v)\land(\forall\langle\\_,\\_,S_{k},P_{k}\rangle_{k}\in
C:j\in S_{k}\ \land$ $\displaystyle\quad\quad\mathtt{VRF\\_verify}(K_{u,k},v\
||\ ``\text{prepare}",o\times q,S_{k},P_{k}))$

Once a replica $j$ creates a prepared certificate for a value $x$ in a view
$v$ (i.e., $j$ prepares $x$), it stores $x$, $v$, and this certificate in
$\mathit{preparedVal}$, $\mathit{preparedView}$, and $\mathit{cert}$,
respectively. Afterward, the replica generates a new random sample of replicas
$S_{c}$ to whom it will multicast a Commit message (lines 23-25). Every
correct replica that multicasts a Commit message enters the _commit_ phase. It
then waits until receiving Commit messages from a probabilistic quorum. It is
worth noting that a correct replica neither sends a Commit message nor
processes a received Commit message (line 27) if it has not yet prepared a
value. After observing a quorum of Commit messages, a correct replica with a
prepared certificate decides on the proposed value (line 29).

Recall that when the synchronizer triggers a $\mathtt{newView}$ notification
in a replica for a view greater than one, the replica sends a NewLeader
message to the new leader. If a replica has created a prepared certificate in
a prior view, it sends that certificate in the NewLeader message. This allows
the leader to generate its proposal based on a quorum of well-formed NewLeader
messages that can be checked using the following predicate:

$\displaystyle\begin{split}&\mathtt{validNewLeader}(\langle\textsc{NewLeader},v,\mathit{view},\mathit{val},\mathit{cert}\rangle_{j})\iff\\\
&\qquad\mathit{view}<v\land\mathit{view}\neq
0\Rightarrow\mathtt{prepared}(\mathit{cert},\mathit{view},\mathit{val},j)\end{split}$

The leader chooses its proposal by selecting the value prepared in the most
recent view by more replicas (lines 9-10). If no such prepared values exist,
it uses its own proposal provided by the function myValue(). Since a faulty
leader may not follow this rule, it is essential for the correct replicas to
validate that the leader adheres to this selection rule for proposals. With
this aim, the leader’s Propose message contains the NewLeader messages
received by the leader, in addition to the proposal. A correct replica checks
the validity of the proposed value by redoing the leader’s computation using
the following predicate:

$\displaystyle\begin{split}&\mathtt{safeProposal}(\langle\textsc{Propose},\langle
v,x\rangle_{j},M\rangle_{j})\iff\\\ &\quad v\geq 1\land
j=\mathtt{leader}(v)\land\mathtt{valid}(x)\ \land(v=1\ \lor\\\
&\quad\quad(|M|\geq\lceil{(n+f+1)/2}\rceil\land(\forall m\in
M:\;\mathtt{validNewLeader}(m))\land\\\ &\quad\quad\quad(\exists
v_{\mathit{max}}=\mathtt{max}\\{\mathit{view}_{k}:\langle\textsc{NewLeader},v,\mathit{view}_{k},\\_,\\_\rangle_{k}\in
M\\}\land\\\ &\quad\quad\quad\quad
x=\mathtt{mode}\\{\mathit{val}_{k}:\langle\textsc{NewLeader},v,v_{\mathit{max}},\mathit{val}_{k},\\_\rangle_{k}\in
M\\})))\end{split}$

When a correct replica detects that the leader is faulty, i.e., receiving
messages from any replica with different proposals signed by the leader, it
instantly blocks the current view and waits for the synchronizer to trigger a
new view (lines 31-33). Besides, it informs other replicas about this
misbehavior. It is important to emphasize that informing other replicas is
necessary only when the leader is Byzantine and sends distinct proposals.
Therefore, it does not impact the message complexity of the protocol when the
leader is correct.

###  3.3. Message and Communication Complexities

ProBFT’s message complexity is $O(n\sqrt{n})$, as computed based on four
terms: $O(n)$ for NewLeader messages, $O(n)$ for Propose messages,
$O(n\sqrt{n})$ for Prepare messages, and $O(n\sqrt{n})$ for Commit messages.
Further, in ProBFT, for any view greater than one, a new leader sends a
Propose message with a certificate containing a full (not probabilistic)
quorum of NewLeader messages to all replicas. Each NewLeader message might
contain a prepared certificate with a probabilistic quorum of Prepare
messages. Hence, ProBFT’s communication complexity is $O(n^{2}\sqrt{n})$. Note
that ProBFT has this communication complexity only when a view-change occurs.
In the first view, there is no need to send NewLeader messages to the leader,
as avoided in practical instantiations of PBFT (e.g., (Castro and Liskov,
1999; Bessani et al., 2014)). Therefore, ProBFT’s best-case communication
complexity is $\Omega(n\sqrt{n})$, contrary to PBFT, which still has
$\Omega(n^{2})$.

##  4\. ProBFT Proof Outline

This section outlines the correctness proofs of ProBFT. More specifically, we
show that ProBFT satisfies three properties of probabilistic consensus, i.e.,
Validity, Probabilistic Termination, and Probabilistic Agreement. Here we
discuss the main arguments of the proofs and refer to the appendix for the
theorems whose proofs are not provided in this section.

###  4.1. Validity

Recall that the Validity property states that the value decided by a correct
replica satisfies the application-defined $\mathtt{valid}$ predicate. In
ProBFT, before deciding a value $x$, a correct replica $i$ must receive $x$ as
a proposal from the leader and verify its validity using the
$\mathtt{safeProposal}$ predicate (line 16). In this predicate, several
conditions must be satisfied, one of which is that $\mathtt{valid}(x)$ must be
$\mathit{true}$. Accordingly, a value decided by a correct replica is valid,
satisfying the Validity property.

###  4.2. Probabilistic Termination

To demonstrate that ProBFT satisfies Probabilistic Termination, suppose there
is a non-empty subset of correct replicas that have not decided a value by
GST. Recall that ProBFT employs a round-robin mechanism for changing the
leaders. Accordingly, among the replicas that have not made a decision by GST,
there will be some correct replica $i$ that performs the leader’s role by
proposing a value $x$ in a view $v$. Note that all correct replicas receive
such a proposal during $v$ as the system is synchronous after GST and
multicast their Prepare messages. We show that any correct replica decides $x$
with a high probability during view $v$ if it has not already decided a value.
To do so, we first demonstrate that any correct replica receives Prepare
messages from a probabilistic quorum of replicas with a high probability. The
following theorem demonstrates that with a proper value of $o$, such an event
occurs for a correct replica with a probability of at least
$1-\mathit{exp}(-\sqrt{n})$, i.e., forming such a quorum with high
probability, even if all Byzantine replicas remain silent.

###### Theorem 1.

Suppose each correct replica takes a sample composed of $o\times l\sqrt{n}$
distinct replicas, uniformly at random from $\Pi$, and multicasts a message to
them, where $o\in[1,3.732(n/(n-f))]$, and $l\geq 1$. Provided that a replica
forms a probabilistic quorum upon receiving $l\sqrt{n}$ messages, the
probability of forming such a quorum is at least $1-\mathit{exp}(-\sqrt{n})$.

Recall that a correct replica prepares the value proposed by the leader upon
receiving Prepapre messages from a probabilistic quorum. According to Theorem
1, a correct replica prepares the value proposed by a correct leader with high
probability, so almost all correct replicas send Commit messages to their
randomly selected samples. It is clear that the probability of receiving
Commit messages from a probabilistic quorum is less than the probability of
receiving Prepare messages from a probabilistic quorum. However, the following
theorem demonstrates that every correct replica receives Commit messages from
a probabilistic quorum with a high probability, resulting in deciding a value
with a high probability.

###### Theorem 2.

After GST, if the leader of view $v$ is correct, then each correct replica
decides a value in $v$ with a probability of at least
$1-2(n-f)\times\mathit{exp}\boldsymbol{(}-\Theta(\sqrt{n})\boldsymbol{)}$.

Proving the above theorem constitutes the most complex part of demonstrating
that ProBFT satisfies the Probabilistic Termination property. This complexity
arises from the following sources:

  * –

The probability of forming probabilistic quorums by replicas is dependent.
That is, as replicas multicast their Prepare (resp., Commit) messages to
random samples, knowing that a replica has received Prepare (resp., Commit)
messages from a probabilistic quorum decreases the chance of other replicas to
receive Prepare (resp., Commit) messages from a probabilistic quorum. This
dependency prevents us from directly using well-known and sharp bounds like
the Chernoff bounds (Motwani and Raghavan, 1995). To circumvent this
dependency, we use the notion of negative association (Dubhashi and Panconesi,
2009), enabling us to leverage the Chernoff bounds.

  * –

The number of replicas that receive Commit messages from probabilistic quorums
_depends on_ the number of replicas that receive Prepare messages from
probabilistic quorums. We address this dual dependency inherent in computing
the probability of deciding a value by a replica by conditioning the
probability of forming quorums by Commit messages on the probability of
forming quorums by Prepare messages.

In ProBFT, when the leader of view $v$ is correct, a correct replica might not
receive enough messages to form quorums, leading to not deciding a value in
view $v$. According to Theorem 2, such an event happens with a low
probability. However, as there are infinite views whose leaders are correct,
each correct replica decides with probability $1$.

###### Theorem 3 (Main liveness result).

In ProBFT, every correct replica eventually decides a value with probability
$1$.

###  4.3. Probabilistic Agreement

In ProBFT, different replicas may decide different values since quorum
intersections are not guaranteed, but the protocol has to ensure that the
probability of agreement violation is low. We begin by computing the
probability of ensuring agreement within a view.

#### Probabilistic Agreement in a view

In ProBFT, to cause disagreement in a view, it is required that multiple
values are decided in the same view by multiple correct replicas. Such a
situation only happens when the leader is Byzantine since correct leaders send
a single proposal in their views.

There are many cases in which a Byzantine leader can compromise the agreement
in a view. Rather than examining every possible case individually, we find the
optimal behavior for a Byzantine leader, considering that it intends to
maximize the probability of agreement violation. For this purpose, we consider
the three cases illustrated in Figure 4(c). The first case is the most general
one, which can be used to derive any possible situation. The second and third
cases demonstrate specific situations. In the third case, the probability of
agreement violation is greater than or equal to the probability of agreement
violation in the second case and any other situation obtained from the first
case.

(a) The general case. The Byzantine leader sends $m$ different proposals to
$m$ non-empty subset of replicas, which might overlap. It also does not send
any proposal to subset $\Pi^{0}$.

(b) A sub-optimal case. The Byzantine leader sends two proposals
$\mathit{val}_{1}$ and $\mathit{val}_{2}$ to $\Pi^{1}$ and $\Pi^{2}$,
respectively.

(c) The optimal case. Given two sets $\Pi^{1}_{C},\Pi^{2}_{C}\subseteq\Pi_{C}$
with equal sizes, the Byzantine leader sends only two proposals
$\mathit{val}_{1}$ and $\mathit{val}_{2}$ to $\Pi^{1}_{C}\cup\Pi_{F}$ and
$\Pi^{2}_{C}\cup\Pi_{F}$, respectively.

Figure 4. Different scenarios in which a Byzantine leader can cause
disagreements in a view.

[]

  * –

_The general case._ The Byzantine leader sends multiple proposals
$\mathit{val}_{1},\dots,\mathit{val}_{m}$, where $m\geq 2$. As a result, some
replica(s) might receive one or even multiple proposals, and some others might
not receive any proposals. This case is depicted in Figure 4(a).

  * –

_A sub-optimal case._ The Byzantine leader divides the set of replicas into
two equally sized groups $\Pi^{1}$ and $\Pi^{2}$. It sends a proposal
$\mathit{val}_{1}$ to $\Pi^{1}$ and another proposal $\mathit{val}_{2}$ to
$\Pi^{2}$. This case is depicted in Figure 4(b).

  * –

_The optimal case._ The Byzantine leader makes a distinction between correct
and Byzantine replicas. It divides the correct replicas into two equally sized
groups – $\Pi_{C}^{1}$ and $\Pi_{C}^{2}$. It sends a proposal
$\mathit{val}_{1}$ to $\Pi_{C}^{1}\cup\Pi_{F}$ and another proposal
$\mathit{val}_{2}$ to $\Pi_{C}^{2}\cup\Pi_{F}$. This case is depicted in
Figure 4(c).

In order to describe why the first case represents the most general situation,
we need to present some notations. For each proposal $\mathit{val}_{i}$, where
$1\leq i\leq m$, we associate a set $\Pi^{i}\subset\Pi$ containing each
replica $p$ that receives $\mathit{val}_{i}$ as a proposal from the leader. As
the leader might send multiple proposals to a replica, any set $\Pi^{i}$ might
intersect with another set $\Pi^{j}$, where $1\leq i<j\leq m$. We denote by
$\Pi^{0}$ the set of replicas to which the leader does not send any proposal,
but these replicas can receive messages from other replicas. Indeed,
$\Pi\setminus\Pi^{0}$ contains every replica that can multicast Prepare and
Commit messages. Furthermore, we denote the correct (resp. Byzantine) replicas
within a set $\Pi^{i}$ by $\Pi^{i}_{C}$ (resp. $\Pi^{i}_{F}$).

It is essential to remark that a correct replica $p$ to decide a value
$\mathit{val}_{i}$ requires to form a probabilistic prepare quorum $P$ and a
probabilistic commit quorum $Q$ such that $P,Q\subseteq\Pi^{i}$; otherwise,
$p$ does not decide a value due to receiving two distinct values.
Consequently, if replica $p\in\Pi^{i}$ decides a value, the value is
$\mathit{val}_{i}$.

Using the first case, we can model any situation in the system when the
Byzantine leader sends multiple proposals, as we do not impose any
restrictions on the leader’s behavior. For instance, replica $p$ decides
$\mathit{val}_{i}$ when either  (1) it forms a probabilistic prepare quorum
and a probabilistic commit quorum, both composed of Byzantine replicas within
$\Pi^{i}$, i.e., $P,Q\subseteq\Pi^{i}_{F}$,  (2) it forms a probabilistic
prepare quorum composed of Byzantine replicas and a probabilistic commit
quorum composed of correct replicas, i.e., $P\subseteq\Pi^{i}_{F}$ and
$Q\subseteq\Pi^{i}_{C}$, or  (3) it forms a probabilistic prepare quorum
composed of correct and Byzantine replicas and a probabilistic commit quorum
composed of correct replicas, i.e., $P\subseteq\Pi^{i}$,
$P\cap\Pi_{C}^{i}\cap\Pi_{F}^{i}\neq\emptyset$, and $Q\subseteq\Pi^{i}_{C}$.

Beyond the situations where a replica decides a value, the first case
demonstrates situations where a replica does not decide a value because of
receiving multiple proposals. For example, replica $p$ does not decide a value
when either  (1) it receives multiple proposals from the leader, i.e.,
$p\in\Pi^{i}$ and $p\in\Pi^{j}$, where $1\leq i<j\leq m$,  (2) it receives at
least two different proposals $\mathit{val}_{i}$ and $\mathit{val}_{j}$ such
that $\mathit{val}_{i}$ is received from the leader and $\mathit{val}_{j}$ is
received from one of the replicas sending its Prepare message, or  (3) it
receives at least two different proposals $\mathit{val}_{i}$ and
$\mathit{val}_{j}$ such that $\mathit{val}_{i}$ is received from a replica
sending its Prepare message, while $\mathit{val}_{j}$ is received from another
replica sending its Commit message.

In order to grasp why the third case is optimal, consider the following
observations:

  1. (1)

If the Byzantine leader sends different proposals to a correct replica $p$,
$p$ will detect the misbehavior of the leader and notify all replicas about it
(line 33 in Algorithm 1). Hence, sending multiple proposals to $p$ increases
the probability that correct replicas avoid deciding some value(s). Note that
there is no agreement violation when correct replicas avoid deciding a value.
Hence, the Byzantine leader should send only one proposal to each correct
replica, i.e., $\Pi^{i}_{C}\cap\Pi^{j}_{C}=\emptyset$, for any
$i,j\in\\{1,\dots,m\\}$, as it intends to increase the probability of
agreement violation. Consequently, in the optimal case, the number of
proposals the leader sends is bounded by the number of correct replicas, i.e.,
$m\leq n-f$.

  2. (2)

The Byzantine leader should send two proposals to increase the probability of
agreement violation. To show this result, we prove in Theorem 4 that sending
$m$ proposals instead of $m+1$ proposals, where $m\geq 2$, increases the
probability of agreement violation. Given the previous observation that states
the leader sends at most $n-f$ proposals, we can now say that the leader
prefers to send $n-f-1$ proposals instead of sending $n-f$ proposals in the
optimal case. Likewise, it prefers to send $n-f-2$ proposals instead of
sending $n-f-1$ proposals. Following this line of reasoning, we conclude that
the Byzantine leader should send two proposals to increase the probability of
agreement violation.

  3. (3)

The probability of forming a probabilistic quorum by a replica $p$ for a
proposal $\mathit{val}$ increases by expanding the set of replicas that send
$\mathit{val}$. This result is formally presented in Theorem 5. From the
previous observation, we know that the leader should send two proposals. Now,
we can say that the Byzantine leader should maximize the size of these two
sets, resulting in the optimal case depicted in Figure 4(c).

###### Theorem 4.

Given a Byzantine leader who intends to send multiple proposals, consider the
following two scenarios:  (1) given non-empty sets $\Pi^{1},\dots,\Pi^{m+1}$
of replicas, where $m\geq 2$, and $|\Pi^{1}|\leq$
$|\Pi^{2}|\leq\dots\leq|\Pi^{m+1}|$, the leader sends a distinct proposal to
each set, and  (2) the leader merges two sets $\Pi^{1}$ and $\Pi^{2}$ to
create a set $\Pi^{1,2}$ and sends $m$ proposals to
$\Pi^{1,2},\Pi^{3},\dots,\Pi^{m+1}$.  The probability of agreement violation
in the second scenario is greater than in the first scenario.

###### Theorem 5.

Suppose any replica forms a quorum upon receiving $q$ messages. Consider a set
of $r$ replicas, each of which takes a sample composed of $o\times q$ distinct
replicas uniformly at random from $\Pi$, with the condition that $n<o\times
r$, and sends a message to all sample members. The value of $r$ and the
probability of a replica forming a quorum are directly proportional.

Since the third case discussed above is optimal, i.e., the probability of
compromising the agreement is maximized by a Byzantine leader when it divides
the correct replicas into two equally sized groups, $\Pi_{C}^{1}$ and
$\Pi_{C}^{2}$, and sends a proposal $\mathit{val}_{1}$ to
$\Pi_{C}^{1}\cup\Pi_{F}$ and another proposal $\mathit{val}_{2}$ to
$\Pi_{C}^{2}\cup\Pi_{F}$, we only analyze this case. We prove that given a
Byzantine leader who may send several proposals, the probability of agreement
violation in a view under the worst-case scenario is bounded by
$\mathit{exp}\boldsymbol{(}-\Theta(\sqrt{n})\boldsymbol{)}^{4}$ in the
following theorem.

###### Theorem 6.

Given a Byzantine leader who may send several proposals, the probability of
agreement violation in a view under the worst-case scenario is at most
$\mathit{exp}\boldsymbol{(}-\Theta(\sqrt{n})\boldsymbol{)}^{4}$.

#### Probabilistic Agreement with view change

We now consider the case of a view change. When referring to agreement within
different views, we need to guarantee that if at least one correct replica
decides on a proposal $\mathit{val}$ in a view $v$, the probability that some
correct replica decides on a different proposal $\mathit{val}^{\prime}$ in a
view $v^{\prime}>v$ is negligible. To guarantee this condition, we need to
demonstrate that the leader of any view $v^{\prime\prime}>v$ proposes
$\mathit{val}$ with high probability.

Recall that, in Algorithm 1, when the synchronizer notifies a replica to enter
a new view $v^{\prime\prime}$, the replica informs the leader of
$v^{\prime\prime}$ about its latest prepared value through a NewLeader
message. The leader of $v^{\prime\prime}$ waits until it observes a
deterministic quorum of NewLeader messages. If at least
$\lceil{(n+f+1)/2}\rceil$ correct replicas have prepared $\mathit{val}$, then
the leader must propose $\mathit{val}$, regardless of its type, whether
Byzantine or correct. The problem occurs when $w<\lceil{(n+f+1)/2}\rceil$
correct replicas have prepared $\mathit{val}$. Note that $w\geq 1$ as we
assumed at least one correct replica has decided $\mathit{val}$. One of the
following scenarios can happen:

  * –

$1\leq w\leq f$. If the leader is Byzantine, it can propose any value
different than $\mathit{val}$. Besides, if the leader is correct, it proposes
a value $\mathit{val}^{\prime}\neq\mathit{val}$ when the number of NewLeader
messages received from replicas that prepared $\mathit{val}^{\prime}$ is
greater than the number of NewLeader messages received from replicas that
prepared $\mathit{val}$.

  * –

$f+1\leq w<\lceil{(n+f+1)/2}\rceil$. If the leader is Byzantine, it can
propose a value $\mathit{val}^{\prime}\neq\mathit{val}$ if the number of
replicas that prepared $\mathit{val}^{\prime}$ is greater than the number of
replicas that prepared $\mathit{val}$. Besides, if the leader is correct, it
proposes a value $\mathit{val}^{\prime}\neq\mathit{val}$ when the number of
NewLeader messages received from replicas that prepared
$\mathit{val}^{\prime}$ is greater than the number of NewLeader messages
received from replicas that prepared $\mathit{val}$.

We need to ensure that there is a high probability that the system will not be
in these scenarios. The following theorem shows this.

###### Theorem 7.

The probability of proposing a value $\mathit{val}^{\prime}$ when another
value $\mathit{val}$ has been decided by a correct replica in a prior view is
at most
$\mathit{exp}\boldsymbol{(}-(q\times\delta^{2})/((\delta+1)\times(\delta+2))\boldsymbol{)}$,
where $\delta=2n/(o\times(n+f))-1$.

###### Corollary 0 (Main safety result).

ProBFT guarantees safety with a probability of at least
$1-\mathit{exp}(-\Theta(\sqrt{n}))$.

##  5\. Numerical Evaluation

In this section, we illustrate the usefulness of ProBFT by presenting a
numerical analysis of the agreement and termination probabilities, considering
$q=2\sqrt{n}$ and $o\in\\{1.6,1.7,1.8\\}$.

#### Analysis with fixed fault threshold and varying system sizes

In Figure 5, the top sub-figures depict analyses with $f/n=0.2$ and varying
system sizes. The top-left sub-figure depicts the probability of ensuring
agreement, considering the worst-case scenario in which there are faulty
leaders in each view. It shows that as the system size increases, the
probability of ensuring agreement also increases. Besides, the top-right sub-
figure depicts the probability of terminating in a view after GST when the
leader is correct. It shows the probability of deciding increases as the
number of replicas increases.

#### Analysis with fixed system size and a varying number of faulty replicas

In Figure 5, the bottom sub-figures depict similar analyses with $n=100$ and a
varying number of faulty replicas. The bottom-left sub-figure shows that the
probability of ensuring agreement increases as we have fewer Byzantine
replicas. Similarly, the bottom-right sub-figure shows that the probability of
deciding increases as we have fewer Byzantine replicas.

#### Number of exchanged messages

Figure 1(b) shows the number of exchanged messages in PBFT, ProBFT (for
different values of $o$), and HotStuff. In the figure, it is possible to see
that ProBFT exchanges significantly fewer messages than PBFT despite having
the same good-case optimal latency. Taking together with the results of Figure
5, we can see that ProBFT with $o=1.7$ ensures a high probability of agreement
and termination exchanging only $18$-$25\%$ of the messages required by PBFT.

Figure 5.  ProBFT agreement and termination probability analysis with
$q=2\sqrt{n}$. For $f/n=0.2$, the top-left figure depicts the probability of
ensuring agreement with faulty leaders in every view, while the top-right
figure shows the probability of terminating in a view after GST when the
leader is correct. For $n=100$, the bottom-left figure depicts the probability
of ensuring agreement with faulty leaders in every view, while the bottom-
right figure depicts the probability of terminating in a view after GST when
the leader is correct.

[]

##  6\. Related Work

#### Scalable BFT consensus protocols

PBFT (Castro and Liskov, 1999) is considered the baseline “practical” BFT
protocol. It is optimal in terms of resilience ($f<n/3$) and best-case latency
(three communication steps) but employs an all-to-all message exchange
pattern, which results in a quadratic message complexity, making it very
costly in large deployments. With the advent of large-scale systems like
blockchains and decentralized payment systems, the scalability of Byzantine
consensus protocols has become a hot topic, with numerous contributions from
both academia and industry.

There are several approaches to enhance the scalability of BFT consensus
protocols. For instance, protocols like HotStuff (Yin et al., 2019) modify the
message exchange pattern from all-to-all to leader-to-all-to-leader, resulting
in a linear message complexity. Alternatively, to improve the message
complexity and balance the load on the system, some protocols (Neiheiser et
al., 2021; Li et al., 2020a) utilize a tree-based message exchange pattern,
while other protocols (e.g., (Gilad et al., 2017; Zamani et al., 2018; Li et
al., 2020b; Cason et al., 2021)) employ a gossip layer for communication.
Similarly, there are some works that use expander graphs (and related
techniques) to make Byzantine agreement more scalable (e.g., (King and Saia,
2011)). Other works like RedBelly (Crain et al., 2021) improve different
aspects of the protocol, such as how ordered transactions are disseminated and
verified, to achieve better scalability in practical deployments without
reducing the message complexity of the base protocol. While most of these
works avoid the all-to-all communication pattern, they increase the number of
communication steps necessary to achieve consensus.

#### Randomized consensus protocols

The primary drive for developing randomized consensus protocols was the well-
known FLP impossibility result (Fischer et al., 1985). This result states that
for crash-prone asynchronous systems, designing a deterministic consensus
protocol is impossible. One of the main approaches to circumvent such an
impossibility result involves relaxing deterministic termination to
probabilistic termination, assuming processes have access to random numbers.

The randomized consensus protocol by Ben-Or (Ben-Or, 1983) assumes a strong
adversary who can observe the entire history of the system and uses a local
coin. The protocol operates in rounds, with each round involving $O(n^{2})$
message exchanges, and it requires exponential expected time to converge in
the worst case. Subsequent works like RITAS (Moniz et al., 2011) and WaterBear
(Zhang et al., 2023) showed this type of protocol can be made practical.

Rabin (Rabin, 1983) showed that the same type of protocol could achieve
termination in the expected constant time by resorting to a common coin. The
construction of this common coin typically requires strong cryptographic
primitives, which can negatively affect the performance of the protocol.
Further works like Cachin et al. (Cachin et al., 2000) leveraged threshold
signatures to devise a protocol with constant expected time and message
complexity of $O(n^{2})$. More recently, Mostéfaoui et al. (Mostéfaoui et al.,
2015) proposed a similar protocol that is signature-free. HoneyBadgerBFT
(Miller et al., 2016) is a practical randomized consensus protocol that has at
least an $O(n^{3})$ message complexity. Follow-up works (e.g., (Duan et al.,
2018; Gao et al., 2022; Liu et al., 2023)) improved different aspects of
practical randomized protocols, including their message complexity, but never
below $O(n^{2})$. The same can be said about DAG-based protocols (e.g.,
(Keidar et al., 2021; Spiegelman et al., 2022)) that use local rules to commit
blocks (i.e., decide consensus values) and resort to a kind of randomized
consensus only when such rules are not enough.

#### Synchronizer

Byzantine fault-tolerant consensus protocols designed for partially
synchronous systems typically structure their execution in a sequence of
views, with the premise that there will be a view in which all correct
replicas will overlap with enough time to reach a consensus if there is a
correct leader. Designing these protocols is challenging, and researchers
usually pay more attention to guaranteeing the system’s safety rather than
liveness (Castro and Liskov, 1999; Gueta et al., 2019; Yin et al., 2019). The
problem with the partially synchronous model and designing the protocols in a
sequence of views is that replicas may diverge indefinitely before the GST,
reaching GST in different views. This problem is typically not addressed in
commonly used Byzantine fault-tolerant protocols (Castro and Liskov, 1999;
Bessani et al., 2014; Naor et al., 2021) in which the liveness is argued based
on the assumption that after the system reaches GST, all the correct replicas
will eventually converge to the same view. By separating the mechanism used
for view synchronization in a distinct component, Bravo et al. (Bravo et al.,
2022) formally defined the synchronizer abstraction, which we employ in
ProBFT. Notice that using such abstraction does not incur added message
complexity as there are constructions with linear message complexity (Naor and
Keidar, 2020; Lewis-Pye and Abraham, 2023).

#### Probabilistic quorum systems

Malkhi et al. (Malkhi et al., 2001) introduced probabilistic quorum systems to
enhance the efficiency of data replication by relaxing strict quorum
requirements and allowing for probabilistic guarantees of consistency. These
quorum systems operate under the implicit assumption that any chosen quorum
will be accessible without taking into account the potential effects of
failures or asynchrony (Aiyer et al., 2005; Vukolić, 2013; Yu, 2006). In other
words, it does not account for the impact of an adversarial scheduler (also
known as an active adversary (Aiyer et al., 2005) or an asynchronous scheduler
(Yu, 2006)) that could potentially delay the delivery of messages. Yu (Yu,
2006) introduced an alternative concept termed signed quorum systems, aiming
to address the challenges posed by network scheduling. Nevertheless, Yu’s
method remains susceptible to manipulation by an adversarial scheduler (Aiyer
et al., 2005).

##  7\. Conclusion

We presented ProBFT, a Byzantine fault-tolerant consensus protocol that
ensures safety and liveness with high probability in permissioned partially
synchronous systems. This protocol’s message complexity is $O(n\sqrt{n})$ in a
system with $n$ replicas, and it has an optimal number of communication steps.
ProBFT introduces a novel paradigm for designing scalable Byzantine-resilient
protocols for less pessimistic contexts. We believe the same techniques used
in ProBFT can be employed in other types of quorum-based protocols. As future
work, we are particularly interested in leveraging ProBFT for constructing a
scalable state machine replication protocol and a streamlined blockchain
consensus, eliminating the need for a view-change sub-protocol.

###### Acknowledgements.

This work was partially supported by the Sponsor Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) https://www.dfg.de/ –
Grant #446811880 (BFT2Chain), and by Sponsor FCT  through the Grant
#SMaRtChain project (2022. 08431.PTDC) and the Grant #LASIGE Research Unit
(UIDB/00408/2020 and UIDP/00408/2020).

## References

  * (1)
  * Abraham et al. (2021) Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021\.  Good-case Latency of Byzantine Broadcast: a Complete Categorization. In _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC ’21)_.
  * Aiyer et al. (2005) Amitanand Aiyer, Lorenzo Alvisi, and Rida A. Bazzi. 2005\.  On the Availability of Non-strict Quorum Systems. In _Proceedings of th 19th International Symposium on Distributed Computing (DISC ’05)_.
  * Ben-Or (1983) Michael Ben-Or. 1983\.  Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. In _Proceedings of the 2nd Symposium on Principles of Distributed Computing (PODC ’83)_.
  * Bessani et al. (2020) Alysson Bessani, Eduardo Alchieri, João Sousa, André Oliveira, and Fernando Pedone. 2020\.  From Byzantine Replication to Blockchain: Consensus is only the Beginning. In _Proceedings of the 50th IEEE/IFIP Int. Conference on Dependable Systems and Networks (DSN ’20)_.
  * Bessani et al. (2014) Alysson Bessani, João Sousa, and Eduardo E. P. Alchieri. 2014\.  State Machine Replication for the Masses with BFT-SMaRt. In _Proceedings of the 44th International Conference on Dependable Systems and Networks (DSN ’14)_.
  * Bravo et al. (2022) Manuel Bravo, Gregory Chockler, and Alexey Gotsman. 2022\.  Making Byzantine Consensus Live.  _Distributed Computing_ 35, 6 (2022).
  * Buterin and Griffith (2019) Vitalik Buterin and Virgil Griffith. 2019.  Casper the Friendly Finality Gadget.  arXiv:1710.09437 [cs.CR]
  * Cachin et al. (2001) Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001.  Secure and Efficient Asynchronous Broadcast Protocols. In _Proceedings of the 21st Annual International Cryptology Conference (Crypto ’01)_.
  * Cachin et al. (2000) Christian Cachin, Klaus Kursawe, and Victor Shoup. 2000\.  Random Oracles in Constantipole: Practical Asynchronous Byzantine Agreement Using Cryptography. In _Proceedings of the 19th Symposium on Principles of Distributed Computing (PODC ’00)_.
  * Cachin et al. (2022) Christian Cachin, Giuliano Losa, and Luca Zanolini. 2022\.  Quorum Systems in Permissionless Network. In _Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS ’22)_.
  * Cason et al. (2021) Daniel Cason, Enrique Fynn, Nenad Milosevic, Zarko Milosevic, Ethan Buchman, and Fernando Pedone. 2021\.  The Design, Architecture and Performance of the Tendermint Blockchain Network. In _Proceedings of the 40th International Symposium on Reliable Distributed Systems (SRDS ’21)_.
  * Castro and Liskov (1999) Miguel Castro and Barbara Liskov. 1999.  Practical Byzantine Fault Tolerance. In _Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI ’99)_.
  * Chvátal (1979) V. Chvátal. 1979\.  The Tail of the Hypergeometric Distribution.  _Discrete Mathematics_ 25, 3 (1979).
  * Crain et al. (2021) Tyler Crain, Christopher Natoli, and Vincent Gramoli. 2021\.  Red Belly: A Secure, Fair and Scalable Open Blockchain. In _Proceedings of the IEEE Symposium on Security and Privacy (SP ’21)_.
  * Distler (2021) Tobias Distler. 2021\.  Byzantine Fault-Tolerant State-Machine Replication from a Systems Perspective.  _Comput. Surveys_ 54, 1 (2021).
  * Douceur (2002) John R Douceur. 2002\.  The Sybil Attack. In _Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS ’02)_.
  * Duan et al. (2018) Sisi Duan, Michael K Reiter, and Haibin Zhang. 2018\.  BEAT: Asynchronous BFT made practical. In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18)_.
  * Dubhashi and Panconesi (2009) Devdatt P Dubhashi and Alessandro Panconesi. 2009.  _Concentration of Measure for the Analysis of Randomized Algorithms_.  Cambridge University Press.
  * Dwork et al. (1988) Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988\.  Consensus in the Presence of Partial Synchrony.  _J. ACM_ 35, 2 (1988).
  * Fischer et al. (1985) Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985.  Impossibility of Distributed Consensus with One Faulty Process.  _J. ACM_ 32, 2 (1985).
  * Gao et al. (2022) Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2022\.  Dumbo-NG: Fast Asynchronous BFT Consensus with Throughput-Oblivious Latency. In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS ’22)_.
  * Gilad et al. (2017) Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017.  Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In _Proceedings of the 26th Symposium on Operating Systems Principles (SOSP ’17)_.
  * Goldberg et al. (2022) Sharon Goldberg, Leonid Reyzin, Dimitrios Papadopoulos, and Jan Včelák. 2022.  _Verifiable Random Functions (VRFs)_.  Technical Report. Internet Engineering Task Force.
  * Gueta et al. (2019) Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019.  SBFT: A Scalable and Decentralized Trust Infrastructure. In _Proceedings of the 49th International Conference on Dependable Systems and Networks (DSN ’19)_.
  * Hadzilacos and Toueg (1994) Vassos Hadzilacos and Sam Toueg. 1994.  _A modular approach to fault-tolerant broadcasts and related problems_.  Technical Report. Cornell University.
  * Hayter (2012) Anthony J. Hayter. 2012\.  _Probability and Statistics for Engineers and Scientists_.  Cengage Learning.
  * Joag-Dev and Proschan (1983) Kumar Joag-Dev and Frank Proschan. 1983.  Negative Association of Random Variables with Applications.  _The Annals of Statistics_ (1983).
  * Keidar et al. (2021) Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021.  All You Need is DAG. In _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC ’21)_.
  * King and Saia (2011) Valerie King and Jared Saia. 2011.  Breaking the $O(n^{2})$ bit barrier: Scalable Byzantine agreement with an adaptive adversary.  _J. ACM_ 58, 4 (2011).
  * Lamport et al. (1982) Leslie Lamport, Robert Shostak, and Marshall Pease. 1982\.  The Byzantine Generals Problem.  _ACM Transactions on Programming Languages and Systems_ 4, 3 (1982).
  * Lewis-Pye and Abraham (2023) Andrew Lewis-Pye and Ittai Abraham. 2023.  Fever: Optimal Responsive View Synchronisation. In _Proceedings of the 27th International Conference on Principles of Distributed Systems (OPODIS ’23)_.
  * Li et al. (2020b) Peilun Li, Guosai Wang, Xiaoqi Chen, Fan Long, and Wei Xu. 2020b.  Gosig: A Scalable and High-Performance Byzantine Consensus for Consortium Blockchains. In _Proceedings of the 11th Symposium on Cloud Computing (SoCC ’20)_.
  * Li et al. (2020a) Wenyu Li, Chenglin Feng, Lei Zhang, Hao Xu, Bin Cao, and Muhammad Ali Imran. 2020a.  A Scalable Multi-Layer PBFT Consensus for Blockchain.  _IEEE Transactions on Parallel and Distributed Systems_ 32, 5 (2020).
  * Li et al. (2023) Xiao Li, Eric Chan, and Mohsen Lesani. 2023.  Quorum Subsumption for Heterogeneous Quorum Systems. In _Proceedings of the 37th International Symposium on Distributed Computing (DISC ’23)_.
  * Liu et al. (2023) Shengyun Liu, Wenbo Xu, Chen Shan, Xiaofeng Yan, Tianjing Xu, Bo Wang, Lei Fan, Fuxi Deng, Ying Yan, and Hui Zhang. 2023.  Flexible Advancement in Asynchronous BFT Consensus. In _Proceedings of the 29th Symposium on Operating Systems Principles (SOSP ’23)_.
  * Lokhava et al. (2019) Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, and Jed McCaleb. 2019.  Fast and Secure Global Payments with Stellar. In _Proceedings of the ACM Symposium on Operating Systems Principles (SOSP ’19)_.
  * Luan and Gligor (1990) Shyh-Wei Luan and Virgil D Gligor. 1990.  A Fault-tolerant Protocol for Atomic Broadcast.  _IEEE Transactions on Parallel & Distributed Systems_ 1, 3 (1990).
  * Malkhi et al. (2001) Dahlia Malkhi, Michael Reiter, Avishai Wool, and Rebecca Wright. 2001.  Probabilistic Quorum Systems.  _Information and Computation_ 170, 2 (2001).
  * Micali et al. (1999) Silvio Micali, Michael Rabin, and Salil Vadhan. 1999\.  Verifiable Random Functions. In _Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS ’99)_.
  * Miller et al. (2016) Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016.  The Honey Badger of BFT Protocols. In _Proceedings of the 23rd Conference on Computer and Communications Security (CCS ’16)_.
  * Moniz et al. (2011) Henrique Moniz, Nuno Ferreria Neves, Miguel Correia, and Paulo Verissimo. 2011.  RITAS: Services for Randomized Intrusion Tolerance.  _IEEE Transactions on Dependable and Secure Computing_ 8, 1 (2011).
  * Mostéfaoui et al. (2015) Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. 2015\.  Signature-free Asynchronous Binary Byzantine Consensus with $t<n/3$, $O(n^{2})$ Messages, and $O(1)$ Expected Time.  _J. ACM_ 62, 4 (2015).
  * Motwani and Raghavan (1995) Rajeev Motwani and Prabhakar Raghavan. 1995.  _Randomized Algorithms_.  Cambridge University Press.
  * Nakamoto (2008) Satoshi Nakamoto. 2008\.  Bitcoin: A Peer-to-Peer Electronic Cash System.
  * Naor et al. (2021) Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. 2021.  Cogsworth: Byzantine View Synchronization.  _Cryptoeconomic Systems_ 1, 2 (2021).
  * Naor and Keidar (2020) Oded Naor and Idit Keidar. 2020.  Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR. In _Proceedings of the 34th International Symposium on Distributed Computing (DISC ’20)_.
  * Neiheiser et al. (2021) Ray Neiheiser, Miguel Matos, and Luís Rodrigues. 2021\.  Kauri: Scalable BFT Consensus with Pipelined Tree-based Dissemination and Aggregation. In _Proceedings of the 28th Symposium on Operating Systems Principles (SOSP ’21)_.
  * Pass and Shi (2017) Rafael Pass and Elaine Shi. 2017.  The Sleepy Model of Consensus. In _Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT ’17)_.
  * Pedone and Schiper (1998) Fernando Pedone and André Schiper. 1998.  Optimistic Atomic Broadcast. In _Proceedings of the 12th International Symposium on Distributed Computing (DISC ’98)_.
  * Rabin (1983) Michael O. Rabin. 1983\.  Randomized Byzantine Generals. In _Proceedings of the 24th Proceedings of the 24th Symposium on Foundations of Computer Science (FOCS ’83)_.
  * Schneider (1990) Fred B. Schneider. 1990\.  Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial.  _Comput. Surveys_ 22, 4 (1990).
  * Skala (2013) Matthew Skala. 2013\.  Hypergeometric Tail Inequalities: Ending the Insanity.  _arXiv preprint arXiv:1311.5939_ (2013).
  * Sousa and Bessani (2012) João Sousa and Alysson Bessani. 2012.  From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation. In _Proceedings of the 9th European Conference on Dependable Computing (EDCC’12)_.
  * Spiegelman et al. (2022) Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. 2022.  Bullshark: DAG BFT Protocols Made Practical. In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS ’22)_.
  * Vassantlal et al. (2023) Robin Vassantlal, Hasan Heydari, and Alysson Bessani. 2023\.  On the Minimal Knowledge Required for Solving Stellar Consensus. In _Proceedings of the 43rd International Conference on Distributed Computing Systems (ICDCS ’23)_.
  * Vukolić (2013) Marko Vukolić. 2013\.  The Origin of Quorum Systems.  _Bulletin of EATCS_ 2, 101 (2013).
  * Vukolić (2015) Marko Vukolić. 2015\.  The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication. In _Proceedings of the International Workshop on Open Problems in Network Security (iNetSec ’15)_.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019\.  HotStuff: BFT Consensus with Linearity and Responsiveness. In _Proceedings of the 38th Symposium on Principles of Distributed Computing (PODC ’19)_.
  * Yu (2006) Haifeng Yu. 2006\.  Signed Quorum Systems.  _Distributed Computing_ 18, 4 (2006).
  * Zamani et al. (2018) Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018\.  RapidChain: Scaling Blockchain via Full Sharding. In _Proceedings of the 2018 Conference on Computer and Communications Security (CCS ’18)_.
  * Zhang et al. (2023) Haibin Zhang, Sisi Duan, Boxin Zhao, and Liehuang Zhu. 2023\.  WaterBear: Practical Asynchronous BFT Matching Security Guarantees of Partially Synchronous BFT. In _Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23)_.

##  Appendix A Probability Definitions and Bounds

We utilize several probability definitions and bounds to establish the
correctness of ProBFT. This appendix presents such definitions and bounds.

### Chernoff bounds

We use the Chernoff bounds (Motwani and Raghavan, 1995) for bounding the
probability that the sum of independent random variables deviates
significantly from its expected value. Suppose $X_{1},\dots,X_{n}$ are
independent Bernoulli random variables, and let $X$ denote their sum. Then,
for any $\delta\in(0,1)$:

(1)
$\displaystyle\Pr\boldsymbol{(}X\leq(1-\delta)\mathop{\mathbb{E}}[X]\boldsymbol{)}\leq\mathit{exp}(-\delta^{2}\mathop{\mathbb{E}}[X]/2).$

Besides, for any $\delta\geq 0$:

(2)
$\displaystyle\Pr\boldsymbol{(}X\geq(1+\delta)\mathop{\mathbb{E}}[X]\boldsymbol{)}\leq\mathit{exp}\boldsymbol{(}-\delta^{2}\mathop{\mathbb{E}}[X]/(2+\delta)\boldsymbol{)}.$

### Negative association

In randomized algorithms and analysis, using independent random variables is
common, enabling the application of powerful theorems and bounds like
Inequalities 1 and 2. However, random variables may not always be independent.
The following definition and theorem allow us to leverage Inequalities 1 and 2
when random variables are dependent.

###### Definition 0 (Negative association (Dubhashi and Panconesi, 2009)).

The random variables $X_{i},i\in\\{1,\dots,n\\}$, are negatively associated if
for all disjoint subsets $I,J\subseteq\\{1,\dots,n\\}$ and all non-decreasing
functions $f$ and $g$,

$\displaystyle\mathop{\mathbb{E}}[f(X_{i},i\in I)g(X_{j},j\in
J)]\leq\mathop{\mathbb{E}}[f(X_{i},i\in I)]\mathop{\mathbb{E}}[g(X_{j},j\in
J)].$

###### Theorem 2 (Chernoff–Hoeffding bounds with negative dependence (Dubhashi
and Panconesi, 2009)).

The Chernoff–Hoeffding bounds can be applied to
$X=\sum_{i\in\\{1,\dots,n\\}}X_{i}$ if the random variables
$X_{1},\dots,X_{n}$ are negatively associated.

In order to ease showing negative association, two following properties are
considered (Dubhashi and Panconesi, 2009):

  * –

Closure under Products: If $X_{1},\ldots,X_{n}$ and $Y_{1},\ldots,Y_{m}$ are
two independent families of random variables that are separately negatively
associated, then the family $X_{1},\ldots,X_{n},$ $Y_{1},\ldots,Y_{m}$ is also
negatively associated.

  * –

Disjoint Monotone Aggregation: If $X_{i}$, $i\in\\{1,\dots,n\\}$, are
negatively associated and $\mathcal{A}$ is a family of disjoint subsets of
$\\{1,\dots,n\\}$, then the random variables $f_{A}(X_{i},i\in A)$,
$A\in\mathcal{A}$, are also negatively associated, where the $f_{A}$s are
arbitrary non-decreasing (or non-increasing) functions.

We also use the following result adapted from (Joag-Dev and Proschan, 1983) in
the process of showing a negative association.

###### Theorem 3.

Consider $n$ distinct items from which a sample of size $s$ is chosen without
replacement. Let $X_{i},i\in\\{1,\dots,n\\}$, be random variables indicating
the presence of a specific item in the sample. Random variables
$X_{i},i\in\\{1,\dots,n\\}$, are negatively associated.

### Hypergeometric distribution

The hypergeometric distribution, denoted as $\mathcal{HG}(N,M,r)$,
characterizes the number of specific items within a random sample of size $r$,
drawn without replacement from a population of size $N$, containing $M$ items
of the same type (Hayter, 2012). The expected value of a random variable $X$
following this distribution equals $rM/N$. Additionally, a tail bound for $X$
can be derived as follows:

(3)
$\Pr\big{(}X\leq\mathop{\mathbb{E}}[X]-rt\big{)}\leq\mathit{exp}(-2rt^{2}),$

with $t$ taking values within the interval $(0,M/N)$ (Chvátal, 1979; Skala,
2013).

##  Appendix B Probability of Forming a Probabilistic Quorum

Here we present preliminary results that will be used to analyze ProBFT.
Recall that in ProBFT, in each view $v$, upon receiving the first proposal
from the leader of $v$, a correct replica takes a random sample of size
$o\times q$ and sends a Prepare message to all members of that sample. Upon
receiving $q$ valid Prepare messages, a correct replica forms a probabilistic
quorum. Here we compute the probability that a correct replica forms a
probabilistic quorum when all correct replicas send their Prepare messages. We
later use this result to compute the probability of ensuring termination after
GST and when the leader is correct. With this aim, given a correct process
$i$, assuming that $r$ processes send their Prepare messages, we first compute
the expected number of processes that have $i$ in their samples. Using such an
expected value and the Chernoff bound, we then provide a lower bound for the
probability that $i$ forms a probabilistic quorum. Last, we set $r=|\Pi_{C}|$
and present the desired probability.

###### Lemma 0.

Let $R$ be a subset of replicas with a size of $r$, where each replica $i\in
R$ takes a sample composed of $s$ distinct replicas uniformly at random from
$\Pi$. The expected number of replicas in $R$ with a given replica $j$ in
their samples is $r\times s/n$.

###### Proof.

For each replica $i\in R$, we define an indicator random variable $I_{ij}$
identifying whether replica $j$ is in the sample of $i$:

$\displaystyle I_{ij}=\begin{cases}1\quad\text{$j$ is in the sample of $i$}\\\
0\quad\text{otherwise.}\end{cases}$

The expected value of $I_{ij}$ can be computed as follows:

$\displaystyle\mathop{\mathbb{E}}[I_{ij}]=\Pr(\text{$j$ is in the sample of
$i$})=s/n.$

Let $I_{j}=\sum_{i\in R}I_{ij}$, indicating the number of replicas in $R$ that
have $j$ in their samples. Using the linearity of expectation, the expected
value of $I_{j}$ can be computed as follows:

$\displaystyle\mathop{\mathbb{E}}[I_{j}]=\sum_{i\in
R}\mathop{\mathbb{E}}[I_{ij}]=r\times s/n.$

∎

###### Theorem 2.

Let $R$ be a subset of replicas with size $r$, where each replica $i\in R$
takes a sample composed of $s=o\times q$ distinct replicas uniformly at random
from $\Pi$. If $n<o\times r$, then at least $q$ replicas within $R$ have a
given replica $j$ in their samples with a probability of at least
$1-\mathit{exp}\boldsymbol{(}-((s\times r)/(2n))\times(1-(n/(o\times
r)))^{2}\boldsymbol{)}$.

###### Proof.

Let $I_{j}$ be defined in the same way as in Lemma 1, representing the number
of replicas in $R$ that have replica $j$ in their samples. We need to find a
lower bound for $\Pr(I_{j}\geq q)$. Since $I_{j}$ is obtained by taking the
summation of $r$ i.i.d. indicator random variables, we can use the Chernoff
bound 1 to find a lower bound for $\Pr(I_{j}\geq q)$. If $n<o\times r$, we
have:

$\displaystyle\Pr(I_{j}\geq q)$ $\displaystyle=1-\Pr(I_{j}\leq q)$
$\displaystyle=1-\Pr(I_{j}\leq s/o)\qquad\qquad\qquad\qquad\qquad\text{(since
$s=o\times q$)}$ $\displaystyle=1-\Pr\left(I_{j}\leq\frac{s\times
r}{n}\times\frac{n}{o\times r}\right)$
$\displaystyle=1-\Pr\left(I_{j}\leq\frac{s\times
r}{n}\times\boldsymbol{(}1-(1-\frac{n}{o\times r})\boldsymbol{)}\right)$
$\displaystyle\geq 1-\mathit{exp}\left(-\frac{\frac{s\times
r}{n}\times\left(1-\frac{n}{o\times r}\right)^{2}}{2}\right).$

As $\mathop{\mathbb{E}}[I_{j}]=r\times s/n$ according to Lemma 1, the last
line holds using the Chernoff bound 1 by assuming $\delta=1-n/(o\times r)$.
Note that in Chernoff bound 1, $\delta$ needs to be in the interval $(0,1)$.
Hence, we need to assume that $n<o\times r$. ∎

###### Corollary 0.

Suppose each correct replica takes a sample composed of $s=o\times q$ distinct
replicas uniformly at random from $\Pi$ and multicasts a message to all
members of the sample. Provided that a replica forms a probabilistic quorum
upon receiving $q$ messages if $n<o\times(n-f)$, the probability of forming a
probabilistic quorum by a replica is at least
$1-\mathit{exp}\boldsymbol{(}-q(c-1)^{2}/(2c)\boldsymbol{)}$, where
$c=o\times(n-f)/n$.

###### Proof.

Given a replica $j$, let $I_{j}$ be defined in the same way as in Lemma 1,
representing the number of correct replicas that have $j$ in their samples. We
have:

$\displaystyle\Pr\left(\text{$j$ forms a probabilistic
quorum}\right)=\Pr\left(I_{j}\geq q\right).$

We now use Theorem 2 to find a lower bound for $\Pr\left(I_{j}\geq q\right)$.
Note that in Theorem 2, $r$ is the number of replicas that take random
samples. Since all correct replicas take random samples, $r=n-f$. We have:

$\displaystyle\Pr\left(I_{j}\geq q\right)$ $\displaystyle\geq
1-\mathit{exp}\left(-\frac{\frac{s\times r}{n}\times\left(1-\frac{n}{o\times
r}\right)^{2}}{2}\right)$ (from Theorem 2)
$\displaystyle=1-\mathit{exp}\left(-\frac{\frac{o\times
q(n-f)}{n}\times\left(1-\frac{n}{o\times(n-f)}\right)^{2}}{2}\right)$ (since
$s=o\times q$, and $r=n-f$)
$\displaystyle=1-\mathit{exp}\left(-\frac{q(c-1)^{2}}{2c}\right),$

where $c=o\times(n-f)/n$. ∎

##  Appendix C Theorems related to the optimal behavior of a Byzantine leader

This section presents two theorems related to the optimal behavior of a
Byzantine leader. In the first theorem, we compute a relationship between the
number of replicas that send Prepare (resp. Commit) messages and the
probability of forming a probabilistic quorum in the _prepare_ (resp.
_commit_) phase.

###### Theorem 1 (Theorem 5).

Suppose a replica forms a probabilistic quorum upon receiving $q$ messages.
Consider $r$ replicas, each of which takes a sample composed of $s=o\times q$
distinct replicas uniformly at random from $\Pi$, with the condition that
$n<o\times r$, and sends a message to all members of the sample. The value of
$r$ and the probability that a replica forms a probabilistic quorum are
directly proportional.

###### Proof.

Consider two systems where the first comprises a finite set $\Pi$, and the
second comprises a finite set $\Pi^{\prime}$, with $|\Pi|=|\Pi^{\prime}|=n$.
Further, consider a set $R\subseteq\Pi$ of size $r$ and another set
$R^{\prime}\subseteq\Pi^{\prime}$ of size $r^{\prime}$ such that
$r<r^{\prime}$, $n<o\times r$, and $n<o\times r^{\prime}$. Suppose any replica
within $R$ (resp. $R^{\prime}$) takes a sample of size $s$ uniformly at random
from $\Pi$ (resp. $\Pi^{\prime}$) and sends a message to all members of the
sample. Let $i\in R$ and $j\in R^{\prime}$. In order to prove the theorem, we
need to show that the probability of $j$ forming a probabilistic quorum is
greater than the probability of $i$ forming a probabilistic quorum. If a
random variable $X$ (resp. $Y$) denotes the number of replicas that have $i$
(resp. $j$) in their samples, we need to show that $\Pr(Y\geq q)>\Pr(X\geq
q)$, or equivalently, $\Pr(Y\leq q)<\Pr(X\leq q)$.

As any replica within $R$ (resp. $R^{\prime}$) takes its sample without
replacement, the probability of replica $i$ (resp. $j$) being within the
sample equals $s/n$. It is clear that $X\sim\mathit{Bin}(r,s/n)$ and
$Y\sim\mathit{Bin}(r^{\prime},s/n)$. Thus,

$\displaystyle\Pr(X\leq
q)=\sum_{k=0}^{q}\binom{r}{k}(s/n)^{k}\big{(}1-(s/n)\big{)}^{r-k},$
$\displaystyle\Pr(Y\leq
q)=\sum_{k=0}^{q}\binom{r^{\prime}}{k}(s/n)^{k}\big{(}1-(s/n)\big{)}^{r^{\prime}-k}.$

Without loss of generality, assume that $r^{\prime}=r+1$. In order to show
$\Pr(Y\leq q)\leq\Pr(X\leq q)$, we show that for each $k\in[0,q]$,

$\displaystyle\binom{r+1}{k}(s/n)^{k}\big{(}1-(s/n)\big{)}^{r+1-k}<\binom{r}{k}(s/n)^{k}\big{(}1-(s/n)\big{)}^{r-k}.$

We have:

$\displaystyle n<o\times r^{\prime}=o\times(r+1)$
$\displaystyle\hfill(\text{by assumption})$ $\displaystyle\Rightarrow
q<(r+1)(o\times q/n)$ $\displaystyle\Rightarrow q<(r+1)(s/n)$
$\displaystyle\hfill(s=o\times q)$ $\displaystyle\Rightarrow
q<(r+1)\big{(}1-\boldsymbol{(}1-(s/n)\boldsymbol{)}\big{)}$
$\displaystyle\Rightarrow(r+1)\boldsymbol{(}1-(s/n)\boldsymbol{)}<r+1-q$
$\displaystyle\Rightarrow(r+1)\boldsymbol{(}1-(s/n)\boldsymbol{)}<r+1-k$
$\displaystyle\hfill(\text{since }r+1-q\leq r+1-k)$
$\displaystyle\Rightarrow\frac{r+1}{r+1-k}<\boldsymbol{(}1-(s/n)\boldsymbol{)}^{-1}$
$\displaystyle\Rightarrow\frac{r+1}{r+1-k}<\boldsymbol{(}1-(s/n)\boldsymbol{)}^{r-k-(r+1-k)}$
$\displaystyle\Rightarrow\binom{r+1}{k}(s/n)^{k}\boldsymbol{(}1-(s/n)\boldsymbol{)}^{r+1-k}<\binom{r}{k}(s/n)^{k}\boldsymbol{(}1-(s/n)\boldsymbol{)}^{r-k}.$

∎

###### Theorem 2 (Theorem 4).

Given a Byzantine leader who intends to send multiple proposals, consider the
following two scenarios:  (1) the leader creates non-empty sets
$\Pi^{1},\dots,\Pi^{m+1}$ of replicas, where $m\geq 2$ and
$|\Pi^{1}|\leq|\Pi^{2}|\leq\dots\leq|\Pi^{m+1}|$, and sends a distinct
proposal to each set, and  (2) the leader merges two sets $\Pi^{1}$ and
$\Pi^{2}$ to create a set $\Pi^{1,2}$ and sends $m$ proposals to
$\Pi^{1,2},\Pi^{3},\dots,\Pi^{m+1}$.  The probability of agreement violation
in the second scenario is greater than in the first scenario.

###### Proof.

We need to show that the probability of agreement violation in the second
scenario is greater than in the first scenario. To do so, we show that the
probability of not having any agreement violation in the second scenario is
less than in the first scenario, as $\Pr(\exists\text{ an agreement
violation})$ equals $1-\Pr(\nexists\text{ any agreement violation})$. As the
leader proposes multiple proposals, it is essential to note that there is no
agreement violation if and only if correct replicas find out the faultiness of
the leader and do not decide the proposed values. Accordingly, the proof is
complete by showing that the probability of finding out the faultiness of the
leader by correct replicas in the second scenario is less than in the first
scenario.

For this purpose, consider two correct replicas $i$ and $j$. Assume that
$i\in\Pi^{k}$ and $j\in\Pi^{l}$. There are the following cases for the values
of $k$ and $l$:

  1. (1)

$3\leq k,l\leq m+1$. The probability of finding out the faultiness of the
leader by $i$ and $j$ does not change by altering the scenarios, as from the
viewpoints of $i$ and $j$, the number of replicas whose proposal is different
is not changed.

  2. (2)

$1\leq k\leq 2$ and $3\leq l\leq m+1$. The probability of finding out the
faultiness of the leader by $j$ does not change by altering the scenarios, as
from $j$’s point of view, the number of replicas whose proposal is different
is not changed. However, the probability of finding out the faultiness of the
leader by $i$ in the second scenario is less than in the first scenario. This
is because there are more replicas that propose the same value in the second
scenario, and according to Theorem 5, the probability of deciding a proposal
by $i$ increases in the second scenario. As the probability of deciding a
proposal increases, the probability that $i$ finds out the faultiness of the
leader decreases.

  3. (3)

$3\leq k\leq m+1$ and $1\leq l\leq 2$. This case is similar to the previous
case.

  4. (4)

$k=l=1$. The probability of finding out the faultiness of the leader by $i$
and $j$ in the second scenario is less than in the first scenario exactly
according to the reasoning presented for the second case.

  5. (5)

$k=l=2$. This case is similar to the fourth case.

  6. (6)

$k=1$ and $l=2$. This case is similar to the fourth case.

  7. (7)

$k=2$ and $l=1$. This case is similar to the fourth case.

As in any possible case, the probability of finding out the faultiness of the
leader by any two correct replicas $i$ and $j$ in the second scenario is less
than in the first scenario, the probability of finding out the faultiness of
the leader by all correct replicas in the second scenario is less than in the
first scenario, completing the proof. ∎

##  Appendix D Analysis of ProBFT

###  D.1. The Probability of Termination

To ensure that ProBFT satisfies Probabilistic Termination, we need to
guarantee that, after GST, every correct replica terminates in a view $v$ with
high probability if the leader of $v$ is correct. As described in Section 3,
in ProBFT, a correct replica decides on a value if it has observed a
probabilistic quorum of Prepare messages and a probabilistic quorum of Commit
messages. However, ProBFT lacks deterministic quorums compared to PBFT, so it
is essential to guarantee that the probability of observing probabilistic
quorums is high.

Notice that the number of replicas sending Commit messages will be lower than
the number of replicas sending Prepare messages. However, in Theorem 1, we
stated that a replica observes a quorum with a high probability if the leader
is correct so that most replicas will observe quorums and can terminate.

###### Theorem 1 (Theorem 1).

Suppose each correct replica takes a sample composed of $o\times l\sqrt{n}$
distinct replicas, uniformly at random from $\Pi$, and multicasts a message to
them, where $o\in[1,(n/(n-f))\times(2+\sqrt{3})]$, and $l\geq 1$. Provided
that a replica forms a quorum upon receiving $q=l\sqrt{n}$ messages, the
probability of forming a quorum for a replica is at least
$1-\mathit{exp}(-\sqrt{n})$.

###### Proof.

From Corollary 3, if $q=l\sqrt{n}$, then a replica forms a quorum upon
receiving $q$ messages with a probability of at least
$1-\mathit{exp}\big{(}-\boldsymbol{(}l\sqrt{n}\times(c-1)^{2}\boldsymbol{)}/(2c)\big{)}$,
where $c=o\times(n-f)/n$. Note that if $l=(2c)/(c-1)^{2}$, the probability is
at least $1-\mathit{exp}(-\sqrt{n})$. Based on the assumption that $l\geq 1$,
it follows that $c$ must be in the interval $[2-\sqrt{3},2+\sqrt{3}]$.
Accordingly, $2-\sqrt{3}\leq o\times(n-f)/n\leq 2+\sqrt{3}$. Thus,
$(2-\sqrt{3})\times(n/(n-f))\leq o\leq(2+\sqrt{3})\times(n/(n-f))$. ∎

###### Lemma 0.

If the leader is correct, then a correct replica receives Commit messages from
at least $q$ correct replicas with a probability of at least
$1-\mathit{exp}\boldsymbol{(}-(\alpha-q)^{2}/(2\alpha)\boldsymbol{)}$, where
$\alpha=(s/n)\times(n-f)\times\boldsymbol{(}1-\mathit{exp}(-\sqrt{n})\boldsymbol{)}$.

###### Proof.

Suppose $i$ is a correct replica for which we aim to compute the probability
of receiving Commit messages from $q$ correct replicas. For each correct
replica $j$, let $X_{j}$ denote a random variable defined as follows:

$\displaystyle X_{j}=\begin{cases}1&\text{if $j$ sends a $\textsc{Commit}$
message to $i$}\\\ 0&\text{otherwise}.\end{cases}$

For simplicity of notation, we assume that $\Pi_{C}=\\{1,\dots,n-f\\}$ in this
proof. Furthermore, let $X=\sum_{j=1}^{n-f}X_{j}$ indicating the number of
correct replicas that send Commit messages to $i$. Note that $X\geq q$ means
$i$ receives Commit messages from at least $q$ correct replicas. Consequently,
we need to compute a lower bound for $\Pr(X\geq q)$.

It is essential to note that random variables $X_{j},j\in\Pi_{C}$ are not
independent due to the following reason. Each random variable
$X_{j},j\in\Pi_{C}$ equals 1 if $j$ sends a Commit message to $i$. Replica $j$
sends a Commit message to $i$ if (a) it forms a quorum of Prepare messages and
(b) $i$ is in the random sample of $j$. The point is that the probability of
forming a quorum of Prepare messages by $j$ depends on the probability of
forming a quorum of Prepare messages by any other replica, as sampling in
ProBFT is done without replacement.

As random variables $X_{j},j\in\Pi_{C}$ are dependent, we cannot directly use
the Chernoff bound 1 to compute a lower bound for $\Pr(X\geq q)$. However, we
will show that random variables $X_{j},j\in\Pi_{C}$ are negatively associated,
so the Chernoff bound can be employed to compute a lower bound for $\Pr(X\geq
q)$ according to Theorem 2. To do so, given a correct replica $k$, for each
correct replica $l\in\Pi_{C}$, let random variable $X_{k,l}$ denote the event
of sending a Prepare message from $k$ to $l$. According to Theorem 3, random
variables $X_{k,l},l\in\Pi_{C}$ are negatively associated. Based on the
closure under products property,

$X_{1,1},\dots,X_{1,n-f},X_{2,1},\dots,X_{2,n-f},\dots,X_{n-f,1},\dots,X_{n-f,n-f}$

are negatively associated. We now define a non-decreasing function $I$ as
follows:

$\displaystyle I(l)=\begin{cases}1&\text{if }\sum_{k=1}^{n-f}X_{k,l}\geq q\\\
0&\text{otherwise.}\end{cases}$

Note that function $I(l)$ for each $l\in\Pi_{C}$ is indeed an indicator random
variable determining whether $l$ forms a quorum of Prepare messages. According
to the disjoint monotone aggregation property, random variables
$I(l),l\in\Pi_{C}$ are negatively associated.

Notice that a correct replica $j$ sends a Commit message to $i$ if and only if
(a) $j$ forms a quorum of Prepare messages and (b) $i$ is in the random sample
of $j$. As $i$ being in the random sample of $j$ is independent of forming a
quorum of Prepare messages by $j$, as well as being independent of $i$ being
in the random sample of any other correct replica, random variables
$X_{j},j\in\Pi_{C}$ are negatively associated. We are now ready to compute a
lower bound for $\Pr(X\geq q)$. With this aim, let us first compute the
expected value of $X$. Recall that $X=\sum_{j=1}^{n-f}X_{j}$; using the
linearity of expectation, we have:

$\displaystyle\mathop{\mathbb{E}}[X]$
$\displaystyle=\sum_{j=1}^{n-f}\mathop{\mathbb{E}}[X_{j}]$
$\displaystyle=\sum_{j=1}^{n-f}\Pr(X_{j}=1)$
$\displaystyle=\sum_{j=1}^{n-f}\Pr\big{(}I(j)=1\land\text{$i$ is in the random
sample of $j$}\big{)}$
$\displaystyle=\sum_{j=1}^{n-f}\Pr\big{(}I(j)=1\big{)}\times\Pr(\text{$i$ is
in the random sample of $j$})$
$\displaystyle\geq\sum_{j=1}^{n-f}(1-\mathit{exp}(-\sqrt{n}))\times(s/n)\qquad\text{(using
Theorem~{}\ref{cor:epsilon})}$
$\displaystyle=(s/n)\times(n-f)\times\big{(}1-\mathit{exp}(-\sqrt{n})\big{)}.$

By assuming $\delta=1-(q/\mathop{\mathbb{E}}[X])$, we now use the Chernoff
bound 1 to compute a lower bound for the desired probability:

$\displaystyle\Pr(X\geq q)$ $\displaystyle=1-\Pr(X\leq q)$
$\displaystyle=1-\Pr\big{(}X\leq(1-\delta)\mathop{\mathbb{E}}[X]\big{)}$
$\displaystyle\geq 1-\mathit{exp}(-\delta^{2}\mathop{\mathbb{E}}[X]/2)$
$\displaystyle=1-\mathit{exp}\big{(}-(\mathop{\mathbb{E}}[X]-q)^{2}/(2\mathop{\mathbb{E}}[X])\big{)}$
$\displaystyle\geq 1-\mathit{exp}\big{(}-(\alpha-q)^{2}/(2\alpha)\big{)},$

where
$\alpha=(s/n)\times(n-f)\times\boldsymbol{(}1-\mathit{exp}(-\sqrt{n})\boldsymbol{)}$.
∎

###### Lemma 0.

If the leader is correct, then a correct replica terminates, i.e., it decides
a value, with a probability of at least
$1-\mathit{exp}\boldsymbol{(}-(\alpha-q)^{2}/(2\alpha)\boldsymbol{)}-\mathit{exp}(-\sqrt{n})$,
where
$\alpha=(s/n)\times(n-f)\times\boldsymbol{(}1-\mathit{exp}(-\sqrt{n})\boldsymbol{)}$.

###### Proof.

Suppose the leader is correct. A correct replica $i$ terminates by happening
the following two events:

  * –

$E_{p}$: $i$ forms a quorum of Prepare messages,

  * –

$E_{c}$: $i$ forms a quorum of Commit messages.

Note that these two events are dependent. Thus,

$\displaystyle\Pr(\text{$i$ terminates})$ $\displaystyle=\Pr(E_{c}\cap E_{p})$
$\displaystyle=1-\Pr(\bar{E}_{c}\cup\bar{E}_{p})$ $\displaystyle\geq
1-\Pr(\bar{E}_{c})-\Pr(\bar{E}_{p})$ $\displaystyle=\Pr(E_{c})+\Pr(E_{p})-1$
$\displaystyle=1-\mathit{exp}\big{(}-(\alpha-q)^{2}/(2\alpha)\big{)}-\mathit{exp}(-\sqrt{n}),$

where
$\alpha=(s/n)\times(n-f)\times\boldsymbol{(}1-\mathit{exp}(-\sqrt{n})\boldsymbol{)}$.
The last line holds due to Theorem 1 and Lemma 2. ∎

###### Theorem 4.

If the leader is correct, then every correct replica terminates, i.e., it
decides a value, with a probability of at least
$1-(n-f)\left(\mathit{exp}(-(\alpha-q)^{2}/(2\alpha))-\mathit{exp}(-\sqrt{n})\right)$,
where $\alpha=(s/n)(n-f)(1-\mathit{exp}(-\sqrt{n}))$.

###### Proof.

For each replica $i\in\Pi_{C}$, let $E_{i}$ be the event deciding a value by
$i$. Using Lemma 3, we have:

$\displaystyle\Pr(\cap_{i\in\Pi_{C}}E_{i})$
$\displaystyle\quad=1-\Pr(\cup_{i\in\Pi_{C}}\bar{E}_{i})$
$\displaystyle\quad\geq 1-\sum_{i\in\Pi_{C}}\Pr(\bar{E}_{i})$
$\displaystyle\quad\geq 1-\sum_{i\in\Pi_{C}}\big{(}1-\Pr(E_{i})\big{)}$
$\displaystyle\quad\geq 1-(n-f)+\sum_{i\in\Pi_{C}}\Pr(E_{i})$
$\displaystyle\quad\geq
1-(n-f)+(n-f)\Big{(}1-\mathit{exp}(-(\alpha-q)^{2}/(2\alpha))-\mathit{exp}(-\sqrt{n})\Big{)}$
$\displaystyle\quad\geq
1-(n-f)\left(\mathit{exp}(-(\alpha-q)^{2}/(2\alpha))-\mathit{exp}(-\sqrt{n})\right),$

where
$\alpha=(s/n)\times(n-f)\times\boldsymbol{(}1-\mathit{exp}(-\sqrt{n})\boldsymbol{)}$.
∎

###### Theorem 5 (Theorem 2).

After GST, if the leader of view $v$ is correct, then every correct replica
decides a value in view $v$ with a probability of at least
$1-2(n-f)\times\mathit{exp}\boldsymbol{(}-\Theta(\sqrt{n})\boldsymbol{)}$.

###### Proof.

According to Theorem 4, every correct replica terminates, i.e., it decides a
value, with a probability of at least
$1-(n-f)\times\left(\mathit{exp}(-(\alpha-q)^{2}/(2\alpha))-\mathit{exp}(-\sqrt{n})\right)$,
where $\alpha=(s/n)\times(n-f)\times(1-\mathit{exp}(-\sqrt{n}))$. As
$f=[0,n/3)$, we have:

$\displaystyle\alpha>(2s/3)(1-\mathit{exp}(-\sqrt{n}))\approx 2s/3.$

Since $s=o\times q$, and $q\approx\sqrt{n}$, we have:

$\displaystyle\mathit{exp}\big{(}-(\alpha-q)^{2}/(2\alpha)\big{)}$
$\displaystyle=\mathit{exp}\big{(}-(2oq/3-q)^{2}/(4oq/3)\big{)}$
$\displaystyle\approx\mathit{exp}(-\sqrt{n}).$

Consequently, every correct replica terminates with a probability of at least
$1-2(n-f)\mathit{exp}\boldsymbol{(}-\Theta(\sqrt{n})\boldsymbol{)}$. ∎

###### Theorem 6 (Theorem 3).

In ProBFT, every correct replica eventually decides a value with probability
one.

###### Proof.

Given a correct leader that proposes a value in a view $v$ after GST, every
correct replica decides a value with high probability according to Theorem 2.
However, a correct replica might not decide a value due to not receiving
enough messages to form quorums. Note that there will be an infinite number of
views whose leaders are correct after view $v$. As the number of views
required to decide a value follows a geometric distribution (Hayter, 2012)
with parameter $p\approx 1-2(n-f)\mathit{exp}(-\sqrt{n})$, the probability of
deciding a value by a correct replica in $k$ views whose leaders are correct
is as follows:

$\displaystyle\lim\limits_{k\rightarrow\infty}\Pr(\text{deciding a value in
$k$ views with correct
leaders})\approx\lim\limits_{k\rightarrow\infty}1-(1-p)^{k}=1.$

∎

###  D.2. Probability of Agreement within a View

In ProBFT, different replicas may decide different values since quorum
intersections are not deterministic as in PBFT, but the protocol has to ensure
that the probability of this is low. To cause disagreement in a view of
ProBFT, it is required that two different proposals $m$ and $m^{\prime}$, are
decided on the same view by two distinct correct replicas $i$ and $j$. Before
addressing possible scenarios, it is essential to clarify that since the
leader signs every proposal in our protocol, a prerequisite for disagreement
in the same view in ProBFT is to have a faulty leader.

As discussed in Section 3, there are three scenarios in which agreement can be
violated within a view. The third scenario depicted in Figure 4(c) is optimal.
Hence, we only consider this case in our analysis.

###### Lemma 0.

Given a Byzantine leader who may send several proposals, the probability of
forming a quorum by a correct replica is at most $\mathit{exp}(-q/2)$.

###### Proof.

According to our discussion in Subsection 4, the best strategy for the
Byzantine leader is the one depicted in Figure 4(c). Consequently, we can
consider two sets $\Pi^{1}$ and $\Pi^{2}$, each with a size of $((n-f)/2)+f$.
Let $X$ (resp. $Y$) be a random variable indicating the number of replicas
within $\Pi^{1}$ (resp. $\Pi^{2}$) that have a replica $i$ in their samples.
Suppose we take a random sample $Q$ of size $q$ uniformly at random without
replacement from those replicas that have $i$ in their samples. Let $Z$ denote
the number of replicas that are within $Q\cap\Pi^{1}$, i.e.,
$Z=|Q\cap\Pi^{1}|$. Note that $Z\sim\mathcal{HG}(X+Y,X,q)$. Hence, we can
compute a lower bound using Inequality 3 for $\Pr(Z\geq q)$. In order to use
such an inequality, we first need to compute the expected value of $Z$.
Because of the distribution of $Z$, $\mathop{\mathbb{E}}[Z]=qX/(X+Y)$. Note
that:

$\displaystyle\mathop{\mathbb{E}}[Z]=qX/(X+Y)$
$\displaystyle\Rightarrow\mathop{\mathbb{E}}\left[\mathop{\mathbb{E}}[Z]\right]=\mathop{\mathbb{E}}[qX/(X+Y)]$
(4)
$\displaystyle\Rightarrow\mathop{\mathbb{E}}[Z]=q\mathop{\mathbb{E}}[X/(X+Y)]$

Let $t=1-E[Z]/q$. Using Equation 4, and by considering that $X\gg Y$, we have:

(5) $\displaystyle\begin{split}t&=1-E[Z]/q\\\
&=1-\mathop{\mathbb{E}}[X/(X+Y)]\\\ &\geq 1-\mathop{\mathbb{E}}[X/(X+X)]\\\
&=1/2\end{split}$

We can now use the tail bound presented in Inequality 3 as follows:

$\displaystyle\Pr(Z\geq q)$ $\displaystyle=\Pr\left(Z\geq
q\left(t+E[Z]/q\right)\right)$ $\displaystyle=\Pr\left(Z\geq E[Z]+tq\right)$
$\displaystyle\leq\mathit{exp}(-2qt^{2})$
$\displaystyle\leq\mathit{exp}(-q/2).$

Note that the last line holds because of Relation 5. ∎

###### Theorem 8 (Theorem 6).

Given a Byzantine leader who may send several proposals, the probability of
agreement violation in a view is at most
$\mathit{exp}\boldsymbol{(}-\Theta(\sqrt{n})\boldsymbol{)}^{4}$.

###### Proof.

Given a Byzantine leader who sends at least two proposals, the agreement can
be violated if at least two replicas $i$ and $j$ decide different values. Note
that a replica can decide a value if it forms two consecutive quorums. Suppose
$E_{p}$ and $E_{c}$ denote the event of forming a prepare quorum and the event
of forming a commit quorum, respectively. According to Lemma 7, the
probability of forming a quorum is bounded by $\mathit{exp}(-q/2)$. Hence, the
probability of forming two consecutive quorums can be computed as follows:

$\displaystyle\Pr(E_{p}\cap E_{c})$ $\displaystyle=\Pr(E_{c}\ |\
E_{p})\Pr(E_{p})$ $\displaystyle\leq\Pr(E_{c})\Pr(E_{p})$
$\displaystyle\leq\big{(}\mathit{exp}(-q/2)\big{)}^{2}.$

As replica $i$ is independent of replica $j$, the probability of deciding
values by these replicas is at most
$\boldsymbol{(}\mathit{exp}(-q/2)\boldsymbol{)}^{4}$. ∎

###  D.3. Probability of Agreement with a View Change

###### Lemma 0.

The probability of deciding a value $v$ by a correct replica when $r\leq n/o$
replicas prepared $v$ is at most
$\mathit{exp}\boldsymbol{(}-\delta^{2}oqr/(n(\delta+2))\boldsymbol{)}$, where
$\delta=(n/(or))-1$.

###### Proof.

Assume that a correct replica $i$ decides a value $v$ when a set of replicas
$R$ with a size of $r$ prepared $v$. Let $X$ be a random variable identifying
the number of replicas within $R$ that have $i$ in their commit samples. From
Lemma 1, we know that $\mathop{\mathbb{E}}[X]=sr/n$. As $s=o\times q$,
$\mathop{\mathbb{E}}[X]=oqr/n$. Let $E$ denote the event that $i$ receives $v$
from a probabilistic quorum within $R$. By assuming $\delta=(n/(o\times
r))-1$, we have:

$\displaystyle\Pr(\text{$i$ decides $v$})$ $\displaystyle\ =\Pr(E)$
$\displaystyle\leq\ \Pr(X\geq q)$ $\displaystyle=\
\Pr\big{(}X\geq(1+\delta)oqr/n\big{)}$ $\displaystyle=\
\Pr\big{(}X\geq(1+\delta)\mathop{\mathbb{E}}[X]\big{)}$ $\displaystyle\leq\
\mathit{exp}\big{(}-\delta^{2}\mathop{\mathbb{E}}[X]/(\delta+2)\big{)}\quad(\text{using
the Chernoff bound~{}\ref{ineq:chernof}})$ $\displaystyle=\
\mathit{exp}\big{(}-\delta^{2}oqr/(n(\delta+2))\big{)}.$

∎

###### Theorem 10 (Theorem 7).

The probability of proposing a value $\mathit{val}^{\prime}$ when another
value $\mathit{val}$ has been decided by a correct replica in a prior view is
at most
$\mathit{exp}\boldsymbol{(}-(q\times\delta^{2})/((\delta+1)\times(\delta+2))\boldsymbol{)}$,
where $\delta=2n/(o\times(n+f))-1$.

###### Proof.

Assume that a value $\mathit{val}$ is decided by a correct replica in view
$v$. The leader of view $v+1$ needs to collect $\lceil(n+f+1)/2\rceil$ NewView
messages to be allowed to propose a value. Due to Lemma 9, the number of
replicas that have prepared $\mathit{val}$ is greater than $(n+f)/2$ with a
probability of
$\mathit{exp}\boldsymbol{(}-(q\times\delta^{2})/((\delta+1)\times(\delta+2))\boldsymbol{)}$,
where $\delta=2n/(o\times(n+f))-1$. Hence, there is an intersection between
the set of replicas that have prepared $\mathit{val}$ and the quorum of
NewView messages. ∎

###### Corollary 0 (Corollary 8).

ProBFT guarantees safety with a probability of
$1-\mathit{exp}(-\Theta(\sqrt{n}))$.

###### Proof.

From Theorems 6 and 7, it follows that ProBFT guarantees safety with a
probability of $1-\mathit{exp}(-\Theta(\sqrt{n}))$. ∎