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

Hei Habr!

I denne artikkelen vil jeg snakke om generering av pseudo-tilfeldige tall av deltakere som ikke stoler på hverandre. Som vi vil se nedenfor, er det ganske enkelt å implementere en "nesten" god generator, men en veldig god en er vanskelig.

Hvorfor skulle det være nødvendig å generere tilfeldige tall blant deltakere som ikke stoler på hverandre? Ett applikasjonsområde er desentraliserte applikasjoner. For eksempel, en applikasjon som aksepterer et spill fra en deltaker og enten dobler beløpet med 49 % sannsynlighet eller tar bort med 51 % sannsynlighet, vil bare fungere hvis den objektivt kan motta et tilfeldig tall. Hvis en angriper kan påvirke utfallet av tilfeldig tallgeneratoren, og til og med øke sjansen for å motta en utbetaling i applikasjonen litt, vil han lett ødelegge den.

Når vi designer en distribuert tilfeldig tallgenereringsprotokoll, vil vi at den skal ha tre egenskaper:

1. Han må være objektiv. Ingen deltaker skal med andre ord på noen måte påvirke resultatet av tilfeldig tallgeneratoren.

2. Han må være uforutsigbar. Med andre ord, ingen deltaker skal være i stand til å forutsi hvilket tall som vil bli generert (eller utlede noen av dets egenskaper) før det genereres.

3. Protokollen må være levedyktig, det vil si motstandsdyktig mot at en viss prosentandel av deltakerne kobler seg fra nettverket eller bevisst prøver å stoppe protokollen.

I denne artikkelen vil vi se på to tilnærminger: RANDAO + VDF og tilnærmingen til slettekoder. I neste del vil vi undersøke i detalj tilnærmingen basert på terskelsignaturer.

Men først, la oss se på en enkel og ofte brukt algoritme som er levedyktig, uforutsigbar, men partisk.

RANDAO

RANDAO er en veldig enkel og derfor ganske vanlig tilnærming til å generere tilfeldighet. Alle nettverksdeltakere velger først lokalt et pseudorandomnummer, deretter sender hver deltaker en hash av det valgte nummeret. Deretter bytter deltakerne på å avsløre sine valgte tall og utføre en XOR-operasjon på de avslørte tallene, og resultatet av denne operasjonen blir resultatet av protokollen.

Trinnet med å publisere hashen før avsløring av tallene er nødvendig slik at angriperen ikke kan velge nummeret sitt etter at han har sett tallene til de andre deltakerne. Dette vil tillate ham å praktisk talt på egen hånd bestemme utgangen til tilfeldig tallgeneratoren.

I løpet av protokollen må deltakerne komme til en felles avgjørelse (såkalt konsensus) to ganger: når de skal begynne å avsløre de valgte tallene, og derfor slutte å akseptere hash, og når de skal slutte å godta de valgte tallene og beregne den resulterende tilfeldige Antall. Å ta slike beslutninger mellom deltakere som ikke stoler på hverandre er ikke en lett oppgave i seg selv, og vi vil komme tilbake til det i fremtidige artikler; i denne artikkelen vil vi anta at en slik konsensusalgoritme er tilgjengelig for oss.

Hvilke av egenskapene vi beskrev ovenfor har RANDAO? Den er uforutsigbar, har samme vitalitet som den underliggende konsensusprotokollen, men den er partisk. Spesifikt kan en angriper observere nettverket, og etter at andre deltakere har avslørt tallene sine, kan han beregne XOR og bestemme om han skal avsløre nummeret sitt for å påvirke utfallet. Selv om dette hindrer angriperen i å bestemme utdataene til tilfeldig tallgeneratoren på egenhånd, gir det ham fortsatt 1 bit av innflytelse. Og hvis angripere kontrollerer flere deltakere, vil antallet biter de kontrollerer være lik antallet deltakere under deres kontroll.

Angripernes innflytelse kan reduseres kraftig ved å kreve at deltakerne avslører tallene i rekkefølge. Da vil angriperen kun kunne påvirke utfallet hvis den åpnes sist. Selv om påvirkningen er betydelig mindre, er algoritmen fortsatt partisk.

RANDAO+VDF

En måte å gjøre RANDAO objektiv på er denne: etter at alle tallene er avslørt og XOR er beregnet, mates resultatet inn i inngangen til en funksjon, som tar veldig lang tid å beregne, men lar deg sjekke riktigheten av beregning veldig raskt.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Denne funksjonen kalles Verifiable Delay Function, eller VDF. Hvis det tar lengre tid å beregne det endelige resultatet enn tallavsløringsstadiet, vil angriperen ikke kunne forutsi effekten av å vise eller skjule nummeret sitt, og derfor vil han miste muligheten til å påvirke resultatet.

