ビットコインの原論文を読む 11節 数学的根拠（前編）

この節は数式が多いので、MathJaXを使用します。古いブラウザでは読めないかもしれません。

個人的には、論文の中で一番面白い節です。

１１　数学的根拠

正しいチェーンよりも速く、攻撃者が自身のチェーンを伸ばすには、どれ程の計算能力を持てば良いだろうか。ただしこれが成功しても、正当な量以上のコインを生成したり、扱ったことがないコインを他人から盗み出せるようになったりするわけではない。善良なノードは、不正な取引を受け付けず、また不正な取引が埋まったブロックも受け付けないからだ。攻撃者がなし得る詐欺行為は、他人に支払った過去の取引を無効にし、コインを奪い戻すことのみである。それも、取引から時間が経つほど困難になる。

善良なチェーンと攻撃者のチェーンとの闘いは、±1歩ずつのランダムウォークと見なせる。善良なチェーンが1ブロック伸びた場合は1歩進み、攻撃者のチェーンが1ブロック伸びた場合は1歩下がる。

攻撃者のチェーンが、より長い善良なチェーンに追いつく確率は、「ギャンブラー破産問題」の理論を使って計算できる。ギャンブラーは一定額の赤字から開始するが、無限の資金を持ち何回でも賭け続けられるとする。そして、一度でも損益無しの状態になれば勝ちである。その確率は、攻撃者が善良なチェーンに追いつく確率と同じで、次のような式になる[8]。

$p=$善良なノードが先にブロックを生成する確率
$q=$攻撃者が先にブロックを生成する確率$(p+q=1)$
$q_z=z$ブロック遅れている攻撃者のチェーンが、一度でも善良なチェーンに追いつく確率
$q_z = \left\{ \begin{array}{ll}
1 & if\hspace{3mm} p\le q \\
(q/p)^z & if\hspace{3mm} p>q
\end{array} \right\}
$

[8] W. Feller, “An introduction to probability theory and its applications,” 1957.9

[解説]　
攻撃者がどれだけCPU能力をかき集めても、コイン所有者の秘密鍵が無ければ勝手に送金することは不可能です。もっとも、天文学的なCPU能力を持てば公開鍵から秘密鍵を生成できますが、事実上不可能でしょう。また、生成ブロック内の送金情報に不正があれば、他のノードはそれを受け付けません。

従って攻撃者ができることは、自分が送金した過去の取引を無かったことにする程度、ということになります。そのためには、無効にしたい取引より前から演算量証明を開始し、生成ブロック数で善良ノード群を上回る必要があります。例えば、ある時点から演算量証明を開始し、その後30分間に善良ノード群よりも多くのブロックを生成できれば、その30分間の取引を無効に出来ます。

相手を騙すには、一定期間その取引が成立したと思い込ませる必要があるので、初期にたまたまブロックを生成できてもすぐには送金を取り消せません。しかし、相手からサービスを受けた後なら、その後一瞬でも累計生成ブロック数が善良ノード群のそれを超えれば、送金のキャンセルが可能です。

サービスを受けた時点で善良ノード群を上回っていれば、もちろん何の支障もありません。そうでない場合は、ギャンブラーの破産問題と同じ状態になります。資金を無限に持つギャンブラーを考えるので「破産問題」と呼ぶのはためらわれますが。

念のために、上の最後の式を証明しておきましょう。マルチンゲール理論を元にした、裏技を使ってみます。まず、問題文を少し変えて、「正直なノードに$z_{max}$の差を付けられたら攻撃者が負け」とするケースを考えます。すなわち次のような問題で、本来の破産問題に近いものです。

善良ノードが攻撃者ノードよりも$z(>0)$ブロックだけ長いチェーンを持っているとする。攻撃者ノードが善良ノードに追いつけば攻撃者の勝ち、逆に、差が$z_{max}$まで開けば善良ノードの勝ちとする。善良ノード・攻撃側ノードのブロック生成確率を$p,q$とする時、攻撃者ノードが勝つ確率$q_z$を求めよ。

一度これを解いて、最後に$z_{max}\to\infty$とする方針で行きましょう。以下、Eは平均を表します。

