# Permissionless Consensus

Andrew Lewis-Pye  Department of Mathematics London School of Economics London
UK<EMAIL_ADDRESS>and  Tim Roughgarden  Data Science Institute Columbia
University & a16z Crypto New York USA<EMAIL_ADDRESS>
(Date: Jan 2023)

###### Abstract.

Blockchain protocols typically aspire to run in a permissionless setting, in
which nodes are owned and operated by a potentially large number of diverse
and unknown entities, with each node free to use multiple identifiers and to
start or stop running the protocol at any time. This paper offers a framework
for reasoning about the rich design space of blockchain protocols and their
capabilities and limitations in permissionless settings.

We propose a hierarchy of settings with fundamentally different “degrees of
permissionlessness,” specified by the amount of knowledge that a protocol has
about the current participants:

  * •

Fully permissionless setting: A protocol has no knowledge about current
participation. Proof-of-work protocols are typically interpreted as operating
in this setting.

  * •

Dynamically available setting: A protocol knows a (dynamically evolving) list
of identifiers (e.g., public keys associated with locked-up stake), and the
current participants are a subset of these identifiers. Proof-of-stake
longest-chain protocols are typically interpreted as operating in this
setting.

  * •

Quasi-permissionless setting: The current participants are all of the
identifiers in the set above. Proof-of-stake PBFT-style protocols are
typically interpreted as operating in this setting.

This paper also presents a number of results that showcase the versatility of
our analysis framework for reasoning about blockchain protocols that operate
in one these settings. For example:

  * •

In the fully permissionless setting, even in the synchronous setting and with
severe restrictions on the total size of the Byzantine players, every
deterministic protocol for Byzantine agreement has an infinite execution in
which honest players never terminate.

  * •

In the dynamically available and partially synchronous setting, no protocol
can solve the Byzantine agreement problem with high probability, even if there
are no Byzantine players at all.

  * •

In the quasi-permissionless and partially synchronous setting, by contrast,
assuming a suitable bound on the total size of the Byzantine players, there is
a deterministic proof-of-stake protocol for state machine replication.

  * •

In the dynamically available, authenticated, and synchronous setting, no
optimistically responsive state machine replication protocol guarantees
consistency and liveness, even when there are no Byzantine players at all.

  * •

In the quasi-permissionless and synchronous setting, every proof-of-stake
state machine replication protocol that uses only time-malleable cryptographic
primitives is vulnerable to long-range attacks.

##  1\. Introduction

###  1.1. Consensus: Permissioned vs. Permissionless

The goal of a consensus protocol is, loosely speaking, to keep a distributed
network of nodes “in sync,” even in the presence of an unpredictable
communication network and incorrect behavior by some of the nodes. In a
typical traditional application, such as replicating a database in order to
boost its uptime, the nodes would generally be owned and operated by one or a
small number of entities, like a government agency or a corporation. Such
applications are most naturally modeled with what is now called the
permissioned setting, meaning that the set of nodes that will be running the
consensus protocol is fixed and known at the time of protocol deployment. Many
consensus protocols are, quite reasonably, designed and analyzed with the
permissioned setting in mind.

Over the past 40+ years, the feasibility of permissioned consensus has been
studied intensely for a wide range of problems, communication network models,
and fault models. For example, for the Byzantine agreement problem, classical
work has characterized, as a function of the degree of asynchrony (e.g.,
synchronous vs. partially synchronous vs. asynchronous) and the severity of
faults (e.g., crash vs. omission vs. Byzantine), the maximum-possible fraction
of faulty nodes that can be tolerated by a correct consensus protocol.

Like any mathematical framework worth its salt, the traditional models and
language for discussing consensus problems and protocols are versatile and
have proved relevant for contemporary, unforeseen applications. The focus of
this work is blockchain protocols. The fundamental goal of a typical such
protocol is state machine replication—keeping a network of nodes in sync on
the current state of the blockchain. For example, the goal of the Bitcoin
protocol is to keep the nodes running it in agreement on the current set of
“unspent transaction outputs (UTXOs).” The goal of the Ethereum protocol is to
keep the nodes running it in agreement on the current state of the Ethereum
Virtual Machine.

Unlike traditional consensus protocols, blockchain protocols such as Bitcoin
and Ethereum aspire to run in a “permissionless setting,” which means,
roughly, that the protocol has no idea who is running it. The shift from
permissioned to permissionless entails three distinct challenges:

> The unknown players challenge. The set of distinct entities that might run
> the protocol is unknown at the time of protocol deployment and is of unknown
> size.

> The player inactivity challenge. Such entities can start or stop running the
> protocol at any time.

> The sybil challenge. Each such entity can operate the protocol using an
> unknown and unbounded set of identifiers (a.k.a. “sybils”).

We stress that these three challenges are logically independent, and every
subset of them leads to a distinct and well-defined setting that has its own
set of possibility and impossibility results (see also Section 2). Indeed,
different impossibility results in this paper are driven by different subsets
of these challenges.

Why impose these three additional challenges to the tried-and-true
permissioned setting? Because while the traditional motivation for replication
is tolerance to hardware and software faults, the primary motivation for it in
blockchain protocols such as Bitcoin and Ethereum is “decentralization,”
meaning that anyone should be able to contribute meaningfully to running the
protocol and that no entity or small cartel of entities should be in a
position to “turn it off” or otherwise interfere with its operation. All known
approaches to designing blockchain protocols that are decentralized in this
sense must grapple with the unknown players, player inactivity, and sybil
challenges.

All else equal, consensus cannot be easier with these additional challenges
than without. Many consensus protocols designed for the permissioned setting
are not even well defined outside of it. For example, if a protocol makes
progress by assembling agreeing votes from a supermajority (i.e., more than
two-thirds) of the nodes running it, how could it be run in a setting in which
the number of nodes is unknown, or in a setting in which one node can
masquerade as many? The best-case scenario would seem to be that consensus
problems that are solvable in the permissioned setting remain solvable in a
permissionless setting, albeit with additional protocol complexity and/or
under compensatory assumptions; the worst-case scenario would be that such
problems cannot be solved at all in a permissionless setting. A priori, there
is no reason to expect that any consensus protocol could provide non-trivial
guarantees when facing the unknown players, player inactivity, and sybil
challenges.

The Bitcoin protocol (Nakamoto et al., 2008) was the first to demonstrate
that, under appropriate assumptions, state machine replication is in fact
possible in a permissionless setting. We now know that the design space of
blockchain protocols is surprisingly rich, and even the protocols that are
most widely used in practice differ substantially across multiple dimensions.
For example, different protocols employ different types of sybil-resistance
mechanisms to address the sybil challenge and ensure that a participant’s
control over the protocol is independent of the number of identities under
which it participates. The Bitcoin protocol takes a “proof-of-work” approach
to sybil-resistance (with a participant’s control determined by its
computational power, specifically hashrate). Many more modern blockchain
protocols use alternative approaches including, most commonly, “proof-of-
stake” (with a participant’s power controlled by how much of a protocol’s
native cryptocurrency it has locked up in escrow). Blockchain protocols can
also differ in their approaches to permissionless consensus along several
other dimensions, including the approach to voting (e.g., the longest-chain
rule versus more traditional quorum certificates) and the assumed
cryptographic primitives (e.g., digital signature schemes and cryptographic
hash functions only, or also more exotic primitives like verifiable delay
functions or ephemeral keys).

Summarizing: (i) permissionless consensus is a fundamental component of modern
blockchain protocols and must address the unknown players, player inactivity,
and sybil challenges; (ii) these challenges appear to make consensus strictly
harder to achieve than in the traditional permissioned setting; and (iii) any
model for reasoning thoroughly about the design space of blockchain protocols
and their capabilities and limitations must accommodate an unruly rogues’
gallery of examples. This paper provides such a model, demonstrates several
senses in which permissionless settings are provably more difficult than the
traditional permissioned setting, and identifies unavoidable protocol
ingredients and additional assumptions that are necessary (and often
sufficient) to achieve permissionless consensus.111This paper subsumes two
earlier versions with different titles (Lewis-Pye and Roughgarden, 2020, 2021)
and includes a more fleshed-out model (e.g., the explicit hierarchy in Section
1.2) and a number of new results (Theorems 7.4, 9.1, 10.1, 11.1 and 11.2).

###  1.2. Degrees of Permissionlessness: A Hierarchy of Four Settings

The traditional foils to a consensus protocol are message delays and faulty
nodes, and in much of the literature these challenges are parameterized
through hierarchies of successively weaker assumptions. For example, the
synchronous and asynchronous models can be viewed as opposite ends of a
“degree of asynchrony” hierarchy, while crash and Byzantine faults bookend a
“fault severity” hierarchy.

The first contribution of this paper is to make explicit a “degree of
permissionlessness” hierarchy that is defined by four settings (Table
1).222Sections 2.1–2.3 discuss how these settings compare to those studied or
implicit in previous works. As the degree of permissionlessness of the setting
increases—roughly, as the knowledge a protocol has about current participation
decreases—positive results become more impressive and harder to come by (and
impossibility results are increasingly to be expected). Informally, the four
settings are:

  1. (1)

Fully permissionless setting. At each moment in time, the protocol has no
knowledge about which players are currently running it. Proof-of-work (PoW)
protocols such as Bitcoin are typically interpreted as operating in this
setting.

  2. (2)

Dynamically available setting. At each moment in time, the protocol is aware
of a dynamically evolving list of identifiers (e.g., public keys that
currently have stake committed in a designated staking contract). Importantly,
the evolution of this list can be a function of the protocol’s execution, and
different players may have different views of this list (depending on the
messages they have received thus far). Membership in this list is a necessary
condition for participating in the protocol at that time. Proof-of-stake (PoS)
longest-chain protocols such as Ouroboros (Kiayias et al., 2017) and Snow
White (Daian et al., 2019) are typically interpreted as operating in this
setting.

  3. (3)

Quasi-permissionless setting. Membership in the dynamically evolving list of
identifiers is also a sufficient condition for current participation in the
protocol. That is, every identifier in the list controlled by an honest player
is assumed to be running the protocol (correctly) at that time. Proof-of-stake
PBFT-style protocols such as Algorand are typically interpreted as operating
in this setting.333We use the term “PBFT-style protocol” informally to mean a
consensus protocol that, like PBFT (Liskov and Castro, 1999) and many other
protocols, proceeds via a series of voting stages and guarantees safety via
some form of quorum certificates. Certain proof-of-work protocols such as
Byzcoin (Kokoris Kogias et al., 2016), Hybrid (Pass and Shi, 2016) and Solida
(Abraham et al., 2016) also operate in this setting (and, unlike Bitcoin, do
not function as intended in the fully permissionless setting).

  4. (4)

Permissioned setting. The list of identifiers is fixed at the time of the
protocol’s deployment, with one identifier per participant and with no
dependence on the protocol’s execution. At each moment in time, membership in
this list is necessary and sufficient for current participation in the
protocol. Tendermint is a canonical example of a blockchain protocol that is
designed for the permissioned setting.444Tendermint Core is a permissioned
protocol (see https://docs.tendermint.com/v0.34/tendermint-
core/validators.html): “Validators are expected to be online, and the set of
validators is permissioned/curated by some external process. Proof-of-stake is
not required, but can be implemented on top of Tendermint consensus.”
Permissionless blockchain protocols based on the Tendermint protocol (such as
Cosmos (Kwon and Buchman, 2019)) must also define a sybil-resistant way of
periodically choosing validators (e.g., via a proof-of-stake approach along
the lines of the protocol described in Section 15).

Setting | Protocol’s Knowledge of Current Participants | Canonical Protocol
---|---|---
Fully permissionless | None | Bitcoin
Dynamically available | Subset of the currently known ID list | Ouroboros
Quasi-permissionless | All of the currently known ID list | Algorand
Permissioned | All of the a priori fixed ID list | Tendermint
Table 1. A hierarchy of four settings, ordered according to “degree of
permissionlessness.” The results in this paper demonstrate that the four
settings are mathematically distinct.

The hierarchy is formally defined in Sections 3–9. Our results demonstrate
that the four levels of this hierarchy are mathematically distinct (see
Section 1.3 and Tables 2–3). The first three levels can be viewed as
explicitly parameterizing the player inactivity challenge of permissionless
consensus. The sybil challenge is present in all three of these settings, and
is addressed by a protocol through the use of “resources” such as hashrate or
stake. The unknown players challenge is also fully present in each, although
stronger assumptions on player activity effectively provide more knowledge to
a protocol about the set of (relevant) players; for example, in the quasi-
permissionless setting, a protocol can regard the “current player set” as the
players that control the identifiers possessing a non-zero amount of an on-
chain resource such as stake.

With the definitions of these settings in place, we can then colloquially
speak about the “permissionlessness of a blockchain protocol,” meaning the
most permissionless setting in which the protocol satisfies desired properties
such as safety and liveness (under appropriate assumptions, for example on the
combined power of Byzantine players and on message delays). For example, the
same way the term “asynchronous protocol” might refer to a protocol that
functions as intended even in the asynchronous model, we could describe
Bitcoin as a “fully permissionless protocol,” and similarly for Ouroboros (a
“dynamically available protocol”) and Algorand (a “quasi-permissionless
protocol”).555Appendix B classifies several more blockchain protocols
according to this hierarchy. In particular, the Ethereum protocol proves the
point that a fixed blockchain protocol can be fruitfully analyzed (and possess
different sets of non-trivial guarantees) in different levels of our
hierarchy. In this way, our framework makes precise the common intuition that
proof-of-stake protocols are typically “more permissioned” than proof-of-work
protocols (dynamically available or quasi-permissionless, but not fully
permissionless) but also “more permissionless” than traditional (permissioned)
consensus protocols.666One commonly expressed viewpoint is that proof-of-stake
protocols are “automatically permissioned,” on the grounds that you cannot
participate unless someone agrees to give or sell you some of the protocol’s
native currency. We disagree with this viewpoint, on two grounds. First, from
a pragmatic perspective, the prospect of being unable to acquire enough ETH
(say) from an exchange like Coinbase or Uniswap to become a (proof-of-stake)
Ethereum validator is arguably as far-fetched as being unable to acquire
enough ASICs to participate meaningfully in the (proof-of-work) Bitcoin
protocol. Second, from a mathematical perspective, the current participants of
a proof-of-stake protocol generally depend on the protocol’s execution—a
surprisingly subtle issue, as we’ll explore in Section 11—while the
participants of a permissioned protocol are fixed once and for all. Theorem
11.1 shows that this distinction materially changes the conditions under which
consensus is achievable.

