Je li moguće generirati nasumične brojeve ako ne vjerujemo jedni drugima? Dio 1

Hej Habr!

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

Zašto bi bilo potrebno generirati nasumične brojeve među učesnicima koji ne vjeruju jedni drugima? Jedno područje primjene su decentralizirane aplikacije. Na primjer, aplikacija koja prihvati opkladu od učesnika i ili udvostruči iznos sa vjerovatnoćom od 49% ili oduzme s vjerovatnoćom od 51%, radit će samo ako može nepristrasno primiti nasumični broj. Ako napadač može utjecati na ishod generatora slučajnih brojeva, pa čak i malo povećati svoje šanse da dobije isplatu u aplikaciji, lako će ga uništiti.

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

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

2. Mora da je nepredvidiv. Drugim rečima, nijedan učesnik ne bi trebalo da bude u stanju da predvidi koji će broj biti generisan (ili zaključiti bilo koje od njegovih svojstava) pre nego što bude generisan.

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

U ovom članku ćemo pogledati dva pristupa: RANDAO + VDF i pristup kodovima za brisanje. U sljedećem dijelu ćemo detaljno ispitati pristup baziran na graničnim potpisima.

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

RANDAO

RANDAO je vrlo jednostavan i stoga prilično često korišten pristup generiranju slučajnosti. Svi učesnici mreže prvo lokalno biraju pseudoslučajni broj, a zatim svaki učesnik šalje heš odabranog broja. Zatim, učesnici naizmjence otkrivaju svoje odabrane brojeve i izvode operaciju XOR na otkrivenim brojevima, a rezultat ove operacije postaje rezultat protokola.

Korak objavljivanja heševa prije otkrivanja brojeva je neophodan kako napadač ne bi mogao izabrati svoj broj nakon što je vidio brojeve ostalih učesnika. To bi mu omogućilo da praktično samostalno odredi izlaz generatora slučajnih brojeva.

U toku protokola, učesnici treba dva puta da donesu zajedničku odluku (tzv. konsenzus): kada da počnu da otkrivaju odabrane brojeve, a samim tim i da prestanu da prihvataju hešove, i kada da prestanu da prihvataju odabrane brojeve i izračunavaju rezultirajući slučajni rezultat. broj. Donošenje ovakvih odluka između učesnika koji nemaju povjerenja jedni u druge nije samo po sebi lak zadatak i tome ćemo se vratiti u narednim člancima; u ovom članku ćemo pretpostaviti da nam je takav algoritam konsenzusa dostupan.

Koje od svojstava koje smo opisali iznad ima RANDAO? Nepredvidiv je, ima istu vitalnost kao i osnovni protokol konsenzusa, ali je pristrasan. Konkretno, napadač može promatrati mrežu, a nakon što drugi učesnici otkriju svoje brojeve, može izračunati njihov XOR i odlučiti hoće li otkriti svoj broj kako bi utjecao na ishod. Iako ovo sprečava napadača da sam odredi izlaz generatora slučajnih brojeva, to mu i dalje 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 znatno smanjiti zahtjevom da učesnici otkrivaju brojeve po redu. Tada će napadač moći da utiče na ishod samo ako se otvori poslednji. Iako je uticaj znatno manji, algoritam je i dalje pristrasan.

RANDAO+VDF

Jedan od načina da RANDAO učinite nepristranim je sljedeći: nakon što se otkriju svi brojevi i izračuna se XOR, njegov rezultat se unosi u ulaz funkcije, za koju je potrebno mnogo vremena za izračunavanje, ali vam omogućava da provjerite ispravnost proračun veoma 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čunavanje konačnog rezultata potraje duže od faze otkrivanja broja, tada napadač neće moći predvidjeti učinak prikazivanja ili skrivanja svog broja, te će stoga izgubiti priliku da utiče na rezultat.

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

