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

Hej Habr!

В Pjesa e parë Në këtë artikull, ne diskutuam pse mund të jetë e nevojshme të gjenerohen numra të rastësishëm për pjesëmarrësit që nuk i besojnë njëri-tjetrit, cilat kërkesa parashtrohen për gjeneruesit e tillë të numrave të rastësishëm dhe konsideruam dy qasje për zbatimin e tyre.

Në këtë pjesë të artikullit, ne do të hedhim një vështrim më të afërt në një qasje tjetër që përdor nënshkrimet e pragut.

Pak kriptografi

Për të kuptuar se si funksionojnë nënshkrimet e pragut, duhet të kuptoni pak kriptografi bazë. Ne do të përdorim dy koncepte: skalar, ose thjesht numra, të cilët do t'i shënojmë me shkronja të vogla (x, y) dhe pikat në lakoren eliptike, të cilat do t'i shënojmë me shkronja të mëdha.

Për të kuptuar bazat e nënshkrimeve të pragut, nuk keni nevojë të kuptoni se si funksionojnë kthesat eliptike, përveç disa gjërave themelore:

1. Pikat në një kurbë eliptike mund të shtohen dhe të shumëzohen me një skalar (ne do të shënojmë shumëzimin me një skalar si xG, edhe pse shënimi Gx gjithashtu përdoret shpesh në literaturë). Rezultati i mbledhjes dhe shumëzimit me një skalar është një pikë në një kurbë eliptike.

2. Duke ditur vetëm pikën G dhe produkti i tij me një skalar xG nuk mund të llogaritet x.

Do të përdorim edhe konceptin e një polinomi p(x) shkallë k-1. Në veçanti, do të përdorim vetinë e mëposhtme të polinomeve: nëse e dimë vlerën p(x) për çdo k i ndryshëm x (dhe nuk kemi më shumë informacion rreth p(x)), mund të llogarisim p(x) për këdo tjetër x.

Është interesante se për çdo polinom p(x) dhe një pikë në kurbë Gduke ditur kuptimin p(x)G për çdo k kuptime të ndryshme x, ne gjithashtu mund të llogarisim p(x)G për çdo x.

Ky është informacion i mjaftueshëm për të gërmuar në detaje se si funksionojnë nënshkrimet e pragut dhe si t'i përdorin ato për të gjeneruar numra të rastësishëm.

Gjeneruesi i numrave të rastësishëm në nënshkrimet e pragut

Le të themi se n pjesëmarrësit duan të gjenerojnë një numër të rastësishëm dhe ne duam që kushdo të marrë pjesë k kishte mjaft prej tyre për të gjeneruar një numër, por në mënyrë që sulmuesit që kontrollojnë k-1 ose më pak pjesëmarrës nuk mund të parashikonin ose ndikonin në numrin e krijuar.

Supozoni se ekziston një polinom i tillë p(x) shkallë k-1 çfarë di pjesëmarrësi i parë p (1), i dyti e di p (2), dhe kështu me radhë (n-th e di p(n)). Ne gjithashtu supozojmë se për një pikë të paracaktuar G të gjithë e dinë p(x)G për të gjitha vlerat x. Ne do të thërrasim p(i) "komponent privat" ipjesëmarrësi i th (sepse vetëm ipjesëmarrësi i th e njeh atë), dhe p(i)G "komponenti publik" i- pjesëmarrësi i th (sepse të gjithë pjesëmarrësit e njohin atë). Siç e mbani mend, njohuri p(i)G nuk mjafton për të rivendosur p(i).

Krijimi i një polinomi të tillë në mënyrë që vetëm i-Pjesëmarrësi i parë dhe askush tjetër nuk e dinte komponentin e tij privat - kjo është pjesa më komplekse dhe më interesante e protokollit, dhe ne do ta analizojmë atë më poshtë. Tani për tani, le të supozojmë se kemi një polinom të tillë dhe të gjithë pjesëmarrësit i dinë përbërësit e tyre privatë.

