Last active
December 13, 2017 08:59
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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