# Blockchain Security when Messages are Lost

Taha Ameen  University of Illinois at Urbana-Champaign  Suryanarayana
Sankagiri  University of Illinois at Urbana-Champaign  Bruce Hajek  University
of Illinois at Urbana-Champaign

###### Abstract

Security analyses for consensus protocols in blockchain research have
primarily focused on the synchronous model, where point-to-point communication
delays are upper bounded by a known finite constant. These models are
unrealistic in noisy settings, where messages may be lost (i.e. incur infinite
delay). In this work, we study the impact of message losses on the security of
the proof-of-work longest-chain protocol. We introduce a new communication
model to capture the impact of message loss called the $0\mathchar
45\relax\infty$ model, and derive a region of tolerable adversarial power
under which the consensus protocol is secure. The guarantees are derived as a
simple bound for the probability that a transaction violates desired security
properties. Specifically, we show that this violation probability decays
almost exponentially in the security parameter. Our approach involves
constructing combinatorial objects from blocktrees, and identifying random
variables associated with them that are amenable to analysis. This approach
improves existing bounds and extends the known regime for tolerable
adversarial threshold in settings where messages may be lost.

##  1 Introduction

Blockchain is the data structure used by peers (miners) in a peer-to-peer
network to maintain a common ledger in a decentralized manner. The consistency
of this ledger is ensured through consensus protocols such as the longest-
chain protocol. Following this protocol, an honest miner groups transactions
into a block and appends its block to the longest chain in its view, before
broadcasting the new blockchain to all other peers. Further, the system may
have adversarial users that deviate from the protocol arbitrarily. Despite
adversarial users attempting to disrupt the system and peer-to-peer
communication incurring message delays, it is desirable that the parties
following the protocol agree on a consistent ledger.

Blockchain security has been studied under various consensus protocols (see
[BSAB+19, GK20] for a survey). Of these, the longest-chain protocol is of
great interest, due its heavy use in modern blockchain implementations. The
longest-chain protocol has been modeled under various assumptions: for
example, discrete time is used in [GKR20, BKM+20], and continuous time
dynamics is used in [LGR21, Ren19, DKT+20]. Further, the protocol has also
been studied for a variety of leader election mechanisms in the consensus
protocol. For instance, [PSS17, Ren19, GKL20] assume the proof-of-work
mechanism, whereas [PS17, KRDO17, FZ17] assume a proof-of-stake mechanism. All
these works establish security of the longest-chain protocol for the
synchronous communication model, where communication delays are upper bounded
by a known finite constant. A common theme among these results is that in the
synchronous delay model, the longest-chain protocol is ‘secure’ under
sufficient honest representation, with high probability.

In this work, we analyze the impact of message losses on the security of the
longest-chain protocol following proof-of-work leader election, by introducing
and analyzing an appropriate communication network model. We motivate this by
reviewing some existing communication models in the literature and the known
security guarantees associated with them.

###  1.1 Related Work

The underlying communication network can delay the successful delivery of
peer-to-peer message broadcasts. Popular blockchains such as Bitcoin use the
Internet as their communication network. Since this communication is subject
to delay, it is natural to model the delays incurred by each block, and study
the impact of delay on the security of the longest-chain protocol.

Let $0\leq i<j$. Let $b_{i}$ represent the $i$-th mined honest block. Let
$\mathsf{delay}\left(b_{i}\to b_{j}\right)$ denote the time taken for block
$b_{i}$ to reach the miner of block $b_{j}$, and let $\beta$ represent the
fraction of adversarial computational power in the system. Finally, let
$\lambda$ be the rate at which blocks are mined in the system. Various
descriptions of $\mathsf{delay}\left(b_{i}\to b_{j}\right)$ lead to different
communication network models:

##### Instantaneous Model

The original white-paper by Satoshi Nakamoto [Nak08] assumes an ideal
communication channel, i.e. $\mathsf{delay}\left(b_{i}\to b_{j}\right)=0$. In
this model, the longest-chain protocol is provably secure when the honest
computational power in the system exceeds the adversarial computational power,
i.e. when $\beta<1-\beta$, or equivalently, when $\beta<1/2$.

##### Synchronous Model

The model assumes a deterministic delay for each block that is upper bounded
by a known constant $\Delta$, i.e., $\mathsf{delay}\left(b_{i}\to
b_{j}\right)\leq\Delta<\infty$. This delay effectively reduces the growth rate
of the chain held by an honest user. Even so, it has been proved [DKT+20,
GKR20] that the synchronous model is secure with high probability if and only
if

$\displaystyle\beta<\frac{1}{1+\left(1-\beta\right)\lambda\Delta}\left(1-\beta\right),$

where $\lambda$ is the total mining rate of the honest users.

##### Partially Synchronous Model

The partially synchronous model assumes the existence of some unknown and
adversarially chosen ‘Global Stabilization Time ($\mathsf{GST}$)’ such that
the delays are unbounded before $\mathsf{GST}$, but bounded after it [DLS88].
Therefore, at any time $t$, the delay satisfies $\mathsf{delay}\left(b_{i}\to
b_{j}\right)\leq\Delta+\max\left(0,\mathsf{GST}-t\right)$. If certain
conditions are met, the partially synchronous model is known to be secure with
high probability after the Global Stabilization Time [NTT21].

##### Sleepy Model

The sleepy model considers the setting where miners may either be online or
offline, and their participation status may change during the execution of the
protocol [PS17]. Let $h_{i}$ denote the miner of block $b_{i}$. The incurred
delay is thus

$\displaystyle\mathsf{delay}\left(b_{i}\to
b_{j}\right)=\begin{cases}0&\text{$h_{j}$ is awake when $b_{i}$ is mined}\\\
\infty&\text{$h_{j}$ is asleep when $b_{i}$ is mined}\end{cases}.$

Pass and Shi [PS17] showed that consensus can be achieved in the sleepy model
with high probability, if a majority of the awake miners at any point in time
are honest.

##### Random Delay Model

The random delay model assumes that the point-to-point delays are independent
and identically distributed, i.e. $\mathsf{delay}\left(b_{i}\to
b_{j}\right)\sim\mathsf{X}$, where $\mathsf{X}$ is some known distribution.
The longest-chain protocol is shown to be secure with high probability in the
random delay model, if the delay distribution satisfies certain conditions and
the adversarial representation in the system is below a certain threshold
[SGH21].

Except for the random delay model, none of the above models account for the
possibility that point-to-point communication may incur infinite delay, i.e.
messages may be lost at random. For instance, the sleepy model allows infinite
delay for users that are offline, but does not account for noise in the
communication process. In contrast, we introduce and analyze a new
communication model to study the impact of lost messages on blockchain
security.

###  1.2 Contributions

#####  $0\mathchar 45\relax\infty$ Model

We introduce the $0\mathchar 45\relax\infty$ model, where the delays are
independent and identically distributed over the set $\\{0,\infty\\}$.
Specifically, for any $i$, $j\geq 0$ such that $i<j$:

$\displaystyle\mathsf{delay}\left(b_{i}\to
b_{j}\right)=\begin{cases}0&\text{with probability }1-d\\\ \infty&\text{with
probability }d\end{cases}.$

This simple model postulates that a message sent point-to-point is either
immediately received or permanently lost. This delay is independent for each
user, and for each block. The modeling choice aligns with our objective of
studying the effect of message losses.

We remark that the $0\mathchar 45\relax\infty$ model is a special case of the
i.i.d. random delay model introduced in [SGH21], which identifies a region of
tolerable adversarial power as a function of the delay distribution.
Specifically, if $d$ is the probability of message loss and $\beta$ is the
fraction of computational power in the system that is adversarial, it is shown
that the $0\mathchar 45\relax\infty$ model is secure with high probability
when $\beta<\frac{1-2d}{2\left(1-d\right)}$. However, this characterization is
not tight for the $0\mathchar 45\relax\infty$ model, and the analysis in
[SGH21] breaks down in the high-noise regime. For example, security of the
model cannot be established when $d>1/2$, i.e. more than half the messages are
lost on average.

It is reasonable to wonder if adversarial computational power can at all be
tolerated in the high-noise regime, for instance, when almost all messages are
lost. Our work answers this question in the affirmative, by expanding the
known security threshold for the $0\mathchar 45\relax\infty$ model. In
particular, our sufficient condition for security is
$\frac{\beta}{1-\beta}<1-d$. Figure 1 shows this improvement.

Figure 1: Characterizing the region of tolerable adversarial power

Our method of analysis is significantly different from that in [SGH21]: we
introduce a transmission-graph that captures the history of communication
delays between blocks, and identify special paths in the graph that are linked
to random variables which are amenable to analysis. Specifically, we identify
special objects such as forward-special and backward-special blocks, and
associate with them random variables such as forward-unheard and backward-
unheard. Our technique also presents a new approach to infer the inclusion of
special blocks in the chain held by an honest user through the concept of
user-unheard-criterion. The method of analysis is inspired from [DKT+20],
where security of the synchronous model is established by considering races
between honest and adversarial chains. However, our approach does not rely on
message delays being finite, and we hope that the tools we introduce are of
utility in the study of consensus mechanisms in more general settings, as well
as of independent mathematical interest. Our contributions are summarized as:

  * •

We introduce the $0\mathchar 45\relax\infty$ model as a playground for
studying the impact of message losses. This model provides a starting step for
more complex models involving message losses.

  * •

We introduce combinatorial objects of independent interest such as the
transmission-graph. We also identify random variables (forward-unheard,
backward-unheard) associated with this graph that are amenable to analysis,
and introduce the user-unheard-criterion. These concepts may be utilized in
security analysis of blockchain protocols in more general settings.

  * •

We prove that the longest-chain protocol is secure in the $0\mathchar
45\relax\infty$ model if certain conditions are met. These conditions are
fairly general, and considerably extend the known threshold of tolerable
adversarial power. In this regime, we show that the probability of security
violation decays almost exponentially in the security parameter.

##  2 System Model

In this section, we describe our system model. We consider the setting where
infinitely many miners participate in the longest-chain protocol for an
infinite duration, and use proof-of-work as the leader election mechanism.

##### Ledgers, Transactions, Miners, and Blocks

Blockchain is the data structure at the heart of the decentralized mechanism
to maintain and update a ledger. The ledger is simply an ordered list of
transactions. Transactions are assumed to be available to all the miners as
soon as they are made. Miners verify the validity of transactions, and update
the ledger by grouping the transactions into blocks and linking blocks to form
a blockchain. A block is an abstract data structure that contains a hash
pointer to a parent block, a cryptographic signature of the block’s miner,
transactions, and other metadata. The first block in the system is called the
genesis block.

##### Longest-Chain Protocol and Proof-of-Work

Miners follow the proof-of-work longest-chain protocol for consensus.
Following this protocol, a miner groups any and all transactions that are not
included in this longest chain into a block, and attempts to append the block
to the longest chain in its view. To do so, it must solve a hash puzzle and
include the solution as proof-of-work. If the miner is successful, it
broadcasts its chain as a message to other miners over a peer-to-peer network,
subject to a communication delay. Upon receiving this message, an honest miner
adopts the new chain if the received chain is longer than the chain in the
miner’s memory. Ties are broken using any deterministic rule, for example, by
choosing the chain that terminates in the block that hashes to a lower value.
The process continues indefinitely. We assume there are infinitely many
miners, and at any finite time, a miner who successfully solves the hash
puzzle is doing so for the first time almost surely.

##### Parties in the Protocol

We refer to parties in the protocol as users. Users that contribute to
modifying the ledger through appending blocks to the blockchain are called
miners. A miner is either honest or corrupt. Honest miners follow the longest-
chain protocol, whereas corrupt miners may deviate from the protocol. For
simplicity, all corrupt users are grouped into a single entity called the
adversary. This allows corrupt miners to communicate instantaneously, and
captures the strong setting of perfect coordination between corrupt miners.
The adversary can mine on any previously mined block, but its block must
contain the proof-of-work to be valid. It can reveal its chain to any subset
of honest users, and can delay its message by arbitrary amounts of time. It
can also not include all the transactions it knows about that were not in
ancestor blocks. We use $\beta$ to represent the fraction of computational
power in the system that is adversarial.

##### Mining Process

The mining process is abstracted as follows. Let $\lambda$ denote the total
mining rate of the system. We consider a continuous time model where blocks
are mined as a Poisson process with rate $\lambda$. Since $\beta$ denotes the
fraction of power that is adversarial and since successive mining instances
are independent, adversarial block arrivals follow a Poisson process with rate
$\beta\lambda$.

##### Blockchains and Blocktrees

From any block, a unique sequence of blocks leading back to the genesis block
can be identified via the hash pointers. We call this sequence a blockchain,
or simply a chain. The convention is that the genesis block is the first block
of a chain, and the terminating block is called the tip. At any given slot,
honest users store a single chain in their memory.

##### Communication Delays

We consider the setting where messages are either instantaneously delivered or
permanently lost in an independent and identically distributed manner. Let
$\mathsf{delay}\left(b_{i}\to b_{j}\right)$ denote the delay incurred by block
$b_{i}$ to reach the miner of block $b_{j}$. It is assumed that:

$\displaystyle\mathsf{delay}\left(b_{i}\to b_{j}\right)=\begin{cases}0,&\text{
with probability }1-d\\\ \infty,&\text{ with probability }d\end{cases}.$

Here, $d$ is the probability of message loss in an instance of point-to-point
communication.

##  3 Main Result

In this section, we outline the desired security properties and present our
main result. We define security on the level of transactions. It is desirable
that a transaction eventually makes it to the ledger, and stays permanently at
the same position in the ledger. This notion is formalized in Definition 3.1.

######  Definition 3.1 (Security).

Let $\tau>0$. Let $\mathcal{H}$ be any set of honest users. For any
$h\in\mathcal{H}$, let $\mathcal{C}_{h}(t)$ denote the chain held by user $h$
at time $t$. We say that a transaction $\mathsf{tx}$ made at some time $s$ is
$\left(\tau,\mathcal{H}\right)$-secure if for any $h_{1},h_{2}\in\mathcal{H}$
and any $s_{1},s_{2}>s+\tau$, it holds that $\mathsf{tx}$ is included in a
block $b$ that is at the same position in $\mathcal{C}_{h_{1}}(s_{1})$ and
$\mathcal{C}_{h_{2}}(s_{2})$.

In the literature, security of a transaction is often defined as the
confluence of _persistence_ and _liveness_. A transaction satisfies liveness
if it is eventually added to the ledger, and it satisfies persistence if it
remains in the same position in the ledger for all future time, after a
confirmation time. We remark that our definition of security implies these
notions of persistence and liveness, and is consistent with existing
definitions of security, such as in [GKL15, DKT+20]. Specifically, if a
transaction $\mathsf{tx}$ satisfies $\left(\tau,\mathcal{H}\right)$-security,
then it is part of the chain held by all users in $\mathcal{H}$ before a
confirmation time $\tau$ time has elapsed. Furthermore, once this confirmation
time elapses, the transaction remains at the same position in the ledger for
all future time. Our main result shows that if certain conditions are
satisfied, then any transaction $\mathsf{tx}$ satisfies
$\left(\tau,\mathcal{H}\right)$ security except with a probability that decays
almost exponentially in the confirmation time and scales linearly in the size
of $\mathcal{H}$. It is stated as Theorem 3.2.

######  Theorem 3.2 (Main Result).

Let $\beta$ be the fraction of computational power in the system that is
adversarial, and $d$ be the probability of message loss. If
$\frac{\beta}{1-\beta}<\left(1-d\right)$, then for every $\varepsilon>0$,
there exist positive constants $a$ and $b$ such that for all $\tau\geq 0$ and
for any honest transaction $\mathsf{tx}$ and any finite set of honest users
$\mathcal{H}$:

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(\tau,\mathcal{H}\right)$-security}\right)\leq\exp\left(-a\tau^{1-\varepsilon}\right)+|\mathcal{H}|\exp\left(-b\tau\right).$

The result states that under a certain threshold of tolerable adversarial
power, the probability of security violation for any transaction and any
finite set of users decays (almost) exponentially in the confirmation time.
Hence, this violation probability can be made arbitrarily small by
appropriately selecting the confirmation time. The sufficient condition
$\frac{\beta}{1-\beta}<1-d$ significantly improves the known threshold of
tolerable adversarial power for the $0\mathchar 45\relax\infty$ model (Figure
1). We also remark that our bound for the probability violation comprises of
two terms, the latter of which scales linearly in $|\mathcal{H}|$. This linear
scaling is expected, because no single message is successfully transmitted to
all users in the model. Therefore, requiring a larger set of users to
permanently adopt a transaction in their ledger requires a larger waiting
time.

