simple []

# Modeling Resources in Permissionless Longest-chain Total-order Broadcast

Sarah Azouvi
Protocol Labs  Christian Cachin
University of Bern  Duc V. Le
University of Bern  Marko Vukolić
Protocol Labs  Luca Zanolini
University of Bern

###### Abstract

Blockchain protocols implement total-order broadcast in a permissionless
setting, where processes can freely join and leave. In such a setting, to
safeguard against Sybil attacks, correct processes rely on cryptographic
proofs tied to a particular type of _resource_ to make them eligible to order
transactions. For example, in the case of Proof-of-Work (PoW), this resource
is computation, and the proof is a solution to a computationally hard puzzle.
Conversely, in Proof-of-Stake (PoS), the resource corresponds to the number of
coins that every process in the system owns, and a secure lottery selects a
process for participation proportionally to its coin holdings.

Although many resource-based blockchain protocols are formally proven secure
in the literature, the existing security proofs fail to demonstrate why
particular types of resources cause the blockchain protocols to be vulnerable
to distinct classes of attacks. For instance, PoS systems are more vulnerable
to long-range attacks, where an adversary corrupts past processes to re-write
the history, than PoW and Proof-of-Storage systems. Proof-of-Storage-based and
PoS-based protocols are both more susceptible to private double-spending
attacks than PoW-based protocols; in this case, an adversary mines its chain
in secret without sharing its blocks with the rest of the processes until the
end of the attack.

In this paper, we formally characterize the properties of resources through an
abstraction called _resource allocator_ and give a framework for understanding
longest-chain consensus protocols based on different underlying resources. In
addition, we use this resource allocator to demonstrate security trade-offs
between various resources focusing on well-known attacks (e.g., the long-range
attack and nothing-at-stake attacks).

##  1 Introduction

Permissionless consensus protocols are open for everyone to participate and
often rely on a _resource_ to protect against Sybil attacks. In the case of
Proof-of-Work (PoW), this resource is computation: A computational puzzle must
be solved in order to gain writing rights in the system. In contrast, in a
Proof-of-Stake (PoS) system, writing access is granted using a form of lottery
where participants are elected proportionally to the number of coins they own.
Other resource-based systems, such as Proof-of-Storage, have also appeared.
Participants are elected proportionally to the number of resources they commit
to the system, and hence this commitment must be publicly verifiable.
Different resources present different trade-offs. For example, PoS is much
more energy-efficient than PoW but presents many additional vulnerabilities
[5]. Comparing the security of protocols based on multiple resource types is a
non-trivial task, as they all operate under different assumptions and
frameworks.

In this paper, we provide a common framework to formally compare consensus
protocols based on different underlying resources. We only consider longest-
chain protocols [11] based on an underlying resource, as we want to highlight
the properties affected by relying varying the resource for the same consensus
method. In future work, our framework could be used to model further
approaches to ensure consensus, such as well-known BFT protocols [7], for
instance. In longest-chain protocols, one participant is elected at each time
step, on expectation, proportionally to their amount of resource and that
participant gets to write to the append-only database by adding a _block_
containing all the necessary data to the longest chain of blocks.

We also explore known attacks in this work. The first one is the long-range
attack. In a long-range attack, an adversary corrupts processes that used to
participate in the system but that no longer hold any resources. Moreover, we
investigate nothing-at-stake attacks, where processes mine on multiple chains
at the same time, and private attacks, where an adversary mines on its own
chain without contributing to the honest chain. We are interested in
quantifying gain or loss of security with different resources. It has already
been shown that, when considering longest-chain protocols, PoS is less secure
than PoW. We furthermore show that Proof-of-Storage stands in the middle, as
storage is not virtual (like stake), but is reusable (unlike the computation
of PoW).

We start the paper by providing a formal framework in which protocols based on
different resources can meaningfully be compared. We differentiate between
virtual and external resources to highlight which properties make longest-
chain PoS and Proof-of-Storage less secure than PoW, although they both
present trade-offs when it comes to their efficiency.

Contributions. Our contributions can be summarized as follows.

  * •

We formally characterize the properties of resources through an abstraction
called _resource allocator_ and formally define properties for a _secure_
resource allocator.

  * •

We concretely define different resource allocator abstractions, each one for
every type of resource used in popular blockchain protocols, namely,
computation, stake, and storage.

  * •

We present an algorithm that, when instantiated with different resource
allocators, leads to a generalization of existing protocols such as Nakamoto
consensus, Ouroboros Praos, and Filecoin’s consensus protocol. We also
formally show this generalization implements total-ordered broadcast under a
fixed total resource and permissionless setting.

  * •

We demonstrate how different resources lead to different security trade-offs
by leveraging our model to explain long-range attacks against virtual
resources and attacks related to the nothing-at-stake nature of reusable
resources.

Related Work. Since the emergence of Bitcoin in 2008, the academic community
has developed a number of frameworks [16, 24, 18, 11] for studying the safety
and liveness properties of its Nakamoto consensus protocol. These studies also
established a strong foundation for the development of blockchain protocols
based on more eco-friendly types of resources, such as stake and storage.
However, despite the fact that all resource-based blockchains have been
formally proven to be secure, they failed to explain why certain properties of
resources make some blockchain protocols more susceptible to particular types
of attacks than others. To the best of our knowledge, no prior work has
attempted to formally study the properties of underlying resources, and our
work aims to fill this gap.

Lewis-Pye and Roughgarden [23] present the concept of a _resource pool_ that
reflects the resource balance of processes in the system at any time, and they
use a _permitter_ together with the resource pool to abstract away the leader
selection procedure. Using this formalization, they demonstrate two crucial
impossibility results for permissionless systems. Two main results of their
work are: _(i)_ no permissionless, deterministic, and decentralized protocol
solves the Byzantine Agreement problem in a synchronous setting, and _(ii)_ no
permissionless and probabilistic protocols solve the Byzantine Agreement
problem in the unsized setting (in which the total number of resources is
unknown) with partially synchronous communication. However, their work could
not capture several aspects of underlying resources used in blockchain
protocols; therefore, their work did not demonstrate long-range attacks
against virtual resources such as stake, and the cost of several other attacks
on _reusable_ resources. Our work takes a similar approach of abstracting away
the leader selection process with a resource allocator (c.f., section 3), and
we further formalize the properties of resources through the interactions
between the process and this allocator. With this formalization, we prove how
permissionless and probabilistic blockchain protocols guarantee properties of
a total-order broadcast in a synchronous setting and demonstrate various
attacks against _virtual_ or _reusable_ resources.

Terner [27] also investigates how to abstract resources used in permissionless
blockchains. While their work outlines several essential properties of
resources and studies how the resource generation rate affects the standard
properties (i.e., consistency and liveness) of robust transaction ledger,
their study does not characterize the properties of the underlying resources
used in permissionless blockchain protocols. Consequently, their model fails
to explain why distinct types of resources render blockchain protocols
vulnerable to different attacks (e.g., long-range attacks and private
attacks).

##  2 Model and Definitions

###  2.1 System Model

Time. We assume that the protocol proceeds in _time steps_ and define a time
step to be a value in $\mathbb{N}$. Moreover, we consider $0$ as starting time
step of protocol execution.

Processes. We consider a system consisting of a set of _processes_ ,
$\mathcal{P}=\\{p_{1},p_{2},\ldots\\}$. Processes interact with each other
through exchanging messages. A protocol for $\mathcal{P}$ consists of a
collection of programs with instructions for all processes. Moreover, to
capture the permissionless nature of various blockchain protocols, processes
can join the system at any time. we denote, $\mathcal{P}_{\leq t}$, the set of
all processes that have participated in the protocol before the time step $t$.
Hence, $\mathcal{P}_{t}\subseteq\mathcal{P}_{t^{\prime}}$ for all $t\leq
t^{\prime}$. At the beginning of each time step, a process becomes _activated_
, and it starts to follow a deterministic protocol. This includes processing
any messages that may have arrived from other processes. Once done, it becomes
_deactivated_. We assume that the activation period of a process $p_{i}$
starts at the time step $t$ and ends before time step $t+1$.

Communication. We assume there is a low-level primitive for sending messages
over point-to-point links between each pair of processes that know of each
other, as well as a probabilistic broadcast primitive [7]. Point-to-point
messages are authenticated and delivered reliably among correct processes. In
probabilistic broadcast, correct processes gossip-deliver and gossip-broadcast
messages with an overwhelming probability, no message is delivered more than
once, and no message is created or corrupted by the network.

Network Delay. We denote by $\Delta\in\mathbb{N}$ with $\Delta\geq 1$ the
maximum network delay [14]. Namely, if a correct process gossip-broadcasts a
message $m$ at a time step $t$, then other processes will have gossip-
delivered or received over the message by the beginning of a time step
$t+\Delta$ with an overwhelming probability.

Idealized Digital Signature. A digital signature scheme, $\Sigma$, consists of
two operations, $\textsl{Sign}(\cdot,\cdot)$ and
$\textsl{Verify}(\cdot,\cdot,\cdot)$. The operation
$\textsl{Sign}(p_{i},\cdot)$ invoked by $p_{i}$ takes $m\in\\{0,1\\}^{*}$ as
input and returns a signature $\sigma\in\\{0,1\\}^{*}$. Only $p_{i}$ can
invoke $\textsl{Sign}(p_{i},\cdot)$. The operation
$\textsl{Verify}(p_{i},\cdot,\cdot)$ takes as input a signature, $\sigma$, and
a message $m$; $\textsl{Verify}(p_{i},\cdot,\cdot)$ returns true for any
$p_{i}\in\mathcal{P}$ and $m\in\\{0,1\\}^{*}$ if and only if $p_{i}$ has
invoked $\textsl{Sign}(p_{i},m)$ and obtained $\sigma$ before. Any process can
invoke $\textsl{Verify}(\cdot,\cdot,\cdot)$.

Random Oracle. All hash functions are modeled as a random oracle, $H$, that
can be queried by any process. $H$ takes as input a bit string
$x\in\\{0,1\\}^{*}$ and returns a uniformly random string from
$\\{0,1\\}^{\lambda}$ where $\lambda$ is the security parameter. Also, upon
repeated queries, $H$ always outputs the same answer.

###  2.2 Modeling Blockchain Data Structures

Blocks. We use $\mathsf{tx}$ to denote a _transaction_. We write
$\overline{\mathsf{tx}}=[\mathsf{tx}_{1},\dots,\mathsf{tx}_{m}]$ to denote a
list of transactions. A _block_ is
$B=(h,\overline{\mathsf{tx}},\pi,\sigma_{i})$, where $h$ is a hash value,
$\overline{\mathsf{tx}}$ is a list of transactions, $\pi$ is a resource
commitment proof (cf. Section 3) and $\sigma_{i}$ is a signature on
$(h,\overline{\mathsf{tx}},\pi)$. In this work, we assume that blocks are
signed. In this way, we can abstract away the notion of _coinbase_
transactions, i.e., the first transaction in a block, created by a miner, and
used to collect the block reward. Finally, we denote with
$B_{0}=(\bot,\overline{\mathsf{tx}},\bot,\bot)$ the genesis block.

Blockchain. A _blockchain_ $\mathcal{C}=[B_{0},B_{1},\dots]$ with respect to
the genesis block $B_{0}$ is a chain of blocks forming a hash chain such that
$h_{j}=H(B_{j-1})$ for $h_{j}\in B_{j}$ for $j=1,2,\dots$ with
$B_{j}=(h_{j},\bar{\mathsf{tx}_{j}},\pi_{j},\sigma_{j})$. For a blockchain
$\mathcal{C}$, we use $\mathcal{C}[-k]$ to denote the last $k$-th block in
$\mathcal{C}$, let $\mathcal{C}[k]$ to denote block $B_{k}$ (i.e., block at
height $k$), and write $\mathcal{C}[:-k]$ to denote the first
$|\mathcal{C}|-k$ blocks. $|\mathcal{C}|$ denotes the length of $\mathcal{C}$.
We write $\mathcal{C}\preceq\mathcal{C}^{\prime}$ when $\mathcal{C}$ is a
prefix $\mathcal{C}^{\prime}$. We use $\mathcal{C}^{t}$ to denote the
blockchain at time step $t$. For two time steps, $t_{1}$ and $t_{2}$,
$\mathcal{C}^{t_{2}}/\mathcal{C}^{t_{1}}$ is a set of blocks that is in
$\mathcal{C}^{t_{2}}$ but not in $\mathcal{C}^{t_{1}}$.

State. The blockchain _state_ st specifies different information of the
underlying blockchain protocol, e.g., the stake distribution of each process,
the block information, such as timestamps, as well as contract local states.
The blockchain state st can be reconstructed by executing transactions
included in a blockchain $\mathcal{C}$. Without loss of generality, we define
the state to be the blockchain, $\textit{st}=\mathcal{C}$. Also, we write
$\textit{st}=(\mathcal{C},B)$ to indicate that a block $B$ is potentially
appended to $\mathcal{C}$.

