Är det möjligt att generera slumptal om vi inte litar på varandra? Del 1

Hej Habr!

I den här artikeln kommer jag att prata om genereringen av pseudo-slumptal av 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 mycket bra sådan är svår.

Varför skulle det vara nödvändigt att generera slumpmässiga siffror bland deltagare som inte litar på varandra? Ett applikationsområde är decentraliserade applikationer. Till exempel, en applikation som accepterar en satsning från en deltagare och antingen dubblar beloppet med 49 % sannolikhet eller tar bort med 51 % sannolikhet kommer bara att fungera om den opartiskt kan ta emot ett slumpmässigt tal. Om en angripare kan påverka resultatet av slumptalsgeneratorn, och till och med något öka sin chans att få en utbetalning i applikationen, kommer han lätt att förstöra den.

När vi designar ett distribuerat slumptalsgenereringsprotokoll vill vi att det ska ha tre egenskaper:

1. Han måste vara opartisk. Med andra ord, ingen deltagare ska på något sätt påverka resultatet av slumptalsgeneratorn.

2. Han måste vara oförutsägbar. Med andra ord bör ingen deltagare kunna förutsäga vilket nummer som kommer att genereras (eller härleda någon av dess egenskaper) innan det genereras.

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

I den här artikeln kommer vi att titta på två tillvägagångssätt: RANDAO + VDF och raderingskoderna. I nästa del kommer vi att i detalj undersöka tillvägagångssättet baserat på tröskelsignaturer.

Men först, låt oss titta på en enkel och vanligt förekommande algoritm som är livskraftig, oförutsägbar, men partisk.

RANDAO

RANDAO är ett mycket enkelt och därför ganska vanligt tillvägagångssätt för att generera slumpmässighet. Alla nätverksdeltagare väljer först lokalt ett pseudoslumpmässigt nummer, sedan skickar varje deltagare en hash av det valda numret. Därefter turas deltagarna om att avslöja sina valda nummer och utföra en XOR-operation på de avslöjade siffrorna, och resultatet av denna operation blir resultatet av protokollet.

Steget att publicera hasharna innan siffrorna avslöjas är nödvändigt så att angriparen inte kan välja sitt nummer efter att han har sett de andra deltagarnas nummer. Detta skulle tillåta honom att praktiskt taget på egen hand bestämma utsignalen från slumptalsgeneratorn.

Under protokollets gång måste deltagarna komma till ett gemensamt beslut (så kallat konsensus) två gånger: när de ska börja avslöja de valda siffrorna, och därför sluta acceptera hash, och när de ska sluta acceptera de valda siffrorna och beräkna den resulterande slumpen siffra. Att fatta sådana beslut mellan deltagare som inte litar på varandra är inte en lätt uppgift i sig, och vi kommer att återkomma till det i framtida artiklar; i den här artikeln kommer vi att anta att en sådan konsensusalgoritm är tillgänglig för oss.

Vilka av egenskaperna vi beskrev ovan har RANDAO? Det är oförutsägbart, har samma vitalitet som det underliggande konsensusprotokollet, men det är partiskt. Specifikt kan en angripare observera nätverket, och efter att andra deltagare avslöjar sina siffror kan han beräkna sin XOR och bestämma om han vill avslöja sitt nummer eller inte för att påverka resultatet. Även om detta hindrar angriparen från att på egen hand bestämma utdata från slumptalsgeneratorn, ger det honom fortfarande 1 bit av inflytande. Och om angripare kontrollerar flera deltagare, kommer antalet bitar de kontrollerar att vara lika med antalet deltagare under deras kontroll.

Angriparnas inflytande kan reduceras kraftigt genom att kräva att deltagarna avslöjar siffrorna i ordning. Då kommer angriparen att kunna påverka utgången endast om den öppnas sist. Även om inflytandet är betydligt mindre, är algoritmen fortfarande partisk.

RANDAO+VDF

Ett sätt att göra RANDAO opartisk är detta: efter att alla siffror har avslöjats och XOR har beräknats, matas dess resultat in i inmatningen av en funktion, vilket tar mycket lång tid att beräkna, men låter dig kontrollera riktigheten av beräkning mycket snabbt.

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

Denna funktion kallas Verifiable Delay Function, eller VDF. Om beräkningen av det slutliga resultatet tar längre tid än antalet avslöjande steg, kommer angriparen inte att kunna förutsäga effekten av att visa eller dölja sitt nummer, och därför kommer han att förlora möjligheten att påverka resultatet.

