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

930927_R

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

コンセンサス(consensus)は、複数の人による「合意」のことです。ちなみによく似た言葉にアグリーメント(agreement)がありますが、これは「同意」と訳されることが多いようです。アルゴリズムは手順や方法、手続きといたことですので、コンセンサスアルゴリズムを直訳すると、「合意方法」という意味になりますが、「合意形成アルゴリズム」「合意形成のための計算方法」「承認アルゴリズム」といった表現がされることが多いようです。

もう少し具体的には、例えば、

「P2Pネットワークにおいて合意を取る方法」

「中央管理者不在のP2Pネットワークにおいても合意形成を可能にする方法」

「ブロックチェーンで使われている合意を得るためのメカニズム」

「分散ネットワーク上で各ノード(※1)が合意形成をする為のアルゴリズム」

「ブロックチェーンネットワークにおいて、ブロックを追加するルールを設定したアルゴリズム」

「ブロックチェーン上で、一番目にブロックを作成する権利を得るためのルール」

といった説明がなされます。

(※1)P2P(Peer – t o -Peer)は、中央サーバーを用意せず、個々の端末(Peer)がお互いに対等の関係で通信しあう通信方式です。

consensus_001_R(https://blog.peer5.com/the-p2p-witch-hunt/ より)

 

(※2)ノード(node)は、節、結節(点)といった意味ですが、オンラインネットワークに参加している各端末を指します。

 

ブロックチェーンとコンセンサスアルゴリズム

ブロックチェーンプラットフォームには、管理者が不在で取引の確認やブロックの生成に誰でも参加できる「Unpermissioned」と、参加者が管理者によって許可された者に限定されている「Permissioned」というタイプがあります。前者は「パブリック型」と呼ばれ、後者には「コンソーシアム型」「プライベイト型」があります。

パブリック型の実装例としてはBitcoin、Ethereumなどがあり、大規模なネットワークに対応できる合意形成アルゴリズムが用いられています。コンソーシアム型やプライベート型の実装例としてはRipple、Hyperledger Fabric(※3)があります。小規模な構成で効率よく動作する合意形成アルゴリズムが用いられています。

パブリック型のコンセンサスアルゴリズムとしては、代表的なものにはBitcoinで使用されるPoWがあります。他にもPoS、PoIといったものがあります。コンソーシアム型、プライベート型ではPBFTと呼ばれるものがあります。

consensus_002_R(ブロックチェーン技術を活用した システムの評価軸 ver. 1.0 平成29年3月29日  商務情報政策局 情報経済課 http://www.meti.go.jp/press/2016/03/20170329004/20170329004-1.pdf より)

(※3)Hyperledger Fabricは、認証されたノードだけが参加でき、仮想通貨のないノードを維持管理する運営主体による台帳管理システムです。ビットコインなどで使われるPoW(Proof of Work)は、「確率的ビザンチン合意」と言われる決済が確率現象なのに対して、Hyperledger Fabricでは確定的な合意形成アルゴリズムによる「ファイナリティ(決済の確定性)」を保つことができるという特徴があります。ビットコインの取引では、6回程度の後続ブロック生成が行われたことをもって、ファイナリティが得られたとみなしています。

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

〇 PoW(Proof of Work:プルーフオブワーク)

PoW(proof of works)とはビットコインなどに用いられているもので、最新ブロックを生成しブロックチェーンに連結する権限を、ハッシュ計算(※4)をいち早く処理したノードに与えるというものです。

〇 PoS(Proof of Stake:プルーフオブステーク)

最新ブロックを生成しブロックチェーンに連結する権限を、ブロックチェーンで管理している資産が一番多いノードに与えるというもので、ブロックの追加のためにはハッシュ関数等の計算による解が必要ですが、資産の大きいノードは難易度の低い計算問題が割り当てられます。このため消費電力的にもPoWよりも少なくて済みます。

〇 PoI(Proof of Importance:プルーフオブインポータンス)

PoS の改良型で、ブロックチェーン内の資産だけでなく取引量も勘案し、PoSでの資産の偏りの是正した仕組みです。仮想通貨ではNEMなどで使用されていて、NEMを多く抱えているだけでなく、使用頻度が高いほどマイニングの難易度を低くする仕組みになっています。ノードの重要性を計算して、重要性の大きなノードに優先権を与えるわけです。

〇 PBFT(Practical Byzantine Fault Tolerance:プラクティカル ビザンチン フォールト トレランス)

PBFTはコアコードと呼ばれる特定のコードに、最新ブロックを生成しブロックチェーンに連結する権限を集中させ、約3分の2以上の合意でトランザクションの承認を行うものです。

「ビザンチン」とあるように、「ビザンチン将軍問題(※5)」を解決するためのアルゴリズムとされています。ノードの総数、不正ノード数の上限などの条件があること、高速な処理が可能といった」特徴があります。

〇 PoC(Proof of Consensus:プルーフ オブ コンセンサス)

リップル(XRP)が採用している方式です。「バリデーター(Validator)」と呼ばれる信頼された承認者の80%が有効と判断した場合に分散型台帳に記録されるというものです。PoWのような大量の電気を消費することもなく、数秒で承認が完了します。

 

(※4)ハッシュ(hash)は、メッセージを特定するための暗号化技術で、

ハッシュ関数と呼ばれる手法を使って、ハッシュ値と呼ばれるデータを作り、それを比較することで改変がないか確認します。(NTTPCコミュニケーションズ 用語解説辞典 https://www.nttpc.co.jp/yougo/ハッシュ値.html より)

ちなみにビットコインではSHA-256とRIPEMD-160というハッシュ関数が使われています。

(※5)ビザンチン将軍問題とは、2013年にチューリング賞を受賞した数学者・コンピュータ科学者のレスラー・ランポート(Leslie Lamport)博士らが考案した分散システム上の信頼性に関する問題です。

Wikipediaでは次のように説明しています。

相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である。(https://ja.wikipedia.org/wiki/ビザンチン将軍問題 より)

 

(参考文献)

・NII Today」69 平成29年9月

・「国内の銀行間振込業務におけるブロックチェーン技術の実証実験に係る報告書」ブロックチェーン研究会 2016年11月30日

・東京大学公共政策大学院ワーキング・ペーパーシリーズ「ブロックチェーン技術のテクノロジーアセスメント」 2017年10月

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です