0. 背景

ヒカリエには毎日お弁当屋さんがきてくれます。（１個500円）
「いつもありがとうございます。」
と、元気に挨拶してくれる、金髪の原宿系おばちゃんもいます。

だいたい皆、1000円札か500円玉でお弁当を買ってます。
そこで、「このおばちゃんは、何枚の500円玉を持っていればお釣りに困ることはないのか？」
そう疑問に思ったのがキッカケです。

というわけで、ビットコインの原著論文に用いられているアルゴリズムを使用して、おばちゃんがお釣りとして用意しておくべき500円玉の数を算出することにしました。

1. サマリ

1.1. 記事の目的

おばちゃんが必要な500円玉の数を算出すること。 (｀・ω・´)ｷﾘｯ

1.2. やったこと

• ブロックチェーンの原著論文を読んだ
• ブロックチェーンの数学的証明を使って、お弁当屋さんのおばちゃんが必要な500円玉の枚数を算出した
• それを通じて、原著論文の11章を可能な限り嚙み砕いた（←now）

1.3. この記事を読んで嬉しいこと

• ブロックチェーン51%攻撃の背景をなんとなく理解できる
• ヒカリエのお弁当屋さんのおばちゃんに感謝される
• ニュースを見て、「あぁ、51%攻撃ね。知ってる、知ってる。」って言える

1.4. 結論

• 10枚くらい用意しておけばいいんじゃね？

2. ブロックチェーンと弁当屋のおばちゃんの関係

2.1. 前提となる情報

この記事の中では、ブロックチェーンを詳しく解説しないです。
「ブロックチェーンが成立している状態とは、一番長いブロックがつながっている状態である。」
ということだけ使って書いていきます。

51%攻撃というは、一番長いブロックが攻撃者によって繋がれた場合のことを指します。要は、改竄し放題やりたい放題してる状態です。

今回は、
原著論文の11章において、この状態が成立しないことを示した証明の流れを援用して、
お釣りに必要な500円玉の数を算出しました。

2.2. ブロックチェーンと弁当屋のおばちゃんの関係

ブロックチェーンが成立していることを証明することと、
お弁当屋さんのおばちゃんのお釣りの関係について。

ブロックチェーンにおける善良なプレイヤーと悪意を持つプレイヤーによって、
それぞれ伸ばされたブロックの差が焦点になります。

この差が0になったら、攻撃者の勝ちになり、
攻撃者によって、ブロックチェーンはうぇいうぇいされます。

ここで、ブロックの差をQnとしておくと、
善良なプレイヤーによって、ブロックが伸ばされると、Qnは +1
悪意を持つプレイヤーによって、ブロックが伸ばされると、Qnは -1
になります。

ここで、
おばちゃんがお釣りのために持つ500円玉の数について考えます。

ここで、おばちゃんが持つお釣りの500円玉の枚数をQnとしておくと、
1000円札で払うと、Qnは -1
500円玉で払うと、Qnは +1
になります。

要は、
ブロックチェーンの正当性を証明することと、ヒカリエのおばちゃんのお釣りを議論することは全く同じ事象で説明できるということです。

2.3. 原著論文の分かりにくい理由

基本的に、初見殺しです。
たとえば、↓

The race between the honest chain and an attacker chain can be characterized as a BinomialRandom Walk. The success event is the honest chain being extended by one block, increasing itslead by +1, and the failure event is the attacker's chain being extended by one block, reducing thegap by -1.The probability of an attacker catching up from a given deficit is analogous to a Gambler's Ruin problem. Suppose a gambler with unlimited credit starts at a deficit and plays potentially aninfinite number of trials to try to reach breakeven.
（11章. Calculationsより）

完全に「ふぁっ？」となります。
ギャンブラーの破産確率を全人類が知っている前提に書かれてます。

事前知識がない状態で読んでもよく分からず、睡魔との戦いになってしまいます。
（そこらへんの事前知識がなくても、なんとなく原著論文の11章を理解できるようにしたいっ!!ってのがこの記事の立ち位置です。）