Validity. We introduce the notion of validity for transactions and blockchains
to capture the fact that only “valid” transactions are delivered. More
importantly, for all blockchain protocols, the decision on the validity is
determined locally by all processes. Because of this, we define the validity
as follows. A transaction $x$ is _valid_ with respect to $\mathcal{C}$ if
$\mathsf{tx}$ satisfies a _validation predicate_
$\mathbb{P}(\mathcal{C},\cdot)$ locally known to all processes (i.e.,
$\mathbb{P}(\mathcal{C},[\mathsf{tx}])=\textsc{true}$). We also use
$\mathbb{P}(\mathcal{C},\overline{\mathsf{tx}})=\textsc{true}$ to indicate
that the sequence of transactions in $\overline{\mathsf{tx}}$ is valid (i.e.,
does not consume the same output in Bitcoin or the same nonce in Ethereum),
and we define $\mathbb{P}(\mathcal{C},[~{}])$ to be true. Depending on the
blockchain protocol, a _valid block_ $B$ issued by $p_{i}$ should consist of a
valid signature issued by $p_{i}$, a valid “proof” $\pi$ for a so-called
resource commitment that we introduce in Section 3 and valid transactions with
respect to $\mathcal{C}$ such that $\mathcal{C}[-1]=B$, (i.e.,
$\mathbb{P}(\mathcal{C},\overline{\mathsf{tx}})=\textsc{true}$ for
$\overline{\mathsf{tx}}\in B$). Finally, _valid blockchains_ are chains that
consist of only valid blocks and start from the genesis block $B_{0}$.

###  2.3 Total-order Broadcast

We will show that the blockchain protocols considered here guarantee the
following properties of total-order broadcast in a permissionless setting. In
particular, total-order broadcast ensures that all processes deliver the same
set of transactions in a common global order. In total-order broadcast, every
process broadcasts a transaction by invoking
$\textsl{a-broadcasts}(\mathsf{tx})$. The broadcast primitive outputs a
transaction $\mathsf{tx}$ through an $\textsl{a-deliver}(\mathsf{tx})$ event.
In this model, we do not distinguish between a process and a client. A client
can be considered as a process that only broadcast transactions and does not
participate in mining.

###### Definition 1 (Total-order Broadcast).

A protocol for total-order broadcast satisfies the following properties.

Validity

If a correct process, $p_{i}$ a-broadcasts a valid transaction $\mathsf{tx}$
according to $\mathbb{P}(\cdot,\cdot)$ (i.e., the validation predicate defined
in Section 2), then $p_{i}$ eventually a-delivers $\mathsf{tx}$ with an
overwhelming probability.

No duplication

No correct process a-delivers the same transaction $\mathsf{tx}$ more than
once.

Agreement

If a transaction $\mathsf{tx}$ is a-delivered by some correct process, then
with an overwhelming probability $\mathsf{tx}$ is eventually a-delivered by
every correct process.

Total order

Let $\mathsf{tx}_{1}$ and $\mathsf{tx}_{2}$ be any two transactions, and
suppose $p_{i}$ and $p_{j}$ are any two correct processes that a-deliver
$\mathsf{tx}_{1}$ and $\mathsf{tx}_{2}$. If $p_{i}$ a-delivers
$\mathsf{tx}_{1}$ before $\mathsf{tx}_{2}$, then with an overwhelming
probability, $p_{j}$ a-delivers $\mathsf{tx}_{1}$ before $\mathsf{tx}_{2}$.

##  3 Modeling Resources in Blockchain

In this section, we model resources, formalize their properties through the
abstraction of a _resource allocator_ , and state our threat assumptions. The
definition of a _resource allocator_ in this section is only syntactic;
security and liveness properties of the resource allocator are defined in
Section 4.

###### Definition 2 (Resource Budget).

A resource budget $r$ is a value in $\mathbb{N}$. At any given time, each
process $p_{i}$ has a resource budget $r_{i}$. In particular, there exists a
function $\textsl{Alloc}:\mathcal{P}\times\mathbb{N}\rightarrow\mathbb{N}$
that takes as input a process $p_{i}$ and a time step $t$, outputs the
resource budget of a process at time step $t$. We define $R$ to be the fixed
resource budget existing in the system.

The definition of a fixed resource budget and the resource allocation function
can be viewed as the sized setting and the resource pool definition in Lewis-
Pye and Roughgarden framework [23]. We note that the specification of the
resource budget varies depending on protocols; e.g., for PoW, we define the
budget to be a number of hash function evaluations per time step. We now
define _resource allocator_ , an abstraction that will allow us to reason
about different resources.

###### Definition 3 (Resource Allocator).

A resource allocator, RA, interacts with the processes through input events
(RA-commit, RA-validate) and output events (RA-assign, RA-is-committed):

  * •

RA-commit($p_{i},\textit{st},r$): At time step $t$, every process $p_{i}$ may
request a resource commitment $\pi$ from the resource allocator by invoking
RA-commit on inputs a state st and a resource budget $0\leq
r\leq\textsl{Alloc}(p_{i},t)$, i.e., $p_{i}$ does not RA-commit more resources
than it possesses. At the end of the activation period of $p_{i}$, the
resource allocator either assigns a resource commitment $\pi$ and a resource
budget $r$ to process $p_{i}$ through an
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)$ event or assigns an empty
value $\bot$ and _possibly_ a resource $r$ to $p_{i}$ through
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\bot)$.

  * •

RA-validate($p_{i},\textit{st},\pi$): Every process $p_{i}$ may validate a
resource commitment $\pi$ by invoking RA-validate on input a state, st, and a
resource commitment $\pi$. The resource allocator validates the resource
commitment $\pi$, through an event $\textsl{{RA}-is-
committed}(p_{i},\textit{st},b)$ event, with $b=\textsc{true}$ if the
commitment $\pi$ is a valid resource commitment for the state st or
$b=\textsc{false}$ otherwise.

A process triggers RA-commit to pledge its resources to a system, and it can
be assigned a resource commitment as a result to extend the blockchain. If the
resource commitment $\pi$ is included on-chain, then it must be _valid_ (i.e.,
RA-validate returns true) for the block to be accepted. Moreover, we assume
that all the events to and from the resource allocator happen within the same
time step. In particular, if a process $p_{i}$ RA-commits some resource budget
$r$ at time step $t$, at the end of the activation period for $p_{i}$ process
$p_{i}$ will receive either a resource commitment $\pi$ and $r$ or an empty
resource commitment value $\bot$ and $r$.

Resources can be classified into various types. In our model, these types can
be described as the interactions between processes and the resource allocator.
The following definition classifies different types of resources used in
existing blockchain protocols.

###### Definition 4 (Types of resource).

A resource can be classified as follows.

Virtual

A resource is _virtual_ when the resource allocator determines the resource
budget of all processes from the given blockchain state st. For a virtual
resource, we assume that there exists a function
$\textsl{StateAlloc}:\mathcal{P}\times\mathbb{C}\rightarrow\mathbb{N}$ that
takes as input a process $p_{i}$ and a blockchain $\mathcal{C}$ and outputs
the resource budget of $p_{i}$, and $p_{i}$ can invoke
$\textsl{{RA}-commit}(\cdot,\cdot,r)$ on an empty resource, $r=\bot$.

External

A resource is _external_ when a process must allocate the resource externally
with a budget $r\geq 0$ to invoke $\textsl{{RA}-commit}()$. For an external
resource, this commitment step is equivalent to giving RA access to the
external resource with the budget $r$. Moreover, we assume that processes
cannot lie about the resource budget $r$ and commit more than $r$.

Burnable

A resource is _burnable_ when a process $p$ can trigger _multiple_
$\textsl{{RA}-commit}(\cdot,\cdot,r)$ at a time step $t$, and it retrieves $r$
through $\textsl{{RA}-assign}(\cdot,\cdot,r,\cdot)$ at the end of the
activation period for $p_{i}$. For all committing events
$\textsl{{RA}-commit}(p_{i},\cdot,r_{i})$ from the same process $p_{i}$ that
occur within a time step $t$ , we require
$\sum_{r_{i}>0}r_{i}\leq\textsl{Alloc}(p_{i},t)$.

Reusable

A resource is _reusable_ when a process $p_{i}$ can use the same resource
budget $r\leq\textsl{Alloc}(p_{i},t)$ to trigger _infinitely many_
$\textsl{{RA}-commit}(\cdot,\cdot,r)$ at each time step $t$, and $p_{i}$ does
not need to retrieve $r$ from the output event RA-assign. Hence, for reusable
resources, we denote the value of $r$ in the output event
$\textsl{{RA}-assign}(\cdot,\cdot,r,\cdot)$ to be $\bot$.

###### Remark 1.

The assumption on external resources is natural because an _external_ resource
is inherently unforgeable; for instance, in PoW, processes cannot fake this
budget as it is the physical limit of the mining hardware. For resources like
storage, the resource is the physical hard drive, and $r$ can be thought of as
the capacity of the hard drive.

Failures. A process that follows its protocol during an execution is called
_correct_. On the other hand, a _faulty_ process may crash or deviate
arbitrarily from its specification, such processes are also called
_Byzantine_. We consider only Byzantine faults in this work. All Byzantine
processes are controlled by a probabilistic polynomial-time adversary,
$\mathcal{A}$; we write $p_{i}\in\mathcal{A}$ to denote that a Byzantine
process is controlled by $\mathcal{A}$. In this model, we require the
adversary to go through the same process of committing resources and getting
assigned resource commitments from the allocator. Since the allocator assigns
the commitment at the end of the time step, we require a minimum delay between
Byzantine processes to be one. We also note that this requirement is only for
definitional reasons and can be relaxed by assuming the network delay to be
zero for Byzantine processes. However, the concrete parameters on the
probability of getting assigned resource commitments for Byzantine processes
will need to be adjusted to reflect this assumption, and we leave this to
future work.

###### Definition 5 (Adversarial Resource Budget).

$R_{\mathcal{A}}$ is the maximum adversarial resource budget. For any time
step $t$, it holds that:
$\sum_{p_{i}\in\mathcal{A}}\textsl{Alloc}(p_{i},t)\leq R_{\mathcal{A}}$.

###### Definition 6 (Corruption).

At any time step $t$, an adversary $\mathcal{A}$ can allocate a resource
budget of $\textsl{Alloc}(p_{i},t)$ from $R_{\mathcal{A}}$ to corrupt a
process $p_{i}\in\mathcal{P}_{\leq t}$.

##  4 Resource-based Total-order Broadcast

unordered: set of transaction $\mathsf{tx}$ that has been received for
execution and ordering
$\textit{delivered}:$ set of transaction $\mathsf{tx}$ that has been executed
and ordered
$k$: common prefix parameter
$\mathcal{B}$: set of received blocks,
$B=(h,\overline{\mathsf{tx}},\pi,\sigma)$, initially containing
$B_{0}=(\bot,\overline{\mathsf{tx}},\bot,\bot)$
$\mathbb{C}$: set of valid blockchains derived from $\mathcal{B}$, initially
contains one chain $\mathcal{C}=[B_{0}]$
$\mathcal{C}_{\mathsf{local}}$: local selected blockchain
$B_{\mathsf{com}}$: a RA-committed block for $p_{i}$
At time step $t$, $r_{i}=\textsl{Alloc}(p_{i},t)$ if $r_{i}$ is _external_ ,
$r_{i}\leftarrow\bot$ if $r_{i}$ is _virtual_

Figure 1: Initial state of a correct process

In this section, we define an algorithm for the _resource-based longest-chain
total-order broadcast_ using a (_probabilistic_) _resource allocator_
$\textsl{RA}_{\mathsf{res}}$. We define various properties needed for a secure
resource allocator so that the generic algorithm correctly guarantees
properties of total-order broadcast. Then, we concretely define three
different resource allocators based on three types of resource: computation,
stake, and storage to inherently capture three popular (probabilistic)
blockchain protocols, namely, Nakamoto consensus, Ouroboros Praos, and
Filecoin’s consensus protocol.

###  4.1 Generic Resource-based Longest-chain Total-order Broadcast

