Is het mogelijk om willekeurige getallen te genereren als we elkaar niet vertrouwen? Deel 1

Hé Habr!

In dit artikel zal ik het hebben over het genereren van pseudo-willekeurige getallen door deelnemers die elkaar niet vertrouwen. Zoals we hieronder zullen zien, is het implementeren van een “bijna” goede generator vrij eenvoudig, maar een hele goede is moeilijk.

Waarom zou het nodig zijn om willekeurige getallen te genereren onder deelnemers die elkaar niet vertrouwen? Eén toepassingsgebied zijn decentrale applicaties. Een applicatie die bijvoorbeeld een weddenschap van een deelnemer accepteert en het bedrag verdubbelt met een waarschijnlijkheid van 49% of wegneemt met een waarschijnlijkheid van 51%, werkt alleen als deze onbevooroordeeld een willekeurig getal kan ontvangen. Als een aanvaller de uitkomst van de generator voor willekeurige getallen kan beïnvloeden en zijn kans op een uitbetaling in de applicatie zelfs maar enigszins kan vergroten, zal hij deze gemakkelijk verwoesten.

Wanneer we een gedistribueerd protocol voor het genereren van willekeurige getallen ontwerpen, willen we dat het drie eigenschappen heeft:

1. Hij moet onpartijdig zijn. Met andere woorden: geen enkele deelnemer mag op enigerlei wijze invloed uitoefenen op het resultaat van de willekeurige getallengenerator.

2. Hij moet onvoorspelbaar zijn. Met andere woorden, geen enkele deelnemer zou in staat moeten zijn om te voorspellen welk getal zal worden gegenereerd (of enige van de eigenschappen ervan af te leiden) voordat het wordt gegenereerd.

3. Het protocol moet levensvatbaar zijn, dat wil zeggen bestand zijn tegen het feit dat een bepaald percentage van de deelnemers de verbinding met het netwerk verbreekt of opzettelijk probeert het protocol te stoppen.

In dit artikel zullen we twee benaderingen bekijken: RANDAO + VDF en de aanpak van wiscodes. In het volgende deel zullen we de aanpak op basis van drempelsignaturen in detail onderzoeken.

Maar laten we eerst eens kijken naar een eenvoudig en veelgebruikt algoritme dat levensvatbaar, onvoorspelbaar en bevooroordeeld is.

RANDAO

RANDAO is een zeer eenvoudige en daarom vrij algemeen gebruikte benadering voor het genereren van willekeur. Alle netwerkdeelnemers selecteren eerst lokaal een pseudo-willekeurig getal, waarna elke deelnemer een hash van het geselecteerde nummer verzendt. Vervolgens onthullen de deelnemers om beurten hun gekozen nummers en voeren ze een XOR-operatie uit op de onthulde nummers, en het resultaat van deze operatie wordt het resultaat van het protocol.

De stap van het publiceren van de hashes voordat de cijfers worden onthuld, is noodzakelijk zodat de aanvaller zijn nummer niet kan kiezen nadat hij de nummers van de andere deelnemers heeft gezien. Hierdoor zou hij vrijwel in zijn eentje de uitvoer van de generator voor willekeurige getallen kunnen bepalen.

In de loop van het protocol moeten de deelnemers twee keer tot een gezamenlijk besluit komen (zogenaamde consensus): wanneer ze moeten beginnen met het onthullen van de geselecteerde getallen, en dus moeten stoppen met het accepteren van hashes, en wanneer ze moeten stoppen met het accepteren van de geselecteerde getallen en het berekenen van de resulterende willekeurige getallen. nummer. Dergelijke beslissingen nemen tussen deelnemers die elkaar niet vertrouwen is op zichzelf geen gemakkelijke taak, en we zullen er in toekomstige artikelen op terugkomen; in dit artikel gaan we ervan uit dat een dergelijk consensusalgoritme voor ons beschikbaar is.

Welke van de hierboven beschreven eigenschappen heeft RANDAO? Het is onvoorspelbaar, heeft dezelfde vitaliteit als het onderliggende consensusprotocol, maar is bevooroordeeld. Concreet kan een aanvaller het netwerk observeren, en nadat andere deelnemers hun cijfers hebben onthuld, kan hij hun XOR berekenen en beslissen of hij zijn nummer wel of niet openbaar wil maken om de uitkomst te beïnvloeden. Hoewel dit voorkomt dat de aanvaller in zijn eentje de uitvoer van de generator voor willekeurige getallen bepaalt, geeft het hem nog steeds 1 beetje invloed. En als aanvallers meerdere deelnemers controleren, zal het aantal bits dat zij controleren gelijk zijn aan het aantal deelnemers onder hun controle.

