Je li moguće generirati slučajne brojeve ako ne vjerujemo jedni drugima? 1. dio

Hej Habr!

U ovom ću članku govoriti o generiranju pseudo-slučajnih brojeva od strane sudionika koji ne vjeruju jedni drugima. Kao što ćemo vidjeti u nastavku, implementacija "gotovo" dobrog generatora je prilično jednostavna, ali vrlo dobrog je teško.

Zašto bi bilo potrebno generirati nasumične brojeve između sudionika koji ne vjeruju jedni drugima? Jedno područje primjene su decentralizirane aplikacije. Na primjer, aplikacija koja prihvaća okladu od sudionika i udvostručuje iznos s vjerojatnošću od 49% ili oduzima s vjerojatnošću od 51% radit će samo ako može nepristrano primiti nasumični broj. Ako napadač može utjecati na ishod generatora slučajnih brojeva i čak malo povećati svoje šanse za isplatu u aplikaciji, lako će je uništiti.

Kada dizajniramo distribuirani protokol za generiranje slučajnih brojeva, želimo da ima tri svojstva:

1. Mora biti nepristran. Drugim riječima, nijedan sudionik ne smije ni na koji način utjecati na rezultat generatora slučajnih brojeva.

2. Mora da je nepredvidiv. Drugim riječima, niti jedan sudionik ne bi trebao moći predvidjeti koji će broj biti generiran (ili zaključiti bilo koje od njegovih svojstava) prije nego što se on generira.

3. Protokol mora biti održiv, odnosno otporan na činjenicu da se određeni postotak sudionika isključi s mreže ili namjerno pokuša zaustaviti protokol.

U ovom članku ćemo pogledati dva pristupa: RANDAO + VDF i pristup kodova za brisanje. U sljedećem ćemo dijelu detaljno ispitati pristup temeljen na potpisima praga.

Ali prvo, pogledajmo jednostavan i često korišten algoritam koji je održiv, nepredvidiv, ali pristran.

RANDAO

RANDAO je vrlo jednostavan i stoga često korišten pristup generiranju slučajnosti. Svi sudionici mreže prvo lokalno odaberu pseudoslučajni broj, zatim svaki sudionik šalje hash odabranog broja. Zatim sudionici naizmjence otkrivaju svoje odabrane brojeve i izvode operaciju XOR nad otkrivenim brojevima, a rezultat te operacije postaje rezultat protokola.

Korak objave hasheva prije otkrivanja brojeva je neophodan kako napadač ne bi mogao odabrati svoj broj nakon što je vidio brojeve ostalih sudionika. To bi mu omogućilo da gotovo sam odredi izlaz generatora slučajnih brojeva.

Tijekom protokola, sudionici trebaju dva puta doći do zajedničke odluke (tzv. konsenzusa): kada početi otkrivati ​​odabrane brojeve i stoga prestati prihvaćati hashove, a kada prestati prihvaćati odabrane brojeve i izračunavati rezultirajući slučajni broj. broj. Donošenje takvih odluka između sudionika koji nemaju povjerenja jedni u druge nije lak zadatak sam po sebi i na njega ćemo se vratiti u narednim člancima; u ovom ćemo članku pretpostaviti da nam je takav algoritam konsenzusa dostupan.

Koja svojstva koja smo gore opisali ima RANDAO? Nepredvidiv je, ima istu vitalnost kao temeljni protokol konsenzusa, ali je pristran. Naime, napadač može promatrati mrežu, a nakon što drugi sudionici otkriju svoje brojeve, može izračunati njihov XOR, te odlučiti hoće li ili ne otkriti svoj broj kako bi utjecao na ishod. Iako to sprječava napadača da sam odredi izlaz generatora slučajnih brojeva, ipak mu daje 1 bit utjecaja. A ako napadači kontroliraju nekoliko sudionika, tada će broj bitova koje kontroliraju biti jednak broju sudionika pod njihovom kontrolom.

Utjecaj napadača može se uvelike smanjiti ako se zahtijeva da sudionici otkrivaju brojeve redom. Tada će napadač moći utjecati na ishod samo ako je zadnji otvoren. Iako je utjecaj značajno manji, algoritam je i dalje pristran.

RANDAO+VDF

Jedan od načina da RANDAO bude nepristran je sljedeći: nakon što se otkriju svi brojevi i izračuna XOR, njegov se rezultat ubacuje u ulaz funkcije, za što je potrebno jako puno vremena da se izračuna, ali vam omogućuje da provjerite ispravnost izračun vrlo brzo.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Ova funkcija se zove Verifiable Delay Function ili VDF. Ako izračun konačnog rezultata traje dulje od faze otkrivanja broja, tada napadač neće moći predvidjeti učinak prikazivanja ili skrivanja svog broja, te će stoga izgubiti priliku utjecati na rezultat.

