Fdtxjr

In Satoshi Nakamoto's paper : Bitcoin: A Peer-to-Peer Electronic Cash System, he describes a scenario where an attacker is trying to add falsified transactions to the blockchain.

He writes : "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$.

We can calculate the probability he ever
reaches break-even, or that an attacker ever catches up with the honest chain, as follows" :

Let $p = $ probability an honest node finds the next block

Let $q = $ probability the attacker finds the next block

Let $q_z = $ probability the attacker will ever catch up from $z$ blocks behind

And so $q_z = 1$ if $p leq q$, and $q_z = (q/p)^z$ if $p > q$.

I'm not sure how he arrived at this. Firstly, I have no idea why $q_z = 1$ if $p leq q$.

Secondly, from what I understand from a binomial distribution, the probability of the attacker catching up from $z$ blocks from behind should be equal
to $z choose z$ $q^z p^0 = q^z$. Any insights appreciated.

These are results of simple random walks on $mathbbZ$. If you are more (or equally) likely to move right than move left, then you will with probability $1$ reach arbitrarily high values. Otherwise, the probability you ever reach $zinmathbbN$ units right of where you started is given by $(q/p)^z$, where $q$ is the probability of moving right on a step, and $p$ is the probability of moving left. See this for example for reading on simple random walks (beware that their $p$ and $q$ may be reversed from here though).

I have no idea why $q_z=1$ if $ple q$.

If $p<q$, then this follows simply from the Strong Law of Large Numbers. Let $X_i=+1$ if the hacker wins the $i^th$ block, and $X_i=-1$ if the honest node wins the $i^th$ block. Let $S_n=X_1+X_2+dots+X_n$. The SLLN implies that $S_n/n$ converges to the expected value of $X_i$, which is $q-p>0$. Since $S_n/n$ converges to a positive number, this means $S_n$ gets arbitrarily large, so the hacker will eventually exceed the honest node by any number (including $z$) of blocks.

When $p=q$, you can instead use the Law of the Iterated logarithm to prove that $S_n$ gets arbitrarily large.

from what I understand from a binomial distribution, the probability of the attacker catching up from z blocks from behind should be equal to $binomzz q^zp^0=q^z$.

This is the probability they catch up after exactly $z$ blocks. We want the probability they eventually catch up, after any number of blocks. This is trickier to compute.

For the probability when $z=1$, see Hitting probability of biased random walk on the integer line. The probability of eventually catching up from a deficit of $z$ is the same as the probability of catching up from a deficit of $1$, a total of $z$ times in a row. This lets you extend the $z=1$ case to general $z$.