uses
---
|  Resource allocator: $\textsl{RA}_{\mathsf{res}}$
|  Probabilistic reliable broadcast: gossip
|  Validation predicate: $\mathbb{P}(\cdot,\cdot)$
|  Random oracle: $H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$
|  Signature scheme: $\Sigma=(\textsl{Sign},\textsl{Verify})$
init
|  $\textsl{Extend}(\mathcal{C}=[B_{0}])$
upon a-$\textsl{broadcast}(\mathsf{tx})$ do
|  invoke gossip-$\textsl{broadcast}([\textsc{op},{\mathsf{tx}}])$
upon gossip-deliver $([\textsc{op},{\mathsf{tx}}])$ do
|  $\textit{unordered}\leftarrow\textit{unordered}\cup\\{\mathsf{tx}\\}$
upon gossip-deliver $([\textsc{request},{B}])$ do $\rhd$ Receive a request for
parents of $B$
|  if $\exists~{}\mathcal{C}\in\mathbb{C}$ s.t. $\mathcal{C}[-1]=B$ then
|  |  forall $B^{\prime}\in\mathcal{C}$ do $\rhd$ Re-send all parents of $B$
|  |  |  invoke gossip-broadcast $([\textsc{blk},{B^{\prime}}])$
upon gossip-deliver $([\textsc{blk},{B}])$ s.t.
$B=(h,\overline{\mathsf{tx}},\pi,$ $\sigma_{i}$) do
|  if
$\textsl{Verify}(p_{j},h||\overline{\mathsf{tx}}||\pi||\textit{sl}_{j},\sigma_{j})$
$\wedge~{}\exists~{}\mathcal{C}\in\mathbb{C}$ s.t. $H(\mathcal{C}[-1])=h$
$\wedge$ $\mathbb{P}(\mathcal{C},\overline{\mathsf{tx}})$ then
|  |  $\textit{st}\leftarrow(\mathcal{C},B)$
|  |  invoke $\textsl{{RA}-validate}(p_{i},\textit{st},\pi)$
|  else
|  |  invoke $\textsl{gossip}\text{-}\textsl{broadcast}([\textsc{request},{B}])$ $\rhd$ Request for parents of $B$
upon $\textsl{{RA}-is-committed}(p_{i},\textit{st},\textsc{true})$ s.t.
$\textit{st}=(\mathcal{C},B)$ do
|  $\mathcal{B}\leftarrow\mathcal{B}\cup\\{B\\}$
|  if $|\mathcal{C}|>|\mathcal{C}_{\mathsf{local}}|$ then
|  |  $\mathcal{C}_{\mathsf{local}}\leftarrow\mathcal{C}$ $\rhd$ Update the local blockchain
|  |  $\textsl{Extend}(\mathcal{C}_{\mathsf{local}})$
upon $\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)$ s.t.
$\textit{st}=(\mathcal{C},B=(h,\overline{\mathsf{tx}},\pi,\bot)),\pi\neq\bot$
do
|  $\sigma_{i}\leftarrow\textsl{Sign}(p_{i},h||\overline{\mathsf{tx}}||\pi)$
|  $B\leftarrow(h,\overline{\mathsf{tx}},\pi,$$\sigma_{i}$)
|  if $r_{i}$ is _burnable_ then
|  |  $r_{i}\leftarrow r_{i}+r$
|  invoke gossip-broadcast $([\textsc{blk},{B}])$
upon $\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)$ s.t. $\pi=\bot$ do
|  if $r$ is _burnable_ then
|  |  $r_{i}\leftarrow r$
|  $\textsl{Extend}(\mathcal{C}_{\mathsf{local}})$
upon a-deliver $([\textsc{op},{\mathsf{tx}}])$ do
|  $\textit{delivered}\leftarrow\textit{delivered}\cup\\{\mathsf{tx}\\}$
function $\textsl{Extend}(\mathcal{C}_{\mathsf{local}})$
|  forall $\mathsf{tx}\in\mathcal{C}_{\mathsf{local}}[:-k]$ $\wedge$
$\mathsf{tx}\notin\textit{delivered}$ do
|  |  output a-deliver$([\textsc{op},{\mathsf{tx}}])$ $\rhd$ Deliver all transactions in the common prefix
|  |  $\textit{unordered}\leftarrow\textit{unordered}\setminus\\{\mathsf{tx}\\}$
|  $h\leftarrow H(\mathcal{C}_{\mathsf{local}}[-1])$
|  select a list of transactions $\overline{\mathsf{tx}}$ from unordered such
that $\mathbb{P}(\mathcal{C},\overline{\mathsf{tx}})=\textsc{true}$
|  $B_{\mathsf{com}}\leftarrow(h,\overline{\mathsf{tx}},\bot,\bot)$
|  invoke
$\textsl{{RA}-commit}(p_{i},(\mathcal{C}_{\mathsf{local}},B_{\mathsf{com}}),r_{i})$
|  if $r$ is _burnable_ then
|  |  $r_{i}\leftarrow 0$
Algorithm 1 Resource-based longest-chain total-order broadcast (process
$p_{i}$).

A protocol for resource-based longest-chain total-order broadcast using
$\textsl{RA}_{\mathsf{res}}$ allows any process $p_{i}$ to _broadcast_
transactions by invoking $\textsl{a-broadcast}(\mathsf{tx})$ and to _deliver_
those that are valid (according to a validation predicate
$\mathbb{P}(\cdot,\cdot)$ and the local chain, $\mathcal{C}_{\mathsf{local}}$)
through an $\textsl{a-deliver}(\mathsf{tx})$ event. Delivered transactions are
_totally ordered_ and stored in a list, delivered, by every process.

In particular, when a process $p_{i}$ a-broadcasts a transaction, this is
gossiped to every process, and eventually every correct process gossip-
delivers it and stores it in a set unordered. Every stored transaction is then
considered by $p_{i}$.

At any given time, a process may receive new blocks from other processes. Any
process $p_{i}$ can validate the block by invoking RA-validate and RA-assigned
resource commitment to a process $p_{j}$ by $\textsl{RA}_{\mathsf{res}}$. Once
the resource commitment is validated, the process verifies other components of
the block such as signature and transactions and store new blocks in
$\mathcal{B}$. Also, if a block $B$ received by other processes does not have
a parent (L1), the process can trigger a request message to pull the
blockchain $\mathcal{C}$ with $B$ as the tip from other processes. Upon
receiving this request message, other processes re-broadcast every blocks in
$\mathcal{C}$ with $B$ as the tip (L1-L1). This step is an oversimplified and
inefficient version of how blockchain nodes synchronize the chain with others.
The goal is to demonstrate that it is feasible to obtain old blocks from other
processes.

At any given time, a correct process adopts the longest chain to its knowledge
as its local chain $\mathcal{C}_{\mathsf{local}}$, and extends with a block
$B_{\mathsf{com}}$ it wishes to order at the last block of its local chain
$\mathcal{C}_{\mathsf{local}}$. Observe that the Extend function in Algorithm
1 captures the operation of creating new blocks, usually called _mining_ , in
blockchain protocols and we refer to the processes in charge of creating
blocks as _miners_ or _validators_ , interchangeably.

In our model, we abstract this _extending_ operation as the interaction
between the processes and the resource allocator $\textsl{RA}_{\mathsf{res}}$.
Namely, to start extending, process $p_{i}$ needs to allocate a resource $r$
along with the proposed state $(\mathcal{C}_{\mathsf{local}},B_{\text{com}})$
to the resource allocator $\textsl{RA}_{\mathsf{res}}$ through
$\textsl{{RA}-commit}()$. Once $\textsl{RA}_{\mathsf{res}}$ $\textsl{assign}s$
a resource commitment $\pi$, $p_{i}$ attaches $\pi$ to the block and gossips
the block to other processes. The details of this interaction differ depending
on the type of resource and are left for the next subsections. Figure 1
specifies all data structures maintained by a process, and the code for a
process is presented in Algorithm 1.

For Algorithm 1 to satisfy the properties of total-order broadcast, the
generic resource allocator needs to satisfy various properties, and we define
those properties as follows.

###### Definition 7 (Secure Resource Allocator).

A resource allocator $R$ is secure if it satisfies the following properties:

Liveness

At a time step $t$, if a process $p_{i}$ invokes
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ with a state st and a resource
budget $r$ then $R$ issues either
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)$ or
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\bot)$ during time step $t$.

Validity

If resource commitment $\pi$ is a valid resource commitment
$(i.e.,\pi\neq\bot)$ contained in an output event
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)$, then any process $p_{j}$ can
invoke $\textsl{{RA}-validate}(p_{j},\textit{st},\pi)$. The resource allocator
$R$ outputs $\textsl{{RA}-is-committed}(p_{j},\textit{st},b)$ with
$b=\textsc{true}$.

Use-Once

At any time step $t$, for any states st, $\textit{st}_{1}$, $\textit{st}_{2}$,
any resource budget $r$, $r_{1},r_{2}\in\mathbb{N}$ such that $r_{1}+r_{2}=r$,
the probability that RA responds with RA-assign$(p_{i},\textit{st},r,\pi)$
with $\pi\neq\bot$ after $\textsl{{RA}-commit}(p_{i},\textit{st},r)$ is
_greater or equal_ to the probability that RA responds _at least one_ RA-
assign$(p_{i},\textit{st}_{i},r_{i},\pi)$ for $i\in\\{1,2\\}$ with
$\pi\neq\bot$ after _two_ $\textsl{{RA}-commit}(p_{i},\textit{st}_{1},r_{1})$
and $\textsl{{RA}-commit}(p_{i},\textit{st}_{2},r_{2})$.

For a _reusable resource_ , at any time step $t$, a resource budget $r$, a
state st and upon potentially multiple repeated
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ from the same process $p_{i}$, if
RA responds with $\textsl{{RA}-assigns}(p_{i},\textit{st},r,\pi)$, then $\pi$
is the same for every RA-commit events output by RA.

Unforgeability

No adversary can produce a resource commitment $\pi$ such that $\pi$ has not
been previously RA-assigned by RA and, upon RA-validate($p_{i},$
$\textit{st},\pi$), RA triggers RA-is-
committed($p_{i},\textit{st},\textsc{true})$, for some state st and some
process $p_{i}$.

Honest-Majority Assignment

At each time step, we denote with ${\varrho}_{H}$ and
${\varrho}_{\mathcal{A}}$ the probabilities that at least one correct process
and one Byzantine process, respectively, obtain a valid resource commitment
for each RA-commit. More formally, for every time step $t$, we define:

$\begin{split}{\varrho}_{\mathcal{A}}&=\Pr[\exists\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)~{}\text{such
that}~{}\pi\neq\bot\wedge p_{i}\in\mathcal{A}],\\\
{\varrho}_{H}&=\Pr[\exists\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)~{}\text{such
that}~{}\pi\neq\bot\wedge p_{i}\notin\mathcal{A}].\end{split}$

Then we require that:

$~{}{\varrho}_{\mathcal{A}}<\frac{1}{\Delta-1+1/{\varrho}_{H}}.$ (1)

The _liveness_ property aims to capture the mining process in permissionless
PoW blockchains and ensure that if processes keep committing resources,
_eventually_ one process will get assigned the resource commitment to extend
the blockchain.

The _validity_ property guarantees that a resource commitment can always be
verified by any process $p_{i}$ by triggering at any point RA-validate. This
property captures the fact that any participant can efficiently verify, for
example, the validity of the solution to the computational puzzle in PoW
protocols or the evaluation of the verifiable random function in PoS
protocols.

The _use-once_ property prevents processes from increasing the probability of
getting assigned the resource commitment either by committing several times,
splitting the resource budget and then committing all the split amounts at
different states or by committing a smaller resource budget. Intuitively, the
_use-once_ property also implies that the property holds for any integer
partition of $r$ (i.e., $r=\sum_{r_{i}>0}{r_{i}}$). Moreover, the use-once
property also implies that our model mainly focuses on probabilistic protocols
as we do not aim to bypass the lower bound established in [23], namely, there
is no deterministic protocol in _permissionless_ setting that solves
consensus. On the other hand, we believe that applying our model to
_permissioned_ blockchains with PoS, e.g., Tendermint [6], can be interesting
future work.

The _unforgeability_ property ensures that no process $p_{i}$ can produce a
valid resource commitment $\pi$ that has not been previously RA-assigned by
the resource allocator.

Finally, the _honest-majority assignment_ implies that despite the network
delay, correct processes will have a higher probability of getting assigned
the resource commitment at each time step. eq. 1 was established by Gaži  _et
al._ [18], and it takes into account that honest blocks may get discarded due
to the network delay $\Delta$.

Security Analysis. With the defined properties of a secure allocator, our
model is equivalent to the idealized model introduced by Gaži  _et al._ [18].
Therefore, their result also holds for our protocol, and we present them in
our model as follows.

###### Lemma 1 ([18]).

Algorithm 1 implemented with a secure resource allocator
$\textsl{RA}_{\mathsf{res}}$ satisfies the following properties:

Safety

For any time steps $t_{1}$ and $t_{2}$ with $t_{1}\leq t_{2}$, a common prefix
parameter $k$ and any local chain maintained by a correct process
$\mathcal{C}_{\mathsf{local}}$, it holds that
$\mathcal{C}_{\mathsf{local}}^{t_{1}}[:-k]\preceq\mathcal{C}_{\mathsf{local}}^{t_{2}}$
with an overwhelming probability.

Liveness

For a parameter $u$ and any time step $t$, let $\mathcal{C}_{\mathsf{local}}$
be the local chain maintained by a correct process, then there is at least one
new honest block in $\mathcal{C}^{t+u}/\mathcal{C}^{t}$ with an overwhelming
probability.

Intuitively, _safety_ implies that correct processes do not deliver different
blocks at the same height, while _liveness_ implies that every transaction is
eventually delivered by all correct processes. Using lemma 1 and properties of
a secure resource allocator, we conclude the following.

###### Theorem 2.

If $\textsl{RA}_{\mathsf{res}}$ is a _secure_ resource allocator, then
Algorithm 1 implements total-order broadcast.

###### Proof.

Observe that, since $\textsl{RA}_{\mathsf{res}}$ is a secure resource
allocator, it satisfies _use-once_ property. Therefore, Byzantine processes
cannot amplify the probability ${\varrho}_{\mathcal{A}}$ by repeatedly
triggering RA-commit() on reusable resources at the same time step.

For the _validity_ property, if a correct process $p_{i}$ a-broadcasts a
transaction $\mathsf{tx}$ (L1), $\mathsf{tx}$ is gossip-broadcast (L1) and,
after $\Delta$, every correct process gossip-delivers $\mathsf{tx}$ (L1) and
adds it to unordered (L1). Eventually, transaction $\mathsf{tx}$ is selected
by a correct process $p_{j}$ as part of a block $B$ (L1). Block $B$ is then
gossip-broadcast by $p_{j}$ (L1) and eventually, after $\Delta$, every correct
process gossip-delivers $B$ (L1), validates $x$ (L1), and validates the
resource commitment (L1). Observe that, because of the _unforgeability_
property of $\textsl{RA}_{\mathsf{res}}$, a valid resource commitment cannot
be produced except by the resource allocator. Observe that this last step is
possible through the validity property of $\textsl{RA}_{\mathsf{res}}$. The
proof then follows from Lemma 1.