3. ブロックチェーンと弁当屋のおばちゃんの関係

3.1. 攻撃者がどれくらいの割合なら破産するのかを知りたい　~ギャンブラーの破産確率~

ギャンブラーの破産確率というのは、
あるギャンブラーが、持ち金を賭けて、破産するか儲けるかの確率のことらしいです。
調べてみると、1600年代からある問題らしいです。

ギャンブラーの破産確率↓

あるギャンブラーの最初の所持金を2000ドルとする．l回の賭けごとに，勝てば所持金が1000ドル増え，負ければ1000ドル失うものとする．所持金がなくなればギャンブラーは 破産しそこで賭けは終わり、また、所持金が5000ドルになれば賭けは終了とする．このギャンブラーが破産して終了する確率はいくらとなるか.

ブロックが増えたり減ったりしながら攻撃者のブロックが追いつく確率を、
ギャンブラーの破産確率を用いています。

論文中では以下のように書いています。

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

よく分かんないので、
今回のケースに置き直すと

p = ヒカリエの社員が500円玉を出す確率
q = ヒカリエの社員が1000円札を出す確率（お釣りの500円玉が減る確率）
rz = z枚の500円玉を持っている状態から破産する確率

となります。
また、破産確率を算出するのに、
マルチンゲールを利用する方法と漸化式で導出する方法がありますが、
今回は直感的に理解しやすそうな漸化式で破産確率を求めます。

おばちゃんの所持している500円玉の枚数が、k枚（0<=k<=N）になった時に、その後Aが破産する確率をr(k)で表します。
このr(k)について漸化式を立てます。破産確率は以下のような関係にあるので。

r(k)は、k-1枚のときの破産確率とk+1枚のときの破産確率の合計になります。
（なんか、steemitのサービスでは数式のMarkdown認識してくれないので画像で貼ってます。。）

ここで（1<=k<=N-1）について整理すると、

と、なるので、ある定数cは（0<=k<=N）について、

となります。
さらに、一番最初のr(0)=1, r(N)=0から

まとめると、

となります。
・p=q かつk=N/2のときを考えると、破産確率は 1/2 になります。
・N を固定して、kを増加させる（用意しておく500円玉の数を増やす）とき、
破産確率r(k)は k の減少関数になっています。つまり、用意しておく500円玉数が多いと、破産確率が低いということを言っています。

最後に、N→∞の極限を取ると、原著論文の第一式と同じ式が導けます。

つまり、
・r(k)=1：1000円札を出す人が、500円玉を出す人より方多いと破産する
・r(k)=(q/p)^k ：破産確率はpとqの比に依存するが、用意しておく500円玉（k）を多くすると、とりま0になる。
ということがこの式からわかります。

余談ですがこの式から、
ブロックチェーンの51％攻撃が成立している状態とはq(z)=1の状態を指します。（51％攻撃）
そして、ブロックチェーンの攻撃成功には51％も演算能力がなくても、わんちゃんいけんじゃね？ってこともわかります。（25％攻撃）

3.2. 最悪のケースに必要な500円玉の数を出す ~ポアソン過程など~

ブロックチェーンが攻撃可能かなんて、一旦どうでもいいので
おばちゃんに必要な500円玉の数を求めます。

ヒカリエのおばちゃんに、
「毎日何個くらい、お弁当持ってきてはるんですか？」
と、ヒアリングしてきましたが、

「え、日によって違うけど、たくさん！」
という曖昧な答えが帰ってきたので、

仕方なくN→∞（たくさん）
また、自分の肌感的に1000円札を出す人は 30%くらいな気がしますので、
p=0.7
q=0.3
として、進んでいきます！

次に、kの減少関数((q/p)^k)を考えたいところですが、
ここで、現実世界について考えてみたいと思います。

