Paraqitje
"Gjenerimi i numrave të rastësishëm është shumë i rëndësishëm për t'u lënë në dorë të fatit."
Robert Cavue, 1970
Ky artikull i kushtohet zbatimit praktik të zgjidhjeve duke përdorur gjenerimin kolektiv të numrave të rastësishëm në një mjedis të pabesueshëm. Shkurtimisht, si dhe pse përdoret rastësia në blockchains, dhe pak se si të dallojmë rastësinë "e mirë" nga "e keqja". Gjenerimi i një numri vërtet të rastësishëm është një problem jashtëzakonisht i vështirë, madje edhe në një kompjuter të vetëm, dhe është studiuar prej kohësh nga kriptografët. Epo, në rrjetet e decentralizuara, gjenerimi i numrave të rastësishëm është edhe më kompleks dhe më i rëndësishëm.
Pikërisht në rrjetet ku pjesëmarrësit nuk i besojnë njëri-tjetrit, aftësia për të gjeneruar një numër të rastësishëm të padiskutueshëm na lejon të zgjidhim në mënyrë efektive shumë probleme kritike dhe të përmirësojmë ndjeshëm skemat ekzistuese. Për më tepër, kumari dhe llotaritë nuk janë qëllimi numër një këtu, siç mund t'i duket në fillim lexuesit të papërvojë.
Gjenerimi i numrave të rastësishëm
Kompjuterët nuk mund të gjenerojnë vetë numra të rastësishëm; ata kërkojnë ndihmë nga jashtë për ta bërë këtë. Kompjuteri mund të marrë disa vlera të rastësishme, për shembull, nga lëvizjet e miut, sasia e memories së përdorur, rrymat e humbura në kunjat e procesorit dhe shumë burime të tjera të quajtura burime entropie. Vetë këto vlera nuk janë plotësisht të rastësishme, pasi ato janë në një gamë të caktuar ose kanë një model të parashikueshëm ndryshimesh. Për t'i kthyer numrat e tillë në një numër vërtet të rastësishëm brenda një diapazoni të caktuar, kriptotransformimet aplikohen në to për të prodhuar vlera pseudo të rastësishme të shpërndara në mënyrë uniforme nga vlerat e shpërndara në mënyrë të pabarabartë të burimit të entropisë. Vlerat që rezultojnë quhen pseudorandom sepse ato nuk janë vërtet të rastësishme, por rrjedhin në mënyrë deterministe nga entropia. Çdo algoritëm i mirë kriptografik, kur kripton të dhënat, prodhon tekste shifrore që duhet të jenë statistikisht të padallueshme nga një sekuencë e rastësishme, kështu që për të prodhuar rastësi mund të merrni një burim entropie, i cili siguron vetëm përsëritshmëri të mirë dhe paparashikueshmëri të vlerave edhe në intervale të vogla. pjesa tjetër e punës është shpërndarja dhe përzierja e biteve në Vlera që rezulton do të merret përsipër nga algoritmi i enkriptimit.
Për të përfunduar një program të shkurtër arsimor, do të shtoj se gjenerimi i numrave të rastit qoftë edhe në një pajisje është një nga shtyllat e sigurimit të sigurisë së të dhënave tona.Numrat pseudo rastësor të gjeneruar përdoren kur vendosen lidhje të sigurta në rrjete të ndryshme, për të gjeneruar çelësat kriptografikë, për balancimin e ngarkesës, monitorimin e integritetit dhe për shumë aplikacione të tjera. Siguria e shumë protokolleve varet nga aftësia për të gjeneruar një rastësi të besueshme, të paparashikueshme nga jashtë, për ta ruajtur atë dhe për të mos e zbuluar deri në hapin tjetër të protokollit, përndryshe siguria do të rrezikohet. Një sulm ndaj një gjeneruesi të vlerave pseudorandom është jashtëzakonisht i rrezikshëm dhe kërcënon menjëherë të gjithë softuerin që përdor gjenerimin e rastësisë.
Ju duhet t'i dini të gjitha këto nëse keni marrë një kurs bazë në kriptografi, kështu që le të vazhdojmë me rrjetet e decentralizuara.
Të rastësishme në blockchains
Para së gjithash, unë do të flas për blockchains me mbështetje për kontratat inteligjente; ata janë ata që mund të përfitojnë plotësisht nga mundësitë e ofruara nga rastësia me cilësi të lartë dhe të pamohueshme. Më tej, për shkurtësi, unë do ta quaja këtë teknologji "Fenerët e rastësishëm të verifikueshëm publikisht” ose PVRB. Meqenëse blockchains janë rrjete në të cilat informacioni mund të verifikohet nga çdo pjesëmarrës, pjesa kryesore e emrit është "Publicly Verifiable", d.m.th. Çdokush mund të përdorë llogaritjet për të marrë prova se numri rezultues i postuar në blockchain ka vetitë e mëposhtme:
- Rezultati duhet të ketë një shpërndarje uniforme të provueshme, d.m.th. të bazohet në kriptografi të provueshme të fortë.
- Nuk është e mundur të kontrollosh asnjë nga pjesët e rezultatit. Si pasojë, rezultati nuk mund të parashikohet paraprakisht.
- Ju nuk mund të sabotoni protokollin e gjenerimit duke mos marrë pjesë në protokoll ose duke mbingarkuar rrjetin me mesazhe sulmi
- Të gjitha sa më sipër duhet të jenë rezistente ndaj marrëveshjeve të fshehta të një numri të lejueshëm pjesëmarrësish të pandershëm të protokollit (për shembull, 1/3 e pjesëmarrësve).
Çdo mundësi e një grupi të vogël pjesëmarrësish në bashkëpunim për të prodhuar edhe një rastësi të kontrolluar çift/tek është një vrimë sigurie. Çdo aftësi e grupit për të ndaluar lëshimin e rastësishëm është një vrimë sigurie. Në përgjithësi, ka shumë probleme dhe kjo detyrë nuk është e lehtë...
Duket se aplikacioni më i rëndësishëm për PVRB janë lojërat e ndryshme, lotaritë dhe përgjithësisht çdo lloj kumari në blockchain. Në të vërtetë, ky është një drejtim i rëndësishëm, por rastësia në blockchains ka aplikime edhe më të rëndësishme. Le t'i shikojmë ato.
Algoritmet e konsensusit
PVRB luan një rol të madh në organizimin e konsensusit të rrjetit. Transaksionet në blockchains mbrohen nga një nënshkrim elektronik, kështu që një "sulm ndaj një transaksioni" është gjithmonë përfshirja/përjashtimi i një transaksioni në një bllok (ose disa blloqe). Dhe detyra kryesore e algoritmit të konsensusit është të bien dakord për rendin e këtyre transaksioneve dhe renditjen e blloqeve që përfshijnë këto transaksione. Gjithashtu, një pronë e nevojshme për zinxhirët e vërtetë të bllokut është finaliteti - aftësia e rrjetit për të rënë dakord që zinxhiri deri në bllokun e përfunduar është përfundimtar dhe nuk do të përjashtohet kurrë për shkak të shfaqjes së një piruni të ri. Zakonisht, për të rënë dakord që një bllok është i vlefshëm dhe, më e rëndësishmja, përfundimtar, është e nevojshme të mblidhen nënshkrime nga shumica e prodhuesve të bllokut (në tekstin e mëtejmë BP - prodhuesit e bllokut), gjë që kërkon të paktën dërgimin e zinxhirit të bllokut. për të gjitha PB-të dhe shpërndarja e nënshkrimeve ndërmjet të gjitha PB-ve. Ndërsa numri i BP-ve rritet, numri i mesazheve të nevojshme në rrjet rritet në mënyrë eksponenciale, prandaj, algoritmet e konsensusit që kërkojnë përfundim, të përdorura për shembull në konsensusin Hyperledger pBFT, nuk funksionojnë me shpejtësinë e kërkuar, duke filluar nga disa dhjetëra BP, që kërkojnë një numër i madh lidhjesh.
Nëse ka një PVRB të pamohueshme dhe të sinqertë në rrjet, atëherë, edhe në përafrimin më të thjeshtë, mund të zgjidhni një nga prodhuesit e bllokut bazuar në të dhe ta emëroni atë si "udhëheqës" gjatë një raundi të protokollit. Nëse kemi N prodhuesit e bllokut, nga të cilët M: M > 1/2 N janë të sinqertë, mos censuroni transaksionet dhe mos e shtyni zinxhirin për të kryer një sulm "shpenzim të dyfishtë", atëherë përdorimi i një PVRB të pakundërshtuar të shpërndarë në mënyrë uniforme do të lejojë zgjedhjen e një udhëheqësi të ndershëm me probabilitet M / N (M / N > 1/2). Nëse çdo lideri i caktohet intervali i tij kohor gjatë të cilit ai mund të prodhojë një bllok dhe të vërtetojë zinxhirin, dhe këto intervale janë të barabarta në kohë, atëherë zinxhiri i bllokut të BP-ve të ndershme do të jetë më i gjatë se zinxhiri i formuar nga BP-të keqdashëse dhe konsensusi algoritmi mbështetet në gjatësinë e zinxhirit, thjesht do të flak "të keqen". Ky parim i ndarjes së pjesëve të barabarta të kohës për çdo BP u zbatua fillimisht në Graphene (paraardhësi i EOS) dhe lejon që shumica e blloqeve të mbyllen me një nënshkrim të vetëm, gjë që redukton shumë ngarkesën e rrjetit dhe lejon që ky konsensus të funksionojë jashtëzakonisht shpejt dhe në mënyrë të qëndrueshme. Megjithatë, rrjeti EOS tani duhet të përdor blloqe speciale (Blloku i fundit i pakthyeshëm), të cilat konfirmohen nga nënshkrimet e 2/3 BP. Këto blloqe shërbejnë për të siguruar finalitetin (pamundësia e një piruni zinxhir që fillon përpara Bllokut të fundit të Parikthyeshëm).
Gjithashtu, në implementimet reale, skema e protokollit është më e ndërlikuar - votimi për blloqet e propozuara kryhet në disa faza për të mirëmbajtur rrjetin në rast të mungesës së blloqeve dhe problemeve me rrjetin, por edhe duke marrë parasysh këtë, algoritmet e konsensusit që përdorin PVRB kërkojnë shumë më pak mesazhe ndërmjet BP-ve, gjë që bën të mundur bërjen e tyre më të shpejtë se PVFT tradicionale, ose modifikimet e ndryshme të saj.
Përfaqësuesi më i shquar i algoritmeve të tilla: nga skuadra Cardano, e cila thuhet se është matematikisht e vërtetueshme kundër marrëveshjes së BP.
Në Ouroboros, PVRB përdoret për të përcaktuar të ashtuquajturin "Plani BP" - një orar sipas të cilit çdo BP i caktohet koha e vet për publikimin e një blloku. Avantazhi i madh i përdorimit të PVRB është "barazia" e plotë e BP-ve (sipas madhësisë së bilanceve të tyre). Integriteti i PVRB siguron që BP-të me qëllim të keq nuk mund të kontrollojnë planifikimin e sferave kohore, dhe për këtë arsye nuk mund të manipulojnë zinxhirin duke përgatitur dhe analizuar paraprakisht pirunët e zinxhirit, dhe për të zgjedhur një pirun mjafton të mbështeteni thjesht në gjatësinë e zinxhir, pa përdorur mënyra të ndërlikuara për të llogaritur "dobinë" e BP dhe "peshën" e blloqeve të saj.
Në përgjithësi, në të gjitha rastet kur një pjesëmarrës i rastësishëm duhet të zgjidhet në një rrjet të decentralizuar, PVRB është pothuajse gjithmonë zgjidhja më e mirë, sesa një opsion përcaktues i bazuar, për shembull, në një hash blloku. Pa PVRB, aftësia për të ndikuar në zgjedhjen e një pjesëmarrësi çon në sulme në të cilat sulmuesi mund të zgjedhë nga të ardhme të shumta për të zgjedhur pjesëmarrësin e ardhshëm të korruptuar ose disa menjëherë për të siguruar një pjesë më të madhe në vendim. Përdorimi i PVRB diskrediton këto lloj sulmesh.
Shkallëzimi dhe balancimi i ngarkesës
PVRB gjithashtu mund të jetë me përfitim të madh në detyra të tilla si reduktimi i ngarkesës dhe shkallëzimi i pagesës. Për të filluar, ka kuptim të njiheni me të Rivesta “Biletat Elektronike të Lotarisë si Mikropagesa”. Ideja e përgjithshme është që në vend që të bëni 100 pagesa 1c nga paguesi te marrësi, ju mund të luani një llotari të ndershme me një çmim prej 1$ = 100c, ku paguesi i jep bankës një nga 1 "biletat e lotarisë" së tij për secilën. pagesa 100c. Një nga këto bileta fiton një kavanoz prej 1 dollarësh dhe është kjo biletë që marrësi mund të regjistrojë në blockchain. Gjëja më e rëndësishme është që 99 biletat e mbetura të transferohen midis marrësit dhe paguesit pa asnjë pjesëmarrje të jashtme, përmes një kanali privat dhe me çdo shpejtësi të dëshiruar. Mund të lexohet një përshkrim i mirë i protokollit të bazuar në këtë skemë në rrjetin Emercoin .
Kjo skemë ka disa probleme, si për shembull, marrësi mund të ndalojë shërbimin ndaj paguesit menjëherë pas marrjes së një bilete fituese, por për shumë aplikacione të veçanta, si faturimi për minutë ose abonimet elektronike në shërbime, këto mund të neglizhohen. Kërkesa kryesore, natyrisht, është drejtësia e lotarisë, dhe për zbatimin e saj një PVRB është absolutisht e nevojshme.
Zgjedhja e një pjesëmarrësi të rastësishëm është gjithashtu jashtëzakonisht e rëndësishme për protokollet e ndarjes, qëllimi i të cilave është të shkallëzojë horizontalisht zinxhirin e bllokut, duke lejuar BP të ndryshme të përpunojnë vetëm fushën e tyre të transaksioneve. Kjo është një detyrë jashtëzakonisht e vështirë, veçanërisht në aspektin e sigurisë gjatë bashkimit të copëzave. Përzgjedhja e drejtë e një BP të rastësishme për qëllimin e caktimit të atyre që janë përgjegjës për një copëz të caktuar, si në algoritmet e konsensusit, është gjithashtu detyrë e PVRB. Në sistemet e centralizuara, copëzat caktohen nga një balancues; ai thjesht llogarit hash-in nga kërkesa dhe ia dërgon atë ekzekutuesit të kërkuar. Në blockchains, aftësia për të ndikuar në këtë detyrë mund të çojë në një sulm ndaj konsensusit. Për shembull, përmbajtja e transaksioneve mund të kontrollohet nga një sulmues, ai mund të kontrollojë se cilat transaksione shkojnë në copëzën që ai kontrollon dhe të manipulojë zinxhirin e blloqeve në të. Mund të lexoni një diskutim për problemin e përdorimit të numrave të rastësishëm për ndarjen e detyrave në Ethereum
Sharding është një nga problemet më ambicioze dhe serioze në fushën e blockchain; zgjidhja e tij do të lejojë ndërtimin e rrjeteve të decentralizuara me performancë dhe vëllim fantastik. PVRB është vetëm një nga blloqet e rëndësishme për ta zgjidhur atë.
Lojërat, protokollet ekonomike, arbitrazhi
Roli i numrave të rastësishëm në industrinë e lojërave është i vështirë të mbivlerësohet. Përdorimi i qartë në kazinotë online dhe përdorimi i nënkuptuar gjatë llogaritjes së efekteve të veprimit të një lojtari janë të gjitha probleme jashtëzakonisht të vështira për rrjetet e decentralizuara, ku nuk ka asnjë mënyrë për t'u mbështetur në një burim qendror të rastësisë. Por përzgjedhja e rastësishme gjithashtu mund të zgjidhë shumë probleme ekonomike dhe të ndihmojë në ndërtimin e protokolleve më të thjeshta dhe më efikase. Supozoni se në protokollin tonë ka mosmarrëveshje në lidhje me pagesën për disa shërbime të lira, dhe këto mosmarrëveshje ndodhin mjaft rrallë. Në këtë rast, nëse ekziston një PVRB e padiskutueshme, klientët dhe shitësit mund të bien dakord për të zgjidhur mosmarrëveshjet në mënyrë të rastësishme, por me një probabilitet të caktuar. Për shembull, me një probabilitet 60% klienti fiton, dhe me një probabilitet 40% fiton shitësi. Kjo qasje, e cila nga pikëpamja e parë është absurde, ju lejon të zgjidhni automatikisht mosmarrëveshjet me një përqindje saktësisht të parashikueshme të fitimeve/humbjeve, gjë që u përshtatet të dyja palëve pa pjesëmarrjen e një pale të tretë dhe humbje të panevojshme kohe. Për më tepër, raporti i probabilitetit mund të jetë dinamik dhe varet nga disa ndryshore globale. Për shembull, nëse një kompani po ecën mirë, ka një numër të ulët mosmarrëveshjesh dhe përfitim të lartë, kompania mund të zhvendosë automatikisht probabilitetin e zgjidhjes së një mosmarrëveshje drejt përqendrimit te klienti, për shembull 70/30 ose 80/20, dhe anasjelltas, nëse mosmarrëveshjet marrin shumë para dhe janë mashtruese ose të pamjaftueshme, ju mund ta zhvendosni probabilitetin në drejtimin tjetër.
Një numër i madh i protokolleve interesante të decentralizuara, të tilla si regjistrat e kuruar me token, tregjet e parashikimit, kthesat e lidhjes dhe shumë të tjera, janë lojëra ekonomike në të cilat sjellja e mirë shpërblehet dhe sjellja e keqe penalizohet. Ato shpesh përmbajnë probleme sigurie për të cilat mbrojtjet bien ndesh me njëra-tjetrën. Ajo që mbrohet nga një sulm nga "balenat" me miliarda argumente ("aksioni i madh") është i cenueshëm ndaj sulmeve nga mijëra llogari me balanca të vogla ("aksioni sybil") dhe masat e marra kundër një sulmi të vetëm, si p.sh. Tarifat lineare të krijuara për ta bërë të padobishme punën me një aksion të madh zakonisht diskreditohen nga një sulm tjetër. Meqenëse po flasim për një lojë ekonomike, peshat statistikore përkatëse mund të llogariten paraprakisht dhe thjesht të zëvendësohen komisionet me ato të rastësishme me shpërndarjen e duhur. Komisione të tilla probabiliste zbatohen jashtëzakonisht thjesht nëse blockchain ka një burim të besueshëm rastësie dhe nuk kërkon ndonjë llogaritje komplekse, duke e bërë jetën të vështirë si për balenat ashtu edhe për sibilat.
Në të njëjtën kohë, është e nevojshme të vazhdoni të mbani mend se kontrolli mbi një bit të vetëm në këtë rastësi ju lejon të mashtroni, duke zvogëluar dhe rritur probabilitetet përgjysmë, kështu që një PVRB e ndershme është komponenti më i rëndësishëm i protokolleve të tilla.
Ku mund të gjeni rastësi të duhur?
Në teori, përzgjedhja e drejtë e rastësishme në rrjetet e decentralizuara e bën pothuajse çdo protokoll të sigurt kundër marrëveshjeve të fshehta. Arsyetimi është mjaft i thjeshtë - nëse rrjeti bie dakord për një bit të vetëm 0 ose 1, dhe më pak se gjysma e pjesëmarrësve janë të pandershëm, atëherë, duke pasur parasysh përsëritjet e mjaftueshme, rrjeti është i garantuar të arrijë një konsensus për atë bit me një probabilitet fiks. Thjesht sepse një rastësi e sinqertë do të zgjedhë 51 nga 100 pjesëmarrës në 51% të rasteve. Por kjo është në teori, sepse... në rrjetet reale, për të siguruar një nivel të tillë sigurie si në artikuj, kërkohen shumë mesazhe midis hosteve, kriptografi komplekse me shumë kalime dhe çdo ndërlikim i protokollit shton menjëherë vektorë të rinj sulmi.
Kjo është arsyeja pse ne nuk shohim ende një PVRB rezistente të provuar në blockchains, i cili do të ishte përdorur për një kohë të mjaftueshme për t'u testuar nga aplikacione reale, auditime të shumta, ngarkesa dhe sigurisht, sulme reale, pa të cilat është e vështirë të quash një produkt vërtet i sigurt.
Sidoqoftë, ka disa qasje premtuese, ato ndryshojnë në shumë detaje, dhe njëra prej tyre patjetër do ta zgjidhë problemin. Me burimet moderne kompjuterike, teoria kriptografike mund të përkthehet mjaft zgjuar në aplikime praktike. Në të ardhmen, do të jemi të lumtur të flasim për implementimet PVRB: tani ka disa prej tyre, secila ka grupin e vet të vetive të rëndësishme dhe veçorive të zbatimit, dhe pas secilës ka një ide të mirë. Nuk ka shumë ekipe të përfshira në randomizim, dhe përvoja e secilit prej tyre është jashtëzakonisht e rëndësishme për të gjithë të tjerët. Shpresojmë që informacioni ynë do t'i lejojë ekipet e tjera të ecin më shpejt, duke marrë parasysh përvojën e paraardhësve të tyre.
Burimi: www.habr.com