_No duplication_ property follows from the algorithm; if a correct process
$p_{i}$ a-delivers a transaction $\mathsf{tx}$, $p_{i}$ adds $\mathsf{tx}$ to
delivered and condition at line L1 cannot be satisfied again.

For the _agreement_ property, let us assume that a correct process $p_{i}$
a-delivered a transaction $\mathsf{tx}$ buried at least $k$ blocks deep in its
adopted chain $\mathcal{C}$. Process $p_{i}$ a-delivers a transaction
$\mathsf{tx}$ when it _updates_ the local blockchain with the longest chain
$\mathcal{C}$ (L1), $\mathsf{tx}$ has not been a-delivered yet and
$\mathsf{tx}$ is part of the common prefix $\mathcal{C}[:-k]$ (L1). The
property then follows from Lemma 1; eventually every correct process
a-delivers transaction $x$, with an overwhelming probability.

Finally, for the _total order_ property, from the safety property of Lemma 1,
we know that correct processes do not deliver different blocks at the same
height. This means that at a given height, if two correct processes $p_{i}$
and $p_{j}$ a-delivered a block, then this block is the same for $p_{i}$ and
$p_{j}$ with an overwhelming probability. Moreover, since a block is
identified by its hash, due to the collision-resistance property of
$H(\cdot)$, it also implies that the set and order of transactions included in
the block are the same for every correct process. So, if process $p_{i}$
a-delivers transaction $\mathsf{tx}_{1}$ before $\mathsf{tx}_{2}$, then either
$\mathsf{tx}_{1}$ and $\mathsf{tx}_{2}$ are in the same block $B$ with
$\mathsf{tx}_{1}$ appearing before $\mathsf{tx}_{2}$ or they are in different
blocks $B_{1}$ and $B_{2}$ such that $B_{2}$ appears in the chain after
$B_{1}$. The total-order property follows. ∎

###  4.2 Proof-of-Work Resource Allocator

In this part, we present the PoW allocator as a concrete instantiation of the
resource allocator for _burnable_ and _external_ resources.

Proof-of-Work Resource Allocator. The PoW resource allocator
$\textsl{RA}_{\mathsf{pow}}$ is parameterized by ${\varrho}$ which is the
default probability of getting assigned resource commitment for $r=1$.
$\textsl{RA}_{\mathsf{pow}}$ works as follows. Upon
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ by process $p_{i}$ with a valid
chain $\mathcal{C}$ with respect to $B_{0}$, $\textsl{RA}_{\mathsf{pow}}$
starts $r$ concurrent threads of $\textsl{Pow}()$ function which acts as a
biased coin with probability ${\varrho}$ of assigning the resource commitment.
Observe that, because computation is a _burnable_ and _external_ resource,
processes cannot lie on about the committed resource budget $r$. In
particular, Pow uniformly sample a value nonce in $\\{0,1\\}^{\lambda}$ and
either returns $\textit{nonce}\in\\{0,1\\}^{\lambda}$ or $\bot$. If nonce is
the returned value in $\\{0,1\\}^{\lambda}$, then $\textsl{RA}_{\mathsf{pow}}$
assigns it as the resource commitment to $p_{i}$, otherwise it RA-assigns
$\bot$ to $p_{i}$. If the committed chain $\mathcal{C}$ is not valid, then
$\textsl{RA}_{\mathsf{pow}}$ RA-assigns $\bot$ to $p_{i}$. Validation of the
resource commitment can be done by any process $p_{j}$ through RA-validate;
the resource allocator $\textsl{RA}_{\mathsf{pow}}$ returns either true or
false, depending on the validity of the resource commitment. We implement the
resource allocator $\textsl{RA}_{\mathsf{pow}}$ in Algorithm 2 and obtain the
following lemma and theorem.

state
---
|  $B_{0}$: Genesis block
|  ${\varrho}$: Default probability of getting assigned resource commitment on
_one_ resource
uses
|  Random oracle: $H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$
upon $\textsl{{RA}-commit}(p_{i},\textit{st},r)$ s.t.
$\textit{st}=(\mathcal{C},B),B=(h,\overline{\mathsf{tx}},\bot,\bot)$ do
|  if $\mathcal{C}$ is valid $\wedge~{}H(\mathcal{C}[-1])=h$ then
|  |  start $r$ concurrent threads with $\textit{nonce}_{j}=\textsl{Pow}(p_{i},\textit{st})$ for $j\in\\{0,\dots,r-1\\}$
|  |  wait for all $r$ threads with $\textsl{Pow}(p_{i},\textit{st})$ for $j\in\\{0,\dots,r-1\\}$ to finish
|  |  if $\exists~{}\textit{nonce}_{j}\neq\bot$ then
|  |  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},r,nonce_{j})$
|  |  else
|  |  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},r,\bot)$
|  else
|  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},r,\bot)$
upon $\textsl{{RA}-validate}(p_{i},\textit{st},\pi)$ s.t.
$\textit{st}=(\mathcal{C},B),B=(h,\overline{\mathsf{tx}},\pi,\sigma),\pi=\textit{nonce}$
do
|  $\textit{b}\leftarrow
H(h||\overline{x}||\textit{nonce})\stackrel{{\scriptstyle?}}{{\leq}}{\varrho}\cdot
2^{\lambda}$ $\wedge~{}\mathcal{C}$ is valid $\wedge~{}H(\mathcal{C}[-1])=h$
|  output RA-is-committed$(p_{i},\textit{st},\textit{b})$
function $\textsl{Pow}(p_{i},\textit{st})$ $\rhd$ With
$\textit{st}=(\mathcal{C},B)$ and $B=(h,\overline{x},\bot)$
|  $\textit{nonce}\xleftarrow{R}\\{0,1\\}^{\lambda}$
|  if $H(h||\overline{x}||\textit{nonce})\leq{\varrho}\cdot 2^{\lambda}$ then
|  |  return nonce
|  return $\bot$
Algorithm 2 Implementing PoW resource allocator, $\textsl{RA}_{\mathsf{pow}}$

###### Lemma 3.

Given the random oracle $H(\cdot)$, the default probability ${\varrho}$ of
getting assigned resource commitment on $r=1$, and the network delay $\Delta$,
there exists a value $R_{\mathcal{A}}$ such that the resource allocator
$\textsl{RA}_{\mathsf{pow}}$ implemented in Algorithm 2 is a secure resource
allocator.

###### Proof.

_Liveness_ property follows from Algorithm 2: upon
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ from process $p_{i}$, the resource
allocator $\textsl{RA}_{\mathsf{pow}}$ either _(i)_ has L2 satisfied and,
eventually, outputs $\textsl{{RA}-assign}(p_{i},\textit{st},r,\pi)$ with a
resource commitment $\pi$ to $p_{i}$ or outputs
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\bot)$ to $p_{i}$ or _(ii)_ if the
chain is invalid (L2), and then the allocator outputs
$\textsl{{RA}-assign}(p_{i},\textit{st},r,\bot)$ to $p_{i}$.

For the _validity_ property, observe that $\pi=\textit{nonce}$ is valid if and
only if there is a valid chain $\mathcal{C}$ with respect to the genesis block
$B_{0}$ such that the last block $B=\mathcal{C}[-1]$ contains $\pi$. Hence,
$\pi$ can be validated by any process $p_{j}$ through
$\textsl{{RA}-validate}(p_{j},(\mathcal{C},B^{*}),\pi)$;
$\textsl{RA}_{\mathsf{pow}}$ then checks if $H(B^{*})=h$ and
$H(h||\overline{x}||\textit{nonce})\leq{\varrho}\cdot 2^{\lambda}$ outputting
the same result at any process $p_{j}$.

The _use-once_ property immediately follows because of the burnable property
of the underlying resource (i.e., computation). Since
$\textsl{RA}_{\mathsf{pow}}$ triggers RA-assigns at the end of the the
activation period for $p_{i}$, we claim that for multiple
$\textsl{{RA}-commit}(p_{i},\cdot,r_{i})$ committed by $p_{i}$ at $t$, it is
equivalent to trigger $\textsl{{RA}-commit}(p_{i},\cdot,r)$ once for
$r=\textsl{Alloc}(p_{i},t)$. In particular, at the time step $t$, let
$\mathsf{Bad}$ be the event of not getting any resource commitment on all
$\textsl{{RA}-commit}(p_{i},\cdot,r_{i})$ for $r_{i}\in\\{r_{1},r_{2}\\}$ such
that $r=r_{1}+r_{2}$, then the probability of getting the resource commitment
is
$1-\Pr[\mathsf{Bad}]=1-(1-1+(1-{\varrho})^{r_{1}})(1-1+(1-{\varrho})^{r_{2}})=1-(1-{\varrho})^{r}$.

Since the resource allocator $\textsl{RA}_{\mathsf{pow}}$ uses the random
oracle $H$ (i.e., idealized hash function with no exploitable weaknesses), the
_unforgeability_ property follows from the observation that, in order to
produce a valid resource commitment, $p_{i}$ has no better way to find the
solution than trying many different queries to $H$. This implies that $p_{i}$
has the same probability of obtaining a valid local resource commitment as it
would have by RA-committing to the resource allocator.

For the _honest-majority assignment_ we recall that ${\varrho}_{H}$ and
${\varrho}_{\mathcal{A}}$ are the probabilities that at least one correct
process and one Byzantine process get the resource commitment after one RA-
commit, respectively. In our model, it is not difficult to see that
${\varrho}_{H}=1-(1-{\varrho})^{R-R_{\mathcal{A}}}$ and
${\varrho}_{\mathcal{A}}=1-(1-{\varrho})^{R_{\mathcal{A}}}$. Therefore, one
can easily derive the amount of resource $R_{\mathcal{A}}$ such that
${\varrho}_{\mathcal{A}}<\frac{1}{\Delta-1+1/{\varrho}_{H}}$. ∎

###### Theorem 4.

Algorithm 1 with the secure resource allocator $\textsl{RA}_{\mathsf{pow}}$
implements total-order broadcast.

###### Proof.

From Theorem 2 and Lemma 3, it follows that, since
$\textsl{RA}_{\mathsf{pow}}$ is a secure resource allocator, then Algorithm 1
with $\textsl{RA}_{\mathsf{pow}}$ implements total-order broadcast. ∎

###  4.3 Proof-of-Stake Resource Allocator

The resource in PoS protocols is the stake of each process, and stake is a
_virtual_ and _reusable_ resource. In those protocols, the probability of a
process $p_{i}$ being assigned a resource commitment is proportional to its
stake in the system. In this part, we focus on Ouroboros Praos [9] for our
formalization. Before presenting the PoS resource allocator as a concrete
instance of a resource allocator for _reusable_ and _virtual_ resources, we
need to introduce additional considerations and definitions.

Reusable Resources. By definition, a reusable resource allows processes to
repeatedly trigger RA-commit in the same time step using the same resource.
Hence, if RA does not satisfy _use-once_ property and assigns a resource
commitment randomly, then every time a process $p_{i}$ triggers RA-commit,
process $p_{i}$ might end up with a different result. For this reason, a naïve
implementation of the resource allocator for reusable resources would allow an
adversary to amplify the probability of getting assigned a resource commitment
(i.e., ${\varrho}_{\mathcal{A}}$) by repeatedly invoking RA-commit using the
same resource, i.e., in a grinding attack [3] at the same time step. Hence,
for _probabilistic_ blockchain protocols, to cope with this problem, one needs
to ensure that the allocator satisfies _use-once_ property. In particular,
from designs of PoS protocols like Snow White [8] and Ouroboros Praos [9],
three commonly used approaches to enforce _use-once_ property are:

$(R1)$ Explicit Time Slots

The first mechanism to enforcing _use-once_ property is to index the resource
by time slots. Protocols like Ouroboros Praos [9] and Snow White [8] require
processes to have synchronized clocks to explicitly track time slots and
epochs to ensure that each process derives a deterministic leader selection
result from the same state.

$(R2)$ Leader Selection from the Common Prefix

This mechanism requires correct processes to extract the set of potential
leaders from the common prefix. In particular, the common prefix is a
shortened local longest chain that is with overwhelming probability the same
for all correct processes. This approach allows them to share the same view of
potential leaders.

$(R3)$ Deterministic and Trustworthy Source of Randomness

The source of randomness has to be trustworthy to ensure a fair leader
election and to defend against an adaptive adversary that might corrupt
processes predicted to be leaders for the upcoming time slots. In addition,
the source of randomness has to be deterministic for each time slot and chain
state in order to prevent the previously mentioned grinding attack. Hence,
popular Proof-of-Stake blockchain protocols often rely on sophisticated
protocols to produce randomness securely.

Slot and Epoch. An _epoch_ $e$ is a set of $q$ adjacent time slot
$S=\\{\textit{sl}_{0},\dots,\textit{sl}_{q-1}\\}$. In practice, slot sl
consists of a sufficient number of time steps so that discrepancies between
processes’ clocks are insignificant, and processes advance the slot at the
same speed. In our model, we simplify this bookkeeping by requiring the
allocator to maintain the slot and epoch.

Stake Distribution. The _stake distribution_ at a time step $t$ is
$\mathbb{S}_{\mathsf{stake}}^{t}=\\{(p_{1},r_{1}),\dots\\}$ with $r_{i}\geq
0$, specifies the amount of stake owned by each process
$p_{i}\in\mathcal{P}_{\leq t}$. We denote $\mathbb{S}_{\mathsf{stake}}^{e}$
the stake distribution at the beginning of epoch $e$. The stake distribution
$\mathbb{S}_{\mathsf{stake}}^{e}$ can be obtained from
$\textsl{StateAlloc}(\mathcal{C}[0:\textit{sl}],p_{i})$ for $\textit{sl}\leq
e\cdot q$ for each $p_{i}\in\mathcal{P}_{\leq t}$.

