前回の記事でも確認したようにオリジナルのPBFTはノードの数が50以上に増えると、コミュニケーションコストが増大してしまう。Zilliqaは600のノードが1つのシャードを構成する設計になっているので、このままではハイスループットは実現できない。
Zilliqa設計の非技術的な話
Communication cost of PBFT
※以下、The Zilliqa Design Story Piece by Piece: Part 3 (Making Consensus Efficient)より
PBFTでは善意のノードはその他のノードと密にコミュニケーションを取る必要がある。各ノードが各ノードに対してn個のメッセージをやり取りする場合、ネットワーク全体でn²のコストがかかってしまう。
Cost of authenticating messages
ビザンティンネットワークにおいてメッセージのやり取りをする場合、ノードAがノードBからメッセージを受け取ったときには、そのメッセージが確かにBによって送信されたものであり、man-in-the-middle攻撃によって改竄されていないことを確かめなければならない。さもなければ、メッセージの正当性に確信を持つことができない。
これを解決するためにはAとBの間でのみ共有される鍵を生成し、鍵によってタグを作り、メッセージに添付させれば良い。タグは鍵によってしか作れないので、メッセージの真正性を確かめることができる。
メッセージ認証符号を使ってこのようなタグを作ることができる。以下の図が示すように、送信者はメッセージと秘密鍵を使ってタグを生成し、メッセージと共に送信し、受信者は受け取ったメッセージと予め共有されている秘密鍵を使って同様のやり方でタグを生成する。タグが一致していれば、メッセージの真正性を確認できる。
The Zilliqa Design Story Piece by Piece: Part 3 (Making Consensus Efficient)
※MACとデジタル署名は異なるので混同しないように注意。このあたりの話は結城氏の以下の入門書が詳しい。
売り上げランキング: 8,348
ここで問題になるのが、やり取りされるメッセージの受け渡し回数。各ノードのペアごとに秘密鍵が設定されており、且つリレイヤーの役割を果たすノードは自分が使うメッセージ以外を再度ブロードキャストしなければいけないのでノードの数nに対して、メッセージのやり取りはn(n-1)/2回になる。これでは、ハイスループットどころの話ではなくなってしまう。
The Zilliqa Design Story Piece by Piece: Part 3 (Making Consensus Efficient)
Public key cryptography to improve efficiency
ここでデジタル署名が登場。公開鍵を使ったメッセージの送受信の場合、より少ない鍵の共有で済ますことが可能。上述の例だと、3回で済む。
シャードがn個のノードで構成されている場合、nの伝達はn-1回。
MACの代わりにデジタル署名を使うことで、600個のノードで構成されるシャード内でのメッセージのやり取りを179,700回から599回に削減できる。
The Zilliqa Design Story Piece by Piece: Part 3 (Making Consensus Efficient)
Reducing the size of each message using a multi-signature scheme
デジタル署名よりもよりよい方法はあるだろうか？あるらしい。
ところでPBFTはブロックチェーンに取り込まれた時点でファイナリティが得られるのであった。このファイナリティは、シャード内で大半を占める善意のノードが各ブロックに署名を行っているという事実から確保されている。あるノードが署名を行うとき、それはそのノードがブロックの中身を検証し、トランザクションが有効であることを確認した、ということを意味する。PoWベースのコンセンサスでは、あるノードがブロックを生成し、残りのノードが受容と拒否を行うが、これが一時的な分岐を引き起こす。
以下のような署名方法を考える。各ノードが署名を行い、署名済みのブロックを他のノードのブロードキャスト、他のノードは自身の署名を添付していく。十分なコミュニケーションが取れた後、ブロックは各善意のノードの署名の過半数を得る。
これはマルチシグナチャーと言われる手法で、n人の参加者からのn個の署名を一定のサイズの1つの署名にまとめあげる。
How does a (simplified) multi-signature work?
登場人物
- n人の署名者（公開鍵、秘密鍵）
- 検証者（最終的な署名の検証を行う）
- アグリゲーター（各署名者によって提出された署名をまとめる）
（以下では各ノードは善意で、メッセージへの署名に協力すると仮定する）
まとめられた署名が検証者によって検証されるとき、検証者は全ての署名者が適切に署名を行っているか否かをチェックする（※検証方法の詳細は要調査）。署名検証は全ての署名者が適切に署名した場合にのみ成功する。
マルチシグナチャーのスキームには2つのステップがある。
各ノードはアグリゲーターに公開鍵を送る
全ての公開鍵は1つの公開鍵を作るためにまとめられる。
Aggregated Public key = Public key_1 + Public key_2 + …. + Public key_n.
こんな感じ。
まとめられた1つの公開鍵は検証者に送られ検証される。
アグリゲーターは各署名者から署名をもらうためにメッセージを送信する。
アグリゲーターは各署名者とインタラクティブなプロトコルを開始する。これには更に3つのステップがある。
Commit phase
各ノードはランダム性を生成（コミットする）。これはサイコロを振って、出た目を紙に書き、ボックスに入れ、ロックし、アグリゲーターに送ることに相当する。アグリゲーターはボックスを開けることはできない。
Challenge phase
アグリゲーターは各コミットメントを1つにまとめる（※addition or multiplication）。次にまとめられたコミットメント、まとめられた公開鍵、そしてメッセージを使って、”チャレンジ”を生成する。チャレンジは各ノードが実際に公開鍵の秘密鍵を知っていることを認証するために使用される。
※addition/multiplicationは『Modular multiplication (article) | Khan Academy』が参考になるかも。
Response phase
各ノードは秘密鍵の使用が要求されるレスポンスを送ることで、チャレンジに対して応対する。レスポンスはアグリゲーターによってまとめられる。各レスポンスは、署名者が公開鍵に対応する秘密鍵を知っていることの証明のようなもの。
最終的にまとめられた署名はチャレンジとまとめられたレスポンスのペアになり、これは最初のステップで生成されたまとめられた公開鍵に対して検証されることになる。
まとめられた署名のサイズは一定で、署名者の数には依存しない。下の図の詳細説明はリンク先に記載あり。
The Zilliqa Design Story Piece by Piece: Part 3 (Making Consensus Efficient)
検証者がまとめられた署名をチェックするとき、検証者は各署名者が適切にプロトコルに則ったかはチェックせず、全ての署名者が全体としてプロトコルに則り、且つ秘密鍵の知識を証明したかのみをチェックする。故に、検証者の決定はall-or-nothing形式になる。
各所に付記した点以外にもシャード間の通信など疑問点が多いのでホワイトペーパー（PDF）を読む必要がある。Zilliqa, EOS, DfinityはEthereum以外のプラットフォーム候補として軽く調べておきたいところ。
