We now deploy the machinery we have developed to prove the main lower bound
result of this paper.

######  Theorem 0.1 (Main Theorem).

Let $\ff$ be a field of characteristic $0$. There is no family of
$\alt_{n}\times\alt_{n}$-symmetric circuits $(C_{n})_{n\in\nats}$ over $\ff$
of size $2^{o(n)}$ computing the determinant over $\ff$.

To prove the Theorem 0.1 we need to construct for each $k$, a pair of $n\times
n$ $\\{0,1\\}$-matrices $M_{k}$ and $N_{k}$ with $n=O(k)$,
$\det(M_{k})\neq\det(N_{k})$ and such that Duplicator has a winning strategy
in the $(T(\alt_{n}\times\alt_{n},\id),k)$-bijection game played on the
matrices. Here, we identify an $n\times n$ $\\{0,1\\}$-matrix $M$ with a
function $M:[n]\times[n]\ra\\{0,1\\}$.

We construct the matrix $M_{k}$ as the biadjacency matrix of a bipartite graph
$\Gamma$. The matrix $N_{k}$ is obtained from $M_{k}$ by interchanging a pair
of columns of $M_{k}$. Hence, $N_{k}$ is also a biadjacency matrix of $\Gamma$
and $\det(M_{k})=-\det(N_{k})$ by construction. Thus, as long as
$\det(M_{k})\neq 0$ the two determinants are different.

In Section 0.1 we describe the construction of the graph which gives rise to
the biadjacency matrix $M_{k}$. This graph is obtained by a CFI construction
from a base graph $\Gamma$ satisfying a number of conditions. We show the
existence of graphs $\Gamma$ satisfying these conditions in Section
LABEL:sec:base-graph. Then, in Section LABEL:sec:game we argue that Duplicator
has a winning strategy in the $(T(\alt_{n}\times\alt_{n},\id),k)$-bijection
game played on $M_{k}$ and $N_{k}$. Since $N_{k}$ is obtained from $M_{k}$ by
swapping a single pair of columns, this is equivalent to showing that
Duplicator has a winning strategy in the
$(T(\alt_{n}\times\alt_{n},\alpha),k)$-bijection game played on two copies of
$M_{k}$, where $\alpha$ is a permutation swapping two columns. We bring it all
together in Section LABEL:sec:main-proof for a proof of Theorem 0.1.

##  0.1 Constructing the Graph

In proving the lower bound for symmetric circuits computing the permanent in
[DawarW20], we adapted a construction due to Cai, Fürer and Immerman [CFI92]
of pairs of graphs not distinguished by the $k$-dimensional Weisfeiler-Leman
algorithm. We showed that we could obtain such a pair of bipartite graphs with
different numbers of perfect matchings. Note that saying a pair of graphs are
not distinguished by the $k$-dimensional Weisfeiler-Leman algorithm is the
same as saying that Duplicator has a winning strategy in the $(k+1)$-pebble
bijection game, using arbitrary bijections. In the present construction, we
consider a game played on a pair of isomorphic bipartite graphs but where the
set of permissible bijections does not include any isomorphisms between them.
Equivalently, we play the game on two distinct biadjacency matrices for the
same graph. The graphs we consider are, indeed, exactly the graphs used in
[CFI92] except that we have to ensure they are bipartite.

### CFI graphs and Determinants

Let $\Gamma=(U\cup V,E)$ be a $3$-regular bipartite graph with bipartition
$U,V$. We obtain the graph $\hG$ by replacing each vertex $v$, with neigbours
$x,y,z$ with the ten-vertex gadget depicted in Figure 1. This gadget is
described as follows.

  * •

There is a set denoted $I_{v}$ of four _inner vertices_ : a vertex $v_{S}$ for
each set $S\subseteq\\{x,y,z\\}$ of even size.

  * •

There is a set denoted $O_{v}$ of six _outer vertices_ : two $u_{0},u_{1}$ for
each $u\in\\{x,y,z\\}$.

  * •

There is an edge between $v_{S}$ and $u_{1}$ if $u\in S$ and an edge between
$v_{S}$ and $u_{0}$ if $u\not\in S$.

Corresponding to each edge $e=\\{u,v\\}\in E$ there is a pair of edges that we
denote $e_{0}$ and $e_{1}$ in $\hG$: $e_{0}$ connects the vertex $u_{0}\in
O_{v}$ with $v_{0}\in O_{u}$ and $e_{1}$ connects the vertex $u_{1}\in O_{v}$
with $v_{1}\in O_{u}$

Figure 1: A gadget in $\hG$ corresponding to vertex $v$ with neighbours
$x,y,z$

Note that the graph $\hG$ is bipartite. Indeed, if we let $X:=\bigcup_{v\in
U}I_{v}\cup\bigcup_{v\in V}O_{v}$ and we let $Y:=\bigcup_{v\in
V}I_{v}\cup\bigcup_{v\in U}O_{v}$ then it is easily seen that all edges in
$\hG$ are between $X$ and $Y$. Since $\Gamma$ is a $3$-regular bipartite
graph, it follows that $|U|=|V|$ and therefore $|X|=|Y|$. Writing $m$ for
$|U|$ and $n$ for $|X|=10m$, we obtain a biadjacency $n\times n$ matrix
representing the graph $\hG$ by fixing a pair of bijections $\eta:X\ra[n]$ and
$\eta^{\prime}:Y\ra[n]$. The action of the group $D_{n}$ divides the
collection of all such matrices into two orbits. Letting $M$ and $N$ be
representatives of the two orbits, we have $\det(M)=-\det(N)$. We next aim to
show that $\det(M)\neq 0$, provided that $\Gamma$ has an odd number of perfect
matchings.

Suppose we are given bijections $\eta:X\ra[n]$ and $\eta^{\prime}:Y\ra[n]$
which determine a biadjacency matrix $M$ representation of $\hG$. We can also
identify each perfect matching in $\hG$ with a bijection $\mu:X\ra Y$ such
that $\mu(x)$ is a neighbour of $x$ for all $x\in X$. We write $\mtch(\hG)$
for the collection of all perfect matchings of $\hG$. Then, the determinant of
$M$ is given by:

From now on, we take $\eta$ and $\eta^{\prime}$ to be fixed and write
$\sgn{\mu}$ and talk of the sign of a matching $\mu$ as short hand for
$\sgn{\eta^{\prime}\mu\eta^{-1}}$.

Hence, to show that this determinant is non-zero, we analyze the structure of
the set $\mtch(\hG)$. In what follows, we assume that $\eta$ and
$\eta^{\prime}$ are fixed and note that this imposes a linear order on the
sets $X$ and $Y$. It also induces a linear order on the sets $U$ and $V$, for
instance by saying that $u<v$, for $u,v\in U$ if the least element of
$\eta(I_{u}\cup O_{u})$ is less than the least element of $\eta(I_{v}\cup
O_{v})$. We make use of this order without further elaboration.

### Perfect Matchings

In any perfect matching $\mu$ of $\hG$, all four vertices in $I_{v}$ for any
$v\in U\cup V$ must be matched to vertices in $O_{v}$ as they have no
neighbours outside this set. Thus, exactly two of the vertices of $O_{v}$ are
matched to vertices in other gadgets. These two could be two vertices in a
pair, e.g. $\\{x_{0},x_{1}\\}$ in Figure 1 or they could be from different
pairs, e.g. $\\{x_{0},y_{0}\\}$. It is easily checked, by inspection of the
gadget, that in either case, removing the two vertices of $O_{v}$ from the
gadget results in an 8-vertex graph that admits a perfect matching. Indeed, if
we remove two vertices in a pair, such as $\\{x_{0},x_{1}\\}$ the resulting
graph is a two-regular bipartite graph on eight vertices. The graph resulting
from removing $x_{0}$ and $y_{0}$ from the gadget is depicted in Figure 2 and
all other cases of removing two vertices of $O_{v}$ from different pairs
result in a graph isomorphic to this one. We now classify perfect matchings in
$\mtch(\hG)$ according to which edges _between_ gadgets are included in the
matching.

Say that a matching $\mu\in\mtch(\hG)$ is _uniform_ if for each edge $e\in E$,
at most one of the two edges $e_{0}$ and $e_{1}$ is included in $\mu$. Thus,
$\mu$ is _non-uniform_ if for some $e\in E$ both $e_{0}$ and $e_{1}$ are
included in $\mu$. Our first aim is to show that the non-uniform matching
contribute a net zero to the determinant of $M$. Write $\umtch(\hG)$ to denote
the set of uniform matchings of $\hG$.

######  Lemma 0.2.

$\displaystyle\det(M)$ $\displaystyle=$
$\displaystyle|\\{\mu\mid\mu\in\umtch(\hG)\text{with}\sgn{\mu}=1\\}|$
$\displaystyle-|\\{\mu\mid\mu\in\umtch(\hG)\text{with}\sgn{\mu}=-1\\}|.$

######  Proof 0.3.

For a non-uniform matching $\mu$, let $e\in E$ be an edge for which both
$e_{0}$ and $e_{1}$ are included in $\mu$ and and $v\in U\cup V$ a vertex such
that $e$ is incident on $v$. Then, the four vertices in $I_{v}$ are matched
with the remaining four vertices in $O_{v}$ and there are exactly two ways
this can be done. To see this, consider the gadget in Figure 1 and suppose
that $e=\\{v,x\\}$ so $x_{0}$ and $x_{1}$ are matched outside the gadget. Then
the only two possible matchings of the remaining eight vertices are
$v_{\emptyset}-y_{0};v_{\\{x,y\\}}-z_{0};v_{\\{y,z\\}}-y_{1};v_{\\{x,z\\}}-z_{1}$
and
$v_{\emptyset}-z_{0};v_{\\{x,y\\}}-y_{1};v_{\\{y,z\\}}-z_{1};v_{\\{x,z\\}}-y_{0}$.
Note that the second one is obtained from the first by composing with an _odd_
permutation: namely the $4$-cycle $(y_{0}z_{0}y_{1}z_{1})$. We can then define
an involution on the set of non-uniform matchings as follows: map $\mu$ to the
unique non-uniform matching $\mu^{\prime}$ which differs from $\mu$ only in
the set $O_{v}$ corresponding to the vertex $v\in U$ which is minimal (in the
order on $U$) among all vertices of $U$ incident on some edge $e$ for which
$e_{0},e_{1}$ are in $\mu$. This is easily seen to be an involution by our
previous observation. Moroever, it takes any matching $\mu$ to one of opposite
sign.

We conclude that all non-uniform matchings $\mu$ come in pairs of opposite
sign and therefore cancel out in the expression for the determinant of $M$.

### Uniform Perfect Matchings.

Our next aim is to count uniform perfect matchings in $\hG$ and classify them
by sign. Suppose then that $\mu$ is a perfect matching that includes for each
$e\in E$ at most one of the two edges $e_{0}$ and $e_{1}$. Let
$F_{\mu}\subseteq E$ be the set of those $e\in E$ such that _exactly_ one of
$e_{0}$ and $e_{1}$ is in $\mu$. Furthermore, let
$f_{\mu}:F_{\mu}\ra\\{0,1\\}$ be the function given by $f_{\mu}(e)=i$ if, and
only if, $e_{i}$ is in $\mu$.

Since for each $v\in U\cup V$, exactly two of the vertices of $O_{v}$ are
matched to vertices in other gadgets we can see that $F_{\mu}$ includes
exactly two edges incident on every vertex $v$. In other words, $F_{\mu}$ is a
$2$-factor of $\Gamma$ and therefore has exactly $2m$ edges.

For a $2$-factor $F$ of $\Gamma$ and a function $f:F\ra\\{0,1\\}$, write
$\mu(F,f)$ for the collection of all matchings $\mu$ of $\hG$ with $F_{\mu}=F$
and $f_{\mu}=f$.

######  Lemma 0.4.

There are exactly $2^{2m}$ perfect matchings in $\mu(F,f)$, for any $2$-factor
$F$ of $\Gamma$ and any function $f:F\ra\\{0,1\\}$.

######  Proof 0.5.

Let $v$ be a vertex of $\Gamma$ with neighbours $x,y,z$ and consider the
gadget in Figure 1. Exactly two of the edges incident on $v$ are included in
$F$ and suppose that it is the edges $\\{v,x\\}$ and $\\{v,y\\}$. Further,
suppose $f(\\{v,x\\})=f(\\{v,y\\})=0$. This means that the matching must pair
the vertices $x_{0}$ and $y_{0}$ with vertices outside the gadget and we
verify that the gadget with these two vertices removed admits two distinct
perfect matchings. The gadget with vertices $x_{0}$ and $y_{0}$ removed is
pictured in Figure 2, where for clarity, we have removed the set brackets in
the subscripts of the vertex labels. It is clear that $v_{\emptyset}$ must be
matched with $z_{0}$. This leaves a six-cycle
$v_{\\{x,y\\}}-x_{1}-v_{\\{x,z\\}}-z_{1}-v_{\\{y,z\\}}-y_{1}$ which admits two
matchings. Entirely analogously, if $f(\\{v,x\\})=f(\\{v,y\\})=1$ we can
consider the gadget with the vertices $x_{1}$ and $y_{1}$ removed and it is
easily checked that the resulting graph is isomorphic to the one depicted in
Figure 2, as is also the case when $f(\\{v,x\\})\neq f(\\{v,y\\})$.

