PoWにおけるコンセンサスの解釈

indiv Report
今日はZilliqaを例にコンセンサスについて
考えてみたいと思います。

コンセンサスは文字通り「合意」という意味ですが、
もう少し細かく
「どのチェーンが正当であるかを決めるルールに従って、
予め定められた比率以上の参加者が同じ選択を取ること」
としたいと思います。

 

PoWにおけるコンセンサスの解釈

ビットコインの場合、ブロック生成者になるための条件は、「他の人よりも早く、適切なナンスを見つけ出すこと(たくさんの計算を素早く行うこと)」となります。

マイニングにで何を早く見つけるための計算をしているのかを知らない方が多いです。ナンスを見つけたマイナーがブロック報酬を得る権利を得ることができます(ビットコインの場合 – 12.5BTC / 10分)。このナンスについての説明はLab内で詳しくしています。

比較対象がないと分かりづらいのでEOSを例にしてみます。

EOSは21人のブロック生成者を選び、持ち回りでブロック生成者を務めます。
そして他のブロック生成者の承認をもってブロックが生成される仕組みです。

ブロックが正当なものとして認められるのはどの段階なのか?

コンセンサス設計によって全然異なるので面白い。

例えばビットコインはナンスを見つけたマイナーがブロック生成権利を持ち、正当なブロックの可否を決めるのはその後、一方EOSは2/3以上の承認を得た段階でブロック生成と承認が完了する。

ちなみにこれはPoWとPoSの違いではありません。

例えばEOSとEthereum Casperは両方共PoSですが、仕組みは異なります。
同様にPoWであってもコンセンサスの形成方法が異なるケースがあります。
ちなみにビットコインとEthereumは両方ともNakamoto consensusという仕組みで運営されています(ビットコインはSHA256, EthereumはEthashなのでアルゴリズムは異なります)。

Nakamoto consensusとは、P2Pネットワーク上でビザンチン将軍問題を解決ではなく、「迂回」するためのコンセンサス(合意)設計と一言で言えます。

筆者は解決ではなく迂回という言葉がしっくりきており、なぜかというとマイニングには多大な電力という負のインセティブがあるからこそ、マイナーはネットワークを攻撃するよりもマイニングに参加する方が合理的なわけで、攻撃するメリットの方が大きければ攻撃するわけです。

つまり根本的な問題の解決をしているわけではなく「迂回」なのです。

Zilliqaは部分的にPoWを使っていますが、Nakamoto consensusではありません。

また、EOSと同じく中心メンバーとなるブロック生成者のグループを作り、順にブロックを生成していく仕組みになっていますが、Zilliqaの場合PoWによって誰がブロック生成者になるかが決定されます。
ブロック生成者になることを希望する人間は一定期間ごとに開催される「計算競争」に参
加し、それに打ち勝てばブロック生成者グループに入ることができる、というのがZilliqaの仕組みです。

簡単にまとめるとEOSとZilliqaは、

  1. 代表を選ぶ
  2. 代表者たちの中で、順にブロック生成者の役割を回す
  3. ブロック生成者を入れ替える

という順番になっていると言えます。

EOSの場合、代表は投票によって、Zilliqaの場合はPoWの計算競争によって決まります。

一方でビットコインやEthereumの場合、我々は直接計算競争に参加することができます。
ただし、先述したようにNakamoto consensusの場合、代表ノードは必要なく、最初にナン
スを見つけた人が独占的にブロックを生成することができます。

関連記事
https://coinpicks1.wordpress.com/ethereum/

 

CoinPicks LINE@

おかげさまで現在お友達が1057名を突破しました。仮想通貨の最新情報や重要なファンダ情報などを「プッシュ通知」にて誰よりもはやくお届けします。

https://platform.twitter.com/widgets.js

CoinPicks Lab

学習項目
 
  • 分析レポート
  • Bitcoinについて
  • Ethereum経済圏について
  • ST(セキュリティートークン)について
  • PoS型プラットフォームトークンについて
  • ステーブルコインについて
  • コンセンサスアルゴリズムについて
  • トークン設計について
  • 流通設計について
  • CBDCについて
  • 各インフルエンサーによる特化した情報
  • Q&A項目の共有
  • 基礎学習
  • 掲示板

https://lounge.dmm.com/detail/761/

などなど…
今後も学習項目は増えていきます。

ZILLIQA – コミュニケーションコスト –

前回の記事で、ZILLIQAが採用しているコンセンサスプロトコル「PBFT」についての概要とメリットについて説明した後に、最後にはPBFTの課題について言及しました。

 

PBFTのコミュニケーションコスト


