Apakah mungkin untuk menghasilkan angka acak jika kita tidak percaya satu sama lain? Bagian 1

Halo, Habr!

Pada artikel ini saya akan berbicara tentang menghasilkan bilangan pseudo-random oleh peserta yang tidak saling percaya. Seperti yang akan kita lihat di bawah, mengimplementasikan generator yang “hampir” bagus cukup sederhana, tetapi generator yang sangat bagus itu sulit.

Mengapa repot-repot membuat angka acak untuk peserta yang tidak percaya satu sama lain? Salah satu area aplikasi dalam aplikasi terdesentralisasi. Misalnya, aplikasi yang menerima tawaran dari peserta dan menggandakan jumlah dengan probabilitas 49%, atau mengambilnya dari 51%, hanya akan berfungsi jika bisa mendapatkan nomor acak dengan cara berpikiran terbuka. Jika penyerang dapat memengaruhi hasil penghasil nomor acak, dan bahkan sedikit meningkatkan peluangnya untuk mendapatkan bayaran dalam aplikasi, ia dapat dengan mudah menghancurkannya.

Ketika kami merancang protokol pembuatan nomor acak terdistribusi, kami ingin memiliki tiga properti:

1. Dia harus tidak memihak. Dengan kata lain, tidak ada peserta yang dengan cara apapun mempengaruhi hasil dari generator nomor acak.

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 .

, .

!