1. Introduction
In this post we analyze two sources of divergence on the blockchain caused respectively by a natural fork and a malicious fork. The revolution that has been brought about by Bitcoin’s blockchain is a direct result of its open nature. Indeed, anyone can be part of it, suggest changes to it, mine new blocks in it, or simply conduct routine validations on it. It is in many respects, the epitome of decentralization and censorship-resistance. Its appealing nature is in large part rooted in its rich interdisciplinary foundation that spans across philosophy, mathematics and economics.
But beyond the elegance of its theoretical underpinning, the blockchain’s seamless implementation rests on an inherent agreement between its different participants. Without agreement, this harmonious apparatus would likely decay into chaos. The rather flawless operation of the system is the result of a particular consensus protocol known as Proof of Work (or PoW for short).
The consensus is meant to be amongst all of the miners on the network. It stipulates that any miner always extend the chain of blocks with the highest amount of cumulative work. In this context, work is a measure of the expected computational effort that a miner exerts in order to solve a given cryptographic challenge. In essence, the challenge consists in finding a value that makes the computation emit an output with a mandatory minimum number of leading 0’s. The work associated with mining a given block corresponds to the value
where
is dynamically adjusted to ensure that the network’s average block rate remains constant at
0.00167 blocks / second (i.e., 1 block per 10 minutes). We discuss PoW as well as other consensus protocols in more details in another post.
In an ideal setting where all miners are honest (i.e., abide by the PoW consensus protocol) and where blocks are propagated instantaneously on the network, all the nodes will always have a unified view of the blockchain — barring the extremely unlikely scenario of two distinct miners generating two valid blocks at the exact same time). However, imperfections do exist:
- Imperfection #1: The network incurs an information propagation delay. As a result, every new block takes a positive amount of time to reach all the other nodes on the network.
- Imperfection #2: There exists a subset of dishonest miners that decide to disregard the PoW consensus protocol. As a result, such miners can fork the blokchain and start mining on top of a parallel chain different than the one with the highest amount of cumulative work.
In the first case, miners are bound to momentarily experience diverging views of the blockchain. Even if all miners were honest, a network propagation delay would still cause natural forks to form on the blockchain. This is not desirable because one of the most important tenets of a well-functioning ledger consists in ensuring a unified view of the state of the system at any point in time.
We will show in section 2 that the probability of a natural fork occuring at some point in time on a system incurring an information propagation delay is equal to 1. However, we prove that the probability of sustaining a natural fork over a certain time interval is upper-bounded by a quantity that decays exponentially with the length of the interval. Consequently, any natural fork will collapse within finite time with high likelihood. A blockchain subject to the PoW consensus protocol is hence inclined to rapidly settle any natural fork that emerges.
In the second case, dishonest miners could stage an attack and maliciously attempt to redirect the blockchain to another chain of their liking and that suits their interest. The likelihood of success of such an attack (also known as a 51% attack) depends on the hashing power of the dishonest miner or pool of miners. We will discuss this case in section 3.
2. Probability of sustaining a natural fork when all miners are honest
We start by defining the following network parameters:
- Let
denote the total number of miners on the network. We let
denote the
miner,
- Let
denote
‘s hashing power,
And let
denote the network’s total hashing power.
- Let
denote the network’s block rate in units of blocks per second. Moreover, let
denote
‘s specific block rate,
. Hence
- Let
denote the average time in seconds it takes to propagate a block from
to
and vice versa (assuming symmetry). We define the network’s average propagation delay to be
We also define the network’s average propagation unit to be
- The probability that
generates
blocks (
) within an interval of
seconds follows a Poisson distribution with mean equal to
blocks. As a result,
we have:
generates
blocks within
seconds
We also define the following four events:
“At least one fork of the blockchain is formed at some point in time
“. The time origin
can be chosen arbitrarily.
“A fork is formed at block #
of the blockchain. All miners shared a unified view of the blockchain right before #
‘s addition.”
“A fork that was created at time
is sustained (i.e., does not collapse) for a minimum duration of
seconds right after its formation.”
“A double-spend transaction coexists with the legitimate transaction,
seconds after the latter got added to a certain block” (We will discuss this event in more details later in this section).
Note that in what follows, we make the following two assumptions:
- The PoW consensus protocol consists in extending the chain of blocks that has the highest amount of accumulated work. Theoretically, this is not equivalent to the longest chain (i.e., the chain with the highest number of blocks). However, for all practical matters, we assume that they are equivalent going forward.
- The block propagation delay
as defined earlier might be a large number since there might be nodes on the network that take a large amount of time on average to receive a given block. In general, block propagation statistics are described in terms of percentiles tracking how long it takes to propagate a block to a certain fraction of the network [2]. For all practical matters, we assume that
corresponds to the average time taken to propagate a block to 99% of the network.
Our objective is four-fold:
- We first calculate the probability
of a natural fork occuring at some point in time (assuming all miners are honest) and show it is equal to 1.
- Second, we derive a non-trivial upper bound on
for any given block
- Third, we derive a non-trivial upper bound on
decaying exponentially in
- Finally, we derive a non-trivial upper bound on
by making use of the results of the preceding two points.
Objective #1: Natural forks on the blockchain happen with probability 1:
- Choose
such that
We can write:
where
“No fork is formed on the blockchain at any time in the interval
“
let
“No fork is formed on the blockchain at any time in the interval
“. We can then write:
- Let
“None of the
miners generate any block in the interval
“, and let
“One and only one miner out of
generates at least 1 block in the interval
“. We claim that:
for all
To see why, note that if both
and
were not true, then there would exist at least two distinct miners that generate at least 1 block each in the interval
But since
it must be that at least two parallel blocks (one from each miner) coexist, hence forming a fork. Indeed, the choice of
guarantees that none of the two blocks will have sufficient time to propagate to the other node. We conclude that
is a necessary condition for
to hold. Observing that
and
are disjoint, we get:
- We can calculate
This quantity is independent of
and so
- Similarly,
This is also independent of
and so
- Putting it altogether, we get:
let
denote the event “
and only
miners out of
generate at least 1 block each in an interval of
seconds”. One can easily see that for a finite value of
As a result, we have:
- Consequently, we get:
And since
we conclude that
Objective #2: A non-trivial upper bound on the probability of a natural fork occuring at an arbitrary block:
Suppose that all miners share a unified view of the blockchain. At time one of the miners adds block #
to the blockchain. Miners that still haven’t received block #
(which for all practical matters could take up to
could generate their own block and start a fork at #
We are interested in computing the probability that such an event occurs, i.e.
We define the following:
“No fork ever gets formed at block #
, knowing that all miners shared a unified view of the blockchain right before #
‘s addition by some miner.”
“None of the miners that still haven’t received block #
by time
, generate any block in
“
- Let
be the total number of miners out of a total of
miners, that still haven’t seen block #
by time
Let these miners be indexed as
and let
denote the block rate of miner
By letting we can write:
And so letting we can write:
Letting be the ratio of miners that still haven’t received block #
by time
we get:
Note that if all miners share the same block rate , then
As a result, we would get
(note the equality in this case). For small
this value can be approximated by
as found in [1]. Below is a representation of a block propagation delay as observed on the
of August 2018 [2]. In order to compute
we make the assumption that the share of miners that still haven’t received the block by a certain time is the same as the corresponding share of generic nodes.
We find that Using
blocks/sec, we get
Objective #3: Natural forks collapse with high likelihood in a finite amount of time:
In what follows, we derive a non-trivial upper bound on To do so, we will first find a lower bound on the probability of occurrence of its complement
“A fork that was created at time
collapses at some point in time in the interval
“. An adequate lower bound on
would be given by
where
is an event whose occurence is a sufficient condition for
to hold true. Our objective becomes one of finding an appropriate
and calculating a lower bound on
In the tree below, we depict the different scenarios that lead to a natural fork formation, starting with a shared view of the blockchain. and
are time instances corresponding to block formations by miners
and
respectively. Recall that
denotes the average block propagation time between
and
Scenarios that lead to a fork formation are one of two types: those that lead to parallel chains of equal length (i.e., Type 1) and those that lead to chains of different lengths (i.e., Type 2):
Forks of type 1: Before time all miners share the same view of the blockchain. At
(for some
generates block #
At
(for some
generates the following block #
such that
If we wait for
seconds and no miner generates any block in interval
then at time
there will be more than one view of the blockchain, all of which have the same length. If for the following
seconds (
), one and only one
generates at least one block #
, and then for the following
seconds no miner generates any block, then by time
all forks would collapse. This is depicted in the figure below:
Forks of type 2: Before time all miners share the same view of the blockchain. At
(for some
generates block #
At
mines the next block #
At
(for some
generates the following block #
Two views of the blockchain will coexist at
with one being a longer chain than the other. If we wait for
seconds, and no miner generates any block in interval
then by
all forks would collapse. This is depicted in the figure below:
One consequence is that given a fork that was formed at time , if we ensure that for the next
seconds no miner generates any blocks, and that for the subsequent
seconds one and only one miner generates at least 1 block, and finally for the subsequent
seconds no miner generates any block, then the fork would collapse in the interval
This construction ensures a sufficient condition for a fork to collapse within a specific time interval. In what follows, we formalize our approach:
- Let
and let
. We refer to
as the interval design parameter expressed in units of seconds. We define the following events:
“No miner out of
generates any block in the time interval
“
“One and only one miner out of
generates at least 1 block in the time interval
“
“No miner out of
generates any block in interval
“
“Any fork that could have existed at time
collapses at some time in the interval
“
“At least one fork that existed at time
is sustained throughout
“
- The previous logic allows us to conclude that if
and
are all satisifed, then
will hold true
and so will
We conclude that the event
is a sufficient condition for the occurence of
and
(
We get:
does not create any block in time interval
creates at least one block in time interval
does not create any block in time interval
does not create any block in
Recognizing that all the events appearing under the union symbol above are disjoint, and that all the intersections are taken over independent events, we get:
- Now note that
And since the exponential function is convex, we can invoke Jensen’s inequality to conclude that
we have:
- As a result,
- And so
- Let
In order to sustain a fork over a minimum duration of
seconds after its formation at time
we must sustain it over each
This implies that:
As a result,
we can write:
And in particular,
- Finally, for a given time interval of
seconds, we can write:
Where
denotes the floor function.
The objective function of the previous optimization problem is not smooth due to the presence of the floor function. As a result, finding a closed form analytical solution might prove difficult. However, numerical methods could be employed to find the optimal upper bound. Observe that this upper bound decays exponentialy with and eventually converges to 0 when
. We use the value of
that corresponds to the average block propagation delay to reach 99% of the network observed over a period of time extending from May
2018 to August
2018 [2].
Below, we include various graphs of this upper bound for different values of and for fixed
and
These graphs show that for the pre-defined values of and
the probability that a natural fork survives
minutes (which on average corresponds to the addition of 2 new blocks on the blockchain) is upper-bounded by 0.25 (or almost 1 in 4 cases). When
minutes (i.e., the duration required to add an average of six new blocks on the blockchain), the upper bound goes down to 0.015 (or almost 1 in 67 cases). And when
minutes, it goes down to 0.00022 (or almost 1 in 4500 cases).
In the graphs above, we assumed a fixed block rate of 1 block per 10 minutes. This is the value used by Bitcoin. For what it is worth, one could further optimize the upper bound over positive values of
For fixed
and
the tightest upper bound becomes:
In order to solve it, we first find the optimal value of that solves the following optimization problem:
Note that since the exponent appearing in the objective function does not depend on and since the base is a positive quantity, we can solve the following equivalent optimization problem whose objective function is now smooth:
Note that when or when
the objective function tends to 1. The objective function turns out to be convex in
and we can solve for
by setting its first derivative with respect to
equal to 0. Doing so, yields:
The tightest upper bound over all positive values of and
then satisfies:
For each of the following graph, we let and specify a particular value for
For each value of
we then calculate the corresponding
as outlined above, and plot the graph of
Objective #4: A non-trivial upper bound on the probability of a double-spend transaction coexisting with the legitimate transaction, seconds after the legitimate transaction is added to the blockchain:
The derivations above demonstrate that even if all miners were honest, forks are bound to happen, although they collapse with high likelihood after a finite time of their formation. The existence of natural forks could encourage dishonest customers to engage in double-spending behavior.
To see how, consider a scenario in which a customer spends some Satoshis to purchase a physical product. Let the transaction be denoted Suppose that at
the vendor sees his transaction
included in block #
for the first time on the blockchain. Suppose that the customer issues another transaction
(before or after
) destined to himself and that uses the same UTXOs as
There is a chance that both
and
be selected by two different miners and included in two separate coexisting blocks. We define the following double-spending event:
“
and
coexist on the bockchain,
seconds after
‘s addition to the blockchain in block
“
Note that if no fork is formed at or before block then
will not constitute a double-spending risk since
would have propagated to all nodes. As a result, a necessary condition for a double-spending risk to exist consists of the union of the following events:
“A fork is formed at block #
of the blockchain and
is added to this fork at some point in time. All miners shared a unified view of the blockchain right before #
‘s addition”
“A fork was formed at some block
preceding
and
is added to this fork at some point in time. All miners shared a unified view of the blockchain right before #
‘s addition”
We would like to calculate a non-trivial upper bound on We can write:
-
We saw earlier that
Moreover,
And so,
Assuming that
we get
- Let
be a non-negative integer and let
be an arbitrary interval of time. Without loss of generality, assume block
was added at
Define
“Block #
preceding #
was created in interval
a fork was formed at #
and
is added to this fork at some point in time. All miners shared a unified view of the blockchain right before #
‘s addition”. We can write:
Note that
-
-
At least one block added in the interval
-
We then have:
at least one block is added in interval
As a result,
Assuming
we get
In the limit when
becomes infinitesimally small and tends to
the quantity
tends to
We can then write
Similar to
, we have
-
We then conclude that
The graphs below depict the upper bound on the probability that a double spend transaction coexists with
on the blockchain
seconds after
is added to block #
for various values of
and
The above graphs show that if before handing over the goods, the vendor waits for an additional minutes after he sees
added to block #
on the blockchain (which at a block rate of
would roughly correspond to two additional blocks on top of #
), then for
and all miners being honest and sharing the same hash rate, the probability of a double-spend attempt coexisting with
at time
is upper-bounded by 0.00149.
That means that there is at most a probability of 0.00149 that is still part of a parallel fork. By virtue of being sustained, it could still become part of the longest chain. If this happens,
gets thrown back into the mempool and
gets validated instead. On the other hand, waiting for an an additional
minutes (i.e., roughly 5 additional blocks on top of #
), would bring down this probability to 0.000183.
One could also optimize the upper bound not only over but also over
Below is a plot showing the optimal value for the case
minutes. In this case, the tightest upper bound is 1.33
which is achieved for
blocks / sec and
sec.
A small note on the value of To the extent of our knowledge, the choice of
used in Bitcoin is not the result of a pure mathematical optimization exercise. The larger the value of
the higher the probability of a natural fork occuring. Natural forks are not desirable as they possibly pave the way to double-spending attempts. However, this is not the only metric that counts.
Another important consideration has to do with the storage capacity requirement and the rate of growth of such capacity that needs to be maintained at the level of each full node on the network. A higher means faster transaction processing but also faster growth of ever-increasing storage requirement. It is most likely that only a handful of nodes will be able to afford such storage, subsequently leading to a centralization scenario. This stands in sharp contrast with Bitcoin’s fundamental philosophy. As a result of this tradeoff, Satoshi’s choice of
is probably a good compromise.
3. Probability that dishonest miner(s) succeed in creating a dominant fork: 51% attack
In this section we look at the second type of imperfections alluded to earlier. More specifically, we turn to the possibility that a subset of dishonest miner(s) decide to disregard the PoW consensus protocol and mine on top of a parallel chain different than the one with the highest amount of cumulative work.
This type of behavior has been introduced and analyzed in section 11 of Nakamoto’s seminal paper [3]. The analysis demonstrates that dishonnest miner(s) could possibly generate a parallel chain that overtakes the original honest chain. As a consequence, malicious miner(s) can potentially engage in double spending behavior.
Such a scenario is commonly referred to as a 51% attack, although malicious miner(s) do not necessarily need 51% of the total hashing power of the network to launch a double spending attack. A control of 51% or more of the total hashing power will however guarantee that the attack will be successful. On the other hand, control of less than 51% is not associated with a deterministic state of success, but rather a probabilistic one. The analysis in [3] quantifies the probability of success as a function of said control. In this section, we simply clarify the mathematical foundation of this analysis.
Building on the notation used in section 2, we further define the following quantities:
- Let
be the subset of malicious miner(s) staging a 51% attack.
- Let
denote the fraction of the total hashing power controlled by the malicious miner(s). Note that in [3], this quantity is denoted by
(in our notation,
refers to the total number of miners).
- Let
denote the fraction of the total hashing power controlled by the honest miners.
- Let
correspond to the legitimate transaction against which
will stage a 51% attack, and let
be the block to which
was initially added.
- Let
denote the interval of time extending from the moment
was added to
to the time the
subsequent block following
got added to the honest chain.
We also define the following two events:
“The subset of malicious miner(s) with a fraction
of the network’s total hashing power conduct a successful 51% attack on
and
has been previously validated by the addition of
blocks on top of
on the honest chain.”
“The subset of malicious miner(s) with a fraction
of the network’s total hashing power created and added
blocks to the parallel chain in interval
.”
We can write:
Calculating : Given a network block rate of
blocks/sec, the rate associated with honest miners is
blocks/sec, and that associated with malicious miner(s) is
blocks/sec. As a result,
sec. In this interval, the subset of malicious miner(s) generate an average of
blocks. As a result, we can model malicious miner(s) block generation over this inteval as a Poisson process with mean
blocks. We get:
Calculating : Knowing that in interval
the malicious miner(s) generated
blocks on the parallel chain, we need to calculate the probability that the malicious miner(s) catch-up to the honest chain and generate a parallel chain that is at least as long (note that technically speaking, the parallel chain should be one block longer than the honest chain for the attack to be successful, but Nakamoto’s analysis considers the case of equal length instead). Clearly, if
the probability is 1. When
we can model the process as a binomial random walk whereby given that the malicious miner(s)’s parallel chain is
blocks shorter than the honest chain:
- Every time the malicious miner(s) generate a new block, the gap gets reduced by 1.
- Every time the honest miners generate a new block, the gap gets increased by 1.
- Otherwise, the gap remains the same.
This problem turns out ot be a slight variant of the Gambler’s Ruin Problem that we introduce next.
- The Gambler’s Ruin Problem:
- The setting consists of a gambler who initially has
units of currency (UOC for short).
- The gambler engages in a series of bets whereby every time she wins she gets UOC
and every time she loses, she gives UOC
.
- Suppose that the gambler has a probability
of winning each bet and a probability
of losing. All bets are mutually independent.
- The objective is for the gambler to reach a fortune of UOC
before losing all her capital. As a result, the process will stop if either the gambler accumulates UOC
or if she sees her capital reduced to 0.
In what follows, we calculate the probability that the gambler wins knowing that she started the game with UOC
This is the probability that she reaches a fortune of UOC
at some point in time knowing that she started off with UOC
We denote it by
A similar derivation can be found in [5] and [4]. Note that in this version of the game, the gambler cannot play if she does not have a positive amount of capital to start the betting process with. This stands in contrast to the aforementioned situation where malicious miner(s) start off with a block deficit. Later on, we will account for this variation.
We start by defining the following events:
{
“The gambler wins”
{
“The gambler wins the first bet in the series”
{
“The gambler looses the first bet in the series”
And let
be a random variable denoting the amount of capital held by the gambler at the beginning of the game.
We can write:
In other terms, we have:
since
Recognizing a telescoping series structure, we write:
And so,
if
if
Noting that
and applying the above when
we get
if
if
Which then allows us to conclude that
if
if
Putting it altogether, we get
if
if
- The setting consists of a gambler who initially has
- Adapting the Gambler’s Ruin Problem to the case of a 51% attack: In the context of a 51% attack, and for
is the probability that the subset of malicious miner(s) catch up to the honest chain when the malicious miner(s)’ parallel chain is
blocks behind. In other terms, the malicious miner(s) have a deficit of
blocks at the beginning of the process and we are interested in calculating the probability that they catch-up at some point in time.
Note that under this setting, the block deficit may widen without having any lower-bound constraint.In the setting of the Gambler’s Ruin Problem, the gambler cannot play when she is in a deficit and will have to stop as soon as her betting capital reaches 0. As such, the problem must be modified to account for a scenario where the gambler could borrow unlimited credit if need be, to continue playing the game.
An equivalent formulation consists of a gambler having an infinite amount of capital to start with. Formally, we assume the same setting as the original problem. The gambler however, has a deficit of UOC
. She then borrows UOC
and starts the game with the objective of reaching UOC
where
. If she wins, she returns UOC
to her creditor and keeps UOC
so as to break-even. In case she loses, she does not return anything to her creditor.
Clearly, the above setting is unrealistic due to the dearth of extremely benevolent creditors. However, when we are dealing with a deficit of a block nature rather than a monetary one, this setting becomes acceptable. We then let
and compute the corresponding probability of success. In our block deficit case,
blocks.
We get
if
if
Next, note that if
then
And so
And if
then
And so
Finally, if
then
As a result,
if
and
if
If malicious miner(s) are not incurring a block deficit, i.e.,
then
Otherwise, if
then noting that the probability of malicious miner(s) finding the next block is equal to
and the one corresponding to the honest miners is equal to
we get:
if
and
if
The calculations above allow us to conclude that:
if
and if
In the graphs below we plot the probability of a successful 51% attack as a function of the fraction of the total hashing power controlled by the subset of malicious miner(s). We do so for different values of the block validation height
For example, assuming that malicious miner(s) controlled 15% of the total hashing power of the network (i.e., ), then a block validation height of 6 blocks (i.e.,
) is associated with a probability of a successful attack of 0.268%.
4. References
[1] Christian Decker and Roger Wattenhofer. Information propagation in the bitcoin network, 2013.
[2] DSN. Block propagation delay history.
[3] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. White Paper, 2008.
[4] A. Pinar Ozisik and Brian Neil Levine. An explanation of nakamoto’s analysis of double-spend attacks, online, 2017.
[5] Karl Sigman. Gambler’s ruin problem, online, 2016.
Tags: 51%, attack, blockchain, double spend, fork, miner
No comments
Comments feed for this article
Trackback link: https://delfr.com/blockchain-fork-analysis/trackback/