# オペレータノードコンセンサス・アルゴリズム

###### tags: `Yellow paper` `オペレータノード`

Ref:
https://hackmd.io/eYGLs-vMTjSuiAl9ueTzjw#%E3%82%AA%E3%83%9A%E3%83%AC%E3%83%BC%E3%82%BF%E9%96%93%E3%81%AE%E9%80%9A%E4%BF%A1

## 要件
SRUオペレータノードの合意形成・同期仮定について定義する。
- **単一障害点があってはならない。**
- システムが単一のオペレータの故障によって停止ないしは不正が発生できてはいけない。
- つまり、単一ノードのビザンチン障害に対応できなければならない。
- **ブロック生成を行うリーダーが選出されていなければならない。また、そのリーダの情報が各ノードで合意のもと同期されてなければならない。**
- 上記と組み合わせて、リーダ選出について単一障害点があってはならない。つまり、リーダが故障した場合に、次のリーダが現実的時間内に選出されなければならない。
- **正常な各ノードは、常にそのノードを介してユーザが Exit 可能な情報を持っていなければならない。**
- つまり、正常なノードは最新のコミットについてのステート(変更履歴SMT含む)を保有していなければならない。
- 各 commit(offchain commit 含む)ごとに正常なノードは同期されてなければならない。

## SPFT
Lightning Network とそのメッセージングを使うことで、単一障害点耐性のある分散システムを構築する。

## リーダ選出アルゴリズム

### リーダノードの役割
リーダノードは次のことを行う。
1. Received Tx
- 各 Tx について、現在の state から状態遷移を計算する。
2. Light L1 commit(old: offchain commit)
- Tx をまとめ上げた Offchain commit を作成し他ノードにブロードキャストする。
- Offchain commit のしきい値署名1/2を集めて L1 に commit する。(疑似Finality)
3. L1 commit
- Offchain commit をまとめあげた L1 commit を作成し Ethereum に commit する。
- その commit を他ノードにブロードキャストする。(これは Ethererum L1 の Event 見れば良いのでいらないかも)

### 非リーダノードの役割
非リーダノードは次のことを行う。
1. Received Tx
- 受け取った Tx をリーダノードに渡す。
2. Light L1 commit(old: offchain commit)
- リーダノードから受け取った Offchain commit を検証し、ステートをアップデートする。
- 検証が完了したらリーダノードにしきい値署名を送る。
3. L1 commit
- リーダノードから L1 commit を受け取りステートをアップデートする。

### 選出方法

**方針**
最新の L1 commit のハッシュ値を seed としてリーダ順列を作成し、Lightning node でオペレータのリストを評価する。

各オペレータは自身のチャネルの連結情報(open channel tx)を broadcast する。各ノードは受け取った情報から Bitcoin の merkle proof をもとに open channel tx の検証を行う。オペレータがチャネルを閉じていることの証明は close channel tx を broadcast する。これらの情報の
boradcast は任意のノードが任意のノードの連結情報に対して可能とする。また、他人によって非SRUオペレータがSRUオペレータとして繋がれないように SRU オペレータはノードになる際に自身の署名による連絡を行う。**また、各チャネルはチャネルオープン時の tx と LN node を紐付ける gossip を行うために public channel として開く必要がある。**