Å utvikle gode VDF-er er ekstremt vanskelig. Det har vært flere gjennombrudd den siste tiden, bl.a. dette и dette, som gjorde VDF mer praktisk i praksis, og Ethereum 2.0 planlegger å bruke RANDAO med VDF som tilfeldig tallkilde på sikt. Bortsett fra det faktum at denne tilnærmingen er uforutsigbar og objektiv, har den den ekstra fordelen av å være levedyktig hvis minst to deltakere er tilgjengelige på nettverket (forutsatt at konsensusprotokollen som brukes er levedyktig når man arbeider med et så lite antall deltakere).

Den største utfordringen med denne tilnærmingen er å sette opp VDF slik at selv en deltaker med svært kostbar spesialisert maskinvare ikke vil være i stand til å beregne VDF før slutten av oppdagelsesfasen. Ideelt sett bør algoritmen til og med ha en betydelig sikkerhetsmargin, for eksempel 10x. Figuren nedenfor viser et angrep fra en skuespiller som har en spesialisert ASIC som lar ham kjøre en VDF raskere enn tiden som er tildelt for å avsløre RANDAO-bekreftelsen. En slik deltaker kan fortsatt beregne det endelige resultatet ved å bruke eller ikke bruke tallet sitt, og deretter, basert på beregningen, velge om han vil vise det eller ikke.

For VDF-familien nevnt ovenfor kan ytelsen til en dedikert ASIC være 100+ ganger høyere enn konvensjonell maskinvare. Så hvis distribusjonsfasen varer i 10 sekunder, må VDF beregnet på en slik ASIC ta mer enn 100 sekunder for å ha en 10x sikkerhetsmargin, og dermed må den samme VDF beregnet på råvaremaskinvare ta 100x 100 sekunder = ~3 timer.

Ethereum Foundation planlegger å løse dette problemet ved å lage sine egne offentlig tilgjengelige, gratis ASIC-er. Når dette skjer, kan alle andre protokoller også dra nytte av denne teknologien, men inntil da vil RANDAO+VDF-tilnærmingen ikke være like levedyktig for protokoller som ikke kan investere i å utvikle sine egne ASIC-er.

Mange artikler, videoer og annen informasjon om VDF er samlet på dette nettstedet.

Vi bruker slettekoder

I denne delen vil vi se på en tilfeldig tallgenereringsprotokoll som bruker slette koder. Den kan tolerere opptil ⅓ angripere mens den forblir levedyktig, og lar opptil ⅔ angripere eksistere før de kan forutsi eller påvirke utfallet.

Hovedideen til protokollen er som følger. For enkelhets skyld, la oss anta at det er nøyaktig 100 deltakere. La oss også anta at alle deltakere lokalt har en privat nøkkel, og de offentlige nøklene til alle deltakerne er kjent for alle deltakerne:

1. Hver deltaker lokalt kommer opp med en lang streng, deler den i 67 deler, lager slettekoder for å oppnå 100 delinger slik at alle 67 er nok til å gjenopprette strengen, tildeler hver av de 100 delingene til en av deltakerne og krypterer dem med samme deltakers offentlige nøkkel. Alle kodede aksjer publiseres deretter.

2. Deltakerne bruker en form for konsensus for å komme til enighet om kodede sett fra spesifikke 67 deltakere.

3. Når konsensus er oppnådd, tar hver deltaker de kodede aksjene i hvert av de 67 settene kryptert med deres offentlige nøkkel, dekrypterer alle slike delinger og publiserer alle slike dekrypterte delinger.

4. Når 67 deltakere har fullført trinn (3), kan alle avtalte sett dekodes og rekonstrueres fullstendig på grunn av egenskapene til slettekoder, og det endelige tallet kan fås som en XOR av de første radene som deltakerne startet med i (1) .

Denne protokollen kan vise seg å være objektiv og uforutsigbar. Det resulterende tilfeldige tallet bestemmes etter at konsensus er oppnådd, men er ikke kjent for noen før ⅔ av deltakerne dekoder delene kryptert med deres offentlige nøkkel. Dermed blir det tilfeldige tallet bestemt før informasjon som er tilstrekkelig til å rekonstruere det publiseres.

Hva skjer hvis en av deltakerne i trinn (1) sendte kodede delinger til de andre deltakerne som ikke er riktig slettekode for en streng? Uten ytterligere endringer vil forskjellige deltakere enten ikke kunne gjenopprette strengen i det hele tatt, eller de vil gjenopprette forskjellige strenger, noe som vil resultere i at forskjellige deltakere mottar et annet tilfeldig tall. For å forhindre dette kan du gjøre følgende: hver deltaker, i tillegg til de kodede andelene, beregner også Merkla tre alle slike delinger, og sender hver deltaker både selve den kodede andelen og roten til merkle-treet, og bevis på inkludering av andelen i merkle-treet. I konsensus i trinn (2) blir deltakerne ikke bare enige om et sett med sett, men om et sett med spesifikke røtter til slike trær (hvis en deltaker avvek fra protokollen og sendte forskjellige merkle trerøtter til forskjellige deltakere, og to slike røtter vises under konsensus, hans rad er ikke inkludert i resultatsettet). Som et resultat av konsensus vil vi ha 67 kodede linjer og de tilsvarende røttene til merkle-treet slik at det er minst 67 deltakere (ikke nødvendigvis de samme som foreslo de tilsvarende linjene), som for hver av de 67 linjene har en melding med en andel av slettekoden, og et bevis på at forekomsten av deres andel i det tilsvarende treet bleknet.