PBFTは、シャード内のノードが50以下の条件下で一番効率的になります。
ZILLIQAはノードが600あり、PBFTの仕組みが参加している全ノードの合意が必要なため、ノード間のコミュニケーションの負荷が大きくなります。
各ノードが合意をするプロセスの中で、nメッセージを送信するので、全ネットワークの通信はn²となりメッセージの認証コストが大きくなります。

*以下よりn=600とします。

メッセージの認証プロセスとコストを知る

仮にノードAがノードBからメッセージを受信するとき、ノードBがメッセージを送信したことと送信の際に改竄がなかったことを確かめなければいけません。

その方法としてノードAとノードBで共通の秘密鍵を作ります。
下記の図を参照して頂くとわかりやすいです。

送信者は共通の秘密鍵とメッセージを使ってタグを発行します。
その後メッセージとタグを受信者に送ります。
受信者は送られてきたタグの同一性を確かめます。

このように、秘密鍵とメッセージをインプットしてタグをアウトプットする方法を、MAC(Message authentication code)と言います。

しかし、MACにも問題があります。
シャード内にnノードがあるとしたら、ノード間同士で秘密鍵とタグが必要になるため、全部n(n-1)/2のメッセージが必要になります。

仮に4ノード存在する場合、下記のように6メッセージ必要になります。

 

コミュニケーションコストの改善策


デジタル署名の採用

ノード間のメッセージ送受信の際に公開鍵によるデジタル署名を使用します。

デジタル署名は、当時高コストだったため使用されていなかったが、現在は大幅にコストダウンしているため、MACによる署名からデジタル署名の採用率が高まっています。

デジタル署名の利点として、発行するメッセージとタグの数を減らすことができます。
下記の図を参照して頂くとわかりやすいです。

仮にデジタル署名を使用して4ノード存在する場合、599メッセージ必要になります。
MACによる署名の場合、179,700メッセージ必要になります。

このようにデジタル署名は、PBFTのコミュニケーションコストを大幅に改善することが可能です。

マルチサイニングの採用

nノード間のn個の署名を一定のサイズで1個にまとめます。

そのプロセスを簡単に説明します。

n署名者:公開鍵と秘密鍵を所有する署名者。
認証者:最後の署名を認証する者。
アグリゲーター:各署名者からの署名を収集する者。

マルチサイニングは2段階あり、まずはnノードが公開鍵をアグリゲーターに送信します。
公開鍵は収集されて一つの公開鍵が発行された後、収集された公開鍵は認証者に転送されます。

公開鍵の収集プロセス
    1. コミット・フェーズ
      nノードはランダムなパータンを生成してアグリゲーターに送信(コミット)する。
    2. チャレンジ・フェーズ
      アグリゲーターはコミットを収集して、収集されたコミットと公開鍵とメッセージを使用してチャレンジを生成します。
      チャレンジの目的は、nノードが公開鍵の秘密鍵を知っているかの認証のためです。
    3. レスポンス・フェーズ
      nノードはチャレンジに対して、秘密鍵を使用するレスポンスを送ります。
      レスポンスはアグリゲーターによって収集されます。
      このレスポンスこそが、n署名者が秘密鍵を所有している証拠となります。

最終的にまとめられた署名はチャレンジとレスポンスのセットであり、初期に認証者に収集された公開鍵と検証します。

まとめられた署名のサイズは一定であり、署名者の数には依存しません。

検証者がまとめられた署名をチェックする際に、検証者は各署名者が適切にプロトコルに則ったかはチェックせず、全ての署名者が全体としてプロトコルに則り、且つ秘密鍵の知識を証明したかのみをチェックします。

故に、検証者の決定は「all-or-nothing形式」となります。

 

デザインストーリー3 – ZILLIQA

 

CoinPicks


– 仮想通貨の質問悩みについて筆者がズバリお答えします –

友だち追加

リアルタイムで仮想通貨の情報収集しています –

 Twitter

–  CoinPicksは「学ぶ」「動く」「繫がる」場所です –

CoinPicks – オンラインサロン –


ZILLIQA – コンセンサスプロトコル –

前回の記事でシャーディングについての概要説明と問題点と解決策について説明しました。

 

コンセンサスプロトコルの採用


ビットコインやイーサリアムが採用しているコンセンサス・プロトコルは、「ナカモトコンセンサス」(Nakamoto Consensus)という仕組みを採用しています。

ナカモトコンセンサスを採用しているビットコインやイーサリアムに限って言えば、「スケーラビリティ」を犠牲にすることで「分散性」と「セキュリティ」を取っています。

