A combinatorial-probabilistic analysis of bitcoin attacks *

Evangelos Georgiadis, Doron Zeilberger

Research output: Contribution to journalArticle

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

Fingerprint

Combinatorial Analysis
Probabilistic Analysis
Attack
Asymptotic Formula
Incomplete beta Function
Higher-order Asymptotics
Recurrence Equations
Proof Theory
Veins
Compilation
Recurrence
Statistical property
Continue
Term

All Science Journal Classification (ASJC) codes

  • Analysis
  • Applied Mathematics
  • Algebra and Number Theory

Cite this

@article{6053b831d52046a486e483a7aed73a3a,
title = "A combinatorial-probabilistic analysis of bitcoin attacks *",
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{\'e}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{\'e}rez-Marco who did the leading term. We then study the statistical properties (expectation, variance, etc.) of the duration of a successful attack.",
author = "Evangelos Georgiadis and Doron Zeilberger",
year = "2019",
month = "1",
day = "2",
doi = "https://doi.org/10.1080/10236198.2018.1555247",
language = "English (US)",
volume = "25",
pages = "56--63",
journal = "Journal of Difference Equations and Applications",
issn = "1023-6198",
publisher = "Taylor and Francis Ltd.",
number = "1",

}

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

In: Journal of Difference Equations and Applications, Vol. 25, No. 1, 02.01.2019, p. 56-63.

Research output: Contribution to journalArticle

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.

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 -