Si mund ta përdorim një polinom të tillë për të gjeneruar një numër të rastësishëm? Për të filluar, na duhet një varg që nuk është përdorur më parë si hyrje në gjenerator. Në rastin e një blockchain, hash-i i bllokut të fundit h është një kandidat i mirë për një linjë të tillë. Lërini pjesëmarrësit të dëshirojnë të krijojnë një numër të rastësishëm duke përdorur h si fara. Pjesëmarrësit konvertohen të parët h në një pikë të kurbës duke përdorur ndonjë funksion të paracaktuar:

H = skalarToPoint(h)

Pastaj secili pjesëmarrës i llogarit dhe publikon Hi = p(i)H, çfarë mund të bëjnë sepse e dinë p(i) dhe H. Zbulimi HUnë nuk i lejoj pjesëmarrësit e tjerë të rivendosin komponentin privat ipjesëmarrësi, dhe për këtë arsye një grup përbërësish privatë mund të përdoret nga blloku në bllok. Kështu, algoritmi i shtrenjtë i gjenerimit të polinomit i përshkruar më poshtë duhet të ekzekutohet vetëm një herë.

Kur k pjesëmarrësve iu bë autopsi Hi = p(i)H, të gjithë mund të llogarisin Hx = = p(x)H per te gjithe x falë vetive të polinomeve që diskutuam në pjesën e fundit. Në këtë moment, të gjithë pjesëmarrësit llogaritin H0 = p(0)H, dhe ky është numri i rastësishëm që rezulton. Ju lutemi vini re se askush nuk e di p (0), dhe për këtë arsye e vetmja mënyrë për të llogaritur p(0)H - ky është interpolim p(x)H, e cila është e mundur vetëm kur k vlerat p(i)H i njohur. Hapja e ç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 vetitë që duam: vetëm sulmuesit që kontrollojnë k-1 pjesëmarrës ose më pak nuk kanë informacion apo ndikim në përfundim, ndërsa ndonjë k pjesëmarrësit mund të llogarisin numrin që rezulton dhe çdo nëngrup të k pjesëmarrësit do të arrijnë gjithmonë në të njëjtin rezultat për të njëjtën farë.

Ekziston një problem që e shmangëm me kujdes më lart. Që interpolimi të funksionojë, është e rëndësishme që vlera Hi cili u publikua nga secili pjesëmarrës i ishte vërtet e njëjta gjë p(i)H. Meqë askush përveç i- pjesëmarrësi nuk e di p(i), askush përveç i-pjesëmarrësi nuk mund ta verifikojë këtë Hi realisht llogaritur saktë dhe pa asnjë provë kriptografike të saktësisë Hunë një sulmues mund të publikojë çdo vlerë si Hi, dhe ndikojnë në mënyrë arbitrare në daljen e gjeneruesit të numrave të rastësishëm:

Vlerat e ndryshme të H_1 të dërguara nga pjesëmarrësi i parë çojnë në rezultate të ndryshme H_0

Ka të paktën dy mënyra për të vërtetuar korrektësinë Hi, do t'i shqyrtojmë pasi të analizojmë gjenerimin e polinomit.

Gjenerimi polinom

Në pjesën e fundit supozuam se kemi një polinom të tillë p(x) shkallë k-1 që pjesëmarrësi i ai e di p(i), dhe askush tjetër nuk ka asnjë informacion për këtë vlerë. Në seksionin tjetër do të na duhet gjithashtu për disa pika të paracaktuara G të gjithë e dinin p(x)G per te gjithe x.

Në këtë seksion do të supozojmë se çdo pjesëmarrës në nivel lokal ka një çelës privat xi, të tillë që të gjithë e dinë çelësin publik përkatës Xi.

Një protokoll i mundshëm i gjenerimit të polinomit është si më poshtë:

1. Çdo pjesëmarrës i lokalisht krijon një polinom arbitrar pi(x) shkalla k-1. Më pas ata dërgojnë secilin pjesëmarrës j vlerë pi(j), i koduar me çelës publik Xj. Kështu vetëm i-th и j-th pjesëmarrësi e di pi(j). pjesëmarrës i shpall edhe publikisht pi(j)G per te gjithe j nga 1 tek k përfshirëse.

2. Të gjithë pjesëmarrësit përdorin një konsensus për të zgjedhur k pjesëmarrësit polinomet e të cilëve do të përdoren. Meqenëse disa pjesëmarrës mund të jenë jashtë linje, nuk mund të presim derisa të gjithë n pjesëmarrësit do të publikojnë polinome. Rezultati i këtij hapi është një grup Z i përbërë nga të paktën k polinomet e krijuara në hapin (1).

3. Pjesëmarrësit sigurohen që vlerat që dinë pi(j) korrespondon me shpalljen publikisht pi(j)G. Pas këtij hapi Z vetëm polinomet për të cilat transmetohen privatisht pi(j) korrespondon me shpalljen publikisht pi(j)G.

4. Çdo pjesëmarrës j llogarit komponentin e tij privat p(j) si shumë pi(j) për të gjithë i в Z. Secili pjesëmarrës gjithashtu llogarit të gjitha vlerat p(x)G si shumë pi(x)G për të gjitha i в Z.

Vini re se p(x) - është me të vërtetë një polinom k-1, sepse është shuma e individit pi(x), secila prej të cilave është një polinom i shkallës k-1. Pastaj, vini re se ndërsa secili pjesëmarrës j ai e di p(j), nuk kanë informacion për p(x) për x ≠ j. Në të vërtetë, për të llogaritur këtë vlerë, ata duhet të dinë gjithçka pi (x), dhe për aq kohë sa pjesëmarrësi j nuk njeh të paktën një nga polinomet e përzgjedhur, ata nuk kanë informacion të mjaftueshëm për p(x).

Ky është i gjithë procesi i gjenerimit të polinomit që nevojitej në seksionin e fundit. Hapat 1, 2 dhe 4 më sipër kanë një zbatim mjaft të qartë. Por hapi 3 nuk është aq i parëndësishëm.

Në mënyrë të veçantë, ne duhet të jemi në gjendje ta vërtetojmë atë të koduar pi(j) korrespondon vërtet me ato të publikuara pi(j)G. Nëse nuk mund ta vërtetojmë, sulmuesi i në vend të kësaj mund të dërgojë mbeturina pi(j) për pjesëmarrësin j, dhe pjesëmarrës j nuk do të jetë në gjendje të marrë vlerën reale pi (j), dhe nuk do të jetë në gjendje të llogarisë komponentin e tij privat.

Ekziston një protokoll kriptografik që ju lejon të krijoni një mesazh shtesë provëi(j), i tillë që çdo pjesëmarrës që ka një vlerë e, dhe gjithashtu prova (j) и pi(j)G, mund ta verifikojë atë në nivel lokal e - është me të vërtetë pi (j), koduar me çelësin e pjesëmarrësit j. Fatkeqësisht, përmasat e provave të tilla janë tepër të mëdha, dhe duke pasur parasysh se është e nevojshme të publikohen O (nk) Prova të tilla nuk mund të përdoren për këtë qëllim.

Në vend që ta provojë atë pi (j) korrespondon me pi(j)G mund të ndajmë një periudhë shumë të gjatë kohore në protokollin e gjenerimit polinom, gjatë së cilës të gjithë pjesëmarrësit kontrollojnë të koduarat e marra pi (j), dhe nëse mesazhi i deshifruar nuk i përgjigjet publikut pi(j)G, ata publikojnë një provë kriptografike që mesazhi i koduar që kanë marrë është i pasaktë. Vërtetoni se mesazhi jo korrespondon me pi(G) shumë më e lehtë sesa të provosh se përputhet. Duhet të theksohet se kjo kërkon që çdo pjesëmarrës të shfaqet në internet të paktën një herë gjatë kohës së caktuar për të krijuar prova të tilla dhe mbështetet në supozimin se nëse ata publikojnë një provë të tillë, ajo do të arrijë të gjithë pjesëmarrësit e tjerë në të njëjtën kohë të caktuar.