###  1.3. Five Representative Results

We next highlight informal statements of five of our results that illustrate
the flexibility of our analysis framework for protocols that operate in one of
the settings described in Section 1.2; see also Tables 2 and 3. The undefined
terms in the statements below are explained in Section 1.4 or in Sections
3–10. See Section 2.4 for a comparison of our results to those in previous
works.

Theorem 6.1. In the fully permissionless, authenticated, and synchronous
setting, every deterministic protocol for solving Byzantine agreement has an
infinite execution, even when Byzantine players control only an arbitrarily
small (but non-zero) fraction of the active players’ resources at each
timeslot and deviate from honest behavior only by delaying message
dissemination (or crashing).

Theorem 6.1 can be viewed as an analog of the FLP impossibility theorem
(Fischer et al., 1985), which states a similar conclusion for permissioned
protocols in the asynchronous setting. In this sense, the fully permissionless
(and synchronous) setting poses as great a challenge as the asynchronous (and
permissioned) setting. Theorem 6.1, coupled with a recent result of Losa and
Gafni (Losa and Gafni, 2023) (see Theorem 7.1 and Appendix C), formally
separates the fully permissionless and dynamically available settings.

Theorem 7.2. In the dynamically available, authenticated, and partially
synchronous setting, no protocol can solve the Byzantine agreement problem
with high probability, even if there are no Byzantine players at all.

Theorem 7.2 can be viewed as a CAP-type result, stemming from the ambiguity
between waning participation (a challenge of the dynamically available
setting) and unexpectedly long message delays (a challenge of the partially
synchronous setting).

Theorem 7.4. In the dynamically available, authenticated, and synchronous
setting, no optimistically responsive state machine replication protocol
guarantees consistency and liveness, even when there are no Byzantine players
at all.

Informally, “optimistic responsiveness” strengthens liveness by requiring that
the speed of transaction confirmation depend only on the realized message
delays (as opposed to on an assumed worst-case bound on message delays).
Theorem 7.4 shows that this performance goal is fundamentally at odds with the
unpredictable inactivity of players in the dynamically available setting.

Theorem 9.1. In the quasi-permissionless, authenticated, and partially
synchronous setting, there exists a deterministic and optimistically
responsive proof-of-stake protocol that solves the state machine replication
problem (and hence also the Byzantine agreement problem), provided Byzantine
players always control less than one-third of the total stake.

Theorem 9.1, together with either Theorem 7.2 or 7.4, proves that the
dynamically available setting is strictly more challenging than the quasi-
permissionless setting.

As an aside, Theorem 9.1 requires the (standard) assumption that the confirmed
transactions always allocate Byzantine players less than a bounded fraction of
the stake. Theorems 11.1 and 11.2 provide possibility and impossibility
results under relaxed assumptions that concern only the transactions that have
been sent (as opposed to the transactions that have been confirmed). In
particular, Theorem 11.1 provides a formal separation between the quasi-
permissionless and permissioned settings.

Setting | prob. BA | det. BA (delays) | det. BA | acct. SMR | opt. resp. SMR
---|---|---|---|---|---
FP (pos.) |  $<\tfrac{1}{2}$ (Garay et al., 2018) | 0 (trivial) | 0 (trivial) | N/A | N/A
FP (imp.) |  $\geq\tfrac{1}{2}$ (folklore) |  $>0$ (Thm. 6.1) |  $>0$ (Thm. 6.1) |  no (Neu et al., 2022) |  no (Thm. 7.4)
DA (pos.) |  $<\tfrac{1}{2}$ (Garay et al., 2018) |  $<\tfrac{1}{2}$ (Losa and Gafni, 2023) |  $<\tfrac{1}{2}$? (conjecture) | N/A | N/A
DA (imp.) |  $\geq\tfrac{1}{2}$ (folklore) |  $\geq\tfrac{1}{2}$ (folklore) |  $\geq\tfrac{1}{2}$ (folklore) |  no (Neu et al., 2022) |  no (Thm. 7.4)
QP (pos.) |  $<\tfrac{1}{2}$ (Dolev and Strong, 1983) |  $<\tfrac{1}{2}$ (Dolev and Strong, 1983) |  $<\tfrac{1}{2}$ (Dolev and Strong, 1983) |  yes (Thm. 9.1) |  yes (Thm. 9.1)
QP (imp.) |  $\geq\tfrac{1}{2}$ (folklore) |  $\geq\tfrac{1}{2}$ (folklore) |  $\geq\tfrac{1}{2}$ (folklore) | N/A | N/A
Table 2. Possibility (pos.) and impossibility (imp.) results in the synchronous setting. “FP” refers to the fully permissionless setting (with resource restrictions) defined in Sections 3–6; “DA” refers to the dynamically available setting defined in Section 7; and “QP” refers to the quasi-permissionless setting (with reactive resources) defined in Sections 8 and 9. “Det. BA” refers to the Byzantine agreement problem defined in Section 3.5, and “prob. BA” to its probabilistic version defined in Section 6.2. “Det. BA (delays)” refers to a version of the Byzantine agreement problem in which faulty players can deviate from honest behavior only by delaying the dissemination of messages (or crashing). “Acct. SMR” and “opt. resp. SMR” concern the existence of state machine replication protocols that satisfy, respectively, accountability (in the sense defined in Section 7.4) and optimistic responsiveness (in the sense defined in Section 7.5). The numbers in the second, third, and fourth columns refer to the fraction of resources controlled by Byzantine players. Setting | prob. BA | det. BA (delays) | det. BA | acct. SMR | opt. resp. SMR
---|---|---|---|---|---
FP (pos.) | N/A | N/A | N/A | N/A | N/A
FP (imp.) |  $\geq 0$ (Thm. 7.2) |  $\geq 0$ (Thm. 7.2) |  $\geq 0$ (Thm. 7.2) |  no (Neu et al., 2022) |  no (Thm. 7.4)
DA (pos.) | N/A | N/A | N/A | N/A | N/A
DA (imp.) |  $\geq 0$ (Thm. 7.2) |  $\geq 0$ (Thm. 7.2) |  $\geq 0$ (Thm. 7.2) |  no (Neu et al., 2022) |  no (Thm. 7.4)
QP (pos.) | $<\tfrac{1}{3}$ | $<\tfrac{1}{3}$ | $<\tfrac{1}{3}$ | yes | yes
|  (Thm. 9.1 for SMR) |  (Thm. 9.1 for SMR) |  (Thm. 9.1 for SMR) |  (Thm. 9.1) |  (Thm. 9.1)
QP (imp.) |  $\geq\tfrac{1}{3}$ (Dwork et al., 1988) |  $\geq\tfrac{1}{3}$ (Dwork et al., 1988) |  $\geq\tfrac{1}{3}$ (Dwork et al., 1988) | N/A | N/A
Table 3. Possibility and impossibility results in the partially synchronous
setting. Abbreviations are defined in the caption of Table 2. The positive
results for the QP setting all follow from Theorem 9.1, which provides an SMR
protocol that uses only reactive resources and achieves the stated properties
(and which can be used to solve BA).

Theorem 10.1. In the quasi-permissionless, authenticated, and synchronous
setting, every proof-of-stake protocol that uses only time-malleable
cryptographic primitives is vulnerable to long-range attacks.

Informally, a “long-range attack” is one in which a Byzantine player violates
the security of a blockchain protocol by acquiring old private keys (e.g.,
from players for whom they no longer have any value) and using them to create
an alternative blockchain history. Informally, a time malleable cryptographic
primitive is one that can be evaluated quickly (unlike, say, a verifiable
delay function) and whose output does not depend on the time of evaluation
(unlike, say, ephemeral keys).

###  1.4. Main Ingredients of the Analysis Framework

Making the informal statements in Section 1.3 precise requires a formal model,
both of the design space of possible protocols and of the assumptions imposed
on the setting. This section is meant to give the reader a quick sense of our
model and how it can be used to formalize the specific results highlighted in
Section 1.3.

  * •

To model the unknown players challenge, we allow an unknown-to-the-protocol
player set of unbounded size.

  * •

To model the sybil challenge, we allow each player to control an unbounded
number of unknown identifiers (e.g., public keys).

  * •

To model the player inactivity challenge, we allow each player to be “active”
(participating in the protocol) or “inactive” (not participating) at any given
timeslot.

  * •

At each timeslot, an (active) player can disseminate an arbitrary finite set
of messages.777We could alternatively take an approach such as that in
Khanchandani and Wattenhoffer (Khanchandani and Wattenhofer, 2021), which
allows for point-to-point communication between players once their addresses
are known; all of this paper’s results would remain the same, with only minor
changes to the proofs. The communication model considered here is chosen to
reflect a permissionless setting, in which players cannot be expected to know
how to reach specific other players and instead rely on a gossip protocol for
message dissemination. All other active players eventually hear all such
messages, possibly after a delay. The assumptions of a setting include
restrictions on the possible message delays. In this paper, we consider only
two standard restrictions on message delays, the synchronous and partially
synchronous settings.

  * •

As is common in distributed computing, we model a player and its behavior via
a state diagram. A protocol is then defined by the state diagram of an honest
player, and the behavior of a Byzantine player is defined by an arbitrary
state diagram. Each timeslot, each player makes a state transition, which
dictates the new state and the messages disseminated by the player at that
timeslot. The state transition is a function of the player’s current state and
the new information it learns in that timeslot (messages from other players
and, as we’ll see below, responses from “oracles”). This model is purely
information-theoretic, with no computational constraints imposed on honest or
Byzantine players (other than the inability to simulate oracles, as described
below).

  * •

One consequence of allowing computationally unbounded players is that any
cryptographic primitives that might be used by a protocol must be incorporated
outside of the state diagram in an idealized form; we use a notion of
“oracles” for this purpose. By definition, no player (honest or Byzantine) can
compute an oracle output without directly querying the oracle (or being told
the answer by some other player that has already queried it).

For example, the “time malleable cryptographic primitives” mentioned in the
final result highlighted in Section 1.3 translate formally in our model to
oracles that respond to queries immediately (in the same timeslot as the
query) with an answer that is independent of the current timeslot.

  * •

To operate in a permissionless setting in a sybil-resistant way, blockchain
protocols must restrict, implicitly or explicitly, the allowable actions of a
player as a function of how much of some scarce “resource” the player owns.
(Proposition 3.1 in Section 3.5 makes this assertion precise.) The two most
canonical examples of such resources are hashrate (for proof-of-work
protocols) and in-escrow cryptocurrency (for proof-of-stake protocols). These
two examples are fundamentally different: the latter is “on-chain” and
publicly known (to the protocol and all the participating players), while the
former is “external,” meaning private and not directly observable (by the
protocol or by other players). In our model, the description of a protocol
includes the list of resources that its behavior depends upon, and a
classification of each resource as “on-chain” or “external.”

  * •

We use a specific type of oracle (a “permitter”) to model the restrictions
imposed on behavior by an external resource.888Restrictions imposed by on-
chain resources like stake can be enforced by honest players without aid of an
oracle. For example, if the current (publicly observable) stake distribution
determines a public key responsible for proposing a block in the current
round, honest players can simply ignore any proposals for the round that do
not include an appropriate signature. A permitter is an oracle whose response
can depend on the amount of the external resource that is controlled by the
querying player. For example, one way to model proof-of-work in a protocol
like Bitcoin is with a permitter that, when queried by a player with current
resource level $b$, returns the smallest of $b$ 256-bit strings drawn
independently and uniformly at random.

  * •

The current distribution of an on-chain resource like stake depends on the
execution-thus-far of the blockchain protocol. (Whereas the evolution of the
distribution of an external resource like hashrate can be reasonably modeled
as a process independent of the protocol’s operation.) Thus, discussing on-
chain resources requires a formal definition of an “environment” that issues
“transactions” to players (which may, for example, update the resource
distribution). Further, the description of a protocol that depends on on-chain
resources must include a “confirmation rule” (which specifies which
transactions an honest player should regard as executed, given the messages
and oracle responses received by the player thus far) and a “resource update
rule” (which specifies how the execution of a transaction affects the
distribution of the relevant resources).

  * •

This completes the high-level description of our model for the fully
permissionless setting. The first two results in Section 1.3 demonstrate the
difficulty of operating in this setting: deterministic consensus is impossible
even in the synchronous setting, and even probabilistic consensus is
impossible in the partially synchronous setting. (A protocol like Bitcoin
operates in the fully permissionless setting, but it enjoys consistency and
liveness guarantees only in the synchronous setting, and only with high
probability.)

  * •

The dynamically available and quasi-permissionless settings impose additional
assumptions on the correlation between honest players’ periods of activity and
their resource balances. (Recall that each player can be active or inactive at
each timeslot.) For example, consider a proof-of-stake protocol that uses a
single on-chain resource that tracks how much cryptocurrency each player has
locked up in escrow in a designated staking contract. The dynamically
available setting makes the minimal assumption that, at each timeslot, among
the honest players that control a non-zero amount of the on-chain resource, at
least one is active.

  * •

A typical PBFT-style protocol based on weighted super-majority voting could
stall in the dynamically available setting, even if on-chain resources are
controlled entirely by honest players, by failing to assemble any quorum
certificates due to unexpectedly low participation. The quasi-permissionless
setting imposes the stronger assumption that, at every timeslot, every honest
player with a non-zero resource balance—e.g., every honest player with stake
locked up at that time—is active. (The definition of the quasi-permissionless
setting can also be extended to on-chain resources beyond stake; see Section 9
for details.)

###  1.5. Possibility vs. Impossibility Results

The primary focus of this paper is impossibility results (Proposition 3.1 and
Theorems 6.1, 7.2, 7.3, 7.4, 10.1, and 11.1), and our model is, accordingly,
optimized to make such results as strong as possible. For example:

  * •

We allow protocols to specify arbitrary oracles, without regard to their
realizability.

  * •

We impose no restrictions on the computational or communication complexity of
a protocol.

  * •

We assume that newly active honest players learn about all previously
disseminated messages (perhaps after a delay).

All of our impossibility results hold even after granting these powers to
protocols and the honest players that run them.

By the same token, any possibility result proved in our model should be
accompanied by a discussion of the extent to which its generosity has been
abused. The two main possibility results in this paper (Theorems 9.1 and 11.2)
rely only on relatively standard assumptions: that secure digital signature
schemes exist, that players can carry out a polynomial amount of computation
and communication, and that newly active honest players can somehow learn
about the blocks that have already been finalized.

