乱数と分散型ネットワーク: 実用的な応用

導入

「乱数の生成は、偶然に任せるにはあまりにも重要です。」
ロバート・カヴュー、1970年

この記事では、信頼できない環境での集団乱数生成を使用したソリューションの実際の適用について説明します。 つまり、ランダムがブロックチェーンでどのように、そしてなぜ使用されるのか、そして「良い」ランダムと「悪い」ランダムを区別する方法について少し説明します。 真の乱数を生成することは、たとえ XNUMX 台のコンピューターであっても非常に難しい問題であり、暗号学者によって長い間研究されてきました。 分散型ネットワークでは、乱数の生成はさらに複雑で重要です。

参加者がお互いを信頼していないネットワークでは、議論の余地のない乱数を生成する機能により、多くの重要な問題を効果的に解決し、既存のスキームを大幅に改善することができます。 さらに、経験の浅い読者には最初はそう思われるかもしれませんが、ギャンブルや宝くじはここでの最大の目的ではありません。

乱数の生成

コンピューターは乱数を自ら生成することができないため、乱数を生成するには外部の助けが必要です。 コンピュータは、たとえば、マウスの動き、メモリの使用量、プロセッサ ピンの迷走電流、およびエントロピー ソースと呼ばれるその他の多くのソースから、何らかのランダムな値を取得できます。 これらの値自体は、特定の範囲内にあるか、予測可能な変化パターンを持っているため、完全にランダムではありません。 このような数値を特定の範囲内の真の乱数に変えるには、暗号変換が適用され、エントロピー ソースの不均一に分散された値から均一に分散された擬似乱数値が生成されます。 結果として得られる値は、真のランダムではなく、エントロピーから決定論的に導出されることから、擬似ランダムと呼ばれます。 優れた暗号アルゴリズムは、データを暗号化するときに、ランダムなシーケンスと統計的に区別できない暗号文を生成します。そのため、ランダム性を生み出すために、エントロピーのソースを使用できます。これにより、たとえ狭い範囲であっても値の優れた再現性と予測不可能性のみが提供されます。残りの作業はビットの分散と混合です。結果の値は暗号化アルゴリズムによって引き継がれます。

簡単な教育プログラムを完成させるために、XNUMX 台のデバイス上でも乱数を生成することは、データのセキュリティを確保するための柱の XNUMX つであることを付け加えておきます。生成された擬似乱数は、さまざまなネットワークで安全な接続を確立するときに使用され、負荷分散、整合性監視、その他多くのアプリケーション用の暗号キー。 多くのプロトコルのセキュリティは、信頼性が高く外部からは予測できないランダムを生成し、それを保存し、プロトコルの次のステップまで公開しない能力に依存しています。そうしないと、セキュリティが侵害されます。 擬似乱数値ジェネレーターへの攻撃は非常に危険であり、乱数生成を使用するすべてのソフトウェアが即座に脅かされます。

暗号化の基礎コースを受講していれば、これらすべてを知っているはずなので、分散ネットワークについて続けましょう。

ブロックチェーンにおけるランダム

まず第一に、スマート コントラクトをサポートするブロックチェーンについて説明します。ブロックチェーンは、高品質で否定できないランダム性によって提供される機会を最大限に活用できます。 さらに、簡潔にするために、このテクノロジーを「」と呼びます。公的に検証可能なランダム ビーコン」またはPVRB。 ブロックチェーンは、あらゆる参加者が情報を検証できるネットワークであるため、名前の重要な部分は「公的に検証可能」、つまり「公的に検証可能」です。 誰でも計算を使用して、ブロックチェーンに投稿された結果の数値が次の特性を持っているという証拠を得ることができます。

• 結果は、証明された一様な分布を持っていなければなりません。つまり、証明された強力な暗号化に基づいている必要があります。
• 結果のビットを制御することはできません。 したがって、結果を事前に予測することはできません。
• プロトコルに参加しなかったり、攻撃メッセージでネットワークに過負荷をかけたりして、生成プロトコルを妨害することはできません。
• 上記のすべては、許容される数の不誠実なプロトコル参加者 (たとえば、参加者の 1/3) の共謀に耐性がなければなりません。

