Est-il possible de générer des nombres aléatoires si nous ne nous faisons pas confiance? Partie 1

Bonjour, Habr!

Dans cet article, je parlerai de la génération de nombres pseudo-aléatoires par des participants qui ne se font pas confiance. Comme nous le verrons ci-dessous, il est assez facile d'implémenter un générateur «presque» bon, mais un très bon générateur est difficile.

Pourquoi se donner la peine de générer des nombres aléatoires pour les participants qui ne se font pas confiance? Un domaine d'application est celui des applications décentralisées. Par exemple, une application qui accepte une offre d'un participant et double le montant avec une probabilité de 49%, ou la prend à partir de 51%, ne fonctionnera que si elle peut obtenir un nombre aléatoire de manière ouverte. Si un attaquant peut influencer le résultat du générateur de nombres aléatoires, et même augmenter légèrement ses chances d'être payé dans l'application, il peut facilement le dévaster.

Lorsque nous concevons un protocole de génération de nombres aléatoires distribués, nous voulons qu'il ait trois propriétés:

1. Il doit être impartial. En d'autres termes, aucun participant ne devrait en aucune façon influencer le résultat du générateur de nombres aléatoires.

2. . , , ( - ) , .

3. , , - .

: RANDAO + VDF , . , .

, , , .

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.

, VDF .

, . ⅓ , , ⅔ , .

. , 100 . , :

1. , 67 , 100 , , 67 , 100 . .

2. , 67 .

3. , 67 , , .

4. 67 (3), , XOR , (1).

, . , , ⅔ , . , , , , .

, (1) , ? , , , . , : , , , , , . (2) , ( , , , ). 67 , 67 ( ), 67 , .

(4) 67 , , :

1. , , , , .

2. , , .

3. .

, (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 – , .

, Rust, .

NEAR, -IDE .

, .

!