¿Es posible generar números aleatorios si no confiamos el uno en el otro? Parte 1

¡Hola, Habr!

En este artículo hablaré sobre la generación de números pseudoaleatorios por parte de participantes que no confían entre sí. Como veremos a continuación, implementar un generador “casi” bueno es bastante simple, pero uno muy bueno es difícil.

¿Por qué molestarse en generar números aleatorios para participantes que no confían entre sí? Un área de aplicación son las aplicaciones descentralizadas. Por ejemplo, una aplicación que acepta una oferta de un participante y duplica la cantidad con una probabilidad del 49%, o la quita del 51%, solo funcionará si puede obtener un número aleatorio de manera abierta. Si un atacante puede influir en el resultado del generador de números aleatorios e incluso aumentar ligeramente sus posibilidades de recibir un pago en la aplicación, puede devastarlo fácilmente.

Cuando diseñamos un protocolo de generación de números aleatorios distribuidos, queremos que tenga tres propiedades:

1. Debe ser imparcial. En otras palabras, ningún participante debe influir de ninguna manera en el resultado del generador de números aleatorios.

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 .

, .

!