ブロックチェーン設定でのリーダー選挙は、ブロックチェーンに追加される次のブロックを決定する参加者を選択することを目的としています。 通常、バリデーターのセットからスロットごとに XNUMX つのバリデーターが選択され、そのスロットで新しいブロックを使用してチェーンを拡張する権利を取得します。 (バリデーターは正確な時刻を保持し、現在のスロット番号に同意していると想定しています。) この記事では、次の戦略について説明します。 無作為化されたリーダー選挙 コンセンサスプロトコルで。 (一般的なランダム性の詳細については、以前の記事を参照してください。 パブリック ランダムネスとランダムネス ビーコンここで、 公的に検証可能で予測不可能なランダム性を生成するためのスタンドアロン プロトコルを調査しました。) 

リーダー選挙が重要な理由

正直で積極的なリーダーを選出することは、チェーンの健全な成長にとって不可欠です。 悪意のあるバリデーターは、リーダーの選出プロセスをバイアスして、より頻繁にリーダーになることができないようにする必要があります。 そうしないと、ブロックの生成が、トランザクションを検閲したり、ブロックチェーンを完全に停止したりできる当事者の手に渡る可能性があります。 最長チェーン スタイルのコンセンサス プロトコルでは、リーダーが無効なブロックを生成する (またはブロックをまったく生成しない) と、チェーンが一時的に分岐する可能性があります。 BFT スタイルのコンセンサス プロトコルでは、悪いリーダーがビュー変更サブプロトコルをトリガーし、通信オーバーヘッドが発生します。 

委員会選挙の代替案

