Juhuslikud numbrid ja detsentraliseeritud võrgud: praktiline rakendus

Sissejuhatus

„Juhuslike numbrite genereerimine on liiga oluline, et jätta see juhuse hooleks“
Robert Cavyu, 1970

See artikkel käsitleb praktilisi lahendusi, mis kasutavad kollektiivset juhuslike numbrite genereerimist usaldamatutes keskkondades. Lühidalt öeldes — kuidas ja miks kasutatakse juhuslikkust plokiahelates, ja veidi ka sellest, kuidas eristada ‘head’ juhuslikkust ‘halvast’. Tõeliselt juhusliku numbri genereerimine on isegi ühel arvutil äärmiselt keeruline probleem ning seda on pikka aega uurinud krüptograafid. Kuid detsentraliseeritud võrkudes on juhuslike numbrite genereerimine veelgi raskem ja olulisem.

Eriti nendes võrkudes, kus osalised ei usalda üksteist, võimalus genereerida vaidlustamatult juhuslik number võimaldab tõhusalt lahendada mitmeid väga olulisi ülesandeid ja oluliselt parandada juba olemasolevaid skeeme. Tõsi, hasartmängud ja loteriid ei ole siin kaugeltki number üks eesmärk, nagu alguses võib tunduda kogenematule lugejale.

Juhuslike numbrite genereerimine

Arvutid ei suuda ise genereerida juhuslikke arve, selleks on neil vaja välist abi. Arvuti saab juhuslikku väärtust näiteks hiire liikumise, kasutatud mälu hulga, protsessori kontaktidel esinevate parasiitpingete ja paljude teiste allikate kaudu, mida nimetatakse entropia allikateks. Need väärtused ei ole täiesti juhuslikud, kuna nad jäävad teatud vahemikku või neil on ettearvatav muudatused. Et muuta sellised numbrid tõeliselt juhuslikuks numbriks määratud vahemikus, rakendatakse neile krüptoparametreid, et saada ebavõrdselt jaotatud entropia allika väärtustest ühtlaselt jaotatud psöüd juhuslikke väärtusi. Saadud väärtusi nimetatakse psöüd juhuslikeks, kuna need ei ole tõeliselt juhuslikud, vaid deterministlikult toodetud entropiast. Iga hea krüptoalgreitm, andmeid krüpteerides, toodab šifritekste, mis statistiliselt peavad olema eristatavad juhuslikust järjestusest, nii et juhuslikkuse tootmiseks võib kasutada entropia allikat, mis tagab head kordumatust ja väärtuste ettearvamatust isegi väikestes vahemikes, ülejäänud osa bitite hajutamise ja segamise töö eest hoolitseb krüpteerimise algoritm.

Lõpetuseks tahan öelda, et juhuslike numbrite genereerimine isegi ühel seadmel on üks meie andmete turvalisuse aluseid. Generaatoris loodud pseudojuhuslikud numbrid on vajalikud turvaliste ühenduste loomisel erinevates võrkudes, krüptograafiliste võtmete genereerimisel, koormuse tasakaalustamisel, terviklikkuse kontrollimisel ja paljus muus. Paljude protokollide turvalisus sõltub võimest luua usaldusväärne ja väljastpoolt ennustamatu juhuslikkus, hoida seda saladuses ning mitte avaldada enne protokolli järgmist sammu, muidu on turvalisus ohus. Rünnak pseudojuhuslike väärtuste generaatorile on äärmiselt ohtlik ja seab ohtu kogu tarkvara, mis kasutab juhuslike numbrite genereerimist.

Kogu see teave on vajalik, kui olete läbinud põhikursuse krüptograafias, seega jätkame detsentraliseeritud võrkude teemaga.

Juhusus plokiahelates

Esiteks räägin ma nutilepingute toetavate plokiahelate kohta, just nemad saavad täielikult kasutada kvaliteetseid, vaieldamatult juhuslikke võimalusi. Edasi, lühiduse huvides, nimetan ma seda tehnoloogiat “Avalikult Kontrollitavad Juhuslikud Signaalid” või PVRB. Kuna plokiahelad on võrgud, mille teavet saavad kontrollida kõik osalised, on nime peamine osa “Avalikult Kontrollitavad”, st iga soovija saab arvutuste abil tõestada, et plokiahelas talletatud number omab järgmisi omadusi:

• Tulemus peab olema tõestatult ühtlaselt jaotatud, st põhineda tõestatult tugevatel krüptograafiatel.
• Ükski tulemusbit ei saa olla kontrollitav. Seetõttu ei saa tulemust eelnevalt ennustada.
• Protokolli genereerimist ei saa saboteerida, osaledes protokollis või koormates võrgustikku ründavate teadetega.
• Kõik eelpooltoodud peab olema vastupidav kokkulepetele lubatud arvu ebaausate osaliste osas (nt 1/3 osalistest).

