%\input{/Users/e155753/.tex/setup}

%%文書開始****************************
\begin{document} 
%%**************************************
\chapter{コンセンサスアルゴリズム}

ブロックチェーンでは, パブリックブロックチェーンの場合とコンソーシアムブロックチェーンによってコンセンサスアルゴリズムが変わる. この章ではパブリックブロックチェーンのBitcoin, Ethereumに使われているProof of Workについて説明し, コンソーシアムブロックチェーンに使えるPaxosを説明する.

\section{Proof of Workを用いたコンセンサス}
パブリックブロックチェーンとは, 不特定多数のノードが参加するブロックチェーンシステムのことを指す. よって, 不特定多数のノード間, 全体のノードの参加数が変わる状況でコンセンサスが取れるアルゴリズムを使用しなければならない. 
Proof of Workは不特定多数のノードを対象としてコンセンサスが取れる. ノードの計算量によってコンセンサスを取るからである. 次のような問題があっても, Proof of Workはコンセンサスを取ることができる.

\begin{enumerate}
\item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある
\item 通信にどれだけの時間がかかるかわからず, その途中でメッセージが失われる可能性がある, 
\item プロセスは停止する可能性がある. また, 復旧する可能性もある.
\item 悪意ある情報を他のノードが送信する可能性がある.
\end{enumerate}


Proof of Workに必要なパラメータは次のとおりである.

\begin{itemize}
\item nonce
\item difficulty
\end{itemize}

nonceはブロックのパラメータに含まれる. difficultyはProof of Workの難しさ, 正確に言えば1つのブロックを生成する時間を調整している.
Proof of Workはこれらのパラメータを使って次のようにブロックを作る.

\begin{enumerate}
\item ブロックとnonceを加えたものをハッシュ化する. この際, nonceによって, ブロックのハッシュは全く違うものになる.
\item ハッシュ化したブロックの先頭から数えた0ビットの数がdifficultyより多ければ, そのブロックにnonceを埋め込み, ブロックを作る. 
\item 2の条件に当てはまらなかった場合はnonceに1を足して, 1からやり直す.
\end{enumerate}
difficulty = 2でProof of Workの手順を図にしたものを図\ref{fig:proof-of-work}に示す. 

\begin{figure}[H]
\centering
  \fbox{
   \includegraphics[scale=0.5]{./images/proof-of-work.pdf}
  }
\caption{proof-of-workの例}
\label{fig:proof-of-work}
\end{figure}


2の条件については, 単純に$(桁数 - difficulty + 1) \times 10 > hash$とも置き換えることができる. 

nonceを変えていくことで, hashはほぼ乱数のような状態になる. つまり, difficultyを増やすほど, 条件に当てはまるhashが少なくなっていくことがわかり, そのhashを探すための計算量も増えることがわかる. 

これらがProof of Workでブロックを生成する手順である. これを用いることによって, ブロックが長くなればなるほど, すでに作られたブロックを変更することは計算量が膨大になるため, 不可能になっていく. 

Proof of Workでノード間のコンセンサスを取る方法は単純で, ブロックの長さの差が一定以上になった場合, 最も長かったブロックを正しいものとする. これを図で表すと, 図\ref{fig:proof-of-work-fork}のようになる. 

\begin{figure}[H]
\centering
  \fbox{
   \includegraphics[scale=0.5]{./images/proof-of-work-fork}
  }
\caption{Proof of Workでのコンセンサス}
\label{fig:proof-of-work-fork}
\end{figure}

計算量の差が51\%以上になると, forkしたブロック同士で差が生まれる. それによって, IPアドレスでのコンセンサスではなく, CPUの性能によるコンセンサスを取ることができる.

コンセンサスでは, ブロックの差が大きければ大きいほど, コンセンサスが正確に取れる. しかし, 正しいチェーンが決まるのに時間がかかる. そのため, コンセンサスに必要なブロックの差はコンセンサスの正確性と時間のトレードオフになっている. 

この方法でコンセンサスを取る場合の欠点を挙げる.
\begin{itemize}
\item この計算をするためだけにCPUを消費する. 単純計算であるため, とても重要な計算をしているわけではなく, CPUの資源が無駄に使われる.
\item Transactionが確定するのに時間がかかる. 
\end{itemize}


\section{Paxos}

コンソーシアムブロックチェーンは許可したノードのみが参加できるブロックチェーンである. そのため, ノードの数も把握できるため, Paxosを使うことができる. Paxosはノードの多数決によってコンセンサスを取るアルゴリズムである. ただし, Paxosは次のような問題があっても値を一意に決めることができる.

\begin{enumerate}
\item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある
\item 通信にどれだけの時間がかかるかわからず, その途中でメッセージが失われる可能性がある, 
\item プロセスは停止する可能性がある. また, 復旧する可能性もある.
\end{enumerate}

Proof of Workにある特性の4がないが, これは許可したノードのみが参加可能だからである. つまり, 悪意あるノードが参加する可能性が少ないためである. 




%%文書終了****************************
\end{document}