お互いを信頼していなくても、乱数を生成することは可能ですか? パート1

おい、ハブル！

この記事では、お互いを信頼していない参加者による疑似乱数の生成について説明します。 以下で説明するように、「ほぼ」優れたジェネレーターを実装するのは非常に簡単ですが、非常に優れたジェネレーターを実装するのは困難です。

お互いを信頼していない参加者の間で乱数を生成する必要があるのはなぜでしょうか? アプリケーション分野の 49 つは分散型アプリケーションです。 たとえば、参加者から賭けを受け入れ、51% の確率で金額を XNUMX 倍にするか、XNUMX% の確率で取り消すアプリケーションは、公平に乱数を受け取ることができる場合にのみ機能します。 攻撃者が乱数生成器の結果に影響を与え、アプリケーションで支払いを受け取る可能性をわずかでも高めることができれば、攻撃者は簡単に乱数生成器を破壊してしまいます。

分散乱数生成プロトコルを設計するときは、次の XNUMX つのプロパティを持たせる必要があります。

1. 彼は公平でなければなりません。 言い換えれば、参加者は乱数発生器の結果にいかなる形でも影響を与えるべきではありません。

2. 彼は予測不可能な人物に違いない。 言い換えれば、参加者は、生成される前にどのような数値が生成されるかを予測 (またはそのプロパティのいずれかを推測) できるべきではありません。

3. プロトコルは実行可能である必要があります。つまり、一定の割合の参加者がネットワークから切断したり、意図的にプロトコルを停止しようとしたりするという事実に耐えられる必要があります。

この記事では、RANDAO + VDF と消去コード アプローチの XNUMX つのアプローチについて説明します。 次のパートでは、しきい値シグネチャに基づくアプローチを詳細に検討します。

まず最初に、実行可能で予測不可能ではあるものの、偏った、シンプルで一般的に使用されるアルゴリズムを見てみましょう。

ランダオ

RANDAO は非常にシンプルなので、ランダム性を生成するために非常に一般的に使用されるアプローチです。 すべてのネットワーク参加者は、まずローカルで擬似乱数を選択し、次に各参加者が選択した数値のハッシュを送信します。 次に、参加者は順番に自分が選択した数値を公開し、公開された数値に対して XOR 演算を実行します。この演算の結果がプロトコルの結果になります。

攻撃者が他の参加者の番号を見た後で自分の番号を選択できないように、番号を明らかにする前にハッシュを公開するステップが必要です。 これにより、彼は事実上独力で乱数発生器の出力を決定できるようになります。

プロトコルの過程で、参加者は XNUMX 回共通の決定 (いわゆるコンセンサス) に達する必要があります。選択された数値の公開をいつ開始するか、したがってハッシュの受け入れを停止するか、もう XNUMX つは選択された数値の受け入れとその結果のランダムの計算をいつ停止するかです。番号。 お互いを信頼していない参加者の間でそのような決定を下すこと自体は簡単な作業ではありませんが、これについては今後の記事で改めて説明しますが、この記事ではそのようなコンセンサス アルゴリズムが利用可能であると仮定します。

RANDAO には、上で説明した特性のうちどれがありますか? これは予測不可能であり、基礎となるコンセンサスプロトコルと同じ活力を持っていますが、偏っています。 具体的には、攻撃者はネットワークを観察し、他の参加者が自分の番号を公開した後、XOR を計算し、結果に影響を与えるために自分の番号を公開するかどうかを決定できます。 これにより、攻撃者が乱数発生器の出力を独力で決定することはできなくなりますが、それでも 1 ビットの影響力が与えられます。 また、攻撃者が複数の参加者を制御する場合、攻撃者が制御するビット数は、攻撃者が制御する参加者の数と等しくなります。

参加者に順番に番号を明らかにさせることで、攻撃者の影響を大幅に軽減できます。 そうすれば、攻撃者は最後に開かれた場合にのみ結果に影響を与えることができます。 影響は大幅に減少していますが、アルゴリズムには依然としてバイアスがかかっています。

ランダオ+VDF

RANDAO を偏りのないものにする XNUMX つの方法は、すべての数値が明らかになり XOR が計算された後、その結果が関数の入力に入力されることです。これにより、計算には非常に長い時間がかかりますが、その結果が正しいかどうかをチェックできます。計算が非常に早くなります。

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

この機能は、Verifiable Delay Function (VDF) と呼ばれます。 最終結果の計算に番号開示段階よりも時間がかかる場合、攻撃者は自分の番号を表示または非表示にした場合の影響を予測できなくなり、結果に影響を与える機会を失うことになります。

