Ist es möglich, Zufallszahlen zu generieren, wenn wir uns nicht vertrauen? Teil 1

Hallo Habr!

In diesem Artikel werde ich über das Generieren von Pseudozufallszahlen durch Teilnehmer sprechen, die sich nicht vertrauen. Wie wir weiter unten sehen werden, ist die Implementierung eines „fast“ guten Generators recht einfach, aber ein sehr guter ist schwierig.

Warum Zufallszahlen für Teilnehmer generieren, die sich nicht vertrauen? Ein Anwendungsbereich sind dezentrale Anwendungen. Beispielsweise funktioniert eine Anwendung, die ein Gebot eines Teilnehmers annimmt und entweder den Betrag mit einer Wahrscheinlichkeit von 49% verdoppelt oder von 51% annimmt, nur, wenn sie eine Zufallszahl auf unvoreingenommene Weise erhalten kann. Wenn ein Angreifer das Ergebnis des Zufallszahlengenerators beeinflussen und seine Chance, in der Anwendung bezahlt zu werden, sogar geringfügig erhöhen kann, wird er ihn leicht zerstören.

Wenn wir ein Protokoll zur Erzeugung verteilter Zufallszahlen entwerfen, möchten wir, dass es drei Eigenschaften hat:

1. Er muss unvoreingenommen sein. Mit anderen Worten, kein Teilnehmer sollte das Ergebnis des Zufallszahlengenerators in irgendeiner Weise beeinflussen.

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 .

, .

!