A është e mundur të gjenerojmë numra të rastësishëm nëse nuk i besojmë njëri-tjetrit? Pjesa 1

Hej Habr!

Në këtë artikull do të flas për gjenerimin e numrave pseudo të rastësishëm nga pjesëmarrësit që nuk i besojnë njëri-tjetrit. Siç do të shohim më poshtë, zbatimi i një gjeneratori "pothuajse" të mirë është mjaft i thjeshtë, por një gjenerator shumë i mirë është i vështirë.

Pse është e nevojshme të gjenerohen numra të rastësishëm midis pjesëmarrësve që nuk i besojnë njëri-tjetrit? Një fushë aplikimi janë 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 49%, ose heq me një probabilitet 51%, do të funksionojë vetëm nëse mund të marrë në mënyrë të paanshme një numër të rastësishëm. Nëse një sulmues mund të ndikojë në rezultatin e gjeneruesit të numrave të rastësishëm dhe madje të rrisë pak shanset e tij për të marrë një pagesë në aplikacion, ai do ta shkatërrojë lehtësisht atë.

Kur hartojmë një protokoll të gjenerimit të numrave të rastësishëm të shpërndarë, duam që ai të ketë tre veti:

1. Ai duhet të jetë i paanshëm. Me fjalë të tjera, asnjë pjesëmarrës nuk duhet të ndikojë në asnjë mënyrë në rezultatin e gjeneruesit të numrave të rastësishëm.

2. Ai duhet të jetë i paparashikueshëm. Me fjalë të tjera, asnjë pjesëmarrës nuk duhet të jetë në gjendje të parashikojë se cili numër do të gjenerohet (ose të konkludojë ndonjë nga vetitë e tij) përpara se të gjenerohet.

3. Protokolli duhet të jetë i zbatueshëm, domethënë, rezistent ndaj faktit që një përqindje e caktuar e pjesëmarrësve shkëputen nga rrjeti ose përpiqen qëllimisht të ndalojnë protokollin.

Në këtë artikull do të shikojmë dy qasje: RANDAO + VDF dhe qasjen e kodeve të fshirjes. Në pjesën tjetër, ne do të shqyrtojmë në detaje qasjen e bazuar në nënshkrimet e pragut.

Por së pari, le të shohim një algoritëm të thjeshtë dhe të përdorur zakonisht që është i zbatueshëm, i paparashikueshëm, por i njëanshëm.

RANDAO

RANDAO është një qasje shumë e thjeshtë dhe për këtë arsye mjaft e përdorur për të gjeneruar rastësi. Të gjithë pjesëmarrësit e rrjetit fillimisht zgjedhin një numër pseudorandom, më pas secili pjesëmarrës dërgon një hash të numrit të zgjedhur. Më pas, pjesëmarrësit me radhë zbulojnë numrat e tyre të zgjedhur dhe kryejnë një operacion XOR në numrat e zbuluar, dhe rezultati i këtij operacioni bëhet rezultat i protokollit.

Hapi i publikimit të hasheve përpara zbulimit të numrave ë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 lejonte atij të përcaktojë praktikisht në mënyrë të vetme prodhimin e gjeneratorit të numrave të rastësishëm.

Gjatë rrjedhës së protokollit, pjesëmarrësit duhet të arrijnë në një vendim të përbashkët (të ashtuquajturin konsensus) dy herë: kur të fillojnë të zbulojnë numrat e zgjedhur, dhe për këtë arsye të ndalojnë pranimin e hasheve, dhe kur të ndalojnë pranimin e numrave të zgjedhur dhe llogaritjen e rastësishme që rezulton. numri. Marrja e vendimeve të tilla midis pjesëmarrësve që nuk i besojnë njëri-tjetrit nuk është një detyrë e lehtë në vetvete dhe ne do t'i kthehemi kësaj në artikujt e ardhshëm; në këtë artikull do të supozojmë se një algoritëm i tillë konsensusi është i disponueshëm për ne.

Cilat nga vetitë që përshkruam më sipër ka RANDAO? Ai është i paparashikueshëm, ka të njëjtin vitalitet si protokolli themelor i konsensusit, por është i njëanshëm. Në mënyrë të veçantë, 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 do të zbulojë ose jo numrin e tij për të ndikuar në rezultat. Ndërsa kjo e pengon sulmuesin që të përcaktojë vetëm rezultatin e gjeneratorit të numrave të rastësishëm, megjithatë i jep atij 1 bit ndikim. Dhe nëse sulmuesit kontrollojnë disa pjesëmarrës, atëherë numri i biteve që ata kontrollojnë do të jetë i barabartë me numrin e pjesëmarrësve nën kontrollin e tyre.