##  4 Definitions and Preliminaries

This section introduces key quantities that are used extensively in the
analysis. In Section 4.1, we introduce the combinatorial objects on which the
analysis is performed, such as the main-blocktree and the transmission-graph.
Properties of these objects are presented alongside to motivate their purpose.
In Section 4.2, key random variables that are amenable to analysis, and
associated with special paths in the transmission-graph are identified. These
quantities are illustrated through an example in Section 4.3. In Section 4.4,
these random variables and are used to define ‘catch-up events’, and the
notion of ‘$\eta$-Nakamoto blocks’. Finally, Section 4.5 introduces the ‘user-
unheard-criterion’, which is used to infer useful information about the
blockchain held by a user.

###  4.1 Graphs and Trees

Three combinatorial objects at the core of our analysis are the main-blocktree
and the transmission-graph.

##### Main-blocktree

Any block can be uniquely traced back to the first block in the system (called
genesis block). The set of all blocks generated (mined) up till time $t$ forms
a directed tree, which we refer to as the main-blocktree and denote it by
$\mathsf{MB}(t)$. Here, $\mathsf{MB}(t)=(V_{t},E_{t})$, where the vertex set
$V_{t}$ is the set of all blocks mined up till time $t$ and the set of
directed edges $E_{t}$ comprises all parent-to-child block pairs.
$\mathsf{MB}(t)$ represents the global information about the system, and both
honest and adversarial blocks are included in it. Figure 2(a) shows an example
of the vicinity of the $j$-th honest block, $b_{j}$ in some $\mathsf{MB}(t)$.

######  Definition 4.1 (Heights).

Let $b_{j}$ be the $j$-th honest block. The height of $b_{j}$ in a blocktree
is the length of the directed path (counting edges) from the genesis block to
$b_{j}$. We denote the height of $b_{j}$ in the main-blocktree by
$0pt{\mathsf{MB}}{b_{j}}$.

##### Transmission-graph

At any time $t$, we associate with the main-blocktree $\mathsf{MB}(t)$, a
graph consisting of only honest blocks that we call the transmission-graph.
The transmission-graph at time $t$, denoted $\mathsf{TG}(t)$ is a directed
acyclic graph that represents the history of network delays among the honest
miners. Here, $\mathsf{TG}(t)=\left(V_{t},E_{t}\right)$, where the vertex set
$V_{t}$ is the set of honestly mined blocks up till time $t$. An edge between
$b_{i}$ and $b_{j}$ is present if $\mathsf{delay}\left(b_{i}\to
b_{j}\right)=0$. A useful observation about $\mathsf{TG}(T)$ is presented in
Lemma 4.2.

(a) Main-blocktree

(b) Transmission-graph

Figure 2: Graphs and trees

######  Lemma 4.2.

Let $b_{i}$ and $b_{k}$ be the $i$-th and $k$-th honest blocks such that
$i<k$. At any time $t$, suppose there exists a path $\mathcal{A}_{i,k}$ of
length $n$ from $b_{i}$ to $b_{k}$ in $\mathsf{TG}(t)$, i.e.

$\mathcal{A}_{i,k}\colon b_{i}=v_{0}-v_{1}-\cdots-v_{n}=b_{k}.$

Then,

$\displaystyle 0pt{\mathsf{MB}}{b_{k}}-0pt{\mathsf{MB}}{b_{i}}$
$\displaystyle\geq n$

###### Proof.

If $v_{i-1}$ and $v_{i}$ are two blocks in $\mathsf{TG}(t)$ such that there is
an edge from $v_{i-1}$ to $v_{i}$, then the miner of block $v_{i}$ has heard
of block $v_{i-1}$. Therefore, it adds its block at a height greater than that
of $v_{i-1}$, so we have

$\displaystyle 0pt{\mathsf{MB}}{v_{i}}$ $\displaystyle\geq
0pt{\mathsf{MB}}{v_{i-1}}+1$

Repeatedly applying this inequality over the path from $b_{i}$ to $b_{k}$
yields the desired result. ∎

###  4.2 Special Sequences of Honest Blocks

Relative to the $j$-th honest block $b_{j}$, we define sequences of special
blocks that correspond to forward and backward paths in $\mathsf{TG}(t)$. We
also define notions of ‘forward unheard’ and ‘backward unheard’.

####  4.2.1 Forward Special Blocks

Relative to the $j$-th honest block $b_{j}$, we define a sequence of ‘forward
special ($\mathsf{FS}$)’ blocks as follows.

######  Definition 4.3 ($j\mathchar 45\relax\mathsf{FS}$ Sequence).

Let $j\geq 0$ and let $b_{j}$ be the $j$-th honest block. The $j\mathchar
45\relax\mathsf{FS}$ sequence is a sequence of blocks
$(b_{j}^{0},b_{j}^{1},b_{j}^{2},\cdots)$ such that $b_{j}^{0}=b_{j}$, and for
all $k\geq 1$, $b_{j}^{k}$ is the first block to hear of $b_{j}^{k-1}$.

Figure 3: $j\mathchar 45\relax\mathsf{FS}$ Sequence

We refer to blocks in the $j\mathchar 45\relax\mathsf{FS}$ sequence as
$j\mathchar 45\relax\mathsf{FS}$ blocks. For $0\leq j<k$, denote by
$\mathsf{FS}_{j}\left(b_{k}\right)$ the number of $j\mathchar
45\relax\mathsf{FS}$ blocks mined between $b_{j}$ and $b_{k}$ (inclusive).
Note that $\mathsf{FS}_{j}\left(b_{k-1}\right)\geq 1$, because $b_{j}$ is
always a $j\mathchar 45\relax\mathsf{FS}$ block. The $j\mathchar
45\relax\mathsf{FS}$ sequence associated with the transmission-graph in Figure
2(b) is shown in Figure 3. Notice that $\mathsf{FS}_{j}\left(b_{j+5}\right)=3$
and $\mathsf{FS}_{j}\left(b_{j+6}\right)=4$. This example is explored in more
detail in Section 4.3.

######  Remark 4.4.

Let $0\leq j\leq k$. Let $d$ be the probability of message loss. The random
variable $\mathsf{FS}_{j}\left(b_{k}\right)$ has the same distribution as
$1+\sum_{i=1}^{k-j}\mathsf{Be}_{i}\left(1-d\right)$, where
$\mathsf{Be}_{i}\left(1-d\right)$ are i.i.d. Bernoulli random variables with
success probability equal to $1-d$. This is because $b_{j}$ is a $j\mathchar
45\relax\mathsf{FS}$ block, and every subsequent block is independently
$j\mathchar 45\relax\mathsf{FS}$ with probability $1-d$.

######  Lemma 4.5.

Let $j\geq 0$. The $j\mathchar 45\relax\mathsf{FS}$ sequence
$(b_{j}^{0},b_{j}^{1},b_{j}^{2},\cdots)$ is a forward directed path in the
transmission-graph. Further, if $k>i\geq 0$, then the heights of the
$j\mathchar 45\relax\mathsf{FS}$ blocks $b_{j}^{i}$ and $b_{j}^{k}$ satisfy:

$\displaystyle 0pt{\mathsf{MB}}{b_{j}^{k}}-0pt{\mathsf{MB}}{b_{j}^{i}}\geq
k-i$

###### Proof.

Let $k\geq 0$. Since the miner of $b_{j}^{k+1}$ has heard of $b_{j}^{k}$,
there is an edge from $b_{j}^{k}$ to $b_{j}^{k+1}$. The conclusion follows
from Lemma 4.2. ∎

######  Definition 4.6 (Forward Unheard).

Let $k\geq j\geq 0$. The Forward Unheard for block $b_{k}$ with respect to
block $b_{j}$ is denoted $\mathsf{FU}_{j}\left(b_{k}\right)$ and defined as
the number of consecutive $j\mathchar 45\relax\mathsf{FS}$ blocks that the
miner of $b_{k}$ has not heard of, going backwards along the $j\mathchar
45\relax\mathsf{FS}$ sequence from the last such block mined before $b_{k}$.
If the miner of $b_{k}$ has not heard of any $j\mathchar 45\relax\mathsf{FS}$
block, then we toss independent biased coins (with failure probability equal
to the probability of message loss) and continue to increment the count until
a success is encountered.

######  Remark 4.7.

Let $0\leq j\leq k$. Let $d$ be the probability of message loss. The random
variable $\mathsf{FU}_{j}\left(b_{k}\right)$ has the same distribution as
$\mathsf{Geom}\left(1-d\right)-1$, where $\mathsf{Geom}(1-d)$ is a geometric
random variable, with minimum value 1. Further, if $k^{\prime}\geq 0$ such
that $k^{\prime}\neq k$, then $\mathsf{FU}_{j}\left(b_{k}\right)$ and
$\mathsf{FU}_{j}\left(b_{k^{\prime}}\right)$ are independent.

The intuition for defining $\mathsf{FU}_{j}\left(b_{k}\right)$ as above is
illustrated through an example in Section 4.3.

####  4.2.2 Backward Relative Special Honest

Relative to the $j$-th honest block $b_{j}$, we define a sequence of ‘backward
special ($\mathsf{BS}$) blocks as follows.

######  Definition 4.8 ($j\mathchar 45\relax\mathsf{BS}$ Sequence).

Let $j\geq 0$, and let $b_{j}$ be the $j$-th honest block. The $j\mathchar
45\relax\mathsf{BS}$ sequence is a sequence of blocks
$(b_{j}^{0},b_{j}^{-1},b_{j}^{-2},\cdots)$ such that $b_{j}^{0}=b_{j}$ and
$b_{j}^{-i}$ is the most recently mined block heard by $b_{j}^{-(i-1)}$ for
all $i\geq 1$.

Figure 4: $j\mathchar 45\relax\mathsf{BS}$ Sequence

For $0\leq i\leq j$, denote by $\mathsf{BS}_{j}\left(b_{i}\right)$ the number
of $j\mathchar 45\relax\mathsf{BS}$ blocks mined between $b_{i}$ and $b_{j}$
(inclusive). Note that $\mathsf{BS}_{j}\left(b_{i}\right)\geq 1$, since
$b_{j}$ is always a $j\mathchar 45\relax\mathsf{BS}$ block. The $j\mathchar
45\relax\mathsf{BS}$ sequence associated with the transmission-graph in Figure
2(b) is shown in Figure 4. Notice that $\mathsf{BS}_{j}\left(b_{j-5}\right)=4$
and $\mathsf{BS}_{j}\left(b_{j-6}\right)=5$. This example is explored in more
detail in Section 4.3.

######  Remark 4.9.

Let $0\leq i\leq j$. Let $d$ be the probability of message loss. The random
variable $\mathsf{BS}_{i}\left(b_{j}\right)$ has the same distribution as
$1+\sum_{k=1}^{j-i}\mathsf{Be}_{k}\left(1-d\right)$, where
$\mathsf{Be}_{k}\left(1-d\right)$ are i.i.d. Bernoulli random variables with
success probability equal to $1-d$. This is because $b_{j}$ is a $j\mathchar
45\relax\mathsf{BS}$ block, and every previous block is independently
$j\mathchar 45\relax\mathsf{BS}$ with probability $1-d$.

######  Lemma 4.10.

Let $j\geq 0$. The $j\mathchar 45\relax\mathsf{BS}$ sequence
$(b_{j}^{0},b_{j}^{-1},b_{j}^{-2},\cdots)$ is a backward directed path in
transmission-graph. Further, if $k>i\geq 0$, then the heights of the
$j\mathchar 45\relax\mathsf{BS}$ blocks $b_{j}^{-i}$ and $b_{j}^{-k}$ satisfy:

$\displaystyle 0pt{\mathsf{MB}}{b_{j}^{-k}}-0pt{\mathsf{MB}}{b_{j}^{-i}}\geq
k-i$

###### Proof.

Let $i\geq 0$. Since the miner of $b_{j}^{-(i-1)}$ has heard of $b_{j}^{-i}$,
there is an edge from $b_{j}^{-i}$ to $b_{j}^{-(i-1)}$. The conclusion follows
from Lemma 4.2. ∎

######  Definition 4.11 (Backward Unheard).

Let $j\geq i\geq 0$. The Backward Unheard for block $b_{i}$ with respect to
block $b_{j}$ is denoted $\mathsf{BU}_{j}\left(b_{i}\right)$ and defined as
the number of consecutive $j\mathchar 45\relax\mathsf{BS}$ blocks whose miners
have not heard of $b_{i}$, going backwards along the $j\mathchar
45\relax\mathsf{BS}$ sequence from the first such block mined after $b_{i}$.
If none of the miners of $j\mathchar 45\relax\mathsf{BS}$ blocks have heard of
$b_{i}$, then we toss independent biased cones (with failure probability equal
to the probability of message loss) and continue to increment the count until
a success is encountered.

######  Remark 4.12.

Let $0\leq i\leq j$. Let $d$ be the probability of message loss. The random
variable $\mathsf{BU}_{j}\left(b_{i}\right)$ has the same distribution as
$\mathsf{Geom}\left(1-d\right)-1$, where $\mathsf{Geom}(1-d)$ is a geometric
random variable, with minimum value 1. Further, if $i^{\prime}\geq 0$ such
that $i^{\prime}\neq i$, then $\mathsf{BU}_{j}\left(b_{i}\right)$ and
$\mathsf{BU}_{j}\left(b_{i^{\prime}}\right)$ are independent.

The intuition for defining $\mathsf{BU}_{j}\left(b_{i}\right)$ as above is
illustrated through an example in Section 4.3. The usefulness of these
quantities is evident from Lemma 4.13.

######  Lemma 4.13.

Let $i<j<k$.

  1. (i)

If $\mathsf{FS}_{j}\left(b_{k-1}\right)>\mathsf{FU}_{j}\left(b_{k}\right)$,
then
$0pt{\mathsf{MB}}{b_{k}}-0pt{\mathsf{MB}}{b_{j}}\geq\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right)$.

  2. (ii)

If $\mathsf{BS}_{j}\left(b_{i+1}\right)>\mathsf{BU}_{j}\left(b_{i}\right)$,
then
$0pt{\mathsf{MB}}{b_{j}}-0pt{\mathsf{MB}}{b_{i}}\geq\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)$.

###### Proof.

We prove statement (i). Let
$m=\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right)>0$.
Consider the $j\mathchar 45\relax\mathsf{FS}$ sequence
$(b_{j}^{0},b_{j}^{1},\cdots,b_{j}^{m},\cdots)$. Note that
$\mathsf{FS}_{j}\left(b_{k-1}\right)$ is the number of $j\mathchar
45\relax\mathsf{FS}$ blocks mined before $b_{k}$, and
$\mathsf{FU}_{j}\left(b_{k}\right)$ is the number of consecutive blocks from
this sequence that were not heard by $b_{k}$ going backward. Therefore,
$b_{k}$ has heard of $b_{j}^{m}$, and will mine at a greater height. Since the
$j\mathchar 45\relax\mathsf{FS}$ blocks are all mined at different heights, we
have

$\displaystyle
0pt{\mathsf{MB}}{b_{k}}-0pt{\mathsf{MB}}{b_{j}}>0pt{\mathsf{MB}}{b_{j}^{m}}-0pt{\mathsf{MB}}{b_{j}^{0}}\geq
m=\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right),$

as desired. The proof of statement (ii) is essentially the same, because the
forward sequences $\mathsf{FS}_{j}$ and $\mathsf{FU}_{j}$ map to the backward
sequences $\mathsf{BS}_{j}$ and $\mathsf{BU}_{j}$ under reversing the
directions of the edges in the transmission-graph. ∎

###  4.3 An Example

Some of the concepts introduced above are best understood through an example.
Consider the main-blocktree in Figure 2(a) and its associated transmission-
graph in Figure 2(b). The same transmission-graph is shown again in Figure 5,
where the $j\mathchar 45\relax\mathsf{FS}$ and $j\mathchar
45\relax\mathsf{BS}$ blocks are highlighted. Recall that in the transmission-
graph, a directed edge from $b_{j}$ to $b_{k}$ indicates that the miner of
$b_{k}$ has heard of the block $b_{j}$.

#####  $j\mathchar 45\relax\mathsf{FS}$ Sequence

