1.記事の目的
ビットコインのホワイトペーパー ビットコイン：P2P電子通貨システム(11:数学的根拠) には、攻撃者のチェーンが正規のチェーンを追い越す確率を議論している。
☆☆☆☆☆☆☆☆☆☆☆☆☆ 引用1 ☆☆☆☆☆☆☆☆☆☆☆☆☆
攻撃者のチェーンが、より長い善良なチェーンに追いつく確率は、「ギャンブラー破
産問題」の理論を使って計算できる。ギャンブラーは一定額の赤字から開始するが、無
限の資金を持ち何回でも賭け続けられるとする。そして、一度でも損益無しの状態にな
れば勝ちである。その確率は、攻撃者が善良なチェーンに追いつく確率と同じで、次の
ような式になる。
$p=$善良なノードが先にブロックを生成する確率
$q=$攻撃者が先にブロックを生成する確率
$p_{z}=z$ブロック遅れている攻撃者のチェーンが、一度でも善良なチェーンに追い
つく確率
q_{z} = \left\{
\begin{array}{ll}
1 & (p ≦ q) \\
\bigl(\frac{q}{p}\bigr)^{z} & (p>q)
\end{array}
\right.
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
ブロックチェーンに収録された情報が改ざん不能であることの根幹理論となるが、その内容を理解するには「ギャンブラーの破産問題」について理解する必要がある。ここでは、「ギャンブラーの破産問題」を数学的に理解する記事を書きたいと思う。
2.ギャンブラーの破産問題
ギャンブラーの破産問題を簡単に説明すると以下の内容になる。
[ギャンブラーの破産問題]
・ Aはコインをn枚所有しており、BはN-n枚のコインを所有している。
・ コイン投げゲームを行う。
・ 表が出た場合は、AからBにコインが1枚支払われる。(コインの表がでる確率はp)
・ 裏が出た場合は、BからAにコインが1枚支払われる。(コインの裏がでる確率はq)
・ A,Bどちらかの手持ちのコインがなくなるまでコイン投げゲームは継続される。
・ コインの表が出る確率pをとするとき、Aのコインが0枚になる(Aが破産)する確率はいくらか?
事象Rと事象Hを下記のように定義する。
$ 事象R={Aの初期保有コインがn枚のとき、Aがいつか破産する} $
$ 事象H={第1回目のコイン投げゲームに表が出る} $
ここで、$P(R),P(H)$をそれぞれ「Aの初期保有コインがn枚のとき、Aがいつか破産する」、「第1回目のゲームに表がでる確率」とすると
\begin{align}
P(R) &= P(R\cap H) + P(R\cap H^c ) \\
&= P(R|H)P(H) + P(R|H^c)P(H^c) \tag{1} \\
\end{align}
となる。ここで
\begin{align}
P(R) &=\left\{Aの初期所持コインn枚のときにいつか破産する確率\right\}=r_{n} とおくと\\
P(R|H) &=\left\{Aの初期所持コインn+1枚のときにいつか破産する確率\right\}=r_{n+1} \\
P(R|H^c) &=\left\{Aの初期所持コインn-1枚のときにいつか破産する確率\right\}=r_{n-1} \\
\end{align}
と表記できる。
コイン投げにて表が出る確率を$p$ , 裏がでる確率を$q$ とするとき $p+q=1$ となる。
以下、$p\neq q $の場合と、$p=q $の場合で場合分けをして議論を進める。
2.1 p≠q のとき
このとき$(1)$式は、下記$(2)$式に書き換えられる。
\begin{align}
r_{n}= p r_{n+1} + q r_{n-1} \tag{2} \\
\end{align}
つまり、
\begin{align}
r_{n+1}-\frac{1}{p}r_{n}+\frac{q}{p}r_{n-1}=0 \tag{3} \\
\end{align}
と記述できる。
いま(3)式が、$r_{n+1}-αr_{n}=β(r_{n}-αr_{n-1}) $と変形できたとする。この式は下記(4)に変形できる。
\begin{align}
r_{n+1}-(α+β)r_{n}+αβr_{n-1}=0 \tag{4} \\
\end{align}
(3)(4)式より、
\begin{align}
\frac{1}{p} &=α+β \tag{5}\\
\frac{q}{p} &=αβ \tag{6} \\
\end{align}
が成立することが分かる。(5)(6)式は、2次方程式の解と係数の関係を表しており、αとβは2次方程式 $t^{2}-\frac{1}{p}t+\frac{q}{p}=0 $の解である。(5)(6)より以下の通りα,βを計算する。
$ α=\frac{1}{2p}(1+\sqrt{1-4pq})= \frac{1}{2p}(1+\sqrt{1-4p(1-p)})
= \frac{1}{2p}(1+1-2p)=\frac{1}{p}(1-p)=\frac{q}{p} $
$ β=\frac{1}{2p}(1-\sqrt{1-4pq})= \frac{1}{2p}(1-(1-2p))=1 $
ここで、
$r_{n+1}-αr_{n}=β(r_{n}-αr_{n-1})=β^{2}(r_{n-1}-αr_{n-2})= ・・・= β^{n}(r_{1}-αr_{0}) \tag{7}$
と書き換えることができる。
つまり、$ α=q/p, β=1 $のときは(7)式は(8)式に, $ α=1,β=q/p $のときは(7)式は(9)式に書き換えられる。
\begin{align}
r_{n+1}-\frac{q}{p}r_{n} &=r_{1}-\frac{q}{p}r_{0} \tag{8}\\
r_{n+1}-r_{n}&=\biggl(\frac{q}{p}\biggr)^{n} (r_{1}-r_{0}) \tag{9}\\
\end{align}
(8)-(9)を計算すると、
\begin{align}
\biggl(-\frac{q}{p}+1 \biggr)r_{n} &=\biggl[1-\biggl(\frac{q}{p}\biggr)^{n}\biggr]r_{1} - \biggl[\frac{q}{p}-\biggl(\frac{q}{p}\biggr)^{n}\biggr]r_{0} \tag{10} \\
\end{align}
となる。
Aの初期保有コインが0枚のときは初めから破産しているので、$r_{0}=1$となる。またAの初期保有コインがN枚のときは、ゲームに勝利しているので$r_{N}=0$である。よって、式(10)より
\begin{align}
r_{N} &=\frac{1-r_{1}}{1-q/p} \biggl(\frac{q}{p} \biggr)^{N} + \frac{r_{1}-q/p}{1-q/p} r_{0} \tag{11} \\
\end{align}
となる。(11)より$r_{1}$が求まる。
\begin{align}
r_{1} &= \frac{\frac{q}{p}-\bigl(\frac{q}{p}\bigr)^{N}}{1-\bigl(\frac{q}{p}\bigr)^{N} } \tag{12} \\
\end{align}
$r_{1}$が既知になったので(10)式より$r_{n}$が求まる。
\begin{align}
r_{n} &= \frac{\bigl(\frac{q}{p}\bigr)^{n}-\bigl(\frac{q}{p}\bigr)^{N}}{1-\bigl(\frac{q}{p}\bigr)^{N} } \tag{13} \\
\end{align}
2.2 p=q のとき
$p+q=1$なので$p=q=1/2$となる。よって式(5)(6)より$α=β=1$となる。式(7)より
\begin{align}
r_{n+1}-r_{n} &= r_{1}-r_{0} \tag{14} \\
\end{align}
となる。
(14)式は、
\begin{align}
r_{2} &= r_{1}+(r_{1}-r_{0}) \\
r_{3} &= r_{2}+(r_{1}-r_{0}) \\
r_{4} &= r_{3}+(r_{1}-r_{0}) \\
& ・・・・・・・・・ \\
r_{n} &= r_{n-1} +(r_{1}-r_{0}) \\
\end{align}
なので、
\begin{align}
r_{n} &= r_{1}+ \sum_{i=1}^{n-1}(r_{1}-r_{0}) \tag{15} \\
\end{align}
となる。$r_{0}=1,r_{N}=0$なので式(15)から式(16)が求まる。
\begin{align}
r_{N} &= r_{1}+ (r_{1}-r_{0})(N-1) \tag{16} \\
\end{align}
したがって、$r_{1}=\frac{N-1}{N} $となる。
以上より、(15)式に$r_{1}=\frac{N-1}{N} $を代入すると、$r_{n}$は
\begin{align}
r_{n} &= r_{1}+ (r_{1}-r_{0})(N-1) \\
&= 1-\frac{n}{N} \tag{17} \\
\end{align}
と求まる。
2.3 ギャンブラーの破産問題まとめ
[ギャンブラーの破産問題]
・ Aはコインをn枚所有しており、BはN-n枚のコインを所有している。
・ コイン投げゲームを行う。
・ 表が出た場合は、AからBにコインが1枚支払われる。(確率p)
・ 裏が出た場合は、BからAにコインが1枚支払われる。(確率q)
・ A,Bどちらかの手持ちのコインがなくなるまでコイン投げゲームは継続される。
・ コインの表が出る確率をpとするとき、Aのコインが0枚になる(Aが破産)する確率はいくらか?
(答え)
コイン投げゲームを行ったときに表が出る確率を$p$, 裏がでる確率を$q$とする。
$r_{n}$をAが初期にn枚のコインを保有している時に破産する確率を表しているとすると、
$r_{n}$は下記の式で表現できる。
r_{n} = \left\{
\begin{array}{ll}
\frac{\bigl(\frac{q}{p}\bigr)^{n}-\bigl(\frac{q}{p}\bigr)^{N}}{1-\bigl(\frac{q}{p}\bigr)^{N} } & (p \neq q) \\
1-\frac{n}{N} & (p=q)
\end{array}
\right.
3 悪意のあるブロックが善良なブロックを追い越す確率
ブロックチェーンの悪意のあるブロックがいつか善良なブロックを追い越す確率を求めるために、2節で説明したギャンブラーの破産問題を書き換えると下記のとおりになる。
[ギャンブラーの破産問題]
・ Aはコインをz枚所有しており、Bは0枚のコインを所有している。
・ 便宜上、A,Bともにコインの枚数が負数をとりうる場合もある。
・ コイン投げゲームを行う。
・ 表が出た場合は、AからBにコインが1枚支払われる。(確率p)
・ 裏が出た場合は、BからAにコインが1枚支払われる。(確率q)
・ AのコインがM枚になれば、Aはゲームに勝利したとする。
・ AがM枚のコインを所持したら、これ以降Aの所持コインが-1になることはほぼ起きないものとする。
・ Aのコインが-1枚になるまでコイン投げゲームは継続される。
・ Aのコインが-1枚になる(Aが破産)する確率はいくらか?
3.1 p≠q のとき
(10)式より、$r_{z}$を$r_{0}$と$r_{-1}$で表現すると、式(18)で書ける。
\begin{align}
\biggl(-\frac{q}{p}+1 \biggr)r_{z} &=\biggl[1-\biggl(\frac{q}{p}\biggr)^{z}\biggr]r_{0} - \biggl[\frac{q}{p}-\biggl(\frac{q}{p}\biggr)^{z}\biggr]r_{-1} \tag{18} \\
\end{align}
問題文の定義より、$r_{-1}=1,r_{M}=0$となる。これより$r_{0}$を算出すると、
\begin{align}
r_{0} &=\frac{\frac{q}{p}-\bigl(\frac{q}{p}\bigr)^{M}}{1-\bigl(\frac{q}{p}\bigr)^{M}} \tag{19} \\
\end{align}
$r_{-1}=1,r_{M}=0$と$r_{0}$の情報より(18)式を書き換える。
\begin{align}
\biggl(-\frac{q}{p}+1 \biggr)r_{z} &=\biggl[1-\biggl(\frac{q}{p}\biggr)^{z}\biggr]\frac{\frac{q}{p}-\bigl(\frac{q}{p}\bigr)^{M}}{1-\bigl(\frac{q}{p}\bigr)^{M}} - \biggl[\frac{q}{p}-\biggl(\frac{q}{p}\biggr)^{z}\biggr] \tag{20} \\
\end{align}
Aが$M$枚のコインを所持すると、以降ゲームを続けるうえでAの所持コインが-1枚になることはほぼないので、$M$は大きな整数であると見なせる。
$ q/p<1 $であれば、$(q/p)^{M} → 0$ となるので(20)式は最終的に(21)に変形できる。
\begin{align}
\biggl(-\frac{q}{p}+1 \biggr)r_{z} &=\biggl[1-\biggl(\frac{q}{p}\biggr)^{z}\biggr]\frac{q}{p} - \frac{q}{p} + \biggl(\frac{q}{p}\biggr)^{z} \\
r_{z} &=\biggl(\frac{q}{p} \biggr)^{z} \tag{21} \\
\end{align}
また、(20)式を変形すると(22)式になる。$ q/p>1 $であれば, $ (q/p)^{M} → +∞ $となるので 最終的に$r_{z}$は(23)式が導出できる。
\begin{align}
\biggl(-\frac{q}{p}+1 \biggr)r_{z} &=\biggl[1-\biggl(\frac{q}{p}\biggr)^{z}\biggr]\frac{\bigl
(\frac{q}{p}\bigr)\frac{1}{(\frac{q}{p})^{M}}-1}{\frac{1}{\bigl(\frac{q}{p}\bigr)^{M}}-1} + \biggl(\frac{q}{p}\biggr)^{z} -\frac{q}{p} \tag{22} \\
r_{z} &=1 \tag{23} \\
\end{align}
3.2 p=q のとき
Aがゲーム開始時にz枚のコインを所持していた場合、(15)式から(24)式が得られる。
\begin{align}
r_{z} &=r_{0}+\sum_{i=1}^{z-1}(r_{0}-r_{-1}) \tag{24} \\
\end{align}
前述の議論のとおり、$r_{M}=0, r_{-1}=1$ なので下記記述の過程を経てより$r_{0}$を算出する。
\begin{align}
r_{M} &=r_{0}+\sum_{i=1}^{M-1}(r_{0}-r_{-1}) \\
r_{M} &=r_{0}+(r_{0}-r_{-1})(M-1) \\
0 &=r_{0}+(r_{0}-1)(M-1) \\
\end{align}
以上より、$r_{0}=1-1/M $ を導ける。いま、Mは大きな整数であると解釈できるので結局$r_{0}=1$と見なすことができる。
★☆★☆★ まとめ ☆★☆★☆
以上より、Aがゲーム開始時にz枚のコインを所持していた場合、Aがいつか破産する確率(Aの所持コインがいつか-1枚になる確率)は、下記の通りになる。
r _{z} = \left\{
\begin{array}{ll}
1 & (p ≦ q) \\
\bigl(\frac{q}{p}\bigr)^{z} & (p>q)
\end{array}
\right.
4.まとめ
本記事では、攻撃者のチェーンがより長い善良なチェーンに追いつく確率を「ギャンブラー破産問題」の理論を使って算出した。攻撃者の新規のブロックを生成する確率が善良者のそれよりも等しいかそれ以上であれば、確実に攻撃者のチェーンがいつか善良者のチェーンよりも長くなってしまうことを数学的に導くことができた。つまりブロックチェーンネットワークの半分以上を支配すれば、確実にネットワークを乗っ取ることができることを示している。