Ali je mogoče ustvariti naključna števila, če si ne zaupamo? 2. del

Pozdravljeni, Habr!

В 1. del V tem članku smo razpravljali o tem, zakaj bi bilo morda potrebno ustvariti naključna števila za udeležence, ki si ne zaupajo, kakšne zahteve so postavljene za takšne generatorje naključnih števil in obravnavali dva pristopa k njihovi izvedbi.

V tem delu članka si bomo podrobneje ogledali drug pristop, ki uporablja podpise praga.

Malo kriptografije

Da bi razumeli, kako delujejo mejni podpisi, morate razumeti malo osnovne kriptografije. Uporabljali bomo dva pojma: skalarje ali preprosto številke, ki jih bomo označevali z malimi črkami (x, y) in točke na eliptični krivulji, ki jih bomo označili z velikimi črkami.

Če želite razumeti osnove podpisov pragov, vam ni treba razumeti, kako delujejo eliptične krivulje, razen nekaj osnovnih stvari:

1. Točke na eliptični krivulji lahko seštejemo in pomnožimo s skalarjem (množenje s skalarjem bomo označili kot xG, čeprav not Gx pogosto uporabljen tudi v literaturi). Rezultat seštevanja in množenja s skalarjem je točka na eliptični krivulji.

2. Vedeti samo bistvo G in njegov produkt s skalarjem xG ni mogoče izračunati x.

Uporabili bomo tudi koncept polinoma p(x) stopinj k-1. Posebej bomo uporabili naslednjo lastnost polinomov: če poznamo vrednost p(x) za katero koli k drugačna x (in nimamo več informacij o p(x)), lahko izračunamo p(x) za koga drugega x.

Zanimivo je, da za vsak polinom p(x) in neka točka na krivulji Gpoznavanje pomena p(x)G za katero koli k različne pomene x, lahko tudi izračunamo p(x)G za katero koli x.

To je dovolj informacij, da se poglobimo v podrobnosti o tem, kako delujejo podpisi pragov in kako jih uporabiti za ustvarjanje naključnih števil.

Generator naključnih števil na mejnih podpisih

Recimo to n udeleženci želijo ustvariti naključno število in želimo, da sodeluje kdorkoli k jih je bilo dovolj za ustvarjanje števila, a tako, da napadalci, ki nadzorujejo k-1 ali manj udeležencev ni moglo napovedati ali vplivati ​​na ustvarjeno število.

Recimo, da obstaja tak polinom p(x) stopinj k-1 kar zna prvi udeleženec p (1), drugi ve p(2), in tako naprej (n-th ve p(n)). Predpostavljamo tudi, da za neko vnaprej določeno točko G vsi vedo p(x)G za vse vrednosti x. Bomo poklicali p(i) "zasebna komponenta" iudeleženec (ker samo iudeleženec jo pozna) in p(i)G "javna komponenta" i-ta udeleženka (ker jo vsi udeleženci poznajo). Kot se spomnite, znanje p(i)G ni dovolj za obnovitev p(i).

Ustvarjanje takega polinoma, tako da samo i-Prvi udeleženec in nihče drug ni poznal njegove zasebne komponente - to je najbolj zapleten in zanimiv del protokola, ki ga bomo analizirali spodaj. Za zdaj predpostavimo, da imamo takšen polinom in vsi udeleženci poznajo svoje zasebne komponente.

Kako lahko uporabimo takšen polinom za ustvarjanje naključnega števila? Za začetek potrebujemo niz, ki še ni bil uporabljen kot vhod v generator. V primeru verige blokov zgoščena vrednost zadnjega bloka h je dober kandidat za tako linijo. Naj udeleženci želijo ustvariti naključno število z uporabo h kot seme. Udeleženci se najprej spreobrnejo h do točke na krivulji s katero koli vnaprej določeno funkcijo:

H = skalarToPoint(h)

Nato vsak udeleženec i izračuna in objavi Hi = p(i)H, kaj morejo, ker znajo p(i) in H. Razkritje Hdrugim udeležencem ne dovolim obnovitve zasebne komponente iudeleženca, zato se lahko en niz zasebnih komponent uporablja od bloka do bloka. Tako je treba drag algoritem generiranja polinoma, opisan spodaj, izvesti le enkrat.

