Why is Poisson instead of Negative Binomial used for computing attacker's potential progress?

Question

In chapter 11 of the Satoshi's paper it is claimed that:

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 zq/p.

I think the precise model should be a negative binomial distribution instead of a Poisson one.

My question is: Is Satoshi's solution an approximation or is it supposed to describe accurately the problem?

Answer 1

I have found the answer in this article by Meni Rosenfeld, page 7. The problem should indeed be modeled with a Negative Binomial distribution, and the computations done on Satoshi's paper are approximations.

The fact of matter is that the quality of the approximation does not rely on the expected high number of trials required to mine a block, but in the general similarity between the negative binomial and the Poisson distributions. This leads to non-negligible differences between the actual probability and the probability computed by Satoshi, e.g. for q=10% and 5 confirmations, Satoshi says P=17.73523%, while Rosenfeld says P=19.762%.

Answer 2

I think you are correct, since the success/failure of each nonce to satisfy the difficulty target is binary, rather than continuous, this is a discrete probability distribution and the correct distribution should be the negative binomial. However since the number of trials required per block is extremely large, ($> 10^20$ as of this writing), it is a very good approximation to take the limit $r\to\infty$ as described on the Wikipedia page. This is equivalent to taking the probability of success in any one trial to be zero, while keeping the mean of the distribution fixed, and results in the Poisson distribution. So, the difference is roughly less than 10^-20 and far to small to be measurable.

Answer 3

Each try in Bitcoin mining is stochastically independent of every other try. Both the Bernoulli process and the Poisson process model independent events, however, the Bernoulli process is focused on the number of binary events from a set of tries, while the Poisson process specifically focuses on the subcase where the likelihood is extremely low, and you're interested in the occurrence of a singular event. As success at mining is very unlikely, and mining starts anew after a block is discovered, the Poisson process is more applicable.