優れた VDF を開発することは非常に困難です。 最近、いくつかの画期的な進歩がありました。 この и これ これにより、VDF は実際にさらに実用的になり、イーサリアム 2.0 では、長期的には VDF とともに RANDAO を乱数ソースとして使用する予定です。 このアプローチは予測不可能で公平であるという事実とは別に、ネットワーク上に少なくとも XNUMX 人の参加者がいる場合に実行可能であるという追加の利点があります (使用されるコンセンサス プロトコルがこのような少数の参加者を扱う場合に実行可能であると仮定します)。

このアプローチの最大の課題は、非常に高価な専用ハードウェアを使用している参加者であっても、検出フェーズが終了するまでは VDF を計算できないように VDF を設定することです。 理想的には、アルゴリズムには大幅な安全マージン (たとえば 10 倍) さえある必要があります。 以下の図は、RANDAO 確認を明らかにするために割り当てられた時間よりも速く VDF を実行できる特殊な ASIC を備えた攻撃者による攻撃を示しています。 このような参加者は、自分の番号を使用するか使用しないで最終結果を計算し、その計算に基づいてそれを表示するかどうかを選択できます。

前述の VDF ファミリの場合、専用 ASIC のパフォーマンスは従来のハードウェアの 100 倍以上になる可能性があります。 したがって、展開フェーズが 10 秒続く場合、そのような ASIC で計算される VDF に 100 倍の安全マージンを持たせるには 10 秒以上かかる必要があり、したがって、同じ VDF を汎用ハードウェアで計算するには 100x 100 秒 = ～ 3 時間かかる必要があります。

イーサリアム財団は、独自の公開されている無料の ASIC を作成することで、この問題を解決することを計画しています。 これが実現すると、他のすべてのプロトコルでもこの​​テクノロジを利用できるようになりますが、それまでは、独自の ASIC の開発に投資できないプロトコルでは、RANDAO+VDF アプローチはそれほど実行可能ではありません。

VDF に関する多くの記事、ビデオ、その他の情報が以下に収集されています。 このサイト.

消去コードを使用しています

このセクションでは、次を使用する乱数生成プロトコルを見ていきます。 コードの消去。 生存を維持しながら最大 XNUMX/XNUMX の攻撃者を許容し、結果を予測したり影響を与えたりする前に最大 XNUMX/XNUMX の攻撃者が存在することを許可します。

プロトコルの主な考え方は次のとおりです。 話を簡単にするために、参加者がちょうど 100 人だと仮定します。 また、すべての参加者がローカルで秘密鍵を持っており、すべての参加者の公開鍵がすべての参加者に知られていると仮定します。

1. 各参加者はローカルで長い文字列を考え出し、それを 67 の部分に分割し、文字列を回復するには 100 個あれば十分であるように 67 シェアを取得する消去コードを作成し、100 シェアのそれぞれを参加者の XNUMX 人に割り当て、暗号化します。同じ参加者の公開鍵。 その後、エンコードされたすべての共有が公開されます。

2. 参加者は、特定の 67 人の参加者からのコード化セットに関する合意に達するために、ある種のコンセンサスを使用します。

3. 合意に達すると、各参加者は公開鍵で暗号化された 67 セットのそれぞれの暗号化された共有を取得し、そのようなすべての共有を復号化し、そのようなすべての復号化された共有を公開します。

4. 67 人の参加者がステップ (3) を完了すると、消失コードの特性により、合意されたすべてのセットが完全にデコードおよび再構築され、参加者が (1) で開始した最初の行の XOR として最終的な番号を取得できます。 。

このプロトコルは偏りがなく、予測不可能であることがわかります。 結果として得られる乱数は合意に達した後に決定されますが、参加者の XNUMX/XNUMX が公開鍵で暗号化された部分を復号するまでは誰にもわかりません。 したがって、乱数は、それを再構築するのに十分な情報が公開される前に決定されます。

ステップ (1) で、参加者の XNUMX 人が、ある文字列の正しい消去コードではないエンコードされた共有を他の参加者に送信した場合はどうなりますか? 追加の変更を行わないと、異なる参加者は文字列をまったく復元できないか、異なる文字列を復元することになり、その結果、異なる参加者が異なる乱数を受け取ることになります。 これを防ぐには、次のことを行うことができます。各参加者は、エンコードされたシェアに加えて、 メルクラの木 すべてのそのような共有を送信し、各参加者に、エンコードされた共有自体とマークル ツリーのルートの両方、およびマークル ツリーに共有が含まれていることの証明を送信します。 ステップ (2) のコンセンサスでは、参加者はセットのセットに同意するだけでなく、そのようなツリーの特定のルートのセットにも同意します (一部の参加者がプロトコルから逸脱し、異なるマークル ツリーのルートを異なる参加者に送信した場合、コンセンサス中にそのような 67 つのルートが表示されますが、その行は結果セットには含まれません)。 コンセンサスの結果、67 のエンコードされた行とマークル ツリーの対応するルートが得られ、少なくとも 67 人の参加者 (対応する行を提案した参加者と同じである必要はありません) が存在することになります。消去コードのシェアを含むメッセージと、対応するツリーでのシェアの発生の証拠が消えました。