By definition, $b_{j}$ is a $j\mathchar 45\relax\mathsf{FS}$ block. The miner
of the next block $b_{j+1}$ has heard of the most recent $j\mathchar
45\relax\mathsf{FS}$ block $b_{j}$, so $b_{j}^{1}=b_{j+1}$ is a $j\mathchar
45\relax\mathsf{FS}$ block. The miner of $b_{j+2}$ has heard of $b_{j}^{1}$,
so we have that $b_{j+2}=b_{j}^{2}$ is also a $j\mathchar 45\relax\mathsf{FS}$
block. However, the miners of $b_{j+3}$, $b_{j+4}$ and $b_{j+5}$ have not
heard of $b_{j}^{2}$, so these blocks are not $j\mathchar
45\relax\mathsf{FS}$. Finally, the miner of $b_{j+6}$ has heard of
$b_{j}^{2}$, so we have that $b_{j}^{3}=b_{j+6}$. Notice that no two
$j\mathchar 45\relax\mathsf{FS}$ blocks can share the same height.

##### Forward Unheard

Let us consider $\mathsf{FU}_{j}\left(b_{k}\right)$ with $k=j+4$. Starting
from $b_{k}$, we count the number of consecutive $j\mathchar
45\relax\mathsf{FS}$ blocks that the miner of $b_{k}$ has not heard of, going
backwards in the $j\mathchar 45\relax\mathsf{FS}$ sequence. The $j\mathchar
45\relax\mathsf{FS}$ sequence at the mining time of $b_{k}$ is
$\left(b_{j},b_{j+1},b_{j+2}\right)$. Going backwards in this sequence, we see
that the miner of $b_{k}$ has not heard of $b_{j+2}$, but has heard of
$b_{j+1}$. Therefore, we stop the count and have
$\mathsf{FU}_{j}\left(b_{j+4}\right)=1$.

#####  $j\mathchar 45\relax\mathsf{BS}$ Sequence

By definition, $b_{j}$ is a $j\mathchar 45\relax\mathsf{BS}$ block. Since the
miner of the most recent $j\mathchar 45\relax\mathsf{BS}$ block ($b_{j}$) has
heard of the previous block $b_{j+1}$, we have that $b_{j-1}=b_{j}^{-1}$ is a
$j\mathchar 45\relax\mathsf{BS}$ block. Similarly, the miner of $b_{j}^{-1}$
has heard of $b_{j-2}$, so we have that $b_{j-2}=b_{j}^{-2}$ is a $j\mathchar
45\relax\mathsf{BS}$ block. However, the miner of $b_{j}^{-2}$ has not heard
of $b_{j-3}$, and so $b_{j-3}$ is not a $j\mathchar 45\relax\mathsf{BS}$
block. Notice that no two $j\mathchar 45\relax\mathsf{BS}$ blocks can share
the same height.

##### Backward Unheard

Let us consider $\mathsf{BU}_{j}\left(b_{i}\right)$ with $i=j-3$. Starting
from the first $j\mathchar 45\relax\mathsf{BS}$ block mined after $b_{i}$, we
count the number of consecutive $j\mathchar 45\relax\mathsf{BS}$ blocks that
have not heard of $b_{i}$, going backwards in the $j\mathchar
45\relax\mathsf{BS}$ sequence. The $j\mathchar 45\relax\mathsf{BS}$ sequence
at the mining time of $b_{i}$ is $b_{j},b_{j-1},b_{j-2}$. Going backwards in
this sequence, we see that the miners of $b_{j-2}$ and $b_{j-1}$ have not
heard of $b_{i}$, but the miner of $b_{j}$ has. Therefore, we stop the count
and have $\mathsf{BU}_{j}\left(b_{j-3}\right)=2$.

Figure 5: Example

###  4.4 Catch-up Events and $\eta$-Nakamoto Blocks

In this section, we define catch-up events and $\eta$-Nakamoto blocks.

##### Adversarial arrivals

Let $a(b_{i},b_{j})$ denote the number of adversarial blocks mined between the
mining times of the $i$-th and $j$-th honest blocks. Similarly, let
$a(b_{j}^{i},b_{j}^{k})$ denote the number of adversarial blocks mined between
the $i$-th and $k$-th $j\mathchar 45\relax\mathsf{FS}$ blocks.

######  Definition 4.14 (Catch-up Events).

Let $0\leq i<j<k$, and let $0<\eta\leq 1$. The forward and backward catch-up
events are respectively defined as:

$\displaystyle\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$
$\displaystyle\colon
a(b_{j},b_{k})\geq\eta\cdot\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right)$
(1) $\displaystyle\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$
$\displaystyle\colon
a(b_{i},b_{j})\geq\eta\cdot\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)$
(2)

These events are catch-up events in the following sense. If the event
$\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$ occurs for some $j<k$
and $0<\eta\leq 1$, then more adversarial blocks have been mined in
$[\tau_{j},\tau_{k}]$ than _effective_ $j\mathchar 45\relax\mathsf{FS}$
blocks. For instance, when $\eta=1$, more adversarial blocks have been mined
in $\left[\tau_{j},\tau_{k}\right]$ than the number of blocks in the
$j\mathchar 45\relax\mathsf{FS}$ sequence from $b_{j}$ up to the last
$j\mathchar 45\relax\mathsf{FS}$ block heard by the miner of $b_{k}$. If these
adversarial blocks were to form a side chain rooted at $b_{j}$, then there is
a possibility that $b_{k}$ mines on this side chain. However, such an attack
would fail if the catch-up events did not occur, because there would
necessarily be a chain longer than the adversarial side chain that the miner
of $b_{k}$ is aware of. Here, $\eta$ is a robustness measure: If the catch-up
event does not occur for a small value of $\eta$, then the honest blocks have
a considerable lead over adversarial side chains.

##### Longest Chains of the main-blocktree

A longest chain of the main-blocktree at time $t$ is a path in
$\mathsf{MB}(t)$ whose length is no shorter than any path in $\mathsf{MB}(t)$.
Notice that $\mathsf{MB}(t)$ can have multiple longest chains.

#####  $\eta$-Nakamoto Blocks

A desirable property for honest block $b_{j}$ is the existence of some
$0<\eta\leq 1$ such that none of the events
$\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$ occur for any $i<j$
and none of the events $\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$
occur for any $k>j$. Intuitively, this ensures that adversarial chains rooted
at any block $b_{i}$ with $i<j$ are never long enough for any block $b_{k}$
with $k>j$ to extend them. In turn, this suggests that block $b_{j}$ would be
in every longest chain of the main-blocktree right from being mined. We
formalize this property using the notion of $\eta$-Nakamoto blocks below, and
make this intuition rigorous in Section 5.

######  Definition 4.15 ($\eta$-Nakamoto Block).

Let $j\geq 0$ and $0<\eta\leq 1$. The $j$-th honest block $b_{j}$ is said to
be an $\eta$-Nakamoto block if the event

$\displaystyle\mathsf{N}_{j}^{\left(\eta\right)}\colon\left[\bigcap_{i\colon
i<j}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right]\bigcap\left[\bigcap_{k\colon
k>j}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right]$
(3)

occurs.

We remark that an $\eta$-Nakamoto block is also an $\eta^{\prime}$-Nakamoto
block, for any $\eta^{\prime}\in[\eta,1]$.

###  4.5 User-unheard-criterion

$\eta$-Nakamoto blocks are useful because they belong to every longest chain
of the main-blocktree. However, this is not equivalent to $\eta$-Nakamoto
blocks belonging to any user’s chain for all future time. This is because at
any given time, a given user has not necessarily heard of all the blocks in
$\mathsf{MB}(t)$. In this section, we introduce the tools that are relevant to
analyzing the state of a user’s chain with respect to the main-blocktree. We
begin by introducing ‘Unheard’ with respect to a user.

######  Definition 4.16 (User-unheard,
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$).

Let $j\geq 0$ and let $b_{j}$ be the $j$-th honest block. Let
$(b_{j}^{0},b_{j}^{1},\cdots)$ denote the $j\mathchar 45\relax\mathsf{FS}$
sequence. Let $h$ be an honest user. For any $k\geq 0$, we define
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ as the number of consecutive
$j\mathchar 45\relax\mathsf{FS}$ blocks that the user $h$ has not heard of,
going backwards along the $j\mathchar 45\relax\mathsf{FS}$ sequence from
$b_{j}^{k}$. If $h$ has not heard of any $j\mathchar 45\relax\mathsf{FS}$
block, then we toss independent biased coins (with failure probability equal
to the probability of message loss) and continue to increment the count until
a success is encountered.

######  Remark 4.17.

Let $j,k\geq 0$. Let $h$ be any honest user and $d$ be the probability of
message loss. Let $\mathsf{Geom}(1-d)$ be a geometric random variable, with
minimum value 1. The distribution of the random variable
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ depends on $h$:

  * •

If $h$ has not mined any block after the mining time of $b_{j}$, then
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ has the same distribution as
$\mathsf{Geom}\left(1-d\right)-1$.

  * •

If $h$ is a miner of a $j\mathchar 45\relax\mathsf{FS}$ block, then $h$ has
heard of its own block as well as the $j\mathchar 45\relax\mathsf{FS}$ block
that immediately preceded it. However, all other delays from the miners of
$j\mathchar 45\relax\mathsf{FS}$ blocks to $h$ are still independent and
identically distributed. In this case,
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ is stochastically dominated by
$\mathsf{Geom}(1-d)$.

  * •

If $h$ is a miner of a block $b_{\ell}$ with $\ell>j$, such that $b_{\ell}$ is
not a $j\mathchar 45\relax\mathsf{FS}$ block, then the delay from the most
recent $j\mathchar 45\relax\mathsf{FS}$ block before $b_{\ell}$ to $h$ is
infinity. However, all other delays from the miners of $j\mathchar
45\relax\mathsf{FS}$ blocks to $h$ are still independent and identically
distributed. In this case, $\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ is
stochastically dominated by $\mathsf{Geom}(1-d)$.

In all cases, we have
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)\leq\mathsf{Geom}\left(1-d\right)$,
where the $\leq$ sign indicates stochastic domination.

We compare ‘forward-unheard’ (denoted $\mathsf{FU}_{j}\left(b_{k}\right)$) and
‘user-unheard’ (denoted $\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$).
Although similar in spirit, the quantity $\mathsf{FU}_{j}\left(b_{k}\right)$
counts the number of consecutive $j\mathchar 45\relax\mathsf{FS}$ blocks not
heard by the miner of block $b_{k}$, going backwards in the $j\mathchar
45\relax\mathsf{FS}$ sequence from the last such block before $b_{k}$, whereas
the quantity $\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ fixes an honest user
$h$ and similarly counts the number of consecutive such blocks not heard by
$h$. Since $b_{k}$ and $b_{\ell}$ are mined by two different miners, then
$\mathsf{FU}_{j}\left(b_{k}\right)$ and $\mathsf{FU}_{j}\left(b_{\ell}\right)$
are independent random variables. However,
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$ and
$\mathsf{Unheard}_{h}\left(b_{j}^{\ell}\right)$ need not be independent.

Next, we introduce the user-unheard-criterion, which will later allow us to
infer useful information about the state of a user’s chain from the main-
blocktree.

######  Definition 4.18 (User-unheard-criterion).

Let $h$ be an honest user. Let $j\geq 1$, $k_{0}\geq 1$, and $0<\eta<1$. We
say that the $\left(h,j,\eta,k_{0}\right)$-user-unheard-criterion is satisfied
if

$\displaystyle\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)<\left(\frac{1-\eta}{2}\right)k,\quad\forall
k\geq k_{0},$ (4)

##  5 Proof Outline

In this section, we present an outline of the proof of Theorem 3.2. First,
deterministic and probabilistic results are stated. These results are used as
building blocks in the proof sketch of our main result, Theorem 3.2 which is
presented in Section 5.3. Rigorous proofs of all the results, including the
main result are relegated to the appendix.

###  5.1 Deterministic Results

######  Theorem 5.1.

Let $j\geq 1$ and $0<\eta\leq 1$. Let $b_{j}$ be the $j$-th honest block, and
$\tau_{j}$ be the mining time of $b_{j}$. Suppose $b_{j}$ is an
$\eta$-Nakamoto block. Then:

  1. (i)

$b_{j}$ is the unique honest block at its height in $\mathsf{MB}(t)$ for all
$t\geq\tau_{j}$.

  2. (ii)

$b_{j}$ is in every longest chain of $\mathsf{MB}(t)$ for all $t\geq\tau_{j}$.

  3. (iii)

$b_{j}$ is the unique block at its height in $\mathsf{MB}(\tau_{j})$.

  4. (iv)

For any $k$ such that $k>j$, $b_{k}$ is a descendant of $b_{j}$ in the main-
blocktree.

###### Proof.

See Appendix A.1 ∎

######  Theorem 5.2.

Let $h$ be an honest user. Let $j\geq 1$ and $0<\eta<1$. Let
$k_{0}=\left\lceil\frac{2\eta}{1-\eta}\right\rceil$. Let $\mathcal{C}_{h}(t)$
denote the chain held by $h$ at time $t$. If $b_{j}$ is an $\eta$-Nakamoto
block, and if the $\left(h,j,\eta,k_{0}\right)$-user-unheard-criterion is
satisfied, then $b_{j}\in\mathcal{C}_{h}(t)$ for all $t\geq\tau_{j}^{k_{0}}$,
where $\tau_{j}^{k_{0}}$ is the mining time of the $k_{0}$-th $j\mathchar
45\relax\mathsf{FS}$ block.

###### Proof.

See Appendix A.2. ∎

###  5.2 Probabilistic Results

######  Lemma 5.3.

Let $0\leq i<j\leq j^{\prime}<k$, and $0\leq\eta\leq 1$. The events:

  * •

$\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ and
$\overrightarrow{\mathsf{B}}_{j^{\prime},k}^{\left(\eta\right)}$ are
independent.

  * •

$\overrightarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ and
$\overleftarrow{\mathsf{B}}_{j^{\prime},k}^{\left(\eta\right)}$ are
independent.

###### Proof.

See Appendix B.1. ∎

######  Theorem 5.4.

Let $j\geq 1$ and $0\leq\eta\leq 1$. Recall that $b_{j}$ is the $j$-th honest
block and $\mathsf{N}_{j}^{\left(\eta\right)}$ is the event that $b_{j}$ is an
$\eta$-Nakamoto block. If $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$,
then there exists a positive constant $p_{0}>0$ such that

$\displaystyle\mathbb{P}\left(\mathsf{N}_{j}^{\left(\eta\right)}\right)\geq
p_{0}>0$

###### Proof.

See Appendix B.2. ∎

######  Lemma 5.5.

Let $0<\eta\leq 1$ and $i<j<k$. Let
$\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$ and
$\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ be the catch-up events
defined in (1), (2). If $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$,
there exists a constant $c>0$ such that

$\displaystyle\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)$
$\displaystyle\leq e^{-c\left(k-j\right)}$
$\displaystyle\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)$
$\displaystyle\leq e^{-c\left(j-i\right)}$

###### Proof.

See Appendix B.3. ∎

######  Theorem 5.6.

Let $0<\eta\leq 1$. Let $\beta$ be the fraction of computational power in the
system that is adversarial and $d$ be the probability of message loss. Let
$B_{s,s+t}^{\left(\eta\right)}$ be the event that there are no $\eta$-Nakamoto
blocks in $[s,s+t]$. If $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$,
then there exists a constant $c_{0}>0$ such that for any $s,t\geq 0$,

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq
e^{-c_{0}\sqrt{t}}$

###### Proof.

See Appendix B.4. ∎

######  Theorem 5.7.

Let $0<\eta\leq 1$. Let $\beta$ be the fraction of computational power in the
system that is adversarial and $d$ be the probability of message loss. Let
$B_{s,s+t}^{\left(\eta\right)}$ be the event that there are no $\eta$-Nakamoto
blocks in $\left[s,s+t\right]$. If
$\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$, then for every
$\varepsilon>0$, there exist positive constants $A$, $a$ such that for any
$s,t>0$,

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq
A\exp\left(-at^{1-\varepsilon}\right).$

###### Proof.

See Appendix B.5. ∎

######  Theorem 5.8.

Let $0<\eta<1$. Suppose the fraction $\beta$ of computational power in the
system that is adversarial, and the probability $d$ of message loss satisfies
$\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$. Given $s\geq 0$, let
$b_{J}$ be the first $\eta$-Nakamoto block mined after time $s$. There exist
constants $C$, $c>0$ such that for any honest user $h$ and for all
$k^{\prime}\geq 1$,

$\displaystyle\mathbb{P}\left(\left(h,J,\eta,k^{\prime}\right)\mathchar
45\relax\text{user-unheard-criterion fails}\right)\leq Ce^{-ck^{\prime}}$

###### Proof.

See Appendix B.6. ∎

###  5.3 Proof Sketch

