Er det muligt at generere tilfældige tal, hvis vi ikke har tillid til hinanden? Del 1

Hej Habr!

I denne artikel vil jeg tale om generering af pseudo-tilfældige tal af deltagere, der ikke stoler på hinanden. Som vi vil se nedenfor, er implementeringen af ​​en "næsten" god generator ret enkel, men en meget god en er svær.

Hvorfor skulle det være nødvendigt at generere tilfældige tal blandt deltagere, der ikke stoler på hinanden? Et anvendelsesområde er decentrale applikationer. For eksempel vil en applikation, der accepterer et væddemål fra en deltager og enten fordobler beløbet med en 49 % sandsynlighed eller tager væk med en 51 % sandsynlighed, kun fungere, hvis den upartisk kan modtage et tilfældigt tal. Hvis en angriber kan påvirke resultatet af generatoren af ​​tilfældige tal, og endda en smule øge sin chance for at modtage en udbetaling i applikationen, vil han let ødelægge den.

Når vi designer en protokol til generering af distribueret tilfældigt tal, ønsker vi, at den skal have tre egenskaber:

1. Han må være upartisk. Med andre ord bør ingen deltager på nogen måde påvirke resultatet af tilfældig talgeneratoren.

2. Han må være uforudsigelig. Med andre ord bør ingen deltager være i stand til at forudsige, hvilket tal der vil blive genereret (eller udlede nogen af ​​dets egenskaber), før det genereres.

3. Protokollen skal være levedygtig, det vil sige modstandsdygtig over for, at en vis procentdel af deltagerne afbryder forbindelsen til netværket eller bevidst forsøger at stoppe protokollen.

I denne artikel vil vi se på to tilgange: RANDAO + VDF og metoden med slettekoder. I den næste del vil vi i detaljer undersøge tilgangen baseret på tærskelsignaturer.

Men lad os først se på en simpel og almindeligt brugt algoritme, der er levedygtig, uforudsigelig, men forudindtaget.

RANDAO

RANDAO er en meget enkel og derfor ret almindeligt anvendt tilgang til at generere tilfældighed. Alle netværksdeltagere vælger først lokalt et pseudotilfældigt nummer, derefter sender hver deltager en hash af det valgte nummer. Derefter skiftes deltagerne til at afsløre deres valgte tal og udføre en XOR-operation på de afslørede tal, og resultatet af denne operation bliver resultatet af protokollen.

Trinnet med at offentliggøre hasherne før afsløring af numrene er nødvendigt, så angriberen ikke kan vælge sit nummer, efter at han har set numrene på de andre deltagere. Dette ville give ham mulighed for praktisk talt på egen hånd at bestemme outputtet fra generatoren af ​​tilfældige tal.

I løbet af protokollen skal deltagerne træffe en fælles beslutning (såkaldt konsensus) to gange: hvornår de skal begynde at afsløre de valgte tal, og derfor stoppe med at acceptere hash, og hvornår de skal stoppe med at acceptere de valgte tal og beregne den resulterende tilfældige nummer. At træffe sådanne beslutninger mellem deltagere, der ikke har tillid til hinanden, er ikke en nem opgave i sig selv, og vi vil vende tilbage til det i fremtidige artikler; i denne artikel vil vi antage, at en sådan konsensusalgoritme er tilgængelig for os.

Hvilke af de egenskaber, vi beskrev ovenfor, har RANDAO? Den er uforudsigelig, har samme vitalitet som den underliggende konsensusprotokol, men den er forudindtaget. Specifikt kan en angriber observere netværket, og efter at andre deltagere har afsløret deres tal, kan han beregne deres XOR og beslutte, om han vil afsløre sit nummer for at påvirke resultatet. Selvom dette forhindrer angriberen i på egen hånd at bestemme outputtet af tilfældige talgeneratoren, giver det ham stadig 1 smule indflydelse. Og hvis angribere kontrollerer flere deltagere, så vil antallet af bits, de kontrollerer, være lig med antallet af deltagere under deres kontrol.

Angribernes indflydelse kan reduceres kraftigt ved at kræve, at deltagerne afslører tallene i rækkefølge. Så vil angriberen kun kunne påvirke resultatet, hvis det åbnes sidst. Selvom påvirkningen er betydeligt mindre, er algoritmen stadig forudindtaget.

RANDAO+VDF

En måde at gøre RANDAO objektiv på er denne: efter at alle tallene er afsløret, og XOR er beregnet, føres dens resultat ind i input af en funktion, som tager meget lang tid at beregne, men giver dig mulighed for at kontrollere rigtigheden af udregning meget hurtigt.

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

