Er det muligt at generere tilfældige tal, hvis vi ikke har tillid til hinanden? Del 2

Hej Habr!

В den første del I denne artikel diskuterede vi, hvorfor det kan være nødvendigt at generere tilfældige tal for deltagere, der ikke har tillid til hinanden, hvilke krav der stilles til sådanne tilfældige talgeneratorer, og vi overvejede to tilgange til deres implementering.

I denne del af artiklen vil vi se nærmere på en anden tilgang, der bruger tærskelsignaturer.

Lidt kryptografi

For at forstå, hvordan tærskelsignaturer fungerer, skal du forstå lidt grundlæggende kryptografi. Vi vil bruge to begreber: skalarer 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å det grundlæggende i tærskelsignaturer behøver du ikke at forstå, hvordan elliptiske kurver fungerer, bortset fra et par grundlæggende ting:

1. Punkter på en elliptisk kurve kan tilføjes og ganges med en skalar (vi vil betegne multiplikation med en skalar som xG, selvom notationen Gx også ofte brugt i litteraturen). Resultatet af addition og multiplikation med en skalar er et punkt på en elliptisk kurve.

2. Kender kun pointen G og dets produkt med en skalar xG kan ikke beregnes x.

Vi vil også bruge begrebet et polynomium p(x) grader k-1. Vi vil især bruge følgende egenskab ved polynomier: hvis vi kender værdien p(x) for enhver k anderledes x (og vi har ikke flere oplysninger om p(x)), kan vi beregne p(x) for enhver anden x.

Det er interessant for ethvert polynomium p(x) og et punkt på kurven Gat kende meningen p(x)G for enhver k forskellige betydninger x, kan vi også beregne p(x)G for enhver x.

Dette er nok information til at grave i detaljerne om, hvordan tærskelsignaturer fungerer, og hvordan man bruger dem til at generere tilfældige tal.

Generator af tilfældige tal på tærskelsignaturer

Lad os sige det n deltagere ønsker at generere et tilfældigt antal, og vi ønsker, at alle deltager k der var nok af dem til at generere et nummer, men så de angribere, der kontrollerer k-1 eller færre deltagere kunne ikke forudsige eller påvirke det genererede antal.

Antag, at der er et sådant polynomium p(x) grader k-1 hvad den første deltager ved p (1), ved den anden p(2), og så videre (n- ved det p(n)). Det antager vi også for et forudbestemt punkt G alle ved p(x)G for alle værdier x. Vi ringer p(i) "privat komponent" ideltager (fordi kun ideltageren kender hende), og svin "offentlig komponent" i-th deltager (fordi alle deltagere kender hende). Som du husker, viden svin ikke nok til at genoprette p(i).

Oprettelse af sådan et polynomium, så kun i-Den første deltager og ingen anden kendte hans private komponent - dette er den mest komplekse og interessante del af protokollen, og vi vil analysere den nedenfor. Lad os nu antage, at vi har sådan et polynomium, og at alle deltagere kender deres private komponenter.

Hvordan kan vi bruge sådan et polynomium til at generere et tilfældigt tal? Til at begynde med skal vi bruge en streng, som ikke tidligere har været brugt som input til generatoren. I tilfælde af en blockchain, hashen af ​​den sidste blok h er en god kandidat til sådan en linje. Lad deltagerne ønsker at oprette et tilfældigt tal vha h som frø. Deltagerne konverterer først h til et punkt på kurven ved hjælp af en foruddefineret funktion:

H = scalarToPoint(h)

Derefter hver deltager i beregner og udgiver Hej = p(i)H, hvad kan de gøre, fordi de ved p(i) og H. afsløring HJeg tillader ikke andre deltagere at gendanne den private komponent ideltager, og derfor kan et sæt private komponenter bruges fra blok til blok. Den dyre polynomialgenereringsalgoritme beskrevet nedenfor skal således kun udføres én gang.

Hvornår k deltagerne blev obduceret Hej = p(i)H, alle kan regne Hx = p(x)H for alle x takket være egenskaben ved polynomier, som vi diskuterede i sidste afsnit. I dette øjeblik beregner alle deltagere H0 = p(0)H, og dette er det resulterende tilfældige tal. Bemærk venligst, at ingen ved det p(0), og derfor den eneste måde at beregne p(0)H – dette er interpolation p(x)H, hvilket kun er muligt når k værdier p(i)H kendt. Åbning af en mindre mængde p(i)H giver ingen oplysninger om p(0)H.

