title: Christieによるブロックチェーンの実装 
author: 赤堀 貴一
profile: 琉球大学 工学部 情報工学科
lang: Japanese
code-engine: coderay

# 目次

- 研究目的
- ブロックチェーンとは
- ブロックチェーンのfork
- コンセンサスアルゴリズム
    - Proof of Work と Paxos
- 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="1000" height="600">
</div>

# ブロックチェーンとは

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

|  | パブリックブロックチェーン | プライベートブロックチェーン |
|:-----------:|:------------:|:------------:|
| ノードの参加権 | 誰でも参加可能 | 管理者(単数 or 複数)によって許可された場合のみ参加可能 |
| コンセンサス | 遅い | 速い |

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

# ブロックチェーンのfork

ブロックがいたるところで作られると, 異なる高さの違うチェーンが複数できる. この状態をforkという.

forkが起こった場合, どちらかを正しいものとしてブロックを積み上げたい. そのため, コンセンサスアルゴリズムを用いて, どちらか1方に統合する.

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

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

# パブリックブロックチェーンのコンセンサスアルゴリズム

- パブリックブロックチェーンのコンセンサスアルゴリズムは, 「ある程度ブロックの差がついたら, 長い方を正とする」というもの.
- これだけだと, 裏切り者が適当なブロックをガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.
- Proof of Workは, 簡単に言えばブロックのHashに条件をつけるアルゴリズム. つまり, 新しいブロックを作るのが難しくなる.
- 新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しい. ただし, トランザクションの確定が遅い.

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

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

# Paxos

- Lamport先生が「故障モデルレベル3での合意が不可能なのを証明してやる」と言って証明の途中で逆に編み出してしまったらしいアルゴリズム.
- レベル3のアルゴリズムの基礎となっている.
- proposerが値を提案し, acceptorが決め, Learnerが集計し, 多数決を取って決まった値を保持.


# Paxos
とりあえず, このアルゴリズムで値が一意に決まる.

# Christieとは

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

# TopologyManagerとは

- TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る.
- TopologyManagerは静的Topologyと動的Topologyを作れる.
- 静的Topologyはdotファイルというものを読み込んで, そのとおりにTopologyを生成する.
- 動的Topologyは参加を表明したノードを動的に配置する. が, 今はTreeしか実装していない.

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

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

# Paxos実験1

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

# Paxos実験2

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

# Paxos実験3

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

# まとめ

- コンセンサスアルゴリズムのPaxosを実装しました.
- ブロック, トランザクション, proof of workも実装しました. ただ, トランザクションはファイルのデータを読めるようにはしていません.
- これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装されます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れます.