Introductie
“Het genereren van willekeurige getallen is te belangrijk om aan het toeval over te laten.”
Robert Cavue, 1970
Dit artikel is gewijd aan de praktische toepassing van oplossingen die gebruikmaken van het collectief genereren van willekeurige getallen in een niet-vertrouwde omgeving. Kortom, hoe en waarom willekeurig wordt gebruikt in blockchains, en een beetje over hoe je ‘goed’ willekeurig van ‘slecht’ kunt onderscheiden. Het genereren van een echt willekeurig getal is een uiterst moeilijk probleem, zelfs op een enkele computer, en wordt al lang bestudeerd door cryptografen. Welnu, in gedecentraliseerde netwerken is het genereren van willekeurige getallen nog complexer en belangrijker.
Het is in netwerken waar deelnemers elkaar niet vertrouwen dat het vermogen om een onbetwistbaar willekeurig getal te genereren ons in staat stelt veel kritieke problemen effectief op te lossen en bestaande schema's aanzienlijk te verbeteren. Bovendien zijn gokken en loterijen hier niet het voornaamste doel, zoals het in eerste instantie voor de onervaren lezer lijkt.
Generatie van willekeurige getallen
Computers kunnen zelf geen willekeurige getallen genereren; daarvoor hebben ze hulp van buitenaf nodig. De computer kan een willekeurige waarde verkrijgen uit bijvoorbeeld muisbewegingen, de hoeveelheid gebruikt geheugen, zwerfstromen op de processorpinnen en vele andere bronnen die entropiebronnen worden genoemd. Deze waarden zijn op zichzelf niet volledig willekeurig, omdat ze binnen een bepaald bereik liggen of een voorspelbaar veranderingspatroon hebben. Om dergelijke getallen binnen een bepaald bereik om te zetten in een echt willekeurig getal, worden er cryptotransformaties op toegepast om uniform verdeelde pseudo-willekeurige waarden te produceren uit de ongelijk verdeelde waarden van de entropiebron. De resulterende waarden worden pseudorandom genoemd omdat ze niet echt willekeurig zijn, maar deterministisch zijn afgeleid van entropie. Elk goed cryptografisch algoritme produceert bij het versleutelen van gegevens cijferteksten die statistisch niet te onderscheiden zijn van een willekeurige reeks, dus om willekeur te produceren kun je een bron van entropie nemen, die alleen een goede herhaalbaarheid en onvoorspelbaarheid van waarden biedt, zelfs in kleine bereiken, de De rest van het werk bestaat uit het verspreiden en mixen van bits. De resulterende waarde wordt overgenomen door het versleutelingsalgoritme.
Om een kort educatief programma af te ronden, wil ik hieraan toevoegen dat het genereren van willekeurige getallen, zelfs op één apparaat, een van de pijlers is van het waarborgen van de veiligheid van onze gegevens. De gegenereerde pseudo-willekeurige getallen worden gebruikt bij het tot stand brengen van veilige verbindingen in verschillende netwerken, om cryptografische sleutels, voor taakverdeling, integriteitsbewaking en voor nog veel meer toepassingen. De veiligheid van veel protocollen hangt af van het vermogen om een betrouwbare, extern onvoorspelbare willekeurige gebeurtenis te genereren, deze op te slaan en deze pas in de volgende stap van het protocol te onthullen, anders komt de veiligheid in gevaar. Een aanval op een generator van pseudo-willekeurige waarden is uiterst gevaarlijk en bedreigt onmiddellijk alle software die gebruikmaakt van het genereren van willekeurige waarden.
Dit zou je allemaal moeten weten als je een basiscursus cryptografie hebt gevolgd, dus laten we verder gaan over gedecentraliseerde netwerken.
Willekeurig in blockchains
Allereerst zal ik het hebben over blockchains met ondersteuning voor slimme contracten; zij zijn degenen die volledig kunnen profiteren van de kansen die worden geboden door hoogwaardige, onmiskenbare willekeur. Verder zal ik deze technologie kortheidshalve “Openbaar verifieerbare willekeurige bakens”of PVRB. Omdat blockchains netwerken zijn waarin informatie door elke deelnemer kan worden geverifieerd, is het belangrijkste deel van de naam ‘Publicly Verifiable’, d.w.z. ‘Publicly Verifiable’. Iedereen kan berekeningen gebruiken om bewijs te verkrijgen dat het resulterende nummer dat op de blockchain wordt geplaatst, de volgende eigenschappen heeft:
- Het resultaat moet een aantoonbaar uniforme verdeling hebben, dat wil zeggen gebaseerd zijn op aantoonbaar sterke cryptografie.
- Het is niet mogelijk om de bits van het resultaat te controleren. Het gevolg hiervan is dat de uitkomst niet op voorhand kan worden voorspeld.
- Je kunt het generatieprotocol niet saboteren door niet mee te doen aan het protocol of door het netwerk te overbelasten met aanvalsberichten
- Al het bovenstaande moet bestand zijn tegen samenzwering van een toegestaan aantal oneerlijke protocoldeelnemers (bijvoorbeeld 1/3 van de deelnemers).
Elke mogelijkheid van een samenspannende kleine groep deelnemers om zelfs maar een gecontroleerde even/oneven willekeurige volgorde te produceren, is een veiligheidslek. Elk vermogen van de groep om de uitgifte van willekeurige documenten te stoppen is een veiligheidslek. Over het algemeen zijn er veel problemen, en deze taak is niet eenvoudig...
Het lijkt erop dat de belangrijkste toepassing voor PVRB verschillende spellen, loterijen en in het algemeen elke vorm van gokken op de blockchain is. Dit is inderdaad een belangrijke richting, maar willekeur in blockchains heeft nog belangrijkere toepassingen. Laten we ze eens bekijken.
consensusalgoritmen
PVRB speelt een grote rol bij het organiseren van netwerkconsensus. Transacties in blockchains worden beschermd door een elektronische handtekening, een ‘aanval op een transactie’ is dus altijd het opnemen/uitsluiten van een transactie in een blok (of meerdere blokken). En de belangrijkste taak van het consensusalgoritme is het eens worden over de volgorde van deze transacties en de volgorde van de blokken die deze transacties omvatten. Een noodzakelijke eigenschap voor echte blockchains is finaliteit: het vermogen van het netwerk om het erover eens te zijn dat de keten tot aan het voltooide blok definitief is en nooit zal worden uitgesloten vanwege het verschijnen van een nieuwe fork. Om het erover eens te worden dat een blok geldig en, belangrijker nog, definitief is, is het doorgaans nodig om handtekeningen te verzamelen van de meerderheid van de blokproducenten (hierna BP genoemd - blokproducenten), waarvoor op zijn minst de blokketen moet worden geleverd. naar alle borderliners, en het verspreiden van handtekeningen tussen alle borderliners. Naarmate het aantal BP’s groeit, groeit het aantal noodzakelijke berichten in het netwerk exponentieel. Daarom werken consensusalgoritmen die finaliteit vereisen, die bijvoorbeeld worden gebruikt in de Hyperledger pBFT-consensus, niet met de vereiste snelheid, beginnend bij enkele tientallen BP’s, waarvoor een groot aantal verbindingen.
Als er een onmiskenbare en eerlijke PVRB in het netwerk aanwezig is, kan men, zelfs in de eenvoudigste benadering, op basis daarvan een van de blokproducenten kiezen en hem tijdens één ronde van het protocol als “leider” benoemen. Als we hebben N blokproducenten, waarvan M: M > 1/2 N eerlijk zijn, geen transacties censureren en de keten niet splitsen om een ‘double spend’-aanval uit te voeren, dan zal het gebruik van een uniform verdeelde, onbetwiste PVRB het mogelijk maken een eerlijke leider met waarschijnlijkheid te kiezen M / N (M / N > 1/2). Als iedere leider zijn eigen tijdsinterval krijgt toegewezen waarin hij een blok kan produceren en de keten kan valideren, en deze intervallen in de tijd gelijk zijn, dan zal de blokketen van eerlijke borderliners langer zijn dan de keten die wordt gevormd door kwaadwillige borderliners, en de consensus algoritme is afhankelijk van de lengte van de keten en zal de ‘slechte’ simpelweg weggooien. Dit principe van het toewijzen van gelijke tijdsperioden aan elke BP werd voor het eerst toegepast in Graphene (de voorloper van EOS) en maakt het mogelijk de meeste blokken te sluiten met een enkele handtekening, waardoor de netwerkbelasting aanzienlijk wordt verminderd en deze consensus extreem snel kan werken. gestaag. Het EOS-netwerk moet nu echter gebruik maken van speciale blokken (Last Irreversible Block), die worden bevestigd door de handtekeningen van 2/3 BP. Deze blokken dienen om de finaliteit te garanderen (de onmogelijkheid dat een kettingvork begint vóór het laatste Laatste Onomkeerbare Blok).
Bovendien is het protocolschema in echte implementaties ingewikkelder: het stemmen op voorgestelde blokken wordt in verschillende fasen uitgevoerd om het netwerk in stand te houden in geval van ontbrekende blokken en problemen met het netwerk. Maar zelfs als hiermee rekening wordt gehouden, vereisen consensusalgoritmen die PVRB gebruiken aanzienlijk minder berichten tussen borderliners, waardoor ze sneller kunnen worden verzonden dan traditionele PVFT of de verschillende aanpassingen daarvan.
De meest prominente vertegenwoordiger van dergelijke algoritmen: van het Cardano-team, waarvan wordt gezegd dat het wiskundig bewijsbaar is tegen BP-collusie.
In Ouroboros wordt PVRB gebruikt om het zogenaamde “BP-schema” te definiëren - een schema volgens welke elke BP zijn eigen tijdslot krijgt toegewezen voor het publiceren van een blok. Het grote voordeel van het gebruik van PVRB is de volledige ‘gelijkheid’ van BP’s (op basis van de omvang van hun balansen). De integriteit van de PVRB zorgt ervoor dat kwaadwillende borderliners geen controle hebben over de planning van tijdvakken, en daarom de keten niet kunnen manipuleren door vorken van de keten vooraf voor te bereiden en te analyseren. Om een vork te selecteren is het voldoende om eenvoudigweg te vertrouwen op de lengte van de ketting. keten, zonder lastige manieren te gebruiken om het ‘nut’ van BP en het ‘gewicht’ van zijn blokken te berekenen.
In het algemeen is PVRB in alle gevallen waarin een willekeurige deelnemer moet worden gekozen in een gedecentraliseerd netwerk vrijwel altijd de beste keuze, in plaats van een deterministische optie gebaseerd op bijvoorbeeld een blok-hash. Zonder PVRB leidt het vermogen om de keuze van een deelnemer te beïnvloeden tot aanvallen waarbij de aanvaller kan kiezen uit meerdere toekomsten om de volgende corrupte deelnemer te kiezen, of meerdere tegelijk om een groter aandeel in de beslissing te verzekeren. Het gebruik van PVRB brengt dit soort aanvallen in diskrediet.
Schalen en taakverdeling
PVRB kan ook van groot nut zijn bij taken zoals belastingvermindering en opschaling van betalingen. Om te beginnen is het logisch om er vertrouwd mee te raken Rivesta “Elektronische loten als microbetalingen”. Het algemene idee is dat je, in plaats van 100 1c-betalingen van de betaler aan de ontvanger te doen, een eerlijke loterij kunt spelen met een prijs van 1$ = 100c, waarbij de betaler de bank voor elk een van de 1 van zijn “loten” geeft. 100c betaling. Eén van deze kaartjes wint een pot van $1, en het is dit kaartje dat de ontvanger in de blockchain kan opnemen. Het allerbelangrijkste is dat de resterende 99 tickets zonder tussenkomst van buitenaf via een privékanaal en met elke gewenste snelheid worden overgedragen tussen de ontvanger en de betaler. Een goede beschrijving van het protocol op basis van dit schema op het Emercoin-netwerk is te lezen .
Dit schema kent een aantal problemen, zo kan het zijn dat de ontvanger onmiddellijk stopt met het bedienen van de betaler nadat hij een winnend ticket heeft ontvangen, maar voor veel speciale toepassingen, zoals facturering per minuut of elektronische abonnementen op diensten, kunnen deze worden verwaarloosd. De belangrijkste vereiste is uiteraard de eerlijkheid van de loterij, en voor de uitvoering ervan is een PVRB absoluut noodzakelijk.
De keuze van een willekeurige deelnemer is ook uiterst belangrijk voor sharding-protocollen, die tot doel hebben de blokketen horizontaal te schalen, waardoor verschillende BP's alleen hun reikwijdte van transacties kunnen verwerken. Dit is een uiterst moeilijke taak, vooral in termen van veiligheid bij het samenvoegen van shards. Een eerlijke selectie van een willekeurige BP met als doel degenen die verantwoordelijk zijn voor een specifieke scherf aan te wijzen, zoals bij consensusalgoritmen, is ook de taak van de PVRB. In gecentraliseerde systemen worden shards toegewezen door een balancer; deze berekent eenvoudigweg de hash van het verzoek en stuurt deze naar de vereiste uitvoerder. In blockchains kan het vermogen om deze opdracht te beïnvloeden leiden tot een aanval op de consensus. De inhoud van transacties kan bijvoorbeeld worden gecontroleerd door een aanvaller, hij kan bepalen welke transacties naar de shard gaan die hij beheert en de keten van blokken daarin manipuleren. Je kunt een bespreking lezen van het probleem van het gebruik van willekeurige getallen voor sharding-taken in Ethereum
Sharding is een van de meest ambitieuze en serieuze problemen op het gebied van blockchain; de oplossing ervan zal het mogelijk maken gedecentraliseerde netwerken met fantastische prestaties en volume te bouwen. PVRB is slechts een van de belangrijke blokken om dit op te lossen.
Spelletjes, economische protocollen, arbitrage
De rol van willekeurige getallen in de game-industrie kan moeilijk worden overschat. Expliciet gebruik in online casino’s en impliciet gebruik bij het berekenen van de effecten van de actie van een speler zijn allemaal uiterst moeilijke problemen voor gedecentraliseerde netwerken, waar er geen manier is om te vertrouwen op een centrale bron van willekeur. Maar willekeurige selectie kan ook veel economische problemen oplossen en helpen bij het bouwen van eenvoudigere en efficiëntere protocollen. Stel dat er in ons protocol geschillen zijn over de betaling voor sommige goedkope diensten, en deze geschillen komen vrij zelden voor. In dit geval kunnen klanten en verkopers, als er sprake is van een onbetwiste PVRB, overeenkomen om geschillen willekeurig op te lossen, maar met een bepaalde waarschijnlijkheid. Met een waarschijnlijkheid van 60% wint de klant bijvoorbeeld, en met een waarschijnlijkheid van 40% wint de verkoper. Deze aanpak, die vanuit het eerste gezichtspunt absurd is, stelt je in staat geschillen automatisch op te lossen met een nauwkeurig voorspelbaar aandeel van winsten/verliezen, wat beide partijen uitkomt, zonder enige deelname van een derde partij en onnodige tijdverspilling. Bovendien kan de waarschijnlijkheidsratio dynamisch zijn en afhankelijk zijn van enkele globale variabelen. Als een bedrijf het bijvoorbeeld goed doet, een laag aantal geschillen heeft en een hoge winstgevendheid heeft, kan het bedrijf de kans op het oplossen van een geschil automatisch verschuiven naar klantgerichtheid, bijvoorbeeld 70/30 of 80/20, en omgekeerd. als geschillen veel geld kosten en frauduleus of ontoereikend zijn, kun je de waarschijnlijkheid in de andere richting verschuiven.
Een groot aantal interessante gedecentraliseerde protocollen, zoals token-curated registers, voorspellingsmarkten, bondingcurves en vele andere, zijn economische spellen waarin goed gedrag wordt beloond en slecht gedrag wordt bestraft. Ze bevatten vaak beveiligingsproblemen waarvoor de beschermingen met elkaar in strijd zijn. Wat wordt beschermd tegen een aanval door “walvissen” met miljarden tokens (“big stake”) is kwetsbaar voor aanvallen van duizenden accounts met kleine saldi (“sybil stake”), en maatregelen die worden genomen tegen een enkele aanval, zoals niet- lineaire vergoedingen die zijn gecreëerd om het werken met een grote inzet onrendabel te maken, worden meestal door een nieuwe aanval in diskrediet gebracht. Omdat we het over een economisch spel hebben, kunnen de overeenkomstige statistische gewichten vooraf worden berekend en de commissies eenvoudigweg worden vervangen door willekeurige commissies met de juiste verdeling. Dergelijke probabilistische commissies kunnen uiterst eenvoudig worden geïmplementeerd als de blockchain een betrouwbare bron van willekeur heeft en geen complexe berekeningen vereist, wat het leven voor zowel walvissen als sybils moeilijk maakt.
Tegelijkertijd is het noodzakelijk om te blijven onthouden dat controle over een enkel bit in deze willekeur je in staat stelt vals te spelen, waardoor de kansen met de helft worden verkleind en vergroot, dus een eerlijke PVRB is het belangrijkste onderdeel van dergelijke protocollen.
Waar vind je de juiste random?
In theorie zorgt eerlijke willekeurige selectie in gedecentraliseerde netwerken ervoor dat vrijwel elk protocol aantoonbaar veilig is tegen collusie. De grondgedachte is vrij eenvoudig: als het netwerk het eens is over een enkele 0 of 1 bit, en minder dan de helft van de deelnemers oneerlijk is, dan zal het netwerk, gegeven voldoende iteraties, gegarandeerd een consensus over dat bit bereiken met een vaste waarschijnlijkheid. Simpelweg omdat een eerlijke willekeurige deelnemer 51% van de tijd 100 van de 51 deelnemers kiest. Maar dit is in theorie, omdat... Om een dergelijk beveiligingsniveau als in de artikelen te garanderen, zijn in echte netwerken veel berichten tussen hosts en complexe multi-pass cryptografie vereist, en elke complicatie van het protocol voegt onmiddellijk nieuwe aanvalsvectoren toe.
Dat is de reden waarom we nog geen bewezen resistente PVRB in blockchains zien, die lang genoeg gebruikt zou zijn om getest te worden door echte applicaties, meerdere audits, ladingen en natuurlijk echte aanvallen, zonder welke het moeilijk is om van een product echt veilig.
Er zijn echter verschillende veelbelovende benaderingen, ze verschillen in veel details, en een daarvan zal het probleem zeker oplossen. Met moderne computerbronnen kan de cryptografische theorie heel slim worden vertaald in praktische toepassingen. In de toekomst zullen we graag praten over PVRB-implementaties: er zijn er nu verschillende, elk heeft zijn eigen reeks belangrijke eigenschappen en implementatiekenmerken, en achter elk zit een goed idee. Er zijn niet veel teams betrokken bij randomisatie, en de ervaring van elk van hen is uiterst belangrijk voor alle anderen. We hopen dat onze informatie andere teams in staat zal stellen sneller te bewegen, rekening houdend met de ervaring van hun voorgangers.
Bron: www.habr.com