Når deltakeren i trinn (4) dechiffrerer 67 slag for en bestemt streng og prøver å rekonstruere den opprinnelige strengen fra dem, er ett av alternativene mulig:

1. Strengen gjenopprettes, og hvis den så slettes kodet igjen, og Merkle-treet beregnes for de lokalt beregnede andelene, faller roten sammen med den det ble oppnådd konsensus om.

2. Raden gjenopprettes, men den lokalt beregnede roten samsvarer ikke med den der konsensus ble oppnådd.

3. Raden er ikke gjenopprettet.

Det er lett å vise at hvis alternativ (1) skjedde for minst én deltaker ovenfor, så skjedde alternativ (1) for alle deltakere, og omvendt, hvis alternativ (2) eller (3) skjedde for minst én deltaker, så for alle deltakere vil alternativ (2) eller (3) skje. Derfor, for hver rad i settet, vil enten alle deltakerne gjenopprette den, eller alle deltakerne vil ikke gjenopprette den. Det resulterende tilfeldige tallet er da en XOR av bare radene som deltakerne var i stand til å gjenopprette.

Terskelsignaturer

En annen tilnærming til tilfeldighet er å bruke det som kalles BLS-terskelsignaturer. En tilfeldig tallgenerator basert på terskelsignaturer har nøyaktig de samme garantiene som den slettekodebaserte algoritmen beskrevet ovenfor, men har et betydelig lavere asymptotisk antall meldinger sendt over nettverket for hvert generert nummer.

BLS-signaturer er et design som lar flere deltakere lage én felles signatur for en melding. Disse signaturene brukes ofte for å spare plass og båndbredde ved ikke å kreve at flere signaturer sendes ut. 

En vanlig applikasjon for BLS-signaturer i blokkjedeprotokoller, i tillegg til å generere tilfeldige tall, er blokksignering i BFT-protokoller. La oss si at 100 deltakere oppretter blokker, og en blokk anses som endelig hvis 67 av dem signerer den. De kan alle sende inn sine deler av BLS-signaturen og bruke en eller annen konsensusalgoritme for å bli enige om 67 av dem og deretter slå dem sammen til én BLS-signatur. Eventuelle 67 (eller flere) deler kan brukes til å lage den endelige signaturen, som vil avhenge av hvilke 67 signaturer som ble kombinert og derfor kan variere, selv om forskjellige valg av de 67 deltakerne vil skape en annen signatur, vil enhver slik signatur være gyldig signatur for blokken. De resterende deltakerne trenger da kun å motta og bekrefte kun én signatur per blokk, i stedet for 67, over nettverket, noe som reduserer belastningen på nettverket betydelig.

Det viser seg at hvis de private nøklene som deltakerne bruker genereres på en bestemt måte, vil den resulterende signaturen være den samme, uansett hvilke 67 signaturer (eller flere, men ikke færre). Dette kan brukes som en kilde til tilfeldighet: deltakerne blir først enige om en melding som de vil signere (dette kan være utdata fra RANDAO eller bare hashen fra den siste blokken, det spiller ingen rolle så lenge den endres hver gang og er konsistent) og lag en BLS-signatur for den. Resultatet av generasjonen vil være uforutsigbart inntil 67 deltakere gir sine deler, og etter det er resultatet allerede forhåndsbestemt og kan ikke avhenge av handlingene til noen deltaker.

Denne tilnærmingen til tilfeldighet er levedyktig så lenge minst ⅔ av deltakerne online både følger protokollen, og er objektiv og uforutsigbar så lenge minst ⅓ av deltakerne følger protokollen. Det er viktig å merke seg at en angriper som kontrollerer mer enn ⅓ men mindre enn ⅔ av deltakerne kan stoppe protokollen, men kan ikke forutsi eller påvirke utgangen.

Terskelsignaturer i seg selv er et veldig interessant tema. I den andre delen av artikkelen vil vi analysere i detalj hvordan de fungerer, og nøyaktig hvordan det er nødvendig å generere deltakernøkler slik at terskelsignaturer kan brukes som en tilfeldig tallgenerator.

i konklusjonen

Denne artikkelen er den første i en serie tekniske bloggartikler 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