Bitcoin Forum

In this thread, we are considering how possible it is for an attacker to generate an alternate chain faster than the honest chain. And the possible means of the attacker to get back the funds they sent on the chain.

the possibility that an attacker catches up with the honest chain is calculated as follows.

p= probability an honest node finds the next block
q= probability the attacker finds the next block
qz= probability the attacker will ever catch up from z block behind.

The mathematical equation can be seen on https://bitcoin.org/bitcoin.pdf

Using 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++)
                 poison * = lambda / i;
            sum -= poisson * (1 - pow(q / p, z - k) );
       }
       return sum;
}

The results can be found on the link posted above. Note: I found this source code from reading the PDF and thought it will be of use to some members too. What are your thoughts on solving for the possibility of double spending when it's almost impossible for the honest chain to accept a block with an invalid transaction.

Bottom line, the Binomial Random Walk success event is the honest chain being extended by one block increasing its lead by +1 and the failure event is the attacker's chain being extended by one block, reducing the gap by -1.

Goodluck!

Fixed a couple of typos in the code, and made it available online so that anyone can play around with it:

https://www.online-cpp.com/sNGDFBVjMC

Tried a couple of values for q and z, and they seem to match the paper

This has already been implemented in here (https://web.archive.org/web/20181231045818/https://people.xiph.org/~greg/attack_success.html).

It's not possible to accept an invalid transaction. Period. What's possible is to reverse a previously confirmed and, therefore, valid transaction. The odds of successfully reversing a block, so you can reverse a transaction, with a given portion of the hashrate can be seen in the above link.