Innledning
"Generering av tilfeldige tall er for viktig til å overlates til tilfeldighetene."
Robert Cavue, 1970
Denne artikkelen er viet til den praktiske anvendelsen av løsninger ved bruk av kollektiv generering av tilfeldige tall i et upålitelig miljø. Kort sagt, hvordan og hvorfor tilfeldig brukes i blokkjeder, og litt om hvordan man skiller «god» tilfeldig fra «dårlig». Å generere et virkelig tilfeldig tall er et ekstremt vanskelig problem, selv på en enkelt datamaskin, og har lenge blitt studert av kryptografer. Vel, i desentraliserte nettverk er generering av tilfeldige tall enda mer kompleks og viktig.
Det er i nettverk der deltakerne ikke stoler på hverandre at evnen til å generere et udiskutabelt tilfeldig tall gjør at vi effektivt kan løse mange kritiske problemer og forbedre eksisterende ordninger betydelig. Dessuten er ikke gambling og lotterier det første målet her, slik det kan se ut til å begynne med for den uerfarne leseren.
Generering av tilfeldig tall
Datamaskiner kan ikke generere tilfeldige tall selv, de trenger hjelp utenfra for å gjøre det. Datamaskinen kan få en tilfeldig verdi fra for eksempel musebevegelser, mengden minne som brukes, streifstrømmer på prosessorpinnene og mange andre kilder som kalles entropikilder. Disse verdiene i seg selv er ikke helt tilfeldige, siden de er innenfor et visst område eller har et forutsigbart mønster av endringer. For å gjøre slike tall til et virkelig tilfeldig tall innenfor et gitt område, brukes kryptotransformasjoner på dem for å produsere jevnt fordelte pseudo-tilfeldige verdier fra de ujevnt fordelte verdiene til entropikilden. De resulterende verdiene kalles pseudorandom fordi de ikke er virkelig tilfeldige, men er deterministisk avledet fra entropi. Enhver god kryptografisk algoritme, når du krypterer data, produserer chiffertekster som statistisk ikke burde kunne skilles fra en tilfeldig sekvens, så for å produsere tilfeldighet kan du ta en kilde til entropi, som bare gir god repeterbarhet og uforutsigbarhet av verdier selv i små områder, resten av arbeidet er å spre og blande biter i Den resulterende verdien vil bli overtatt av krypteringsalgoritmen.
For å fullføre et kort pedagogisk program, vil jeg legge til at generering av tilfeldige tall selv på én enhet er en av pilarene for å sikre sikkerheten til dataene våre. De genererte pseudo-tilfeldige tallene brukes når du etablerer sikre forbindelser i ulike nettverk, for å generere kryptografiske nøkler, for lastbalansering, integritetsovervåking og for mange flere applikasjoner. Sikkerheten til mange protokoller avhenger av evnen til å generere en pålitelig, eksternt uforutsigbar tilfeldighet, lagre den og ikke avsløre den før neste trinn i protokollen, ellers vil sikkerheten bli kompromittert. Et angrep på en pseudotilfeldig verdigenerator er ekstremt farlig og truer umiddelbart all programvare som bruker tilfeldighetsgenerering.
Alt dette bør du kunne hvis du tok et grunnleggende kurs i kryptografi, så la oss fortsette om desentraliserte nettverk.
Tilfeldig i blokkjeder
Først av alt vil jeg snakke om blokkjeder med støtte for smarte kontrakter; det er de som fullt ut kan dra nytte av mulighetene som tilbys av høykvalitets, ubestridelig tilfeldighet. Videre, for korthets skyld, vil jeg kalle denne teknologien "Offentlig verifiserbare tilfeldige beacons” eller PVRB. Siden blokkjeder er nettverk der informasjon kan verifiseres av enhver deltaker, er nøkkeldelen av navnet "Publicly Verifiable", dvs. Alle kan bruke beregninger for å få bevis på at det resulterende tallet som er lagt ut på blokkjeden har følgende egenskaper:
- Resultatet må ha en beviselig jevn fordeling, det vil si være basert på beviselig sterk kryptografi.
- Det er ikke mulig å kontrollere noen av bitene av resultatet. Resultatet kan derfor ikke forutsies på forhånd.
- Du kan ikke sabotere generasjonsprotokollen ved ikke å delta i protokollen eller ved å overbelaste nettverket med angrepsmeldinger
- Alt det ovennevnte må være motstandsdyktig mot samarbeid mellom et tillatt antall uærlige protokolldeltakere (for eksempel 1/3 av deltakerne).
Enhver mulighet for en samvirkende mindre gruppe deltakere til å produsere selv en kontrollert partall/oddetall er et sikkerhetshull. Enhver evne til gruppen til å stoppe utstedelsen av tilfeldig er et sikkerhetshull. Generelt er det mange problemer, og denne oppgaven er ikke lett...
Det ser ut til at den viktigste applikasjonen for PVRB er forskjellige spill, lotterier og generelt alle typer gambling på blokkjeden. Dette er faktisk en viktig retning, men tilfeldighet i blokkjeder har enda viktigere applikasjoner. La oss se på dem.
Konsensusalgoritmer
PVRB spiller en stor rolle i å organisere nettverkskonsensus. Transaksjoner i blokkjeder er beskyttet av en elektronisk signatur, så et "angrep på en transaksjon" er alltid inkludering/ekskludering av en transaksjon i en blokk (eller flere blokker). Og hovedoppgaven til konsensusalgoritmen er å bli enige om rekkefølgen på disse transaksjonene og rekkefølgen på blokkene som inkluderer disse transaksjonene. En nødvendig egenskap for ekte blokkjeder er også endelighet - nettverkets evne til å godta at kjeden frem til den ferdige blokken er endelig, og aldri vil bli ekskludert på grunn av utseendet til en ny gaffel. Vanligvis, for å bli enige om at en blokk er gyldig og, viktigst av alt, endelig, er det nødvendig å samle inn signaturer fra flertallet av blokkprodusenter (heretter referert til som BP - blokkprodusenter), som i det minste krever levering av blokkkjeden til alle BP-er, og distribuere signaturer mellom alle BP-er. Etter hvert som antallet BP-er vokser, vokser antallet nødvendige meldinger i nettverket eksponentielt, derfor fungerer ikke konsensusalgoritmer som krever endelighet, brukt for eksempel i Hyperledger pBFT-konsensus, med den nødvendige hastigheten, fra flere dusin BP-er, som krever et stort antall forbindelser.
Hvis det er en ubestridelig og ærlig PVRB i nettverket, kan man, selv i den enkleste tilnærmingen, velge en av blokkprodusentene basert på den og utnevne ham som "leder" i løpet av en runde av protokollen. Hvis vi har N blokkprodusenter, hvorav M: M > 1/2 N er ærlige, ikke sensurer transaksjoner og ikke splitt kjeden for å utføre et "dobbeltforbruk"-angrep, så vil bruk av en jevnt distribuert uimotsagt PVRB tillate å velge en ærlig leder med sannsynlighet M / N (M / N > 1/2). Hvis hver leder blir tildelt sitt eget tidsintervall der han kan produsere en blokk og validere kjeden, og disse intervallene er like i tid, vil blokkkjeden av ærlige BP-er være lengre enn kjeden dannet av ondsinnede BP-er, og konsensus algoritmen er avhengig av lengden på kjeden, vil ganske enkelt forkaste den "dårlige". Dette prinsippet om å tildele like deler av tiden til hver BP ble først brukt i Graphene (forgjengeren til EOS), og lar de fleste blokker lukkes med en enkelt signatur, noe som i stor grad reduserer nettverksbelastningen og lar denne konsensus fungere ekstremt raskt og jevnt. Imidlertid må EOS-nettverket nå bruke spesielle blokker (Last Irreversible Block), som bekreftes av signaturene til 2/3 BP. Disse blokkene tjener til å sikre endelighet (umuligheten av en kjedegaffel som starter før den siste siste irreversible blokken).
I virkelige implementeringer er protokollskjemaet mer komplisert - stemmegivning for foreslåtte blokker utføres i flere trinn for å opprettholde nettverket i tilfelle manglende blokker og problemer med nettverket, men selv om dette tas i betraktning, krever konsensusalgoritmer som bruker PVRB betydelig færre meldinger mellom BP-er, noe som gjør det mulig å gjøre dem raskere enn tradisjonell PVFT, eller dens ulike modifikasjoner.
Den mest fremtredende representanten for slike algoritmer: fra Cardano-teamet, som sies å være matematisk beviselig mot BP-samarbeid.
I Ouroboros brukes PVRB til å definere den såkalte "BP-planen" - en tidsplan i henhold til hvilken hver BP blir tildelt sin egen tidsluke for publisering av en blokk. Den store fordelen med å bruke PVRB er den fullstendige "likheten" mellom BP-er (i henhold til størrelsen på balansene deres). Integriteten til PVRB sikrer at ondsinnede BP-er ikke kan kontrollere planleggingen av tidsluker, og derfor ikke kan manipulere kjeden ved å forberede og analysere kjedens gafler på forhånd, og for å velge en gaffel er det nok å stole på lengden på kjeden. kjede, uten å bruke vanskelige måter å beregne "nytten" til BP og "vekten" av blokkene.
Generelt, i alle tilfeller der en tilfeldig deltaker må velges i et desentralisert nettverk, er PVRB nesten alltid det beste valget, snarere enn et deterministisk alternativ basert på for eksempel en blokkhash. Uten PVRB fører evnen til å påvirke en deltakers valg til angrep der angriperen kan velge fra flere futures for å velge neste korrupte deltaker eller flere samtidig for å sikre en større andel i beslutningen. Bruken av PVRB diskrediterer denne typen angrep.
Skalering og lastbalansering
PVRB kan også være til stor nytte i oppgaver som belastningsreduksjon og betalingsskalering. Til å begynne med er det fornuftig å gjøre seg kjent med Rivesta "Elektroniske lotteribilletter som mikrobetalinger". Den generelle ideen er at i stedet for å foreta 100 1c-betalinger fra betaleren til mottakeren, kan du spille et ærlig lotteri med en premie på 1$ = 100c, der betaleren gir banken en av 1 av sine "lotterikuponger" for hver 100c betaling. En av disse billettene vinner en krukke på $1, og det er denne billetten som mottakeren kan registrere i blokkjeden. Det viktigste er at de resterende 99 billettene overføres mellom mottaker og betaler uten ekstern deltakelse, gjennom en privat kanal og med ønsket hastighet. En god beskrivelse av protokollen basert på denne ordningen på Emercoin-nettverket kan leses .
Denne ordningen har noen problemer, som at mottakeren kan slutte å betjene betaleren umiddelbart etter å ha mottatt en vinnende billett, men for mange spesialapplikasjoner, som for eksempel fakturering per minutt eller elektronisk abonnement på tjenester, kan disse neglisjeres. Hovedkravet er selvfølgelig lotteriets rettferdighet, og for implementeringen er en PVRB helt nødvendig.
Valget av en tilfeldig deltaker er også ekstremt viktig for sønderdelingsprotokoller, hvis formål er å skalere blokkjeden horisontalt, slik at forskjellige BP-er kun kan behandle omfanget av transaksjoner. Dette er en ekstremt vanskelig oppgave, spesielt med tanke på sikkerhet ved sammenslåing av skår. Rettferdig utvelgelse av en tilfeldig BP med det formål å tildele de ansvarlige for en spesifikk shard, som i konsensusalgoritmer, er også PVRB-oppgaven. I sentraliserte systemer tildeles shards av en balanserer; den beregner ganske enkelt hashen fra forespørselen og sender den til den nødvendige eksekveren. I blokkjeder kan muligheten til å påvirke denne oppgaven føre til et angrep på konsensus. For eksempel kan innholdet i transaksjoner kontrolleres av en angriper, han kan kontrollere hvilke transaksjoner som går til skjæret han kontrollerer og manipulere kjeden av blokker i den. Du kan lese en diskusjon om problemet med å bruke tilfeldige tall for å dele oppgaver i Ethereum
Sharding er et av de mest ambisiøse og alvorlige problemene innen blockchain; løsningen vil tillate å bygge desentraliserte nettverk med fantastisk ytelse og volum. PVRB er bare en av de viktige blokkene for å løse det.
Spill, økonomiske protokoller, voldgift
Tilfeldige talls rolle i spillindustrien er vanskelig å overvurdere. Eksplisitt bruk i nettkasinoer, og implisitt bruk når man beregner effekten av en spillers handling er alle ekstremt vanskelige problemer for desentraliserte nettverk, der det ikke er mulig å stole på en sentral kilde til tilfeldighet. Men tilfeldig utvalg kan også løse mange økonomiske problemer og bidra til å bygge enklere og mer effektive protokoller. Anta at det i vår protokoll er tvister om betaling for noen rimelige tjenester, og disse tvistene forekommer ganske sjelden. I dette tilfellet, hvis det er en ubestridt PVRB, kan kunder og selgere bli enige om å løse tvister tilfeldig, men med en gitt sannsynlighet. For eksempel, med 60 % sannsynlighet vinner klienten, og med 40 % sannsynlighet vinner selgeren. Denne tilnærmingen, som er absurd fra første side, lar deg automatisk løse tvister med en nøyaktig forutsigbar andel av gevinster/tap, som passer begge parter uten deltagelse fra en tredjepart og unødvendig sløsing med tid. Dessuten kan sannsynlighetsforholdet være dynamisk og avhenge av noen globale variabler. For eksempel, hvis et selskap gjør det bra, har et lavt antall tvister og høy lønnsomhet, kan selskapet automatisk flytte sannsynligheten for å løse en tvist mot kundesentrisitet, for eksempel 70/30 eller 80/20, og omvendt, hvis tvister tar mye penger og er uredelige eller utilstrekkelige, kan du flytte sannsynligheten i den andre retningen.
Et stort antall interessante desentraliserte protokoller, som token-kuraterte registre, prediksjonsmarkeder, bindingskurver og mange andre, er økonomiske spill der god oppførsel belønnes og dårlig oppførsel straffes. De inneholder ofte sikkerhetsproblemer der beskyttelsene er i konflikt med hverandre. Det som er beskyttet mot angrep fra «hvaler» med milliarder av tokens («stor innsats») er sårbart for angrep fra tusenvis av kontoer med små saldoer («sybilinnsats»), og tiltak mot et enkelt angrep, som f.eks. lineære avgifter opprettet for å gjøre det ulønnsomt å jobbe med en stor innsats, blir vanligvis diskreditert av et annet angrep. Siden vi snakker om et økonomisk spill, kan de tilsvarende statistiske vektene beregnes på forhånd, og ganske enkelt erstatte provisjonene med randomiserte med riktig fordeling. Slike sannsynlighetsprovisjoner implementeres ekstremt enkelt hvis blokkjeden har en pålitelig kilde til tilfeldighet og ikke krever noen komplekse beregninger, noe som gjør livet vanskelig for både hvaler og sybiler.
Samtidig er det nødvendig å fortsette å huske at kontroll over en enkelt bit i denne tilfeldigheten lar deg jukse, redusere og øke sannsynlighetene med det halve, så en ærlig PVRB er den viktigste komponenten i slike protokoller.
Hvor finner jeg den rette tilfeldigheten?
I teorien gjør rettferdig tilfeldig utvalg i desentraliserte nettverk nesten enhver protokoll beviselig sikret mot samhandling. Begrunnelsen er ganske enkel - hvis nettverket er enig om en enkelt 0 eller 1 bit, og mindre enn halvparten av deltakerne er uærlige, så, gitt nok iterasjoner, er nettverket garantert å nå en konsensus om den biten med en fast sannsynlighet. Rett og slett fordi en ærlig tilfeldig vil velge 51 av 100 deltakere 51 % av tiden. Men dette er i teorien, fordi... i ekte nettverk, for å sikre et slikt sikkerhetsnivå som i artiklene, kreves det mange meldinger mellom verter, kompleks flerpasskryptografi, og enhver komplikasjon av protokollen legger umiddelbart til nye angrepsvektorer.
Det er grunnen til at vi ennå ikke ser en bevist resistent PVRB i blokkjeder, som ville blitt brukt i nok tid til å bli testet av ekte applikasjoner, flere revisjoner, belastninger og selvfølgelig ekte angrep, uten noe som det er vanskelig å kalle en produktet virkelig trygt.
Imidlertid er det flere lovende tilnærminger, de er forskjellige i mange detaljer, og en av dem vil definitivt løse problemet. Med moderne dataressurser kan kryptografisk teori ganske smart oversettes til praktiske applikasjoner. I fremtiden vil vi gjerne snakke om PVRB-implementeringer: det er nå flere av dem, hver har sitt eget sett med viktige egenskaper og implementeringsfunksjoner, og bak hver er det en god idé. Det er ikke mange lag involvert i randomisering, og opplevelsen til hvert av dem er ekstremt viktig for alle andre. Vi håper at informasjonen vår vil tillate andre lag å bevege seg raskere, tatt i betraktning erfaringene til deres forgjengere.
Kilde: www.habr.com