Kan vi generera slumpmässiga tal om vi inte litar på varandra? Del 1

Hej, Habr!

I den här artikeln kommer jag att berätta om generering av pseudo-slumptal bland deltagare som inte litar på varandra. Som vi kommer att se nedan är det ganska enkelt att implementera en "nästan" bra generator, men en riktigt bra är svår.

Varför behövs det ens att generera slumptal för deltagare som inte litar på varandra? Ett av användningsområdena är decentraliserade applikationer. Till exempel kommer en applikation som tar emot ett bud från en deltagare och antingen dubblar beloppet med sannolikheten 49% eller tar 51% bara att fungera om den kan få ett slumptal opartiskt. Om en illvillig aktör kan påverka resultatet av slumptalsgeneratorn, även om det är minimalt, för att öka sina chanser att få en utbetalning i applikationen, kan han lätt tömma den.

När vi utvecklar ett distribuerat protokoll för generering av slumptal vill vi att det ska ha tre egenskaper:

1. Det måste vara opartiskt. Med andra ord får ingen deltagare på något sätt påverka resultatet av slumptalsgeneratorn.

2. Det måste vara oförutsägbart. Med andra ord får ingen deltagare ha möjlighet att förutsäga vilket tal som kommer att genereras (eller dra några av dess egenskaper) innan det har genererats.

3. Protokollet måste vara livskraftigt, det vill säga motståndskraftigt mot att en viss procentandel av deltagarna kopplar från nätverket eller avsiktligt försöker stoppa protokollet.

I den här artikeln kommer vi att titta på två tillvägagångssätt: RANDAO + VDF och ett tillvägagångssätt baserat på utjämnande koder. I nästa del kommer vi att gå igenom tillvägagångssättet som bygger på tröskel-signaturer.

Men först låt oss gå igenom en enkel och ofta använd algoritm som är livskraftig, oförutsägbar men partisk.

RANDAO

RANDAO är en väldigt enkel och därmed ganska ofta använd metod för att få slumpmässighet. Alla deltagare i nätverket väljer först ett pseudo-slumptal lokalt, sedan skickar varje deltagare hash av det valda talet. Därefter avslöjar deltagarna turas om sina valda tal och utför en XOR-operation på de avslöjade talen, och resultatet av denna operation blir resultatet av protokollet.

Steget med att publicera hash innan man avslöjar siffrorna är nödvändigt för att förhindra att en angripare väljer sitt nummer efter att ha sett siffrorna från andra deltagare. Detta skulle faktiskt ge dem möjlighet att ensamt bestämma resultatet av den slumpmässiga talgeneratorn.

Under protokollet måste deltagarna komma överens två gånger (så kallad konsensus): när man ska avslöja de valda siffrorna och därmed sluta ta emot hash, och när man ska avsluta mottagandet av valda siffror och beräkna det resulterande slumpmässiga numret. Att fatta sådana beslut mellan deltagare som inte litar på varandra är en självklar utmaning, och vi kommer att återkomma till det i framtida artiklar. I den här artikeln förutsätter vi att en sådan konsensusalgoritm är tillgänglig för oss.

Vilka av de egenskaper vi beskrev ovan har RANDAO? Den är oförutsägbar, har samma livskraft som den underliggande konsensusprotokollet, men är partisk. Särskilt en angripare kan observera nätverket, och efter att andra deltagare har avslöjat sina siffror kan de beräkna deras XOR och avgöra om de ska avslöja sitt nummer eller inte, för att påverka resultatet. Medan detta inte tillåter angriparen att ensamt bestämma resultatet av den slumpmässiga talgeneratorn, ger det dem fortfarande 1 bits påverkan. Om angriparna kontrollerar flera deltagare kommer antalet bitar de kontrollerar att motsvara antalet deltagare under deras kontroll.

Angriparnas påverkan kan minskas avsevärt om deltagarna tvingas avslöja sina siffror i ordning. Då kan angriparen endast påverka resultatet om de avslöjar sist. Även om påverkan är avsevärt mindre är algoritmen fortfarande partisk.

RANDAO + VDF

Ett av sätten att göra RANDAO opartiskt är att efter att alla nummer har avslöjats och XOR har beräknats, mata in resultatet i en funktion som tar mycket lång tid att beräkna men möjliggör snabb verifiering av beräkningen.

(vdf_output, vdf_proof) = VDF_compute(input) // detta är mycket långsamt
correct = VDF_verify(input, vdf_output, vdf_proof) // detta är mycket snabbt

Denna funktion kallas Verifiable Delay Function, eller VDF. Om beräkningen av det slutliga resultatet tar längre tid än avslöjande av siffrorna, kan en angripare inte förutsäga effekten av att visa eller dölja sin siffra, och därmed förlorar hen möjligheten att påverka resultatet.