少数の参加者グループが共謀して、制御された偶数/奇数のランダムを生成する可能性は、セキュリティ ホールです。 ランダム発行を阻止するグループの能力はセキュリティ ホールです。 一般に、多くの問題があり、このタスクは簡単ではありません...

PVRB の最も重要なアプリケーションは、ブロックチェーン上のさまざまなゲーム、宝くじ、そして一般的にあらゆる種類のギャンブルであるようです。 確かに、これは重要な方向性ですが、ブロックチェーンのランダム性にはさらに重要な用途があります。 それらを見てみましょう。

コンセンサスアルゴリズム

PVRB は、ネットワークのコンセンサスを組織する上で大きな役割を果たします。 ブロックチェーン内のトランザクションは電子署名によって保護されているため、「トランザクションに対する攻撃」は常に、ブロック (または複数のブロック) へのトランザクションの包含/除外になります。 そして、コンセンサス アルゴリズムの主なタスクは、これらのトランザクションの順序と、これらのトランザクションを含むブロックの順序について合意することです。 また、実際のブロックチェーンに必要な特性はファイナリティです。ファイナリティとは、ファイナライズされたブロックまでのチェーンが最終的なものであり、新しいフォークの出現によって決して除外されないことに同意するネットワークの能力です。 通常、ブロックが有効であり、最も重要なことに最終的なものであることに同意するには、大多数のブロック生成者 (以下、BP - ブロック生成者と呼びます) から署名を収集する必要があります。それには、少なくともブロックチェーンの配信が必要です。すべての BP に署名を送信し、すべての BP 間で署名を配布します。 BP の数が増加するにつれて、ネットワーク内で必要なメッセージの数も指数関数的に増加します。そのため、たとえば Hyperledger pBFT コンセンサスで使用されるファイナリティを必要とするコンセンサス アルゴリズムは、数十の BP から開始すると必要な速度で動作しなくなり、膨大な数の接続。

ネットワーク内に否定できない誠実な PVRB が存在する場合、最も単純な近似でも、それに基づいてブロック プロデューサーの XNUMX 人を選択し、プロトコルの XNUMX ラウンド中に彼を「リーダー」として任命できます。 もし持っていれば N ブロックプロデューサー、そのうち M: M > 1/2 N 正直であり、トランザクションを検閲せず、「二重支払い」攻撃を実行するためにチェーンを分岐させない場合、均一に分散された異議のない PVRB を使用すると、確率で正直なリーダーを選択できるようになります。 M / N (M / N > 1/2)。 各リーダーにブロックを生成してチェーンを検証できる独自の時間間隔が割り当てられ、これらの間隔が時間的に等しい場合、誠実な BP のブロック チェーンは悪意のある BP によって形成されるチェーンよりも長くなり、コンセンサスはアルゴリズムはチェーンの長さに依存するため、単に「悪い」チェーンを破棄します。 各 BP に等しい時間スライスを割り当てるこの原則は、Graphene (EOS の前身) で初めて適用され、ほとんどのブロックを 2 つの署名で閉じることができるため、ネットワーク負荷が大幅に軽減され、このコンセンサスが非常に迅速に機能することが可能になります。着実に。 ただし、EOS ネットワークは現在、3/XNUMX BP の署名によって確認される特別なブロック (Last Ireversible Block) を使用する必要があります。 これらのブロックは、ファイナリティ (最後の最後の不可逆ブロックより前に開始されるチェーン フォークの不可能性) を保証するために機能します。

また、実際の実装では、プロトコルスキームはより複雑です。ブロックの欠落やネットワークの問題が発生した場合にネットワークを維持するために、提案されたブロックの投票がいくつかの段階で実行されますが、これを考慮しても、PVRB を使用するコンセンサスアルゴリズムには次のことが必要です。 BP 間のメッセージが大幅に少なくなり、従来の PVFT やそのさまざまな修正よりも高速化が可能になります。

このようなアルゴリズムの最も著名な代表例は次のとおりです。 ウロボロス Cardano チームによるもので、BP の共謀を数学的に証明できると言われています。