Razvijanje dobrih VDF-ova je izuzetno teško. Nedavno je bilo nekoliko otkrića, npr. ovo и ovaj, što je VDF učinilo praktičnijim u praksi, a Ethereum 2.0 dugoročno planira koristiti RANDAO s VDF-om kao izvor slučajnih brojeva. Osim činjenice da je ovaj pristup nepredvidiv i nepristran, ima dodatnu prednost jer je održiv ako su barem dva sudionika dostupna na mreži (pod pretpostavkom da je korišteni konsenzusni protokol održiv kada se radi s tako malim brojem sudionika).

Najveći izazov ovog pristupa je postavljanje VDF-a tako da čak ni sudionik s vrlo skupim specijaliziranim hardverom neće moći izračunati VDF prije kraja faze otkrivanja. U idealnom slučaju, algoritam bi čak trebao imati značajnu sigurnosnu marginu, recimo 10x. Slika ispod prikazuje napad glumca koji ima specijalizirani ASIC koji mu omogućuje pokretanje VDF-a brže od vremena dodijeljenog za otkrivanje RANDAO potvrde. Takav sudionik još uvijek može izračunati konačni rezultat koristeći ili ne koristeći svoj broj, a zatim na temelju izračuna bira hoće li ga prikazati ili ne.

Za gore spomenutu VDF obitelj, performanse namjenskog ASIC-a mogu biti 100+ puta veće od konvencionalnog hardvera. Dakle, ako faza postavljanja traje 10 sekundi, tada VDF-u izračunatom na takvom ASIC-u mora trebati više od 100 sekundi da bi imao 10x veću sigurnosnu marginu, pa stoga isti VDF izračunat na standardnom hardveru mora trajati 100x 100 sekundi = ~3 sata.

Zaklada Ethereum planira riješiti ovaj problem stvaranjem vlastitih javno dostupnih, besplatnih ASIC-ova. Kada se to dogodi, svi drugi protokoli također mogu iskoristiti ovu tehnologiju, ali do tada RANDAO+VDF pristup neće biti održiv za protokole koji ne mogu ulagati u razvoj vlastitih ASIC-ova.

Mnogi članci, videozapisi i druge informacije o VDF-u prikupljeni su na ove stranice.

Koristimo kodove za brisanje

U ovom odjeljku ćemo pogledati protokol za generiranje nasumičnog broja koji koristi brisanje kodova. Može tolerirati do ⅓ napadača dok ostaje održiv i dopušta postojanje do ⅔ napadača prije nego što mogu predvidjeti ili utjecati na ishod.

Glavna ideja protokola je sljedeća. Radi jednostavnosti, pretpostavimo da ima točno 100 sudionika. Pretpostavimo također da svi sudionici lokalno imaju neki privatni ključ, a javni ključevi svih sudionika poznati su svim sudionicima:

1. Svaki sudionik lokalno dolazi s dugačkim nizom, razbija ga na 67 dijelova, stvara kodove za brisanje kako bi dobio 100 dijeljenja tako da je bilo kojih 67 dovoljno za oporavak niza, dodjeljuje svaki od 100 dijeljenja jednom od sudionika i šifrira ih s javni ključ istog sudionika. Sve kodirane dionice se tada objavljuju.

2. Sudionici koriste neku vrstu konsenzusa kako bi postigli dogovor o kodiranim skupovima od specifičnih 67 sudionika.

3. Nakon što se postigne konsenzus, svaki sudionik uzima kodirane dionice u svakom od 67 skupova šifriranih svojim javnim ključem, dekriptira sve takve dionice i objavljuje sve takve dešifrirane dionice.

4. Nakon što 67 sudionika završi korak (3), svi dogovoreni skupovi mogu se potpuno dekodirati i rekonstruirati zbog svojstava kodova za brisanje, a konačni broj može se dobiti kao XOR početnih redaka s kojima su sudionici započeli u (1) .

Može se pokazati da je ovaj protokol nepristran i nepredvidljiv. Rezultirajući nasumični broj određuje se nakon postizanja konsenzusa, ali nikome nije poznat sve dok ⅔ sudionika ne dekodira dijelove šifrirane svojim javnim ključem. Dakle, slučajni broj je određen prije objave informacija dovoljnih za njegovu rekonstrukciju.

Što se događa ako u koraku (1) jedan od sudionika pošalje drugim sudionicima kodirane dionice koje nisu točan kod za brisanje za neki niz? Bez dodatnih promjena, različiti sudionici ili uopće neće moći oporaviti niz ili će oporaviti različite nizove, što će rezultirati time da različiti sudionici dobiju različite slučajne brojeve. Da biste to spriječili, možete učiniti sljedeće: svaki sudionik, osim kodiranih dionica, također izračunava Drvo Merkla sve takve dionice, i šalje svakom sudioniku i sam kodirani dijeljenje i korijen merkleovog stabla, te dokaz o uključivanju dijeljenja u merkleovo stablo. U konsenzusu u koraku (2), sudionici se tada ne samo slažu oko skupa skupova, već i oko skupa specifičnih korijena takvih stabala (ako je neki sudionik odstupio od protokola i poslao različite korijene merkleovog stabla različitim sudionicima, i dva takva korijena prikazana su tijekom konsenzusa, njegov redak nije uključen u skup rezultata). Kao rezultat konsenzusa, imat ćemo 67 kodiranih redaka i odgovarajuće korijene merkleovog stabla tako da postoji najmanje 67 sudionika (ne nužno istih koji su predložili odgovarajuće retke), koji za svaki od 67 redaka imaju poruka s udjelom koda za brisanje i izblijedjelim dokazom pojavljivanja njihovog udjela u odgovarajućem stablu.