Att utveckla bra VDF:er är extremt svårt. På senare tid har det gjorts flera genombrott, till exempel det här och detta, vilka har gjort VDF:er mer praktiskt tillämpbara, och Ethereum 2.0 planerar på lång sikt att använda RANDAO med VDF som källa för slumpmässiga siffror. Förutom att denna metod är oförutsägbar och objektiv, har den den extra fördelen att den är livskraftig, om minst två deltagare är tillgängliga i nätverket (förutsatt att den använda konsensusprotokollet är livskraftigt vid arbete med så få deltagare).

Den största svårigheten med denna metod ligger i att ställa in VDF så att inte ens en deltagare med mycket dyr specialiserad utrustning kan beräkna VDF innan avslöjandefasen är över. I idealfallet bör algoritmen ha en betydande säkerhetsmarginal, låt oss säga 10x. I bilden nedan visas en attack från en deltagare med specialiserad ASIC som möjliggör snabbare körning av VDF än den tid som avsatts för att avslöja bekräftelsen av RANDAO. En sådan deltagare kan fortfarande beräkna det slutliga resultatet med och utan sin siffra, och baserat på beräkningarna välja att visa den eller inte.

För den ovan nämnda familjen av VDF:er kan prestandan hos specialiserad ASIC vara över 100 gånger högre än hos vanlig utrustning. Om avslöjandefasen varar i 10 sekunder, bör VDF:n beräknad på en sådan ASIC ta mer än 100 sekunder för att ha en säkerhetsmarginal på 10 gånger, och därmed bör samma VDF beräknad på vanlig utrustning ta 100 x 100 sekunder = ~ 3 timmar.

Ethereum Foundation planerar att lösa detta problem genom att skapa sina egna offentliga gratis ASICs. Så snart detta är klart, kan alla andra protokoll också dra nytta av denna teknik, men fram till dess kommer RANDAO + VDF-ansatsen inte att vara lika livskraftig för protokoll som inte kan investera i utvecklingen av sina egna ASICs.

Många artiklar, videor och annan information om VDF har samlats på denna webbplats.

Använder utplåningskoder

I det här avsnittet kommer vi att granska protokollet för generering av slumpmässiga nummer, som använder utplåningskoder. Det kan tåla upp till ⅓ skadliga aktörer och tolererar existensen av upp till ⅔ skadliga aktörer innan de kan förutsäga eller påverka resultatet.

Den grundläggande idén med protokollet är följande. För enkelhetens skull låt oss anta att det finns exakt 100 deltagare. Låt oss också anta att alla deltagare lokalt har en viss privat nyckel och att de offentliga nycklarna för alla deltagare är kända av alla deltagare:

1. Varje deltagare lokaliserar en lång sträng, delar upp den i 67 delar, skapar utplåningskoder för att få 100 andelar, sådana att vilka som helst 67 är tillräckliga för att återställa strängen, tilldelar varje av de 100 andelarna till en av deltagarna och krypterar dem med hjälp av den samme deltagarens offentliga nyckel. Därefter publiceras alla krypterade andelar.

2. Deltagarna använder en form av konsensus för att nå enighet om de kodade uppsättningarna från specifika 67 deltagare.

3. Så snart konsensus har nåtts, tar varje deltagare de kodade andelarna i varje av de 67 uppsättningarna, krypterade med deras offentliga nyckel, dekrypterar alla sådana andelar och publicerar alla sådana dekrypterade andelar.

4. När 67 deltagare har genomfört steg (3) kan alla överenskomna uppsättningar fullständigt dekrypteras och återställas på grund av egenskaperna hos utplåningskoder, och det slutliga numret kan erhållas som XOR av de ursprungliga strängarna som deltagarna började med i (1).

Det kan visas att denna protokoll är opartisk och oförutsägbar. Det resulterande slumptalet definieras efter att konsensus har nåtts, men ingen vet det förrän ⅔ av deltagarna dekrypterar de delar som är krypterade med deras offentliga nyckel. På så sätt definieras slumptalet tidigare än informationen som krävs för att återskapa det publiceras.

Vad händer om ett av deltagarna vid steg (1) skickade kodade andelar som inte är en korrekt suddande kod för en viss sträng till de andra deltagarna? Utan ytterligare förändringar kan olika deltagare antingen inte alls återskapa strängen, eller så återskapar de olika strängar, vilket leder till att olika deltagare får olika slumptal. För att förhindra detta kan följande göras: varje deltagare, utöver de kodade andelarna, beräknar också Merkletree alla sådana andelar, och skickar både den kodade andelen och roten av Merkletreet till varje deltagare, samt beviset på inkluderingen av andelen i Merkletreet. Vid konsensus i steg (2) kommer deltagarna då inte bara att enas om en mängd uppsättningar, utan om en mängd specifika rötter för sådana träd (om viss deltagare avviker från protokollet och skickar olika rötter av Merkletreet till olika deltagare, och två sådana rötter visas under konsensus, inkluderas inte hans sträng i den resulterande uppsättningen). I slutet av konsensus kommer vi ha 67 kodade strängar och motsvarande rötter av Merkletreet, sådana att det finns minst 67 deltagare (inte nödvändigtvis samma som de som föreslog motsvarande strängar), för vilka varje av de 67 strängarna har ett meddelande med en andel av suddande kod och bevis på att deras andel ingår i det motsvarande Merkletreet.

