Inleiding
«Random number generation is too important to leave to chance»
Robert Cavyu, 1970
Dit artikel is gewijd aan de praktische toepassing van oplossingen die gebruik maken van collectieve random number generation in een onbetrouwbare omgeving. Kort gezegd, hoe en waarom wordt random gebruikt in blockchains, en een beetje over hoe je ‘goede’ random van ‘slechte’ random kunt onderscheiden. Het genereren van werkelijk willekeurige getallen is een uiterst complexe uitdaging, zelfs op een enkele computer, en wordt al lang bestudeerd door cryptografen. In gedecentraliseerde netwerken is het genereren van random numbers nog moeilijker en crucialer.
In netwerken waar deelnemers elkaar niet vertrouwen, stelt de mogelijkheid om een onbetwistbaar willekeurig getal te genereren ons in staat om vele belangrijke problemen effectief op te lossen en bestaande mechanismen aanzienlijk te verbeteren. Daarbij zijn gokken en loterijen absoluut niet het belangrijkste doel, zoals een onervaren lezer wellicht zou denken.
Generatie van willekeurige getallen
Computers kunnen zelf geen willekeurige getallen produceren; daarvoor hebben ze externe hulp nodig. Een computer kan een willekeurige waarde verkrijgen, bijvoorbeeld door de beweging van de muis, het aantal gebruikt geheugen, parasitaire stromen op de contacten van de processor en vele andere bronnen, die entropiebronnen worden genoemd. Deze waarden zijn niet geheel willekeurig, omdat ze zich binnen een bepaald bereik bevinden of een voorspelbaar karakter van veranderingen vertonen. Om zulke getallen om te zetten in echt willekeurige getallen binnen een bepaald bereik, worden cryptotransformaties toegepast, zodat niet-gelijkmatig verdeelde waarden van de entropiebronnen gelijkmatig verdeelde pseudo-willekeurige waarden genereren. De verkregen waarden worden pseudo-willekeurig genoemd, omdat ze niet echt willekeurig zijn, maar deterministisch geproduceerd zijn uit entropie. Iedere goede crypto-algoritme produceert bij het versleutelen van gegevens ciphertexts die statistisch gezien niet te onderscheiden zijn van een willekeurige volgorde, zodat voor het genereren van random een entropiebron kan worden gebruikt die alleen zorgt voor een goede herhaalbaarheid en onvoorspelbaarheid van de waarden, zelfs binnen kleine bereiken. De rest van het werk met het verspreiden en schudden van de bits in de resulterende waarde wordt door het versleutelingsalgoritme uitgevoerd.
Om een korte lezing af te ronden, voeg ik toe dat de generatie van willekeurige getallen, zelfs op één apparaat, een van de pijlers is voor de beveiliging van onze gegevens. De gegenereerde pseudo-willekeurige getallen worden gebruikt bij het opzetten van beveiligde verbindingen in verschillende netwerken, voor het genereren van cryptografische sleutels, voor load balancing, voor integriteitscontrole en nog veel meer toepassingen. De veiligheid van veel protocollen hangt af van de mogelijkheid om een betrouwbare, onvoorspelbare willekeur te genereren, deze op te slaan en niet openbaar te maken tot de volgende fase van het protocol; anders wordt de veiligheid in gevaar gebracht. Een aanval op de generator van pseudo-willekeurige waarden is uiterst gevaarlijk en brengt alle software die gebruikmaakt van random generatie in gevaar.
Dit moet je weten als je een basiscursus cryptografie hebt gevolgd, laten we daarom doorgaan met gedecentraliseerde netwerken.
Randomness in Blockchains
In the first place, I will talk about blockchains that support smart contracts, as they can fully utilize the capabilities offered by high-quality indisputable randomness. For brevity, I will refer to this technology as “Publicly Verifiable Random Beacons” or PVRB. Since blockchains are networks where any participant can verify the information, a key part of the name is “Publicly Verifiable,” meaning that anyone can obtain proof through computations that the generated number stored in the blockchain possesses the following properties:
- The result must have provably uniform distribution, i.e., it is based on provably secure cryptography.
- It is impossible to control any of the bits of the result. Consequently, the outcome cannot be predicted in advance.
- The protocol for generation cannot be sabotaged by not participating in the protocol or by overwhelming the network with attacking messages.
- All of the above must be resistant to collusion by an acceptable number of dishonest protocol participants (for example, 1/3 of the participants).
Any possibility for a colluding minor group of participants to produce even controlled odd/even randomness is a security hole. Any chance for a group to halt the generation of randomness is a security flaw. In general, there are many problems, and this task is not easy…
It seems that the most important application for PVRB is various games, lotteries, and indeed any form of gambling on the blockchain. Indeed, this is an important direction, but randomness in blockchains has even more significant applications. Let's consider them.
Consensus Algorithms
PVRB speelt een enorme rol bij het organiseren van netwerkkonsensus. Transacties in blockchains zijn beschermd door een elektronische handtekening, dus een “aanval op een transactie” is altijd het in- of uitsluiten van een transactie in een block (of meerdere blocks). De belangrijkste taak van het consensusalgoritme is om overeenstemming te bereiken over de volgorde van deze transacties en de volgorde van de blocks die deze transacties bevatten. Een noodzakelijke eigenschap van echte blockchains is finaliteit — de mogelijkheid voor het netwerk om overeenstemming te bereiken waaruit blijkt dat de keten tot het gefinaliseerde block definitief is en nooit zal worden uitgesloten door het verschijnen van een nieuwe fork. Gewoonlijk is het nodig om handtekeningen van de meerderheid van de block producers (BP) te verzamelen om overeenstemming te bereiken dat een block geldig en, het belangrijkste, final is, wat minstens vereist dat de keten van blocks naar alle BP's wordt gestuurd en de handtekeningen onder alle BP's worden verspreid. Bij een groeiend aantal BP's groeit het aantal benodigde berichten in het netwerk exponentieel, daarom functioneren consensusalgoritmen die finaliteit vereisen, zoals pBFT-consensus van Hyperledger, niet met de benodigde snelheid, al bij enkele tientallen BP's, en vereisen ze een enorme hoeveelheid verbindingen.
Als er in het netwerk een onbetwistbaar en eerlijk PVRB is, kan zelfs in de eenvoudigste benadering, daarop een van de block producers worden gekozen en deze worden aangesteld als “leider” tijdens een protocolronde. Als we hebben N block producers, van wie M: M > 1/2 N eerlijk zijn, geen transacties censureren en geen forks bouwen om een “double spend” aanval uit te voeren, dan stelt het gebruik van een gelijkmatig verdeelde onbetwistbare PVRB ons in staat om een eerlijke leider te kiezen met een waarschijnlijkheid van M / N (M / N > 1/2)Als elke leider een eigen tijdsinterval krijgt toegewezen waarin hij een blok kan aanmaken en de keten kan valideren, en deze intervallen gelijk zijn, dan zal de keten van eerlijke BP langer zijn dan de keten die door kwaadwillige BP wordt gevormd, en het consensusalgoritme dat afhankelijk is van de ketenlengte zal de "slechte" eenvoudigweg verwerpen. Dit principe van het toewijzen van gelijke tijdsquantums aan elke BP werd voor het eerst toegepast in Graphene (de voorganger van EOS) en stelt de meeste blokken in staat om met één handtekening te worden afgesloten, wat de netwerkbelasting aanzienlijk vermindert en dit consensusmechanisme zeer snel en stabiel maakt. Desondanks moet het EOS-netwerk nu speciale blokken (Last Irreversible Block) gebruiken, die worden bevestigd door de handtekeningen van 2/3 BP. Deze blokken dienen ter waarborging van de finaliteit (de onmogelijkheid van het ontstaan van een fork in de keten die eerder begint dan de laatste Last Irreversible Block).
In realistische implementaties is de protocolstructuur complexer — stemmen over voorgestelde blokken vinden plaats in meerdere fasen om de werking van het netwerk te ondersteunen in het geval van gemiste blokken en netwerkproblemen, maar zelfs met dit in overweging, vereisen consensusalgoritmen die gebruikmaken van PVRB aanzienlijk minder berichten tussen BP, waardoor ze sneller zijn dan de traditionele PВFT of verschillende modificaties daarvan.
De meest prominente vertegenwoordiger van dergelijke algoritmen is: van het Cardano-team, dat, zoals aangekondigd, wiskundig bewezen weerstand biedt tegen collusie onder BP.
In Ouroboros wordt PVRB gebruikt om het zogenaamde "BP-schema" vast te stellen — een schema waarin aan elke BP een tijdslot wordt toegewezen voor het publiceren van een blok. Een groot voordeel van het gebruik van PVRB is de volledige "gelijkheid" van BP (afhankelijk van de grootte van hun saldo's). De eerlijkheid van PVRB garandeert dat kwaadwillige BP het schema van tijdslots niet kunnen beheersen en daardoor de keten niet kunnen manipuleren door vooraf forks van de keten voor te bereiden en te analyseren; om een fork te kiezen, hoeft men eenvoudigweg op de ketenlengte te vertrouwen, zonder gebruik te maken van slimme manieren om de "nuttigheid" van BP en het "gewicht" van zijn blokken te berekenen.
In alle gevallen waarin een willekeurige deelnemer in een gedecentraliseerd netwerk moet worden gekozen, is PVRB bijna altijd de beste optie in plaats van een deterministische variant gebaseerd op bijvoorbeeld de hash van een blok. Zonder PVRB kan de mogelijkheid om de deelnemer te beïnvloeden leiden tot aanvallen, waarbij de aanvaller, door te kiezen uit verschillende toekomstige opties, de volgende corrupte deelnemer of zelfs meerdere kan selecteren om een zwaarder gewicht in de besluitvorming te waarborgen. Het gebruik van PVRB discrediteert deze soorten aanvallen.
Schaalbaarheid en load balancing
PVRB kan ook aanzienlijke voordelen opleveren bij het verminderen van belasting en het schalen van betalingen. Het is nuttig om eerst kennis te maken met Rivestas "Electronic Lottery Tickets as Micropayments". Het komt erop neer dat in plaats van 100 betalingen van 1 cent van de betaler naar de ontvanger, men een eerlijke loterij kan spelen met een prijs van 1$ = 100 cent, waarbij de betaler bij elke betaling van 1 cent de bank een van zijn 100 "loterijbiljetten" overhandigt. Een van deze biljetten wint de bank 1$, en dit is het biljet dat de ontvanger in de blockchain kan vastleggen. Het belangrijkste is dat de overige 99 biljetten tussen de ontvanger en de betaler worden overgedragen zonder externe tussenkomst, via een priv kanaal en met de gewenste snelheid. Een goede beschrijving van het protocol op basis van dit schema in het Emercoin-netwerk is te lezen. .
Deze aanpak kent verschillende problemen; bijvoorbeeld kan de ontvanger onmiddellijk stoppen met het bedienen van de betaler nadat deze het winnende biljet heeft ontvangen, maar voor veel specifieke toepassingen, zoals betaling per minuut of elektronische abonnementen op diensten, kunnen deze worden verwaarloosd. De belangrijkste vereiste is uiteraard de eerlijkheid van de gehouden loterij, en hiervoor is PVRB absoluut noodzakelijk.
De keuze van een willekeurige deelnemer is ook uiterst belangrijk voor de schardingprotocollen, waarvan het doel horizontale schaalvergroting van de blockchain is, zodat verschillende BP alleen hun eigen scope van transacties kunnen verwerken. Dit is een zeer complexe taak, vooral wat betreft de veiligheid bij het combineren van shards. Een eerlijke keuze van een willekeurige BP met het doel om deze verantwoordelijk te maken voor een specifieke shard, evenals in consensusalgoritmen, is ook een taak van PVRB. In gecentraliseerde systemen worden shards toegewezen door een load balancer, die eenvoudig de hash van het verzoek berekent en deze naar de benodigde uitvoerder stuurt. In blockchains kan de mogelijkheid om deze toewijzing te beïnvloeden leiden tot aanvallen op de consensus. Bijvoorbeeld, de inhoud van transacties kan door een aanvaller worden gecontroleerd, deze kan beheersen welke transacties in zijn gecontroleerde shard terechtkomen en de blockchain daarin manipuleren. U kunt de discussie over het probleem van het gebruik van willekeurige getallen voor schardingtaken in Ethereum lezen.
Sharding is een van de meest ambitieuze en serieuze taken op het gebied van blockchain; het oplossen ervan zal het mogelijk maken om gedecentraliseerde netwerken van indrukwekkende prestaties en omvang te bouwen. PVRB is slechts een van de belangrijke blokken voor de oplossing.
Spellen, economische protocollen, arbitrage
De rol van willekeurige getallen in de game-industrie is niet te onderschatten. Het expliciete gebruik in online casino's en het impliciete gebruik bij het berekenen van de effecten van bepaalde acties van spelers zijn uiterst complexe problemen voor gedecentraliseerde netwerken, waar niemand op een centrale bron van willekeurigheid kan vertrouwen. Maar een willekeurige keuze kan ook veel economische problemen oplossen en helpen bij het opbouwen van eenvoudigere en efficiëntere protocollen. Stel dat in ons protocol geschillen over de betaling van bepaalde goedkope diensten zich vrij zeldzaam voordoen. In dat geval, als er een onbetwistbaar PVRB is, kunnen klanten en verkopers overeenkomen om geschillen willekeurig op te lossen, maar met een bepaalde waarschijnlijkheid. Bijvoorbeeld, met een kans van 60% wint de klant en met 40% wint de verkoper. Deze aanvankelijke absurde benadering stelt ons in staat om geschillen automatisch op te lossen met een exact voorspelbaar percentage van winsten/verliezen dat beide partijen bevalt, zonder enige tussenkomst van een derde partij en zonder onnodige tijdsverspilling. Bovendien kan de verhouding van waarschijnlijkheden dynamisch zijn en afhankelijk van bepaalde globale variabelen. Bijvoorbeeld, als het goed gaat met het bedrijf, er een laag aantal geschillen is en de winst hoog is, kan het bedrijf automatisch de kans op klantgerichtheid bij de geschiloplossing verschuiven, bijvoorbeeld naar 70/30 of 80/20, en omgekeerd, als geschillen veel kosten met zich meebrengen en frauduleus of ongepast zijn, kan de kans in de andere richting worden verschoven.
Een groot aantal interessante gedecentraliseerde protocollen, zoals token curated registries, prediction markets, bonding curves en vele anderen, vormen economische spellen waarin goed gedrag wordt beloond en slecht gedrag wordt bestraft. Ze hebben vaak te maken met beveiligingsproblemen, waarvan de oplossingen elkaar tegenspreken. Wat beschermd is tegen aanvallen van “whales” met miljarden tokens (“big stake”), is kwetsbaar voor aanvallen door duizenden accounts met kleine saldi (“sybil stake”), en de maatregelen die tegen de ene aanval worden genomen, zoals niet-lineaire vergoedingen die zijn ontworpen om het voordelig maken voor een grote stake, worden meestal ondermijnd door een andere aanval. Aangezien het gaat om een economisch spel, kunnen de bijbehorende statistische gewichten van tevoren worden berekend, en kunnen de vergoedingen simpelweg worden vervangen door gerandomiseerde met de bijbehorende distributie. Dergelijke probabilistische vergoedingen worden uiterst eenvoudig geïmplementeerd, als er een betrouwbare bron van randomisatie in de blockchain aanwezig is, en vereisen geen complexe berekeningen, wat het leven voor zowel whales als sybil-accounts bemoeilijkt.
Het is echter belangrijk om te blijven onthouden dat controle over één bit in deze randomisatie kan leiden tot misleiding, waarbij de kansen dubbel worden verlaagd of verhoogd, dus eerlijke PVRB is een cruciaal onderdeel van dergelijke protocollen.
Waar vind je de juiste randomisatie?
In theorie stelt eerlijke willekeurige selectie in gedecentraliseerde netwerken in staat om aantoonbare veiligheid van bijna elk protocol tegen samenzwering te waarborgen. De onderbouwing is vrij eenvoudig: als een netwerk overeenkomt over één bit, 0 of 1, en minder dan de helft van de deelnemers oneerlijk is, dan, bij voldoende iteraties, zal het netwerk met vaste waarschijnlijkheid zeker tot consensus komen over dit bit. Gewoon omdat eerlijke randomisatie 51 van de 100 deelnemers in 51% van de gevallen zal kiezen. Maar dit is theoretisch, aangezien in echte netwerken, om een dergelijk niveau van veiligheid te waarborgen als in de artikelen, een overvloed aan berichten tussen hosts vereist is, complexe multi-stap cryptografie, en elke complicatie van het protocol onmiddellijk nieuwe aanvalsvectoren toevoegt.
Daarom zien we op dit moment nog geen bewezen robuuste PVRB in blockchains, die al voldoende tijd heeft doorgebracht om te worden getest door echte applicaties, meerdere audits, belastingstests, en uiteraard echte aanvallen, zonder welke het moeilijk is om een product echt veilig te noemen.
Toch zijn er meerdere veelbelovende benaderingen, die in veel details verschillen, en een van hen zal zeker het probleem oplossen. Met de huidige rekenkracht kan cryptografische theorie zich behoorlijk vlot vertalen naar praktische toepassingen. In de toekomst delen we graag informatie over de implementaties van PVRB: er zijn momenteel verschillende, elk met hun eigen set belangrijke eigenschappen en kenmerken in de uitvoering, en achter elk staat een goed idee. Er zijn niet zoveel teams die zich met randomisatie bezighouden, en de ervaring van elk van hen is van groot belang voor de rest. We hopen dat onze informatie andere teams helpt om sneller vooruitgang te boeken, met inachtneming van de ervaringen van hun voorgangers.
Bron: habr.com