###  1.6. Organization of this Paper

The following section summaries are meant to help the reader navigate the rest
of the paper.

  * •

Section 2 provides an overview of related work. Sections 2.1–2.3 and Section
2.4 compare our model and results, respectively, to those in the existing
literature.

  * •

Section 3 formally defines many of the basic ingredients of the fully
permissionless setting listed in Section 1.4, up to and including oracles.
Section 3.5 defines the Byzantine agreement problem and (in Proposition 3.1)
formally shows that it is unsolvable in the fully permissionless setting
without some notion of “resource restrictions” to diffuse the sybil challenge.

  * •

Section 4 formally defines external resources and permitter oracles (in
Section 4.1), and illustrates how they can model the Bitcoin protocol (in
Section 4.2).

  * •

Section 5 formally defines blockchain protocols, transactions, environments,
stake, and confirmation rules (in Section 5.1), as well as consistency and
liveness for blockchain protocols (in Section 5.2).

  * •

Section 6 considers the fully permissionless setting with external resource
restrictions. Section 6.1 gives the formal statement of the first result
described in Section 1.3 (Theorem 6.1), which rules out deterministic
protocols for the Byzantine agreement problem, even in the synchronous
setting. (This statement is proved in Section 12.) Section 6.2 introduces
terminology for reasoning about probabilistic protocols.

  * •

Section 7 concerns the dynamically available setting. Section 7.1 formally
defines the setting; Section 7.2 uses a result of Losa and Gafni (Losa and
Gafni, 2023) to separate the fully permissionless and dynamically available
settings (Theorem 7.1); Section 7.3 formally states the second result
highlighted in Section 1.3 (Theorem 7.2, which is proved in Section 13);
Section 7.4 notes that a result of Neu, Tas, and Tse (Neu et al., 2022) rules
out accountability in the dynamically available setting (Theorem 7.3); and
Section 7.5 formally states the third result highlighted in Section 1.3
(Theorem 7.4, which is proved in Section 14).

  * •

Section 8 defines a version of the quasi-permissionless setting specifically
for proof-of-stake protocols (Section 8.1) and, as a generalization of stake,
the notion of reactive protocol-defined resources (Sections 8.2–8.3).

  * •

Section 9 formally defines the quasi-permissionless setting with arbitrary on-
chain resources (Section 9.1) and, in Section 9.2, gives the formal statement
of the fourth result described in Section 1.3 (Theorem 9.1, proved in Section
15).

  * •

Section 10 formally defines long-range attacks and proves the last result
highlighted in Section 1.3.

  * •

Section 11 investigates relaxing restrictions on the (execution-dependent)
transactions confirmed by a proof-of-stake protocol to restrictions only on
the transactions issued by the environment. Sections 11.1 and 11.2 focus on
impossibility results, culminating in Theorem 11.1 (which is proved in Section
16). Section 11.3 shows (via Theorem 11.2, proved in Section 15) that the
guarantees of Theorem 9.1 can be recovered under additional natural
assumptions on the environment.

  * •

As noted above, Sections 12–16 provide proofs and additional discussion for
results in Sections 6, 7, 9, and 11.

  * •

Appendix A supplements the proof-of-work discussion in Section 4.2 with a
second application of the permitter formalism in Section 4.1, to proof-of-
space protocols.

  * •

Appendix B supplements Table 1 by describing how a number of other blockchain
protocols fit into the hierarchy of settings described in Section 1.2.

  * •

Appendix C presents, for completeness, a full proof of Theorem 7.1 (adapted
from Losa and Gafni (Losa and Gafni, 2023)).

##  2\. Related work

###  2.1. Previous work on consensus without an a priori fixed and known
player set

The Byzantine agreement problem was introduced by Lamport, Pease, and Shostak
(Pease et al., 1980; Lamport et al., 1982) and has long been a central topic
in distributed computing. Even before the advent of Bitcoin and other
blockchain protocols, a number of papers have studied the problem in models
that do not assume a fixed and known set of players (but without considering
the player inactivity or sybil challenges).

The CUP framework. Several papers, including Alchieri et al. (Alchieri et al.,
2008) and Cavin, Sasson, and Schiper (Cavin et al., 2004), study the CUP
framework (for “Consensus amongst Unknown Participants”). In this model, the
player set is fixed and finite but unknown, with each (always-active and
sybil-free) player aware of, and with authenticated channels to, a subset of
the other players that may increase over time. These works assume a known
bound $f$ on the number (rather than the fraction) of faulty players.

Khanchandani and Wattenhoffer (Khanchandani and Wattenhofer, 2021), motivated
in part by blockchain protocols, consider a variant of the CUP framework that
takes a different approach to “player discovery.” In their model, players can
broadcast messages to all other players (whether known or not) or send
individual messages to players from whom they have previously received
messages. (A Byzantine player is allowed to immediately send individual
messages to any player of its choice). Each (always-active) player has a
unique identifier and can sign messages under that identifier only. The
assumption is now that less than one third of the players are Byzantine.
Khanchandani and Wattenhoffer (Khanchandani and Wattenhofer, 2021) prove that
consensus is possible in this setting with synchronous communication, but
impossible in the partially synchronous model.

Reconfiguration protocols. There is a substantial line of work on “player
reconfiguration protocols,” meaning protocols for which the set of players is
allowed to change mid-execution, as dictated by certain “player-change”
instructions; see Duan and Zhang (Duan and Zhang, 2022) for a recent formal
treatment of this idea, and earlier papers by Lamport, Malkhi, and Zhou
(Lamport et al., 2009) and Ongaro and Ousterhout (Ongaro and Ousterhout, 2014)
(for crash faults) and by Abraham and Malkhi (Abraham and Malkhi, 2016) and
Bessani, Sousa, and Alchieri (Bessani et al., 2014) (for Byzantine faults).
The current players are assumed active and can participate under only one
identifier. The specific case of proof-of-stake PBFT-style protocols in the
quasi-permissionless setting (Section 8.1) can be regarded as player
reconfiguration protocols in which the “player-change” instructions have a
specific form (e.g., stake-transferring transactions) and are issued by an
adversarial environment (subject to restrictions such as those proposed in
Section 11).

Protocols tolerating unknown participants and crash faults. A number of papers
(see (Aguilera, 2004) for a brief summary) consider distributed algorithms
designed for a system in which the number of participants may be unbounded and
unknown, but which evade the sybil challenge by restricting attention to crash
(rather than Byzantine) faults. For example, Gafni and Koutsoupias (Gafni and
Koutsoupias, 1998) consider _uniform protocols_ that operate in a setting in
which each execution has a finite but unknown set of participants. In a
further generalization, Merritt and Taubenfeld (Merritt and Taubenfeld, 2013)
and Aguilera (Aguilera, 2004) consider a setting in which infinitely many
participants may join over time during a single execution (and in which the
set of participants is again unknown).

Further related work. Other works consider settings that differ both from the
classical permissioned setting and from the settings considered in this paper
(but again, without considering the player inactivity or sybil challenges).
For example, Okun (Okun, 2005) considers a setting in which a fixed number of
players communicate by private channels, but might be “port unaware,” meaning
that they are unable to determine from which private channel a message has
arrived. Okun (Okun, 2005) shows that deterministic consensus is not possible
in the absence of a signature scheme when players are port unaware, even in
the synchronous setting. Bocherding (Borcherding, 1996) considers a setting in
which a fixed set of $n$ players communicate by private channels (without the
“port unaware” condition of Okun (Okun, 2005)), and in which a signature
scheme is available. Here, however, each player is unaware of the others’
public keys at the start of the protocol’s execution. In this setting,
Bocherding (Borcherding, 1996) shows that Byzantine agreement is impossible
when at least one-third of the players may be Byzantine (even in the
synchronous model).

###  2.2. Previous work on consensus with intermittently active players

Sleepy consensus. The “sleepy consensus” model of Pass and Shi (Pass and Shi,
2017b) focuses squarely on the player inactivity challenge (but without
addressing the unknown players or sybil challenges). In this model, there is a
fixed and known finite set of players (with no sybils). At each timeslot,
however, an unknown subset of these players may be inactive. Pass and Shi
(Pass and Shi, 2017b) design a Nakamoto-type consensus protocol that is live
and consistent in the synchronous setting provided that, at each timeslot, a
majority of the active players are honest. A number of follow-up works (e.g.
(Momose and Ren, 2022; Malkhi et al., 2022; D’Amato and Zanolini, 2023,
2023a)) present further results for the sleepy consensus model and extensions
of it (without incorporating the unknown players or sybil challenges). Momose
and Ren (Momose and Ren, 2022), for example, extend the classic PBFT-style
approach from static quorum size to dynamic quorum size to give a protocol
with constant latency (i.e., with time-to-confirmation bounded by a constant
factor times the worst-case message delay).

Precursors to the dynamically available setting. There are several works that,
as a byproduct of analyzing the mathematical properties of a specific
blockchain protocol, implicitly define special cases of our dynamically
available setting. For example, Neu, Tas, and Tse (Neu et al., 2021) describe
a protocol that, in the terminology of this paper, satisfies consistency and
liveness in both the synchronous and dynamically available setting and in the
partially synchronous and quasi-permissionless setting (under appropriate
bounds on the resources controlled by Byzantine players). Similarly, the
rigorous analyses of the Snow White (Daian et al., 2019) and Ouroboros
(Kiayias et al., 2017) proof-of-stake longest-chain protocols can be
interpreted as working in the special case of the dynamically available
setting in which there are no external resources, no on-chain resources other
than stake, and, in the terminology of Section 5.1, a $\tfrac{1}{2}$-bounded
adversary.

###  2.3. Previous work on consensus with sybils

Frameworks for analyzing proof-of-work (PoW) protocols. Many of the previous
works on permissionless consensus, such as Garay, Kiayias, and Leonardos
(Garay et al., 2018) and a number of follow-up papers, focus specifically on
the Bitcoin protocol (Nakamoto et al., 2008) and its close relatives. Pass,
Seeman, and shelat (Pass et al., 2016) and Pass and Shi (Pass and Shi, 2017a)
consider more general models of proof-of-work protocols. (Indeed, Pass and Shi
(Pass and Shi, 2017a) explicitly discuss analogs of the unknown players,
player inactivity, and sybil challenges studied here, albeit in a narrower
proof-of-work setting.) This line of work generally uses the UC framework of
Canetti (Canetti, 2001), as opposed to the state diagram (with oracles)
approach taken here, and models proof-of-work using a random-oracle
functionality (which, in the terminology of Section 4.1, plays the role of a
single-use permitter). For example, Pass and Shi (Pass and Shi, 2017a)
describe a model for analyzing proof-of-work protocols with a fixed set of
participants, where the number of participants controlled by the adversary
depends on its hashing power. They show that, if a protocol is unsure of the
number of participants (up to a factor of 2) and must provide availability
whenever the number of participants is at least $n$ and at most $2n$, the
protocol cannot guarantee consistency in the event of a network partition.
More recent papers in this line of work include Garay et al. (Garay et al.,
2020), in which a player’s ability to broadcast is limited by access to a
restricted resource, and Terner (Terner, 2020), in which the model is
reminiscent of that in (Garay et al., 2018) but with all probabilistic
elements of player selection “black-boxed.”

Permitters. The idea of black-boxing the process of participant selection as
an oracle, akin to our notion of permitters (Section 4.1), was also explored
by Abraham and Malkhi (Abraham, 2017). Azouvi et al. (Azouvi et al., 2022),
motivated in part by a preliminary version of this paper (Lewis-Pye and
Roughgarden, 2021), identify precisely how the properties of a permitter
(called a “resource allocator” in (Azouvi et al., 2022)) govern the properties
of a longest-chain blockchain protocol that uses it, and prove possibility and
impossibility results for the construction of permitters with various
properties. The updated notion of a single-use permitter (see Section 4.1) in
this paper, relative to (Lewis-Pye and Roughgarden, 2021), is inspired by
(Azouvi et al., 2022).

Aside: going beyond proof-of-work. There are several reasons why it is
important to study permissionless consensus in a model that, like the one in
this paper, also accommodates protocols that use on-chain resources such as
stake for sybil-resistance. First, with the obvious exception of Bitcoin, most
of the major blockchain protocols deployed today (and most notably Ethereum)
are proof-of-stake protocols. Second, restricting attention to pure proof-of-
work protocols forces other design decisions that rule out still larger swaths
of the protocol design space. For example, there is a formal sense in which
proof-of-work protocols cannot work with PBFT-style quorum certificates (see
Theorem 5.1 of (Lewis-Pye and Roughgarden, 2021b)) and therefore typically
default to a longest-chain rule, while proof-of-stake protocols can (as shown
formally by Theorem 9.1, or informally by a number of major deployed proof-of-
stake protocols). Finally, confining attention to external resources like
hashrate, which evolve independently of a blockchain’s execution, completely
evades the key technical challenges of analyzing protocols with on-chain
resources: resource balances are subjective (that is, a function of the
messages received), and inextricably linked to the blockchain’s execution
(specifically, the confirmed transactions). The results in this paper show
that widening the scope of analysis from proof-of-work protocols to general
blockchain protocols reveals a remarkably rich and nuanced picture (e.g.,
Tables 2 and 3 and Theorem 10.1).

Proof-of-stake longest-chain protocols. As discussed in Section 2.2, in
formally analyzing the Snow White and Ouroboros proof-of-stake longest-chain
protocols, respectively, Daian, Pass, and Shi (Daian et al., 2019) and Kiayias
et al. (Kiayias et al., 2017) implicitly define special cases of our general
framework that accommodate both stake and stake-changing transactions. The
main positive results in (Daian et al., 2019; Kiayias et al., 2017), which
effectively match the consistency and liveness guarantees of the Bitcoin
protocol (Garay et al., 2018) with proof-of-stake protocols, can be viewed as
analogs of our positive results (Theorems 9.1 and 11.2) for the dynamically
available (rather than quasi-permissionless) setting (and with a
$\tfrac{1}{2}$-bounded adversary rather than a $\tfrac{1}{3}$-bounded one).
Consistent with Theorems 7.2–7.4, the positive results in (Daian et al., 2019;
Kiayias et al., 2017) hold only in the synchronous setting, and the protocols
defined in those papers satisfy neither accountability nor optimistic
responsiveness.

Brown-Cohen et al. (Brown-Cohen et al., 2019) describe a model for the
analysis of proof-of-stake longest-chain protocols, with a novel focus on the
incentives faced by the players running the protocol. They do not attempt to
model protocols outside of this class. (Of the major deployed proof-of-stake
blockchain protocols, only Cardano, based on Ouroboros (Kiayias et al., 2017),
is a longest-chain protocol.)