Denne funktion kaldes Verifiable Delay Function eller VDF. Hvis det tager længere tid at beregne det endelige resultat end nummeroplysningsstadiet, så vil angriberen ikke være i stand til at forudsige effekten af ​​at vise eller skjule sit nummer, og derfor vil han miste muligheden for at påvirke resultatet.

Det er ekstremt svært at udvikle gode VDF'er. Der har været flere gennembrud på det seneste, bl.a. dette и det her, hvilket gjorde VDF mere praktisk i praksis, og Ethereum 2.0 planlægger at bruge RANDAO med VDF som en tilfældig talkilde på sigt. Ud over det faktum, at denne tilgang er uforudsigelig og upartisk, har den den ekstra fordel, at den er levedygtig, hvis mindst to deltagere er tilgængelige på netværket (forudsat at den anvendte konsensusprotokol er levedygtig, når der er tale om et så lille antal deltagere).

Den største udfordring ved denne tilgang er at opsætte VDF'en sådan, at selv en deltager med meget dyrt specialiseret hardware ikke vil være i stand til at beregne VDF'en inden afslutningen af ​​opdagelsesfasen. Ideelt set bør algoritmen endda have en betydelig sikkerhedsmargin, f.eks. 10x. Figuren nedenfor viser et angreb fra en skuespiller, der har en specialiseret ASIC, der giver ham mulighed for at køre en VDF hurtigere end den tid, der er tildelt til at afsløre RANDAO-bekræftelsen. En sådan deltager kan stadig beregne det endelige resultat ved at bruge eller ikke bruge sit nummer, og derefter, baseret på beregningen, vælge, om han vil vise det eller ej.

For VDF-familien nævnt ovenfor kan ydeevnen af ​​en dedikeret ASIC være 100+ gange højere end konventionel hardware. Så hvis implementeringsfasen varer 10 sekunder, så skal VDF'en beregnet på sådan en ASIC tage mere end 100 sekunder for at have en 10x sikkerhedsmargin, og derfor skal den samme VDF beregnet på råvarehardware tage 100x100 sekunder = ~3 timer.

Ethereum Foundation planlægger at løse dette problem ved at skabe sine egne offentligt tilgængelige, gratis ASIC'er. Når dette 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 at udvikle deres egne ASIC'er.

Der er indsamlet mange artikler, videoer og anden information om VDF dette websted.

Vi bruger slettekoder

I dette afsnit vil vi se på en protokol for generering af tilfældige tal, der bruger slette koder. Den kan tolerere op til ⅓ angribere, mens den forbliver levedygtig, og tillader op til ⅔ angribere at eksistere, før de kan forudsige eller påvirke resultatet.

Hovedideen med protokollen er som følger. Lad os for nemheds skyld antage, at der er præcis 100 deltagere. Lad os også antage, at alle deltagere lokalt har en privat nøgle, og alle deltageres offentlige nøgler er kendt af alle deltagere:

1. Hver deltager kommer lokalt med en lang streng, deler den op i 67 dele, opretter slettekoder for at opnå 100 delinger, således at alle 67 er nok til at gendanne strengen, tildeler hver af de 100 delinger til en af ​​deltagerne og krypterer dem med den samme deltagers offentlige nøgle. Alle indkodede aktier offentliggøres derefter.

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

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

4. Når 67 deltagere har gennemført trin (3), kan alle aftalte sæt afkodes og rekonstrueres fuldstændigt på grund af slettekodernes egenskaber, og det endelige tal kan opnås som en XOR af de indledende rækker, som deltagerne startede med i (1) .

Denne protokol kan vise sig at være upartisk og uforudsigelig. Det resulterende tilfældige tal bestemmes efter konsensus er nået, men er ikke kendt af nogen, før ⅔ af deltagerne afkoder delene krypteret med deres offentlige nøgle. Det tilfældige antal bestemmes således, før der offentliggøres tilstrækkelige oplysninger til at rekonstruere det.

Hvad sker der, hvis en af ​​deltagerne i trin (1) sendte kodede shares til de andre deltagere, som ikke er den korrekte slettekode for en streng? Uden yderligere ændringer vil forskellige deltagere enten slet ikke være i stand til at gendanne strengen, eller de vil gendanne forskellige strenge, hvilket vil resultere i, at forskellige deltagere modtager et andet tilfældigt tal. For at forhindre dette kan du gøre følgende: hver deltager beregner udover de kodede aktier også Merkla træ alle sådanne delinger, og sender hver deltager både selve den kodede andel og roden af ​​merkle-træet og bevis for inkluderingen af ​​andelen i merkle-træet. I konsensus i trin (2) er deltagerne så ikke bare enige om et sæt sæt, men om et sæt specifikke rødder af sådanne træer (hvis en deltager afveg fra protokollen og sendte forskellige merkle trærødder til forskellige deltagere, og to sådanne rødder vises under konsensus, hans række er ikke inkluderet i resultatsættet). Som et resultat af konsensus vil vi have 67 kodede linjer og de tilsvarende rødder af merkle-træet, således at der er mindst 67 deltagere (ikke nødvendigvis de samme, som foreslog de tilsvarende linjer), som for hver af de 67 linjer har en meddelelse med en andel af slettekoden og et bevis på, at forekomsten af ​​deres andel i det tilsvarende træ er falmet.