Att utveckla bra VDF:er är extremt svårt. Det har skett flera genombrott den senaste tiden, t.ex. detta и detta, vilket gjorde VDF mer praktiskt i praktiken, och Ethereum 2.0 planerar att använda RANDAO med VDF som en slumptalskälla på lång sikt. Bortsett från det faktum att detta tillvägagångssätt är oförutsägbart och opartiskt, har det den extra fördelen att det är lönsamt om minst två deltagare är tillgängliga på nätverket (förutsatt att konsensusprotokollet som används är genomförbart när man har att göra med ett så litet antal deltagare).

Den största utmaningen med detta tillvägagångssätt är att ställa in VDF så att inte ens en deltagare med mycket dyr specialiserad hårdvara kommer att kunna beräkna VDF före slutet av upptäcktsfasen. Helst borde algoritmen till och med ha en betydande säkerhetsmarginal, säg 10x. Bilden nedan visar en attack av en skådespelare som har en specialiserad ASIC som gör att han kan köra en VDF snabbare än den tid som tilldelats för att avslöja RANDAO-bekräftelsen. En sådan deltagare kan fortfarande beräkna slutresultatet med eller inte använda sitt nummer, och sedan, baserat på beräkningen, välja om den ska visa det eller inte.

För VDF-familjen som nämns ovan kan prestandan hos en dedikerad ASIC vara 100+ gånger högre än konventionell hårdvara. Så om distributionsfasen varar i 10 sekunder, måste VDF som beräknas på en sådan ASIC ta mer än 100 sekunder för att ha en 10x säkerhetsmarginal, och därför måste samma VDF som beräknas på råvaruhårdvara ta 100x 100 sekunder = ~3 timmar.

Ethereum Foundation planerar att lösa detta problem genom att skapa sina egna offentligt tillgängliga, gratis ASIC:er. När detta väl händer kan alla andra protokoll också dra nytta av denna teknik, men tills dess kommer RANDAO+VDF-metoden inte att vara lika lönsam för protokoll som inte kan investera i att utveckla sina egna ASIC:er.

Många artiklar, filmer och annan information om VDF har samlats på den här webbplatsen.

Vi använder raderingskoder

I det här avsnittet kommer vi att titta på ett slumptalsgenereringsprotokoll som använder radera koder. Den kan tolerera upp till ⅓ angripare samtidigt som den förblir livskraftig, och tillåter upp till ⅔ angripare att existera innan de kan förutsäga eller påverka resultatet.

Huvudtanken med protokollet är följande. För enkelhetens skull, låt oss anta att det är exakt 100 deltagare. Låt oss också anta att alla deltagare lokalt har någon privat nyckel, och alla deltagares publika nycklar är kända för alla deltagare:

1. Varje deltagare kommer lokalt med en lång sträng, delar upp den i 67 delar, skapar raderingskoder för att få 100 delningar så att alla 67 räcker för att återställa strängen, tilldelar var och en av de 100 delningarna till en av deltagarna och krypterar dem med samma deltagares publika nyckel. Alla kodade andelar publiceras sedan.

2. Deltagarna använder någon form av konsensus för att komma överens om kodade set från specifika 67 deltagare.

3. När konsensus uppnåtts tar varje deltagare de kodade andelarna i var och en av de 67 uppsättningarna krypterade med deras publika nyckel, dekrypterar alla sådana andelar och publicerar alla sådana dekrypterade andelar.

4. När 67 deltagare har slutfört steg (3) kan alla överenskomna set avkodas och rekonstrueras helt på grund av egenskaperna hos raderingskoder, och det slutliga numret kan erhållas som en XOR av de initiala raderna som deltagarna började med i (1) .

Detta protokoll kan visa sig vara opartiskt och oförutsägbart. Det resulterande slumptalet bestäms efter att konsensus uppnåtts, men är inte känt för någon förrän ⅔ av deltagarna avkodar delarna krypterade med deras publika nyckel. Således bestäms slumptalet innan information som är tillräcklig för att rekonstruera det publiceras.

Vad händer om en av deltagarna i steg (1) skickade kodade delningar till de andra deltagarna som inte är den korrekta raderingskoden för någon sträng? Utan ytterligare ändringar kommer olika deltagare antingen inte att kunna återställa strängen alls, eller så kommer de att återställa olika strängar, vilket kommer att resultera i att olika deltagare får ett annat slumptal. För att förhindra detta kan du göra följande: varje deltagare, förutom de kodade andelarna, även beräknar Merkla träd alla sådana andelar och skickar till varje deltagare både den kodade andelen själv och roten av merkleträdet, och bevis på inkluderingen av andelen i merkleträdet. I konsensus i steg (2) kommer deltagarna inte bara överens om en uppsättning uppsättningar, utan om en uppsättning specifika rötter för sådana träd (om någon deltagare avvek från protokollet och skickade olika merkle-trädrötter till olika deltagare, och två sådana rötter visas under konsensus, hans rad ingår inte i resultatuppsättningen). Som ett resultat av konsensus kommer vi att ha 67 kodade rader och motsvarande rötter av merkleträdet så att det finns minst 67 deltagare (inte nödvändigtvis samma som föreslog motsvarande rader), som för var och en av de 67 raderna har ett meddelande med en andel av raderingskoden och ett bevis på att deras andel i motsvarande träd har bleknat.