Dembo et al. (Dembo et al., 2020) describe a model for analyzing the
consistency and liveness properties of longest-chain protocols (proof-of-stake
in particular, but also proof-of-work and proof-of-space). Again, the goals of
this paper are more specific and fine-grained than ours here; the main results
in (Dembo et al., 2020) provide a precise analysis of the security properties
of certain canonical longest-chain protocols in the synchronous setting and
with static resource balances.

Ripple, Stellar, and asymmetric trust assumptions. Classical consensus
protocols typically operate with _symmetric_ trust assumptions, meaning that
all honest players operate under the same assumption on the largest-possible
fraction of faulty players. However, a number of papers (e.g. (Damgård et al.,
2007; Cachin and Tackmann, 2019; Cachin and Zanolini, 2021)) have considered
protocols that operate in the permissioned setting, but which allow for
_asymmetric_ trust assumptions. For example, each player could specify which
other players they believe to be honest, and a protocol might then aim to
provide liveness and consistency for players whose assumptions are correct. To
function as intended, such protocols typically require the trust assumptions
of honest players to be strongly aligned. For example, Cachin and Tackmann
(Cachin and Tackmann, 2019) describe a protocol that achieves a form of
reliable broadcast assuming, among other things, the existence of a “guild,”
meaning a large group of influential and mutually trustful players that all
make correct trust assumptions. Cachin and Zanolini (Cachin and Zanolini,
2021) extend these methods to define a protocol that solves the Byzantine
agreement problem under similar conditions.

Developing this idea further, a number of works (Schwartz et al., 2014;
Amores-Sesar et al., 2020; Mazieres, 2015; García-Pérez and Gotsman, 2018;
Losa et al., 2019; Cachin et al., 2022), including the Stellar and Ripple
white papers, have explored asymmetric trust assumptions beyond the
permissioned setting. At a high level, the basic idea is to “outsource” the
problem of sybil-resistance to the protocol participants and then deliver
liveness and consistency in the event that participants (somehow) make good
choices as to whom to trust. Mirroring the permissioned setting, positive
results require strongly aligned trust assumptions (see e.g. (Amores-Sesar et
al., 2020; Cachin and Tackmann, 2019)). Protocols based on this approach would
not qualify as “permissionless” in the senses defined in this paper, as in our
model players have no knowledge about each other (beyond the disseminated
messages that have been received) and thus the blockchain protocol itself must
shoulder the burden of sybil-resistance.

###  2.4. Comparison with existing results

Some of the results in this paper have precursors in the existing literature.
We discuss each of our results in turn.

Proposition 3.1. Proposition 3.1 demonstrates that the sybil challenge cannot
be addressed without supplementing the protocol design space with some notion
of “resources” to prevent a Byzantine player from simulating an arbitrarily
large number of honest players. This result is similar in spirit to Theorem 1
in Pass and Shi (Pass and Shi, 2017a). The proof given here must accommodate
the full generality of our framework (e.g., arbitrary oracles), however. It is
also, in our view, substantially simpler than the proof in (Pass and Shi,
2017a).

Theorem 6.1. Theorem 6.1 shows that in the fully permissionless,
authenticated, and synchronous setting, every deterministic protocol for
solving Byzantine agreement has an infinite execution in which honest players
never terminate, even when Byzantine players control only an arbitrarily small
(but non-zero) fraction of the active players’ resources at each timeslot. The
theorem holds even when faulty players can deviate from honest behavior only
by crashing or delaying message dissemination. Pu, Alvisi, and Eyal (Pu et
al., 2022), motivated in part by a preliminary version of this paper (Lewis-
Pye and Roughgarden, 2021), show the existence of a protocol that guarantees
deterministic agreement and termination with probability 1 under general
omission failures. The two results do not contradict each other because the
protocol of Pu, Alvisi, and Eyal is probabilistic and only guarantees
termination with probability 1, i.e., there remain infinite executions in
which honest players never terminate.

The proof of Theorem 6.1 given in Section 12 is similar in form to the proof
of Moses and Rajsbaum (Moses and Rajsbaum, 2002) that deterministic consensus
is not possible in the synchronous and permissioned setting in the case of a
mobile adversary (with both proofs being bivalency arguments in the style of
Fischer, Lynch, and Paterson (Fischer et al., 1985)).999See Attiya and Ellen
(Attiya and Ellen, 2022, Chapter 7) for an introduction to valency arguments.
We note that impossibility results for the permissioned setting with a mobile
adversary (but without resource restrictions) or the asynchronous permissioned
setting do not generally carry over to the fully permissionless setting (with
resource restrictions and synchronous communication); see also footnotes 33
and 35 in Section 6.2. We leave it for future work to determine whether
Theorem 6.1 can alternatively be established through some kind of reduction to
an already-known impossibility result in a different model (perhaps by
building on the ideas in (Moses and Rajsbaum, 2002; Santoro and Widmayer,
2007; Gafni and Losa, 2023)).

Theorems 7.1–7.4. The four results stated in Section 7 map out what is
possible and impossible in the dynamically available setting. Theorem 7.1 is a
positive result showing that Theorem 6.1 does not hold in this setting—thus
proving a formal separation between the fully permissionless and dynamically
available settings—and it is essentially due to Losa and Gafni (Losa and
Gafni, 2023). Theorem 7.3, starting that accountability is impossible in the
dynamically available setting, is a result of Neu, Tas, and Tse (Neu et al.,
2022).

Theorem 7.2 is new to this paper; its proof resembles that of the “CAP
Theorem” (Brewer, 2000; Gilbert and Lynch, 2002) and other results in the same
lineage. For example, as mentioned in Section 2.3, Pass and Shi (Pass and Shi,
2017a) prove an analogous result specifically for proof-of-work protocols with
a fixed set of participants. Khanchandani and Wattenhoffer (Khanchandani and
Wattenhofer, 2021) prove an analogous result in their variant of the CUP
framework described in Section 2.1.

Theorem 7.4 is, to the best of our knowledge, the first result that identifies
a fundamental conflict between dynamic availability and optimistic
responsiveness. The closest analog is a result of Pass and Shi (Pass and Shi,
2018) that concerns their stronger notion of _responsiveness_ , which insists
that confirmation times scale with the realized message delays even when there
are (a limited number of) Byzantine players. Pass and Shi (Pass and Shi, 2018)
show that, even in a synchronous, authenticated, and permissioned setting, and
even if one augments that setting with resources, responsive state machine
replication protocols cannot tolerate a $\rho$-bounded adversary for any
$\rho\geq 1/3$. To maximize the strength of our impossibility result in
Theorem 7.4, our definition of optimistic responsiveness in Section 7.5 is
specified to be as weak as possible. Theorem 7.4 holds even for $0$-bounded
adversaries, and as such cannot extend to the permissioned (or even quasi-
permissionless) setting; the result is fundamentally driven by the player
inactivity challenge present in the dynamically available setting.

Theorem 9.1. Theorems 9.1 and 11.2 formally establish that proof-of-stake
protocols can be (deterministic and) live and consistent in the partially
synchronous setting. A result along the lines of Theorem 9.1 is strongly
hinted at in several previous works. For example, the analysis of the Algorand
protocol by Chen and Micali (Chen and Micali, 2016) provides a rigorous proof
of the protocol’s liveness and consistency properties in the synchronous
setting, but does not deal formally with partial synchrony. The analysis of
the Algorand protocol in Chen et al. (Chen et al., 2018), meanwhile,
establishes liveness and consistency in the partially synchronous setting, but
only for a permissioned version of the protocol. Chen et al. (Chen et al.,
2018) suggest, without formal analysis, that in a permissionless setting, one
can implement a proof-of-stake version of their permissioned protocol. A
recent paper by Benhamouda et al. (Benhamouda et al., 2023) gives a
probabilistic analysis of consistency and liveness for the presently deployed
instantiation of the Algorand protocol (which differs substantially from the
protocol presented in the older papers cited above), but does not consider
changing players. Similar comments apply to the analysis of the Casper
protocol by Buterin and Griffith (Buterin and Griffith, 2017), which formally
treats a permissioned version of the protocol and, without any further formal
analysis, suggests how it could be extended to a proof-of-stake protocol
suitable for a permissionless setting.

Theorems 9.1 and 11.2 also formally establish the existence of a proof-of-
stake protocol for the authenticated and partially synchronous setting that is
$(1/3,1)$-accountable (as defined in Section 7.4) and optimistically
responsive (as defined in Section 7.5). A number of papers (e.g., (Sheng et
al., 2021; Ranchal-Pedrosa and Gramoli, 2020; Civit et al., 2021; Buterin and
Griffith, 2017; Shamis et al., 2022)) have previously established
accountability for permissioned protocols. Similarly, several variations of
optimistic responsiveness have been achieved by permissioned protocols (e.g.,
(Yin et al., 2019; Liskov and Castro, 1999; Shrestha et al., 2020)).

Theorem 10.1. In (Daian et al., 2019), Daian, Pass, and Shi assert that, in
the absence of “additional trust assumptions,” proof-of-stake protocols are
vulnerable to long-range attacks. As shown by the Algorand protocol, however,
cryptographic primitives such as ephemeral keys can be used to prevent long-
range attacks. Theorem 10.1 formally establishes precisely what form of
cryptographic primitive is required to avoid vulnerability to long-range
attacks.

In more detail, Theorem 10.1 shows that in the quasi-permissionless,
authenticated, and synchronous setting, every proof-of-stake protocol that
uses only time-malleable cryptographic primitives is vulnerable to long-range
attacks (see Section 10 for the definition of time-malleable oracles). This
result holds even if the adversary obtains stake only through posterior
corruption, meaning the acquisition of the private keys of players who no
longer own stake. Some previous works (Chen and Micali, 2016; Badertscher et
al., 2018) can be interpreted as exploring, in our terminology, how non-time-
malleable oracles might be used to prevent long-range attacks. In a different
but related direction, Tas et al. (Tas et al., 2023, 2022) show that
_slashable-safety_ and liveness cannot be achieved for proof-of-stake
protocols (even those with non-time-malleable oracles) if the adversary can,
even without any posterior corruption, acquire a majority of the stake (and
without extra trust assumptions such as those considered in (Buterin ., 2014;
Daian et al., 2019)). Tas et al. (Tas et al., 2023, 2022) also show how long-
range attacks on proof-of-stake protocols can be mitigated by using a system
of checkpoints recorded in the Bitcoin blockchain (the security of which is,
in effect, an extra trust assumption).

Finally, Azouvi, Danezis, and Nikolaenko (Azouvi et al., 2020) describe an
approach to mitigating long-range attacks on proof-of-stake protocols by
having clients sign off on checkpoints, where a “client” refers to an entity
that does not participate directly in a blockchain protocol but may monitor
and submit transactions to the protocol. The motivation for this idea is that
the potentially large set of clients may be less vulnerable to widespread
posterior corruption than the (presumably smaller) set of validators.

Theorems 11.1 and 11.2. All existing analyses of the consistency and liveness
properties of proof-of-stake protocols in the partially synchronous setting
have restricted attention to protocol executions in which Byzantine players
always control less than a certain fraction of the total stake. In a proof-of-
stake protocol, however, the amount of stake controlled by Byzantine
players——and, thus, whether an execution meets the hypothesis of such a
guarantee—can depend on the realized network delays, the strategies of the
Byzantine players, and even the decisions of the protocol itself. Theorems
11.1 and 11.2 are, to our knowledge, the first results in the literature to
address this issue by investigating what can be achieved in the partially
synchronous setting under assumptions only on the environment (e.g., on the
set of transactions issued at each timeslot) rather than on the specific
execution.

##  3\. The fully permissionless setting without resource restrictions

This section describes a basic version of our model, without any notion of
“resources” (which will be introduced in Section 4). The most important
concept in this section is “oracles,” which we use to model various
cryptographic primitives. Some of the impossibility results presented in this
paper hold independent of the assumed cryptographic primitives, while others
depend on which cryptographic primitives are assumed to exist.

###  3.1. The set of players and the means of communication

The set of players. We consider a potentially infinite set of players
$\mathcal{P}$. Each player $p\in\mathcal{P}$ is allocated a non-empty and
potentially infinite set of _identifiers_ $\mathtt{id}(p)$. One can think of
$\mathtt{id}(p)$ as an arbitrarily large pre-generated set of public keys for
which $p$ knows the corresponding private key; a player $p$ can use its
identifiers to create an arbitrarily large number of sybils. Identifier sets
are disjoint, meaning $\mathtt{id}(p)\cap\mathtt{id}(p^{\prime})=\emptyset$
when $p\neq p^{\prime}$; intuitively, no player knows the private keys that
are held by other players.

Permissionless entry and exit. Time is divided into discrete timeslots
$t=1,2,\dots,d$, where $d\in\mathbb{N}_{\geq 1}\cup\\{\infty\\}$ is referred
to as the _duration_. Each player may or may not be _active_ at each timeslot.
A _player allocation_ is a function specifying $\mathtt{id}(p)$ for each
$p\in\mathcal{P}$ and the timeslots at which each player is active. Because
protocols generally require _some_ active players to achieve any non-trivial
functionality, unless explicitly stated otherwise we assume that a non-zero
but finite number of players is active at each timeslot $\leq d$.

Inputs. Each player is given a finite set of _inputs_ , which capture its
knowledge at the beginning of the execution of a protocol. If a variable is
specified as one of $p$’s inputs, we refer to it as _determined for_ $p$,
otherwise it is _undetermined for_ $p$. If a variable is
determined/undetermined for all $p$ then we refer to it as
_determined/undetermined_. For example, to model a permissionless environment
with sybils, we generally assume that the player set and the player allocation
are undetermined. The duration $d$, on the other hand, we typically treat as
determined.

Message sending. At each timeslot, each active player may _disseminate_ a
finite set of messages (each of finite length) to the other players, and will
receive a (possibly empty) multiset of messages that have been disseminated by
other players at previous timeslots. (Inactive players do not disseminate or
receive any messages.) Each time $p$ disseminates a message at some timeslot,
we wish to stipulate that it is received at most once by each of the other
players. Formally, for each dissemination of the message $m$, i.e., for each
triple $(p,m,t)$ such that $p$ disseminates $m$ at $t$, and for each
$p^{\prime}\neq p$, we allow that $p^{\prime}$ may _receive that
dissemination_ at a single timeslot $t^{\prime}>t$. If $p^{\prime}$ receives
$k$ disseminations of $m$ at $t^{\prime}$, then $k$ is the multiplicity with
which $m$ appears in the multiset of messages received by $p^{\prime}$ at
$t^{\prime}$. If $p$ disseminates $m$ at $t$, then it is convenient to suppose
that $p$ regards that dissemination as received (by itself) at timeslot $t+1$
(if active).

