Skip to content

Instantly share code, notes, and snippets.

@ShenTengTu
Last active December 13, 2017 08:59
Show Gist options
  • Save ShenTengTu/90cc67602309514f1e5106d70959bc7b to your computer and use it in GitHub Desktop.
Save ShenTengTu/90cc67602309514f1e5106d70959bc7b to your computer and use it in GitHub Desktop.
Bitcoin Attacker Success Probability,Javascript version. Reference Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System", 2008.
/**
* Reference Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System", 2008.
* The attacker's potential progress will be a Poisson distribution with expected value.
* @param [Number] q Probability the attacker finds the next block,(double).
* @param [Number] z The attacker will ever catch up from z blocks behind,(int).
**/
function AttackerSuccessProbability(q,z){
//p = probability an honest node finds the next block
//q = probability the attacker finds the next block
let p = 1.0 - q;//Binomial Random Walk
let lambda = z * (q / p);//The average expected time per block
let sum = 1.0;
let i, k;
for (k = 0; k <= z; k++){
let poisson = Math.exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - Math.pow(q / p, z - k));
}
return sum;
}
///Running some results, same as the paper.
let P,Q,Z;
Q=0.1;
console.log(`q=${Q}`);
for(Z=0;Z<=10;Z++){
P = AttackerSuccessProbability(Q,Z);
console.log(` z=${Z} P=%s`,P.toLocaleString(undefined, {minimumFractionDigits:7,maximumFractionDigits: 7}));
}
Q=0.3;
console.log(`q=${Q}`);
for(Z=0;Z<=50;Z+=5){
P = AttackerSuccessProbability(Q,Z);
console.log(` z=${Z} P=%s`,P.toLocaleString(undefined, {minimumFractionDigits:7,maximumFractionDigits: 7}));
}
console.log(`P < 0.001`);
for(Q=0.10;Q<=0.45;Q+=0.05){
Z=-1;
do{
Z++;
P = AttackerSuccessProbability(Q,Z);
}while(P>=0.001);
console.log(` q=%s z=${Z}`,Q.toLocaleString(undefined, {minimumFractionDigits:2,maximumFractionDigits: 2}));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment