Indledning
"Generering af tilfældige tal er for vigtig til at overlades til tilfældighederne."
Robert Cavue, 1970
Denne artikel er afsat til den praktiske anvendelse af løsninger ved hjælp af kollektiv generering af tilfældige tal i et miljø, der ikke er tillid til. Kort sagt, hvordan og hvorfor random bruges i blockchains, og lidt om hvordan man skelner "god" tilfældig fra "dårlig". Generering af et virkelig tilfældigt tal er et ekstremt vanskeligt problem, selv på en enkelt computer, og er længe blevet undersøgt af kryptografer. Nå, i decentrale netværk er genereringen af tilfældige tal endnu mere kompleks og vigtig.
Det er i netværk, hvor deltagerne ikke stoler på hinanden, at evnen til at generere et indiskutabelt tilfældigt tal giver os mulighed for effektivt at løse mange kritiske problemer og forbedre eksisterende ordninger væsentligt. Desuden er gambling og lotterier ikke mål nummer et her, som det umiddelbart kan virke for den uerfarne læser.
Generering af tilfældige tal
Computere kan ikke selv generere tilfældige tal; de kræver hjælp udefra til at gøre det. Computeren kan få en tilfældig værdi fra for eksempel musebevægelser, mængden af brugt hukommelse, strejfstrømme på processorbenene og mange andre kilder kaldet entropikilder. Disse værdier i sig selv er ikke helt tilfældige, da de er inden for et bestemt område eller har et forudsigeligt mønster af ændringer. For at gøre sådanne tal til et virkelig tilfældigt tal inden for et givet område, anvendes kryptotransformationer på dem for at producere ensartet fordelte pseudo-tilfældige værdier fra de ujævnt fordelte værdier af entropikilden. De resulterende værdier kaldes pseudorandom, fordi de ikke er virkelig tilfældige, men er deterministisk afledt af entropi. Enhver god kryptografisk algoritme, når data krypteres, producerer chiffertekster, der statistisk ikke burde kunne skelnes fra en tilfældig sekvens, så for at producere tilfældighed kan du tage en kilde til entropi, som kun giver god repeterbarhed og uforudsigelighed af værdier, selv i små områder. resten af arbejdet er at sprede og blande bits i Den resulterende værdi vil blive overtaget af krypteringsalgoritmen.
For at fuldende et kort uddannelsesprogram vil jeg tilføje, at generering af tilfældige tal selv på én enhed er en af søjlerne for at sikre sikkerheden af vores data. De genererede pseudo-tilfældige tal bruges, når der etableres sikre forbindelser i forskellige netværk, til at generere kryptografiske nøgler, til belastningsbalancering, integritetsovervågning og til mange flere applikationer. Sikkerheden i mange protokoller afhænger af evnen til at generere en pålidelig, eksternt uforudsigelig tilfældig, gemme den og ikke afsløre den før næste trin i protokollen, ellers vil sikkerheden blive kompromitteret. Et angreb på en pseudorandom-værdigenerator er ekstremt farligt og truer øjeblikkeligt al software, der bruger tilfældig generering.
Alt dette burde du vide, hvis du tog et grundkursus i kryptografi, så lad os fortsætte med decentrale netværk.
Tilfældig i blockchains
Først og fremmest vil jeg tale om blockchains med understøttelse af smarte kontrakter; det er dem, der fuldt ud kan drage fordel af mulighederne i høj kvalitet, ubestridelig tilfældighed. Yderligere vil jeg for kortheds skyld kalde denne teknologi "Offentligt verificerbare tilfældige beacons” eller PVRB. Da blockchains er netværk, hvori information kan verificeres af enhver deltager, er den centrale del af navnet "Publicly Verifiable", dvs. Enhver kan bruge beregninger til at opnå bevis for, at det resulterende tal, der er lagt på blockchainen, har følgende egenskaber:
- Resultatet skal have en beviseligt ensartet fordeling, dvs. være baseret på beviselig stærk kryptografi.
- Det er ikke muligt at kontrollere nogen af bits af resultatet. Resultatet kan derfor ikke forudsiges på forhånd.
- Du kan ikke sabotere genereringsprotokollen ved ikke at deltage i protokollen eller ved at overbelaste netværket med angrebsmeddelelser
- Alt ovenstående skal være modstandsdygtigt over for samordning af et tilladt antal uærlige protokoldeltagere (f.eks. 1/3 af deltagerne).
Enhver mulighed for, at en mindre gruppe deltagere sammen kan producere selv en kontrolleret lige/ulige tilfældig er et sikkerhedshul. Enhver evne for gruppen til at stoppe udstedelsen af tilfældig er et sikkerhedshul. Generelt er der mange problemer, og denne opgave er ikke let...
Det ser ud til, at den vigtigste applikation til PVRB er forskellige spil, lotterier og generelt enhver form for gambling på blockchain. Dette er faktisk en vigtig retning, men tilfældighed i blockchains har endnu vigtigere anvendelser. Lad os se på dem.
Konsensus algoritmer
PVRB spiller en stor rolle i at organisere netværkskonsensus. Transaktioner i blockchains er beskyttet af en elektronisk signatur, så et "angreb på en transaktion" er altid inklusion/udelukkelse af en transaktion i en blok (eller flere blokke). Og hovedopgaven for konsensusalgoritmen er at blive enige om rækkefølgen af disse transaktioner og rækkefølgen af de blokke, der inkluderer disse transaktioner. En nødvendig egenskab for rigtige blockchains er også endelighed - netværkets evne til at acceptere, at kæden op til den afsluttede blok er endelig og aldrig vil blive udelukket på grund af udseendet af en ny gaffel. For at blive enige om, at en blok er gyldig og vigtigst af alt endelig, er det normalt nødvendigt at indsamle underskrifter fra størstedelen af blokproducenterne (herefter benævnt BP - blokproducenter), hvilket i det mindste kræver levering af blokkæden til alle BP'er og distribuere signaturer mellem alle BP'er. Efterhånden som antallet af BP'er vokser, vokser antallet af nødvendige meddelelser i netværket eksponentielt, derfor virker konsensusalgoritmer, der kræver endelighed, f.eks. brugt i Hyperledger pBFT-konsensus, ikke med den nødvendige hastighed, startende fra flere dusin BP'er, hvilket kræver et stort antal forbindelser.
Hvis der er en ubestridelig og ærlig PVRB i netværket, så kan man, selv i den enkleste tilnærmelse, vælge en af blokproducenterne baseret på det og udpege ham som "leder" under en runde af protokollen. Hvis vi har N blokproducenter, heraf M: M > 1/2 N er ærlige, censurere ikke transaktioner og fordel ikke kæden for at udføre et "double spend"-angreb, så vil brug af en ensartet distribueret uimodsagt PVRB gøre det muligt at vælge en ærlig leder med sandsynlighed M / N (M / N > 1/2). Hvis hver leder får tildelt sit eget tidsinterval, hvor han kan producere en blok og validere kæden, og disse intervaller er ens i tid, så vil blokkæden af ærlige BP'er være længere end kæden dannet af ondsindede BP'er, og konsensus algoritmen er afhængig af længden af kæden. vil simpelthen kassere den "dårlige". Dette princip med at tildele lige store stykker tid til hver BP blev først anvendt i Graphene (forgængeren til EOS), og gør det muligt for de fleste blokke at blive lukket med en enkelt signatur, hvilket i høj grad reducerer netværksbelastningen og tillader denne konsensus at arbejde ekstremt hurtigt og støt. Men EOS-netværket skal nu bruge specielle blokke (Last Irreversible Block), som bekræftes af signaturerne fra 2/3 BP. Disse blokke tjener til at sikre endelighed (umuligheden af en kædegaffel, der starter før den sidste sidste irreversible blok).
Også i reelle implementeringer er protokolskemaet mere kompliceret - afstemning for foreslåede blokke udføres i flere trin for at vedligeholde netværket i tilfælde af manglende blokke og problemer med netværket, men selv under hensyntagen til dette kræver konsensusalgoritmer, der bruger PVRB betydeligt færre beskeder mellem BP'er, hvilket gør det muligt at gøre dem hurtigere end traditionel PVFT eller dens forskellige modifikationer.
Den mest fremtrædende repræsentant for sådanne algoritmer: fra Cardano-holdet, hvilket siges at være matematisk bevisbart mod BP-samarbejde.
I Ouroboros bruges PVRB til at definere det såkaldte "BP-skema" - en tidsplan, i henhold til hvilken hver BP tildeles sit eget tidsrum til udgivelse af en blok. Den store fordel ved at bruge PVRB er den fuldstændige "lighed" af BP'er (i henhold til størrelsen af deres balancer). PVRB'ens integritet sikrer, at ondsindede BP'er ikke kan kontrollere planlægningen af tidsvinduer og derfor ikke kan manipulere kæden ved at forberede og analysere kædens gafler på forhånd, og for at vælge en gaffel er det nok blot at stole på længden af kæden. kæde, uden at bruge vanskelige måder at beregne "nytten" af BP og "vægten" af dens blokke.
Generelt, i alle tilfælde, hvor en tilfældig deltager skal vælges i et decentraliseret netværk, er PVRB næsten altid det bedste valg frem for en deterministisk mulighed baseret på for eksempel en blokhash. Uden PVRB fører evnen til at påvirke en deltagers valg til angreb, hvor angriberen kan vælge mellem flere futures for at vælge den næste korrupte deltager eller flere på én gang for at sikre en større andel i beslutningen. Brugen af PVRB miskrediterer disse typer angreb.
Skalering og belastningsbalancering
PVRB kan også være til stor gavn i opgaver som belastningsreduktion og betalingsskalering. Til at begynde med giver det mening at sætte sig ind i Rivesta "Elektroniske lotterisedler som mikrobetalinger". Den generelle idé er, at du i stedet for at foretage 100 1c-betalinger fra betaleren til modtageren, kan spille et ærligt lotteri med en præmie på 1$ = 100c, hvor betaleren giver banken en af 1 af sine "lotterisedler" for hver 100c betaling. En af disse billetter vinder en krukke på $1, og det er denne billet, som modtageren kan optage i blockchain. Det vigtigste er, at de resterende 99 billetter overføres mellem modtager og betaler uden ekstern deltagelse, via en privat kanal og med enhver ønsket hastighed. En god beskrivelse af protokollen baseret på denne ordning på Emercoin-netværket kan læses .
Denne ordning har et par problemer, såsom at modtageren kan stoppe med at betjene betaleren umiddelbart efter at have modtaget en vinderkupon, men for mange specielle applikationer, såsom minutfakturering eller elektroniske abonnementer på tjenester, kan disse forsømmes. Hovedkravet er selvfølgelig lotteriets integritet, og for dets gennemførelse er en PVRB absolut nødvendig.
Valget af en tilfældig deltager er også ekstremt vigtigt for sharding-protokoller, hvis formål er at skalere blokkæden horisontalt, så forskellige BP'er kun kan behandle deres omfang af transaktioner. Dette er en ekstremt vanskelig opgave, især med hensyn til sikkerhed ved sammenlægning af skår. Rimelig udvælgelse af en tilfældig BP med det formål at tildele de ansvarlige for en specifik shard, som i konsensusalgoritmer, er også PVRB's opgave. I centraliserede systemer tildeles shards af en balancer; den beregner simpelthen hashen fra anmodningen og sender den til den krævede eksekutør. I blockchains kan muligheden for at påvirke denne opgave føre til et angreb på konsensus. For eksempel kan indholdet af transaktioner kontrolleres af en angriber, han kan kontrollere, hvilke transaktioner der går til det skår, han kontrollerer, og manipulere kæden af blokke i det. Du kan læse en diskussion af problemet med at bruge tilfældige tal til deling af opgaver i Ethereum
Sharding er et af de mest ambitiøse og alvorlige problemer inden for blockchain; dens løsning vil tillade opbygning af decentrale netværk med fantastisk ydeevne og volumen. PVRB er blot en af de vigtige blokke til at løse det.
Spil, økonomiske protokoller, voldgift
Tilfældige tals rolle i spilindustrien er svær at overvurdere. Eksplicit brug i onlinekasinoer og implicit brug ved beregning af virkningerne af en spillers handling er alle ekstremt vanskelige problemer for decentraliserede netværk, hvor der ikke er nogen måde at stole på en central kilde til tilfældighed. Men tilfældig udvælgelse kan også løse mange økonomiske problemer og hjælpe med at opbygge enklere og mere effektive protokoller. Antag, at der i vores protokol er tvister om betaling for nogle billige tjenester, og disse tvister forekommer ret sjældent. I dette tilfælde, hvis der er en ubestridt PVRB, kan kunder og sælgere blive enige om at løse tvister tilfældigt, men med en given sandsynlighed. For eksempel, med 60 % sandsynlighed vinder klienten, og med 40 % sandsynlighed vinder sælgeren. Denne tilgang, som er absurd fra det første synspunkt, giver dig mulighed for automatisk at løse tvister med en præcis forudsigelig andel af gevinster/tab, som passer begge parter uden deltagelse af en tredjepart og unødigt spild af tid. Desuden kan sandsynlighedsforholdet være dynamisk og afhænge af nogle globale variabler. For eksempel, hvis en virksomhed klarer sig godt, har et lavt antal tvister og høj rentabilitet, kan virksomheden automatisk flytte sandsynligheden for at løse en tvist mod kundecentreret, for eksempel 70/30 eller 80/20, og omvendt, hvis tvister tager mange penge og er svigagtige eller utilstrækkelige, kan du flytte sandsynligheden i den anden retning.
Et stort antal interessante decentraliserede protokoller, såsom token-kurerede registre, forudsigelsesmarkeder, bindingskurver og mange andre, er økonomiske spil, hvor god opførsel belønnes og dårlig opførsel straffes. De indeholder ofte sikkerhedsproblemer, hvor beskyttelsen er i konflikt med hinanden. Det, der er beskyttet mod et angreb fra "hvaler" med milliarder af tokens ("stor indsats"), er sårbart over for angreb fra tusindvis af konti med små saldi ("sybil-indsats") og foranstaltninger, der træffes mod et enkelt angreb, såsom ikke- lineære gebyrer, der er oprettet for at gøre arbejdet med en stor indsats urentabelt, miskrediteres normalt af et andet angreb. Da vi taler om et økonomisk spil, kan de tilsvarende statistiske vægte beregnes på forhånd, og blot erstatte provisionerne med randomiserede med den passende fordeling. Sådanne probabilistiske kommissioner implementeres ekstremt enkelt, hvis blockchain har en pålidelig kilde til tilfældighed og ikke kræver nogen komplekse beregninger, hvilket gør livet svært for både hvaler og sybiler.
Samtidig er det nødvendigt at fortsætte med at huske, at kontrol over en enkelt bit i denne tilfældighed giver dig mulighed for at snyde, reducere og øge sandsynligheden med det halve, så en ærlig PVRB er den vigtigste komponent i sådanne protokoller.
Hvor finder man den rigtige tilfældige?
I teorien gør rimelig tilfældig udvælgelse i decentraliserede netværk næsten enhver protokol beviseligt sikker mod hemmeligt samarbejde. Rationalet er ret simpelt - hvis netværket er enige om en enkelt 0 eller 1 bit, og mindre end halvdelen af deltagerne er uærlige, så er netværket, givet nok iterationer, garanteret at nå en konsensus om den bit med en fast sandsynlighed. Simpelthen fordi en ærlig tilfældig vil vælge 51 ud af 100 deltagere 51% af tiden. Men det er i teorien, fordi... i rigtige netværk, for at sikre et sådant sikkerhedsniveau som i artiklerne, kræves der mange beskeder mellem værter, kompleks multi-pass kryptografi, og enhver komplikation af protokollen tilføjer straks nye angrebsvektorer.
Derfor ser vi endnu ikke en dokumenteret resistent PVRB i blockchains, som ville have været brugt i tilstrækkelig tid til at blive testet af rigtige applikationer, flere revisioner, belastninger og selvfølgelig rigtige angreb, uden hvilke det er svært at kalde en produkt virkelig sikkert.
Der er dog flere lovende tilgange, de adskiller sig i mange detaljer, og en af dem vil helt sikkert løse problemet. Med moderne computerressourcer kan kryptografisk teori ganske smart oversættes til praktiske applikationer. I fremtiden vil vi gerne tale om PVRB-implementeringer: der er nu flere af dem, hver har sit eget sæt vigtige egenskaber og implementeringsfunktioner, og bag hver er der en god idé. Der er ikke mange hold involveret i randomisering, og oplevelsen af hver af dem er ekstremt vigtig for alle andre. Vi håber, at vores oplysninger vil give andre hold mulighed for at bevæge sig hurtigere, under hensyntagen til deres forgængeres erfaringer.
Kilde: www.habr.com