We consider two of the most common models of message reliability, the
synchronous and partially synchronous models. These models have to be adapted,
however, to deal with the fact that players may not be active at all
timeslots.101010As discussed in Section 1.5, the fact that honest active
players eventually receive all messages disseminated in the past (even after a
long period of inactivity) only makes our impossibility results stronger. In
the protocol used to prove our possibility results (Theorems 9.1 and 11.2),
newly active players need to know only the set of already-finalized blocks.

Synchronous model. There exists some determined $\Delta\in\mathbb{N}_{>0}$
such that if $p$ disseminates $m$ at $t$, and if $p^{\prime}\neq p$ is active
at $t^{\prime}\geq t+\Delta$, then $p^{\prime}$ receives that dissemination at
a timeslot $\leq t^{\prime}$.111111We typically assume that $\Delta\geq 2$.
(With our dissemination model, if $\Delta=1$, active honest players would
automatically proceed in lockstep, with each receiving the same set of
disseminated messages in each timeslot.)

Partially synchronous model. There exists some determined
$\Delta\in\mathbb{N}_{>0}$, and some undetermined timeslot called GST (with
GST$\leq d$), such that if $p$ disseminates $m$ at $t$, and if $p^{\prime}\neq
p$ is active at $t^{\prime}\geq\text{max}\\{\text{GST},t\\}+\Delta$, then
$p^{\prime}$ receives that dissemination at a timeslot $\leq t^{\prime}$.

Timing rules. It is useful to consider the notion of a _timing rule_ , which
specifies how long messages take to be received by each player after they are
disseminated. Formally, a timing rule is a partial function $T$ that maps
tuples of the form $(p,p^{\prime},m,t)$ to timeslots. An execution of the
protocol follows the timing rule $T$ if the following holds for all players
$p$ and $p^{\prime}$: We have that $p^{\prime}$ receives $m$ at $t^{\prime}$
if and only if there exists some $p$ and $t<t^{\prime}$ such that $p$
disseminates the message $m$ at $t$ and
$T(p,p^{\prime},m,t)\downarrow=t^{\prime}$.121212Generally, we write
$x\downarrow$ to indicate that the variable $x$ (e.g., the output of a partial
function) is defined, and we write $x\uparrow$ to indicate that $x$ is
undefined. Of course, we restrict attention to timing rules that are
consistent with the communication model (synchronous or partially
synchronous).

###  3.2. Players and oracles

The oracles. The description of a protocol will specify a (possibly empty) set
of _oracles_ $\mathcal{O}=\\{O_{1},\dots,O_{z}\\}$ that are generally used to
capture, within our information-theoretic model, idealized cryptographic
primitives (e.g., VDFs) and (in Section 4) the use of external
resources.131313As discussed in Section 1.5, allowing idealized oracles in
place of concrete implementations only makes our impossibility results
stronger. Our possibility results (Theorems 9.1 and 11.2) rely on only an
idealized version of a standard secure digital signature scheme (as described
in Section 3.3). At each timeslot, each active player may send a set of
_queries_ to each oracle $O_{i}$. Each query is a binary string of finite
length.

If $p$ sends a query $q$ to $O_{i}$ at timeslot $t$, it receives a _response_
to that query from $O_{i}$ at a timeslot $t^{\prime}\geq t$. Unlike message
delays, which are determined by the communication network and therefore
unpredictable, the time at which a querying player receives an oracle response
is determined by the oracle specification. (Intuitively, typical oracle
computations are carried out “locally” by a player.) For some oracles, the
response may be received instantly (i.e., $t^{\prime}=t$). For others, such as
those modeling VDFs, the response may be received at a timeslot later than
$t$. Oracles are “non-adaptive,” in that their response (or distribution over
responses) to a query is independent of any previous queries asked of them.

Oracles in the deterministic model. To prove impossibility results that hold
for all possible sets of oracles, we must be fully precise about the way in
which oracles function. Oracles may be given some inputs from amongst the
determined inputs at the start of the protocol execution (e.g., the duration
$d$). During the protocol execution, they are then sent oracle queries by the
players. In the “deterministic model,” we assume that oracles are
deterministic. This means that an oracle’s inputs at the start of the protocol
execution determine a _response function_ $f$ that specifies, for every
possible query $q$ and timeslot $t$, a response $r$ to $q$ (if sent at $t$ by
some $p$) and a delivery timeslot $t^{\prime}\geq t$ for that response; we
write $f(q,t)=(r,t^{\prime})$. We call the response _undelivered_ until
received by $p$.

Oracles in the probabilistic model. In the “probabilistic model,” each oracle
$O$ specifies, given its inputs, a distribution over response functions. At
the start of the protocol execution, a response function is sampled from the
distribution specified by $O$, and that function then specifies the responses
of the oracle in that protocol execution. (Intuitively, the oracle flips all
its coins “up front.”)

Modeling players as state diagrams. Each player is modeled as a processor
specified by a state diagram, for which the set of states $St$ may be
infinite. A player’s state transition at a given timeslot can depend on the
oracle responses received at that time (in addition to the player’s current
state, the messages received from other players, and the number of the current
timeslot).141414Thus, in effect, players automatically know the number of the
current timeslot (even after waking up from a long period of inactivity); this
modeling choice serves to make our impossibility results as strong as
possible. For our positive results in partial synchrony (Theorems 9.1 and
11.2), where such knowledge arguably goes against the spirit of the setting,
we use a protocol for which the behavior of honest players depends only on the
set of messages received (and not on the number of the current timeslot).

One subtle point, which can be ignored on a first reading, is that some
oracles may respond “instantaneously” (i.e., $f(q,t)=(r,t^{\prime})$ with
$t^{\prime}=t$) and players may wish to query such oracles repeatedly in the
same timeslot. (By contrast, messages disseminated by a player in a timeslot
$t$ cannot arrive at their destinations prior to timeslot $t+1$.) For example,
$p$ may query an oracle that models a signature scheme (perhaps with specific
properties, such as are satisfied by ephemeral keys (Chen and Micali, 2016)),
and then make further queries at the same timeslot depending on the response.

For this reason, we use state diagrams that specify a special subset
$St^{\ast}$ of the set $St$ of all states, indicating the states from which
the player will proceed to the next timeslot without further oracle queries.
At the beginning of the protocol’s execution, a player $p$ begins in an
_initial state_ in $St^{\ast}$, which is determined by $\mathtt{id}(p)$ and by
the other inputs given to $p$. At each timeslot $t$ for which $p$ is active,
$p$ begins in some state $s^{\ast}\in St^{\ast}$ and receives a multiset of
messages $M$. Player $p$ then enters a state $s$ (which may or may not belong
to $St^{\ast}$). In the deterministic model, $s$ is determined by $s^{\ast}$,
$M$, and $t$. In the probabilistic model, $s$ is a random variable with
distribution determined by $s^{\ast}$, $M$, and $t$. Player $p$ then
repeatedly carries out the following steps, until instructed to proceed to the
next timeslot:

  1. (1)

Player $p$ receives $R$, which is the set of all undelivered oracle responses
(to queries sent by $p$) with delivery timeslots $\leq t$.

  2. (2)

If $s\in St^{\ast}$, then $p$ disseminates a set of messages $M^{\prime}$ and
stops instructions for timeslot $t$. The set of messages $M^{\prime}$ is
determined by $s$ and $R$. Player $p$ will begin its next active timeslot in
state $s$.

  3. (3)

If $s\notin St^{\ast}$, then $p$ sends a set of oracle queries $Q$ and enters
a new state $s^{\prime}$, where $Q$ and $s^{\prime}$ are determined by $s$ and
$R$. Set $s:=s^{\prime}$ and return to (1).

For certain state diagrams, the instructions above might not terminate. In
this case, $p$ disseminates no messages at timeslot $t$ and is regarded as
inactive at all subsequent timeslots. If $p$ is inactive at timeslot $t$, then
it does not disseminate or receive any messages, does not send any queries at
$t$, and does not change state.

Byzantine and honest players. To ensure that our impossibility results are as
strong as possible, we focus primarily on a _static adversary_. (Section 10
considers a weak type of dynamic adversary, as is necessary to discuss long-
range attacks.) In the static adversary model, each player is either
_Byzantine_ or _honest_ , and an arbitrary and undetermined subset of the
players may be Byzantine. The difference between Byzantine and honest players
is that honest players must have the state diagram $\Sigma$ specified by the
protocol, while Byzantine players may have arbitrary state diagrams. To model
a perfectly coordinated adversary, we also allow that the instructions carried
out by each Byzantine player can depend on the messages and responses received
by other Byzantine players. That is, if $p$ is Byzantine, the messages $p$
disseminates, the queries $p$ sends, and $p$’s state transition at a timeslot
$t$ are a function not only of $p$’s state and the multiset of messages and
oracle responses received by $p$ at $t$, but also of the corresponding values
for all the other Byzantine players.

Protocols and executions. A _protocol_ is a pair $(\Sigma,\mathcal{O})$, where
$\Sigma$ is the state diagram of honest players and $\mathcal{O}$ is a finite
set of oracles. An _execution_ of the protocol $(\Sigma,\mathcal{O})$ is a
specification of the set of players $\mathcal{P}$, the player allocation, the
state diagram of each player and their inputs, and the following values for
each player $p$ at each timeslot:

  1. (i)

$p$’s state at the beginning of the timeslot.

  2. (ii)

The multiset of messages received by $p$.

  3. (iii)

The sequence of sets of queries sent by $p$.

  4. (iv)

The sequence of sets of responses received by $p$.

  5. (v)

The messages disseminated by $p$.

As described above, messages disseminated by a player at the end of a timeslot
(item (v)) can depend on the messages and all oracles responses received
during the timeslot (items (ii) and (iv)). Oracle queries sent during a
timeslot can depend on the messages received in that timeslot, as well as any
oracle responses received previously during the timeslot. A player’s
(ultimate) state transition in a timeslot can be interpreted as occurring
simultaneously with item (v).

Executions “consistent with the setting”. Part of the definition of a
“setting” is the class of executions to be considered; we say that such
executions are “consistent with the setting.” For example, if we are assuming
the synchronous communication model as part of the setting, an execution
consistent with the setting will, in particular, follow a timing rule that is
consistent with the synchronous communication model.

###  3.3. Permitted messages

To model certain cryptographic primitives, and to model resources later on, it
is convenient to restrict the set of messages and queries that a player can
send at any given timeslot. The approach we’ll describe here may initially
seem a little heavy-handed, but in exchange it gives a general methodology
that can be used to model signature schemes, VDFs, proof-of-work (PoW), proof-
of-space (PoSp), and proof-of-stake (PoS).

Message entries and types. We assume that all messages and queries are ordered
tuples $(e_{1},\dots,e_{k})$, where $k$ may vary for different messages and
queries, and where each entry $e_{i}$ may be of a specific _type_. This does
not lose any generality, as tuples may be of length 1 and of _general_ type.
The type of each entry in the tuple could be specified explicitly, but to keep
things simple we suppress type information in our notation.

Permitted messages/queries. At a given timeslot, and for a given player $p$,
each entry $e_{i}$ in a message or query $(e_{1},\dots,e_{k})$ may or may not
be _permitted_ for $p$. The message/query is permitted for $p$ if and only if
all entries are permitted for $p$. The messages that $p$ disseminates at a
given timeslot, and the set of queries that $p$ sends, are those specified by
the state diagram of $p$ which are also permitted. (Importantly, Byzantine
players cannot send oracle queries or messages that are not permitted for
them.)

In addition to the _general_ entry type (which is permitted for all $p$),
entries may be of type _signed_ (used below to model a signature scheme) or of
a type $O_{i}$ corresponding to an oracle (intuitively, representing a
signature by the oracle $O_{i}$).

A simple model of a signature scheme. To model a signature scheme, we suppose
that an entry of signed type must be of the form $(id,m)$, where $id$ is an
identifier and $m$ is arbitrary. In the _authenticated_ setting, the entry
$e=(id,m)$ of signed type is permitted for $p$ at $t$ if and only if
$id\in\mathtt{id}(p)$ or $p$ has previously received a message which contained
the entry $e$ (in which case $p$ is free to repeat it to others). We say that
$e$ is $m$ “signed by” $id$.151515Modeled this way, an idealized signature
scheme requires no oracle, only restrictions on the messages that players are
permitted to send. (Intuitively, we grant idealized standard signatures
“native status” in our framework.) In the unauthenticated setting, entries of
signed type are always permitted.161616The practical deployment of a signature
scheme requires probabilistic processes for key generation. Following a
traditional approach in distributed computing (see, e.g., Lynch (Lynch,
1996)), we treat a protocol that uses a signature scheme as deterministic if
its state diagram and oracles are deterministic (in effect, “fast-forwarding”
past any probabilistic processes that might have been required for the setup).

In general, the “signed” type is used when different entries are initially
permitted for different players. Meanwhile, if an entry $e$ is of type $O$,
then $e$ is permitted for $p$ if $p$ has previously received a message or
response which contained the entry $e$ of type $O$. (Intuitively, such an
entry can be obtained directly by querying the oracle $O$, or can be repeated
after hearing it from others.)

Modeling a perfectly coordinated adversary. If $p$ and $p^{\prime}$ are both
Byzantine, then the set of entries permitted for $p$ is modified to include
those permitted for $p^{\prime}$. (E.g., Byzantine players might pool their
private keys.)

Further terminology. If a message is a tuple of length 1, then the _type of
the message_ is the type of its single entry.

###  3.4. Modeling VDFs and ephemeral keys

Many of the impossibility results in this paper (Proposition 3.1 and Theorems
6.1, 7.2, 7.3, 7.4, and 11.1) apply no matter what oracles a protocol might
use (be they practically realizable or not). Accordingly, the proofs of these
results refer to a protocol’s oracles only in a “generic” way, typically in
the context of a simulation of honest players carried out by Byzantine
players. The exception is Theorem 10.1, which investigates how the choice of
oracles affects a protocol’s vulnerability to long-range attacks. In
preparation for that result, and to furnish additional examples of our oracle
formalism in action, we next show how to model via oracles two different
cryptographic primitives that are useful for repelling long-range attacks.