Figure 2: The gadget from Figure 1 with $x_{0}$ and $y_{0}$ removed

Since the choice of the matching at each gadget is independent, and there are
$2m$ gadgets, one for each vertex in $U\cup V$, we see that there are $2^{2m}$
distinct matchings $\mu$ for the fixed choice of $2$-factor $F$ and function
$f:F\ra\\{0,1\\}$.

As the proof of Lemma 0.4 shows the two matchings $\mu$ and $\mu^{\prime}$ in
$\mu(F,f)$ we get by varying the choice at just one gadget are related to each
other by an _even_ permutation. For instance, the two matchings in Figure 2
are related by the $3$-cycle $x_{1}y_{1}z_{1}$. We can immediately conclude
that all $2^{2m}$ matchings in $\mu(F,f)$ have the same sign.

######  Lemma 0.6.

For any $2$-factor $F$ of $\Gamma$, any function $f:F\ra\\{0,1\\}$ and any
matchings $\mu_{1},\mu_{2}\in\mu(F,f)$, $\sgn{\mu_{1}}=\sgn{\mu_{2}}$.

We next show that we can go further and show that the sign of any matching in
$\mu(F,f)$ does not depend on the choice of $f$.

######  Lemma 0.7.

For any $2$-factor $F$ of $\Gamma$, any functions $f,g:F\ra\\{0,1\\}$ and any
matchings $\mu_{1}\in\mu(F,f)$ and $\mu_{1}\in\mu(F,g)$,
$\sgn{\mu_{1}}=\sgn{\mu_{2}}$.

######  Proof 0.8.

It suffices to show the lemma for functions $f$ and $g$ which differ at
exactly one edge $e\in F$ as the result then follows by transitivity.
Moreover, by Lemma 0.6, it suffices to choose any $\mu_{1}\in\mu(F,f)$ and
$\mu_{2}\in\mu(F,g)$ and show that they have the same sign

So, assume $f(e)=0$ and $g(e)=1$ and they agree on all other edges. Let
$e=\\{v,x\\}$ where $v$ has neighbours $x,y,z$ and $x$ has neighbours $v,u,w$.
Without loss of generality, assume $\\{v,y\\}$ and $\\{x,w\\}$ are in $F$ with
$f(\\{v,y\\})=f(\\{x,w\\})=g(\\{v,y\\})=g(\\{x,w\\})=0$. By assumption,
$\mu_{1}$ includes the edge $x_{0}-v_{0}$ and we can assume further that it
includes the edges $v_{\emptyset}-z_{0}$, $v_{\\{x,y\\}}-x_{1}$ in the gadget
corresponding to $v$ and the edges $x_{\emptyset}-u_{0}$,
$v_{\\{v,w\\}}-v_{1}$ in the gadet corresponding to $x$. In other words, it
contains alternating edges along the $10$-cycle depicted in Figure 3.

Figure 3: An alternating cycle between two matchings in $\mu(F,f)$ and
$\mu(F,g)$ where $f$ and $g$ differ on the edge $\\{v,x\\}$.

Now, choose $\mu_{2}$ to be the symmetric difference between $\mu_{1}$ and the
cycle in Figure 3. This is also a perfect matching and it is in $\mu(F,g)$ as
the only difference with $\mu_{1}$ as far as edges between gadgets is
concerned is that $\mu_{2}$ contains $x_{1}-v_{1}$ rather than $x_{0}-v_{0}$.
Moreover, it is easily seen that $\mu_{2}$ is obtained from $\mu_{1}$ by
composition with an even permutation: namely the $5$-cycle:
$(x_{0}z_{0}x_{1}x_{\\{v,w\\}}x_{\emptyset})$.

With this, we are now ready to establish the main result of this section.

######  Lemma 0.9.

If $\Gamma$ has an odd number of perfect matchings, then $\det(M)\neq 0$.

######  Proof 0.10.

By Lemma 0.2, we have

$\displaystyle\det(M)$ $\displaystyle=$
$\displaystyle|\\{\mu\mid\mu\in\umtch(\hG)\text{with}\sgn{\mu}=1\\}|$
$\displaystyle-|\\{\mu\mid\mu\in\umtch(\hG)\text{with}\sgn{\mu}=-1\\}|.$

For any $2$-factor $F$ of $\Gamma$ write $\mu(F)$ for
$\bigcup_{f:F\ra\\{0,1\\}}\mu(F,f)$ and note that by Lemma 0.4 $\mu(F)=2^{4m}$
for all $F$. Moreover, by Lemma 0.7 all matchings in $\mu(F)$ have the same
sign. Thus, we define $\sgn{F}$ to be the sign of $\eta^{\prime}\mu\eta^{-1}$
for any $\mu\in\mu(F)$. Hence, we have that

$\det(M)=2^{4m}\sum_{F}\sgn{F},$

where the sum is over all $2$-factors of $\Gamma$.

Since $\Gamma$ is $3$-regular, the number of $2$-factors of $\Gamma$ is
exactly the number of perfect matchings. Indeed, the complement of any
$2$-factor is a perfect matching and this gives a bijection between the
collection of perfect matchings and $2$-factors. Thus, since the number of
perfect matchings of $\Gamma$ is odd, so is the number of $2$-factors and we
conclude that the sum $\sum_{F}\sgn{F}$ cannot be zero, proving the result.


Thrust of Financial Technology, HKUST(GZ), Chinaxuechaowang@hkust-
gz.edu.cnhttps://orcid.org/0000-0001-6918-2699Protocol Labs,
USAs.azouvi@gmail.comhttps://orcid.org/0000-0002-7133-1937 Protocol Labs,
USAmarko.vukolic@protocol.aihttps://orcid.org/0000-0002-9898-5383 Xuechao
Wang, Sarah Azouvi and Marko Vukolić Security and privacy Distributed systems
security

###### Acknowledgements.

The authors would like to thank Guy Goren for his suggestion of Consistent
Broadcast as a mitigation to the $n$-split attack.Joseph Bonneau and S.
Matthew Weinberg 2 5th Conference on Advances in Financial Technologies (AFT
2023) AFT 2023 AFT 2023 October 23-25, 2023 Princeton, NJ, USA 282 5

# Security Analysis of Filecoin’s Expected Consensus in the Byzantine vs
Honest Model

Xuechao Wang111Corresponding author, part of work was done at Protocol Labs.
Sarah Azouvi  Marko Vukolić

###### Abstract

Filecoin is the largest storage-based open-source blockchain, both by storage
capacity (>11EiB) and market capitalization. This paper provides the first
formal security analysis of Filecoin’s consensus (ordering) protocol, Expected
Consensus (EC). Specifically, we show that EC is secure against an arbitrary
adversary that controls a fraction $\beta$ of the total storage for $\beta
m<1-e^{-(1-\beta)m}$, where $m$ is a parameter that corresponds to the
expected number of blocks per round, currently $m=5$ in Filecoin. We then
present an attack, the $n$-split attack, where an adversary splits the honest
miners between multiple chains, and show that it is successful for $\beta
m\geq 1-e^{-(1-\beta)m}$, thus proving that $\beta m=1-e^{-(1-\beta)m}$ is the
tight security threshold of EC. This corresponds roughly to an adversary with
$20\%$ of the total storage pledged to the chain. Finally, we propose two
improvements to EC security that would increase this threshold. One of these
two fixes is being implemented as a Filecoin Improvement Proposal (FIP).

###### keywords:

Decentralized storage; Consensus; Security analysis

###### category:

##  1 Introduction

Filecoin is the largest storage-based blockchain in terms of both market cap
[3] and total raw-byte storage capacity (>11EiB) [6]. In Filecoin, miners,
called Storage Providers (SPs), gain the right to participate in the consensus
protocol and to create blocks by pledging storage capacity to the
chain.222Filecoin further incentivizes the storage of “useful” data, where SPs
have the additional opportunity to boost their raw-byte storage power,
offering deals to verified clients, yielding _quality adjusted_ power [2].
They are in return compensated with a financial reward in the form of newly
minted FIL, the cryptocurrency underlying Filecoin, whenever their blocks are
included on-chain, where probability of a miner minting new block corresponds
to their storage power. The Filecoin consensus mechanism Storage Power
Consensus (SPC) consists mainly of two components: first, a _Sybil-resistance
mechanism_ that keeps an accurate map of the storage pledged by each storage
provider; and second, a consensus protocol that can be run by any set of
weighted participants and outputs an ordered list of transactions.

In this paper, we ignore the mechanisms that keep the mapping between miners
and their respective storage accurate (i.e., the Sybil-resistance mechanism
and the quality adjusted power policy) and focus on the sub-protocol run by
the weighted miners to produce an ordered list of transactions. This sub-
protocol is called Expected Consensus (EC) and weighs each participant
according to their storage power. We assume that the weighted list of miners
is accurately maintained and given as an input to EC. EC is a longest-chain
style protocol [1] (or, more accurately, a heaviest-chain protocol). At a high
level, it operates by running a leader election at every time slot in which,
on expectation, $m$ participants may be eligible to submit a block, where $m$
is a parameter currently equal to 5. Each participant is elected with
probability proportional to their weight. Multiple valid blocks submitted in a
given round may form a _tipset_ , which is a set of blocks sharing the same
height (i.e., round number) and parent tipset. In EC, the blockchain is a
chain of tipsets (i.e., a directed acyclic graph [DAG] of blocks) rather than
a chain of blocks. For example, in Figure 1(a) blocks {A,B,C}, {D,E} and
{F,G,H} each form a different tipset; and in Figure 1(b) blocks {A,B,C}, {D,E}
and {F} each form a different tipset. Every block in a tipset adds weight to
its chain of tipsets, while the fork choice rule is to choose the heaviest
tipset. EC works in a very similar fashion as longest-chain protocols like
Bitcoin do, but it uses tipsets instead of blocks. EC’s security has, until
now, only been argued informally, as with Bitcoin in its early days.
Intuitively, tipsets make it harder for an adversary with less storage to form
a competing chain of tipsets with more blocks than the main chain, as miners
can create a number of blocks proportional to their storage power. This is
analogous to Nakamoto’s private attack on the longest-chain protocol [22].
Specifically, assuming that two competing chains of tipsets are growing, with
different amount of storage power producing the two, since in EC more than one
block can be appended to a chain at each round, the difference between the
number of blocks created on each chain will grow roughly $m$ times faster than
in the case without tipset (i.e., where each chain can grow by at most one
block at each round). However, this intuitive security justification only
applies when examining the private attack, a specific instance, not a general
adversary. The lessons learned from the balance attack [23] on GHOST [28]
highlight that a comprehensive analysis encompassing all potential attacks is
crucial for assuring the security of a blockchain protocol. This comprehensive
evaluation is the main focus of this paper.

In this work, we conduct a formal security analysis of EC and prove that EC is
secure against any adversary that owns a fraction $\beta$ of the total storage
power for $\beta m<1-e^{-(1-\beta)m}$ (Section 5). To achieve this, we
carefully extend the proof technique developed in [14] to EC: the key step is
to identify the sufficient condition for a block to stay in the chain forever,
regardless of the complex DAG structure in EC. Indeed, the incorporation of
tipsets introduces substantial complexities to the problem. For instance, in
the longest-chain protocol, the chain growth is an independent and identically
distributed random variable in each round. Conversely, within EC, the chain
growth becomes dependent on the entire history of the blockchain, given that
it depends on the structure of the DAG. This increased dependency adds layers
of intricacy to the security analysis. Following similar literature [14, 16,
19], we consider a rather strong adversary, which we specify in Section 2,
that has “full control” over both the network and the tie breaking rule. We
then propose an attack, the $n$-split attack, in Section 6 in which an
adversary with power $\beta$ such that $\beta m\geq 1-e^{-(1-\beta)m}$ can
break the security of EC, effectively proving that the security threshold
$\beta m=1-e^{-(1-\beta)m}$ is tight for EC. With current parameters, this
means that EC is secure against an adversary that holds roughly 20% of the
total storage power. In our attack, an elected leader, controlled by the
adversary, equivocates by sending different blocks to different miners at each
round with the aim to split the honest miners into different chains and thus
reducing the weight of each tipsets’ chain. While the honest participants are
split and all mine on potentially many different forks, the adversary can
construct a _private_ tipsets’ chain on the side, i.e., a chain that does not
include any block mined by an honest miner (called for simplicity _honest
block_) and that will not be broadcast to any honest miner until the end of
the attack. Finally, in Section 7, we propose two countermeasures against this
attack aimed at augmenting the security threshold of Filecoin. The first one
entails eliminating the concept of tipsets, substituting EC with the longest-
chain protocol [19, 13, 9], as our observations suggest that lowering the
value of $m$ can enhance the security threshold. The second approach involves
the adoption of a consistent or reliable broadcast protocol [12, 18] to
prohibit the adversary from equivocating. Our second countermeasure is
currently in the process of being implemented as a Filecoin Improvement
Proposal [7].