###### Definition 8 (Leader Selection Process).

A _leader selection process_ $(\mathcal{D},F)$ with respect to a stake
distribution $\mathbb{S}_{\mathsf{stake}}=\\{(p_{1},r_{1}),\dots\\}$ is a pair
consisting of a distribution $\mathcal{D}$ and a deterministic function ${F}$.
When $\rho\xleftarrow{R}\mathcal{D}$, for all $sl\in\mathbb{N}$,
$F(\mathbb{S}_{\mathsf{stake}},sl;\rho)$ outputs process $p_{i}$ with
probability $1-(1-{\varrho})^{r_{i}}$ where ${\varrho}$ is the probability of
assigning resource commitment for $r=1$ for a given slot.

state
---
|  $B_{0}$: Genesis block
|  $\mathcal{D}$ : Distribution
|  $F$ : Leader selection function
|  sl : Current slot, initially $\textit{sl}=0$
|  $e$ : Current epoch, initially $e=0$
|  $k$ : common prefix parameter
|  $q$ : number of slots in an epoch, initially $q=16\cdot k$
|  $T$ : set of assigned resource commitments, initially empty
uses
|  Random oracle: $H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$
upon $\textsl{{RA}-commit}(p_{i},\textit{st},r_{i})$ s.t.
$\textit{st}=(\mathcal{C},B)$, $B=(h,\overline{\mathsf{tx}},\bot,\bot)$ do
|  if $\mathcal{C}$ is valid $\wedge~{}H(\mathcal{C}[-1])=h$ then
|  |  obtain $\mathcal{C}_{\mathsf{prefix}}$ by pruning all blocks with slot $>(e-2)\cdot q$, from $\mathcal{C}$
|  |  if $\mathcal{C}_{\mathsf{prefix}}=\emptyset$ do
|  |  |  $\mathcal{C}_{\mathsf{prefix}}\leftarrow[B_{0}]$
|  |  if $\exists(p_{i},\mathcal{C}_{\mathsf{prefix}},\rho^{*},\textit{sl})\in T$ then $\rhd$ Queried before
|  |  |  $\rho\leftarrow\rho^{*}$
|  |  else
|  |  |  $\rho\xleftarrow{R}\mathcal{D}$ $\rhd$ Sample a fresh randomness
|  |  |  $T\leftarrow T\cup\\{(p_{i},\mathcal{C}_{\mathsf{prefix}},\rho,\textit{sl})\\}$ $\rhd$ Update $T$
|  |  obtain the stake distribution $\mathbb{S}_{\mathsf{stake}}^{e-2}$ from $\mathcal{C}_{\mathsf{prefix}}$ $\rhd$ Evaluate $\textsl{StateAlloc}(\cdot,\cdot)$
|  |  $p_{j}\leftarrow F(\mathbb{S}_{\mathsf{stake}}^{e-2},\textit{sl};\rho)$
|  |  if $p_{i}=p_{j}$ then
|  |  |  $\pi\leftarrow(p_{i},\rho,\textit{sl})$
|  |  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\pi)$
|  |  else
|  |  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$
|  else
|  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$
upon $\textsl{{RA}-validate}(p_{i},\textit{st},\pi)$ s.t.
$\textit{st}=(\mathcal{C},B),B=(h,\overline{\mathsf{tx}},\pi,\sigma),\pi=(p_{j},\rho,\textit{sl})$
do
|  obtain $\mathcal{C}_{\mathsf{prefix}}$ by pruning all blocks with slot
$>(e-2)\cdot q$, from $\mathcal{C}$
|  if $\mathcal{C}_{\mathsf{prefix}}=\emptyset$ do
|  |  $\mathcal{C}_{\mathsf{prefix}}\leftarrow[B_{0}]$
|  if $\exists(p_{i},\mathcal{C}_{\mathsf{prefix}},\rho,\textit{sl})\in T$
then $\rhd$ Queried before
|  |  obtain the stake distribution $\mathbb{S}_{\mathsf{stake}}^{e-2}$ from $\mathcal{C}_{\mathsf{prefix}}$
|  |  $p_{j}^{*}\leftarrow F(\mathbb{S}_{\mathsf{stake}}^{e-2},\textit{sl};\rho)$
|  |  $\textit{b}\leftarrow p_{i}\stackrel{{\scriptstyle?}}{{=}}p_{j}^{*}$ $\wedge~{}\mathcal{C}$ is valid $\wedge~{}H(\mathcal{C}[-1])=h$
|  |  output RA-is-committed$(p_{i},\textit{st},\textit{b})$
|  else
|  |  output RA-is-committed$(p_{i},\textit{st},\textsc{false})$
upon Timeout do $\rhd$ Increment slot
|  $\textit{sl}\leftarrow\textit{sl}+1$
|  if $\textit{sl}\mod q=0$ then $\rhd$ Increment epoch
|  |  $e\leftarrow e+1$
|  starttimer()
Algorithm 3 Implementing PoS Resource Allocator, $\textsl{RA}_{\mathsf{pos}}$

Proof-of-Stake Resource Allocator. The Proof-of-Stake resource allocator
$\textsl{RA}_{\mathsf{pos}}$ with the leader selection process
$(\mathcal{D},F)$ works as follows. First, we require that
$\textsl{RA}_{\mathsf{pos}}$ keeps track of the current epoch and time slot to
correctly assign the resource commitment to process $p_{i}$ for the current
slot. $\textsl{RA}_{\mathsf{pos}}$ keeps track of the slot through Timeout
triggered by the $\textsl{starttimer}()$ event. This approach is to enforce
the first requirement of explicit time slots (R1). Secondly, upon
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ by process $p_{i}$ with a valid
state st in slot sl, $\textsl{RA}_{\mathsf{pos}}$ first checks if a random
value $\rho\in\mathcal{D}$ for ($p_{i}$,st,sl) has been previously sampled; if
so, then $\textsl{RA}_{\mathsf{pos}}$ picks it; otherwise, a fresh random
value is sampled. This requirement ensures a deterministic and trustworthy
source of randomness (R3). Then, $\textsl{RA}_{\mathsf{pos}}$ obtains the
stake distribution of two epochs before, $\mathbb{S}^{e-2}_{\text{stake}}$
from st. This ensures a leader selection from the common prefix (R2). The
resource allocator $\textsl{RA}_{\mathsf{pos}}$ uses
$\mathbb{S}^{e-2}_{\text{stake}}$ together with the sampled randomness as
input to the leader selection function $F$ to check if $p_{i}$ is selected for
the slot sl. If this is the case, then $\textsl{RA}_{\mathsf{pos}}$ assigns
the resource commitment to $p_{i}$, otherwise it assigns $\bot$. If the
committed chain $\mathcal{C}$ is not valid, then $\textsl{RA}_{\mathsf{pos}}$
assigns $\bot$ to $p_{i}$. A validation of the resource commitment can be done
by any process $p_{j}$ through RA-validate; the resource allocator
$\textsl{RA}_{\mathsf{pos}}$ returns either true or false, depending on the
validity of the resource commitment. Finally, the PoS resource allocator is
presented in Algorithm 3, and we conclude the following lemma and theorem.

###### Remark 2.

In practice, the randomness generation can be instantiated using verifiable
random function [12], multiparty coin-tossing [21] protocol, or a random
beacon [13]. However, Algorithm 3 aims to show the distinction between
_external_ and _virtual_ resources.

###### Lemma 5.

Given the random oracle $H(\cdot)$, the leader selection process
($\mathcal{D}$, F) parameterized by the default probability ${\varrho}$, and
the network delay $\Delta$, there exists a value $R_{\mathcal{A}}$ such that
the resource allocator $\textsl{RA}_{\mathsf{pos}}$ implemented in Algorithm 3
is a secure resource allocator.

###### Proof.

_Liveness_ property follows from the algorithm: upon
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ from process $p_{i}$, the resource
allocator $\textsl{RA}_{\mathsf{pos}}$ either _(i)_ has L3 satisfied and,
eventually, outputs $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\pi)$ with a
resource commitment $\pi$ to $p_{i}$, or outputs
$\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$ to $p_{i}$ or _(ii)_ if
the chain invalid (L3), the allocator outputs
$\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$ to $p_{i}$.

For the _validity_ property, observe that $\pi=(p_{i},\rho,\textit{sl})$ is
valid if and only if $p_{i}$ is a leader for sl. If $p_{i}$ is a leader for
sl, then in $T$ there must be the random value $\rho$ previously sampled for
$p_{i}$ (L3). This means that $F$ evaluated on $\rho$ will output again
$p_{i}$. Hence, $\pi$ can be validated by any process $p_{j}$ through
$\textsl{{RA}-validate}(p_{j},\textit{st},\pi)$; $\textsl{RA}_{\mathsf{pos}}$
checks if $\pi\in T$ outputting the same result to $p_{j}$.

The _Use-once_ property follows because, in our model,
$\textsl{RA}_{\mathsf{pos}}$ keeps track of previous RA-commit from $p_{i}$
along with the time slots and states. Moreover, the choice of
$\mathsf{prob}_{i}$ is stake-invariant, and it ensures that an adversary
cannot increase its probability of being elected leader by dividing its stake
into multiple identities. The proof for this is identical to the proof in
lemma 3. In practice, this property is enforced by the deterministic outputs
of VRF and Hash function along with slot number and the common chain prefix as
input.

The _unforgeability_ property follows from the fact that any resource
commitment produced by $\textsl{RA}_{\mathsf{pos}}$ is stored by the resource
allocator in a set $T$ of assigned resource commitments (L3). Hence, it is not
possible for any process $p_{i}$ to produce a valid resource commitment that
is not in $T$. In practice, this property is guaranteed by the uniqueness
property of verifiable random functions or the collision-resistant property of
hash functions.

For the _honest-majority assignment_ property, it is not difficult to see that
we can derive ${\varrho}_{H}$ and ${\varrho}_{\mathcal{A}}$ from $R$ and
$R_{\mathcal{A}}$. In particular, ${\varrho}_{H}=1-(1-{\varrho})^{R-R_{A}}$
and ${\varrho}_{\mathcal{A}}\approx 1-(1-{\varrho})^{R_{A}}$. Here we note
that the adversary can slightly increase ${\varrho}_{\mathcal{A}}$ by
committing to shorter chains. However, it also means that the adversary will
fall behind as it has to extend a much shorter chain than the current local
chain maintained by correct processes, and we assume the adversary has no
reason to do so. Hence, we consider
${\varrho}_{\mathcal{A}}=1-(1-{\varrho})^{R_{A}}$. Thus, we can derive $R_{A}$
so that ${\varrho}_{\mathcal{A}}<\frac{1}{\Delta-1+1/{\varrho}_{H}}$. ∎

###### Theorem 6.

Algorithm 1 with the secure resource allocator $\textsl{RA}_{\mathsf{pos}}$
implements total-order broadcast.

###### Proof.

From Theorem 2 and Lemma 5, it follows that, since
$\textsl{RA}_{\mathsf{pos}}$ is a secure resource allocator, then Algorithm 1
with $\textsl{RA}_{\mathsf{pos}}$ implements total-order broadcast. ∎

##  5 Proof-of-Space Resource Allocator

In this subsection, we consider a Proof-of-Storage allocator inspired by
Filecoin [22], a blockchain protocol based on storage. Storage is an example
of _external_ and _reusable_ resources.

Overview of Filecoin. In the Filecoin protocol, participants get elected to
write new blocks proportionally to the amount of storage they pledge to the
blockchain. Since storage can be reused, an adversary could pledge multiple
time the same storage. Hence, Filecoin protocol asks that participants
periodically post cryptographic proofs of their storage to the blockchain, to
ensure that the resources that they pledge are still committed. If a miner
fails to prove their storage frequently, they are removed from the _power
table_ , i.e., the mapping from miners’ identity to their amount of storage,
and lose their right to create blocks. The maintenance of the power table thus
happens on top of the consensus protocol. The consensus protocol then uses the
power table to elect leaders, just like a PoS blockchain, except that
participants are weighted according to their storage instead of coins.

Filecoin uses a tipset model instead of the longest chain model, meaning that
a block can have more than one parent. This model is inspired by blockDAGs
[20], although in the tipset model all the blocks included in a tipset must
have the same set of parents (unlike blockDAGs). In this paper however, we are
interested in modeling resource allocators based on different resources and
regardless of the underlying consensus protocol. For this reason, we choose to
use a longest-chain protocol to model Filecoin as this ensures that we can
meaningfully compare all the protocols based on their underlying resource
rather than their fork-choice rule or consensus protocol.

In the following we discuss how to build the Proof-of-Storage resource
allocator based on Filecoin protocol in our model.

Resource budget. A _sector_ is the smallest unit of storage that a process can
commit. In our model, we define the resource budget $r$ controlled by each
process to be the number of sectors each process owns.

Filecoin implements the three approaches described in Section 4.3 to enforce
_use-once_ property of the resource allocator. Moreover, it also implements an
_external resource verification_ procedure to verify if the committed resource
is valid.

Explicit Time Slot. Similar to PoS protocols, Filecoin requires processes to
explicitly keep track of the time slot. Hence, in our model, we require the
resource allocator $\textsl{RA}_{\mathsf{space}}$ to maintain the time step
number sl explicitly and include it to be a part of the resource commitment.

