$t^{\prime}$, respectively, such that $\mathtt{T}\cup\mathtt{T}^{\prime}$ is
not a valid set of transactions relative to $S_{0}$. We say that a protocol is
$(\rho_{1},\rho_{2})$-_accountable_ (with security parameter $\epsilon$) if
there exists a _blame_ function $F$ which maps message sets to identifier sets
and satisfies:

  1. (1)

only Byzantine players are ever blamed, meaning that in any execution, and for
any subset of messages $M$ disseminated in that execution, $F(M)$ is a
(possibly empty) set of identifiers belonging to Byzantine players; and

  2. (2)

for each protocol instance in which the adversary is $\rho_{2}$-bounded, the
following holds with probability at least $1-\epsilon$: if a consistency
failure occurs, then there exists some finite set of disseminated messages $M$
with $F(M)$ of weight at least $\rho_{1}$.373737To make the impossibility
result in Theorem 7.3 as strong as possible, this definition deems a set of
blamed identifiers “high-weight” in an execution if there exists any subset of
transactions confirmed in that execution that allocate them a large fraction
of the stake. The protocol used to prove our positive results (Theorems 9.1
and 11.2) offers a stronger form of accountability, with the set of blamed
identifiers allocated a large amount of stake specifically at an “epoch
boundary”; see Section 15.5 for details.

A $\rho$-resilient protocol is vacuously $(\rho_{1},\rho)$-accountable for all
$\rho_{1}$ (with $F(M)=\emptyset$ for all $M$), as with a $\rho$-bounded
adversary consistency violations can occur only with probability at most
$\epsilon$. Thus, in the interesting parameter regime, $\rho_{2}$ exceeds the
values of $\rho$ for which $\rho$-resilient protocols exist. In this regime,
one cannot expect $(\rho_{1},\rho_{2})$-accountability unless
$\rho_{1}\leq\rho_{2}$. For fixed $\rho_{2}$, then, the goal is to design
protocols with $\rho_{1}$ as close to $\rho_{2}$ as possible.

An impossibility result. The proof of Theorem 7.2 implies that, in the
dynamically available, authenticated, and partially synchronous setting, no
blockchain protocol can be $(\rho_{1},\rho_{2})$-accountable for any
$\rho_{1}>0$ and $\rho_{2}\geq 0$. In the dynamically available,
authenticated, and synchronous setting, the interesting case is when
$\rho_{2}\geq 1/2$. (As discussed in Section 6.2 and footnote 33, for every
$\rho<1/2$, there is a Bitcoin-style protocol that is $\rho$-resilient in this
setting.) Neu, Tas, and Tse (Neu et al., 2022) have shown that accountability
is not possible in this case, and their proof is easily adapted to our formal
framework:

###### Theorem 7.3 (Neu, Tas, and Tse (Neu et al., 2022)).

For every $\epsilon<1/4$, $\rho_{1}>0$, and $\rho_{2}\geq 1/2$, there is no
0-resilient blockchain protocol that is $(\rho_{1},\rho_{2})$-accountable with
security parameter $\epsilon$ in the dynamically available, authenticated, and
synchronous setting.

Discussion. The proof of Theorem 7.3 in (Neu et al., 2022), once adapted to
our model, is driven by the possibility of inactive players in the dynamically
available setting. This feature of the setting is necessary for Theorem 7.3 to
hold, as otherwise the set of players allocated non-zero stake by the initial
stake distribution could carry out a permissioned and accountable state
machine replication protocol (e.g., as described in (Sheng et al., 2021)).
Inactive players serve two purposes in the proof: (i) to force active honest
players to confirm transactions when the other players might plausibly be
inactive; and (ii) to allow for “late-arriving” players, who cannot
disambiguate between conflicting sets of allegedly confirmed transactions.

Theorem 9.1 in Section 9 shows that, in the quasi-permissionless,
authenticated, and partially synchronous setting, there is a proof-of-stake
blockchain protocol that is $(1/3,1)$-accountable. Together, Theorems 7.3 and
9.1 therefore establish another formal separation between what is possible in
the dynamically available and quasi-permissionless settings.

###  7.5. Optimistic responsiveness in the dynamically available setting

Ideally, a blockchain protocol would not only be consistent and live in
“worst-case” executions that are consistent with a given setting, but would
also automatically offer stronger guarantees (such as faster transaction
confirmations) for “non-worst-case” executions. Pass and Shi (Pass and Shi,
2018) introduce the notion of _optimistic responsiveness_ to capture this
idea.

Defining optimistic responsiveness. Roughly speaking, for our purposes, an
optimistically responsive protocol is one that confirms transactions at
network speed whenever all players are honest. The formal definition resembles
that of liveness (Section 5.2), with a liveness parameter $\ell$ that scales
with the realized (post-GST) maximum message delay.

More formally, for a given protocol execution in the partially synchronous
setting with no Byzantine players, define $\delta$ as the realized maximum
message delay following GST (which will be at most the worst-case delay bound
$\Delta$, but may be much smaller). Said differently, $\delta$ is the smallest
number such that whenever $p$ disseminates $m$ at $t$, every $p^{\prime}\neq
p$ that is active at $t^{\prime}\geq\text{max}\\{\text{GST},t\\}+\delta$
receives that dissemination at a timeslot $\leq t^{\prime}$. (In the special
case of the synchronous setting, GST$=0$.)

A protocol is then _optimistically responsive_ (with security parameter
$\epsilon$) if there exists a liveness parameter $\ell=O(\delta)$ and a “grace
period” parameter $\Delta^{*}=O(\Delta)$ such that, in every instance
consistent with the setting, with probability at least $1-\epsilon$, the
following condition is satisfied for every $t$. Suppose that:

  * •

$t^{\ast}:=\text{max}\\{\text{GST}+\Delta^{*},t\\}+\ell$ is at most $d$.

  * •

The transaction $\mathtt{tr}$ is received by an honest player at some timeslot
$\leq t$, and $\mathtt{tr}$ is valid for all honest players through timeslot
$t^{*}$ (in the same sense as in the definition of liveness in Section 5.2).

Then, $\mathtt{tr}$ is confirmed for all honest players active at any timeslot
after $t^{\ast}$, and is confirmed for those players at the first timeslot
$\geq t^{\ast}$ at which they are active.383838Intuitively, the “grace period”
$\Delta^{*}$ grants a protocol time to “switch over” to “fast confirmation
mode.” Allowing a grace period that scales with $\Delta$ is natural (and
similar to the definition in Pass and Shi (Pass and Shi, 2018)), and the
impossibility result in Theorem 7.4 holds for this definition of optimistic
responsiveness. The PoS-HotStuff protocol used to prove our positive results
(Theorems 9.1 and 11.2), meanwhile, is in fact optimistically responsive with
$\Delta^{*}=0$, and also satisfies stronger definitions of optimistic
responsiveness (as in, e.g., (Lewis-Pye and Abraham, 2023)).

An impossibility result. The next result asserts that blockchain protocols
cannot be optimistically responsive in the dynamically available setting.

###### Theorem 7.4.

For every $\epsilon<\tfrac{1}{3}$, there is no $0$-resilient blockchain
protocol that is optimistically responsive with security parameter $\epsilon$
in the dynamically available, authenticated, and synchronous setting.

We present a proof of Theorem 7.4 in Section 14.

Theorem 9.1 in Section 9 shows that, in the quasi-permissionless and partially
synchronous setting, there is a proof-of-stake protocol that is optimistically
responsive. Thus, Theorems 7.4 and 9.1 provide yet another formal separation
between the dynamically available and quasi-permissionless settings.

##  8\. General on-chain resources

The discussion in Section 7.1 noted that, in the fully permissionless setting,
protocols cannot generally take advantage of stake or other on-chain resources
because all the honest players with a non-zero amount of some such resource
might well be inactive. The dynamically available setting defined there
insists on a very weak correlation between player activity and on-chain
resource balances: at each timeslot, if there is an honest player with a non-
zero amount of stake, some such player must be active. While Theorem 7.1
demonstrates that this additional assumption can lead to strictly stronger
positive results, Theorems 7.2–7.4 illustrate the persisting limitations of
the dynamically available setting. All three of these impossibility results
take advantage of the fact that, in this setting, network delays and some
types of Byzantine player behavior can be indistinguishable from the
inactivity of honest players. Making further progress requires resolving this
ambiguity via stronger player activity assumptions; this is the idea behind
the “quasi-permissionless” setting.

The quasi-permissionless setting can be defined narrowly for “pure proof-of-
stake protocols,” as is outlined in Section 8.1, but its full versatility is
unlocked once we allow protocols to define arbitrary on-chain resources that
are expected to correlate with player activity. Section 8.2 defines such
“protocol-defined resources” and notes examples of existing protocols that
make use of them. Section 8.3 defines the subclass of “reactive” protocol-
defined resources, which rules out certain “essentially permissioned”
protocols and describes more precisely the nature of the on-chain resources
used by the protocols surveyed in Section 8.2. The general quasi-
permissionless setting is then defined in Section 9 with respect to arbitrary
on-chain resources.

###  8.1. Looking forward to the quasi-permissionless setting

For the purposes of this section, by a “proof-of-stake (PoS)” protocol, we
mean a blockchain protocol $(\Sigma,\mathcal{O},\mathcal{C})$ in which
$\mathcal{O}$ contains no permitters.393939Technically, a blockchain protocol
with no stake distribution (and no permitters) qualifies as a PoS protocol
according to this definition. To offer any non-trivial guarantees in a
permissionless setting, however, blockchain protocols without permitters must
make use of a non-trivial stake distribution and player activity assumptions
with respect to it (otherwise, all honest players might well be inactive at
all timeslots). (The full definition of PoS protocols, in the more general
setting that allows for protocol-defined resources, is stated in Section 9.1.)
Typically, PBFT-style PoS protocols such as Algorand require stronger
assumptions on the set of active players than are provided by the dynamically
available setting:

Quasi-permissionless setting (specifically for PoS protocols). An execution of
a proof-of-stake protocol is consistent with the quasi-permissionless setting
if:

  * Whenever $p$ is honest and active at $t$, with $\mathtt{T}$ the set of transactions confirmed for $p$ at $t$ in this execution, every honest player that is assigned a non-zero amount of stake in $\mathtt{S}(S_{0},\mathtt{T})$ is active at $t$.

By definition, every execution of a PoS protocol consistent with the quasi-
permissionless setting is also consistent with the dynamically available
setting.

Sections 8.2 and 8.3 describe terminology for discussing forms of on-chain
resources other than stake, as are used by, for example, Byzcoin (Kokoris
Kogias et al., 2016), Hybrid (Pass and Shi, 2016), and Solida (Abraham et al.,
2016). Readers uninterested in on-chain resources other than stake can keep in
mind the simplified version of the quasi-permissionless setting defined above
and skip to Section 9.2.

###  8.2. Protocol-defined resources

What would be an on-chain resource other than stake? Consider, for example,
the two-stage protocol of Andrychowicz and Dziembowski (Andrychowicz and
Dziembowski, 2015). The basic idea is to, in the first stage, employ a proof-
of-work protocol in which players compete to establish identities that are
recorded as having provided PoW. (For example, one could interpret a public
key as “established” in a Bitcoin-style protocol if it contributed one of the
first 100 blocks of the longest chain.) After a set of identities has been
established, in the second stage, those identities then carry out a version of
the (permissioned) Dolev-Strong protocol (Dolev and Strong, 1983) to execute
an instance of single-shot consensus. (The Andrychowicz-Dziembowski protocol,
like the Dolev-Strong protocol, is intended for the synchronous setting.) This
idea translates to a protocol that relies on one external resource (for the
PoW) and one on-chain resource (e.g., a 0-1 function encoding which identities
have permission to participate in the second-stage permissioned protocol).
Protocols of this type are typically assumed to operate in a generalization of
the simplified quasi-permissionless setting described in Section 8.1, with all
honest players with on-chain resources assumed to be active.

Taking this idea further, protocols such as Byzcoin (Kokoris Kogias et al.,
2016), Hybrid (Pass and Shi, 2016), and Solida (Abraham et al., 2016)
implement state machine replication (Schneider, 1990) by using PoW to select a
rolling sequence of committees. The basic idea is that, once a committee is
selected, it should carry out a PBFT-style protocol to implement the next
consensus decision. This consensus decision includes the next sequence of
transactions to be committed to the blockchain and also determines which
identifiers have provided sufficient PoW in the meantime for inclusion in the
next committee. Again, such protocols are assumed to operate in a
generalization of the simplified quasi-permissionless setting: all honest
players with on-chain resources (i.e., those belonging to the current
committee) are required to be active for the PBFT-style protocol to function
correctly.

Defining protocol-defined resources. A _protocol-defined resource_ is a
function $\mathtt{S}^{\ast}$ such that $\mathtt{S}^{\ast}(M,id)\in\mathbb{N}$
for every identifier $id$ and set of messages $M$, and such that
$\mathtt{S}^{\ast}(M,id)=0$ for identifiers $id$ outside of
$\cup_{p\in\mathcal{P}}\mathtt{id}(p)$. Let $\mathtt{S}^{\ast}(M)$ denote the
function which on input $id$ gives output $\mathtt{S}^{\ast}(M,id)$.

Thus, an honest player that has received the messages $M$ by timeslot $t$
regards $\mathtt{S}^{\ast}(M)$ as the balances of the protocol-defined
resource at that time. (In effect, each protocol-defined resource specifies
its own message semantics and confirmation rule.) By an _on-chain_ resource,
we mean a resource that is either stake or protocol-defined.

###  8.3. Reactive resources: not all protocol-defined resources are created
equal

Because the definition of protocol-defined resources is so general,
generalizing the simplified quasi-permissionless setting to arbitrary such
resources can lead to the consideration of “essentially permissioned”
protocols. For example, while the two-stage protocol by Andrychowicz and
Dziembowski (Andrychowicz and Dziembowski, 2015) only asks the selected
committee to carry out a single consensus decision, a variant of that protocol
could select a single static committee that is then tasked with carrying out
state machine replication (e.g., using a PBFT-style permissioned protocol) for
an unbounded duration. This protocol can be viewed as operating in a version
of the quasi-permissionless setting with unrestricted protocol-defined
resources, with one such resource indicating membership in the static
committee and the quasi-permissionless assumption then requiring that
committee members be active for the remainder of the protocol’s execution. Can
one call such a protocol “(quasi-)permissionless” with a straight face?

Why aren’t the Byzcoin, Hybrid, and Solida protocols “essentially
permissioned” in a similar sense? And why didn’t this issue come up in Section
5 for the specific case of stake as an on-chain resource? Because stake, and
the protocol-defined resources used by the Byzcoin, Hybrid, and Solida
protocols, can be forced to change through the confirmation of certain
messages and transactions that might be issued by the environment or by
players. (E.g., recall from Section 5.1 our assumption that stake can always
be transferred via an appropriate transaction.) To rule out “essentially
permissioned” protocols, then, it must be possible for players to eventually
lose their on-chain resources. This leads to the notion of “reactive”
resources, which cannot be held indefinitely by any players that own no
external resources or stake.

Generalizing the sense in which stake can be forced to change. Formally,
consider a protocol that uses $k$ permitters with corresponding resources
$\mathcal{R}_{1},\dots,\mathcal{R}_{k}$. Consider an execution of this
protocol and a time interval $I=[t_{1},t_{2}]$. We say that a player $p$:

  * •

owns no external resources in $I$ if $\mathcal{R}_{i}(p,t)=0$ for all $t\in I$
and $i\in\\{1,\ldots,k\\}$;

  * •

owns no stake in $I$ if, for every $id\in\texttt{id}(p)$,
$\mathtt{S}(S_{0},\mathtt{T},id)=0$ whenever $\mathtt{T}$ is the set of
transactions confirmed for an honest player $p^{\prime}$ at a timeslot $t\in
I$;

  * •

owns none of a protocol-defined resource $\mathtt{S}^{\ast}$ at $t$ if, for
every $id\in\texttt{id}(p)$, $\mathtt{S}^{\ast}(M,id)=0$ whenever $M$ is the
set of messages received by an honest player $p^{\prime}$ at timeslots $\leq
t$.

