title: 分散ネットワークChristieによるBlockchainの実装
author: Takahiro Ikki, Shinji Kono
profile: 琉球大学
lang: Japanese
code-engine: coderay

## 研究目的

- コンピュータのデータの不整合は, 誤作動や複数人によるデータの同時書き込みによって発生し, 特に分散環境下で問題となる.
- ブロックチェーンはデータの分散ができ, 不整合の検知が可能な仕組みとなっている.
- 当研究室で開発中のGearsOSの分散システムの技術として, ブロックチェーンが使用できるか調査中である.
- 将来的にGearsOSに組み込む予定のある分散フレームワークChristieに分散フレームワークを実装することにした. (?次にも同様の記述がある)

<!--
# OS の拡張性と信頼性の両立

-->

## Christie
- Christieは当研究室で開発している分散フレームワークである.
- 現在はjava上で開発されているが, GearsOSに組み込む予定があるため, 言語Continuation based Cへ書き換え可能な構成となっている. (?GeasOSの解説がより欲しい？)
- 言語CbCと近い概念として以下の概念が存在する。
  - CodeGear(以下CG)
  - CodeGearManager(以下CGM)
  - DataGear(以下DG)
  - DataGearManager(以下DGM)

## Christieの言語概念
- CGはスレッド, クラスに相当し, javaの継承を用いて記述する.
- DGは変数データに相当し, CG内でアノテーションを用いて変数データを取り出せる.
- CGMはノードであり, DG, CG, DGMを管理する.
- DGMはDGを管理するものであり, putという操作により, 変数データ(DG)を格納できる.
  - DGMにはLocalDGMとRemoteDGMが存在する。LocalDGMは各ノード固有のデータベースである。RemoteDSMは他ノードのLocalDGMに対応するproxyであり、接続しているノードの数だけ存在する。
  - DGMのput操作を行う際にはLocalとRemoteのどちらかを選ぶ.Localであれば、LocalのCGMが管理するDGMに対しDGを格納し, Remoteの場合は接続したRemoteさきのCGMのDGMにDGを格納する.

## DGM
- RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。
- 立ち上げ後はManager名を指定してDataSegmentAPI用いてDSのやり取りを行うため、プログラマはManager名を意識することでLocalへの操作もRemoteへの操作も同様に扱える。

## DGのアノテーション
- DGを取り出す際にはCG内で宣言した変数データにアノテーションをつける。DGアノテーションには
Take、Peek、TakeFrom、PeekFrom、の4つがある。
  - Take
    - 先頭のDGを読み込み、そのDGを削除する。
  - Peek
    - 先頭のDGを読み込むが、DGが消去されない。そのため特に操作をしない場合、同じデータを参照し続ける。
  - TakeFrom
    - Takeと似ているが、Remote DGM nameをしているすることで、その接続先のDGM からTake操作をおこえる。
  - PeekFrom
    - Peekと似ているが、 Remote DGM nameをしているすることで、その接続先のDGM からPeek操作をおこえる。

## Christieのコード例
```code
package christie.example.HelloWorld;

import christie.codegear.CodeGearManager;
import christie.codegear.StartCodeGear;

public class StartHelloWorld extends StartCodeGear {

    public StartHelloWorld(CodeGearManager cgm) {
        super(cgm);
    }

    public static void main(String[] args){
        CodeGearManager cgm = createCGM(10000);
        cgm.setup(new HelloWorldCodeGear());
        cgm.getLocalDGM().put("helloWorld","hello");
        cgm.getLocalDGM().put("helloWorld","world");
    }
}

```

## Annottation
- ChristieではInputDGの指定にはアノテーションを使う。
- アノテーションとはクラスやメソッド、パッケージに対して、付加情報を記述できるJavaのMeta Computationである。
- 先頭に@をつけることで記述し、オリジナルのアノテーションを定義することもできるInput
となる型の変するを直接宣言し、変数名としてkeyを記述する。その上にアノテーションでTakeもしくはPeekを指定する。
```code
@Take
public String name;
```
```code
@TakeFrom("remote")
public String name;
```