De invloed van aanvallers kan sterk worden verminderd door te eisen dat deelnemers de cijfers in de juiste volgorde onthullen. Dan kan de aanvaller de uitkomst alleen beïnvloeden als deze als laatste wordt geopend. Hoewel de invloed aanzienlijk kleiner is, is het algoritme nog steeds bevooroordeeld.

RANDAO+VDF

Eén manier om RANDAO onbevooroordeeld te maken is deze: nadat alle getallen zijn onthuld en de XOR is berekend, wordt het resultaat ingevoerd in de invoer van een functie, wat erg lang duurt om te berekenen, maar waarmee je de juistheid van de getallen kunt controleren. zeer snel berekenen.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Deze functie wordt Verifiable Delay Function of VDF genoemd. Als het berekenen van het eindresultaat langer duurt dan de fase waarin het nummer wordt bekendgemaakt, kan de aanvaller het effect van het tonen of verbergen van zijn nummer niet voorspellen en verliest hij daardoor de mogelijkheid om het resultaat te beïnvloeden.

Het ontwikkelen van goede VDF's is buitengewoon moeilijk. Er zijn de laatste tijd verschillende doorbraken geweest, b.v. deze и dit, wat VDF in de praktijk praktischer maakte, en Ethereum 2.0 is van plan om RANDAO met VDF op de lange termijn te gebruiken als bron van willekeurige getallen. Afgezien van het feit dat deze aanpak onvoorspelbaar en onbevooroordeeld is, heeft deze als bijkomend voordeel dat deze haalbaar is als er ten minste twee deelnemers beschikbaar zijn op het netwerk (ervan uitgaande dat het gebruikte consensusprotocol haalbaar is als er met zo'n klein aantal deelnemers wordt gewerkt).

De grootste uitdaging van deze aanpak is het zo opzetten van de VDF dat zelfs een deelnemer met zeer dure gespecialiseerde hardware de VDF niet kan berekenen vóór het einde van de ontdekkingsfase. Idealiter zou het algoritme zelfs een aanzienlijke veiligheidsmarge moeten hebben, bijvoorbeeld 10x. De onderstaande afbeelding toont een aanval door een acteur die een gespecialiseerde ASIC heeft waarmee hij een VDF sneller kan uitvoeren dan de tijd die is toegewezen om de RANDAO-bevestiging te onthullen. Zo'n deelnemer kan nog steeds het eindresultaat berekenen met of zonder zijn nummer, en vervolgens, op basis van de berekening, kiezen of hij het wel of niet wil tonen.

Voor de hierboven genoemde VDF-familie kunnen de prestaties van een speciale ASIC meer dan 100 keer hoger zijn dan die van conventionele hardware. Dus als de implementatiefase 10 seconden duurt, moet de VDF berekend op een dergelijke ASIC meer dan 100 seconden duren om een ​​veiligheidsmarge van 10x te hebben, en dus moet dezelfde VDF berekend op gewone hardware 100x 100 seconden = ~3 uur duren.

De Ethereum Foundation is van plan dit probleem op te lossen door haar eigen openbaar beschikbare, gratis ASIC’s te creëren. Zodra dit gebeurt, kunnen alle andere protocollen ook profiteren van deze technologie, maar tot die tijd zal de RANDAO+VDF-aanpak niet zo haalbaar zijn voor protocollen die niet kunnen investeren in de ontwikkeling van hun eigen ASIC's.

Er zijn veel artikelen, video's en andere informatie over VDF verzameld deze site.

Wij maken gebruik van wiscodes

In deze sectie zullen we kijken naar een protocol voor het genereren van willekeurige getallen dat gebruikmaakt van codes wissen. Het kan maximaal ⅓ aanvallers tolereren terwijl het levensvatbaar blijft, en laat maximaal ⅔ aanvallers bestaan ​​voordat ze de uitkomst kunnen voorspellen of beïnvloeden.

