引き続きMathJaXを使用します。古いブラウザでは読めないかもしれません。
$p>q$という本システムの前提下では、攻撃者が追いつく確率は、追いつくべきブロック数が増えるほど指数関数的に小さくなる。従って、もし最初に運良く相手との差を詰められなければ、差が急激に開き、追いつく可能性はほとんど無くなるだろう。
支払人による取引改ざんを事実上不可能にするために、受取人はどの程度待てば良いだろうか。攻撃者は、受取人に対してしばらくの間正しく支払われたと思い込ませ、その後に払った額を奪い戻す。受取人は、いずれ不正な取引であるとの警告を受けるが、支払人はその時刻をできるだけ遅らせたい。
受取人は、取引のたびに鍵のペアを生成し、相手に公開鍵を送って間を開けずに支払うよう促す。さもないと、支払人が、チェーンを偶然何ブロックか伸ばせた瞬間を狙って、取引を実行するかもしれないからである。攻撃者である支払人は、取引を実行してから、それと異なる情報をブロックに含めて演算量証明を開始し、正規のものとは別にチェーンを伸ばし始める。
受取人が、自分の取引がブロックに埋め込まれ、その後にチェーンが$z$ブロック伸びたことを確認したとする。その間に攻撃者が影でどれだけチェーンを伸ばしたかは、分からない。しかし、善良なチェーンが設定通りの間隔でブロックを生成したと仮定したら、攻撃者が伸ばせるチェーンの長さはポアソン分布に従い、そのパラメータ$\lambda$は次のようになる。
\[\lambda=z \frac{q}{p}\]
「受取人は、取引のたびに鍵のペアを生成し支払人に公開鍵を送って、間を開けずに送金するよう促す」
の部分は、意味が曖昧で翻訳に迷いました。原文は”The receiver generates a new key pair and gives the public key to the sender shortly before signing.”で、そのまま訳すと「”signing”の直前に、受取人は鍵のペアを生成し公開鍵を送金人に送る」ですが、”signing”が電子署名のことだとすると、受取人は電子署名を使わないので、送金者が電子署名すること（＝送金すること）になります。相手が送金する直前まで、受取人は公開鍵を知らせるな、ということです。
しかし、これは意味が無いのではないでしょうか。公開鍵を送金者が知らなくても、ダミーのアドレスに送金したという取引データを準備していれば、不正が可能だからです。あるいは”before signing”というのは一般的な意味での「契約直前」を指しているのかもしれません。しかし、どう翻訳しても論理的に合わないので、著者の勘違いではないかと思うのですが……よくわかりません。
ただし、送金側がタイミングを選択することにより、チェーンが伸びた時点を見計らってブロック数を稼いだまま送金できるというのは、事実です。信用ならない相手から支払いを受ける場合は、何らかの方法で送金時刻を指定する必要があります。それでも以下の計算のように、相手のCPU能力が一般的な規模ならば問題なく、またある程度の時間を待機して取引を確認することにより、送金がキャンセルされることは防げます。大きな組織から大金を受け取るような場合でなければ、ほとんど問題にはならないでしょう。
では、どの程度の時間を待てば良いか。そのためには、善良チェーンが$z$ブロック伸びた間に、攻撃者チェーンがどれだけブロック数を稼いでいるかを知らなければなりません。暗号論的ハッシュ関数を使う限り、演算量証明の探索空間はほぼ無限なので、ブロックの生成頻度はポアソン過程となります。攻撃者は善良ノードの$q/p$倍のCPU能力を持つので、平均生成頻度は$z q/p$で、これがポアソン分布のパラメータとなる、というわけです。
攻撃者が追いつく確率は、開始時に攻撃者が$k$ブロックを計算し終えている確率（ポアソン分布の確率関数）に、$z-k$ ブロック差から追いつく確率を掛け、それをすべての$k$について足し合わせれば良い。
\[
\sum_{k=0}^\infty \frac{\lambda^k e^{-k}}{k!}\cdot
\left\{ \begin{array}{ll}
(q/p)^{z-k} & if\hspace{3mm} k\le z \\
1 & if\hspace{3mm} k\gt z
\end{array} \right\}
\]
無限の項を足し合わせなくても良いように、式を変形する。
\[
1-\sum_{k=0}^z \frac{\lambda^k e^{-k}}{k!}
\left\{ 1-(q/p)^{z-k}\right\}
\]
これを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
最初の式は前回の結果を利用、その次の式では、ポアソン分布の確率関数を$k=0 \sim\infty$まで足し合わせると1になることを利用していますね。
もう少し厳密に考えると、ブロックの生成頻度は善良側もポアソン分布なので、同じ$z$ブロックでも長い時間がかかった場合は、攻撃側がブロックを多めに生成している可能性があります。そのため実際には、$z$の値と共に経過時間も考慮してPを算出すべきでしょう。その場合の式を考えてみるのも面白いかと思います。
最近のコメント