Ouroboros では、PVRB はいわゆる「BP スケジュール」、つまり各 BP にブロックを公開するための独自のタイムスロットが割り当てられるスケジュールを定義するために使用されます。 PVRB を使用する大きな利点は、BP が (貸借対照表のサイズに応じて) 完全に「平等」であることです。 PVRB の整合性により、悪意のある BP はタイムスロットのスケジューリングを制御できないため、チェーンのフォークを事前に準備して分析することでチェーンを操作できなくなります。また、フォークを選択するには、単にフォークの長さに依存するだけで十分です。 BP の「有用性」とそのブロックの「重み」を計算するためのトリッキーな方法を使用せずにチェーンを構築します。

一般に、分散型ネットワークでランダムな参加者を選択する必要があるすべての場合、ブロック ハッシュなどに基づく決定論的なオプションではなく、PVRB がほぼ常に最良の選択となります。 PVRB がないと、参加者の選択に影響を与える能力により、攻撃者が複数の将来から次の破損した参加者を選択したり、決定におけるより大きなシェアを確保するために一度に複数の参加者を選択したりする攻撃が発生します。 PVRB を使用すると、この種の攻撃の信頼性が失われます。

スケーリングと負荷分散

PVRB は、負荷の軽減や支払いのスケーリングなどのタスクにも大きなメリットをもたらします。 まず、次のことをよく理解するのが理にかなっています。 論文 リベスタ「マイクロペイメントとしての電子宝くじ」。 一般的な考え方は、支払者から受取人に 100 枚の 1 セントの支払いを行う代わりに、賞金 1 ドル = 100 セントの正直な宝くじをプレイすることができます。この場合、支払者は、1 回につき 100 枚の「宝くじ」を銀行に渡します。 1c支払い。 これらのチケットの 99 つが XNUMX ドルの瓶を獲得し、受信者がブロックチェーンに記録できるのはこのチケットです。 最も重要なことは、残りの XNUMX 枚のチケットが、外部の関与なしに、プライベート チャネルを通じて任意の速度で受信者と支払者の間で転送されることです。 Emercoin ネットワーク上のこのスキームに基づくプロトコルの詳しい説明を読むことができます。 ここで.

このスキームには、受信者が当選チケットを受け取った直後に支払者へのサービスを停止する可能性があるなど、いくつかの問題がありますが、分単位の請求やサービスの電子購読などの多くの特殊なアプリケーションでは、これらは無視できます。 もちろん、主な要件は宝くじの完全性であり、その実装には PVRB が絶対に必要です。

ランダムな参加者の選択は、シャーディング プロトコルにとっても非常に重要です。シャーディング プロトコルの目的は、ブロック チェーンを水平方向に拡張し、異なる BP がトランザクションの範囲のみを処理できるようにすることです。 これは、特にシャードを結合するときのセキュリティの観点から、非常に困難な作業です。 コンセンサスアルゴリズムのように、特定のシャードの責任者を割り当てる目的でランダムな BP を公平に選択することも、PVRB のタスクです。 集中型システムでは、シャードはバランサーによって割り当てられます。バランサーは単にリクエストからハッシュを計算し、必要なエグゼキューターに送信します。 ブロックチェーンでは、この割り当てに影響を与える能力がコンセンサスへの攻撃につながる可能性があります。 たとえば、トランザクションの内容は攻撃者によって制御される可能性があり、攻撃者は、自分が制御するシャードにどのトランザクションが送信されるかを制御し、そのシャード内のブロックのチェーンを操作することができます。 Ethereum のシャーディング タスクに乱数を使用する問題についてのディスカッションを読むことができます。 ここで
シャーディングはブロックチェーンの分野で最も野心的かつ深刻な問題の XNUMX つであり、その解決策により、素晴らしいパフォーマンスとボリュームの分散型ネットワークを構築できるようになります。 PVRB は、それを解決するための重要なブロックの XNUMX つにすぎません。

ゲーム、経済プロトコル、仲裁