###### Definition 9 (Storage Distribution).

The storage distribution
$\mathbb{S}_{\mathsf{space}}=\\{(p_{1},r_{1}),\dots\\}$, where $r_{i}\geq 0$,
specifies the amount of storage that each process pledged through sealing
transactions. We denote with $\mathbb{S}_{\mathsf{space}}^{\textit{sl}}$ the
storage distribution at the slot sl.

###### Definition 10 (Leader Selection Process).

A _leader selection process_ $(\mathcal{D},F)$ with respect to a storage
distribution $\mathbb{S}_{\mathsf{space}}=\\{(p_{1},r_{1}),\dots\\}$ is a pair
consisting of a distribution $\mathcal{D}$ and a deterministic function ${F}$.
When $\rho\xleftarrow{R}\mathcal{D}$, for all $sl\in\mathbb{N}$,
$F(\mathbb{S}_{\mathsf{space}},\textit{sl};\rho)$ outputs process $p_{i}$ with
probability $1-(1-{\varrho})^{r_{i}}$ where ${\varrho}$ is the probability
that a process gets assigned resource commitment with $r=1$ for a given slot.

###### Remark 3.

we note that in practice Filecoin uses a Poisson
sortition111https://spec.filecoin.io, Section 4.18.53.111 Running a leader
election, inspired by Algorand cryptographic sortition [19], to elect multiple
leaders. This means that a process will pseudorandomly generate a number using
its private keys and the value of its random number will determine how many
times it is elected leader. The smallest the random value is the more
elections it wins. The target values, i.e., the values that determine the
number of elections won, are chosen according to a Poisson distribution with
parameter $\small{\textsf{numberOfExpectedLeader}}\times\alpha$, i.e., the
number of elections won for a process with proportional resource $\alpha$
follows a Poisson distribution of parameter
$\small{\textsf{numberOfExpectedLeader}}\times\alpha$. If we are to translate
this election process to the case where only one leader is elected, we set
$\small{\textsf{numberOfExpectedLeader}}=1$ and then a process is elected if
it wins at least one election. As the Binomial distribution can be
approximated by Poisson, this is equivalent to using the probability above.

In addition to the leader selection process, Filecoin protocol also validates
the _external_ resources pledged by the leader. This validation is
accomplished by requiring the process $p_{i}$ to provide a cryptographic proof
showing the existence of a random data partition (e.g., Proof-of-Storage). The
randomness used for this challenge is generated through the use of Drand [13]
values and verifiable random functions. To simplify the protocol’s
description, similar to the PoS-based protocol, we rely on the resource
allocator to securely generate randomness for each slot. Moreover, we require
every process $p_{i}$ to commit $r$ indicating the number of partitions
$p_{i}$ stores. To capture the _external resource verification_ procedure used
in Filecoin, we introduce the following definition.

###### Definition 11 (External Resource Verification).

An _external resource verification_ procedure $(\mathcal{D},E)$ is a pair
consisting of a distribution $\mathcal{D}$ and a deterministic function ${E}$.
When $\rho\xleftarrow{R}\mathcal{D}$, for every $r$ and $r^{\prime}$ in
$\mathbb{N}$ with $r^{\prime}\geq r$, $E(r,r^{\prime};\rho)$ outputs true with
a probability $\displaystyle\frac{r}{r^{\prime}}$, if $r_{i}=0$ or
$r>r^{\prime}$, $E()$ outputs false for all $\rho\in\mathcal{D}$.

Proof-of-Storage Resource Allocator. Proof-of-Storage resource allocator
$\textsl{RA}_{\mathsf{space}}$ using the leader selection process $F()$ and
the external resource verification $E()$ works as follows. First, we require
that $\textsl{RA}_{\mathsf{space}}$ keeps track of the current time slot in
order to correctly assign the resource commitment to process $p_{i}$ for the
current slot. Resource allocator $\textsl{RA}_{\mathsf{space}}$ keeps track of
the slot through Timeout triggered by the $\textsl{starttimer}()$ event. This
approach implements the explicit time slot requirement (R1). Second, upon
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ by process $p_{i}$ with a valid
chain $\mathcal{C}$ in slot sl, $\textsl{RA}_{\mathsf{space}}$ first checks if
a randomness $\rho\in\mathcal{D}$ for st and sl has been previously sampled;
if so, then $\textsl{RA}_{\mathsf{space}}$ uses it for leader selection and
external resource verification. Otherwise, a fresh randomness is sampled. This
requirement ensures deterministic and trustworthy source of randomness (R3).
To ensure the leader selection from the common prefix (R2),
$\textsl{RA}_{\mathsf{space}}$ obtains the storage distribution
$\mathbb{S}_{\mathsf{space}}$ (i.e., the power table) only from blocks with
slot number less than $sl-k$. Finally, together with the sampled randomness,
$\textsl{RA}_{\mathsf{space}}$ uses $F()$ and $E()$ to check if $p_{i}$ is the
leader for the slot sl and if $p_{i}$ passes the external resource
verification. If both verifications pass then $\textsl{RA}_{\mathsf{space}}$
assigns the resource commitment to $p_{i}$, otherwise it assigns $\bot$. If
the committed chain $\mathcal{C}$ is not valid, then
$\textsl{RA}_{\mathsf{space}}$ assigns $\bot$ to $p_{i}$.

A validation of the resource commitment can be done by any process $p_{j}$
through RA-validate; the resource allocator $\textsl{RA}_{\mathsf{space}}$
returns either true or false, depending on the validity of the resource
commitment.

We implement the resource allocator $\textsl{RA}_{\mathsf{space}}$ in
Algorithm 4.

state:
---
|  $B_{0}$: Genesis block
|  $\mathcal{D}$ : Distribution
|  $F$ : Leader selection function
|  $E$ : External resource verification function
|  sl : Current time slot, initially $\textit{sl}=0$
|  $k$: Common prefix parameter
|  $T$ : Set of issued resource commitments, initially empty
uses:
|  Random oracle: $H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$
upon $\textsl{{RA}-commit}(p_{i},\textit{st},r)$ s.t.
$\textit{st}=(\mathcal{C},B)$, $B=(h,\overline{\mathsf{tx}},\bot,\bot)$ do:
|  if $\mathcal{C}$ is valid $\wedge~{}H(\mathcal{C}[-1])=h$ then
|  |  obtain $\mathcal{C}_{\mathsf{prefix}}$ by pruning all blocks with slot $>\textit{sl}-k$, from $\mathcal{C}$
|  |  if $\mathcal{C}_{\mathsf{prefix}}=\emptyset$ then
|  |  |  $\mathcal{C}_{\mathsf{prefix}}\leftarrow[B_{0}]$
|  |  if $\exists(p_{i},\mathcal{C}_{\mathsf{prefix}},\rho^{*},\textit{sl})\in T$ then $\rhd$ Queried before
|  |  |  $\rho\leftarrow\rho^{*}$
|  |  else
|  |  |  $\rho\xleftarrow{R}\mathcal{D}$ $\rhd$ Sample a fresh randomness
|  |  |  $T\leftarrow T\cup\\{(p_{i},\mathcal{C}_{\mathsf{prefix}},\rho,\textit{sl})\\}$ $\rhd$ Update $T$
|  |  obtain the storage distribution $\mathbb{S}_{\mathsf{space}}$ from $\mathcal{C}_{\mathsf{prefix}}$ $\rhd$ Evaluate $\textsl{StateAlloc}(\cdot,\cdot)$
|  |  $p_{j}\leftarrow F(\mathbb{S}_{\mathsf{space}},\textit{sl};\rho)$
|  |  $b\leftarrow E(r,\textsl{StateAlloc}(p_{i},\mathcal{C}_{\mathsf{prefix}});\rho)$ $\rhd$ Verify the existence of the external resource
|  |  if $p_{i}=p_{j}\wedge b=\textsc{true}$:
|  |  |  $\pi\leftarrow(p_{i},\rho,\textit{sl})$
|  |  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\pi)$
|  |  else
|  |  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$
|  else
|  |  output $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$
upon $\textsl{{RA}-validate}(p_{i},\textit{st},\pi)$ s.t.
$\textit{st}=(\mathcal{C},B),B=(h,\overline{\mathsf{tx}},\pi,\sigma),\pi=(p_{j},\rho,\textit{sl})$
do
|  obtain $\mathcal{C}_{\mathsf{prefix}}$ by pruning all blocks with slot
$>\textit{sl}-k$, from $\mathcal{C}$
|  if $\mathcal{C}_{\mathsf{prefix}}=\emptyset$ do
|  |  $\mathcal{C}_{\mathsf{prefix}}\leftarrow[B_{0}]$
|  if $\exists(p_{i},\mathcal{C}_{\mathsf{prefix}},\rho,\textit{sl})\in T$
then $\rhd$ Queried before
|  |  obtain the storage distribution $\mathbb{S}_{\mathsf{space}}$ from $\mathcal{C}_{\mathsf{prefix}}$ $\rhd$ Evaluate $\textsl{StateAlloc}(\cdot,\cdot)$
|  |  $p_{j}^{*}\leftarrow F(\mathbb{S}_{\mathsf{space}},\textit{sl};\rho)$
|  |  $\textit{b}\leftarrow p_{j}\stackrel{{\scriptstyle?}}{{=}}p_{j}^{*}$ $\wedge~{}\mathcal{C}$ is valid $\wedge~{}H(\mathcal{C}[-1])=h$
|  |  output RA-is-committed$(p_{i},\textit{st},\textit{b})$
|  else
|  |  output RA-is-committed$(p_{i},\textit{st},\textsc{false})$
upon Timeout do $\rhd$ Increment slot
|  $\textit{sl}\leftarrow\textit{sl}+1$
|  starttimer()
Algorithm 4 Implementing Proof-of-Storage resource allocator,
$\textsl{RA}_{\mathsf{space}}$

###### Lemma 7.

Given the random oracle $H(\cdot)$, the leader selection process
$(\mathcal{D},F)$ parameterized by the default probability ${\varrho}$, the
external resource verification $(\mathcal{D},E)$, and the network delay
$\Delta$, there exists a value $R_{\mathcal{A}}$ such that the resource
allocator $\textsl{RA}_{\mathsf{space}}$ implemented in Algorithm 4 is a
secure resource allocator.

###### Proof.

The _Liveness_ property follows from the algorithm: upon
$\textsl{{RA}-commit}(p_{i},\textit{st},r)$ from process $p_{i}$, the resource
allocator $\textsl{RA}_{\mathsf{space}}$ either _(i)_ has L4 satisfied and,
eventually, it outputs $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\pi)$ with
a resource commitment $\pi$ to $p_{i}$, or it outputs
$\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$ to $p_{i}$ either if the
external resource verification fails or if $p_{i}$ is not a leader for the
current slot (L4) or _(ii)_ if the chain is invalid (L4), the allocator
outputs $\textsl{{RA}-assign}(p_{i},\textit{st},\bot,\bot)$ to $p_{i}$.

For the _validity_ property, one can apply the same reasoning as in Lemma 5;
if $p_{i}$ is a leader for sl, then in $T$ there must be the random value
$\rho$ previously sampled for $p_{i}$ (L4). This means that $F$ evaluated on
$\rho$ will output again $p_{i}$. We note that Byzantine process $p$ with no
resource can trigger a commit, then uniformly choose $\rho$ later so that
$F()$ outputs $p$; however, this happens with a negligible probability for
sufficiently large $|\mathcal{D}|$. Hence, $\pi$ can be validated by any
process $p_{j}$ through $\textsl{{RA}-validate}(p_{j},B,\pi)$;
$\textsl{RA}_{\mathsf{space}}$ checks if $\pi\in T$ and it outputs the same
result to process $p_{j}$.

The _use-once_ property follows because, in our model,
$\textsl{RA}_{\mathsf{space}}$ keeps track of previous RA-commit from $p_{i}$
along with the time slots and states. Moreover, the choice of
$\mathsf{prob}_{i}$ ensures that an adversary cannot increase its probability
of being elected leader by dividing its storage into multiple identities. The
proof for this is identical to the proof in lemma 3.

The _unforgeability_ property can be proved in the same way as in Lemma 5.

For the _honest-majority assignment_ , due to the choice of probability
defined in definition 10, one can derive ${\varrho}_{H}$ and
${\varrho}_{\mathcal{A}}$ directly from $R$ and $R_{\mathcal{A}}$. In
particular, ${\varrho}_{H}=1-(1-{\varrho})^{R-R_{\mathcal{A}}}$ and
${\varrho}_{\mathcal{A}}\leq 1-(1-{\varrho})^{R_{A}}$. Observe that the
adversary can commit fewer resources than the pledged amount. However, due to
external resource verification $E()$, the probability of getting assigned a
resource commitment will be strictly lower. Therefore,
${\varrho}_{\mathcal{A}}$ is strictly less than or equal to
$1-(1-{\varrho})^{R_{A}}$; the equality occurs only when Byzantine processes
commit all resource budgets. Additionally, as in the proof of stake protocols,
we note that the adversary can slightly increase ${\varrho}_{\mathcal{A}}$ by
committing to shorter chains. However, in this case, this means that the
adversary will fall behind as it has to extend a much shorter chain than the
current local chain maintained by correct processes. Hence, we consider
${\varrho}_{\mathcal{A}}=1-(1-{\varrho})^{R_{A}}$. Thus, we can derive $R_{A}$
so that ${\varrho}_{\mathcal{A}}<\frac{1}{\Delta-1+1/{\varrho}_{H}}$. ∎

