# Some pointers and notes about Bitcoin security analysis
### Vincenzo Iovino

For my own learning, in 2023 I had written down a set of handwritten notes about Bitcoin security analysis that I will likely publish in the future. Recently I revised it in light of simpler analysis that I had missed by Ling Reng [1] that improves [4] and I was discussing with a colleague this paper, along with some complementary material contained in several good notes [3], and he asked me for some explanations of some some assumptions that are either not intuitive or not backed by proof.
The current note tries to provide pointers and back the mathematics in the aforementioned analysis with some more background and intuitive explanations.
## Mining and Proof of Work
The core of the Bitcoin protocol is a process in which a party invokes a random oracle $H$ with a so called *nonce* $n$ (a bit string of a given length) and some auxiliary data $aux$ (of some given length) and gets an integer $y=H(n,aux)$ of a given length. The process is said to be successful if $y<t$, that is $y$ is less than a given threshold; in this case we say that the party *wins the game* or *solves the puzzle*.
For sake of simplicity we can assume that the computation of $H$ takes 1 step on a given computer of reference. The party can then try many times to invokes $H$ with random nonces until the party wins the game.
First of all, observe that in theory guessing a nonce at random is not the only strategy a party can apply to win the game. However, since $H$ is modelled as a random oracle, there is no other better strategy.
The process of guessing a nonce at random is called *mining* in analogy with the physical process of searching for gold and the party who performs the mining is called *miner*. Note that the nonce that allows a miner to win the game can be seen as a proof for the computational effort spent in solving the puzzle, for this reason this mechanism is called *Proof of Work (PoW)*.
The value $t$ is the *difficulty of the puzzle*.

## Mining as a Poisson point process
Now, several papers and notes in the literature proceed stating that the mining process can be seen as a Poisson point process. We now try to justify this hypothesis.

A discrete random variable $X$ taking non-negative integer values follows the *Poisson distribution* with parameter $\lambda$ if:
$Pr[X=i]=\frac{\lambda^i}{i!}\cdot e^{-\lambda}$ for all $i\ge 0$.
Why is the mining process related to the Poisson distribution?
Actually, the mining process can be modelled via the binomial distribution. Indeed, we could see any attempt to solve the puzzle as a Bernoulli trial with probability $p$, where $p$ is the probability that a miner solves the puzzle with a random nonce in one attempt.
Then, it turns out that if $Y$ is the number of attempts to solve the puzzle with a random nonce among $n$ attempts, then $Y$ can be approximated with a Poisson random variable with parameter $\lambda=np$. We can see this as follows.

$Pr[X=i]=\frac{n!}{(n-i)!i!}p^i\cdot (i-p)^{n-i}=$
$\frac{n!}{(n-i)!i!}(\frac{\lambda}{n})^i\cdot (i-\frac{\lambda}{n})^{n-i}=$
$\frac{n(n-1)\cdots (n-i+1)}{n^i}(\frac{\lambda}{n})^i\cdot (i-\frac{\lambda}{n})^{n-i}/$
For large $n$ and small $p$ (as the case in Bitcoin) we have that $(1-\lambda/n)^n~e^{-\lambda}$, $\frac{n(n-1)\cdots (n-i+1)}{n^i}~1$ and $(1-\lambda/n)^n~1$.
Therefore, we conclude that for large $n$ and small $p$,
$Pr[X=i]~\frac{\lambda^i}{i!}\cdot e^{-\lambda}$, exactly as in the Poisson random variable.

Also, observe that the mean of a Poisson distribution $X$ with parameter $\lambda$ is exactly $\lambda$. This can be seen considering the moment generating $G(t)=E[e^{tX}]$.
Indeed, $G(t)=E[e^{tX}]=$
$\sum_{i=0}^{\infty}e^{tn}\cdot (\frac{\lambda^i}{i!}\cdot e^{-\lambda})=$
$e^{-\lambda}\cdot \sum_{i=0}^{\infty}\frac{(\lambda\cdot e^t)^i}{i!}=$
$e^{-\lambda}\cdot e^{-\lambda\cdot e^t}=$
$=e^{\lambda\cdot (e^t-1)}.$

By differantiating both sides, we have that $G'(t)=e^t\cdot\lambda\cdot e^{\lambda\cdot (e^t-1)}$ and, by the well-known relation between mean and generating function of a random variable, we have that $E[t]=G'(0)=\lambda$.
(Similar arguments also show that the variance of the Poisson distribution with parameter $\lambda$ is $\lambda.$)