ゲーム業界における乱数の役割を過大評価することは困難です。 オンラインカジノでの明示的な使用、およびプレーヤーのアクションの効果を計算する際の暗黙的な使用はすべて、中央のランダム性ソースに依存する方法がない分散型ネットワークにとっては非常に困難な問題です。 しかし、ランダムな選択は多くの経済的問題も解決し、よりシンプルで効率的なプロトコルの構築に役立ちます。 私たちのプロトコルで、いくつかの安価なサービスの支払いに関する紛争があり、このような紛争が発生することはほとんどないとします。 この場合、議論の余地のない PVRB があれば、顧客と販売者はランダムに、ただし一定の確率で紛争を解決することに同意できます。 たとえば、60% の確率で顧客が勝ち、40% の確率で売り手が勝ちます。 このアプローチは、第一の観点からすると不合理ですが、第三者の参加や不必要な時間の無駄を伴うことなく、双方の当事者にとって都合の良い、正確に予測可能な勝敗の割合で紛争を自動的に解決することができます。 さらに、確率比は動的であり、いくつかのグローバル変数に依存する可能性があります。 たとえば、会社の業績が良好で、紛争の数が少なく、収益性が高い場合、その会社は紛争を解決する確率を顧客中心に、たとえば 70/30 または 80/20 に自動的にシフトしたり、その逆に変更したりできます。紛争に多額の費用がかかり、詐欺的または不適切な場合は、可能性を別の方向にシフトできます。

トークンキュレートされたレジストリ、予測市場、結合曲線、その他多くの興味深い分散プロトコルは、良い行動が報われ、悪い行動が罰せられる経済ゲームです。 これらには、保護が互いに競合するセキュリティ上の問題が含まれることがよくあります。 数十億のトークン (「ビッグステーク」) を持つ「クジラ」による攻撃から保護されているものは、残高が少ない数千のアカウント (「シビルステーク」) による攻撃には脆弱であり、単一の攻撃に対して講じられる対策は、多額の賭け金を使った作業を不採算にするために設定された線形手数料は、通常、別の攻撃によって信用を失います。 ここでは経済ゲームについて話しているので、対応する統計的重みを事前に計算し、手数料を適切な分布を持つランダム化された手数料に置き換えるだけです。 このような確率的な手数料は、ブロックチェーンに信頼できるランダム性のソースがあり、複雑な計算を必要としない場合に非常に簡単に実装されるため、クジラとシビルの両方の生活が困難になります。
同時に、このランダム性の単一ビットを制御すると、確率を半分に減らしたり増やしたりする不正行為が可能になるため、正直な PVRB がそのようなプロトコルの最も重要なコンポーネントであることを引き続き覚えておく必要があります。

適切なランダムはどこで見つけられますか?

理論的には、分散型ネットワークにおける公正なランダム選択により、ほぼすべてのプロトコルが共謀に対して安全であることが証明されています。 理論的根拠は非常に単純です。ネットワークが単一の 0 または 1 ビットに同意し、参加者の半数未満が不正である場合、十分な反復を経て、ネットワークは固定の確率でそのビットに関して合意に達することが保証されます。 それは単純に、正直なランダムにより 51% の確率で 100 人の参加者から 51 人が選ばれるからです。 しかし、これは理論上の話です、なぜなら... 実際のネットワークでは、記事にあるようなレベルのセキュリティを確保するには、ホスト間の多くのメッセージ、複雑なマルチパス暗号化が必要であり、プロトコルが複雑になるとすぐに新しい攻撃ベクトルが追加されます。
そのため、ブロックチェーンには耐性が証明された PVRB がまだ見つかっていないのですが、実際のアプリケーション、複数の監査、負荷、そしてもちろん実際の攻撃によってテストされるのに十分な期間使用されていたはずであり、それがなければブロックチェーンと呼ぶのは困難です。本当に安全な製品。

ただし、有望なアプローチがいくつかあり、それらは多くの点で異なりますが、そのうちの XNUMX つが確実に問題を解決します。 最新のコンピューティング リソースを使用すると、暗号理論を実際のアプリケーションに非常に巧みに変換できます。 将来的には、PVRB 実装について喜んでお話しさせていただきます。現在、PVRB 実装がいくつかあり、それぞれに重要なプロパティと実装機能の独自のセットがあり、それぞれの背後には良いアイデアがあります。 ランダム化に関与するチームはそれほど多くありませんが、各チームの経験は他のチームにとって非常に重要です。 私たちの情報により、他のチームが前任者の経験を考慮してより迅速に行動できるようになることを願っています。

出所： habr.com