Kan vi generere tilfældige tal, hvis vi ikke stoler på hinanden? Del 1

Hello, Habr!

I denne artikel vil jeg fortælle om generering af pseudo-tilfældige tal blandt deltagere, der ikke stoler på hinanden. Som vi vil se nedenfor, er det relativt simpelt at implementere en "næsten" god generator, men en virkelig god er svær.

Hvorfor er det overhovedet nødvendigt at generere tilfældige tal for deltagere, der ikke stoler på hinanden? Et af anvendelsesområderne er decentraliserede applikationer. For eksempel vil en applikation, der modtager et væddemål fra en deltager og enten fordobler beløbet med 49% sandsynlighed eller tager 51%, kun fungere, hvis den kan modtage et tilfældigt tal neutralt. Hvis en ondsindet aktør kan påvirke resultatet af den tilfældige talgenerator, selv minimalt øge sin chance for at modtage en udbetaling i applikationen, kan han let tømme den.

Når vi udvikler en distribueret protokol til generering af tilfældige tal, ønsker vi, at den har tre egenskaber:

1. Den skal være upartisk. Med andre ord skal ingen deltager på nogen måde påvirke resultatet af den tilfældige talgenerator.

2. Den skal være uforudsigelig. Med andre ord skal ingen deltager være i stand til at forudsige, hvilket tal der vil blive genereret (eller udlede nogen af dens egenskaber) før det bliver genereret.

3. Protokollen skal være levedygtig, det vil sige modstandsdygtig overfor, at en vis procentdel af deltagerne frakobles netværket eller med vilje forsøger at stoppe protokollen.

I denne artikel vil vi se på to tilgange: RANDAO + VDF og en tilgang baseret på udslettende koder. I den næste del vil vi grundigt gennemgå tilgangen baseret på tærskelsignaturer.

Men lad os først gennemgå en simpel og ofte anvendt algoritme, der er levedygtig, uforudsigelig, men partisk.

RANDAO

RANDAO er en meget simpel og derfor ret ofte anvendt tilgang til at opnå tilfældighed. Alle deltagere i netværket vælger først lokalt et pseudo-tilfældigt tal, hvorefter hver deltager sender en hash af det valgte tal. Derefter afslører deltagerne skiftevis deres valgte tal og udfører en XOR-operation på de afslørede tal, og resultatet af denne operation bliver resultatet af protokollen.

Trin med at offentliggøre hasher før afsløringen af numrene er nødvendig for at sikre, at en angriber ikke kan vælge sit eget nummer efter at have set de andre deltageres numre. Dette ville give dem mulighed for faktisk at bestemme resultatet af den tilfældige talgenerator alene.

Under protokollen skal deltagerne nå til enighed to gange (den såkaldte konsensus): hvornår de skal begynde at afsløre de valgte numre og dermed stoppe med at modtage hasher, og hvornår de skal afslutte modtagelsen af de valgte numre og beregne det resulterende tilfældige tal. At træffe sådanne beslutninger blandt deltagere, der ikke stoler på hinanden, er i sig selv en udfordrende opgave, og vi vil vende tilbage til det i fremtidige artikler; i denne artikel antager vi, at en sådan konsensusalgoritme er tilgængelig.

Hvilke af de egenskaber, vi har beskrevet ovenfor, har RANDAO? Den er uforudsigelig, har samme levedygtighed som den underliggende konsensusprotokol, men den er skæv. Især kan en angriber overvåge netværket, og efter at de andre deltagere har afsløret deres numre, kan han beregne deres XOR og beslutte, om han vil afsløre sit eget nummer for at påvirke resultatet. Selvom dette ikke tillader angriberen at bestemme resultatet af den tilfældige talgenerator, giver det ham stadig 1 bit indflydelse. Og hvis angriberne kontrollerer flere deltagere, vil antallet af bits, de kontrollerer, være lig med antallet af deltagere under deres kontrol.

Indflydelsen fra angribere kan reduceres betydeligt, hvis det kræves, at deltagerne afslører numrene i rækkefølge. Så vil angriberen kun kunne påvirke udfaldet, hvis han afslører sidst. Selvom indflydelsen er meget mindre, er algoritmen stadig skæv.

RANDAO + VDF

En af metoderne til at gøre RANDAO skæv er følgende: efter at alle numre er afsløret, og XOR er beregnet, sendes resultatet som input til en funktion, der tager meget lang tid at beregne, men som muliggør hurtig verifikation af beregningens korrekthed.

(vdf_output, vdf_proof) = VDF_compute(input) // dette er meget langsomt
correct = VDF_verify(input, vdf_output, vdf_proof) // dette er meget hurtigt

Denne funktion kaldes Verifiable Delay Function, eller VDF. Hvis beregningen af det endelige resultat tager længere tid, end trinnet med at afsløre tallene, så kan en angriber ikke forudsige effekten af at demonstrere eller skjule sit tal, og vælger derfor at miste muligheden for at påvirke resultatet.