Iga võimalus, millega seotud vähemusgrupp osaleb kontrollitud paaris/ümardatud juhuslikkuses, on turvaauk. Iga võimalus grupil juhuslikkuse väljastamist peatada, on turvaauk. Kokkuvõttes on probleeme palju ja see ülesanne ei ole kerge…

Tundub, et kõige olulisem rakendus PVRB jaoks on erinevad mängud, loteriid ja üldiselt kõik nädalavahetuse hasartmängud plokiahelas. Tõepoolest, see on oluline suund, kuid juhusliku valiku rakendusi plokiahelas on ka tõsisemaid. Vaadakem neid.

Konsensusalgoritmid

PVRB mängib võrgu konsensuse loomisel suurt rolli. Blokeeringute tehingud on kaitstud digiallkirjaga, mistõttu tähendab "tehingu rünnak" alati tehingu lisamist või eemaldamist blokist (või mitmest blokist). Konsensuse algoritmi peamine ülesanne on leppida kokku nende tehingute järjekorras ja blokkide järjekorras, mis need tehingud sisaldavad. Samuti on reaalsete plokiahelate vajalikuks omaduseks lõplikkus – võime, et võrk lepiks kokku, et järgmise lõpliku bloki ahel on lõplik ja seda ei saa kõrvaldada uue fork'i tõttu. Tavaliselt on vaja kokku koguda allkirjad enamiku blokkide tootjatelt (edasi BP – block-producers), et leppida kokku, et blokk on kehtiv ja mis kõige tähtsam, lõplik. See nõuab vähemalt blokiahela edastamist kõigile BP-dele ja allkirjade jagamist kõigi BP-de vahel. BP-de arvu suurenedes kasvab vajalik sõnumite arv võrgus eksponentsiaalselt, seetõttu ei tööta lõplikkust nõudvad konsensuse algoritmid, mida kasutatakse näiteks Hyperledgeri pBFT konsensusel, vajaliku kiirusen d, alates juba mõnest kümnest BP-st, nõudes tohutut šnede ühendusi.

Kui võrgus on usaldusväärne ja aus PVRB, siis isegi kõige lihtsamas lähenemises võib selle alusel valida ühe block producer'i ja määrata ta "juhiks" ühe protokolli vooru jooksul. Kui meil on N block producer'eid, millest M: M > 1/2 N on ausad, ei tsenseeri tehinguid ning ei ehita järjestusi rünnaku "double spend" läbiviimiseks, siis ühtlaselt jaotatud usaldusväärse PVRB kasutamine võimaldab ausa juhi valimist tõenäosusega M / N (M / N > 1/2). Kui iga liidri jaoks seada kindel ajaintervall, mille jooksul ta saab ploki luua ja ahelat valideerida, ning need intervallid on võrdsed ajaliselt, siis on ausate BP plokkide ahel pikem kui pahatahtlike BP moodustatud ahel. Konsensuse algoritm, mis toetub ahela pikkusele, lihtsalt viskab „halva” kõrvale. See põhimõte võrdsete ajakvantide määramisest igale BP-le rakendati esmakordselt Graphene'is (EOS-i eelkäijas) ning see võimaldab enamikul plokkidel sulgeda ühe allkirjaga, mis vähendab oluliselt võrgu koormust ja võimaldab sellel konsensusel töötada äärmiselt kiiresti ja stabiilselt. Siiski peab EOS võrgud praegu kasutama spetsiaalseid plokke (Viimane Eitusplokk), mis kinnitatakse 2/3 BP allkirjadega. Need plokid tagavad lõplikkuse (ahela forkide tekkimise võimatuse, mis algab enne viimast Viimast Eitusplokki).

Samuti on reaalses rakenduses protokolli skeem keerulisem — pakutud plokkide hääletamine toimub mitmes etapis, et toetada võrgu tööd plokkide jätmise ja võrgu probleemide korral, kuid isegi sellega arvestades nõuavad PVRB-konsensuse algoritmid BP-de vahel märksa vähem sõnumeid, mis muudab need kiiremateks kui traditsiooniline PВFT või selle erinevad modifikatsioonid.

Eri tõendite esindaja selliste algoritmide seas: Ouroboros Cardano meeskonnalt, mis, nagu on kuulutatud, omab matemaatiliselt tõestatavat vastupidavust BP-de vahelistele kokkulepetele.

