A combinatorial-probabilistic analysis of bitcoin attacks *

Evangelos Georgiadis, Doron Zeilberger

Research output: Contribution to journalArticle

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)56-63
Number of pages8
JournalJournal of Difference Equations and Applications
Volume25
Issue number1
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'A combinatorial-probabilistic analysis of bitcoin attacks <sup>*</sup>'. Together they form a unique fingerprint.

  • Cite this