Predstavitev
"Generacija naključnih števil je preveč pomembna, da bi jo prepustili naključju."
Robert Cavue, 1970
Ta članek je posvečen praktični uporabi rešitev z uporabo kolektivnega generiranja naključnih števil v nezaupljivem okolju. Na kratko, kako in zakaj se naključno uporablja v verigah blokov in nekaj o tem, kako ločiti »dobro« naključno od »slabega«. Generiranje resnično naključnega števila je izjemno težaven problem, tudi na enem samem računalniku, in že dolgo ga proučujejo kriptografi. No, v decentraliziranih omrežjih je generiranje naključnih števil še bolj zapleteno in pomembno.
Prav v omrežjih, kjer udeleženci drug drugemu ne zaupajo, nam zmožnost generiranja neizpodbitnega naključnega števila omogoča učinkovito reševanje številnih kritičnih problemov in bistveno izboljšanje obstoječih shem. Še več, igre na srečo in loterije tukaj niso cilj številka ena, kot se na prvi pogled zdi neizkušenemu bralcu.
Generiranje naključnih števil
Računalniki ne morejo sami ustvariti naključnih števil; za to potrebujejo zunanjo pomoč. Računalnik lahko pridobi nekaj naključnih vrednosti na primer iz premikov miške, količine uporabljenega pomnilnika, potepuških tokov na nožicah procesorja in številnih drugih virov, imenovanih viri entropije. Te vrednosti same po sebi niso povsem naključne, saj so v določenem območju ali pa imajo predvidljiv vzorec sprememb. Da bi taka števila spremenili v resnično naključno število znotraj danega obsega, se zanje uporabijo kriptotransformacije, da se proizvedejo enakomerno porazdeljene psevdonaključne vrednosti iz neenakomerno porazdeljenih vrednosti vira entropije. Dobljene vrednosti se imenujejo psevdonaključne, ker niso resnično naključne, ampak so deterministično izpeljane iz entropije. Vsak dober kriptografski algoritem pri šifriranju podatkov proizvede šifrirana besedila, ki bi morala biti statistično nerazločljiva od naključnega zaporedja, zato lahko za ustvarjanje naključnosti vzamete vir entropije, ki zagotavlja le dobro ponovljivost in nepredvidljivost vrednosti tudi v majhnih razponih, ostalo delo je razprševanje in mešanje bitov v. Dobljeno vrednost bo prevzel algoritem za šifriranje.
Za zaključek kratkega izobraževalnega programa naj dodam, da je generiranje naključnih števil tudi na eni napravi eden od stebrov zagotavljanja varnosti naših podatkov.Gerirana psevdonaključna števila se uporabljajo pri vzpostavljanju varnih povezav v različnih omrežjih, za generiranje kriptografske ključe, za uravnoteženje obremenitve, nadzor celovitosti in za številne druge aplikacije. Varnost številnih protokolov je odvisna od zmožnosti generiranja zanesljivega, zunanje nepredvidljivega naključja, njegovega shranjevanja in ne razkritja do naslednjega koraka protokola, sicer bo varnost ogrožena. Napad na generator psevdonaključnih vrednosti je izjemno nevaren in takoj ogrozi vso programsko opremo, ki uporablja generiranje naključnosti.
Vse to bi morali vedeti, če ste opravili osnovni tečaj kriptografije, zato nadaljujmo z decentraliziranimi omrežji.
Naključno v verigah blokov
Najprej bom govoril o blockchainih s podporo za pametne pogodbe, saj so ti tisti, ki lahko v celoti izkoristijo priložnosti, ki jih ponuja kakovostna, nesporna naključnost. Nadalje, zaradi kratkosti, bom to tehnologijo imenoval "Javno preverljivi naključni svetilniki« ali PVRB. Ker so verige blokov omrežja, v katerih lahko podatke preveri vsak udeleženec, je ključni del imena »Javno preverljivo«, tj. Vsakdo lahko uporabi izračune, da pridobi dokaz, da ima dobljeno število, objavljeno v verigi blokov, naslednje lastnosti:
- Rezultat mora imeti dokazljivo enakomerno porazdelitev, tj. temeljiti mora na dokazljivo močni kriptografiji.
- Ni mogoče nadzorovati nobenega bita rezultata. Posledično izida ni mogoče vnaprej predvideti.
- Generacijskega protokola ne morete sabotirati tako, da ne sodelujete pri protokolu ali da preobremenite omrežje z napadalnimi sporočili
- Vse našteto mora biti odporno na dogovarjanje dovoljenega števila nepoštenih udeležencev protokola (npr. 1/3 udeležencev).
Vsaka možnost, da bi manjša skupina udeležencev v dogovarjanju izdelala celo nadzorovano naključno sodo/liho, je varnostna luknja. Vsaka zmožnost skupine, da ustavi izdajanje naključnih podatkov, je varnostna luknja. Na splošno je težav veliko in ta naloga ni lahka ...
Zdi se, da so najpomembnejša aplikacija za PVRB različne igre, loterije in na splošno vse vrste iger na srečo na blockchainu. To je res pomembna usmeritev, vendar ima naključnost v verigah blokov še pomembnejše aplikacije. Poglejmo jih.
Algoritmi soglasja
PVRB ima veliko vlogo pri organiziranju omrežnega soglasja. Transakcije v verigah blokov so zaščitene z elektronskim podpisom, zato je »napad na transakcijo« vedno vključitev/izključitev transakcije v blok (ali več blokov). In glavna naloga konsenznega algoritma je, da se dogovori o vrstnem redu teh transakcij in vrstnem redu blokov, ki te transakcije vključujejo. Prav tako je nujna lastnost pravih verig blokov dokončnost – zmožnost omrežja, da se strinja, da je veriga do finaliziranega bloka dokončna in ne bo nikoli izključena zaradi pojava novega forka. Običajno je za soglasje, da je blok veljaven in kar je najpomembneje dokončen, potrebno zbrati podpise večine proizvajalcev blokov (v nadaljevanju BP – block-producers), kar zahteva vsaj dostavo verige blokov. vsem BP in razdeljevanje podpisov med vse BP. Ko število BP raste, število potrebnih sporočil v omrežju eksponentno raste, zato konsenzni algoritmi, ki zahtevajo dokončnost, ki se uporabljajo na primer v soglasju Hyperledger pBFT, ne delujejo z zahtevano hitrostjo, začenši z več deset BP, ki zahtevajo ogromno povezav.
Če v omrežju obstaja nesporen in pošten PVRB, potem lahko tudi v najpreprostejšem približku na njegovi podlagi izberemo enega izmed proizvajalcev blokov in ga postavimo za “vodjo” v enem krogu protokola. Če imamo N proizvajalci blokov, od katerih M: M > 1/2 N so pošteni, ne cenzurirajo transakcij in ne razcepijo verige, da bi izvedli napad "dvojne porabe", potem bo uporaba enakomerno porazdeljenega nespornega PVRB omogočila izbiro poštenega vodje z verjetnostjo M / N (M / N > 1/2). Če je vsakemu vodji dodeljen svoj časovni interval, v katerem lahko izdela blok in potrdi verigo, in so ti intervali časovno enaki, bo veriga blokov poštenih BP daljša od verige, ki jo tvorijo zlonamerni BP, in konsenz algoritem se opira na dolžino verige. bo preprosto zavrgel »slabo«. To načelo dodeljevanja enakih delov časa vsakemu BP je bilo prvič uporabljeno v Graphene (predhodnik EOS) in omogoča, da se večina blokov zapre z enim samim podpisom, kar močno zmanjša obremenitev omrežja in omogoča, da to soglasje deluje izjemno hitro in enakomerno. Vendar pa mora omrežje EOS sedaj uporabljati posebne bloke (Last Irreversible Block), ki so potrjeni s podpisi 2/3 BP. Ti bloki zagotavljajo dokončnost (nezmožnost, da bi se verižne vilice začele pred zadnjim zadnjim nepovratnim blokom).
Tudi v resničnih izvedbah je shema protokola bolj zapletena - glasovanje za predlagane bloke poteka v več fazah, da se ohrani omrežje v primeru manjkajočih blokov in težav z omrežjem, vendar tudi ob upoštevanju tega algoritmi soglasja, ki uporabljajo PVRB, zahtevajo znatno manj sporočil med BP, kar omogoča, da so hitrejši od tradicionalnega PVFT ali njegovih različnih modifikacij.
Najvidnejši predstavnik takih algoritmov: iz ekipe Cardano, ki naj bi bil matematično dokazljiv proti tajnemu dogovarjanju BP.
V Ouroborosu se PVRB uporablja za definiranje tako imenovanega "urnika BP" - urnika, po katerem je vsakemu BP dodeljen svoj časovni okvir za objavo bloka. Velika prednost uporabe PVRB je popolna "enakost" BP (glede na velikost njihovih bilanc). Celovitost PVRB zagotavlja, da zlonamerni BP ne morejo nadzorovati razporejanja časovnih rež in zato ne morejo manipulirati verige s pripravo in analizo razcepov verige vnaprej, za izbiro razcepa pa je dovolj, da se preprosto zanesete na dolžino razcepa. verige, brez uporabe zapletenih načinov za izračun "uporabnosti" BP in "teže" njegovih blokov.
Na splošno je v vseh primerih, ko je treba izbrati naključnega udeleženca v decentraliziranem omrežju, PVRB skoraj vedno najboljša izbira, namesto deterministične možnosti, ki temelji na, na primer, zgoščenem bloku. Brez PVRB zmožnost vplivanja na izbiro udeleženca vodi do napadov, v katerih lahko napadalec izbira med več prihodnostmi, da izbere naslednjega pokvarjenega udeleženca ali več hkrati, da zagotovi večji delež pri odločitvi. Uporaba PVRB diskreditira tovrstne napade.
Skaliranje in uravnoteženje obremenitve
PVRB je lahko zelo koristen tudi pri nalogah, kot sta zmanjšanje obremenitve in skaliranje plačil. Za začetek se je smiselno seznaniti Rivesta »Elektronske loterijske srečke kot mikroplačila«. Splošna ideja je, da lahko namesto 100 plačil 1c od plačnika prejemniku igrate pošteno loterijo z nagrado 1$ = 100c, kjer plačnik banki da eno od 1 svojih "loterijskih srečk" za vsako 100c plačilo. Ena od teh vstopnic osvoji kozarec v vrednosti 1 USD in to vstopnico lahko prejemnik zabeleži v verigi blokov. Najpomembneje je, da se preostalih 99 vstopnic prenaša med prejemnikom in plačnikom brez zunanjega sodelovanja, po zasebnem kanalu in s poljubno želeno hitrostjo. Dober opis protokola, ki temelji na tej shemi v omrežju Emercoin, je mogoče prebrati .
Ta shema ima nekaj težav, na primer prejemnik lahko preneha služiti plačniku takoj po prejemu zmagovalnega listka, toda za številne posebne aplikacije, kot je zaračunavanje na minuto ali elektronske naročnine na storitve, jih je mogoče zanemariti. Glavna zahteva je seveda poštenost loterije, za njeno izvedbo pa je PVRB nujno potreben.
Izbira naključnega udeleženca je izjemno pomembna tudi za protokole shardinga, katerih namen je horizontalno prilagajanje verige blokov, kar omogoča različnim BP, da obdelujejo le svoj obseg transakcij. To je izjemno težka naloga, zlasti glede varnostnih vprašanj pri združevanju drobcev. Pravična izbira naključnega BP za namene dodelitve odgovornih za določen shard, kot pri konsenznih algoritmih, je tudi naloga PVRB. V centraliziranih sistemih razdelke dodeli balanser; preprosto izračuna zgoščeno vrednost iz zahteve in jo pošlje zahtevanemu izvajalcu. V verigah blokov lahko zmožnost vplivanja na to dodelitev povzroči napad na soglasje. Vsebino transakcij lahko na primer nadzoruje napadalec, lahko nadzoruje, katere transakcije gredo v delček, ki ga nadzoruje, in manipulira z verigo blokov v njem. Preberete lahko razpravo o problemu uporabe naključnih števil za naloge razdeljevanja v Ethereum
Sharding je eden najbolj ambicioznih in resnih problemov na področju blockchaina, njegova rešitev bo omogočila gradnjo decentraliziranih omrežij fantastične zmogljivosti in obsega. PVRB je le eden od pomembnih blokov za njegovo rešitev.
Igre, ekonomski protokoli, arbitraža
Vlogo naključnih števil v igričarski industriji je težko preceniti. Eksplicitna uporaba v spletnih igralnicah in implicitna uporaba pri izračunu učinkov igralčevega dejanja sta izjemno težavni težavi za decentralizirana omrežja, kjer se ni mogoče zanesti na osrednji vir naključnosti. Toda naključna izbira lahko reši tudi številne ekonomske težave in pomaga zgraditi preprostejše in učinkovitejše protokole. Recimo, da v našem protokolu obstajajo spori glede plačila za nekatere poceni storitve in ti spori se pojavljajo zelo redko. V tem primeru, če obstaja nesporen PVRB, se lahko kupci in prodajalci dogovorijo za naključno reševanje sporov, vendar z določeno verjetnostjo. Na primer, s 60% verjetnostjo zmaga stranka, s 40% verjetnostjo pa prodajalec. Ta na prvi pogled nesmiselni pristop omogoča avtomatsko reševanje sporov z natančno predvidljivim deležem zmag/izgub, ki ustreza obema stranema brez sodelovanja tretje osebe in nepotrebnega izgubljanja časa. Poleg tega je razmerje verjetnosti lahko dinamično in odvisno od nekaterih globalnih spremenljivk. Na primer, če podjetje dobro posluje, ima nizko število sporov in visoko dobičkonosnost, lahko podjetje samodejno preusmeri verjetnost rešitve spora v smeri osredotočenosti na stranko, na primer 70/30 ali 80/20, in obratno, če spori vzamejo veliko denarja in so goljufivi ali neustrezni, lahko verjetnost premaknete v drugo smer.
Veliko število zanimivih decentraliziranih protokolov, kot so žetoni, kurirani registri, napovedni trgi, krivulje vezave in mnogi drugi, so ekonomske igre, v katerih je dobro vedenje nagrajeno in slabo vedenje kaznovano. Pogosto vsebujejo varnostne težave, zaradi katerih so zaščite med seboj v nasprotju. Tisto, kar je zaščiteno pred napadom »kitov« z milijardami žetonov (»veliki vložek«), je ranljivo za napade tisočih računov z majhnim stanjem (»vložek sybil«) in ukrepi, sprejetimi proti enemu napadu, kot je ne- linearne pristojbine, ustvarjene za nedonosno delo z velikim deležem, so običajno diskreditirane z drugim napadom. Ker govorimo o ekonomski igri, lahko ustrezne statistične uteži izračunamo vnaprej, provizije pa enostavno nadomestimo z randomiziranimi z ustrezno porazdelitvijo. Takšne verjetnostne provizije se izvajajo izjemno preprosto, če ima blockchain zanesljiv vir naključnosti in ne zahtevajo nobenih zapletenih izračunov, ki otežujejo življenje tako kitom kot sibilam.
Hkrati je treba še naprej zapomniti, da vam nadzor nad enim bitom v tej naključnosti omogoča goljufanje, zmanjšanje in povečanje verjetnosti za polovico, zato je pošten PVRB najpomembnejša komponenta takšnih protokolov.
Kje najti pravi random?
V teoriji poštena naključna izbira v decentraliziranih omrežjih naredi skoraj vsak protokol dokazano varen pred tajnim dogovorom. Utemeljitev je povsem preprosta – če se omrežje strinja glede enega samega bita 0 ali 1 in je manj kot polovica udeležencev nepoštenih, potem je ob zadostnem številu iteracij zagotovljeno, da bo omrežje doseglo soglasje o tem bitu s fiksno verjetnostjo. Preprosto zato, ker bo pošten naključni izbor izbral 51 izmed 100 udeležencev v 51% primerov. Ampak to je v teoriji, ker... v resničnih omrežjih je za zagotovitev takšne stopnje varnosti, kot je v člankih, potrebnih veliko sporočil med gostitelji, zapletena večprehodna kriptografija, vsak zaplet protokola pa takoj doda nove vektorje napadov.
Zato v verigah blokov še ne vidimo dokazano odpornega PVRB, ki bi bil dovolj časa uporabljen za testiranje realnih aplikacij, večkratnih revizij, obremenitev in seveda pravih napadov, brez katerih težko rečemo izdelek resnično varen.
Obetavnih pa je več pristopov, ki se razlikujejo v mnogih podrobnostih in eden od njih bo zagotovo rešil problem. S sodobnimi računalniškimi viri je mogoče kriptografsko teorijo precej spretno prevesti v praktične aplikacije. V prihodnje bomo z veseljem govorili o implementacijah PVRB: zdaj jih je več, vsaka ima svoj nabor pomembnih lastnosti in implementacijskih funkcij, za vsako pa stoji dobra ideja. Ekip, ki sodelujejo pri randomizaciji, ni veliko, izkušnje vsake od njih pa so za vse ostale izjemno pomembne. Upamo, da bodo naše informacije drugim ekipam omogočile hitrejše premikanje ob upoštevanju izkušenj njihovih predhodnikov.
Vir: www.habr.com