We now take a critical step back in our approximation of the mining process as a Poisson random variable.
The subtle point is that time is not discrete but continuous. The miner does not proceed in rounds but mine *continuously*. The right tool here is the stocasthic counting process that, we will see shorly, turn out to be tightly related to the Poisson distribution.
A counting process ${C(t), t\ge 0}$ represents the number of occurrences of an event by time $t$.
For instance, the number $C(t)$ of customers of a pizzeria is a counting process in which an event occurs when a customer enters the pizzeria. A counting process must be non-negative, integer-valued and strictly increasing. Moreover, $C(t)-C(s)$ must equal the the number of occurrences of events in the half-open interval $(s,t]$. A counting process is said to have *stationary increments* if the distribution of the number of events that occur in any interval of time depends only on the length of the time interval, that is $C(s+t)-C(s)$ is i.i.d for all $s$. A counting process is said to have *independent increments* if the number of events that occur in disjoint time intervals are independent.
Observe that stationary increments property is not satisfied for the example of customers entering a pizzeria but seems reasonable for Bitcoin mining.
However, here we see where assumptions represent a useful simplification but are also a limitation. Indeed, the mining process might be affected by periods of outage occuring only in selected periods of time, heat and weather conditions, etc.
On the other hand, independent increments may not be reasonable for the pizzeria example (customers may be lured to enter if they think the pizzeria is popular) but it perfectly matches with the mining process where the probability of solving the puzzle is completely independent from having solved or not solved the puzzle at any point in the past.

A Poisson point process (or just Poisson process) is a particular case of counting process defined as follows.
A counting process ${C(t)},t\ge 0$ is a Poisson process with *rate* $\lambda>0$ if $C(0)=0$, the number of events in any interval of the length $t$ is distributed as a Poisson random variable with parameter $\lambda\cdot t$ and the process satisfies independent increments.
(Observe that we do not need to add stationary increments as it is a direct consequence of the fact that the number of events in any interval follows the Poisson distribution with mean proportional to the length of the interval.)
Now, the papers and notes on the analysis of the Bitcoin mining proceed by simplying assuming that mining is a Poisson process with rate $\lambda$ equal to the total mining rate (we will discuss what this means later).
This is not quite satisfying if not backed by explanations. Recall that when we were trying to model the mining process discretely, we discovered that the Poisson distribution was a meaningul approximation to the binomial distribution that, in the discrete case, directly mimics the mining process.
But why should the number of successful puzzles solved in an interval of length $t$ have a Poisson distribution with parameter $\lambda\cdot t$?

The answer is well-studied.
An alternative definition of a Poisson process with rate $\lambda$ is the following [2]. A counting process ${C(t)},t\ge 0$ is a Poisson process with rate $\lambda, \lambda>0$ if $C(0)=0$, the process has independent and stationary increments and (a) $Pr[C(s)=1]=\lambda\cdot s+\omega(s)$ and (b) $Pr[C(s) \ge 2]=\omega(s).$
Here, with a slight abuse of notation, by $\omega(\cdot)$ we mean the class of functions $f(\cdot)$ such that $f(s)/s$ goes to zero as s tends to zero. So $f(s)=s^2$ is in $\omega(s)$ but $f(s)=s$ is not in $\omega(s)$. By $\lambda\cdot s+\omega(s)$ we mean that we can add to $\lambda\cdot s$ any function in the class $\omega(s)$.

Now, it turns out that the two definitions are actually equivalent. I will provide a simple argument of one direction of the equivalence using the mining analogy.
Consider an interval of time $t$ and divide it into $n$ subintervals. Suppose that any sub-interval is very small so any interval has length $t/n$ and by $(b)$ the probability that there is more than one successful puzzle in one such interval is essentially $0$ (precisely, tends to $0$ as $n$ tends to infinity).
Therefore, if $n$ goes to infinity, with all but negligible probability, $C(t)$ equals the number of sub-intervals in which a successful puzzle is solved.

By stationary and independent increment, it turns out that the probability that a puzzle is solved in an arbitrary sub-interval is $\lambda\cdot (t/n)+\omega(t/n)$.
Therefore, $C(t)$ follows the binomial distribution with parameters $n$ and $p=\lambda\cdot (t/n)+\omega(t/n)$.
When $n$ tends to infinity, the binomial distribution with such parameters will be approximated by a Poisson distribution with parameter
$n\cdot (\lambda\cdot (t/n)+\omega(t/n))=$
$t\cdot\lambda+ n\cdot\omega(t/n)=$
$t\cdot\lambda+ \frac{n\cdot(t/n)\cdot\omega(t/n)}{(t/n)}=$
$=t\cdot\lambda+ t\cdot \frac{\omega(t/n))}{(t/n)}.$
By definition of $\omega(t/n)$ the quantity $\frac{\omega(t/n))}{(t/n)}$ tends to $0$ as $n$ tends to infinity and so when $n$ tends to infinity the binomial distributions with the above parameters will be approximated by a Poisson distribution with parameter $\lambda\cdot t$.

