分散型コンセンサス・アルゴリズム プロトコル まとめ

分散型コンセンサス・アルゴリズム プロトコル まとめ

暗号通貨、ブロックチェーン技術の方向からの分散型合意形成(コンセンサス)アルゴリズム、メカニズムの説明になります。

【コンセンサス・アルゴリズムをざっくりまとめると】
・ブロックチェーンにおいて、正しいブロックやトランザクションを検査し、正当なものだと全員で合意（承認）してチェーンに加える方法。
・代表的なものに、PoW(Bitcoinで使用)、PoS(Ethereumに実装予定）、PoI（NEMに実装）などがある。
・コンセンサス・アルゴリズム間に優劣はなく、一概にどのアルゴリズムが良い、悪いとは言えない。目的や用途に応じて最適と思われるものを選択する。
目次

コンセンサス・アルゴリズムとは何か？

分散型コンセンサス・アルゴリズム（合意アルゴリズムと言われることも）とは、文字通り「合意形成をとる方法」を意味します。

ブロックチェーンでは、正しいブロックやトランザクションを検査し、正当なものだと全員で合意（承認）してチェーンに加えることが必要になります。このとき、その合意形成方法について規定するものがコンセンサス・アルゴリズムです。

以下のように呼称されることもありますが、違いは不明瞭のようです。

  • 分散コンセンサス (distributed consensus)
  • 分散型合意システム
  • 合意プロトコル

英語が苦手でなければ、下記の記事がよくまとまっていて参考になります。
Consensus Algorithms: The Root Of The Blockchain Technology

なぜ必要か?

分散システムでの高可用性を実現する方法は、「冗長化」一つのみと考えられるためです。

参考:VitalikによるBFTとコンセンサス・アルゴリズムの話↓
Software and Bounded Rationality

主要なコンセンサスアルゴリズム

コンセンサス・アルゴリズムの代表例としては、以下の5つが挙げられます。大半の暗号通貨プロジェクトは、これらの中のいずれかのコンセンサス・アルゴリズムを採用しています。

続いて、主要なコンセンサス・アルゴリズムについて解説します。

PoW：Proof of Work

PoWとは、ビットコインなど多くの暗号通貨で採用されている主要なコンセンサス・アルゴリズムです。PoWでは、マイナーが膨大な計算（マイニング）を行うことでハッシュ値を見つけ出し、ブロックを生成します。そして、そのブロックがネットワーク上の他のコンピューター（ノード）に承認されることで、チェーンに追加される仕組みになっています。

PoWのデメリットとしては、「セキュリティの脆弱性」、「マイニングにかかる膨大な消費電力量」、「取引速度の遅さ」が指摘されています。

PoS：Proof of Stake

このようなPoWの問題点を改善するためにPoSが考案されました。PoSは、ひとことで言えば「ネイティブ通貨の保有量に比例して、新たにブロックを生成・承認する権利を得ることができるようになる仕組み」です。

PoSではコインの保有量に比例してブロック承認の成功確率が上がります。そして、この「コインの保有量」を定義する仕組みには
コインの保有量とコインの保有期間で算出される「Coin Age」
コインの保有量に比例して、ランダムに取引承認者を選ぶ仕組みの「Randomized Proof of Stake」
の2種類があります。

PoSのメリットとしては、「51%攻撃に強い」、「PoWより消費電力を抑制できる」、「スケーラビリティを高められる」ことが挙げられます。
一方デメリットとしては、「コインの溜め込みによる流動性の低下」が懸念されています。

PoSについては以下にまとめています。
block-chain.jp「Proof of Stakeとは何か？」

DPOS：Delegated Proof of Stake

DPOSとは、Delegated Proof of Stakeの略称であり、コインの保有者に保有量に応じた投票権を割り当て、その投票により取り引きの承認者を委任するアルゴリズムです。委任された承認者は、ブロック生成で得られた報酬を投票した人に還元する仕組みになっており、全投票トップ100の代理人で新たなブロックを生成します。

DPOSのメリットには、「高速なトランザクション処理」、「消費電力の抑制」、「フォークするリスクの軽減」があります。
逆にデメリットとしては、「中央集権化する危険性」が指摘されています。

DPOSについては以下にまとめています。
block-chain.jp「DPOS: Delegated Proof of Stake とは何か？」

PoI：Proof of Importance

PoIは、PoSの問題点を改善したアルゴリズムです。「Proof of Importance」とは、「重要度による証明」を意味します。
コインの「保有量」「取引量」「取引回数」などから、コイン保有者の重要度を総合的にスコアリングし、スコアの高い人にブロック生成権が付与される仕組みになっています。

PoIはNEMに実装されています。NEMとは「New Economy Movement」の略であり、ブロックチェーンによる新しい経済圏を作ろうとするプロジェクトです。

PoIでは、「流動性が高まる」ことが期待されますが、その一方で、結局資産が多い者が有利になってしまうことが批判されています。

PoC：Proof of Consensus

PoCは、銀行など信頼できる少数者のみで承認作業を行うことから、「プライベートブロックチェーン」と呼ばれています。

現状、PoCを採用している通貨はRippleのみであり、以下の説明は全てRippleに関してのものとなります。

RippleのPoCでは、バリデーター（承認作業をする人）の内80%以上が承認するとトランザクションが完了する仕組みになっています。
少数のバリデーターが承認作業を行うことにより、取引承認速度を飛躍的に向上させることができます。
ただし、「許可型のプライベートブロックチェーンはブロックチェーンではない」、「分散型データベースと呼ぶべき」との主張もあります。

PoS関連のコンセンサス・アルゴリズム

Casper

Casperは、今後Ethereumに導入予定のPoSアルゴリズムです。
Casperには、Slasherという懲罰的アルゴリズムが含まれており、正しい取引を承認するインセンティブとなります。

Casperについては以下にまとめています。
block-chain.jp「EthereumのPoS: Casper まとめ」

SCP：Stellar Consensus Protocol

SCPはPoCの問題点を解消するために開発されたコンセンサス・アルゴリズムです。バリデーター全体の承認を要しないため、分岐が発生しません。
SCPを実装しているStellarは、デロイトやIBMとの提携をしていることから注目を集めています。

SCPについては以下にまとめています。
block-chain.jp「SCP(Stellar Consensus Protocol) まとめ」

SCP補足

* ビザンチン (Byzantine): みんな共謀しようとする
* 利他主義 (Altruistic): プロトコルにいつも従う
* 合理的 (Rational): 合っていれば、プロトコルに従い、合わなければプロトコルに従わない

引用: Software and Bounded Rationality – Ethereum Blog
https://blog.ethereum.org/2014/09/02/software-bounded-rationality/

POA：Proof of Activity

PoAとは、PoSのバリデーターをランダムにしたアルゴリズムのことです。
PoSでは、コインの保有量が多いほど攻撃の対象になるため、PoAでは承認者の選択をランダムに行うことでセキュリティを向上させています。

POAについては以下にまとめています。
block-chain.jp「Proof of Activityとは何か？」

PoST：Proof of Stake-Time

PoSTは、Vericoinに実装されており、Veriumに実装されているProof of Work Time（PoWT）と相互補完することで取引速度を高められるバイナリ・チェーンを構成しています。

PoMAS：Proof of Minimum Aged Stake

PoMASは、ある一定以上量のコインを保有する人の中で、コインの保有期間の短さに比例してブロックの承認権を与えるアルゴリズムです。

その他のPOSのコンセンサス・アルゴリズム一覧

上で紹介したもの以外にも、PoSベースのコンセンサス・アルゴリズムをいくつか挙げておきます。

引用元: Blockchain Consensus Protocols

その他コンセンサス・アルゴリズム

Paxos

Paxosは、「非同期システム上のコンセンサス・アルゴリズムの1つ」（下記Preferred Networks資料より引用）です。
非常に難解なアルゴリズムであることから、より簡単なアルゴリズムとして以下のRaftが開発されました。

（引用）
Preferred Networks「Paxos」 19 of 64
https://www.slideshare.net/pfi/paxos-13615514

その他、Paxos補足情報
– 1990年に登場、命名。論文が出たのは1998年。
– 実装の難易度が高い、と言われる
– 故障に耐える合意プロトコルとしてきっちり証明されたのは、paxosが初?
– 地理分散DBについて(https://www.slideshare.net/kumagi/db-75506786)
– Paxosアルゴリズム – Wikipedia(https://ja.wikipedia.org/wiki/Paxos%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)

Raft

Raftは、Paxosの改良版として作られました。「複製されたログを管理するためのアルゴリズム」（下記Preferred Networks資料より引用）です。

（引用）
Preferred Networks「Raft」 3 of 77
https://www.slideshare.net/pfi/raft-36155398

その他、Raftに関する補足情報
– 本家: Raft Consensus Algorithm(https://raft.github.io/)
– Raftの解説がある日本語スライド CoreOS入門(https://www.slideshare.net/YutakaMatsubara/coreos-35320632)
– ZooKeeper: Chubbyクローン, ZAB(ZooKeeper Atomic Broadcast)
– etcdが利用している
– Leader, Follower, Candidateから構成。
– 大きなクラスタを組むのに適してない。適切なノードの数は、5から9?
– P2P(全員同じ役割)なコンセンサス・アルゴリズムと違い、リーダーがいるモデル
– はじめはフォロワー。キャンディデート(候補者)からリーダを選び、リーダーを中心にデータを送信、コミットしてから、合意に達するモデル
– Raftを動的に理解できるスライド→Raft(http://thesecretlivesofdata.com/raft/)

PBFT

PBFTとは、「Practical Byzantine Fault Tolelance」の略であり、ビザンチン将軍問題の耐性を備えたコンセンサス・アルゴリズムです。

ビザンチン将軍問題とは、「何らかの理由で情報伝達に不具合があった場合でも、全体として正しい合意形成ができるかを問う問題」です。
また、ビザンチン将軍問題が発生しても全体が正しく機能するかどうかをビザンチン・フォールト・トレランス性と呼びます。

ビザンチン将軍問題に関する論文（英語）↓
Miguel Castro, Barbara Liskov “Practical Byzantine Fault Tolerance”. 1999
http://www.pmg.lcs.mit.edu/papers/osdi99.pdf

その他

地理分散データベース

  • 地理分散DBについて
  • Paxos, 2PC, 3PC, 2 Phase Lock, viewstamped replication, stake replication, MV2PL, Spanner, Replicated Commit, Calvin, FaunaDB,

Byzantine Agreement Protocol (synchronous)

  • 2PC (Two-phase Commit):
  • 3PC (Three-phase Commit):
  • Paxos: Microsoft/Lamport: (State machine replication)
  • Paxos
  • 実装例?: Aerospike, Zookeeper/Chubby, Megastore
  • Chubby: Google (serve strongly consistent files), Paxos実装?
  • Zab:

DLS

日本語情報

スライド

関連用語

まとめ

コンセンサス・アルゴリズムの比較において、それぞれに優劣はありません。
「どれが良い・悪い」という話ではなく、利用目的に応じて最適なものを選ぶことが重要です。

参考

     

免責事項

本記事に掲載されている記事の内容につきましては、正しい情報を提供することに務めてはおりますが、提供している記事の内容及び参考資料からいかなる損失や損害などの被害が発生したとしても、弊社では責任を負いかねます。実施される際には、法律事務所にご相談ください。

技術・サービス・実装方法等のレビュー、その他解説・分析・意見につきましてはblock-chani.jp運営者の個人的見解です。正確性・正当性を保証するものではありません。本記事掲載の記事内容のご利用は読者様個人の判断により自己責任でお願いいたします。

     

コンセンサス・ベイス（株）とブロックチェーン事業を行なってみませんか？

当サイトを運営するコンセンサス・ベイス株式会社は、2015年設立の国内で最も古いブロックチェーン専門企業です。これまでに、大手企業の顧客を中心に、日本トップクラスのブロックチェーンの開発・コンサルティング実績があります。

ブロックチェーンに関わるビジネスコンサル・システム開発・教育・講演などご希望でしたら、お気軽にお問い合わせください。

     
コンセンサス・ベイス（株）の実績を見てみる
     

ブロックチェーン学習に最適の書籍の紹介

図解即戦力 ブロックチェーンのしくみと開発がこれ1冊でしっかりわかる教科書

ブロックチェーン　イーサリアムへの入り口　第二版 (ブロックチェーン技術書籍)

本書は、ブロックチェーン技術に興味を持ったエンジニアや、その仕組みを学び、自分の仕事に活かしたいビジネスパーソンを対象にして、ブロックチェーンのコア技術とネットワーク維持の仕組みを平易な言葉で解説しています。この本を読んだうえで、実際にコードを書くような専門書、ブロックチェーンビジネスの解説書を読むことで、理解度が飛躍的に高まるでしょう。（はじめにより）

Blockchainカテゴリの最新記事