|
5
|
1 %\input{/Users/e155753/.tex/setup}
|
|
|
2
|
|
|
3 %%文書開始****************************
|
|
|
4 \begin{document}
|
|
|
5 %%**************************************
|
|
|
6 \chapter{コンセンサスアルゴリズム}
|
|
|
7
|
|
|
8 ブロックチェーンでは, パブリックブロックチェーンの場合とコンソーシアムブロックチェーンによってコンセンサスアルゴリズムが変わる. この章ではパブリックブロックチェーンのBitcoin, Ethereumに使われているProof of Workについて説明し, コンソーシアムブロックチェーンに使えるPaxosを説明する.
|
|
|
9
|
|
|
10 \section{Proof of Workを用いたコンセンサス}
|
|
|
11 パブリックブロックチェーンとは, 不特定多数のノードが参加するブロックチェーンシステムのことを指す. よって, 不特定多数のノード間, 全体のノードの参加数が変わる状況でコンセンサスが取れるアルゴリズムを使用しなければならない.
|
|
|
12 Proof of Workは不特定多数のノードを対象としてコンセンサスが取れる. ノードの計算量によってコンセンサスを取るからである. 次のような問題があっても, Proof of Workはコンセンサスを取ることができる.
|
|
|
13
|
|
|
14 \begin{enumerate}
|
|
|
15 \item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある
|
|
|
16 \item 通信にどれだけの時間がかかるかわからず, その途中でメッセージが失われる可能性がある,
|
|
|
17 \item プロセスは停止する可能性がある. また, 復旧する可能性もある.
|
|
|
18 \item 悪意ある情報を他のノードが送信する可能性がある.
|
|
|
19 \end{enumerate}
|
|
3
|
20
|
|
|
21
|
|
5
|
22 Proof of Workに必要なパラメータは次のとおりである.
|
|
|
23
|
|
|
24 \begin{itemize}
|
|
|
25 \item nonce
|
|
|
26 \item difficulty
|
|
|
27 \end{itemize}
|
|
|
28
|
|
|
29 nonceはブロックのパラメータに含まれる. difficultyはProof of Workの難しさ, 正確に言えば1つのブロックを生成する時間を調整している.
|
|
|
30 Proof of Workはこれらのパラメータを使って次のようにブロックを作る.
|
|
|
31
|
|
|
32 \begin{enumerate}
|
|
|
33 \item ブロックとnonceを加えたものをハッシュ化する. この際, nonceによって, ブロックのハッシュは全く違うものになる.
|
|
|
34 \item ハッシュ化したブロックの先頭から数えた0ビットの数がdifficultyより多ければ, そのブロックにnonceを埋め込み, ブロックを作る.
|
|
|
35 \item 2の条件に当てはまらなかった場合はnonceに1を足して, 1からやり直す.
|
|
|
36 \end{enumerate}
|
|
|
37 difficulty = 2でProof of Workの手順を図にしたものを図\ref{fig:proof-of-work}に示す.
|
|
|
38
|
|
|
39 \begin{figure}[H]
|
|
|
40 \centering
|
|
|
41 \fbox{
|
|
|
42 \includegraphics[scale=0.5]{./images/proof-of-work.pdf}
|
|
|
43 }
|
|
|
44 \caption{proof-of-workの例}
|
|
|
45 \label{fig:proof-of-work}
|
|
|
46 \end{figure}
|
|
|
47
|
|
|
48
|
|
|
49 2の条件については, 単純に$(桁数 - difficulty + 1) \times 10 > hash$とも置き換えることができる.
|
|
|
50
|
|
|
51 nonceを変えていくことで, hashはほぼ乱数のような状態になる. つまり, difficultyを増やすほど, 条件に当てはまるhashが少なくなっていくことがわかり, そのhashを探すための計算量も増えることがわかる.
|
|
|
52
|
|
|
53 これらがProof of Workでブロックを生成する手順である. これを用いることによって, ブロックが長くなればなるほど, すでに作られたブロックを変更することは計算量が膨大になるため, 不可能になっていく.
|
|
|
54
|
|
|
55 Proof of Workでノード間のコンセンサスを取る方法は単純で, ブロックの長さの差が一定以上になった場合, 最も長かったブロックを正しいものとする. これを図で表すと, 図\ref{fig:proof-of-work-fork}のようになる.
|
|
|
56
|
|
|
57 \begin{figure}[H]
|
|
|
58 \centering
|
|
|
59 \fbox{
|
|
|
60 \includegraphics[scale=0.5]{./images/proof-of-work-fork}
|
|
|
61 }
|
|
|
62 \caption{Proof of Workでのコンセンサス}
|
|
|
63 \label{fig:proof-of-work-fork}
|
|
|
64 \end{figure}
|
|
|
65
|
|
|
66 計算量の差が51\%以上になると, forkしたブロック同士で差が生まれる. それによって, IPアドレスでのコンセンサスではなく, CPUの性能によるコンセンサスを取ることができる.
|
|
|
67
|
|
|
68 コンセンサスでは, ブロックの差が大きければ大きいほど, コンセンサスが正確に取れる. しかし, 正しいチェーンが決まるのに時間がかかる. そのため, コンセンサスに必要なブロックの差はコンセンサスの正確性と時間のトレードオフになっている.
|
|
|
69
|
|
|
70 この方法でコンセンサスを取る場合の欠点を挙げる.
|
|
|
71 \begin{itemize}
|
|
7
|
72 \item CPUのリソースを使用する.
|
|
5
|
73 \item Transactionが確定するのに時間がかかる.
|
|
|
74 \end{itemize}
|
|
|
75
|
|
|
76
|
|
|
77 \section{Paxos}
|
|
|
78
|
|
|
79 コンソーシアムブロックチェーンは許可したノードのみが参加できるブロックチェーンである. そのため, ノードの数も把握できるため, Paxosを使うことができる. Paxosはノードの多数決によってコンセンサスを取るアルゴリズムである. ただし, Paxosは次のような問題があっても値を一意に決めることができる.
|
|
|
80
|
|
|
81 \begin{enumerate}
|
|
|
82 \item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある
|
|
|
83 \item 通信にどれだけの時間がかかるかわからず, その途中でメッセージが失われる可能性がある,
|
|
|
84 \item プロセスは停止する可能性がある. また, 復旧する可能性もある.
|
|
|
85 \end{enumerate}
|
|
|
86
|
|
6
|
87 Proof of Workにある特性の4がないが, これは許可したノードのみが参加可能だからである. つまり, 悪意あるノードが参加する可能性が少ないためである.
|
|
|
88
|
|
7
|
89 Paxosは3つの役割のノードがある.
|
|
|
90
|
|
|
91 \begin{description}
|
|
|
92 \item[proposer] 値を提案するノード.
|
|
|
93 \item[acceptor] 値を決めるノード.
|
|
|
94 \item[learner] acceptorから値を集計し, 過半数以上のacceptorが持っている値を決める.
|
|
|
95 \end{description}
|
|
|
96
|
|
|
97 Paxosのアルゴリズムに入る前に, 定義された用語を説明する. 以下にその用語の定義を示す.\begin{description}
|
|
|
98 \item[提案(リクエスト)] 提案は, 異なる提案ごとにユニークな提案番号と, 値からなる. 提案番号とは, 異なる提案を見分けるための識別子であり, 単調増加する. 値は一意に決まってほしいデータである.
|
|
|
99 \item[値(提案)がacceptされる] acceptorによって値(提案)が決まること.
|
|
|
100 \item[値(提案)が選択される] 過半数以上のacceptorによって, 値(提案)がacceptされた場合, それを値(提案)が選択されたと言う.
|
|
|
101 \end{description}
|
|
|
102
|
|
|
103
|
|
|
104 Paxosのアルゴリズムは2フェーズある.
|
|
|
105
|
|
|
106 1つ目のフェーズ, prepare-promiseは次のような手順で動作する.
|
|
|
107 \begin{enumerate}
|
|
|
108 \item proposerは提案番号nを設定した提案を過半数以上のacceptorに送る. これをprepareリクエストという.
|
|
|
109 \item acceptorはprepareリクエストが来たら次の動作をする.
|
|
|
110 \begin{enumerate}
|
|
|
111 \item もし, 以前に送られたprepareリクエストの提案番号より, 今送られてきたprepareリクエストの提案番号のほうが大きければ, それ以下の提案番号の提案を拒否するという約束を返す. この状態をPromiseしたという.
|
|
|
112 \item もし, 値がすでにacceptされていれば, accpetされた提案を返す.
|
|
|
113 \end{enumerate}
|
|
|
114
|
|
|
115 \end{enumerate}
|
|
|
116
|
|
|
117 2つ目のフェーズ, accept-acceptedは次のような手順で動作する.
|
|
|
118 \begin{enumerate}
|
|
|
119 \item proposerは過半数のacceptorから返信が来たならば, 次の提案をacceptorに送る. これをacceptリクエストという.
|
|
|
120 \begin{enumerate}
|
|
|
121 \item もし, 約束のみが返ってきているならば, 任意の値vをprepareリクエストで送った提案に設定する.
|
|
|
122 \item もし, acceptされた提案が返ってきたら, その中で最大の提案番号を持つ提案の値v'をprepareリクエストで送った提案の値として設定する.
|
|
|
123 \end{enumerate}
|
|
|
124
|
|
|
125 \item acceptorはacceptリクエストが来た場合, Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ, その提案を拒否する. それ以外の場合はacceptする.
|
|
|
126 \end{enumerate}
|
|
|
127
|
|
|
128 このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある.
|
|
|
129
|
|
|
130 \begin{enumerate}
|
|
|
131 \item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる.
|
|
|
132 \item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる(Acceptorの数の通信量になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない.
|
|
|
133 \end{enumerate}
|
|
|
134
|
|
|
135 2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる.
|
|
|
136
|
|
|
137 Paxosでコンセンサスを取ることは, Proof of Workと比較して次のようなメリットがある.
|
|
|
138
|
|
|
139 \begin{itemize}
|
|
|
140 \item CPUのリソースを消費しない
|
|
|
141 \item Transactionの確定に時間がかからない.
|
|
|
142 \end{itemize}
|
|
|
143
|
|
|
144 \section{Paxosによるブロックチェーン}
|
|
|
145
|
|
|
146 PaxosはProof of Workに比べ, CPUのリソースを消費せず, Transactionの確定に時間がかからない. そのため, Paxosでブロックのコンセンサスを取るブロックチェーンを実装することにはメリットが有る.
|
|
|
147 また, Paxos自体がそもそもリーダー選出に向いているアルゴリズムである. そのため, リーダーを決め, そのノードのブロックチェーンの一貫性のみを考えることもできる.
|
|
6
|
148
|
|
5
|
149
|
|
|
150
|
|
|
151 %%文書終了****************************
|
|
|
152 \end{document}
|