Recall that here $\lambda$ must be regarded as the total mining rate.
What does this mean?
This is the expected rate at which puzzles are solved by *any* miner.
This assumption looks quite weird. Suppose that at time $t_1$ the total mining rate is $\lambda$. If at time $t_2$ new computers start mining, why should not the mining rate increase?
This assumption can be justified by assuming that the total mining rate stays constant during short intervals of time and observing that with many miners working with high computational power a new computer starting mining would not change the total mining rate significantly. Moreover, Bitcoin protocol is subject, by design, to difficulty adjustments that rescale the total mining rate as function of the actual one.
## Mining interarrival times
The main assumption stated in [2] is that the interarrival times in a Poisson process follow independent exponential distributions with the same parameter
$\lambda$ whose cumulative distribution function is $Pr[T \le t] = 1 − e^{−\lambda\cdot t}$.
I now provide an explanation of that.
Firstly, we recall the def. of exponential distributions.
A continuous random variable $X$ follows the *exponential distribution* with parameter $\lambda$ if its dentity fuction is:
$f(x)=\lambda\cdot e^{-\lambda\cdot x}$ if $x\ge 0$ and $0$ otherwise.
In this case its cdf is $Pr[X\le x]=1-e^{-\lambda\cdot x}$ if $x\ge 0$ and $0$ otherwise.
The exponential distributions satisfies the important property of being *memoryless*, that is $Pr[X>s+t|X>t]=Pr[X>s]$ for all $s,t\ge 0$.
What Reng means by interarrival times is the following.
The interarrival times ${T_n}, n\ge 0$ of successfully solved puzzles correspond to the length of the time interval between the $(n-1)$th successful mining event and the $n$th one.
So, for instance, if the first puzzle is solved at time $2$ and the second is solved at time $10$ then $T_0=2$ and $T_1=8$.
The fact that the interarrival times follow the exponential distribution can be determined as follows by induction.
Observe that $T_{1}>t$ occurs iff no event occurs in $[0,t]$ and so $Pr[T_1>t]=Pr[C(t)=0]=e^{-\lambda\cdot t}$.
We have that:
$Pr[T_2>t]=Pr[T_2> t \wedge \cup_{s\in[0,\infty]} T_1=s ]=$.
$Pr[T_2>t]=Pr[T_2> t \wedge \cup_{s\in[0,t]} T_1=s ].$
Now, for any $s\in [0,t]$ it holds that:
$Pr[T_2>t\ |\ T_1=s]=Pr[C(s+t)-C(s)=0]\ |\ T_1=s].$
By independent and stationary events the latter is equal to:
$Pr[C(s+t)-C(s)=0]=e^{-\lambda\cdot t}.$
Therefore, we can conclude that $Pr[T_1>t]=e^{-\lambda\cdot t}.$

## The Reng's main theorem
With this background, the reader can smoothly follow the analysis of [1] whose purpose is to prove the following theorem.

**Theorem.**
Assume the network delay between any pair of honest nodes is upper bounded by $\Delta$, let $\alpha$ be the honest mining rate, $\beta$ the malicious mining rate, $\delta$ be any positive constant, $g = e^{\alpha\cdot \delta}$.
Nakamoto consensus with the
$k$-confirmation rule guarantees safety and liveness except for probability $e^{−\Omega(\Delta^2\cdot g^2\cdot k)}$ if $g^2\cdot α > (1 + \delta)\cdot\beta$.

The interpretation of the result is the following. Consider a $0$ network delay.
Then the condition in the theorem boils down to $\alpha > (1 + \delta)\cdot\beta$, that is the honest mining assumption.
The factor $\alpha$ is the key in the analysis. This is called the *discount factor* and is dependent from the network delay.
Whereas malicious nodes can coordinate their actions with theoretical zero delay thus not losing mining rate, the effect of network delays brings to a measurable loss in mining rate. Higher is the delay, lower would the honest mining rate is, and so the honest mining assumption deteriorate.
Whether this analysis is tight and there exist attacks that meet the above condition.
Also, observe that the error probability depends exponentially on $k$ as it is expected, higher $k$ corresponds to lower error probability.

The proof of the main theorem can be found in [1] and I highly recommend you to study it as it the simplest analysis of Nakamoto consensus up to date.
## Bibliography
[1] Lin Reng. Analysis of Nakamoto Consensus. https://eprint.iacr.org/2019/943.pdf
[2] Robert Gallagher. Poisson processes (Discrete stocasthic processes). MIT Lecture Notes. https://ocw.mit.edu/courses/6-262-discrete-stochastic-processes-spring-2011/3a19ce0e02d0008877351bfa24f3716a_MIT6_262S11_chap02.pdf
[3] David Tse. Scaling blockchains. https://web.stanford.edu/class/archive/ee/ee374/ee374.1206/
[4] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The Bitcoin backbone protocol: Analysis and applications. Crypto 2015.