※2018年7月5日公開
※2018年7月25日編集
「ハッシュグラフって何？」という方は、こちらの記事をご参照ください。
N−Village CTOの林田です。
以前の記事でも簡単にご説明しましたが、今回はさらに詳細にHashgraphのコンセンサスアルゴリズムを見ていきたいと思います。Hedera Hashgraphの公式解説動画「A Simple Explanation of Hashgraph with Pictures」の内容ほぼそのままとなっています。
今回は概念の話をメインにしたいので、実際のシステム実装や悪意を持ったメンバー等については考慮しないものとします。
「ラウンド」という考え方
例えば、メンバーA〜Dによって構成されるコミュニティにおいて、以下のようにHashgraphが成長していくとします。
Hashgraphでは、時系列に沿って「ラウンド」を区切ります。このとき、各メンバーが各ラウンドにて生成する最初のイベントを「witness（＝証人）」（図中の赤色のイベント）と呼びます。witnessを生成するタイミングで各メンバーが仮想投票を行い、過去のイベントの処理順を決定します（仮想投票の概要については以前の記事を参照してください）。
仮想投票には少なからず計算コストがかかります。ラウンドを設けることで、仮想投票の回数を適度に減らしているようです。
なお、各イベントの妥当性はそれを作成するメンバーによって検証されますので、イベントの承認／非承認はラウンドの概念に影響を受けません。
仮想投票の例
では、 上記ラウンド3開始時点における仮想投票の模様を見てみましょう。ラウンド2のwitness「B2」および「C2」（下図参照）に対する投票をそれぞれ取り上げてみます。
まず、「B2」について見てみると、ラウンド3のそれぞれのwitnessから「B2」を辿れることがわかります。つまり、ラウンド3の時点で各witnessが「B2」に対して投票した場合、「B2」が「famous witness（＝有名な証人）」として承認されるということを意味します。famous witnessとして承認されたイベントは、過去のイベントの処理順を決定する役割の一部を担います。
つぎに、「C2」について見てみると、ラウンド3の全witnessのうち1/3以下のwitness（今回の場合はCのwitnessのみ）からしか「C2」を辿れません。つまり、ラウンド3の時点で各witnessが「C2」に対して投票した場合、「C2」はfamous witnessとして承認されないということを意味します。
以上のように、ラウンド3開始時点において、「B2」はfamous witnessとして承認されるものの、「C2」については未承認となることがわかりました。
以前の記事でも記載しましたが、この一連の投票について、各メンバーはお互いがどの情報を知っているのかを知っているため、どのメンバーがどういった投票をするかを推定することができ、「仮想投票」が成立します。したがって、投票に関しての各メンバー間でのメッセージングは不要です。
処理順が決定されるイベントの範囲
さて、ラウンド3開始時点の仮想投票では、「B2」と同様にメンバーA、Dのwitnessもfamous witnessとして承認されます。この時、famous witnessから辿ることができるイベントについて、連鎖的に処理順が決定されます。
たとえば、下図の黒いイベントは、ラウンド3で承認されたすべてのfamous witneesから辿ることができます。したがって、ラウンド3開始時点で処理順が決定されます。
一方、その右隣のイベントは、ラウンド3で承認された一部のwitnessからしか辿ることができません。したがって、ラウンド3開始時点では処理順が未決定ということになります。
このように各イベントを評価していくと、ラウンド3開始時点での処理順の決定／未決定の状況は以下のようになります。
過去ラウンドのwitnessについても他のイベントと同様に評価されるため、ラウンド1のwitnessについても処理順が決定れます。
この時点で処理順が未決定のイベントは、まだ十分に伝達されていないというだけなので、ラウンド4以降に処理順が決定されます。
イベントの処理順の決定プロセス
イベントの処理順は、以下の優先度で評価され、決定されます。
- ラウンドが早い順
- コンセンサスタイムスタンプが早い順
- 拡張コンセンサスタイムスタンプが早い順
- 電子署名の文字列の昇順
まずは、イベントが属するラウンド（承認されたラウンドではない）を見ます。より過去のラウンドのイベントほど、古いイベントであると解釈されます。
次に、ラウンドが同じイベントであれば、コンセンサスタイムスタンプを見ます。「コンセンサスタイムスタンプ」について、例を挙げて解説します。
例えば、下図オレンジ色のイベントについて考えます。このイベントを承認したwitnessを持つメンバーはA、B、Dです。これらのメンバーが一番最初にこのイベントを受け取ったタイムスタンプがそれぞれ「1:00」「1:02」「1:01」だったとします。
このとき、これらのタイムスタンプを早い順に並び替え、その中央値である「1：01」がオレンジ色のイベントのコンセンサスタイムスタンプであると解釈されます。
次に、コンセンサスタイムスタンプが同じイベントであれば、拡張コンセンサスタイムスタンプを見ます。「拡張コンセンサスタイムスタンプ」というのは、タイムスタンプの中央値だけでなく、その中央値前後の値を加味した値のことです（この部分は公式解説動画でも詳細に語られていなかったため、不明瞭です）。
最後に、拡張コンセンサスタイムスタンプが同じイベントであれば、そのイベントの電子署名を見ます。電子署名はランダムな文字列となっており、それを昇順に並び替えて先にくる方がより古いイベントであると解釈されます。
Hashgraphのコンセンサスアルゴリズムの所感
ブロックチェーンと比較して、公平性が高いアルゴリズムだなと感じました。この仕組みであれば、特定のイベントを早く処理するような不正はできませんし、メンバー毎にマシンの時間がずれていたとしてもその差を吸収することが可能です。
内容に間違いがあればご指摘いただけますと幸いです。よろしくお願いいたします。