Numra të rastësishëm dhe rrjete të decentralizuara: aplikimi praktik

Hyrje

«Generimi i numrave të rastësishëm është tepër i rëndësishëm për ta lënë në dorë të fatit»
Robert Cavyu, 1970

Ky artikull është kushtuar përdorimit praktik të zgjidhjeve që përdorin gjenerimin kolektiv të numrave të rastësishëm në një mjedis të paqartë. Nëse e përmbledhim — si dhe për çfarë përdoret rastësia në bllokçenet, dhe pak rreth se si të dallojmë një “rastësi të mirë” nga një “rastësi të keqe”. Gjenerimi i një numri të vërtetë rastësor është një problem shumë i komplikuar edhe në një kompjuter të vetëm, dhe është studiuar prej kohësh nga kriptografët. Ndërsa në rrjetet e decentralizuara, gjenerimi i numrave të rastësishëm është edhe më i komplikuar dhe i rëndësishëm.

Së fundmi, në rrjetet ku pjesëmarrësit nuk i besojnë njëri-tjetrit, mundësia për të gjeneruar një numër të pahtushëm rastësor lejon zgjidhjen efektive të shumë problemeve të rëndësishme dhe përmirëson ndjeshëm skemat ekzistuese. Për më tepër, lojërat e fatit dhe lotaritë nuk janë aspak qëllimi numër një, siç mund të duket fillimisht për lexuesin e pakëndshëm.

Gjenerimi i numrave të rastësishëm

Kompjuterët nuk dinë të krijojnë numra të rastësishëm vetvetiu; për këtë u kërkohet ndihma nga jasht. Një kompjuter mund të marrë një vlerë të rastit duke përdorur, për shembull, lëvizjet e miut, sasinë e memories së përdorur, rrymat parazite në kontaktet e procesorit dhe shumë burime të tjera, të quajtur burime entropie. Vetë këto vlera nuk janë krejtësisht të rastësishme, pasi ato ndodhen brenda një gamë të caktuar ose kanë një natyrë parashikueshmërie. Për të bërë që këto numra të shndërrohen në numra vërtetë të rastësishëm në një gamë të caktuar, u aplikohen transformime kriptografike, për të marrë vlera pseudorastësore të shpërndara njëtrajtësisht nga vlerat e burimeve të entropisë. Vlerat e marra quhen pseudorastësore, pasi ato nuk janë vërtet të rastësishme, por janë prodhuar në mënyrë deterministe nga entropia. Çdo algoritëm kriptografik i mirë, në procesin e enkriptimit të të dhënave, prodhon ciphertext që statistikorisht duhet të jenë të padallueshëm nga një sekuencë e rastësishme, kështu që për prodhimin e rastësisë mund të merret një burim entropie që siguron vetëm një riprodhim të mirë dhe parashikueshmëri të vlerave, edhe në gamat e vogla; pjesa tjetër e punës për shpërndarjen dhe përzierjen e bixhive në vlerën përfundimtare e merr përsipër algoritmi i enkriptimit.

Për të përfunduar këtë shpjegim të shkurtër, do të theksoj se gjenerimi i numrave të rastësishëm edhe në një pajisje është një nga shtyllat e sigurimit të të dhënave tona. Numrat e rastësishëm të gjeneruar përdoren për të vendosur lidhje të siguruara në rrjete të ndryshme, për të krijuar çelësa kriptografikë, për balancimin e ngarkesës, kontrollin e integritetit dhe për shumë aplikime të tjera. Siguria e shumë protokolleve varet nga mundësia për të gjeneruar një rastësor të besueshëm dhe të papërcaktueshëm nga jashtë, për ta ruajtur atë dhe për ta mbajtur sekret deri në hapin tjetër të protokollit, përndryshe siguria do të vihet në rrezik. Një sulm ndaj gjeneratorit të numrave të rastësishëm është jashtëzakonisht i rrezikshëm dhe rrezikon menjëherë të gjithë software-in që përdor gjenerimin e rastësorëve.

Të gjitha këto duhet t'i dini, nëse keni kaluar një kurs bazë mbi kriptografinë, prandaj le të vazhdojmë me rrjetet decentralizuara.

Rastësor në blockchain