###### Theorem 8.

Algorithm 1 with the secure resource allocator $\textsl{RA}_{\mathsf{space}}$
implements total-order broadcast.

###### Proof.

From Theorem 2 and Lemma 7, it follows that, since
$\textsl{RA}_{\mathsf{space}}$ is a secure resource allocator, then Algorithm
1 with $\textsl{RA}_{\mathsf{space}}$ implements total-order broadcast. ∎

##  6 Trade-offs Between Different Resources

In this section, we describe various attacks against the resource-based total-
order broadcast. In particular, we demonstrate long-range attacks against
_virtual_ resources, and we discuss the incentive consideration that describes
the cost of launching attacks against _burnable_ and _reusable_ resources.

###  6.1 Virtual Resource vs External Resource: Long-Range Attacks

Long-range Attacks on Virtual Resources. Long-range attacks [10] (LRAs), also
sometimes called posterior-corruption attacks, can be mounted on any
blockchain based on a virtual resource (such as PoS) if the majority of the
set of active processes from an earlier slot becomes inactive in a later slot,
as they no longer have any stake left in the system. Formally, they can be
defined as follows:

###### Definition 12 (Virtual-Resource-Shifting Event).

A _Virtual-Resource-Shifting Event_ happens when there exist two values
$h_{0}$, $h_{1}$, and a set of processes $\mathcal{P_{\mathsf{maj}}}$ such
that:

  * •

Active at $h_{0}$: At height $h_{0}$, processes in
$\mathcal{P}_{\mathsf{maj}}$ control the majority of the total virtual
resource (i.e., $R$), namely:
${\sum_{p_{i}\in\mathcal{P}_{\mathsf{maj}}}(\textsl{StateAlloc}(p_{i},\mathcal{C}[0:h_{0}]))>R-R_{A}}$

  * •

Inactive at $h_{1}$: At height $h_{1}>h_{0}$, processes in
$\mathcal{P}_{\mathsf{maj}}$ control less virtual resources than the total
number of resources controlled by the adversary (i.e., $R_{\mathcal{A}}$):
${\sum_{p_{i}\in\mathcal{P}_{\mathsf{maj}}}(\textsl{StateAlloc}(p_{i},\mathcal{C}[0:h_{1}]))\leq
R_{\mathcal{A}}}$

If definition 12 is satisfied, then most processes in
$\mathcal{P}_{\mathsf{maj}}$ have released all or part of their resources by
height $h_{1}$, and the adversary has enough budget to corrupt all the active
processes in $\mathcal{P}_{\mathsf{maj}}$ since they are all inactive in the
present. The adversary could then use these processes to re-write the chain
from $\mathcal{C}[h_{0}]$ since with a virtual resource as no external
resource is needed to call the resource allocator. Furthermore, the _release
of resource_ from processes in $\mathcal{P}_{\mathsf{maj}}$ also happens on-
chain, e.g., in the case of PoS for a process to move from active to inactive,
it will spend its coins on-chain. An adversary re-writing the history of the
chain could simply omit these transactions such that all processes satisfying
definition 12 stay active in the alternative chain that the adversary is
writing. The attack proceeds as follows:

  1. 1.

When a virtual-resource-shifting event happens at the current height $h_{1}$,
$\mathcal{A}$ corrupts all processes in $\mathcal{P}_{\mathsf{maj}}$. Since
the total of resources controlled by these processes is less than
$R_{\mathcal{A}}$, $\mathcal{A}$ has enough budget to do so;

  2. 2.

$\mathcal{A}$ starts a new chain $\mathcal{C}^{*}$ at $\mathcal{C}[h_{0}]$. At
this height, $\mathcal{A}$ controls the majority of the virtual resource, and
because the resource allocator takes no further input apart from the state of
$\mathcal{C}[0:h_{0}]$, it assigns the resource commitment to $\mathcal{A}$
with high probability;

  3. 3.

$\mathcal{A}$ now controls all processes in $\mathcal{P}_{\mathsf{maj}}$ and
can alter the state of the chain such that the processes in
$\mathcal{P}_{\mathsf{maj}}$ never release their resource;

  4. 4.

The adversarial chain will grow at a faster rate and will _eventually_ become
longer than the honest chain because there is no network delay between
corrupted processes.

Long-range Attacks on External Resources. The strategy above does not work
with _external_ resources. Even if definition 12 holds, the adversary cannot
call the resource allocator by simply corrupting the processes $p_{i}$ as an
_external_ resources would be needed as input to the resource allocator (step
2 in the strategy above).

We formalize the implication of the long-range attack in the following lemma
and theorem.

###### Lemma 9 (Long-range Attack).

In a virtual-resource-based total-order broadcast (Algorithm 1), let
$\mathcal{C}_{\mathsf{local}}$ be the longest chain maintained by a correct
process, if a virtual-resource-shifting event occurs, then an adversary can
_eventually_ form a valid chain $\mathcal{C}^{*}$ that is longer than
$\mathcal{C}_{\mathsf{local}}$.

###### Proof.

If a virtual-resource-shifting event (definition 12) occurs, an adversary
$\mathcal{A}$ can corrupt all $p_{i}\in\mathcal{P}_{\mathsf{maj}}$ at height
$h_{1}$. Notice that $\mathcal{A}$ can do this because according to the threat
model defined in definition 6, $\mathcal{A}$ has enough resource budget to
corrupt all $p_{i}\in\mathcal{P}_{\mathsf{maj}}$.

Adversary $\mathcal{A}$ can start a new chain $\mathcal{C}^{*}$ at height
$h_{0}$ by requiring all the corrupted processes
$p_{i}\in\mathcal{P}_{\mathsf{maj}}$ to commit old states to
$\textsl{RA}_{\mathsf{pos}}$. Since the Byzantine processes control the
majority of the resources, the probability of Byzantine processes getting
assigned commitment is strictly higher than the probability of correct
processes getting assigned commitment; hence, the growth rate of
$\mathcal{C}^{*}$ is strictly higher than the growth rate of the honest chain
$\mathcal{C}_{\mathsf{local}}$; therefore, $\mathcal{C}^{*}$ will eventually
catch up and outgrow $\mathcal{C}_{\mathsf{local}}$ in terms of the length.

More concretely, to simplify our analysis, we also assume the network delay to
be $1$ (i.e., $\Delta=1$) between correct processes. We recall that
${\varrho}_{H}$ is the probability that at least one correct process gets
selected on the honest chain $\mathcal{C}_{\mathsf{local}}$ at each time step.
For any interval $[t_{0},t_{0}+t]$ and arbitrary $t_{0},t\in\mathbb{N}$, we
denote with $X_{0},\dots,X_{t-1}$ independent Poisson trails such that
$\Pr[X_{i}=1]={\varrho}_{H}$, and we let $X_{H}=\sum_{i=0}^{t-1}X_{i}$. Using
the Chernoff bound, one can show that for any $\epsilon\in(0,1)$ it holds that
$\Pr[X_{H}<(1-\epsilon)\cdot{\varrho}_{H}\cdot t]\leq\exp(-{\varrho}_{H}\cdot
t\cdot\epsilon^{2}/2)$. Intuitively, the Chernoff bound implies that the value
of $X_{H}$ cannot deviate too much from the mean; hence, for sufficiently
large $t$ and sufficiently small $\epsilon$, the upper bound on the honest
chain growth is approximately ${\varrho}_{H}\cdot t$, with an overwhelming
probability.

Using the same argument for the growth of the malicious chain, one can show
that for a sufficiently large time interval (i.e., $t$) and a sufficiently
small $\epsilon$, the lower bound of chain growth is approximately
${\varrho}_{\mathcal{A}}\cdot t$ (i.e.,
$(1+\epsilon)\cdot{\varrho}_{\mathcal{A}}\cdot t$) with an overwhelming
probability (i.e., $\exp(-{\varrho}_{\mathcal{A}}\cdot
t\cdot\epsilon^{2}/3)$), where ${\varrho}_{\mathcal{A}}$ is the probability
that at least one Byzantine processes get selected on the honest chain
$\mathcal{C}^{*}$ at each time step.

So, if ${\varrho}_{\mathcal{A}}>{\varrho}_{H}$, we can claim that
$\mathcal{C}^{*}$ grows at a faster rate than $\mathcal{C}_{\mathsf{local}}$.
This is the case for Algorithm 1 that uses $\textsl{RA}_{\mathsf{pos}}$
allocator. Due to definition 12, the probability of getting assigned the
resource commitment with $\mathcal{C}^{*}$, is
${\varrho}_{\mathcal{A}}>1-(1-{\varrho})^{R-R_{\mathcal{A}}}={\varrho}_{H}$,
where ${\varrho}_{H}$ is the probability that at least one correct processes
get assigned a resource commitment with $\mathcal{C}_{\mathsf{local}}$. ∎

###### Remark 4.

Also, if we assume a $\Delta>1$ network delay between correct processes, there
will a non-zero probability that a fork can happen, and honest blocks can get
discarded due to the network delay. On the other hand, we also assume a
perfect synchrony ($\Delta=1$) between Byzantine processes; therefore, there
is no loss in the malicious growth rate. Therefore, even when correct
processes and Byzantine processes control the same amount of resources on both
chains, due to network delay, the chain growth rate of $\mathcal{C}^{*}$ can
still be higher than the chain growth rate of the honest chain
$\mathcal{C}_{\mathsf{local}}$.

###### Theorem 10.

If a virtual-resource-shifting event occurs, a total-order broadcast based on
virtual resources (Algorithm 1) does not guarantee properties of total-order
broadcast.

###### Proof.

Let $\mathcal{C}$ be the honest chain adopted by every correct process and let
us assume that all the transactions buried at least $k$ blocks deep in
$\mathcal{C}$ have been a-delivered (Algorithm 1, L1) by every correct
process. If a virtual-resource-shifting event occurs then, by Lemma 9, an
adversary can eventually form a valid chain $\mathcal{C}^{*}$ that is longer
than $\mathcal{C}$.

For existing processes, the adversary can send this $\mathcal{C}^{*}$ to a
subset of correct processes. This implies that some correct processes will
adopt $\mathcal{C}^{*}$ as a valid chain; they will a-deliver all the
transactions buried at least $k$ blocks deep in $\mathcal{C}^{*}$. This
implies that, eventually, the _total-order_ property is violated. Also, due to
the permissionless nature of our model, correct processes might join the
system at any time. Hence, new processes will adopt the malicious chain as the
local chain; therefore, delivered will be different among correct processes.
Hence, the _total-order_ property is violated ∎

###  6.2 Incentives in Burnable and Reusable Resources

One of the vulnerabilities induced by _reusable_ resources is that extending
the blockchain is _costless_ with respect to the resource considered. This is
different from _burnable_ resources, where creating a block consumes the
resource; this consumption is captured in our model as the interaction between
processes and the resource allocator. The use of reusable resources can result
in two different types of adversarial behaviors. The first one consists in
creating multiple blocks at the same time slots on different chains. The
second one consists in keeping blocks created private from the rest of the
processes. In both cases, we discuss how this _costless_ property associated
with block creation for longest-chain consensus protocols based on a reusable
resource impacts their security compared to those based on burnable resource.
In this section, we assume, as is traditional with any blockchain system, that
some financial reward is associated with block creation, and we assume the
cost of acquiring resources is the same for both reusable and burnable
resources. With these assumptions and the use-once property of resource
allocator, we define the chain extension cost as follows.

###### Definition 13 (Chain Extension Cost).

The cost of extending a valid chain for a process $p_{i}$ between two time
steps $t_{1}$ and $t_{2}$ such that $t_{1}\leq t_{2}$ is defined to be the
resource budgets committed and assigned back during this time interval. In
particular, we have:

  * •

For burnable resources:
$\textsl{Cost}_{\mathsf{burn}}(p_{i},t_{1},t_{2})=\sum_{t=t_{1}}^{t_{2}}\textsl{Alloc}(p_{i},t)$

  * •

For reusable resources:
$\textsl{Cost}_{\mathsf{reuse}}(p_{i},t_{1},t_{2})\leq\max_{t\in[t_{1},\dots,t_{2}]}\\{\textsl{Alloc}(p_{i},t)\\}$

###### Proposition 11.

For all time step $t_{2}>t_{1}$ and a process $p_{i}$, the cost of extending a
valid chain with a burnable resource is strictly more expensive than with a
reusable resource, i.e.,
$\textsl{Cost}_{\mathsf{burn}}(p_{i},t_{1},t_{2})>\textsl{Cost}_{\mathsf{reuse}}(p_{i},t_{1},t_{2})$.

proposition 11 indicates that it is inherently more expensive to extend the
blockchain for _burnable_ resources; hence, it is more difficult to launch
different types of attacks on blockchain based on _burnable_ resources. In the
following, we explain different types of attacks.