Ouroboros PVRB võimaldab määrata nii nimetatud "BP ajakava" - ajakava, mille kohaselt antakse igale BP-le oma ajavöönd ploki avaldamiseks. PVRB kasutamise suur eelis on BP-de täielik "ühtsus" (vastavalt nende bilansside suurusele). PVRB ausus tagab, et pahatahtlikud BP-d ei saa ajakavade üle kontrolli omada ning seetõttu ei saa nad manipuleerida ahelaga, valmistades ette ja analüüsides ahela haru, sest haru valimiseks piisab lihtsalt ahela pikkuse järgimisest, ilma et oleks vaja kasutada keerulisi meetodeid BP "kasulikkuse" ja selle plokkide "kaalu" arvutamiseks.

Tõeliselt, kui peab valima juhusliku osaleja detsentraliseeritud võrgus, on peaaegu alati parim valik PVRB, mitte deterministlik variant nagu näiteks ploki räsi põhjal. Ilma PVRB-teta võivad osalejate valikule mõju avaldada rünnakud, kus ründaja võib, valides mitmest tulevikuvõimalusest, valida järgmise korruptsiooniga osaleja või mitmed korraga, et tagada suurem osalus otsuse tegemises. PVRB kasutamine diskrediteerib selliseid rünnakutüüpe.

Skaalabeliseerimine ja koormuse tasakaalustamine

PVRB võib tõsiselt kasu tuua ka koormuse vähendamise ja maksete skaleerimise ülesannetes. Esiteks on mõistlik tutvuda artikkel Rivesta "Electronic Lottery Tickets as Micropayments". Üldine idee on, et asemel et teha 100 makset 1 senti maksjalt saajale, saab mängida ausat loterii, kus auhind on 1 dollar = 100 senti, kus iga makse 1 senti annab maksjale ühe oma 100-st "loteriipiletist" pangale. Üks neist piletitest võidab pangale 1 dollari, ja just selle pileti saab saaja fikseerida plokiahelas. Märkimisväärne on see, et ülejäänud 99 piletit edastatakse saaja ja makja vahel ilma välist osalust, privaatkanali kaudu ja igas vajalikus tempos. Hea protokolli kirjeldust, mis põhineb sellel skeemil Emercoinis, võib lugeda. siit.

Sellel skeemil on mitmeid probleeme, näiteks võib saaja lõpetada makse saajaga teenuste osutamine kohe pärast võidupileti saamist, kuid paljude erikohalduste, nagu minutite kaupa arveldamine või teenuse elektronallkirjad, osas võib neid ignoreerida. Peamine nõue on muidugi läbipaistvus korraldatud loterii osas, ja selleks on täiesti vajalik PVRB.

Juhusliku osaleja valimine on äärmiselt oluline ka shardimise protokollide jaoks, mille eesmärk on plokiahela horisontaalne skaleerimine, võimaldades erinevatel BP-del töödelda vaid oma tehingute ulatust. See on äärmiselt keeruline ülesanne, eriti turvalisuse küsimustes shardide liitmisel. Aus juhuslik BP valimine, kellele määratakse vastutus kindla shardi eest, on samuti PVRB ülesanne, nagu ka konsensuse algoritmid. Tsentraliseeritud süsteemides määrab shardid koormuse jaotaja, kes arvutab lihtsalt päringu hash'i ja saadab selle vajalikule täitjale. Plokiahelates võib võimalus mõjutada seda määramist viia konsensusele rünnakuni. Näiteks võivad tehingute sisu kontrollida ründajad, kes saavad kontrollida, millised tehingud satuvad tema kontrollitavasse shardi, ning manipuleerida plokiahela sisuga. Üksikasjalikku arutelu juhuslike arvude kasutamise probleemist shardimise ülesannetes Ethereumi kontekstis on võimalik lugeda. siit
Shardimine on üks kõige ambitsioonikamaid ja tõsisematest ülesannetest plokiahela valdkonnas. Selle lahendamine võimaldab luua detsentraliseeritud võrke fantastilise jõudluse ja mahtude jaoks. PVRB on vaid üks tähtsamaid komponente selle saavutamiseks.

Mängud, majandusprotokollid, arbitraaž

