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 censorshipresistance. 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 wellfunctioning 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 upperbounded 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 doublespend 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 fourfold:
 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 nontrivial upper bound on for any given block
 Third, we derive a nontrivial upper bound on decaying exponentially in
 Finally, we derive a nontrivial 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 nontrivial 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 nontrivial 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 predefined 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 upperbounded 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 nontrivial upper bound on the probability of a doublespend 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 doublespending behavior.
To see how, consider a scenario in which a customer uses BTC to purchase a physical product. Let the corresponding transaction be denoted Suppose that at the vendor sees his transaction included in a certain 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 be included in two separate coexisting blocks. We define the following doublespending 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 doublespending risk since would have propagated to all nodes. As a result, a necessary condition for a doublespending 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 nontrivial upper bound on We can write:

We have seen earlier that
And if all miners have the same block rate, then
and
Moreover,
Assuming that we get
 Let be a nonnegative integer and let be an arbitrary interval of time. 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:
Next, note that
at least one block gets generated 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
And if all miners have the same block rate, then
and
We can 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
These 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 doublespend attempt coexisting with at time is upperbounded 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 doublespending 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 everincreasing 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) catchup 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
 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 catchup at some point in time.
Note that under this setting, the block deficit may widen without having any lowerbound 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 breakeven. 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 peertopeer electronic cash system. White Paper, 2008.
[4] A. Pinar Ozisik and Brian Neil Levine. An explanation of nakamoto’s analysis of doublespend 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/wptrackback.php?p=1378