Së pari, do të flas për blockchain-et me mbështetje për kontratat inteligjente, sepse ato mund të shfrytëzojnë plotësisht mundësitë që ofron një rastësi të kalibruar cilësore. Më tej, për shkak të shkurtësisë, unë do t'i referohem kësaj teknologjie si “Publicly Verifiable Random Beacons” ose PVRB. Duke qenë se blockchain-et janë rrjete, informacionin e të cilës mund ta verifikojë çdo anëtar, një pjesë kyçe e emrit është “Publicly Verifiable”, pra, kushdo mund, përmes llogaritjeve, të marrë prova se numri të cilin e ka publikuar blockchain-i ka këto vetitë:

• Rezultati duhet të ketë një shpërndarje që provon të jetë uniforme, pra të bazohet në kriptografinë e qëndrueshme që provohet.
• Nuk është e mundur të kontrolloni asnjë nga bitët e rezultatit. Si pasojë, rezultati nuk mund të parashikohet paraprakisht.
• Nuk është e mundur të sabotosh protokollin e gjenerimit përmes mos pjesëmarrjes në protokoll ose duke e ngarkuar rrjetin me mesazhe sulmuese.
• Të gjitha të mësipërmet duhet të jenë të forta ndaj komplotit të një numri të pranueshëm të pjesëmarrësve të pandershëm në protokoll (për shembull 1/3 e pjesëmarrësve).

Cdo mundësi e një grupi minor nën marrëveshje për të prodhuar një rastësi të kontrolluar çift/tek — është një hapësirë në sigurim. Cdo mundësi e një grupi për të ndaluar lëshimin e rastësisë — është një hapësirë në sigurim. Në përgjithësi, ka shumë probleme, dhe ky është një detyrë e vështirë…

Duket se aplikimi më i rëndësishëm për PVRB është lojërat e ndryshme, llotaritë dhe çdo formë tjetër të bixhozit në blockchain. Në të vërtetë, kjo është një fushë e rëndësishme, por rastësia në blockchain ka aplikime edhe më të rëndësishme. Le të shqyrtojmë ato.

Algoritmet e konsensusit

PVRB ka organizimi i konsensusit rrjetor ka një rëndësi të madhe. Transaksionet në blockchain janë të mbrojtura nga nënshkrimet elektronike, prandaj, "sulmi në transaksion" është gjithmonë përfshirja/hoqja e një transaksioni nga një bllok (ose nga disa blloqe). Detyra kryesore e algoritmit të konsensusit është të arrijë një marrëveshje mbi rendin e këtyre transaksioneve dhe mbi rendin e blloqeve që përfshijnë këto transaksione. Një pronë e nevojshme për blockchain të vërtetë është finaliteti — mundësia që rrjeti të arrijë një marrëveshje se sajoja deri në bllokun e finalizuar është përfundimtare dhe asnjëherë nuk do të përjashtohet për shkak të shfaqjes së një fork-u të ri. Zakonisht, që të arrijmë marrëveshjen se një bllok është i vlefshëm dhe, më e rëndësishmja, final, kërkohet të mblidhen nënshkrime nga shumica e prodhuesve të bllokut (më pas BP — block-producers), gjë që kërkon minimalisht të dërgohet sajoja e blloqeve te të gjithë BP, dhe nënshkrimet të shpërndahen ndërmjet të gjithë BP. Me rritjen e numrit të BP, numri i mesazheve të nevojshme në rrjet rritet eksponencialisht, prandaj, algoritmet e konsensusit që kërkojnë finalitet, të përdorura për shembull në konsensusin pBFT të Hyperledger, nuk punojnë me shpejtësinë e duhur, duke filluar që nga disa dhjetëra BP, duke kërkuar një numër të madh lidhjesh.