((a)) Example of a tipset chain: {A,B,C} is the first tipset after Genesis,
and the parent tipset of {D,E}, which is itself the parent tipset of tipset
{F,G,H}.

((b)) Example of two tipsets with equal weight. Tipset {D,E} and tipset {F}
both have a weight of 5. (roughly, the weight is calculated as the sum of the
blocks in all the tipsets, see Section 3.3 for details).

Figure 1: Tipset structure in EC.

#### Related Work

This work is directly inspired by the line of work formally analyzing longest-
chain protocols either in the proof-of-work case [16, 27, 20] or proof-of-
stake [10, 19, 14, 25]. We adapt the technique in [14] to account for tipsets
instead of blocks (see Lemma 5.2). The main difference between using a chain
of tipsets and a chain of blocks is that in the tipset case, the number of
blocks in the chain at each round can increase by any finite integer value and
also depends on the structure of the DAG. By contrast, in the chain-of-blocks
case, the number of blocks of any honest chain increases by zero or one at
each round. This makes the tipset analysis more complex.

Similar attacks to the one we describe in Section 6 were proposed by Bagaria
et al. [10] in the context of proof-of-stake and by Natoli and Gramoli [23] in
the proof-of-work context. In both these works, the attacks are described on a
DAG-based blockchain, where each new block can include any previous block as
its parent. We adapt it to the tipset case, which is slightly different: in
the case of tipsets, a block may have multiple parents, but only blocks that
have themselves the same set of parents can be referenced by the child block.
The idea behind these attacks is to have an adversary publish its blocks in a
timely manner on different forks to ensure that honest miners keep on
extending two or even more chains instead of one, effectively spreading their
_power_ (be it stake, computation or storage) on different chains.

##  2 Model

In this section we present our model and assumptions.

###  2.1 Participants

Filecoin requires participants to pledge storage capacity to the chain to be
added to the list of participants. Following the work in [16, 19] we consider
a flat model, meaning that each participant accounts for one unit of storage.
This could easily be extended to a non-flat model by considering that a
participant holding $x$ units of storage controls $x$ “flat” participants. We
consider a static model wherein the set of participants is fixed during the
execution of the protocol. We assume that each participant $i$ possesses a key
pair $(\textsf{sk}_{i},\textsf{pk}_{i})$ and that every participant is aware
of the other participants and their respective public keys.

We consider a static adversary that corrupts a fraction $\beta$ of the
participants at the beginning of the execution of the protocol. In order to
defend against an adaptive adversary who can corrupt honest nodes on the fly
(i.e., dynamically, at the start of each round), one can either use key
evolving signature schemes [13] or checkpointing [8]. However, in order to
keep the problem simple, we do not consider an adaptive adversary in this
paper.

###  2.2 Network assumptions

We consider the lock-step synchronous network model adopted in [16, 19]. Time
is divided into synchronized rounds, each indexed with an integer in
$\mathbb{N}$. Following Filecoin’s terminology [1], we refer to each time slot
as an _epoch_. Each epoch has a fixed duration (currently 30 seconds in
Filecoin). To abstract the underlying peer-to-peer gossip network in Filecoin,
we simply assume that all messages sent by honest nodes are broadcast to all
nodes and that all honest nodes re-broadcast any message they deliver. All
network messages are delivered by the adversary, and we allow the adversary to
selectively delay messages sent by honest nodes, with the following
restrictions: (i) the messages sent in an epoch must be delivered by the end
of the current epoch; and (ii) the adversary cannot forge or alter any message
sent by an honest node. The adversary does not suffer any network delay. Note
that the adversary can selectively send its message only to a subset of honest
nodes. However, due to the re-broadcast mechanism, all honest nodes will
receive the message by the end of the next epoch.

The non-lock-step synchronous model, also known as the $\Delta$-synchronous
model, is also frequently employed in blockchain security analysis [9, 13, 14,
24, 27]. This model ensures messages sent by honest nodes are delivered within
a sliding window of $\Delta$ epochs. While this model might be more suitable
for proof-of-work blockchains, where miners persistently mine and broadcast
blocks, its application becomes less pertinent for PoS blockchains. In the
latter, honest nodes primarily remain dormant, awaiting the epoch boundaries
to send messages. Given the efficiency of today’s network infrastructure, a
30-second window adopted by EC is quite conservative. Consequently, we find
little justification to incorporate the $\Delta$-synchronous model in our EC
analysis.

###  2.3 Randomness

Random beacon. A random beacon [26] is a system that emits a random number at
regular intervals. EC relies on drand [4], a decentralized random beacon, to
provide miners a different random number at each epoch. This service is run by
a set of 16 independent institutions that run a multi-party protocol to
output, at regular intervals, a fresh random number. We assume that this
random number is unbiasable (i.e., truly random) and unpredictable before the
beginning of the epoch. We also assume that each miner in Filecoin has the
same view of each drand output, i.e., that drand is secure. We denote
$\textsf{drand}_{i}$ the random beacon emitted by drand and used by Filecoin
miners at epoch $i$.

Verifiable Random Function. A Verifiable Random Function (VRF) [21] is a
function that outputs a random number in a verifiable way, i.e., everyone can
verify that the output is indeed random and was generated correctly. A VRF is
composed of two polynomial-time algorithms: VRF.Proof and VRF.Verify (we omit
the key generation). VRF.Proof takes as inputs a seed seed and a secret key sk
and outputs a tuple
$(y=G_{\textsf{sk}}(\textsf{seed}),p=\pi_{\textsf{sk}}(\textsf{seed}))$ where
$y$ is a random number and $p$ is a proof that can be used to verify the
correctness of $y$. VRF.Verify takes as input a tuple $(\textsf{seed},y,p)$
and a public key pk and uses $p$ to verify that
$y=G_{\textsf{sk}}(\textsf{seed})$, in which case it outputs 1; otherwise, it
outputs 0. A VRF is correct if:

  1. 1.

if $(y,p)=\textsf{VRF.Proof}_{\textsf{sk}}(\textsf{seed})$, then
$\textsf{VRF.Verify}_{\textsf{pk}}(\textsf{seed},y,p)=1$;

  2. 2.

for all $(\textsf{sk},\textsf{seed})$, there is a unique $y$ s.t.
$\textsf{VRF.Verify}_{\textsf{pk}}(\textsf{seed},y,\pi_{\textsf{sk}}(\textsf{seed}))=1$;

  3. 3.

$G_{\textsf{sk}}(\textsf{seed})$ is computationally indistinguishable from a
random number for any probabilistic polynomial-time adversary.

Throughout the rest of this paper, we assume the existence of a correct VRF.

##  3 Filecoin’s Expected Consensus (EC)

Filecoin’s consensus protocol, EC, consists of three main components: a leader
election sub-protocol, a mining algorithm and a fork choice rule. Briefly, at
the beginning of each epoch, participants will check their eligibility to
produce a block by running the leader election. If they are elected, they use
the fork choice rule to select a tipset and include it as their _parent_
before broadcasting their block. We define the protocol more formally in this
section. However, we intentionally omit some details, such as those regarding
how participants must continually post proofs related to their pledged
storage, as they are not relevant to our analysis. Instead, we assume that all
participants continuously maintain one unit of storage. Furthermore, in
practice in Filecoin [1] a participant with power $x$ that is elected twice in
the same epoch will create only one block that _weighs_ twice more. This is
not relevant to our analysis, so we ignore it and prefer a flat model wherein
a participant elected twice simply creates two blocks under two different
identities. Such a model will favor an adversary as we illustrate in Section 6
and hence renders our analysis stronger.

Due to space limitations, a pseudocode representation of the algorithms
described in this section can be found in Appendix A.

###  3.1 Leader Selection Protocol

EC’s leader election is inspired by Algorand’s cryptographic sortition [17].
Briefly, the leader selection relies on a Verifiable Random Function (VRF)
[21] that takes as input the drand output value for that epoch. In each epoch,
each participant will compute
$\textsf{VRF.Proof}_{\textsf{sk}}(\textsf{seed})=(y=G_{\textsf{sk}}(\textsf{seed}),p=\pi_{\textsf{sk}}(\textsf{seed}))$
where seed is the drand value. If $y$ is below a predefined value target that
is a parameter of the protocol, then that participant is elected leader. Any
other participant can then use $p$ in order to verify that the random value
$y$ was computed correctly (i.e.,
$\textsf{VRF.Verify}_{\textsf{pk}}(\textsf{seed},y,p)=1$) and that the
participant is indeed an elected leader. The value of target is chosen such
that on expectation $m$ leaders are elected in each epoch. $m$ is a parameter
of the EC protocol currently set to $m=5$.

Proving that the leader selection mechanism is secure is outside the scope of
this paper, as similar results were already proven in, e.g., Algorand [17].
Instead, we assume that in each epoch, there is an independent random number
of participants that are elected leaders and that the number of leaders in
each epoch follows a Poisson distribution of parameter $m$. For a coalition
that consists of a fraction $\alpha$ of all the participants, their number of
elected leaders in an epoch follows a Poisson distribution of parameter
$\alpha\times m$.

###  3.2 Block and Tipset Structure

A block is composed of a header and a payload. The payload includes
transactions as well as other messages necessary for maintaining the set of
participants up to date. We omit its content in this analysis.

When a participant is elected to create a block, they include in the _header_
of the block their proof of eligibility (i.e., the VRF proof), an epoch number
(the epoch at which the block was created), a proof of storage called
WinningPost to prove that they maintain the storage they have pledged (we omit
the details of such proof) and finally a pointer to a set of _parent_ blocks.
For a block $\mathcal{B}$, we denote $\mathcal{B}.\mathsf{parent}$ its parents
set and $\mathcal{B}.\mathsf{epoch}$ its epoch number. The parents of a block
must satisfy certain conditions. First, they must all be in the same epoch,
and that epoch needs to be smaller than the block’s epoch. Second, all parent
blocks need to have the same set of parents themselves. Each set of blocks
that are in the same epoch and have the same set of parents is called a
_tipset_ and denoted $\mathcal{T}$. Formally, a tipset $\mathcal{T}$ is a non-
empty set of blocks:
$\mathcal{T}=\\{\mathcal{B}_{1},\cdots,\mathcal{B}_{r}\\}$, each of which
belongs to the same epoch, i.e.,
$\mathcal{B}_{1}.\mathsf{epoch}=\cdots=\mathcal{B}_{r}.\mathsf{epoch}$ and has
the same set of parents, i.e.,
$\forall(\mathcal{B}_{i},\mathcal{B}_{j})\in\mathcal{T}^{2}:\;\>\mathcal{B}_{i}.\mathsf{parent}=\mathcal{B}_{j}.\mathsf{parent}$.
Since all blocks in a tipset have the same parent, we abuse the notation and
denote $\mathcal{T}.\mathsf{parent}$ to denote the parent of tipset
$\mathcal{T}$. Similarly, $\mathcal{T}.\mathsf{epoch}$ denotes the tipset
epoch. We note that $\mathcal{T}.\mathsf{parent}$ is a tipset itself.

Since each block references a set of blocks, a Directed Acyclic Graph (DAG)
structure can be inferred from each block or tipset, where the blocks are the
vertices and the references to parents are the edges. Similarly, the set of
tipsets referencing each other as parents form a _chain_. For example, Figure
1(a) represents a chain of 4 tipsets (including the genesis) and a blockDAG of
9 blocks. Formally, a chain $\mathcal{C}$ is then a set of ordered tipsets
$\mathcal{C}=\\{\mathcal{T}_{0},\mathcal{T}_{1},\cdots,\mathcal{T}_{l}\\}$
such that $\mathcal{T}_{i}.\mathsf{parent}=\mathcal{T}_{i-1}$ for all $i>1$.
By convention, we have
$\mathcal{T}_{1}.\mathsf{parent}=\mathcal{T}_{0}=\\{\text{Genesis block}\\}$
and $\mathcal{T}_{i}=\emptyset$ if there is no block in epoch $i$. We note
$\mathcal{C}[\mathcal{T}_{i}]=\\{\mathcal{T}_{0},\mathcal{T}_{1},\cdots,\mathcal{T}_{i}\\}$.
Similarly, for a tipset $\mathcal{T}$, we can infer the associated chain,
denoted $\mathcal{C}[\mathcal{T}]$ as follows:
$\mathcal{C}[\mathcal{T}]=\\{\mathcal{T}_{0},\cdots,(\mathcal{T}.\mathsf{parent}).\mathsf{parent},\mathcal{T}.\mathsf{parent},\mathcal{T}\\}$.