$\eta$-Nakamoto blocks are special blocks that are part of every longest chain
in the main-blocktree, for all time after they are mined (Theorem 5.1).
Therefore, if a transaction is included in an $\eta$-Nakamoto block or in any
of its ancestors, then it will be included in every longest chain of the main-
blocktree. Furthermore, if an honest user is up-to-date with the main-
blocktree (specifically, by satisfying a relevant user-unheard-criterion, and
therefore having heard of more forward special blocks with respect to the
$\eta$-Nakamoto block, than adversarial blocks), then it is reasonable to
expect that the honest user will also include the transaction in its chain.
This idea is formalized in the user-unheard-criterion, and made rigorous in
Theorem 5.2.

The core idea behind the proof of the main result (Theorem 3.2) is to show
that $\eta$-Nakamoto blocks occur frequently with high probability (Theorem
5.7). In turn, this implies that a transaction is highly likely to be included
in an $\eta$-Nakamoto block or its ancestor, soon after it is made. Theorem
5.8 then shows that it is also highly likely that a relevant user-unheard-
criterion will hold for the honest user, once a waiting time has elapsed.

To prove Theorem 5.7, we bootstrap from a milder version of it, which is
stated as Theorem 5.6. Inspired by the proof strategy in [DKT+20], we prove
Theorem 5.6 by separating catch-up events into long and short-term catch-up
events. We show that long term catch-ups occur rarely as a consequence of
Lemma 5.5, and short-term catch-up probabilities are bounded using a lower
bound on the probability that the $j$-th block is an $\eta$-Nakamoto block
(Theorem 5.4), and the fact that non-overlapping catch-up events are
independent (Lemma 5.3). This establishes that a transaction is highly likely
to be included in the main-blocktree for all future time, once a waiting
period has elapsed. This proves thereom 5.7.

Next, we show that an honest user is likely to always be up-to-date with the
main-blocktree, forever after a waiting time. This is done by explicitly
bounding the probability that a relevant user-unheard-criterion is violated
using tools from stochastic analysis. This proves Theorem 5.8.

Theorems 5.7 and 5.8 together imply the main result. The details of this proof
are presented in Appendix B.7.

##  6 Conclusion

In this work, we introduced the $0\mathchar 45\relax\infty$ model: a framework
to study the impact of random message losses on the security of the proof-of-
work longest-chain protocol. We investigated the security of this protocol by
analyzing the transmission-graph, a dynamically evolving graph that captures
the delays incurred by the blocks mined by honest miners. Specifically, we
studied special sequences of blocks and identified random variables associated
with them that are amenable to analysis. These random variables were used to
define useful objects and desirable events, such as $\eta$-Nakamoto blocks and
user-unheard-criterion respectively. These ideas allowed us to generalize
analysis techniques from the synchronous delay model to a setting where delays
are possibly infinite. We showed that the condition
$\frac{\beta}{1-\beta}<1-d$ is sufficient for a transaction to satisfy desired
security properties except with a probability that decays almost exponentially
in the security parameter. This greatly improved the known threshold of the
fraction of adversarial power that is tolerable for a given probability of
message loss in an instance of point-to-point communication.

## References

  * [BKM+20] Erica Blum, Aggelos Kiayias, Cristopher Moore, Saad Quader, and Alexander Russell.  The combinatorics of the longest-chain rule: Linear consistency for proof-of-stake blockchains.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1135–1154. SIAM, 2020.
  * [BSAB+19] Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis.  Sok: Consensus in the age of blockchains.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 183–198, 2019.
  * [DKT+20] 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 Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 859–878, 2020.
  * [DLS88] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer.  Consensus in the presence of partial synchrony.  Journal of the ACM (JACM), 35(2):288–323, 1988.
  * [FZ17] Lei Fan and Hong-Sheng Zhou.  A scalable proof-of-stake blockchain in the open setting (or, how to mimic nakamoto’s design via proof-of-stake).  Technical report, Cryptology ePrint Archive, Report 2017/656, 2017.
  * [GK20] Juan Garay and Aggelos Kiayias.  Sok: A consensus taxonomy in the blockchain era.  In Cryptographers’ Track at the RSA Conference, pages 284–318. Springer, 2020.
  * [GKL15] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol: Analysis and applications.  In Annual international conference on the theory and applications of cryptographic techniques, pages 281–310. Springer, 2015.
  * [GKL20] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  Full analysis of nakamoto consensus in bounded-delay networks.  Cryptology ePrint Archive, 2020.
  * [GKR20] Peter Gaži, Aggelos Kiayias, and Alexander Russell.  Tight consistency bounds for bitcoin.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 819–838, 2020.
  * [Kin64] John F Kingman.  A martingale inequality in the theory of queues.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 60, pages 359–361. Cambridge University Press, 1964.
  * [KRDO17] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In Annual International Cryptology Conference, pages 357–388. Springer, 2017.
  * [LGR21] Jing Li, Dongning Guo, and Ling Ren.  Close latency-security trade-off for the nakamoto consensus.  In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 100–113, 2021.
  * [MU17] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomization and probabilistic techniques in algorithms and data analysis.  Cambridge University Press, 2017.
  * [Nak08] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  Decentralized Business Review, page 21260, 2008.
  * [NTT21] Joachim Neu, Ertem Nusret Tas, and David Tse.  Ebb-and-flow protocols: A resolution of the availability-finality dilemma.  In 2021 IEEE Symposium on Security and Privacy (SP), pages 446–465. IEEE, 2021.
  * [PS17] Rafael Pass and Elaine Shi.  The sleepy model of consensus.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 380–409. Springer, 2017.
  * [PSS17] Rafael Pass, Lior Seeman, and Abhi Shelat.  Analysis of the blockchain protocol in asynchronous networks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 643–673. Springer, 2017.
  * [Ren19] Ling Ren.  Analysis of nakamoto consensus.  IACR Cryptol. ePrint Arch., 2019:943, 2019.
  * [SGH21] Suryanarayana Sankagiri, Shreyas Gandlur, and Bruce Hajek.  The longest-chain protocol under random delays.  arXiv preprint arXiv:2102.00973, 2021.

##  Appendix A Proofs of Deterministic Results

###  A.1 Proof of Theorem 5.1

######  Theorem 5.1.

Let $j\geq 1$ and $0<\eta\leq 1$. Let $b_{j}$ be the $j$-th honest block, and
$\tau_{j}$ be the mining time of $b_{j}$. Suppose $b_{j}$ is an
$\eta$-Nakamoto block. Then:

  1. (i)

$b_{j}$ is the unique honest block at its height in $\mathsf{MB}(t)$ for all
$t\geq\tau_{j}$.

  2. (ii)

$b_{j}$ is in every longest chain of $\mathsf{MB}(t)$ for all $t\geq\tau_{j}$.

  3. (iii)

$b_{j}$ is the unique block at its height in $\mathsf{MB}(\tau_{j})$.

  4. (iv)

For any $k$ such that $k>j$, $b_{k}$ is a descendant of $b_{j}$ in the main-
blocktree.

###### Proof.

Let $\mathsf{N}_{j}^{\left(\eta\right)}$ be the event that $b_{j}$ is an
$\eta$-Nakamoto block. Recall that

$\displaystyle\mathsf{N}_{j}^{\left(\eta\right)}=\left[\bigcap_{i\colon
i<j}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right]\bigcap\left[\bigcap_{k\colon
k>j}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right]$

Suppose $\mathsf{N}_{j}^{\left(\eta\right)}$ occurs, so that $b_{j}$ is an
$\eta$-Nakamoto block.

  1. (i)

Let $t\geq\tau_{j}$. We show that $b_{j}$ is the unique honest block at its
height in $\mathsf{MB}(t)$, i.e. for any $i,k\geq 0$ such that $i<j<k$, we
show that

$\displaystyle
0pt{\mathsf{MB}}{b_{i}}<0pt{\mathsf{MB}}{b_{j}}<0pt{\mathsf{MB}}{b_{k}}.$ (5)

We begin by proving the first inequality in (5). Since
$\mathsf{N}_{j}^{\left(\eta\right)}$ occurs, it follows that the event
$\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}$
occurs. Therefore, we have

$\displaystyle 0pt{\mathsf{MB}}{b_{j}}-0pt{\mathsf{MB}}{b_{i}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\eta\cdot\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{>}}a(b_{i},b_{j}),$

where (a) is from Lemma 4.13, (b) follows from the fact that $\eta\leq 1$, and
(c) is the definition of
$\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}$.
Since $a(b_{i},b_{j})\geq 0$, it follows that
$0pt{\mathsf{MB}}{b_{i}}<0pt{\mathsf{MB}}{b_{j}}$. Similarly, the occurrence
of
$\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}$
implies that $0pt{\mathsf{MB}}{b_{j}}<0pt{\mathsf{MB}}{b_{k}}$. Thus, $b_{j}$
is the unique honest block at its height in $\mathsf{MB}(t)$.

  2. (ii)

We show that $b_{j}$ is in every longest chain of $\mathsf{MB}(t)$. Let
$\mathcal{V}$ be any longest chain in $\mathsf{MB}(t)$, i.e.

$\mathcal{V}=v_{0}-v_{1}-\cdots-v_{0pt{\mathsf{MB}}{b_{j}}}-\cdots-
v_{m-1}-v_{m},$

where $v_{0}$ is the genesis block, $v_{0pt{\mathsf{MB}}{b_{j}}}=:v$ is the
block at the height of $b_{j}$, and $m$ is the height of $\mathsf{MB}(t)$. It
suffices to show that $v=b_{j}$. In fact, since $b_{j}$ is the unique honest
block at its height, it suffices to only show that $v$ must be an honest
block. Starting from $v$ and traversing blocks in $\mathcal{V}$ in the
backward direction, let $b_{i}$ denote the first honest block encountered in
$\mathcal{V}$, not including $v$ itself. Since the genesis block is honest,
such a $b_{i}$ exists. Similarly, we also want to traverse blocks in
$\mathcal{V}$ along the forward direction. Here, we have two cases:

Case 1: There is an honest block in $\mathcal{V}$ after $v$. In this case, let
$b_{k}$ be the first honest block in $\mathcal{V}$ after $v$. Let $H$ denote
$0pt{\mathsf{MB}}{b_{k}}$, and $\mathcal{V}_{1}$ be the sequence
$b_{i}-\cdots-v-\cdots-b_{k}$.

Case 2: There is no honest block in $\mathcal{V}$ after $v$. In this case, let
$b_{k}$ be the first honest block mined after time $t$. Let $H=m$ denote the
height of the main-blocktree, and $\mathcal{V}_{1}$ be the sequence
$b_{i}-\cdots-v-\cdots-v_{m}$.

In both cases, let $N$ denote the number of blocks in $\mathcal{V}_{1}$, not
including $b_{i}$. Notice that the blocks are at consecutive heights. We have:

$\displaystyle N$ $\displaystyle=H-0pt{\mathsf{MB}}{b_{i}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}0pt{\mathsf{MB}}{b_{j}}+\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right)-0pt{\mathsf{MB}}{b_{i}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\left(\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right)\right)+\left(\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\left(a(b_{i},b_{j})+1\right)+\left(a(b_{j},b_{k})+1\right)$
$\displaystyle>a(b_{i},b_{k})+1,$

where (a) follows from Lemma 4.13 in case 1, and the fact that $j\mathchar
45\relax\mathsf{FS}$ blocks are mined at different heights in case 2. Further,
(b) is due to Lemma 4.13 and the fact that $\eta\leq 1$, and (c) follows
because the events
$\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}$
and
$\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}$
occur. However, by definition of $b_{i}$ and $b_{k}$, all blocks in
$\mathcal{V}_{1}$ after $b_{i}$ except for $b_{k}$ and possibly $v$ are
adversarial. Therefore, there must be at least one honest block in
$\mathcal{V}_{1}$ strictly between $b_{i}$ and $b_{k}$. Since the only
possibility for this is $v$, it follows that $v$ must be an honest block.
Since $b_{j}$ is the unique honest block at the height of $v$, we conclude
that $b_{j}$ in every longest chain of $\mathsf{MB}(t)$, as desired.

  3. (iii)

Let $v$ be a block in $\mathsf{MB}(\tau_{j})$ such that
$0pt{\mathsf{MB}}{v}=0pt{\mathsf{MB}}{b_{j}}$. Let $\mathcal{T}$ be the tine
of ancestors of $v$. Traversing blocks along the backward direction starting
from $v$, let $b_{i}$ denote the first honest block encountered. The portion
of $\mathcal{T}$ between $b_{i}$ and $v$ consists of only adversarial blocks.
However,

$\displaystyle 0pt{\mathsf{MB}}{v}-0pt{\mathsf{MB}}{b_{i}}$
$\displaystyle=0pt{\mathsf{MB}}{b_{j}}-0pt{\mathsf{MB}}{b_{i}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\eta\cdot\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{>}}a(b_{i},b_{j}),$

where (a) is from Lemma 4.13, and (b) is true because $b_{j}$ is an
$\eta$-Nakamoto block. Since $v$ is the only possibility for an honest block
in the portion of $\mathcal{T}$ after $b_{i}$, it follows that $v$ must be an
honest block. From (i), we conclude that $v=b_{j}$. This concludes the proof.

  4. (iv)

Let $k>j$. Since $b_{j}$ is an $\eta$-Nakamoto block, we have from the proof
of (i) that $0pt{\mathsf{MB}}{b_{k}}>0pt{\mathsf{MB}}{b_{j}}$. Let $v$ denote
the ancestor of $b_{k}$ at the height of $b_{j}$ in the main-blocktree.
Starting from $v$ and traversing blocks along the ancestors of $v$, let
$b_{i}$ denote the first honest block encountered. This is exactly case 1 in
the proof of (ii), and it follows that $v=b_{j}$.

∎

###  A.2 Proof of Theorem 5.2

######  Theorem 5.2.

Let $h$ be an honest user. Let $j\geq 1$ and $0<\eta<1$. Let
$k_{0}=\left\lceil\frac{2\eta}{1-\eta}\right\rceil$. Let $\mathcal{C}_{h}(t)$
denote the chain held by $h$ at time $t$. If $b_{j}$ is an $\eta$-Nakamoto
block, and if the $\left(h,j,\eta,k_{0}\right)$-user-unheard-criterion is
satisfied, then $b_{j}\in\mathcal{C}_{h}(t)$ for all $t\geq\tau_{j}^{k_{0}}$,
where $\tau_{j}^{k_{0}}$ is the mining time of the $k_{0}$-th $j\mathchar
45\relax\mathsf{FS}$ block.

###### Proof.

Let $|\mathcal{C}_{h}(t)|$ denote the number of blocks in
$\mathcal{C}_{h}(t)$. Let $\tau_{j}$ denote the mining time of $b_{j}$, and
let $\tau_{j}^{k}$ denote the mining time of $b_{j}^{k}$. Since $b_{j}$ is an
$\eta$-Nakamoto block, we know that the event
$\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}$
occurs for all $k>j$. In turn, this implies

$\displaystyle a(b_{j}^{0},b_{j}^{k+1})<\eta\cdot\left(k+1\right)\quad\forall
k>0.$

However, $\eta\left(k+1\right)\leq\left(\frac{1+\eta}{2}\right)k$ whenever
$k\geq k_{0}$. Further, since $\left(h,j,\eta,k_{0}\right)$-user-unheard-
criterion holds, we have that
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)<\left(\frac{1-\eta}{2}\right)k$
whenever $k\geq k_{0}$. These facts imply:

$\displaystyle
a(b_{j}^{0},b_{j}^{k+1})<k-\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)\quad\forall
k\geq k_{0}.$ (6)

Fix $k\geq k_{0}$. Let $t$ be such that $\tau_{j}^{k}\leq t<\tau_{j}^{k+1}$.
We show that $h$ includes $b_{j}$ in its chain at time $t$.

Since $a(b_{j}^{0},b_{j}^{k+1})\geq 0$, it follows from (6) that
$\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)<k$. Therefore, $h$ has heard of at
least one $j\mathchar 45\relax\mathsf{FS}$ block. Therefore,
$|\mathcal{C}_{h}(t)|\geq 0pt{\mathsf{MB}}{b_{j}}$. Let
$v\in\mathcal{C}_{h}(t)$ be the block at the height of $b_{j}$. To show that
$b_{j}\in\mathcal{C}_{h}(t)$, it suffices by statement (iv) in Theorem 5.1 to
prove that $\mathcal{C}_{h}(t)$ contains at least one honest block mined in
$[\tau_{j}^{k},\infty)$.