Nëse në rrjet ka një PVRB të pakontestueshëm dhe të ndershëm, atëherë, madje edhe në një afrim të thjeshtë, mund të zgjidhni një nga prodhuesit e bllokut dhe ta emëroni atë "lider" për një raund të protokollit. Nëse kemi N prodhues bllokesh, nga të cilët M: M > 1/2 N janë të ndershëm, nuk censurojnë transaksionet dhe nuk ndërtojnë forka të zinxhirit me qëllim për të kryer sulmin "double spend", atëherë përdorimi i një PVRB të pakontestueshëm të shpërndarë në mënyrë të barabartë do të lejojë zgjedhjen e një lideri të ndershëm me probabilitet M / N (M / N > 1/2). Nëse çdo lider caktohet një interval të vetin të kohës, gjatë së cilës ai mund të prodhojë një bllok dhe të verifikojë zinxhirin, dhe këto intervale janë të barabarta në kohë, atëherë zinxhiri i blloqeve të ND-së së ndershme do të jetë më i gjatë se zinxhiri i formuar nga ND-të keqdashëse, dhe algoritmi i konsensusit që mbështetet në gjatësi do të hidhte thjesht "të keqen". Ky parim i ndarjes së kvanteve të barabarta të kohës për çdo ND u aplikua për herë të parë në Graphene (parardhësi i EOS) dhe lejon shumicën e blloqeve të mbyllen me një nënshkrim, çka e ul ndjeshëm ngarkesën në rrjet dhe e bën këtë konsensus të funksionojë shumë shpejt dhe me stabilitet. Megjithatë, rrjetet EOS tani janë të detyruara të përdorin blloqe speciale (Blloku i fundit të pakthyeshëm), të cilat konfirmohen nga nënshkrime 2/3 nga ND-të. Këto blloqe shërbejnë për të siguruar përfundimin (pashmangshmëria e shfaqjes së një ndarjeje të zinxhirit që fillon para Bllokut të fundit të pakthyeshëm).

Gjithashtu, në implementimet reale, skema e protokollit është më e komplikuar - votimet për blloqet e propozuara bëhen në disa etapa, për të mbështetur funksionimin e rrjetit në rastin e humbjes së blloqeve dhe problemeve me rrjetin, por edhe duke marrë parasysh këtë, algoritmet e konsensusit që përdorin PVRB kërkojnë në mënyrë të dukshme më pak mesazhe midis BP, që i bën ato më të shpejta se tradita PВFT, ose variacione të ndryshme të tij.

Përfaqësuesi më i spikatur i këtyre algoritmeve: Ouroboros nga ekipi i Cardano, i cili, siç është shpallur, ka qëndrueshmëri të provuar matematikore ndaj pranisë së marrëveshjeve midis BP.

Në Ouroboros PVRB përdoret për të përcaktuar atë që quhet "BP schedule" — një orar sipas të cilit çdo BP i caktohet një slot temporal për publikimin e një bloku. Një përfitim i madh i përdorimit të PVRB është "barazia" e plotë e BP-ve (sipas madhësive të bilanceve të tyre). Ndershmëria e PVRB garanton që BP-të e këqija nuk mund të kontrollojnë orarin e slotëve temporal, dhe prandaj nuk mund të manipulojnë zinxhirin, duke përgatitur paraprakisht dhe analizuar degët e zinxhirit; për të zgjedhur një degë, është mjaft të mbështetesh thjesht në gjatësi e zinxhirit, pa përdorur taktika të sofistikuara për të llogaritur "përdorshmërinë" e BP-ve dhe "pesha" e blloqeve të tij.

Në të gjitha rastet kur në një rrjet të decentralizuar duhet të zgjidhet një pjesëmarrës rastësor, pothuajse gjithmonë zgjedhja më e mirë do të jetë PVRB, në vend të një varianti të përcaktuar, bazuar, për shembull, në hash-in e bllokut. Pa PVRB, mundësia për të ndikuar në zgjedhjen e pjesëmarrësit çon në shfaqjen e sulmeve, në të cilat sulmuesi mund, duke zgjedhur nga disa opsione të ardhshme, të zgjedhë pjesëmarrësin e ardhshëm të korruptuar ose menjëherë disa, për të siguruar një pjesë më të madhe në vendimmarrje. Përdorimi i PVRB diskreditohet këto lloje sulmesh.

Shkallëzimi dhe balancimi i ngarkesës

PVRB mund të sjellë përfitime të konsiderueshme gjithashtu në detyra për zvogëlimin e ngarkesës, shkallëzimin e pagesave. Fillimisht, ka kuptim të njihet me artikullin Rivesta "Biletet Elektronike të Llotarisë si Mikropagë". Thellësia e konceptit është se, në vend që të bëni 100 pagesa nga 1c nga paguesi te marrës, mund të luani një llotari të ndershme me një çmim prej 1$ = 100c, ku paguesi në çdo pagesë prej 1c i kalon bankës një nga 100 "biletat e tij të llotarisë". Një nga këto bileta fiton 1$ për bankën, dhe ky është bileti që merrësi mund ta regjistrojë në blockchain. Më e rëndësishmja, 99 bileta të tjera kalohen midis marrësit dhe paguesit pa ndihmën e tretë, përmes një kanali privat dhe me shpejtësinë e nevojshme. Një përshkrim i mirë i protokollit të bazuar në këtë skemë në rrjetin Emercoin mund të lexoni. këtu.