対してZILLIQAは、”PBFT”と呼ばれるコンセンサス・プロトコルを採用しています。
ZILLIQAに限って言えば、「分散性」を犠牲にすることで「スケーラビリティ」とセキュリティ」を取っています。

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

コンセンサス・メカニズム(合意の仕組み)と一連のルールを指します。
主に以下の4つに分解することができます。

  • Proof of Work (PoW)
  • Block Selection(ブロック選択)
  • Scarcity(希少性)
  • Incentive Structure(インセンティブ構造)

ナカモトコンセンサスによるブロック承認者の選出は、PoWによって決められます。
PoWによる選出には、多大な計算量を必要としており時間を要します。

 

PBFTによるコンセンサスの流れ


PBFTは”Practical Byzantine Fault Tolerance”の略称です。
前提として、シャード内のノードのうち3分の1が悪意を持っていることを前提にしています。

シャード内には、リーダーであるプライマリーノード(Primary Node)と、それ以外のバックアップノード(Backup Node)が存在します。

PBFTのプロセス

Pre-prepare phase

リーダーであるプライマリーノードが「prepareメッセージ」の発信によって、グループ内のノードが承認しなければいけないレコードを送信します。

Prepare phase

「prepareメッセージ」を受信したバックアップノードは、リーダーによってアナウンスされたレコードの正確さと正当性を検証します。
その後、「prepareメッセージ」を他のノードに一斉送信します。

Commit phase

「prepareメッセージ」を受信した各ノードは、Commit Messageをグループに一斉送信します。
各ノード群は、他のノードから送信されるCommit Messageが一定量集まることで、リーダーによってアナウンスされたレコードに合意していることを確認します。

 

PBFTを採用する3つのメリット


PBFTを採用することによる3つのメリットについて解説します。
このメリットは、ナカモトコンセンサスと比較したメリットとなります。

Transaction finality

PBFTはFinality(ファイナリティ)に対して優位性があります。
ナカモトコンセンサスを採用しているビットコインの場合、ブロック生成後に”完了状態”となるまでに、最低でも6承認待たなければいけません。
1承認約10分とした場合、6承認得るのに約1時間を要します。
これでは、日常的な決済に活用できるとは言えません。

対してPBFTは、上述した”PBFTのプロセス”によって、生成されたブロックが”完了状態”となる為、ブロックが分岐することなく瞬時に決済が完了します。

Low energy footprint

PBFTはメッセージによるグループ合意を得ているため、エネルギー消費を抑えることができます。
対してPoWは、多大な計算量を必要とするためその分エネルギー消費が必要になります。
しかしZILLIQAでは、ノードの善悪を審査する時のみ(シビルアタック)Powを採用しています。
ノードの正体が一旦判明したら、PBFTを起動することで複数のブロックを連続でコンセンサスを求めます。

Powによる審査は100ブロック毎に採用しています。対して、ナカモトコンセンサスは1ブロックごとにPowによるコンセンサスが必要となります。

Low reward variance

PBFTは参加している全ノードに対してインセンティブを与えることが可能です。
ナカモトコンセンサスの場合、多大な計算によって難解な問題を一番早く解決できたマイナーのみにインセティブがあります。

参加者全員にインセティブを与えることができる設計は、非常に興味深く別途記事にて詳細をお伝えしたいと思います。

 

PBFTの課題


PBFTは、グループ(ノード群)が50以下の条件下で一番効率的になります。
しかし、ZILLIQAは悪意のあるノードにシャードをコントロールされてしまう可能性を考慮して、シャードのサイズの最小限を600ノードに設定しています。

「効率性」と「セキュリティ」でトレードオフの関係であることがわかります。

ノード群が多くなることで、グループ内の「コミュニケーションコスト」によって、PBFTの効率が悪くなります。

 

デザインストーリー2 – ZILLIQA –

 

CoinPicks


– 仮想通貨の質問悩みについて筆者がズバリお答えします –

友だち追加

リアルタイムで仮想通貨の情報収集しています –

 Twitter

–  CoinPicksは「学ぶ」「動く」「繫がる」場所です –

CoinPicks – オンラインサロン –


ZILLIQA – ネットワークシャーディング –

ZiLLIQAとは


ZILLIQAとは、パーミッションレスな分散型ネットワークを安全に拡張できるように設計されたブロックチェーンプラットフォームです。
また、イーサリアムへの実装が進められているSharding(シャーディング)というソリューションをブロックチェーン上に実装しています。

「パーミッション」とはアクセス権を意味しており、単純にビットコインやイーサリアムのような、中央管理者が存在しないブロックチェーンを指します。
対義語として「パーミッションレス」が存在しており、リップルのような中央管理者が存在するブロックチェーンを指します。

 

Sharding(シャーディング)とは