委員会の選挙は関連する問題であり、その目標は一定サイズのバリデーターの均一にランダムなサブセットを選択することです k. コンセンサスの実行を高速化するためにバリデータセットのサイズを縮小するためにブロックチェーン設定でサブコミッティが必要になることが多いため、この機能はそれ自体で役立ちます (多くの例の中で、 アルゴランドのソーティング & イーサリアムの委員会の選択）。 しかし、委員会の選挙はリーダーの選挙にも役立ち、選出されたリーダーが現れなかった場合に、バリデーターがリーダー選挙プロトコルの再実行を回避できるようにします。 リーダーの代わりに委員会が決ま​​った順序で選出された場合、最初の委員が不在の場合、XNUMX 番目の委員がリーダーになることができます。 

優れた選挙プロトコルの特性

リーダー選挙プロトコルでは、リーダーは予測不能であるべきです。 攻撃者が次のリーダーが誰であるかを知ると、サービス拒否 (DoS) 攻撃を開始して、ブロックの公開を阻止する可能性があります。 その後、攻撃者は次のリーダーなどを倒し、ブロックチェーンを停止させる可能性があります。 バリデータ自体がリードするタイミングを学習しないようにするために、予測不可能性も強化される可能性があります。これは、贈収賄防止にとって重要な場合があります。

リーダー選出プロセスには、次の XNUMX つのプロパティが必要です。

• 公正さ: 各正直なバリデーターの確率は 1/N のセットから選ばれる N バリデーター (の緩和された概念 ゲーム理論の公平性により、 ラウンド数の下限は一定ではありませんが、悪意のある過半数が存在する場合でもリーダーの選出を構築します)。
• 予測不可能性: 敵対者は、しばらくするまで次のリーダーを学習しません。 T リーダーが次のブロックを発表する前に。
• 独自性: 各スロットで XNUMX 人のリーダーが選択されます。

秘密のリーダー選挙

秘密のリーダー選挙は予測不可能な選挙です T = 0. このプロセスでは、リーダーはブロックを発行するまで誰にも知られません。 これにより、DoS 攻撃の可能性が完全になくなります。リーダーが自分自身を明らかにする前に、攻撃者は誰を攻撃するかわからないため、最善の戦略を無作為に推測することになります。 そして、リーダーがブロックを発行した後、リーダーはプロトコルに対する責任をすでに果たしているため、攻撃するには遅すぎます。 

ただし、「リーダーがブロックを公開した後」という概念は、実際には単純化されています。現実の世界では即時のブロードキャストがないためです。 強力なネットワーク ポジションを持つ攻撃者は、リーダーが最初にブロックをブロードキャストしていることに気づき、すぐにリーダーを破損させ、別のブロックを作成し、元のブロードキャストをフロントランできる可能性があります。 

これは非常に強力な攻撃者モデルですが、それに対する防御策が提案されています。 アルゴランドが提案した 消去モデル、リーダーは実際にそのスロットでブロックに署名するために必要なキーを消去できます そのため、リーダーが公的な行動を起こすまでに攻撃するには遅すぎます。 Thaddeus Dryja、Quanquan C. Liu、および Neha Narula の MIT メディア ラボの XNUMX 人の研究者は、 提案された リーダーがブロードキャストの前にそのブロックで VDF を計算し、適応攻撃者が目的のスロットに受け入れられるように間に合うように代替の有効なブロックを構築できないようにします。

その他の選挙方法 

最も単純なリーダー選出プロセスは、 ラウンドロビン、リーダーは決定論的な順序で選出されます。 このアプローチは予測可能であり、そのため DoS 攻撃を受けやすいにもかかわらず、バリデーターが優れた DoS 保護を備えている許可システムに適しています。

リーダーは、外部の出力を使用して選出することもできます ランダム性ビーコン、利用可能で、安全であると信頼されている場合。 残念ながら、コンセンサス参加者が分散ランダムネス ビーコン (DRB) プロトコルを自分で実行するのは難しいです。DRB プロトコルは通常、信頼できるブロードキャストまたはコンセンサスの概念を前提としており、そのために再びリーダーの選出が必要になり、循環依存が導入されるからです。

電流プローブ イーサリアムのリーダー選挙 良いケーススタディです。 新しい各リーダーは、Verifiable Randomness Function (VRF) 出力 (エポック番号の BLS 署名) を計算し、値をミックスに XOR します。 エポック終了時のミックスの値 i エポック期間中のリーダーと分科会を定義する i+2。 リーダーとそのスケジュールは、6.4 エポック (現在 ~XNUMX 分) 先に予測可能です。 プロトコルは、最後のリーダーがミックスへの貢献を公開または保留することを選択し、次の選挙の結果に XNUMX ビット影響を与える可能性があるため、公平性攻撃を受けやすくなっています。 最後の場合  k 指導者は結託し、彼らは紹介するかもしれません k  悪意のあるユーザーが選択される可能性が高くなります。 イーサリアム財団は、以下で説明するリーダー選挙のためのより高度な技術に積極的に取り組んでいます。

VRF ベースのリーダー選挙

によって開拓された別のアプローチ アルゴリズムであり、 VRF ベースのリーダー選挙これには、各バリデータが非公開で VRF 出力を計算し、出力がしきい値を下回っているかどうかを確認する必要があります。 この手順では、ほとんどのバリデーターが既に除外されています。これは、しきい値を下回る可能性が低いようにしきい値が選択されているためです。 残りのいくつかのバリデータが VRF 出力を明らかにし、VRF 値が最も低いバリデータが選択されます。 このアプローチは、完全な予測不可能性 (または機密性) を実現しますが、一意性を保証するものではありません。 一部のバリデーターは潜在的なリーダーのすべてからメッセージを受信しない可能性があり、間違ったリーダーが選挙に勝ったと想定する可能性があり、これらのバリデーターがメインチェーンから分岐する原因となります。 

VRF 評価はランダムネス ビーコンの出力で定期的にシードされ、バリデーター自体がどのスロットをリードするかを予測しにくくします。 このプロパティは、バリデーターがリーダーになるときにスロットを学習し、バリデーターがブロックを発表しようとしているときに攻撃を開始するときに、バリデーターを黙って侵害する攻撃者を防ぎます。 このアプローチは贈収賄攻撃の防止にも役立ちます。この攻撃では、バリデーターが特定のスロットのリーダーになることを外部関係者に証明し、リーダーとしてのタスクを完了することと引き換えに賄賂を受け取ります (トランザクションのブロックなど)。

選出されたリーダーの数が確率変数であるこのようなアプローチは、 確率的リーダー選出 (PLE)。 PLE により、特定のスロットにリーダーが選出されない場合があります。 これは、スロットが最終的にスキップされ、コンセンサス プロトコルの効率が低下するという点で、悪意のあるリーダーまたはオフラインのリーダーを選出することと同じです。

しかし、PLE に関する最大の注意点は、複数のリーダーが選出される可能性があり、ある種のタイブレーク手順が必要になることです。 同点はコンセンサスにリスクをもたらします。なぜなら、勝利した入力を持つバリデーターがそれをネットワークの半分だけに報告し、選ばれたリーダーに不一致を引き起こす可能性があるからです。 さらに、関係を解決するためのプロセスには、余分な時間とコミュニケーションが必要になり、効率が低下する可能性があります。 Dfinityで詳しく説明します。 最初の投稿 このシリーズの XNUMX つは、VRF ベースのランダムネス ビーコンを使用して単一のリーダーを選出します。 ただし、そうするために予測不可能性が犠牲になります。 理想的には、リーダーを選ぶプロセスは完全に同点を避けるべきであり、それでも予測不可能であるべきであり、それがこの研究分野の聖杯である単一の秘密のリーダー選挙に私たちを導きます.

シングルシークレットリーダー選挙 

の目標 シングルシークレットリーダー選挙 (SSLE) は、公平性と予測不可能性を維持しながら、一連のバリデーターから一意のリーダーを選択することです。 Protocol Labs は、この概念を 研究問題、およびスタンフォード大学のコンピューター科学者であり a16z 暗号研究アドバイザーである Dan Boneh と、Saba Eskandarian、Lucjan Hanzlik、および Nicola Greco が後に提供しました。 SSLE の正式な定義. この独自性の特性により、タイブレーク手順から生じるコンセンサス リスクと効率コストが回避されます。 具体的には、Protocol Labs の Sarah Azouvi とトリノ工科大学の Danielle Cappelletti は、 表示する 最長チェーン プロトコルで PLE と比較して SSLE を使用すると、ブロックを大幅に高速化できます (敵対者がステークの 25 分の XNUMX を制御すると、XNUMX% 高速になります)。 したがって、実用的な SSLE プロトコルの開発は重要な問題です。

最も一般的なアプローチでは、これを呼び出します シャッフルベース (元の SSLE 論文と イーサリアム SSLE 提案)、各バリデータは 使節 ランダムに見えますが、自分のものであることを証明できます。 その後、ナンスはリストにコンパイルされます。 リストはシャッフルされ、ノンスがそれらを送信したバリデータからリンク解除されます。 つまり、シャッフルされたリストを考えると、どのバリデーターがどのノンスを送信したかを敵対者が知ることはできません。 リスト インデックスは、パブリックに従って選択されます。 ランダム性ビーコン、そしてリーダーは、シャッフルされたリストのそのインデックスのナンスがそれらに属していることを証明することによって自分自身を明らかにします。 

XNUMX つのインデックスのみが選択されるため、シャッフル ベースのプロトコルは常に ユニーク 盟主。 ランダム ビーコンは一様にランダムな値を出力するように構築されているため、プロトコルも フェア: 各バリデーターが選出される可能性は均等です。 さらに、シャッフルが適切に (つまり、一様にランダムに) 行われ、ノンスがバリデーターの ID にリンクできなくなった場合、このプロトコルも達成されます。 予測不能.

ランダムなビーコンに基づいてシャッフルされていないリストからインデックスを選択するだけで一意性と公平性が得られるため、シャッフルが必要です。予測不可能性を達成するのは難しいためです。リーダーを識別できます。 

これらの次の XNUMX つのアプローチは、さまざまな方法でリストをシャッフルします。 より単純なのは、 イーサリアム SSLE 提案、ここで、 n バリデーターは、Tor を介してノンスを送信し、バリデーターの ID をノンスからリンク解除します。 すべてのバリデーターが登録されると、パブリック ランダムネス ビーコンを使用してリストがシャッフルされ、シャッフルされたリストの順序でバリデーターがリーダーになります。 このスキームは実用的ですが、選挙は毎年 XNUMX 回だけ実施する必要があります。 n スロット – この Tor への依存は望ましくない場合があります (外部プロトコルのセキュリティに依存する場合と同様)。 さらに、完全に予測できないわけではありません。 n-1 リーダーが自分自身を明らかにし、最終的に nth リーダーが知られています。

Tor を使用する代わりに、元の SSLE 論文では、ノンスをリストに追加し、リストをシャッフルし、 再ランダム化 ナンス。 この再ランダム化は、各ノンスが新しいリンク不可能な文字列にマップされることを意味し、それが属するバリデーターは再ランダム化されたナンスの所有権を引き続き証明できます。 再ランダム化により、少なくとも XNUMX 人のシャッフラーが正直であると仮定して、シャッフル後に特定のノンスがどの位置に到達したかを敵が知ることができないようになります。

元の SSLE ペーパーからのこの順次シャッフル アプローチは、Tor への依存を回避し、SSLE の正式な特性を実現しますが、費用がかかります。彼らが正直に行ったという証拠を提供することで、バリデーターごとの通信量が線形になります。 不変のバリデーターのセットでは、ナンスの証拠を明らかにするとリーダーが再登録するため、これは選挙ごとに XNUMX 回実行 (償却) する必要があります。 この論文は、調整可能な効率と予測可能性のトレードオフを示しています。代わりに、少量の予測可能性を許可する場合は、リストのより小さなサブセットのみをシャッフルしてコストを削減できます。 効率とセキュリティの適切なバランスを達成することは困難であり、その結果、SSLE プロトコルは実際にはまだ広く使用されていません。 

便利なことに、この順次シャッフル アプローチは、ランダム ビーコンを使用してリストから k 個の異なるインデックスを委員会メンバーとして選択することにより、委員会の選挙問題を解決するためにも使用できます。 確率的な VRF ベースのプロトコルを実行しているため、VRF ベースのアプローチでは問題が自明に解決されないため、これは素晴らしい成果です。 k 時間は、ランダム性に応じてさまざまな委員会のサイズを選択する場合があります。 

SSLE へのその他のアプローチ

別のシャッフルベースのアプローチは DDH から適応的にセキュアな SSLE. この構造は少し複雑ですが、より強力なセキュリティの概念を実現し、攻撃から保護します。 適応敵 アルゴランドの消去モデルで. この敵対者は、プロトコルの開始前ではなく、プロトコル中に破損するバリデーターを選択できるという点で適応的です。 

SSLE のさらなる課題は、一様にランダムではなく、ステークに比例した確率で各バリデーターを選出することです。 シャッフルベースのプロトコルは、各バリデーターが複数のノンスを登録できるようにすることで、単純にこれを実現できます。保持するステークの単位ごとに XNUMX つのナンスです。 ただし、シャッフルのコストは、賭け金の数に比例して増加します S、現実的な賭け金の分配でも非常に高価になります。 エレガント MPC ベースの SSLE アプローチはログのみで複雑さが増します S、また、信頼できるセットアップやランダムネス ビーコンの必要性を回避します。 ただし、シャッフルベースのアプローチと比較して、選出されたリーダーごとにより多くの通信ラウンド (参加者数の対数) が必要です。

***

この便利な表に分析をまとめました。

* ラウンドロビン ビーコンは完全に予測可能ですが、残りのビーコンでは ✗ は、その概念が一定の限定された程度まで達成されることを意味します。 理想ランダムネス ビーコンは予測不可能ですが、敵対者は選出されたリーダーと同時に出力を学習するため、選出されたリーダーはブロックを発表する前に攻撃される可能性があります。 Etherum のビーコンは最大 6 分まで予測不可能であり、公平性を損なうためにわずかに偏っている可能性があります。 アルゴランドは、わずかな確率で複数のリーダーを選出します。

SSLE は有望な方向性であり、公平性、予測不能性、独自性を実現します。 その採用が直面している XNUMX つの顕著な課題は、効率性と、不均一なステーク配分に対応する能力です。 さらに、強調するシャッフル ベースの SSLE アプローチは、偏りのないランダム ビーコンの存在を前提としていますが、これを実際に達成するのは簡単ではありません。 SSLE は最近正式に定義されたばかりであるため、近い将来、SSLE の課題に対処する改善されたプロトコルが見られる可能性があります。 

***

ミランダ・クライスト 彼女は、コロンビア大学のコンピューター サイエンスの博士課程の学生であり、理論グループのメンバーであり、プレジデンシャル フェローでもあります。 彼女は a16z crypto の研究インターンでもあります。

ジョセフ・ボノー a16z crypto のリサーチ パートナーです。 彼の研究は、応用暗号とブロックチェーン セキュリティに焦点を当てています。 メルボルン大学、ニューヨーク大学、スタンフォード大学、プリンストン大学で暗号通貨コースを教え、ケンブリッジ大学でコンピューター サイエンスの博士号を取得し、スタンフォード大学で理学士/修士号を取得しています。

ヴァレリアニコレンコ a16z crypto のリサーチ パートナーです。 彼女の研究は、暗号化とブロックチェーン セキュリティに焦点を当てています。 彼女はまた、PoS コンセンサス プロトコルでの長距離攻撃、署名スキーム、ポスト量子セキュリティ、マルチパーティ計算などのトピックにも取り組んできました。 彼女はスタンフォード大学で Dan Boneh 教授の指導の下、暗号学の博士号を取得しており、コア研究チームの一員として Diem ブロックチェーンに取り組みました。

***

エディタ： ティム·サリバン

***

ここに示されている見解は、引用された個々のAH Capital Management、LLC（「a16z」）の担当者の見解であり、a16zまたはその関連会社の見解ではありません。 ここに含まれる特定の情報は、a16zが管理するファンドのポートフォリオ企業を含むサードパーティの情報源から入手したものです。 a16zは、信頼できると思われる情報源から取得したものですが、そのような情報を独自に検証しておらず、情報の永続的な正確性や特定の状況に対するその適切性について表明していません。 さらに、このコンテンツにはサードパーティの広告が含まれる場合があります。 a16zはそのような広告をレビューしておらず、そこに含まれる広告コンテンツを推奨していません。

このコンテンツは情報提供のみを目的として提供されており、法律、ビジネス、投資、または税務に関するアドバイスとして信頼されるべきではありません。 これらの問題については、ご自身のアドバイザーにご相談ください。 証券またはデジタル資産への言及は、説明のみを目的としたものであり、投資の推奨または投資顧問サービスの提供を構成するものではありません。 さらに、このコンテンツは、投資家または将来の投資家による使用を目的としたものではなく、a16zが管理するファンドへの投資を決定する際にいかなる状況においても信頼されない場合があります。 （a16zファンドへの投資の申し出は、私募覚書、サブスクリプション契約、およびそのようなファンドの他の関連文書によってのみ行われ、その全体を読む必要があります。）言及、参照、または記載されているのは、a16zが管理する車両へのすべての投資を代表するものではなく、投資が有益である、または将来行われる他の投資が同様の特性または結果をもたらすという保証はありません。 アンドリーセンホロウィッツが管理するファンドが行った投資のリスト（発行者がa16zに公開を許可していない投資、および公開されているデジタル資産への未発表の投資を除く）は、https：//a16z.com/investmentsで入手できます。 /。

記載されているチャートおよびグラフは、情報提供のみを目的としており、投資を決定する際に信頼することはできません。 過去の実績は将来の結果を示すものではありません。 内容は、示された日付の時点でのみ話されています。 これらの資料に記載されている予測、推定、予測、目標、見通し、および/または意見は、予告なしに変更される場合があり、他の人が表明した意見と異なる場合があります。 その他の重要な情報については、https：//a16z.com/disclosuresを参照してください。