Zugによるシンプルで高速なコンセンサス

Zugによるシンプルで高速なコンセンサス

Casperノードは、プラグイン可能なコンセンサス・プロトコルを念頭に置いて設計されました。これまではHighwayのみの選択肢となっていたところCasper 2.0にてよりシンプルなコンセンサスプロトコル（日本語）であるZugが追加されました。

Zugプロトコルは、バリデータの重みの最大3分の1が欠陥のあるバリデータに起因していることを要求します。また、正しいバリデータがメッセージを配信するまでにネットワーク遅延の上限が存在することを前提としています。上限値は未知であるが存在します。このような条件下では、すべての正しいノードは最終化されたチェーン上のブロックにて合意に達します。

もちろん、ネットワーク内のすべてのノードが同じプロトコルを実行しなければ連携できないが、新しいネットワークを立ち上げるときや既存のネットワークをアップグレードするときに、Chainspecファイルにて consensus_protocol をHighway もしくは Zugにて設定できるようになりました。Casper MainnetはZugに切り替わりました（2025/05/06）。

How Zug Works​

すべてのラウンドで、指名されたリーダーはブロックを提案するために提案メッセージ（proposal message）に署名することができます。提案は親ブロックが提案された以前のラウンドを指します。

その後、各バリデータは提案のハッシュを含むエコーメッセージ（echo message）に署名します。正しいバリデータは1ラウンドにつき1つのecho messageのみ署名するため、定足数（quorum）が署名できる提案は最大1つとなります。定足数（quorum）とは、総重量が (n + f) / 2 より大きいバリデータの集合のことであり、ここで n は全バリデータの総重量、f は欠陥のあるバリデータの最大許容総重量となります。

したがって、どのような2つの定足数でも必ず1つは正しいバリデータが存在しています。n > 3f である限り、 (n + f) / 2 < n – f となるため正しいバリデータは定足数を構成します。

定足数が満たされており、かつ他のいくつかの条件が満たされている場合 (後述)、その提案は受け入れられます。次のラウンドのリーダーは、この提案を親とする新しい提案を行えるようになっています。

時間内に提案を観測した各バリデータは、投票（Vote(true)）メッセージに署名します。バリデータが待ち時間にタイムアウトした場合、代わりに 投票（Vote(false)） メッセージに署名します。定足数以上のバリデータが true に署名した場合そのラウンドはコミットされ提案とそのすべての先祖が確定します。定足数以上のバリデータがfalseに署名した場合はskippable（スキップ可能）となります。つまり、次のラウンドのリーダは、以前のラウンドの親を持つブロックを提案することができます。正しいバリデータは true か false のどちらかしか署名しない為、ラウンドはコミット可能にもスキップ可能にもなるが、その両方にはなり得ません。

受け入れ可能な提案がない場合、すべての正しいバリデータは最終的にfalseに投票するため、そのラウンドはスキップ可能になります。これがプロトコルを live にする理由です。次のリーダが最終的に提案を行うことができるのは、親となる承認済みの提案があるか、そのラウンドが最終的にスキップ可能になり以前のラウンドの提案を親として使用可能となるためです。タイムアウトが十分長ければ、正しい提案者のブロックはたいてい確定されます。

提案が受理されるためには親提案も受理されなければならず、親と現在のラウンド間のすべてのラウンドがスキップ可能でなければなりません。これがこのプロトコルを安全（safe）なものにしています。2つのラウンドがコミットされた場合、それらの提案はスキップ可能ではないため互いの先祖でなければならず、プロトコルは相反する2つのブロックを確定することはできません。

もちろん、最初のブロックも存在します。それ以前のすべてのラウンドがスキップ可能な場合(特に最初のラウンド)、 リーダーは親を持たないブロックを提案することができます。

すべての新しい署名付きメッセージは、楽観的にすべてのピアに直接送信されます。我々は、たとえ完全な接続状態でなくても最終的にすべてのバリデータがそのメッセージを見ることを保証。これは、プル（Pull）リクエストベースのランダム化ゴシップメカニズムによって達成されます。そこでは、ローカルプロトコルの状態のランダムな部分に関する情報を含むSyncRequestメッセージがランダムなピアに定期的に送信されます。ピアはそれを自分のローカル状態と比較し、記録したすべての署名付きメッセージで応答します。

重要
Zugプロトコルは次のように要約できる：

