A combinatorial-probabilistic analysis of bitcoin attacks*

In 2008, Satoshi Nakamoto famously invented bitcoin, and in his (or her, or their, or its) white paper sketched an approximate formula for the probability of a successful double spending attack by a dishonest party. This was corrected by Meni Rosenfeld, who, under more realistic assumptions, gave the exact probability (missing a foundational proof); and another formula (along with foundational proof), in terms of the Incomplete Beta function, was given later by Cyril Grunspan and Ricardo Pérez-Marco, that enabled them to derive an asymptotic formula for that quantity. Using Wilf-Zeilberger algorithmic proof theory, we continue in this vein and present a recurrence equation for the above-mentioned probability of success, that enables a very fast compilation of these probabilities. We next use this recurrence to derive (in algorithmic fashion) higher-order asymptotic formulas, extending the formula of Grunspan and Pérez-Marco who did the leading term. We then study the statistical properties (expectation, variance, etc.) of the duration of a successful attack.