公開ランダム性 多くの現実世界のセキュリティ プロトコルの不可欠なコンポーネントです。 ギャンブルやマルチプレイヤー ゲームなどの一部のアプリケーションでは、ランダム性によって楽しみが増します。 他のアプリケーションでは、ランダム性は、グリーン カードから、巡回裁判所の判事の事件への割り当て、スポーツ トーナメントでのシードに至るまで、分割できないリソースを公平に割り当てる方法を提供します。 割り振りにも使われる 負 税務調査や空港での二次セキュリティ審査などのリソース。
従来、これらのプロトコルのランダム性を生成するために、信頼できる機関に依存してきましたが、web3 の世界では、さらに改善する必要があります。 この投稿では、公的に検証可能なランダム性を構築するためのアプローチを探ります。 分散ランダムビーコン 次に、いくつかのオンチェーン アプリケーションについて説明します。 (近日公開予定のパート II では、特にリーダーの選出に焦点を当て、代わりのリーダー選出アプローチの評価を提供します。)
希望する特性
乱数の生成は、非常に微妙な作業です。 たとえば、多くの暗号鍵が漏えいしています。 欠陥のある乱数発生器に依存していた (そのための Cloudflare の壁 溶岩ランプ 創造的な緩和策として機能したでしょう)。 それだけです プライベートランダム性ただし、一方の当事者のみがそれを生成して使用する必要があります。
対照的に、パブリック ランダムネスはマルチパーティ プロセスであり、これがかなりの困難をもたらします。 パブリック ランダム性を生成するための適切なプロトコルには、次のセキュリティ プロパティがあります。
- 公平な: 攻撃者または攻撃者の連合は、出力にバイアスをかけることができません。
- 高信頼性: 攻撃者は、プロトコルが出力を生成するのを防ぐことはできません。
- 検証可能: 誰でも簡単にプロトコル出力を確認でき、他の人と同じ出力が表示されるはずです。
- 予測できない: プロトコルが時間に出力を生成する場合 T1、しばらく前に出力について誰も予測できないはずです T0<T1、理想的には T0 にとても近い T1.
予測不可能なプロトコルはバイアスがかからないようにする必要があるため、不偏性は予測不可能性よりも弱い特性です。 コンピューター科学者は偏りがないと言うだろう 軽減 バイアスをかけることができれば、予測できるからです。 しかし、それらは異なる仮定に依存している可能性があるため、個別に推論したい場合があります。
これらのプロパティに加えて、プロトコルは効率的に実行し、多数のランダム ビットを生成する必要があります。 (実際には、多くの場合、アプリケーションは 128 の乱数ビットを生成し、それらを使用して疑似乱数ジェネレーター [PNRG] をシードし、必要に応じてより多くのビットを出力するだけで十分です。ただし、出力の個々のビットをそのような目的で使用できるようにするためには、予測不可能性を保持する必要があります。宝くじやリソース割り当てなどのアプリケーション。) プロトコルは、理想的には、通信および計算コストの点でも効率的であるべきです。
異なるプロトコルは、異なる条件下でこれらの特性を達成する可能性があります。 たとえば、一部のプロトコルは、 f1 悪意のあるノードとの連合によって予測不可能 f2<f1 悪意のあるノード。 バイアスの程度もさまざまです。 たとえば、一部のプロトコルでは、参加者は出力を「XNUMX ビット」だけバイアスできる場合があります。つまり、XNUMX つの可能な出力のいずれかを選択できます。 他の攻撃では、出力を完全に修正できる可能性があります。 ただし、通常、偏り (または予測可能性) をまったく許容したくありません。
暗号の理想: R無秩序ビーコン
暗号学者は、多くの場合、問題に対する理想的な解決策について考えるところから始めます。 公開ランダム性の場合、 ランダム性ビーコン 必要なセキュリティ要件をすべて満たすランダムな出力を定期的に生成する理想的なサービスです。
ランダム オラクルや一般的なグループ モデルなどの他の暗号化抽象化と同様に、このような理想化されたランダムネス ビーコンは、現実の世界には存在しません。 しかし、これは努力するのに役立つ目標であり、公開のランダム性に依存するプロトコルについて推論するのに役立つモデルです。
理想的なランダム性ビーコンのいくつかの近似を考えることができます。
- 集中型ビーコン: 適切なランダム性を生成する最も簡単な方法は、次のようなサービスを提供する中央集権型のサード パーティを使用することです。 NISTランダムネスビーコン or random.org、大気ノイズからランダム性を生成し、ギャンブルでの使用が認定されています。 このような第三者への依存は、分散化の哲学を完全に損なうものです。 実際、上記の例では、関連する組織がランダム性を正しく生成していることを信頼する必要がありますが、暗号による証拠はありません。
- 物理的ランダム性の表示: 従来の宝くじの多くは公開ディスプレイに依存しており、たとえば、誰かがさまざまな番号のピンポン球の容器に手を伸ばすことが含まれる場合があります。 残念ながら、これらは多くの場合簡単に操作できます。 例えば、 特定のボールは冷凍庫に入れることができます & セレクターに冷たいものを選ぶように指示することができます.
- ナチュラルビーコン: 一般的なアイデアは、天候や宇宙背景放射などのランダムな自然現象をビーコンとして使用することです。 残念ながら、提案されたすべての情報源が強力なコンセンサスを提供しているわけではありません。 オブザーバーが異なればわずかに異なる値が表示されるため、信頼できる関係者を再紹介して公式の測定を行う必要があり、集中型ビーコンのすべての欠点があります.
- 半集中ビーコン: より良いアプローチは、からランダム性を取得することです ビットコイン ブロック ヘッダー 直接またはから 株式の終値、これは公的に検証するのがより簡単で、いずれかの当事者が完全に制御するのがより困難です. それでも微妙な攻撃はまだ両方に存在します プルーフ・オブ・ワーク ブロックチェーンのランダム性 & 株価のランダム性. たとえば、ブロックチェーン ヘッダーを使用すると、マイナーは、ヘッダーが好ましくないビーコン値を生成するブロックを保留することを選択できます。 または、好みのビーコン出力に基づいて XNUMX つの衝突ブロックが見つかった場合に、関係を断ち切ることを選択できます。
分散ランダムネス ビーコン (DRB)
集中型ビーコンの問題に対する自然なアプローチは、パブリック ランダム性を生成するための分散型暗号プロトコルを設計することです。 この問題は、分散型コンセンサス プロトコルの設計にやや似ていますが、難しいだけです。 すべての参加者が出力 (ランダム性) に同意する必要があるだけでなく、プロトコルの悪意のある参加者が出力を偏らせたり予測したりすることは不可能であるべきです。
ランダムネス ビーコンをシミュレートするように設計されたプロトコルは、分散ランダムネス ビーコン (DRB) と呼ばれます。 (他の名前には「分散型コイン投げ」が含まれます。) この問題は何十年にもわたって研究されてきました。 1980年代に証明された有名な不可能性の結果、しかし、ブロックチェーン時代に再び関心が高まっています。 DRB は、オンチェーンのランダム性を提供するために使用できます。これは、公正、安全、透明なオンチェーン アプリケーションの重要な要素となります。
古典的なアプローチ: コミット公開プロトコル
楽観的なケースでは、DRB には非常に単純な 1 ラウンドのプロトコルで十分です。 ラウンド XNUMX では、各参加者 i ランダムな値を生成します ri 暗号化コミットメントを発行する ci=専念(ri)。 このアプリケーションでは、コミットメントは単純に SHA-256 のようなハッシュ関数にすることができます。 各参加者のコミットメントが公開された後、彼らは自分の選択にロックインされます ri、しかしコミットメントは、他の参加者の貢献に関する情報を明らかにしません。 ラウンド 2 では、すべての参加者が公開することで「コミットメントを開始」します。 ri. 次に、すべてのランダム値が、たとえばそれらを XOR するか、(できれば) 連結をハッシュすることによって結合されます。
このプロトコルは単純で、参加者の XNUMX 人でも自分のビーコンを選択する限り、ランダムなビーコン出力を生成します。 ri 無作為に。 残念ながら、これには古典的な欠陥があります。XNUMX 人を除くすべての参加者がランダム値を明らかにすると、最後の参加者が推定ビーコン出力を計算できます。 気に入らない場合は、値の公開を拒否して、プロトコルを中止することができます。 不完全な参加者の貢献を無視しても問題は解決しません。これは、攻撃者が XNUMX つのビーコン出力 (XNUMX つは貢献を考慮して計算され、もう XNUMX つは貢献を含まない) のいずれかを選択できるためです。
ブロックチェーンは、この問題に対する自然な解決策を提供します。各参加者は、ランダムな貢献を明らかにしない場合、押収される一部の資金をエスクローに入れるよう要求される可能性があります。 これはまさにクラシックが採用したアプローチでした ランダオ イーサリアムのビーコン。 このアプローチの欠点は、出力に偏りが残る可能性があることです。これは、エスクローの金額がビーコンの結果にかかる金額よりも少ない場合、攻撃者にとって経済的に価値がある可能性があります。 バイアス攻撃に対するセキュリティを強化するには、より多くのコインをエスクローに入れる必要があります。
コミット・公開・回復プロトコル
すべての当事者にランダムな貢献を明らかにするように強制しようとする代わりに、一部のプロトコルには回復メカニズムが含まれているため、少数の参加者が脱落した場合でも、残りの参加者はプロトコルを完了することができます。 プロトコルがどちらの場合でも同じ結果を生成することが重要です。これにより、関係者がドロップアウトするかどうかを選択して結果にバイアスをかけることができなくなります。
これを達成するための XNUMX つのアプローチは、各参加者にその秘密の共有を他の参加者に提供させ、大多数がそれを再構築できるようにすることです。たとえば、 シャミールの秘密共有. ただし、重要なプロパティは、コミットされたシークレットが適切に共有されていることを他のユーザーが確認できることです。これには、公的に検証可能なシークレット共有 (PVSS) と呼ばれるより強力なプリミティブを使用する必要があります。
他にもいくつかの回復メカニズムが可能ですが、すべて同じ制限があります。 ある場合 N 参加者、および最大のグループがあれば回復力が必要です f ノードが脱落した場合、 Nf 参加者は最終結果を計算できます。 しかし、それはまた、悪意のある連合を意味します Nf 参加者は、回復メカニズムを個人的にシミュレートすることにより、事前に結果を予測できます。 これは、プロトコルの最初のラウンド中にも発生する可能性があり、その間、そのような連合は独自のランダム性の選択を変更し、結果にバイアスをかける可能性があります.
別の言い方をすれば、これは Nf ノードには、少なくとも XNUMX つの正直なノードが含まれている必要があります。 単純な代数により、 Nf > fので、 f < N/2、およびこれらのプロトコルは本質的に正直な過半数を必要とします。 これは、commit-reveal の元のセキュリティ モデルとの大きな違いです。 f<N (少なくとも XNUMX 人の正直な参加者)。
これらのプロトコルでは、多くの場合、プロトコルの実行ごとにすべてのノード間で追加の PVSS 情報を共有するために、かなりの通信コストが必要になります。 研究コミュニティは、過去数年間、この問題に対してかなりの作業を行ってきました。 ランドシェア, スクレープ, セカンドランド, HERBまたは アホウドリ、しかし、実際の展開を見た人は誰もいないようです.
検証可能なランダム関数ベースのプロトコル
のグループであることを認識する Nf 参加者は上記のプロトコルでランダム ビーコン値を計算でき、やや単純なアプローチにつながります。 N 関係者にそれを使用して評価してもらいます。 検証可能なランダム関数 (VRF)。 秘密鍵は、 t-外-N しきい値スキーム、したがって、 t 参加者は VRF を計算できます (ただし、小規模な連合は計算できません)。 ために t=Nf、これはに同じ回復力を提供します f 上記の commit-revere-recover プロトコルなどの悪意のあるノード。
明確さ このアプローチを開拓した しきい値 BLS 署名 (VRF として機能) を使用するコンセンサス プロトコルの一部として。 スタンドアロン ドランド 乱数ビーコンは基本的に同じアプローチを使用し、各ラウンドで参加者のしきい値 BLS 署名カウンターを使用します。 の リーグ・オブ・エントロピー は、30 の参加ノード (16 年 2022 月現在) を使用して XNUMX 秒ごとにランダム性を生成する drand のオープン ソース インスタンスであり、企業と大学の研究グループが混在して運営されています。
これらのアプローチの欠点は、しきい値キーの初期化が比較的複雑であり、ノードが参加または離脱するときにキーを再構成することです。 ただし、一般的なケースでは、プロトコルは非常に効率的です。
前述のように、単純にカウンター値に署名するだけでは、ラウンドごとに新たなランダム性が追加されるわけではないため、十分な数の参加者の鍵が危険にさらされた場合、プロトコルは将来のすべてのラウンドで予測可能になります。
チェーンリンクVRF 組み合わせ このアプローチ( NSEC5 VRF) を、ランダム性を要求する当事者によって指定されたランダム性の外部ソース (通常、実際には最近のブロックチェーン ヘッダー) と共に使用します。 このデータは、VRF を介して供給されます。VRF は、一方の当事者によって実行されるか、グループにしきい値設定されます。
エテリアムズ ビーコンチェーン 現在、BLS ベースの VRF を使用しています。各ラウンドの提案者は、VRF 値をミックスに追加します。 これにより、commit-reveal パラダイムと比較して通信のラウンドが節約されます (長期の BLS 公開鍵が XNUMX 回登録されると仮定します)。ただし、この設計は、出力を保留することによってビーコンの出力にバイアスをかける可能性など、commit-reveal アプローチのいくつかの注意事項を継承しています。 .
検証可能な遅延機能ベースのプロトコル
最後に、有望な新しい方向性は、時間ベースの暗号化、特に検証可能な遅延関数 (VDF)。 このアプローチは、優れた通信効率と堅牢性を提供し、回復力を提供することを約束します N-1 悪意のあるノード。
元の commit-reveal プロトコルに戻ると、従来のコミットメントを次のプロトコルに置き換えることができます。 時限コミットメント 参加者がランダムな貢献を明らかにすることを拒否するという問題を排除します。 時間指定されたコミットメントは、元のコミッター、または遅い関数 (本質的には VDF) を計算したい人なら誰でも効率的に開くことができます。 したがって、参加者が commit-revele プロトコルから脱落した場合でも、他の参加者がそのコミットメントを開くことができます。 コミットメントを開くための最小時間は、プロトコルの最初のラウンド (コミット フェーズ) では実行できないほど十分に長いことが不可欠です。そうしないと、悪意のある参加者が他の参加者のコミットメントをすばやく開いて、自分の貢献を変更し、結果に偏りを与える可能性があります。 .
最新の VDF では、さらに洗練されたワンラウンド プロトコルが可能です。コミットメントを完全に削除します。 各参加者は、ランダムな貢献を簡単に公開できます ri、最終的な結果は、VDF を介して実行される各参加者の貢献の組み合わせです。 VDF を計算する際の時間遅延により、最終的な出力に偏りのある方法でコミットメントを選択することはできなくなります。 このアプローチは次のように提案されました。 UNICORN Arjen Lenstra と Benjamin Wesolowski によって 2015 年に発表されました。 VDFの開発.
このアプローチは、いくつかの実用的な展開を見てきました。 チーア これのバージョンをコンセンサス プロトコルの一部として実装し、クラス グループで反復二乗 VDF を使用します。 スタークウェア 実装された 概念実証の VDF ベースのビーコン SNARK ベースの VDF を使用します。 Ethereum も計画しています 使用する このアプローチ、コンセンサスレイヤーでランダム性を生成するためにVDFを計算するための専用ASICを構築します。
***
パブリック ランダム性は多くのプロトコルの重要な要素ですが、高度なセキュリティを提供する標準的な DRB はまだありません。 設計空間は大きく、上記のアプローチの多くのハイブリッドおよび組み合わせが可能です。 たとえば、VRF ベースのプロトコルを VDF ベースのプロトコルと組み合わせて、新しいエントロピーを追加することが可能です。 ランドランナー. イーサリアムのビーコン チェーンは現在 VRF を使用していますが、将来的に VDF を追加して、ブロック保留攻撃によるバイアスの可能性を排除する可能性があります。
正直多数派のプロトコルが受け入れられるかどうかも、未解決の問題です。 リーグ・オブ・エントロピーのように、精査された比較的少数の参加者グループの場合、正直な過半数の仮定が妥当です。 一方、正直な参加者を XNUMX 人だけ必要とするプロトコルには固有の利点があります。参加者が増えると、セキュリティが向上するだけです。 これは、これらのプロトコルが、オープンで許可のない参加で展開される可能性があることを意味します。
パート II では、コンセンサス プロトコルにおけるランダム化されたリーダー選挙の特定のアプリケーションについて説明します。これはわずかに異なる設計目標を持ち、その結果、さらに多くのプロトコルとアプローチが提案されています。
***
ジョセフ・ボノー 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を参照してください。