Let $\mathcal{C}_{h}(t)^{\lceil v}$ denote the sub-chain of
$\mathcal{C}_{h}(t)$ starting from $v$, i.e. $\mathcal{C}_{h}(t)^{\lceil v}$
contains blocks of $\mathcal{C}_{h}(t)$ that are at height no less than that
of $v$. We show that (6) implies that $\mathcal{C}_{h}(t)^{\lceil v}$ cannot
contain all adversarial blocks. We know from statement (iii) of Theorem 5.1
that $b_{j}$ is the unique block at its height in $\mathsf{MB}(\tau_{j})$.
Therefore, all blocks in $\mathcal{C}_{h}(t)^{\lceil v}$ are mined at or after
time $\tau_{j}$. Since $t<\tau_{j}^{k+1}$, we have

$\displaystyle
a(b_{j}^{0},b_{j}^{k+1})\stackrel{{\scriptstyle(a)}}{{<}}k-\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)\stackrel{{\scriptstyle(b)}}{{\leq}}|\mathcal{C}_{h}(t)^{\lceil
v}|,$

where (a) is the same as (6) and (b) follows from the fact that $h$ has heard
of $b_{j}^{m}$, where $m=k-\mathsf{Unheard}_{h}\left(b_{j}^{k}\right)$.
Therefore, $h$ adopts a chain that has length at least
$0pt{\mathsf{MB}}{v}+m$. We conclude that there exists an honest block
$b_{k}\in\mathcal{C}_{h}(t)^{\lceil v}$. From statement (iv) in Theorem 5.1,
it follows that $\mathcal{C}_{h}(t)$ contains $b_{j}$.

The above argument is true for all $t\in[\tau_{j}^{k},\tau_{j}^{k+1})$, so it
follows that $h\in\mathcal{C}_{h}(t)$ for all
$t\in[\tau_{j}^{k},\tau_{j}^{k+1})$. Since this is true for all $k\geq k_{0}$,
it follows that $h\in\mathcal{C}_{h}(t)$ for all $t\geq\tau_{j}^{k_{0}}$, as
desired. ∎

##  Appendix B Proofs of Probabilistic Results

###  B.1 Proof of Lemma 5.3

######  Lemma 5.3.

Let $0\leq i<j\leq j^{\prime}<k$, and $0\leq\eta\leq 1$. The events:

  * •

$\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ and
$\overrightarrow{\mathsf{B}}_{j^{\prime},k}^{\left(\eta\right)}$ are
independent.

  * •

$\overrightarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ and
$\overleftarrow{\mathsf{B}}_{j^{\prime},k}^{\left(\eta\right)}$ are
independent.

###### Proof.

We prove only the first statement, since the second uses a similar argument.
For any $m\in\\{i,j,j^{\prime},k\\}$, let $\tau_{m}$ denote the mining time of
$b_{m}$. The LHS of the event

$\displaystyle\overrightarrow{\mathsf{B}}_{j^{\prime},k}^{\left(\eta\right)}$
$\displaystyle\colon
a(b_{j^{\prime}},b_{k})\geq\eta\cdot\mathsf{FS}_{j^{\prime}}\left(b_{k-1}\right)-\mathsf{FU}_{j^{\prime}}\left(b_{k}\right)$

depends on the number of adversarial arrivals in
$[\tau_{j^{\prime}},\tau_{k}]$. Further, the RHS depends on the delays from
$b_{j^{\prime}}$ to all the honest blocks mined in
$[\tau_{j^{\prime}},\tau_{k})$.

In contrast, the LHS of the event

$\displaystyle\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$
$\displaystyle\colon
a(b_{i},b_{j})\geq\eta\cdot\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right)$

depends on the number of adversarial arrivals in $[\tau_{i},\tau_{j}]$.
Further, the RHS depends on the delays from all the honest blocks mined in
$[\tau_{i},\tau_{j})$ to $b_{j}$.

Since honest and adversarial arrivals are independent Poisson processes, and
since the delay associated with any two blocks in $[\tau_{i},\tau_{j}]$ is
independent of the delay associated with any two blocks in
$[\tau_{j^{\prime}},\tau_{k}]$, and since the two intervals do not overlap, it
follows that $\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ and
$\overrightarrow{\mathsf{B}}_{j^{\prime},k}^{\left(\eta\right)}$ are
independent. ∎

###  B.2 Proof of Theorem 5.4

######  Theorem 5.4.

Let $j\geq 1$ and $0\leq\eta\leq 1$. Recall that $b_{j}$ is the $j$-th honest
block and $\mathsf{N}_{j}^{\left(\eta\right)}$ is the event that $b_{j}$ is an
$\eta$-Nakamoto block. If $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$,
then there exists a positive constant $p_{0}>0$ such that

$\displaystyle\mathbb{P}\left(\mathsf{N}_{j}^{\left(\eta\right)}\right)\geq
p_{0}>0$

###### Proof.

Fix $j$. Recall that the event
$\mathsf{N}_{j}^{\left(\eta\right)}=\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\bigcap\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}$,
where
$\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}=\bigcap\limits_{i\colon
i<j}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}$
and
$\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}=\bigcap\limits_{k\colon
k>j}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}$.
From Lemma 5.3, it follows that
$\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}$ and
$\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}$ are independent events.
Therefore,

$\displaystyle\mathbb{P}\left(\mathsf{N}_{j}^{\left(\eta\right)}\right)=\mathbb{P}\left(\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\bigcap\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)=\mathbb{P}\left(\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\mathbb{P}\left(\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right).$

Thus, it suffices to show the existence of $p>0$ such that
$\mathbb{P}\left(\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\geq
p$ and
$\mathbb{P}\left(\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\geq
p$.

##### Notation:

If an i.i.d. random process is a sequence of random variables with known
distribution, say Geometric or Bernoulli with parameter $q$, we refer to the
$i$-th random variable in the sequence as $\mathsf{Geom}_{i}(q)$ or
$\mathsf{Be}_{i}(q)$ respectively.

Showing
$\mathbb{P}\left(\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\geq
p>0$: By definition, the event
$\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}$ occurs if

$\displaystyle
a(b_{j},b_{k})-\eta\cdot\mathsf{FS}_{j}\left(b_{k-1}\right)<-\mathsf{FU}_{j}\left(b_{k}\right)\
\forall k>j.$ (7)

Notice that the LHS are RHS are independent random variables. The random
variables inn the LHS are:

$\displaystyle a(b_{j},b_{k})$
$\displaystyle=\sum_{i=1}^{k-j}\left(\mathsf{Geom}_{i}\left(1-\beta\right)-1\right),$
(8) $\displaystyle\mathsf{FS}_{j}\left(b_{k-1}\right)$
$\displaystyle=1+\sum_{i=1}^{k-j-1}\mathsf{Be}_{i}\left(1-d\right),$ (9)

where equation (8) follows from the fact that there are
$\mathsf{Geom}\left(1-\beta\right)-1$ adversarial arrivals between two
successive honest arrivals, and the fact that the number of adversarial
arrivals in disjoint intervals is independent. Equation (9) follows from
Remark 4.4.

Let $\left(\mathsf{X}_{i}\colon i\geq 1\right)$ be an i.i.d. random process,
with
$\mathsf{X}_{i}\sim\mathsf{Geom}_{i}\left(1-\beta\right)-1-\eta\cdot\mathsf{Be}_{i}\left(1-d\right)$.
Let $\mathsf{W}_{j}=\sum_{i=1}^{j}\mathsf{X}_{i}$ denote the sum of the first
$j$ terms of the process $\left(\mathsf{X}_{i}\colon i\geq 1\right)$. Finally,
it follows from Remark 4.7 that $\left(\mathsf{FU}_{j}\left(b_{k}\right)\colon
k>j\right)$ is identical to the i.i.d. random process
$\left(\mathsf{Y}_{i}\colon i>0\right)$, with
$\mathsf{Y}_{i}\sim\mathsf{Geom}_{i}\left(1-d\right)-1$. Using these random
variables, equation (7) can be equivalently stated as

$\displaystyle\sum_{i=1}^{k-j}\mathsf{X}_{i}<-\mathsf{Y}_{k-j}\quad\forall
k>j.$ (10)

Let $\gamma$ be a constant to be determined later, such that $0<\gamma<\eta$.
The inequality in (10) holds if
$\mathsf{E}_{\mathsf{A}}\cap\mathsf{E}_{\mathsf{B}}$ occur, where

$\displaystyle\mathsf{E}_{\mathsf{A}}$
$\displaystyle\colon\sum_{j=1}^{i}\mathsf{X}_{j}<-\gamma i\quad\forall i\geq
1$ $\displaystyle\mathsf{E}_{\mathsf{B}}$ $\displaystyle\colon-\gamma
i<-\mathsf{Y}_{i}\quad\forall i\geq 1.$

Here, $\mathsf{E}_{\mathsf{A}}$ and $\mathsf{E}_{\mathsf{B}}$ are independent
events. Therefore, we have
$\mathbb{P}\left(\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\geq\mathbb{P}\left(\mathsf{E}_{\mathsf{A}}\cap\mathsf{E}_{\mathsf{B}}\right)=\mathbb{P}\left(\mathsf{E}_{\mathsf{A}}\right)\mathbb{P}\left(\mathsf{E}_{\mathsf{B}}\right)$.
It suffices to show the existence of $p_{1},p_{2}>0$ such that
$\mathbb{P}\left(\mathsf{E}_{\mathsf{A}}\right)\geq p_{1}$ and
$\mathbb{P}\left(\mathsf{E}_{\mathsf{B}}\right)\geq p_{2}$. First, we bound
$\mathbb{P}\left(\mathsf{E}_{\mathsf{B}}\right)$.

$\displaystyle\mathbb{P}\left(\mathsf{E}_{\mathsf{B}}\right)=\mathbb{P}\left(\bigcap_{i\geq
1}\left\\{\mathsf{Y}_{i}\leq\gamma
i\right\\}\right)=\prod_{i=1}^{\infty}\left(1-d^{1+\gamma i}\right)=:p_{2}>0,$

since $\left(\mathsf{Y}_{i}\colon i\geq 1\right)$ is an i.i.d process with
$1+\mathsf{Y}_{i}\sim\mathsf{Geom}_{i}\left(1-d\right)$. Notice that $p_{2}>0$
for all $0\leq d<1$ and for all $\gamma>0$.

Next, we bound $\mathbb{P}\left(\mathsf{E}_{\mathsf{A}}\right)$. Fix some
$\ell\in\mathbb{N}$, and let $c$ be a positive constant given by
$c=\left(\eta-\gamma\right)\ell$. Consider the following two desirable events:

$\displaystyle\mathsf{G}_{1}$
$\displaystyle\colon\mathsf{W}_{\ell}\leq-\gamma\ell-c$
$\displaystyle\mathsf{G}_{2}$ $\displaystyle\colon\max_{m\geq
0}\left(\mathsf{W}_{\ell+m}-\mathsf{W}_{\ell}+\gamma m\right)<c$

It is clear that
$\mathsf{G}_{1}\cap\mathsf{G}_{2}\implies\mathsf{E}_{\mathsf{A}}$, and that
$\mathsf{G}_{1}$ and $\mathsf{G}_{2}$ are independent events, since Poisson
arrivals over disjoint intervals are independent. Therefore, it suffices to
find constants $p_{11},p_{12}>0$ such that
$\mathbb{P}\left(\mathsf{G}_{1}\right)\geq p_{11}$ and
$\mathbb{P}\left(\mathsf{G}_{2}\right)\geq p_{12}$.

$\displaystyle\mathbb{P}\left(\mathsf{G}_{1}\right)$
$\displaystyle=\mathbb{P}\left(\sum_{i=1}^{\ell}\mathsf{X}_{i}\leq-\gamma\ell-c\right)$
(11)
$\displaystyle=\mathbb{P}\left(\sum_{i=1}^{\ell}\left(\mathsf{Geom}_{i}\left(1-\beta\right)-1-\eta\cdot\mathsf{Be}_{i}\left(1-d\right)\right)\leq-\gamma\ell-c\right)$
(12)
$\displaystyle=\mathbb{P}\left(\sum_{i=1}^{\ell}\left(\mathsf{Geom}_{i}\left(1-\beta\right)-\eta\cdot\mathsf{Be}_{i}\left(1-d\right)\right)\leq\left(1-\gamma\right)\ell-c\right)$
(13)
$\displaystyle\geq\mathbb{P}\left(\bigcap_{i=1}^{\ell}\left[\left\\{\mathsf{Geom}_{i}\left(1-\beta\right)=1\right\\}\cap\left\\{\mathsf{Be}_{i}\left(1-d\right)=1\right\\}\right]\right)$
(14) $\displaystyle=p_{11}>0,$ (15)

for fixed $\ell$, since $\gamma<\eta$ and since $c$ is chosen to be
sufficiently small. Here, the inequality in (14) holds because one way to
satisfy the inequality in the event in (13) is when both LHS and RHS of the
inequality equal $\left(1-\eta\right)\ell$.

It remains to show $p_{12}>0$. Consider the random process
$(\mathsf{Z}_{i}\colon i\geq 1)$, where
$\mathsf{Z}_{i}=\mathsf{X}_{i}+\gamma$. Then,
$\left(\sum_{i=1}^{m}\mathsf{Z}_{i}\colon m\geq 1\right)$ and
$\left(\mathsf{W}_{\ell+m}-\mathsf{W}_{\ell}+\gamma m\colon m\geq 1\right)$
follow the same distribution. The Kingman bound [Kin64] yields,

$\displaystyle\mathbb{P}\left(\mathsf{G}_{2}\right)=\mathbb{P}\left(\max_{m\geq
0}\sum_{i=1}^{m}\mathsf{Z}_{i}<c\right)\geq 1-e^{-\theta^{*}c}=:p_{12},$

where

$\displaystyle\theta^{*}=\sup\left\\{\theta>0\colon\mathbb{E}\left[e^{\theta\mathsf{Z}_{1}}\leq
1\right]\right\\}.$

Since $c>0$, we see that $p_{12}>0$ if $\theta^{*}>0$. We show that
$\theta^{*}>0$ if $\frac{\beta}{1-\beta}<\eta\left(1-d\right)$. A simple
computation yields

$\displaystyle\mathbb{E}\left[\mathsf{Z}_{1}\right]$
$\displaystyle=\frac{\beta}{1-\beta}-\eta\cdot\left(1-d\right)+\gamma,$

If $\frac{\beta}{1-\beta}<\eta\left(1-d\right)$, then there exists
$0<\gamma<\eta$ such that $\mathbb{E}\left[\mathsf{Z}_{1}\right]<0$. Since
$\mathbb{E}\left[e^{\theta\mathsf{Z}_{1}}\right]_{\theta=0}=1$, and
$\frac{d}{d\theta}\mathbb{E}\left[e^{\theta\mathsf{Z}_{1}}\right]_{\theta=0}=\mathbb{E}\left[\mathsf{Z}_{1}\right]<0$,
we know that there exists $\theta_{1}>0$ such that
$\mathbb{E}\left[e^{\theta\mathsf{Z}_{1}}\right]_{\theta=\theta_{1}}<1$, which
then implies $\theta^{*}>\theta_{1}>0$.

The above argument is summarized as

$\displaystyle\mathbb{P}\left(\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\geq\mathbb{P}\left(\mathsf{E}_{\mathsf{A}}\right)\mathbb{P}\left(\mathsf{E}_{\mathsf{B}}\right)\geq\mathbb{P}\left(\mathsf{G}_{1}\right)\cdot\mathbb{P}\left(\mathsf{G}_{2}\right)\cdot\mathbb{P}\left(\mathsf{E}_{\mathsf{B}}\right)\geq
p_{11}\cdot p_{12}\cdot p_{2}=:p>0.$ (16)

Showing
$\mathbb{P}\left(\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)\geq
p>0$: For any $i,k\geq 0$ such that $j-i=k-j$, it follows from Remarks 4.4,
4.7, 4.9 and 4.12 that
$\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)=\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)$.
By symmetry, we have

$\displaystyle\mathbb{P}\left(\overleftarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)$
$\displaystyle=\mathbb{P}\left(\bigcap_{i=0}^{j}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)$
$\displaystyle=\mathbb{P}\left(\bigcap_{k=j+1}^{2j+1}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)$
$\displaystyle\geq\mathbb{P}\left(\bigcap_{k:k>j}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)$
$\displaystyle=\mathbb{P}\left(\overrightarrow{\mathsf{E}}_{j}^{\left(\eta\right)}\right)$
$\displaystyle\geq p,$

where the constant $p>0$ is the same as in (16). This concludes the proof. ∎

###  B.3 Proof of Lemma 5.5

######  Lemma 5.5.

Let $0<\eta\leq 1$ and $i<j<k$. Let
$\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$ and
$\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$ be the catch-up events
defined in (1), (2). If $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$,
there exists a constant $c>0$ such that

$\displaystyle\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)$
$\displaystyle\leq e^{-c\left(k-j\right)}$
$\displaystyle\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)$
$\displaystyle\leq e^{-c\left(j-i\right)}$

###### Proof.

First, we show the existence of $c>0$ such that
$\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)\leq
e^{-c\left(k-j\right)}$. Recall that the event
$\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$ is defined as