Udviklingen af gode VDF'er er utrolig kompleks. I de seneste år er der gjort flere gennembrud, som for eksempel denne og dette, som har gjort VDF'er mere anvendelige i praksis, og Ethereum 2.0 planlægger på lang sigt at bruge RANDAO sammen med VDF som en kilde til tilfældige tal. Udover at denne tilgang er uforudsigelig og objektiv, har den den ekstra fordel, at den er levedygtig, så længe mindst to deltagere er tilgængelige i netværket (forudsat at den anvendte konsensusprotokol er levedygtig ved en så lille deltagergruppe).

Den største udfordring ved denne tilgang er at indstille VDF korrekt, så selv en deltager med meget dyrt specialudstyr ikke kan beregne VDF'en før afslutningsfasen. Ideelt set bør algoritmen have en betydelig sikkerhedsmargin, lad os sige 10x. I figuren nedenfor ses et angreb fra en deltager med specialiseret ASIC, som gør det muligt for ham at køre VDF hurtigere end den tid, der er afsat til at afsløre bekræftelsen fra RANDAO. En sådan deltager kan stadig beregne det endelige resultat ved at bruge og ikke bruge sit tal, og derefter vælge at vise det eller ej, baseret på beregningerne.

For den ovennævnte familie af VDF'er kan præstationen af en specialiseret ASIC være mere end 100 gange højere end almindeligt udstyr. Så hvis afsløringsfasen varer 10 sekunder, skal VDF'en, der beregnes på en sådan ASIC, tage mere end 100 sekunder for at have en 10 gange sikkerhedsmargin, og derfor skal den samme VDF, der beregnes på almindeligt udstyr, tage 100 x 100 sekunder = ~ 3 timer.

Ethereum Foundation planlægger at løse dette problem ved at skabe deres egne offentligt tilgængelige gratis ASIC. Så snart det sker, kan alle andre protokoller også drage fordel af denne teknologi, men indtil da vil RANDAO + VDF-tilgangen ikke være lige så levedygtig for protokoller, der ikke kan investere i udviklingen af deres egne ASIC.

Masser af artikler, videoer og andre oplysninger om VDF er samlet på denne hjemmeside.

Vi bruger fejkoder

I dette afsnit vil vi se på protokollen til generering af tilfældige tal, der bruger fejkoder. Den kan modstå op til ⅓ ondsindede aktører og tillader eksistensen af op til ⅔ ondsindede aktører, før de kan forudsige eller påvirke resultatet.

Hovedideen i protokollen er som følger. For enkelheds skyld antager vi, at der præcist er 100 deltagere. Lad os også antage, at alle deltagere har en privat nøgle lokalt, og de offentlige nøgler for alle deltagere er kendt af alle deltagere:

1. Hver deltager opdager lokalt en lang streng, opdeler den i 67 dele, skaber fejkoder for at få 100 andele, sådan at 67 af dem er tilstrækkelige til at genoprette strengen, tildeler hver af de 100 andele til en deltager og krypterer dem med den pågældende deltagers offentlige nøgle. Derefter offentliggøres alle kodede andele.

2. Deltagerne bruger en form for konsensus for at nå til enighed om de kodede sæt fra specificerede 67 deltagere.

3. Når konsensus er nået, tager hver deltager de kodede andele fra hvert af de 67 sæt, krypteret med deres offentlige nøgle, dekrypterer alle sådanne andele og offentliggør alle sådanne dekrypterede andele.

4. Når de 67 deltagere har udført trin (3), kan alle de aftalte sæt fuldt ud dekodes og genoprettes takket være egenskaberne ved fejkoder, og det endelige tal kan opnås som XOR af de oprindelige strenge, som deltagerne startede med i (1).

Det kan vises, at denne protokol er upartisk og uforudsigelig. Det resulterende tilfældige tal defineres efter opnåelse af konsensus, men ingen kender det, før ⅔ af deltagerne har dekodet de dele, der er krypteret med deres offentlige nøgle. Således er det tilfældige tal defineret tidligere end den information, der er tilstrækkelig til at genetablere det, offentliggøres.

Hvad sker der, hvis i trin (1) en af deltagerne sender krypterede andele til de andre deltagere, som ikke er en korrekt slettekode for en bestemt række? Uden yderligere ændringer vil forskellige deltagere enten ikke kunne genskabe rækken overhovedet, eller genskabe forskellige rækker, hvilket vil føre til, at forskellige deltagere får forskellige tilfældige tal. For at forhindre dette kan man gøre følgende: hver deltager, ud over de krypterede andele, beregner også Merkle-træet for alle sådanne andele, og hver deltager sender både den krypterede andel og roden af Merkle-træet samt et bevis for inkluderningen af andelen i Merkle-træet. I konsensus skal i trin (2) deltagerne ikke bare blive enige om en mængde sæt, men om en mængde konkrete rødder af sådanne træer (hvis en deltager er gået væk fra protokollen og har sendt forskellige rødder af Merkle-træet til forskellige deltagere, og to sådanne rødder vises under konsensus, inkluderes hans række ikke i det resulterende sæt). Efter konsensus vil vi have 67 krypterede rækker og de tilsvarende rødder af Merkle-træet, således at der er mindst 67 deltagere (ikke nødvendigvis de samme, der foreslog de tilsvarende rækker), der for hver af de 67 rækker har en besked med en andel af slettekoden og et bevis for, at deres andel er inkluderet i det tilsvarende Merkle-træ.