När en deltagare i steg (4) dekrypterar 67 andelar för en viss sträng och försöker återskapa den ursprungliga strängen, är en av alternativen möjliga:

1. Strängen återskapas, och om den då kodas med suddande koder igen, och Merkletreet beräknas för de lokalt beräknade andelarna, så stämmer roten överens med den som konsensus har nått.

2. Strängen återskapas, men den lokalt beräknade roten motsvarar inte den som konsensus har nått.

3. Strängen kan inte återskapas.

Det är lätt att visa att om minst en deltagare upplever alternativ (1), så kommer alla deltagare att uppleva alternativ (1), och omvänt, om minst en deltagare upplever alternativ (2) eller (3), då kommer alla deltagare att uppleva alternativ (2) eller (3). På så sätt, för varje rad i datasetet antingen kommer alla deltagare att återställa den framgångsrikt, eller så kommer alla deltagare att misslyckas med att återställa den. Den resulterande slumpmässiga siffran är då XOR av endast de rader som deltagarna kunde återställa.

Tröskelattester

Ett annat tillvägagångssätt för slumpmässighet involverar användningen av så kallade BLS-tröskelattester. En slumpgenerator baserad på tröskelattester har exakt samma garantier som den ovan beskrivna algoritmen baserad på utplåningskoder, men har en betydligt lägre asymptotik för antalet meddelanden som skickas över nätverket för varje genererat tal.

BLS-signaturer är en konstruktion som tillåter flera deltagare att skapa en gemensam signatur för ett meddelande. Dessa signaturer används ofta för att spara utrymme och bandbredd, eftersom de inte kräver att flera signaturer distribueras. 

En vanlig tillämpning av BLS-signaturer i blockchain-protokoll, förutom generering av slumpmässiga nummer, är signering av block i BFT-protokoll. Låt säga att 100 deltagare skapar block och blocket anses vara slutgiltigt om 67 av dem signerar det. Alla kan presentera sina delar av BLS-signaturen och använda en viss konsensusalgoritm för att enas om 67 av dem, och sedan kombinera dessa till en enda BLS-signatur. Vilka 67 (eller fler) delar som används kan skapa den slutliga signaturen, vilket innebär att den kan variera, men trots att olika val av 67 deltagare kommer att skapa olika signaturer, kommer vilken som helst av dessa signaturer att vara en giltig signatur för blocket. Övriga deltagare behöver sedan bara få och verifiera en signatur per block över nätverket, istället för 67, vilket märkbart minskar belastningen på nätverket.

Det visar sig att om de privata nycklar som används av deltagarna genereras på ett visst sätt, så kommer den resulterande signaturen att vara densamma oavsett vilka 67 signaturer (eller fler, men inte färre) som aggregeras. Detta kan användas som en källa till slumpmässighet: deltagarna kommer först överens om ett meddelande som de ska signera (det kan vara resultatet av RANDAO eller helt enkelt hash av den senaste blocket, det spelar faktiskt ingen roll så länge det ändras varje gång och är överenskommet), och skapar en BLS-signatur för det. Resultatet av genereringen kommer att vara oförutsägbart tills 67 deltagare lämnar sina delar, och efter det kommer resultaten att vara förbestämda och kan inte bero på någon deltagares handlingar.

Denna metod för slumpmässighet är livskraftig om åtminstone ⅔ av deltagarna är online och följer protokollet, och den är opartisk och oförutsägbar så länge minst ⅓ av deltagarna följer protokollet. Det är viktigt att notera att en angripare som kontrollerar mer än ⅓ men mindre än ⅔ av deltagarna kan stoppa protokollet, men inte kan förutsäga eller påverka dess utfall.

Tröskelsignaturer i sig är ett mycket intressant ämne. I den andra delen av artikeln kommer vi att utforska hur de fungerar, och hur deltagarnas nycklar ska genereras för att tröskelsignaturer ska kunna användas som en generator av slumpmässiga nummer.

Avslutningsvis

Denna artikel är den första i en serie tekniska artiklar i bloggen NEAR. NEAR är ett blockchain-protokoll och en plattform för att utveckla decentraliserade applikationer med fokus på enkel utveckling och användarvänlighet för slutanvändarna.

Protokollets kod är öppen, vår implementation är skriven i Rust, och kan hittas ). Ett typiskt exempel på användning:.

Du kan se hur utvecklingen under NEAR ser ut och experimentera i en online-IDE här.

Håll koll på alla nyheter på ryska i gruppen på Telegram och i gruppen på VKontakte, och på engelska i den officiella Twitter.

Vi ses snart!

Källa: habr.com