ビットコインの論文の中に、悪意あるノードと善意のノードがプロックチェーンの伸ばし合いの競争をしたとき、善意のノードが僅かでも多ければブロックチェーンを乗っ取れる確率がかなり低い、ということを説明したコードがありますが、これを実際に実行して試してみました。
ビットコイン論文
http://bitcoin.peryaudo.org/vendor/bitcoin.pdf
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <stdio.h> #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; } int main() { printf(" "); for(double q=0.1 ; q <= 0.55 ; q += 0.05){ printf("q = %1.2f ", q); } printf("\n"); for(int i=0; i<30; i++){ printf("%2d ", i); for(double q=0.1 ; q <= 0.55 ; q += 0.05){ double d = AttackerSuccessProbability(q, i); printf("%f ", d); } printf("\n"); } } |
実行結果
論文より
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 blocks behind
実行結果にあるqは q=1-p の関係で、AttackerSuccessProbabilityはqz、zは縦軸の先行されているブロック数に相当します。
論文の説明にある
P < 0.001 q=0.10 z=5 q=0.15 z=8 q=0.20 z=11 q=0.25 z=15 q=0.30 z=24 q=0.35 z=41 q=0.40 z=89 q=0.45 z=340
の一番最初は、悪意あるノードが10%のとき、5ブロック後から追いつく確率が0.001(0.1%)以下という意味になります。実行結果は0.000914であっていることが確認できます。
もっと違うケースを見てみると実行結果から、悪意あるノードが50%の場合は、100%乗っ取られることがわかります。そんなことはまず想定しなくてもいいということなのでしょう。
30%のときは、5ブロックビハインドで18%くらいまで一気に下がります。またビハインドがゼロのときは悪意のノードがたとえ10%でも100%乗っ取れる計算になりますが、これはありえないということなのでしょう。