Hallo, Habr!
In dit artikel bespreek ik de generatie van pseudo-willekeurige getallen door deelnemers die elkaar niet vertrouwen. Zoals we hieronder zullen zien, is het realiseren van een 'bijna' goede generator vrij eenvoudig, maar een zeer goede generator is complex.
Waarom is het überhaupt nodig om willekeurige getallen te genereren voor deelnemers die elkaar niet vertrouwen? Een van de toepassingsgebieden is gedecentraliseerde applicaties. Bijvoorbeeld, een applicatie die een inzet van een deelnemer accepteert en ofwel het bedrag met 49% verdubbelt, ofwel 51% afneemt, werkt alleen als deze onbevooroordeeld een willekeurig getal kan krijgen. Als een aanvaller invloed kan uitoefenen op de uitkomst van de willekeurige getallengenerator, en zelfs zijn kansen om een betaling in de applicatie te krijgen een beetje kan verhogen, zal hij deze gemakkelijk kunnen leegroven.
Wanneer we een gedistribueerd protocol voor het genereren van willekeurige getallen ontwikkelen, willen we dat het drie eigenschappen heeft:
Het moet onbevooroordeeld zijn. Met andere woorden, geen enkele deelnemer mag de uitkomst van de willekeurige getallengenerator op enige manier beïnvloeden.
Het moet onvoorspelbaar zijn. Met andere woorden, geen enkele deelnemer mag in staat zijn te voorspellen welk getal zal worden gegenereerd (of enige van zijn eigenschappen kan afleiden) voordat het is gegenereerd.
Het protocol moet levensvatbaar zijn, dat wil zeggen bestand tegen het feit dat een bepaald percentage deelnemers het netwerk verlaat of opzettelijk probeert het protocol te stoppen.
In dit artikel zullen we twee benaderingen bespreken: RANDAO + VDF en een benadering gebaseerd op foutencorrectiecodes. In het volgende deel zullen we de benadering gebaseerd op drempelhandtekeningen in detail behandelen.
Maar laten we eerst een eenvoudige en vaak gebruikte algoritme bekijken die levensvatbaar, onvoorspelbaar, maar bevooroordeeld is.
RANDAO
RANDAO is een zeer eenvoudige en daardoor vrij vaak gebruikte benadering voor het verkrijgen van willekeurigheid. Alle deelnemers in het netwerk kiezen eerst lokaal een pseudo-willekeurig getal, waarna elke deelnemer de hash van het gekozen getal verzendt. Vervolgens onthullen de deelnemers om beurten hun gekozen getallen en voeren ze een XOR-bewerking uit op de onthulde getallen, en het resultaat van deze bewerking wordt het resultaat van het protocol.
De stap met het publiceren van hashes voordat de cijfers worden onthuld is noodzakelijk, zodat de aanvaller zijn cijfer niet kan kiezen nadat hij de cijfers van de andere deelnemers heeft gezien. Dit zou hem in staat stellen om feitelijk eenzijdig de output van de random number generator te bepalen.
Tijdens het protocol moeten de deelnemers twee keer tot een gezamenlijke beslissing komen (de zogenaamde consensus): wanneer ze de gekozen cijfers beginnen te onthullen en dus stoppen met het accepteren van hashes, en wanneer ze stoppen met het accepteren van de gekozen cijfers en het resulterende willekeurige nummer berekenen. Het maken van deze beslissingen tussen deelnemers die elkaar niet vertrouwen, is op zichzelf al een moeilijke opgave, en we zullen hier later in toekomstige artikelen op terugkomen; in dit artikel gaan we ervan uit dat zo'n consensus-algoritme beschikbaar is.
Welke van de eigenschappen die we hierboven beschreven hebben, zijn van toepassing op RANDAO? Het is onvoorspelbaar, heeft dezelfde levensvatbaarheid als het onderliggende consensusprotocol, maar het is bevooroordeeld. In het bijzonder kan een aanvaller het netwerk observeren, en nadat andere deelnemers hun cijfers hebben onthuld, kan hij hun XOR berekenen en beslissen of hij zijn cijfer onthult of niet, om de uitkomst te beïnvloeden. Hoewel dit de aanvaller niet in staat stelt om de output van de random number generator eenzijdig te bepalen, geeft het hem nog steeds 1 bit invloed. En als aanvallers meerdere deelnemers controleren, is het aantal bits dat zij beheersen gelijk aan het aantal deelnemers onder hun controle.
De invloed van aanvallers kan sterk worden verminderd door te vereisen dat deelnemers de cijfers in volgorde onthullen. Dan kan een aanvaller de uitkomst alleen beïnvloeden als hij als laatste onthult. Hoewel de invloed veel geringer is, blijft het algoritme nog steeds bevooroordeeld.
RANDAO + VDF
Een van de manieren om RANDAO onbevooroordeeld te maken, is als volgt: nadat alle cijfers zijn onthuld en de XOR is berekend, wordt het resultaat opgegeven als invoer voor een functie die erg veel tijd kost om te berekenen, maar die het mogelijk maakt om de correctheid van de berekening zeer snel te controleren.
(vdf_output, vdf_proof) = VDF_compute(input) // dit is erg traag
correct = VDF_verify(input, vdf_output, vdf_proof) // dit is erg snelDeze functie wordt een Verifiable Delay Function, of VDF, genoemd. Als de berekening van het uiteindelijke resultaat meer tijd in beslag neemt dan de fase van het onthullen van getallen, kan een aanvaller het effect van het tonen of verbergen van zijn getal niet voorspellen, waardoor hij geen invloed kan uitoefenen op het resultaat.
Het ontwikkelen van goede VDF's is uiterst complex. De laatste tijd zijn er verschillende doorbraken geweest, zoals en die VDF's praktischer maken, en Ethereum 2.0 is van plan om op lange termijn RANDAO met VDF te gebruiken als bron van willekeurige getallen. Naast het feit dat deze aanpak onvoorspelbaar en onbevooroordeeld is, heeft het een bijkomend voordeel dat het levensvatbaar is, mits ten minste twee deelnemers beschikbaar zijn in het netwerk (op voorwaarde dat het gebruikte consensusprotocol levensvatbaar is bij zo'n klein aantal deelnemers).
De grootste uitdaging van deze aanpak ligt in het zodanig instellen van de VDF dat zelfs een deelnemer met zeer dure gespecialiseerde apparatuur de VDF niet kan berekenen voordat de onthulfase is voltooid. Idealiter zou het algoritme zelfs een aanzienlijke veiligheidsmarge moeten hebben, laten we zeggen 10x. In de onderstaande afbeelding wordt een aanval getoond van een deelnemer met gespecialiseerde ASIC's, waardoor hij de VDF sneller kan uitvoeren dan de tijd die is gereserveerd voor het onthullen van de bevestiging van RANDAO. Deze deelnemer kan nog steeds het uiteindelijke resultaat berekenen met en zonder zijn getal, en op basis van die berekeningen kiezen of hij het toont of niet.
Voor het eerder genoemde VDF-familie kan de prestatie van gespecialiseerde ASIC's meer dan 100 keer hoger zijn dan die van gewone apparatuur. Dus als de onthulfase 10 seconden duurt, zou de VDF die op zo'n ASIC wordt berekend meer dan 100 seconden moeten duren om 10 keer veiligheidsmarge te hebben; en aldus zou dezelfde VDF, berekend op gewone apparatuur, 100 x 100 seconden = ~ 3 uur moeten duren.
De Ethereum Foundation is van plan dit probleem op te lossen door eigen openbare gratis ASIC's te creëren. Zodra dit gebeurt, kunnen ook andere protocollen profiteren van deze technologie, maar totdat dat zo is, zal de RANDAO + VDF-aanpak niet even levensvatbaar zijn voor protocollen die niet in de ontwikkeling van hun eigen ASIC's kunnen investeren.
Er is veel artikelen, video's en andere informatie over VDF verzameld op .
We gebruiken foutencodes
In dit gedeelte zullen we het protocol voor het genereren van willekeurige getallen bespreken, dat gebruikmaakt van . Het kan tot ⅓ aanvallers weerstaan en staat tot ⅔ aanvallers toe voordat zij de uitkomst kunnen voorspellen of beïnvloeden.
Het belangrijkste idee van het protocol is als volgt. Ter vereenvoudiging nemen we aan dat er precies 100 deelnemers zijn. Laten we ook aannemen dat alle deelnemers lokaal een bepaalde privésleutel hebben en dat de publieke sleutels van alle deelnemers aan alle deelnemers bekend zijn:
Elke deelnemer bedenkt lokaal een lange string, splitst deze in 67 delen, genereert foutencodes om 100 aandelen te verkrijgen, zodat elke groep van 67 voldoende is voor het terughalen van de string, wijst elk van de 100 aandelen toe aan een van de deelnemers en versleutelt deze met de openbare sleutel van dezelfde deelnemer. Daarna worden alle versleutelde aandelen gepubliceerd.
De deelnemers gebruiken enige consensus om overeenstemming te bereiken over de gecodeerde sets van specifieke 67 deelnemers.
Zodra de consensus is bereikt, neemt elke deelnemer de gecodeerde aandelen in elke van de 67 sets, versleuteld met hun openbare sleutel, ontsleutelt al deze aandelen en publiceert al deze ontsleutelde aandelen.
Zodra 67 deelnemers stap (3) hebben voltooid, kunnen alle overeenkomen sets volledig worden gedecodeerd en hersteld dankzij de eigenschappen van foutencodes, en het uiteindelijke getal kan worden verkregen als de XOR van de oorspronkelijke strings waarmee de deelnemers begonnen in (1).
Het is mogelijk aan te tonen dat dit protocol onbevooroordeeld en onvoorspelbaar is. Het resulterende willekeurige getal wordt vastgesteld na het bereiken van consensus, maar is voor niemand bekend totdat ⅔ van de deelnemers de delen die met hun openbare sleutel zijn versleuteld hebben gedecodeerd. Op deze manier is het willekeurige getal vastgesteld voordat de informatie die nodig is voor het herstel ervan, is gepubliceerd.
Wat gebeurt er als in stap (1) een van de deelnemers versleutelde delen naar andere deelnemers heeft gestuurd die geen correcte erasure code van een bepaalde string zijn? Zonder verdere aanpassingen zullen verschillende deelnemers of de string helemaal niet kunnen herstellen, of verschillende strings herstellen, wat ertoe leidt dat verschillende deelnemers verschillende willekeurige getallen ontvangen. Om dit te voorkomen, kan elk deelnemer, naast de versleutelde delen, ook berekenen van al deze delen, en elke deelnemer stuurt zowel het versleutelde deel als de wortel van de Merkle-boom en een bewijs van de opname van het deel in de Merkle-boom. In consensus, in stap (2), komen de deelnemers niet alleen overeen over een veelvoud van sets, maar ook over een veelvoud van specifieke wortels van dergelijke bomen (als een bepaalde deelnemer zich van het protocol heeft afgekeerd en verschillende wortels van de Merkle-boom naar verschillende deelnemers heeft gestuurd, en twee van deze wortels worden tijdens de consensus getoond, wordt zijn string niet opgenomen in de resulterende set). Aan het einde van de consensus hebben we 67 versleutelde strings en de bijbehorende wortels van de Merkle-boom, zodat er minstens 67 deelnemers zijn (niet noodzakelijk dezelfde die de overeenkomende strings hebben voorgesteld), die voor elke van de 67 strings een bericht hebben met een deel van de erasure code, en een bewijs van opname van hun deel in de overeenkomstige Merkle-boom.
Wanneer een deelnemer in stap (4) 67 delen voor een bepaalde string decodert en probeert de oorspronkelijke string te herstellen, is een van de mogelijkheden:
De string wordt hersteld, en als deze vervolgens weer met erasure codes wordt gecodeerd en de Merkle-boom wordt berekend voor de lokaal berekende delen, komt de wortel overeen met die waarop consensus is bereikt.
De string wordt hersteld, maar de lokaal berekende wortel komt niet overeen met die waarop consensus is bereikt.
De string kan niet worden hersteld.
Het is gemakkelijk aan te tonen dat als voor een van de deelnemers hierboven variant (1) is gebeurd, dit voor alle deelnemers variant (1) zal zijn, en omgekeerd, als voor een van de deelnemers variant (2) of (3) is gebeurd, dan zal dit voor alle deelnemers variant (2) of (3) zijn. Dus voor elke regel in de set zal ofwel elke deelnemer deze succesvol herstellen, of niemand zal het kunnen herstellen. Het resulterende willekeurige nummer is dus de XOR van alleen die rijen die de deelnemers hebben kunnen herstellen.
Drempelhandtekeningen
Een andere benadering van willekeurigheid is het gebruik van zogenaamde BLS-drempelhandtekeningen. Een willekeurige getallengenerator gebaseerd op drempelhandtekeningen heeft precies dezelfde garanties als het hierboven beschreven algoritme op basis van wissen codes, maar heeft aanzienlijk lagere asymptotische kosten voor het aantal berichten dat over het netwerk wordt verzonden voor elk gegenereerd getal.
BLS-handtekeningen zijn een constructie die het mogelijk maakt voor meerdere deelnemers om één gezamenlijke handtekening voor een bericht te creëren. Dergelijke handtekeningen worden vaak gebruikt om ruimte en bandbreedte te besparen, doordat ze niet vereisen dat meerdere handtekeningen worden verzonden.
Een veelvoorkomende toepassing van BLS-handtekeningen in blockchainprotocollen, naast het genereren van willekeurige getallen, is het ondertekenen van blokken in BFT-protocollen. Stel dat 100 deelnemers blokken creëren en een blok als definitief wordt beschouwd als 67 van hen dit ondertekenen. Al deze deelnemers kunnen hun delen van de BLS-handtekening presenteren en een consensus-algoritme gebruiken om 67 van hen overeen te laten komen, en deze vervolgens samenvoegen tot één BLS-handtekening. Elke combinatie van 67 (of meer) delen kan worden gebruikt om de uiteindelijke handtekening te creëren, die afhankelijk is van welke specifieke 67 handtekeningen zijn samengevoegd, en dus kan verschillen, maar ongeacht het feit dat een andere keuze van 67 deelnemers een andere handtekening zal genereren, zal elke handtekening geldig zijn voor het blok. De overige deelnemers hoeven dan alleen nog maar één handtekening per blok over het netwerk te ontvangen en te verifiëren, in plaats van 67, wat de netwerkbelasting aanzienlijk vermindert.
Het blijkt dat als de privésleutels die door de deelnemers worden gebruikt op een bepaalde manier worden gegenereerd, de resulterende handtekening, ongeacht welke 67 handtekeningen (of meer, maar nooit minder) zijn geaggregeerd, identiek zal zijn. Dit kan worden gebruikt als een bron van willekeurigheid: deelnemers stemmen eerst overeen over een bepaald bericht dat ze zullen ondertekenen (dit kan de output van RANDAO zijn of gewoon de hash van de laatste blok, het maakt in feite niet uit, zolang het elke keer verandert en overeengekomen is), en creëren een BLS-handtekening voor dit bericht. Het resultaat van de generatie zal onvoorspelbaar zijn totdat 67 deelnemers hun delen hebben geleverd, en daarna zijn de uitvoerresultaten al voorbestemd en kunnen ze niet afhangen van de acties van een deelnemer.
Deze aanpak voor willekeurigheid is levensvatbaar als ten minste ⅔ van de deelnemers online is en het protocol volgt, en is eerlijk en onvoorspelbaar zolang ten minste ⅓ van de deelnemers het protocol volgt. Het is belangrijk om op te merken dat een aanvaller die controle heeft over meer dan ⅓ maar minder dan ⅔ van de deelnemers het protocol kan stoppen, maar niet het resultaat kan voorspellen of beïnvloeden.
Drempelhandtekeningen zijn op zich een zeer interessant onderwerp. In het tweede deel van het artikel zullen we in detail bespreken hoe ze werken en hoe deelnemers hun sleutels moeten genereren om drempelhandtekeningen als generatoren van willekeurige getallen te kunnen gebruiken.
Ter conclusie
Dit artikel is de eerste in een serie technische artikelen op de blog. . NEAR is een blockchainprotocol en platform voor de ontwikkeling van gedecentraliseerde applicaties met de nadruk op de eenvoud van ontwikkeling en het gebruiksgemak voor eindgebruikers.
De protocolcode is open, onze implementatie is geschreven in Rust en kan worden gevonden .
Bekijk hoe ontwikkeling op NEAR eruit ziet en experimenteer in de online IDE .
Volg al het nieuws in het Russisch op en in , en in het Engels in de officiële .
Tot snel!
Bron: habr.com