Når i trin (4) en deltager dekrypterer 67 andele for en bestemt række og forsøger at genskabe den oprindelige række, er en af mulighederne:

1. Rækken genskabes, og hvis den derefter krypteres med slettekoder igen og Merkle-træet beregnes for de beregnede lokale andele, stemmer roden overens med den, hvor konsensus er opnået.

2. Rækken genskabes, men den beregnede lokale rod svarer ikke til den, hvor konsensus er opnået.

3. Rækken kan ikke genskabes.

Det er let at vise, at hvis mindst én deltager har oplevet situation (1), så vil alle deltagere også opleve situation (1), og omvendt, hvis mindst én deltager har oplevet situation (2) eller (3), så vil alle deltagere opleve situation (2) eller (3). På den måde vil hver række i sættet enten blive genoprettet af alle deltagere, eller alle deltagere vil ikke kunne genoprette den. Det resulterende tilfældige tal er dermed XOR kun af de rækker, som deltagerne kunne genoprette.

Terskelsignaturer

En anden tilgang til tilfældighed involverer brugen af såkaldte BLS-terskelsignaturer. En tilfældig talgenerator, der er baseret på terskelsignaturer, har nøjagtig de samme garantier som den ovenfor beskrevne algoritme baseret på udviskende koder, men har en betydeligt lavere asymptotisk mængde meddelelser, der sendes over netværket for hvert genereret tal.

BLS-signaturer er en konstruktion, der muliggør, at flere deltagere kan oprette én fælles signatur for en meddelelse. Sådanne signaturer bruges ofte til at spare plads og båndbredde, da de ikke kræver udsendelse af flere signaturer. 

En almindelig anvendelse af BLS-signaturer i blockchain-protokoller, ud over generering af tilfældige tal, er signering af blokke i BFT-protokoller. Lad os sige, at 100 deltagere opretter blokke, og en blok betragtes som endelig, hvis 67 af dem signerer den. Alle kan præsenterer deres dele af BLS-signaturen og bruge en eller anden konsensus-algoritme til at enes om 67 af dem og derefter kombinere dem til én BLS-signatur. Enhver gruppe med 67 (eller flere) dele kan bruges til at skabe den endelige signatur, som afhænger af, hvilke 67 signaturer der er blevet kombineret, og derfor kan variere; men på trods af at forskellige valg af de 67 deltagere vil skabe forskellige signaturer, vil enhver sådan signatur være en gyldig signatur for blokken. De øvrige deltagere skal derefter blot modtage og verificere én signatur pr. blok over netværket, i stedet for 67, hvilket markant reducerer belastningen på netværket.

Det viser sig, at hvis de private nøgler, som deltagerne bruger, genereres på en bestemt måde, vil den resulterende signatur være den samme, uanset hvilke 67 underskrifter (eller flere, men ikke mindre) der er aggregeret. Dette kan bruges som en kilde til tilfældighed: deltagerne aftaler først et bestemt budskab, som de vil underskrive (det kan være output fra RANDAO eller blot hashen fra den seneste blok, det betyder ikke noget, så længe det ændrer sig hver gang og er aftalt), og skaber en BLS-signatur for det. Resultatet af genereringen vil være uforudsigeligt, indtil 67 deltagere leverer deres bidder, hvorefter output allerede er forudbestemt og ikke kan afhænge af nogen deltageres handlinger.

Denne tilgang til tilfældighed er levedygtig, hvis mindst ⅔ af deltagerne er online og følger protokollen, og er upartisk og uforudsigelig, så længe mindst ⅓ af deltagerne følger protokollen. Det er vigtigt at bemærke, at en angriber, der kontrollerer mere end ⅓, men mindre end ⅔ af deltagerne, kan stoppe protokollen, men ikke kan forudsige eller påvirke dens output.

Tærskelsignaturer i sig selv er et meget interessant emne. I den anden del af artiklen vil vi detaljeret gennemgå, hvordan de fungerer, og hvordan det nøjagtigt er nødvendigt at generere deltageres nøgler for at kunne bruge tærskelsignaturerne som generator af tilfældige tal.

Afslutningsvis

Denne artikel er den første i en serie tekniske artikler i bloggen. NEAR. NEAR er en blockchain-protokol og platform til udvikling af decentraliserede applikationer med fokus på enkel udvikling og brugervenlighed for slutbrugere.

Protokolens kode er åben, vores implementering er skrevet i Rust, og den kan findes her.

Du kan se, hvordan udviklingen under NEAR ser ud, og eksperimentere i online-IDE'en. her.

Hold dig opdateret med alle nyheder på russisk i gruppen i Telegram. og i gruppen på VKontakte,mens du kan finde nyheder på engelsk i det officielle Twitter..

Vi ses snart!

Kilde: habr.com