Private Attack. The private attack [11], sometimes called double-spending
attack, is the most simple attack in longest-chain blockchains. The adversary
creates a private chain, i.e., it mines on its own without broadcasting its
blocks to the other processes and without accepting the blocks from other
processes. In particular, the adversary runs Algorithm 1, except that it does
not broadcast its blocks until the end of the attack. This means that two
chains grow in parallel: the adversarial one, that only the adversary is aware
of, and the honest one. The adversary is aware of the honest chain but chooses
not to contribute to it and it wins the attack if it creates a chain longer
than the honest chain. In the case of a _burnable_ resource, this attack has a
cost as every block created consumes a resource. If the adversary wins the
attack, then the cost is recovered as the adversary wins the reward associated
with block creation. Otherwise, it loses the cost associated with all the
resources consumed. In the case of a _reusable_ resource, the only cost of the
attack is the _opportunity cost_ , i.e., the adversary takes the risk of
potentially not earning the rewards associated with block creation if the
attack fails but does not lose any resources. The attack in this case is then
much cheaper than in the case of a burnable resource. The cost of a private
attack is higher if the resource allocator is based on a burnable resource
than if it is on a reusable resource, thus creating a stronger
disincentivisation for an adversary. The results follow from the fact that for
a reusable resource, the resource allocator can be invoked on the same
resource several times. From proposition 11, it is not difficult to see that
the expected return on performing a private attack is higher for a _reusable_
resources as the probability of winning the attack (i.e. producing a longer
chain) is the same in both cases, but the cost is higher for a _burnable_
resource.

Resource-bleeding Attack. Stake-bleeding attacks [17] were proposed in the
context of PoS blockchains and work, informally, as follows. An adversary
starts creating a private chain (i.e., it does not broadcast its blocks to the
rest of the network) but, differently from the private attack described
previously, the adversary may continue creating blocks on the honest chain. In
its private chain, the adversary includes all of the transactions it is aware
of, harvesting the associated transaction fees. Furthermore, the adversary
also receives the coinbase reward usually associated with block production.
After a sufficient amount of time, the adversary will have bloated its amount
of resources and will _eventually_ be able to create a chain that becomes as
long as the honest chain. This attack could be extended to the general-
resource case, which we call this attack _resource-bleeding attack_ , and note
that in the case of an external resource, this attack is much easier to detect
than in the Proof-of-Stake case. In order to understand this attack, we must
extend the model from Section 4 to take into account _total resource
adjustments_ in the case of inactive processes. In Appendix 7 we describe the
general case of resource-bleeding attacks and discuss how they are more
detectable on an external resource and the most mitigated for burnable
resources.

Nothing-at-Stake Attack. In a Nothing-at-Stake attack, instead of deciding to
extend the longest chain (Algorithm 1, L1), a process decides to mine
simultaneously on all of the chains it is aware of. In the case of a burnable
resource, an adversary cannot reuse the same resource to mine on multiple
chains (due to L1), hence in order to mount this attack, the adversary must
decide how to commit its resources to multiple chains. In contrast, with a
reusable resource, each resource can be fully committed to each chain. If
there exists multiple forks of the same length, there is a risk that a process
will mine on a chain that ends up being abandoned and thus will miss out on
the associated reward. It thus becomes rational for a process to deviate from
the protocol and mine on every chain since this reduces chance of losing
reward because network may select different chain. If every process adopts
this strategy, the protocol cannot achieve the common prefix property as every
chain will keep on growing at the same pace.

##  7 Discussion

Resource-bleeding Attack in the Flexible Resource Setting. The resource-
bleeding attack stems from this observation: in order to deal with inactive
processes, if the protocol wants to maintain its block production rate, it
needs to adjust its leader selection processes such that inactive processes
are not selected anymore. In practice, this means increasing ${\varrho}$ such
that every active process has a higher chance of being selected and removing
the inactive processes from the list of eligible block producers and hence
maintaining a steady block rate. If an adversary starts a private attack,
since no resource commitment from the other processes is included in the
adversarial chain, after a sufficient time, ${\varrho}$ will be updated to
ensure that the adversarial chain block rate is maintained. On the other hand,
with a reusable resource, the adversary could keep maintaining its resources
on the honest chain to ensure that the leader selection probability is not
adjusted on the honest chain. After enough time, all the honest processes will
be removed from the power table in the adversarial chain. This means that when
electing a leader (Algorithm 4, L4) on the adversarial chain, the adversary
now represents the full power table and is guaranteed to be elected at each
epoch. On the other hand, since the adversary maintain its resource on the
honest chain, without contributing as many blocks as it could. This means
that, after some time, the honest chain will grow at a slower rate than the
adversarial chain and the adversary will be able to create a chain as long as
the honest chain, breaking the safety of the protocol.

In practice in Bitcoin, the _target_ value [28] is updated every two weeks
(roughly) to ensure that blocks are created, on average, at the same pace. An
adversary could fork the chain, wait for the difficulty adjustment to adjust
and then be able to create a chain at the same pace as the honest chain. This
is, however, easily detectable. In the PoW case, one can simply see that the
difficulty has been adjusted and that one chain has much fewer resources than
the other. Moreover, since the resource is burnable, it is not possible for an
adversary to continue mining on the honest chain as the same burnable resource
cannot be used twice, hence the adversary cannot maintain its full resource on
the honest chain and the honest chain difficulty must be adapted accordingly.

For an external, but reusable, resource such as storage, the adversary could
maintain its power in both chain, however, it is easy to detect the
adversarial chain as it will have fewer resources committed to it and hence is
distinguishable from the honest chain.

Mitigations against Different Attacks. In the following, we discuss various
mitigations against attacks described in section 6.

Long-range Attacks. In practice, many PoS systems deal with long-range attacks
by using some form of checkpointing [1, 26, 25], requiring key-evolving
cryptography [9, 19], or using multiple types of resources [15]. Others use
more refined chain selection rules [9, 2] (i.e., chain density analysis or
selecting the longest chain that fork less than $k$ blocks) instead of the
longest chain selection.

Resource-bleeding Attacks. In the case of PoS, mitigation has been proposed in
Ouroboros Genesis [2] and it works as follows. When a process is presented
with two forks, it differentiates between two cases. In the first case, the
fork is smaller than the common prefix parameter $k$, i.e., the two chains
differ for a number of slots smaller than $k$, in which case the usual
longest-chain rule is applied. If on the other hand, the forks differ from
more than $k$ slots, then the processes look at the first $k$ slots after the
fork (i.e., the first $k$ slots where the two chains diverge) and choose the
chain with the most blocks in that period. Intuitively, this is because during
the beginning of the fork, an adversary has not had the time to bloat its
stake and hence the rate at which its chain grows will be smaller than that of
the correct processes. In the case of an external resource, it suffices to
look at the total power (which can be explicit in the case of a reusable
resource, or implicit for a burnable resource, e.g., _target_ value) at the
tip (end) of the chains and pick the one with the most resource.

Nothing-at-stake Attacks. A process that performs a nothing-at-stake attack
with a reusable resource is easily detectable as anyone can see that the same
resource was used on different chains. One typical mitigation adopted by PoS
systems is to _slash_ , i.e., financially punish, processes who use their
resource on concurrent chains. This is usually done by having processes
deposit some money before gaining participation rights, and then burning some
of this deposit if a proof of misbehavior is sent to the blockchain. The
details of this mechanism are out of scope for this paper.

##  8 Conclusion

Resources are essential in ensuring the safety property of total-order
broadcast protocols in a permissionless setting as it protects the protocol
from Sybil attacks. However, there exist several attacks on protocols based on
reusable and virtual resources that a formal specification would help
understand and address.

In this work, we formalize properties of resources through a _resource
allocator_ abstraction, and identify crucial properties on how to make this
resource allocator secure for blockchain protocols. Using a secure resource
allocator, we demonstrate how to construct a generic _longest-chain_ _total-
order_ broadcast algorithm. Furthermore, we also illustrate how certain types
of resources tend to make blockchain protocols more vulnerable to different
types of attacks. We believe that this formalization will help blockchain
protocol designers to select suitable types of resources for their protocols
and understand and analyze the potential security trade-offs on those
resources.

Outlook. For future work, we find the following research directions worth
investigating:

  * •

Relaxed Assumptions. Our analysis works with a setting where the total amount
of active resources is known and fixed. Hence, it is natural to extend this
model to a setting where the total amount of resources is unknown and
potentially fluctuates.

  * •

Different Network Setting and Participation Models. Our model focuses on
_probabilistic_ _longest-chain_ protocols in a $\Delta$-synchrony setting.
However, we believe that our model can be applied to analyze properties of
resource-based _deterministic_ protocols in a permissioned and partially
synchrony setting such as Tendermint [6] and HotStuff [29].

  * •

Different Types of Resources. Finally, there are other resource-based
protocols such as the Proof-of-Elapsed-Time (PoET) protocol [4] or multi-
resources-based protocol [15] that have not been considered in this work.
Hence, one can extend this model to analyze those protocols.

## Acknowledgments

The authors thank anonymous reviewers for helpful feedback. DVL has been
supported by a grant from Protocol Labs to the University of Bern. LZ has been
supported by the Swiss National Science Foundation (SNSF) under grant
agreement Nr. 200021_188443 (Advanced Consensus Protocols).

## References

  * [1] Sarah Azouvi, George Danezis, and Valeria Nikolaenko.  Winkle: Foiling long-range attacks in proof-of-stake systems.  In AFT, pages 189–201. ACM, 2020.
  * [2] Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas.  Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability.  In CCS, pages 913–930. ACM, 2018.
  * [3] Joseph Bonneau, Jeremy Clark, and Steven Goldfeder.  On bitcoin as a public randomness source.  IACR Cryptol. ePrint Arch., page 1015, 2015.
  * [4] Mic Bowman, Debajyoti Das, Avradip Mandal, and Hart Montgomery.  On elapsed time consensus protocols.  In INDOCRYPT, volume 13143 of Lecture Notes in Computer Science, pages 559–583. Springer, 2021.
  * [5] Jonah Brown-Cohen, Arvind Narayanan, Alexandros Psomas, and S. Matthew Weinberg.  Formal barriers to longest-chain proof-of-stake protocols.  In EC, pages 459–473. ACM, 2019.
  * [6] Ethan Buchman, Jae Kwon, and Zarko Milosevic.  The latest gossip on BFT consensus.  CoRR, abs/1807.04938, 2018.
  * [7] Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues.  Introduction to Reliable and Secure Distributed Programming (2. ed.).  Springer, 2011.
  * [8] Phil Daian, Rafael Pass, and Elaine Shi.  Snow white: Robustly reconfigurable consensus and applications to provably secure proof of stake.  In Financial Cryptography, volume 11598 of Lecture Notes in Computer Science, pages 23–41. Springer, 2019.
  * [9] Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexander Russell.  Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain.  In EUROCRYPT (2), volume 10821 of Lecture Notes in Computer Science, pages 66–98. Springer, 2018.
  * [10] Evangelos Deirmentzoglou, Georgios Papakyriakopoulos, and Constantinos Patsakis.  A survey on long-range attacks for proof of stake protocols.  IEEE Access, 7:28712–28725, 2019.
  * [11] Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni.  Everything is a race and nakamoto always wins.  In CCS, pages 859–878. ACM, 2020.
  * [12] Yevgeniy Dodis and Aleksandr Yampolskiy.  A verifiable random function with short proofs and keys.  In Public Key Cryptography, volume 3386 of Lecture Notes in Computer Science, pages 416–431. Springer, 2005.
  * [13] drand: Distributed randomness beacon.  URL: https://drand.love/.
  * [14] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer.  Consensus in the presence of partial synchrony.  J. ACM, 35(2):288–323, 1988.
  * [15] Matthias Fitzi, Xuechao Wang, Sreeram Kannan, Aggelos Kiayias, Nikos Leonardos, Pramod Viswanath, and Gerui Wang.  Minotaur: Multi-resource blockchain consensus.  In CCS, pages 1095–1108. ACM, 2022.
  * [16] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol: Analysis and applications.  In EUROCRYPT (2), volume 9057 of Lecture Notes in Computer Science, pages 281–310. Springer, 2015.
  * [17] Peter Gazi, Aggelos Kiayias, and Alexander Russell.  Stake-bleeding attacks on proof-of-stake blockchains.  In CVCBT, pages 85–92. IEEE, 2018.
  * [18] Peter Gazi, Aggelos Kiayias, and Alexander Russell.  Tight consistency bounds for bitcoin.  In CCS, pages 819–838. ACM, 2020.
  * [19] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich.  Algorand: Scaling byzantine agreements for cryptocurrencies.  In SOSP, pages 51–68. ACM, 2017.
  * [20] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman.  All you need is DAG.  In PODC, pages 165–175. ACM, 2021.
  * [21] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In CRYPTO (1), volume 10401 of Lecture Notes in Computer Science, pages 357–388. Springer, 2017.
  * [22] Protocol Lab.  Filecoin: A decentralized storage network, 2017.  https://filecoin.io/filecoin.pdf.
  * [23] Andrew Lewis-Pye.  Byzantine generals in the permissionless setting.  CoRR, abs/2101.07095, 2021.
  * [24] Ling Ren.  Analysis of nakamoto consensus.  IACR Cryptol. ePrint Arch., page 943, 2019.
  * [25] Selma Steinhoff, Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolic.  BMS: secure decentralized reconfiguration for blockchain and BFT systems.  CoRR, abs/2109.03913, 2021.
  * [26] Ertem Nusret Tas, David Tse, Fangyu Gai, Sreeram Kannan, Mohammad Ali Maddah-Ali, and Fisher Yu.  Bitcoin-enhanced proof-of-stake security: Possibilities and impossibilities.  IACR Cryptol. ePrint Arch., page 932, 2022.
  * [27] Benjamin Terner.  Permissionless consensus in the resource model.  In Financial Cryptography, volume 13411 of Lecture Notes in Computer Science, pages 577–593. Springer, 2022.
  * [28] Bitcoin Wiki.  Target.  https://en.bitcoin.it/wiki/Target.
  * [29] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham.  Hotstuff: BFT consensus with linearity and responsiveness.  In PODC, pages 347–356. ACM, 2019.