Het hoofdidee van het protocol is als volgt. Laten we voor de eenvoud aannemen dat er precies 100 deelnemers zijn. Laten we ook aannemen dat alle deelnemers lokaal een privésleutel hebben, en dat de publieke sleutels van alle deelnemers bekend zijn bij alle deelnemers:

1. Elke deelnemer bedenkt lokaal een lange reeks, verdeelt deze in 67 delen, creëert wiscodes om 100 aandelen te verkrijgen, zodat elke 67 voldoende zijn om de reeks te herstellen, wijst elk van de 100 aandelen toe aan een van de deelnemers en codeert ze met de publieke sleutel van dezelfde deelnemer. Alle gecodeerde aandelen worden vervolgens gepubliceerd.

2. Deelnemers gebruiken een vorm van consensus om overeenstemming te bereiken over gecodeerde sets van specifieke 67 deelnemers.

3. Zodra consensus is bereikt, neemt elke deelnemer de gecodeerde aandelen in elk van de 67 sets die zijn gecodeerd met hun publieke sleutel, decodeert al deze aandelen en publiceert al deze gedecodeerde aandelen.

4. Zodra 67 deelnemers stap (3) hebben voltooid, kunnen alle overeengekomen sets volledig worden gedecodeerd en gereconstrueerd vanwege de eigenschappen van uitwiscodes, en kan het uiteindelijke getal worden verkregen als een XOR van de initiële rijen waarmee de deelnemers zijn begonnen in (1). .

Er kan worden aangetoond dat dit protocol onbevooroordeeld en onvoorspelbaar is. Het resulterende willekeurige getal wordt bepaald nadat consensus is bereikt, maar is bij niemand bekend totdat ⅔ van de deelnemers de met hun openbare sleutel gecodeerde delen heeft gedecodeerd. Het willekeurige getal wordt dus bepaald voordat er voldoende informatie wordt gepubliceerd om het te reconstrueren.

Wat gebeurt er als in stap (1) een van de deelnemers gecodeerde shares naar de andere deelnemers stuurt die niet de juiste wiscode voor een bepaalde tekenreeks zijn? Zonder aanvullende wijzigingen zullen verschillende deelnemers de string helemaal niet kunnen herstellen, of zullen ze verschillende strings herstellen, wat ertoe zal leiden dat verschillende deelnemers een ander willekeurig getal ontvangen. Om dit te voorkomen kun je het volgende doen: iedere deelnemer rekent naast de gecodeerde aandelen ook mee Merkla-boom al dergelijke aandelen, en stuurt elke deelnemer zowel het gecodeerde aandeel zelf als de wortel van de merkle-boom, en een bewijs van de opname van het aandeel in de merkle-boom. In de consensus in stap (2) zijn de deelnemers het dan niet alleen eens over een reeks sets, maar over een reeks specifieke wortels van dergelijke bomen (als een deelnemer afwijkt van het protocol en verschillende merkle-boomwortels naar verschillende deelnemers stuurt, en twee van dergelijke wortels worden getoond tijdens consensus, de rij is niet opgenomen in de resultatenset). Als resultaat van de consensus zullen we 67 gecodeerde regels en de overeenkomstige wortels van de merkle-boom hebben, zodat er minstens 67 deelnemers zijn (niet noodzakelijk dezelfde die de overeenkomstige regels hebben voorgesteld), die voor elk van de 67 regels een bericht met een deel van de wiscode, en een bewijs dat het voorkomen van hun aandeel in de overeenkomstige boom vervaagde.

Wanneer de deelnemer in stap (4) 67 tellen voor een bepaalde snaar ontcijfert en daaruit de originele snaar probeert te reconstrueren, is een van de opties mogelijk:

1. De string wordt hersteld, en als deze vervolgens opnieuw wordt gecodeerd met wissen, en de Merkle-boom wordt berekend voor de lokaal berekende aandelen, valt de wortel samen met die waarover consensus werd bereikt.

2. De rij is hersteld, maar de lokaal berekende wortel komt niet overeen met de wortel waarop consensus werd bereikt.

3. De rij wordt niet hersteld.

Het is gemakkelijk aan te tonen dat als optie (1) voor minstens één deelnemer hierboven gebeurde, optie (1) voor alle deelnemers gebeurde, en omgekeerd, als optie (2) of (3) voor minstens één deelnemer gebeurde, dan voor alle deelnemers zal optie (2) of (3) plaatsvinden. Dus voor elke rij in de set zullen alle deelnemers deze met succes herstellen, of zullen alle deelnemers er niet in slagen deze te herstellen. Het resulterende willekeurige getal is dan een XOR van alleen de rijen die deelnemers konden herstellen.

