Përshëndetje, Habr!
Në këtë artikull do të flas për gjenerimin e numrave të rastësishëm nga pjesëmarrës që nuk besojnë njëri-tjetrit. Si do të shohim më poshtë, është mjaft e thjeshtë të realizosh një gjenerator "të casi" të mirë, por për të krijuar një gjenerator shumë të mirë, është e vështirë.
Pse është e nevojshme të gjenerohen numra të rastësishëm për pjesëmarrësit që nuk besojnë njëri-tjetrit? Një nga fushat e përdorimit është aplikacionet e decentralizuara. Për shembull, një aplikacion që merr një bast nga një pjesëmarrës dhe ose dyfishon shumën me probabilitet 49%, ose e merr atë me 51%, do të funksionojë vetëm nëse mund të marrë një numër të rastësishëm pa paragjykim. Nëse një sulmues mund të ndikoje në rezultatin e punës së gjeneratorit të numrave të rastësishëm dhe madje të rritë pak shanset për të marrë pagesën në aplikacion, ai do të mund ta shkatërrojë lehtësisht atë.
Kur zhvillojmë një protokoll të shpërndarë për gjenerimin e numrave të rastësishëm, duam që ai të ketë tri veti:
Ai duhet të jetë i paanshëm. Me fjalë të tjera, asnjë pjesëmarrës nuk duhet të ndikojë në ndonjë mënyrë në rezultatin e gjeneratorit të numrave të rastësishëm.
Ai duhet të jetë i paparashikueshëm. Në fjalë të tjera, asnjë pjesëmarrës nuk duhet të ketë mundësinë të parashikojë cfarë numri do të gjenerohet (ose të nxjerrë ndonjë nga karakteristikat e tij) para se të gjenerohet.
Protokolli duhet të jetë i qëndrueshëm, domethënë i qëndrueshëm ndaj faktit që një përqindje e caktuar e pjesëmarrësve do të dalin nga rrjeti ose përpiqen me qëllim të ndalojnë protokollin.
Në këtë artikull ne do të shqyrtojmë dy qasje: RANDAO + VDF dhe një qasje të bazuar në kodet e fshirjes. Në pjesën tjetër do të shqyrtojmë detajisht qasjen e bazuar në nënshkrimet e pragut.
Por përpara se të fillojmë, le të shqyrtojmë një algoritëm të thjeshtë dhe të përdorur shpesh, i cili është i qëndrueshëm, i paparashikueshëm, por i anshëm.
RANDAO
RANDAO është një qasje shumë e thjeshtë dhe, për pasojë, mjaft e përdorur për marrjen e rastësisë. Të gjithë pjesëmarrësit e rrjetit së pari përzgjidhin një numër pseudorastësor në mënyrë lokale, pastaj çdo pjesëmarrës dërgon hash-in e numrit të zgjedhur. Më pas, pjesëmarrësit radhiten dhe zbulojnë numrat e zgjedhur dhe kryejnë operacionin 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 përpara se të zbulojmë numrat është i nevojshëm në mënyrë 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ë rastit.
Gjatë protokollit, pjesëmarrësit duhet të arrijnë dy herë një vendim të përbashkët (të ashtuquajturin konsensus): kur të fillojnë të zbulojnë numrat e zgjedhur dhe, për pasojë, të ndalojnë pranimin e hash-eve, dhe kur të përfundojnë pranimin e numrave të zgjedhur dhe të llogarisin numrin rastësor rezultues. Marrja e këtyre vendimeve mes pjesëmarrësve që nuk i besojnë njëri-tjetrit është një detyrë e vështirë, dhe ne do të kthehemi te kjo në artikujt e ardhshëm; në këtë artikull do të supozojmë se një algoritëm konsensusi është në dispozicion për ne.
Cilat nga karakteristikat që përmendëm më sipër të RANDAO-s janë të pranishme? Ai është i paparashikueshëm, ka të njëjtin qëndrushmëri si protokolli konsensus që e mbështet, por është i predispozuar. Konkretisht, një sulmues 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ë rezultatin. Ndërsa kjo nuk i lejon sulmuesit të përcaktojë në mënyrë të vetme rezultatin e gjeneratorit të numrave të rastit, ai 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ë reduktohet 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ë ndjeshëm më i vogël, algoritmi ende mbetet i predispozuar.
RANDAO + VDF
Një nga mënyrat për ta bërë RANDAO të paanshëm është si më poshtë: pasi të gjitha numrat të kenë u zbuluar, dhe XOR të jetë llogaritur, rezultati i tij jepet si hyrje në një funksion që kërkon shumë kohë për t'u llogaritur, por lejon të kontrollohet 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ë shpejtKy funksion quhet Funksion Verifikues vonesash, ose VDF. Nëse llogaritja e rezultatit përfundimtar merr më shumë kohë sesa faza e zbulimit të numrave, atëherë keqbërësi nuk do të jetë në gjendje ta parashikojë efektin e demonstrimit ose fshehjes së numrit të tij, dhe si rezultat do të humbë mundësinë për të ndikuar në rezultatin.
Zhvillimi i VDF-ve të mira është jashtëzakonisht i komplikuar. Kohët e fundit, janë bërë disa përparime, për shembull dhe të cilat e bënë VDF më praktik, dhe Ethereum 2.0 planifikon të përdorë RANDAO me VDF si burim të numrave të rastit në një afat të gjatë. Përveç faktit se ky qasje është e paparashikueshme dhe e paanshme, ai ka një avantazh shtesë, që është qëndrueshmëria, nëse të paktën dy pjesëmarrës janë të disponueshëm në rrjet (me kusht që protokolli i konsensusit të jetë i qëndrueshëm me një numër kaq të vogël pjesëmarrësish).
Sfidat më të mëdha të kësaj qasjeje janë të rregullohet VDF, në mënyrë që asnjë pjesëmarrës me pajisje shumë të shtrenjtë të specializuara të mos mund të llogarisë VDF-në deri në përfundimin e fazës së zbuluar. Idealisht, algoritmi duhet të ketë edhe një rezervë të konsiderueshme, le të themi, 10x. Në figurën më poshtë është shfaqur një sulm nga një pjesëmarrës, që ka një ASIC të specializuar, e cila i lejon atij të ekzekutojë VDF më shpejt se koha e caktuar për të zbuluar vërtetimin RANDAO. Ky pjesëmarrës mund të llogarisë ende rezultatin final duke përdorur ose pa numrin e tij, dhe më pas, në bazë të llogaritjeve, të vendosë nëse do ta tregojë atë apo jo.
Për familjen e përmendur më lart, performanca e ASIC-ve të specializuara mund të jetë më shumë se 100 herë më e lartë se ajo e pajisjeve normale. Kështu, nëse faza e zbulesës zgjat 10 sekonda, atëherë VDF, e llogaritur në një ASIC të tillë, 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ë zgjasë 100 x 100 sekonda = ~ 3 orë.
Fondacioni Ethereum planifikon të zgjidhë këtë problem duke krijuar ASIC-e të vetëfinancuara dhe të hapura. Sapo të ndodhi kjo, të gjithë protokollet e tjera gjithashtu mund të përfitojnë nga kjo teknologji, por deri atëherë, qasja RANDAO + VDF nuk do të jetë po aq e vlefshme për protokollet që nuk mund të investojnë në zhvillimin e ASIC-ve të tyre.
Shumë artikuj, video dhe informacion tjetër mbi VDF janë mbledhur në .
Përdorim kodi fshirës
Në këtë seksion do të shqyrtojmë protokollin për gjenerimin e numrave të rastësishëm, i cili përdor . Ai mund të përballojë deri në ⅓ të sulmuesve duke mbetur funksional, dhe lejon ekzistencën e deri në ⅔ të sulmuesve, para se ata të mund të parashikojnë ose ndikojnë në rezultat.
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 që të gjithë pjesëmarrësit lokalmente kanë një çelës privat dhe çelësat publikë të të gjithë pjesëmarrësve janë të njohur nga të gjithë:
Çdo pjesëmarrës lokalmente sajon një varg të gjatë, e ndan atë në 67 pjesë, krijon kode fshirëse për të marrë 100 pjesë, të tilla që çdo 67 është mjaftueshëm për të rikonstruktuar vargun, cakton secilën nga 100 pjesët njërit prej pjesëmarrësve dhe i enkripton ato me çelësin publik të po atij pjesëmarrësi. Pastaj, të gjitha pjesët e koduara publikohen.
Pjesëmarrësit përdorin një konsensus të caktuar për të arritur pajtim mbi grupe të koduara nga 67 pjesëmarrësit e caktuar.
Sapo konsensusi të arrihet, çdo pjesëmarrës merr pjesët e koduara në secilin nga grupet 67, të enkriptuara me çelësin e tyre publik, dekripton të gjitha ato pjesë dhe publikon të gjitha ato pjesë të dekriptuara.
Sa herë që 67 pjesëmarrës përfunduan hapin (3), të gjithë setet e përftuar mund të dekriptohen dhe rikuperohen plotësisht falë pronave të kodeve shlyese, dhe numri përfundimtar mund të merret si XOR i rreshtave fillestarë me të cilët filluan pjesëmarrësit në (1).
Mund të tregohesh se ky protokoll është i paanshëm dhe i paparashikueshëm. Numri rastësor rezultues përcaktohet pas arritjes së konsensusit, por askush nuk e di atë deri sa ⅔ e pjesëmarrësve të dekriptojnë pjesët e koduara me çelësin e tyre të hapur. Kështu, numri rastësor përcaktohet para se informata e mjaftueshme për rikuperimin e tij të publikohet.
Çfarë ndodh nëse në hapin (1) një nga pjesëmarrësit dërgon pjesë të koduara për pjesëmarrësit e tjerë, të cilat nuk janë një kod shlyes të saktë për ndonjë rresht? Pa ndryshime të tjera, pjesëmarrësit e ndryshëm ose nuk do të jenë në gjendje ta rikuperojnë fare rreshtin, ose do të rikuperojnë rreshta të ndryshëm, duke çuar në atë që pjesëmarrësit e ndryshëm do të marrin numra rastësorë të ndryshëm. Për ta parandaluar këtë, mund të bëhet e tillë: çdo pjesëmarrës, përveç pjesëve të koduara, gjithashtu llogarit 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ë konsensus, në hapin (2), pjesëmarrësit nuk pajtohen vetëm në shumë grupe, por në shumë rrënjë specifike të tillë pemësh (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 dy nga këto rrënjë tregohen gjatë konsensusit, vargu i tij nuk përfshihet në grupin rezultues). Pas konsensusit, do të kemi 67 vargje të koduara dhe rrënjët e tyre përkatëse të pemës Merkle, në mënyrë që të ketë të paktën 67 pjesëmarrës (nuk është e domosdoshme që ata të jenë të njëjtët që propozuan vargjet përkatëse), të cilët për çdo një nga 67 vargjet kanë një mesazh me një pjesë të kodit fshirës, dhe provën e përfshirjes së pjesës së tyre në pemën përkatëse Merkle.
Kur në hapin (4) një pjesëmarrës dekodifikon 67 pjesët për një varg të caktuar, dhe përpiqet të rikrijojë vargun origjinal, një nga opsionet mund të jetë:
Strën e rikuperohet, dhe nëse ajo pastaj kodifikohet përsëri me kodet fshijëse, dhe llogaritë pemën Merkle për aksionet e llogaritura lokalisht, rrënjën e përputhet me atë mbi të cilën është arritur konsensusi.
Strën e rikuperohet, por rrënjën e llogaritur lokalisht nuk përputhet me atë mbi të cilën është arritur konsensusi.
Strën nuk rikuperohet.
Është e lehtë të tregohet se nëse ndonjë nga pjesëmarrësit përjetojë variantin (1), atëherë të gjithë pjesëmarrësit do të përjetojnë variantin (1), dhe përndryshe, nëse ndonjë nga pjesëmarrësit përjeton variantin (2) ose (3), atëherë të gjithë pjesëmarrësit do të përjetojnë variantin (2) ose (3). Prandaj, për çdo strënë në grup, ose të gjithë pjesëmarrësit do ta rikuperojnë me sukses, ose të gjithë pjesëmarrësit nuk do të mund ta rikuperojnë. Pastaj, numri rastësor rezultues është XOR vetëm për ato strenja që pjesëmarrësit arritën të rikuperojnë.
Nënshkrimet kufizuese
Një qasje tjetër ndaj rastësisë është përdorimi i ashtuquajturëve nënshkrime BLS me prag. Një gjenerues numrash rastësorë i bazuar në nënshkrime me prag ka garanci të njëjta me algoritmin e mësipërm të bazuar në kodet që fshihen, por ka një asimptotikë dukshëm më të ulët të numrit të mesazheve që dërgohen në rrjet për çdo numër të gjeneruar.
Nënshkrimet BLS janë një konstruksion që lejon disa pjesëmarrës të krijojnë një nënshkrim të përbashkët për një mesazh. Këto nënshkrime shpesh përdoren për të kursyer hapësirë dhe kapacitet bande duke mos kërkuar shpërndarjen e disa nënshkrimeve.
Një përdorim i shpeshtë për nënshkrimet BLS në protokollet e blockchain, përveç gjenerimit të numrave të rastit, është nënshkrimi i blloqeve në protokollet BFT. Le të themi, 100 pjesëmarrës krijojnë blloqe dhe një bllok shpallet përfundimtar nëse 67 prej tyre e nënshkruajnë atë. Të gjithë ata mund të paraqesin pjesët e tyre të nënshkrimit BLS dhe të përdorin ndonjë algoritëm konsensusi për të arritur një marrëveshje për 67 nga ata, dhe pastaj t'i bashkojnë ato në një nënshkrim BLS të vetëm. Ç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 pavarësisht se zgjedhja e ndryshme e 67 pjesëmarrësve do të krijojë 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ë më pas duhet vetëm të marrin përmes rrjetit dhe të verifikojnë vetëm një nënshkrim për çdo bllok, në vend të 67, gjë që e ul ndjeshëm ngarkesën në rrjet.
Duket se nëse çelësat privatë që përdoren nga pjesëmarrësit gjenerohen në një mënyrë të caktuar, atëherë pavarësisht se cilat janë 67 nënshkrimet (ose më shumë, por asnjëherë më pak) të agreguara, nënshkrimi rezultues do të jetë i njëjtë. Kjo mund të përdoret si burim rastësie: pjesëmarrësit fillimisht bien dakord për një mesazh që do të nënshkruajnë (mund të jetë rezultati i RANDAO-s ose thjesht heksi i bllokut të fundit, në të vërtetë nuk ka rëndësi, përveç faktit që duhet të ndryshojë çdo herë dhe të jetë i miratuar), dhe krijojnë një nënshkrim BLS për të. Rezultati i gjenerimit do të jetë i papërcaktuar, derisa 67 pjesëmarrësit të ofrojnë pjesët e tyre, dhe pas kësaj, të dhënat e daljes janë tashmë të paracaktuara dhe nuk mund të varen nga veprimet e ndonjë pjesëmarrësi.
Kjo qasje ndaj rastësisë është e qëndrueshme, nëse të paktën ⅔ e pjesëmarrësve janë online dhe ndjekin protokollin, dhe është e paanshme dhe e paparashikueshme përderisa të paktën ⅓ e pjesëmarrësve ndjekin protokollin. Është e rëndësishme të theksohet se një sulmues që kontrollon më shumë se ⅓ por më pak se ⅔ të pjesëmarrësve mund ta ndalë protokollin, por nuk mund ta parashikojë ose ndikojë në rezultatin e tij.
Nënshkrimet prag për vete janë një temë shumë interesante. Në pjesën e dytë të artikullit do të shqyrtojmë në detaje se si funksionojnë ato, dhe se si duhet të gjenerohen çelësat e pjesëmarrësve që nënshkrimet prag të mund të përdoren si gjenerator numrash rastësorë.
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ë thjeshtësinë e zhvillimit dhe thjeshtësinë e përdorimit për përdoruesit e fundit.
Kodi i protokollit është i hapur, zbatimi ynë është shkruar në Rust dhe mund të gjendet .
Të shikoni si duket zhvillimi nën NEAR dhe të eksperimentoni në online-IDE mund të bëhet .
Të ndjekni të gjitha lajmet në gjuhën ruse mund të bëhet në dhe në , dhe në anglisht në zyrtare .
Shihemi së shpejti!
Burimi: habr.com
