### 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 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Analysis
- Applied Mathematics
- Algebra and Number Theory

### Keywords

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

### Cite this

}

^{*}',

*Journal of Difference Equations and Applications*, vol. 25, no. 1, pp. 56-63. https://doi.org/10.1080/10236198.2018.1555247

**A combinatorial-probabilistic analysis of bitcoin attacks ^{*}.** / Georgiadis, Evangelos; Zeilberger, Doron.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A combinatorial-probabilistic analysis of bitcoin attacks *

AU - Georgiadis, Evangelos

AU - Zeilberger, Doron

PY - 2019/1/2

Y1 - 2019/1/2

N2 - 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.

AB - 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.

KW - Bitcoin protocol

KW - Wilf-Zeilberger algorithmic proof theory

KW - combinatorics

KW - cryptography

KW - double-spend attack

KW - negative binomial distribution

KW - symbolic-probabilistic computation

UR - http://www.scopus.com/inward/record.url?scp=85058196538&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058196538&partnerID=8YFLogxK

U2 - https://doi.org/10.1080/10236198.2018.1555247

DO - https://doi.org/10.1080/10236198.2018.1555247

M3 - Article

VL - 25

SP - 56

EP - 63

JO - Journal of Difference Equations and Applications

JF - Journal of Difference Equations and Applications

SN - 1023-6198

IS - 1

ER -