## TopologyManager
- TopologyManagerとはTopologyを形成するために、参加を表明したノード、TopologyNodeに名前を与え、必要があればノード同士の配線を行うノードである。
- TopologyManagerのTopology形成方法として、静的Topologyと動的Topologyがある。
- 動的Topologyは参加を表明したノードに対し、動的にノード同士の関係を作る。例えばTreeを構成する場合、参加したノードから順にrootに近い役割を与え、またCodeGearはノードが参加し、parentに接続された後に実行される。

## 静的Topology
- 静的Toopologyはdotファイルを与えることでノード関係を下の図のようにする。
- 静的Topologyはdotファイルのノード数と同等のTopologyNodeがあって初めて、CodeGearが実行される。
```Code
digraph test {
	node0 -> node1 [label="right"]
	node1 -> node2 [label="right"]
	node2 -> node0 [label="right"]
}
```

<div style="text-align: center;">
　<img src="../paper/images/ring.pdf" alt="MetaGear" width="300">
</div>

## ブロックチェーンのトランザクション
- ブロックチェーンはP2Pにてネットワーク間が動作している。つまり、ブロックチェーンにはサーバー、クライアントの区別がなく全てのノードが平等である。
- ブロックチェーンにおけるブロックは複数のトランザクションをまとめたものである。ブロックの構造は使用するコンセンサスにより変わるが基本的には、previous block hash, merkle root hash, timeが含まれるBlockHeaderとTransactionListにより構成される。

## BlockHeader
- BlockHeaderには、前のブロックをハッシュ化したもの、トランザクションをまとめたmarkle treeのrootのhash、そのブロックを生成したtimeとなっている。
- previous block hashは、前のブロックのパラメータを並べてhash化したものである。
- 上記のものがそれぞれ連なっていることによって下の図のようなブロック繋がっている。そのため一つが更新されたらそのあとにつながるブロック全てを更新しなければならなくなる。
<div style="text-align: center;">
　<img src="../paper/images/chain.pdf" alt="MetaGear" width="600">
</div>

## Blockの動作
- ブロックが生成された場合、知っているノードにそのブロックをブロードキャストする。通信量を抑えるためにブロックを送ったあと、ブロックをシリアライズして送信する場合もある。
- 誤りがあればさらにそのノードがブロックをブロードキャストする。そしてTransaction PoolというTransactionをためておく場所から、そのブロックに含まれるTransactionを削除し、新しいブロックを生成する。

## Transaction
- トランザクションとはデータのやり取りを行なった記録の最小単位である。トランザクションの構造は次のとおりである。
- TransactionHash
  - トランザクションをハッシュ化したもの。
- data
  - データ
- sendAddress
  - 送り元のアドレス。
- receiveAddress
  - 送り先のアカウントのアドレス。
- signature
  - トランザクションの一部と秘密鍵をSHA256でハッシュ化したもの。ECDSAで署名している。
- トランザクションはノード間で伝搬され、ノードごとに検証される。そして検証を終え、不正なトランザクションであればそれを破棄し、検証に通った場合はTransaction Poolに取り込まれ、また検証したノードからトランザクションがブロードキャストする。


## コンセンサスアルゴリズム
- fork
  - ブロック生成後にブロードキャストを行うと、ブロック高の同じもしくは高いブロックチェーンにたどり着く状態があり、異なるブロックを持った二つのブロックチェーンのうちどちらかを破棄する必要がある。
- fork状態を解消するために用いられるのがコンセンサスアルゴリズムである。
- ブロックチェーンはパブリックブロックチェーンとコンソーシアムブロックチェーンの場合によってコンセンサスアルゴリズムが変わる。
  - パブリックブロックチェーン
    - 不特定たすのノードが参加するブロックチェーンを指す。
    - 不特定多数のノード間、全体のノードの参加数が変わる状況でコンセンサスの変わるアルゴリズムでなければならない。
  - コンソーシアムブロックチェーン
    - 許可したノードのみが参加できるブロックチェーンである。

# Paxos
- Paxosはノードの多数決によってコンセンサスをとるアルゴリズムである。
- Paxosは以下のような問題があっても値を一意に決めることができる。
  - 1,プロセス毎に処理の速度が違う。つまりメッセージの返信が遅い可能性がある。
  - 2,通信にどれだけの時間がかかるかわからず、その途中でメッセージが失われる可能性がある。
  - 3,プロセスは停止する可能性もある。

