乱数と分散ネットワーク：実用的なアプリケーション

はじめに

「ランダムな番号の生成はあまりにも重要であり、偶然に任せることはできません」

ロバートカヴー、1970

この記事は、信頼できない環境で乱数の集合生成を使用したソリューションの実用的なアプリケーションに専念します。 簡単に説明すると、ブロックチェーンでランダムに使用される方法と理由、および「良い」ランダムと「悪い」を区別する方法について少し説明します。 真に乱数を生成することは、別のコンピューターであっても非常に難しい問題であり、暗号学者によって長い間研究されてきました。 分散ネットワークでは、乱数生成はさらに複雑で重要です。

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

乱数生成

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

短い教育プログラムを完了するために、1台のデバイスでも乱数を生成することはデータのセキュリティを確保するための柱の1つであると付け加えます。さらに多くの用途に。 多くのプロトコルのセキュリティは、信頼性が高く予測できないランダムデータを外部から生成し、保存し、プロトコルの次のステップまで開かないかどうかに依存します。そうしないとセキュリティが低下します。 疑似ランダム値ジェネレーターに対する攻撃は非常に危険であり、ランダム生成を一度に使用するすべてのソフトウェアを脅かします。

基本的な暗号化コースを修了している場合は、これらすべてを知っておく必要があります。そのため、分散ネットワークを続けましょう。

ブロックチェーンランダム

まず、スマートコントラクトをサポートするブロックチェーンについて説明します。高品質で否定できないランダム性によって提供される機会を十分に活用できるのはブロックチェーンです。 さらに、簡潔にするために、このテクノロジーを「 公開検証可能なランダムビーコン 」またはPVRBと呼びます。 ブロックチェーンは参加者が情報を検証できるネットワークであるため、名前の重要な部分は「公開検証可能」です。 計算の助けを借りれば誰でも、ブロックチェーンに配置された結果の数値が次のプロパティを持っていることを証明できます。

• 結果は、証明可能な均一な分布、つまり証明可能な強力な暗号化に基づいている必要があります。
• 結果のビットを制御することはできません。 その結果、結果を事前に予測することはできません。
• プロトコルに参加しないか、攻撃メッセージでネットワークをオーバーロードすることにより、生成プロトコルを妨害することはできません。
• 上記のすべては、プロトコルの不正な参加者の許容数（たとえば、参加者の3分の1）の共謀に抵抗する必要があります。

参加者の共謀する小さなグループが、制御された偶数/奇数のランダムを生成する機会は、セキュリティホールです。 グループがランダムハウスの発行を停止する機会は、セキュリティホールです。 一般的に、多くの問題があり、このタスクは簡単ではありません...

PVRBの最も重要なアプリケーションは、さまざまなゲーム、宝くじ、および一般的にブロックチェーン上のあらゆる種類のギャンブルです。 実際、これは重要な分野ですが、ランダムブロックチェーンにはより重要な用途があります。 それらを考慮してください。

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

PVRBは、ネットワークのコンセンサスに不可欠です。 ブロックチェーン内のトランザクションは電子署名によって保護されているため、「トランザクションに対する攻撃」とは、常にブロック（または複数のブロック）でのトランザクションの包含/除外です。 コンセンサスアルゴリズムの主なタスクは、これらのトランザクションの順序と、これらのトランザクションを含むブロックの順序について合意することです。 また、実際のブロックチェーンに必要な特性はファイナリティです。ファイナライズされたブロックへのチェーンがファイナルであり、新しいフォークの出現により除外されないことをネットワークが同意する能力です。 通常、ブロックが有効であり、最も重要なのは最終であることに同意するために、ほとんどのブロックプロデューサー（以降BP-ブロックプロデューサー）から署名を収集する必要があります。 。 BPの数が増えると、ネットワーク上の必要なメッセージの数が指数関数的に増加するため、HyperledgerのpBFTコンセンサスで使用されるアルゴリズムなど、最終性を必要とするコンセンサスアルゴリズムは、数十のBPから開始して適切な速度で動作せず、膨大な数の接続が必要になります。

ネットワークに否定できない誠実なPVRBがある場合、最も単純な近似であっても、それに基づいてブロックプロデューサーの1つを選択し、プロトコルの1ラウンドの「リーダー」を指定できます。 N



ブロックプロデューサーがあり、 M: M > 1/2 N