どちらかがブロックを1つ発見する毎に時刻$t$が1進むとして、各時刻において善良ノード側が何ブロック優位に立っているかを、確率変数$X_t$で表します。すると次が成り立ちます。(**)
\[\begin{align}
E[(q/p)^{X_t}]&=p \cdot E[(q/p)^{X_{t-1} +1}]+q\cdot E[(q/p)^{X_{t-1} -1}]\\
&=E[(q/p)^{X_{t-1}}]\\
&=\ldots\\
&=E[(q/p)^{X_0}]\\
&=(q/p)^z
\end{align}
\]
決着が付いた時刻を確率変数$T$で表すと、$X_T$は攻撃側ノードが勝った時に0、負けた時に$z_{max}$になります。平均の定義から、次の式を展開できます。
\[\begin{align}E[(q/p)^{X_T}]&=q_z (q/p)^0+(1-q_z)(q/p)^{z_{max}}\\
&=(q/p)^{z_{max}}+q_z (1-(q/p)^{z_{max}})\end{align}\]
そして$E[(q/p)^{X_T}]$は$(q/p)^z$に等しいはずです。つまり
\[(q/p)^z=(q/p)^{z_{max}}+q_z (1-(q/p)^{z_{max}})\]
で、これを$q_z$で解くと次式を得ます。
\[q_z=\frac{(q/p)^z-(q/p)^{z_{max}}}{1-(q/p)^{z_{max}}}\]
そして$z_{max}\to\infty$の極限を取ると
\[
q_z = \left\{ \begin{array}{ll}
1 & if\hspace{3mm} p\le q \\
(q/p)^z & if\hspace{3mm} p>q
\end{array} \right\}
\]
になります。元論文の式を得られました。$p=q$の場合ゼロ割りが発生してしまいますが、その場合を除いて考え極限を取ると、$q_z=1$となり問題ありません。なお、本文には書かれていませんが、$z\le 0$の場合は明らかに$q_z=1$となります。（サービスを受けた時点で善良ノード群を上回っていた場合に相当します。）

ギャンブラー破産問題に関しては、岩沢宏和「リスクを知るための確率・統計入門」を参考にしました。

ところで、$p,q$はどう求めれば良いのでしょうか。実はこれ、善良ノードと攻撃者ノードがそれぞれ単独でブロックを生成する平均頻度の比、すなわちCPU能力の比になります。これも確認しましょう。暗号論的ハッシュ関数を使う 限り探索空間が事実上無限なので、両陣営ともブロックの生成はポアソン過程となります。また、こんな定理があります。「2つのポアソン過程において、ある時点から観測してどちら の事象が先に発生するかの確率は、その平均頻度（この場合は$p, q$）に比例する」つまり、次にどちらがブロックを生成するかの確率とCPU能力比は等しいわけです。この辺は、ポアソン過程の再生性が関係しますね。

(*)
「正当な量以上のコインを生成」することはできないはずですが、これを可能にする裏技が考え出されています。善良なノードがブロックを生成した瞬間に、手持ちのブロックを拡散するという方法で、25%アタックなどと呼ばれています。別の機会に解説予定。

(**)

\[E[(q/p)^{X_t}]=p \cdot E[(q/p)^{X_{t-1} +1}]+q\cdot E[(q/p)^{X_{t-1} -1}]\]
という変換は、人によっては当たり前に思うようですが、何となくもやもやとします。もう少し詳しく証明しておきましょう。
$X_t$について、直前にどちら側がブロックを生成したかで場合分けすると、任意の$x$について
\[P(X_t=x)=p\cdot P(X_{t-1}=x-1)+q\cdot P(X_{t-1}=x+1)\]
が成り立ちます。従って、
\[\begin{align}
E[(q/p)^{X_t}]&=\sum^{z_{max}}_{x=0} (q/p)^x P(X_t=x)\\
&=\sum^{z_{max}}_{x=0} (q/p)^x \left\{p\cdot P(X_{t-1}=x-1)+q\cdot P(X_{t-1}=x+1)\right\}\\
&=p\sum^{z_{max}}_{x=0} (q/p)^x P(X_{t-1} +1=x)+q\sum^{z_{max}}_{x=0} (q/p)^x P(X_{t-1} -1=x)\\
&=p\cdot E[(q/p)^{X_{t-1} +1}]+q\cdot E[(q/p)^{X_{t-1} -1}]\end{align}\]
となります。