NEW KIND OF NETWORK( $NKN )のオートマトンを利用したネットワーク構造を数学で見ていく。
New Kind of Network(NKN)というブロックチェーンがありまして、一体どこがNew Kindなのか気になったのでホワイトペーパーをあさって調べてみました。
工学部で習う内容に触れる記事となっていますので、ちょっと難しく感じられるかもしれません。
しかし、かなり面白いと思うので、もし興味がございましたら読んでみてください。
かくいう私も情報理工学専攻ではないため、間違いも多々あると思います。間違った点があれば心置き無く教えていただければ幸いです。
NKNとセルオートマタネットワーク
分散化されたネットワークを自然発生させる際、効率的なモデルを考える必要がある。それはセルオートマタネットワークで実現できる。（３次元のオートマタらしい）
それについてじっくりと説明していく。
ネットワーク形状とその接続規則
N個のノードから形成されるネットワークは、NxNの正方行列Aで表現できる。単位ステップあたりにネットワーク形状は変化する。その変化は、Aの形状変化がマルコフ連鎖*1である場合、ルールを
A(t+1)=f[A(t)] ・・・①
で表現できる。
このとき、それぞれのノードの形状変化は、隣り合うノードの状態によってのみ決まるようにしたい。なぜかというと、そうしないとネットワークがローカルでなくなるからである。
ところで、①の表し方だと、fがAと独立なので、Aの状態変化が内部状態によらずに形状のみで決まってしまう。
形状変化は、Aの形状（トポロジー）と内部情報の両方を加味して行いたい。だから、マルコフ連鎖のルールfは次のように書き換えるべきである。
A(t+1)=f[A(t),S(t)]
S(t+1)=g[A(t),S(t)]
ここで、S(t)は要素数Nからなるベクトルで、t秒におけるAのN個のノードの状態が格納されている。
fは形状（トポロジー）の変更ルールで、gは状態の変更ルールである。fとgどちらも、ノードの変更では隣接ノードの情報のみによって決まるようにして、ネットワークのローカル性を維持する。
つまりは各ノードiは自身の状態Siと近隣ノード（{ j | Aij ≠ 0 }となるノードSj）の状態を知っていればいい。
ここで、ブロックチェーンにおける新規ブロックの認証プロセスを考えたい。ブロックを受け取ったノードは電子署名を用いて隣接ブロックにブロックを手渡すが、それには「競合するブロックがないか」「ブロックが承認されているか」などの基準が設けなけなければならない。
NKNのネットワーク成長過程を紹介する前に、一般的なネットワークオートマトンについて紹介する。
まず、初期状態(t=0)として、下記(FIG.6.)のように８つのノードが立方体の頂点に配置され、立方体の線分で結ばれている形状を考える。
この状態にどんどんノードを追加していく。追加して行った時の形状は、下の写真のように変化のルールの内容によって大きく異なる（FIG.7.）。
(a)はrule1655146で1573ステップ変化させた場合。（リング型トポロジー）
(b)はrule1655185で1537ステップ変化させた場合。（擬似ランダムトポロジー）
NKNのネットワーク構造の変化
ルールは以下の二つの情報に従って動くようにする。
・新規ノードから与えられた情報
・すでにあるノードが持つ情報
しかし、そのルールを作るのは非常に難しい。ちょっとルールを変えるだけで全く違う形状になってしまう。下の写真。少しルールを変えるだけで構造が随分と変わる。
ブロックチェーンネットワークの現実的な運用のため、このネットワーク(CAoN)においては、各ノードが同期して状態を更新しない。つまり、各ノードは非同期に状態を更新する。
数学的な簡単さは損なわれるが、実際の利用に耐えうる。
ネットワークの自己組織化
ネットワークを最も効率的にするにはどうすればよいだろうか。
ネットワークの形状は、その複雑さλによって４種類に大別できる。
λ=0は複雑さ０の不動点で、λが増すごとに周期的、複雑、カオスというクラスに移行する。*2
全く情報がない不動点と、完全にランダムでノイズしかないカオスの中間に、最も情報の多い状態を含んでいる部分があるはずである。それをカオスの縁と呼び、λ=λc(≒0.3)で表される。カオスの縁にある系の多くは、チューリング完全である。*3カオスの縁は、"複雑"の段階にある。
下の写真(FIG.10)はそれぞれの状態における二次元オートマタの形状で、Class-4となっている部分がカオスの縁が含まれる、"複雑"の部分である。
効率的で長きに渡る運用が可能なネットワークを形成するには、ネットワークの状態がカオスの縁にある必要がある。
ルールによって、ネットワークが永続的にカオスの縁にあるようにネットワークを自己組織化することができる。つまり、分散化システムのための理想的なネットワークをオートマトンにより形成できる。
CAoNによって複雑なまま成長するネットワーク（FIG.11）
続きはまた今度書きます！ 書いてと催促があればもっと頑張るかも、、。
参考文献：NKN_Whitepaper.pdf
