こんにちは、Habr！
この記事では、お互いを信頼していない参加者による疑似ランダム数の生成について説明します。以下で説明するように、「ほぼ」優れたジェネレーターを実装するのは非常に簡単ですが、非常に優れたジェネレーターを実装することは困難です。
お互いを信頼していない参加者のためにわざわざランダムな数字を生成するのはなぜですか？アプリケーションの1つの領域は、分散型アプリケーションです。たとえば、参加者からの入札を受け入れ、49％の確率で金額を2倍にするか、51％から取得するアプリケーションは、偏りのない方法でランダムな数値を取得できる場合にのみ機能します。攻撃者がランダム数ジェネレーターの結果に影響を与え、アプリケーションで支払いを受ける可能性をわずかに高めることができれば、攻撃者は簡単に彼を荒廃させることができます。
分散ランダム数生成プロトコルを設計するときは、次の3つのプロパティが必要です。
彼は偏見がないに違いない。言い換えれば、参加者は、ランダム数ジェネレーターの結果に影響を与えるべきではありません。
彼は予測できないに違いない。言い換えると、参加者は、生成される前に、生成される番号を予測（またはそのプロパティのいずれかを推測）できないようにする必要があります。
プロトコルは実行可能である必要があります。つまり、特定の割合の参加者がネットワークから切断したり、プロトコルを意図的に停止しようとしたりすることに抵抗する必要があります。
この記事では、RANDAO + VDFと消去コードアプローチの2つのアプローチについて説明します。次のパートでは、しきい値署名アプローチについて詳しく見ていきます。
しかし、最初に、実行可能で、予測不可能であるが、偏っている、単純で一般的に使用されるアルゴリズムを分解してみましょう。
RANDAO
RANDAO - , , . , . , XOR, .
, , . .
(.. ): , , . , , , , .
, , RANDAO? , , , . , , , , XOR, , , . , 1 . , .
, , -. . , .
RANDAO + VDF
, RANDAO , : , , XOR , , , , .
(vdf_output, vdf_proof) = VDF_compute(input) //
correct = VDF_verify(input, vdf_output, vdf_proof) // Verifiable Delay Function, VDF. , , , .
VDF . , , VDF , Ethereum 2.0 RANDAO VDF . , , , , ( , ).
VDF, VDF . , , 10x. , ASIC, VDF , , RANDAO. - , , , , .
VDF ASIC 100+ , . , 10 , VDF, ASIC, 100 , 10- , , , VDF, , 100 x 100 = ~ 3 .
Ethereum Foundation ASIC. , , RANDAO + VDF , ASIC.
. , 100 . , :
, 67 , 100 , , 67 , 100 . .
, 67 .
, 67 , , .
67 (3), , XOR , (1).
, . , , ⅔ , . , , , , .
, (1) , ? , , , . , : , , , , , . (2) , ( , , , ). 67 , 67 ( ), 67 , .
(4) 67 , , :
, , , , .
, , .
.
, (1), (1), , (2) (3), (2) (3). , , . – XOR , .
BLS. , , , , , .
BLS – , . , .
BLS- , , – BFT. , 100 , , 67 . BLS- -, 67 , BLS-. 67 ( ) , , 67 , , , 67- , . , 67, .
, , , , , 67 ( , ) , . : , ( RANDAO , , ), BLS-. , 67 , .
, ⅔ , ⅓ . , , ⅓ ⅔ , .
– . , , .
– NEAR. NEAR – , .
!