2

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.

David G. Stork
  • 29,774
IntegrateThis
  • 3,778
  • These are results of simple random walks on $\mathbb{Z}$. If you are more (or equally) likely to move right than move left, (with probability $1$) you will reach arbitrarily high values. Otherwise, the probability you ever reach $z\in\mathbb{N}$ 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). – Minus One-Twelfth Mar 22 '19 at 00:08
  • @MinusOne-Twelfth ok, I am not familiar with this topic and will do more research. If you post this as an answer I will accept it. – IntegrateThis Mar 22 '19 at 00:11

2 Answers2

3

These are results of simple random walks on $\mathbb{Z}$. 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 $z\in\mathbb{N}$ 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).

Minus One-Twelfth
  • 7,413
1

I have no idea why $q_z=1$ if $p\le 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 $\binom{z}z 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$.

Mike Earnest
  • 75,930