# Paxosの役割ノード
- Paxosは3つの役割ノードがある。
  - proposer
    - 値を提案するノード。
  - accepter
    - 値を決めるノード。
  - lerner
    - accepterから値を集計し、過半数以上のaccepterが持っている値を決める。

# Paxosの役割定義
- 提案
  - 異なる提案ごとにユニークな提案番号と値からなる。提案番号とは、異なる提案を見分けるための識別子であり、単調増加である。
- 値(提案)がacceptされる
  - accepterによって値(提案)が決まること。
- 値(提案)が選択(chosen)される
  - 過半数以上のacceptorによって、値がacceptされた場合、それを値(提案)が選択されたと言う。


# paxosのアルゴリズム
- paxosのアルゴリズムは2フューズあり、一つ目のフェーズprepare-promiseと二つ目のフェーズaccept-acceptedの二つに区分される。

# paxosのアルゴリズム prepare-promise
- (言葉での説明記入?)
<div style="text-align: center;">
　<img src="../paper/images/prepare-promise.pdf" alt="MetaGear" width="600">
</div>

# paxosのアルゴリズム accept-accepted
- (1)proposerは過半数のacceptorから返事が来たのなら、次の提案をaccepterに送る。これをacceptリクエストという。
    - (a)もし、約束のみ帰って来ているのならば、任意の値vをprepareリクエストで送った提案に設定する。
    - (b)もし、acceptされた提案が帰って来たら、その中で最大の提案番号v'をprepareリクエストで送った提案の値として設定する。
- (2)acceptorはacceptリクエストが来た場合、Promiseした提案よりもacceptリクエストで提案された番号が低ければ、その提案を拒否する。それ以外の場合、acceptする。
<div style="text-align: center;">
　<img src="../paper/images/accept-accepted.pdf" alt="MetaGear" width="600">
</div>

# Paxos
- Proof of Workと比較しメッセージ通信量と耐障害性のトレードオフになっている。
- Paxosでコンセンサスを取る際、Proof of Workと比較して次のようなメリットがある。
  - CPUにリソースを消費しない。
  - Transactionの確定に時間がかからない。
- Paxos自体がリーダー選出に向いているアルゴリズムである。そのため、リーダーを決定し、そのノードのブロックチェーンの一貫性のみをかんがえることができる。



# Gears OS の構成図

<div style="text-align: center;">
　<img src="./fig/gears_structure.pdf" alt="gears_structure" width="900">
</div>



# Context
- Context とは使用される Code Gear と Data Gear を全て格納した Meta Data Gear である。
- Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。
<div style="text-align: center;">
　<img src="./fig/Gearef.pdf" alt="gearef" width="900">
</div>

# context の定義

```contexr
/* context define */
struct Context {
    int codeNum; //実行可能な Code Gear の数
    __code (**code) (struct Context*); //実行可能な code Gear のリスト
    void* heapStart; //Data Gear の Allocate用のヒープ
    void* heap;
    long heapLimit;
    int dataNum; //Data Gear の数
    union Data **data; //Data Gear のリスト
};
```

#Context
- Code/Data Gear の名前は enum で定義される。
- Code/Data Gear の名前とポインタの対応は enum を使って行われる。

```code
enum Code {
    C_cg1,
    C_cg2,
};
```

```data
enum Data {
    D_dg1,
    D_dg2,
};
```

# Data Gear の定義
- Data Gear は union と struxt を用いて定義される
- これをもとに必要な Data Gear の allocate を行う

```data
union Data {
    struct Time {
        enum Code next;
        double time;
    } time;
    struct LoopCounter {
        int i;
    } loopCounter;
    ...
};
```


<!--
# CbC による Gears OS 記述の問題点
- Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
- 本研究ではこれらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
- そのためのプロトタイプとして perl スクリプトを作成した。
-->

# Interface
- Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
- Interface は使用される Data Gear の定義と、それに対する Code Gear の集合である。
- Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。

# Interface のコード
```interface
typedef struct Stack<Type, Impl>{
        union Data* stack;
        union Data* data;
        union Data* data1;
        __code whenEmpty(...);
        __code clear(Impl* stack,__code next(...));
        __code push(Impl* stack,Type* data, __code next(...));
        __code pop(Impl* stack, __code next(Type* data, ...));
        __code pop2(Impl* stack, __code next(Type* data, Type* data1, ...));
        __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
        __code get(Impl* stack, __code next(Type* data, ...));
        __code get2(Impl* stack, __code next(Type* data, Type* data1, ...));
        __code next(...);
} Stack;
```