###  3.3 Fork Choice Rule and Weight Function

In order to decide which tipset to include as its parents, EC provides a
_weight function_ that assigns a weight to different tipsets. The fork choice
rule will then consist of choosing the tipset with the heaviest weight. In
practice, EC’s weight function [1] is a complex function of (1) the number of
blocks in the chain and (2) the total amount of storage committed to the
chain. Moreover, the total amount of storage is taken far in the past to
ensure that everyone agrees on it. Since in our analysis we assume a static
model where the set of participants is fixed during the execution of the
protocol, we only take into consideration the number of blocks in the chain.
We discuss the impact of this simplification in Section 8. Formally, for a
tipset $\mathcal{T}$, we denote its weight $w(\mathcal{T})$ and have:

$w(\mathcal{T})=\sum_{\mathcal{T}_{i}\in\mathcal{C}[\mathcal{T}]}|\mathcal{T}_{i}|.$

In the case of a tie between two chains, a deterministic tie-breaker is used.
In practice, the tipset that contains the smallest VRF value is chosen.
However, in our analysis we consider a powerful adversary that has the power
to decide on ties. See Figure 1(b) for a visual representation of two tipsets
with equal weight.

###  3.4 Mining Algorithm

We describe the mining algorithm that miners in Filecoin run continuously. At
each epoch $i>0$ each participant with key pair $(\textsf{sk},\textsf{pk})$
performs the following:

  1. 1.

Fetch the drand value for epoch $i$ and verify eligibility by checking

$G_{\textsf{sk}}(\text{drand}_{i})\stackrel{{\scriptstyle?}}{{\leq}}\textsf{target},$

where target is chosen such that on expectation $m$ leaders are elected (with
$m=5$ in the current implementation).

  2. 2.

If elected leader, create a block as follows:

     * •

Choose the tipset with the highest weight (i.e., the most blocks) and
reference it as the block’s parent.

     * •

Include a proof of eligibility (i.e., the VRF value:
$\textsf{VRF.Proof}_{\textsf{sk}}(\textsf{drand}_{i})=(y,p)$), a WinningPost
to prove storage maintenance, as well as the payload.

  3. 3.

Broadcast the block newly created.

In parallel, whenever they receive a new block in epoch $i$, participants
verify its validity and, if it is valid, add it to their blockDAG. A block is
valid if and only if:

  1. 1.

The election proof $(y,p)$ is valid, i.e.,
$\textsf{VRF.Verify}_{\textsf{pk}}(\textsf{drand}_{i},y,p)=1$ and
$y\leq\textsf{target}$.

  2. 2.

The WinningPost is valid (details omitted).

  3. 3.

All the transactions in the payload are valid (details omitted).

  4. 4.

All its parent blocks form a valid tipset, i.e.:

     * •

They all belong to the same epoch.

     * •

They all have the same parents.

     * •

They are all valid blocks.

We analyze the backbone of EC in a static setting and hence omit some details
of the protocol. For example, in practice, the leader election mechanism uses
a _lookback parameter_ , meaning that only participants who pledged their
storage sufficiently in the past are eligible for block creation. Because we
consider a flat and static model, these details are not relevant to our
analysis.

##  4 Security Definitions

Security properties. We consider the standard security properties of _robust
transaction ledgers_ defined for blockchain systems [16, 14]. We start by
defining a transaction ledger and confirmed transactions in the ledger.

######  Definition 4.1 (Transaction ledger generated by a chain
${\mathcal{C}}$).

Given a chain ${\mathcal{C}}$, a transaction ledger $\mathcal{L}$ generated by
$C$ is a deterministic, totally-ordered and append-only list of transactions.
In particular, if ${\mathcal{C}}_{1}$ is a prefix of ${\mathcal{C}}_{2}$, then
$\mathcal{L}_{1}$ generated by ${\mathcal{C}}_{1}$ is a prefix of
$\mathcal{L}_{2}$ generated by ${\mathcal{C}}_{2}$.

For example, one way to generate a transaction ledger from a chain
$\mathcal{C}$ is to order the transactions from $\mathcal{C}$ by order of
chronological appearance (i.e., epoch number where they appeared in the chain)
and lexicographical order. Any deterministic rule is however valid and we
leave this unspecified.

######  Definition 4.2 (Confirmed transaction parameterized by
$\tau\in\mathbb{R}$).

If a transaction tx in the ledger appears in a block which is mined in epoch
$j\leq i-\tau$, then tx is said to be $\tau$-_confirmed_ in epoch $i$.

Our goal is to generate a transaction ledger that satisfies persistence and
liveness as defined in [16, 14]. Together, persistence and liveness guarantee
a robust transaction ledger; transactions will be adopted to the ledger and be
immutable.

######  Definition 4.3 (Robust transaction ledger from [16, 14]).

A blockchain protocol $\Pi$ maintains a robust transaction ledger if the
generated ledger satisfies the following two properties:

  * •

(Persistence) Parameterized by $\tau\in\mathbb{R}$. If a transaction tx
becomes $\tau$-confirmed at epoch $i$ in the view of one honest node, then tx
will be at least $\tau$-confirmed in the same position in the ledger by all
honest nodes for every epoch $k\geq i$.

  * •

(Liveness) Parameterized by $u\in\mathbb{R}$, if a transaction tx is received
by all honest nodes at epoch $i$, then after epoch $i+u$ all honest nodes will
contain tx in the same place in the ledger forever.

Notations. We then define random variables and stochastic processes of
interest and their properties.

Let $\alpha$ and $\beta$ be the collective fraction of storage power
controlled by honest nodes and malicious nodes, respectively
($\alpha+\beta=1$). We follow the notations of [11]. Let $H[r]$ and $Z[r]$ be
the number of blocks mined by the honest nodes and by the malicious nodes in
epoch $r$, then $H[r]$, $Z[r]$ are independent Poisson random variables with
means $(1-\beta)m$ and $\beta m$ respectively [1] (the value of the target
parameter is chosen to ensure this). In addition, the random variables
$\\{H[0],H[1],\cdots\\}$ and $\\{Z[0],Z[1],\cdots\\}$ are independent of one
another, since the value provided by drand to feed the leader election is
random. We now define the auxiliary random variables $X[r]$ and $Y[r]$ as
follows. If at epoch $r$ an honest node mines at least one block (i.e.,
$H[r]\geq 1$), then $X[r]=1$ and epoch $r$ is called a _successful_ epoch,
otherwise $X[r]=0$. If at epoch $r$ honest nodes mine exactly one block (i.e.,
$H[r]=1$), then $Y[r]=1$ and epoch $r$ is called a _uniquely successful_
epoch, otherwise $Y[r]=0$. Epoch $r$ is called an _isolated successful_ epoch
if it further satisfies that there is no honest block in epoch $r-1$ (i.e.,
$H[r-1]=0$ and $Y[r]=1$). Further, $X[r_{1},r_{2}]$ and $Y[r_{1},r_{2}]$ are
the number of successful and uniquely successful epochs, respectively, in the
interval $(r_{1},r_{2}]$, and $H[r_{1},r_{2}]$ and $Z[r_{1},r_{2}]$ are the
number of blocks mined by honest nodes and by the adversary respectively in
the interval $(r_{1},r_{2}]$.

In EC, chains may have equal weights. For simplicity and generality, we assume
tie-breaking always favors the adversary. This means that the persistence will
be broken as long as there are two sufficiently long forks with equal weights.

Given a chain of tipsets ${\mathcal{C}}$, let ${\mathcal{C}}[r]$ be the chain
truncated up to blocks in epoch $r$. Further, let $w({\mathcal{C}})$ be the
weight of ${\mathcal{C}}$. Let $W_{\max}[r]$ and $W_{\min}[r]$ be the maximum
and minimum weights of chains adopted by honest nodes at the end of epoch $r$.
Then, by our network model, we have:

$W_{\min}[r]\leq W_{\max}[r]\leq W_{\min}[r+1].$ (1)

Even if some honest nodes’ chains are “behind” in epoch $r$, by our re-
broadcast mechanism, their view for epoch $r$ will catch up with the rest of
the honest nodes in epoch $r+1$. Furthermore, honest participants always
extend the heaviest chain they are aware of, hence the inequality above.

We also have the following minimum honest chain growth property, which is
essential to our proof. For $t\geq r+1$,

$W_{\min}[t]\geq W_{\min}[r+1]+X[r+1,t]\geq W_{\max}[r]+X[r+1,t].$ (2)

This inequality again follows from the fact that honest participants always
extend the heaviest chain they know of. However, it could be that different
honest participants have different views and thus create blocks on different
chains, hence why we consider $X$ in the inequality above and not $H$.

##  5 Security Proof

In this section, we prove our main theorem, Theorem 5.1 stated below,
parameterized by the security parameter $\kappa$. The proof will proceed in
multiple steps. We extend the technique of Nakamoto blocks developed in [14].
We first define the notion of Nakamoto epochs in EC and prove that the honest
blocks mined in Nakamoto epochs remain in the heaviest chain forever. Then we
show that Nakamoto epochs exist and appear frequently regardless of the
adversarial strategy. Straightforwardly, the protocol satisfies liveness and
persistence: transactions can enter the ledger frequently through the Nakamoto
epochs, and once they enter, they remain at a fixed location in the ledger.

######  Theorem 5.1.

If $\beta m<1-e^{-(1-\beta)m}$, then EC generates a robust transaction ledger
that satisfies persistence (parameterized by $\tau=\kappa$) and liveness
(parameterized by $u=\kappa$) in Definition 4.3 with probability at least
$1-e^{-\Omega(\kappa^{1-\epsilon})}$, for any $0<\epsilon<1$.

###  5.1 Nakamoto epochs

Let us define the events:

$E_{rs}=\\{\mbox{event that $Z[r-1,t]<X[r+1,t]$ for all $t\geq s$}\\},$

$F_{s}=\bigcap_{0\leq r\leq s-2}E_{rs},$

$U_{s}=\\{\mbox{event that epoch $s$ is an isolated successful
epoch}\\}=\\{H[s-1]=0,Y[s]=1\\},$

and

$G_{s}=F_{s}\cap U_{s}.$

We will call epoch $s$ a _Nakamoto epoch_ if the event $G_{s}$ occurs. And we
have the following lemma.

######  Lemma 5.2.

If epoch $s$ is a Nakamoto epoch, then the unique honest block mined in epoch
$s$ is contained in any future chain ${\mathcal{C}}[t]$, $t\geq s$.

######  Proof 5.3.

Let $b_{s}$ be the unique honest block mined in epoch $s$. We will argue by
contradiction. Suppose $G_{s}$ occurs and let $t\geq s$ be the smallest $t$
such that $b_{s}$ is not contained in ${\mathcal{C}}[t]$, an honest chain
adopted by some honest node at the end of epoch $t$. Let $b_{r}$, mined in
epoch $r$, be the last honest block on ${\mathcal{C}}[t]$ (which must exist,
because the genesis block is by definition honest). If $r>s$, then
${\mathcal{C}}[r-1]$ is the prefix of ${\mathcal{C}}[t]$ before block $b_{r}$,
and does not contain $b_{s}$ (because ${\mathcal{C}}[r-1]$ is a prefix of
${\mathcal{C}}[t]$) contradicting the minimality of $t$. So $b_{r}$ must be
mined before or in epoch $s$. Since epoch $s$ is an isolated successful epoch,
we further know that $r\leq s-2$. The part of ${\mathcal{C}}[t]$ after block
$b_{r}$ must consist of all malicious blocks by the definition of $b_{r}$.
Note that this may also include malicious blocks in epoch $r$ (i.e., headstart
of the adversary). Hence, we have an upper bound for the weight of
${\mathcal{C}}[t]$.

$w({\mathcal{C}}[t])\leq W_{\max}[r]+Z[r-1,t]<W_{\max}[r]+X[r+1,t],$ (3)

where the first inequality is illustrated in Figure 2, and the second
inequality follows from the fact that event $F_{s}$ occurs. We also have a
trivial lower bound: $w({\mathcal{C}}[t])\geq W_{\min}[t]$. Therefore, we have

$W_{\min}[t]<W_{\max}[r]+X[r+1,t],$ (4)