Når deltageren i trin (4) dechifrerer 67 slag for en bestemt streng og forsøger at rekonstruere den originale streng ud fra dem, er en af ​​mulighederne mulig:

1. Strengen gendannes, og hvis den så slettes kodet igen, og Merkle-træet beregnes for de lokalt beregnede andele, falder roden sammen med den, der blev opnået konsensus om.

2. Rækken gendannes, men den lokalt beregnede rod stemmer ikke overens med den, hvor konsensus blev opnået.

3. Rækken er ikke gendannet.

Det er let at vise, at hvis mulighed (1) fandt sted for mindst én deltager ovenfor, så skete mulighed (1) for alle deltagere, og omvendt, hvis mulighed (2) eller (3) fandt sted for mindst én deltager, så for alle deltagere vil mulighed (2) eller (3) ske. For hver række i sættet vil enten alle deltagere gendanne det, eller alle deltagere vil ikke gendanne det. Det resulterende tilfældige tal er så en XOR af kun de rækker, som deltagerne var i stand til at gendanne.

Tærskelsignaturer

En anden tilgang til tilfældighed er at bruge det, der kaldes BLS-tærskelsignaturer. En tilfældig talgenerator baseret på tærskelsignaturer har nøjagtig de samme garantier som den slettekodebaserede algoritme beskrevet ovenfor, men har et væsentligt lavere asymptotisk antal meddelelser sendt over netværket for hvert genereret nummer.

BLS-signaturer er et design, der gør det muligt for flere deltagere at oprette én fælles signatur for en besked. Disse signaturer bruges ofte til at spare plads og båndbredde ved ikke at kræve, at flere signaturer skal sendes ud. 

En almindelig applikation til BLS-signaturer i blockchain-protokoller, udover at generere tilfældige tal, er bloksignering i BFT-protokoller. Lad os sige, at 100 deltagere opretter blokke, og en blok betragtes som endelig, hvis 67 af dem underskriver den. De kan alle indsende deres dele af BLS-signaturen og bruge en eller anden konsensusalgoritme til at blive enige om 67 af dem og derefter flette dem til én BLS-signatur. Alle 67 (eller flere) dele kan bruges til at skabe den endelige signatur, hvilket vil afhænge af hvilke 67 signaturer der blev kombineret og derfor kan variere, selvom forskellige valg af de 67 deltagere vil skabe en anden signatur, vil enhver sådan signatur være en gyldig underskrift for blokken. De resterende deltagere skal så kun modtage og verificere én signatur pr. blok, i stedet for 67, over netværket, hvilket reducerer belastningen på netværket markant.

Det viser sig, at hvis de private nøgler, som deltagerne bruger, er genereret på en bestemt måde, så vil den resulterende signatur være den samme, uanset hvilke 67 signaturer (eller flere, men ikke færre), der er samlet. Dette kan bruges som en kilde til tilfældighed: Deltagerne bliver først enige om en besked, som de vil underskrive (dette kan være output fra RANDAO eller bare hashen fra den sidste blok, det betyder ikke rigtig noget, så længe det ændres hver gang og er konsekvent) og opret en BLS-signatur for det. Resultatet af generationen vil være uforudsigeligt, indtil 67 deltagere leverer deres dele, og derefter er outputtet allerede forudbestemt og kan ikke afhænge af nogen deltagers handlinger.

Denne tilgang til tilfældighed er levedygtig, så længe mindst ⅔ af deltagerne online både 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 er i sig selv et meget interessant emne. I anden del af artiklen vil vi analysere i detaljer, hvordan de fungerer, og hvordan det præcist er nødvendigt at generere deltagernøgler, så tærskelsignaturer kan bruges som en tilfældig talgenerator.

Afslutningsvis

Denne artikel er den første i en række tekniske blogartikler NEAR. NEAR er en blockchain-protokol og -platform til udvikling af decentrale applikationer med vægt på nem udvikling og brugervenlighed for slutbrugere.

Protokolkoden er åben, vores implementering er skrevet i Rust, den kan findes her.

Du kan se, hvordan udviklingen for NEAR ser ud, og eksperimentere i online IDE her.

Du kan følge alle nyhederne på russisk kl telegram gruppe og gruppe på VKontakte, og på engelsk i det officielle twitter.

Со скорых встреч!

Kilde: www.habr.com