Er det mulig å generere tilfeldige tall hvis vi ikke stoler på hverandre? Del 2

Hei Habr!

В første del I denne artikkelen diskuterte vi hvorfor det kan være nødvendig å generere tilfeldige tall for deltakere som ikke stoler på hverandre, hvilke krav som stilles til slike tilfeldige tallgeneratorer, og vurderte to tilnærminger til implementeringen av dem.

I denne delen av artikkelen skal vi se nærmere på en annen tilnærming som bruker terskelsignaturer.

Litt kryptografi

For å forstå hvordan terskelsignaturer fungerer, må du forstå litt grunnleggende kryptografi. Vi vil bruke to begreper: skalarer, eller ganske enkelt tall, som vi vil angi med små bokstaver (x, y) og punkter på den elliptiske kurven, som vi vil betegne med store bokstaver.

For å forstå det grunnleggende om terskelsignaturer, trenger du ikke å forstå hvordan elliptiske kurver fungerer, annet enn noen få grunnleggende ting:

1. Punkter på en elliptisk kurve kan legges til og multipliseres med en skalar (vi vil betegne multiplikasjon med en skalar som xG, selv om notasjonen Gx også ofte brukt i litteraturen). Resultatet av addisjon og multiplikasjon med en skalar er et punkt på en elliptisk kurve.

2. Kunne bare poenget G og dets produkt med en skalar xG kan ikke beregnes x.

Vi vil også bruke begrepet et polynom p (x) grad k-1. Spesielt vil vi bruke følgende egenskap til polynomer: hvis vi vet verdien p (x) for noen k annerledes x (og vi har ikke mer informasjon om p (x)), kan vi beregne p (x) for noen andre x.

Det er interessant at for ethvert polynom p (x) og et punkt på kurven Gkjenne meningen p(x)G for noen k forskjellige betydninger x, kan vi også beregne p(x)G for noen x.

Dette er nok informasjon til å grave i detaljene om hvordan terskelsignaturer fungerer og hvordan du bruker dem til å generere tilfeldige tall.

Tilfeldig tallgenerator på terskelsignaturer

La oss si det n deltakere ønsker å generere et tilfeldig antall, og vi vil at alle skal delta k det var nok av dem til å generere et tall, men slik at angriperne som kontrollerer k-1 eller færre deltakere kunne ikke forutsi eller påvirke antallet genererte.

Anta at det finnes et slikt polynom p (x) grad k-1 hva den første deltakeren vet p (1), vet den andre p(2), og så videre (n-det vet p(n)). Vi antar også det for et forhåndsbestemt punkt G alle vet p(x)G for alle verdier x. Vi ringer p(i) "privat komponent" ideltaker (fordi kun ideltakeren kjenner henne), og gris "offentlig komponent" i-th deltaker (fordi alle deltakere kjenner henne). Som du husker, kunnskap gris ikke nok til å gjenopprette p(i).

Å lage et slikt polynom slik at bare i-Den første deltakeren og ingen andre kjente til hans private komponent - dette er den mest komplekse og interessante delen av protokollen, og vi vil analysere den nedenfor. For nå, la oss anta at vi har et slikt polynom og at alle deltakerne kjenner sine private komponenter.

Hvordan kan vi bruke et slikt polynom til å generere et tilfeldig tall? Til å begynne med trenger vi en streng som ikke tidligere har vært brukt som input til generatoren. I tilfelle av en blokkjede, hashen til den siste blokken h er en god kandidat for en slik linje. La deltakerne ønsker å lage et tilfeldig tall ved hjelp av h som frø. Deltakerne konverterer først h til et punkt på kurven ved å bruke en forhåndsdefinert funksjon:

H = scalarToPoint(h)

Deretter hver deltaker i beregner og publiserer Hei = p(i)H, hva kan de gjøre fordi de vet p(i) og H. avsløring HJeg tillater ikke andre deltakere å gjenopprette den private komponenten ideltaker, og derfor kan ett sett med private komponenter brukes fra blokk til blokk. Dermed trenger den dyre polynomgenereringsalgoritmen beskrevet nedenfor bare å bli utført én gang.

