Why can the race between the honest chain and an attacker chain be characterized as a Binomial Random Walk?

Question

I am not familiar with Bitcoin, hope someone can tell me why. Thank you!

Let's consider the following scenario.

The probability of the attacker finds the next block is q and the probability of the honest node finds the next block is p.

Suppose the attacker and the honest node began to find the next block in the meantime (so they spend the same time on finding the PoW solution). If now the attacker finds the next block, since the attacker will not broadcast the block, it won't affect the honest node. The honest node will continue to work on its own PoW. So maybe the probability of the honest node finds the next block is larger than p now (Because the honest node now will spend more time than the attacker on finding the solution of the next block's PoW). Why can Satoshi consider this catch-up process as the gambler game? Is this just a simplified math model? Or is there any procedure I don't know such that once one node finds the next block, all miners will restart their mining work?

Answer 1

Great question.

So the general gist of 'random walk' is contingent on two different things:

1. Probability

2. Logic

It's better to start with the logic part because it will make the probability portion more logical.

Looking at the Logic

From the Bitcoin whitepaper, Satoshi states:

"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 failiure event is the attacker's chain being extended by one block, reducing the gap by -1."

"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."

Breaking This Down

If we were to consider a miner to be an "attacker" then that means that they must have "reversed" a transaction they spent in order to spend it elsewhere (maybe to a wallet they own).

Using this principle, we know that the transaction must be in the past.

So if we're mining at block height 'n', then at best, the attacker must start at n-1 (since they need to reverse a transaction that already was mined in a block).

Here's Where Probability Comes in

As that miner attempts to catch up to the network, they're already at an inherent disadvantage since they're a block behind.

Assuming the network solves for 'n' before the attacker solves 'n-1', then their chances of then solving 'n-1', 'n', then ultimately solving 'n+1' (the new block that the network is working on) decreases substantially.

With this decreased possibility of catching up, the network's probability of extending the lead then increases.

Formula

Not sure if this suffices, but Satoshi included both a formula and C code in the original whitepaper.

The formula is as follows:

The C code is as follows:

#include "math.h"
#include "stdio.h"

double AttackerSuccessProbability(double q, int z)
{
 double p = 1.0 - q;
 double lambda = z * (q / p);
 double sum = 1.0;
 int i; 
 int k;
 for (k = 0; k <= z; k++)
 {
     double poisson = exp(-lambda);
     
     for (i = 1; i <= k; i++)
     poisson *= lambda / i;
     sum -= poisson * (1 - pow(q / p, z - k));
 }
 return sum;
}

int main()
{
double ans = AttackerSuccessProbability(0.1, 1);
printf("'%f'", ans);
}

Hopefully this explanation thus far makes sense (and you find the answer to your question to be adequate)