ステップ (4) で、参加者が特定の文字列の 67 ビートを解読し、そこから元の文字列を再構築しようとすると、次のいずれかのオプションが考えられます。

1. 文字列が復元され、再度消去エンコードされ、ローカルに計算されたシェアに対してマークル ツリーが計算されると、ルートは合意に達したルートと一致します。

2. 行は復元されますが、ローカルで計算されたルートは、合意に達したルートと一致しません。

3. 行は復元されません。

上記の少なくとも 1 人の参加者にオプション (1) が発生した場合、すべての参加者にオプション (2) が発生し、その逆、少なくとも 3 人の参加者にオプション (2) または (3) が発生した場合は、すべての参加者に対して、オプション (XNUMX) または (XNUMX) が発生します。 したがって、セット内の各行について、すべての参加者がその行の回復に成功するか、すべての参加者がその行の回復に失敗するかのどちらかになります。 結果の乱数は、参加者が回復できた行のみの XOR になります。

しきい値署名

ランダム性に対するもう XNUMX つのアプローチは、BLS しきい値署名と呼ばれるものを使用することです。 しきい値署名に基づく乱数生成器は、上記で説明した消去コードベースのアルゴリズムとまったく同じ保証を備えていますが、生成された数値ごとにネットワーク上に送信されるメッセージの漸近数が大幅に少なくなります。

BLS 署名は、複数の参加者がメッセージに対して XNUMX つの共通の署名を作成できるようにする設計です。 これらの署名は、複数の署名を送信する必要がないため、スペースと帯域幅を節約するためによく使用されます。 

ブロックチェーン プロトコルでの BLS 署名の一般的な用途は、乱数の生成に加えて、BFT プロトコルでのブロック署名です。 100 人の参加者がブロックを作成し、そのうち 67 人が署名したブロックは最終的なものとみなされます。 全員が BLS 署名の各自の部分を送信し、コンセンサス アルゴリズムを使用してそのうちの 67 個に同意し、それらを 67 つの BLS 署名にマージできます。 任意の 67 (またはそれ以上) の部分を使用して最終的な署名を作成できます。署名は、どの 67 の署名が結合されたかによって異なるため、異なる場合があります。ただし、67 の参加者による選択が異なると、異なる署名が作成されますが、そのような署名はすべて有効です。ブロックの署名。 残りの参加者は、ネットワーク経由でブロックごとに XNUMX 署名ではなく XNUMX 署名だけを受信して​​検証するだけで済み、ネットワークの負荷が大幅に軽減されます。

参加者が使用する秘密鍵が特定の方法で生成された場合、どの 67 個の署名 (またはそれ以上、それ以下) が集約されても、結果として得られる署名は同じになることがわかります。 これはランダム性のソースとして使用できます。参加者はまず、署名するメッセージに同意します (これは RANDAO の出力または最後のブロックのハッシュである可能性があります。毎回変更される限り、実際には問題ありません)一貫性があります) を作成し、それに対する BLS 署名を作成します。 生成の結果は、67 人の参加者がパーツを提供するまで予測できません。その後、出力は事前に決定されており、参加者のアクションに依存することはできません。

このランダム性へのアプローチは、オンラインの参加者の少なくとも XNUMX/XNUMX が両方ともプロトコルに従う限り実行可能であり、参加者の少なくとも XNUMX/XNUMX がプロトコルに従う限り公平で予測不可能です。 参加者の XNUMX/XNUMX を超え XNUMX/XNUMX 未満を制御する攻撃者はプロトコルを停止できますが、その出力を予測したり影響を与えたりすることはできないことに注意することが重要です。

しきい値署名自体は非常に興味深いトピックです。 記事の後半では、しきい値署名がどのように機能するか、またしきい値署名を乱数生成器として使用できるように参加者キーを生成する必要があることを詳しく分析します。

結論

この記事は、一連の技術ブログ記事の最初の記事です NEAR。 NEAR は、開発の容易さとエンドユーザーの使いやすさに重点を置いた分散型アプリケーションを開発するためのブロックチェーン プロトコルおよびプラットフォームです。

プロトコル コードはオープンであり、実装は Rust で書かれており、次の場所で見つけることができます。 ここで.

NEAR の開発がどのようなものかを確認し、オンライン IDE で実験することができます ここで.

すべてのニュースをロシア語でフォローできます。 電報グループ と VKontakteのグループ、公式では英語で さえずり.

またね！

出所： habr.com