Juhuslikud numbrid ja detsentraliseeritud võrgud: praktiline rakendus.

Sissejuhatus

„Juhuslike numbrite genereerimine on liiga tähtis, et seda juhuse hooleks jätta“
Robert Kavju, 1970

See artikkel käsitleb kollektiivsete juhuslike numbrite genereerimise lahenduste praktilist rakendamist usaldamatutes keskkondades. Lihtsalt öeldes — kuidas ja miks kasutatakse juhuslikkust plokiahelates ning natuke ka sellest, kuidas eristada „head“ juhuslikkust „halvast“. Tõeliselt juhusliku numbri genereerimine on isegi eraldi arvutis äärmiselt keeruline probleem, mis on juba pikka aega olnud krüptograafide uurimistöö objekt. Ja jaotatud võrkudes on juhuslike numbrite genereerimine veelgi keerulisem ja tähtsam.

Just sellistes võrkudes, kus osalised ei usalda üksteist, võimalus genereerida vaieldamatult juhuslik number aitab tõhusalt lahendada mitmeid olulisi ülesandeid ja oluliselt täiustada juba olemasolevaid skeeme. Tegelikult ei ole hasartmängud ja loteriid siin sugugi esikohal, nagu alguses võib kogenematule lugejale tunduda.

Juhuslike numbrite genereerimine

Arvutid ei oska ise genereerida juhuslikke numbreid, selle jaoks vajavad nad väliseid abi. Arvuti võib saada mõne juhusliku väärtuse näiteks hiire liikumise, kasutatud mälu hulga, protsessori kontaktidel esinevate parasiitide voolude ja paljude teiste allikate kaudu, mida nimetatakse entropia allikateks. Need väärtused pole päris juhuslikud, kuna nad asuvad kindlas vahemikus või muutuvad ennustatult. Et muuta sellised numbrid tõeliselt juhuslikeks numbriteks antud vahemikus, kasutatakse krüptopreparerimisi, et saada ebaühtlaselt jaotatud entropia allikast ühtlaselt jaotatud pseudojuhuslikke väärtusi. Saadud väärtusi nimetatakse pseudojuhuslikeks, kuna nad ei ole tõeliselt juhuslikud, vaid deterministlikult genereeritud entropiast. Iga hea krüptoalgoritm, andmeid krüpteerides toodab šifritekste, mis statistiliselt ei tohiks erineda juhuslikust järjestusest, nii et juhuslikkuse tootmiseks võib kasutada entropia allikat, mis tagab vaid head kordumatust ja ennustamatust väärtustes isegi väikestes vahemikes, ülejäänud töö bittide hajutamise ja segamise osas tuleks algoritmil.

Lõpetamaks lühikese koolituse, lisan, et juhuslike numbrite genereerimine isegi ühel seadmel on üks meie andmete turvalisuse alustalasid, genereeritud pseudojuhuslikke numbreid kasutatakse turvaliste ühenduste loomisel erinevates võrkudes, krüptograafiliste võtmete genereerimisel, koormuse tasakaalustamisel, terviklikkuse kontrollimisel ja veel paljude rakenduste puhul. Paljude protokollide turvalisus sõltub võimest genereerida usaldusväärne, väljastpoolt ennustamatud juhuslikkus, seda salvestada ja mitte paljastada järgmise protokolli sammu jooksul, vastasel juhul on turvalisus ohus. Rünnak pseudojuhuslike väärtuste generaatori vastu on äärmiselt ohtlik ja ohustab korraga kogu tarkvara, mis kasutab juhuslike numbrite genereerimist.

Kõike seda peaksite teadma, kui olete läbinud krüptograafia baaskursuse, seetõttu jätkame detsentraliseeritud võrkude teemaga.

Juhus blockchainides

Esiteks räägin plokiahelatest, mis toetavad nutilepinguid, kuna just nemad saavad täielikult ära kasutada kvaliteetse ja vaieldamatu juhuse võimalusi. Edaspidi nimetan seda tehnoloogiat “Avalikult kontrollitavad juhuslikud signaalid” või PVRB. Kuna plokiahelad on võrgud, mille teavet saavad kontrollida kõik osalejad, on nime olulisim osa “Avalikult kontrollitavad”, s.t. igaühel on võimalus läbi arvutuste tõestada, et plokiahelas avaldatud number omab järgmisi omadusi:

• Tulemus peab olema tõestatud ühtlaselt jaotunud, s.t. põhinev tõestatud krüptograafial.
• Mitte ühtegi tulemust bitist ei saa kontrollida. Seetõttu ei saa tulemust ette ennustada.
• Protokolli genereerimist ei saa saboteerida, osalemat protokollis või koormates võrku ründavate sõnumitega.
• Kõik ülalnimetatud peab olema vastupidav lubatud arvu ebaausate protokolli osalejate (näiteks 1/3 osalejat) koostööle.