Reactive sets of resources. Let $\epsilon\geq 0$ be a determined security
parameter. A set
$\mathcal{S}=\\{\mathtt{S}^{*}_{1},\ldots,\mathtt{S}^{*}_{j}\\}$ of on-chain
resources used by a protocol is _reactive_ if there exists a value $\ell$,
which may depend on the determined inputs but must be sublinear in $d$, such
that the following condition holds with probability at least $1-\epsilon$ for
each protocol instance:

  * If $t_{1}\geq$ GST, $t_{2}-t_{1}\geq\ell$, $t_{2}\leq d$, and each of the players of some set $P$ owns no external resources or stake in $I:=[t_{1},t_{2}]$, then for every $p\in P$ and $i\in\\{1,\ldots,j\\}$, $p$ owns none of $\mathtt{S}^{\ast}_{i}$ at $t_{2}$.

Restricting to reactive sets of on-chain resources. The quasi-permissionless
setting, defined in the next section, requires a protocol to explicitly list
the on-chain resources to which the setting’s player activity assumption
applies. Unless one wants to also consider permissioned protocols, one
generally restricts attention to protocols that use a reactive set of on-chain
resources (or some variation thereof).

##  9\. The quasi-permissionless setting

###  9.1. Defining the setting

For the purposes of the general quasi-permissionless setting, a protocol is a
tuple $(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$, where
$\Sigma,\mathcal{O}$, and $\mathcal{C}$ are as in the fully permissionless and
dynamically available settings, and where
$\mathcal{S}=\\{\mathtt{S}^{\ast}_{1},\dots,\mathtt{S}^{\ast}_{k}\\}$ is a set
of on-chain resources (possibly including stake $\mathtt{S}$). A proof-of-
stake (PoS) protocol is then, for the purposes of this paper, one in which
$\mathcal{O}$ contains no permitters and $\mathcal{S}$ contains no on-chain
resources other than stake.

Quasi-permissionless setting. Consider the protocol
$(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$, where
$\mathcal{S}=\\{\mathtt{S}^{\ast}_{1},\dots,\mathtt{S}^{\ast}_{k}\\}$. By
definition, an execution of the protocol is consistent with the quasi-
permissionless setting if the following hold for all $i\in\\{1,\ldots,k\\}$:

  * (i)

If $\mathtt{S}_{i}^{\ast}=\mathtt{S}$ then, whenever $p$ is honest and active
at $t$, with $M$ the set of messages received by $p$ at timeslots $\leq t$ in
this execution, every honest player that is assigned a non-zero balance by
$\mathtt{S}(S_{0},M)$ is active at $t$. (Recall that $\mathtt{S}(S_{0},M)$ is
shorthand for $\mathtt{S}(S_{0},\mathcal{C}(M))$.)

  * (ii)

If $\mathtt{S}_{i}^{\ast}\neq\mathtt{S}$ then, whenever $p$ is honest and
active at $t$, with $M$ the set of messages received by $p$ at timeslots $\leq
t$ in this execution, every honest player that is assigned a non-zero balance
by $\mathtt{S}^{\ast}_{i}(M)$ is active at $t$.

Thus, the quasi-permissionless setting insists on activity from every honest
player that possesses any amount of any of the on-chain resources listed in
the protocol description.404040An interesting direction for future work is to
investigate analogs of the quasi-permissionless setting for protocols that use
only external resources. For example, what becomes possible when the sum of
the resource balances of each external resource is fixed and known? Every
execution consistent with the quasi-permissionless setting is also consistent
with the dynamically available setting.414141A protocol
$(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$ can be treated in the
dynamically available setting by ignoring $\mathcal{S}$. The definition of
$\rho$-bounded adversaries remains the same as in Section 5.1, and refers only
to external resources and stake.

Proving impossibility results for the quasi-permissionless setting. As noted
in Section 8.3, coupling the activity assumptions of the quasi-permissionless
setting with unrestricted protocol-defined resources allows for “essentially
permissioned” protocols, such as protocols that treat the initial stake
distribution as a (non-reactive) protocol-defined resource encoding the
identifiers allowed to participate in some permissioned consensus protocol.
Thus, proving impossibility results for the quasi-permissionless setting (that
do not already apply to the permissioned setting) requires imposing
constraints on the protocol-defined resources allowed, such as the reactivity
restriction from Section 8.3. Theorem 11.1 in Section 11 is an example of such
an impossibility result.

###  9.2. A positive result for the quasi-permissionless setting

The next result provides a blockchain protocol that, in the quasi-
permissionless setting, overcomes the impossibility results in Theorems
7.2–7.4 for the dynamically available setting. Specifically, in the quasi-
permissionless, authenticated, and partially synchronous setting:

  * •

For every $\rho<1/3$, the blockchain protocol is $\rho$-resilient (with
respect to consistency and liveness) and induces a $\rho$-resilient protocol
for solving BA. (Cf., Theorem 7.2.)424242As discussed at length in Section
2.4, several previous works strongly hint at such a result while stopping
short of providing a full proof.

  * •

The protocol is $(1/3,1)$-accountable. (Cf., Theorem 7.3.)434343Sheng et al.
(Sheng et al., 2021) show how to convert several permissioned protocols into
$(1/3,2/3)$-accountable protocols. Our protocol achieves
$(1/3,1)$-accountability through more stringent requirements for block
confirmation. Roughly, an honest player will regard a block of transactions as
confirmed only after seeing a full “plausible history” (at least within each
“epoch”) leading to confirmation of that block.

  * •

The protocol is optimistically responsive with $\Delta^{*}=0$. (Cf., Theorem
7.4.)

Moreover, the protocol can be made deterministic.

###### Theorem 9.1.

Consider the quasi-permissionless, authenticated, and partially synchronous
setting. For every $\rho<1/3$, there exists a deterministic and
$\rho$-resilient PoS blockchain protocol. Moreover, the protocol can be made
$(1/3,1)$-accountable and optimistically responsive.

We present the proof of Theorem 9.1 in Section 15. The protocol used in the
proof, which we call the PoS-HotStuff protocol, can be viewed as an extension
of the (permissioned) HotStuff protocol (Yin et al., 2019) to a permissionless
PoS protocol. (One could similarly adapt a protocol such as PBFT (Liskov and
Castro, 1999).) Although the protocol is designed to make the proof of Theorem
9.1 as straightforward as possible, the proof is complicated by a number of
difficulties that may not be immediately apparent. For example, one issue
revolves around the heights at which the protocol ensures that players receive
_direct_ confirmation of a block (e.g., for HotStuff, receiving three quorum
certificates (QCs) for a block as opposed to only for one of its descendant
blocks). Player changes at an indirectly confirmed height can lead to
consistency violations. One approach to addressing this issue is to ensure
direct confirmation of blocks at all heights, but honest leaders must then re-
propose blocks initially proposed by Byzantine leaders, which in turn
threatens liveness (which requires the confirmation of honestly proposed
blocks). Our proof instead divides the execution into epochs, each of which
contains potentially infinitely many views. Each epoch is concerned with
producing confirmed blocks up to a certain height, but may also produce blocks
of greater height that receive three QCs in three rounds of voting but are not
considered confirmed. More generally, the proof of consistency must now
address the fact that different players may see different versions of the
blockchain (especially during asynchrony) and therefore possess different
beliefs as to who should be producing and voting on the block in each round.
In particular, the definition of a “quorum certificate” is now both player-
and time-relative. See Section 15.3 for a more detailed overview of some of
the technical challenges involved in the proof of Theorem 9.1.

It would be interesting to extend versions of Theorem 9.1 to one or more of
the major PoS blockchain protocols that have been deployed in practice.

##  10\. Long-range attacks

A weakly dynamic adversary. Long-range attacks on PoS protocols fundamentally
involve the corruption of honest players (i.e., a non-static adversary). To
make our impossibility result as strong as possible, we consider a
particularly restricted type of dynamic adversary. Given a protocol with
security parameter $\epsilon\geq 0$ (in the sense of Section 5.2), we consider
only protocol instances in which:

  * •

Byzantine players have no initial stake.

  * •

Except with probability at most $\epsilon$, no stake is transferred from
honest to Byzantine players.

  * •

At exactly one timeslot $t_{c}$ in a protocol execution, there may be a
_corruption event_ for some set $P$ of players that have “cashed out,” in the
sense that: for every honest player $p$, if $\mathtt{T}$ is the set of
transactions confirmed for $p$ at $t_{c}$, then $\mathtt{S}(S_{0},\mathtt{T})$
allocates zero stake to all identifiers belonging to players in $P$.

If a corruption event occurs at $t_{c}$, then:

    * –

The state diagram of each player $p\in P$ may be replaced by an arbitrary
state diagram, and $p$ may begin in any state of that diagram at $t_{c}$.

    * –

If $P_{B}$ was the set of initially Byzantine players, then at $t_{c}$ the set
of Byzantine players becomes $P_{B}^{\ast}:=P_{B}\cup P$.

    * –

As in Section 3.3, message entries permitted for one Byzantine player are
permitted for all Byzantine players: if $p\in P_{B}^{\ast}$ and $t\geq t_{c}$,
then all entries permitted for $p$ at $t$ are also permitted for all
$p^{\prime}\in P^{\ast}_{B}$.

The first restriction ensures that an adversary cannot use the initial stakes
of the Byzantine players to cause violations of consistency or liveness. The
second ensures that the environment cannot conspire with Byzantine players to
cause such violations by issuing transactions that would force the transfer of
stake to them. The third restriction (to “cashed-out” honest players) prevents
an adversary from causing such violations by using a corruption event to
acquire stake from stake-holding honest players.

Desired property. A blockchain protocol is _invulnerable to simple long-range
attacks_ if it satisfies consistency and liveness (Section 5.2) with a dynamic
adversary of the restricted type above.

Theorem 10.1 below establishes that PoS protocols cannot be invulnerable to
simple long-range attacks unless they make use of cryptographic primitives
with certain time-dependent features, such as VDFs or ephemeral
keys.444444Section 3.4 shows how VDFs and ephemeral keys can be modeled within
our framework via suitably defined oracles. Neither of these oracles is time
malleable in the sense defined in this section (with the VDF oracle violating
the first condition and the ephemeral keys oracle the second condition). One-
shot signatures (Amos et al., 2020) could also potentially play a role similar
to ephemeral keys in defending against long-range attacks.

Time malleable oracles. We call an oracle $O$ _time malleable_ if it satisfies
the following conditions for each response function $f$ in the support of $O$
and for every pair $(q,t)$:

  * •

$f(q,t)=(r,t)$ for some $r$, and;

  * •

If $f(q,t)=(r,t)$ then $f(q,t^{\prime})=(r,t^{\prime})$ for all $t^{\prime}$.

These conditions assert that every oracle response is delivered
instantaneously and is independent of the timeslot in which the query is made.

###### Theorem 10.1.

For every $\epsilon<\tfrac{1}{4}$, no PoS blockchain protocol that uses only
time malleable oracles is invulnerable to simple long-range attacks with
security parameter $\epsilon$ in the quasi-permissionless, authenticated, and
synchronous setting.

###### Proof.

Towards a contradiction, suppose there is a PoS blockchain protocol
$(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$ (with
$\mathcal{S}=\\{\mathtt{S}\\}$) that is invulnerable to simple long-range
attacks in the setting described, with security parameter
$\epsilon<\tfrac{1}{4}$ and liveness parameter $\ell$ (see Section 5.2). Fix
all parameter inputs (see Section 3.1), which will be the same for all
protocol instances considered. Assume that the duration $d$ is larger than
$\ell$. Choose non-empty and pairwise disjoint sets of players $P_{0}$,
$P_{1}$, and $P_{2}$. Let $S_{0}$ denote the protocol’s initial stake
distribution, which we assume is not the all-zero allocation. Assign
identifiers to players such that every identifier assigned non-zero stake in
$S_{0}$ belongs to $\mathtt{Id}(p)$ for some $p\in P_{0}$. Set
$\mathtt{Id}_{i}:=\cup_{p\in P_{i}}\mathtt{Id}(p)$ for $i\in\\{0,1,2\\}$.
Define $\mathtt{T}_{1}$ and $\mathtt{T}_{2}$ to be disjoint sets of
transactions, each valid with respect to $S_{0}$, such that:

  1. (i)

For $i\in\\{1,2\\}$, each $\mathtt{tr}\in\mathtt{T}_{i}$ takes some
$id\in\mathtt{Id}_{0}$ such that $\mathtt{S}(S_{0},\emptyset,id)>0$ and
transfers all the corresponding stake to an identifier in $\mathtt{Id}_{i}$.

  2. (ii)

For $i\in\\{1,2\\}$, $\mathtt{S}(S_{0},\mathtt{T}_{i})$ allocates all stake to
identifiers in $\mathtt{Id}_{i}$.

The sets $\mathtt{T}_{1}$ and $\mathtt{T}_{2}$ exist because we assume that
stake is transferable (see Section 5.1). Note that the set
$\mathtt{T}_{1}\cup\mathtt{T}_{2}$ is not valid with respect to $S_{0}$. This
completes the setup.

We first consider two instances of the protocol (in the sense of Section 6.2),
$\mathtt{I}_{1}$ and $\mathtt{I}_{2}$. For $i\in\\{1,2\\}$, instance
$\mathtt{I}_{i}$ is specified as follows:

  * •

$\mathcal{P}:=P_{0}\cup P_{i}$, with all players honest.

  * •

All players are active at all timeslots $\leq d$.

  * •

All disseminations are received by all other players at the next timeslot.

  * •

The environment sends all transactions in $\mathtt{T}_{i}$ to all players at
timeslot 1.

Choose $t^{\ast}>\ell$. Generate “coupled executions” of the instances $I_{1}$
and $I_{2}$ by first sampling a single response function (shared across the
two executions) for each oracle $O\in\mathcal{O}$ according to the
distribution specified by $O$ and then sampling state transitions (timeslot-
by-timeslot) independently in each of the instances. For $i=1,2$, let $M_{i}$,
a random variable, denote the set of all messages disseminated by players at
timeslots $\leq t^{*}$ in such an execution of the protocol instance $I_{i}$.

Liveness implies that, for each $i=1,2$,
$\mathbb{P}(\mathcal{C}(M_{i}))=\mathtt{T}_{i})\geq 1-\epsilon$. Because the
output of a confirmation rule is a valid set of transactions (see Section 5.1)
and $\mathtt{T}_{1}\cup\mathtt{T}_{2}$ is not valid with respect to $S_{0}$
(by construction), there must be a value of $i^{*}\in\\{1,2\\}$ such that,
with probability at least $\tfrac{1}{2}(1-2\epsilon)=\tfrac{1}{2}-\epsilon$
over the messages $(M_{1},M_{2})$ disseminated in the coupled executions:

  * (1)

$\mathcal{C}(M_{i})=\mathtt{T}_{i}$ for $i=1,2$;

  * (2)

$\mathcal{C}(M_{1}\cup M_{2})$ does not contain all of $\mathtt{T}_{i^{*}}$.

Without loss of generality, suppose $i^{\ast}=1$.

We then consider a third protocol instance $\mathtt{I}_{3}$, specified as
follows:

  * •

Players in $P_{0}$ and $P_{1}$ are initially honest, while players in $P_{2}$
are initially Byzantine.

  * •

All players are active at all timeslots $\leq d$.

  * •

All disseminations are received by all other players at the next timeslot.

  * •

The environment sends all transactions in $\mathtt{T}_{1}$ to all players at
timeslot 1.

  * •

Players in $P_{2}$ perform no actions until $t^{\ast}$, and perform no actions
at any timeslot unless a corruption event occurs.

  * •

If all transactions in $\mathtt{T}_{1}$ are confirmed for all players in
$P_{0}\cup P_{1}$ by $t^{\ast}$, then a corruption event for players in
$P_{0}$ occurs at $t_{c}=t^{\ast}$. (Thus, a corruption event occurs with
probability at least $1-\epsilon$.) The (Byzantine) players of $P_{2}$ are in
a position to detect this event because they receive the same messages at the
same timeslots as the players of $P_{0}\cup P_{1}$.

  * •

The environment sends the players in $P_{0}\cup P_{2}$ all transactions in
$\mathtt{T}_{2}$ at $t_{c}$. (Provided a corruption event occurs, these
transactions do not transfer stake from honest to Byzantine players.)454545If
we allowed the environment to issue transactions as a function of players’ and
oracles’ coin flips (see footnote 31 in Section 6.2), then these transactions
could be issued only when there is a corruption event, guaranteeing that no
stake is ever transferred from honest to Byzantine players.

  * •

If a corruption event occurs at timeslot $t_{c}$, then at this timeslot the
players in $P_{0}\cup P_{2}$ simulate the first $t_{c}$ many timeslots of the
protocol instance $\mathtt{I}_{2}$, disseminating all messages as dictated by
the protocol instructions.

Crucially, when a corruption event occurs at $t_{c}$, the players in
$P_{0}\cup P_{2}$ are capable of simulating the first $t_{c}$ timeslots of the
protocol instance $\mathtt{I}_{2}$. This is true because:

  1. (i)

All oracles in $\mathcal{O}$ are time malleable. (Otherwise, the players of
$P_{0}\cup P_{2}$ either wouldn’t be able to reconstruct oracle queries from
earlier timeslots $t^{\prime}<t_{c}$ at the timeslot $t_{c}$, or wouldn’t
receive the oracle responses quickly enough to simulate many timeslots in a
single one.)

  2. (ii)

The instructions carried out by each Byzantine player can depend on the
messages and oracle responses received by other Byzantine players, and if
$p\in P_{B}^{\ast}$, then any entry/message permitted for $p$ is permitted for
all $p^{\prime}\in P_{B}^{\ast}$. (If Byzantine players couldn’t
instantaneously simulate each other, they would need to communicate explicitly
to carry out the simulation, and message delays would then preclude the
simulation of many timeslots in a single one.)

Let $M$ denote the set of all messages disseminated by the end of timeslot
$t_{c}$ in instance $\mathtt{I}_{3}$. By construction, conditioned on a
corruption event, $M$ has the same distribution as the union $M_{1}\cup M_{2}$
of messages disseminated in the coupled executions of $I_{1}$ and $I_{2}$
(conditioned on the event that $\mathcal{C}(M_{1})=\mathtt{T}_{1}$).
Intuitively, in this case, an execution of $I_{3}$ generates a “superposition”
of executions of $I_{1}$ and $I_{2}$—one from the “honest execution” of
$I_{1}$ up to timeslot $t_{c}$, the other from the simulation of $I_{2}$ that
the Byzantine players carry out at $t_{c}$—which share a common set of oracle
response functions. Thus, whenever conditions (1) and (2) above hold for
$M_{1}$ and $M_{2}$ (which in particular implies
$\mathcal{C}(M_{1})=\mathtt{T}_{1}$ and a corruption event), instance
$\mathtt{I}_{3}$ sees a consistency violation, with at least one transaction
of $\mathtt{T}_{1}$ flipping from confirmed (at $t_{c}$) to unconfirmed (at
$t_{c}+1$). Because (1) and (2) hold with probability at least $1/2-\epsilon$
and $\epsilon<\tfrac{1}{4}$, the given protocol does not satisfy consistency
(with security parameter $\epsilon$), a contradiction. ∎

Discussion. The proof of Theorem 10.1 uses the fact that, in the quasi-
permissionless setting, the set $\mathcal{P}$ of players may be unknown
($P_{0}\cup P_{1}$, $P_{0}\cup P_{2}$, or $P_{0}\cup P_{1}\cup P_{2}$). The
proof holds when there is a finite and determined upper bound on the number of
players (namely, $|P_{0}\cup P_{1}\cup P_{2}|$). Neither sybils nor the
possibility of player inactivity are used in the proof (players are always
active and can use unique identifiers). Alternatively, the proof can be
rephrased as working with a known player set ($\mathcal{P}=P_{0}\cup P_{1}\cup
P_{2}$) but relying instead on the possibility that the players of $P_{1}$ or
$P_{2}$ might be permanently inactive.

Given that all players are always active and all messages are received
promptly after dissemination, the proof of Theorem 10.1 also relies on our
assumption that the confirmation rule $\mathcal{C}$ is a function only of the
set of messages received by an honest player, and not on the timeslots in
which the player received those messages (see footnote 26 in Section 5.1).
Intuitively, a timing-dependent confirmation rule could, in instance
$\mathtt{I}_{3}$, resolve the conflicts between $\mathtt{T}_{1}$ and
$\mathtt{T}_{2}$ according to the timeslots at which a player received the
messages in $M_{1}$ and $M_{2}$ (as opposed to using the timing-independent
output $\mathcal{C}(M_{1}\cup M_{2})$ assumed in the proof). The proof can be
modified to apply also to timing-dependent confirmation rules by using players
that become active only after the dissemination of all the messages in $M_{1}$
and $M_{2}$; such players would receive all those messages at the same time
and would not know which way to resolve the conflicts between the transactions
in $\mathtt{T}_{1}$ and $\mathtt{T}_{2}$.464646One of the simpler practical
approaches to repelling long-range attacks is to require that newly active
players communicate out-of-protocol with other (hopefully honest) players that
have been active in order to learn which older messages should be regarded as
confirmed; this idea relates to the “weak subjectivity” notion proposed by
Buterin (Buterin ., 2014), and is also explored by Daian, Pass, and Shi (Daian
et al., 2019). For similar reasons, the proof can also be extended to timing-
dependent confirmation rules with always-active players in the partially
synchronous setting (with unbounded message delays substituting for unbounded
player inactivity).

##  11\. Restricting environments instead of executions

Thus far, we have focused on possibility and impossibility results in various
settings with respect to a $\rho$-bounded adversary (for some $\rho\in[0,1]$),
meaning for executions of a protocol in which Byzantine players never control
more than a $\rho$ fraction of an external resource or of the stake controlled
by active players (see Section 5.1). The restriction on external resources,
which evolve independently of a protocol’s execution, is straightforward to
interpret and mirrors the restrictions on the fraction of Byzantine players
that are familiar from the study of permissioned consensus protocols.

Stake, on the other hand, evolves in tandem with a protocol’s execution. (The
closest analog in a traditional permissioned state machine replication model
would be if the set of Byzantine players was somehow a function of the set of
transactions confirmed by the protocol.) The amount of stake controlled by
Byzantine players—and, thus, whether an execution qualifies as one for which a
$\rho$-resilient protocol must guarantee consistency and liveness—is
determined by the set of confirmed transactions. Even after fixing the initial
stake distribution and the transactions issued by the environment, this set
can depend on the realized network delays, the strategies of the Byzantine
players, and (somewhat circularly) on the decisions of the protocol itself.

Section 11.1 sharpens this point with a concrete example that shows how
network delays can result in all stake being transferred to a single Byzantine
player, despite a seemingly reasonable initial stake distribution and set of
issued transactions. Section 11.2 builds on this idea and, in Theorem 11.1,
shows that no blockchain protocol can guarantee consistency and liveness (for
all executions) with respect to any non-trivial adversary in the quasi-
permissionless and partially synchronous setting. Section 11.3 introduces a
natural restriction on the transactions issued by the environment—intuitively,
that a transaction is issued only once its “prerequisite transactions” have
been confirmed by some honest player—under which the guarantees of Theorem 9.1
can be extended (with the same protocol) to apply no matter what the realized
network delays and Byzantine player strategies.

###  11.1. The Payment Circle

A simple example illustrates how, even with an initial distribution that
allocates Byzantine players at most a $\rho$-fraction of the stake, and even
with a seemingly benign set of transactions, specific executions may lead to
Byzantine players controlling more than a $\rho$ fraction of the stake.
Consider a set $\\{p_{0},p_{1},\ldots,p_{n-1}\\}$ of $n$ players, each with a
single unit of initial stake. Suppose $p_{0}$ is Byzantine and the other $n-1$
players are honest. Imagine that, in each of $n$ consecutive rounds, for each
player $p_{i}$, the environment issues a new transaction that transfers a
single unit of stake from $p_{i}$ to $p_{i+1\bmod n}$. Let $\mathtt{T}$ denote
the set of these $n^{2}$ transactions. Each round of $n$ transactions leaves
everyone’s stake unaffected—each $p_{i}$ still controls one unit of stake—so
what could possibly go wrong?

Suppose we are working in the partially synchronous setting, and that GST is
well after the $n$ rounds in which the transactions $\mathtt{T}$ are issued by
the environment. Perhaps, for some subset
$\mathtt{T}^{\prime}\subseteq\mathtt{T}$, only one honest player $p$ receives
the transactions in $\mathtt{T}\setminus\mathtt{T}^{\prime}$ from the
environment. Further, prior to GST, network delays may prevent $p$ from
disseminating these transactions to other honest players. If
$\mathtt{T}^{\prime}$ is a valid set of transactions and GST is sufficiently
large, liveness then forces the honest players other than $p$ to confirm all
the transactions in $\mathtt{T}^{\prime}$. (For these players, the execution
is indistinguishable from a synchronous execution in which the transactions in
$\mathtt{T}^{\prime}$ are the only ones ever issued by the environment.)

Now choose $\mathtt{T}^{\prime}$ to contain the first $i$ of the $n$ transfers
from $p_{i}$ to $p_{i+1\bmod n}$ (for each $i=0,1,2,\ldots$). This is a valid
set of transactions, with the (Byzantine) player $p_{0}$ ending up with all
$n$ units of stake!

###  11.2. A General Impossibility Result

The payment circle example demonstrates that the following assumption does not
suffice to prevent Byzantine players from acquiring all the stake (even when
the environment never issues conflicting pairs of transactions): “the
execution of all transactions issued prior to a given timeslot always results
in Byzantine players controlling at most a $\rho$ fraction of the stake.” Any
pure proof-of-stake protocol would fail to satisfy liveness or consistency in
the payment circle example. Next, in Theorem 11.1, we prove a general
impossibility result, which shows that analogous examples plague every
protocol that uses an arbitrary collection of external resources and on-chain
resources that, like stake, are reactive in the sense defined in Section 8.3.

For simplicity, and to make our impossibility result as strong as possible, we
assume that the transactions issued by the (adversarial) environment are
restricted to “simple payments” from one identifier to another (like those in
the payment circle example). For example, we can work with the UTXO model of
Bitcoin. We can interpret the initial stake distribution $S_{0}$ as an initial
set of UTXOs (each associated with some identifier). A transaction then spends
one or more existing UTXOs (all associated with the same identifier) and
creates one or more new ones (each associated with an arbitrary identifier),
and two transactions conflict if and only if they spend a common UTXO. The sum
of the values of the UTXOs created by a transaction must be no larger than the
sum of the values of the UTXOs that it spends. A set $\mathtt{T}$ of
transactions is valid relative to $S_{0}$ if and only if it contains no
conflicting transactions and every transaction spends only UTXOs that are
either in $S_{0}$ or created by some other transaction of $\mathtt{T}$.

Maximal valid sets of transactions. For the statement of Theorem 11.1 below,
we cannot directly impose requirements on the stake distribution resulting
from “the set of transactions issued by the environment,” because that set may
not be valid relative to the initial stake distribution $S_{0}$. Instead, we
impose a requirement on every maximal valid subset of the transactions issued
by the environment up until some timeslot.

Formally, we say that $\mathtt{T}$ is a _maximal valid set of transactions at
$t$_ if:

  * (i)

$\mathtt{T}$ is valid relative to $S_{0}$;

  * (ii)

Every transaction in $\mathtt{T}$ is received by at least one honest player
from the environment at some timeslot $\leq t$, and;

  * (iii)

No proper superset of $\mathtt{T}$ satisfying (i) and (ii) is valid relative
to $S_{0}$.

Call an environment maximally $\rho$-bounded with respect to the initial stake
distribution $S_{0}$ if:

  * •

whenever the environment sends a transaction $\mathtt{tr}$ to some player at
timeslot $t$, it sends $\mathtt{tr}$ to some honest player at a timeslot $\leq
t$; and

  * •

for every $t$ and every $\mathtt{T}$ which is a maximal valid set of
transactions at $t$, $\mathtt{S}(S_{0},\mathtt{T})$ allocates Byzantine
players at most a $\rho$-fraction of the stake.

In particular, taking $t=0$ in the second condition, its conclusion must hold
for the initial distribution $S_{0}$.

###### Theorem 11.1.

Consider the quasi-permissionless, authenticated, and partially synchronous
setting. For every $\rho>0$ and $\epsilon<\tfrac{1}{5}$, there is no
blockchain protocol $(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$ that uses a
reactive set $\mathcal{S}$ of on-chain resources and satisfies consistency and
liveness with security parameter $\epsilon$ with respect to an externally
$\rho$-bounded adversary and a maximally $\rho$-bounded environment.

###### Proof.

See Section 16. ∎

As foreshadowed in Section 9.1, the proof of Theorem 11.1 must take advantage
of the restriction to reactive sets of on-chain resources. Theorem 11.1 does
not hold without the reactivity assumption: Otherwise, provided Byzantine
players control less than one-third of the initial stake, a protocol could
include the (fixed) initial stake distribution as a (non-reactive) on-chain
resource in $\mathcal{S}$ and, taking advantage of the player activity
assumptions of the general quasi-permissionless model (see Section 9.1), use
the players allocated non-zero initial stake to carry out a permissioned state
machine replication protocol such as PBFT (Liskov and Castro, 1999).

As Theorem 11.1 does not hold in the permissioned setting, its proof also
takes advantage of the limited non-permissioned features of the quasi-
permissionless setting: that a protocol does not have advance knowledge of the
player set, and that players without resources may be inactive.

###  11.3. A Sufficient Condition on the Environment

Defining $\rho$-bounded environments (for the UTXO model). To define
$\rho$-bounded environments, we again consider the UTXO model of Bitcoin.
There is then, for any transaction $\mathtt{tr}$, a smallest set $\mathtt{T}$
of transactions such that $\mathtt{T}\cup\\{\mathtt{tr}\\}$ is valid relative
to $S_{0}$; we say that $\mathtt{T}$ is the set of transactions required for
$\mathtt{tr}$ to be valid relative to $S_{0}$.

The trouble in the payment circle example stemmed from the multiple rounds of
transactions, with each round produced without waiting for confirmation of the
transactions in previous rounds. In response, we now assume that an honestly
produced transaction $\mathtt{tr}$ is issued only once all the transactions
required for $\mathtt{tr}$ to be valid are already confirmed. Because we do
not wish to limit the issuing of dishonestly produced transactions in any way,
we distinguish between Byzantine and honest transactions, according to the
type of player that controls the identifier associated with the transaction’s
inputs. Intuitively, we will assume that at any moment in time, the immediate
confirmation of all the pending honest transactions and no new Byzantine
transactions would result in the Byzantine players controlling at most a
$\rho$-fraction of the total stake. (The remaining concern, then, is that the
delayed confirmation of pending honest transactions or the immediate
confirmation of some Byzantine transactions might nevertheless cause Byzantine
players to be allocated more than a $\rho$-fraction of the total stake.)

Precisely, we say that the environment is $\rho$-bounded if
$\mathtt{S}(S_{0},\emptyset)$ allocates the adversary at most a
$\rho$-fraction of the total stake and if the following holds for all $p$ and
$t$. Suppose that:

  1. (i)

Player $p$ is honest and $\mathtt{T}_{1}$, which is the set of transactions
confirmed for $p$ at $t$, is valid relative to $S_{0}$;

  2. (ii)

$\mathtt{S}(S_{0},\mathtt{T}_{1})$ allocates the adversary at most a
$\rho$-fraction of the total stake;

  3. (iii)

$\mathtt{T}_{2}$ is the set of all honest transactions sent by the environment
at timeslots $\leq t$.

Then: $\mathtt{T}_{1}$ contains all transactions required for any transaction
in $\mathtt{T}_{2}$ to be valid relative to $S_{0}$;
$\mathtt{T}_{1}\cup\mathtt{T}_{2}$ is valid relative to $S_{0}$; and
$\mathtt{S}(S_{0},\mathtt{T}_{1}\cup\mathtt{T}_{2})$ allocates the adversary
at most a $\rho$-fraction of the total stake.474747We sometimes consider
protocols that require players to hold stake in escrow to participate. In this
case, it is convenient to consider a function $\hat{\mathtt{S}}$ (in addition
to $\mathtt{S}$) that determines how much stake players have held in escrow. A
weakly $\rho$-bounded environment then, by definition, satisfies the following
additional assumption: If $p$ is honest, if the set $\mathtt{T}$ of
transactions confirmed for $p$ at $t$ is valid relative to $S_{0}$, and if
$\mathtt{S}(S_{0},\mathtt{T})$ allocates the adversary at most a
$\rho$-fraction of the stake, then $\hat{\mathtt{S}}(S_{0},\mathtt{T})$ also
allocates the adversary at most a $\rho$-fraction of the stake in escrow.

Some terminology. We say that the adversary is weakly $\rho$-bounded if all
resource allocations are $\rho$-bounded and the environment is $\rho$-bounded.
A blockchain protocol is strongly $\rho$-resilient if it is live and
consistent for weakly $\rho$-bounded adversaries.

The following result is a strengthening of Theorem 9.1, in that our proof of
Theorem 11.2 will also prove Theorem 9.1. The protocol used in the proof, PoS-
HotStuff, is the same in both cases.

###### Theorem 11.2.

Consider the quasi-permissionless, authenticated, and partially synchronous
setting. For every $\rho<1/3$, there exists a deterministic and strongly
$\rho$-resilient PoS blockchain protocol. Moreover, the protocol can be made
$(1/3,1)$-accountable and optimistically responsive.

###### Proof.

See Section 15. ∎

To get a feel for the role that the $\rho$-bounded environment plays in the
proof of Theorem 11.2, suppose that (i)–(iii) above hold for sets
$\mathtt{T}_{1}$ and $\mathtt{T}_{2}$ of transactions. We claim that, for any
$\mathtt{T}_{3}\subseteq\mathtt{T}_{2}$ and any set of Byzantine transactions
$\mathtt{T}_{4}$ such that
$\mathtt{T}_{5}:=\mathtt{T}_{1}\cup\mathtt{T}_{3}\cup\mathtt{T}_{4}$ is valid
relative to $S_{0}$, $\mathtt{S}(S_{0},\mathtt{T}_{5})$ allocates the
adversary at most a $\rho$-fraction of the stake. This claim holds because
$\mathtt{T}_{1}$ already contains all transactions required for transactions
in $\mathtt{T}_{2}$ to be valid—ruling out examples such as the payment circle
and ensuring that $\mathtt{S}(S_{0},\mathtt{T}_{1}\cup\mathtt{T}_{3})$
allocates the adversary at most a $\rho$-fraction of the total stake—and
because transactions in $\mathtt{T}_{4}$ can only transfer stake from
identifiers controlled by Byzantine players. The significance of this
observation in the proof of Theorem 11.2 is that, when a new block of
transactions is confirmed by the protocol, no choice of included transactions
in that block can result in Byzantine players being allocated more than a
$\rho$-fraction of the total stake.

##  12\. Proof of Theorem 6.1

###  12.1. The approach

The rough idea is to adapt the bivalency proof by Aguilera and Toueg (Aguilera
and Toueg, 1999) of the result by Dolev and Strong (Dolev and Strong, 1983)
that $f$-resilient consensus requires $f+1$ timeslots in the permissioned
setting. We use this approach to produce a proof by contradiction: We assume a
deterministic protocol solving BA in the fully permissionless setting and then
show that there must be executions in which honest players never output.
Taking this route, rather than adapting the original proof of Dolev and Strong
(Dolev and Strong, 1983), leads to a proof that is somewhat simpler than the
one given in the conference version of this paper (Lewis-Pye and Roughgarden,
2021). Still, the argument must accommodate several new features of our
framework, including message dissemination (as opposed to point-to-point
communication), failures other than crash failures, and the presence of
general oracles.

###  12.2. Some conventions

For convenience, we assume that an active honest player disseminates exactly
one message per timeslot. Because we impose no bounds on message length, an
honest player never needs to send more than one message in a timeslot. Forcing
honest players to send at least one message per timeslot (as opposed to
sometimes remaining silent) is also easily seen to be without loss of
generality; see Aguilera and Toueg (Aguilera and Toueg, 1999) for details.

We can assume that a protocol uses one or more permitter oracles; otherwise,
there are no constraints in the fully permissionless setting that prevent the
adversary from deeming all honest players inactive at all timeslots. (Recall
from Section 4.1 that the assumptions there on external resources guarantee at
least one honest active player at every timeslot.) Because the fully
permissionless setting imposes no constraints on the activity periods of
players with a non-zero amount of stake, however, we are forced to confront
the case in which none of the players included in the initial stake
distribution are ever active.

Finally, we can assume an initial stake distribution that allocates 0 stake to
the Byzantine players (making the impossibility result as strong as possible).
We need to consider only the “null” environment that never sends any
transactions.

###  12.3. The setup

Fix $\rho>0$. Towards a contradiction, suppose that the $\rho$-resilient and
deterministic protocol $(\Sigma,\mathcal{O},\mathcal{C})$ solves BA in the
fully permissionless and authenticated setting with synchronous communication.

We consider an infinite set of players $\mathcal{P}$, but, as per the
assumptions described in Section 3, we suppose a finite number of players are
active at each timeslot. The infinite set of players is used only to ensure
that there are always new players that can join at any timeslot, i.e., that
the set of players is not ultimately fixed.

The rough idea. The idea is to restrict attention to executions in which a
fresh set of players become active at each timeslot $t$, and contribute
briefly to the protocol before becoming inactive again. So long as the number
of fresh players becoming active at $t$ is large, and so long as all resources
are allocated evenly between them and at most one of those players is
Byzantine, all resource allocations will be $\rho$-bounded. The only
deviations by Byzantine players that are relevant for our argument are to
crash or delay the dissemination of a message.

The details. Choose $s\geq\text{max}\\{1/\rho,3\\}$ and partition
$\mathcal{P}$ into $s$ infinite and disjoint sets $P_{1},\dots,P_{s}$. We will
be able to derive a contradiction even after restricting attention to
executions that satisfy the conditions $(\Pi_{0})-(\Pi_{10})$ below.

First, some conditions restricting the inputs:

  * ($\Pi_{0}$)

All players in a given $P_{k}$ receive the same protocol input, either 0 or 1.

  * ($\Pi_{1}$)

All players receive parameter inputs $d=\infty$ and $\Delta=2$, as well as
their personal value $\mathtt{id}(p)$.

Next, we specify that $s$ new players become active at each timeslot:

  * ($\Pi_{2}$)

Each player $p$ is active at timeslots in an interval $[en_{p},ex_{p}]$. It
may be that $en_{p}=ex_{p}=\infty$.

  * ($\Pi_{3}$)

For each $t$, there exists precisely one player $p$ in each $P_{k}$ with
$en_{p}=t$. Let $P^{\ast}_{t}$ denote the set of all players $p$ such that
$en_{p}=t$; thus, $|P^{\ast}_{t}|=s$ for each $t$.

  * ($\Pi_{4}$)

We consider a single fixed sequence $(P^{\ast}_{t})_{t\geq 1}$, which defines
the specific choice of players (from the $P_{i}$’s) that belong to each set
$P^{*}_{t}$. This sequence is the same in all executions considered.

The next conditions specify the various values $ex_{p}$, when disseminations
may be received, and the possible behaviors of Byzantine players:

  * ($\Pi_{5}$)

If $p$ is honest, then $ex_{p}=en_{p}$.

  * ($\Pi_{6}$)

If $p\in P^{*}_{t}$ is honest and disseminates $m$ at $t$, then all players
active at $t+1$ receive that dissemination at $t+1$.

  * ($\Pi_{7}$)

Byzantine players can display only two forms of non-honest behavior:

    1. (1)

If $p\in P^{\ast}_{t}$ is Byzantine, it may crash immediately before
disseminating a message at $t$ (but after receiving messages delivered at $t$,
sending oracle queries, and receiving the oracle responses delivered at
$t$).484848Formally, a player that has “crashed” never again disseminates any
messages or issues any oracle queries. In this case, $ex_{p}=t$.

    2. (2)

If $p\in P^{\ast}_{t}$ is Byzantine, then it may not crash but may fail to
disseminate the instructed message $m$ at $t$. We let $ex_{p}$ be the first
timeslot at which $p$ disseminates $m$ (meaning $ex_{p}=\infty$ is possible
and that $ex_{p}=t$ if $p$ disseminates $m$ at $t$), and stipulate that $p$
performs no actions at stages $>t$ other than (possibly) disseminating $m$ at
some first timeslot. If $ex_{p}>t$, then we say that $p$ suffers dissemination
failure at each $t^{\prime}\in[t,ex_{p}]$.

  * ($\Pi_{8}$)

We say $p$ _suffers delays at_ $t$ if either:

    * –

$p$ crashes at $t$;

    * –

$p$ suffers dissemination failure at $t$, or;

    * –

$p$ disseminates a message $m$ at $t$ which is not received by some active
player at $t+1$.

We stipulate that at most one (Byzantine) player can suffer delays at each
timeslot.

Finally, we stipulate conditions that ensure resource allocations are
$\rho$-bounded:

  * ($\Pi_{9}$)

At most one player in each $P^{\ast}_{t}$ is Byzantine.

  * ($\Pi_{10}$)

For each permitter oracle $O\in\mathcal{O}$, the corresponding resource
allocation $\mathcal{R}^{O}$ satisfies the following for every $p$ and $t$:
$\mathcal{R}^{O}(p,t)=1$ if $p\in P^{\ast}_{t}$ and $\mathcal{R}^{O}(p,t)=0$
otherwise. (Thus, no matter how many timeslots a player might be active, it
possesses a non-zero amount of resource in at most one timeslot.) Together
with the conditions above, this condition ensures that all resource
allocations are $\rho$-bounded.

Let $\Pi$ denote the set of all executions of the protocol satisfying these
conditions.

###  12.4. Bivalent $t$-runs and indistinguishable executions

Bivalent $t$-runs. Roughly, by a “$t$-run” we mean a specification of the
first $t$ timeslots of an execution (as defined in Section 3.2). More
precisely:

By a $0$-run, we mean a specification of the inputs for each player.

For $t\geq 1$, by a $t$-run, we mean a specification of:

  1. (i)

The inputs given to each player.

  2. (ii)

The messages disseminated by each player at each timeslot $\leq t$.

  3. (iii)

The sequence of queries sent and responses received by each player at each
timeslot $\leq t$.

  4. (iv)

The players that crash at each timeslot $\leq t$.

  5. (v)

The set of disseminations received by each player at each timeslot $\leq t+1$.

For $t^{\prime}>t$, we say that the $t^{\prime}$-run $x^{\prime}$ _extends_
the $t$-run $x$ if: (a) Players receive the same inputs in both runs; (b)
Players disseminate the same messages at all timeslots $\leq t$ in both runs;
(c) Players send and receive the same sequence of oracle queries and responses
at timeslots $\leq t$ in both runs; (d) The same players crash at all
timeslots $\leq t$ in both runs, and; (e) Players receive the same
disseminations at all timeslots $\leq t+1$ in both runs. Extending this
definition in the obvious way, we can also speak about an execution extending
a $t$-run.

For $i\in\\{0,1\\}$, we say a $t$-run $x$ is $i$-valent if, for every
execution extending $x$, there exists $t^{\ast}$ such that all honest players
output $i$ if they are active at any timeslot $\geq t^{\ast}$. We say $x$ is
univalent if it is $i$-valent for some $i\in\\{0,1\\}$. We say $x$ is bivalent
if it is not univalent.

For each $t$, we let $X_{t}$ denote the set of all $t$-runs extended by some
execution in $\Pi$.

Indistinguishable executions. In the deterministic model, we say that two
executions $\mathtt{E}_{0}$ and $\mathtt{E}_{1}$ are _indistinguishable_ for
honest $p$ if:

  * •

Player $p$ has the same inputs in $\mathtt{E}_{0}$ and $\mathtt{E}_{1}$, and;

  * •

At each timeslot $t$, player $p$ receives the same multiset of messages and
the same sequence of oracle responses in $\mathtt{E}_{0}$ as it does in
$\mathtt{E}_{1}$.

By induction on timeslots, the behavior (and eventual output) of a player must
be identical in any two executions that are indistinguishable for it.

###  12.5. Defining an execution in which honest players never output

There exists a bivalent $0$-run in $X_{0}$. The proof of this fact is
essentially the same as the proof of the corresponding lemma in the proof by
Aguilera and Toueg (Aguilera and Toueg, 1999) (which, in turn, is the same as
in the proof of the FLP Theorem (Fischer et al., 1985)). Towards a
contradiction, suppose all $0$-runs in $X_{0}$ are univalent. For each $k$
with $0\leq k\leq s$, let $x_{k}$ be the $0$-run in which players in each
$P_{i}$ for $1\leq i\leq k$ all get input 1, while all other players get input
0. Because $x_{0}$ is 0-valent and $x_{s}$ is 1-valent (by Validity and
Termination), there must exist a smallest $k$ for which $x_{k}$ is 0-valent,
while $x_{k+1}$ is 1-valent.

For each $i\in\\{0,1\\}$, let $\mathtt{E}_{i}$ be the (unique) execution in
$\Pi$ that extends $x_{k+i}$ and such that all players are honest except the
players in $P_{k+1}$, who all crash before sending messages if they ever
become active. There exist such executions $\mathtt{E}_{0}$ and
$\mathtt{E}_{1}$ in $\Pi$ because, if only the players in $P_{k+1}$ are
Byzantine, then at most one player in each $P^{\ast}_{t}$ is Byzantine.

Because $x_{k}$ is 0-valent, all honest players that output must output 0 in
$\mathtt{E}_{0}$. Because $x_{k+1}$ is 1-valent, all honest players that
output must output 1 in $\mathtt{E}_{1}$. This contradicts the fact that
$\mathtt{E}_{0}$ and $\mathtt{E}_{1}$ are indistinguishable for players
outside $P_{k+1}$. This last statement holds because the protocol inputs for
players in $P_{k+1}$ are undetermined for the oracles and for players outside
$P_{k+1}$, and because oracles are non-adaptive (see Section 3.2).494949The
players of $P_{k+1}$ may send different oracle queries in $\mathtt{E}_{0}$ and
$\mathtt{E}_{1}$ immediately before crashing, but because these players send
no messages after these oracle queries, the executions remain
indistinguishable to all other players.

Extending the bivalent run. Suppose $x\in X_{t}$ is bivalent. We show that
there exists $x^{\prime}\in X_{t+1}$ such that $x^{\prime}$ extends $x$ and is
bivalent. Combined with the existence of a bivalent 0-run in $X_{0}$, this
suffices to establish the existence of an execution in which honest players
never output.

Towards a contradiction, suppose all extensions of $x$ in $X_{t+1}$ are
univalent. Let $x^{\ast}$ be the (unique) extension of $x$ in $X_{t+1}$ in
which all players in $P^{*}_{t+1}$ are honest, and in which any Byzantine
player still active at $t+1$ disseminates a message which is received by all
active players at the next timeslot. (Such a player must be suffering delays
at $t+1$, so there is at most one such player.)

We’re done if $x^{*}$ is bivalent so assume, without loss of generality, that
$x^{\ast}$ is 1-valent. Because $x$ is bivalent, there must exist
$x^{\dagger}\in X_{t+1}$ which is an extension of $x$ and which is not
1-valent. We’re done if $x^{\dagger}$ is bivalent, so assume that it is
0-valent. From the definition of $\Pi$, it follows that there exists a single
player $p$ that is Byzantine, and which suffers delays at $t+1$ in
$x^{\dagger}$. There are now two possibilities to consider, depending on
whether these delays are caused by the communication network or by the player
itself.

Case 1: In $x^{\dagger}$, player $p$ does disseminate $m$ at $t+1$, but there
exists some non-empty subset $\\{p_{1},\dots,p_{r}\\}$ of the players in
$P^{\ast}_{t+2}$ who do not receive the dissemination at $t+2$. In this case,
define $x_{0}:=x^{\dagger}$, $x_{r}:=x^{\ast}$, and, for each $k\in[1,r)$,
define $x_{k}$ to be the $t+1$-run that is identical to $x^{\dagger}$ except
that players $p_{1},\dots,p_{k}$ receive $m$ at $t+2$. Assume that every such
$x_{k}$ is univalent (otherwise, we are done).

Because $x_{0}$ is 0-valent and $x_{r}$ is 1-valent, there must exist a least
$k$ such that $x_{k}$ is 0-valent and $x_{k+1}$ is 1-valent. For
$i\in\\{0,1\\}$, let $\mathtt{E}_{i}$ be the execution extending $x_{k+i}$ in
which players in $P^{\ast}_{t^{\prime}}$ are honest for all $t^{\prime}\geq
t+2$ save $p_{k+1}$, who crashes immediately before sending messages at
timeslot $t+2$. Because $x_{k}$ is 0-valent, all honest players that output
must output 0 in $\mathtt{E}_{0}$. Because $x_{k+1}$ is 1-valent, all honest
players that output must output 1 in $\mathtt{E}_{1}$. This contradicts the
fact that $\mathtt{E}_{0}$ and $\mathtt{E}_{1}$ are indistinguishable for
honest players.

Case 2: In $x^{\dagger}$, player $p$ does not disseminate $m$ at $t+1$, either
because it crashes at this timeslot or because it delays message
dissemination. We can assume the latter scenario. For if $p$ crashes at $t+1$,
consider instead the $t+1$-run $x^{\diamond}$ which is identical to
$x^{\dagger}$ except that $p$ does not crash and does not disseminate a
message at $t+1$. If $x^{\diamond}$ is bivalent, we are done. It cannot be
1-valent, as there is an execution extending it (with $p$ never disseminating
and with all other players active at timeslots $>t+1$ being honest) that is
indistinguishable for all honest players from one extending $x^{\dagger}$
(which is 0-valent). Thus $x^{\diamond}$, like $x^{\dagger}$, is a 0-valent
extension of $x$ in $X_{t+1}$, and it can substitute for $x^{\dagger}$ in the
rest of the argument.

Assuming now that $p$ delays the dissemination of $m$ in $x^{\dagger}$, let
$y_{0}$ be the $t+2$-run in $X_{t+2}$ that extends $x^{\dagger}$ and such that
all players in $P^{\ast}_{t+2}$ are honest, player $p$ disseminates $m$ at
$t+2$, and $m$ is received by all active players at the next
timeslot.505050The $t+2$-run $y_{0}\in X_{t+2}$ is well defined, as in the
$t+1$-run $x^{\dagger}$, $p$ receives all the messages and oracle responses
needed to disseminate the message $m$ at $t+1$ (which, in $y_{0}$, $p$ does at
$t+2$). Because $y_{0}$ extends $x^{\dagger}$, it is 0-valent. Let $x_{0}$ be
the $t+2$-run in $X_{t+2}$ that is identical to $y_{0}$, except that $p$
disseminates $m$ at $t+1$, while it remains the case that no players in
$P^{\ast}_{t+2}$ receive that dissemination at $t+2$. Then $x_{0}$ must also
be 0-valent, because for each execution extending either of $y_{0}$ or
$x_{0}$, there is an execution extending the other that is indistinguishable
from the first execution for all honest players. (Intuitively, honest players
cannot know whether $m$ was disseminated at $t+1$ and took two timeslots to be
delivered, or was disseminated at $t+2$ and took a single timeslot to be
delivered.)

Let $p_{1},\dots,p_{s}$ be an enumeration of the players in $P^{\ast}_{t+2}$.
For each $k\in[1,s]$, let $x_{k}$ be the $t+2$-run that is identical to
$x_{0}$, except that all players $p_{i}$ for $1\leq i\leq k$ receive $m$ at
$t+2$. Because $x_{s}$ extends $x^{\ast}$, it must be 1-valent. The rest of
the argument is identical to that in Case 1, with $x_{s}$ playing the previous
role of $x_{r}$ and the player set $\\{p_{1},\ldots,p_{s}\\}$ playing the
previous role of $\\{p_{1},\ldots,p_{r}\\}$.

###  12.6. Discussion

The proof of Theorem 6.1 is driven by two properties of the fully
permissionless setting: (i) there is no bound on the number of players; (ii)
the set of players that are active can change arbitrarily at each timeslot
(subject to the constraint that the adversary be $\rho$-bounded). Theorem 6.1
is trivially false if all players are always active, as otherwise the players
allocated non-zero stake by the initial stake distribution could carry out a
standard permissioned Byzantine Agreement protocol. We leave as an open
question whether Theorem 6.1 continues to hold when there is a determined and
finite upper bound on the number of players (but an arbitrary and undetermined
player allocation). We also leave open whether Theorem 6.1 holds for protocols
that use only external resources (i.e, that have no initial stake
distribution) in the setting in which all players are always active.

The proof of Theorem 6.1 does not require sybils, in the sense that it holds
even when $|\mathtt{id}(p)|=1$ for all $p$. The positive result of
Khanchandani and Wattenhofer (Khanchandani and Wattenhofer, 2021) shows that
Theorem 6.1 no longer holds when the player set is finite, identifiers are
(undetermined but) unique (i.e., $|\mathtt{id}(p)|=1$ for all $p$), and all
players are always active. This positive result does not require an initial
stake distribution.

Theorem 6.1 trivially fails to hold if $\rho=0$. To see this, consider the
following protocol that makes use of a single permitter $O$. Active players
are instructed to send a single query $(b,i)$ to the permitter at timeslot 1,
where $b$ is their external resource balance at that time and $i$ is their
protocol input. The permitter ignores queries with $b=0$—which, because
$\rho=0$, includes any queries issued by faulty players—and “certifies” a
query $(b,i)$ with $b>0$ by responding with a type-$O$ message with a single
entry $i$. Players are instructed to immediately disseminate the permitter’s
responses. Players can then, at the first timeslot $\geq 1+\Delta$ at which
they are active, safely output $i$ if all received type-$O$ messages consist
of the entry $i$, and a default value otherwise.

##  13\. Proof of Theorem 7.2

###  13.1. The intuition

Towards a contradiction, fix a 0-resilient protocol that solves probabilistic
BA in the dynamically available and partially synchronous setting with
security parameter $\epsilon<\tfrac{1}{3}$. Recall the definition of a
protocol instance from Section 6.2. We consider protocol instances with
$d=\infty$ and a finite set of players, all of whom are honest. Partition a
set $\mathcal{P}$ of players into two non-empty sets $P_{0}$ and $P_{1}$;
suppose players of $P_{i}$ receive the protocol input $i$ (for
$i\in\\{0,1\\}$). We suppose further that $\mathcal{R}^{O}(p,t)>0$ for every
$p,t$ and for each permitter $O$.

We then consider a network partition during which messages disseminated by
players in each $P_{i}$ are received by other players in $P_{i}$ but not by
players in $P_{1-i}$. If the network partition is sufficiently long then, with
significant probability, all players will eventually terminate before the
partition ends. Because the protocol is assumed to solve probabilistic BA in
the dynamically available setting, the Validity condition forces players in
$P_{0}$ to, with significant probability, terminate and output 0. The reason
is that, from their viewpoint, the protocol execution is indistinguishable
from a synchronous protocol execution in which the active player set is
$P_{0}$. Invoking the Validity condition again, players in $P_{1}$ must, with
significant probability, terminate and output 1; from their viewpoint, the
protocol execution is indistinguishable from a synchronous protocol execution
in which the active player set is $P_{1}$. This leads to a violation of the
Agreement condition.

###  13.2. The details

Let $\mathcal{P}=P_{0}\cup P_{1}$, where each $P_{i}$ is non-empty and where
$P_{0}\cap P_{1}=\emptyset$. We consider three different instances of the
protocol, $\mathtt{I}_{0}$, $\mathtt{I}_{1}$, and $\mathtt{I}_{2}$. In all
three instances, the player set is $\mathcal{P}$.

The inputs and the player allocations. In all three instances, each player
will either be active at every timeslot or inactive at every time slot. In
$\mathtt{I}_{0}$, $\mathtt{I}_{1}$, and $\mathtt{I}_{2}$, the active players
are $\mathcal{P}$, $P_{0}$, and $P_{1}$, respectively. In all three instances,
every player is honest and has a unique identifier, and all players are given
the determined parameter inputs $d=\infty$ and $\Delta$ (say, $\Delta=2$). In
$\mathtt{I}_{0}$, players in $P_{i}$ are given input $i$. In $\mathtt{I}_{1}$,
all players are given input 0. In $\mathtt{I}_{2}$, all players are given
input 1. In all three instances:

  * •

Every resource allocation $\mathcal{R}^{O}$ satisfies the condition that
$\mathcal{R}^{O}(p,t)=1$ for all $p$ active at $t$.

  * •

We consider an initial stake distribution $S_{0}$ which allocates all players
in $\mathcal{P}$ resource balance 1 (whether or not the player is active) and
an environment that does not issue any transactions.

The timing rules. The timing rules in the three instances are as follows:

  * •

In $\mathtt{I}_{0}$, a dissemination at $t$ by any player in $P_{i}$ is
received by other players in $P_{i}$ at $t+1$ and is received by players in
$P_{1-i}$ at timeslot $t^{\prime}=\text{max}\\{t+1,\text{GST}\\}$.

  * •

In $\mathtt{I}_{1+i}$, a dissemination at $t$ by any player in $P_{i}$ is
received by other players in $P_{i}$ at $t+1$.

Producing a probable violation of Agreement. It follows by induction on
timeslots $<$GST that:

  1. $(\dagger)$

For each $i\in\\{0,1\\}$ and all $t<$GST, $\mathtt{I}_{0}$ and
$\mathtt{I}_{1+i}$ are indistinguishable for players in $P_{i}$ until $t$.

Because the given protocol is assumed to solve BA (and, in particular, satisfy
Validity) with probability at least $1-\epsilon$ in the dynamically available
setting with a 0-bounded adversary, there is a timeslot $t^{\ast}$ by which:
(i) in $\texttt{I}_{1}$, with probability at least $1-\epsilon$, all players
of $P_{0}$ terminate and output 0; (ii) in $\texttt{I}_{2}$, with probability
at least $1-\epsilon$, all players of $P_{1}$ terminate and output 1.

Using $(\dagger)$, in instance $\mathtt{I}_{0}$, if GST is chosen to be
sufficiently large (greater than $t^{\ast}$), then with probability at least
$1-2\epsilon$, by timeslot $t^{*}$ all players of $P_{i}$ have terminated with
output $i$ (for $i\in\\{0,1\\}$). Because $\epsilon<\tfrac{1}{3}$, this
likelihood of a disagreement contradicts the initial assumption that the
protocol satisfies Agreement with security parameter $\epsilon$ in the
partially synchronous setting.

Discussion. The proof of Theorem 7.2 is driven solely by the possibility of
inactive players; this assumption is necessary, as otherwise the set of
players allocated non-zero stake by the initial stake distribution could carry
out a standard permissioned Byzantine Agreement protocol. The player set
$\mathcal{P}$ used in the proof can be known and finite, with each player in
possession of only a single identifier.

##  14\. Proof of Theorem 7.4

The proof resembles that of Theorem 7.2. Towards a contradiction, fix a
0-resilient blockchain protocol that is optimistically responsive in the
dynamically available, authenticated, and synchronous setting, with security
parameter $\epsilon<\tfrac{1}{3}$. Suppose the protocol satisfies the
definition of optimistic responsiveness with liveness parameter
$\ell=O(\delta)$ and grace period parameter $\Delta^{*}=O(\Delta)$, where
$\delta$ denotes the (undetermined) realized maximum message delay. Let $K$ be
a constant such that $\ell<K\delta$ for all $\delta\geq 1$, and choose
$\Delta>K$ (thereby fixing $\Delta^{*}$).

The player set. Let $\mathcal{P}=P_{0}\cup P_{1}$, where the $P_{i}$’s are
non-empty and disjoint sets. We consider three instances of the protocol,
$\mathtt{I}_{0}$, $\mathtt{I}_{1}$, and $\mathtt{I}_{2}$. In all three
instances, the player set is $\mathcal{P}$.

The inputs and the player allocations. In all three instances, each player
will either be active in all timeslots or active for all and only the
timeslots $\leq\Delta^{*}$. The players active at timeslots $>\Delta^{*}$ are
$P_{0}$ in $\mathtt{I}_{0}$, $P_{1}$ in $\mathtt{I}_{1}$, and $\mathcal{P}$ in
$\mathtt{I}_{2}$. In all three instances, every player is honest and has a
unique identifier, and all players are given the determined parameter inputs
$\Delta$ and $d=\Delta^{*}+2\Delta$. In all three instances:

  * •

Every resource allocation $\mathcal{R}^{O}$ satisfies the condition that
$\mathcal{R}^{O}(p,t)=1$ for all $p$ active at $t$.

  * •

We consider an initial stake distribution $S_{0}$ which allocates all players
in $\mathcal{P}$ resource balance 1 (whether or not the player is active).

Let $\mathtt{tr}_{0}$ and $\mathtt{tr}_{1}$ denote two transactions that are
conflicting relative to $S_{0}$. In $\mathtt{I}_{0}$, the environment sends
$\mathtt{tr}_{0}$ to all players in $P_{0}$ at timeslot $\Delta^{*}+1$. In
$\mathtt{I}_{1}$, the environment sends $\mathtt{tr}_{1}$ to all players in
$P_{1}$ at timeslot $\Delta^{*}+1$. In $\mathtt{I}_{2}$, the environment sends
$\mathtt{tr}_{0}$ to all players in $P_{0}$ at timeslot $\Delta^{*}+1$ and
sends $\mathtt{tr}_{1}$ to all players in $P_{1}$ at timeslot $\Delta^{*}+1$.

The timing rules. The timing rules in the three instances are as follows:

  * •

In all three instances, a dissemination by any player at a timeslot
$\leq\Delta^{*}$ is received by all other players at the next timeslot.

  * •

In $\mathtt{I}_{0}$, a dissemination at timeslot $t>\Delta^{*}$ by a player in
$P_{0}$ is received by the other players in $P_{0}$ at $t+1$. (By this point,
only the players of $P_{0}$ are active in this instance.)

  * •

In $\mathtt{I}_{1}$, a dissemination at timeslot $t>\Delta^{*}$ by a player in
$P_{1}$ is received by the other players in $P_{1}$ at $t+1$. (By this point,
only the players of $P_{1}$ are active in this instance.)

  * •

In $\mathtt{I}_{2}$, a dissemination at timeslot $t>\Delta^{*}$ by any player
in $P_{0}$ is received by other players in $P_{0}$ at $t+1$ and is received by
players in $P_{1}$ at timeslot $t+\Delta$. A dissemination at timeslot
$t>\Delta^{*}$ by any player in $P_{1}$ is received by other players in
$P_{1}$ at $t+1$ and is received by players in $P_{0}$ at timeslot $t+\Delta$.

Producing a probable consistency violation. It follows by induction on
timeslots $\leq\Delta^{*}+\Delta$ that:

  1. $(\dagger)$

For each $i\in\\{0,1\\}$ and all $t\leq\Delta^{*}+\Delta$, $\mathtt{I}_{i}$
and $\mathtt{I}_{2}$ are indistinguishable for players in $P_{i}$ until the
end of timeslot $t$.

Because $\delta=1$ in the instances $\texttt{I}_{0}$ and $\texttt{I}_{1}$ and
$\Delta>K$, the definition of optimistic responsiveness implies that: (i) in
$\texttt{I}_{0}$, with probability at least $1-\epsilon$, $\mathtt{tr}_{0}$
will be confirmed for all players in $P_{0}$ by timeslot $\Delta^{*}+\Delta$;
(ii) in $\texttt{I}_{1}$, with probability at least $1-\epsilon$,
$\mathtt{tr}_{1}$ will be confirmed for all players in $P_{1}$ by timeslot
$\Delta^{*}+\Delta$.

From $(\dagger)$, it follows that, with probability at least $1-2\epsilon$ in
$\mathtt{I}_{2}$, $\mathtt{tr}_{0}$ will be confirmed for all players in
$P_{0}$ and $\mathtt{tr}_{1}$ will be confirmed for all players in $P_{1}$ by
timeslot $\Delta^{*}+\Delta$. Because $\mathtt{tr}_{0}$ and $\mathtt{tr}_{1}$
are conflicting transactions and $\epsilon<\tfrac{1}{3}$, this provides the
required contradiction.

Discussion. The proof of Theorem 7.4, like that of Theorem 7.2, is driven
solely by the possibility of inactive players; this assumption is necessary,
as otherwise the set of players allocated non-zero stake by the initial
distribution could carry out a standard permissioned protocol. The player set
$\mathcal{P}$ used in the proof can be known and finite, with each player
using a unique and known identifier.

##  15\. Proofs of Theorems 9.1 and 11.2

We present a proof of Theorem 11.2, as this is the stronger result. Readers
interested only in Theorem 9.1 can omit all aspects of the proof that are
concerned with ensuring that, if $p$ is honest and $\mathtt{T}$ is the set of
transactions confirmed for $p$ at $t$, then $\mathtt{S}(S_{0},\mathtt{T})$
allocates the adversary at most a $\rho$ fraction of the stake (as this
condition is automatically guaranteed by the hypotheses of Theorem 9.1).

###  15.1. Preliminaries

We prove Theorem 11.2 by modifying the (permissioned) HotStuff protocol (Yin
et al., 2019) to work as a PoS protocol. While HotStuff is designed to achieve
optimistic responsiveness and simultaneously minimize message complexity, our
concerns here are different: For the sake of simplicity, we ignore issues of
efficiency and strive for the simplest protocol with the required properties.
Section 15.7 describes some ways to improve the efficiency of our protocol.

Removing the ‘baked in’ knowledge of time. The definition of a state diagram
in Section 3.2 allows a player’s state transition at a given timeslot to
depend on the number of that timeslot. This modeling choice serves to make our
impossibility results as strong as possible. For the present proof, however,
such knowledge arguably goes against the spirit of the setting. We therefore
weaken the model so that a player’s state transition at a given timeslot can
depend only on the player’s current state and the oracle responses and
messages received by that time.

Allowing clock drift. Section 3.1 defined a version of the partial synchrony
model in which message delivery may take an arbitrary amount of time prior to
GST, but in which players have “internal clocks” of identical speed. That is,
active players proceed in lockstep, carrying out one round of instructions
according to their state diagram at each timeslot. This definition is more
generous to a protocol than other versions of the partial synchrony model
(e.g., (Dwork et al., 1988)). This modeling choice only strengthens our
impossibility results in the partially synchronous setting, Theorems 7.2 and
11.1. To make our positive result here as strong as possible, however, we
extend the model to allow for bounded clock drift.

Formally, the player allocation (see Section 3.1) will now specify, for each
player and timeslot at which that player is active, whether the player is
_waiting_ or _not waiting_ at that timeslot. (Intuitively, the slower a
player’s clock, the more frequently they will be waiting.) If honest $p$ is
active and not waiting at timeslot $t$, it carries out the protocol
instructions as specified in Section 3.2. If $p$ is active but waiting at $t$,
it acts as if inactive at $t$ (and does not receive any messages or oracle
responses at that timeslot). We assume that there is some known bound
$\kappa\in(0,1]$ such that, for each $t,\ell\in\mathbb{N}_{\geq 1}$ and each
honest player $p$ active in the interval $(t,t+\ell]$, there are at least
$\lfloor\kappa\cdot\ell\rfloor$ many timeslots in that interval at which $p$
is active and not waiting (with $p$ active but waiting at the other timeslots
in $(t,t+\ell]$). Intuitively, the closer $\kappa$ is to 1, the smaller the
difference in the rates at which the internal clocks of honest players
advance.

In the version of the partial synchrony model considered in this section, we
assume that if $p$ disseminates $m$ at $t$, and if $p^{\prime}\neq p$ is
active and not waiting at $t^{\prime}\geq\text{max}\\{\text{GST},t+\Delta\\}$,
then $p^{\prime}$ receives that dissemination at a timeslot $\leq t^{\prime}$.

###  15.2. Recalling (permissioned) HotStuff

To segue into the description of our PoS-HotStuff protocol in Sections
15.3–15.4, we first provide a rough description of a simplified specification
of the (permissioned) HotStuff protocol that makes no effort to minimize
communication complexity. Accordingly, in this subsection, we consider a set
of $n$ players, of which at most $f$ may be Byzantine, with $n\geq 3f+1$.

Views in HotStuff. The protocol instructions are divided into _views_. Within
each view, there are three stages of voting, each of which is an opportunity
for players to vote on a _block_ of transactions proposed by the _leader_ of
that view. (All these notions will subsequently be formalized.) Each block of
transactions $B$ is associated with a specific view, denoted $v^{\ast}(B)$. If
the first stage of voting in a view establishes a _stage 1 quorum certificate_
(QC) for a block $B$ proposed in that view (in the form of $2f+1$ votes for
$B$, signed by distinct players), then the second stage of the view may
establish a _stage 2_ QC for $B$, whereupon the third stage of the view may
establish a _stage 3_ QC for $B$. If $Q$ is a QC for $B$, then we define
$v^{*}(Q):=v^{*}(B)$ and $B^{*}(Q):=B$. Deviating somewhat from the exposition
in (Yin et al., 2019), each honest player maintains two local variables
$Q^{1}$ and $Q^{2}$ (persistent across views) that implement a “locking”
mechanism; for $i=1,2$, $Q^{i}$ records the stage $i$ QC that triggered the
player’s most recent stage $i+1$ vote.

The instructions within a view are deterministic. If the leaders of views are
also chosen deterministically—for example, with player $p_{i}$ the leader of
view $v$ whenever $i=v\text{ mod }n$—the entire protocol is deterministic.

View changes. Given that we ignore communication complexity, moving from one
view to the next is straightforward in the permissioned setting. When an
honest player $p$ enters a view $v$, it sets a timer. When the timer expires,
or if $p$ sees a stage 3 QC for a block proposed by the leader of view $v$,
$p$ disseminates a (signed) $\mathtt{view}\ v+1$ message $(v+1,Q^{1})$. A
_view certificate_ (VC) for view $v+1$ is a set of $2f+1$ $\mathtt{view}\ v+1$
messages, signed by distinct players. Player $p$ enters view $v+1$ upon
receiving a VC for view $v+1$, if presently in a lower view.

Block proposals in HotStuff. When an honest player enters a view $v$ for which
it is the leader, it chooses, among all QCs received to-date as part of a
$\mathtt{view}$ $v$ message, the most recent such QC $Q$ (i.e., with
$v^{*}(Q)$ as large as possible). The leader then disseminates a block
proposal $(B,Q)$ in which $B$ lists $B^{*}(Q)$ as its parent block. An honest
player $p$ that receives such a block proposal while in view $v$ will regard
it as _valid_ if and only if: (i) $Q$ is a QC for a block $B^{*}(Q)$ that is
the parent of $B$; and (ii) $v^{*}(Q^{2})\leq v^{*}(Q)$, where $Q^{2}$ denotes
the current value of $p$’s corresponding local variable. Upon receiving such a
valid proposal, $p$ will disseminate a stage 1 vote for $B$. Upon seeing a
stage 1 QC for $B$ (a set of $2f+1$ stage 1 votes signed by distinct players)
while in view $v$, $p$ will disseminate a stage 2 vote for $B$ (and reset its
local $Q^{1}$ variable, after which $B^{*}(Q^{1})=B$ and $v^{*}(Q^{1})=v$).
Upon seeing a stage 2 QC for $B$ (a set of $2f+1$ stage 2 votes signed by
distinct players) while in view $v$, $p$ will disseminate a stage 3 vote for
$B$ (and reset its local $Q^{2}$ variable, after which $B^{*}(Q^{2})=B$ and
$v^{*}(Q^{2})=v$). Upon seeing a stage 3 QC for any block, an honest player
considers that block and all its ancestors _confirmed_.

Consistency and liveness for HotStuff. We now argue (briefly and somewhat
informally) that this protocol satisfies consistency and liveness. For the
former, call two distinct blocks incompatible if neither is an ancestor of the
other. It suffices to argue that, once a stage 3 QC $Q$ is created for a block
$B$ in a view $v$—a prerequisite for confirmation—no QCs will be created for
any block incompatible with $B$ at any view $v^{\prime}\geq v$. Let $H$ denote
the honest players that contributed (stage 3) votes to $Q$ (updating at that
time their local $Q^{2}$-values to a view-$v$ stage 2 QC); because $n\geq
3f+1$ and a QC requires votes from at least $2f+1$ distinct players, $|H|\geq
f+1$. Any QC thus requires the participation of at least one player from $H$.
An honest player votes at most once in each stage of each view, so at view
$v^{\prime}=v$, players of $H$ will not vote for blocks other than $B$ and no
QCs for such blocks will be created. At view $v^{\prime}=v+1$, a valid block
proposal must either list $B$ as the parent block (in which case the proposed
block is compatible with $B$) or a block $B^{\prime\prime}$ that is supported
by a QC from some view $v^{\prime\prime}<v$ (in which case no player of $H$
will vote for it). We conclude that, at view $v^{\prime}=v+1$, no QC will be
created for any block incompatible with $B$. The same argument applies
inductively to views $v^{\prime}=v+2,v+3,\ldots$.

For liveness, consider a view $v$ with an honest leader $p$, with $v$ large
enough that, at GST, every honest player is in some view earlier than $v$. Let
$t$ denote the first timeslot at which some honest player enters view $v$.
(The timeslot $t$ must exist because no honest player can enter a view
$v^{\prime}>v$ prior to some honest player entering view $v$.) Because
$t\geq\text{GST}$, all honest players enter view $v$ by timeslot
$t+\lceil\Delta/\kappa\rceil$ and the leader $p$ will disseminate a block
proposal $(B,Q)$ by this timeslot. But will honest players vote in support of
this proposal? Consider such a player $p^{\prime}$ with locally defined
variable $Q^{2}$. Because $p^{\prime}$ set this value upon seeing a stage 2 QC
for $B^{*}(Q^{2})$ while in view $v^{*}(Q^{2})$, at least $f+1$ honest players
must have seen a stage 1 QC for $B^{*}(Q^{2})$ while in view $v^{*}(Q^{2})$,
and must have set their local value $Q^{1}$ so that
$v^{*}(Q^{1})=v^{*}(Q^{2})$ while in this view. At least one of the $2f+1$
$\mathtt{view}\ v$ messages in the VC for view $v$ received by the leader $p$
must be from one of these $f+1$ honest players, meaning that $v^{*}(Q)\geq
v^{*}(Q^{2})$; therefore, $p^{\prime}$ will regard the block proposal $(B,Q)$
made by $p$ as valid. Thus, so long as timer expiries are set appropriately,
stage 1, 2, and 3 QCs will be produced for $B$ in view $v$, resulting in the
block’s confirmation.

###  15.3. An informal overview of the required modifications

We define a protocol $(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$ such that
$\mathcal{O}$ is empty and $\mathcal{S}$ contains only the stake allocation
function. Modifying the permissioned HotStuff protocol to give a proof of
Theorem 11.2 involves three key considerations: dealing with changing sets of
players, determining a safe way to end epochs, defining a deterministic
protocol, and ensuring that the adversary remains $\rho$-bounded.

Accommodating changing players. To deal with a changing player set, we divide
the instructions into _epochs_ and have the player set change with each epoch.
(Each epoch loosely corresponds to a single execution of the permissioned
HotStuff protocol; due to asynchrony, however, different players may be in
different epochs at the same time.) Each epoch consists of an (unbounded)
number of views and, for some $N$, is responsible for producing confirmed
blocks with heights in $(eN,eN+N)]$. (While the view number will reset to 0
with every new epoch, block heights will continue to increment throughout the
execution of the protocol; all of this will be made precise in Section 15.4.)
To ensure that the player set changes only once with each epoch, blocks are
confirmed in batches, with all blocks with heights in $(eN,eN+N)]$ confirmed
at the same time (once blocks of all such heights have been produced). After
such a batch confirmation, executions consistent with the quasi-permissionless
setting will see all honest players that control a non-zero amount of stake
(with respect to the newly confirmed transactions) being active and carrying
out the instructions for epoch $e+1$.

How to complete an epoch. In the permissioned HotStuff protocol, a block may
be confirmed indirectly (without any stage 3 QC ever being produced for it),
by inheriting confirmation from a descendant block for which stage 1, 2 and 3
QCs have been received. This aspect of the protocol’s design poses a challenge
to safely updating the player set: if a potentially epoch-ending block $B$ at
height $eN+N$ receives only stage 1 and 2 QCs (say), which identifiers should
be allowed to propose and vote on descendants of $B$? If the protocol could be
sure that $B$ would eventually be indirectly confirmed, it could use the stake
allocation resulting from the execution of the transactions in $B$ and its
ancestors. But another block $B^{\prime}$ at height $eN+N$ might well also
receive stage 1 and 2 QCs, leading to conflicting opinions about the next
epoch’s player set.

Our solution is to allow the player set for epoch $e$ to continue proposing
and voting on blocks of heights greater than $eN+N$ until they produce a
(directly or indirectly) confirmed block $B^{*}$ of height $eN+N$. Once they
do so, any blocks produced in epoch $e$ with height $>eN+N$, together with the
votes for those blocks, are kept as part of the protocol’s permanent history
(as proof that the protocol operated as intended); crucially, any transactions
in these blocks are treated by the protocol as if they had never been included
in any block.515151Indeed, treating these transactions as confirmed could lead
to consistency violations. The issue is that the player set for epoch $e+1$
may not have been present to implement HotStuff’s locking mechanism during
epoch $e$. Concretely, suppose $B^{\prime}$ and $B^{\prime\prime}$ are both
blocks of height $>eN+N$ produced during epoch $e$, with $B^{\prime}$ the
parent of $B^{\prime\prime}$. Suppose both blocks receive stage 1, 2, and 3
QCs; this can occur during asynchrony, as the QCs for $B^{\prime\prime}$ may
be produced before any player has seen all of the QCs for $B^{\prime}$. If the
protocol were to regard the transactions in $B^{\prime}$ and
$B^{\prime\prime}$ as confirmed, then some of the epoch-$(e+1)$ player set may
initially see $B^{\prime\prime}$ as confirmed, even though most of that player
set has only seen stage 1, 2, and 3 QCs for $B^{\prime}$. The new player set
might then confirm new blocks that are descendants of $B^{\prime}$
incompatible with $B^{\prime\prime}$, resulting in a consistency violation.
The player set for epoch $e+1$ treats $B^{*}$ as a genesis block for the
epoch; transactions from the “orphaned” epoch-$e$ blocks (i.e., those with
height $>eN+N$) can then be re-included in epoch-$(e+1)$ blocks.

Defining a deterministic protocol. What is $N$? If a randomized protocol were
acceptable, each leader could be chosen with probability proportional to its
current stake, and the set of active players could change with every confirmed
block (i.e., $N=1$). To obtain a deterministic protocol, we take advantage of
the assumptions introduced in Section 11.3: every transaction preserves the
total amount of stake in existence; and stake is denominated in some
indivisible unit (and so stake amounts can be regarded as integers). Then, to
obtain the simplest-possible solution that is deterministic and guarantees at
least one honest leader produces a confirmed block in each epoch following
GST, we set $N$ equal to total amount of stake:
$N:=\sum_{p\in\mathcal{P}}\sum_{id\in\mathtt{id}(p)}\mathtt{S}(S_{0},\emptyset,id)$.
This choice of $N$ ensures that, in each epoch, every stake-holding honest
player has at least one opportunity as the leader of a view.

A more reasonable (and still deterministic) alternative would be a PoS
protocol in which, for some $N^{\prime}$, participating players must lock up
in escrow some positive integer multiple of $1/N^{\prime}$ of the total stake.
Then, $N^{\prime}$ plays (roughly) the previous role of $N$ but can be chosen
to be much smaller. See Section 15.7 for further details on the changes to the
basic PoS-HotStuff protocol that are required to implement such an “in escrow”
version.

Ensuring the adversary remains $\rho$-bounded. As highlighted by Theorem 11.1,
we must also be careful to ensure that confirmed sets of transactions do not
allocate more than a $\rho$-fraction of the stake to the adversary. As we will
see in Section 15.5, the assumption that the environment is $\rho$-bounded is
the key ingredient in an inductive proof that this property always holds (and
that, in fact, consistency is never violated).

###  15.4. PoS-HotStuff: The formal specification

As noted in Section 3.1, it is convenient to assume that whenever honest $p$
disseminates a message at some timeslot $t$, $p$ regards that dissemination as
received (by $p$) at the next timeslot.

Signed messages. Recall from Section 3.3 that, to model the use of a signature
scheme, we suppose that an entry of signed type must be of the form $(id,m)$
such that $id$ is an identifier (and where $m$ is arbitrary). In the
_authenticated_ setting that we work in here, an entry $e=(id,m)$ of signed
type is permitted for $p$ at $t$ if $id\in\mathtt{id}(p)$, or if $p$ has
previously received a message which contained the entry $e$ (in which case $p$
is free to repeat it to others).

Transaction gossiping and the variable $\mathtt{T}^{\ast}$. We assume that,
whenever any honest player first receives a transaction $\mathtt{tr}$, from
the environment or another player, they disseminate $\mathtt{tr}$ at the same
timeslot. Each honest player $p$ maintains a variable $\mathtt{T}^{\ast}$
which is the set of all transactions received by $p$ thus far.

Blocks. A block (other than the genesis block) is a tuple
$B=(id,(h,e,v,\mathtt{T},B^{\prime},Q))$, where $h\in\mathbb{N}$ denotes the
height of the block, $e$ denotes an epoch, $v$ denotes a view in epoch $e$,
$\mathtt{T}$ is a set of transactions, and $B^{\prime}$ is a block that is the
_parent_ of $B$. The entry $Q$ is a QC that will be used to verify the
validity of $B$; the intention is that $Q$ will record a stage 1 QC for
$B^{\prime}$. When an honest player receives $B$, it also regards the
transactions in $\mathtt{T}$ as having been received, and so disseminates
those transactions if it has not already done so. We set $id^{*}(B):=id$,
$h^{*}(B):=h$, $e^{*}(B):=e$, $v^{*}(B):=v$, $\mathtt{T}^{*}(B):=\mathtt{T}$,
and $Q^{*}(B):=Q$. The _genesis block_ $B_{g}:=(\emptyset)$ is regarded by
honest players as having been received at the beginning of the protocol
execution. The genesis block has no parent and has only itself as an
_ancestor_ , and we define $h^{*}(B_{g}):=0$, $e^{*}(B_{g}):=-1$,
$v^{*}(B_{g}):=0$, $\mathtt{T}^{*}(B_{g}):=\emptyset$, and
$Q^{*}(B_{g}):=\emptyset$; $id^{*}(B_{g})$ is undefined. For all other blocks
$B$, $h^{*}(B)\geq 1$, $e^{*}(B)\geq 0$, and $v^{*}(B)\geq 0$; otherwise
honest players will regard $B$ as invalid. The _ancestors_ of such a block $B$
are $B$ and all ancestors of its parent. Two blocks are _incompatible_ if
neither is an ancestor of the other.

Votes. A vote is a tuple $V=(id,(c,B,s))$, where $id$ is an identifier,
$c\in\mathbb{N}$ represents an amount of stake, $B$ is a block, and
$s\in\\{1,2,3\\}$ specifies the voting stage within the view. We define
$id^{*}(V):=id$, $c^{*}(V):=c$, $B^{*}(V):=B$, and $s^{*}(V):=s$. A vote
inherits the epoch, view, and height of its block: $e^{*}(V):=e^{*}(B)$,
$v^{*}(V):=v^{*}(B)$, and $h^{*}(V):=h^{*}(B)$.

$\mathtt{T}$-Quorum Certificates (QCs). Because quorum certificates (QCs) must
be stake-weighted (to accommodate sybils) and transactions can transfer stake
from one identifier to another, QCs must be defined relative to a set of
transactions (for us, the set of transactions confirmed in previous epochs).
For the genesis block, by definition, the empty set $\emptyset$ constitutes a
stage $s$ $\emptyset$-QC for all $s\in\\{1,2,3\\}$. For a block $B$ with
$h(B)>0$ and $s\in\\{1,2,3\\}$, a stage $s$ $\mathtt{T}$-QC for $B$ is,
roughly, a set of correctly specified stage $s$ votes for $B$ from players who
own at more than two-thirds of the stake according to
$\mathtt{S}(S_{0},\mathtt{T})$. Precisely, we say that a set of votes $Q$ is a
_stage $s$ $\mathtt{T}$-QC for $B$_ if the following conditions are all
satisfied:

  1. (QC1)

Agreement: For every $V\in Q$, $B^{*}(V)=B$ and $s^{*}(V)=s$. In this case, we
define $B^{*}(Q):=B$, $e^{*}(Q):=e^{*}(B)$, $v^{*}(Q):=v^{*}(B)$,
$h^{*}(Q):=h^{*}(B)$, and $s^{*}(Q):=s$.

  2. (QC2)

Correct stake amounts (w.r.t. $\mathtt{T}$). For each $V\in Q$,
$c^{*}(V)=\mathtt{S}(S_{0},\mathtt{T},id^{*}(V))$.

  3. (QC3)

No double-voting. There do not exist distinct
$(id,(c,B,s)),(id^{\prime},(c^{\prime},B^{\prime},s^{\prime}))\in Q$ with
$id=id^{\prime}$.

  4. (QC4)

Supermajority of stake. $\sum_{V\in Q}c^{*}(V)>\frac{2}{3}N$.

Selecting leaders. We denote by $\mathtt{leader}$ a function that allocates
leaders to views within an epoch in proportion to their stake. Because this
function is stake-dependent, it must be defined relative to a set of
transactions $\mathtt{T}$ (again, for us, the transactions confirmed in
previous epochs). Formally, we let $\mathtt{leader}$ be any function that
satisfies: If $\mathtt{S}(S_{0},\mathtt{T},id)=c$, then, for each
$k\in\mathbb{N}$ there exist $c$ many $v$ in the interval $[kN,(k+1)N)$ such
that $\mathtt{leader}(\mathtt{T},v)=id$. For example, given $\mathtt{T}$,
$\mathtt{leader}(\mathtt{T},\cdot)$ could repeatedly iterate through all $N$
coins (with $\mathtt{leader}(\mathtt{T},v)$ the identifier that owns the coin
$v\bmod N$) in some canonical order.

The variables $\mathtt{T}_{e}$ and $B_{g,e}$. Each player $p$ maintains local
variables $\mathtt{T}_{e}$ and $B_{g,e}$ (for each $e\in\mathbb{N}$), which
are initially undefined and become defined upon the player beginning epoch
$e$: intuitively, $\mathtt{T}_{e}$ is the set of transactions that $p$ regards
as confirmed by epochs $e^{\prime}<e$, while $B_{g,e}$ is the block of height
$eN$ that $p$ first sees as confirmed (regarded as a “genesis block” for epoch
$e$). The transactions of $\mathtt{T}_{e}$ will be the ones that determine who
should be leaders and who should be voting (and with weight) during epoch $e$.
The instructions of epoch $e$ attempt to build the blockchain above $B_{g,e}$.

The variable $M$. Each honest player $p$ maintains a local variable $M$, which
is the set of all messages received by $p$ thus far. Initially,
$M:=\\{B_{g}\\}$.

Defining $B^{*}_{g,e}(M),\mathtt{T}^{*}_{e}(M)$ and block validity. We next
specify the functions that an honest player uses to define its local variables
$B_{g,e}$ and $\mathtt{T}_{e}$ based on its local variable $M$. The function
$\mathtt{T}^{*}_{e}$ is defined on input $M$ if and only if
$\mathtt{B}^{*}_{g,e}$ is; in this case,
$\mathtt{T}^{*}_{e}(M)=\cup_{B^{\prime\prime}\in\mathcal{B}}\mathtt{T}^{*}(B^{\prime\prime})$,
where $\mathcal{B}$ denotes the ancestors of $B^{*}_{g,e}(M)$. That is,
whenever $\mathtt{T}^{*}_{e}(M)$ is defined, it is all the transactions
included in the blocks between the original genesis block $B_{g}$ and
$\mathtt{B}^{*}_{g,e}(M)$ (inclusive).

We can now define (or leave undefined), for a fixed set of messages $M$, the
value of $B^{*}_{g,e}(M)$ for all $e\geq 0$. We proceed by induction on $e$.
For $e=0$, $B^{*}_{g,0}(M):=B_{g}$ (and
$\mathtt{T}^{*}_{0}(M):=\mathtt{T}^{*}_{-1}(M):=\emptyset$). Now consider
arbitrary $e\geq 0$ and suppose that $B^{*}_{g,e}(M)$ is defined (as otherwise
we leave $B^{*}_{g,e+1}(M)$ undefined as well). We next define what it means
for a block $B$ in epoch $e$ to be “valid”; intuitively, $B$ is valid if it is
formed by the correct leader, if its parent is valid and $B$ correctly reports
a stage 1 QC for the parent, if it correctly reports its own height, and if it
includes a set of transactions that is valid relative to those already
included in ancestor blocks other than $B$.525252Thus, formally, we define
validity for a block $B$ (with respect to $M$) by induction on $e^{*}(B)$ and
then on height. Precisely, the block $B=(id,(h,e,v,\mathtt{T},B^{\prime},Q))$
is $M$-valid if and only if $B=B_{g}$ or:

  * •

Correct leader: $id=\mathtt{leader}(T^{*}_{e}(M),v)$.

  * •

Valid transactions:
$\cup_{B^{\prime\prime}\in\mathcal{B}}\mathtt{T}^{*}(B^{\prime\prime})$ is a
valid set of transactions relative to $S_{0}$, where $\mathcal{B}$ denotes the
ancestors of $B$.

  * •

Valid predecessor: $B^{\prime}$ is $M$-valid, with $h(B^{\prime})=h-1$.

  * •

Parent supported by QC (case 1): If $e^{*}(B^{\prime})=e-1$ then $Q$ is a
stage 1 $\mathtt{T}_{e-1}^{*}(M)$-QC for $B^{\prime}$.

  * •

Parent supported by QC (case 2): If $e^{*}(B^{\prime})=e$ then $Q$ is a stage
1 $\mathtt{T}_{e}^{*}(M)$-QC for $B^{\prime}$.

In particular, $p$ regards a block $B$ as $M$-valid only if it regards all of
$B$’s ancestors as $M$-valid, and in particular has seen stage 1 QCs for all
of $B$’s ancestors. (The player may not have seen stage 3 QCs for all of these
blocks, however.)

Finally, $B^{*}_{g,e+1}(M)$ is defined if and only if:

  * •

there is at least one $M$-valid block $B$ with $e^{*}(B)=e$ and $h^{*}(B)\geq
eN+N$ for which $M$ contains stage 1, 2, and 3 $\mathtt{T}_{e}$-QCs for $B$;

  * •

no two such blocks are incompatible; and

  * •

$B$ has $B^{*}_{g,e}(M)$ as an ancestor;

in this case, $B^{*}_{g,e+1}(M)$ is defined as the unique ancestor
$B^{\prime}$ of $B$ at height $eN+N$ (and $\mathtt{T}^{*}_{e+1}(M)$ is then
defined, as usual, as all transactions included in $B^{\prime}$ and its
ancestors).

The confirmation rule. Given a set $M$ of messages, the confirmed transactions
are defined as $\mathcal{C}(M):=\mathtt{T}_{e}^{*}(M)$, where $e$ the largest
value for which $\mathtt{T}_{e}^{*}(M)\downarrow$.

Comment. It is a subtle but important point in the definitions above that,
while executing the instructions for epoch $e$, honest players may produce
blocks of height $>eN+N$ with stage 3 $\mathtt{T}_{e}$-QCs (where
$\mathtt{T}_{e}$ is as defined for some honest player), but the transactions
in such blocks will not be considered confirmed by the confirmation rule. The
reason for this is explained in Section 15.3.

View certificates (VCs). Recall that, when a player $p$ wishes to enter view
$v$ in our permissioned version of HotStuff, $p$ disseminates a
$\mathtt{view}\ v$ message. The role of this message is two-fold. First, it
alerts other players that $p$ wishes to enter view $v$. Second, the message
relays $p$’s present value for its local variable $Q^{1}$ to the leader of
view $v$: as explained in the liveness argument of Section 15.2, this is the
information the leader needs to propose a block that other honest players will
vote for. In our PoS version of the protocol, we use a similar setup.

A $\mathtt{view}\ (e,v)$ message is a tuple $r=(id,(c,e,v,Q))$. Such a message
is $M$-valid if all of the following are true:

  * •

Epoch $e$ has begun according to $M$: $\mathtt{T}^{*}_{e}(M)\downarrow$;

  * •

Correct stake amount (w.r.t. $\mathtt{T}^{*}_{e}(M)$):
$c=\mathtt{S}(S_{0},T^{*}_{e}(M),id)$;

  * •

Supported by QC: $Q=\emptyset$ or $Q$ is a stage 1 $\mathtt{T}^{*}_{e}(M)$-QC
for some block $B$ that is $M$-valid with $e^{*}(B)=e$.

For such a tuple $r$, define $c^{*}(r):=c$. A set $R\subseteq M$ of
$\mathtt{view}\ (e,v)$ messages is then an $M$-VC for $(e,v)$ if and only if
the following three requirements are met:

  * •

Validity: every $r\in R$ is $M$-valid;

  * •

No double-voting: there do not exist distinct
$(id,(c,e,v,Q)),(id^{\prime},(c^{\prime},e^{\prime},v^{\prime},Q^{\prime}))\in
R$ with $id=id^{\prime}$; and

  * •

Supermajority of stake: $\sum_{r\in R}c^{*}(r)>\frac{2}{3}N$.

Choosing blocks to propose. When an honest player $p$ controls the identifier
$id$ that is the leader of a view $v$ (within some epoch $e$), they are
instructed to propose a block as follows. Suppose $p$ entered $v$ on account
of receiving an $M$-VC for $(e,v)$, which we denote by $R$. First, suppose
that no one has an opinion about which existing block to build on, in the
sense that, for every $r=(id,(c,e,v,Q))\in R$, $Q=\emptyset$. Then, $p$ is
instructed to extend the block it sees as the genesis block of this epoch with
a new block that contains all of the not-yet-confirmed transactions that $p$
is aware of. Formally, in this case, define the block proposal function
$\mathtt{block}$ by

(1) $\mathtt{block}(\underbrace{B_{g,e},\mathtt{T}^{*},M}_{\text{$p$'s local
vars}},id):=(id,(h^{*}(B_{g,e})+1,e,v,\mathtt{T},B_{g,e},Q)),$

where $\mathtt{T}^{*}$ denotes the set of all transactions that $p$ has
received;
$\mathtt{T}=\mathtt{T}^{*}-\cup_{B^{\prime\prime}\in\mathcal{B}}\mathtt{T}^{*}(B^{\prime\prime})$,
where $\mathcal{B}$ denotes the ancestors of $B_{g,e}$; and $Q$ is a stage 1
$\mathtt{T}^{*}_{e-1}(M)$-QC for $B_{g,e}$.

Otherwise, the leader proceeds similarly to the permissioned HotStuff
protocol, choosing the QC $Q$ with largest view and proposing a block with
$B^{*}(Q)$ as the parent. Formally, from amongst all $Q^{\prime}$ such that
there exists $r=(id,(c,e,v,Q^{\prime}))\in R$, choose $Q$ such that $v^{*}(Q)$
is maximal and define $\mathtt{block}$ by

(2)
$\mathtt{block}(B_{g,e},\mathtt{T}^{*},M,id):=(id,(h^{*}(Q)+1,e,v,\mathtt{T},B^{*}(Q),Q));$

here
$\mathtt{T}=\mathtt{T}^{*}-\cup_{B^{\prime\prime}\in\mathcal{B}}\mathtt{T}^{*}(B^{\prime\prime})$,
where $\mathcal{B}$ denotes the ancestors of $B^{*}(Q)$.

The variables $Q^{1}_{e}$ and $Q^{2}_{e}$. Each player maintains variables
$Q^{1}_{e}$ and $Q^{2}_{e}$ which, analogous to the variables $Q^{1}$ and
$Q^{2}$ in our description of permissioned HotStuff in Section 15.2, implement
a locking mechanism within epoch $e$.

The pseudocode for the PoS-HotStuff protocol is described in Algorithm 1.
There are six main blocks of pseudocode, which describe when and how a player
enters a new epoch (and what to do at that time); when and how to enter a new
view (and, if the view’s leader, disseminate a block); when and how to
disseminate a stage 1, stage 2, and stage 3 vote; and when and how to
disseminate a $\mathtt{view}$ message.

Algorithm 1 PoS-HotStuff (instructions for a player $p$)

1:Local variables

2:$Q^{1}_{e}$, initially set to $\emptyset$, $Q^{2}_{e}$, initially undefined
$\triangleright$ Used to implement locking

3:$B_{g,e},\mathtt{T}_{e}$, initially undefined $\triangleright$ Defined upon
entering epoch $e$

4:$\mathtt{T}^{\ast}$, initially $\mathtt{T}^{\ast}:=\emptyset$
$\triangleright$ The set of all transactions received by $p$

5:$M$, initially $M:=\\{B_{g}\\}$ $\triangleright$ The set of all messages
received by $p$

6:$e$, initially $e:=-1$ $\triangleright$ $p$’s present epoch

7:$v$, initially $v:=-1$ $\triangleright$ $p$’s present view

8:$B$, initially undefined $\triangleright$ Records a block value

9:

10:At every timeslot $t$

11: Update $M$ and $\mathtt{T}^{\ast}$;

12: Disseminate all transactions in $\mathtt{T}^{\ast}$ received for the first
time at $t$;

13:

14:Upon $\mathtt{T}_{e^{\prime}}^{*}(M)\downarrow$ for $e^{\prime}>e$:

15: Set $\mathtt{T}_{e^{\prime}}:=\mathtt{T}_{e^{\prime}}^{*}(M)$,
$B_{g,e^{\prime}}:=B_{e^{\prime}}^{*}(M)$, $e:=e^{\prime}$, $v:=-1$;
$\triangleright$ Enter new epoch

16: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(S_{0},\mathtt{T}_{e},id)>0$:

17: Let $c:=\mathtt{S}(S_{0},\mathtt{T}_{e},id)$;

18: Disseminate the view $(e,0)$ message $(id,(c,e,0,\emptyset))$;

19:

20:Upon receiving an $M$-VC for $(e,v^{\prime})$ with $v^{\prime}>v$:

21: Set $v:=v^{\prime}$; Set $B\uparrow$; $\triangleright$ Enter new view

22: Set the $(e,v)$-timer to expire after $5\lceil\Delta/\kappa\rceil$ active
non-waiting timeslots; $\triangleright$ Set timer

23: If $\mathtt{leader}(\mathtt{T}_{e},v)=id\in\mathtt{id}(p)$ then:

24: Disseminate $\mathtt{block}(B_{g,e},\mathtt{T}^{*},M,id)$;
$\triangleright$ Leader disseminates block as per (1) or (2)

25:

26:Upon first receiving an $M$-valid block
$(id,(h,e,v,\mathtt{T},B^{\prime},Q))$:

27: If $Q_{e}^{2}\uparrow$ or $Q_{e}^{2}\leq v^{*}(Q)$ then: $\triangleright$
Checks lock

28: Set $B:=(id,(h,e,v,\mathtt{T},B^{\prime},Q))$;

29: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(S_{0},\mathtt{T}_{e},id)>0$:

30: Let $c:=\mathtt{S}(S_{0},\mathtt{T}_{e},id)$;

31: Disseminate the vote $(id,(c,B,1))$; $\triangleright$ Stage 1 vote

32:

33:Upon $B\downarrow$ and first receiving $Q^{\prime}$ which is a stage 1
$\mathtt{T}_{e}$-QC for $B$:

34: Set $Q^{1}_{e}:=Q^{\prime}$; $\triangleright$ Sets $Q^{1}_{e}$

35: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(S_{0},\mathtt{T}_{e},id)>0$:

36: Let $c:=\mathtt{S}(S_{0},\mathtt{T}_{e},id)$;

37: Disseminate the vote $(id,(c,B,2))$; $\triangleright$ Stage 2 vote

38:

39:Upon $B\downarrow$ and first receiving $Q^{\prime\prime}$ which is a stage
2 $\mathtt{T}_{e}$-QC for $B$:

40: Set $Q^{2}_{e}:=Q^{\prime\prime}$; $\triangleright$ Sets $Q^{2}_{e}$

41: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(S_{0},\mathtt{T}_{e},id)>0$:

42: Let $c:=\mathtt{S}(S_{0},\mathtt{T}_{e},id)$;

43: Disseminate the vote $(id,(c,B,3))$; $\triangleright$ Stage 3 vote

44:

45:Upon $(e,v)$-timer expiry or first receiving a stage 3 $\mathtt{T}_{e}$-QC
for $B$:

46: For each $id\in\mathtt{id}(p)$ such that
$\mathtt{S}(S_{0},\mathtt{T}_{e},id)>0$:

47: Let $c:=\mathtt{S}(S_{0},\mathtt{T}_{e},id)$;

48: Disseminate the $\mathtt{view}(e,v+1)$ message $(id,(c,e,v+1,Q^{1}_{e}))$;

###  15.5. Consistency, accountability, and weakly $\rho$-bounded adversaries

We prove in this section that, whenever an execution of the PoS-HotStuff
protocol leads to a consistency violation, it is possible to extract from the
disseminated messages a set of identifiers that are guaranteed to belong to
Byzantine players and that collectively control at least one-third of the
overall stake. That is, we prove that the protocol is $(1/3,1)$-accountable in
the sense of Section 7.4. In particular, the protocol satisfies consistency
with respect to a $\rho$-bounded adversary (in the sense of Section 5.1) for
all $\rho<1/3$. We conclude this section with the additional arguments needed
to accommodate a weakly $\rho$-bounded adversary, as required by Theorem 11.2.

Defining a blame function. The definition of accountability involves a blame
function $F$ that maps a set of messages to a set of identifiers controlled by
Byzantine players. Intuitively, our blame function will return identifiers
that double-voted in the protocol’s execution. Precisely, given a message set
$M$, define $F(M)$ as the set of all identifiers $id$ that cast two votes
$V,V^{\prime}\in M$ such that:

  * (F1)

$V$ is a stage 3 vote for some block $B$, signed by identifier $id$;

  * (F2)

$V^{\prime}$ is a stage 1 vote for some block $B^{\prime}\neq B$, signed by
identifier $id$;

  * (F3)

$e^{*}(B)=e^{*}(B^{\prime})$ and $v^{*}(V)\leq v^{*}(V^{\prime})$; and

  * (F4)

$v^{*}(Q^{*}(B^{\prime}))<v^{*}(V)$.

To see why $F(M)$ can never include an identifier controlled by an honest
player, suppose that such a player $p$ casts a stage 3 vote for a block $B$ in
the view $v:=v^{*}(V)$. Within a view, an honest player votes for at most one
block (the first block proposal it receives from the view’s leader), so $p$
will not vote for any block other than $B$ in the view $v$. Because $p$ casts
a stage 3 vote for $B$ in view $v$, it resets its local variable $Q^{2}_{e}$
at that time so that $v^{*}(Q^{2}_{e})=v$; further resets at later views
within the epoch will only increase its value. Thus, at all views
$v^{\prime}>v$, $p$ will never cast a vote for a block $B^{\prime}$ for which
$v^{*}(Q^{*}(B^{\prime}))<v$.

Consistency failures. Consider an execution of the PoS-HotStuff protocol that
sees a consistency failure, in the form of two incompatible blocks that are
confirmed by different honest players. By the definition of block validity,
players that agree on their local values of $B_{g,e}$ and $B_{g,e+1}$ for some
$e\geq 0$ also agree on all blocks in between. By the definition of the
confirmation rule, a player only confirms descendants of $B_{g,e}$ for values
of $e\geq 0$ for which both $B_{g,e}$ and $B_{g,e+1}$ are defined. Thus, a
consistency failure occurs only if, for some $e\geq 0$, two honest players set
distinct values for their local variable $B_{g,e+1}$.

We say that a block $B$ is _seen as valid_ if there exists some honest $p$ and
some timeslot $t$ at which $B$ is $M$-valid, where $M$ is as locally defined
for $p$ at $t$. Let $e$ be the first epoch at which honest players set
distinct values for $B_{g,e+1}$. Recalling the definition of the function
$B^{*}_{g,e+1}(\cdot)$, there must exist incompatible blocks $B$ and
$B^{\prime\prime}$—descendants of the competing values for $B_{g,e+1}$, each
with height at least $eN+N$—such that:

  * •

$e^{*}(B)=e^{*}(B^{\prime\prime})=e$;

  * •

$B$ and $B^{\prime\prime}$ are both seen as valid;

  * •

$B$ and $B^{\prime\prime}$ both receive stage 1,2, and 3 $\mathtt{T}_{e}$-QCs.

Without loss of generality, suppose $v^{*}(B)\leq v^{*}(B^{\prime\prime})$,
set $v:=v^{*}(B)$, and let $Q$ be a stage 3 $\mathtt{T}_{e}$-QC for $B$. Among
all blocks $B^{\prime}$ incompatible with $B$ that received a stage 1 QC
$Q^{\prime}$ at a view $v^{\prime}\geq v$, choose one with $v^{\prime}$ as
small as possible. (Such a block exists because $B^{\prime\prime}$ is one
candidate.) This choice of $v^{\prime}$ ensures that the parent of
$B^{\prime}$ is from a view prior to $v$ (i.e., $v^{*}(Q^{*}(B^{\prime}))<v$).

A pair of votes for $Q$ and $Q^{\prime}$ satisfies (F1)–(F4), so every
identifier that casts such a pair will be included in $F(Q\cup Q^{\prime})$.
Because $Q$ is a stage 3 $\mathtt{T}_{e}$-QC for $B$, no identifier appears
twice and $\sum_{V\in
Q}\mathtt{S}(S_{0},\mathtt{T}_{e},id^{*}(V)))>\frac{2}{3}N$. Because
$Q^{\prime}$ is a stage 1 $\mathtt{T}_{e}$-QC for $B^{\prime}$, no identifier
appears twice and $\sum_{V^{\prime}\in
Q^{\prime}}\mathtt{S}(S_{0},\mathtt{T}_{e},id^{*}(V^{\prime})))>\frac{2}{3}N$.
It follows that:

  1. $(\dagger_{1})$

$\sum_{id\in F(Q\cup
Q^{\prime})}\mathtt{S}(S_{0},\mathtt{T}_{e},id)>\frac{1}{3}N$, implying that
the protocol is $(1/3,1)$-accountable.535353Accountability, as defined in
Section 7.4, requires only that the blamed identifiers be assigned a large
amount of stake with respect to some subset of confirmed transactions. Here,
this subset is precisely specified and natural: the set $\mathtt{T}_{e}$ of
transactions confirmed by all honest players in the epochs that precede the
first epoch $e$ with a consistency failure.

  2. $(\dagger_{2})$

$\mathtt{T}_{e}$ allocates $\geq\frac{1}{3}N$ stake to Byzantine players,
implying that, for every $\rho<1/3$, the protocol satisfies consistency with
respect to a $\rho$-bounded adversary.

Proving that the adversary remains $\rho$-bounded. To satisfy the requirements
of Theorem 11.2 (as opposed to only Theorem 9.1), we consider next a weakly
$\rho$-bounded adversary, meaning that we make no blanket assumptions on the
fraction of stake controlled by Byzantine players throughout the protocol
execution and instead restrict attention to an environment that is
$\rho$-bounded in the sense of Section 11.3.

Assume that the environment is $\rho$-bounded for some $\rho<1/3$. We argue by
induction that, for every epoch $e\geq 0$:

  1. (P1)

For all $e^{\prime}\leq e$, no two honest players define distinct values for
$B_{g,e^{\prime}}$ or $\mathtt{T}_{e^{\prime}}$.

  2. (P2)

If $\mathtt{T}_{e}\downarrow$, $\mathtt{S}(S_{0},\mathtt{T}_{e})$ allocates at
most a $\rho$-fraction of the total stake to Byzantine players.

The base case of $e=0$ holds by the initialization of the protocol and the
assumption of a $\rho$-bounded environment. Now suppose (P1) and (P2) hold for
some epoch $e\geq 0$. Using $(\dagger_{2})$, above, property (P1) will hold
also for epoch $e+1$. To prove (P2), suppose there is some timeslot at which
$B_{g,e+1}$ and $\mathtt{T}_{e+1}$ become defined for some honest player.
(Otherwise, there is nothing to prove.) Because $\mathtt{T}_{e}$ allocates the
adversary at most a $\rho$-fraction of the stake with $\rho<1/3$, at least one
vote in any stage 1 $\mathtt{T}_{e}$-QC for $B_{g,e+1}$ must be by an honest
player. Let $t^{*}$ be a timeslot at which some honest player $p$ disseminates
a stage 1 vote for $B_{g,e+1}$. At $t^{*}$, $\mathtt{T}_{e}$ is the set of
confirmed transactions for $p$, and all transactions in $\mathtt{T}_{e+1}$
have already been issued by the environment. Let $\mathtt{T}_{\text{hon}}$
denote the set of all honest transactions issued by the environment at
timeslots $\leq t^{*}$. From the definition of a $\rho$-bounded environment in
Section 11.3—with $\mathtt{T}_{e}$ and $\mathtt{T}_{\text{hon}}$ playing the
roles of $\mathtt{T}_{1}$ and $\mathtt{T}_{2}$, respectively—it follows that
$\mathtt{T}_{e}$ contains all the transactions required for any transaction in
$\mathtt{T}_{\text{hon}}$ to be valid relative to $S_{0}$,
$\mathtt{T}_{e}\cup\mathtt{T}_{\text{hon}}$ is a valid set of transactions
relative to $S_{0}$, and
$\mathtt{S}(S_{0},\mathtt{T}_{e}\cup\mathtt{T}_{\text{hon}})$ allocates the
adversary at most a $\rho$-fraction of the stake. Because honest transactions
can only increase the adversary’s share of stake,
$\mathtt{S}(S_{0},\mathtt{T}_{e}\cup(\mathtt{T}_{e+1}\cap\mathtt{T}_{\text{hon}}))$
also allocates the adversary at most a $\rho$-fraction of the stake. Because
Byzantine transactions can only decrease the adversary’s share of stake,
$\mathtt{S}(S_{0},\mathtt{T}_{e+1})$ must allocate the adversary at most a
$\rho$-fraction of the stake, completing the argument.

###  15.6. Liveness and optimistic responsiveness

We first show that the PoS-HotStuff protocol satisfies liveness (in the sense
of Section 5.2) with respect to a weakly $\rho$-bounded adversary with
$\rho<1/3$, and then extend the argument to show that the protocol satisfies
optimistic responsiveness (in the sense of Section 7.5). We make no attempt to
optimize the constants in our liveness parameters.

Proving liveness. Order epoch-view pairs $(e,v)$ lexicographically; in an
abuse of terminology, we often refer to such pairs as “views.” Because the
environment is $\rho$-bounded, the consistency argument in Section 15.5
implies that honest players always agree on the values of $B_{g,e}$ and
$\mathtt{T}_{e}$ (whenever they are defined). When $B_{g,e}$ (and hence
$\mathtt{T}_{e}$) is defined, the “leader of view $(e,v)$” refers to the
identifier $\mathtt{leader}(\mathtt{T}_{e},v)$. In this case, call a view
$(e,v)$ post-GST if every honest player is in some view earlier than $(e,v)$
at GST, and call it good if it is post-GST and
$\mathtt{leader}(\mathtt{T}_{e},v)$ is controlled by an honest player. Call a
player a stakeholder in view $(e,v)$ if at least one if its identifiers is
allocated a non-zero amount of stake in $\mathtt{S}(S_{0},\mathtt{T}_{e}$). By
the definition of the $\mathtt{leader}$ function, the leader of a view must be
controlled by a stakeholder. By the definition of the quasi-permissionless
setting, honest stakeholders are always active.

The first claim asserts that good views result in blocks with stage 3 QCs,
unless some honest player transitions to a larger epoch first.

Claim 1: If $(e,v)$ is a good view that is first reached by an honest player
($p$, say) at timeslot $t$ (with $t$ necessarily larger than GST), then by
timeslot $t+5\lceil\Delta/\kappa\rceil$, either:

  * (i)

a block proposed in view $(e,v)$ receives stage 1, 2, and 3 QCs in that view,
which are seen by all honest stakeholders; or

  * (ii)

some honest player has entered an epoch $e^{\prime}>e$.

###### Proof.

Because $t\geq\text{GST}$, by timeslot $t+\lceil\Delta/\kappa\rceil$, every
honest stakeholder will have received all the messages that had been received
by $p$ by timeslot $t$ and must therefore be in some view at least as large as
$(e,v)$. Suppose first that no honest stakeholder enters a view higher than
$(e,v)$ at or before timeslot $t+4\lceil\Delta/\kappa\rceil$. In this case,
the (honest and active) leader $p^{\prime}$ of view $(e,v)$ will disseminate a
block proposal $B$ for the view by timeslot $t+\lceil\Delta/\kappa\rceil$. All
honest stakeholders will receive this proposal by timeslot
$t+2\lceil\Delta/\kappa\rceil$, and will regard the proposed block as valid by
that timeslot (having then received all messages received by $p^{\prime}$ by
timeslot $t+\lceil\Delta/\kappa\rceil$). Let $p^{\prime\prime}$ denote an
honest stakeholder with the maximum value of $v^{*}(Q^{2}_{e})$ upon entering
view $(e,v)$. Because $p^{\prime\prime}$ set this value upon seeing a stage 2
$\mathtt{T}_{e}$-QC for $B^{*}(Q^{2}_{e})$, there must exist a set of honest
stakeholders $P_{1}$, controlling at least $N/3$ units of stake (according to
$\mathtt{T}_{e}$), that saw a stage 1 $\mathtt{T}_{e}$-QC for
$B^{*}(Q^{2}_{e})$ while in view $v^{*}(Q_{e}^{2})$ and therefore set their
local values $Q^{1}_{e}$ so that $v^{*}(Q^{1}_{e})=v^{*}(Q_{e}^{2})$ while in
this view. If any player in $P_{1}$ subsequently updated their local value
$Q^{1}_{e}$, then $v^{*}(Q^{1}_{e})$ must have increased with this update. Now
let $R$ denote the VC received by the leader $p^{\prime}$ that caused it to
enter view $(e,v)$, and let $P_{2}$ denote the stakeholders that disseminated
the messages in $R$. Because the players in $P_{2}$ own total stake more than
$2N/3$ (according to $\mathtt{T}_{e}$), there must be some (honest)
stakeholder in the intersection $P_{1}\cap P_{2}$ that contributed a
$\mathtt{view}\leavevmode\nobreak\ (e,v)$ message to $R$ with a QC $Q$
satisfying $v^{*}(Q)\geq v^{*}(Q_{e}^{2})$. Because $p^{\prime}$ is honest,
and by the definition of the function $\mathtt{block}$, the block proposal by
$p^{\prime}$ satisfies $v^{*}(Q^{*}(B))\geq v^{*}(Q_{e}^{2})$. Thus, due to