Bitcoin whitepaper — Calculations explained
11. Calculations
We consider the scenario of an attacker trying to generate an alternate chain faster than the honest chain. Even if this is accomplished, it does not throw the system open to arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Nodes are not going to accept an invalid transaction as payment, and honest nodes will never accept a block containing them. An attacker can only try to change one of his own transactions to take back money he recently spent.
Why can an attacker only try to change one of his own transactions to take back the money he recently spent?
Because even though an attacker can create an alternative longer chain it doesn’t mean it has the power to make the majority of nodes adopt it.
The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The success event is the honest chain being extended by one block, increasing its lead by +1, and the failure event is the attacker’s chain being extended by one block, reducing the gap by -1.
Why a Binomial Random Walk?
Because this problem has only two outcomes, either the attacker wins or fails increasing its chain by one block. It’s like flipping a coin, leading to a graphical representation like this:
The probability of an attacker catching up from a given deficit is analogous to a Gambler’s Ruin problem. Suppose a gambler with unlimited credit starts at a deficit and plays potentially an infinite number of trials to try to reach breakeven. We can calculate the probability he ever reaches breakeven, or that an attacker ever catches up with the honest chain, as follows [8]:
Why is it analogous to a Gambler’s Ruin problem?
The Gambler’s Ruin problem is a competition between two gamblers, where they bet against each other with a limited amount of money.
If gambler A wins a round, then A increases its money and reduces B’s money.
If gambler B wins a round, then B increases its money and reduces A’s money.
The game goes on until one gambler is ruined.
Getting back to the analogy:
If the attacker writes a block, then the attacker increases its chain by +1 and as result reduces the gap between its chain and the honest chain.
If the honest nodes write a block, then the honest chain is increased by +1 and increases the gap between the honest chain and the attacker’s chain by putting it 1 block behind.
Given our assumption that p > q, the probability drops exponentially as the number of blocks the attacker has to catch up with increases. With the odds against him, if he doesn’t make a lucky lunge forward early on, his chances become vanishingly small as he falls further behind.
Why is p > q assumed?
Because P (probability of an honest node to find the next block) should be higher as long as 51% of the nodes in the network are honest.
The recipient waits until the transaction has been added to a block and z blocks have been linked after it. He doesn’t know the exact amount of progress the attacker has made, but assuming the honest blocks took the average expected time per block, the attacker’s potential progress will be a Poisson distribution with expected value:
Why a Poisson distribution?
Because of the assumptions for using a Poisson distribution model are true.
“k is the number of times an event occurs in an interval and k can take values 0, 1, 2, ….
The occurrence of one event does not affect the probability that a second event will occur. That is, events occur independently.
The rate at which events occur is constant. The rate cannot be higher in some intervals and lower in other intervals.
Two events cannot occur at exactly the same instant; instead, at each very small sub-interval exactly one event either occurs or does not occur.
Or
The actual probability distribution is given by a binomial distribution and the number of trials is sufficiently bigger than the number of successes one is asking about (see Related distributions).
If these conditions are true, then k is a Poisson random variable, and the distribution of k is a Poisson distribution.” — Source: Wikipedia.
If the code does not speak for itself to you
That may be because the lines 10 and 11 are a very elegant implementation of the Poisson density. Instead of using recursion for getting factorials k! and pow(lambda, k), it was simplified with iterations (it is faster and consumes less memory).
This code will compute the following if k=5:
Which is equal to:
Conclusion:
We can conclude from section 11 of Bitcoin whitepaper that the more blocks the attacker is behind the honest chain, the less its probability to succeed on its attempt to take back the money he recently spent.
Attacker’s probability is reduced exponentially.
The attacker can try to change one of its own transactions because it can not force the other nodes to accept invalid transactions unless it owns them or hacks them.
It is designed to withdraw incentive of acting dishonestly because while having the odds against the attacker, in the meantime it will be wasting time and electricity.
The attacker may have an inferior probability against an honest node assuming the majority of nodes in the network are honest.
When one block is mined after the one containing your transaction it is called one confirmation. So, this is the reason systems ask for a certain number of confirmations since it will be exponentially harder to revert the transaction, making the receiver securer.
References:
Bitcoin: A Peer-to-Peer Electronic Cash System
Harvard: Lecture 7: Gambler’s Ruin and Random Variables | Statistics 110