Nëse një pjesëmarrës nuk u shfaq në internet gjatë kësaj periudhe kohore dhe ai kishte të paktën një komponent të pasaktë, atëherë ai pjesëmarrës i veçantë nuk do të jetë në gjendje të marrë pjesë në gjenerimin e mëtejshëm të numrave. Megjithatë, protokolli do të vazhdojë të funksionojë nëse ka të paktën k pjesëmarrësit të cilët ose sapo morën komponentët e duhur ose arritën të lënë prova të pasaktësisë brenda kohës së caktuar.

Dëshmitë e korrektësisë së H_i

Pjesa e fundit që mbetet për t'u diskutuar është se si të vërtetohet korrektësia e botuar Hunë, domethënë atë Hi = p(i)H, pa hapur p(i).

Le të kujtojmë se vlerat H, G, p(i)G publike dhe të njohura për të gjithë. Marrja e operacionit p(i) duke ditur p(i)G и G quhet logaritëm diskret, ose dlog, dhe ne duam të vërtetojmë se:

dlog(p(i)G, G) = dlog(Hi, H)

pa zbulim p(i). Për shembull ekzistojnë ndërtime për prova të tilla Protokolli i Schnorr.

Me këtë dizajn, çdo pjesëmarrës, së bashku me Hi dërgon një vërtetim korrektësie sipas dizajnit.

Pasi të krijohet një numër i rastësishëm, ai shpesh duhet të përdoret nga pjesëmarrës të ndryshëm nga ata që e kanë gjeneruar. Këta pjesëmarrës, së bashku me numrin, duhet të dërgojnë të gjithë Hi dhe dëshmitë përkatëse.

Një lexues kureshtar mund të pyesë: pasi numri përfundimtar i rastësishëm është H0, dhe p(0)G - Ky është informacion publik, pse na duhen prova për çdo individ HUnë, pse të mos dërgoj prova se në vend të kësaj

dlog(p(0)G, G) = dlog(H0, H)

Problemi është se një provë e tillë nuk mund të krijohet duke përdorur Protokollin Schnorr sepse askush nuk e di vlerën p (0), e nevojshme për të krijuar provën, dhe për më tepër, i gjithë gjeneratori i numrave të rastësishëm bazohet në faktin se askush nuk e di këtë vlerë. Prandaj është e nevojshme të kemi të gjitha vlerat Hi dhe dëshmitë e tyre individuale për të vërtetuar korrektësinë H0.

Megjithatë, nëse do të kishte ndonjë veprim në pikat në kthesat eliptike që është semantikisht i ngjashëm me shumëzimin, prova e korrektësisë H0 do të ishte e parëndësishme, ne thjesht do të siguroheshim për këtë

H0 × G = p(0)G × H

Nëse kurba e zgjedhur mbështet çiftimet e kurbës eliptike, kjo provë funksionon. Në këtë rast H0 nuk është vetëm prodhimi i një gjeneruesi të numrave të rastësishëm, i cili mund të verifikohet nga çdo pjesëmarrës që di G, H и p(0)G. H0 është gjithashtu një nënshkrim në mesazhin që është përdorur si farë, duke e konfirmuar atë k и n pjesëmarrësit nënshkruan këtë mesazh. Kështu, nëse fara - është hash-i i bllokut në protokollin blockchain, atëherë H0 është njëkohësisht një shumë-nënshkrim në një bllok dhe një numër shumë i mirë rastësor.

Në përfundim

Ky artikull është pjesë e një serie blogu teknik 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