Modeling a VDF. To model VDFs, we suppose queries to the VDF oracle $O_{v}$
must be of the form $(m,k)$, where $k\in\mathbb{N}$ and $m$ is arbitrary. If
$p$ submits the query $(m,k)$ at timeslot $t$, then it receives the response
$(m,k)$ at timeslot $t+k$, where the response is of type $O_{v}$ (in effect,
signed by the oracle). A player can send a message that includes such a
type-$O_{v}$ entry only after receiving it as a response from the oracle or in
a message from another player.

Modeling ephemeral keys. For our purposes, we can model (the signatures
produced by) ephemeral keys using an oracle $O$ to which player $p$ may submit
any finite number of requests of the form $((id,m),t^{\prime})$ at any
timeslot $t$, where the entry $(id,m)$ is of signed type (and must be
permitted for $p$). If $t^{\prime}>t$, then $O$ sends $p$ the response
$((id,m),t^{\prime})$ at timeslot $t$, which is an entry of type $O$ (“signed
by $O$,” in effect). If $t^{\prime}\leq t$, then $O$ sends some predefined
“null” response at $t$ (intuitively, the key for timeslot $t^{\prime}$ has
already expired).

###  3.5. Consensus is not possible in the fully permissionless setting
without resource restrictions

We conclude this section by showing that the Byzantine Agreement problem is
unsolvable without some notion of “resources” to limit the collective power of
the Byzantine players.

Defining the Byzantine Agreement Problem (BA). We must modify the standard
definition of the problem to accommodate players that may not be active at all
timeslots. Suppose $d=\infty$ and that each player is given an input in
$\\{0,1\\}$. We refer to the latter input as the _protocol_ input for $p$, as
distinguished from other _parameter_ inputs, such as the duration $d$ and
$\mathtt{id}(p)$. For simplicity, in this section we consider deterministic
solutions to the problem; probabilistic solutions are taken up in Section 6.
We say that a deterministic protocol “solves Byzantine Agreement” if, for
every protocol execution consistent with the setting, there exists a timeslot
$t^{\ast}$ for which the following three conditions are satisfied:

Termination. All honest players active at any timeslot $\geq t^{\ast}$
terminate and give an output in $\\{0,1\\}$.

Agreement. All honest players that output give the same output.

Validity. If all players are given the same input $i$, then every honest
player that outputs gives $i$ as their output.

Solving BA is impossible in this setting. Because we have imposed no bounds on
the “combined power” of Byzantine players, no protocol (even with the use of
oracles) can solve Byzantine Agreement in the model that we have described
thus far.

###### Proposition 3.0.

Consider the fully permissionless setting (with oracles but without resources)
and suppose that the player set $\mathcal{P}$ is finite. For every $\rho>0$,
no protocol solves Byzantine agreement when up to a $\rho$ fraction of the
players may be Byzantine. This result holds even in the synchronous setting,
with a known player set, and with all players active at all timeslots.

###### Proof.

We give a proof for the deterministic case, but the argument extends easily to
probabilistic protocols and the probabilistic version of Byzantine Agreement
defined in Section 6.2; see also footnote 32.

Towards a contradiction, suppose that such a protocol exists. Fix a set of
parameter inputs with $\Delta=1$. Choose $n\geq 3$ such that $2/n<\rho$ and
consider a set of players $\mathcal{P}:=\\{p_{0},p_{1},\dots,p_{n-1}\\}$. Let
$\mathtt{id}_{1},\mathtt{id}_{2},\ldots,\mathtt{id}_{n-1},\mathtt{id}_{1}^{\prime},\mathtt{id}_{2}^{\prime},\ldots,\mathtt{id}_{n-1}^{\prime}$
denote $2n-2$ disjoint sets of identifiers. We consider three possible
executions of the given protocol:

  1. (1)

Execution $\mathtt{E}_{1}$:

     * •

Player $p_{0}$ is Byzantine, players $p_{1},p_{2},\ldots,p_{n-1}$ are honest.

     * •

All players are active in all timeslots.

     * •

For each honest player $p_{i}$, $\mathtt{id}(p_{i})=\mathtt{id}_{i}$.

     * •

All players receive an input of 0.

     * •

For $p_{0}$, $\mathtt{id}(p_{0})=\cup_{i=1}^{n-1}\mathtt{id}_{i}^{\prime}$.

     * •

$p_{0}$ ignores its input and simulates the behavior (including messages sent
and oracle queries made) of $n-1$ honest (and fictitious) players
$p^{\prime}_{1},p^{\prime}_{2},\ldots,p^{\prime}_{n-1}$ that all have an input
of 1 and in which
$\mathtt{id}(p_{i}^{\prime})=\mathtt{id}_{i}^{\prime}$.171717Player $p_{0}$ is
in a position to carry out this simulation because neither honest players nor
oracles know whether the player to which an identifier belongs is Byzantine,
and because there is no limit on the number of messages or oracle queries and
responses that a player can send or receive in a single timeslot.

  2. (2)

Execution $\mathtt{E}_{2}$:

     * •

Player $p_{0}$ is Byzantine, players $p_{1},p_{2},\ldots,p_{n-1}$ are honest.

     * •

All players are active in all timeslots.

     * •

For $p_{1}$, $\mathtt{id}(p_{1})=\mathtt{id}_{1}$. For every other honest
player $p_{i}$, $\mathtt{id}(p_{i})=\mathtt{id}_{i}^{\prime}$.

     * •

Player $p_{1}$ receives an input of 0 and all other players receive an input
of 1.

     * •

For $p_{0}$,
$\mathtt{id}(p_{0})=\mathtt{id}_{1}^{\prime}\cup\bigcup_{i=2}^{n-1}\mathtt{id}_{i}$.

     * •

$p_{0}$ simulates $n-1$ honest players
$p^{\prime}_{1},p^{\prime}_{2},\ldots,p^{\prime}_{n-1}$ under the conditions
that $p^{\prime}_{1}$ has an input of 1,
$p_{2}^{\prime},p_{3}^{\prime},\ldots,p_{n-1}^{\prime}$ each has an input of
0, $\mathtt{id}(p^{\prime}_{1})=\mathtt{id}_{1}^{\prime}$, and
$\mathtt{id}(p_{i}^{\prime})=\mathtt{id}_{i}$ for each $i=2,3,\ldots,n-1$.

  3. (3)

Execution $\mathtt{E}_{3}$:

     * •

Players $p_{0}$ and $p_{1}$ are Byzantine, players
$p_{2},p_{3},\ldots,p_{n-1}$ are honest.

     * •

All players are active in all timeslots.

     * •

All players receive an input of 1.

     * •

Identifier assignments for all players are the same as in execution
$\mathtt{E}_{2}$.

     * •

$p_{0}$ and $p_{1}$ behave identically as in execution $\mathtt{E}_{2}$. (In
particular, player $p_{1}$ acts as if its input is 0.)

The following observations complete the contradiction:

  1. (1)

By validity and termination, in $\mathtt{E}_{1}$, all honest players must
eventually output 0.

  2. (2)

By validity and termination, in $\mathtt{E}_{3}$, all honest players must
eventually output 1.

  3. (3)

Because the executions $\mathtt{E}_{1}$ and $\mathtt{E}_{2}$ are
indistinguishable for $p_{1}$—that is, $p_{1}$ receives the same inputs and
the same messages and oracle responses at each timeslot in both
executions—$p_{1}$ must eventually output 0 in $\mathtt{E}_{2}$.

  4. (4)

By agreement and termination, in $\mathtt{E}_{2}$, all honest players must
eventually output 0.

  5. (5)

Because the executions $\mathtt{E}_{2}$ and $\mathtt{E}_{3}$ are
indistinguishable for all the players $p_{2},p_{3},\ldots,p_{n-1}$, they must
output the same value in both executions.

∎

Discussion. The proof of Proposition 3.1 is driven by the fact that identifier
sets are undetermined and of unbounded size (i.e., that Byzantine players can
employ sybils).181818This aspect of the model will not feature in any of our
other impossibility results as, from Section 4 onward, protocols will be
allowed to make use of “resources” that, in many scenarios, suffice to nullify
the sybil challenge. In particular, the unbounded size assumption is crucial:
The positive result of Khanchandani and Wattenhofer (Khanchandani and
Wattenhofer, 2021) shows that Proposition 3.1 no longer holds with a finite
undetermined player set and undetermined player allocation when
$|\mathtt{id}(p)|=1$ for every player $p$.

The statement of Proposition 3.1 assumes that the player set is finite. A
similar result holds quite trivially in the case that the player set is
infinite after dropping the (no longer meaningful) assumption that at most a
$\rho$ fraction of the players are Byzantine. Consider two infinite sets of
(always-active) players $A$ and $B$. Let players in $A$ have input 0, while
those in $B$ have input 1. If all players are honest, then all must terminate
and give a common output. Without loss of generality, suppose they all output
0 in this case. Then validity is violated in the case that all players receive
input 1, but the players in $A$ are Byzantine and behave exactly like honest
players with input 0.

Proposition 3.1 shows that, to make progress, we must somehow bound the
combined power of Byzantine players, and in a way different from the
traditional approach of bounding the fraction of players that are Byzantine.
How should we phrase such a bound? The proof of Proposition 3.1 fundamentally
depends on the ability of Byzantine players to costlessly generate an
arbitrarily large number of sybils, which in turn enables the simultaneous
simulation of an arbitrarily large number of honest players. The bound must
therefore concern something that is scarce and costly to acquire—something
that prevents a Byzantine player from carrying out a simulation of many honest
players. These ideas bring us to the notion of resources that limit the number
of times that a player can query an oracle in a single timeslot; these are
discussed next.

##  4\. External resources

This section introduces external resources, which typically represent the
hardware (such as ASICs or memory chips) that is used by validators in proof-
of-work (PoW) or proof-of-space (PoSp) protocols. Sections 5 and 8 consider
on-chain resources such as staked cryptocurrency.

###  4.1. External resources and permitters

_Permitter oracles_ , or simply permitters, are required for modeling external
resources (but not for on-chain resources). In the fully permissionless
setting (with resource restrictions), a protocol may use a finite set of
permitters. These are listed as part of the protocol amongst the oracles in
$\mathcal{O}$, but have some distinguished features. Like other oracles,
permitters may be deterministic or probabilistic.

The resource allocation. For each execution of the protocol, and for each
permitter oracle $O$, we are given a corresponding _resource allocation_ ,
denoted $\mathcal{R}^{O}$. We assume that $\mathcal{R}^{O}$ is undetermined,
as befits an “external” resource. The resource allocation can be thought of as
assigning each player some amount of the external resource at each timeslot.
That is, for all $p\in\mathcal{P}$ and $t\leq d$, we have
$\mathcal{R}^{O}(p,t)\in\mathbb{N}$. We refer to $\mathcal{R}^{O}(p,t)$ as
$p$’s resource balance at $t$. Because resource balances are unknown to a
protocol, an inactive player might as well have a zero resource balance:
$\mathcal{R}^{O}(p,t)=0$ whenever $p$ is not active at $t$. (For example, a
protocol can’t know whether a player owns no ASICs, or owns a large number of
ASICs but currently has them all turned off.) For each $t$, we also define
$\mathcal{R}^{O}(t):=\sum_{p}\mathcal{R}^{O}(p,t)$.

Restricting the adversary. An arbitrary value $R^{O}_{\text{max}}$ is given as
a protocol input. This value is determined, but the protocol must function for
any given value of $R^{O}_{\text{max}}\geq 1$.191919Our assumption that the
(possibly very loose) upper bound $R^{O}_{\text{max}}$ on the total resource
usage is given as an input reflects the fact that protocols such as Bitcoin
are not expected to function properly for arbitrarily changing total
hashrates. For example, the Bitcoin protocol need not be secure (even in the
synchronous setting) when the total hashrate can increase extremely quickly.
(One could alternatively bound the maximum rate of change of
$\mathcal{R}^{O}(t)$, but we’ll work here with the simpler assumption.)  Let
$B$ denote the set of Byzantine players and define
$\mathcal{R}^{O}_{B}(t):=\sum_{p\in B}\mathcal{R}^{O}(p,t)$. For
$\rho\in[0,1]$, we say that $\mathcal{R}^{O}$ is $\rho$-bounded if the
following conditions are satisfied for all $t\leq d$:

  * •

$\mathcal{R}^{O}(t)\in[1,R^{O}_{\text{max}}]$.

  * •

$\mathcal{R}^{O}_{B}(t)/\mathcal{R}^{O}(t)\leq\rho$.

The smaller the value of $\rho$, the more severe the restriction on the
combined “power” of the Byzantine players. When $\rho<1$, the assumption that
$\mathcal{R}^{O}(t)\geq 1$ for all $t\leq d$ avoids the degenerate case in
which there are no active honest players. If all resource allocations
corresponding to permitters in $\mathcal{O}$ are $\rho$-bounded, then we say
the adversary is _externally_ $\rho$-_bounded_.

Generally, protocols in the fully permissionless setting will be expected to
function for arbitrary and undetermined resource allocations, so long as they
are externally $\rho$-bounded for a certain specified $\rho$.202020Further
restrictions on resource allocations can be imposed when convenient, as when
we model the (proof-of-space) Chia protocol in Appendix A.

Permitter oracles. The difference between permitter oracles and other oracles
is that the queries that a player $p$ can send to a permitter oracle $O$ at
timeslot $t$ depend on $\mathcal{R}^{O}(p,t)$. If a player $p$ sends a query
to the permitter oracle $O$ at timeslot $t$, the query must be of the form
$(b,\sigma)$ such that $b\in\mathbb{N}$ and $b\leq\mathcal{R}^{O}(p,t)$.
Importantly, this constraint applies also to Byzantine players.

A player may make multiple queries
$(b_{1},\sigma_{1}),\ldots,(b_{k},\sigma_{k})$ to a permitter in a single
timeslot $t$—possibly across multiple iterations within the timeslot, as
described in Section 3.2—subject to the following constraints. With a single-
use permitter—the appropriate version for modeling the Bitcoin protocol
(Section 4.2)—these queries are restricted to satisfy
$\sum_{i=1}^{k}b_{i}\leq\mathcal{R}^{O}(p,t)$. (Interpreting the $b_{i}$’s as
hashrates devoted to the queries, this constraint asserts that none of a
player’s overall hashrate can be “reused.”) With a multi-use permitter—the
more convenient version for modeling the Chia protocol in Appendix A—the only
restriction is that $b_{i}\leq\mathcal{R}^{O}(p,t)$ for each $i=1,2,\ldots,k$.
(Intuitively, space devoted to storing lookup tables can be reused across
different “challenges.”)