Når k deltakerne ble obdusert Hei = p(i)H, alle kan regne Hx = p(x)H for alle x takket være egenskapen til polynomer som vi diskuterte i den siste delen. I dette øyeblikket beregner alle deltakerne H0 = p(0)H, og dette er det resulterende tilfeldige tallet. Vær oppmerksom på at ingen vet p(0), og derfor den eneste måten å regne på p(0)H – dette er interpolasjon p(x)H, som kun er mulig når k verdier p(i)H kjent. Åpning av et mindre kvantum p(i)H gir ingen informasjon om p(0)H.

Generatoren ovenfor har alle egenskapene vi ønsker: angripere kontrollerer kun k-1 deltakere eller færre har ingen informasjon eller innflytelse på konklusjonen, mens evt k deltakere kan beregne det resulterende antallet, og enhver delmengde av k deltakere vil alltid komme til samme resultat for samme frø.

Det er ett problem som vi nøye unngått ovenfor. For at interpolasjon skal fungere er det viktig at verdien Hi som ble publisert av hver deltaker i det var virkelig det samme p(i)H. Siden ingen unntatt i-deltakeren vet ikke p(i), ingen unntatt i-deltakeren kan ikke bekrefte det Hi faktisk beregnet riktig, og uten noe kryptografisk bevis for korrekthet Hjeg en angriper kan publisere hvilken som helst verdi som Hei, og vilkårlig påvirke utgangen til tilfeldig tallgeneratoren:

Ulike verdier av H_1 sendt av den første deltakeren fører til forskjellige resulterende H_0

Det er minst to måter å bevise riktigheten på Hi, vi vil vurdere dem etter at vi har analysert genereringen av polynomet.

Polynomgenerering

I den siste delen antok vi at vi har et slikt polynom p (x) grad k-1 at deltakeren i han vet p(i), og ingen andre har informasjon om denne verdien. I neste avsnitt vil vi også trenge det for et forhåndsbestemt punkt G alle visste p(x)G for alle x.

I denne delen vil vi anta at hver deltaker lokalt har en privat nøkkel xi, slik at alle kjenner den tilhørende offentlige nøkkelen Xi.

En mulig polynomgenereringsprotokoll er som følger:

1. Hver deltaker i skaper lokalt et vilkårlig polynom pi(x) grad k-1. De sender deretter hver deltaker j значение pi(j), kryptert med offentlig nøkkel Xj. Bare dermed i-th и j-th deltaker vet pi(j). Deltager i kunngjør også offentlig pi(j)G for alle j fra 1 til k inkluderende.

2. Alle deltakerne bruker en viss konsensus for å velge k deltakere hvis polynomer vil bli brukt. Siden noen deltakere kan være offline, kan vi ikke vente til alle n deltakerne vil publisere polynomer. Resultatet av dette trinnet er et sett Z bestående av minst k polynomer opprettet i trinn (1).

3. Deltakerne sørger for at verdiene de kjenner pi(j) tilsvarer offentlig annonsert pi(j)G. Etter dette steget inn Z bare polynomer som overføres privat pi(j) tilsvarer offentlig annonsert pi(j)G.

4. Hver deltaker j beregner sin private komponent pysjamas) som en sum pi(j) for alle i в Z. Hver deltaker beregner også alle verdier p(x)G som en sum pi(x)G for alle i в Z.

Vær oppmerksom på det p(x) – det er egentlig et polynom k-1, fordi det er summen av individet pi(x), som hver er et polynom med grad k-1. Legg deretter merke til at mens hver deltaker j han vet pysjamas), de har ingen informasjon om p (x) for x ≠ j. Faktisk, for å beregne denne verdien, trenger de å vite alt pi(x), og så lenge deltakeren j ikke kjenner minst ett av de valgte polynomene, de har ikke tilstrekkelig informasjon om p(x).

Dette er hele polynomgenereringsprosessen som var nødvendig i den siste delen. Trinn 1, 2 og 4 ovenfor har en ganske åpenbar implementering. Men trinn 3 er ikke så trivielt.

Spesielt må vi være i stand til å bevise det kryptert pi(j) svarer virkelig til de publiserte pi(j)G. Hvis vi ikke kan bevise det, angriperen i kan sende søppel i stedet pi(j) til deltaker j, og deltaker j vil ikke kunne få den virkelige verdien pi(j), og vil ikke være i stand til å beregne sin private komponent.

