数学者向けにblock chainの原理についてまとめてみた

※slackにがーーーーーーっと打ち込んだものの転記なのです。
ちょいちょい見づらいのは許してください。

原論文：Bitcoin: A Peer-to-Peer Electronic Cash System
https://bitcoin.org/bitcoin.pdf 

## 用語の定義

Transaction：データ。
bitcoinの場合、お金のやり取りデータ。なので（？）Transactionと呼ばれる。

HASH化アルゴリズム：データからデータへの写像。特に以下を満たすものをそう呼ぶ。
- inputからoutpupを計算するのは簡単
- outputを与えたとき、それを実現するinputの構成が非常に困難

bitcoinの場合、SHA256と呼ばれるHASH化アルゴリズムが使われる。
この場合、outputは意味のないランダムに見える文字列。

HASH値：とあるデータに対してHASH化アルゴリズムを適用した結果得られるデータ。

nonce：特に意味を持たないデータ

block：「何らかのデータのHASH値」、「nonce」、「Transaction」×n、からなるデータ。
ただし、このblockのnonceは、blockから得られたHASH値が一定の条件を満たすようなもののみを許容する。
bitcoinの場合、「HASH値の最初の一定文字が全て0」という条件が課される

block chain：次の条件を満たすblockの列 $(B\_n)\_{0 \leq n \leq N}$
- 全ての $n(<N)$ に対し、 $B\_{n+1}$ の構成要素である「何らかのデータのハッシュ値」が、 $B\_n$ のハッシュ値に一致する


## block chainをbitcoinでは次のように利用。
### 基本の原理

（はじめに、block $B\_0$を用意。）

いま、block chain $(B\_n)\_{0 \leq n \leq N}$がある状態とする。
このblock chainに対して、

pre-block：「$B\_N$のハッシュ値」、「Transaction」×nからなるデータ

とする。

計算機を用意する。

pre-block $B$ として、Transactionが0つのものを用意。

計算機はつねに以下の2つを続ける。

Transactionが発生するたびに、そのTransactionをpre-block $B$ に加える。（加えたものをまた $B$ と書く。）

pre-block $B$ に対し、nonce $x$ であって、 $B$ に $x$ を加えたblockを $B\_{N+1}$ としたとき、 $(B\_n)\_{0 \leq n \leq N+1}$ がblock chainとなるような $x$ を探す。

上記のようなnonce $x$ が発見されたら、 $(B\_n)\_{0 \leq n \leq N+1}$ を所与のblock chainとして、上記を繰り返す。


[21:04] 
これによって、全てのTransactionが含まれたblock chainが生成され続ける。

[21:05] 
Transactionとは、bitcoinのやり取りの履歴（誰から誰へいくら。とか。）であったことを思い出す。
すると、このblock chainは、全てのbitcoinのやり取りの履歴を保持したものになる。

[21:05] 
これが、bitcoinの台帳になる。

[21:06] 
ここまでに話したものが、計算機が1台の場合のblock chain。

[21:06] 
### 以下、計算機が複数ある場合のblock chain。

[21:06] 
計算機を複数用意する。


sugiyama [21:19] 
全ての計算機 $C$ は、以下を繰り返す。
- block chain $(B^C\_n)\_{0 \leq n \leq N\_C}$ と、それに対するpre-block $B^C$ を持つ。（block chainは計算機 $C$ ごとに異なる可能性もある）
- block chainに記録したいTransactionが生成された場合、他の計算機にそのTransactionのデータを渡す。
- 計算機 $C$ がTransactionを受け取った場合、pre-block $B^C$ にそのTransactionを加える。また、もらったTransactionを更に別の計算機に伝達する。
- nonce $x^C$ であって、pre-block $B^C$ に $x^C$ を加えたものを $B^C\_{N+1}$ としたときに、 $(B^C\_n)\_{0 \leq n \leq N\_C+1}$ がblock chainになるものを探す
- nonce $x^C$ が見つかった計算機は、 $n \leq N$ のblock $B\_n$ と、 $B\_{N+1}$ の中にあるTransactionデータが整合的な場合（同じTransactionが2つはいっていない、Transactionの結果、bitcoin残高が負にならない等）のみ、block chain $(B^C\_n)\_{0 \leq n \leq N\_C+1}$ を他の計算機に渡す。（そうでない場合はどうする？pre-blockを破棄？）
- block chainを受け取った計算機 $D$ は、以下を行う。
  - $N\_D < N\_C+1$ であった場合、block chain $(B^D\_n)\_{0 \leq n \leq N\_D}$ を破棄し、受け取ったblock chainを新たに $(B^D\_n)\_{0 \leq n \leq N\_D}$ として保持する。（その際、旧い $(B^D\_n)\_{0 \leq n \leq N\_D}$ に含まれていて、新しい $(B^D\_n)\_{0 \leq n \leq N\_D}$ に含まれていないTransactionを自分の新しいpre-blockに加え、また、他の計算機に伝達するといい気がする）
  - $N\_C+1 \leq N\_D$ の場合は受け取ったblock chainは破棄。


[21:23] 
こうしておけば、つぎの2つの仮定：
- ある時間 $T$ が存在し、全てのデータは $T$ 以内に全ての計算機へ渡る
- block chain内にあるTransactionを改竄しようと試みる勢力CPU（の計算能力）が全体の50%未満

の下で、

- 任意の $M \in \mathbb{N}$ に対して、ある一定時間 $T_M$ が経過したあとは、全ての計算機のblock chainの $n<M$ の部分は共通となる。
- 全てのTransactionはその発生から有限時間の間に全ての計算機のblock chainの（上記の意味での）共通部分に組み込まれる
- 一度block chainの共通部分に組み込まれたTransactionは、その後ろに組み込まれたblockの個数が増える極限で改竄可能性が0に収束する

とかそんな感じな気がする。
（適当に書いたので、これが証明できるかは知らない）

[21:25] 
これを以てして、Trustlessでも改竄可能性が極めて低い（事実上0）なデータの集合を構成することができるという主張の根拠か。


[21:25] 
アルゴリズム面は、そんなとこですね。たぶん。たぶん。ホントか？