A combinatorial-probabilistic analysis of bitcoin attacks^*

* Important: This article is accompanied by a Maple package, Bitcoin.txt, available from the front of this article http://sites.math.rutgers.edu/∼zeilberg/mamarim/mamarimhtml/bitcoin.html, where readers can also find numerous input and output files. In due course, the current package will also be available along with an implementation in MathCognify's own symbolic language (®:Donations in BTC are appreciated, if you'd like to support this type of research; some parts of the work will see the light of Free Software. The BTC address is: 3B69VRGSGt41K5GBrvCWaiUZ6uE2md9i9q.) from https://github.com/MathCognifyTechnologies/fr-crypto-bitcoin-1.

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.

KEYWORDS:

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

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 68W30
• 05A10
• 33C90
• 11B37
• 39A60

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

* Important: This article is accompanied by a Maple package, Bitcoin.txt, available from the front of this article http://sites.math.rutgers.edu/∼zeilberg/mamarim/mamarimhtml/bitcoin.html, where readers can also find numerous input and output files. In due course, the current package will also be available along with an implementation in MathCognify's own symbolic language ($\text{®}$:Donations in BTC are appreciated, if you'd like to support this type of research; some parts of the work will see the light of Free Software. The BTC address is: 3B69VRGSGt41K5GBrvCWaiUZ6uE2md9i9q.) from https://github.com/MathCognifyTechnologies/fr-crypto-bitcoin-1.

1 Androids are humanoid robots. Our incentive for picking androids, is at least two-fold. For one, our creations are emotionless – thereby strengthening some of our key assumptions below by taking the almost unpredictable nature or volatility of human emotions out of the parameter space. For another, networked androids enable easier generalizations.

2 In honour of Meni Rosenfeld's pioneering spirit for correctly guessing that the negative binomial distribution provides a better approximation. Note, the duo, Cyril Grunspan and Ricardo Pérez-Marco, are the first to cement this guess via proof in [7, Proposition 5.3 on p. 10]; namely, that the negative binomial distribution is the exact distribution in the bitcoin model, under a given set of simplifying assumptions.

3 For completeness, we provide their formula in [7, Theorem 6.1 on p. 13], $P\left(z\right)=I_s(z,1/2).$

4 Other slip-ups of different nature, did occur in the paper; e.g. the omission of Feller's volume number in the reference section on page 9 in [8]. Any serious student of probability is aware that Feller published two volumes. Incidentally, the publication year that he provides, maybe indicative of his age or it's just noise. That said, in today's era, the printing year provided, for supposedly volume 1, is, harder to obtain.

5 Care needs to be taken when using technical jargon. In [7] the term block validation should be replaced by finding a solution to the proof-of-work or an analogous phrase, since the process of validating blocks is more or less instantaneous.

6 August 12,2018. www.coinmarketcap.com