Generatoren ovenfor har alle de egenskaber, vi ønsker: Angribere kontrollerer kun k-1 deltagere eller mindre har ingen information eller indflydelse på konklusionen, mens evt k deltagere kan beregne det resulterende antal og enhver delmængde af k deltagere vil altid komme til det samme resultat for det samme frø.

Der er et problem, som vi omhyggeligt har undgået ovenfor. For at interpolation skal virke, er det vigtigt, at værdien Hi som blev offentliggjort af hver deltager i det var virkelig det samme p(i)H. Da ingen undtagen i-deltageren ved det ikke p(i), ingen undtagen i-Det kan deltageren ikke bekræfte Hi faktisk beregnet korrekt, og uden noget kryptografisk bevis for rigtigheden Hjeg en angriber kan publicere enhver værdi som Hej, og vilkårligt påvirke outputtet af tilfældigt talgeneratoren:

Forskellige værdier af H_1 sendt af den første deltager fører til forskellige resulterende H_0

Der er mindst to måder at bevise rigtigheden på Hi, vi vil overveje dem, efter at vi har analyseret genereringen af ​​polynomiet.

Polynomisk generation

I det sidste afsnit antog vi, at vi har et sådant polynomium p(x) grader k-1 at deltageren i kender p(i), og ingen andre har nogen oplysninger om denne værdi. I det næste afsnit skal vi også bruge det til et forudbestemt punkt G alle vidste p(x)G for alle x.

I dette afsnit vil vi antage, at hver deltager lokalt har en eller anden privat nøgle xi, sådan at alle kender den tilsvarende offentlige nøgle Xi.

En mulig polynomialgenereringsprotokol er som følger:

1. Hver deltager i lokalt skaber et vilkårligt polynomium pi(x) grad k-1. De sender derefter hver deltager j значение pi(j), krypteret med offentlig nøgle Xj. Kun således i-th и j-th deltager kender pi(j). Deltager i meddeler også offentligt pi(j)G for alle j fra 1 til k inklusive.

2. Alle deltagere bruger en vis konsensus til at vælge k deltagere, hvis polynomier vil blive brugt. Da nogle deltagere kan være offline, kan vi ikke vente til alle n deltagere vil offentliggøre polynomier. Resultatet af dette trin er et sæt Z bestående af mindst k polynomier oprettet i trin (1).

3. Deltagerne sørger for, at de værdier, de kender pi(j) svarer til offentligt annonceret pi(j)G. Efter dette skridt ind Z kun polynomier, som sendes privat for pi(j) svarer til offentligt annonceret pi(j)G.

4. Hver deltager j beregner sin private komponent p(j) som en sum pi(j) for alle i в Z. Hver deltager beregner også alle værdier p(x)G som en sum pi(x)G for alle i в Z.

Bemærk, at p(x) – det er virkelig et polynomium k-1, fordi det er summen af ​​individet pi(x), som hver er et polynomium af grad k-1. Dernæst skal du bemærke, at mens hver deltager j kender p(j), de har ingen oplysninger om p(x) for x ≠ j. For at beregne denne værdi skal de faktisk vide alt pi(x), og så længe deltageren j ikke kender mindst et af de udvalgte polynomier, de ikke har tilstrækkelig information om p(x).

Dette er hele den polynomielle generationsproces, der var nødvendig i det sidste afsnit. Trin 1, 2 og 4 ovenfor har en ret indlysende implementering. Men trin 3 er ikke så trivielt.

Specifikt skal vi være i stand til at bevise det krypteret pi(j) svarer virkelig til de offentliggjorte pi(j)G. Hvis vi ikke kan bevise det, angriberen i kan sende affald i stedet for pi(j) til deltager j, og deltager j vil ikke være i stand til at få den reelle værdi pi(j), og vil ikke være i stand til at beregne sin private komponent.

