įvedimas
„Atsitiktinių skaičių generavimas yra pernelyg svarbus, kad būtų paliktas atsitiktinumui.
Robertas Cavue, 1970 m
Šis straipsnis skirtas praktiniam sprendimų taikymui naudojant kolektyvinį atsitiktinių skaičių generavimą nepatikimoje aplinkoje. Trumpai tariant, kaip ir kodėl atsitiktinis yra naudojamas blokų grandinėse, ir šiek tiek apie tai, kaip atskirti „gerą“ atsitiktinį nuo „blogo“. Sugeneruoti tikrai atsitiktinį skaičių yra nepaprastai sudėtinga problema, net ir viename kompiuteryje, ir ją jau seniai tyrinėjo kriptografai. Na, decentralizuotuose tinkluose atsitiktinių skaičių generavimas yra dar sudėtingesnis ir svarbesnis.
Būtent tinkluose, kuriuose dalyviai nepasitiki vieni kitais, galimybė sugeneruoti neginčijamą atsitiktinį skaičių leidžia efektyviai išspręsti daugelį kritinių problemų ir gerokai patobulinti esamas schemas. Be to, lošimai ir loterijos čia nėra pagrindinis tikslas, kaip gali pasirodyti iš pradžių nepatyrusiam skaitytojui.
Atsitiktinių skaičių generavimas
Kompiuteriai negali patys generuoti atsitiktinių skaičių, tam reikia išorės pagalbos. Kompiuteris gali gauti tam tikrą atsitiktinę vertę naudodamas, pavyzdžiui, pelės judesius, naudojamos atminties kiekį, procesoriaus kontaktų sroves ir daugelį kitų šaltinių, vadinamų entropijos šaltiniais. Šios vertės nėra visiškai atsitiktinės, nes jos yra tam tikrame diapazone arba turi nuspėjamą pokyčių modelį. Norint tokius skaičius paversti tikrai atsitiktiniu skaičiumi tam tikrame diapazone, jiems taikomos kriptotransformacijos, kad būtų gaunamos tolygiai paskirstytos pseudoatsitiktinės reikšmės iš netolygiai paskirstytų entropijos šaltinio verčių. Gautos reikšmės vadinamos pseudoatsitiktinėmis, nes jos nėra tikrai atsitiktinės, o deterministiškai išvestos iš entropijos. Bet koks geras kriptografinis algoritmas šifruodamas duomenis sukuria šifruotus tekstus, kurie statistiškai neturėtų skirtis nuo atsitiktinės sekos, todėl atsitiktinumui sukurti galite paimti entropijos šaltinį, kuris užtikrina tik gerą reikšmių nepakartojamumą ir nenuspėjamumą net ir mažuose diapazonuose. , likęs darbas – bitų sklaidymas ir maišymas Gautą reikšmę perims šifravimo algoritmas.
Baigdamas trumpą edukacinę programą pridursiu, kad atsitiktinių skaičių generavimas net viename įrenginyje yra vienas iš mūsų duomenų saugumo užtikrinimo ramsčių.Sugeneruoti pseudoatsitiktiniai skaičiai naudojami užmezgant saugius ryšius įvairiuose tinkluose, generuojant kriptografiniai raktai, skirti apkrovos balansavimui, vientisumo stebėjimui ir daugeliui kitų programų. Daugelio protokolų saugumas priklauso nuo galimybės sugeneruoti patikimą, išoriškai nenuspėjamą atsitiktinumą, jį saugoti ir neatskleisti iki kito protokolo žingsnio, kitaip saugumas bus pažeistas. Ataka prieš pseudoatsitiktinių verčių generatorių yra itin pavojinga ir iš karto kelia grėsmę visai programinei įrangai, kuri naudoja atsitiktinumo generavimą.
Visa tai turėtumėte žinoti, jei išklausėte pagrindinį kriptografijos kursą, todėl tęskime apie decentralizuotus tinklus.
Atsitiktinis blokų grandinėse
Pirmiausia pakalbėsiu apie „blockchain“ su išmaniųjų kontraktų palaikymu – būtent jie gali visapusiškai išnaudoti kokybiško, nepaneigiamo atsitiktinumo teikiamas galimybes. Be to, dėl trumpumo šią technologiją pavadinsiu “Viešai patikrinami atsitiktiniai švyturiai“ arba PVRB. Kadangi blokų grandinės yra tinklai, kuriuose informaciją gali patikrinti bet kuris dalyvis, pagrindinė pavadinimo dalis yra „Publicly Verifiable“, t.y. Kiekvienas gali naudoti skaičiavimus, kad gautų įrodymą, kad gautas skaičius, paskelbtas blokų grandinėje, turi šias savybes:
- Rezultatas turi turėti įrodytai vienodą pasiskirstymą, t. y. turi būti pagrįstas įrodomai stipria kriptografija.
- Neįmanoma valdyti nė vieno rezultato bito. Dėl to rezultato iš anksto numatyti negalima.
- Negalite sabotuoti generavimo protokolo nedalyvaudami protokole arba perkraudami tinklą atakos pranešimais
- Visa tai turi būti atspari leistino skaičiaus nesąžiningų protokolo dalyvių (pvz., 1/3 dalyvių) susitarimui.
Bet kokia galimybė susiderinusiai nedidelei dalyvių grupei sukurti net kontroliuojamą lyginį/nelyginį atsitiktinumą yra saugumo spraga. Bet koks grupės gebėjimas sustabdyti atsitiktinių išdavimą yra saugumo spraga. Apskritai problemų yra daug, ir ši užduotis nėra lengva...
Atrodo, kad svarbiausia PVRB programa yra įvairūs žaidimai, loterijos ir apskritai bet koks lošimas blokų grandinėje. Iš tiesų, tai yra svarbi kryptis, tačiau atsitiktinumas blokų grandinėse turi dar svarbesnių pritaikymų. Pažiūrėkime į juos.
Konsensuso algoritmai
PVRB vaidina didžiulį vaidmenį organizuojant tinklo konsensusą. Sandoriai blokų grandinėse yra apsaugoti elektroniniu parašu, todėl „operacijos ataka“ visada yra operacijos įtraukimas / pašalinimas į bloką (ar kelis blokus). O pagrindinė konsensuso algoritmo užduotis – susitarti dėl šių operacijų eiliškumo ir blokų, į kuriuos įtrauktos šios operacijos, eilės. Taip pat būtina tikrų blokų grandinių savybė yra baigtumas – tinklo galimybė susitarti, kad grandinė iki užbaigto bloko yra galutinė ir niekada nebus pašalinta dėl naujos šakutės atsiradimo. Paprastai norint susitarti, kad blokas yra galiojantis ir, svarbiausia, galutinis, reikia surinkti daugumos blokų gamintojų (toliau – BP – blokų gamintojai) parašus, tam reikia bent jau pristatyti bloko grandinę. visiems BP ir paskirstyti parašus tarp visų BP . Augant BP skaičiui, reikalingų pranešimų skaičius tinkle auga eksponentiškai, todėl baigtinumo reikalaujantys konsensuso algoritmai, naudojami, pavyzdžiui, Hyperledger pBFT consensus, neveikia reikiamu greičiu, pradedant nuo kelių dešimčių BP. didžiulis jungčių skaičius.
Jei tinkle yra neabejotinas ir sąžiningas PVRB, tai, net ir paprasčiausiai apytiksliai, pagal jį galima pasirinkti vieną iš blokų gamintojų ir vieno protokolo etapo metu paskirti jį „lyderiu“. Jei turime N blokų gamintojų, iš kurių M: M > 1/2 N yra sąžiningi, necenzūruokite sandorių ir nešakėte grandinės vykdyti „dvigubų išlaidų“ ataką, tada tolygiai paskirstyto neginčijamo PVRB naudojimas leis su tikimybe pasirinkti sąžiningą lyderį M / N (M / N > 1/2). Jei kiekvienam lyderiui bus priskirtas savo laiko intervalas, per kurį jis gali sudaryti bloką ir patvirtinti grandinę, o šie intervalai laike yra vienodi, tada sąžiningų BP blokų grandinė bus ilgesnė nei piktybinių BP sudaryta grandinė ir sutarimas algoritmas priklauso nuo grandinės ilgio. „blogąjį“ tiesiog atmes. Šis vienodų laiko gabalų paskirstymo kiekvienam BP principas pirmą kartą buvo pritaikytas Graphene (EOS pirmtakas) ir leidžia daugumą blokų uždaryti vienu parašu, o tai labai sumažina tinklo apkrovą ir leidžia šiam konsensusui veikti itin greitai ir stabiliai. Tačiau EOS tinkle dabar tenka naudoti specialius blokus (Last Irreversible Block), kuriuos patvirtina 2/3 BP parašai. Šie blokai padeda užtikrinti užbaigtumą (neįmanoma grandininės šakės prasidėti prieš paskutinį paskutinį negrįžtamą bloką).
Be to, realiose programose protokolo schema yra sudėtingesnė - balsavimas už siūlomus blokus vyksta keliais etapais, kad tinklas būtų išlaikytas, jei trūksta blokų ir problemų su tinklu, tačiau net ir atsižvelgiant į tai, konsensuso algoritmai, naudojantys PVRB, reikalauja. žymiai mažiau pranešimų tarp BP, o tai leidžia juos padaryti greičiau nei tradicinis PVFT ar įvairios jo modifikacijos.
Ryškiausias tokių algoritmų atstovas: iš Cardano komandos, kuri, kaip teigiama, matematiškai įrodoma prieš BP susitarimą.
„Ouroboros“ PVRB naudojamas apibrėžti vadinamąjį „BP tvarkaraštį“ - grafiką, pagal kurį kiekvienam BP priskiriamas atskiras laiko tarpas blokui paskelbti. Didelis PVRB naudojimo pranašumas yra visiška BP „lygybė“ (pagal jų balansų dydį). PVRB vientisumas užtikrina, kad kenkėjiški BP negalėtų kontroliuoti laiko tarpsnių planavimo, todėl negalėtų manipuliuoti grandine iš anksto paruošdami ir analizuodami grandinės šakutes, o norint pasirinkti šakę pakanka tiesiog pasikliauti laiko tarpų trukme. grandinę, nenaudojant sudėtingų būdų apskaičiuoti BP „naudingumą“ ir jo blokų „svorį“.
Apskritai visais atvejais, kai decentralizuotame tinkle reikia pasirinkti atsitiktinį dalyvį, PVRB beveik visada yra geriausias pasirinkimas, o ne deterministinė parinktis, pagrįsta, pavyzdžiui, bloko maiša. Be PVRB, galimybė daryti įtaką dalyvio pasirinkimui sukelia atakas, kurių metu užpuolikas gali pasirinkti iš kelių ateities sandorių ir pasirinkti kitą korumpuotą dalyvį arba kelis iš karto, kad užtikrintų didesnę sprendimo dalį. PVRB naudojimas diskredituoja tokio tipo atakas.
Mastelio keitimas ir apkrovos balansavimas
PVRB taip pat gali būti labai naudinga atliekant tokias užduotis kaip apkrovos mažinimas ir mokėjimo mastelio keitimas. Pirmiausia prasminga susipažinti su Rivesta „Elektroninės loterijos bilietai kaip mikromokėjimai“. Bendra idėja yra ta, kad užuot atlikę 100 1c mokėjimų iš mokėtojo gavėjui, galite žaisti sąžiningą loteriją su 1 USD = 100 c laimėjimu, kai mokėtojas duoda bankui vieną iš 1 savo „loterijos bilietų“ už kiekvieną. 100c mokėjimas. Vienas iš šių bilietų laimi 1 USD indelį ir būtent šį bilietą gavėjas gali įrašyti į blokų grandinę. Svarbiausia, kad likę 99 bilietai būtų perduodami tarp gavėjo ir mokėtojo be jokio išorinio dalyvavimo, privačiu kanalu ir bet kokiu norimu greičiu. Galima perskaityti gerą protokolo, pagrįsto šia schema, aprašymą Emercoin tinkle .
Ši schema turi keletą problemų, pvz., gavęs laimėtą bilietą, gavėjas gali iš karto nustoti aptarnauti mokėtoją, tačiau daugeliui specialių programų, tokių kaip minutinis atsiskaitymas ar elektroninis paslaugų prenumerata, jų galima nepaisyti. Pagrindinis reikalavimas, be abejo, yra loterijos sąžiningumas, o jos įgyvendinimui būtinas PVRB.
Atsitiktinio dalyvio pasirinkimas taip pat labai svarbus dalijimosi protokolams, kurių tikslas yra horizontaliai mastelėti blokų grandinę, leidžiančią skirtingiems BP apdoroti tik savo operacijų apimtį. Tai itin sudėtinga užduotis, ypač saugumo požiūriu suliejant šukes. Sąžiningas atsitiktinio BP parinkimas, siekiant priskirti asmenis, atsakingus už konkrečią skeveldrą, kaip ir konsensuso algoritmuose, taip pat yra PVRB užduotis. Centralizuotose sistemose skeveldras priskiria balansuotojas, jis tiesiog apskaičiuoja užklausos maišą ir siunčia jį reikiamam vykdytojui. Blokų grandinėse galimybė paveikti šią užduotį gali sukelti sutarimo puolimą. Pavyzdžiui, operacijų turinį gali valdyti užpuolikas, jis gali kontroliuoti, kurios operacijos patenka į jo valdomą skeveldrą ir manipuliuoti joje esančia blokų grandine. Galite perskaityti diskusiją apie atsitiktinių skaičių naudojimo Ethereum užduotims suskaidyti
Dalijimasis yra viena ambicingiausių ir rimčiausių problemų blokų grandinės srityje, jos sprendimas leis sukurti fantastiško našumo ir apimties decentralizuotus tinklus. PVRB yra tik vienas iš svarbių blokų jai išspręsti.
Žaidimai, ekonominiai protokolai, arbitražas
Atsitiktinių skaičių vaidmenį žaidimų pramonėje sunku pervertinti. Aiškus naudojimas internetiniuose kazino ir numanomas naudojimas skaičiuojant žaidėjo veiksmų poveikį yra labai sudėtingos decentralizuotų tinklų problemos, kuriose nėra galimybės pasikliauti pagrindiniu atsitiktinumo šaltiniu. Tačiau atsitiktinė atranka taip pat gali išspręsti daugelį ekonominių problemų ir padėti sukurti paprastesnius ir efektyvesnius protokolus. Tarkime, mūsų protokole yra ginčų dėl apmokėjimo už kai kurias nebrangias paslaugas, ir šie ginčai pasitaiko gana retai. Tokiu atveju, jei yra neginčijamas PVRB, klientai ir pardavėjai gali susitarti ginčus spręsti atsitiktine tvarka, tačiau su tam tikra tikimybe. Pavyzdžiui, 60% tikimybe laimės klientas, o 40% – pardavėjas. Šis iš pirmo žvilgsnio absurdiškas požiūris leidžia automatiškai išspręsti ginčus su tiksliai nuspėjama laimėjimų/pralaimėjimų dalimi, kas tinka abiem pusėms be jokio trečiosios šalies dalyvavimo ir bereikalingo laiko švaistymo. Be to, tikimybės santykis gali būti dinamiškas ir priklausyti nuo kai kurių pasaulinių kintamųjų. Pavyzdžiui, jei įmonei sekasi gerai, ji turi mažai ginčų ir turi didelį pelningumą, įmonė gali automatiškai nukreipti ginčo sprendimo tikimybę į klientą, pavyzdžiui, 70/30 arba 80/20 ir atvirkščiai, jei ginčai atima daug pinigų ir yra apgaulingi arba netinkami, galite pakeisti tikimybę kita linkme.
Daug įdomių decentralizuotų protokolų, tokių kaip žetonų kuruojami registrai, prognozavimo rinkos, susiejimo kreivės ir daugelis kitų, yra ekonominiai žaidimai, kuriuose už gerą elgesį atlyginama, o už blogą elgesį baudžiama. Juose dažnai yra saugumo problemų, dėl kurių apsaugos prieštarauja viena kitai. Tai, kas apsaugota nuo „banginių“ atakų su milijardais žetonų („didelė dalis“) yra pažeidžiama tūkstančių sąskaitų su mažu likučiu („sybil stake“) išpuolių ir priemonių, kurių imamasi prieš vieną ataką, pvz. linijiniai mokesčiai, sukurti tam, kad darbas su dideliu akcijų paketu būtų nepelningas, paprastai yra diskredituojami kitos atakos. Kadangi kalbame apie ekonominį žaidimą, atitinkamus statistinius svorius galima apskaičiuoti iš anksto, o komisinius tiesiog pakeisti atsitiktine tvarka su atitinkamu pasiskirstymu. Tokie tikimybiniai komisiniai įgyvendinami itin paprastai, jei blokų grandinė turi patikimą atsitiktinumo šaltinį ir nereikalauja jokių sudėtingų skaičiavimų, apsunkinančių gyvenimą tiek banginiams, tiek sibilams.
Tuo pačiu reikia ir toliau atsiminti, kad vieno bito kontrolė šiame atsitiktinume leidžia sukčiauti, sumažinant ir padidinant tikimybę per pusę, todėl sąžiningas PVRB yra svarbiausias tokių protokolų komponentas.
Kur rasti tinkamą atsitiktinį?
Teoriškai sąžininga atsitiktinė atranka decentralizuotuose tinkluose daro beveik bet kokį protokolą apsaugotą nuo slapto susitarimo. Loginis pagrindas yra gana paprastas – jei tinklas susitaria dėl vieno 0 ar 1 bito, o mažiau nei pusė dalyvių yra nesąžiningi, tada, atlikus pakankamai iteracijų, tinklas garantuotai pasieks sutarimą dėl to bito su fiksuota tikimybe. Tiesiog todėl, kad sąžiningas atsitiktinis žmogus 51% atvejų pasirinks 100 iš 51 dalyvių. Bet tai teoriškai, nes... tikruose tinkluose, norint užtikrinti tokį saugumo lygį kaip ir straipsniuose, reikalinga daug pranešimų tarp kompiuterių, sudėtinga kelių praėjimų kriptografija, o bet kokia protokolo komplikacija iš karto prideda naujų atakų vektorių.
Štai kodėl blokų grandinėse dar nematome įrodyto atsparaus PVRB, kuris būtų buvęs naudojamas pakankamai ilgai, kad būtų išbandytas realiomis programomis, daugkartiniais auditais, apkrovomis ir, žinoma, tikromis atakomis, be kurių sunku pavadinti produktas tikrai saugus.
Tačiau yra keletas perspektyvių požiūrių, jie skiriasi daugybe detalių, ir vienas iš jų tikrai išspręs problemą. Naudojant šiuolaikinius skaičiavimo išteklius, kriptografijos teoriją galima gana sumaniai paversti praktiniais pritaikymais. Ateityje mielai pakalbėsime apie PVRB diegimus: dabar jų yra keletas, kiekvienas turi savo svarbių savybių ir diegimo ypatybių rinkinį, o už kiekvieno slypi gera idėja. Atsitiktinių atrankoje dalyvauja nedaug komandų, o kiekvienos iš jų patirtis yra be galo svarbi visiems kitiems. Tikimės, kad mūsų informacija leis kitoms komandoms judėti greičiau, atsižvelgiant į savo pirmtakų patirtį.
Šaltinis: www.habr.com