シャーディングとは、取引処理を分割して複数のグループで検証を同時進行する事でスケーラビリティ問題を解決する為のソリューションです。
良く誤解があるのですが、シャーディングはイーサリアム独自の技術というわけではなく、あくまでもデータを分散して処理するための解決策ということになります。

シャーディングに関する詳細は、本稿では割愛させて頂きます。
詳細を知りたい方は、Osukeさんの記事がおすすめです。

シャーディングには、ネットワークシャーディング(Network Sharding)、トランザクションシャーディング(Transaction Sharding)、コンピュテーショナルシャーディング(Computational Sharding)など、様々な種類が存在します。

ZILLIQAが採用しているのは、ネットワークシャーディングです。

 

ネットワークシャーディングとは


ネットワークシャーディングの論理は、仮に1,000ノードのネットワークがある場合、100ノードずつ10のシャードに割り振ります。
シャードは並列にトランザクションを処理できるため、1つのシャードが秒間10トランザクションを処理可能とする場合、10シャードは合計でその10倍、つまり秒間1,000件の取引を処理できることになります。

従来ではブロードキャストされたトランザクションは、1つのノードが処理します。
しかし、シャーディングによってノードを分割することで、処理を分割することでノードの負担を減らすことができます。

元々データベース管理システムの分野で使われていた技術ですが、「シャーディング」は2015年にZILLIQAのチームメンバーによって初めて、ブロックチェーンでの活用を主張されました。

上記の説明のように、シャーディングを論理で語るのは容易ですが、実際にシャーディングを実現するためには以下の問題を解決しなければなりません。

  • シビル攻撃問題
  • シャード分割問題
  • シャードのサイズ

 

シャーディングを実現するための3つの問題


シビル攻撃問題

問題
ZILLIQAはパブリックブロックチェーンのため、インターネット上なら誰でもアクセスが可能です。
結果的に悪意のあるユーザーは、1人で複数のノードを作成することができ、多数のコンセンサス(合意)を演出(シビル攻撃)することを可能にします。

解決策
ZILLIQAはプルーフ・オブ・ワーク(POW)を採用しています。
ユーザーがネットワークに参加するためには、POWの作業を義務付けます。
POWの作業をすることで、ユーザーはネットワークに参加するためのエントリーが可能になります。
その後、ネットワークの既存ノードがエントリーを確認します。
悪意のないことが認められると、ネットワークへの参加が認められます。

シャードの分割問題

問題
仮に1,000ノードのネットワークがあるとします。
それを10シャードに分割する際に、どのノードをどのシャードに割り振るかについて慎重になる必要があります。
仮に悪意のあるノードが1箇所に集まると、ネットワーク全体の安全性が損なわれる可能性があります。

解決策
ZILLIQAではまず、DS Committee (Directory Service Committee)という専用ノード群を選出します。
DS Committeeの選出はPOWを通して行われ、Committeeは一定の間隔で、既存ユーザーの除去と新規ユーザーの選出を1人ずつ行います。

ユーザーの除去方法は、先入れ先出しの順番で行われ、常にネットワーク内のユーザー数は一定となります。新規ユーザーの選出方法は、POWによる計算で最初に勝ち抜いたユーザーが選出されます。

コミッティーは、メンバーが選定されたら、シャーディングのプロセスを起動する。ここで、ネットワークに参加しているすべてのノードがもう一回プルーフ・オブ・ワーク作業をしなければならない。
つまり、悪意のあるユーザーは選出されるまでPOWを繰り返す必要があり、コストデメリットによって攻撃を未然に防ぐことが可能になります。

シャードのサイズ

問題
シャード内のノードの数が少ないほどに、悪意のあるノードにシャードをコントロールされてしまう可能性があります。

解決策
シャード内のノードの数をいくつにするのかついて慎重になる必要があります。
仮に100ノードが入っているシャードがあるとします。
そのなかの3分の1が悪意のノードである確率はおおよそ0.04としています。
この確率はシャードのサイズが増えるほどに小さくなります。

仮に600ノードが入っている場合は、悪意のノードが全体の3分の1以上を占める確率は1/100万まで下がります。
そのため、ZILLIQAはシャードのサイズの最小限を600ノードに設定することで、悪意のあるノードが入ってしまう可能性を最小限にとどめます。

 

デザインストーリー – ZILLIQA

 

CoinPicks


– 仮想通貨の質問悩みについて筆者がズバリお答えします –

友だち追加

リアルタイムで仮想通貨の情報収集しています –

 Twitter

–  CoinPicksは「学ぶ」「動く」「繫がる」場所です –

CoinPicks – オンラインサロン –