$\displaystyle\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\colon\ \
a(b_{j},b_{k})\geq\eta\cdot\mathsf{FS}_{j}\left(b_{k-1}\right)-\mathsf{FU}_{j}\left(b_{k}\right).$

From Remarks 4.4, 4.7, 4.9 and 4.12, these random variables are characterized
as:

$\displaystyle a(b_{j},b_{k})$
$\displaystyle=\sum_{i=1}^{k-j}\left(\mathsf{Geom}_{i}\left(1-\beta\right)-1\right),$
$\displaystyle\mathsf{FS}_{j}\left(b_{k-1}\right)$
$\displaystyle=1+\sum_{i=1}^{k-j-1}\mathsf{Be}_{i}\left(1-d\right),$
$\displaystyle\mathsf{FU}_{j}\left(b_{k}\right)$
$\displaystyle=\mathsf{Geom}\left(1-d\right)-1.$

Further, the three random variables
$a(b_{j},b_{k}),\mathsf{FS}_{j}\left(b_{k-1}\right),\mathsf{FU}_{j}\left(b_{k}\right)$
are mutually independent. Consider the following desirable events associated
with them.

$\displaystyle\mathsf{G}_{1}$ $\displaystyle\colon
a(b_{j},b_{k})<\frac{\beta}{1-\beta}\left(k-j\right)\left(1+\varepsilon\right)$
$\displaystyle\mathsf{G}_{2}$
$\displaystyle\colon\mathsf{FS}_{j}\left(b_{k-1}\right)>\left(1-d\right)\left(k-j\right)\left(1-\delta\right)$
$\displaystyle\mathsf{G}_{3}$
$\displaystyle\colon\mathsf{FU}_{j}\left(b_{k}\right)\leq\left(k-j\right)\left[\left(1-\delta\right)\eta\cdot\left(1-d\right)-\frac{\beta}{1-\beta}\left(1+\varepsilon\right)\right]$

Clearly,
$\mathsf{G}_{1}\cap\mathsf{G}_{2}\cap\mathsf{G}_{3}\implies\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}$.
Therefore, we have

$\displaystyle\mathbb{P}\left(\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\geq\mathbb{P}\left(\mathsf{G}_{1}\cap\mathsf{G}_{2}\cap\mathsf{G}_{3}\right)=\mathbb{P}\left(\mathsf{G}_{1}\right)\mathbb{P}\left(\mathsf{G}_{2}\right)\mathbb{P}\left(\mathsf{G}_{3}\right).$
(17)

It suffices to find bounds for each term separately in the RHS of (17).

##### Bounding $\mathsf{G}_{1}$:

Since
$\mathbb{E}\left[a(b_{j},b_{k})\right]=\frac{\beta}{1-\beta}\left(k-j\right)$,
it follows from the Chernoff bound that

$\displaystyle\begin{aligned}
\mathbb{P}\left(\mathsf{G}_{1}^{\mathsf{c}}\right)&=\mathbb{P}\left(a(b_{j},b_{k})\geq\frac{\beta}{1-\beta}\left(k-j\right)\left(1+\varepsilon\right)\right)\leq
e^{-c_{1}\left(k-j\right)},\\\ \text{where
}c_{1}&=\frac{\beta}{1-\beta}\left(1+\varepsilon\right)\log\left(1+\varepsilon\right)+\frac{1}{1-\beta}\left(1+\beta\varepsilon\right)\log\left(1+\beta\varepsilon\right)>0\end{aligned}$

##### Bounding $\mathsf{G}_{2}$:

It follows from the Hoeffding bound that

$\displaystyle\mathbb{P}\left(\mathsf{G}_{2}^{\mathsf{c}}\right)$
$\displaystyle=\mathbb{P}\left(1+\sum_{i=1}^{k-j-1}\mathsf{Be}_{i}\left(1-d\right)\leq\left(1-d\right)\left(k-j\right)\left(1-\delta\right)\right)$
$\displaystyle\leq\mathbb{P}\left(\sum_{i=1}^{k-j}\mathsf{Be}_{i}\left(1-d\right)\leq\left(1-d\right)\left(k-j\right)\left(1-\delta\right)\right)$
$\displaystyle\leq e^{-c_{2}\left(k-j\right)},$

where $c_{2}=\frac{\delta^{2}\left(1-d\right)}{2}>0$.

##### Bounding $\mathsf{G}_{3}$:

Consider the quantity
$c_{4}=\left[\left(1-\delta\right)\eta\cdot\left(1-d\right)-\frac{\beta}{1-\beta}\left(1+\varepsilon\right)\right]$.
If $\frac{\beta}{1-\beta}<\eta\left(1-d\right)$, then there exist $\
\varepsilon,\delta>0$ such that $c_{4}>0$. Since
$1+\mathsf{FU}_{j}\left(b_{k}\right)$ follows a geometric distribution, we
have

$\displaystyle\mathbb{P}\left(\mathsf{G}_{3}^{\mathsf{c}}\right)$
$\displaystyle=\mathbb{P}\left(\mathsf{Geom}\left(1-d\right)-1>c_{4}\left(k-j\right)\right)$
$\displaystyle=\mathbb{P}\left(\mathsf{Geom}\left(1-d\right)>1+c_{4}\left(k-j\right)\right)$
$\displaystyle=1-d^{c_{4}\left(k-j\right)}$ $\displaystyle\geq
1-e^{c_{3}\left(k-j\right)},$

for some $c_{3}>0$.

Combining these facts together, we revisit (17). We have

$\displaystyle\mathbb{P}\left(\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)$
$\displaystyle\geq\mathbb{P}\left(\mathsf{G}_{1}\right)\mathbb{P}\left(\mathsf{G}_{2}\right)\mathbb{P}\left(\mathsf{G}_{3}\right)$
(18)
$\displaystyle=\left(1-\mathbb{P}\left(\mathsf{G}_{1}^{\mathsf{c}}\right)\right)\left(1-\mathbb{P}\left(\mathsf{G}_{2}^{\mathsf{c}}\right)\right)\left(1-\mathbb{P}\left(\mathsf{G}_{3}^{\mathsf{c}}\right)\right)$
(19)
$\displaystyle\geq\left(1-e^{-c_{1}(k-j)}\right)\left(1-e^{-c_{2}(k-j)}\right)\left(1-e^{-c_{3}(k-j)}\right)$
(20) $\displaystyle\geq\left(1-e^{-c_{0}(k-j)}\right)^{3}$ (21)
$\displaystyle\geq 1-e^{-c\left(k-j\right)},$ (22)

where $c_{0}=\max\left\\{c_{1},c_{2},c_{3}\right\\}>0$, and subsequently
$c>0$. We conclude the existence of $c>0$ for which
$\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)\leq
e^{-c\left(k-j\right)}$.

It remains to show that
$\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)\leq
e^{-c\left(j-i\right)}$. The proof is very similar, so the details are
omitted. Recall that

$\displaystyle\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\colon\ \
a(b_{i},b_{j})\geq\eta\cdot\mathsf{BS}_{j}\left(b_{i+1}\right)-\mathsf{BU}_{j}\left(b_{i}\right),$

where the random variables involved may be written as

$\displaystyle a(b_{i},b_{j})$
$\displaystyle=\sum_{k=1}^{j-i}\left(\mathsf{Geom}_{k}\left(1-\beta\right)-1\right),$
$\displaystyle\mathsf{BS}_{j}\left(b_{i+1}\right)$
$\displaystyle=1+\sum_{k=1}^{j-i-1}\mathsf{Be}_{k}\left(1-d\right),$
$\displaystyle\mathsf{BU}_{j}\left(b_{i}\right)$
$\displaystyle=\mathsf{Geom}\left(1-d\right)-1,$

Thus, if $k-j$ = $j-i$, we see that

  * •

$a(b_{i},b_{j})$ and $a(b_{j},b_{k})$ follow the same distribution.

  * •

$\mathsf{BS}_{j}\left(b_{i+1}\right)$ and
$\mathsf{FS}_{j}\left(b_{k-1}\right)$ follow the same distribution.

  * •

$\mathsf{BU}_{j}\left(b_{i}\right)$ and $\mathsf{FU}_{j}\left(b_{k}\right)$
follow the same distribution.

Therefore, the same concentration inequalities apply, and we conclude that for
the same constant $c$ in (22), we have
$\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)\leq
e^{-c\left(j-i\right)}$. ∎

###  B.4 Proof of Theorem 5.6

######  Theorem 5.6.

Let $0<\eta\leq 1$. Let $\beta$ be the fraction of computational power in the
system that is adversarial and $d$ be the probability of message loss. Let
$B_{s,s+t}^{\left(\eta\right)}$ be the event that there are no $\eta$-Nakamoto
blocks in $[s,s+t]$. If $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$,
then there exists a constant $c_{0}>0$ such that for any $s,t\geq 0$,

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq
e^{-c_{0}\sqrt{t}}$

###### Proof.

For any $i\geq 0$, let $\tau_{i}$ denote the mining time of block $b_{i}$.
Partition the interval $[s,s+t]$ into $\sqrt{t}$ intervals of length
$\sqrt{t}$ each. Group these sub-intervals into threes, so that there are
$\sqrt{t}/3$ groups of sub-intervals, namely $I_{1}$, $I_{2}$, $\cdots$,
$I_{\sqrt{t}/3}$. Thus,
$I_{\ell}=\left[s+3\left(\ell-1\right)\sqrt{t},s+3\ell\sqrt{t}\right]$.
Further, let $S_{\ell}$ represent the middle sub-interval of $I_{\ell}$, so
that
$S_{\ell}=[s+\left(3\ell-2\right)\sqrt{t},s+\left(3\ell-1\right)\sqrt{t}]$, as
shown in Figure 6.

Figure 6: Partitioning $[s,s+t]$ into sub-intervals

Consider the following desirable events.

$\displaystyle\mathsf{G}_{1}\colon\bigcap_{j\colon\tau_{j}\in[s+\sqrt{t},s+t-\sqrt{t}]}\left[\left(\bigcap_{\begin{subarray}{c}i<j\\\
\tau_{i}<\tau_{j}-\sqrt{t}\end{subarray}}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\bigcap\left(\bigcap_{\begin{subarray}{c}k>j\\\
\tau_{k}>\tau_{j}+\sqrt{t}\end{subarray}}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\right]$
$\displaystyle\mathsf{G}_{2}\colon\bigcup_{\ell=1}^{\sqrt{t}/3}\mathsf{H}_{\ell},\text{
where }\mathsf{H}_{\ell}\colon\bigcup_{j\colon\tau_{j}\in
S_{\ell}}\left[\left(\bigcap_{\begin{subarray}{c}i<j\\\
\tau_{i}\geq\tau_{j}-\sqrt{t}\end{subarray}}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\bigcap\left(\bigcap_{\begin{subarray}{c}k>j\\\
\tau_{k}\leq\tau_{j}+\sqrt{t}\end{subarray}}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\right]$

First, observe that
$\mathsf{G}_{1}\cap\mathsf{G}_{2}\implies\left[B_{s,s+t}^{\left(\eta\right)}\right]^{\mathsf{c}}$.
This is because $\mathsf{G}_{1}$ ensures that no catch-up events (neither
$\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}$, nor
$\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}$) occur when $b_{i}$
and $b_{k}$ are separated in time by more than $\sqrt{t}$ from $b_{j}$, for
any $b_{j}$ mined in $[s+\sqrt{t},s+t-\sqrt{t}]$. This means that the
existence of a block $b_{j}$ in this interval for which no catch-up event
occurs whenever $i$ and $k$ are within $\sqrt{t}$ of $\tau_{j}$ is sufficient
to ensure that $b_{j}$ is a Nakamoto block. This is exactly the event
$\mathsf{G}_{2}$. Since
$\cup_{\ell}S_{\ell}\subset\left[s+\sqrt{t},s+t-\sqrt{t}\right]$, it follows
that
$\mathsf{G}_{1}\cap\mathsf{G}_{2}\implies\left[B_{s,s+t}^{\left(\eta\right)}\right]^{\mathsf{c}}$.
Thus,

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right).$

Next, we bound the probability of each term in the RHS separately.

##### Bounding $\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)$:

Fix $\delta>0$. Consider the following events:

$\displaystyle\mathsf{D}_{1}$
$\displaystyle\colon\left\\{\\#\left\\{i\colon\tau_{i}\in[s,s+t]\right\\}>2\lambda_{h}t\right\\},$
$\displaystyle\mathsf{D}_{2}$ $\displaystyle\colon\left\\{\exists\
\tau_{i},\tau_{k}\in[s,s+t]\colon\left(k-i\right)<\left(1-\delta\right)\lambda_{h}\sqrt{t},\tau_{k}-\tau_{i}>\sqrt{t}\right\\}.$

By the tail bound for Poisson random variables, we know that
$\mathbb{P}\left(\mathsf{D}_{1}\right)\leq e^{-c_{0}t}$ for some $c_{0}>0$. We
now show that $\mathbb{P}\left(\mathsf{D}_{2}\right)\leq e^{-c_{1}\sqrt{t}}$
for some $c_{1}>0$. Let $T_{i,k}:=\tau_{k}-\tau_{i}$ be the random variable
denoting the time between the $i$-th and $k$-th mining. Let
$M(t)=\left(1-\delta\right)\lambda_{h}\sqrt{t}$. Notice that

$\displaystyle\bigcap_{i\in\left[s,s+t\right]}\left\\{T_{i,i+M(t)}<\sqrt{t}\right\\}\implies\mathsf{D}_{2}^{\mathsf{c}}.$

For any honest arrival time $\tau_{i}$, we have

$\displaystyle\mathbb{E}\left[T_{i,i+M(t)}\right]=\mathbb{E}\left[\sum_{j=i}^{i+M(t)}\left(\tau_{j}-\tau_{j-1}\right)\right]=\frac{M(t)}{\lambda_{h}}=\left(1-\delta\right)\sqrt{t}.$

Applying the Chernoff bound, we see that there exists $c>0$ such that

$\displaystyle\mathbb{P}\left(T_{i,i+M(t)}>\sqrt{t}\right)\leq\mathbb{P}\left(T_{i,i+M(t)}>\left(1-\delta\right)\sqrt{t}+\delta\sqrt{t}\right)\leq
e^{-c\sqrt{t}}.$

Thus, we get

$\displaystyle\mathbb{P}\left(\mathsf{D}_{2}\right)$
$\displaystyle=\mathbb{P}\left(\bigcup_{i\colon\tau_{i}\in[s,s+t]}\left\\{T_{i,i+M(t)}>\sqrt{t}\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\left(\bigcup_{i\colon\tau_{i}\in[s,s+t]}\left\\{T_{i,i+M(t)}>\sqrt{t}\right\\}\right)\cap\mathsf{D}^{\mathsf{c}}_{1}\right)+\mathbb{P}\left(\mathsf{D}_{1}\right)$
$\displaystyle\leq\left(\sum_{i=1}^{2\lambda_{h}t}\mathbb{P}\left(T_{i,i+M(t)}>\sqrt{t}\right)\right)+e^{-c_{0}t}$
$\displaystyle\leq e^{-c_{1}\sqrt{t}},$

for some $c_{1}>0$. Thus, $\mathbb{P}\left(\mathsf{D}_{2}\right)\leq
e^{-c_{1}\sqrt{t}}$. We may therefore bound
$\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)$ as

$\displaystyle\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{D}_{1}\cup\mathsf{D}_{2}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{2}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{D}_{1}\right)+\mathbb{P}\left(\mathsf{D}_{2}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{2}\right)$
$\displaystyle\leq
e^{-c_{0}t}+e^{-c_{1}\sqrt{t}}+\sum_{j=1}^{2\lambda_{h}t}\left[\left(\sum_{i=0}^{j-M(t)}\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)\right)+\left(\sum_{k=j+M(t)}^{\infty}\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)\right)\right]$
$\displaystyle\leq
e^{-c_{0}t}+e^{-c_{1}\sqrt{t}}+\sum_{j=1}^{2\lambda_{h}t}\left[\left(\sum_{i=0}^{j-M(t)}e^{-c\left(j-i\right)}\right)+\left(\sum_{k=j+M(t)}^{\infty}e^{-c\left(k-j\right)}\right)\right]$
$\displaystyle\leq
e^{-c_{0}t}+e^{-c_{1}\sqrt{t}}+\sum_{j=1}^{2\lambda_{h}t}\left(2\sum_{m=M(t)}^{\infty}e^{-cm}\right)$
$\displaystyle=e^{-c_{0}t}+e^{-c_{1}\sqrt{t}}+\frac{4\lambda_{h}t}{1-e^{-c}}e^{-cM(t)}$
$\displaystyle=e^{-c_{0}t}+e^{-c_{1}\sqrt{t}}+\frac{4\lambda_{h}t}{1-e^{-c}}e^{-c\left(1-\delta\right)\lambda_{h}\sqrt{t}}$
$\displaystyle\leq e^{-c_{3}\sqrt{t}},$

