Uvod
"Generiranje nasumičnog broja previše je važno da bi se prepustilo slučaju."
Robert Cavue, 1970
Ovaj je članak posvećen praktičnoj primjeni rješenja koja koriste kolektivno generiranje slučajnih brojeva u nepouzdanom okruženju. Ukratko, kako i zašto se random koristi u blockchainovima, i malo o tome kako razlikovati "dobar" random od "lošeg". Generiranje istinski slučajnog broja iznimno je težak problem, čak i na jednom računalu, a kriptografi ga već dugo proučavaju. Pa, u decentraliziranim mrežama generiranje nasumičnih brojeva još je složenije i važnije.
Upravo u mrežama gdje sudionici ne vjeruju jedni drugima, sposobnost generiranja neospornog slučajnog broja omogućuje nam učinkovito rješavanje mnogih kritičnih problema i značajno poboljšanje postojećih shema. Štoviše, kockanje i lutrija ovdje nisu cilj broj jedan, kako bi se na prvi pogled neiskusnom čitatelju moglo učiniti.
Generiranje slučajnih brojeva
Računala ne mogu sama generirati nasumične brojeve; za to im je potrebna pomoć izvana. Računalo može dobiti neku slučajnu vrijednost iz, na primjer, pokreta miša, količine korištene memorije, lutajućih struja na pinovima procesora i mnogih drugih izvora koji se nazivaju entropijskim izvorima. 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 stvarno slučajne brojeve unutar zadanog raspona, na njih se primjenjuju kriptotransformacije kako bi se proizvele jednoliko raspoređene pseudoslučajne vrijednosti iz neravnomjerno raspoređenih vrijednosti izvora entropije. Rezultirajuće vrijednosti nazivaju se pseudoslučajnim jer nisu doista slučajne, već su deterministički izvedene iz entropije. Svaki dobar kriptografski algoritam, prilikom šifriranja podataka, proizvodi šifrirane tekstove koji se statistički ne bi trebali razlikovati od nasumičnog niza, tako da za proizvodnju nasumičnosti možete uzeti izvor entropije, koji osigurava samo dobru ponovljivost i nepredvidivost vrijednosti čak i u malim rasponima, ostatak posla je raspršivanje i miješanje bitova u Rezultirajuću vrijednost će preuzeti algoritam za šifriranje.
Da završim kratki edukativni program, dodati ću da je generiranje slučajnih brojeva čak i na jednom uređaju jedan od stupova osiguravanja sigurnosti naših podataka. Generirani pseudo-slučajni brojevi koriste se prilikom uspostavljanja sigurnih veza u raznim mrežama, za generiranje kriptografske ključeve, za uravnoteženje opterećenja, nadzor integriteta i za mnoge druge aplikacije. Sigurnost mnogih protokola ovisi o sposobnosti generiranja pouzdanog, izvana 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 iznimno je opasan i odmah ugrožava sav softver koji koristi generiranje slučajnosti.
Sve ovo biste trebali znati ako ste pohađali osnovni tečaj kriptografije, pa nastavimo o decentraliziranim mrežama.
Nasumično u lancima blokova
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 kvalitetna, neosporna slučajnost. Nadalje, zbog kratkoće, nazvat ću ovu tehnologiju "Javno provjerljivi nasumični svjetionici” ili PVRB. Budući da su blockchaini mreže u kojima informacije može provjeriti bilo koji sudionik, ključni dio naziva je “Javno provjerljivo”, tj. Svatko može koristiti izračune kako bi dobio dokaz da rezultirajući broj objavljen na blockchainu ima sljedeća svojstva:
- Rezultat mora imati dokazivo jednoliku distribuciju, tj. temeljiti se na dokazano jakoj kriptografiji.
- Nije moguće kontrolirati nijedan od bitova rezultata. Kao posljedica toga, ishod se ne može unaprijed predvidjeti.
- Ne možete sabotirati protokol generiranja nesudjelujući u protokolu ili preopterećivanjem mreže porukama napada
- Sve navedeno mora biti otporno na dogovaranje dopuštenog broja nepoštenih sudionika protokola (npr. 1/3 sudionika).
Svaka mogućnost da manja skupina sudionika u dosluhu proizvede čak i kontrolirani nasumični izbor par/nepar sigurnosna je rupa. Svaka sposobnost grupe da zaustavi izdavanje nasumičnih je sigurnosna rupa. Općenito, problema je mnogo, a ovaj zadatak nije nimalo lak...
Čini se da je najvažnija primjena PVRB-a razne igre, lutrije i općenito bilo koja vrsta kockanja na blockchainu. Doista, ovo je važan smjer, ali slučajnost u lancima blokova ima još važnije primjene. Pogledajmo ih.
Algoritmi konsenzusa
PVRB igra veliku ulogu u organiziranju mrežnog konsenzusa. Transakcije u lancima blokova zaštićene su elektroničkim potpisom, pa je “napad na transakciju” uvijek uključivanje/isključivanje transakcije u blok (ili više blokova). A glavni zadatak algoritma konsenzusa je dogovoriti redoslijed tih transakcija i redoslijed blokova koji uključuju te transakcije. Također, nužno svojstvo pravih blockchaina je konačnost – sposobnost mreže da se složi da je lanac do finaliziranog bloka konačan, te da nikada neće biti isključen zbog pojave novog forka. Obično je za suglasnost da je blok valjan i, što je najvažnije, konačan, potrebno prikupiti potpise većine proizvođača blokova (dalje u tekstu BP – block-producers), za što je potrebno dostaviti barem lanac blokova. svim BP-ima i distribucija potpisa između svih BP-a. Kako broj BP-ova raste, broj potrebnih poruka u mreži eksponencijalno raste, stoga algoritmi konsenzusa koji zahtijevaju konačnost, korišteni na primjer u Hyperledger pBFT konsenzusu, ne rade potrebnom brzinom, počevši od nekoliko desetaka BP-ova, zahtijevajući ogroman broj veza.
Ako u mreži postoji neosporan i pošten PVRB, tada se i u najjednostavnijoj aproksimaciji može na temelju njega izabrati jedan od proizvođača blokova i postaviti ga za “lidera” tijekom jednog kruga protokola. Ako imamo N proizvođači blokova, od kojih M: M > 1/2 N su pošteni, ne cenzuriraju transakcije i ne račvaju lanac za izvođenje napada "dvostruke potrošnje", tada će korištenje jednoliko raspodijeljenog neprikosnovenog PVRB-a omogućiti odabir poštenog vođe s vjerojatnošću M / N (M / N > 1/2). Ako se svakom vođi dodijeli vlastiti vremenski interval tijekom kojeg može proizvesti blok i potvrditi lanac, a ti su intervali jednaki u vremenu, tada će lanac blokova poštenih BP-ova biti duži od lanca koji tvore zlonamjerni BP-ovi, a konsenzus algoritam se oslanja na duljinu lanca. jednostavno će odbaciti "loš". Ovo načelo dodjele jednakih odsječaka vremena svakom BP-u prvi je put primijenjeno u Grapheneu (prethodniku EOS-a) i omogućuje zatvaranje većine blokova jednim potpisom, što uvelike smanjuje opterećenje mreže i omogućuje ovom konsenzusu da radi iznimno brzo i stalno. 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 za osiguranje konačnosti (nemogućnost da lančana vilica počne prije zadnjeg posljednjeg nepovratnog bloka).
Također, u stvarnim implementacijama, shema protokola je kompliciranija - glasanje za predložene blokove provodi se u nekoliko faza kako bi se mreža održala u slučaju blokova koji nedostaju i problema s mrežom, ali čak i uzimajući to u obzir, konsenzusni algoritmi koji koriste PVRB zahtijevaju znatno manje poruka između BP-ova, što ih čini bržima od tradicionalnog PVFT-a ili njegovih raznih modifikacija.
Najistaknutiji predstavnik takvih algoritama: iz tima Cardano, za koji se kaže da je matematički dokaziv protiv tajnih dogovora s BP-om.
U Ouroborosu, PVRB se koristi za definiranje takozvanog "BP rasporeda" - rasporeda prema kojem se svakom BP-u dodjeljuje vlastiti vremenski interval za objavljivanje bloka. Velika prednost korištenja PVRB-a je potpuna “jednakost” BP-a (prema veličini bilance). Integritet PVRB-a osigurava da zlonamjerni BP-ovi ne mogu kontrolirati raspoređivanje vremenskih odsječaka, te stoga ne mogu manipulirati lancem unaprijed pripremajući i analizirajući račve lanca, a za odabir račvanja dovoljno je jednostavno osloniti se na duljinu račvanja. lanac, bez korištenja lukavih načina za izračunavanje "korisnosti" BP-a i "težine" njegovih blokova.
Općenito, u svim slučajevima kada je potrebno odabrati slučajnog sudionika u decentraliziranoj mreži, PVRB je gotovo uvijek najbolji izbor, a ne deterministička opcija koja se temelji na, na primjer, hash-u 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 za odabir sljedećeg korumpiranog sudionika ili nekoliko odjednom kako bi osigurao veći udio u odluci. Korištenje PVRB diskreditira ove vrste napada.
Skaliranje i uravnoteženje 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 “Elektroničke srećke kao mikroplaćanja”. Opća ideja je da umjesto 100 1c uplata od platitelja primatelju, možete igrati poštenu lutriju s nagradom od 1$ = 100c, gdje platitelj daje banci jednu od 1 svojih "lutrijskih karata" za svaku 100c plaćanje. Jedna od ovih ulaznica osvaja staklenku od 1 USD, a upravo tu ulaznicu primatelj može snimiti u blockchain. Najvažnije je da se preostalih 99 karata prenosi između primatelja i uplatitelja bez vanjskog sudjelovanja, privatnim kanalom i željenom brzinom. Može se pročitati dobar opis protokola koji se temelji na ovoj shemi na mreži Emercoin .
Ova shema ima nekoliko problema, kao što je primatelj može prestati služiti uplatitelju odmah nakon primitka dobitnog listića, ali za mnoge posebne primjene, kao što je naplata po minuti ili elektroničke pretplate na usluge, oni se mogu zanemariti. Glavni je zahtjev, naravno, integritet lutrije, a za njezinu provedbu PVRB je apsolutno neophodan.
Izbor nasumičnog sudionika također je iznimno važan za protokole dijeljenja, čija je svrha horizontalno skaliranje lanca blokova, dopuštajući različitim BP-ovima da obrađuju samo svoj opseg transakcija. Ovo je iznimno težak zadatak, posebice u smislu sigurnosti prilikom spajanja shardova. Pravedan odabir slučajnog BP-a u svrhu dodjele odgovornih za određeni shard, kao u konsenzusnim algoritmima, također je zadatak PVRB-a. U centraliziranim sustavima, shardove dodjeljuje balanser; on jednostavno izračunava hash iz zahtjeva i šalje ga traženom izvršitelju. U lancima blokova, mogućnost utjecaja na ovu dodjelu može dovesti do napada na konsenzus. Na primjer, napadač može kontrolirati sadržaj transakcija, može kontrolirati koje transakcije idu na shard 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, čije će rješenje 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
Ulogu nasumičnih brojeva u industriji igara teško je precijeniti. Eksplicitna upotreba u online kockarnicama i implicitna upotreba pri izračunavanju učinaka igračeve radnje iznimno su teški problemi za decentralizirane mreže, gdje se ne može osloniti na središnji izvor slučajnosti. Ali nasumični odabir također može riješiti mnoge ekonomske probleme i pomoći u izgradnji jednostavnijih i učinkovitijih protokola. Pretpostavimo da u našem protokolu postoje sporovi oko plaćanja za neke jeftine usluge, a ti se sporovi događaju vrlo rijetko. U tom slučaju, ako postoji neosporan PVRB, kupci i prodavači mogu se dogovoriti da će sporove rješavati nasumično, ali s određenom vjerojatnošću. Na primjer, s vjerojatnošću od 60% pobjeđuje klijent, a s vjerojatnošću od 40% prodavatelj. Ovakav pristup, koji je iz prve perspektive apsurdan, omogućuje automatsko rješavanje sporova s točno predvidljivim udjelom dobitaka/gubitaka, što odgovara objema stranama, bez sudjelovanja treće strane i nepotrebnog gubljenja vremena. Štoviše, omjer vjerojatnosti može biti dinamičan i ovisiti o nekim globalnim varijablama. Na primjer, ako poduzeće dobro posluje, ima mali broj sporova i visoku profitabilnost, poduzeće može automatski prebaciti vjerojatnost 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 promijeniti vjerojatnost u drugom smjeru.
Velik broj zanimljivih decentraliziranih protokola, kao što su tokenski kurirani registri, tržišta predviđanja, krivulje povezivanja 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 zbog kojih su zaštite međusobno sukobljene. Ono što je zaštićeno od napada "kitova" s milijardama tokena ("veliki ulog") ranjivo je na napade tisuća računa s malim saldom ("ulog u sibilu") i mjerama poduzetim protiv jednog napada, kao što su ne- linearne naknade stvorene da rad s velikim udjelom učine neprofitabilnim obično se diskreditiraju drugim napadom. Budući da je riječ o ekonomskoj igri, odgovarajuće statističke težine moguće je izračunati unaprijed, a provizije jednostavno zamijeniti randomiziranim s odgovarajućom raspodjelom. Takve probabilističke provizije provode se krajnje jednostavno ako blockchain ima pouzdan izvor slučajnosti i ne zahtijevaju nikakve složene izračune, što otežava život i kitovima i sibilama.
U isto vrijeme, potrebno je nastaviti zapamtiti da vam kontrola nad jednim bitom u ovoj slučajnosti omogućuje varanje, smanjujući i povećavajući vjerojatnosti za pola, tako da je pošteni PVRB najvažnija komponenta takvih protokola.
Gdje pronaći pravi random?
U teoriji, pravičan nasumični odabir u decentraliziranim mrežama čini gotovo svaki protokol dokazano sigurnim od tajnih dogovora. Obrazloženje je prilično jednostavno - ako se mreža složi oko jednog bita 0 ili 1, a manje od polovice sudionika je nepošteno, tada je, uz dovoljan broj ponavljanja, zajamčeno da će mreža postići konsenzus o tom bitu s fiksnom vjerojatnošću. Jednostavno zato što će pošteni nasumični odabir izabrati 51 od 100 sudionika u 51% slučajeva. Ali to je u teoriji, jer... u stvarnim mrežama, da bi se osigurala takva razina sigurnosti kao u člancima, potrebno je mnogo poruka između hostova, složena višeprolazna kriptografija, a svako kompliciranje protokola odmah dodaje nove vektore napada.
Zato još ne vidimo dokazano otporan PVRB u blockchainovima, koji bi se koristio dovoljno vremena da se testira stvarnim aplikacijama, višestrukim revizijama, učitavanjima i naravno pravim napadima, bez kojih je teško nazvati proizvod uistinu siguran.
Ipak, postoji nekoliko pristupa koji obećavaju, razlikuju se u mnogim detaljima, a jedan od njih će sigurno riješiti problem. S modernim računalnim resursima, kriptografska teorija može se vrlo pametno prevesti u praktične primjene. U budućnosti ćemo rado razgovarati o PVRB implementacijama: sada ih ima nekoliko, svaka ima svoj skup važnih svojstava i značajki implementacije, a iza svake stoji dobra ideja. Nema puno timova uključenih u randomizaciju, a iskustvo svakog od njih iznimno je važno za sve ostale. Nadamo se da će naše informacije omogućiti drugim timovima da se kreću brže, uzimajući u obzir iskustvo svojih prethodnika.
Izvor: www.habr.com