Najveći izazov ovog pristupa je postavljanje VDF-a tako da čak i učesnik sa veoma skupim specijalizovanim hardverom neće moći da izračuna VDF pre kraja faze otkrivanja. U idealnom slučaju, algoritam bi čak trebao imati značajnu sigurnosnu marginu, recimo 10x. Slika ispod prikazuje napad od strane glumca koji ima specijalizovani ASIC koji mu omogućava da pokrene VDF brže od vremena dodeljenog za otkrivanje RANDAO potvrde. Takav učesnik i dalje može izračunati konačni rezultat koristeći ili ne koristeći svoj broj, a zatim na osnovu proračuna izabrati hoće li ga prikazati ili ne.

Za VDF porodicu pomenutu gore, performanse namenskog ASIC-a mogu biti 100+ puta veće od konvencionalnog hardvera. Dakle, ako faza implementacije traje 10 sekundi, tada VDF-u izračunatom na takvom ASIC-u mora biti potrebno više od 100 sekundi da bi imao 10x sigurnosnu marginu, i stoga istom VDF-u izračunatom na robnom hardveru mora biti potrebno 100x 100 sekundi = ~3 sata.

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

Sakupljeni su mnogi članci, video zapisi i druge informacije o VDF-u ovu stranicu.

Koristimo kodove za brisanje

U ovom odeljku ćemo pogledati protokol generisanja slučajnih brojeva koji koristi brisanje kodova. Može tolerirati do ⅓ napadača dok ostaje održiv i omogućava postojanje do ⅔ napadača prije nego što mogu predvidjeti ili utjecati na ishod.

Osnovna ideja protokola je sljedeća. Radi jednostavnosti, pretpostavimo da ima tačno 100 učesnika. Pretpostavimo i da svi učesnici lokalno imaju neki privatni ključ, a javni ključevi svih učesnika su poznati svim učesnicima:

1. Svaki učesnik lokalno dolazi do dugačkog niza, razbija ga na 67 dijelova, kreira kodove za brisanje kako bi dobio 100 dijeljenja tako da je bilo kojih 67 dovoljno za oporavak niza, dodjeljuje svaki od 100 dionica jednom od sudionika i šifrira ih sa javni ključ istog učesnika. Zatim se objavljuju svi kodirani dionici.

2. Učesnici koriste neku vrstu konsenzusa kako bi postigli dogovor o kodiranim skupovima od konkretnih 67 učesnika.

3. Kada se postigne konsenzus, svaki učesnik uzima kodirane dionice u svakom od 67 skupova šifriranih njihovim javnim ključem, dešifruje sve takve dionice i objavljuje sve takve dešifrirane dionice.

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

Može se pokazati da je ovaj protokol nepristrasan i nepredvidiv. Rezultirajući nasumični broj se određuje nakon postizanja konsenzusa, ali nikome nije poznat sve dok ⅔ učesnika ne dekodira dijelove šifrirane njihovim javnim ključem. Dakle, slučajni broj se određuje prije nego što se objave informacije dovoljne za njegovu rekonstrukciju.

Šta se dešava ako u koraku (1) jedan od učesnika pošalje kodirane deljenje drugim učesnicima koji nisu ispravni kod za brisanje za neki niz? Bez dodatnih izmjena, različiti učesnici ili uopće neće moći oporaviti niz, ili će oporaviti različite nizove, što će rezultirati da različiti učesnici dobiju različite nasumične brojeve. Da biste to spriječili, možete učiniti sljedeće: svaki učesnik, osim kodiranih udjela, također izračunava Merkla drvo sve takve dionice, i šalje svakom sudioniku i sam kodirani dio i korijen merkle stabla, kao i dokaz o uključivanju udjela u merkle stablu. U konsenzusu u koraku (2), učesnici se tada ne slažu samo oko skupa skupova, već i oko skupa specifičnih korijena takvih stabala (ako je neki učesnik odstupio od protokola i poslao različite korijene merkle stabala različitim učesnicima, i dva takva korijena su prikazana tokom konsenzusa, njegov red nije uključen u skup rezultata). Kao rezultat konsenzusa, imaćemo 67 kodiranih linija i odgovarajuće korijene merkle stabla tako da ima najmanje 67 učesnika (ne nužno istih onih koji su predložili odgovarajuće linije), koji za svaki od 67 redova imaju poruka sa udjelom koda za brisanje i dokazom da je njihov udio u odgovarajućem stablu izblijedio.