・各ラウンドにおいて、ラウンドリーダーは新しいブロックBを提案する
・各バリデータは B に署名したechoメッセージを作成しブロードキャストする
・適切なブロックBが67%のバリデータからechoを受け取ったとき、次のラウンドが始まる：
　　- 次のラウンドが始まる。次のリーダーはチャイルド Bを提案できる
　　- すべてのバリデータが署名して投票メッセージをブロードキャストし 「yes」に投票する
・タイムアウトまでにこの操作が行われなかった場合、バリデータは代わりに「no」に投票する
　　- 67%の投票がない場合、次のラウンドも開始される。次のリーダは以前のブロックのチャイルドを提案し、このラウンドをスキップすることができる。
・67%の賛成票があればBは最終決定され、すべての先祖とともに実行される（通常、この時点ですでに次のラウンドが始まっている）

提案、投票、echo（エコー）はブロードキャストされるため1つの正しいノードがメッセージを受信すると、最終的にすべてのノードがそれを受信することをご留意ください。正直なバリデータは1ラウンドに1回だけechoまたは投票を送信します。そのため、34%のバリデータが二重署名をしない限り1ラウンドにつき最大でも1つのブロックに67%のエコーが送られることになります。ある提案に対して67%のエコーがある限り次のラウンドが始まり、Zugが行き詰まることはありません。そうでない場合は、全員が反対票を投じ次のラウンドが始まります。

  • ▶Expand to see a simple example
    Zuk・コンセンサスを示す簡単なシナリオを見てみましょう。
この例では、異なるリーダーとノードがカードスーツに投票する5つのラウンドを示しています。
一番下の行は、ラウンドが確定したかどうかを示しています。ラウンド 5 が最初の最終ラウンドであることに注意してください。

ラウンド1では、♥を提案したリーダーがいましたが時間がかかったため他のノードはタイムアウトして反対票を投じました。
最初のラウンドは提案ありのためスキップ可能だったが何も最終決定されませんでした。

ラウンド2では、2番目の提案者が♥を見て、♣を♥の子として提案しました。あるノードは賛成票を投じ、あるノードはタイムアウトして反対票を投じました。
つまり、ラウンド2は決定がなかったため何も出力されませんでした。

ラウンド3では、リーダーが♦を♣の子として提案しました。
リーダーがまだ遅いと仮定すると、全員が反対票を投じ、ラウンド3は提案があったにもかかわらずスキップ可能になった。

ラウンド4では、提案者がクラッシュしたか悪意があったかもしれないため全員タイムアウトし否決しました。

ラウンド5では、リーダーはラウンド3の♦提案を見なかったが否決を見ました。
つまり、彼らから見れば、ラウンド3と4はスキップ可能であり提案はなかったことになります。
したがって、ラウンド5のリーダーは♠を♣の子として提案しました。アルゴリズムはフォークに遭遇しました。
ともあれ、全員が賛成票を投じラウンド5が確定しました。つまり、その瞬間に♥、♣、♠はすべて確定しその順番で実行されます。
その結果、今後の提案者はすべてこのラウンドの子を提案する必要がある。

重要な注意事項

定数未投票のラウンドの提案であっても、間接的に最終決定となる可能性がある。

ラウンドが最終決定でもスキップ可能でもない場合、そのラウンドは将来のある時点で最終決定される可能性が高いです。
ネットワークのウェイトの3分の1が賛成票を投じると、エコー定数のプロポーザルが形成されます。
その結果、他のすべての正直なノードは、最終的にこのエコーの定足数と受け入れられた提案を見ることになり、将来のラウンドで親として機能することになります。

ノードはエコーの定足数を持ち、その提案のすべての先祖がエコーの定足数を持つとき賛成票を投じます。
また、それらの先祖はエコーの定足数を持っており、先祖のいないラウンドはすべて無投票の定足数を持っています（スキップ可能）。

このアルゴリズムは、必ず Accepted proposal か Finalized round の行の少なくとも一つに結果を出します。
ラウンドで提案が受理されなかった場合、全員がタイムアウトしてノーと投票する。そうでない場合、その提案は定数以上の票を持つ誰かに公開され最終的には全員に公開されます。

Zugの利用価値

  • 提案ブロックを送信しなければならないリーダーを除けば、各バリデータノードは各ラウンドで2つの小さなメッセージをブロードキャストするだけとなり通信のオーバーヘッドは非常に小さいものとなる
  • HighwayやPBFT（Practical Byzantine Fault Tolerance）とは異なり、またHotStuffのようなパイプラインプロトコルと同様に次のリーダーがブロックを提案するために必要なメッセージ（エコー）は1ラウンドのみでありブロックとそのチャイルドの間の遅延を減らすことができる
  • しかし、Zugは、HotStuffとは異なり子（チャイルド）や孫を待たずにブロックを確定することができ、Highwayとは異なりタイムアウトを待たずにそれを行う

