Përshëndetje, Habr!
Në Në artikujt e mëparshëm, ne diskutuam se përse mund të jetë e nevojshme të gjenerohen numra rastësorë për pjesëmarrësit që nuk i besojnë njëri-tjetrit, cilat janë kërkesat që i parashtrohen këtyre gjeneratorëve të numrave rastësorë, dhe shqyrtuam dy qasje për implementimin e tyre.
Në këtë pjesë të artikullit ne do të shqyrtojmë në detaje një qasje tjetër që përdor nënshkrime prag.
Pak kriptografi
Për të kuptuar sesi funksionojnë nënshkrimet prag, duhet të kuptoni pak kriptografi bazë. Ne do të përdorim dy koncepte: skalare, ose thjesht numra, të cilët do t'i përcaktojmë me shkronja të vogla (x, y) dhe pika në një kurbë eliptike, të cilat do t'i përcaktojmë me shkronja të mëdha.
Për të kuptuar bazën e nënshkrimeve prag, nuk është e nevojshme të kuptohet si funksionojnë kurbat eliptike, përveç disa gjërave bazike:
Pikat në kurbën eliptike mund të shtohen dhe të shumëzohen me skalare (shumëzimi me skalar do ta paraqesim si xG, megjithëse nota Gx shqiptohet shpesh në literaturë). Rezultati i mbledhjes dhe shumëzimit me skalar është një pikë në kurbën eliptike.
Duke ditur vetëm pikën G dhe produktin e saj me skalarin xG nuk mund të llogaritet x.
Ne gjithashtu do të përdorim konceptin e polinomit p(x) me gradë k-1. Në veçanti, ne do të përdorim pasurinë e mëposhtme të polinomëve: nëse ne e dimë vlerën p(x) për çdo k të ndryshëm x (dhe nuk kemi ndonjë informacion tjetër rreth p(x)), ne mund të llogarisim p(x) për çdo tjetër x.
Është interesante që për çdo polinom p(x) dhe një pikë të caktuar në kurbë G, duke ditur vlerën p(x)G për çdo k të vlerave të ndryshme x, gjithashtu mund të llogarisim p(x)G për çdo x.
Kjo informacion mjafton për të thelluar në detajet se si funksionojnë nënshkrimet prag, dhe si mund të përdoren për të gjeneruar numra rastësorë.
Gjeneratori i numrave rastësorë me nënshkrime prag
Supozoni se n pjesëmarrësit duan të gjenerojnë një numër rastësor, dhe ne duam që pjesëmarrja e çdo k prej tyre të mjaftojë për të gjeneruar numrin, por që keqbërësit, të cilët kontrollojnë k-1 ose më pak pjesëmarrës, të mos mundin të parashikojnë ose ndikojnë në numrin e gjeneruar.
Supozoni se ekziston një polinom p(x) me gradë k-1, që pjesëmarrësi i parë e di p(1), pjesëmarrësi i dytë e di p(2), dhe kështu me radhë (n-ti e di p(n)). Po gjithashtu lejohet që për një pikë të përcaktuar më parë, G të gjithë e dinë p(x)G për të gjitha vlerat x. Ne do ta quajmë p(i) “komponent privat” ii -të pjesëmarrësi (sepse vetëm i-i pjesëmarrës e njeh atë), dhe p(i)G “komponent publik” ii -të pjesëmarrësi (sepse të gjithë pjesëmarrësit e dinë atë). Siç e mbani mend, njohja p(i)G nuk është e mjaftueshme për të rikuperuar p(i).
Krijimi i një polinomi të tillë në mënyrë që vetëm i -ti-i pjesëmarrës dhe askush tjetër ta dijë komponentin e tij privat – kjo është pjesa më e vështirë dhe interesante e protokollit, dhe ne do ta shqyrtojmë më poshtë. Për tani le lejojmë që një polinom i tillë të kemi, dhe të gjithë pjesëmarrësit e dinë komponentet e tyre private.
Si mund ta përdorim një polinom të tillë për të gjeneruar një numër rastësor? Në fillim na nevojitet një varg që më parë nuk është përdorur si hyrje për gjeneratorin. Në rastin e blockchain, hash-i i bllokut të fundit h është një kandidat i mirë për një varg të tillë. Le të supozojmë se pjesëmarrësit duan të krijojnë një numër rastësor, duke përdorur h si seed. Së pari, pjesëmarrësit konvertojnë h në një pikë në kurbë duke përdorur çdo funksion të përcaktuar më parë:
H = scalarToPoint(h)
Pastaj çdo pjesëmarrës i llogarit dhe publikon Hi = p(i)H, të cilin ata mund ta bëjnë, sepse ata e dinë p(i) dhe H. Zbulimi Hi nuk i lejon pjesëmarrësit e tjerë të rikuperojnë komponentin privat itë -të pjesëmarrësi, dhe për këtë arsye një set i vetëm i komponentëve privat mund të përdoret nga blloku në bllok. Kështu, algoritmi i shtrenjtë i krijimit të polinomit të shqiptuar më poshtë, duhet të zbatohen vetëm një herë.
Kur k pjesëmarrësit e zbuluar Hi = p(i)H, të gjithë mund të llogaritin Hx = p(x)H për të gjithë x falë pronësisë së polinomëve, të cilat ne i diskutuam në seksionin e kaluar. Në këtë moment, të gjithë pjesëmarrësit llogarisin H0 = p(0)H, dhe kjo është numri rastësor rezultues. Vini re se askush nuk e di p(0), dhe kështu mënyra e vetme për të llogaritur p(0)H – është interpolimi p(x)H, çfarë është e mundur vetëm kur k vlerat p(i)H janë të njohura. Zbulimi i çdo sasie më të vogël p(i)H nuk jep asnjë informacion për p(0)H.
Gjeneratori i mësipërm ka të gjitha karakteristikat që ne duam: sulmuesit, që kontrollojnë vetëm k-1 pjesëmarrës, ose më pak, nuk kanë asnjë informacion dhe ndikim mbi rezultatin, ndërsa çdo k pjesëmarrës mund të llogarisë numrin rezultues, dhe çdo nëngrup prej k pjesëtarët gjithmonë do të çojnë në të njëjtin rezultat për të njëjtin seed.
Ka një problem, të cilin e kemi anashkaluar me kujdes më lart. Që të funksionojë interpolimi, është e rëndësishme që vlera Hi që publikoi çdo pjesëmarrës i të jetë me të vërtetë e barabartë me p(i)H. Duke qenë se askush përveç i-it pjesëmarrës nuk di p(i), askush përveç i -ti-it pjesëmarrës nuk mund të verifikojë se Përshëndetje vërtet është llogaritur saktësisht, dhe pa ndonjë provë kriptografike të saktësisë Hi, një sulmues mund të publikojë çdo vlerë si Përshëndetje, dhe të ndikojë arbitralisht në daljen e gjeneratorit të numrave të rastit.:
Vlera të ndryshme H_1, të dërguara nga pjesëmarrësi i parë, çojnë në H_0 rezultat të ndryshëm.
Ka të paktën dy mënyra për të provuar saktësinë Hi, ne do t'i shqyrtojmë ato pasi të analizojmë gjenerimin e polinomit.
Gjenerimi i polinomit
Në seksionin e kaluar supozuam se kemi një polinom të tillë p(x) me gradë k-1 që pjesëmarrësi i e di p(i), dhe askush tjetër nuk ka informacione të tjera për këtë vlerë. Në seksionin e ardhshëm do të jetë e nevojshme që për një pikë të parapërcaktuar G të gjithë të dinë p(x)G për të gjithë x.
Në këtë seksion ne do të supozojmë se çdo pjesëmarrës ka një çelës privat lokal xi, të tillë që çelësi publik i tij Xi është i njohur.
Një protokoll i mundshëm për gjenerimin e polinomit është si më poshtë:
Çdo pjesëmarrës i lokalisht krijon një polinom të rastësishëm pi(x) të gradës k-1. Ata pastaj i dërgojnë çdo pjesëmarrësi j vlerën pi(j), e enkriptuar me çelësin publik Xj. Kështu vetëm i -tii dhe j-i pjesëmarrës e dinë pi(j). Pjesëmarrësi i po ashtu publikon publikisht pi(j)G për të gjithë j nga 1 në k përfshirë.
Të gjithë pjesëmarrësit përdorin një konsensus për të zgjedhur k pjesëmarrësit, të cilët polinomët e tyre do të përdoren. Duke qenë se disa pjesëmarrës mund të jenë offline, ne nuk mund të presim deri sa të gjithë n pjesëmarrësit të publikojnë polinomët. Rezultati i këtij hapi është një grup Z i përbërë nga të paktën k polinomësh, të krijuar në hapin (1).
Pjesëmarrësit sigurohen që vlerat e njohura prej tyre pi(j) korrespondon me pi(j)G që është shpallur publikisht. Pas këtij hapi, në Z duhen mbetur vetëm polinomët, për të cilët komponenti privat pi(j) korrespondon me pi(j)G që është shpallur publikisht.
Çdo pjesëmarrës j i llogarit p(j) si shumën pi(j) për të gjithë i në Z. Çdo pjesëmarrës gjithashtu llogarit të gjitha vlerat p(x)G si shumën pi(x)G për të gjithë i në Z.
Vini re se p(x) – kjo është vërtet një polinom i gradës k-1, sepse kjo është shuma e individëve të veçantë pi(x), çdo njëri prej të cilëve është një polinom i gradës k-1. Pastaj, vini re se ndërsa çdo pjesëmarrës j e di p(j), ata nuk kanë asnjë informacion mbi p(x) për x ≠ j. Në të vërtetë, për të llogaritur këtë vlerë, ata duhet të dinë të gjitha pi(x), dhe për sa kohë që një pjesëmarrës j nuk di të paktën një nga polinomët e zgjedhur, ata nuk kanë informacion të mjaftueshëm mbi p(x).
Ky është i gjithë procesi i gjenerimit të polinomëve, i nevojshëm në seksionin e kaluar. Hapat 1, 2 dhe 4 më sipër kanë një implementim të mjaftueshëm të qartë. Megjithatë, hapi 3 nuk është aq triviale.
Specifikisht, na nevojitet të jemi në gjendje të provojmë se të koduarit pi(j) vërtet i korrespondon publikimeve pi(j)G që është shpallur publikisht. Nëse nuk e bëjmë këtë fakt, një sulmues i mund të dërgojë plehra në vend të pi(j) për pjesëmarrësin j, dhe pjesëmarrësi j nuk do të jetë në gjendje të marrë vlerën e vërtetë pi(j), dhe nuk do të mund të llogarisë komponentin e tij privat.
Ka një protokoll kriptografik që lejon krijimin e një mesazhi të mëtejshëm proofi(j), i tillë që çdo pjesëmarrës, duke pasur një vlerë të caktuar e, dhe gjithashtu proofi(j) dhe pi(j)G, mund të sigurohet lokalisht se e është vërtet pi(j), i koduar me çelësin e pjesëmarrësit j. Fatkeqësisht, madhësia e këtij dëshmimi është jashtëzakonisht e madhe, dhe duke pasur parasysh se duhet të publikohen O(nk) të tilla dëshmi, përdorimi i tyre për këtë qëllim nuk do të jetë i mundur.
Në vend që të provojmë se pi(j) përputhet me pi(j)G ne mund të ndajmë në protokollin e gjenerimit të polinomëve një periudhë të gjatë, gjatë së cilës të gjithë pjesëmarrësit kontrollojnë të koduarit e marrë pi(j), dhe nëse mesazhi i çkoduar nuk përputhet me publikun pi(j)G, ata publikojnë një provë kriptografike se mesazhi i koduar që morën është i gabuar. Të provojmë se mesazhi jo përputhet me pi(G) është shumë më e lehtë sesa të provojmë se ai përputhet. Duhet të theksohet se kjo kërkon që çdo pjesëmarrës të shfaqet në rrjet të paktën një herë brenda periudhës së caktuar për të krijuar të tilla dëshmi, dhe mbështetet në supozimin se nëse ata kanë publikuar një dëshmi të tillë, ajo do të arrijë të gjithë pjesëmarrësit e tjerë brenda kësaj periudhe të caktuar.
Nëse një pjesëmarrës nuk ishte online gjatë këtij periudhe kohore dhe realisht kishte të paktën një komponent të pavlefshëm, atëherë ky pjesëmarrës konkret nuk do të mund të merrte pjesë në gjenerimin e mëtejshëm të numrave. Protokolli, megjithatë, do të vazhdojë të funksionojë, nëse ka të paktën k pjesëmarrës që ose sapo kishin marrë komponentet e sakta, ose kishin arritur të lënë dëshmi të pavlefshmërisë në kohën e caktuar.
Dëshmitë e saktesisë H_i
Pjesa e fundit që na mbetet për të diskutuar është se si të provoni saktësinë e publikimeve Hi, domethënë që Hi = p(i)H, pa zbuluar p(i).
Kujtojmë se vlerat H, G, p(i)G janë publike dhe janë të njohura për të gjithë. Operacioni i marrjes p(i) duke ditur p(i)G dhe G quhet logaritmi diskret, ose dlog, dhe ne duam të provojmë se:
dlog(p(i)G, G) = dlog(Hi, H)
pa zbuluar p(i). Strukturat për dëshmi të tilla ekzistojnë, për shembull.
Me një strukturë të tillë, çdo pjesëmarrës së bashku me Përshëndetje dërgon një dëshmi saktësie sipas strukturës.
Kur numri i rastësishëm është gjeneruar, shpesh është e nevojshme të përdoret nga pjesëmarrës të ndryshëm nga ata që e kanë gjeneruar. Këtyre pjesëmarrësve së bashku me numrin duhet t'u dërgohen të gjitha Përshëndetje dhe dëshmitë shoqëruese.
Lexuesi i kureshëm mund të pyesë: pse numri fundit rastësor – është H0, dhe p(0)G – kjo është informacion publik, çfarë është nevoja për dëshmi për secilin individual Hi, pse në vend të kësaj të mos dërgohet dëshmia se
dlog(p(0)G, G) = dlog(H0, H)
Problemi është që me Protokollin Schnorr nuk mund të krijohet një dëshmi e tillë, sepse askush nuk e di vlerën p(0), e cila është e nevojshme për të krijuar dëshminë, dhe për më tepër, i gjithë gjeneratori i numrave rastësor është i bazuar në atë që askush nuk e di këtë vlerë. Prandaj, është e nevojshme të ketë të gjitha vlerat Përshëndetje dhe dëshmitë e tyre individuale, për të provuar saktësinë. H0.
Megjithatë, nëse do të kishte një operacion në pikët në kurbat elliptike që është semantikisht i ngjashëm me shumimin, dëshmia e saktësisë H0 do të ishte triviale, ne do të thoshim vetëm që
H0 × G = p(0)G × H
Nëse kriva e zgjedhur mbështet , një dëshmi e tillë funksionon. Në këtë rast H0 – nuk është vetëm output i gjeneratorit të numrave rastësor, i cili mund të verifikohet nga çdo pjesëmarrës që e di G, H dhe p(0)G. H0 – kjo është gjithashtu një nënshkrim në mesazhin që u përdor si seed, duke konfirmuar që k dhe n anëtarët e kanë nënshkruar këtë mesazh. Kështu, nëse seed – është hash i blokut në protokollin e bllokadës, atëherë H0 – është njëkohësisht nënshkrimi shumë në bllok dhe një numër shumë i mirë rastësor.
Në përfundim
Ky artikull është pjesë e një serie artikujsh teknikë në blog . NEAR është një protokoll bllokadë 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, 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