が正直であり、トランザクションを検閲せず、「二重支出」攻撃を行うためにフォークチェーンを構築しない場合、均一に分散した議論の余地のないPVRBを使用すると、正直なリーダーを選択できます確率M / N (M / N > 1/2)



。 各リーダーにブロックを作成してチェーンを検証できる独自の時間間隔が割り当てられ、これらの間隔が時間的に等しい場合、正直なBPブロックのチェーンは、悪意のあるBPによって形成されたチェーンより長くなり、コンセンサスアルゴリズムはチェーンの長さに依存します「不良」を単に破棄します。 各BPに等しいタイムスライスを割り当てるこの原則は、グラフェン（EOSの前身）で最初に適用され、1つの署名でほとんどのブロックを閉じることができます。これにより、ネットワーク負荷が大幅に削減され、このコンセンサスが非常に迅速かつ着実に機能します。 ただし、EOSネットワークでは、2/3 BP署名によって確認される特別なブロック（最後の不可逆ブロック）を使用する必要があります。 これらのブロックは、最終性（最後の最後の不可逆ブロックよりも早く始まるフォークチェーンの不可能性）を確保するために使用されます。

また、実際の実装では、プロトコルスキームはより複雑です-ブロックの欠落やネットワークの問題が発生した場合にネットワークを維持するために、提案されたブロックの投票はいくつかの段階で実行されますが、これを念頭に置いても、PVRBコンセンサスアルゴリズムはBP間のメッセージを大幅に少なくし、これにより、従来のPBFTまたはそのさまざまな変更よりも高速にできます。

そのようなアルゴリズムの最も印象的な代表者：カルダノチームのウロボロスは、発表されたように、BP間の共謀に対して数学的に証明可能な抵抗力を持っています。

ウロボロスでは、PVRBを使用して、いわゆる「BPスケジュール」、つまり各BPがブロックを公開するための独自のタイムスロットに割り当てられるスケジュールを定義します。 PVRBを使用する大きな利点は、BPの完全な「平等な権利」です（残高の大きさによる）。 誠実なPVRBは、悪意のあるBPがタイムスロットのスケジュールを制御できないことを保証するため、事前にチェーンフォークを準備および分析してチェーンを操作することはできません。フォークを選択するには、BPの「有用性」を計算するのに難しい方法を使用せずにチェーンの長さに依存するだけで十分ですブロックの「重量」。

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

スケーリングと負荷分散

PVRBは、ワークロードを削減し、支払いをスケールするタスクでも大きなメリットがあります。 手始めに、Rivestの記事 「マイクロペイメントとしての電子宝くじ券」を読むことは理にかなっています。 一般的な本質は、支払人から受取人に1cを100回支払う代わりに、賞金1ドル= 100cの正直な宝くじをプレーできることです。支払者は、1cの支払ごとに100個の「宝くじ」を銀行に転送します。 これらのチケットの1つが銀行の$ 1を獲得し、受信者がブロックチェーンで修正できるのはこのチケットです。 最も重要なことは、残りの99枚のチケットは、外部からの参加なしに、プライベートチャネルを介して任意の速度で、受信者と支払人の間で転送されます。 ここで Emercoinネットワークのこの体系に基づくプロトコルの良い記述を見つけることができます 。

このスキームにはいくつかの問題があります。たとえば、受取人は当選チケットを受け取った直後に支払人へのサービスを停止する場合がありますが、分単位の課金やサービスへの電子サブスクリプションなど、多くの特別なアプリケーションでは無視できます。 もちろん、主な要件は宝くじの誠実さであり、PVRBはその開催に絶対に必要です。

ランダム参加者の選択もシャーディングプロトコルにとって非常に重要です。シャーディングプロトコルの目的は、ブロックのチェーンを水平方向にスケーリングし、異なるBPがトランザクションのスコープのみを処理できるようにすることです。 これは、特にシャードをマージする際のセキュリティに関して非常に難しいタスクです。 コンセンサスアルゴリズムのように、特定のシャードの責任者に割り当てるために、ランダムBPを正直に選択することもPVRBタスクです。 中央集中型システムでは、シャードはバランサーによって割り当てられ、バランサーはリクエストからハッシュを計算し、必要なエグゼキューターに送信します。 ブロックチェーンでは、この割り当てに影響を与える能力がコンセンサスへの攻撃につながる可能性があります。 たとえば、攻撃者はトランザクションの内容を制御でき、攻撃者は自分が制御するシャードにどのトランザクションを分類し、その中のブロックのチェーンを操作できます。 イーサリアムのシャーディングタスクに乱数を使用する問題については、 こちらをご覧ください。