Kjo skemë ka disa probleme, për shembull, marrësi mund të ndalojë shërbimin për paguesin menjëherë pas marrjes së biletës fituese, por për shumë aplikacione të veçanta, si tarifimi për minutë ose abonimet elektronike për shërbime, mund të injorohen. Kërkesa kryesore, natyrisht, është ndershmëria e llotarive të zhvilluara, dhe për të realizuar këtë, PVRB është krejtësisht e nevojshme.

Zgjedhja e një pjesëmarrësi të rastësishëm është jashtëzakonisht e rëndësishme edhe për protokollet e sharding, të cilat kanë si qëllim shkallëzimin horizontal të zinxhirit të bllokëve, duke lejuar që BP të ndryshëm të përpunojnë vetëm skopin e tyre të transaksioneve. Kjo është një detyrë shumë sfiduese, sidomos në çështjet e sigurisë kur bashkohen shardet. Zgjedhja e ndershme e BP të rastësishëm për të emëruar ata përgjegjës për një shard të veçantë, ashtu si në algoritmet e konsensusit — është gjithashtu një detyrë PVRB. Në sistemet e centralizuara, shardet emërohen nga një balancues, i cili vetëm llogarit hash nga kërkesa dhe e dërgon tek përfituesi i nevojshëm. Në blockchain, mundësia për të ndikuar në këtë emërim mund të çojë në një sulm në konsensus. Për shembull, përmbajtja e transaksioneve mund të kontrollohet nga një sulmues, ai mund të kontrollojë se cilat transaksione hyjnë në shardin e kontrolluar prej tij dhe të manipulojë zinxhirin e bllokëve në të. Diskutimi për problemin e përdorimit të numrave të rastit për detyrat e sharding në Ethereum mund të lexohet. këtu
Sharding është një nga detyrat më ambicioze dhe serioze në fushën e blockchain, zgjidhja e saj do të lejojë ndërtimin e rrjeteve të decentralizuara me performancë dhe volum fantastik. PVRB është vetëm njё nga blloket e rëndësishme për zgjidhjen e saj.

Lojëra, protokolle ekonomike, arbitrazh

Roli i numrave të rastësishëm në industrinë e lojërave është shumë i rëndësishëm. Përdorimi i qartë në kazinotë online, dhe ai i padukshëm gjatë llogaritjes së efekteve të veprimeve të ndryshme të lojtarit — të gjitha këto janë probleme jashtëzakonisht të komplikuara për rrjetet e decentralizuara, ku nuk ka mundësi të besosh në një burim qendror të rastësisë. Por, zgjedhja e rastësishme mund të zgjidhë shumë probleme ekonomike dhe të ndihmojë në ndërtimin e protokolleve më të thjeshta dhe më efektive. Supozoni se në protokollin tonë ka mosmarrëveshje në lidhje me pagesën për ndonjë shërbim të lirë, dhe këto mosmarrëveshje ndodhin mjaft rrallë. Në këtë rast, nëse ka një PVRB të pa kontestueshëm, klientët dhe shitësit mund të bien dakord për një zgjidhje të rastësishme të mosmarrëveshjeve, por me një probabilitet të caktuar. Për shembull, me një probabilitet prej 60% fiton klienti, ndërsa me 40% fiton shitësi. Ky qasje, që në dukje duket absurde, lejon zgjidhjen automatike të mosmarrëveshjeve me një ndarje të saktë fitimesh/ Humbjesh, që i kënaq të dyja palët pa asnjë përfshirje të një pale të tretë dhe pa humbje kohe të panevojshme. Për më tepër, raporti i probabiliteteve mund të jetë dinamik dhe të varet nga disa variabël globalë. Për shembull, nëse kompania po zhvillohet mirë, ka një numër të ulët të mosmarrëveshjeve dhe një kthim të lartë, kompania mund të zhvendosë automatikisht probabilitetin e zgjidhjes së mosmarrëveshjeve në favor të klientit, për shembull 70/30 ose 80/20, dhe anasjelltas, nëse mosmarrëveshjet po marrin shumë mjete dhe janë mashtruese ose të papërshtatshme, mund të zhvendosë probabilitetin në anën tjetër.

