\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}
Block chain is also called decentralized ledger, which is a technique for aligning blocks linked by Hash in a group of multiple transactions on all nodes on the system.

Distributed framework Solves data inconsistency in GearsOS file system by implementing block chain in Christie. This makes it possible to configure distributed file system on Gears OS.

In this study, we implemented block chains in Christie and confirmed that it actually runs in a distributed environment on the department's PC cluster.
\end{onecolabstract}]
\thispagestyle{fancy} 

\section{研究目的}
ブロックチェーンとは分散型台帳とも呼ばれ, 複数のトランザクションをまとめたブロックをHashでつなげたものを, システム上のすべてのノードで整合させる技術である.

分散フレームワークChristieにブロックチェーンを実装することにより, 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.17]{./images/chain.pdf}
  }
\caption{hash chain}
\label{fig:chain}
\end{figure}


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

同時に異なるノードで複数のブロックができることを, 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
\item DataGear
\item CodeGearManager
\item DataGearManager
\end{itemize}

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

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

CGはCodeGearManagerによって実行されるが, 実行するにはCodeGearに必要なDateGearが全て揃う必要がある. もしDateGearが全て揃わない場合, CodeGearManagerはずっと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 デバッグが難しい. DataGearでのkeyのスペルミスなどが起こると, CodeGearが実行されず, waitする. この場合, 標準出力には何も出ないため, どこで止まっているか, ただ変数を待っているだけなのかという判断が難しい.
\item TakeFrom, PeekFromの使い方が難しい. TakeFrom, PeekFromは引数でDGM nameを指定する. しかし, DateGearManagerの名前を静的に与えるよりも, 動的に与えたい場合が多かった.
\item Takeの待ち合わせでCodeGearが実行されない. 2つのCodeGearで同じ変数をTakeしようとすると, setupされた時点で変数がロックされる. このとき, 片方のCodeGearはDataGearがすべて揃っているのに, すべての変数が揃っていないもう片方のCodeGearに同名の変数がロックされ, 実行されない場合がある. 
\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{Paxosの実行の結果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}