which contradicts the minimum honest chain growth property (Eqn. 2).

Figure 2: Upper bound and lower bound of the weight of ${\mathcal{C}}[t]$ in
the proof of Lemma 5.2. Blocks with dotted lines are adversarial blocks. The
parent links are omitted for readability; each block has all blocks from the
previous epoch as parents.

Note that Lemma 5.2 implies that if $G_{s}$ occurs, then the entire chain
leading to the unique honest block mined in epoch $s$ from the genesis is
stabilized after epoch $s$.

###  5.2 Occurrence of Nakamoto epochs

Although the existence of Nakamoto epochs ensures that the block at this epoch
will be finalized, i.e., it will appear in every honest future chain, the
question now remains whether Nakamoto epochs exist at all and, if so, at what
frequency they appear. We start answering this question by proving in the next
lemma that Nakamoto epochs have a strictly positive probability of happening,
i.e., the probability of each epoch being a Nakamoto epoch is strictly
positive.

######  Lemma 5.4.

If $\beta m<1-e^{-(1-\beta)m}$, then there exists $p>0$ such that
$P(G_{s})\geq p$ for all $s$.

######  Proof 5.5.

Let $1-e^{-(1-\beta)m}=(1+\varepsilon)\beta m$ for some $\varepsilon>0$. The
random processes of interest start from epoch $0$. To look at the system in
stationarity, let us extend them to $-\infty<r<\infty$. This extension allows
us to extend the definition of $E_{rs}$ to all $r,s$, $-\infty<r<s<\infty$,
and define $\hat{F}_{s}$ and $\hat{G}_{s}$ to be:

$\hat{F}_{s}=\bigcap_{r\leq s-2}E_{rs}$

and

$\hat{G}_{s}=\hat{F}_{s}\cap U_{s}.$

Note that $\hat{G}_{s}\subset G_{s}$, so to prove that $P(G_{s})\geq p$ for
all $s$, it suffices to prove that $P(\hat{G}_{s})\geq p$ for all $s$. This is
proved next.

Let $\mathcal{W}_{r}=(H[r],Z[r])$. Let’s note that the variables
$\\{\mathcal{W}_{r}\\}$’s are independent from each other, hence
$\hat{F}_{s}\cap U_{s}=\bigcap_{r\leq s-2}(E_{rs}\cap U_{s})$ has a time-
invariant dependence on $\\{\mathcal{W}_{r}\\}$, which means that
$P(\hat{G}_{r})$ does not depend on $r$. Then it suffices to show
$P(\hat{G}_{0})>0$.

$\displaystyle P(\hat{G}_{0})$ $\displaystyle=P(\hat{F}_{0}|U_{0})P(U_{0})$
$\displaystyle=P(\hat{F}_{0}|U_{0})P(H[-1]=0)P(H[0]=1)$
$\displaystyle=(1-\beta)me^{-2(1-\beta)m}P(\hat{F}_{0}|U_{0}).$

Then, it remains to show that $P(\hat{F}_{0}|U_{0})>0$.

Recall that

$\hat{F}_{0}=\mbox{event that $Z[r-1,t]<X[r+1,t]$ for all $t\geq 0$ and
$r\leq-2$.}$

Let

$\hat{B}_{rt}=\mbox{event that $Z[r-1,t]\geq X[r+1,t]$},$

then

$\hat{F}_{0}^{c}=\bigcup_{t\geq 0,r\leq-2}\hat{B}_{rt}.$

Let us fix a particular integer $n>2$, and define:

$M_{n}=\mbox{event that $Z[-n-1,n]=0$}.$

Then

$\displaystyle P(\hat{F}_{0}|U_{0})$ $\displaystyle\geq$ $\displaystyle
P(\hat{F}_{0}|U_{0},M_{n})P(M_{n}|U_{0})$ (5) $\displaystyle=$
$\displaystyle\left(1-P(\cup_{t\geq
0,r\leq-2}\hat{B}_{rt}|U_{0},M_{n})\right)P(M_{n}|U_{0})$ $\displaystyle\geq$
$\displaystyle\left(1-\sum_{t\geq
0,r\leq-2}P(\hat{B}_{rt}|U_{0},M_{n})\right)P(M_{n}|U_{0})$
$\displaystyle\geq$ $\displaystyle(1-a_{n}-b_{n}-c_{n})P(M_{n}|U_{0}),$

where

$\displaystyle a_{n}$ $\displaystyle:=$ $\displaystyle\sum_{(r,t):-n\leq
r\leq-2\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }0\leq t\leq
n}P(\hat{B}_{rt}|U_{0},M_{n}),$ $\displaystyle b_{n}$ $\displaystyle:=$
$\displaystyle\sum_{(r,t):r\leq-2\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }t>n}P(\hat{B}_{rt}|U_{0},M_{n}),$ $\displaystyle
c_{n}$ $\displaystyle:=$
$\displaystyle\sum_{(r,t):r<-n\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }t\geq 0}P(\hat{B}_{rt}|U_{0},M_{n}).$

Note that the cases where $t>n$ and $r<-n$ are counted twice in $b_{n}$ and
$c_{n}$, but this is fine because we only need a lower bound. Next we will
bound $P(\hat{B}_{rt}|U_{0},M_{n})$. Consider three cases:

Case 1: $-n\leq r\leq-2\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}0\leq t\leq n$:

$\displaystyle P(\hat{B}_{rt}|U_{0},M_{n})$ $\displaystyle=$ $\displaystyle
P(Z[r-1,t]\geq X[r+1,t]|H[0]=1,H[-1]=0,Z[-n-1,n]=0)$ $\displaystyle=$
$\displaystyle P(X[r+1,t]\leq 0|H[0]=1,H[-1]=0,Z[-n-1,n]=0)$
$\displaystyle\leq$ $\displaystyle P(X[0]\leq 0|H[0]=1,H[-1]=0,Z[-n-1,n]=0)$
$\displaystyle=$ $\displaystyle 0.$

Summing these terms, we have $a_{n}=0$.

Case 2: $r\leq-2\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }t>n$:

$\displaystyle P(\hat{B}_{rt}|U_{0},M_{n})$ $\displaystyle=$ $\displaystyle
P(Z[r-1,t]\geq X[r+1,t]|H[0]=1,H[-1]=0,M_{n})$ $\displaystyle\leq$
$\displaystyle P((Z[r-1,-2]+Z[n,t])\geq(X[r+1,-2]+X[0,t]+1))$
$\displaystyle\leq$ $\displaystyle
P((Z[r-1,-2]+Z[n,t])\geq(X[r+1,-2]+X[0,t]))\text{//(*)}$ $\displaystyle\leq$
$\displaystyle P(Z[r+3,t]\geq X[r+3,t])\text{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ //$n>1$ and
$Z$'s and $X$'s are i.i.d r.v.s. }$ $\displaystyle\leq$ $\displaystyle
P(Z[r+3,t]\geq
X[r+3,t],X[r+3,t]\geq(1-\varepsilon/4)(1-e^{-(1-\beta)m})(t-r-3))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ +P(Z[r+3,t]\geq
X[r+3,t],X[r+3,t]<(1-\varepsilon/4)(1-e^{-(1-\beta)m})(t-r-3))$
$\displaystyle\leq$ $\displaystyle P(Z[r+3,t]\geq(1+\varepsilon/4)\beta
m(t-r-3))$ $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+P(X[r+3,t]<(1-\varepsilon/4)(1-e^{-(1-\beta)m})(t-r-3))$ $\displaystyle\leq$
$\displaystyle A_{0}e^{-\alpha_{0}\varepsilon^{2}(t-r-3)}$

for some positive constants $A_{0},\alpha_{0}$ independent of $n,r,t$.
Inequality (*) follows from counting $t-r-3$ epochs on the right hand side of
the equation and $\leq t-r-3$ epochs on the left hand side. The last two
inequalities follow from Lemma B.2, Lemma B.1 and the facts that
$1-e^{-(1-\beta)m}=(1+\varepsilon)\beta m$ and
$\frac{1+\varepsilon/4}{1-\varepsilon/4}<1+\varepsilon$. Summing these terms,
we have:

$\displaystyle b_{n}$ $\displaystyle=$
$\displaystyle\sum_{(r,t):r\leq-2\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }t>n}P(\hat{B}_{rt}|U_{0},M_{n})$ $\displaystyle\leq$
$\displaystyle\sum_{(r,t):r\leq-2\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}t>n}\left[A_{0}e^{-\alpha_{0}\varepsilon^{2}(t-r-3)}\right]:=\bar{b}_{n},$

which is bounded and moreover $\bar{b}_{n}\rightarrow 0$ as
$n\rightarrow\infty$.

Case 3: $r<-n\text{\leavevmode\nobreak\ and\leavevmode\nobreak\ }t\geq 0$:

$\displaystyle P(\hat{B}_{rt}|U_{0},M_{n})$ $\displaystyle=$ $\displaystyle
P(Z[r-1,t]\geq X[r+1,t]|H[0]=1,H[-1]=0,M_{n})$ $\displaystyle\leq$
$\displaystyle P((Z[r-1,-n-1]+Z[2,t])\geq(X[r+1,-2]+X[0,t]+1))$
$\displaystyle\leq$ $\displaystyle
P((Z[r-1,-n-1]+Z[2,t])\geq(X[r+1,-2]+X[0,t]))$ $\displaystyle\leq$
$\displaystyle P(Z[r+3,t]\geq X[r+3,t])\text{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ //$n>2$ and
$Z$'s and $X$'s are i.i.d r.v.s.}$ $\displaystyle\leq$ $\displaystyle
P(Z[r+3,t]\geq
X[r+3,t],X[r+3,t]\geq(1-\varepsilon/4)(1-e^{-(1-\beta)m})(t-r-3))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ +P(Z[r+3,t]\geq
X[r+3,t],X[r+3,t]<(1-\varepsilon/4)(1-e^{-(1-\beta)m})(t-r-3))$
$\displaystyle\leq$ $\displaystyle P(Z[r+3,t]\geq(1+\varepsilon/4)\beta
m(t-r-3))$ $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+P(X[r+3,t]<(1-\varepsilon/4)(1-e^{-(1-\beta)m})(t-r-3))$ $\displaystyle\leq$
$\displaystyle A_{0}e^{-\alpha_{0}\varepsilon^{2}(t-r-3)}$

for some positive constants $A_{0},\alpha_{0}$ independent of $n,r,t$. The
last two inequalities follow from Lemma B.2, Lemma B.1 and the facts that
$1-e^{-(1-\beta)m}=(1+\varepsilon)\beta m$ and
$\frac{1+\varepsilon/4}{1-\varepsilon/4}<1+\varepsilon$. Summing these terms,
we have:

$\displaystyle c_{n}$ $\displaystyle=$
$\displaystyle\sum_{(r,t):r<-n\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }t\geq 0}P(\hat{B}_{rt}|U_{0},M_{n})$
$\displaystyle\leq$ $\displaystyle\sum_{(r,t):r<-n\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }t\geq
0}\left[A_{0}e^{-\alpha_{0}\varepsilon^{2}(t-r-3)}\right]:=\bar{c}_{n},$

which is bounded and moreover $\bar{c}_{n}\rightarrow 0$ as
$n\rightarrow\infty$.

Substituting these bounds in (5) we finally get:

$P(\hat{F}_{0}|U_{0})>(1-\bar{b}_{n}-\bar{c}_{n})P(M_{n}|U_{0}).$

By setting $n$ sufficiently large such that $\bar{b}_{n}$ and $\bar{c}_{n}$
are sufficiently small, we conclude that $P(\hat{G}_{0})>0$.

###  5.3 Waiting time for Nakamoto epochs

We have established the fact that the event $G_{s}$ has $P(G_{s})\geq p>0$ for
all $s$. But how long do we need to wait for such an epoch to occur? We answer
this question in the following lemma, wherein we provide a bound on the
probability that in a interval $(j,j+k]$ of $k$ consecutive epochs, there are
no Nakamoto epochs, i.e., a bound on:

$q(j,j+k]:=P(\bigcap_{s=j+1}^{j+k}G_{s}^{c}),$

where $G_{s}^{c}$ is the complement of $G_{s}$.

######  Lemma 5.6.

If $\beta m<1-e^{-(1-\beta)m}$, then there exist constants $\alpha,A$ so that
for all $j,k\geq 0$,

$q(j,j+k]\leq A\exp(-\alpha\sqrt{k}).$ (6)

######  Proof 5.7.

Following the definition in Lemma 5.4, let

$\hat{B}_{rt}=\mbox{event that $Z[r-1,t]\geq X[r+1,t]$}.$

Similar to the calculation in Lemma 5.4, we have

$P(\hat{B}_{rt})\leq A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}$ (7)

