51% attack: Probability of double spending
We tried to understand the 51% attack through the gambler’s ruin problem and the probability of a gambler winning T dollars in the last article. Let’s look at how we can apply the equation we derived for the gambler’s ruin problem to find the probability of double spending in this article.
In the gambler’s ruin problem, a gambler starts with i dollars and tries to reach T dollars. If they run out of money, they lose. In blockchain, an attacker tries to catch up with an honest chain by mining blocks. Mining, as is the case with betting, depends a lot on luck.
As we saw earlier, when the attacker mines a block, they win and get a step closer to the target. If an honest node mines a block, the attacker loses and moves a step backward. This makes the gambler’s ruin problem comparable to the problem of an attacker catching up with an honest chain.
However, there is a caveat. In the gambler’s ruin problem, the gambler loses when they lose all their money. In contrast, in blockchain, there is no way an attacker can lose. The only time an attacker would stop their attempt is once they overtake the honest chain. This is provided that they don’t mind paying a huge electricity bill.
This is similar to a gambler having an infinite amount of money so that they never run out of money. So, to apply the gambler’s ruin problem to the blockchain problem, we need to consider the i in the equation we derived in the previous article as being infinity.
We know:
T=i+z
Let i be infinity.
T=\infty+z
z is the difference between the money the gambler has now and the money they have to make. With regard to blockchain, z is the number of blocks the attacker has to mine to catch up with the honest chain. So, we can rewrite the equation from the previous article as follows:
P_\infty =
\begin{cases}
\frac{1-(\frac{p}{q})^\infty}{1-(\frac{p}{q})^{\infty+z}} & \text{if $p$ != $q$}\\
\frac{\infty}{\infty+z} & \text{if $p=q=0.5$}
\end{cases}\text{ ---(16)}Let’s first consider P∞ when p = q = 0.5:
Any number added to infinity produces infinity. So, dividing infinity by infinity gives us 1.
When p != q, we can have two scenarios. If q > p, (p/q) will give us a value less than 1. When that value is raised to the power of infinity, we get a value almost equal to 0. So,
\frac{1-0}{1-0} = 1This means, if q > p, then the probability of the attacker catching up with z number of blocks is 1.
To find the probability when p > q, we need to simplify equation (16) further. To do that, let’s take (p/q)∞ as the common factor from both the denominator and the numerator.
\frac{1-(\frac{p}{q})^\infty}{ 1-(\frac{p}{q})^{\infty + z}}\frac{(\frac{p}{q})^\infty((\frac{p}{q})^{-\infty}-1)}{(\frac{p}{q})^\infty((\frac{p}{q})^{-\infty}- (\frac{p}{q})^z)}\frac{(\frac{p}{q})^{-\infty}-1}{(\frac{p}{q})^{-\infty}- (\frac{p}{q})^z}\frac{(\frac{q}{p})^\infty-1}{(\frac{q}{p})^\infty- (\frac{p}{q})^z} \text{ ---(17)}When p > q,
(\frac{q}{p})^\infty=0So, plugging this into equation (17), we get,
\frac{0-1}{0- (\frac{p}{q})^z}\frac{-1}{- (\frac{p}{q})^z}\frac{1}{(\frac{p}{q})^z}(\frac{p}{q})^{-z}(\frac{q}{p})^zThus, when p > q, we get,
P_\infty = (\frac{q}{p})^zWe can summarize the values of P∞ as follows:
P_\infty =
\begin{cases}
1 & \text{if $q >= p$}\\
(\frac{q}{p})^z & \text{if $q < p$}
\end{cases}
The notation P∞ may have made sense when we wanted to find the probability of the gambler getting to T with i dollars but doesn’t make sense when we want to find the probability of an attacker catching up from z number of blocks behind with an infinite amount of resources. So, let’s use Pz to denote this probability of an attacker catching up from z blocks behind. Thus, the resources the attacker has do not matter here.
P_z =
\begin{cases}
1 & \text{if $q >= p$}\\
(\frac{q}{p})^z & \text{if $q < p$}
\end{cases} \text{ ---(18)}The intuition that we get from the above equation is that if an attacker has 50 or more percent of the hash rate of a blockchain network, then the probability of them catching up with the honest chain and overtaking it is 1. To put this in other words, an attacker can double spend, if their hash rate is more than or equal to 50% of the total hash rate of the network. This is known as the 51% attack.
Nonetheless, keep in my mind that the 51% attack doesn’t allow an attacker to transfer money from another individual’s account or create new coins out of nowhere. All that an attacker can do is to double-spend or invalidate transactions that are already a part of the blockchain.
From equation (18), we know that the probability of an attacker catching up with the honest chain from z blocks behind when p > q is (q/p)z. When z increases, the probability goes down exponentially. So, how many blocks should a recipient wait for before accepting the transaction?
If we say the answer is 1 and assume an attacker has a probability of 0.3 of mining the next block, then:
(\frac{0.3}{0.7})^1=0.430.43 is a fairly high probability. We may actually want it to be far less. Of course, we can plot a graph as a function of z and find out the appropriate value of z. However, there is a caveat. An attacker isn’t going to wait till z blocks are mined by the honest nodes to start mining blocks with the hope of overtaking the honest chain.
In fact, an attacker will start working on their chain as soon as their transaction gets validated. So, by the time z blocks are mined by the honest nodes, the attacker may have already mined a few blocks themself. If we assume the attacker mined x blocks while the honest nodes mined z blocks, then the attacker will have to produce only z – x blocks more once the recipient accepts the transaction.
So, how can we find out how many blocks an attacker may produce while honest nodes produce z number of blocks? Let’s find that out in the next article.
Leave a Reply