###  4.2. Modeling PoW in Bitcoin

We next show how to model proof-of-work, as used in the Bitcoin protocol,
using our permitter formalism. The basic idea is that, at each timeslot, a
player should be able to request permission to publish a certain block, with
the permitter response depending on the player’s resource balance (i.e.,
hashrate). To integrate properly with the “difficulty adjustment” algorithm
used by the Bitcoin protocol to regulate the average rate of block production
(even as the total hashrate devoted to the protocol fluctuates), we define the
permitter oracle so that its responses can have varying “quality.” Each PoW
oracle response will be a 256-bit string $\tau$, and we can regard the quality
of $\tau$ as the number of 0s that it begins with.

An example. As an example, suppose that $\mathcal{R}^{O}(p,t)=5$. Then $p$
might send a single query $(5,\sigma)$ at timeslot $t$, and this should be
thought of as a request for a PoW for $\sigma$ (which could represent a block
proposal, for example). If $p$ does not get the response that it’s looking
for, it might, at a later timeslot $t^{\prime}$ with
$\mathcal{R}^{O}(p,t^{\prime})=5$, send another query $(5,\sigma)$ to the PoW
oracle.

Formal details. We consider a single-use permitter. All queries to the
permitter must be of the form $(b,\sigma)$, where $\sigma$ is any finite
string. As already stipulated above, the fact that $O$ is a single-use
permitter means that $p$ can send the queries
$(b_{1},\sigma_{1}),\dots(b_{k},\sigma_{k})$ at the same timeslot $t$ only if
$\sum_{i=1}^{k}b_{i}\leq\mathcal{R}^{O}(p,t)$.

Sampling the response function. At the beginning of the protocol execution, we
choose a response function $f$, as follows. For each triple $(b,\sigma,t)$, we
independently sample $b$-many 256-bit strings uniformly at random and let
$\tau$ be the lexicographically smallest of these sampled strings. We define
$f((b,\sigma),t)$ to be $(r,t)$, where $r:=(\sigma,\tau)$ is an entry of type
$O$.212121Recall from Section 3 that players cannot send messages with a
specific entry of type $O$ until they have received a message or a response
including that same entry of type $O$. For example, a Byzantine player cannot
acquire an original PoW without querying the PoW oracle directly. That is, if
$p$ submits the query $(b,\sigma)$ at timeslot $t$, it receives the above
type-$O$ response $r=(\sigma,\tau)$ at timeslot $t$.

##  5\. Blockchain protocols and stake

For an external resource (Section 4), players’ resource balances evolve
according to an exogenous function $\mathcal{R}^{O}$ that does not depend on
the execution of the protocol under consideration. On-chain resources (such as
staked cryptocurrency) evolve in lockstep with a protocol’s execution, and as
such require a more sophisticated model. This section focuses on the specific
case of stake, which is relevant, in particular, to the fully permissionless
setting (with resource restrictions) defined in Section 6. More general
protocol-defined resources, which are defined in Section 8, are not relevant
to the fully permissionless setting but play an important role in the quasi-
permissionless setting studied in Sections 9–11.

###  5.1. Stake and transaction confirmation

On-chain resources, and stake in particular, make sense in the context of
blockchain protocols, meaning protocols that _confirm_ certain messages such
as _transactions_.222222Many blockchain protocols decide on a total ordering
on the set of confirmed transactions. The general form of “payment system”
considered here also captures, for example, DAG-based (“directed acyclic
graph”) protocols that do not specify such a total ordering (e.g.,
(Sompolinsky et al., 2016)).

The initial stake distribution. Players are allocated an _initial stake
distribution_ , denoted $S_{0}$, as input.232323“Stake” could be interpreted
as the cryptocurrency balance of an account, or more restrictively as the
amount of an account’s cryptocurrency that is held in escrow in a designated
staking contract. Except where necessary, we won’t distinguish between these
two interpretations. This distribution allocates a positive integer amount of
stake to each of a finite number of identifiers, and can be thought of as
chosen by an adversary, subject to any constraints imposed on the fraction of
stake controlled by Byzantine players.

The environment. For each execution of the blockchain protocol, there exists
an undetermined _environment_ , denoted $\mathtt{En}$, which sends messages of
_transaction type_ to players—messages with a single entry, which is of
_transaction type_. An entry/message $\mathtt{tr}$ of transaction type,
henceforth referred to as a _transaction_ , is not permitted for $p$ until
received by $p$ (directly from the environment, or from another player).

If $\mathtt{En}$ sends $\mathtt{tr}$ to $p$ at timeslot $t$, then $p$
_receives_ $\mathtt{tr}$ at $t$ as a member of its multiset of messages
received at that timeslot. Formally, the environment $\mathtt{En}$ is simply a
set of triples of the form $(p,\mathtt{tr},t)$ such that $p$ is active at $t$.
We stipulate that, if $(p,\mathtt{tr},t)\in\mathtt{En}$, then $p$ receives the
transaction $\mathtt{tr}$ at $t$, in addition to the other disseminations that
it receives at $t$. We assume that, for each $p\in\mathcal{P}$ and each $t$,
there exist at most finitely many triples $(p,\mathtt{tr},t)$ in
$\mathtt{En}$.

One may think of the environment as being chosen by an adversary, subject to
constraints that are detailed below.

The stake allocation function. We assume some fixed notion of validity for
transactions: Any set of transactions $\mathtt{T}$ may or may not be _valid_
relative to $S_{0}$. We say that $\mathtt{tr}$ is valid relative to $S_{0}$
and $\mathtt{T}$ if $\mathtt{T}\cup\\{\mathtt{tr}\\}$ is valid relative to
$S_{0}$. If $\mathtt{T}$ is a set of transactions that is valid relative to
$S_{0}$, we let $\mathtt{S}(S_{0},\mathtt{T},id)$ ($\in\mathbb{N}$) be the
stake owned by identifier $id$ after execution of the transactions in
$\mathtt{T}$. It will also be notationally convenient to let
$\mathtt{S}(S_{0},\mathtt{T})$ denote the function which on input $id$ gives
output $\mathtt{S}(S_{0},\mathtt{T},id)$.242424We are assuming that the stake
distribution depends only on the subset of transactions that have been
processed, and not on the order in which they were processed. (Similarly,
validity is assumed to be a property of an unordered set of transactions, not
of an ordering of transactions.) This property holds for payment systems, but
does not generally hold in Turing-complete blockchain protocols. For our
impossibility results, this restriction on the possible transactions only
makes them stronger. Theorem 9.1, a positive result, holds more generally when
the transaction order matters. The role of this restriction in Theorem 11.2 is
discussed at length in Sections 11 and 15.

We assume that stake can be transferred and that “negative balances” are not
allowed.252525If stake represents cryptocurrency in a designated staking
contract (see footnote 23), then we are additionally assuming that each
account is free to stake or unstake any amount of the cryptocurrency owned by
that account. Formally, suppose $\mathtt{T}$ is a valid set of transactions
relative to $S_{0}$. Suppose $\mathtt{S}(S_{0},\mathtt{T},id_{1})=x_{1}$ and
$\mathtt{S}(S_{0},\mathtt{T},id_{2})=x_{2}$. Then, for each $x\in\mathbb{N}$
with $x\leq x_{1}$, there exists a transaction $\mathtt{tr}$ that is valid
relative to $\mathtt{T}$ and $S_{0}$ and such that
$\mathtt{S}(S_{0},\mathtt{T}\cup\\{\mathtt{tr}\\},id_{1})=x_{1}-x$,
$\mathtt{S}(S_{0},\mathtt{T}\cup\\{\mathtt{tr}\\},id_{2})=x_{2}+x$, and
$\mathtt{S}(S_{0},\mathtt{T}\cup\\{\mathtt{tr}\\},id)=\mathtt{S}(S_{0},\mathtt{T},id)$
for $id\notin\\{id_{1},id_{2}\\}$. If $\mathtt{tr}$ is as specified and
$\mathtt{T}^{\prime}$ is a set of transactions which is valid relative to
$S_{0}$ with $\mathtt{S}(S_{0},\mathtt{T}^{\prime},id_{1})<x$, then
$\mathtt{T}^{\prime}\cup\\{\mathtt{tr}\\}$ is not a valid set of transactions.

We say transactions $\mathtt{tr}_{1}$ and $\mathtt{tr}_{2}$ are _conflicting_
relative to $\mathtt{T}$ and $S_{0}$ if $\mathtt{T}\cup\\{\mathtt{tr}_{1}\\}$
and $\mathtt{T}\cup\\{\mathtt{tr}_{2}\\}$ are both valid relative to $S_{0}$,
but $\mathtt{T}\cup\\{\mathtt{tr}_{1}\\}\cup\\{\mathtt{tr}_{2}\\}$ is not
valid relative to $S_{0}$.

Confirmed transactions. Each _blockchain protocol_ specifies a _confirmation
rule_ $\mathcal{C}$, which is a function that takes as input an arbitrary set
of messages $M$ and returns a subset $\mathtt{T}\subseteq M$ of the
transactions among those messages; the confirmed transactions $\mathtt{T}$
must be valid with respect to the initial stake distribution $S_{0}$. At
timeslot $t$, if $M$ is the set of all messages received by an honest player
$p$ at timeslots $\leq t$, then $p$ regards the transactions in
$\mathcal{C}(M)$ as _confirmed_.262626In principle, a confirmation rule could
depend on the timeslots at which an honest player received its
messages—necessarily timeslots at which the player was active—in addition to
the messages themselves. This distinction plays an interesting role in our
treatment of long-range attacks in Section 10. (All other results in this
paper hold whether or not a confirmation rule is allowed to depend on the
timeslots in which messages were received.) For a set of messages $M$, define
$\mathtt{S}(S_{0},M,id):=\mathtt{S}(S_{0},\mathcal{C}(M),id)$ and
$\mathtt{S}(S_{0},M):=\mathtt{S}(S_{0},\mathcal{C}(M))$.

The confirmation rule $\mathcal{C}$ is separate from the state diagram
$\Sigma$ (i.e., the protocol instructions), and one may therefore consider
different confirmation rules for the same protocol instructions. In the fully
permissionless setting, a blockchain protocol is thus a triple
$(\Sigma,\mathcal{O},\mathcal{C})$. For example, the Bitcoin protocol
instructs players to extend the longest chain. One confirmation rule might
extract the “longest chain” from $M$ and regard a transaction as confirmed if
it belongs to a block that is at least 6 deep in that chain. Another rule
might regard a transaction as confirmed once it belongs to a block that is at
least 10 deep in the longest chain.

Defining $\rho$-bounded adversaries. We say that an execution of a protocol is
$\rho$-bounded if:

  * •

The adversary is externally $\rho$-bounded (in the sense of Section 4.1).

  * •

Among active players, Byzantine players never control more than a $\rho$
fraction of the stake. Formally, for every honest player $p$ at timeslot $t$,
if $\mathtt{T}$ is the set of transactions that are confirmed for $p$ at $t$
in this execution, then at most a $\rho$ fraction of the stake allocated to
players active at $t$ by $\mathtt{S}(S_{0},\mathtt{T})$ is allocated to
Byzantine players.

When we say that “the adversary is $\rho$-bounded,” we mean that we restrict
attention to $\rho$-bounded executions. In a slight abuse of language, we say
that a protocol is $\rho$-resilient when it satisfies a certain claimed
functionality under the assumption that the adversary is $\rho$-bounded. So,
for example, we might say that a protocol for solving BA is $\rho$-resilient
if it solves BA for $\rho$-bounded adversaries.272727The restriction to
executions that are $\rho$-bounded may seem natural—what could one hope to
prove for an execution of a proof-of-stake protocol in which Byzantine players
amass enough stake to exceed a critical threshold? But it is arguably
preferable and more interpretable to instead impose a protocol-independent
restriction on the environment; this point is explored at length in Section
11.

###  5.2. Liveness and Consistency

With our notions of transactions and confirmation in place, we can proceed to
defining _liveness_ and _consistency_ for blockchain protocols. These
definitions are complicated by the fact that probabilistic protocols such as
Bitcoin and Algorand can offer consistency guarantees only for protocol
executions of finite duration. For this reason, our liveness definition
requires that transactions are confirmed sufficiently quickly (i.e., bounded
by a parameter sublinear in the duration). Our definitions must also
accommodate players that are not always active.

Defining liveness. Blockchain protocols are run relative to a determined input
$\epsilon\in[0,1)$, which is called the _security parameter_. (In the
deterministic model, $\epsilon=0$.) Liveness requires the existence of a value
$\ell$, which can depend on the determined inputs (such as $\epsilon$ and $d$)
but must be sublinear in $d$ (i.e., with $\ell=o(d)$ as $d\rightarrow\infty$),
such that with probability at least $1-\epsilon$, the following condition is
satisfied for every $t$. Suppose that:

  * •

