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

• ZILLIQA – コンセンサスプロトコル – | CoinPicks

 

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

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

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

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

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

 

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

 

CoinPicks

---

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

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

 Twitter

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

CoinPicks – オンラインサロン –

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

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

 

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

---

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

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

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

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

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

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

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

 

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

---

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

シャード内には、リーダーであるプライマリーノード（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とは、パーミッションレスな分散型ネットワークを安全に拡張できるように設計されたブロックチェーンプラットフォームです。
また、イーサリアムへの実装が進められているSharding（シャーディング）というソリューションをブロックチェーン上に実装しています。

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

 

Sharding（シャーディング）とは

---

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

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

• Sharding Phase 1 の具体的な仕組みとセキュリティ課題

シャーディングには、ネットワークシャーディング（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ノードが入っているシャードがあるとします。
そのなかの３分の１が悪意のノードである確率はおおよそ0.04としています。
この確率はシャードのサイズが増えるほどに小さくなります。

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

 

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

 

CoinPicks

---

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

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

 Twitter

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

CoinPicks – オンラインサロン –