# Interface の実装例

```impl
Stack* createSingleLinkedStack(struct Context* context) {
    struct Stack* stack = new Stack();
    struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
    stack->stack = (union Data*)singleLinkedStack;
    singleLinkedStack->top = NULL;
    stack->push = C_pushSingleLinkedStack;
    stack->pop  = C_popSingleLinkedStack;
    stack->pop2  = C_pop2SingleLinkedStack;
    stack->get  = C_getSingleLinkedStack;
    stack->get2  = C_get2SingleLinkedStack;
    stack->isEmpty = C_isEmptySingleLinkedStack;
    stack->clear = C_clearSingleLinkedStack;
    return stack;
}
```

# Interface の実装例

```impl
__code pushSingleLinkedStack(struct SingleLinkedStack* stack,
                                union Data* data, __code next(...)) {
    Element* element = new Element();
    element->next = stack->top;
    element->data = data;
    stack->top = element;
    goto next(...);
}

```

# interface の使用例

- goto interface-\>code() と記述する。

```code
__code stackTest1(struct Stack* stack) {
    Node* node = new Node();
    node->color = Red;
    goto stack->push(node, stackTest2);
}

```


<!--

<div style="text-align: center;">
　<img src="./images/multiComponent.pdf" alt="message" width="600">
</div>

-->

# stub Code Gear

- Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。
- しかし、Meta Data Gear である Context をノーマルレベルの Code Gear から直接アクセスするのはよろしくない。
- そこで Context から必要なデータを取り出して Code Gear に接続する、メタレベルの stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。

# stub Code Gear の例
```stub
__code clearSingleLinkedStack(struct Context *context,
                    struct SingleLinkedStack* stack,enum Code next) {
    stack->top = NULL;
    goto meta(context, next);
}

__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack =
                (SingleLinkedStack*)GearImpl(context, Stack, stack);
        enum Code next = Gearef(context, Stack)->next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

# Context、stub Code Gear の自動生成
- Gears OS ではノーマルレベルの計算の他に Context や stub などのメタ計算を記述する必要がある。
- 現在の CbC で Gears OS を記述すると、このメタ計算の記述も行わなくてはならず、これには多くの労力を要する。
- この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。


# stub Code Gear の生成
- stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
- stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
- generate_stub は指定された cbc ファイルの __code で記述された Code Gear を取得。
- Code Gear の引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
- cbc ファイルの Code Gear から、生成した stub Code Gear を加えたファイルを生成する。

# 生成された stub Code Gear

```stub
__code clearSingleLinkedStack(struct Context *context,
                    struct SingleLinkedStack* stack,enum Code next) {
    stack->top = NULL;
    goto meta(context, next);
}

__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack =
                (SingleLinkedStack*)GearImpl(context, Stack, stack);
        enum Code next = Gearef(context, Stack)->next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

# Context の生成

- generate_context は context.h から Data Gear、generate_stub から生成されたファイルから Code Gear を取得し、以下を生成する。
    - Code/Data Gear を enum で定義した enumCode.h、enumData.h
    - 取得した Code/Data Gear から Context の生成を行う target-context
    - Context を生成する際の Data Gear の Allocation を行う dataGearInit.c

<div style="text-align: center;">
　<img src="./fig/generate_context3.pdf" alt="generate_context3" width="600">
</div>

# 今後の課題
- 本研究では CbC を用いた Code Gear と Data Gear を持つ Gears OS の記述を行なった。
- また、Gears OS の記述に必要な Meta の生成を行う perl スクリプトの作成を行なった。
- これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
- 今後の課題は、今回 perl スクリプトによって Context や stub を含むファイルの生成を行なったが、LLVM/clang 上で実装しコンパイラから直接 CbC を実行できるようにすることを目的とする。
- また、xv6 を Gears OS での書き換えや、継続ではスタックは積まないため、スタックトレースを使わない手法でのデバッグの考案などもある。

[](プロシン発表時間 セッション7 1/21 10:40 - 12:00)