A CombinatorialProbabilistic Analysis of Bitcoin Attacks
By Evangelos Georgiadis and Doron Zeilberger
.pdf
.ps
.tex
[Appeared in Journal of Difference Equations and its Applications, volume 25, issue 1 (2019), 5663.]
First Written: Aug. 15, 2018;
Last update of this webpage: Nov. 23, 2018.
Using WilfZeilberger algorithmic proof theory, we continue pioneering work of Meni Rosenfeld
(followed up by interesting work by Cyril Grunspan and Ricardo PerezMarco)
and study the probability and duration of successful bitcoin attacks, but using an equivalent,
and much more congenial, formulation as a certain twophase soccer match.
Added Sept. 7, 2018: watch the
lecture:
vimeo:
part 1 part 2
(videotaped and uploaded by Mingjia Yang).
youtube:
part 1 part 2
( uploaded by Edinah Gnang).
Added Nov. 4, 2018: Read
Version 2
Added Nov. 11, 2018: Read
Version 3
Maple packages

Bitcoin.txt,
a Maple package to compute probabilities associated with bitcoin attacks.
Sample Input and Output for Bitcoin.txt

If you want to see a computergenerated essay about our subject, that was used to write
the human paper,
the input file generates the
output file.

If you want to see results of simulations, confirming the theoretical results of
the article. We have the following

The probablity of the bad team scoring a goal, q, is 1/5, for n from 1 to 16
(for n more than 16 it FAILED since the prob. of the bad team winning is so low) run 10000 times
the input file generates the
output file.
[Note, that YOU should get different outputs every time, since this is simulations]

If you want to see the first 100 Rosenfeld polynomials that tell you the probability of a successful attack
if the good guys accululated n coins, for n from 1 to 100
the input file generates the
output file.

If you want to see the first 100 GeorgiadisZeilberger rational functions that tell you the expected duration of the second phase
if the case of a successful attack,
the input file generates the
output file.

If you want to see the cutoffs for the number of good coins to mint in order to guarantee
probability of a successful attack to be less than 1/10, 1/100, and 1/1000 for
q=0.29,q=0.323,..., q=0.356, ... all the way to q=0.49
the input file generates the
output file.
Articles of Doron Zeilberger
Doron Zeilberger's Home Page