In the previous article, we talked about forks in blockchain. So far in this series, we have talked about double spending and how blockchain avoids it. However, we also briefly touched upon the idea of the 51% attack and how it actually allows double spending to happen. In this article, we will start to look at the theoretical basis of the 51% attack.
We have already seen that to double spend, an attacker must create a branch longer than the branch that contains their transaction. We also saw that recipients usually wait for six more blocks before they accept the transaction in order to protect themselves against double-spending. Can an attacker create a longer branch and perform a double spend? Does waiting for a few more blocks offer complete protection against double spending? What does a 51% attack entail and how does it allow an attacker to double spend?
Probability of mining the next block
To answer these questions, we need some mathematics. For starters, let’s try to find out how likely a miner is to mine a block. To mine the next block, every miner would hash the block they have created and see if it is below the target hash. The number of hashes a miner can produce per second is called the hash rate.
Now, let’s say there are only two miners. Each one can produce only one hash per second. So, the probability of each one of them mining the next block is 0.5. Now, let’s say one of the miners improves their mining rig and can now produce two hashes per second. Now, this miner has a 2/3 probability of mining the next block.
To understand the intuition behind this, let’s look at this example. If two people keep rolling a dice each every second, then they both have an equal probability of getting the number 6 first. But if one person is going to roll two dice every second, then they have a higher chance of getting the number 6 first. Since there are three dice involved and each has an equal probability of producing the number 6 first, the probability of one of the dice producing 6 first is 1/3. Now, since one person has two dice, the probability of that person producing the number 6 first becomes 2/3.
Thus, we can define the probability of a person producing the right number first as:
the number of dice the person can roll per unit time / the total number of dice rolled per unit time.
Similarly, we can define the probability of a miner mining the next block as:
the hash rate of the miner / the total hash rate of the blockchain network
Probability of double spending
To be able to build a longer branch than the legitimate one, an attacker has to catch up with the number of blocks the honest nodes mine and then mine one extra to overtake it. So, our goal is to find an attacker’s probability of mining one block more than the honest nodes. First, let’s define the probability of the attacker mining the next block as q. The probability of the honest nodes mining the next block is p. And p + q = 1. Let’s now see how we can find the probability of double spending based on these factors.
To that end, let’s look at this as an arms race. As an attacker tries to mine a block, the honest nodes try to do the same. We can also look at it in another way. The attacker will initially lag behind the honest chain by one block. If the attacker manages to mine a block, then the difference between the two will be zero. Instead, if the honest nodes manage to mine a block, the difference will become two. In other words, when the attacker mines a block, they move a step closer to the goal. When the honest nodes mine a block, the attacker moves a step back from the goal.
Binomial Random Walk
This is known as a Binomial Random Walk. This is a mathematical process whereby you move forward if you win and backward if you lose. The goal of our Binomial Random Walk here is to eventually close down the initial gap between the two chains. Let’s assume that the initial gap between the two chains is z blocks. So, the goal of the random walk is to get to z + 1.
This is very similar to the gambler’s ruin problem. By solving the gambler’s ruin problem, we will be able to find an answer to our question. Before we try to solve the gambler’s ruin problem, let’s try to see what it is in the next article.