Përshëndetje, Habr!
Në këtë artikull do të flas për gjenerimin e numrave pseudo-t rastësor nga pjesëmarrësit që nuk i besojnë njëri-tjetrit. Siç do të shohim më poshtë, të realizosh një gjenerator "gjithmonë" të mirë është mjaft e lehtë, por një gjenerator të shkëlqyer është e vështirë.
Pse na nevojitet në fakt të gjenerojmë numra të rastit për pjesëmarrësit që nuk i besojnë njëri-tjetrit? Një nga fushat e aplikimit është aplikacionet e decentralizuara. Për shembull, një aplikacion që pranon një bast nga një pjesëmarrës dhe ose dyfishon shumën me një probabilitet prej 49%, ose e merr me 51%, do të funksionojë vetëm nëse mund të marrë një numër të rastësor pa paragjykim. Nëse një sulmues mund të ndikojë në rezultatin e punës së gjeneratorit të numrave të rastit, dhe madje edhe të rrisë fares shanset për të marrë një pagesë në aplikacion, ai do të mund të zbrazë atë lehtë.
Kur zhvillojmë një protokoll të shpërndarë për gjenerimin e numrave të rastit, ne duam që ai të ketë tri veti:
Ai duhet të jetë pa paragjykim. Në fjalë të tjera, asnjë pjesëmarrës nuk duhet të ndikojë në ndonjë mënyrë në rezultatin e gjeneratorit të numrave të rastit.
Ai duhet të jetë i paparashikueshëm. Në fjalë të tjera, asnjë pjesëmarrës nuk duhet të ketë mundësinë të parashikojë se cili numër do të gjenerohet (ose të nxjerrë ndonjë nga vetitë e tij) para se ai të gjenerohet.
Protokolli duhet të jetë funksional, do të thotë të jetë i qëndrueshëm ndaj faktit që një përqindje e disa pjesëmarrësve të shkëputen nga rrjeti ose të përpiqen qëllimisht të ndalojnë protokollin.
Në këtë artikull, ne do të shqyrtojmë dy qasje: RANDAO + VDF dhe qasjen që bazohet në kodet fshirëse. Në pjesën tjetër do ta shqyrtojmë në detaje qasjen që bazohet në nënshkrimet me prag.
Por përpara se të fillojmë, le të shqyrtojmë një algoritëm të thjeshtë dhe mjaft të përdorur, i cili është funksional, i paparashikueshëm, por i paragjykuar.
RANDAO
RANDAO është një qasje shumë e thjeshtë dhe, për më tepër, mjaft e përdorur për të marrë rastësishmëri. Të gjithë pjesëmarrësit e rrjetit fillimisht zgjedhin lokalisht një numër pseudo-t rastësor, pastaj çdo pjesëmarrës dërgon një hash të numrit të zgjedhur. Më pas, pjesëmarrësit e zbulojnë numrat e zgjedhur njëri pas tjetrit, dhe kryejnë një operacion XOR mbi numrat e zbuluar, dhe rezultati i këtij operacioni bëhet rezultati i punës së protokollit.
Hapi i publikimit të hash-eve para se të zbulohet numrat është i nevojshëm, që sulmuesi të mos mund të zgjedhë numrin e tij pasi të ketë parë numrat e pjesëmarrësve të tjerë. Kjo do t'i jepte atij mundësinë për të përcaktuar në mënyrë të vetme rezultatin e gjeneratorit të numrave të rastësishëm.
Gjatë protokollit, pjesëmarrësit duhet të arrijnë dy herë në një marrëveshje të përbashkët (të ashtuquajturin konsensus): kur të fillojnë të zbulojnë numrat e zgjedhur dhe për pasojë të ndalen së pranuari hash-e, dhe kur të përfundojnë pranimin e numrave të zgjedhur dhe të llogarisin numrin e rastësishëm përfundimtar. Arritja e këtyre vendimeve midis pjesëmarrësve që nuk i besojnë njëri-tjetrit është një detyrë e vështirë, dhe ne do të kthehemi në të në artikujt në vazhdim; në këtë artikull do ta supozojmë se një algoritëm konsensusi është në dispozicion.
Cilat nga karakteristikat që përshkruam më sipër ka RANDAO? Ai është i paparashikueshëm, ka të njëjtin jetëgjatësi si protokolli i konsensusit në të cilin bazohet, por është i favorizuar. Në veçanti, sulmuesi mund të vëzhgojë rrjetin, dhe pasi pjesëmarrësit e tjerë të zbulojnë numrat e tyre, ai mund të llogarisë XOR-in e tyre dhe të vendosë nëse të zbulojë ose jo numrin e tij, për të ndikuar në rezultat. Ndërsa kjo nuk i lejon sulmuesit të përcaktojë në mënyrë të vetme rezultatin e gjeneratorit të numrave të rastësishëm, ende i jep atij 1 bit ndikimi. Dhe nëse sulmuesit kontrollojnë disa pjesëmarrës, numri i bitëve të kontrolluar do të jetë i barabartë me numrin e pjesëmarrësve nën kontrollin e tyre.
Ndikimi i sulmuesve mund të pakësohet ndjeshëm nëse kërkohet që pjesëmarrësit të zbulojnë numrat në rend. Atëherë, sulmuesi do të mund të ndikojë në rezultatin vetëm nëse zbulohet i fundit. Ndërsa ndikimi është shumë më i vogël, algoritmi ende është i favorizuar.
RANDAO + VDF
Një nga opsionet për ta bërë RANDAO të paanshëm është si në vijim: pas zbules së të gjithëve numrave dhe pas llogaritjes së XOR-it, rezultati i tij jepet si hyrje për një funksion që merr shumë kohë për t'u llogaritur, por lejon të verifikohet saktësia e llogaritjes shumë shpejt.
(vdf_output, vdf_proof) = VDF_compute(input) // kjo është shumë e ngadaltë
correct = VDF_verify(input, vdf_output, vdf_proof) // kjo është shumë e shpejtëKy funksion quhet Verifiable Delay Function, ose VDF. Nëse llogaritja e rezultatit përfundimtar zgjat më shumë se faza e zbulimit të numrave, atëherë një sulmues nuk do të jetë në gjendje të parashikojë efektin e demonstrimit ose fshehjes së numrit të tij, dhe për pasojë ai do të humbasë mundësinë për të ndikuar në rezultat.
Zhvillimi i një VDF të mirë është jashtëzakonisht i vështirë. Kohët e fundit janë bërë disa përparime, për shembull dhe e cila e bëri VDF më të aplikueshme në praktikë, dhe Ethereum 2.0 në afat të gjatë planifikon të përdorë RANDAO me VDF si burim të numrave të rastësishëm. Përveç faktit që ky qasje është e paparashikueshme dhe e paanshme, ajo ka një avantazh suplementar që përkatësia, nëse të paktën dy pjesëmarrës janë të disponueshëm në rrjet (në kushtet që protokolli i konsensusit të përdorur është i vlefshëm për të punuar me një numër kaq të vogël pjesëmarrësish).
Vështirësia më e madhe e këtij qasje është në përcaktimin e një VDF, në mënyrë që edhe një pjesëmarrës me pajisje të specializuara shumë të shtrenjta të mos jetë në gjendje ta llogarisë atë deri në përfundimin e fazës së zbulimit. Në mënyrë ideale, algoritmi duhet të ketë madje edhe një rezervë të rëndësishme, le të themi, 10x. Në figurën më poshtë është shfaqur një sulm nga një pjesëmarrës që ka një ASIC të specializuar, i cili i lejon atij të ekzekutojë VDF më shpejt se koha e caktuar për zbulimin e konfirmimit RANDAO. Ky pjesëmarrës ende mund të llogarisë rezultatin përfundimtar duke përdorur ose jo numrin e tij, dhe pas kësaj, në bazë të llogaritjeve, mund të zgjedhë ta tregojë atë ose jo.
Për familjen e sipërpërmendur të VDF-ve, performanca e një ASIC të specializuar mund të jetë më shumë se 100 herë më e lartë se ajo e pajisjeve normale. Pra, nëse faza e zbulimit zgjat 10 sekonda, atëherë VDF, e llogaritur në një të tillë ASIC, duhet të zgjasë më shumë se 100 sekonda për të pasur një rezervë sigurie 10-fish, dhe, kështu, e njëjta VDF e llogaritur në pajisje normale duhet të kushtojë 100 x 100 sekonda = ~ 3 orë.
Fondi Ethereum planifikon të zgjidhë këtë problem përmes krijimit të ASIC publikë falas. Sapo kjo të ndodhi, të gjitha protokollet e tjera gjithashtu mund të përfitojnë nga kjo teknologji, por deri në atë kohë, qasja RANDAO + VDF nuk do të jetë po aq e qëndrueshme për protokollet që nuk mund të investojnë në zhvillimin e ASIC-it të tyre të vet.
Shumë artikuj, video dhe informacione të tjera mbi VDF janë mbledhur në .
Përdorim kodet fshirëse
NĂ« kĂ«tĂ« seksion ne do tĂ« shqyrtojmĂ« protokollin e gjenerimit tĂ« numrave tĂ« rastit qĂ« pĂ«rdor . Ai mund tĂ« pĂ«rballojĂ« deri nĂ« â tĂ« sulmuesve, duke mbetur i qĂ«ndrueshĂ«m, dhe lejon ekzistencĂ«n e deri nĂ« â sulmuesve, pĂ«rpara se ata tĂ« mund tĂ« parashikojnĂ« ose ndikojnĂ« nĂ« rezultatin.
Ideja kryesore e protokollit është si më poshtë. Për thjeshtësi, le të supozojmë se ka saktësisht 100 pjesëmarrës. Le të supozojmë gjithashtu se të gjithë pjesëmarrësit lokalisht kanë një çelës privat, dhe çelësat publikë të të gjithë pjesëmarrësve janë të njohur nga të gjithë pjesëmarrësit:
Ădo pjesĂ«marrĂ«s lokalisht krijon njĂ« varg tĂ« gjatĂ«, e ndan atĂ« nĂ« 67 pjesĂ«, krijon kode fshirĂ«se pĂ«r tĂ« marrĂ« 100 aksione, tĂ« tilla qĂ« çdo 67 janĂ« tĂ« mjaftueshme pĂ«r tĂ« rikonstruktuar vargun, i cakton secilĂ«s nga 100 aksionet njĂ« nga pjesĂ«marrĂ«sit dhe i kodon ato me çelĂ«sin publik tĂ« tĂ« njĂ«jtit pjesĂ«marrĂ«s. Pastaj tĂ« gjitha aksionet e koduara publikohen.
Pjesëmarrësit përdorin një konsensus, për të arritur një marrëveshje mbi setet e koduara nga 67 pjesëmarrës konkret.
Sapo konsensusi të arrihet, çdo pjesëmarrës merr aksionet e koduara në secilin nga 67 setet, të koduara me çelësin e tyre publik, i dekriptojnë të gjitha këto aksione dhe publikojnë të gjitha këto aksione të dekriptuara.
Sapo 67 pjesëmarrës përfundojnë hapat (3), të gjitha setet e miratuara mund të dekodohen plotësisht dhe të rikonstruktohen për shkak të pronave të kodit fshirës, dhe numri përfundimtar mund të merret si XOR i vargjeve fillestare, me të cilat pjesëmarrësit filluan në (1).
ĂshtĂ« e mundur tĂ« tregohet se ky protokoll Ă«shtĂ« i paanshĂ«m dhe i paparashikueshĂ«m. Numri i rastĂ«sishĂ«m rezultues Ă«shtĂ« i pĂ«rcaktuar pasi tĂ« arrihet konsensusi, por askush nuk e di atĂ« derisa â e pjesĂ«marrĂ«sve tĂ« dekodojnĂ« pjesĂ«t e koduara me çelĂ«sat e tyre publikĂ«. Pra, numri i rastĂ«sishĂ«m Ă«shtĂ« pĂ«rcaktuar pĂ«rpara publikimit tĂ« informacionit tĂ« mjaftueshĂ«m pĂ«r rikuperimin e tij.
ĂfarĂ« ndodh nĂ«se nĂ« hapin (1) njĂ« nga pjesĂ«marrĂ«sit u dĂ«rgon pjesĂ«marrĂ«sve tĂ« tjerĂ« pjesĂ« tĂ« koduara qĂ« nuk janĂ« njĂ« kod fshirĂ«s i saktĂ« i njĂ« vargu tĂ« caktuar? Pa ndryshime tĂ« tjera, pjesĂ«marrĂ«sit e ndryshĂ«m nuk do tĂ« jenĂ« nĂ« gjendje tĂ« rikuperojnĂ« vargun fare, ose do tĂ« rikuperojnĂ« vargje tĂ« ndryshme, qĂ« do tĂ« rezultojĂ« nĂ« numra tĂ« ndryshĂ«m rastĂ«sorĂ« pĂ«r pjesĂ«marrĂ«s tĂ« ndryshĂ«m. PĂ«r tĂ« parandaluar kĂ«tĂ«, mund tĂ« bĂ«het si mĂ« poshtĂ«: çdo pjesĂ«marrĂ«s, pĂ«rveç pjesĂ«ve tĂ« koduara, llogarit gjithashtu tĂ« gjitha kĂ«tyre pjesĂ«ve, dhe çdo pjesĂ«marrĂ«s dĂ«rgon si pjesĂ«n e koduar, ashtu edhe rrĂ«njĂ«n e pemĂ«s Merkle, dhe provĂ«n e pĂ«rfshirjes sĂ« pjesĂ«s nĂ« pemĂ«n Merkle. NĂ« konsensusin nĂ« hapin (2), pjesĂ«marrĂ«sit nuk bien dakord thjesht pĂ«r shumĂ« grupe, por pĂ«r shumĂ« rrĂ«njĂ« specifike tĂ« kĂ«tyre pemĂ«ve (nĂ«se ndonjĂ« pjesĂ«marrĂ«s largohet nga protokolli dhe dĂ«rgon rrĂ«njĂ« tĂ« ndryshme tĂ« pemĂ«s Merkle pĂ«r pjesĂ«marrĂ«s tĂ« ndryshĂ«m, dhe kĂ«to dy rrĂ«njĂ« tregohen gjatĂ« konsensusit, vargu i tij nuk pĂ«rfshihet nĂ« grupin rezultues). Pas konsensusit, ne do tĂ« kemi 67 vargje tĂ« koduara dhe rrĂ«njĂ«t pĂ«rkatĂ«se tĂ« pemĂ«s Merkle, tĂ« tilla qĂ« ka tĂ« paktĂ«n 67 pjesĂ«marrĂ«s (nuk Ă«shtĂ« e nevojshme qĂ« tĂ« jenĂ« ata tĂ« njĂ«jtĂ« qĂ« sugjeruan vargjet pĂ«rkatĂ«se), pĂ«r tĂ« cilat pĂ«r çdo nga 67 vargjet ka njĂ« mesazh me pjesĂ«n e kodit fshirĂ«s dhe provĂ«n e pĂ«rfshirjes sĂ« pjesĂ«s sĂ« tyre nĂ« pemĂ«n Merkle tĂ« pĂ«rshtatshme.
Kur në hapin (4) një pjesëmarrës dekodifikon 67 pjesë për një varg të caktuar, dhe përpiqet të rikuperojë vargun origjinal, është e mundur një nga variantet e mëposhtme:
Vargu rikuperohet, dhe nëse më pas kodifikohet përsëri me kodet fshirëse dhe llogaritet pemën Merkle për pjesët e llogaritura lokal, rrënja përputhet me atë mbi të cilën është arritur konsensusi.
Vargu rikuperohet, por rrënja e llogaritur lokal nuk përputhet me atë mbi të cilën është arritur konsensusi.
Vargu nuk rikuperohet.
ĂshtĂ« e lehtĂ« tĂ« tregohet se nĂ«se pĂ«r tĂ« paktĂ«n njĂ« pjesĂ«marrĂ«s ndodhi mĂ«nyra (1), atĂ«herĂ« pĂ«r tĂ« gjithĂ« pjesĂ«marrĂ«sit do tĂ« ndodhĂ« mĂ«nyra (1), dhe pĂ«rkundrazi, nĂ«se pĂ«r tĂ« paktĂ«n njĂ« pjesĂ«marrĂ«s ndodhi mĂ«nyra (2) ose (3), atĂ«herĂ« pĂ«r tĂ« gjithĂ« pjesĂ«marrĂ«sit do tĂ« ndodhĂ« mĂ«nyra (2) ose (3). Pra, pĂ«r çdo rresht nĂ« grup, ose tĂ« gjithĂ« pjesĂ«marrĂ«sit e rikthejnĂ« me sukses, ose tĂ« gjithĂ« pjesĂ«marrĂ«sit nuk e rikthejnĂ« dot. Numri i rastĂ«sishĂ«m qĂ« rezulton Ă«shtĂ« XOR vetĂ«m i atyre rreshtave qĂ« pjesĂ«marrĂ«sit arritĂ«n t'i rikthenin.
NĂ«nshkrimet e pragut
Një qasje tjetër për rastësinë është përdorimi i ashtuquajturave nënshkrime BLS. Gjeneratori i numrave të rastësishëm, i bazuar në nënshkrimet e pragut, ka të njëjtat garanci si algoritmi i mësipërm i bazuar në kodet e fshirjes, por ka një asimptotikë ndjeshëm më të ulët të numrit të mesazheve të dërguara për çdo numër të gjeneruar.
NĂ«nshkrimet BLS janĂ« njĂ« konstrukcion qĂ« lejon disa pjesĂ«marrĂ«s tĂ« krijojnĂ« njĂ« nĂ«nshkrim tĂ« pĂ«rbashkĂ«t pĂ«r njĂ« mesazh. KĂ«to nĂ«nshkrime pĂ«rdoren shpesh pĂ«r tĂ« kursyer hapĂ«sirĂ« dhe bandwidth duke mos kĂ«rkuar shpĂ«rndarjen e disa nĂ«nshkrimeve.Â
PĂ«rdorimi i shpeshtĂ« pĂ«r nĂ«nshkrimet BLS nĂ« protokollet e blockchain, pĂ«rveç gjenerimit tĂ« numrave tĂ« rastĂ«sishĂ«m, Ă«shtĂ« nĂ«nshkrimi i bllokĂ«ve nĂ« protokollet BFT. Le tĂ« themi se 100 pjesĂ«marrĂ«s krijojnĂ« blloqe, dhe blloku konsiderohet i pĂ«rfunduar nĂ«se 67 nga ata e nĂ«nshkruajnĂ« atĂ«. TĂ« gjithĂ« ata mund tĂ« paraqesin pjesĂ«t e nĂ«nshkrimit tĂ« tyre BLS dhe tĂ« pĂ«rdorin njĂ« algoritĂ«m konsensusi pĂ«r tĂ« pajtuar 67 nga ata, dhe mĂ« pas t'i bashkojnĂ« ato nĂ« njĂ« nĂ«nshkrim tĂ« vetĂ«m BLS. Ădo 67 (ose mĂ« shumĂ«) pjesĂ« mund tĂ« pĂ«rdoren pĂ«r tĂ« krijuar nĂ«nshkrimin pĂ«rfundimtar, i cili do tĂ« varet nga cilat 67 nĂ«nshkrime janĂ« bashkuar, dhe prandaj mund tĂ« ndryshojĂ«, por megjithatĂ« zgjedhja e ndryshme e 67 pjesĂ«marrĂ«sve do tĂ« formonte njĂ« nĂ«nshkrim tĂ« ndryshĂ«m, çdo nĂ«nshkrim i tillĂ« do tĂ« ishte njĂ« nĂ«nshkrim i saktĂ« pĂ«r bllokun. PjesĂ«marrĂ«sit e tjerĂ« pastaj kanĂ« mjaftueshĂ«m tĂ« marrin pĂ«rmes rrjetit dhe tĂ« verifikojnĂ« vetĂ«m njĂ« nĂ«nshkrim pĂ«r çdo bllok, nĂ« vend tĂ« 67, qĂ« ndjeshĂ«m zvogĂ«lon ngarkesĂ«n nĂ« rrjet.
Duket se nëse çelësat e mbyllur që përdorin pjesëmarrësit gjenerohen në një mënyrë të caktuar, atëherë pavarësisht nga cila janë 67 nënshkrime (ose më shumë, por asnjëherë më pak), nënshkrimi që rezulton do të jetë i njëjtë. Kjo mund të përdoret si burim rastësie: pjesëmarrësit së pari bien dakord për një mesazh të caktuar që do të nënshkruajnë (kjo mund të jetë rezultati i RANDAO-s ose thjesht hash i bllokut të fundit, në të vërtetë nuk ka rëndësi, mjafton të ndryshojë çdo herë dhe të jetë e rënë dakord), dhe krijojnë një nënshkrim BLS për të. Rezultati i gjenerimit do të jetë i paparashikueshëm, derisa 67 pjesëmarrës të ofrojnë pjesët e tyre, dhe pas kësaj, daljet tashmë janë të paracaktuara dhe nuk mund të varen nga veprimet e ndonjë pjesëmarrësi.
Ky qasje ndaj rastĂ«sisĂ« Ă«shtĂ« e qĂ«ndrueshme, nĂ«se sĂ« paku â e pjesĂ«marrĂ«sve janĂ« online dhe ndjekin protokollin, dhe Ă«shtĂ« e paanshme dhe e paparashikueshme derisa sĂ« paku â e pjesĂ«marrĂ«sve tĂ« ndjekin protokollin. ĂshtĂ« e rĂ«ndĂ«sishme tĂ« theksohet se njĂ« sulmues, i cili kontrollon mĂ« shumĂ« se â , por mĂ« pak se â e pjesĂ«marrĂ«sve, mund tĂ« ndalojĂ« protokollin, por nuk mund tĂ« parashikojĂ« ose tĂ« ndikojĂ« nĂ« daljen e tij.
Nënshkrimet me prag vetë janë një temë shumë interesante. Në pjesën e dytë të artikullit ne do të shqyrtojmë në detaje se si ato funksionojnë, dhe si duhet të gjenerohen çelësat e pjesëmarrësve për t'u përdorur nënshkrimet me prag si një gjenerator numrash të rastësishëm.
Në përfundim
Ky artikull është i pari në një seri artikujsh teknikë në blog . NEAR është një protokoll blockchain dhe platformë për zhvillimin e aplikacioneve të decentralizuara me fokus në lehtësinë e zhvillimit dhe lehtësinë e përdorimit për përdoruesit fundorë.
Kodi i protokollit është i hapur, realizimi ynë është i shkruar në Rust, mund të gjendet .
Të shikoni se si duket zhvillimi nën NEAR, dhe të eksperimentoni në online IDE, mund të .
Të ndiqni të gjitha lajmet në rusisht mund të bëhet në dhe në , ndërsa në anglisht në zyrtarin .
Shihemi së shpejti!
Burimi: habr.com