Der er en kryptografisk protokol, der giver dig mulighed for at oprette en ekstra besked bevisi(j), sådan at enhver deltager har en vis værdi e, samt proofi(j) и pi(j)G, kan lokalt verificere det e - det er virkelig pi(j), krypteret med deltagerens nøgle j. Desværre er størrelsen af ​​sådanne beviser utroligt store, og givet at det er nødvendigt at offentliggøre O(nk) Sådanne beviser kan ikke bruges til dette formål.

I stedet for at bevise det pi(j) svarer til pi(j)G kan vi tildele en meget lang tidsperiode i polynomialgenereringsprotokollen, hvor alle deltagere kontrollerer det modtagne krypterede pi(j), og hvis den dekrypterede besked ikke svarer til offentligheden pi(j)G, de offentliggør et kryptografisk bevis på, at den krypterede besked, de modtog, er forkert. Bevis, at budskabet nej svarer til svin) meget nemmere end at bevise, at det matcher. Det skal bemærkes, at dette kræver, at hver deltager optræder online mindst én gang i løbet af den tid, der er tildelt til at skabe sådanne beviser, og bygger på den antagelse, at hvis de offentliggør et sådant bevis, vil det nå alle andre deltagere inden for samme tildelte tid.

Hvis en deltager ikke dukkede op online i denne periode, og han havde mindst én forkert komponent, så vil den pågældende deltager ikke være i stand til at deltage i yderligere nummergenerering. Protokollen vil dog stadig fungere, hvis der er mindst k deltagere, der enten lige har modtaget de korrekte komponenter eller formået at efterlade bevis for ukorrekthed inden for den afsatte tid.

Beviser for rigtigheden af ​​H_i

Den sidste del, der mangler at blive diskuteret, er, hvordan man kan bevise rigtigheden af ​​publiceret Hjeg, nemlig det Hej = p(i)H, uden åbning p(i).

Lad os huske, at værdierne H, G, p(i)G offentlig og kendt af alle. Modtag operation p(i) vide svin и G kaldet diskret logaritme, eller hund, og vi ønsker at bevise, at:

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

uden afsløring p(i). Konstruktioner til sådanne beviser findes f.eks Schnorr-protokollen.

Med dette design kan hver deltager sammen med Hi sender et bevis for rigtigheden i henhold til designet.

Når et tilfældigt tal er genereret, skal det ofte bruges af andre deltagere end dem, der har genereret det. Sådanne deltagere skal sammen med nummeret sende alle Hi og relaterede beviser.

En nysgerrig læser kan spørge: da det endelige tilfældige tal er H0, og p(0)G – Dette er offentlig information, hvorfor har vi brug for bevis for hver enkelt person Hjeg, hvorfor ikke sende bevis på det i stedet for

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

Problemet er, at et sådant bevis ikke kan skabes ved hjælp af Schnorr-protokollen, fordi ingen kender værdien p (0), nødvendigt for at skabe beviset, og hvad mere er, hele tilfældige talgeneratoren er baseret på det faktum, at ingen kender denne værdi. Derfor er det nødvendigt at have alle værdierne Hi og deres individuelle beviser for at bevise rigtigheden H0.

Men hvis der var en operation på punkter på elliptiske kurver, der semantisk ligner multiplikation, er beviset for rigtigheden H0 ville være trivielt, ville vi blot sørge for det

H0 × G = p(0)G × H

Hvis den valgte kurve understøtter elliptiske kurveparringer, dette bevis virker. I dette tilfælde H0 er ikke kun output fra en tilfældig talgenerator, som kan verificeres af enhver deltager, der ved G,H и p(0)G. H0 er også en signatur på den besked, der blev brugt som et frø, hvilket bekræfter det k и n deltagere underskrev denne besked. Således, hvis frø – er blokkens hash i blockchain-protokollen, altså H0 er både en multisignatur på en blok og et meget godt tilfældigt tal.

Afslutningsvis

Denne artikel er en del af en teknisk blogserie NEAR. NEAR er en blockchain-protokol og platform til udvikling af decentrale applikationer med vægt på let udvikling og brugervenlighed for slutbrugere.

Protokolkoden er åben, vores implementering er skrevet i Rust, den kan findes her.

Du kan se, hvordan udviklingen for NEAR ser ud, og eksperimentere i online IDE her.

Du kan følge alle nyhederne på russisk kl telegram gruppe og gruppe på VKontakte, og på engelsk i det officielle twitter.

Со скорых встреч!

Kilde: www.habr.com