例え、ネットワークが1分間に1ブロックしか生成しないように設定されていたとしても、ネットワーク接続が許す限りすべてのブロックは数秒以内にファイナライズされる

  • Zugの技術的な説明はHighwayのものよりも柔軟であり、選択肢として関連する正しい実装のファミリーを提供する

Highwayとの比較

Highwayとは異なり、Zugは通信履歴DAGを使用しておらず、Highwayは引用のために大きなメッセージを送信するため更に遅いです。ZugはHighwayのように引用単位の概念を持たず、署名されたメッセージの交換に依存します。一方、Highwayはブロック報酬をより細かく設定できます。

Zugでは、ブロックが提案されたラウンドもしくはこのラウンドを祖先とする後のラウンドにてネットワーク全体のウェイトの3分の2を占めるノードがtrueに投票後、最終決定（finality）となります。Highwayの最終性を検出する基準は、Summitと呼ばれるメッセージのパターンが存在していることです。Summitは多項式時間で検出される一方で調整可能なフォールトトレランスの利点を保持します。最終性を検出する両方の方法は、達成するのがより難しく検出するための計算コストがより高かった以前のCBC Casperの最終性基準よりも改善されています。

HighwayとZugは、フォールトトレランスの閾値に関して柔軟性を提供します。Highwayでは、異なるクライアントが様々な閾値でプロトコルに従うことができ、それぞれがセキュリティとレイテンシのバランスをとっています。しかし、十分な数のバリデーターがオンラインであれば、Zugはどのような閾値においてもHighwayより低いレイテンシを示します。これは、Zugがラウンド長にあらかじめ定義された厳密な値を持たず、ネットワークが実際の遅延に適応できるように設計されているためです。遅延が発生した場合、ブロック時間は変化する可能性があります。そうでなければ、ブロックは確定するとすぐに現れるはずです。ハイウェイには最小ラウンド長が定められており、ラウンド長はその最小ラウンド長の2乗でなければなりません。Zugには最小ラウンド長が定義されているが、十分なメッセージが交換され次第ラウンドはいつでも終了することができます。そのため、Zugの場合、実際の時間が最小値の2乗の間に収まっていればそれを待つ必要はない。

HighwayはZugよりもはるかに複雑なプロトコルです。実装には2倍以上のコード行数を要し、Highwayの正しさの証明はZugよりも検証が難しいことが判明しています。ZugはサードパーティがCasperノードで動作する互換性のあるノードソフトウェアを作ることを容易にしてくれます。

Zugコンセンサスとより小さなメッセージを使うことで、ネットワークはより多くのバリデーターに拡張することができます。

ブロック報酬

ハイウェイでDAGを使うことで、バリデータの行動に関するきめ細かな情報を一時的にプロトコルのステートで利用でき、コンセンサスプロトコルへの完全な参加を促すようにブロック報酬を調整できるようになっています。しかし、これは各eraの終わりには適用されません。そのeraの最終ブロックが提案された後に送信されたメッセージは、そのブロックを確定するために必要であるにも関わらず考慮されません。そして、このきめ細かさには代償が伴う：Highwayのメッセージは比較的大きいため。

現在のシステムは、間違いなく最も重要な成果である最終署名に報酬はありません。署名とは、実行されたブロックが正しいことをバリデータによって署名されたユーザーの目に見える形で証明するものです。

Zugでは、メッセージははるかに小さいので、メッセージを送信するインセンティブはより小さい必要があります。

Casper 2.0.0では、最終署名に対する報酬としてシニョリッジの設定可能な割合を分配し、残りは各ブロックに対する単純な報酬としてどちらもバリデータの賭け金（ステーク）に比例して分配します。

この新しい報酬システムは、よりシンプルで公平、予測可能で透明性が高いです。すべてのブロックに等しい重みが与えられるが（とあるeraの最後も含む）、すべてのコンセンサスメッセージは考慮されません。

Read the Paper

ここでは、我々の論文 From Weakly-terminating Binary Agreement and Reliable Broadcast to Atomic Broadcastのアイデアを実装したZugについて述べています。しかし、この論文には、タイトルにある2つのサブプロトコルによってパラメータ化された、より一般的なアルゴリズム： Reliable BroadcastとWeakly-terminating Binary Agreement が含まれています。このアルゴリズムをCasperブロックチェーン用に特殊化したものでは、エコーメッセージは信頼性ブロードキャストの実装で使用され投票メッセージは弱終端バイナリ合意の実装で使用されます。