É possível gerar números aleatórios se não confiarmos uns nos outros? Parte 1

Olá, Habr!

Neste artigo, vou falar sobre a geração de números pseudo-aleatórios por participantes que não confiam uns nos outros. Como veremos a seguir, é bastante fácil implementar um gerador “quase” bom, mas um muito bom é difícil.

Por que se preocupar em gerar números aleatórios para participantes que não confiam uns nos outros? Uma área de aplicação é em aplicativos descentralizados. Por exemplo, um aplicativo que aceita um lance de um participante e duplica o valor com uma probabilidade de 49% ou tira de 51% só funcionará se puder obter um número aleatório de forma imparcial. Se um invasor puder influenciar o resultado do gerador de números aleatórios e até mesmo aumentar ligeiramente sua chance de ser pago no aplicativo, ele pode facilmente devastá-lo.

Quando projetamos um protocolo de geração de número aleatório distribuído, queremos que ele tenha três propriedades:

1. Ele deve ser imparcial. Em outras palavras, nenhum participante deve influenciar de forma alguma o resultado do gerador de números aleatórios.

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 .

, .

!