### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 56-63 |

Number of pages | 8 |

Journal | Journal of Difference Equations and Applications |

Volume | 25 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2 2019 |

### All Science Journal Classification (ASJC) codes

- Analysis
- Algebra and Number Theory
- Applied Mathematics

### Keywords

- Bitcoin protocol
- Wilf-Zeilberger algorithmic proof theory
- combinatorics
- cryptography
- double-spend attack
- negative binomial distribution
- symbolic-probabilistic computation