Kada u koraku (4) učesnik dešifruje 67 taktova za određeni niz i pokuša iz njih rekonstruisati originalni niz, moguća je jedna od opcija:

1. Niz se vraća, a ako se zatim ponovo kodira brisanjem, a Merkle stablo se izračuna za lokalno izračunate udjele, korijen se poklapa s onim o kojem je postignut konsenzus.

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

3. Red nije vraćen.

Lako je pokazati da ako se opcija (1) desila za najmanje jednog učesnika iznad, onda se opcija (1) dogodila za sve učesnike, i obrnuto, ako se opcija (2) ili (3) dogodila za najmanje jednog učesnika, tada za sve učesnike će se desiti opcija (2) ili (3). Dakle, za svaki red u skupu, ili će ga svi učesnici uspješno oporaviti, ili ga svi učesnici neće uspjeti oporaviti. Rezultirajući slučajni broj je tada XOR samo za redove koje su učesnici uspjeli oporaviti.

Potpisi praga

Drugi pristup slučajnosti je korištenje onoga što se zove BLS granični potpisi. Generator slučajnih brojeva zasnovan na potpisima praga ima potpuno iste garancije kao algoritam baziran na kodu za brisanje gore opisan, ali ima znatno manji asimptotski broj poruka koje se šalju preko mreže za svaki generisani broj.

BLS potpisi su dizajn koji omogućava više učesnika da kreiraju jedan zajednički potpis za poruku. Ovi se potpisi često koriste za uštedu prostora i propusnog opsega tako što ne zahtijevaju slanje više potpisa. 

Uobičajena aplikacija za BLS potpise u blockchain protokolima, pored generiranja slučajnih brojeva, je i potpisivanje blokova u BFT protokolima. Recimo da 100 učesnika kreira blokove, a blok se smatra konačnim ako ga 67 potpiše. Svi oni mogu predati svoje dijelove BLS potpisa i koristiti neki konsenzus algoritam da se dogovore oko njih 67, a zatim ih spoje u jedan BLS potpis. Bilo kojih 67 (ili više) dijelova može se koristiti za kreiranje konačnog potpisa, što će ovisiti o tome kojih 67 potpisa je kombinirano i stoga može varirati, iako će različiti izbori 67 učesnika stvoriti drugačiji potpis, svaki takav potpis će biti važeći potpis za blok. Preostali učesnici tada trebaju primiti i verifikovati samo jedan potpis po bloku, umjesto 67, preko mreže, što značajno smanjuje opterećenje mreže.

Ispada da ako se privatni ključevi koje sudionici koriste generiraju na određeni način, onda bez obzira na to kojih 67 potpisa (ili više, ali ne manje) će biti agregirano, rezultirajući potpis će biti isti. Ovo se može koristiti kao izvor slučajnosti: učesnici se prvo dogovore oko neke poruke koju će potpisati (ovo može biti izlaz RANDAO-a ili samo hash posljednjeg bloka, nije bitno sve dok se mijenja svaki put i konzistentan je) i kreirajte BLS potpis za njega. Rezultat generacije će biti nepredvidiv sve dok 67 učesnika ne obezbedi svoje delove, a nakon toga je izlaz već unapred određen i ne može zavisiti od akcija bilo kog učesnika.

Ovaj pristup slučajnosti je održiv sve dok najmanje ⅔ učesnika na mreži i prate protokol, i nepristrasan je i nepredvidiv sve dok najmanje ⅓ učesnika prati protokol. Važno je napomenuti da napadač koji kontroliše više od ⅓ ali manje od ⅔ učesnika može zaustaviti protokol, ali ne može predvidjeti niti utjecati na njegov izlaz.

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

U zaključku

Ovaj članak je prvi u nizu tehničkih članaka na blogu U BLIZINI. 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 online IDE-u ovdje.

Sve vijesti na ruskom možete pratiti na telegram grupa i unutra grupa na VKontakteu, i na engleskom u službenom twitter.

Do skoryh vstreč!

izvor: www.habr.com