コンセンサスアルゴリズムについて

2008年10月にサトシ・ナカモトと名乗る正体不明の人物が、仮想通貨ビットコインに関する論文“Bitcoin: A Peer-to-Peer Electronic Cash System”を発表しました。

わずか9頁の画期的な論文は、研究者の目にとまり、プログラマによる実装が進んだ結果、わずか3か月後の2009年1月には史上初のブロックが生成されました。
このブロックを「ジェネシスブロック」と呼んでます。

ここでは、サトシ・ナカモトの論文の中でも最も秀逸なアイデア（発明）といわれるコンセンサスアルゴリズムについて説明したいと思います。

コンセンサスアルゴリズムとは

分散型ネットワーク上に不特定多数のノードが存在する環境において、「AさんがBさんに1ビットコインを送金をした」というような取引情報を記録した台帳に対して、誰もがその真正性に合意できる仕組みのことをコンセンサスアルゴリズムと呼びます。

もう少し具体的に考えてみましょう。

例えば普段私たちがお世話になっている銀行の口座情報は、特定の機関の権限と責任において信用が担保される中央集権型のシステムであるがゆえに、安心して利用することができます。

一方、中央集権型ではないシステム、即ち分散型ネットワーク上に見ず知らずの参加者が取引情報を流すようなシステムの場合、間違った情報や悪意のある情報が流れてくる可能性が十分に予想されます。

私たちはそれをどのように信用すればよいでしょうか？

まさにサトシ・ナカモトはこの課題、即ち「中央の権威によらず取引情報の真正性を担保する手法」を暗号学を駆使することにより解決したのです。

その根幹をなすのがコンセンサスアルゴリズムであり、取引情報を参加者が自律的に蓄積する「分散型台帳」に導くための定型化された処理体系が実現されてます。

一般的な障害パターン

一般的に分散型ネットワーク上で発生する障害には以下の2種類が存在します。

1. 無反応
   クラッシュやタイムアウトにより規定時間内に反応ができない状態
2. ビザンチン障害
   ブロックチェーンのように不特定のノードから構成されるネットワークでは、予測不可能なタイミングで裏切者からの反応で矛盾が生じ障害が発生する状態

後者の説明のためによく登場するのが「ビザンチン将軍問題」です。
結論から言うと、裏切者がm人いる中で、障害が起きないようにするには指揮官を含む将軍の人数N＝3m+1だけ必要になることが数学的に証明されています。

しかし、実際のブロックチェーンではノードの数も、裏切者も数も予想できないため、ビザンチン耐性では解決できないことが分かりますね。

Proof of Work ≠ コンセンサスアルゴリズム

代表的なコンセンサスアルゴリズムとしてよくあげられるのが、PoW（Proof of Work）やPoS（Proof of Stake）です。

しかしそれ自体がコンセンサスアルゴリズムではなく、単にブロックの作成者を決定する手法です。

それではPoWやPoSは正確にはどんな機能なのでしょうか？
これを専門用語では「Sybil耐性メカニズム」と呼んでいます（後述）

ブロックの作成者を決定する手法

PoWにしてもPoSにしても、ブロックの作成者を決定する手法に共通しているのは以下の3つの機能が備わっていることです。

1. 価値の提供
2. 報酬
3. 検証性

価値の提供

マイナーが新しいブロックを追加する場合に、シビル攻撃（後述）などの不正な行動をしないようにするために、ある種の価値の提供を求めます。
その価値とは、例えば演算コスト、電気コスト、信用コストなどです。

報酬

不正が発覚したり、正当な第三者が権利を獲得すると、先行投資した価値は失われますが、それでもチャレンジさせる仕組みが必要となります。
ブロックチェーンの場合、もし参加者の合意が得られれば、先行投資をした価値を大きく上回る報酬が与えられます。

報酬の原資は、取引をした時の手数料、新規発行された暗号通貨、またはその両方で構成されています。

検証性

ブロックチェーンには、誰もが取引情報に不正がないかどうかを安価に検証できる仕組みが備わっているため、マイナーは常に衆目の監視下に置かれます。

ブロックチェーンにおける代表的な検証手段は以下のとおりです。
（詳細はブロックチェーンは何故信頼できるのかをご参照ください）

1. ハッシュチェーン
2. ハッシュツリー（マークルルート）
3. トランザクションスクリプト(ScriptSigとScriptPubkeyの整合性)
4. Nonceの正当性
5. フォーマット検証

ナカモトコンセンサスとは

サトシ・ナカモトが考案したコンセンサスアルゴリズムは、以下の2つの仕組みから構成され、「ナカモトコンセンサス」として知られています。

1. PoW(Sybil耐性）
2. 最長チェーン選択ルール

PoW（Sybil耐性）

ビットコインでは、Proof of Work、即ち大量の演算装置と電力を消費させることにより、シビル耐性、即ちシビル攻撃の可能性を排除しています。

これによりマイナーはブロックを提案する権利を取得できます。

最長チェーン選択ルール

最長チェーン選択ルールは、どのチェーンが「正しい」チェーンであるかを決定するために使用されます。

分散型ネットワークの場合、同時多発的にブロックが生成される可能性があり、そのため複数の異なったチェーンが同時に存在する状態が生まれます。

その場合、最も長いチェーンが有効となり、それ以外のチェーンは捨てられます。
これを最長チェーン選択ルールと呼ばれます。

最終的にチェーンが確定する時間はどのくらいでしょうか？
ビットコインの場合、Nonce発見の難易度である”Difficulty Bits”により、10分に1ブロックが生成されるよう調整されており、6ブロックがチェーン化した時点、即ちブロックが生成されてから約1時間で確定することになります。

コンセンサスメカニズムの種類

PoW

ビットコインにおけるコンセンサスアルゴリズム（Sybil耐性）はPoW(Proof of Work）を使用しています。

ブロックの作成

PoWでは、トランザクションが詰め込まれた新しいブロックを作成する権利を、所定の条件を満たすNonceの発見者に与えるというロジックです。

つまり、誰のコンピュータが暗号パズルを最も速く解くことができるかを競うわけですね。

安全

不正なチェーンを操作するにはネットワークのコンピューティングパワー（ハッシュレート）の51％が必要となります。

暗号パズルを解くためには演算装置と電力コストに巨額の投資が必要であり、彼らの演算能力を合計するとGoogleが保有するすべてのコンピュータの能力を上回わると謂われてます。

多くのマイナーが競い合っている中で、現時点で51％攻撃をするのは事実上不可能ということで安全が担保されています。

PoS

PoWがあまりにも多くの電力を使う為、生み出されたのがPoS(Proof of Stake）と呼ばれるコンセンサスアルゴリズムです。

ブロックの作成

仮想通貨を多くそのネットワークに預け入れている参加者の中から、新しいブロックを承認する人を選出する、というコンセンサスアルゴリズムです。

• プルーフ（Proof）＝「証明」
• ステーク（Stake）＝「掛け金」

PoSのルールに従い選出された参加者は、正しく処理承認を行うことで、その仮想通貨を報酬として受け取ることができます。

安全

つまり、保有する仮想通貨と、報酬を受けた仮想通貨の価値が失われてしまわないよう、参加者が正しく承認を行うというインセンティブを生み出すことにより、不正のない取引や処理を行う仕組みになっています。

以上