Iga võimalus kokku saanud alamhulga osalejatel genereerida isegi kontrollitav paaris/üksuslik juhus — turvaauk. Iga võimalus rühmal peatada juhuse genereerimise — turvaauk. Ühesõnaga, probleeme on palju ja see ülesanne pole kerge...

Tundub, et PVRB kõige olulisem rakendus on erinevad mängud, loteriid ja üldiselt kõik mänguasi plokiahelas. Tõepoolest, see on oluline suund, kuid juhusel plokiahelates on ka tähtsamaid rakendusi. Vaatame neid.

Konsensuse algoritmid

PVRB organisatsiooni võrgukonsensuse jaoks mängib tohutut rolli. Tehingud plokiahelates on kaitstud digitaalse allkirjaga, seetõttu on "rünnak tehingu vastu" alati tehingu lisamine/riismine plokki (või mitmesse plokki). Peamine ülesanne konsensuse algoritmil on kokku leppida, kuidas need tehingud ja plokid, mis sisaldavad neid tehinguid, järjekorda seada. Samuti on tõeliselt toimivate plokiahelate vajalik omadus lõppus — võime, et võrk lepiks kokku, et ahel kuni lõppplokini on lõplik ja ei saa kunagi välistada uue jagunemise tõttu. Tüüpiliselt, et kokku leppida, et plokk on kehtiv ja, mis kõige olulisem, lõplik, on vaja koguda allkirjad enamuselt plokki tootjatelt (edaspidi BP — block-producers), mis nõuab vähemalt plokkide ahela edastamist kõigile BP-dele ja allkirjade levitamist kõigi BP-de vahel. BP-de arvu suurenedes kasvab vajalike sõnumite arv võrku eksponentsiaalselt, seetõttu konsensuse algoritmid, mis nõuavad lõplikkust, nagu näiteks pBFT konsensus Hyperledgeris, ei tööta vajaliku kiirusena, alustades juba mõnest kümnest BP-st, nõudes tohutult palju ühendusi.

Kui võrgus on vaieldamatu ja aus PVRB, siis isegi kõige lihtsamas lähenemises saame selle põhjal valida ühe block produceridest ja nimetada ta "liidriks" ühe protokolli vooru ajaks. Kui meil on N block producer-it, kellest M: M > 1/2 N on ausad, ei tsenseeri tehinguid ja ei loo ahela jagunemisi, et korraldada "double spend" rünnakut, siis ühtlaselt jaotatud vaieldamatu PVRB kasutamine võimaldab valida ausa liidri tõenäosusega M / N (M / N > 1/2). Kui iga liidri jaoks määrata oma ajavahemik, mille jooksul ta saab ploki luua ja ahelat valideerida, ja need ajavahemikud on ühesugused, siis on ausate BP plokke ahel pikem kui pahatahtlike BP loodud ahel ning konsensusalgoritm, mis toetub ahela pikkusele, lihtsalt kõrvaldab "halva". See võrdselt ajakvante igale BP andmise põhimõte rakendati esmakordselt Graphenes (EOS-i eelkäijas) ning võimaldab enamus plokkidest sulgeda ühe allkirjaga, mis vähendab oluliselt võrgu koormust ja võimaldab sellel konsensusel töötada äärmiselt kiiresti ja stabiilselt. Siiski peab EOS-i võrk praegu kasutama spetsiaalseid plokke (Viimane Kinnitatud Plokk), mida kinnitatakse 2/3 BP allkirjadega. Need plokid tagavad lõplikkuse (keti haru tekkimise võimatuse, mis algab enne viimast Viimast Kinnitatud Plokki).

Reaalsetes rakendustes on protokolli skeem keerulisem — pakutud plokkide hääletused toimuvad mitmes etapis, et toetada võrgu tööd plokkide vahelejätmise ja võrgu probleemide korral, kuid isegi sellega arvestades nõuavad PVRB kasutavad konsensusalgoritmid oluliselt vähem sõnumeid BP vahel, mis muudab need kiiremateks kui traditsiooniline PВFT või erinevad selle variandid.

Selliste algoritmide kõige silmatorkavam esindaja: Ouroboros Cardano meeskonnalt, mis, nagu on kuulutatud, omab matemaatiliselt tõestatud vastupidavust BP-de vahelisele salajasele kokkuleppele.