$t^{\ast}:=\text{max}\\{\text{GST},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^{*}$. (Formally, for every honest $p$ and every
$t^{\prime}\in[t,t^{\ast}]$, if $\mathtt{T}$ is the set of transactions
confirmed for $p$ at $t^{\prime}$, then $\mathtt{T}\cup\\{\mathtt{tr}\\}$ is a
valid set of transactions relative to $S_{0}$.)

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.282828This liveness requirement would
become vacuous if $\ell$ were allowed to depend linearly on $d$. We work with
the weak liveness requirement considered here (with $\ell$ required only to be
sublinear in $d$) in order to make our impossibility results as strong as
possible.

Defining consistency. Consistency requires that, with probability at least
$1-\epsilon$, the following two conditions always hold:

  * (i)

No roll-backs: If $\mathtt{tr}$ is confirmed for honest $p$ at $t$, then
$\mathtt{tr}$ is confirmed for $p$ at all $t^{\prime}\geq t$.

  * (ii)

Confirmed transactions never conflict: If $\mathtt{T}$ and
$\mathtt{T}^{\prime}$ are the sets of transactions confirmed for honest $p$
and $p^{\prime}$ at $t$ and $t^{\prime}$, respectively, then
$\mathtt{T}\cup\mathtt{T}^{\prime}$ is a valid set of transactions relative to
$S_{0}$.

##  6\. The fully permissionless setting (with resource restrictions)

###  6.1. Defining the setting and the main result

The fully permissionless setting (with resource restrictions) is the same as
the setting without resources described in Section 3, but with the following
changes:

  1. (a)

Protocols may now make use of a finite set of permitters (and their
corresponding resource allocations), as described in Section 4, and may now
run relative to an environment that sends transactions (which might, for
example, update a stake distribution), as described in Section 5.292929In the
fully permissionless setting, we do not make any assumptions about the
activity status of players with non-zero stake. For example, having stake
locked up in a staking contract does not prevent a player from going offline
for any number of reasons. For an external resource, by contrast, inactive
players might as well possess a zero resource balance (a protocol cannot
distinguish between different external resource balances that might be
possessed by an inactive player).

  2. (b)

One may assume that the adversary is $\rho$-bounded (as defined in Section 5),
for some $\rho\in[0,1]$.

In the fully permissionless setting, a protocol is a triple
$(\Sigma,\mathcal{O},\mathcal{C})$. We will sometimes consider protocols that
are not blockchain protocols (i.e., that do not receive any transactions from
an environment, only the initial protocol inputs) and do not need a
confirmation rule; in this case, $\mathcal{C}$ can be interpreted as, for
example, a function that always returns the empty set.

Now that we have defined the fully permissionless setting (with resource
restrictions), we can state our first main result—the analog of the FLP
impossibility result for the fully permissionless (and synchronous) setting
mentioned in Section 1.3. (Recall the definition of the Byzantine Agreement
Problem from Section 3.5.)

###### Theorem 6.1.

Consider the fully permissionless, authenticated, and synchronous setting, and
suppose that, for some $\rho>0$, the adversary is $\rho$-bounded. Suppose that
dishonest players can only deviate from honest behavior by crashing or
delaying message dissemination by an arbitrary number of timeslots. Every
deterministic protocol for the Byzantine Agreement Problem has an infinite
execution in which honest players never terminate.

We present the proof of Theorem 6.1 in Section 12, along with a discussion of
which aspects of the fully permissionless setting matter for the
proof.303030Could a simple proof of Theorem 6.1 be achieved by adapting the
proof of Dolev and Strong (Dolev and Strong, 1983) that $f+1$ rounds are
necessary to solve Byzantine Agreement with $f$ faulty players? (The intuition
being that, if a new Byzantine player can enter in each round, then no finite
number of rounds should suffice to solve Byzantine Agreement.) The difficulty
with this approach is that the non-existence of a protocol with bounded
termination time does _not_ imply the non-existence of a protocol that always
(eventually) terminates, unless one can establish an appropriate compactness
condition on the execution space. Such an approach can be made to work (as in
the conference version of this paper (Lewis-Pye and Roughgarden, 2021)), but
the alternative argument we present in Section 12 is arguably somewhat
simpler.

Can the impossibility results in Proposition 3.1 or Theorem 6.1 be
circumvented by a probabilistic solution to BA? The next section introduces
the definitions necessary to discuss such questions.

###  6.2. Defining the probabilistic setting

The meaning of probabilistic statements. For a given (possibly randomized)
protocol, one way to completely specify an execution is via the following
breakdown:

  1. 1.

The set of players $\mathcal{P}$ and their inputs;

  2. 2.

The player allocation;

  3. 3.

The inputs and resource allocation for each permitter;

  4. 4.

The set of Byzantine players and their state transition diagrams;

  5. 5.

The timing rule;

  6. 6.

The transactions sent by the environment (and to which players and when);

  7. 7.

The (possibly probabilistic) state transitions of each player at each
timeslot;

  8. 8.

The (possibly probabilistic) responses of permitter oracles.

When we say that a protocol satisfies a certain condition (such as solving the
Byzantine Agreement Problem), we mean that this holds for all values of
(1)-(8) above that are consistent with the setting. We call a set of values
for (1)-(6) above a _protocol instance_. When we make a probabilistic
statement to the effect that a certain condition holds with at most/least a
certain probability, this means that the probabilistic bound holds for all
protocol instances that are consistent with the setting (with the
randomization over the realizations in (7) and (8)).313131This approach
implicitly restricts attention to protocol instances that can be defined
independently of the realizations in (7) and (8); for example, we do not allow
the transactions issued by the environment to depend on the outcomes of
players’ coin flips. The proofs of our impossibility results for probabilistic
protocols (Proposition 3.1 and Theorems 7.2, 7.3, 7.4, 10.1, and 11.1) all use
only instances of this restricted type; this restriction to “oblivious”
adversaries and environments only makes those results stronger. This
discussion is not relevant for the other results in the paper (Theorems 6.1,
9.1, and 11.2), which concern deterministic protocols.

Indistinguishability of instances. We say that two protocol instances are
_indistinguishable for $p$ at timeslots $\leq t$_ if both of the following
hold: (a) Player $p$ receives the same inputs for both instances, and; (b) The
distributions on messages and responses received by $p$ at each timeslot
$t^{\prime}\leq t$ are the same for the two instances. We say that two
protocol instances are _indistinguishable for $p$_ if they are
indistinguishable at all timeslots $<\infty$.323232For example, with this
definition of indistinguishability, steps (3) and (5) of the proof of
Proposition 3.1 apply more generally to probabilistic protocols. (For a
probabilistic protocol with security parameter $\epsilon$, steps (1), (2), and
(4) of that proof hold except with at most $\epsilon$ probability each,
leading to a contradiction provided $\epsilon<1/3$.)

Discussion. Some results that are impossible in the deterministic setting
become possible in the probabilistic setting. For example, Garay, Kiayias, and
Leonardos (Garay et al., 2018) prove that, for every $\rho<0.5$ and
$\epsilon>0$, the Bitcoin protocol can be used to define a $\rho$-resilient
protocol (in the sense of Section 5.1) that solves probabilistic BA with
security parameter $\epsilon$ in the synchronous and fully permissionless
setting (with resource restrictions).333333More precisely, for every
$\rho<1/2$, $\epsilon>0$, and value $\Delta>0$ for the delay bound parameter,
there exists a finite $T$ such that the variant of the Bitcoin protocol with
an average interblock time of $T$ can be used to define such a
$\rho$-resilient protocol. That is, the impossibility result in Theorem 6.1
does not extend to the probabilistic setting, even when arbitrary Byzantine
behavior is allowed.343434An easy argument—similar to the argument in the
discussion following Proposition 3.1—shows that no protocol solves
probabilistic BA with a security parameter $\epsilon<1/2$ when $\rho\geq 1/2$,
even in the permissioned and authenticated setting (with resource
restrictions). Interestingly, this positive result holds even in the
unauthenticated setting.353535Pease, Shostak, and Lamport (Pease et al., 1980)
and Fischer, Lynch, and Merritt (Fischer et al., 1986) show that, already in
the permissioned setting, probabilistic BA cannot be solved without
authentication when $\rho\geq 1/3$, even with synchronous communication. Why
doesn’t this impossibility result contradict the positive result (for all
$\rho<1/2$) in (Garay et al., 2018)? Because the Bitcoin protocol uses a
permitter (see Section 4.2) and the negative results in (Pease et al., 1980;
Fischer et al., 1986) consider only protocols that do not use any resources or
permitters. Intuitively, resources and permitters can partially substitute for
authentication in limiting the ability of a Byzantine player to simulate
honest players.

##  7\. The dynamically available setting

Theorem 6.1 establishes limitations on what is possible in the fully
permissionless setting; are there palatable additional assumptions under which
stronger positive results are possible? Relatedly, the fully permissionless
setting studied in Section 6 does not meaningfully differentiate between
protocols that use only external resources (like typical proof-of-work
protocols) and those that use on-chain resources (like typical proof-of-stake
protocols) as, in the fully permissionless setting, all the players with on-
chain resources might well be inactive. The way forward, then, would seem to
be additional assumptions on how player activity correlates with on-chain
resource balances. The dynamically available setting, defined in Section 7.1,
is an instantiation of this idea. (As is the quasi-permissionless setting,
which is defined in Section 9.) Section 7.2 notes that a recent result of Losa
and Gafni (Losa and Gafni, 2023) can be adapted to show that the dynamically
available setting is indeed meaningfully less demanding than the fully
permissionless setting (with resource restrictions).

The primary goal of this section is to demonstrate fundamental limitations on
what protocols can achieve in the dynamically available (and hence also the
fully permissionless) setting: they cannot solve the Byzantine Agreement
problem in partial synchrony (Theorem 7.2 in Section 7.3); they cannot provide
accountability, even in the synchronous setting (Theorem 7.3 in Section 7.4,
which follows directly from work of Neu, Tas, and Tse (Neu et al., 2022)); and
they cannot provide optimistic responsiveness, even in the synchronous setting
(Theorem 7.4 in Section 7.5). (With the stronger assumptions of the quasi-
permissionless setting, on the other hand, Theorem 9.1 shows that there is a
protocol that attains all three of these properties.)

###  7.1. Defining the setting

In the dynamically available setting, a protocol is a tuple
$(\Sigma,\mathcal{O},\mathcal{C})$. No assumptions are made about
participation by honest players, other than the minimal assumption that, if
any honest player owns a non-zero amount of stake, then at least one such
player is active. (Additional assumptions about the fraction of stake
controlled by active honest players are, as usual, phrased using the notion of
$\rho$-bounded adversaries from Section 5.1.)

Dynamically available setting. Consider the protocol
$(\Sigma,\mathcal{O},\mathcal{C})$. By definition, an execution of the
protocol is consistent with the dynamically available 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, if there exists an honest player assigned a non-zero amount of stake in $\mathtt{S}(S_{0},\mathtt{T})$, then at least one such player is active at $t$.

###  7.2. Separating the dynamically available and fully permissionless
settings

The additional assumptions imposed by the dynamically available setting,
relative to the fully permissionless setting, may appear modest. But the
following result, due (essentially) to Losa and Gafni (Losa and Gafni, 2023),
provides a formal separation between the two settings: the impossibility
result in Theorem 6.1 no longer holds in the dynamically available setting,
even in the unauthenticated case.

###### Theorem 7.1 (Losa and Gafni (Losa and Gafni, 2023)).

Consider the dynamically available, unauthenticated, and synchronous setting,
and suppose that, for some $\rho<1/2$, the adversary is $\rho$-bounded. There
is a deterministic protocol that solves the Byzantine Agreement problem
provided dishonest players can deviate from honest behavior only by crashing
or delaying message dissemination by an arbitrary number of timeslots.

The protocol used in the proof of Theorem 7.1 is similar in spirit to the
permissioned Dolev-Strong protocol (Dolev and Strong, 1983). Losa and Gafni
(Losa and Gafni, 2023) phrase their results in a model that differs from ours
in several respects; for completeness, we include a full proof of Theorem 7.1
in Appendix C. The additional assumptions of the dynamically available setting
circumvent the impossibility result in Theorem 6.1 by allowing a protocol to
ignore, without suffering an immediate loss of liveness, all identifiers with
no initial stake. Restricting attention to identifiers with non-zero initial
stake has the effect of bounding the maximum number of identifiers that could
be controlled by faulty players, which in turn opens the door to a Dolev-
Strong-style approach.

###  7.3. The dynamically available and partially synchronous setting

Theorem 6.1 established that deterministic protocols cannot solve BA in the
fully permissionless setting, even with synchronous communication. The
following result shows that, in the dynamically available and partially
synchronous setting (and therefore also in the fully permissionless and
partially synchronous setting), BA cannot be solved, even in the probabilistic
sense and with no Byzantine players.363636Recall that a protocol is
$\rho$-resilient if it achieves the desired functionality—such as solving BA,
or satisfying consistency and liveness with a security parameter
$\epsilon$—for adversaries that are $\rho$-bounded in the sense of Section
5.1. Thus, a “0-resilient” protocol is required to function correctly only
when all external resources and stake are always controlled by honest players.

###### Theorem 7.2.

For every $\epsilon<\tfrac{1}{3}$, there is no 0-resilient protocol solving
probabilistic BA with security parameter $\epsilon$ in the dynamically
available, authenticated, and partially synchronous setting.

We present the proof of Theorem 7.2 in Section 13, along with a discussion of
which aspects of the dynamically available setting matter for the proof. As
noted in Section 2.4, the argument resembles the logic behind the “CAP
Theorem.”

Theorem 9.1 in Section 9 shows that, in the quasi-permissionless and partially
synchronous setting, there is a (deterministic) proof-of-stake protocol that
solves BA. Theorems 7.2 and 9.1 thus provide a formal separation between the
dynamically available and quasi-permissionless settings, with the former
setting strictly more difficult than the latter.

###  7.4. Accountability in the dynamically available setting

The remaining results in this section concern blockchain protocols in the
sense of Section 5. Intuitively, such a protocol is “accountable” if there is
always a “smoking gun” for consistency violations, such as two signatures by a
common identifier that support conflicting transactions. Formally, we adopt
the definition of “forensic support” by Sheng et al. (Sheng et al., 2021)—who
studied only the traditional permissioned setting without external or on-chain
resources—to our framework.

Defining accountability. Consider a blockchain protocol
$(\Sigma,\mathcal{O},\mathcal{C})$ and security parameter $\epsilon$. For a
player set $\mathcal{P}$ and set of identifiers $\mathtt{id}^{*}$, let
$P(\mathtt{id}^{*}):=\\{p\in\mathcal{P}:\
\mathtt{id}^{*}\cap\mathtt{id}(p)\neq\emptyset\\}$ denote the players that
control at least one identifier in $\mathtt{id}^{*}$. For $\rho_{1}\in[0,1]$,
we say that $\mathtt{id}^{*}$ is of _weight at least_ $\rho_{1}$ in a given
execution if either:

  * •

there exists $t$ and a permitter $O\in\mathcal{O}$ such that $\sum_{p\in
P(\mathtt{id}^{*})}\mathcal{R}^{O}(p,t)\geq\rho_{1}\cdot\mathcal{R}^{O}(t)$;
or

  * •

there exists $t$ and honest $p$, with $\mathtt{T}$ the set of confirmed
transactions for $p$ at $t$, such that, for some
$\mathtt{T}^{\prime}\subseteq\mathtt{T}$,
$\mathtt{S}(S_{0},\mathtt{T}^{\prime})$ allocates the identifiers in
$\mathtt{id}^{*}$ at least a $\rho_{1}$-fraction of the total stake.

We say that a _consistency failure_ occurs in an execution if there exist
honest $p$ and $p^{\prime}$, with $\mathtt{T}$ and $\mathtt{T}^{\prime}$ the
sets of transactions confirmed for $p$ and $p^{\prime}$ at timeslots $t$ and