Pri k udeležencev so opravili obdukcijo Hi = p(i)H, vsak lahko izračuna Hx = p(x)H za vse x zahvaljujoč lastnosti polinomov, ki smo jih obravnavali v zadnjem razdelku. V tem trenutku izračunajo vsi udeleženci H0 = p(0)H, in to je nastala naključna številka. Upoštevajte, da nihče ne ve p(0), in zato edini način za izračun p(0)H – to je interpolacija p(x)H, kar je mogoče le takrat, ko k vrednote p(i)H znan. Odpiranje poljubne manjše količine p(i)H ne daje nobenih informacij o p(0)H.

Zgornji generator ima vse lastnosti, ki jih želimo: samo nadzor napadalcev k-1 udeleženec ali manj nima informacij ali vpliva na sklep, medtem ko noben k udeleženci lahko izračunajo dobljeno število in katero koli podmnožico k udeleženci bodo vedno prišli do istega rezultata za isto seme.

Obstaja ena težava, ki smo se ji zgoraj skrbno izognili. Da interpolacija deluje, je pomembno, da vrednost Hi, ki ga je objavil vsak udeleženec i res je bilo isto p(i)H. Ker nihče razen i-ti udeleženec ne ve p(i), nihče razen i-udeleženec tega ne more preveriti Hi dejansko pravilno izračunan in brez kakršnega koli kriptografskega dokaza pravilnosti Hi napadalec lahko objavi katero koli vrednost kot Hi, in poljubno vpliva na izhod generatorja naključnih števil:

Različne vrednosti H_1, ki jih pošlje prvi udeleženec, vodijo do različnih rezultatov H_0

Obstajata vsaj dva načina za dokazovanje pravilnosti Hi, jih bomo obravnavali, ko bomo analizirali generiranje polinoma.

Polinomska generacija

V zadnjem delu smo predpostavili, da imamo takšen polinom p(x) stopinj k-1 da udeleženec i ve p(i), in nihče drug nima informacij o tej vrednosti. V naslednjem razdelku bomo to potrebovali tudi za neko vnaprej določeno točko G vsi so vedeli p(x)G za vse x.

V tem razdelku bomo domnevali, da ima vsak udeleženec lokalno nek zasebni ključ xi, tako, da vsi poznajo ustrezni javni ključ Xi.

Eden od možnih protokolov za generiranje polinoma je naslednji:

1. Vsak udeleženec i lokalno ustvari poljuben polinom pi(x) stopnja k-1. Nato pošljejo vsakega udeleženca j vrednost pi(j), šifrirano z javnim ključem Xj. Samo tako i-yy и j-yy udeleženec ve pi(j). Udeleženec i tudi javno objavlja pi(j)G za vse j od 1 za k vključujoč.

2. Vsi udeleženci pri izbiri uporabljajo določeno soglasje k udeležencev, katerih polinomi bodo uporabljeni. Ker so nekateri udeleženci morda brez povezave, ne moremo čakati na vse n udeleženci bodo objavili polinome. Rezultat tega koraka je niz Z sestavljen iz vsaj k polinomi, ustvarjeni v koraku (1).

3. Udeleženci se prepričajo o vrednotah, ki jih poznajo pi(j) ustrezajo javno objavljenemu pi(j)G. Po tem koraku v Z samo polinome, za katere zasebno prenese pi(j) ustrezajo javno objavljenemu pi(j)G.

4. Vsak udeleženec j izračuna svojo zasebno komponento p(j) kot vsota pi(j) za vse i в Z. Vsak udeleženec vse vrednosti tudi izračuna p(x)G kot vsota pi(x)G za vse i в Z.

Prosimo, upoštevajte, da se p(x) – res je polinom k-1, ker je vsota posameznika pi(x), od katerih je vsak polinom stopnje k-1. Nato upoštevajte, da medtem ko vsak udeleženec j ve p(j), nimajo informacij o p(x) za x ≠ j. Dejansko morajo za izračun te vrednosti vedeti vse pi(x), in dokler udeleženec j ne pozna vsaj enega od izbranih polinomov, o katerem nimajo dovolj informacij p(x).

To je celoten proces generiranja polinoma, ki je bil potreben v zadnjem razdelku. Koraki 1, 2 in 4 zgoraj imajo dokaj očitno izvedbo. Toda korak 3 ni tako trivialen.

Natančneje, moramo biti sposobni dokazati, da je šifrirano pi(j) res ustrezajo objavljenim pi(j)G. Če tega ne moremo dokazati, napadalec i namesto tega lahko pošlje smeti pi(j) udeležencu j, in udeleženec j ne bo mogel dobiti prave vrednosti pi(j), in ne bo mogel izračunati njegove zasebne komponente.

