The number of blocks to wait for before confirming transactions

We looked at the probability of an attacker mining without 50% of the hash rate in the last article. Toward the end of the article, we found a way to find the probability of this attacker double-spending. In this article, let’s try to generalize this solution and find how many blocks a recipient should wait for before accepting a transaction.

We have already seen that we can’t exactly know how many blocks an attacker will mine during the waiting time. We can only know the probability of an attacker mining different numbers of blocks. But for a given number of blocks an attacker may mine, we can find the probability of an attacker catching up with the honest chain. We saw an example of it in the previous article. Let’s try to express that in a formula now.

Let k be the number of blocks mined during the interval.

P(X=k; Ÿ).P_{z-k}

This gives the probability of an attacker overtaking an honest chain if a recipient waits for z number of blocks. But this is assuming the attacker mines k number of blocks during the waiting time. Let’s find out the probability of an attack succeeding for any value of k. So, let’s sum the probabilities of an attacker succeeding when they mine 0 to ∞ blocks during the waiting time.

\sum_{k=0}^{\infty} P(X=k; Ÿ).P_{z-k}

\sum_{k=0}^{\infty} \frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.(\frac{q}{p})^{z-k}  \text{ ---(21)}

But when k > z, i.e., when the number of blocks mined while the honest miners mine z number of blocks is greater than z, since the attacker has already overtaken the honest chain, the probability of the attacker catching up with the honest chain is 1. In other words, when k > z, P_z-k=1

So, we can rewrite equation 21 as follows:

\sum_{k=0}^{z}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.{(\frac{q}{p})^{z-k}} +
\sum_{k=z+1}^{\infty}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.1  \text{ ---(22)}

We can simplify this equation further. Practically, we can’t sum up till infinity. So, let’s get rid of it. To do so, let’s use this concept: the probability of something happening is one minus the probability of something not happening.

So, what we are going to do is to find the probability of the attacker not catching up with the honest chain after mining k number of blocks during the waiting time.

1-P_{z-k}

By summing this up, we will get the total probability of the attacker not succeeding in their attack.

\sum_{k=0}^{z}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.(1-{(\frac{q}{p})^{z-k}} )+
\sum_{k=z+1}^{\infty}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.(1-1)

\sum_{k=0}^{z}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.(1-{(\frac{q}{p})^{z-k}} ) \text{ ---(23)}

This gives us the total probability of an attack not succeeding. To find out the total probability of an attack succeeding, we need to deduct equation (23) from 1.

1- [\sum_{k=0}^{z}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.(1-{(\frac{q}{p})^{z-k}} )] \text{ ---(24)}

This way we can practically find the total probability of an attack succeeding. Using this equation, given z, q, and p, we can find the probability of an attack being successful. Satoshi Nakamoto, in their Bitcoin whitepaper, came up with a C program that has a function that takes in q and z as arguments (p is 1 – q) and generates the probability of success for different values of z and q.

However, here z is the number of blocks the attacker is behind the honest chain. To catch up, the attacker needs z + 1 blocks. So, we can rewrite equation (24) as follows [Pinar Ozisik et al.]:

1- [\sum_{k=0}^{z+1}\frac{z(\frac{q}{p})^k . e^{- z(\frac{q}{p})}}{k!}.(1-{(\frac{q}{p})^{z-k+1}} )] \text{ ---(25)}

Then, Satoshi found the combinations of z and q that produce a probability of less than 0.001. Since this is a very low probability, it is considered safe. For example, if an attacker has a probability of 0.1 of mining (q = 0.1), then z should be 5. That is a recipient needs to wait for at least 5 blocks before accepting the transaction to prevent the money they received becoming invalid due to a double-spend attack. The challenge, however, is to find q since it is difficult to know which nodes are trying to double-spend.

The graph below gives the different combinations of z and q that produce probabilities of 0.001, 0.01, 0.1, and 0.5.

The takeaway is that if an attacker possesses more than 50% of the hash rate, then double-spending is easy. If the attacker’s hash rate is less than 50%, then the recipients must wait for a few blocks before accepting the transaction. The number of blocks the recipients have to wait before accepting the transactions goes up almost exponentially with the increase in the hash rate of the attacker.

This concludes our series of articles on how blockchains function. As we have seen, blockchain allows us to transact money using a decentralized system, solving the age-old problems associated with decentralized financial systems. Blockchain establishes trust without a centralized authority between transacting parties, which is why the transactions are called trustless transactions. Blockchain also helps establish consensus among nodes using the Proof-of-Work algorithm. The use of blockchains is now becoming increasingly felt outside financial systems as well, as this technology is now being explored to create everything from decentralized applications to the Internet of Things.