for some $c_{3}>0$.

##### Bounding $\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right)$:

We have
$\mathsf{G}^{\mathsf{c}}_{2}=\bigcap_{\ell=1}^{\sqrt{t}/3}\mathsf{H}^{\mathsf{c}}_{\ell}$.
Notice that $\mathsf{H}^{\mathsf{c}}_{\ell}$ are mutually independent for
distinct $\ell$ by Lemma 5.3. Recall that

$\displaystyle\mathsf{H}_{\ell}=\bigcup_{j\colon\tau_{j}\in
S_{\ell}}\mathsf{R}_{j}^{\ell},\text{ where
}\mathsf{R}_{j}^{\ell}\colon\left(\bigcap_{\begin{subarray}{c}i<j\\\
\tau_{i}\geq\tau_{j}-\sqrt{t}\end{subarray}}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\bigcap\left(\bigcap_{\begin{subarray}{c}k>j\\\
\tau_{k}\leq\tau_{j}+\sqrt{t}\end{subarray}}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right).$

Let $M_{\ell}$ be the number of honest blocks mined in $S_{\ell}$, and
$N_{\ell}$ be the number of $\eta$-Nakamoto blocks mined in $S_{\ell}$. Since
$\mathsf{H}_{\ell}$ is contained in the event $M_{\ell}\geq 1$, we have for
each $\ell\in\left\\{1,2,\cdots,\sqrt{t}/3\right\\}$:

$\displaystyle\mathbb{P}\left(\mathsf{H}_{\ell}\right)$
$\displaystyle=\mathbb{P}\left(\bigcup_{j\colon\tau_{j}\in
S_{\ell}}\mathsf{R}_{j}^{\ell}\right)$
$\displaystyle=\mathbb{P}\left(\left(\bigcup_{j\colon\tau_{j}\in
S_{\ell}}\mathsf{R}_{j}^{\ell}\right)\bigcap\left\\{M_{\ell}\geq
1\right\\}\right)$ $\displaystyle\geq\mathbb{P}\left(\bigcup_{j:\tau_{j}\in
S_{\ell}}\mathsf{N}_{j}^{\left(\eta\right)}\right)$
$\displaystyle\geq\frac{p_{0}^{2}}{2},$ (23)

where $p_{0}$ is the lower bound on the probability that $b_{j}$ is an
$\eta$-Nakamoto block, obtained in Theorem 5.4. The inequality in (23)
deserves some elaboration: Since $M_{\ell}$ is a non-negative integer valued
random variable, we have from the second moment method that

$\displaystyle\mathbb{P}\left(N_{\ell}\geq
1\right)=\mathbb{P}\left(N_{\ell}>0\right)\geq\frac{\left(\mathbb{E}\left[N_{\ell}\right]\right)^{2}}{\mathbb{E}\left[N_{\ell}^{2}\right]}\geq\frac{\left(p_{0}\lambda_{h}\sqrt{t}\right)^{2}t}{\lambda_{h}\sqrt{t}+\left(\lambda_{h}\sqrt{t}\right)^{2}}\geq\frac{\lambda_{h}^{2}p_{0}^{2}t}{2\lambda_{h}^{2}t}\geq\frac{p_{0}^{2}}{2},$

for sufficiently large $t$. Here, we used the fact that
$\mathbb{E}\left[N_{\ell}\right]=p_{0}\lambda_{h}\sqrt{t}$, and
$\mathbb{E}\left[N_{\ell}^{2}\right]\leq\mathbb{E}\left[M_{\ell}^{2}\right]=\lambda_{h}\sqrt{t}+\left(\lambda_{h}\sqrt{t}\right)^{2}$.

Thus, $\mathbb{P}\left(\mathsf{H}^{\mathsf{c}}_{\ell}\right)\leq
1-\frac{p_{0}^{2}}{2}<1$, which yields

$\displaystyle\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right)=\mathbb{P}\left(\bigcap_{\ell=1}^{\sqrt{t}/3}\mathsf{H}^{\mathsf{c}}_{\ell}\right)=\prod_{\ell=1}^{\sqrt{t}/3}\mathbb{P}\left(\mathsf{H}^{\mathsf{c}}_{\ell}\right)\leq\left(1-\frac{p_{0}^{2}}{2}\right)^{\sqrt{t}/3}\leq
e^{-c_{4}\sqrt{t}},$

for some $c_{4}>0$, since the $\mathsf{H}_{\ell}$’s are mutually independent
events. Therefore, we conclude that

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right)\leq
e^{-c_{3}\sqrt{t}}+e^{-c_{4}\sqrt{t}}\leq e^{-c_{0}\sqrt{t}},$

for some $c_{0}>0$, as desired. ∎

###  B.5 Proof of Theorem 5.7

######  Theorem 5.7.

Let $0<\eta\leq 1$. Let $\beta$ be the fraction of computational power in the
system that is adversarial and $d$ be the probability of message loss. Let
$B_{s,s+t}^{\left(\eta\right)}$ be the event that there are no $\eta$-Nakamoto
blocks in $\left[s,s+t\right]$. If
$\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$, then for every
$\varepsilon>0$, there exist positive constants $A$, $a$ such that for any
$s,t>0$,

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq
A\exp\left(-at^{1-\varepsilon}\right).$

###### Proof.

Fix $m>1$. Consider the following statement for $m$:

$\displaystyle\mathbb{S}[m]\ \colon\forall\ \theta\geq m,\ \exists\
a_{\theta}>0,A_{\theta}>0\text{ such that
}\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq
A_{\theta}\exp\left(-a_{\theta}t^{1/\theta}\right)$

In Theorem 5.6, we proved that $\mathbb{S}[2]$ is true. Next, we show the
following:

$\displaystyle\mathbb{S}[m]\implies\mathbb{S}\left[\frac{2m-1}{m}\right].$

Assume $\mathbb{S}[m]$ is true. For any $i\geq 0$, let $\tau_{i}$ denote the
mining time of block $b_{i}$. Partition the interval $[s,s+t]$ into
$t^{\frac{m-1}{2m-1}}$ intervals of length $t^{\frac{m}{2m-1}}$ each. Group
these sub-intervals into threes, so that there are
$\frac{t^{\frac{m-1}{2m-1}}}{3}$ groups of sub-intervals, namely
$I_{1},I_{2},\cdots,I_{t^{\frac{m-1}{2m-1}}/3}$. Thus,

$\displaystyle I_{\ell}$
$\displaystyle\colon=\left[s+3\left(\ell-1\right)t^{\frac{m}{2m-1}},s+3\ell
t^{\frac{m}{2m-1}}\right],$ $\displaystyle S_{\ell}$
$\displaystyle\colon=\left[s+\left(3\ell-2\right)t^{\frac{m}{2m-1}},s+\left(3\ell-1\right)t^{\frac{m}{2m-1}}\right].$

Consider the following desirable events.

$\displaystyle\mathsf{G}_{1}\colon\bigcap_{j\colon\tau_{j}\in\left[s+t^{\frac{m}{2m-1}},s+t-t^{\frac{m}{2m-1}}\right]}\left[\left(\bigcap_{\begin{subarray}{c}i<j\\\
\tau_{i}<\tau_{j}-t^{\frac{m}{2m-1}}\end{subarray}}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\bigcap\left(\bigcap_{\begin{subarray}{c}k>j\\\
\tau_{k}>\tau_{j}+t^{\frac{m}{2m-1}}\end{subarray}}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\right]$
$\displaystyle\mathsf{G}_{2}\colon\bigcup_{\ell=1}^{t^{\frac{m-1}{2m-1}}/3}\mathsf{H}_{\ell},\text{
where }\mathsf{H}_{\ell}\colon\bigcup_{j\colon\tau_{j}\in
S_{\ell}}\left[\left(\bigcap_{\begin{subarray}{c}i<j\\\
\tau_{i}\geq\tau_{j}-t^{\frac{m}{2m-1}}\end{subarray}}\left[\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\bigcap\left(\bigcap_{\begin{subarray}{c}k>j\\\
\tau_{k}\leq\tau_{j}+t^{\frac{m}{2m-1}}\end{subarray}}\left[\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right]^{\mathsf{c}}\right)\right]$

Observe that
$\mathsf{G}_{1}\cap\mathsf{G}_{2}\implies\left[B_{s,s+t}^{\left(\eta\right)}\right]^{\mathsf{c}}$.

##### Bounding $\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)$:

We show that $\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)\leq
e^{-c_{3}t^{\frac{m}{2m-1}}}$ for some $c_{3}>0$. This is done following the
steps in Theorem 5.6. Fix $\delta>0$ and consider the following events:

$\displaystyle\mathsf{D}_{1}$
$\displaystyle\colon\left\\{\\#\left\\{i\colon\tau_{i}\in[s,s+t]\right\\}>2\lambda_{h}t\right\\},$
$\displaystyle\mathsf{D}_{2}$ $\displaystyle\colon\left\\{\exists\
\tau_{i},\tau_{k}\in[s,s+t]\colon\left(k-i\right)<\left(1-\delta\right)\lambda_{h}t^{\frac{m}{2m-1}},\tau_{k}-\tau_{i}>t^{\frac{m}{2m-1}}\right\\}.$

By the tail bound for Poisson random variables, we know that
$\mathbb{P}\left(\mathsf{D}_{1}\right)\leq e^{-c_{0}t}$ for some $c_{0}>0$. We
now show that $\mathbb{P}\left(\mathsf{D}_{2}\right)\leq
e^{-c_{1}t^{\frac{m}{2m-1}}}$ for some $c_{1}>0$. Let
$T_{i,k}:=\tau_{k}-\tau_{i}$ be the random variable denoting the time between
the $i$-th and $k$-th mining. Let
$M(t)=\left(1-\delta\right)\lambda_{h}t^{\frac{m}{2m-1}}$. Notice that

$\displaystyle\bigcap_{i\in\left[s,s+t\right]}\left\\{T_{i,i+M(t)}<\sqrt{t}\right\\}\implies\mathsf{D}_{2}^{\mathsf{c}}.$

For any honest arrival time $\tau_{i}$, we have

$\displaystyle\mathbb{E}\left[T_{i,i+M(t)}\right]=\mathbb{E}\left[\sum_{j=i}^{i+M(t)}\left(\tau_{j}-\tau_{j-1}\right)\right]=\frac{M(t)}{\lambda_{h}}=\left(1-\delta\right)t^{\frac{m}{2m-1}}.$

Applying the Chernoff bound, we see that there exists $c>0$ such that

$\displaystyle\mathbb{P}\left(\mathsf{T}_{i,i+M(t)}>t^{\frac{m}{2m-1}}\right)$
$\displaystyle\leq\mathbb{P}\left(T_{i,i+M(t)}>\left(1-\delta\right)t^{\frac{m}{2m-1}}+\delta
t^{\frac{m}{2m-1}}\right)\leq e^{-ct^{\frac{m}{2m-1}}}.$

Thus, we get

$\displaystyle\mathbb{P}\left(\mathsf{D}_{2}\right)$
$\displaystyle=\mathbb{P}\left(\bigcup_{i\colon\tau_{i}\in[s,s+t]}\left\\{T_{i,i+M(t)}>t^{\frac{m}{2m-1}}\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\left(\bigcup_{i\colon\tau_{i}\in[s,s+t]}\left\\{T_{i,i+M(t)}>t^{\frac{m}{2m-1}}\right\\}\right)\cap\mathsf{D}^{\mathsf{c}}_{1}\right)+\mathbb{P}\left(\mathsf{D}_{1}\right)$
$\displaystyle\leq\left(\sum_{i=1}^{2\lambda_{h}t}\mathbb{P}\left(T_{i,i+M(t)}>t^{\frac{m}{2m-1}}\right)\right)+e^{-c_{0}t}$
$\displaystyle\leq e^{-c_{1}t^{\frac{m}{2m-1}}},$

for some $c_{1}>0$. Thus, $\mathbb{P}\left(\mathsf{D}_{2}\right)\leq
e^{-c_{1}t^{\frac{m}{2m-1}}}$. We may therefore bound
$\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)$ as

$\displaystyle\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{D}_{1}\cup\mathsf{D}_{2}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{2}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{D}_{1}\right)+\mathbb{P}\left(\mathsf{D}_{2}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{1}\cap\mathsf{D}^{\mathsf{c}}_{2}\right)$
$\displaystyle\leq
e^{-c_{0}t}+e^{-c_{1}t^{\frac{m}{2m-1}}}+\sum_{j=1}^{2\lambda_{h}t}\left[\left(\sum_{i=0}^{j-M(t)}\mathbb{P}\left(\overleftarrow{\mathsf{B}}_{i,j}^{\left(\eta\right)}\right)\right)+\left(\sum_{k=j+M(t)}^{\infty}\mathbb{P}\left(\overrightarrow{\mathsf{B}}_{j,k}^{\left(\eta\right)}\right)\right)\right]$
$\displaystyle\leq
e^{-c_{0}t}+e^{-c_{1}t^{\frac{m}{2m-1}}}+\sum_{j=1}^{2\lambda_{h}t}\left[\left(\sum_{i=0}^{j-M(t)}e^{-c\left(j-i\right)}\right)+\left(\sum_{k=j+M(t)}^{\infty}e^{-c\left(k-j\right)}\right)\right]$
$\displaystyle\leq
e^{-c_{0}t}+e^{-c_{1}t^{\frac{m}{2m-1}}}+\sum_{j=1}^{2\lambda_{h}t}\left(2\sum_{m=M(t)}^{\infty}e^{-cm}\right)$
$\displaystyle=e^{-c_{0}t}+e^{-c_{1}t^{\frac{m}{2m-1}}}+\frac{4\lambda_{h}t}{1-e^{-c}}e^{-cM(t)}$
$\displaystyle=e^{-c_{0}t}+e^{-c_{1}t^{\frac{m}{2m-1}}}+\frac{4\lambda_{h}t}{1-e^{-c}}e^{-c\left(1-\delta\right)\lambda_{h}t^{\frac{m}{2m-1}}}$
$\displaystyle\leq e^{-c_{3}t^{\frac{m}{2m-1}}},$

for some $c_{3}>0$.

##### Bounding $\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right)$:

We have
$\mathsf{G}^{\mathsf{c}}_{2}=\bigcap_{\ell=1}^{t^{\frac{m-1}{2m-1}}/3}\mathsf{H}^{\mathsf{c}}_{\ell}$.
Notice that $\mathsf{H}^{\mathsf{c}}_{\ell}$ are mutually independent for
distinct $\ell$ by Lemma 5.3. Since $\mathbb{S}[m]$ is true, we have

$\displaystyle\mathbb{P}\left(\mathsf{H}_{\ell}^{\mathsf{c}}\right)\leq\mathbb{P}\left(B_{s+\left(3\ell-2\right)t^{\frac{m}{2m-1}},s+\left(3\ell-1\right)t^{\frac{m}{2m-1}}}^{\left(\eta\right)}\right)\leq
A_{m}\exp\left(-a_{m}\left(t^{\frac{m}{2m-1}}\right)^{\frac{1}{m}}\right)\leq
A_{m}\exp\left(-a_{m}t^{1/(2m-1)}\right)$

Therefore, it follows that

$\displaystyle\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right)=\mathbb{P}\left(\bigcap_{\ell=1}^{t^{\frac{m-1}{2m-1}}/3}\mathsf{H}^{\mathsf{c}}_{\ell}\right)=\prod_{\ell=1}^{t^{\frac{m-1}{2m-1}}/3}\mathbb{P}\left(\mathsf{H}^{\mathsf{c}}_{\ell}\right)\leq\left(A_{m}\exp\left(-a_{m}t^{1/(2m-1)}\right)\right)^{t^{\frac{m-1}{2m-1}}/3}\leq
e^{-c_{4}t^{\frac{m}{2m-1}}},$

for some $c_{4}>0$, since the $\mathsf{H}_{\ell}$’s are mutually independent
events. Therefore, we have

$\displaystyle\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{1}\right)+\mathbb{P}\left(\mathsf{G}^{\mathsf{c}}_{2}\right)\leq
e^{-c_{3}t^{\frac{m}{2m-1}}}+e^{-c_{4}t^{\frac{m}{2m-1}}}\leq
A_{m^{\prime}}e^{-a_{m^{\prime}}t^{1/m^{\prime}}},$

where $m^{\prime}=\frac{m}{2m-1}$, and $a_{m^{\prime}},A_{m^{\prime}}>0$. In
turn, this implies that $\mathbb{S}\left[\frac{2m-1}{m}\right]$ is true.

Finally, consider the recursion given by $m_{k+1}=\frac{2m_{k}-1}{m_{k}}$, and
the initial condition $m_{1}=2$. We have proved that $\mathbb{S}[m_{1}]$ is
true and that $\mathbb{S}\left[m_{k+1}\right]$ is true whenever
$\mathbb{S}[m_{k}]$ is true. By induction, it follows that $\mathbb{S}[m_{k}]$
is true for all $k\in\mathbb{N}$. Since $m_{k}=\frac{k+1}{k}$ and
$\lim_{k\to\infty}m_{k}=1$, we conclude that for every $\varepsilon>0$, there
exist positive constants $A$, $a$ such that
$\mathbb{P}\left(B_{s,s+t}^{\left(\eta\right)}\right)\leq
A\exp\left(-at^{1-\varepsilon}\right)$. This concludes the proof. ∎

###  B.6 Proof of Theorem 5.8

######  Theorem 5.8.

Let $0<\eta<1$. Suppose the fraction $\beta$ of computational power in the
system that is adversarial, and the probability $d$ of message loss satisfies
$\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$. Given $s\geq 0$, let
$b_{J}$ be the first $\eta$-Nakamoto block mined after time $s$. There exist
constants $C$, $c>0$ such that for any honest user $h$ and for all
$k^{\prime}\geq 1$,

$\displaystyle\mathbb{P}\left(\left(h,J,\eta,k^{\prime}\right)\mathchar
45\relax\text{user-unheard-criterion fails}\right)\leq Ce^{-ck^{\prime}}$

###### Proof.

By the union bound, we have

$\displaystyle\mathbb{P}\left(\bigcup_{k=k^{\prime}}^{\infty}\left\\{\mathsf{Unheard}_{h}\left(b_{J}^{k}\right)>\left(\frac{1-\eta}{2}\right)k\right\\}\right)$
$\displaystyle\leq\sum_{k=k^{\prime}}^{\infty}\mathbb{P}\left(\mathsf{Unheard}_{h}\left(b_{J}^{k}\right)>\left(\frac{1-\eta}{2}\right)k\right).$
(24)

From remark 4.17, it follows that
$\mathsf{Unheard}_{h}\left(b_{J}^{k}\right)\leq\mathsf{Geom}\left(1-d\right)$.
Thus, for all $k\geq 1$, we have

$\displaystyle\mathbb{P}\left(\mathsf{Unheard}_{h}\left(b_{J}^{k}\right)>\left(\frac{1-\eta}{2}\right)k\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{Geom}\left(1-d\right)>\left(\frac{1-\eta}{2}\right)k\right)$
$\displaystyle\leq C_{0}\cdot e^{-ck},$

for some positive constants $C_{0}$ and $c$. Combining this with (24) yields

$\displaystyle\mathbb{P}\left(\bigcup_{k=k^{\prime}}^{\infty}\left\\{\mathsf{Unheard}_{h}\left(b_{J}^{k}\right)>\left(\frac{1-\eta}{2}\right)k\right\\}\right)\leq\sum_{k=k^{\prime}}^{\infty}C_{0}\cdot
e^{-ck}=C\cdot e^{-ck^{\prime}},$

where $C=\frac{C_{0}}{1-e^{-c}}$ is a positive constant. This concludes the
proof. ∎

###  B.7 Proof of Theorem 3.2

Before we prove our main result, we recall a useful lemma about Poisson random
variables.

######  Lemma B.1.

Let $X$ be a Poisson random variable with mean $\mu$. Then

  1. (i)

$\mathbb{P}\left(X\geq 2\mu\right)\leq e^{-\frac{4}{3}\mu}$.

  2. (ii)

$\mathbb{P}\left(X\leq\frac{1}{2}\mu\right)\leq e^{-\frac{1}{8}\mu}$.

###### Proof.

The proof follows from Theorem 4.5 in [MU17]. ∎

We are now ready to state and prove our main result.

######  Theorem 3.2.

Let $\beta$ be the fraction of computational power in the system that is
adversarial, and $d$ be the probability of message loss. If
$\frac{\beta}{1-\beta}<\left(1-d\right)$, then for every $\varepsilon>0$,
there exist positive constants $a$ and $b$ such that for all $\tau\geq 0$ and
for any honest transaction $\mathsf{tx}$ and any finite set of honest users
$\mathcal{H}$:

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(\tau,\mathcal{H}\right)$-security}\right)\leq\exp\left(-a\tau^{1-\varepsilon}\right)+|\mathcal{H}|\exp\left(-b\tau\right).$