Juhuslike numbrite roll mängutööstuses on raske üle hinnata. Nende otsene kasutamine online-kasiinodes ja kaudne kasutamine mängija tegevuste tagajärgede arvutamisel tekitab keerulisi küsimusi detsentraliseeritud võrkudes, kus ei saa toetuda keskse juhuslikkuse allikale. Kuid juhuslik valik aitab lahendada ka paljusid majanduslikke probleeme ja luua lihtsamaid ja efektiivsemaid protokolle. Kujutame ette, et meie protokollis on vaidlusi odavate teenuste eest maksmise üle, mis esinevad piisavalt harva. Sellisel juhul, kui on vaieldamatult PVRB, saavad kliendid ja müüjad kokku leppida juhuslikus vaidluste lahenduses, 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 automaatselt lahendada vaidlusi täpselt ennustatava võitude/kaotuste osakaalu abil, mis rahuldab mõlemaid osalisi, ilma kolmanda osapoole sekkumiseta ja tarbetu ajakulu. Veelgi enam, tõenäosuste suhe võib olla dünaamiline ja sõltuda teatud globaalsetest muutujatest. Näiteks, kui ettevõttel läheb hästi, on vähe vaidlusi ja kõrge kasumlikkus, võib ettevõte automaatselt tõsta vaidluste lahendamise tõenäosust kliendi suunas, näiteks 70/30 või 80/20, ja vastupidi, kui vaidlused neelavad palju raha ja on petlikud või ebaadekvaatsed, saab tõenäosust suunata teise suunda.

Suure hulga huvitavate detsentraliseeritud protokollide, nagu token-cuuritud registrid, ennustusturud, sidumiskõverad ja paljud teised, kaudu saavad majandusmängud premeerida head käitumist ning karistada halba. Nendes esinevad sageli turvaprobleemid, kus kaitsemeetmed üksteist kontrasteerivad. See, mis on kaitstud miljardite tokenitega „kala” rünakute vastu, on haavatav tuhandete väikeste bilanssidega konto rünnakute („sybil stake”) ees, ja meetmed, mida rakendatakse ühe rünnaku vastu, näiteks mittelineaarsed tasud, mis on välja töötatud suurte panuste kasumit vähendamise eesmärgil, üldiselt diskrediteeritakse teise rünnaku poolt. Kuna tegemist on majandusmänguga, saab vastavaid statistilisi kaalud eelnevalt arvutada ja lihtsalt asendada tasud vastava jaotuse põhjal juhuslikega. Sellised tõenäosuslikud tasud on äärmiselt lihtsad teostada, kui plokiahelas on usaldusväärne juhuslikkuse allikas ning ei nõua keerulisi arvutusi, muutes elu keeruliseks nii „kala” kui ka „sybil”-ite puhul.
Oluline on jätkata meeles, et ühe bit'i kontrollimine selles juhuslikkuses võimaldab petta, kergendades ja raskendades tõenäosusi kahekordselt, seega on aus PVRB selliste protokollide kriitiline osa.

Kust leida õiget juhuslikkust?

Teoreetiliselt võimaldab aus juhuslik valik detsentraliseeritud võrkudes peaaegu igasuguste protokollide tõendatavat turvalisust kartelli vastu. Põhjendus on üsna lihtne — kui võrk lepib kokku ühes bit'is 0 või 1, ning osalejate seas on vähem kui pooled ebaausad, siis piisava arvu iteratsioonide korral saavutab võrk garantii konsensuse selle bit'i osas kindla tõenäosusega. Lihtsalt sellepärast, et aus juhuslik valik valib 51 100 osalejast 51% juhtudel. Kuid see on teoorias, kuna reaalsetes võrkudes, et saavutada sellist turvalisuse taset nagu artiklites, on vajalik suur hulk sõnumeid hostide vahel, keeruline mitmeastmeline krüptograafia, ning iga protokolli keerulisemaks muutmine toob kaasa uusi rünnakusuundi.
Justament sellepärast ei näe me veel plokiahelates sõltumatult tõestatud PVRB-d, mida oleks kasutatud piisavalt kaua, et läbida ehtsate rakenduste, mitme auditi, koormuste ning loomulikult ka reaalsete rünnakute testid, ilma milleta on keeruline nimetada toodet tõeliselt turvaliseks.

Sellegipoolest on mitu perspektiivset lähenemist, mis erinevad paljuski detailides, ja üks neist lahendab kindlasti probleemi. Tänapäevaste arvutusressursside juures suudab krüptograafia teooria üsna osavalt muutuda praktilisteks rakendusteks. Edasi räägime rõõmuga PVRB rakendustest: neid on praegu mitu, igaühel on oma oluline omaduste ja rakenduse eripära, ning igaühe taga on hea idee. Rändamisega tegelevaid meeskondi ei ole palju, ning igaühe kogemus on äärmiselt oluline kõigile teistele. Loodame, et meie teave aitab teistel meeskondadel liikuda kiiremini, tuginedes eelkäijate kogemusele.

Allikas: habr.com