Obstaja kriptografski protokol, ki omogoča ustvarjanje dodatnega sporočila dokaziloi(j), tako da ima vsak udeleženec neko vrednost e, kot tudi proofi(j) и pi(j)G, lahko to lokalno preveri e - je resnično pi(j), šifrirano s ključem udeleženca j. Na žalost je obseg takih dokazov neverjetno velik in glede na to, da jih je treba objaviti O (nk) Takih dokazov ni mogoče uporabiti za ta namen.

Namesto da bi to dokazal pi(j) соответствующий pi(j)G lahko dodelimo zelo dolgo časovno obdobje v protokolu za generiranje polinoma, v katerem vsi udeleženci preverjajo prejeto šifrirano pi(j), in če dešifrirano sporočilo ne ustreza javnosti pi(j)G, objavijo kriptografski dokaz, da šifrirano sporočilo, ki so ga prejeli, ni pravilno. Dokažite, da sporočilo ne соответствующий pi(G) veliko lažje kot dokazati, da se ujema. Treba je opozoriti, da to zahteva, da se vsak udeleženec pojavi na spletu vsaj enkrat v času, ki je dodeljen za ustvarjanje takšnih dokazov, in se zanaša na predpostavko, da bo, če objavijo takšen dokaz, dosegel vse druge udeležence v istem dodeljenem času.

Če se udeleženec v tem času ni pojavil na spletu in je imel vsaj eno napačno komponento, potem ta udeleženec ne bo mogel sodelovati pri nadaljnjem ustvarjanju številke. Protokol pa bo še vedno deloval, če obstaja vsaj k udeleženci, ki so pravkar prejeli pravilne komponente ali uspeli pustiti dokazilo o nepravilnosti v dodeljenem času.

Dokazila o pravilnosti H_i

Zadnji del, o katerem je treba razpravljati, je, kako dokazati pravilnost objavljenega Hjaz, namreč to Hi = p(i)H, brez odpiranja p(i).

Spomnimo se, da vrednote H, G, p(i)G javno in znano vsem. Prejmi operacijo p(i) vedenje p(i)G и G imenujemo diskretni logaritem, oz dlog, in to želimo dokazati:

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

brez razkritja p(i). Konstrukcije za take dokaze obstajajo npr Schnorrjev protokol.

S to zasnovo vsak udeleženec skupaj z Hi pošlje dokazilo o pravilnosti glede na projekt.

Ko je naključno število ustvarjeno, ga morajo pogosto uporabiti udeleženci, ki niso tisti, ki so ga ustvarili. Takšni udeleženci morajo skupaj s številko poslati vse Hi in povezani dokazi.

Radovedni bralec se lahko vpraša: saj je končna naključna številka H0 in p(0)G – To je javni podatek, zakaj rabimo dokaz za vsakega posameznika Hjaz, zakaj ne bi namesto tega poslal dokaza

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

Težava je v tem, da takega dokaza ni mogoče ustvariti s protokolom Schnorr, ker nihče ne pozna vrednosti p (0), potrebno za ustvarjanje dokaza, in še več, celoten generator naključnih števil temelji na dejstvu, da nihče ne pozna te vrednosti. Zato je treba imeti vse vrednote Hi in njihove individualne dokaze za dokaz pravilnosti H0.

Vendar, če obstaja neka operacija na točkah na eliptičnih krivuljah, ki je pomensko podobna množenju, je dokaz pravilnosti H0 bi bilo nepomembno, bi se preprosto prepričali, da

H0 × G = p(0)G × H

Če izbrana krivulja podpira eliptične pare krivulj, ta dokaz deluje. V tem primeru H0 ni samo rezultat generatorja naključnih števil, kar lahko preveri vsak udeleženec, ki ve G, H и p(0)G. H0 je tudi podpis na sporočilu, ki je bilo uporabljeno kot seme, kar potrjuje to k и n udeleženci podpisali to sporočilo. Torej, če seme – je torej zgoščena vrednost bloka v protokolu blockchain H0 je hkrati večpodpis na bloku in zelo dobro naključno število.

Na koncu

Ta članek je del serije tehničnih blogov NEAR. NEAR je blockchain protokol in platforma za razvoj decentraliziranih aplikacij s poudarkom na enostavnosti razvoja in enostavni uporabi za končne uporabnike.

Koda protokola je odprta, naša implementacija je napisana v Rustu, lahko jo najdete tukaj.

Ogledate si lahko, kako izgleda razvoj za NEAR, in preizkusite v spletnem IDE tukaj.

Vse novice v ruščini lahko spremljate na skupina telegramov in skupina na VKontakte, v angleščini pa v uradnem twitter.

Se vidiva kmalu!

Vir: www.habr.com