Uvod
“Generacija slučajnih brojeva je previše važna da bi se prepustila slučaju.”
Robert Cavue, 1970
Ovaj članak je posvećen praktičnoj primjeni rješenja korištenjem kolektivnog generiranja slučajnih brojeva u nepouzdanom okruženju. Ukratko, kako i zašto se random koristi u blockchains-u, i malo o tome kako razlikovati “dobro” nasumično od “lošeg”. Generisanje zaista slučajnog broja je izuzetno težak problem, čak i na jednom računaru, i kriptografi su ga dugo proučavali. Pa, u decentraliziranim mrežama, generiranje slučajnih brojeva je još složenije i važnije.
Upravo u mrežama u kojima učesnici nemaju povjerenja jedni u druge, sposobnost generiranja neospornog slučajnog broja nam omogućava da efikasno riješimo mnoge kritične probleme i značajno poboljšamo postojeće šeme. Štaviše, kockanje i lutrija ovdje nisu cilj broj jedan, kako se neiskusnom čitatelju na prvi pogled može učiniti.
Generisanje slučajnih brojeva
Računari ne mogu sami generirati nasumične brojeve; za to im je potrebna pomoć izvana. Računar može dobiti neku nasumične vrijednosti iz, na primjer, pokreta miša, količine korišćene memorije, zalutalih struja na pinovima procesora i mnogih drugih izvora koji se nazivaju izvori entropije. Ove vrijednosti same po sebi nisu potpuno slučajne, jer su u određenom rasponu ili imaju predvidljiv obrazac promjena. Da bi se takvi brojevi pretvorili u istinski slučajni broj unutar određenog raspona, na njih se primjenjuju kriptotransformacije kako bi se proizvele ravnomjerno raspoređene pseudoslučajne vrijednosti iz neravnomjerno raspoređenih vrijednosti izvora entropije. Rezultirajuće vrijednosti nazivaju se pseudoslučajnim jer nisu istinski slučajne, već su deterministički izvedene iz entropije. Svaki dobar kriptografski algoritam, prilikom šifriranja podataka, proizvodi šifrirane tekstove koji bi se trebali statistički ne razlikovati od slučajnog niza, tako da za proizvodnju slučajnosti možete uzeti izvor entropije, koji pruža samo dobru ponovljivost i nepredvidljivost vrijednosti čak i u malim rasponima, Ostatak posla je raspršivanje i miješanje bitova u Rezultirajuću vrijednost će preuzeti algoritam šifriranja.
Da zaokružim kratak edukativni program, dodaću da je generiranje slučajnih brojeva čak i na jednom uređaju jedan od stubova osiguranja sigurnosti naših podataka.Generisani pseudoslučajni brojevi se koriste prilikom uspostavljanja sigurnih veza u različitim mrežama, za generiranje kriptografski ključevi, za balansiranje opterećenja, praćenje integriteta i za mnoge druge aplikacije. Sigurnost mnogih protokola ovisi o sposobnosti generiranja pouzdanog, eksterno nepredvidivog slučajnog odabira, pohranjivanja i ne otkrivanja do sljedećeg koraka protokola, inače će sigurnost biti ugrožena. Napad na generator pseudoslučajnih vrijednosti je izuzetno opasan i odmah prijeti svim softverima koji koriste generiranje slučajnosti.
Sve ovo biste trebali znati ako ste pohađali osnovni kurs kriptografije, pa hajde da nastavimo s decentraliziranim mrežama.
Slučajno u blockchains-u
Prije svega, govorit ću o blockchainima s podrškom za pametne ugovore; oni su ti koji mogu u potpunosti iskoristiti mogućnosti koje pruža visokokvalitetna, neosporna slučajnost. Dalje, radi sažetosti, nazvat ću ovu tehnologiju "Javno provjerljivi nasumični signali” ili PVRB. Budući da su blockchains mreže u kojima bilo koji učesnik može provjeriti informacije, ključni dio naziva je “Publicly Verifiable”, tj. Svako može koristiti izračune da dobije dokaz da rezultirajući broj objavljen na blockchainu ima sljedeća svojstva:
- Rezultat mora imati dokazivo ujednačenu distribuciju, tj. biti zasnovan na dokazivo jakoj kriptografiji.
- Nije moguće kontrolisati bilo koji od bitova rezultata. Kao posljedica toga, ishod se ne može unaprijed predvidjeti.
- Ne možete sabotirati generacijski protokol tako što ne učestvujete u protokolu ili preopteretiti mrežu porukama napada
- Sve navedeno mora biti otporno na dogovaranje dozvoljenog broja nepoštenih učesnika u protokolu (npr. 1/3 učesnika).
Svaka mogućnost da manja grupa učesnika u dosluhu proizvede čak i kontrolisane paran/neparan slučajni slučaj je sigurnosna rupa. Svaka sposobnost grupe da zaustavi izdavanje nasumice predstavlja sigurnosnu rupu. Generalno, problema je mnogo, a ovaj zadatak nije lak...
Čini se da su najvažnija aplikacija za PVRB razne igre, lutrije i općenito bilo koje vrste kockanja na blockchainu. Zaista, ovo je važan smjer, ali slučajnost u blockchainima ima još važnije primjene. Pogledajmo ih.
Algoritmi konsenzusa
PVRB igra veliku ulogu u organizaciji mrežnog konsenzusa. Transakcije u blockchain-u su zaštićene elektronskim potpisom, tako da je “napad na transakciju” uvijek uključivanje/isključivanje transakcije u blok (ili nekoliko blokova). A glavni zadatak algoritma konsenzusa je da se dogovori oko redosleda ovih transakcija i redosleda blokova koji uključuju ove transakcije. Također, neophodno svojstvo za stvarne blockchaine je konačnost - sposobnost mreže da se složi da je lanac do finaliziranog bloka konačan i nikada neće biti isključen zbog pojave nove viljuške. Obično, da bi se dogovorili da je blok validan i, što je najvažnije, konačan, potrebno je prikupiti potpise većine proizvođača blokova (u daljem tekstu BP - block-producers), što zahtijeva barem isporuku lanca blokova. svim BP, i distribucija potpisa između svih BP. Kako broj BP raste, broj potrebnih poruka u mreži raste eksponencijalno, stoga algoritmi konsenzusa koji zahtijevaju konačnost, koji se koriste na primjer u Hyperledger pBFT konsenzusu, ne rade potrebnom brzinom, počevši od nekoliko desetina BP, što zahtijeva ogroman broj veza.
Ako u mreži postoji neosporan i pošten PVRB, onda se, čak iu najjednostavnijoj aproksimaciji, na osnovu njega može izabrati jedan od proizvođača blokova i imenovati ga za „lidera“ tokom jedne runde protokola. Ako imamo N proizvođači blokova, od kojih M: M > 1/2 N su pošteni, ne cenzurišu transakcije i ne račvajte lanac kako biste izvršili napad „dvostruke potrošnje“, tada će korištenje ravnomjerno raspoređenog neospornog PVRB-a omogućiti odabir poštenog vođe s vjerovatnoćom M / N (M / N > 1/2). Ako se svakom vođi dodijeli vlastiti vremenski interval tokom kojeg može proizvesti blok i potvrditi lanac, a ti intervali su vremenski jednaki, tada će blok lanac poštenih BP biti duži od lanca koji formiraju zlonamjerni BP, a konsenzus algoritam se oslanja na dužinu lanca, jednostavno će odbaciti onaj "loš". Ovaj princip dodjeljivanja jednakih dijelova vremena svakom BP-u prvi je put primijenjen u Graphene-u (prethodniku EOS-a) i omogućava da se većina blokova zatvori jednim potpisom, što uvelike smanjuje opterećenje mreže i omogućava da ovaj konsenzus radi izuzetno brzo i postojano. Međutim, EOS mreža sada mora koristiti posebne blokove (Last Irreversible Block), koji su potvrđeni potpisima 2/3 BP. Ovi blokovi služe da se osigura konačnost (nemogućnost da lančana viljuška počne prije posljednjeg posljednjeg nepovratnog bloka).
Također, u stvarnim implementacijama, shema protokola je složenija - glasanje za predložene blokove provodi se u nekoliko faza kako bi se mreža održala u slučaju nedostajućih blokova i problema s mrežom, ali čak i uzimajući to u obzir, algoritmi konsenzusa koji koriste PVRB zahtijevaju znatno manje poruka između BP-a, što ih čini bržim od tradicionalnog PVFT-a ili njegovih različitih modifikacija.
Najistaknutiji predstavnik ovakvih algoritama: iz Cardano tima, za koji se kaže da je matematički dokaziv protiv BP dosluha.
U Ouroborosu, PVRB se koristi za definiranje takozvanog “BP rasporeda” - rasporeda prema kojem se svakom BP-u dodjeljuje svoj vremenski slot za objavljivanje bloka. Velika prednost korištenja PVRB-a je potpuna „jednakost“ BP-a (prema veličini njihovih bilansa). Integritet PVRB-a osigurava da zlonamjerni BP-ovi ne mogu kontrolirati raspoređivanje vremenskih slotova, te stoga ne mogu manipulirati lancem pripremajući i analizirajući viljuške lanca unaprijed, a za odabir viljuške dovoljno je jednostavno se osloniti na dužinu lanca. lanca, bez upotrebe lukavih načina za izračunavanje „korisnosti“ BP-a i „težine“ njegovih blokova.
Općenito, u svim slučajevima u kojima se u decentraliziranoj mreži treba odabrati slučajni sudionik, PVRB je gotovo uvijek najbolji izbor, a ne deterministička opcija zasnovana na, na primjer, heš bloka. Bez PVRB-a, mogućnost utjecaja na izbor sudionika dovodi do napada u kojima napadač može birati između više budućnosti kako bi izabrao sljedećeg korumpiranog učesnika ili nekoliko odjednom kako bi osigurao veći udio u odluci. Upotreba PVRB-a diskredituje ove vrste napada.
Skaliranje i balansiranje opterećenja
PVRB također može biti od velike koristi u zadacima kao što su smanjenje opterećenja i skaliranje plaćanja. Za početak, ima smisla upoznati se Rivesta “Ulaznice za elektronske lutrije kao mikro plaćanja”. Opšta ideja je da umjesto plaćanja od 100 1c od uplatitelja primatelju, možete igrati poštenu lutriju sa nagradom od 1$ = 100c, gdje uplatitelj daje banci jednu od 1 svojih "lutrijskih listića" za svaku 100c plaćanje. Jedna od ovih tiketa osvaja teglu od 1 USD, i to je taj tiket koji primalac može snimiti u blockchain. Najvažnije je da se preostalih 99 tiketa prenosi između primaoca i platitelja bez ikakvog vanjskog učešća, privatnim kanalom i željenom brzinom. Dobar opis protokola zasnovanog na ovoj šemi na Emercoin mreži se može pročitati .
Ova šema ima nekoliko problema, kao što je primatelj može prestati usluživati uplatitelja odmah nakon što primi dobitnu kartu, ali za mnoge posebne aplikacije, kao što je naplata po minuti ili elektronička pretplata na usluge, oni se mogu zanemariti. Glavni uslov je, naravno, pravičnost lutrije, a za njeno sprovođenje je PVRB apsolutno neophodan.
Izbor slučajnog učesnika je takođe izuzetno važan za protokole za dijeljenje, čija je svrha da horizontalno skaliraju lanac blokova, omogućavajući različitim BP-ima da obrađuju samo svoj obim transakcija. Ovo je izuzetno težak zadatak, posebno u smislu sigurnosti prilikom spajanja krhotina. Pravedan odabir nasumične BP u svrhu dodjele odgovornih za određeni dio, kao u konsenzus algoritmima, također je zadatak PVRB-a. U centralizovanim sistemima, šardove dodeljuje balanser; on jednostavno izračunava heš iz zahteva i šalje ga potrebnom izvršiocu. U blockchains-u, mogućnost utjecaja na ovaj zadatak može dovesti do napada na konsenzus. Na primjer, sadržaj transakcija može kontrolirati napadač, on može kontrolirati koje transakcije idu na dio koji kontrolira i manipulirati lancem blokova u njemu. Možete pročitati raspravu o problemu korištenja nasumičnih brojeva za zadatke dijeljenja u Ethereumu
Sharding je jedan od najambicioznijih i najozbiljnijih problema u području blockchaina; njegovo rješenje će omogućiti izgradnju decentraliziranih mreža fantastičnih performansi i volumena. PVRB je samo jedan od važnih blokova za njegovo rješavanje.
Igre, ekonomski protokoli, arbitraža
Uloga nasumičnih brojeva u industriji igara teško je precijeniti. Eksplicitna upotreba u onlajn kockarnicama i implicitna upotreba pri izračunavanju efekata igračevih akcija su izuzetno teški problemi za decentralizovane mreže, gde se ne može osloniti na centralni izvor slučajnosti. Ali slučajni odabir također može riješiti mnoge ekonomske probleme i pomoći u izgradnji jednostavnijih i efikasnijih protokola. Pretpostavimo da u našem protokolu postoje sporovi oko plaćanja nekih jeftinih usluga, a ti se sporovi javljaju prilično rijetko. U ovom slučaju, ako postoji neosporan PVRB, kupci i prodavci mogu se dogovoriti da će sporove rješavati nasumično, ali sa određenom vjerovatnoćom. Na primjer, sa vjerovatnoćom od 60% pobjeđuje klijent, a sa vjerovatnoćom od 40% pobjeđuje prodavac. Ovakav pristup, koji je s prve tačke gledišta apsurdan, omogućava vam da automatski rješavate sporove sa tačno predvidljivim udjelom pobjeda/gubitaka, što odgovara objema stranama bez ikakvog učešća treće strane i nepotrebnog gubljenja vremena. Štaviše, omjer vjerovatnoće može biti dinamičan i ovisiti o nekim globalnim varijablama. Na primjer, ako kompanija dobro posluje, ima mali broj sporova i visoku profitabilnost, kompanija može automatski pomjeriti vjerovatnoću rješavanja spora prema klijentu, na primjer 70/30 ili 80/20, i obrnuto, ako sporovi oduzimaju mnogo novca i lažni su ili neadekvatni, možete pomjeriti vjerovatnoću u drugom smjeru.
Veliki broj interesantnih decentralizovanih protokola, kao što su registri sa token-kursom, tržišta predviđanja, krive vezivanja i mnogi drugi, ekonomske su igre u kojima se dobro ponašanje nagrađuje, a loše ponašanje kažnjava. Često sadrže sigurnosne probleme za koje se zaštite međusobno sukobljavaju. Ono što je zaštićeno od napada "kitova" sa milijardama tokena ("veliki ulog") ranjivo je na napade hiljada računa sa malim salovima ("sibil ulog") i merama koje se preduzimaju protiv jednog napada, kao što je ne- linearne naknade stvorene kako bi rad s velikim udjelom bio neprofitabilan obično se diskredituju drugim napadom. Budući da je riječ o ekonomskoj igri, odgovarajuće statističke težine se mogu izračunati unaprijed i jednostavno zamijeniti provizije nasumično odabranim sa odgovarajućom raspodjelom. Takve probabilističke provizije se implementiraju izuzetno jednostavno ako blockchain ima pouzdan izvor nasumice i ne zahtijeva nikakve složene proračune, što otežava život i kitovima i sibilama.
Istovremeno, potrebno je i dalje zapamtiti da vam kontrola nad jednim bitom u ovoj nasumičnosti omogućava varanje, smanjujući i povećavajući vjerovatnoću za polovicu, tako da je pošten PVRB najvažnija komponenta takvih protokola.
Gdje pronaći pravi random?
U teoriji, pravičan slučajni odabir u decentraliziranim mrežama čini gotovo svaki protokol dokazano sigurnim od dosluha. Obrazloženje je prilično jednostavno - ako se mreža složi oko jednog bita 0 ili 1, a manje od polovine učesnika je nepošteno, tada će, s obzirom na dovoljno iteracija, mreža zajamčeno postići konsenzus o tom bitu sa fiksnom vjerovatnoćom. Jednostavno zato što će pošteni slučajni odabir izabrati 51 od 100 učesnika 51% vremena. Ali to je u teoriji, jer... u stvarnim mrežama, da bi se osigurao takav nivo sigurnosti kao u člancima, potrebne su mnoge poruke između hostova, složena višeprolazna kriptografija, a svaka komplikacija protokola odmah dodaje nove vektore napada.
Zato još ne vidimo dokazano otporan PVRB u blockchain-ovima, koji bi se koristio dovoljno vremena da ga testiraju stvarne aplikacije, višestruke revizije, opterećenja i naravno, stvarni napadi, bez kojih je teško nazvati proizvod zaista siguran.
Međutim, postoji nekoliko pristupa koji obećavaju, oni se razlikuju u mnogim detaljima, a jedan od njih će definitivno riješiti problem. Sa savremenim računarskim resursima, kriptografska teorija se može prilično pametno prevesti u praktične primene. U budućnosti ćemo rado razgovarati o PVRB implementacijama: sada ih ima nekoliko, svaka ima svoj skup važnih svojstava i karakteristika implementacije, a iza svake stoji dobra ideja. Nema mnogo timova uključenih u randomizaciju, a iskustvo svakog od njih je izuzetno važno za sve ostale. Nadamo se da će naše informacije omogućiti i drugim timovima da se kreću brže, uzimajući u obzir iskustva svojih prethodnika.
izvor: www.habr.com