Fermat’s Library | Bitcoin: A Peer-to-Peer Electronic Cash System annotated/explained version.
Given
our a
ssumption th
at
p >
q,
the
probability
drops
exponentially
as
the
number
of
blocks
the
attacker
has
to
catch
u
p
with
increases.
Wit
h
the
o
dds
against
hi
m,
if
he
doesn’t
make
a
lu
cky
lunge forward early on, his chances become
vanishingly small as he falls further behind.
W
e
now
consider
how
long
the
recip
ient
of
a
new
tran
saction
needs
to
wait
before
being
sufficiently
c
ertain
the
sender
can’t
change
th
e
transaction.
W
e
assume
the
sende
r
is
an
attacker
who
wants
to
make
th
e
recipient
believe
he
p
aid
him
for
a
while,
then
switch
it
to
pay
b
ack
to
himself
after
some
ti
me
has
passed.
T
he
receiver
will
be
alerted
when
that
happens,
but
the
sender hopes it will be too late.
The
receiver
generates
a
new
key
pair
and
gives
the
public
key
to
the
sender
shortly
before
signing.
This
prevents
the
sender
from
preparing
a
chain
of
blocks
ahead
of
ti
me
by
working
on
it continuousl
y until
he is
lucky enough
to get
far
enough ahead,
then execu
ting the
transaction a
t
that
moment.
On
ce
the
tr
ansaction
is
sent,
the
dishonest
sender
starts
working
in
secr
et
o
n
a
parallel chain containing an a
lternate version of his transaction.
The
recipient
waits
until
the
transaction
h
as
been
added
to
a
block
and
z
blocks
have
been
linked
after
it.
He
doesn’t
know
the
exact
amount
of
progress
the
attacker
has
made,
but
assuming
the
honest
blocks
took
the
average
expected
time
per
block,
the
atta
cker’s
potential
progress will be a Poisson distribution with
expected value:
=
z
q
p
T
o
ge
t
the
p
robability
the
attacker
could
still
catch
up
now
,
we
multiply
the
Poisson
density
for
each amount of progress he could have
made by the probability he could catch up from that point:
∑
k
=
0
∞
k
e
−
k
!
⋅
{
q
/
p
z
−
k
if
k
≤
z
1
if
k
z
}
Rearranging to avoid summing the infinite tail
of the distribution…
1
−
∑
k
=
0
z
k
e
−
k
!
1
−
q
/
p
z
−
k
Converting to C code…
#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 – q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 – pow(q / p, z – k));
}
return sum;
}
7
