\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\usepackage{abstract}
\usepackage{here}
\usepackage{url}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\input{dummy.tex}
\renewcommand{\abstractname}{Abstract}
\begin{document}
\title{Blockchain implements in Christie}
\author{155753A 氏名 {赤堀}{貴一} 指導教員 : 河野 真治}
\date{}
\twocolumn [
\maketitle
\begin{onecolabstract}

Data corruption and inconsistency in computers causes severe problem. Therefore, we detect corruption and inconsistency by Blockchain. The Blockchain is a distributed system.  It is possible to compare between hash value and data which is correct. Even if there are incorrect operation and tampering, data are possible to recover with Blockchain.

We are developing Christie and GearsOS. Christie is a distributed framework and GearsOS is a Operating System. GearsOS Filesystem will refer to Christie. if implementing block chain in Christie and implementing it in GearsOS, makes it possible to detect data corruption and inconsistency in the GearsOS file system. In addition, it is possible to configure decentralized distributed network between Gears OS. if it does not configure, data is protected. So, our purpose can be achieved.

In this study, We implement Blockchain in Christie and run it in distributed environment on PC cluster.
\end{onecolabstract}]
\thispagestyle{fancy} 

\section{研究目的}

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

当研究室では分散フレームワークとしてChristieを開発している. これはGearsOSにファイルシステムに組み込む予定がある. そのため, Christieにブロックチェーンを実装し, GearsOSに組み込むことにより, GearsOSのファイルシステムにおいてデータの不整合を検知できる. また, GearsOS同士による分散ファイルシステムを構成することができ, 非中央的にデータの分散ができるようになる. もし分散システムを構成しない場合でもデータの整合性保持は行え, 上記の目的は達成できる.

本研究では, Christieにブロックチェーンを実装し, 実際に学科のPCクラスタ上の分散環境で動かす.

\section{ブロックチェーン}
ブロックチェーンを実装することは次のようなメリットが有る.

\begin{itemize}
\item データの追跡, 検証が容易である.
\item 中央管理者が存在しない. 単一障害点がない.
\end{itemize}

データの追跡, 検証が容易であるのは, ブロックの構造によるものである. ブロックの構造は簡易化すれば次のようなものである.

\begin{itemize}
\item 前のブロックの暗号化ハッシュ.
\item タイムスタンプ.
\item トランザクションリスト.
\end{itemize}

ブロックは図\ref{fig:chain}のようにhashでつながっている. 一つのブロックが変更されれば, その後に連なるブロックも整合性が保たれないため, これによってデータの整合性保持が行える.

\begin{figure}[H]
\centering
  \fbox{
   \includegraphics[scale=0.3]{./images/chain.pdf}
  }
\caption{hash chain}
\label{fig:chain}
\end{figure}


トランザクション, ブロックともにノード間で伝搬され, ノードごとに検証される. そして検証を終え, 不正なトランザクション, ブロックであれば破棄する. 検証に通った場合は, トランザクションはTransaction PoolにTransactionを貯めておき, ブロックはブロックチェーンに取り組まれ, 検証したノードからトランザクション, ブロックがブロードキャストされる. ノード間はP2Pで通信が行われている.

同時に異なるノードで複数のブロックができることを, forkという. これによってブロックチェーンの分岐が起こる. 
ブロックチェーンの分岐を収束させるにはコンセンサスアルゴリズムを使用する.

\section{コンセンサスアルゴリズム}
コンセンサスアルゴリズムとは, 一意の値を分散環境上で決めるためのアルゴリズムである.

今回は分散アルゴリズムとしてPaxosを実装した. 

Paxosは3つの役割のノードがある.

\begin{description}
\item[proposer] 値を提案するノード.
\item[acceptor] 値を決めるノード.
\item[learner] acceptorから値を集計し, 過半数以上のacceptorが持っている値を決める.
\end{description}

Paxosのアルゴリズムに入る前に, 定義された用語を説明する. 以下にその用語の定義を示す.\begin{description}
\item[提案] 提案は, 異なる提案ごとにユニークな提案番号と値からなる. 提案番号とは, 異なる提案を見分けるための識別子であり, 単調増加する. 値は一意に決まってほしいデータである.
\item[値(提案)がacceptされる] acceptorによって値(提案)が決まること. 
\item[値(提案)が選択(chosen)される] 過半数以上のacceptorによって, 値(提案)がacceptされた場合, それを値(提案)が選択されたと言う.
\end{description}


Paxosのアルゴリズムは2フェーズある. 

1つ目のフェーズ, prepare-promiseは次のような手順で動作する. 
\begin{enumerate}
\item proposerは提案番号nを設定した提案を過半数以上のacceptorに送る. これをprepareリクエストという. 
\item acceptorはprepareリクエストが来たら次の動作をする. 
\begin{enumerate}
\item もし, 以前に送られたprepareリクエストの提案番号より, 今送られてきたprepareリクエストの提案番号のほうが大きければ, それ以下の提案番号の提案を拒否するという約束を返す. この状態をPromiseしたという.
\item もし, 値がすでにacceptされていれば, accpetされた提案を返す. 
\end{enumerate}

\end{enumerate}