Ndikimi i sulmuesve mund të reduktohet shumë duke kërkuar që pjesëmarrësit të tregojnë numrat sipas renditjes. Atëherë sulmuesi do të jetë në gjendje të ndikojë në rezultatin vetëm nëse ai hapet i fundit. Ndërsa ndikimi është dukshëm më i vogël, algoritmi është ende i njëanshëm.

RANDAO+VDF

Një mënyrë për ta bërë RANDAO të paanshëm është kjo: pasi të zbulohen të gjithë numrat dhe të llogaritet XOR, rezultati i tij futet në hyrjen e një funksioni, i cili kërkon shumë kohë për t'u llogaritur, por ju lejon të kontrolloni korrektësinë e llogaritja shumë shpejt.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Ky funksion quhet Funksioni i Vonesës së Verifikueshme, ose VDF. Nëse llogaritja e rezultatit përfundimtar zgjat më shumë se faza e zbulimit të numrave, atëherë sulmuesi nuk do të jetë në gjendje të parashikojë efektin e shfaqjes ose fshehjes së numrit të tij, dhe për këtë arsye ai do të humbasë mundësinë për të ndikuar në rezultat.

Zhvillimi i VDF-ve të mira është jashtëzakonisht i vështirë. Kohët e fundit ka pasur disa përparime, p.sh. этот и kjo, gjë që e bëri VDF më praktike në praktikë, dhe Ethereum 2.0 planifikon të përdorë RANDAO me VDF si një burim numrash të rastësishëm në terma afatgjatë. Përveç faktit që kjo qasje është e paparashikueshme dhe e paanshme, ajo ka përfitimin e shtuar të të qenit e zbatueshme nëse të paktën dy pjesëmarrës janë të disponueshëm në rrjet (duke supozuar se protokolli i konsensusit i përdorur është i zbatueshëm kur kemi të bëjmë me një numër kaq të vogël pjesëmarrësish).

Sfida më e madhe e kësaj qasjeje është vendosja e VDF-së në mënyrë të tillë që edhe një pjesëmarrës me pajisje të specializuara shumë të shtrenjta nuk do të jetë në gjendje të llogarisë VDF-në përpara përfundimit të fazës së zbulimit. Në mënyrë ideale, algoritmi duhet të ketë edhe një diferencë të konsiderueshme sigurie, të themi 10x. Figura më poshtë tregon një sulm nga një aktor që ka një ASIC të specializuar që e lejon atë të ekzekutojë një VDF më shpejt se koha e caktuar për të zbuluar konfirmimin RANDAO. Një pjesëmarrës i tillë ende mund të llogarisë rezultatin përfundimtar duke përdorur ose jo duke përdorur numrin e tij, dhe më pas, bazuar në llogaritjen, të zgjedhë nëse do ta shfaqë atë apo jo.

Për familjen VDF të përmendur më lart, performanca e një ASIC të dedikuar mund të jetë 100+ herë më e lartë se hardueri konvencional. Pra, nëse faza e vendosjes zgjat 10 sekonda, atëherë VDF-ja e llogaritur në një ASIC të tillë duhet të marrë më shumë se 100 sekonda për të pasur një diferencë sigurie 10x, dhe kështu e njëjta VDF e llogaritur në pajisjen e mallrave duhet të marrë 100x 100 sekonda = ~ 3 orë.

Fondacioni Ethereum planifikon ta zgjidhë këtë problem duke krijuar ASIC-et e veta falas të disponueshme publikisht. Pasi të ndodhë kjo, të gjitha protokollet e tjera gjithashtu mund të përfitojnë nga kjo teknologji, por deri atëherë qasja RANDAO+VDF nuk do të jetë aq e zbatueshme për protokollet që nuk mund të investojnë në zhvillimin e ASIC-ve të tyre.

Shumë artikuj, video dhe informacione të tjera rreth VDF janë mbledhur në këtë faqe.

Ne përdorim kode fshirjeje

Në këtë seksion, ne do të shikojmë një protokoll gjenerimi të numrave të rastësishëm që përdor fshirja e kodeve. Mund të tolerojë deri në ⅓ sulmues ndërkohë që mbetet i zbatueshëm dhe lejon deri në ⅔ sulmues të ekzistojnë përpara se të mund të parashikojnë ose ndikojnë në rezultatin.

Ideja kryesore e protokollit është si më poshtë. Për thjeshtësi, le të supozojmë se janë saktësisht 100 pjesëmarrës. Le të supozojmë gjithashtu se të gjithë pjesëmarrësit në nivel lokal kanë një çelës privat dhe çelësat publikë të të gjithë pjesëmarrësve janë të njohur për të gjithë pjesëmarrësit:

1. Çdo pjesëmarrës vjen me një varg të gjatë, e ndan atë në 67 pjesë, krijon kode fshirjeje për të marrë 100 aksione të tilla që çdo 67 të mjaftojë për të rikuperuar vargun, ia cakton secilin prej 100 aksioneve njërit prej pjesëmarrësve dhe i kodon ato me çelësi publik i të njëjtit pjesëmarrës. Më pas publikohen të gjitha aksionet e koduara.

2. Pjesëmarrësit përdorin një lloj konsensusi për të arritur marrëveshje mbi grupet e koduara nga 67 pjesëmarrës të veçantë.

3. Pasi të arrihet konsensusi, secili pjesëmarrës merr aksionet e koduara në secilin prej 67 grupeve të koduara me çelësin e tyre publik, deshifron të gjitha këto aksione dhe publikon të gjitha aksionet e tilla të deshifruara.

4. Pasi 67 pjesëmarrës të kenë përfunduar hapin (3), të gjitha grupet e dakorduara mund të deshifrohen dhe rindërtohen plotësisht për shkak të vetive të kodeve të fshirjes, dhe numri përfundimtar mund të merret si një XOR i rreshtave fillestarë me të cilët pjesëmarrësit filluan në (1) .

Ky protokoll mund të tregohet i paanshëm dhe i paparashikueshëm. Numri i rastësishëm që rezulton përcaktohet pasi arrihet konsensusi, por askush nuk i dihet derisa ⅔ e pjesëmarrësve të deshifrojnë pjesët e koduara me çelësin e tyre publik. Kështu, numri i rastësishëm përcaktohet përpara se të publikohet informacioni i mjaftueshëm për ta rindërtuar atë.

Çfarë ndodh nëse në hapin (1) njëri prej pjesëmarrësve u dërgon pjesëmarrësve të tjerë aksione të koduara që nuk janë kodi i saktë i fshirjes për disa vargje? Pa ndryshime shtesë, pjesëmarrës të ndryshëm ose nuk do të jenë në gjendje ta rikuperojnë fare vargun, ose do të rikuperojnë vargje të ndryshme, gjë që do të rezultojë në marrjen e një numri të ndryshëm të rastësishëm nga pjesëmarrës të ndryshëm. Për ta parandaluar këtë, mund të bëni sa më poshtë: secili pjesëmarrës, përveç aksioneve të koduara, llogarit edhe Pema Merkla të gjitha këto aksione dhe i dërgon secilit pjesëmarrës si pjesën e koduar, ashtu edhe rrënjën e pemës merkle, si dhe dëshminë e përfshirjes së pjesës në pemën merkle. Në konsensusin në hapin (2), pjesëmarrësit atëherë jo vetëm bien dakord për një grup grupesh, por për një grup rrënjësh specifike të pemëve të tilla (nëse ndonjë pjesëmarrës ka devijuar nga protokolli dhe ka dërguar rrënjë të ndryshme pemësh merkle te pjesëmarrës të ndryshëm, dhe dy rrënjë të tilla tregohen gjatë konsensusit, rreshti i tij nuk përfshihet në grupin e rezultateve). Si rezultat i konsensusit, do të kemi 67 linja të koduara dhe rrënjët përkatëse të pemës merkle të tilla që të jenë të paktën 67 pjesëmarrës (jo domosdoshmërisht të njëjtët që propozuan linjat përkatëse), të cilët për secilën nga 67 rreshtat kanë një mesazh me një pjesë të kodit të fshirjes dhe një provë e shfaqjes së pjesës së tyre në pemën përkatëse u zbeh.

Kur në hapin (4) pjesëmarrësi deshifron 67 rrahje për një varg të caktuar dhe përpiqet të rindërtojë vargun origjinal prej tyre, një nga opsionet është e mundur:

1. Vargu restaurohet dhe nëse më pas kodohet përsëri me fshirje dhe pema Merkle llogaritet për aksionet e llogaritura në nivel lokal, rrënja përkon me atë për të cilën është arritur konsensusi.

2. Rreshti është restauruar, por rrënja e llogaritur në nivel lokal nuk përputhet me atë në të cilën është arritur konsensusi.

3. Rreshti nuk është restauruar.

Është e lehtë të tregohet se nëse opsioni (1) ka ndodhur për të paktën një pjesëmarrës më lart, atëherë opsioni (1) ka ndodhur për të gjithë pjesëmarrësit, dhe anasjelltas, nëse opsioni (2) ose (3) ka ndodhur për të paktën një pjesëmarrës, atëherë për të gjithë pjesëmarrësit do të ndodhë opsioni (2) ose (3). Kështu, për çdo rresht në grup, ose të gjithë pjesëmarrësit do ta rikuperojnë atë me sukses, ose të gjithë pjesëmarrësit do të dështojnë ta rikuperojnë atë. Numri i rastësishëm që rezulton është atëherë një XOR i vetëm rreshtave që pjesëmarrësit ishin në gjendje të rikuperonin.

