前回の記事で、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ノードが公開鍵をアグリゲーターに送信します。
公開鍵は収集されて一つの公開鍵が発行された後、収集された公開鍵は認証者に転送されます。
公開鍵の収集プロセス
-
- コミット・フェーズ
nノードはランダムなパータンを生成してアグリゲーターに送信(コミット)する。 - チャレンジ・フェーズ
アグリゲーターはコミットを収集して、収集されたコミットと公開鍵とメッセージを使用してチャレンジを生成します。
チャレンジの目的は、nノードが公開鍵の秘密鍵を知っているかの認証のためです。 - レスポンス・フェーズ
nノードはチャレンジに対して、秘密鍵を使用するレスポンスを送ります。
レスポンスはアグリゲーターによって収集されます。
このレスポンスこそが、n署名者が秘密鍵を所有している証拠となります。
- コミット・フェーズ
最終的にまとめられた署名はチャレンジとレスポンスのセットであり、初期に認証者に収集された公開鍵と検証します。
まとめられた署名のサイズは一定であり、署名者の数には依存しません。
検証者がまとめられた署名をチェックする際に、検証者は各署名者が適切にプロトコルに則ったかはチェックせず、全ての署名者が全体としてプロトコルに則り、且つ秘密鍵の知識を証明したかのみをチェックします。
故に、検証者の決定は「all-or-nothing形式」となります。
デザインストーリー3 – ZILLIQA –
CoinPicks
– 仮想通貨の質問や悩みについて筆者がズバリお答えします –
– リアルタイムで仮想通貨の情報収集しています –
– CoinPicksは「学ぶ」「動く」「繫がる」場所です –