Introduktion
«Generering af tilfældige tal er for vigtig til at overlade til tilfældighederne»
Robert Cavu, 1970
Denne artikel handler om praktisk anvendelse af løsninger, der bruger kollektiv generering af tilfældige tal i en mistroisk kontekst. Kort sagt — hvordan og hvorfor tilfældigheder bruges i blokkæder, og lidt om hvordan man adskiller “god” tilfældighed fra “dårlig”. At generere et virkelig tilfældigt tal er en ekstremt vanskelig udfordring, selv på en enkelt computer, og har længe været genstand for studier blandt kryptografer. I decentraliserede netværk er genereringen af tilfældige tal endnu mere kompleks og vigtig.
I netværk, hvor deltagerne ikke stoler på hinanden, muliggør muligheden for at generere et uigenkaldeligt tilfældigt tal effektivt at løse mange vigtige opgaver og forbedre allerede eksisterende ordninger. Desuden er gambling og lotterier slet ikke det primære formål, som en uerfaren læser måske først forestiller sig.
Generering af tilfældige tal
Computere kan ikke selv generere tilfældige tal; de har brug for hjælp udefra. Computeren kan få et tilfældigt værdig ved at bruge for eksempel musebevægelser, mængden af brugt hukommelse, parasitstrømme på processorens kontakter og mange andre kilder, der kaldes entropikilder. Disse værdier er ikke helt tilfældige, da de ligger inden for et bestemt interval eller har en forudsigelig karakter af ændringer. For at omdanne sådanne tal til et reelt tilfældigt tal inden for et givent interval tilføres kryptografiske transformationer, så de ujævnt fordelte værdier fra entropikilderne genererer jævnt fordelte pseudotilfældige værdier. De opnåede værdier kaldes pseudotilfældige, da de ikke er ægte tilfældige, men deterministisk genereret fra entropi. Enhver god kryptografisk algoritme, der krypterer data, producerer chiffertekst, der statistisk set bør være uadskillelig fra en tilfældig sekvens, så til fremstillingen af random kan man tage en entropikilde, der blot sikrer god unika og uforudsigelighed af værdierne, selv i små intervaller; resten af arbejdet med at spredning og blande bits i resultatværdien vil algoritmen overtage.
For at afslutte en kort introduktion vil jeg tilføje, at generering af tilfældige tal, selv på én enhed, er en af søjlerne til sikring af vores data. De genererede pseudotilfældige tal bruges ved etablering af sikre forbindelser i forskellige netværk, til generering af kryptografiske nøgler, til belastningsbalancering, kontrol af integritet og mange andre anvendelser. Sikkerheden i mange protokoller afhænger af muligheden for at generere en pålidelig, uforudsigelig tilfældighed udefra, at bevare den og ikke afsløre den før næste protokoltrin, ellers vil sikkerheden være i fare. Et angreb på generatoren af pseudotilfældige værdier er ekstremt farligt og truer alt software, der bruger tilfældig generation.
Alt dette bør du vide, hvis du har gennemført et grundkursus i kryptografi, så lad os fortsætte med decentrale netværk.
Random i blockchain
Først og fremmest vil jeg tale om blockchains med støtte til smart contracts, da de fuldt ud kan udnytte mulighederne, der tilbydes af kvalitetsbevist random. For korthedens skyld vil jeg i det følgende kalde denne teknologi “Publicly Verifiable Random Beacons” eller PVRB. Da blockchains er netværk, hvor enhver deltager kan bekræfte informationen, er en nøglekomponent i navnet “Publicly Verifiable”, dvs. enhver kan gennem beregninger få bevis for, at det nummer, der er offentliggjort i blockchains, har følgende egenskaber:
- Resultatet skal have en beviseligt ensartet fordeling, dvs. baseret på beviseligt robust kryptografi.
- Ingen af bits i resultatet kan kontrolleres. Som følge heraf kan resultatet ikke forudses på forhånd.
- Man kan ikke saboterer protokollet til generering ved at undlade at deltage i protokollet eller ved at overbelaste netværket med angribermeddelser.
- Alt det ovenstående skal være modstandsdygtigt over for sammensvérgelser fra et acceptabelt antal uærlige deltagere i protokollen (f.eks. 1/3 af deltagerne).
Enhver mulighed for en sammensvoren gruppe af deltagere til at producere selv kontrolleret lige/ulige random er en sikkerhedsbrist. Enhver mulighed for, at en gruppe kan stoppe udgivelsen af random, er en sikkerhedsbrist. Generelt er der mange problemer, og denne opgave er ikke let...
Det ser ud til, at den mest vigtige anvendelse af PVRB er forskellige spil, lotterier og generelt enhver form for gambling på blockchain. Faktisk er det en vigtig retning, men der er også mere vigtige anvendelser for random i blockchains. Lad os se på dem.
Konsensusalgoritmer
PVRB for network consensus is of immense importance. Transactions in blockchains are secured by electronic signatures, so a "transaction attack" always involves adding/removing a transaction in a block (or in several blocks). The main task of the consensus algorithm is to agree on the sequence of these transactions and the order of blocks that include these transactions. Additionally, a necessary property for real blockchains is finality—the ability of the network to agree that the chain up to the finalized block is definitive and will never be excluded due to the emergence of a new fork. Usually, to agree that a block is valid and, importantly, final, it is necessary to collect signatures from the majority of block producers (hereinafter BP—block-producers), which requires at least delivering the chain of blocks to all BPs and disseminating the signatures among all BPs. As the number of BPs increases, the number of necessary messages in the network grows exponentially. Therefore, consensus algorithms requiring finality, used in pBFT consensus of Hyperledger, do not work at the required speed, starting from just a few dozen BPs, demanding an enormous number of connections.
If there is an undisputed and honest PVRB in the network, then even in the simplest approximation, one can select one of the block producers based on it and appoint them as the "leader" for one round of the protocol. If we have N block producers, of which M: M > 1/2 N are honest, do not censor transactions, and do not create chain forks with the aim of executing a "double spend" attack, then using a uniformly distributed undisputed PVRB will allow for the selection of an honest leader with a probability of M / N (M / N > 1/2). Hvis hver leder får tildelt sin egen tidsperiode, hvor han kan producere et blok og validere kæden, og disse perioder er ligelige i tid, vil kæden af ærlige BP være længere end kæden dannet af ondsindede BP, og konsensusalgoritmen, der er baseret på kædelængden, vil simpelt hen afvise den "dårlige". Dette princip om at tildele lige tidskvanta til hver BP blev først anvendt i Graphene (forgængeren til EOS) og gør det muligt for flertallet af blokke at blive lukket med en enkelt signatur, hvilket reducerer netværksbelastningen betydeligt og gør denne konsensus hurtig og stabil. Ikke desto mindre må EOS-netværket nu bruge specielle blokke (Last Irreversible Block), som bekræftes med signaturer fra 2/3 BP. Disse blokke tjener til at sikre endelighed (umuligheden af at der opstår en fork, der starter før den sidste Last Irreversible Block).
Også i reelle implementeringer er protokolschemaet mere komplekst — afstemninger om de foreslåede blokke gennemføres i flere trin for at opretholde netværkets drift i tilfælde af blokke der springes over og netværksproblemer, men selv under sådanne omstændigheder kræver konsensusalgoritmer, der bruger PVRB, væsentligt færre meddelelser mellem BP, hvilket gør dem hurtigere end klassisk PVFT eller forskellige afvigelser heraf.
Den mest fremtrædende repræsentant for sådanne algoritmer: fra Cardano-teamet, som angiveligt har matematiske beviser for modstand mod sammensværgelser blandt BP.
I Ouroboros anvendes PVRB til at bestemme det såkaldte "BP schedule" — en tidsplan, ifølge hvilken hver BP tildeles sin egen tidslukket for offentliggørelse af blokken. En stor fordel ved at bruge PVRB er den fulde "lighed" blandt BP (i henhold til størrelsen af deres balances). Ærligheden af PVRB garanterer, at ondsindede BP ikke kan kontrollere tidslisterne, og derfor ikke kan manipulere kæden ved proaktivt at forberede og analysere kædeforke, og til valget af fork er det tilstrækkeligt blot at stole på kædelængden uden at anvende snedige metoder til at beregne BP's "nytte" og "vægt" af dens blokke.
I alle tilfælde, hvor man i et decentraliseret netværk skal vælge en tilfældig deltager, vil PVRB næsten altid være det bedste valg frem for en deterministisk variant baseret på for eksempel hash af blokken. Uden PVRB kan muligheden for at påvirke deltagervalget føre til angreb, hvor angriberen kan vælge den næste korrupte deltager eller flere ad gangen ved at vælge mellem forskellige fremtidsmuligheder for at sikre en større indflydelse på beslutningen. Brug af PVRB diskrediterer disse typer angreb.
Skalering og belastningsfordeling
PVRB kan også være til stor fordel i opgaver til nedbringelse af belastning og skalering af betalinger. Først er det fornuftigt at gøre sig bekendt med Rivestas "Electronic Lottery Tickets as Micropayments". Hovedideen er, at i stedet for at lave 100 betalinger på 1c fra betaleren til modtageren, kan man spille et ærligt lotteri med en præmie på 1$ = 100c, hvor betaleren ved hver betaling på 1c overfører én af sine 100 "lotteribilletter" til banken. En af disse billetter vinder banken 1$, og det er netop denne billet, som modtageren kan registrere på blockchainen. Det vigtigste er, at de resterende 99 billetter overføres mellem modtageren og betaleren uden ekstern deltagelse, gennem en privat kanal og med den ønskede hastighed. En god beskrivelse af protokollen baseret på denne ordning i Emercoin-netværket kan læses .
Denne ordning har flere problemer, for eksempel kan modtageren stoppe med at betjene betaleren umiddelbart efter at have modtaget den vindende billet, men for mange specielle anvendelser, såsom minut-efter-minut taksering eller elektroniske abonnementer på tjenester, kan disse overses. Det vigtigste krav er selvfølgelig ærligheden i det afholdte lotteri, og for dets gennemførelse er PVRB helt nødvendigt.
Valget af en tilfældig deltager er også ekstremt vigtigt for sharding-protokoller, hvis mål er at opnå horisontal skalering af blokkæden, hvilket gør det muligt for forskellige BP at behandle kun deres respektive transaktioner. Dette er en meget kompleks opgave, især hvad angår sikkerhed ved sammenlægning af shards. Et ærligt valg af tilfældig BP til at udpege dem ansvarlige for en specifik shard, ligesom i konsensusalgoritmer, er også en opgave for PVRB. I centraliserede systemer udpeges shards af en balancer, som simpelthen beregner en hash fra forespørgslen og sender den til den nødvendige udfører. I blokchains kan muligheden for at påvirke denne udnævnelse føre til angreb på konsensus. For eksempel kan indholdet af transaktioner kontrolleres af en angriber, der kan styre hvilke transaktioner der kommer ind i den shard, han kontrollerer, og manipulere med blokkæden indenfor den. Diskussionen om problemet med brug af tilfældige tal til sharding-opgaver i Ethereum kan læses
Sharding er en af de mest ambitiøse og seriøse opgaver inden for blockchain, og løsningen på denne vil muliggøre opbygning af decentrale netværk med fantastisk ydeevne og volumen. PVRB er blot en af de vigtige brikker i løsningen på dette.
Spil, økonomiske protokoller, arbitrage
Det er svært at overdrive betydningen af tilfældige tal i spilindustrien. Der er en åbenlys anvendelse i online casinoer og en mere implicit i beregningen af effekten af forskellige spillerhandlinger — alt sammen er det ekstremt komplekse problemer for decentraliserede netværk, hvor der ikke er mulighed for 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 skabe enklere og mere effektive protokoller. Lad os antage, at vi i vores protokol har tvister om betaling for nogle billige tjenester, og disse tvister forekommer ret sjældent. I så fald, hvis der er en uomtvistelig PVRB, kan kunder og sælgere blive enige om en tilfældig løsning af tvister, men med en given sandsynlighed. For eksempel, med en sandsynlighed på 60% vinder kunden, mens sælgeren vinder med en sandsynlighed på 40%. Denne tilsyneladende absurde tilgang gør det muligt automatisk at løse tvister med en præcist forudsigelig andel af gevinster/tab, der tilfredsstiller begge parter uden inddragelse af en tredje part og unødvendigt tidsspilde. Desuden kan sandsynlighedsforholdet være dynamisk og afhænge af nogle globale variable. For eksempel, hvis virksomheden klarer sig godt, observeres der et lavt antal tvister og høj rentabilitet, kan virksomheden automatisk justere sandsynligheden for tvistløsning til at favorisere kunderne, for eksempel 70/30 eller 80/20, og omvendt, hvis tvisterne koster mange penge og er svindelagtige eller uretfærdige, kan sandsynligheden skubbes i den modsatte retning.
Et stort antal interessante decentraliserede protokoller, såsom token curaterede registre, forudsigelsesmarkeder, bondingskurver og mange andre, fungerer som økonomiske spil, hvor godt adfærd belønnes, og dårligt adfærd straffes. Der opstår ofte sikkerhedsproblemer her, og beskyttelsesforanstaltningerne kan stå i kontrast til hinanden. Det, der er beskyttet mod angreb fra "hvaler" med milliarder af tokens ("big stake"), er sårbart over for angreb fra tusinder af konti med små balance ("sybil stake"), og de foranstaltninger, der tages mod et angreb, som for eksempel ikke-lineære gebyrer, der er skabt for at gøre det ufordelagtigt for stort staking, bliver normalt diskrediteret af et andet angreb. Da det handler om et økonomisk spil, kan de relevante statistiske vægte beregnes på forhånd, og gebyrerne kan simpelthen erstattes med randomiserede med det relevante fordelingsmønster. Sådanne sandsynlighedsgebyrer implementeres ekstremt simpelt, hvis der i blockchainen findes en pålidelig kilde til tilfældighed og kræver ingen komplekse beregninger, hvilket komplicerer livet for både hvaler og sybiler.
Det er dog vigtigt at huske, at kontrol over det enkelte bit i denne tilfældighed muliggør manipulation, idet man kan fordoble og halvere sandsynlighederne, så en ærlig PVRB er den vigtigste komponent i sådanne protokoller.
Hvor finder man den rigtige tilfældighed?
I teorien tillader ærlig tilfældig udvælgelse i decentraliserede netværk at sikre pålidelig sikkerhed mod næsten enhver protokol mod sammensværgelser. Begrundelsen er ret simpel — hvis netværket bliver enige om et enkelt bit 0 eller 1, og mindre end halvdelen af deltagerne er uærlige, så vil netværket efter tilstrækkeligt antal iterationer med sikkerhed nå til konsensus om dette bit med en fast sandsynlighed. Bare fordi ærlig tilfældighed vil vælge 51 ud af 100 deltagere i 51% af tilfældene. Men dette er i teorien, da det i virkelige netværk, for at sikre et sådant sikkerhedsniveau som i artiklerne, kræver mange meddelelser mellem værter, kompleks multi-trins kryptografi, og enhver kompleksitet i protokollen tilføjer straks nye angrebsvinkler.
Derfor ser vi endnu ikke blockchains med beviseligt robust PVRB, der har været i brug længe nok til at bestå testene fra rigtige applikationer, flere audits, belastninger, og selvfølgelig reelle angreb, uden hvilke det er svært at kalde et produkt for rigtig sikkert.
Der er dog flere lovende tilgange, som adskiller sig i mange detaljer, og en af dem vil helt sikkert løse problemet. Med moderne beregningsressourcer kan kryptografisk teori ret hurtigt blive omsat til praktiske anvendelser. Fremover vil vi gerne fortælle om implementeringerne af PVRB: der er flere af dem nu, hver med sit eget sæt vigtige egenskaber og særpræg i implementeringen, og bag hver står en god idé. Der er ikke mange teams, der beskæftiger sig med tilfældigheder, og erfaringen fra hvert af dem er ekstremt vigtig for alle de andre. Vi håber, at vores information vil hjælpe andre teams med at bevæge sig hurtigere, givet erfaringen fra forudgående teams.
Kilde: habr.com