ref: [PublicChanel(channel_announcement)](https://github.com/lightning/bolts/blob/master/07-routing-gossip.md#the-channel_announcement-message)

<!-- |occupancies|{node: string, occupacy: uint128}[]|各ノードの稼働率|
-->

#### 評価アルゴリズム

評価アルゴリズムにはビットコインのセキュリティレベルで取得可能な次の要素を元に決定する。

|name|type|remarks|
|:--:|:--:|:--:|
|channels|{ v1: string, v2: string capacity: uint32 }[]|openしているチャネルのリスト。各要素は辺の端点のアドレス情報とBTCの流量を持つ。|

チャネル情報をもとに生成されるグラフから各ノードの評価を求める。

1. `channels` の情報から各頂点についてP=capの総和となる双方向グラフを作成する。
3. Pagerank を適用する。
4. 上位20%且つ評価値が0より大きいノードをリーダー候補として、アドレス降順にソートする。
5. ソートしたリーダ候補について seed から求めた順列に従ってリーダを決定する。

Pagerank: https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%A9%E3%83%B3%E3%82%AF

##### 以下参考資料:
グラフの中心性概念
http://bin.t.u-tokyo.ac.jp/startup17/file/2-1.pdf (47P~)
https://tjo.hatenablog.com/entry/2015/12/09/190000

### 辺/頂点の追加/削除

SRU オペレータを立ち上げ、他のオペレータノードにチャネルを接続した後に open channel tx を broadcast することで自身のノードをSRUオペレータとして追加することができる。 open channel tx / close channel tx それぞれにおいて誰が broadcast しても問題ない。

#### 頂点の追加
そのノードの署名付きでSRUオペレータとして参加することを broadcast する。
最初の時点では評価値0の孤立ノードとして追加される。

#### 辺の追加

open channel tx の inclusion proof を broadcast を提出する。open channel tx の重複登録がないことを確認して辺を追加する。端点が新規のノードである場合はノードも追加する。

#### 辺の削除

close channel tx の inclusion proof を broadcast を提出する。対応する open channel tx で開かれたチャネルが閉じられたことを検証し、対象の辺を削除する。

## 同期の通信フロー

### Initialize
初期データをvalid なノードからダウンロードする。

Note left of Node: Initialize
Node->Other node: fetch latest datum
Other node-->Node: latest datum

### Received tx
トランザクションをノードが受け取ったとき、そのトランザクションをリーダノードに send する。
tx を受け取ったノードはそれをローカルDBの transaction pool に保存する。

Note left of Node: Received tx
Node->Leader: send tx
Leader->Leader: save into tx pool

### Offchain commited
そのノードがオフチェーンコミットを行った時に、オフチェーンコミットの中身を broadcast する。
offchain commit を受け取ったノードは commit 情報が valid であるかを検証し、それをもとにローカルDBのステートをアップデートする。(finalized)
また、閾値署名をリーダに送信しリーダは1/2以上の閾値署名によって L1 に light commit を提出する。

Note left of Leader: Offchain committed
Leader->Gossip: offchain commit info
Gossip->Others: offchain commit info
Others->Others: verify commit
Others-->Leader: signed threshold hash(offchain commit)
Leader->Ethereum: light commit
Others-->Ethereum: confirm commit
Others->Others: commit db

### L1 commited
そのノードがL1 commit を行った時に L1 commit の中身を broadcast する。
L1 commit を受け取ったノードは commit 情報が valid であるかを検証し、それをもとにローカルDBのステートをアップデートする。(finalized)

Note left of Leader: L1 committed

Leader->Gossip: L1 commit info
Gossip->Others: L1 commit info
Leader->Ethereum: L1 commit
Others->Others: verify L1 commit
Others-->Ethereum: confirm commit
Others->Others: commit db

## Gossip について

Lightning のコントロールメッセージを使用する。
c-lihgtning の sendcustommsg RPC とプラグイン機能にあるcustommsgフックで実装する。
参考：
https://lightning.readthedocs.io/lightning-sendcustommsg.7.html

## ローカルDB

以下参照： [分散ストレージに保存するデータ種別
](https://hackmd.io/RUzKWv6yQoK6MumW1oFWMQ?view#%E5%88%86%E6%95%A3%E3%82%B9%E3%83%88%E3%83%AC%E3%83%BC%E3%82%B8%E3%81%AB%E4%BF%9D%E5%AD%98%E3%81%99%E3%82%8B%E3%83%87%E3%83%BC%E3%82%BF%E7%A8%AE%E5%88%A5)