Kada u koraku (4) sudionik dešifrira 67 otkucaja za određenu žicu i pokuša iz njih rekonstruirati originalnu žicu, moguća je jedna od opcija:

1. Niz se obnavlja, a ako se zatim ponovno kodira brisanjem i izračuna Merkleovo stablo za lokalno izračunate udjele, korijen se podudara s onim oko kojeg je postignut konsenzus.

2. Red je vraćen, ali lokalno izračunati korijen ne odgovara onom kod kojeg je postignut konsenzus.

3. Red nije vraćen.

Lako je pokazati da ako se opcija (1) dogodila za barem jednog sudionika iznad, tada se opcija (1) dogodila za sve sudionike, i obrnuto, ako se opcija (2) ili (3) dogodi za barem jednog sudionika, tada za sve sudionike dogodit će se opcija (2) ili (3). Dakle, za svaki red u skupu, ili će ga svi sudionici uspješno oporaviti ili ga svi sudionici neće uspjeti oporaviti. Rezultirajući nasumični broj tada je XOR samo onih redaka koje su sudionici uspjeli oporaviti.

Potpisi praga

Drugi pristup nasumičnosti je korištenje onoga što se naziva BLS potpisom praga. Generator slučajnih brojeva temeljen na potpisima praga ima potpuno ista jamstva kao gore opisani algoritam temeljen na kodu za brisanje, ali ima značajno niži asimptotski broj poruka poslanih preko mreže za svaki generirani broj.

BLS potpisi su dizajn koji omogućuje većem broju sudionika stvaranje jednog zajedničkog potpisa za poruku. Ovi se potpisi često koriste za uštedu prostora i propusnosti jer ne zahtijevaju slanje više potpisa. 

Uobičajena primjena za BLS potpise u blockchain protokolima, uz generiranje nasumičnih brojeva, je blokovno potpisivanje u BFT protokolima. Recimo da 100 sudionika kreira blokove, a blok se smatra konačnim ako ga potpiše njih 67. Svi oni mogu predati svoje dijelove BLS potpisa i upotrijebiti neki algoritam konsenzusa da se dogovore oko njih 67 i zatim ih spojiti u jedan BLS potpis. Bilo kojih 67 (ili više) dijelova može se koristiti za stvaranje konačnog potpisa, što će ovisiti o tome kojih je 67 potpisa kombinirano i stoga može varirati, iako će različiti izbori 67 sudionika stvoriti drugačiji potpis, svaki takav potpis bit će valjan potpis za blok. Preostali sudionici tada samo trebaju primiti i verificirati samo jedan potpis po bloku, umjesto 67, preko mreže, što značajno smanjuje opterećenje mreže.

Ispada da ako su privatni ključevi koje sudionici koriste generirani na određeni način, tada će bez obzira kojih 67 potpisa (ili više, ali ne manje) biti agregirano, rezultirajući potpis biti isti. Ovo se može koristiti kao izvor nasumičnosti: sudionici se prvo dogovore oko neke poruke koju će potpisati (ovo može biti rezultat RANDAO-a ili samo hash posljednjeg bloka, zapravo nije važno sve dok se mijenja svaki put i dosljedan je) i izradite BLS potpis za njega. Rezultat generiranja bit će nepredvidiv dok 67 sudionika ne ustupi svoje dijelove, a nakon toga je output već unaprijed određen i ne može ovisiti o akcijama bilo kojeg sudionika.

Ovaj pristup nasumičnosti je održiv sve dok najmanje ⅔ sudionika na mreži slijedi protokol, te je nepristran i nepredvidiv sve dok najmanje ⅓ sudionika slijedi protokol. Važno je napomenuti da napadač koji kontrolira više od ⅓, ali manje od ⅔ sudionika može zaustaviti protokol, ali ne može predvidjeti niti utjecati na njegov izlaz.

Sami potpisi pragova vrlo su zanimljiva tema. U drugom dijelu članka detaljno ćemo analizirati kako funkcioniraju i kako je točno potrebno generirati ključeve sudionika kako bi se potpisi praga mogli koristiti kao generator slučajnih brojeva.

U zaključku

Ovaj je članak prvi u nizu tehničkih članaka na blogu NEAR. NEAR je blockchain protokol i platforma za razvoj decentraliziranih aplikacija s naglaskom na jednostavnost razvoja i jednostavnost korištenja za krajnje korisnike.

Kod protokola je otvoren, naša implementacija je napisana u Rustu, može se pronaći ovdje.

Možete vidjeti kako izgleda razvoj za NEAR i eksperimentirati u mrežnom IDE-u здесь.

Sve vijesti na ruskom možete pratiti na brzojavna grupa i grupa na VKontakteu, a na engleskom u službenom cvrkut.

Vidimo se uskoro!

Izvor: www.habr.com