Inledning
"Slumpmässig nummergenerering är för viktig för att lämnas åt slumpen."
Robert Cavue, 1970
Den här artikeln ägnas åt den praktiska tillämpningen av lösningar som använder kollektiv generering av slumptal i en opålitlig miljö. Kort sagt, hur och varför slumpmässigt används i blockkedjor, och lite om hur man skiljer "bra" slumpmässigt från "dåligt". Att generera ett verkligt slumptal är ett extremt svårt problem, även på en enda dator, och har länge studerats av kryptografer. Tja, i decentraliserade nätverk är genereringen av slumptal ännu mer komplex och viktig.
Det är i nätverk där deltagarna inte litar på varandra som förmågan att generera ett obestridligt slumptal tillåter oss att effektivt lösa många kritiska problem och avsevärt förbättra befintliga system. Dessutom är spel och lotterier inte det främsta målet här, som det först kan tyckas för den oerfarna läsaren.
Generering av slumptal
Datorer kan inte generera slumptal själva, de behöver hjälp utifrån för att göra det. Datorn kan få ett slumpmässigt värde från till exempel musrörelser, mängden minne som används, ströströmmar på processorstiften och många andra källor som kallas entropikällor. Dessa värden i sig är inte helt slumpmässiga, eftersom de ligger inom ett visst intervall eller har ett förutsägbart mönster av förändringar. För att förvandla sådana tal till ett verkligt slumpmässigt tal inom ett givet intervall, tillämpas kryptotransformationer på dem för att producera enhetligt fördelade pseudoslumpvärden från de ojämnt fördelade värdena från entropikällan. De resulterande värdena kallas pseudoslumpmässiga eftersom de inte är riktigt slumpmässiga, utan är deterministiskt härledda från entropi. Vilken bra kryptografisk algoritm som helst, vid kryptering av data, producerar chiffertexter som borde vara statistiskt omöjliga att skilja från en slumpmässig sekvens, så för att producera slumpmässighet kan du ta en källa till entropi, som endast ger god repeterbarhet och oförutsägbarhet av värden även i små intervall, resten av arbetet är att sprida och blanda bitar i Det resulterande värdet kommer att tas över av krypteringsalgoritmen.
För att slutföra ett kort utbildningsprogram, ska jag tillägga att generering av slumptal även på en enhet är en av pelarna för att säkerställa säkerheten för våra data. De genererade pseudoslumptalen används när man upprättar säkra anslutningar i olika nätverk, för att generera kryptografiska nycklar, för lastbalansering, integritetsövervakning och för många fler applikationer. Säkerheten för många protokoll beror på förmågan att generera en tillförlitlig, externt oförutsägbar slump, lagra den och inte avslöja den förrän nästa steg i protokollet, annars kommer säkerheten att äventyras. En attack på en pseudoslumpvärdegenerator är extremt farlig och hotar omedelbart all programvara som använder slumpgenerering.
Du bör veta allt detta om du gått en grundkurs i kryptografi, så låt oss fortsätta om decentraliserade nätverk.
Slumpmässigt i blockkedjor
Först och främst kommer jag att prata om blockkedjor med stöd för smarta kontrakt; det är de som fullt ut kan dra nytta av de möjligheter som högkvalitativ, obestridlig slumpmässighet ger. Vidare, för korthets skull, kommer jag att kalla denna teknik "Offentligt verifierbara slumpmässiga beacons” eller PVRB. Eftersom blockkedjor är nätverk där information kan verifieras av vilken deltagare som helst, är nyckeldelen av namnet "Publicly Verifiable", dvs. Vem som helst kan använda beräkningar för att få bevis på att det resulterande numret som publiceras på blockkedjan har följande egenskaper:
- Resultatet måste ha en bevisligen enhetlig fördelning, det vill säga vara baserat på bevisligen stark kryptografi.
- Det är inte möjligt att kontrollera någon av bitarna i resultatet. Resultatet kan därför inte förutsägas i förväg.
- Du kan inte sabotera genereringsprotokollet genom att inte delta i protokollet eller genom att överbelasta nätverket med attackmeddelanden
- Allt ovanstående måste vara motståndskraftigt mot maskopi av ett tillåtet antal oärliga protokolldeltagare (till exempel 1/3 av deltagarna).
Varje möjlighet för en samverkande mindre grupp av deltagare att producera även en kontrollerad jämn/udda slump är ett säkerhetshål. Varje förmåga hos gruppen att stoppa utfärdandet av slumpmässigt är ett säkerhetshål. I allmänhet finns det många problem, och denna uppgift är inte lätt...
Det verkar som om den viktigaste applikationen för PVRB är olika spel, lotterier och i allmänhet alla typer av spel på blockchain. Detta är faktiskt en viktig riktning, men slumpmässighet i blockkedjor har ännu viktigare tillämpningar. Låt oss titta på dem.
Konsensusalgoritmer
PVRB spelar en stor roll för att organisera nätverkskonsensus. Transaktioner i blockkedjor skyddas av en elektronisk signatur, så en "attack på en transaktion" är alltid inkludering/uteslutning av en transaktion i ett block (eller flera block). Och huvuduppgiften för konsensusalgoritmen är att komma överens om ordningen för dessa transaktioner och ordningen på blocken som inkluderar dessa transaktioner. En nödvändig egenskap för riktiga blockkedjor är också finalitet - nätverkets förmåga att komma överens om att kedjan fram till det slutgiltiga blocket är slutgiltig och kommer aldrig att uteslutas på grund av utseendet på en ny gaffel. Vanligtvis, för att komma överens om att ett block är giltigt och, viktigast av allt, slutgiltigt, är det nödvändigt att samla in signaturer från majoriteten av blockproducenterna (nedan kallade BP - blockproducenter), vilket åtminstone kräver att blockkedjan levereras till alla BP och distribuera signaturer mellan alla BP . När antalet BP växer, växer antalet nödvändiga meddelanden i nätverket exponentiellt, därför fungerar konsensusalgoritmer som kräver finalitet, som används till exempel i Hyperledger pBFT-konsensus, inte med den hastighet som krävs, med början från flera dussin BP:er, vilket kräver ett stort antal förbindelser.
Om det finns en obestridlig och ärlig PVRB i nätverket, kan man, även i den enklaste approximationen, välja en av blockproducenterna baserat på det och utse honom som "ledare" under en omgång av protokollet. Om vi har N blockproducenter, varav M: M > 1/2 N är ärliga, censurera inte transaktioner och splittra inte kedjan för att utföra en "dubbel spendera"-attack, då kommer användningen av en enhetligt fördelad oemotsagd PVRB att göra det möjligt att välja en ärlig ledare med sannolikhet M / N (M / N > 1/2). Om varje ledare tilldelas sitt eget tidsintervall under vilket han kan producera ett block och validera kedjan, och dessa intervall är lika i tid, kommer blockkedjan av ärliga BP:er att vara längre än kedjan som bildas av skadliga BP:er, och konsensus algoritmen förlitar sig på kedjans längd. kommer helt enkelt att kassera den "dåliga". Denna princip att tilldela lika delar av tiden till varje BP tillämpades först i Graphene (föregångaren till EOS), och gör att de flesta block kan stängas med en enda signatur, vilket avsevärt minskar nätverksbelastningen och gör att denna konsensus fungerar extremt snabbt och stadigt. Emellertid måste EOS-nätverket nu använda speciella block (Last Irreversible Block), som bekräftas av signaturerna från 2/3 BP. Dessa block tjänar till att säkerställa finalitet (omöjligheten av en kedjegaffel som börjar före det sista sista oåterkalleliga blocket).
I verkliga implementeringar är protokollschemat också mer komplicerat - röstning för föreslagna block utförs i flera steg för att underhålla nätverket i händelse av saknade block och problem med nätverket, men även med hänsyn till detta kräver konsensusalgoritmer som använder PVRB betydligt färre meddelanden mellan BP:er, vilket gör det möjligt att göra dem snabbare än traditionell PVFT, eller dess olika modifieringar.
Den mest framträdande representanten för sådana algoritmer: från Cardano-teamet, vilket sägs vara matematiskt bevisbart mot BP-samverkan.
I Ouroboros används PVRB för att definiera det så kallade "BP-schemat" - ett schema enligt vilket varje BP tilldelas sin egen tidslucka för publicering av ett block. Den stora fördelen med att använda PVRB är den fullständiga "jämlikheten" mellan BP:er (enligt storleken på deras balansräkningar). PVRB:s integritet säkerställer att skadliga BP:er inte kan kontrollera schemaläggningen av tidsluckor och därför inte kan manipulera kedjan genom att förbereda och analysera kedjans gafflar i förväg, och för att välja en gaffel räcker det att helt enkelt lita på längden på kedja, utan att använda knepiga sätt att beräkna "nyttan" för BP och "vikten" av dess block.
I allmänhet, i alla fall där en slumpmässig deltagare behöver väljas i ett decentraliserat nätverk, är PVRB nästan alltid det bästa valet, snarare än ett deterministiskt alternativ baserat på till exempel en blockhash. Utan PVRB leder förmågan att påverka en deltagares val till attacker där angriparen kan välja från flera framtider för att välja nästa korrupta deltagare eller flera samtidigt för att säkerställa en större andel i beslutet. Användningen av PVRB misskrediterar dessa typer av attacker.
Skalning och lastbalansering
PVRB kan också vara till stor nytta i uppgifter som belastningsminskning och betalningsskalning. Till att börja med är det vettigt att bekanta sig med Rivesta "Elektroniska lotter som mikrobetalningar". Den allmänna idén är att istället för att göra 100 1c-betalningar från betalaren till mottagaren kan du spela ett ärligt lotteri med ett pris på 1$ = 100c, där betalaren ger banken en av 1 av sina "lotterikuponger" för varje 100c betalning. En av dessa biljetter vinner en burk på $1, och det är denna biljett som mottagaren kan spela in i blockkedjan. Det viktigaste är att de återstående 99 biljetterna överförs mellan mottagaren och betalaren utan något externt deltagande, via en privat kanal och med valfri hastighet. En bra beskrivning av protokollet baserat på detta schema på Emercoin-nätverket kan läsas .
Detta system har några problem, som att mottagaren kan sluta betjäna betalaren omedelbart efter att ha mottagit en vinnande lott, men för många speciella applikationer, såsom fakturering per minut eller elektroniska prenumerationer på tjänster, kan dessa försummas. Huvudkravet är naturligtvis lotteriets rättvisa, och för dess genomförande är en PVRB absolut nödvändig.
Valet av en slumpmässig deltagare är också extremt viktigt för splittringsprotokoll, vars syfte är att horisontellt skala blockkedjan, vilket gör det möjligt för olika BP:er att endast behandla deras omfattning av transaktioner. Detta är en extremt svår uppgift, särskilt när det gäller säkerheten vid sammanslagning av skärvor. Rättvist val av en slumpmässig BP i syfte att tilldela de ansvariga för en specifik skärva, som i konsensusalgoritmer, är också PVRB:s uppgift. I centraliserade system tilldelas skärvor av en balanserare; den beräknar helt enkelt hashen från begäran och skickar den till den nödvändiga exekutorn. I blockkedjor kan möjligheten att påverka detta uppdrag leda till en attack mot konsensus. Till exempel kan innehållet i transaktioner kontrolleras av en angripare, han kan kontrollera vilka transaktioner som går till skärvan han kontrollerar och manipulera kedjan av block i den. Du kan läsa en diskussion om problemet med att använda slumpmässiga siffror för sönderdelningsuppgifter i Ethereum
Sharding är ett av de mest ambitiösa och allvarliga problemen inom blockchain-området; dess lösning kommer att tillåta att bygga decentraliserade nätverk med fantastisk prestanda och volym. PVRB är bara ett av de viktiga blocken för att lösa det.
Spel, ekonomiska protokoll, skiljeförfarande
Slumptalens roll i spelbranschen är svår att överskatta. Explicit användning i onlinekasinon och implicit användning när man beräknar effekterna av en spelares agerande är alla extremt svåra problem för decentraliserade nätverk, där det inte finns något sätt att förlita sig på en central källa till slumpmässighet. Men slumpmässigt urval kan också lösa många ekonomiska problem och hjälpa till att bygga enklare och effektivare protokoll. Anta att det i vårt protokoll finns tvister om betalning för vissa billiga tjänster, och dessa tvister förekommer ganska sällan. I det här fallet, om det finns en obestridd PVRB, kan kunder och säljare komma överens om att lösa tvister slumpmässigt, men med en given sannolikhet. Till exempel, med 60 % sannolikhet att kunden vinner, och med 40 % sannolikhet att säljaren vinner. Detta tillvägagångssätt, som är absurt ur den första synvinkeln, gör att du automatiskt kan lösa tvister med en exakt förutsägbar andel vinster/förluster, vilket passar båda parter utan deltagande av en tredje part och onödigt slöseri med tid. Dessutom kan sannolikhetskvoten vara dynamisk och bero på vissa globala variabler. Till exempel, om ett företag går bra, har ett lågt antal tvister och hög lönsamhet, kan företaget automatiskt flytta sannolikheten för att lösa en tvist mot kundcentrerad, till exempel 70/30 eller 80/20, och vice versa, om tvister tar mycket pengar och är bedrägliga eller otillräckliga kan du flytta sannolikheten åt andra hållet.
Ett stort antal intressanta decentraliserade protokoll, såsom tokenkurerade register, prediktionsmarknader, bindningskurvor och många andra, är ekonomiska spel där gott beteende belönas och dåligt beteende bestraffas. De innehåller ofta säkerhetsproblem där skydden står i konflikt med varandra. Det som är skyddat från en attack av "valar" med miljarder tokens ("stor insats") är sårbart för attacker från tusentals konton med små saldon ("sybil-insats") och åtgärder som vidtas mot en enskild attack, såsom icke- linjära avgifter som skapas för att göra det olönsamt att arbeta med en stor insats misskrediteras vanligtvis av en annan attack. Eftersom vi talar om ett ekonomiskt spel kan motsvarande statistiska vikter beräknas i förväg, och helt enkelt ersätta provisionerna med slumpmässiga sådana med lämplig fördelning. Sådana sannolikhetskommissioner implementeras extremt enkelt om blockkedjan har en pålitlig källa till slumpmässighet och inte kräver några komplexa beräkningar, vilket gör livet svårt för både valar och sybiler.
Samtidigt är det nödvändigt att fortsätta komma ihåg att kontroll över en enda bit i denna slumpmässighet låter dig fuska, minska och öka sannolikheterna med hälften, så en ärlig PVRB är den viktigaste komponenten i sådana protokoll.
Var hittar man rätt random?
I teorin gör rättvist slumpmässigt urval i decentraliserade nätverk nästan alla protokoll bevisligen säkert mot maskopi. Grunden är ganska enkel - om nätverket kommer överens om en enda 0 eller 1 bit, och mindre än hälften av deltagarna är oärliga, då, givet tillräckligt många iterationer, kommer nätverket garanterat att nå en konsensus om den biten med en fast sannolikhet. Helt enkelt för att en ärlig slump kommer att välja 51 av 100 deltagare 51% av gångerna. Men detta är i teorin, eftersom... i riktiga nätverk, för att säkerställa en sådan säkerhetsnivå som i artiklarna, krävs många meddelanden mellan värdar, komplex multi-pass kryptografi, och varje komplikation av protokollet lägger omedelbart till nya attackvektorer.
Det är därför vi ännu inte ser en bevisad resistent PVRB i blockkedjor, som skulle ha använts tillräckligt länge för att testas av riktiga applikationer, flera granskningar, belastningar och naturligtvis riktiga attacker, utan vilka det är svårt att kalla en produkt verkligen säker.
Det finns dock flera lovande tillvägagångssätt, de skiljer sig åt i många detaljer, och en av dem kommer definitivt att lösa problemet. Med moderna datorresurser kan kryptografisk teori ganska skickligt översättas till praktiska tillämpningar. I framtiden kommer vi gärna att prata om PVRB-implementeringar: det finns nu flera av dem, var och en har sin egen uppsättning viktiga egenskaper och implementeringsfunktioner, och bakom varje finns en bra idé. Det finns inte många team inblandade i randomisering, och upplevelsen av var och en av dem är oerhört viktig för alla andra. Vi hoppas att vår information kommer att tillåta andra team att röra sig snabbare, med hänsyn till erfarenheterna från deras föregångare.
Källa: will.com