title: Christieによるブロックチェーンの実装 
author: 赤堀 貴一
profile: 並列信頼研
lang: Japanese
code-engine: coderay

# 目次

- 研究目的
- ブロックチェーンとは
- コンセンサスアルゴリズム
- Christieとは
- TopologyManagerの実装
- PCクラスタ上でPaxosを動かした話
- まとめ

# 研究目的 OS単位での分散システム

- コンピュータのデータに不整合は起こりえます. 不整合は誤操作や, 複数人によるデータの同時書き込みによって起こる.
- ブロックチェーンはデータを分散でき, 不整合の検知が可能である.
- 当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある.
- Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムを構成することが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの不整合を検知できる.
- よって, Christieにブロックチェーンを実装する.

# ブロックチェーンとは

ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているノードが保持する技術である.

ノード同士はP2Pでつながっており, 対等である. そのため, 管理者がいなくてもデータの管理が行える.

# ブロックチェーンとは

<div style="text-align: center;">
    <img src="./images/blockchain.svg" alt="blockchain" width="800">
</div>

# ブロックチェーンとは

ブロックチェーンにも種類がある. パブリックブロックチェーンとプライベートブロックチェーンである. 以下に, その違いを述べる.

|  | パブリックブロックチェーン | プライベートブロックチェーン |
|:-----------:|:------------:|:------------:|
| ノードの参加権 | 誰でも参加可能 | 許可された場合のみ参加可能 |
| コンセンサス | 遅い | 速い |

細かい違いは色々あるが, ほとんどはこの2つの違いから生まれる.

# コンセンサスアルゴリズム

- コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである.
    - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.
    - 故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.
- Proof of Workを使っているパブリックブロックチェーンは「ブロックが多ければ多いほど」, レベル4に近づく.

# プライベートブロックチェーンのコンセンサスアルゴリズム

- プライベートブロックチェーンは管理者が許可するノードしか参加しない. つまり, レベル3のコンセンサスアルゴリズムで十分.
- 新しいブロックもパブリックブロックチェーンより早く作れる.
- Paxosを実装しました.

# Paxos

- Proposerが値を提案する.
- Acceptorが値を決める.
- Learnerが決めた値を集計して, 多数決により値を選択する.

これによって, 値が一意に決まる.


# Christieとは

- 研究室で使っていたAliceの問題点を解消した, 分散プログラミングを簡単に書けるjavaのフレームワーク.
- Continued based C(CbC)と似た書き方が可能. DataGearという単位でDataの移動ができる.
- まだAliceから引き継いでない機能でTopologyManagerというものがある. これは, Topologyを構成するための機能.
- 簡単に言えば, ノード間の配線をしてくれる. 分散環境上で実験を行いたい場合に便利なため, これを実装してからPaxosを実装した.

# TopologyManagerとは

- TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る.
- TopologyManagerはdotファイルというものを読み込んで, そのとおりにTopologyを生成する.

```
digraph test {
	node0 -> node1 [label="right"]
	node1 -> node2 [label="right"]
	node2 -> node0 [label="right"]
}
```

<div style="text-align: center;">
    <img src="./images/ring.svg" alt="blockchain" width="800">
</div>



# Christieによる実装の利点

ブロックチェーンの実装に伴ってわかったChristieの利点を述べる.

- ブロック, トランザクションを送るのが簡単. ChristieはDataGearという単位でデータを保持するため, データ構造に@Messageを付け, putすることでデータの送信ができる.
- TopologyManagerでのテストが便利. dotファイルが有れば, TopologyManagerが任意の形でTopologyを作れる. そのため, ノードの配置について理想のテスト環境を作ることができる.
- ソースコードの機能ごとにファイルが実装できるため, 見通しが良い. ChristieはCbCのgotoと同じように関数が終わるとsetupによって別の関数に移動する. そのため自然に機能ごとにファイルを作るため, 見通しが良くなった.

# Paxos実験1

<div style="text-align: center;">
    <img src="./images/paxos1.svg" alt="blockchain" width="800">
</div>

# PCクラスタ上でPaxosを動かした話

- ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした.
- 評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックごとにコンセンサスをとっても良い.
- 今回は単純化のために, 整数でコンセンサスを取る.
- また, ノードはproposerが2つ, acceptorが3つ, learnerが1つという構成で実験した.
- その結果, 値が一意に決まることがわかった.

# まとめ

- Christieを用いてコンセンサスアルゴリズムのPaxos, ブロック, トランザクション, proof of workも実装しました.
- これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装できます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れる. 2つ作って速度比較も行える.