Det er en kryptografisk protokoll som lar deg lage en ekstra melding bevisi(j), slik at enhver deltaker, har en viss verdi e, samt proofi(j) и pi(j)G, kan lokalt verifisere det e - det er virkelig pi(j), kryptert med deltakerens nøkkel j. Dessverre er størrelsen på slike bevis utrolig store, og gitt at det er nødvendig å publisere O (nk) Slike bevis kan ikke brukes til dette formålet.

I stedet for å bevise det pi(j) соответствует pi(j)G vi kan tildele en veldig lang tidsperiode i polynomgenereringsprotokollen, hvor alle deltakere sjekker det mottatte krypterte pi(j), og hvis den dekrypterte meldingen ikke samsvarer med offentligheten pi(j)G, publiserer de et kryptografisk bevis på at den krypterte meldingen de mottok er feil. Bevis at meldingen no соответствует gris) mye enklere enn å bevise at det stemmer. Det skal bemerkes at dette krever at hver deltaker skal vises på nettet minst én gang i løpet av tiden som er tildelt for å lage slike bevis, og er avhengig av antagelsen om at hvis de publiserer et slikt bevis, vil det nå alle andre deltakere innen samme tildelte tid.

Hvis en deltaker ikke dukket opp på nettet i løpet av denne tidsperioden, og han hadde minst én feil komponent, vil ikke den aktuelle deltakeren kunne delta i videre nummergenerering. Protokollen vil imidlertid fortsatt fungere hvis det er minst k deltakere som enten nettopp har mottatt de riktige komponentene eller klarte å legge igjen bevis på feil innen den tildelte tiden.

Bevis for riktigheten av H_i

Den siste delen som gjenstår å diskutere er hvordan man kan bevise riktigheten av publisert Hjeg, nemlig det Hei = p(i)H, uten åpning p(i).

La oss huske at verdiene H, G, p(i)G offentlig og kjent for alle. Motta operasjon p(i) vite gris и G kalt diskret logaritme, eller hund, og vi ønsker å bevise at:

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

uten avsløring p(i). Konstruksjoner for slike bevis finnes for eksempel Schnorr-protokollen.

Med dette designet vil hver deltaker sammen med Hi sender et korrekthetsbevis i henhold til designet.

Når et tilfeldig tall er generert, må det ofte brukes av andre deltakere enn de som genererte det. Slike deltakere, sammen med nummeret, må sende alle Hi og relaterte bevis.

En nysgjerrig leser kan spørre: siden det endelige tilfeldige tallet er H0, og p(0)G – Dette er offentlig informasjon, hvorfor trenger vi bevis for hver enkelt Hjeg, hvorfor ikke sende bevis på det i stedet

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

Problemet er at et slikt bevis ikke kan lages ved hjelp av Schnorr-protokollen fordi ingen vet verdien p (0), nødvendig for å lage beviset, og dessuten er hele tilfeldig tallgeneratoren basert på det faktum at ingen kjenner denne verdien. Derfor er det nødvendig å ha alle verdiene Hi og deres individuelle bevis for å bevise riktigheten H0.

Men hvis det var en operasjon på punkter på elliptiske kurver som er semantisk lik multiplikasjon, beviset på riktigheten H0 ville være trivielt, vi ville ganske enkelt sørge for det

H0 × G = p(0)G × H

Hvis den valgte kurven støtter elliptiske kurveparinger, dette beviset fungerer. I dette tilfellet H0 er ikke bare utdata fra en tilfeldig tallgenerator, som kan verifiseres av enhver deltaker som vet G, H и p(0)G. H0 er også en signatur på meldingen som ble brukt som et frø, som bekrefter det k и n deltakerne signerte denne meldingen. Således, hvis frø - er hashen til blokken i blokkjedeprotokollen, da H0 er både en multisignatur på en blokk og et veldig godt tilfeldig tall.

i konklusjonen

Denne artikkelen er en del av en teknisk bloggserie NEAR. NEAR er en blokkjedeprotokoll og plattform for utvikling av desentraliserte applikasjoner med vekt på enkel utvikling og brukervennlighet for sluttbrukere.

Protokollkoden er åpen, implementeringen vår er skrevet i Rust, den kan finnes her.

Du kan se hvordan utviklingen for NEAR ser ut og eksperimentere i den elektroniske IDE her.

Du kan følge alle nyhetene på russisk på telegram gruppe og gruppe på VKontakte, og på engelsk i det offisielle Twitter.

Ser deg snart!

Kilde: www.habr.com