Ouroboroses kasutatakse PVRB-d nii-öelda "BP ajakava" määramiseks — ajakava, mille kohaselt määratakse igale BP oma ajavahemik ploki avaldamiseks. PVRB kasutamise suur eelis on BP täielik "võrdsus" (vastavalt nende bilansside suurusele). PVRB ausus tagab, et pahatahtlikud BP-d ei saa ajakava ajavahemike üle kontrolli omada ja seetõttu ei saa nad ahelat manipuleerida, valmistades ette ja analüüsides ahela haru, ning haru valimiseks piisab lihtsalt ahela pikkusele toetumisest, ilma et peaks kasutama keerukaid meetodeid BP "kasutegurite" ja tema plokkide "kaalu" arvutamiseks.

Üldiselt, kui detsentraliseeritud võrgustikus tuleb valida juhuslik osaleja, on peaaegu alati parem valik PVRB, mitte deterministlik variant, mis põhineb näiteks ploki hash'il. Ilma PVRB-ta võimalus mõjutada osaleja valikut viib rünnakuteni, kus ründaja saab valides mitmest tulevikuvõimalusest valida järgmise korruptsiooniga seotud osaleja või isegi mitu, et tagada suurem osakaal otsuste tegemises. PVRB kasutamine diskrediteerib neid rünnakutüüpe.

Skaleerimine ja koormuse tasakaalustus

PVRB võib tuua tõsiseid eeliseid ka koormuse vähendamise ja maksete skaleerimise ülesannetes. Esiteks on mõistlik tutvuda artikkel Rivesta "Electronic Lottery Tickets as Micropayments". Üldine sisu on see, et selle asemel, et teha 100 makset 1 senti, saab mängida õiglast loterii, mille auhind on 1 dollar = 100 senti, kus maksja iga 1 sendi eest annab pangale ühe oma 100-st "loterii piletist". Üks nendest piletitest võidab pangale 1 dollar, ja just seda piletit saaja saab plokkides fikseerida. Kõige olulisem on see, et ülejäänud 99 piletit edastatakse saaja ja maksja vahel ilma igasuguse välise sekkumiseta, privaatses kanalis ja vajalikul kiirusel. Selle skeemi põhjaliku protokolli kirjeldust Emercoin'i võrgustikus võib lugeda siin.

Sellel skeemil on mitu probleem, näiteks võib saaja kohe pärast võidupileti saamist lõpetada maksja teenindamise, kuid paljude eriliste rakenduste, nagu minutipõhine tasustamine või teenuste elektroonilised tellimused, korral võib neid probleeme ignoreerida. Peamine nõue on loomulikult korraliku loterii ausus, ja selle läbiviimiseks on täiesti vajalik PVRB.

Juhusliku osaleja valimine on äärmiselt oluline ka šardimise protokollide jaoks, mis on suunatud plokiahela horisontaalsele skaleerimisele, võimaldades erinevatel BP-del töödelda ainult oma tehingute ulatust. See on äärmiselt keeruline ülesanne, eriti turvalisuse küsimustes šardide ühendamisel. Aus juhuslik BP valimine konkreetse šardi nimetamiseks, nagu ka konsensuse algoritmides — on samuti PVRB ülesanne. Keskhaldusstruktuurides määrab šardid tasakaalustaja, kes lihtsalt arvutab päringu järgi hash'i ja saadab selle vajalikele täitmisportfellidele. Plokiahelates võib selle määramise mõjutamine viia konsensuse ründamiseni. Näiteks võivad tehingute sisule mõju avaldada ründajad, kes saavad kontrollida, millised tehingud satuvad nende kontrollitavasse šardisse, ja manipuleerida sealset plokiahelat. Šardimiseks juhuslike numbrite kasutamise probleemi arutelu Ethereumis on saadaval. siin
Šardimine on üks ambitsioonikamaid ja tõsisemaid ülesandeid plokiahela valdkonnas, mille lahendamine võimaldab luua suurepärase jõudluse ja mahuga detsentraliseeritud võrke. PVRB on vaid üks tähtsamaid komponente selle ülesande lahendamiseks.

Mängud, majandusprotokollid, arbitraaž