Drempel handtekeningen

Een andere benadering van willekeur is het gebruik van zogenaamde BLS-drempelsignaturen. Een generator van willekeurige getallen op basis van drempelsignaturen heeft precies dezelfde garanties als het hierboven beschreven op wiscode gebaseerde algoritme, maar heeft voor elk gegenereerd nummer een aanzienlijk lager asymptotisch aantal berichten dat over het netwerk wordt verzonden.

BLS-handtekeningen zijn een ontwerp waarmee meerdere deelnemers één gemeenschappelijke handtekening voor een bericht kunnen maken. Deze handtekeningen worden vaak gebruikt om ruimte en bandbreedte te besparen, omdat er niet meerdere handtekeningen hoeven te worden verzonden. 

Een veel voorkomende toepassing voor BLS-handtekeningen in blockchain-protocollen, naast het genereren van willekeurige getallen, is blokondertekening in BFT-protocollen. Laten we zeggen dat 100 deelnemers blokken maken, en een blok wordt als definitief beschouwd als 67 van hen het ondertekenen. Ze kunnen allemaal hun delen van de BLS-handtekening indienen en een consensusalgoritme gebruiken om overeenstemming te bereiken over 67 ervan en deze vervolgens samenvoegen tot één BLS-handtekening. Elke 67 (of meer) delen kunnen worden gebruikt om de definitieve handtekening te maken, die afhangt van welke 67 handtekeningen zijn gecombineerd en daarom kan variëren. Hoewel verschillende keuzes van de 67 deelnemers een andere handtekening zullen creëren, zal elke dergelijke handtekening een geldige handtekening zijn. handtekening voor het blok. De overige deelnemers hoeven dan slechts één handtekening per blok, in plaats van 67, via het netwerk te ontvangen en te verifiëren, wat de belasting van het netwerk aanzienlijk vermindert.

Het blijkt dat als de privésleutels die deelnemers gebruiken op een bepaalde manier worden gegenereerd, ongeacht welke 67 handtekeningen (of meer, maar niet minder) worden samengevoegd, de resulterende handtekening hetzelfde zal zijn. Dit kan worden gebruikt als een bron van willekeur: deelnemers komen eerst een bericht overeen dat ze zullen ondertekenen (dit kan de uitvoer van RANDAO zijn of alleen de hash van het laatste blok, het maakt niet echt uit, zolang het maar elke keer verandert en consistent is) en maak er een BLS-handtekening voor. Het resultaat van de generatie zal onvoorspelbaar zijn totdat 67 deelnemers hun onderdelen leveren, en daarna is de output al vooraf bepaald en kan deze niet afhankelijk zijn van de acties van welke deelnemer dan ook.

Deze benadering van willekeur is haalbaar zolang minstens ⅔ van de deelnemers online het protocol volgt, en is onbevooroordeeld en onvoorspelbaar zolang minstens ⅓ van de deelnemers het protocol volgt. Het is belangrijk op te merken dat een aanvaller die meer dan ⅓ maar minder dan ⅔ van de deelnemers controleert, het protocol kan stoppen, maar de output ervan niet kan voorspellen of beïnvloeden.

Drempelhandtekeningen zelf zijn een zeer interessant onderwerp. In het tweede deel van het artikel zullen we in detail analyseren hoe ze werken, en hoe het precies nodig is om deelnemerssleutels te genereren, zodat drempelhandtekeningen kunnen worden gebruikt als generator van willekeurige getallen.

Concluderend

Dit artikel is het eerste in een reeks technische blogartikelen NEAR. NEAR is een blockchain-protocol en -platform voor het ontwikkelen van gedecentraliseerde applicaties met de nadruk op ontwikkelgemak en gebruiksgemak voor eindgebruikers.

De protocolcode is open, onze implementatie is geschreven in Rust en is te vinden hier.

In de online IDE kun je zien hoe de ontwikkeling voor NEAR eruit ziet en experimenteren hier.

U kunt al het nieuws in het Russisch volgen op telegram groep en groep op VKontakte, en in het Engels in de ambtenaar tjilpen.

Tot ziens!

Bron: www.habr.com