Is it possible to generate random numbers if we don't trust each other? Part 1

Hello, Habr!

In this article I will talk about generating pseudo-random numbers by participants who do not trust each other. As we will see below, it is quite easy to implement an “almost” good generator, but a very good one is difficult.

Why bother generating random numbers for participants who do not trust each other? One area of ​​application is in decentralized applications. For example, an application that accepts a bid from a participant and either doubles the amount with a 49% probability, or takes it from 51%, will only work if it can get a random number in an open-minded way. If an attacker can influence the result of the random number generator, and even slightly increase his chance of getting paid in the application, he can easily devastate him.

When we design a distributed random number generation protocol, we want it to have three properties:

1. He must be unbiased. In other words, no participant should in any way influence the result of the random number generator.

2. He must be unpredictable. In other words, no participant should be able to predict which number will be generated (or infer any of its properties) before it is generated.

3. The protocol must be viable, that is, resistant to the fact that a certain percentage of participants disconnect from the network or deliberately try to stop the protocol.

In this article we will look at two approaches: RANDAO + VDF and the erasure code approach. In the next part, we'll take a closer look at the threshold signature approach.

But first, let's break down a simple and commonly used algorithm that is viable, unpredictable, but biased.

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 .

, .

!