for some positive constants $A_{1},\alpha_{1}$ independent of $r,t$.

Also we have

$G_{s}^{c}=F_{s}^{c}\cup U_{s}^{c}=\bigcup_{(r,t):r\leq s-2,t\geq
s}\hat{B}_{rt}\cup U_{s}^{c}.$ (8)

Divide $(j,j+k]$ into $\sqrt{k}$ sub-intervals of length $\sqrt{k}$ (assuming
$\sqrt{k}$ is a integer), so that the $i$-th sub-interval is:

$\mathcal{J}_{i}:=[j+1+(i-1)\sqrt{k},j+i\sqrt{k}].$

Now look at the first, fourth, seventh, etc sub-intervals, i.e. all the
$i=1\mod 3$ sub-intervals. Introduce the event that in the $\ell$-th ($1\mod
3$) sub-interval ($\mathcal{J}_{3\ell+1}$), a pure adversarial chain that is
rooted at a honest block (or more accurately a tipset including at least one
honest block) mined in that sub-interval ($\mathcal{J}_{3\ell+1}$) or in the
previous ($0\mod 3$) sub-interval ($\mathcal{J}_{3\ell}$) catches up with a
honest block in that sub-interval ($\mathcal{J}_{3\ell+1}$) or in the next
($2\mod 3$) sub-interval ($\mathcal{J}_{3\ell+2}$).

Formally,

$C_{\ell}=\bigcap_{s\in\mathcal{J}_{3\ell+1}}\bigcup_{(r,t):r\in\mathcal{J}_{3\ell}\cup\mathcal{J}_{3\ell+1},r\leq
s-2,t\geq
s,t\in\mathcal{J}_{3\ell+1}\cup\mathcal{J}_{3\ell+2}}\hat{B}_{rt}\cup
U_{s}^{c}.$

Note that for distinct $\ell$, the events $C_{\ell}$’s are independent since
$\hat{B}_{rt}$’s in different $C_{\ell}$’s do not have overlap (the
$\mathcal{J}$ intervals were cut specifically for this purpose). Also, we have

$P(C_{\ell})\leq P(\mbox{no Nakamoto epoch in $\mathcal{J}_{3\ell+1}$})=1-p<1$
(9)

by Lemma 5.4.

Introduce the atypical events:

$\displaystyle B$ $\displaystyle=$
$\displaystyle\bigcup_{(r,t):r\in(j,j+k]\mbox{\leavevmode\nobreak\
or\leavevmode\nobreak\ }t\in(j,j+k],r<t,t-r\geq\sqrt{k}}\hat{B}_{rt}\;,\text{
and }$ $\displaystyle\tilde{B}$ $\displaystyle=$
$\displaystyle\bigcup_{(r,t):r\leq j,j+k<t}\hat{B}_{rt}\;.$

The events $B$ and $\tilde{B}$ are the events that an adversarial chain
catches up with an honest block far ahead (more than $\sqrt{k}$ epochs).

By (7) and an union bound we have that

$\displaystyle P(B)$ $\displaystyle\leq$
$\displaystyle\sum_{(r,t):r\in[j+1,j+k]\mbox{\leavevmode\nobreak\
or\leavevmode\nobreak\
}t\in[j+1,j+k],r<t,t-r\geq\sqrt{k}}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}$
$\displaystyle\leq$
$\displaystyle\sum_{r=j+1}^{j+k}\big{(}\sum_{t=r+\sqrt{k}}^{\infty}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}\big{)}+\sum_{t=j+1}^{j+k}\big{(}\sum_{r=0}^{t-\sqrt{k}}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}\big{)}$
$\displaystyle\leq$ $\displaystyle
2k\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}\sqrt{k}}}{1-e^{-\alpha_{1}\varepsilon^{2}}},$

and

$\displaystyle P(\tilde{B})$ $\displaystyle\leq$
$\displaystyle\sum_{(r,t):r\leq
j,t>j+k}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}$ $\displaystyle\leq$
$\displaystyle\sum_{r=0}^{j}\big{(}\sum_{t=j+k+1}^{\infty}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{r=0}^{j}\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}(j+k+1-r)}}{1-e^{-\alpha_{1}\varepsilon^{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}(k+1)}}{(1-e^{-\alpha_{1}\varepsilon^{2}})^{2}}.$

Now, we have:

$\displaystyle q(j,j+k]$ $\displaystyle\leq$ $\displaystyle P(\mbox{no
Nakamoto epoch in $\bigcup_{\ell=0}^{\sqrt{k}/3}\mathcal{J}_{3\ell+1}$})$
$\displaystyle\leq$ $\displaystyle P(\mbox{no isolated successful epoch in
$\bigcup_{\ell=0}^{\sqrt{k}/3}\mathcal{J}_{3\ell+1}$})+P(B)+P(\tilde{B})+P(\bigcap_{\ell=0}^{\sqrt{k}/3}C_{\ell})$
$\displaystyle=$ $\displaystyle
e^{-\Omega(k)}+P(B)+P(\tilde{B})+(P(C_{\ell}))^{\sqrt{k}/3}$
$\displaystyle\leq$ $\displaystyle
e^{-\Omega(k)}+2k\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}\sqrt{k}}}{1-e^{-\alpha_{1}\varepsilon^{2}}}+\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}(k+1)}}{(1-e^{-\alpha_{1}\varepsilon^{2}})^{2}}+(P(C_{\ell}))^{\sqrt{k}/3}$
$\displaystyle\leq$ $\displaystyle A\exp(-\alpha\sqrt{k})$ (11)

for some positive constants $A$ and $\alpha$. The equality (5.7) is due to the
independence of $C_{\ell}$’s and the inequality (11) is due to (9). Hence the
lemma follows.

We can also tighten the exponent, but at the cost of larger constants in the
bound. The proof of the following lemma is almost verbatim identical with the
proof of Lemma 5.6, and its detailed explanation can be found in Appendix C.

######  Lemma 5.8.

If $\beta m<1-e^{-(1-\beta)m}$, then there exist constants
$\alpha_{\epsilon},A_{\epsilon}$ so that for all $j,k\geq 0$,

$q(j,j+k]\leq A_{\epsilon}\exp(-\alpha_{\epsilon}k^{1-\epsilon}),$ (12)

for any $0<\epsilon<1$.

###  5.4 Persistence and liveness

Equipped with all the previous lemmas, we can now prove the persistence and
liveness properties of EC for $\beta m<1-e^{-(1-\beta)m}$.

######  Proof 5.9 (Proof of Theorem 5.1).

Suppose current epoch is $r$. Then by Lemma 5.8, with probability at least
$1-e^{-\Omega(\kappa^{1-\epsilon})}$, there is at least one Nakamoto epoch in
the interval $(r-\kappa,r]$. Let epoch $s\in(r-\kappa,r]$ be a Nakamoto epoch.
Then by Lemma 5.2, the chain up to epoch $s-1$ is permanent since the unique
honest block in epoch $s$ never leaves the heaviest chain. Hence EC is
persistent with probability at least $1-e^{-\Omega(\kappa^{1-\epsilon})}$. The
liveness of EC is simply a consequence of the frequent occurrence of Nakamoto
epochs. Particularly, for each honest transaction, either it will be included
by an honest block $B$ in a Nakamoto epoch or it has already been included by
$B$’s ancestors.

##  6 n-split Attack

In order to confirm whether an adversary with power $\beta m\geq
1-e^{-(1-\beta)m}$ can indeed break the persistence and liveness properties of
the system, we consider the following $n$-split attack.

###  6.1 Attack description

The attacker tries to split the honest participants among $n$ chains such that
in each epoch, at most one honest block is added to each chain (i.e., no two
honest players mine on the same chain). To do this, the attacker creates $n$
copies of one of its block (each copy has the same election proof, but
different payloads) and sends one different block to each of the $n$ honest
players; see illustration in Figure 3(a). To maintain the split for a long
period, the adversary must repeat the attack at every epoch where at least one
honest block is mined. In this case, the weight of the chain of each honest
player will increase by two: one honest block and one adversarial block. For
example in Figure 3(a), since blocks C and D are both honest (i.e., created by
honest miners), by the next epoch, epoch 3, all the participants will have
received them and use the deterministic tie breaker to all decide to mine on
the same tipset, say {D}. Hence the adversary must create equivocating blocks
in epoch 2 as well in order to ensure that in epoch 3, honest miners all
choose different tipsets to append their block to. In Figure 3(b), the
adversary sends equivocating blocks $E_{1}$ and $E_{2}$ to prevent blocks $H$
and $F$ from being appended to the same chain. These figures include only two
honest blocks at epoch 2 and 3 for clarity. In practice, the adversary will
create as many equivocating blocks as there are honest miners to ensure that
everyone sees a different block and that no two honest participants mine on
the same tipset.

Whenever there is no honest block mined in an epoch, the attacker does
nothing. In this case, the weight of the chain of each honest player will not
increase. Meanwhile, the attacker also reuses all its blocks to build a
private chain, i.e., a chain that it does not broadcast to other participants
and that does not include any honest blocks. The expected chain growth of the
adversary’s private chain is $\beta m$. The weight of the honest chain
increases by two if there is at least one honest block mined in an epoch
(which happens with probability $1-e^{-(1-\beta)m}$), and 0 otherwise (which
happens with probability $e^{-(1-\beta)m}$). Hence, the expected chain growth
of the honest chain is $2(1-e^{-(1-\beta)m})$. Therefore, this attack succeeds
with non-negligible probability when $\beta m>2(1-e^{-(1-\beta)m})$, i.e.,
when the adversarial chain grows at a higher rate than the honest split
chains. Rather than specifying the exact success probability, we demonstrate
that it remains constant, independent of the confirmation depth $\tau$, as
defined in Definition 4.2. Let $L$ be adversarial lead, i.e., the adversary
has a lead of $L$ additional private blocks over the public heaviest chain.
Suppose that with probability $p_{L_{0}}$, the initial lead before the attack
starts is $L_{0}$. Although $p_{L_{0}}$ decreases with $L_{0}$, it remains
non-zero because there’s a chance the adversary could mine $L_{0}$ blocks
before the honest nodes mine any block. Note that in the $n$-split attack, as
long as the adversarial lead $L>0$, the adversary can invariably split the
honest nodes across $n$ chains. Therefore, the adversarial private chain will
grow faster than the honest public chain when $\beta m>2(1-e^{-(1-\beta)m})$.
According to the standard random walk (with drift) theory [15], $L$ goes to 0
only with a probability of $e^{-O(L_{0})}$. This implies that the $n$-split
attack succeed with probability at least $p_{L_{0}}(1-e^{-O(L_{0})})$, for any
value of the confirmation depth $\tau$.

((a)) The adversary sends two different blocks $B_{1}$, $B_{2}$ in epoch 1
such that in epoch 2, honest blocks $C$, $D$ have different parents and hence
cannot be included in a tipset. The honest power is thus split between
different tipsets’ chains.

((b)) The adversary keeps the network split in epoch 3 by creating two
equivocating blocks: $E_{1}$ and $E_{2}$ in epoch 2. In epoch 3, honest blocks
$H$ and $F$ are mined on two different tipsets.

((c)) If ties are always broken in favor of the adversary, the adversary can
instead create another block $B_{3}$ in epoch 1. In epoch 2, blocks $E_{1}$
and $E_{2}$ are preferred to $C$ and $D$, hence in epoch 2, all the tipsets’
chains increase by only one block. The attack is repeated in the next epoch,
as long as the adversary has enough blocks to create a fork as heavy as the
honest chains.

Figure 3: n-split attack. Each block filled in grey is an equivocating block,
meaning they were created by the adversary using the same leader election
proof in one epoch. Each green block is an honest block.

Some numerical results: for $m=3$, we have $\beta>0.512$; for $m=5$, we have
$\beta>0.382$; and $\beta>0.284$ for $m=7$. Approximately, $\beta\gtrsim 2/m$.
Intuitively, with this attack, the threshold is inversely proportional to $m$,
as with a bigger $m$, the adversary is elected leader more often and thus has
more opportunities to keep the network split. If the adversary were elected
leader on a less regular basis, it would be harder to keep sending
equivocating blocks and thus keep the network split for longer. Note that this
threshold applies specifically to the attack described above, and it differs
from the security threshold identified in Theorem 5.1. This is because
different thresholds may exist for different attacks.

