Hello, Habr!
I I artiklen diskuterede vi, hvorfor det kan være nødvendigt at generere tilfældige tal for deltagere, der ikke stoler på hinanden, hvilke krav der stilles til sådanne tilfældige talgeneratorer, og vi gennemgik to tilgange til deres implementering.
I denne del af artiklen vil vi se nærmere på endnu en tilgang, der bruger tærskelsignaturer.
Lidt kryptografi
For at forstå, hvordan tærskelsignaturer fungerer, skal man have lidt grundlæggende viden om kryptografi. Vi vil bruge to begreber: skalærer, eller blot tal, som vi vil betegne med små bogstaver (x, y) og punkter på den elliptiske kurve, som vi vil betegne med store bogstaver.
For at forstå grundlaget for tærskelsignaturer er det ikke nødvendigt at forstå, hvordan elliptiske kurver fungerer, bortset fra nogle grundlæggende ting:
Punkter på en elliptisk kurve kan lægges sammen og ganges med et skalær (multiplikation med et skalær vil vi betegne som xG, selvom notationen Gx også ofte bruges i litteraturen). Resultatet af addition og multiplikation med et skalær er et punkt på den elliptiske kurve.
At kende kun punktet G og dets produkt med skalæren xG gør det umuligt at beregne x.
Vi vil også bruge begrebet polynomium p(x) af graden k-1. Især vil vi bruge følgende egenskab ved polynomer: hvis vi kender værdien p(x) for enhver k forskellig x (og ikke har flere oplysninger om p(x)), kan vi beregne p(x) for enhver anden x.
Det er interessant, at for ethvert polynomium p(x) og et bestemt punkt på kurven G, at kende værdien p(x)G for enhver k af forskellige værdier x, kan man også beregne p(x)G for enhver x.
Denne information er tilstrækkelig til at dykke ned i detaljerne om, hvordan tærskelsignaturer fungerer, og hvordan de bruges til at generere tilfældige tal.
Tilfældig talgenerator baseret på tærskelsignaturer
Lad os antage, at n deltagere ønsker at generere et tilfældigt tal, og vi ønsker, at deltagelsen fra enhver k af dem skal være tilstrækkelig til at generere et tal, men at angribere, der kontrollerer k-1 eller færre deltagere, ikke kan forudsige eller påvirke det genererede tal.
Lad os antage, at der findes et sådant polynomium p(x) af graden k-1, så den første deltager kender p(1), den anden kender p(2), og så videre (n-ende kender p(n)). Det er også antaget, at for et bestemt forudbestemt punkt G ved alle ved p(x)G for alle værdier x. Vi vil kalde p(i) “den private komponent” i-de deltagers (fordi kun i-deltageren kender den), og p(i)G “den offentlige komponent” i-de deltagers (fordi alle deltagere kender den). Som du husker, er viden p(i)G ikke tilstrækkeligt til at genskabe p(i).
At skabe et sådant polynomium, så kun i--deltageren og ingen andre kender sin private komponent – er den mest komplekse og interessante del af protokollen, og vi vil gennemgå det nedenfor. Indtil videre antager vi, at vi har et sådant polynomium, og at alle deltagere kender deres private komponenter.
Hvordan kan vi bruge et sådant polynomium til at generere et tilfældigt tal? Først skal vi have en streng, der ikke tidligere er brugt som input til generatoren. I tilfælde af blockchain er hash af den seneste blok h — en god kandidat til en sådan streng. Lad os antage, at deltagerne ønsker at skabe et tilfældigt tal ved at bruge h som seed. Først konverterer deltagerne h til et punkt på kurven ved hjælp af en hvilken som helst forudbestemt funktion:
H = scalarToPoint(h)
Derefter beregner og offentliggør hver deltager i Hi = p(i)H, som de kan gøre, fordi de kender p(i) og H. Afsløring H i giver ikke andre deltagere mulighed for at genskabe den private komponent-de deltagers, og derfor kan et sæt private komponenter bruges fra blok til blok. Således skal den dyre algoritme til at skabe polynomet, der er beskrevet nedenfor, kun udføres én gang. iDeltagerne har afsløret
Når k alle kan beregne som de kan gøre, fordi de kender x = i giver ikke andre deltagere mulighed for at genskabe den private komponentp(x)H for alle takket være egenskaberne ved polynomer, som vi diskuterede i det foregående afsnit. På dette tidspunkt beregner alle deltagere x H0 = p(0)H, og dette er det resulterende tilfældige tal. Bemærk, at ingen kender p(0), og derfor er den eneste måde at beregne p(0)H – at interpolere p(x)H, hvilket kun er muligt, når værdierne k p(i)H er kendt. Afsløring af ethvert mindre antal giver ingen information om er kendt. Afsløring af ethvert mindre antal p(0)H. Generatoren ovenfor har alle de egenskaber, vi ønsker: angribere, der kun kontrollerer
k- -1 deltagere, eller færre, har ingen information og indflydelse på output, mens enhverdeltager kan beregne det resulterende tal, og ethvert delmængde af k deltagere kan. k Deltagerne vil altid nå frem til det samme resultat for den samme seed.
Der er ét problem, som vi forsigtigt har undgået ovenfor. For at interpolationen fungerer, er det vigtigt, at værdien i giver ikke andre deltagere mulighed for at genskabe den private komponenti som hver deltager har offentliggjort i faktisk er lig med p(i)H. Da ingen andre end iden deltagende person ved p(i), kan ingen andre end i-den deltagende person bekræfte, at Hej faktisk er blevet korrekt beregnet, og uden noget kryptografisk bevis for korrektheden i giver ikke andre deltagere mulighed for at genskabe den private komponentkan en angriber offentliggøre enhver værdi som Hej, og arbitrært påvirke output fra den tilfældige talgenerator.:
Forskellige værdier H_1, sendt af den første deltager, fører til forskellige resulterende H_0.
Der er mindst to måder at bevise korrektheden på i giver ikke andre deltagere mulighed for at genskabe den private komponenti, som vi vil se på, efter vi har behandlet polynomiegenereringen.
Polynomiegenerering
I det tidligere afsnit antog vi, at vi har et sådant polynomium p(x) af graden k-1 som den deltagende person i kender p(i), og ingen andre har nogen information om denne værdi. I det næste afsnit vil vi også have brug for, at for et bestemt forudbestemt punkt G alle kender p(x)G takket være egenskaberne ved polynomer, som vi diskuterede i det foregående afsnit. På dette tidspunkt beregner alle deltagere x.
I dette afsnit antager vi, at hver deltager har lokalt en privat nøgle xi, sådan at den tilsvarende offentlige nøgle Xi er kendt af alle.
En mulig protokol for polynomiegenerering er den følgende:
Hver deltager i lokalt opretter et vilkårligt polynomium pi(x) af graden k-1. De sender derefter til hver deltager j værdien pi(j), krypteret med den offentlige nøgle Xj. Således ved kun i-den og j-den deltager, hvad pi(j) er. Deltageren i annoncerer også offentligt pi(j)G takket være egenskaberne ved polynomer, som vi diskuterede i det foregående afsnit. På dette tidspunkt beregner alle deltagere j fra 1 op til k inklusive.
Alle deltagere bruger en form for konsensus til at vælge k de deltagere, hvis polynomier vil blive brugt. Da nogle deltagere kan være offline, kan vi ikke vente, indtil alle n deltagere offentliggør polynomier. Resultatet af dette trin – mængden Z består af mindst k polynomier, der er oprettet i trin (1)..
Deltagerne sikrer, at de kendte værdier pi(j) svarer til de offentligt annoncerede pi(j)G. Efter dette trin skal der kun være polynomier, for hvilke privat overførte Z beregner deres private komponent pi(j) svarer til de offentligt annoncerede pi(j)G.
Hver deltager j p(j) som summen i(j) for alle p. Hver deltager beregner også alle værdier i i Zpi(x)G for alle i p(x)G i(j) for alle p(x) – i Z.
Bemærk venligst, at det er faktisk et polynomium af graden k-1. k-1, fordi det er summen af de individuelle pi(x), hvor hver enkelt er et polynomium af grad k-1. Bemærk desuden, at mens hver deltager j kender p(j), de har ingen information om p(x) for x ≠ j. Faktisk, for at beregne denne værdi, skal de vide alt om pi(x), og så længe deltageren j ikke kender mindst et af de valgte polynomer, har de ikke tilstrækkelig information om p(x).
Dette er hele processen til at generere polynomet, som var nødvendig i det foregående afsnit. Trin 1, 2 og 4 ovenfor har en ret åbenlys implementation. Men trin 3 er ikke så trivielt.
Specifikt skal vi være i stand til at bevise, at de krypterede pi(j) virkelig svarer til de offentliggjorte pi(j)G. Hvis vi ikke kan bevise det, kan en angriber i sender affald i stedet for pi(j) til deltageren j, og deltageren j vil ikke kunne få den rigtige værdi pi(j), og vil ikke kunne beregne sin private komponent.
Der er en kryptografisk protokol, der gør det muligt at skabe en yderligere besked proofi(j), sådan at enhver deltager, der har en vis værdi e, samt proofi(j) og pi(j)G, kan lokalt sikre, at e – det er faktisk pi(j), krypteret med deltagerens nøgle j. Desværre er størrelsen af en sådan bevis utrolig stor, og idet der skal offentliggøres O(nk) sådanne beviser, kan de ikke bruges til dette formål.
I stedet for at bevise, at pi(j) svarer til pi(j)G kan vi i protokollen til generering af polynomiet afsætte en meget lang periode, hvor alle deltagere kontrollerer de modtagne krypterede pi(j), og hvis den dekrypterede besked ikke svarer til det offentlige pi(j)G, offentliggør de et kryptografisk bevis for, at den krypterede besked, de har modtaget, er forkert. At bevise, at beskeden ikke svarer til pi(G) er meget lettere end at bevise, at den svarer til. Det skal bemærkes, at dette kræver, at hver deltager dukker op på netværket mindst én gang i den tid, der er afsat til at skabe sådanne beviser, og det antages, at hvis de har offentliggjort et sådant bevis, når det når alle andre deltagere inden for den samme afsatte tid.
Hvis en deltager ikke er online i denne periode, og de faktisk har haft mindst ét forkert komponent, så vil denne specifikke deltager ikke kunne deltage i den videre generering af tal. Protokollen vil dog stadig fungere, hvis der er mindst k deltagere, der enten kun har fået korrekte komponenter, eller som har formået at efterlade bevis for ukorrekthed inden for den tildelte tid.
Beviser for korrekthed H_i
Den sidste del, vi mangler at diskutere, er, hvordan man beviser korrektheden af de offentliggjorte i giver ikke andre deltagere mulighed for at genskabe den private komponenti, nemlig at som de kan gøre, fordi de kender uden afsløring p(i).
Lad os huske, at værdierne H, G, p(i)G er offentlige og kendt af alle. Operationen til at få p(i) kendt som p(i)G og G diskret logarithme, eller dlog, og vi ønsker at bevise, at:
dlog(p(i)G, G) = dlog(Hi, i giver ikke andre deltagere mulighed for at genskabe den private komponent)
uden afsløring p(i). Konstruktioner til sådanne beviser eksisterer, for eksempel.
Med en sådan konstruktion, sender hver deltager sammen med Hej beviset for korrekthed i henhold til konstruktionen.
Når et tilfældigt tal er genereret, er det ofte nødvendigt, at deltagerne, der er forskellige fra dem, der genererede det, også skal bruge det. Sådanne deltagere skal modtage alle Hej og tilknyttede beviser sammen med tallet.
Den nysgerrige læser kan spørge: da det endelige tilfældige tal er i giver ikke andre deltagere mulighed for at genskabe den private komponent0, og p(0)G - er offentlige oplysninger, hvorfor er der behov for et bevis for hver enkelt i giver ikke andre deltagere mulighed for at genskabe den private komponenti, hvorfor i stedet ikke sende et bevis for at
dlog(p(0)G, G) = dlog(H0, i giver ikke andre deltagere mulighed for at genskabe den private komponent)
Problemet er, at det ikke er muligt at oprette et sådant bevis med Schnorr Protokol, fordi ingen kender værdien p(0), nødvendig for at oprette beviset, og desuden er hele generatoren af tilfældige tal baseret på, at ingen kender denne værdi. Derfor er det nødvendigt at have alle værdier Hej og deres individuelle beviser for at bevise korrektheden. i giver ikke andre deltagere mulighed for at genskabe den private komponent0.
Men hvis der var en eller anden operation ved punkterne på elliptiske kurver, som er semantisk lig med multiplikation, ville beviset for korrektheden H0 være trivielt, vi ville blot sikre os, at
i giver ikke andre deltagere mulighed for at genskabe den private komponent0 × G = p(0)G × H
Hvis den valgte kurve understøtter , fungerer et sådant bevis. I dette tilfælde i giver ikke andre deltagere mulighed for at genskabe den private komponent0 - er ikke blot output fra generatoren af tilfældige tal, som enhver deltager, der kender G, H og p(0)G. H0 – dette er også en signatur på beskeden, der blev brugt som seed, der bekræfter, at k og n deltagerne har underskrevet denne besked. Dermed, hvis seed – er en hash af blokken i blockchain-protokollen, så H0 er det samtidig en multi-signatur på blokken og et meget godt tilfældigt tal.
Afslutningsvis
Denne artikel er en del af en serie tekniske artikler på bloggen . NEAR er en blockchain-protokol og platform til udvikling af decentraliserede applikationer med fokus på enkelhed i udviklingen og brugervenlighed for slutbrugerne.
Protokolens kode er åben, vores implementering er skrevet i Rust, og den kan findes .
Du kan se, hvordan udviklingen under NEAR ser ud, og eksperimentere i online-IDE'en. .
Hold dig opdateret med alle nyheder på russisk i og i mens du kan finde nyheder på engelsk i det officielle .
Vi ses snart!
Kilde: habr.com