Juhuslike numbrite roll mängutööstuses on keeruline üle hinnata. Selge kasutamine online-kasiinodes ja varjatud kasutamine mängija tegevuse efektide hindamisel — need on kõik äärmiselt keerulised probleemid detsentraliseeritud võrkudes, kus ei ole võimalik tugineda kesksele juhuslikkusele. Kuid juhusliku valiku rakendamine võib lahendada ka paljusid majandusprobleeme ja aidata luua lihtsamaid ja tõhusamaid protokolle. Oletame, et meie protokollis on vaidlused odavate teenuste tasumise osas, ja need vaidlused esinevad piisavalt harva. Sellisel juhul, kui on vaieldamatu PVRB, saavad kliendid ja müüjad kokku leppida juhuslikus vaidluste lahendamises, kuid kindla tõenäosusega. Näiteks 60% tõenäosusega võidab klient ja 40% tõenäosusega müüja. See, esmapilgul absurdne, lähenemine võimaldab vaidlusi automaatselt lahendada, pakkudes täpselt prognoositavat võitude/kaotuste suhet, mis sobib mõlemale poolele ilma kolmanda osapoole sekkumiseta ja tarbetu aja raiskamiseta. Veelgi enam, tõenäosuste suhe võib olla dünaamiline ja sõltuda teatud globaalsetest muutujatest. Näiteks, kui ettevõtte asjad lähevad hästi, tuvastatakse madal vaidluste arv ja kõrge tulusus, võib ettevõte automaatselt suunata vaidluste lahendamise tõenäosuse kliendikesksemaks, näiteks 70/30 või 80/20, ja vastupidi, kui vaidlused nõuavad palju vahendeid ja on petturlikud või ebamugavad, saab tõenäosust suunata teisele poole.

Suur hulk huvitavaid detsentraliseeritud protokolle, nagu token currated registries, prediction markets, bonding curves ja paljud teised, esindavad majandusmänge, kus hea käitumine on auhinnatud ja halb käitumine karistatud. Neil esinevad sageli turvaprobleemid, mille kaitse vastandub üksteisele. See, mis on kaitstud "kitse" rünnaku eest, kellel on miljardite tokenite "suur osalus", on haavatav tuhandete väikeste saldosega kontode "sybil osaluse" rünnaku ees, ning meetmed, mida tehakse ühe rünnaku vastu, näiteks mitte-lineaarsed tasud, mis on loodud selleks, et muuta suure osaluse töö ebaefektiivseks, diskrediteeritakse tavaliselt teise rünnaku poolt. Kuna tegemist on majandusmänguga, saab vastavad statistilised kaalukesed eelnevalt arvutada ja lihtsalt asendada tasud juhuslike vastava jaotusega. Sellised tõenäosuslikud tasud on väga lihtsad rakendada, kui plokiahelas on usaldusväärne juhuslikkuse allikas, ja need ei vaja keerulisi arvutusi, keerates elu keeruliseks nii kitle kui ka sybile.
Samas tuleb alati meeles pidada, et kontroll ühe bitiga selles juhuslikkuses võimaldab petta, vähendades ja suurendades tõenäosusi kahekordselt, seega on aus PVRB selliste protokollide jaoks äärmiselt oluline.

Kust leida õiget juhuslikkust?

Teoorias võimaldab aus juhuslik valik detsentraliseeritud võrkudes tagada peaaegu iga protokolli tõestatud turvalisuse vandenõu eest. Põhjendus on üsna lihtne — kui võrk leppib kokku ühes bitis 0 või 1, ning osalejate seas on vähem kui pooled ebaausad, siis piisava iteratsioonide arvu korral jõuab võrk garanteeritult konsensusele selle bitiga kindla tõenäosusega. Lihtsalt sellepärast, et aus juhuslik valik valib 51 100 osalejast 51% juhtudest. Kuid see on teoorias, kuna reaalsetes võrkudes sellise turvalisuse taseme saavutamiseks, nagu artiklites, on vajalik palju sõnumeid hostide vahel, keeruline mitmejärguline krüptograafia ja iga protokolli keerustamine toob kohe juurde uusi rünnakute vektoreid.
Seetõttu ei näe me seni blockchainides usaldusväärset PVRB-d, mida oleks piisavalt kaua kasutatud, et läbida tõeliste rakendustega, mitmete audititega, koormustestidega ja loomulikult ka tõeliste rünnakutega seotud katsed, ilma milleta on raske rääkida tõeliselt turvalisest tootest.

Küll aga on mitmeid perspektiivseid lähenemisviise, mis erinevad mitmete detailide poolest, ja üks neist kindlasti lahendab probleemi. Tänapäeva arvutusressursside tasemel suudab krüptograafia teooria oskuslikult muutuda praktilisteks rakendusteks. Edaspidi räägime hea meelega PVRB rakendustest: neid on mitu, igal neist on oma oluline omaduste ja rakenduse eripära kogum, ning igaühe taga on hea idee. Vähe meeskondi tegeleb juhuslikkusega ja igaühe kogemus on äärmiselt oluline kõigi teiste jaoks. Loodame, et meie teave aitab teistel meeskondadel kiiremini edasi liikuda, arvestades eelnevat kogemust.

Allikas: habr.com