Following the standard model of longest-chain analysis [16, 13, 14], we give
the power of tie-breaking to the attacker (i.e., tie-breaking always favors
the attacker’s block). Recall that the same assumption is made in our model
(Section 2) and proof (Section 5). For example in Figure 3(c), if we assume
that the adversarial blocks (in red) will always be favored in the case of two
chains with the same number of blocks, then the adversary does not need to
create a block on the same tipset as honest blocks (as in Figure 3(b)). The
adversary will instead create another block $B_{3}$ and mine yet on another
tipset than the honest participant in epoch 2. In epoch 3 the adversarial
chains ending in tipsets $\\{E_{1}\\}$ and $\\{E_{2}\\}$ are preferred over
$\\{C\\}$ or $\\{D\\}$, hence honest blocks $H$ and $F$ are mined on different
forks and each fork’s weight increased by only one in epoch 2, as opposed to 2
in Figure 3(b). By repeating this attack at each epoch, the weight of the
chain of each honest player will only increase by one when there is at least
one honest block mined. Following the same argument as above, this attack
succeeds with non-negligible probability when $\beta m>(1-e^{-(1-\beta)m})$,
i.e., when the adversarial chain grows at a higher rate than the honest split
chains. We notice that this now matches the security threshold in Theorem 5.1,
hence proving that $\beta m=1-e^{-(1-\beta)m}$ is the tight threshold of the
protocol in our security model as defined in Section 2. Indeed, Theorem 5.1
proves that no adversary below this threshold can break the security of the
EC, and the $n$-chain split attack just described proves that an adversary
above this threshold can indeed break the persistence and liveness of the EC.

Some numerical results: for $m=3$, we have $\beta\simeq 0.293$; for $m=5$, we
have $\beta\simeq 0.196$; and $\beta\simeq 0.143$ for $m=7$. Approximately,
$\beta\simeq 1/m$. As remarked before, the threshold is inversely proportional
to the number of leaders elected as, intuitively, being elected more often
gives more opportunities to an adversary.

###  6.2 Discussion

Rationality of the attack. We note that this attack is detectable as everyone
can see that blocks with the same proof of eligibility but different payload
were created. In practice, this behaviour is slashable in Filecoin [1].
However, in Filecoin an adversary has the ability to spread its storage over
multiple identities, i.e., create multiple identities that each possesses one
unit of storage. For example in Filecoin the minimum unit of storage that can
be pledged to the chain is 32 GiB. As of August 2023 the total storage pledged
to the chain is around 11 EiB [6], hence an adversary that possesses 20% of
the total power, i.e., 2.2 EiB could potentially “spread” its storage over
$\frac{2.2\times 10^{18}}{32\times 10^{9}}\simeq 10^{8}$ different identities,
that each possesses 32 GiB of storage. At each epoch, except with extremely
small probability, the adversary will have a new “identity” elected to create
a block (it is very unlikely for a miner with 32GiB of storage out of 11 EiB
to be elected twice in a row). Assuming that each identity gets slashed and
removed from the list of participants after equivocation, after performing the
attack over 1000 epochs, the adversary will still have $9.9999\cdot 10^{7}$
identities left out of $10^{8}$ and will only be slashed
$\frac{10^{3}}{10^{8}}=10^{-5}$ of its total collateral. In this analysis we
considered orders of magnitude rather than exact numbers, so for simplicity we
counted only the “real power” and did not account for the “boosted adjusted
power” that can be gained through the FIL+ program [5]. Note that it is not
possible for any honest miner to know which identities belong to the adversary
before the equivocation. Hence excluding equivocating participants from the
protocol is not sufficient to prevent the attack.

Furthermore, we note that for the adversary to be slashed, a special
transaction, _a fraud proof_ transaction must be submitted on-chain by any
participant. An adversary that is able to continually exclude honest blocks as
is the case with the $n$-split attack may thus in practice never be slashed as
no honest participant will get the opportunity to include the slashing
transaction on-chain. This is why even when considering incentives and the
slashing mechanism in place, this attack is still rational.

Network control. In this attack, we assumed a powerful adversary that not only
has the power to break ties in its favor, but has also full control of the
network, as specified in Section 2.2. However we remark that for this attack
to work, an adversary only needs limited power over the network. Specifically,
the adversary needs to be directly connected to every participants but does
not need to control the propagation time between honest participants, as we
illustrate now.

In Filecoin honest miners will stop accepting blocks for an epoch after a
cutoff time. For the split to happen the adversary could send each block
$B_{1},\dots,B_{n}$ to each different participants $1,\dots,n$ right before
the cutoff, i.e., participant $i$ receives block $B_{i}$ from the adversary
just before the cutoff time, ensuring block $B_{i}$ is accepted by participant
$i$. The adversary would need to know the propagation time between itself and
each participant to do so, however this is easy to estimate. Since participant
$i$, receives $B_{i}$ just before the cutoff time, whatever the propagation
delay between $i$ and another honest participant $j$ is, the adversary is
guaranteed that $j$ will received $B_{i}$ from $i$ _after_ the cutoff time and
hence that any honest miner $j\neq i$ will not accept $B_{i}$.

Furthermore we note that when participant $j$ receives block $B_{i}$, after
the cutoff, $j$ will detect the equivocation as $j$ already received block
$B_{j}$ from the adversary. However at that point, $j$ has already created its
block that includes $B_{j}$ as a parent, hence it is too late for $j$ to
discard $B_{j}$ due to equivocation. The mitigation that we propose in Section
7.2 changes this.

((a)) Current case.

((b)) Case with a (simplified) consistent broadcast.

Figure 4: The dashed arrow represents the arrow of time. The different cutoff
and arrival time are marked with vertical arrows. The adversary ensures that
$j$ receives $B_{j}$ right before the cutoff so $j$ accepts $B_{j}$. In the
first case, by the time $j$ sees an equivocation, it is too late as $B_{j}$
was already included as a parent. In the second case, assuming $j$ receives
$B_{i}$ before the second cutoff, then $j$ will discard $B_{j}$ and not
include it as a parent.

##  7 Mitigations

We propose two possible mitigations to the $n$-split attack described in
Section 6 which could also help increase the security threshold of EC.

###  7.1 Replace EC by the Longest-chain Protocol in SPC

One solution to the $n$-split attack is to remove the notion of tipsets and
instead change EC to the longest-chain protocol (i.e., Ouroboros family of
protocols [19, 13, 9] in the proof-of-stake setting), where one block has
exactly one parent. In the longest-chain protocol, the effort of an adversary
to split the network would have much less impact on the overall security of
the protocol since each chain can increase by one block at each epoch at most
anyway. Furthermore, moving to the longest-chain protocol allows for
inheritance of all the security properties (e.g., a security threshold of 50%)
of all proof-of-stake protocols based on that setting [13, 10, 14]. Dembo et
al. [14] indeed showed that in the longest-chain case, the worst attack is the
private attack. Hence, the $n$-split attack described in Section 6, or its
variant, would not be the worst attack anymore. However, transitioning from EC
to a longest-chain protocol is not a straightforward task. First, it’s crucial
to understand that merely setting $m=1$ does not transform EC into a longest-
chain protocol, as more than one block can still be added per epoch.
Furthermore, our analysis indicates that an EC with $m=1$ has a security
threshold of approximately 43.2%, as opposed to 50% in the longest-chain
protocol. Consequently, to enhance the security, the concept of a tipset will
need to be eliminated. Implementing such a change, however, would necessitate
a hard fork.

###  7.2 Consistent Broadcast

Another solution is to use a form of consistent or reliable broadcast [12,
18]. This type of broadcast prevents an adversary from equivocating (i.e.,
creating two blocks with the same leader election proof but different
contents). The consistent broadcast consists in adding a second cutoff to the
cutoff discussed in Section 6.2. Specifically, it ensures that after
participant $j$ received $B_{j}$ from the adversary (before the first cutoff),
$j$ will wait for a “second” cutoff before forming its block and including
$B_{j}$ as a parent. When $j$ receives equivocating block $B_{i}$ from the
adversary, $j$ will detect the equivocation and decide not to include $B_{j}$
(neither $B_{i}$), hence the attack is mitigated. This is illustrated in
Figure 4. The epoch in Filecoin is thus split as follows: during the first
period, participants will store every valid block received in their “pending
blocks” set. In the second period, after the first cutoff and before the
second cutoff, every new valid block received will be stored in the set of
“rejected blocks” for that epoch. In the third period, after the second
cutoff, participants will compare the set of pending blocks and rejected
blocks, if they detect equivocating blocks, they are removed from the pending
set. Every block that is left in the pending set will then be included in the
tipset. This implementation as it is simple and backward compatible (i.e.,
only requires a soft-fork) although it assumes synchronicity. With consistent
broadcast, however, the adversary is still able to split the network in two
ways. First it could do so by ensuring that only a fraction of the honest
nodes accept its block (i.e., the network will be split between the nodes that
accept the adversarial block vs those that do not). The second way in which
the network could be split is if the adversary is elected more than once, say
$\ell$ times in one epoch (here we assume that the adversary controls many
different participants). Then the adversary could similarly ensure that for
each block it is able to create (with different election proofs), only some of
the nodes accept it. The network is then split in $2^{\ell}$ ways (all the
combination of accept vs reject for each of the $\ell$ blocks).We hypothesize
that, under a non-equivocating adversary, the security threshold of EC with
$m=5$ is approximately $40\%$. Intuitively, with this level of power, the
adversary creates fewer than two blocks per epoch on average; furthermore,
without the ability for equivocation, it is impossible for the adversary to
maintain two chains of equal weights over numerous epochs. We leave a formal
proof as future work.

##  8 Limitations and Future Work

For practical reasons, this work made a few simplifying assumptions. We
discuss them here.

Incentive consideration. This work considers the classic model of honest vs
malicious participants and does not address the rationality of participants. A
formal study of incentive compatibility is also important for understanding
the security of EC. However, we leave this for future work. Assuming a fully
malicious adversary that is willing to lose money to attack the system, a
scenario we consider in this paper, makes for a stronger proof than assuming a
rational adversary. In Section 6.2, we discussed why it is realistic to
consider an irrational adversary for the $n$-split attack we proposed, as
slashing may not always be possible if the adversary has the ability to censor
transactions. It still remains to show that the honest strategy is compatible
with a rational strategy even in the presence of an adversary. We leave this
for future work.

Weight function. In our analysis, we only took into consideration the number
of blocks in the chain for the weight function. We leave as future work an
analysis that also considers the total storage, as specified in Expected
Consensus [1]. Specifically we believe that a complex weight function allows
for more vectors of attack and that an adversary could use this to try to blow
the weight of its own chain. For example, the adversary could remove its
storage from the main chain and thus decrease the weight of the main chain,
while privately creating an alternative chain that would be heavier because it
has more storage pledged. The mechanisms for maintaining and removing storage
are, however, complex and ignored in this work. For simplicity, we thus
consider the weight of a tipset to simply be equal to the number of blocks
referenced in its blockDAG.

##  9 Conclusion

In this paper we presented a formal analysis of Expected Consensus, a sub-
protocol of Filecoin’s Storage Power Consensus, and we proposed two concrete
ways to improve SPC’s security. One of our mitigations, using consistent
broadcast, is currently being implemented as a Filecoin Improvement Proposal.
It remains an open problem to quantify the new security threshold of EC with
this fix, although our proofs remain valid in this case, hence the security
threshold is at least such that $\beta m<1-e^{-(1-\beta)m}$ as proved in
Section 5. Furthermore, we made many simplifying assumptions in this work. It
would be interesting to relax these in the future work; e.g., by extending
this proof to the dynamic and asynchronous case, considering the more complex
variant of the weight function or incorporating incentives.