Një numër i madh protokollesh interesantë të decentralizuara, si regjistrat e kuratuar me tokene, tregjet e parashikimit, kurbat e lidhjes dhe shumë të tjera, përbëjnë lojëra ekonomike ku shpërblehet sjellja e mirë dhe ndëshkohet ajo e keqe. Ato shpesh hasin probleme sigurie, mbrojtja e të cilave shkon në kundërshtim me njëra-tjetrën. Ajo që është e mbrojtur nga sulmet e "kitëve" me miliarda tokene, është e prekshme nga sulmet e mijëra llogarive me bilance të vogla. Masat e marra kundër një sulmi, siç janë tarifat jo lineare, të krijuara për të bërë të pafavorshme veprimin e stake të madh, zakonisht diskreditohen nga një sulm tjetër. Duke qenë se bëhet fjalë për një lojë ekonomike, pesha përkatëse statistikore mund të llogaritet paraprakisht, dhe thjesht të zëvendësohen tarifat me ato të rastësishme me shpërndarjen përkatëse. Këto tarifa probabilistike realizohen shumë lehtë, nëse në blockchain ekziston një burim i besueshëm rastësie dhe nuk kërkojnë ndonjë llogaritje të komplikuar, duke e komplikuar jetën si kitëve ashtu edhe sybil-ave.
Në këtë mënyrë, është e rëndësishme të mbani mend se kontrolli mbi një bit të vetëm në këtë rast mund të manipuloj, duke reduktuar dhe rritur probabilitetet në dyfish. Kështu, një PVRB i ndershëm është një përbërës kyç i këtyre protokolleve.

Ku të gjejmë rastin e duhur?

Në teori, një përzgjedhje e rastësishme e ndershme në rrjetet e decentralizuara siguron siguri të provueshme për pothuajse çdo protokoll nga komplotet. Justifikimi është mjaft i thjeshtë — nëse një rrjet bie dakord për një bit 0 ose 1 dhe midis pjesëmarrësve më pak se gjysma janë të pazakontë, atëherë pas një numri të mjaftueshëm iteracionesh, rrjeti me siguri do të arrijë konsensus në lidhje me këtë bit me një probabilitet të caktuar. Thjesht sepse rasti i ndershëm do të zgjedhë 51 nga 100 pjesëmarrës në 51% të rasteve. Por kjo është në teori, sepse në rrjete reale, për të siguruar një nivel të tillë sigurie si në artikuj, kërkohen shumë mesazhe midis hosteve, kriptografi e komplikuar dhe çdo kompleksitet që shtohet në protokoll menjëherë sjell horizonte të reja sulmesh.
Pikërisht për këtë arsye, ne akoma nuk shohim në blockchain-et një PVRB të provuar si të qëndrueshëm, i cili do të kishte qenë në përdorim për një kohë mjaft të gjatë për të kaluar provat e aplikacioneve reale, auditeve të shumta, ngarkesave, dhe sigurisht, sulmeve reale, pa të cilat është e vështirë ta quash një produkt me të vërtetë të sigurt.

Megjithatë, ekzistojnë disa qasje premtuese, të cilat ndryshojnë në shumë detaje, dhe ndonjëra prej tyre me siguri do të zgjidhë këtë problem. Me burimet aktuale të llogaritjes, teoritë e kriptografisë janë në gjendje të shndërrohen në aplikime praktike. Në vazhdim, ne do të jemi të lumtur të flasim për implementimet e PVRB: tani ka disa prej tyre, secila ka një grup të veçantë të veçorive dhe karakteristikave në realizim, dhe pas secilës qëndron një ide e mirë. Rëndom mund të merret nga pak ekipe, dhe përvoja e secilës prej tyre është jashtëzakonisht e rëndësishme për të gjitha të tjerat. Shpresojmë se informacioni ynë do t'u ndihmojë ekipeve të tjera të avancojnë më shpejt, duke marrë parasysh përvojën e paraardhësve.

Burimi: habr.com