Nënshkrimet e pragut

Një qasje tjetër ndaj rastësisë është përdorimi i atyre që quhen nënshkrime të pragut BLS. Një gjenerues numrash të rastësishëm i bazuar në nënshkrimet e pragut ka saktësisht të njëjtat garanci si algoritmi i bazuar në kodin e fshirjes, i përshkruar më sipër, por ka një numër dukshëm më të ulët asimptotik të mesazheve të dërguara përmes rrjetit për çdo numër të gjeneruar.

Nënshkrimet BLS janë një dizajn që lejon shumë 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ën dhe gjerësinë e brezit duke mos kërkuar që të dërgohen nënshkrime të shumta. 

Një aplikim i zakonshëm për nënshkrimet BLS në protokollet blockchain, përveç gjenerimit të numrave të rastësishëm, është nënshkrimi i bllokut në protokollet BFT. Le të themi se 100 pjesëmarrës krijojnë blloqe dhe një bllok konsiderohet përfundimtar nëse 67 prej tyre e nënshkruajnë atë. Ata të gjithë mund të dorëzojnë pjesët e tyre të nënshkrimit BLS dhe të përdorin një algoritëm konsensusi për të rënë dakord për 67 prej tyre dhe më pas t'i bashkojnë ato në një nënshkrim BLS. Çdo 67 (ose më shumë) pjesë mund të përdoret për të krijuar nënshkrimin përfundimtar, i cili do të varet se cilat janë kombinuar 67 nënshkrime dhe për këtë arsye mund të ndryshojnë, megjithëse zgjedhje të ndryshme nga 67 pjesëmarrësit do të krijojnë një nënshkrim të ndryshëm, çdo nënshkrim i tillë do të jetë i vlefshëm. nënshkrim për bllokun. Pjesëmarrësit e mbetur atëherë duhet të marrin dhe verifikojnë vetëm një nënshkrim për bllok, në vend të 67, në rrjet, gjë që redukton ndjeshëm ngarkesën në rrjet.

Rezulton se nëse çelësat privatë që përdorin pjesëmarrësit gjenerohen në një mënyrë të caktuar, atëherë pavarësisht se cilat 67 nënshkrime (ose më shumë, por jo më pak) janë grumbulluar, nënshkrimi që rezulton do të jetë i njëjtë. Kjo mund të përdoret si një burim rastësie: pjesëmarrësit fillimisht bien dakord për një mesazh që do të nënshkruajnë (kjo mund të jetë rezultati i RANDAO ose thjesht hash-i i bllokut të fundit, nuk ka shumë rëndësi për sa kohë që ndryshon çdo herë dhe është konsistente) dhe krijoni një nënshkrim BLS për të. Rezultati i gjenerimit do të jetë i paparashikueshëm derisa 67 pjesëmarrës të japin pjesët e tyre, dhe pas kësaj produkti është tashmë i paracaktuar dhe nuk mund të varet nga veprimet e asnjë pjesëmarrësi.

Kjo qasje ndaj rastësisë është e zbatueshme për sa kohë që të paktën ⅔ e pjesëmarrësve në internet ndjekin protokollin, dhe është e paanshme dhe e paparashikueshme për sa kohë që 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 të ndalojë protokollin, por nuk mund të parashikojë ose të ndikojë në daljen e tij.

Vetë nënshkrimet e pragut janë një temë shumë interesante. Në pjesën e dytë të artikullit, ne do të analizojmë në detaje se si funksionojnë ato dhe se si saktësisht është e nevojshme të gjenerohen çelësat e pjesëmarrësve në mënyrë që nënshkrimet e pragut të mund të përdoren si një gjenerues i numrave të rastësishëm.

Në përfundim

Ky artikull është i pari në një seri artikujsh teknikë të blogut NEAR. NEAR është një protokoll dhe platformë blockchain për zhvillimin e aplikacioneve të decentralizuara me theks në lehtësinë e zhvillimit dhe lehtësinë e përdorimit për përdoruesit fundorë.

Kodi i protokollit është i hapur, zbatimi ynë është shkruar në Rust, mund të gjendet këtu.

Mund të shihni se si duket zhvillimi për NEAR dhe të eksperimentoni në IDE në internet këtu.

Ju mund të ndiqni të gjitha lajmet në Rusisht në grupi i telegramit dhe grup në VKontakte, dhe në anglisht në zyrtar eksitim.

Shihemi se shpejti!

Burimi: www.habr.com