正規取引のチェーンよりも速く、攻撃者がチェーンを伸ばすには、どれ程の計算能力を持てば良いでしょう？
攻撃者が可能な詐欺行為は、他人に支払った過去の取引を無効にし、コインを奪い戻すことだけです。それも、取引から時間が経つほど困難になります。
攻撃者のチェーンが、より長い善良なチェーンに追いつく確率は、ギャンブラー破産問題の理論を使って計算できます。
ギャンブラーは一定額の赤字（マイナススタート）から開始するが、無限の資金を持ち何回でも賭け続けられるとします。そして、一度でも損益無し（マイナスをゼロにもっていければ勝ちと定義する）の状態になれば勝ちとします。
その確率は、攻撃者が善良なチェーンに追いつく確率と同じで、次のような式になります※8。
p=善良なノードが先にブロック生成する確率
q=攻撃者が先にブロック生成する確率 (p+q=1)
qz=zブロック遅れている攻撃者のブロックチェーンが善良なノードのブロックチェーンに追いつく確率
qzはp≤qの場合１になる
qzはp＞qであれば(q/p)^zになる
^はルートの意味
p>qという前提では、攻撃者が正規のチェーンに追いつく確率は、ブロック数が増えるほど指数関数的に小さくなります。
そのため最初のうちに、相手（正規チェーン）との差を詰めないと、差が急激に開き、追いつく可能性はほとんど無くなります。
取引の改ざんを不可能にするために、受取人はどの程度待てば良いでしょう？
ちなみに攻撃者は、受取人に対してしばらくの間、正しく支払われたと思い込ませて、その後に払った額を奪い戻せば良いです。
受取人は、いずれ不正な取引であるとわかってしまいます。なので、支払人（攻撃者）はその時刻をできるだけ遅らせたいと考えます。
通常、受取人は、取引を行う際には、鍵のペアを生成し、相手に公開鍵を送ってすぐに支払うよう促します。
そうでないと、支払人（攻撃者）が、チェーンを偶然にも何ブロックか伸ばせた瞬間を狙って、取引を実行するかもしれないためです。
攻撃者である支払人は、取引を実行し、それと異なる情報をブロックに含めて演算量証明を開始し、正規のものとは別にチェーンを伸ばし始めようとするでしょう。
仮に受取人が、自分の取引がブロックに埋め込まれ、その後にチェーンがzブロック伸びたことを確認したとしましょう。
その場合、攻撃者が実は裏でどれだけチェーンを伸ばしたかは、分かりません。
しかし、善良なチェーンが設定通りの間隔でブロックを生成したと仮定したら、攻撃者が伸ばせるチェーンの長さはポアソン分布に従い、そのパラメータλは次のようになります。
λ=z(q/p)
攻撃者が正規のチェーンに追いつく確率は、攻撃開始時に攻撃者がkブロックを計算し終えている確率（ポアソン分布の確率関数）に、z−kブロック差から追いつく確率を掛け、それをすべてのkについて足し合わせればOKです。
∞∑k=0 (λke−k )/k!⋅{(q/p)z−k if k≤z 1 if k>z}
無限の項を足し合わせなくても良いように、式を変形します。
1−z∑k=0 (λke−k)/k!{1−(q/p)z−k}
これをC言語で記述すると、次のようになります。
#include 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;
}
具体的な数値を計算すると、攻撃者が追いつく確率は、zに対して指数関数的に減少することがわかっています。
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
受取人はどの程度の時間を待つべきだろうか。攻撃者が改ざんできる確率を0.1%未満に抑えたい場合は、次に示す個数のブロックを善良なノードが生成するまでです。
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
※8 W. Feller, “An introduction to probability theory and its applications,” 1957.9