ヒカリエのおばちゃんは、毎日お弁当を持ってきてくれます。
そんな日々の中で1日くらいは、
意味わかんないくらいの人が連続で1000円札を出す日があるはずです。

つまり、おばちゃんにとって上記で求められた500円玉の数を持っていっても、
「1年365日に1日あるかないかの1日を乗り越えることができない」かもしれません。

そこで、連続して1000円札が出される最大のケースを考えます。
このケースはポアソン分布を使用しています。（馬の例が有名です↓）

1年あたり平均0.61人の兵士が馬に蹴られて死ぬ軍隊において、「1年に何人の兵士が馬に蹴られて死ぬかの確率の分布」を求める。

つまり、
「稀にしか起こらないことでも、連続して発生することもあるから、その確率と回数が知りたい。」という時に用いられるものです。
その上で、減少関数を考慮すれば、最悪のケースを考慮していることになります。
（すごく分かりにくくて、すいません、、下図のイメージです。）

例えば、
5枚お釣りがある中で、連続して2人1000円札で払う人がいて（ポアソン過程）、その上で連続して3人1000円札で払う人が生じる確率(q/p)^3
を考慮すれば良くて、そのケースをk=0~∞まで考慮すれば問題ない。ということになります。

では、破産確率をq(z)として、計算していきます。

（なんか、Markdown認識してくれんくなったので、eをexpで表示してます。）
最後に余事象を取ると

と、なり論文の最後の式を導くことができました。

3.3. いよいよ500円玉の数を出す

繰り返しですが、"自分の肌感的"に1000円札を出す人は 30%なので、

p=0.7
q=0.3
として、
最後に破産確率q(z)を求めます。 (｀・ω・´)ｷﾘｯ

0枚：q(z)=1.000
5枚：q(z)=0.177
10枚：q(z)=0.041
15枚：q(z)=0.010
20枚：q(z)=0.002
25枚：q(z)=0.001
30枚：q(z)=0.0002

と、なります。

つまり、
だいたい10枚くらい持っておけば大丈夫！・ω・
という結論になりました。（たぶん）

(余談；
ブロックチェーンの場合も、
善良なチェーンがzブロック伸びるまでの期間に、
悪意のあるチェーン側のブロックがいくつ増えるのかを、ポアソン過程を利用して考慮しています。
同様期待値に従うので、悪意のあるチェーン側が、zブロック差から善良なチェーン側に追いつく確率もお弁当の時と同様になります。）

4. その他諸々

4.1. ブロック生成の比について（pとqの関係）

pとq は、善良ノードと攻撃者ノードがそれぞれ単独でブロックを生成する平均頻度の比、（CPU能力の比）になるそうです。

4.2. ビットコインのブロック承認の個数

え、ビットコインって攻撃余裕じゃね？って思ったので調べてみると
ビットコインは、6段階の認証（ブロックのつながりを最低6つ担保してる）らしく
「おう、すまんかった。」
って、なりました。

4.3. 現在のブロックチェーン（2018年6月 現在）

去年の今頃には、とりあえず"仮想通貨"と名前の付くものは値が上がりましたが、
一旦、今はその勢いを潜めているように思えます。

むしろ、最近では51%攻撃や25%攻撃などといった謎の単語が行き交い、
人の不安を煽るような記事とかが乱立し始めて、全体の雰囲気としてはすごく良くないなぁと思います。

その一方で、
異なるトークンを紐付ける0xとかのプラットフォームは整いつつありますし、
異なるブロックチェーンを紐付けるPolkadotとかのプロジェクトも走り続けているので、
個人的には、落胆するにはまだ早いというか、まだまだこれからの話なのかなぁ〜と。

ブロックチェーンの強みを最大限に活用したサービスも、
まだ大々的には出てきている訳ではないのですし。

以上、ブロックチェーンの数学的証明を使って、お弁当屋さんのおばちゃんが必要な500円玉の枚数を算出しました。

（ところどころ、間違いや良く分かってないところもあるので、適宜修正していきます。）