Blockchain

数学者向けに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]
アルゴリズム面は、そんなとこですね。たぶん。たぶん。ホントか?