2つ目のフェーズ, accept-acceptedは次のような手順で動作する. 
\begin{enumerate}
\item proposerは過半数のacceptorから返信が来たならば, 次の提案をacceptorに送る. これをacceptリクエストという.
\begin{enumerate}
\item もし, 約束のみが返ってきているならば, 任意の値vをprepareリクエストで送った提案に設定する.
\item もし, acceptされた提案が返ってきたら, その中で最大の提案番号を持つ提案の値v'をprepareリクエストで送った提案の値として設定する.
\end{enumerate}

\item acceptorはacceptリクエストが来た場合, Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ, その提案を拒否する. それ以外の場合はacceptする.
\end{enumerate}


このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある.

\begin{enumerate}
\item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる.
\item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる($Acceptorの数 + Learnerの数$になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない.
\end{enumerate}

2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる.

Paxosでコンセンサスを取ることは, Proof of Workと比較して次のようなメリットがある.

\begin{itemize}
\item CPUのリソースを消費しない
\item Transactionの確定に時間がかからない.
\end{itemize}

\section{Christie}

Christieは当研究室で開発している分散フレームワークである. ChristieはJavaで書かれているが, 当研究室で開発しているGearsOSに組み込まれる予定がある. そのため, GearsOSを構成する言語Continuation based Cと似た概念がある. Christieに存在する概念として次のようなものがある.

\begin{itemize}
\item CodeGear(以下CG)
\item DataGear(以下DG)
\item CodeGearManager(以下CGM)
\item DataGearManager(以下DGM)
\end{itemize}

CGはクラス, スレッドに相当し, DGは変数データに相当する. CGMはノードであり, DGM, CG, DGを管理する. DGMはDGを管理するものであり, putという操作により変数データ, つまりDGを格納できる. 

DGMにはLocalとRemoteと2つの種類があり, Localであれば, LocalのCGMが管理しているDGMに対し, DGを格納していく. Remoteであれば接続したRemote先のCGMのDGMにDGを格納できる. DGを取り出す際にはアノテーションを付けることで, データの取り出し方も指定できる. Take, Peekという操作があり, Takeは読み込んだDGが消えるが, PeekはDGを消さずにそのまま残す. また, RemoteTake, RemotePeekというものもあり, リモート先を指定することにより, RemoteDGMからデータを取ることができる.

CGはCGMによって実行されるが, 実行するにはCGに必要なDGが全て揃う必要がある. もしDGが全て揃わない場合, CGMはずっとlistenし, データが揃うまで実行を待つ.

\section{Christieでのブロックチェーンの実装}
Christieでブロックチェーンのブロック, トランザクション, Paxosを実装した. 

その際の, Christieの便利な点を述べる.

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

不便な点を以下に述べる.

\begin{itemize}
\item デバッグが難しい. DGでのkeyのスペルミスなどが起こると, CodeGearが実行されず, waitされる問題が出る.
\item TakeFrom, PeekFromの使い方が難しい. TakeFrom, PeekFromは引数でDGM nameを指定する. しかし, DGMの名前を静的に与えるよりも, 動的に与えたい場合が多かった.
\item Takeの待ち合わせでCGが実行されない. 2つのCGで同じ変数をTakeしようとすると, setupされた時点で変数がロックされる. このとき, 片方のCGはDGがすべて揃っているのに, すべての変数が揃っていないもう片方のCGに同名の変数がロックされ, 実行されない場合がある. 
\end{itemize}




\section{実験, 評価}
ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 琉球大学のPCクラスタ上で動かした. 

今回は単純化のために, 整数でコンセンサスを取る. ノードはproposerが2つ, acceptorが3つ, learnerが1つという構成で実験する.

Paxosの実験は3回行った. Paxosにはlog4j2を実装しており, logを取るようにしている. そのため, そのlogから値が一意に決まるまでを調べた. 1つの実験の結果を図\ref{fig:paxos2}に示す. 

\begin{figure}[h]
\centering
  \fbox{
   \includegraphics[scale=0.45]{./images/paxos2.pdf}
  }
\caption{実験の結果1}
\label{fig:paxos2}
\end{figure}

実際にLearnerの値が一意に決まっていることがわかる.



\section{まとめ}


本研究ではブロックチェーンと, 分散環境上で値を一意に決めるコンセンサスアルゴリズムを述べ, Christieという分散フレームワークで実際にPaxosを作り, PCクラスタ上で動かした. その結果, コンセンサスの結果として一意のデータが取り出せることがわかった. 

まだPCクラスタ上ではブロックチェーンを動かすことができない. しかし, Block, Transaction, Hash生成, 署名のためのクラスはいずれも作られている. Transactionにおいてはまだファイルのデータを入れる機能は実装していないが, これらを組み合わせれば簡易的なブロックチェーンが作れる. そのため, あとはPaxosとこれらのクラスをどのようにつなげるかが問題となる.
また, Proof of Workを行うクラスも作られている. そのため, ブロックチェーンが実装できた場合, このクラスを用いてPaxosと速度比較も行える.

今後の課題としては, Paxosによるブロックチェーンを作り, 分散クラスタ上でファイルのやり取りができるかを見る. その際にどの程度スケーラビリティがあるのか, Proof of Workと比較し, どの程度速度が違うのかを見ていきたい.



\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}
\end{document}