## References

  * [1] Filecoin Spec.  https://spec.filecoin.io/.
  * [2] A Guide to Filecoin Storage Mining.  https://filecoin.io/blog/posts/a-guide-to-filecoin-storage-mining/.  Accessed: 2023-08-02.
  * [3] Coin Market Cap.  https://coinmarketcap.com/.
  * [4] Drand.  http://https://drand.love/.  Accessed: 2022-08-30.
  * [5] Filecoin Plus.  https://docs.filecoin.io/basics/how-storage-works/filecoin-plus/.
  * [6] Filfox - Filecoin Explorer.  https://filfox.info/en.
  * [7] FIP-0051: Improving EC security with Consistent Broadcast.  https://github.com/filecoin-project/FIPs/blob/master/FRCs/frc-0051.md.
  * [8] Sarah Azouvi and Marko Vukolić.  Pikachu: Securing PoS blockchains from long-range attacks by checkpointing into Bitcoin PoW using Taproot.  arXiv preprint arXiv:2208.05408, 2022.
  * [9] Christian Badertscher, Peter Gaži, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas.  Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 913–930, 2018.
  * [10] Vivek Bagaria, Amir Dembo, Sreeram Kannan, Sewoong Oh, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni.  Proof-of-stake longest chain protocols: Security vs predictability.  arXiv preprint arXiv:1910.02218, 2019.
  * [11] Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath.  Prism: Deconstructing the blockchain to approach physical limits.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 585–602. ACM, 2019.
  * [12] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  Journal of the ACM (JACM), 32(4):824–840, 1985.
  * [13] Bernardo David, Peter Gaži, Aggelos Kiayias, and Alexander Russell.  Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 66–98. Springer, 2018.
  * [14] 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.
  * [15] William Feller.  An introduction to probability theory and its applications.  Technical report, Wiley series in probability and mathematical statistics, 3rd edn.(Wiley, New …, 1971.
  * [16] 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.
  * [17] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich.  Algorand: Scaling Byzantine agreements for cryptocurrencies.  In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51–68, 2017.
  * [18] Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Dragos-Adrian Seredinschi, and Yann Vonlanthen.  Scalable Byzantine reliable broadcast (extended version).  arXiv preprint arXiv:1908.01738, 2019.
  * [19] 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.
  * [20] Lucianna Kiffer, Rajmohan Rajaraman, and Abhi Shelat.  A better method to analyze blockchain consistency.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 729–744, 2018.
  * [21] Silvio Micali, Michael Rabin, and Salil Vadhan.  Verifiable random functions.  In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 120–130. IEEE, 1999.
  * [22] Satoshi Nakamoto and A Bitcoin.  A peer-to-peer electronic cash system.  Bitcoin.–URL: https://bitcoin. org/bitcoin. pdf, 4(2), 2008.
  * [23] Christopher Natoli and Vincent Gramoli.  The balance attack against proof-of-work blockchains: The r3 testbed as an example.  arXiv preprint arXiv:1612.09426, 2016.
  * [24] Rafael Pass, Lior Seeman, and Abhi Shelat.  Analysis of the blockchain protocol in asynchronous networks.  In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part II, pages 643–673. Springer, 2017.
  * [25] 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.
  * [26] Michael O Rabin.  Transaction protection by beacons.  Journal of Computer and System Sciences, 27(2):256–267, 1983.
  * [27] Ling Ren.  Analysis of Nakamoto consensus.  Cryptology ePrint Archive, 2019.
  * [28] Yonatan Sompolinsky and Aviv Zohar.  Secure high-rate transaction processing in bitcoin.  In Financial Cryptography and Data Security: 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected Papers 19, pages 507–527. Springer, 2015.

## Appendix

##  Appendix A Pseudocode for EC

The main algorithm is presented in Algorithm 1 and the algorithm for block
validation is presented in Algorithm 2.

1:import

2: drand

3: ForkChoiceRule

4: Broadcast

5: VRF

6: isValid (Algorithm 2)

7:Parameters:

8: epochLength

9: $m$

10: target $\triangleright$ Chosen such that $m$ leaders are elected on
expectation

11:Init:

12: epochNumber $\leftarrow 0$

13: blockDAG$\leftarrow${Genesis Block}

14:upon event time.Now() % epochLength == 0 do $\triangleright$ Beginning of
the epoch

15: epochNumber $\leftarrow$ epochNumber +1

16: $\textsf{seed}\leftarrow$ drand(epochNumber)

17: $(y,p)\leftarrow\textsf{VRF.Proof}_{\textsf{sk}}(\textsf{seed})$

18: if $y\leq\textsf{target}$ then

19: $\mathcal{T}\leftarrow$ForkChoiceRule(blockDAG) $\triangleright$ Choose
the DAG with the most blocks

20: $\mathcal{B}\leftarrow$ CreateBlock($\mathcal{T},(y,p)$,
epochNumber,WinningPost payload)

21: Broadcast($\mathcal{B}$)

22:upon event Receiving block $\mathcal{B}$ do

23: if $\textsf{isValid}(\mathcal{B})==1$ then

24: blockDAG.append($\mathcal{B}$)

Algorithm 1 Main algorithm

1:Input: block $\mathcal{B}$

2:import

3: drand

4: isPayloadValid

5: isStorageValid

6:Parse ($\mathcal{T},(y,p)$, epochNumber,WinningPost payload)
$\leftarrow\mathcal{B}$

7:$\textsf{seed}\leftarrow$ drand(epochNumber)

8:if $\textsf{VRF.Verify}_{\textsf{pk}}(\textsf{seed},y,p)==0$ or
$y>\textsf{target}$ then$\triangleright$ Check the election proof

9: return 0

10:if isPayloadValid(payload)==0 then$\triangleright$ Check the payload

11: return 0

12:if $\textsf{isStorageValid(WinningPost)}==0$ then$\triangleright$ Check the
storage proof

13: return 0

14:for $\mathcal{B}_{i}\in\mathcal{T}$ do$\triangleright$ Check validity of
parent blocks

15: if $\textsf{isValid}(\mathcal{B}_{i})==0$ then

16: return 0

17:return 1

Algorithm 2 $\textsf{isValid}(\mathcal{B})$

##  Appendix B Concentration Inequalities

######  Lemma B.1 (Chernoff).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}=1$ with probability $p_{i}$ and
$X_{i}=0$ with probability $1-p_{i}$, and all $X_{i}$’s are independent. Let
$\mu=\mathbb{E}[X]=\sum_{i=1}^{n}p_{i}$. Then for $0<\delta<1$,
$\mathbb{P}(X>(1+\delta)\mu)<e^{-\Omega(\delta^{2}\mu)}$ and
$\mathbb{P}(X<(1-\delta)\mu)<e^{-\Omega(\delta^{2}\mu)}$.

######  Lemma B.2 (Poisson).

Let $X$ be a Poisson random variable with rate $\mu$. Then for $0<\delta<1$,
$\mathbb{P}(X>(1+\delta)\mu)<e^{-\Omega(\delta^{2}\mu)}$ and
$\mathbb{P}(X<(1-\delta)\mu)<e^{-\Omega(\delta^{2}\mu)}$.

##  Appendix C Proof of Lemma 5.8

######  Proof C.1.

By Lemma 5.6, we know that the statement is true for $\epsilon=1/2$ (and hence
for $\epsilon>1/2$). Now we prove for any $\epsilon>0$ by recursively applying
the bootstrapping procedure in Lemma 5.6. We use induction to show that the
statement is true for all $\epsilon\geq m_{n}$, where
$m_{n}=\frac{1}{n+1},n\geq 1$. As a base step, this is true for $n=1$. Now we
assume it holds for $n\geq 1$ and prove for the step $n+1$.

Divide $(j,j+k]$ into $k^{\frac{1}{n+2}}$ sub-intervals of length
$k^{\frac{n+1}{n+2}}$ (assuming $k^{\frac{1}{n+2}}$ is a integer), so that the
$i$-th sub-interval is:

$\mathcal{J}_{i}:=[j+1+(i-1)k^{\frac{n+1}{n+2}},j+ik^{\frac{n+1}{n+2}}].$

Now look at the first, fourth, seventh, etc sub-intervals, i.e. all the
$i=1\mod 3$ sub-intervals. Introduce the event that in the $\ell$-th ($1\mod
3$) sub-interval ($\mathcal{J}_{3\ell+1}$), an pure adversarial chain that is
rooted at a honest block (or more accurately a tipset including at least one
honest block) mined in that sub-interval ($\mathcal{J}_{3\ell+1}$) or in the
previous ($0\mod 3$) sub-interval ($\mathcal{J}_{3\ell}$) catches up with a
honest block in that sub-interval ($\mathcal{J}_{3\ell+1}$) or in the next
($2\mod 3$) sub-interval ($\mathcal{J}_{3\ell+2}$). Formally,

$C_{\ell}=\bigcap_{s\in\mathcal{J}_{3\ell+1}}\bigcup_{(r,t):r\in\mathcal{J}_{3\ell}\cup\mathcal{J}_{3\ell+1},r\leq
s-2,t\geq
s,t\in\mathcal{J}_{3\ell+1}\cup\mathcal{J}_{3\ell+2}}\hat{B}_{rt}\cup
U_{s}^{c}.$

Note that for distinct $\ell$, the events $C_{\ell}$’s are independent since
$\hat{B}_{rt}$’s in different $C_{\ell}$’s do not have overlap. Also by the
previous induction step, we have

$\displaystyle P(C_{\ell})$ $\displaystyle\leq$ $\displaystyle P(\mbox{no
Nakamoto epoch in $\mathcal{J}_{3\ell+1}$})$ (13) $\displaystyle\leq$
$\displaystyle
A_{m_{n}}\exp(-\alpha_{m_{n}}{(k^{\frac{n+1}{n+2}})}^{1-m_{n}})$
$\displaystyle=$ $\displaystyle
A_{m_{n}}\exp(-\alpha_{m_{n}}k^{\frac{n}{n+2}}).$

Introduce the atypical events:

$\displaystyle B$ $\displaystyle=$
$\displaystyle\bigcup_{(r,t):r\in(j,j+k]\mbox{\leavevmode\nobreak\
or\leavevmode\nobreak\ }t\in(j,j+k],r<t,t-r\geq
k^{\frac{n+1}{n+2}}}\hat{B}_{rt}\;,\text{ and }$ $\displaystyle\tilde{B}$
$\displaystyle=$ $\displaystyle\bigcup_{(r,t):r\leq j,j+k<t}\hat{B}_{rt}\;.$

The events $B$ and $\tilde{B}$ are the events that an adversarial chain
catches up with an honest block far ahead (more than $k^{\frac{n+1}{n+2}}$
epochs). Following the calculations in Lemma 5.6, we have

$\displaystyle P(B)$ $\displaystyle\leq$
$\displaystyle\sum_{(r,t):r\in[j+1,j+k]\mbox{\leavevmode\nobreak\
or\leavevmode\nobreak\ }t\in[j+1,j+k],r<t,t-r\geq
k^{\frac{n+1}{n+2}}}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}$
$\displaystyle\leq$
$\displaystyle\sum_{r=j+1}^{j+k}\big{(}\sum_{t=r+k^{\frac{n+1}{n+2}}}^{\infty}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}\big{)}+\sum_{t=j+1}^{j+k}\big{(}\sum_{r=0}^{t-k^{\frac{n+1}{n+2}}}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}\big{)}$
$\displaystyle\leq$ $\displaystyle
2k\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}k^{\frac{n+1}{n+2}}}}{1-e^{-\alpha_{1}\varepsilon^{2}}},$

and

$\displaystyle P(\tilde{B})$ $\displaystyle\leq$
$\displaystyle\sum_{(r,t):r\leq
j,t>j+k}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}$ $\displaystyle\leq$
$\displaystyle\sum_{r=0}^{j}\big{(}\sum_{t=j+k+1}^{\infty}A_{1}e^{-\alpha_{1}\varepsilon^{2}(t-r)}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{r=0}^{j}\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}(j+k+1-r)}}{1-e^{-\alpha_{1}\varepsilon^{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}(k+1)}}{(1-e^{-\alpha_{1}\varepsilon^{2}})^{2}}.$

Now, we have

$\displaystyle q(j,j+k]$ $\displaystyle\leq$ $\displaystyle P(\mbox{no
Nakamoto epoch in
$\bigcup_{\ell=0}^{k^{\frac{1}{n+2}}/3}\mathcal{J}_{3\ell+1}$})$
$\displaystyle\leq$ $\displaystyle P(\mbox{no isolated successful epoch in
$\bigcup_{\ell=0}^{k^{\frac{1}{n+2}}/3}\mathcal{J}_{3\ell+1}$})+P(B)+P(\tilde{B})+P(\bigcap_{\ell=0}^{k^{\frac{1}{n+2}}/3}C_{\ell})$
$\displaystyle=$ $\displaystyle
e^{-\Omega(k)}+P(B)+P(\tilde{B})+(P(C_{\ell}))^{k^{\frac{1}{n+2}}/3}$
$\displaystyle\leq$ $\displaystyle
e^{-\Omega(k)}+2k\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}k^{\frac{n+1}{n+2}}}}{1-e^{-\alpha_{1}\varepsilon^{2}}}+\frac{A_{1}e^{-\alpha_{1}\varepsilon^{2}(k+1)}}{(1-e^{-\alpha_{1}\varepsilon^{2}})^{2}}+(P(C_{\ell}))^{k^{\frac{1}{n+2}}/3}$
$\displaystyle\leq$ $\displaystyle
A_{m_{n+1}}\exp(-\alpha_{m_{n+1}}k^{\frac{n+1}{n+2}})$ $\displaystyle=$
$\displaystyle A_{m_{n+1}}\exp(-\alpha_{m_{n+1}}k^{1-m_{n+1}})$

for some positive constants $A_{m_{n+1}}$ and $\alpha_{m_{n+1}}$. Equality
(C.1) is due to the independence of $C_{\ell}$’s and inequality (C.1) is due
to (13).

So we know that the statement holds for all $\epsilon\geq
m_{n+1}=\frac{1}{n+2}$. And since $\lim_{n\rightarrow\infty}m_{n}=0$, this
concludes the lemma.