シャーディングは、ブロックチェーンの分野で最も野心的で深刻なタスクの1つであり、そのソリューションにより、素晴らしいパフォーマンスとボリュームの分散ネットワークを構築できます。 PVRBは、それを解決する重要なブロックの1つにすぎません。

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

ゲーム業界での乱数の役割を過大評価することは困難です。 オンラインカジノでの明示的な使用、およびプレーヤーのアクションの効果の計算における暗黙の使用は、中央ネットワークのランダム性に依存することができない分散ネットワークにとって非常に難しい問題です。 しかし、ランダム選択は多くの経済的問題を解決し、よりシンプルで効率的なプロトコルを構築するのに役立ちます。 私たちのプロトコルには、いくつかの安価なサービスの支払いについての論争があり、これらの論争は非常にまれであるとします。 この場合、否定できないPVRBがある場合、顧客と売り手は紛争のランダムな解決に同意できますが、一定の確率で可能です。 たとえば、60％の確率でクライアントが勝ち、40％の確率で売り手が勝ちます。 このようなばかげたアプローチは、最初の観点から、勝者と敗者の正確に予測可能なシェアで紛争を自動的に解決することを可能にし、第三者の関与と不必要な時間の浪費なしに双方に適しています。 さらに、確率比は動的であり、いくつかのグローバル変数に依存します。 たとえば、企業の業績が良好で、紛争が少なく収益性が高い場合、紛争が多額の資金を必要とする場合、紛争解決の可能性を自動的に顧客志向、たとえば70/30または80/20にシフトできます。不正または不適切である場合、確率を他の方向にシフトできます。

トークンキュレーションレジストリ、予測市場、ボンディングカーブなど、多数の興味深い分散プロトコルは、良い行動と素晴らしい悪い行動に報いる経済的なゲームです。 多くの場合、セキュリティの問題が発生し、保護は互いに矛盾します。 数十億のトークンを持つ「クジラ」による攻撃（「ビッグステーク」）から保護されているものは、残高の少ない数千のアカウント（「シビルステーク」）による攻撃、および1つの攻撃に対して取られた措置（たとえば、大規模なステーキの仕事を不利にするために、彼らは通常、別の攻撃によって信用を失います。 これは経済的なゲームであるため、対応する統計的重みを事前に計算し、適切な分布のランダム化された手数料に単純に置き換えることができます。 ブロックチェーンにランダム性の信頼できるソースがあり、複雑な計算を必要とせず、クジラとシビルの生活を困難にしている場合、そのような確率的委員会は非常に簡単に実装されます。

このランダム化の単一ビットを制御することで、確率をごまかし、削減し、倍にすることができるため、正直なPVRBがそのようなプロトコルの最も重要なコンポーネントであることに注意してください。

正しいランダムはどこにありますか？

理論的には、分散ネットワークでの正直でランダムな選択は、共謀に対するほぼすべてのプロトコルの証明可能なセキュリティを提供します。 理論的根拠は非常に単純です-ネットワークが1ビット0または1に同意し、半数未満の参加者が不正である場合、十分な数の反復により、ネットワークはこのビットで一定の確率でコンセンサスになることが保証されます。 正直なランダムが51％のケースで100人の参加者から51人を選択するからです。 しかし、これは理論上です。なぜなら 実際のネットワークでは、記事のようなレベルのセキュリティを確保するために、ホスト間で大量のメッセージ、複雑なマルチパス暗号化が必要であり、プロトコルの複雑さはすぐに新しい攻撃ベクトルを追加します。

そのため、実際のアプリケーション、複数の監査、負荷、そしてもちろん実際の攻撃によってテストされるのに十分な時間使用された実証済みのPVRBがブロックチェーンにまだ表示されていません。

それにもかかわらず、いくつかの有望なアプローチが一度にあり、それらは多くの詳細が異なり、それらのいくつかは間違いなく問題を解決します。 最新の計算リソースにより、暗号理論は非常に巧みに実用的なアプリケーションになります。 将来的には、PVRBの実装についてお話しできることを楽しみにしています。現在、それらのいくつかがあり、それぞれに実装における重要なプロパティと機能の独自のセットがあり、それぞれに良いアイデアがあります。 ランダムに関与するチームは多くありません。各チームの経験は他のすべての人にとって非常に重要です。 私たちの情報が、他のチームが前任者の経験を考慮に入れてより速く動くことを可能にすることを願っています。