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

# 目次

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

# OS単位での分散システム

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

# ブロックチェーンとは

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

ブロック同士はハッシュでつながっている. そのため, 1つのブロックが変更されると, それ以降のブロックの整合性が保たれないため, そのHashを調べることで不整合を検知できる

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

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

- コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである.
    - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.
    - 分散環境に故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. 
        - 故障が起きない.
        - 任意のマシンが故障し, メッセージを受信したり送れない可能性がある.
        - メッセージに遅延が発生する. そのため, マシンが壊れたのかどうか処理に時間がかかっているのかわからない.
        - 悪意あるマシンがいる可能性がある.
    - Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.

- 

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

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

# Paxos

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


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


# Christieとは

- 分散プログラミングを簡単に書けるjavaのフレームワーク.
- 研究室で使っていたAliceの問題点を解消した.
    - データの取り出しをアノテーションを用いてシンプルに記述することができるようになった. そのため, ソースコードの可視性が上がった.
    - テストが簡単になった. AliceではLocalDataGearManagerを一つしか持てないため, LocalDataGearManagerの通信のテストが難しかった. Christieは複数のLocalDataGearManagerを持てるようになったため, 1つのアプリケーション内で分散のテストができるようになった.
- 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="300">
</div>

# Christieによる実装の利点

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

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


# PCクラスタ上でのPaxosの実行

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

# Paxos実行結果1

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



# まとめ

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