###### Proof.

Let $\eta$ be such that $\frac{\beta}{1-\beta}<\eta\cdot\left(1-d\right)$. Let
$k_{0}=\left\lceil\frac{2\eta}{1-\eta}\right\rceil$, and fix an honest subset
of users $\mathcal{H}$. The idea of the proof is as follows: if an
$\eta$-Nakamoto block $b_{J}$ is mined in the time interval $(s,s+t_{1})$, and
$k_{0}$ number of $J\mathchar 45\relax\mathsf{FS}$ blocks are mined before
time $s+t_{1}+t_{2}$, and if all users $h\in\mathcal{H}$ satisfy the
$\left(h,J,\eta,k_{0}\right)$-user-unheard-criterion, then Theorems 5.1 and
5.2 together imply that the $\eta$-Nakamoto block $b_{J}$ is included in
$\mathcal{C}_{h}(t)$ for all $t\geq s+t_{1}+t_{2}$. Since $\mathsf{tx}$ must
be included in either $b_{J}$ or its ancestors, $\mathsf{tx}$ satisfies
$\left(t_{1}+t_{2},\mathcal{H}\right)$-security.

Let $b_{J}$ be the first $\eta$-Nakamoto block mined after time $s$. Let
$T_{J}=\tau_{J}-s$ denote the time between $s$ and the mining time of the
first $\eta$-Nakamoto block. For the $r$-th honest block $b_{r}$ and any time
$t$, let $N_{r}(t)$ denote the number of $r\mathchar 45\relax\mathsf{FS}$
blocks mined until time $t$. Consider the following events:

$\displaystyle\mathsf{E}_{1}$ $\displaystyle\colon T_{J}>t_{1}$
$\displaystyle\mathsf{E}_{2}^{h}$ $\displaystyle\colon\text{The
}\left(h,J,\eta,k_{0}\right)\text{-user-unheard-criterion is violated}$
$\displaystyle\mathsf{E}_{3}$
$\displaystyle\colon\bigcup_{r:\tau_{r}\in[s,s+t_{1}]}\left\\{N_{r}\left(s+t_{1}+t_{2}\right)<k_{0}\right\\}.$

By the first paragraph of the proof, the union bound gives

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(t_{1}+t_{2},\mathcal{H}\right)$-security}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{E}_{1}\right)+\sum_{h\in\mathcal{H}}\mathbb{P}\left(\mathsf{E}_{2}^{h}\right)+\mathbb{P}\left(\mathsf{E}_{3}\right).$
(25)

From Theorem 5.7, we have that for any $\varepsilon>0$, there exist positive
constants $A^{\prime},a^{\prime}$ such that
$\mathbb{P}\left(\mathsf{E}_{1}\right)\leq
A^{\prime}\left(\exp{-a^{\prime}t_{1}^{1-\varepsilon}}\right)$.

From Theorem 5.8, we have that there exist positive constants $C$,
$c^{\prime}$ such that $\mathbb{P}\left(\mathsf{E}_{2}^{h}\right)\leq
C\exp\left(-c^{\prime}k_{0}\right)$ for all $h\in\mathcal{H}$.

It remains to bound $\mathbb{P}\left(\mathsf{E}_{3}\right)$. Let $\lambda_{h}$
denote the aggregate mining rate of the honest users. Let
$t_{2}>\frac{2k_{0}}{\left(1-d\right)\lambda_{h}}$. Let $M$ be the number of
honest miners in $[s,s+t_{1}]$, so that $M$ has the Poisson distribution with
mean $\lambda_{h}\left(1-d\right)t_{1}$. Therefore, we have from Lemma B.1
that

$\displaystyle\mathbb{P}\left(M>2\lambda_{h}t_{1}\right)\leq\exp\left(\frac{-4\lambda_{h}t_{1}}{3}\right).$

For $r\geq 1$, consider the $r$-th honest miner $b_{r}$ after time $s$ and
consider the $r\mathchar 45\relax\mathsf{FS}$ sequence. Let $U_{r}$ denote the
number of $r\mathchar 45\relax\mathsf{FS}$ blocks mined in
$\left[\tau_{r},\tau_{r}+t_{2}\right]$. Then, $U_{r}$ has the Poisson
probability distribution with mean $\lambda_{h}\left(1-d\right)t_{2}$.
Applying Lemma B.1, we get

$\displaystyle\mathbb{P}\left(U_{r}\leq
k_{0}\right)\leq\mathbb{P}\left(U_{r}\leq\frac{1}{2}\lambda_{h}\left(1-d\right)t_{2}\right)\leq\exp\left(\frac{-\lambda_{h}\left(1-d\right)t_{2}}{8}\right).$

Therefore, we have

$\displaystyle\mathbb{P}\left(\mathsf{E}_{3}\right)$
$\displaystyle=\mathbb{P}\left(\mathsf{E}_{3}\cap\left\\{M>2\lambda_{h}t_{1}\right\\}\right)+\mathbb{P}\left(\mathsf{E}_{3}\cap\left\\{M<2\lambda_{h}t_{1}\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(N>2\lambda_{h}t_{1}\right)+\sum_{r=1}^{2\lambda_{h}t_{1}}\mathbb{P}\left(U_{r}\leq
k_{0}\right)$
$\displaystyle\leq\exp\left(\frac{-4\lambda_{h}t_{1}}{3}\right)+2\lambda_{h}t_{1}\cdot\exp\left(\frac{-\lambda_{h}\left(1-d\right)t_{2}}{8}\right).$

Therefore, combining (25) and the bounds on
$\mathbb{P}\left(\mathsf{E}_{1}\right)$,
$\mathbb{P}\left(\mathsf{E}_{2}^{h}\right)$, and
$\mathbb{P}\left(\mathsf{E}_{3}\right)$ yields

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(t_{1}+t_{2},\mathcal{H}\right)$-security}\right)$
$\displaystyle\leq\mathbb{P}\left(\mathsf{E}_{1}\right)+\sum_{h\in\mathcal{H}}\mathbb{P}\left(\mathsf{E}_{2}^{h}\right)+\mathbb{P}\left(\mathsf{E}_{3}\right)$
$\displaystyle\leq
A^{\prime}\exp\left(-a^{\prime}t_{1}^{1-\varepsilon}\right)+\sum_{h\in\mathcal{H}}C\exp\left(-ct_{2}\right)+\exp\left(\frac{-4\lambda_{h}t_{1}}{3}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+2\lambda_{h}t_{1}\exp\left(\frac{-\lambda_{h}\left(1\\!-\\!d\right)t_{2}}{8}\right)$
$\displaystyle\leq
A\exp\left(-at_{1}^{1-\varepsilon}\right)+B\left(|\mathcal{H}|+t_{1}\right)\exp\left(-bt_{2}\right)$

for some positive constants $A$, $a$, $B$, and $b$. The following lemma
therefore completes the proof of Theorem 3.2.

######  Lemma B.2.

Let $\varepsilon>0$. Suppose there exist positive constants $A$, $a$, $B$, $b$
such that for all $t_{1}>0$, $t_{2}>0$ and for any honest transaction
$\mathsf{tx}$ and any finite set of honest users $\mathcal{H}$:

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(t_{1}+t_{2},\mathcal{H}\right)$-security}\right)\leq
A\exp\left(-at_{1}^{1-\varepsilon}\right)+B\left(|\mathcal{H}|+t_{1}\right)\exp\left(-bt_{2}\right).$
(26)

Then there exist positive constants $a^{\prime\prime\prime}$ and
$b^{\prime\prime\prime}$ such that for all $\tau\geq 0$ and for any honest
transaction $\mathsf{tx}$ and any finite set of honest users $\mathcal{H}$:

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(\tau,\mathcal{H}\right)$-security}\right)\leq\exp\left(-a^{\prime\prime\prime}\tau^{1-\varepsilon}\right)+|\mathcal{H}|\exp\left(-b^{\prime\prime\prime}\tau\right).$
(27)

###### Proof.

The lefthand side of (26) is zero if $\mathcal{H}=\emptyset$ so assume without
loss of generality that $|\mathcal{H}|\geq 1.$ Given $\tau\geq 0$, let
$t_{1}=t_{2}=\tau/2.$ Then (26) yields

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(\tau,\mathcal{H}\right)$-security}\right)\leq
A\exp\left(-(a/2^{1-\epsilon})\tau^{1-\varepsilon}\right)+2B\left(|\mathcal{H}|+\tau\right)\exp\left(-(b/2)\tau\right).$
(28)

Let $a^{\prime}$ and $b^{\prime}$ be positive constants such that
$a^{\prime}<a/2^{1-\epsilon}$ and $b^{\prime}<b/2.$ Let $\bar{\tau}$ be so
large that
$A\exp\left(-[(a/2^{1-\epsilon})-a^{\prime}]\tau^{1-\varepsilon}\right)\leq 1$
and $2B\exp\left(-[(b/2)-b^{\prime}]\tau\right)\leq 1$ for all
$\tau\geq\bar{\tau}.$ Then for $\tau\geq\bar{\tau}$

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(\tau,\mathcal{H}\right)$-security}\right)\leq\exp\left(-a^{\prime}\tau^{1-\varepsilon}\right)+\left(|\mathcal{H}|+\tau\right)\exp\left(-b^{\prime}\tau\right)$
(29)

Let $b^{\prime\prime}$ be a positive constant with $b^{\prime\prime}<b.$ Then,
using the assumption $|\mathcal{H}|\geq 1,$

$\displaystyle\left(|\mathcal{H}|+\tau\right)\exp\left(-b^{\prime}\tau\right)$
$\displaystyle=|\mathcal{H}|\exp\left(-b^{\prime\prime}\tau\right)+\tau\exp\left(-b^{\prime}\tau\right)-|\mathcal{H}|(\exp\left(-b^{\prime\prime}\tau\right)-\exp\left(-b^{\prime}\tau\right))$
$\displaystyle\leq|\mathcal{H}|\exp\left(-b^{\prime\prime}\tau\right)+\tau\exp\left(-b^{\prime}\tau\right)-(\exp\left(-b^{\prime\prime}\tau\right)-\exp\left(-b^{\prime}\tau\right))$
$\displaystyle=|\mathcal{H}|\exp\left(-b^{\prime\prime}\tau\right)-(\exp\left(-b^{\prime\prime}\tau\right)-(1+\tau)\exp\left(-b^{\prime}\tau\right))$
$\displaystyle\leq|\mathcal{H}|\exp\left(-b^{\prime\prime}\tau\right)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{for all $\tau$ sufficiently
large}$ (30)

Combining (29) and (30) implies that there exists $\bar{\tau}^{\prime}$ such
that

$\displaystyle\mathbb{P}\left(\mathsf{tx}\text{ violates
$\left(\tau,\mathcal{H}\right)$-security}\right)\leq\exp\left(-a^{\prime}\tau^{1-\varepsilon}\right)+\tau\exp\left(-b^{\prime\prime}\tau\right)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{ for $\tau\geq\bar{\tau}^{\prime}$}$ (31)

Select positive constants $a^{\prime\prime\prime}$ and
$b^{\prime\prime\prime}$ such that $a^{\prime\prime\prime}<a^{\prime}$ and
$b^{\prime\prime\prime}<b^{\prime\prime}$ and

$\displaystyle
1\leq\exp\left(-a^{\prime\prime\prime}\tau^{1-\varepsilon}\right)+\tau\exp\left(-b^{\prime\prime\prime}\tau\right)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{ for $0\leq\tau\leq\bar{\tau}^{\prime}$}$ (32)

Combining (31) and (32) yields (27) for all $\tau\geq 0.$ ∎

This concludes the proof of Theorem 3.2. ∎