Përshëndetje, Habr!
Në në artikujt e mëparshëm diskutuam arsyet pse mund të jetë e nevojshme të gjenerohen numra të rastit për pjesëmarrësit që nuk i besojnë njëri-tjetrit, kërkesat që i bëhen këtyre gjeneratorëve të numrave të rastit dhe shqyrtuam dy qasje për realizimin e tyre.
Në këtë pjesë të artikullit do të shqyrtojmë në detaje një tjetër qasje që përdor nënshkrime me prag.
Pak kriptografi
Për të kuptuar se si funksionojnë nënshkrimet me prag, duhet të kuptoni pak kriptografi bazike. Ne do të përdorim dy koncepte: shkallarë, ose thjesht numra, të cilat ne do t'i shënojmë me shkronja të vogla (x, y) dhe pika në kurbën eliptike, të cilat ne do t'i shënojmë me shkronja të mëdha.
Për të kuptuar bazat e nënshkrimeve me prag nuk është e nevojshme të kuptoni si funksionojnë kurbat eliptike, përveç disa informacioneve bazike:
Pikat në kurbën eliptike mund të shtohen dhe të shumëzohen me një shkallar (shumëzimi me një shkallar do ta shënojmë si xG, megjithëse nota Gx përdoret gjithashtu shpesh në literaturë). Rezultati i shtimit dhe shumëzimit me një shkallar është një pikë në kurbën eliptike.
Duke ditur vetëm pikën G dhe produktin e saj me shkallarin 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 këtë pronë të polinomëve: nëse ne dimë vlerën p(x) për çdo k vlerë të ndryshme x (dhe nuk kemi asnjë informacion tjetër për p(x)), ne mund të llogarisim p(x) për çdo x.
vlerĂ« tjetĂ«r. p(x) ĂshtĂ« e interesante qĂ« pĂ«r çdo polinom Gdhe njĂ« pikĂ« nĂ« kurbĂ« , duke ditur vlerĂ«n pĂ«r çdo k p(x)G xtĂ« vlerave tĂ« ndryshme , duke ditur vlerĂ«n , gjithashtu mund tĂ« llogarisim x.
për çdo
kjo informacion është e mjaftueshme për të hyrë në detajet e funksionimit të nënshkrimeve me prag dhe si t'i përdorim për të gjeneruar numra të rastit.
Gjeneratori i numrave të rastit me nënshkrime me prag n Le të themi se k pjesëmarrësit duan të gjenerojnë një numër të rastit, dhe ne duam që pjesëmarrja e çdo kprej tyre të jetë e mjaftueshme për të gjeneruar numrin, por që sulmuesit që kontrollojnë
-1 ose më pak pjesëmarrës, të mos kenë mundësinë të parashikojnë ose të ndikojnë në numrin e gjeneruar. p(x) me gradë kLe të supozojmë se ekziston një polinom -1, që pjesëmarrësi i parë e dip(1) , pjesëmarrësi i dytë e di p(2),ndhe kështu me radhë ( -i dip(n) G ). Po ashtu, le të supozojmë që për një pikë të caktuar , duke ditur vlerën të gjithë e dinë xpër të gjitha vlerat . Ne do ta quajmë p(i) i"komponent privat" itë pjesëmarrësit -i (sepse vetëm -i pjesëmarrës e di atë), dhe p(i)G i"komponent publik" -i pjesëmarrës e di atë), dhe të pjesëmarrësit -i (sepse të gjithë pjesëmarrësit e dinë atë). Siç e mbani mend, njohja e nuk është e mjaftueshme për të rikonstruktuar
p(i). Krijimi i një polinomi të tillë në mënyrë që vetëmi-
pjesĂ«marrĂ«si dhe askush tjetĂ«r e di komponentin e tij privat â kjo Ă«shtĂ« pjesa mĂ« e komplikuar dhe interesante e protokollit, dhe ne do ta shqyrtojmĂ« mĂ« poshtĂ«. NdĂ«rkohĂ« le tĂ« supozojmĂ« se kemi njĂ« polinom tĂ« tillĂ«, dhe tĂ« gjithĂ« pjesĂ«marrĂ«sit e dinĂ« komponentet e tyre private. h Si mund ta pĂ«rdorim njĂ« polinom tĂ« tillĂ« pĂ«r tĂ« gjeneruar njĂ« numĂ«r tĂ« rastit? Fillimisht, na nevojitet njĂ« varg qĂ« nuk Ă«shtĂ« pĂ«rdorur mĂ« parĂ« 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Ă« themi se pjesĂ«marrĂ«sit duan tĂ« krijojnĂ« njĂ« numĂ«r tĂ« rastit duke pĂ«rdorur h si seed. Fillimisht, pjesĂ«marrĂ«sit i konvertojnĂ«
në një pikë në kurbë duke përdorur cfarëdo funksioni të paracaktuar:
H = scalarToPoint(h) i Pastaj çdo pjesëmarrës llogarit dhe publikoi Hi = p(i)H, çfarë ata mund ta bëjnë, sepse ata e dinë p(i) dhe H. Hi nuk i lejon pjesëmarrësit e tjerë të rivendosin komponentin privat i-të pjesëmarrësit, dhe kështu një grup privat komponentesh mund të përdoret nga blloku në bllok. Kështu, algoritmi i shtrenjtë për krijimin e polinomit, i përshkruar më poshtë, duhet të realizohet vetëm një herë.
Kur k nĂ«se pjesĂ«marrĂ«sit e zbulojnĂ« llogarit dhe publikoi tĂ« gjithĂ« mund tĂ« llogarisin Hx = p(x)H pĂ«r tĂ« gjithĂ« x pĂ«r shkak tĂ« pronĂ«s sĂ« polinomĂ«ve qĂ« ne e diskutuam nĂ« seksionin e kaluar. NĂ« kĂ«tĂ« moment tĂ« gjithĂ« pjesĂ«marrĂ«sit llogarisin H0 = p(0)H, dhe ky Ă«shtĂ« numri rezultant i rastĂ«sishĂ«m. 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, çka Ă«shtĂ« e mundur vetĂ«m kur k vlerat p(i)H janĂ« tĂ« njohura. Zbulimi i njĂ« numri mĂ« tĂ« vogĂ«l p(i)H nuk jep asnjĂ« informacion rreth p(0)H.
Gjeneratori më sipër ka të gjitha pronat që ne duam: sulmuesit, që kontrollojnë vetëm k-1 pjesëmarrës, ose më pak, nuk kanë informacion ose ndikim mbi rezultatin, ndërsa çdo k pjesëmarrës mund të llogarisë numrin përfundimtar, dhe çdo nën-grup prej k pjesëmarrësish gjithmonë do të arrijë në të njëjtin rezultat për të njëjtin seed.
Ka një problem të vetëm, të cilin e kemi kaluar me kujdes më lart. Për të funksionuar interpolimi, është e rëndësishme që vlera Hi e publikuar nga çdo pjesëmarrës i të jetë vërtet e barabartë me p(i)H. Tani, askush përveç i-it pjesëmarrës nuk e di p(i), askush përveç Krijimi i një polinomi të tillë në mënyrë që vetëmpjesëmarrësit nuk mund të verifikojë se Përshëndetje është llogaritur saktë dhe pa ndonjë provë kriptografike të saktësisë Hi një sulmues mund të publikojë çdo vlerë si Hi, dhe të ndikojë arbitrarisht në rezultatin e gjeneratorit të numrave të rastit.:
Të ndryshmet vlera H_1, të dërguara nga pjesëmarrësi i parë, çojnë në H_0 të ndryshme rezultuese.
Ka të paktën dy mënyra për të dëshmuar saktësinë Hi, ne do t'i shqyrtojmë ato pasi të trajtojmë gjenerimin e polinomit.
Gjenerimi i polinomit
Në seksionin e kaluar ne supozuam se kemi një polinom të tillë p(x) me gradë k-1 që pjesëmarrësi i di . Ne do ta quajmë, dhe askush tjetër nuk ka informacion mbi këtë vlerë. Në seksionin e ardhshëm do të na nevojitet gjithashtu që për një pikë të paracaktuar G të gjithë të dinë , duke ditur vlerën për të gjithë x.
Në këtë seksion do të supojmë se çdo pjesëmarrës ka lokalizuar një çelës privat xi, i cili është i njohur për të gjithë çelësin publik Xi.
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 dĂ«rgojnĂ« çdo pjesĂ«marrĂ«si j vlerĂ«n pi(j), i koduar me çelĂ«sin publik Xj. KĂ«shtu vetĂ«m Krijimi i njĂ« polinomi tĂ« tillĂ« nĂ« mĂ«nyrĂ« qĂ« vetĂ«mj- dhe pjesĂ«marrĂ«si dij- i(j). PjesĂ«marrĂ«si ppo ashtu shpall publikisht i pi(j)G pĂ«rfshirĂ«. pĂ«r tĂ« gjithĂ« j nga 1 deri nĂ« k TĂ« gjithĂ« pjesĂ«marrĂ«sit pĂ«rdorin njĂ« konsensus pĂ«r tĂ« zgjedhur
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 që të gjithë k pjesëmarrësit të publikojnë polinomët. Rezultati i këtij hapi është një grup n që përbëhet nga të paktën Z polinomë, të krijuara në hapin (1) k Pjesëmarrësit sigurohen që vlerat e njohura për ta.
i(j) përkojnë me të publikuara ppi(j)G. Pas këtij hapi, duhet të mbeten vetëm polinomët, për të cilët vlera e transferuar privatisht Z llogarit komponentin e saj privat ppi(j)G. Pas këtij hapi,
Ădo pjesĂ«marrĂ«s j p(j) si njĂ« shumĂ« i(j) pĂ«r tĂ« gjithĂ«. pĂdo pjesĂ«marrĂ«s gjithashtu llogarit tĂ« gjitha vlerat i nĂ« Zpi(x)G pĂ«r tĂ« gjithĂ« i , duke ditur vlerĂ«n i(j) pĂ«r tĂ« gjithĂ«. p(x) â nĂ« Z.
Merrni parasysh se kĂ«tu Ă«shtĂ« vĂ«rtet njĂ« polinom i gradĂ«s k-1, sepse kjo Ă«shtĂ« njĂ« shumĂ« e veçorive i(x), secili prej tĂ« cilĂ«ve Ă«shtĂ« njĂ« polinom i gradĂ«s p-1. Pastaj, vini re se ndĂ«rsa çdo pjesĂ«marrĂ«s kp(j), j di ata nuk kanĂ« asnjĂ« informacion mbi x â j. p(x) pĂ«r NĂ« tĂ« vĂ«rtetĂ«, pĂ«r tĂ« llogaritur kĂ«tĂ« vlerĂ«, ata duhet tĂ« dinĂ« tĂ« gjithĂ«pi(x), dhe pĂ«r sa kohĂ« qĂ« pjesĂ«marrĂ«si nuk di tĂ« paktĂ«n njĂ« nga polinomĂ«t e zgjedhur, ata nuk kanĂ« informacion tĂ« mjaftueshĂ«m mbi j p(x). Ky Ă«shtĂ« i gjithĂ« procesi i gjenerimit tĂ« polinomit, i cili ishte i nevojshĂ«m nĂ« seksionin e kaluar. Hapat 1, 2 dhe 4 tĂ« lartpĂ«rmendur kanĂ« njĂ« implementim mjaft tĂ« qartĂ«. NdĂ«rsa hapi 3 nuk Ă«shtĂ« aq i thjeshtĂ«.
Specifikisht, ne duhet të jemi në gjendje të dëshmojmë se të koduar
i(j) vërtet përkojnë me të publikuara. pNëse ne nuk mund ta dëshmojmë, një sulmues Pas këtij hapi, mund të dërgojë mbetje në vend të i i(j) për pjesëmarrësin p, dhe pjesëmarrësi jnuk do të jetë në gjendje të marrë vlerën reale j pi(j), dhe nuk do të jetë në gjendje të llogarisë komponentin e tij privat. Ka një protokoll kriptografik që lejon krijimin e një mesazhi shtesë.
proof i(j), nĂ« mĂ«nyrĂ« qĂ« çdo pjesĂ«marrĂ«s, duke pasur njĂ« vlerĂ« tĂ« caktuare, si dhe proofi(j) i(j)G, mund tĂ« sigurohet lokal qĂ« dhe pâ Ă«shtĂ« vĂ«rtet e i koduar me çelĂ«sin e pjesĂ«marrĂ«sit dhe nuk do tĂ« jetĂ« nĂ« gjendje tĂ« llogarisĂ« komponentin e tij privat. j. FatkeqĂ«sisht, madhĂ«sia e kĂ«tij dĂ«shmimi Ă«shtĂ« jashtĂ«zakonisht e madhe, dhe duke pasur parasysh se Ă«shtĂ« e nevojshme tĂ« publikohet O(nk) tĂ« tillĂ« prova, pĂ«rdorimi i tyre pĂ«r kĂ«tĂ« qĂ«llim nuk do tĂ« funksionojĂ«. NĂ« vend tĂ« dĂ«shmisĂ« se
pi(j) i(j)G ne mund të ndajmë një periudhë të madhe kohore në protokollin e gjenerimit të polinomit, gjatë të cilës të gjithë pjesëmarrësit do të verifikojnë mesazhet e koduara përputhet pe nëse mesazhi i dekoduar nuk përkon me publikun dhe nuk do të jetë në gjendje të llogarisë komponentin e tij privat. i(j)G, ata publikojnë një provë kriptografike se mesazhi i marrë prej tyre është i pasaktë. Dëshmia se mesazhi ppi(G) nuk përputhet është shumë më e lehtë se sa të tregosh se ai përkon. Duhet të theksohet se kjo kërkon që çdo pjesëmarrës të shfaqet në rrjet së paku një herë gjatë kohës së alokuar për krijimin e provave të tilla, dhe mbështetet në supozimin se nëse ata kanë publikur një provë të tillë, ajo do të arrijë të gjithë pjesëmarrësit e tjerë brenda të njëjtës periudhë të alokuar. Nëse një pjesëmarrës nuk shfaqet në rrjet gjatë këtij periudhe, dhe ata me të vërtetë kishin të paktën një komponent të pasaktë, atëherë ky pjesëmarrës specifik nuk do të jetë në gjendje të marrë pjesë në gjenerimin e mëtejshëm të numrave. Protokolli, megjithatë, do të funksionojë akoma nëse ka të paktën
Nëse pjesëmarrësi nuk është shfaqur në rrjet gjatë këtij periudhe dhe vërtet kishte të paktën një komponent të gabuar, atëherë ky pjesëmarrës specifik nuk do të mund të marrë pjesë në gjenerimin e mëtejmë të numrave. Protokolli, megjithatë, do të funksionojë ende nëse ka të paktën k pjesëtarëve që ose sapo morën komponentet e sakta, ose arritën të lënë provën e pasaktësisë brenda kohës së caktuar.
Provave të saktësisë H_i
Pjesa e fundit që mbetet për t'u diskutuar është se si të provohet saktësia e publikuar Hi, domethënë se llogarit dhe publikoi pa zbuluar nuk është e mjaftueshme për të rikonstruktuar
Kujtojmë se vlerat H, G, p(i)G së bashku dhe janë të njohura për të gjithë. Operacioni i marrjes . Ne do ta quajmë duke ditur -i pjesëmarrës e di atë), dhe dhe G quhet logaritmi diskret, ose dlog, dhe ne duam të provojmë se:
dlog(p(i)G, G) = dlog(Hi, H)
pa zbuluar . Ne do ta quajmë. Ndërtesa për këto prova ekzistojnë, për shembull.
Me një ndërtim të tillë, çdo pjesëmarrës së bashku me Përshëndetje dërgon provën e saktësisë sipas ndërtimit.
Kur numri i rastësishëm është gjeneruar, shpesh duhet ta përdorin pjesëmarrësit, të ndryshëm nga ata që e gjeneruan. Të tillëve u nevojitet të dërgohen së bashku me numrin të gjitha Përshëndetje dhe provat përcjellëse.
Lexuesi kurioz mund tĂ« pyesĂ«: pasi numri pĂ«rfundimtar i rastĂ«sishĂ«m Ă«shtĂ« H0, dhe p(0)G â Ă«shtĂ« informacion publik, pĂ«rse Ă«shtĂ« e nevojshme prova pĂ«r secilin tĂ« veçantĂ« Hi, pse tĂ« mos dĂ«rgohet provĂ« se
dlog(p(0)G, G) = dlog(H0, H)
Problemi është se me Protokollin Schnorr nuk mund të krijohet një provë e tillë, sepse askush nuk e di vlerën p(0), e nevojshme për të krijuar provën, dhe më tepër, gjithë gjeneratori i numrave rastësishëm bazohet në faktin se askush nuk e di këtë vlerë. Prandaj, është e nevojshme të kemi të gjitha vlerat Përshëndetje dhe provat e tyre individuale, për të provuar saktësinë H0.
Megjithatë, nëse do të kishte ndonjë operacion në piketat në kurbat eliptike, i cili është semantikisht i ngjashëm me shumëzimin, provat e saktësisë H0 do të ishte triviale, ne do të siguroheshim thjesht se
H0 Ă G = p(0)G Ă H
NĂ«se curva e zgjedhur mbĂ«shtet njĂ« provĂ« e tillĂ« funksionon. NĂ« kĂ«tĂ« rast H0 â Ă«shtĂ« jo vetĂ«m rezultati i gjeneratorit tĂ« numrave rastĂ«sishĂ«m qĂ« mund tĂ« verifikohet nga çdo pjesĂ«marrĂ«s qĂ« e njeh G, H dhe p(0)G. H0 â Ă«shtĂ« gjithashtu njĂ« nĂ«nshkrim mbi mesazhin, i cili u pĂ«rdor si seed, qĂ« konfirmon se k dhe n pjesĂ«tarĂ«t e nĂ«nshkruan kĂ«tĂ« mesazh. Ashtu qĂ«, nĂ«se seed â Ă«shtĂ« hesh i blokut nĂ« protokollin e blockchain, atĂ«herĂ« H0 â Ă«shtĂ« njĂ«kohĂ«sisht njĂ« nĂ«nshkrim i shumĂ«fishtĂ« mbi bllokun dhe njĂ« numĂ«r shumĂ« tĂ« mirĂ« rastĂ«sor.
Në përfundim
Ky artikull është pjesë e një serie artikujsh teknik në blog . NEAR është një protokoll blockchain dhe platformë për zhvillimin e aplikacioneve të decentralizuara me theks mbi thjeshtësinë e zhvillimit dhe përdorimin e thjeshtë për përdoruesit përfundimtarë.
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