När deltagaren i steg (4) dechiffrerar 67 slag för en viss sträng och försöker rekonstruera den ursprungliga strängen från dem, är ett av alternativen möjligt:

1. Strängen återställs, och om den sedan raderas igen, och Merkle-trädet beräknas för de lokalt beräknade andelarna, sammanfaller roten med den som konsensus nåddes om.

2. Raden återställs, men den lokalt beräknade roten matchar inte den där konsensus nåddes.

3. Raden är inte återställd.

Det är lätt att visa att om alternativ (1) hände för minst en deltagare ovan, så hände alternativ (1) för alla deltagare, och vice versa, om alternativ (2) eller (3) hände för minst en deltagare, då för alla deltagare kommer alternativ (2) eller (3) att ske. För varje rad i uppsättningen kommer alltså antingen alla deltagare att återställa den, eller så kommer alla deltagare inte att återställa den. Det resulterande slumptalet är då en XOR av endast de rader som deltagarna kunde återställa.

Tröskelsignaturer

Ett annat tillvägagångssätt för slumpmässighet är att använda vad som kallas BLS-tröskelsignaturer. En slumptalsgenerator baserad på tröskelsignaturer har exakt samma garantier som den raderingskodbaserade algoritmen som beskrivs ovan, men har ett betydligt lägre asymptotiskt antal meddelanden som skickas över nätverket för varje genererat nummer.

BLS-signaturer är en design som gör att flera deltagare kan skapa en gemensam signatur för ett meddelande. Dessa signaturer används ofta för att spara utrymme och bandbredd genom att inte kräva att flera signaturer skickas ut. 

En vanlig applikation för BLS-signaturer i blockchain-protokoll, förutom att generera slumptal, är blocksignering i BFT-protokoll. Låt oss säga att 100 deltagare skapar block och ett block anses vara slutgiltigt om 67 av dem undertecknar det. De kan alla skicka in sina delar av BLS-signaturen och använda någon konsensusalgoritm för att komma överens om 67 av dem och sedan slå samman dem till en BLS-signatur. Vilka 67 (eller fler) delar som helst kan användas för att skapa den slutliga signaturen, vilket beror på vilka 67 signaturer som kombinerades och därför kan variera, även om olika val av de 67 deltagarna kommer att skapa en annan signatur, en sådan signatur kommer att vara en giltig signatur för blocket. De återstående deltagarna behöver då bara ta emot och verifiera endast en signatur per block, istället för 67, över nätverket, vilket avsevärt minskar belastningen på nätverket.

Det visar sig att om de privata nycklar som deltagarna använder genereras på ett visst sätt, oavsett vilka 67 signaturer (eller fler, men inte färre) som aggregeras, blir den resulterande signaturen densamma. Detta kan användas som en källa till slumpmässighet: deltagarna kommer först överens om ett meddelande som de kommer att underteckna (detta kan vara utdata från RANDAO eller bara hashen från det sista blocket, det spelar ingen roll så länge det ändras varje gång och är konsekvent) och skapa en BLS-signatur för den. Resultatet av genereringen kommer att vara oförutsägbart tills 67 deltagare tillhandahåller sina delar, och efter det är resultatet redan förutbestämt och kan inte bero på någon deltagares handlingar.

Denna metod för slumpmässighet är genomförbar så länge som minst ⅔ av deltagarna online både följer protokollet och är opartisk och oförutsägbar så länge som 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 resultat.

Tröskelsignaturer i sig är ett mycket intressant ämne. I den andra delen av artikeln kommer vi att analysera i detalj hur de fungerar, och hur exakt det är nödvändigt att generera deltagarnycklar så att tröskelsignaturer kan användas som en slumptalsgenerator.

Sammanfattningsvis

Den här artikeln är den första i en serie tekniska bloggartiklar NEAR. NEAR är ett blockchain-protokoll och plattform för att utveckla decentraliserade applikationer med tonvikt på enkel utveckling och användarvänlighet för slutanvändare.

Protokollkoden är öppen, vår implementering är skriven i Rust, den kan hittas här.

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

Du kan följa alla nyheter på ryska på telegramgrupp och grupp på VKontakte, och på engelska i det officiella Twitter.

Ses snart!

Källa: will.com