Slumptal och decentraliserade nätverk: praktisk tillämpning

Introduktion

«Att generera slumpmässiga tal är för viktigt för att överslåtit åt slumpen»
Robert Kavyu, 1970

Denna artikel handlar om praktisk tillämpning av lösningar som använder kollektiv generering av slumpmässiga tal i en osäker miljö. För att sammanfatta – hur och varför används slumpmässighet i blockkedjor, och lite om hur man kan särskilja ”bra” slumpmässighet från ”dålig”. Att generera verkligt slumpmässiga tal är en oerhört komplex problematik, även på enskilda datorer, och har länge studerats av kryptografer. I decentraliserade nätverk är genereringen av slumpmässiga tal ännu mer komplicerad och viktig.

I nätverk där deltagarna inte litar på varandra, möjliggör förmågan att generera ett oförnekligt slumpmässigt tal effektivt lösande av många viktiga uppgifter och avsevärt förbättra redan existerande system. Det är värt att notera att spel och lotterier inte är det främsta syftet här, vilket kanske först kan verka vara fallet för den ovana läsaren.

Generering av slumpmässiga tal

Datorer kan inte själva producera slumpmässiga tal, de behöver hjälp utifrån för detta. En dator kan få ett visst slumpmässigt värde genom att till exempel använda musrörelser, mängden använd minne, parasitära strömmar på processorens kontakter och många andra källor, kallade entropikällor. Dessa värden är inte helt slumpmässiga, då de ligger inom ett visst intervall eller har ett förutsägbart förändringsmönster. För att omvandla sådana tal till verkligen slumpmässiga tal inom ett givet intervall tillämpar man kryptografiska transformationer för att få jämnt fördelade pseudorandomvärden från oregelbundet fördelade värden från entropikällorna. De erhållna värdena kallas pseudorandom, eftersom de inte är sanna slumpmässiga utan deterministiskt producerade från entropi. Varje bra kryptovaloritm, när den krypterar data, producerar chiffertext som statistiskt bör vara ob distinguishable från en slumpmässig sekvens, så att man kan använda en entropikälla som säkerställer god unikhet och oförutsägbarhet även inom små intervall; resten av arbetet med att sprida och blanda bitarna i det resulterande värdet kommer krypteringsalgoritmen att ta hand om.

För att avsluta den korta genomgången, vill jag tillägga att generering av slumpmässiga tal även på en enda enhet är en av grundpelarna för säkerheten av våra data. De genererade pseudorandomtal används vid upprättande av säkra anslutningar i olika nätverk, för att generera kryptografiska nycklar, för lastbalansering, integritetskontroll och för många andra tillämpningar. Många protokollens säkerhet beror på förmågan att generera pålitlig, oförutsägbar slumpmässighet utifrån, att bevara den och inte avslöja den förrän nästa steg i protokollet, annars hotas säkerheten. En attack mot generatorn av pseudorandomvärden är extremt farlig och hotar all mjukvara som använder slumpgenerering.

Detta är något ni bör veta om ni har genomgått en grundkurs i kryptografi, så vi fortsätter med decentraliserade nätverk.

Slumpar i blockkedjor

Först kommer jag att tala om blockkedjor som stöder smarta kontrakt, eftersom de verkligen kan utnyttja de möjligheter som erbjuds av högkvalitativ och oförneklig slump. Från och med nu kommer jag för korthetens skull att kalla denna teknik "Offentligt verifierbara slumpmässiga ljus" eller PVRB. Eftersom blockkedjor är nätverk där varje deltagare kan verifiera information, är en nyckelkomponent i namnet "Offentligt verifierbar", det vill säga att vem som helst kan genom beräkningar få ett bevis på att det erhållna numret, som lagts upp i blockkedjan, har följande egenskaper:

• Resultatet måste ha ett bevisligen jämnt fördelat resultat, dvs baserat på bevisligen säker kryptografi.
• Ingen bit av resultatet kan kontrolleras. Som en följd kan resultatet inte förutsägas i förväg.
• Protokollet för generation får inte saboteras genom att inte delta i protokollet eller genom att överbelasta nätverket med attackerande meddelanden.
• Allt ovanstående måste vara motståndskraftigt mot sammansvärjningar av ett tillåtet antal oärliga deltagare i protokollet (t.ex. 1/3 av deltagarna).

Möjligheten för en sammansvuren minoritet av deltagare att producera även kontrollerad jämn/ojämn slump — en säkerhetslucka. Möjligheten för en grupp att stoppa utdelningen av slumpen — en säkerhetslucka. Det finns många problem, och denna uppgift är inte lätt...

Det verkar som att den mest betydelsefulla användningen för PVRB är olika spel, lotterier och alla typer av gambling på blockkedjan. Verkligen, detta är en viktig riktning, men det finns också mer viktiga tillämpningar för slumpen i blockkedjor. Låt oss överväga dem.

Konsensusalgoritmer

PVRB för att organisera nätverkskonsensus spelar en avgörande roll. Transaktioner i blockkedjor skyddas av digitala signaturer, så en "attack på transaktionen" innebär alltid att inkludera/exkludera transaktionen i blocket (eller i flera block). Huvuduppgiften för konsensusalgoritmen är att enas om ordningen av dessa transaktioner och om ordningen av blocken som innehåller dessa transaktioner. En nödvändig egenskap för verkliga blockkedjor är finalitet – möjligheten för nätverket att enas om att kedjan fram till det finaliserade blocket är slutgiltig och aldrig kommer att exkluderas på grund av en ny fork. Vanligtvis, för att enas om att ett block är giltigt och, viktigast av allt, finalt, krävs det att samla signaturer från majoriteten av blockproducenterna (härefter BP – blockproducenter), vilket åtminstone kräver att blockkedjan levereras till alla BP och att signaturerna sprids mellan alla BP. Med ökningen av antalet BP växer antalet nödvändiga meddelanden i nätverket exponentiellt, därför fungerar konsensusalgoritmer som kräver finalitet, som till exempel pBFT-konsensuset i Hyperledger, inte med den önskade hastigheten, redan från några dussin BP, vilket kräver ett enormt antal anslutningar.

Om det finns en obestridlig och ärlig PVRB i nätverket, så kan man, även i den enklaste approximationen, utifrån detta välja en av blockproducenterna och utse denne som "ledare" under en runda av protokollet. Om vi har N blockproducenter, av vilka M: M > 1/2 N är ärliga, censurerar inte transaktioner och bygger inga forks av kedjan för att utföra en "double spend"-attack, så möjliggör användningen av en jämnt distribuerad obestridlig PVRB att välja en ärlig ledare med sannolikheten M / N (M / N > 1/2). Om varje ledare tilldelas en egen tidsram under vilken de kan producera en block och validera kedjan, och dessa intervaller är lika i tid, kommer kedjan av ärliga BP att vara längre än kedjan skapad av illvilliga BP, och konsensusalgoritmen, som är baserad på kedjans längd, kommer helt enkelt att avvisa den "dåliga". Denna princip om att tilldela lika tidskvanta till varje BP tillämpades först i Graphene (föregångaren till EOS) och möjliggör att majoriteten av blocken stängs med en enda signatur, vilket kraftigt minskar nätbelastningen och gör att denna konsensus kan fungera extremt snabbt och stabilt. Trots detta måste EOS-nätverk nu använda speciella block (Last Irreversible Block), som bekräftas med signaturer från 2/3 BP. Dessa block säkerställer slutgiltighet (oförmåga att skapa en gaffel som börjar tidigare än den senaste Last Irreversible Block).

I verkliga implementationer är dock protokollschemat mer komplext — omröstningar om de föreslagna blocken genomförs i flera steg för att upprätthålla nätverkets funktion även vid blocköverskridningar och nätverksproblem, men även med detta i åtanke kräver konsensusalgoritmer som använder PVRB betydligt färre meddelanden mellan BP, vilket gör dem snabbare än traditionell PВFT eller olika modifieringar av denna.

Den mest framträdande representanten för sådana algoritmer: Ouroboros från Cardano-teamet, som enligt uppgift har matematiskt bevisad motståndskraft mot sammansvärjningar bland BP.

I Ouroboros används PVRB för att definiera det så kallade "BP-schemat" — ett schema där varje BP får en egen tidslucka för publicering av block. En stor fördel med att använda PVRB är den fullständiga "jämlikheten" bland BP (baserat på storleken på deras saldon). Integriteten hos PVRB garanterar att illvilliga BP inte kan kontrollera schemat för tidsluckor, och därför kan de inte manipulera kedjan genom att i förväg förbereda och analysera kedjegaflar, och för att välja gaffeln räcker det att bara förlita sig på kedjans längd, utan att använda subtila metoder för att beräkna BP:s "nytta" och "vikten" av dess block.

I alla fall där en decentraliserad nätverk behöver välja en slumpmässig deltagare, är PVRB nästan alltid det bästa valet, snarare än en deterministisk variant baserad på till exempel blockhash. Utan PVRB kan möjligheten att påverka valet av deltagare leda till attacker, där angriparen, genom att välja mellan flera möjliga framtider, kan välja nästa korrumperade deltagare eller flera av dem för att säkra ett större inflytande över beslutsprocessen. Användningen av PVRB diskrediterar dessa typer av attacker.

Skalning och belastningsbalansering

PVRB kan också medföra betydande fördelar för uppgifter som syftar till att minska belastningen och skala betalningar. För att börja är det vettigt att bekanta sig med artikeln Rivest "Electronic Lottery Tickets as Micropayments". Den övergripande idén är att i stället för att göra 100 betalningar om 1 cent från betalaren till mottagaren, kan man spela på en rättvis lotteri med ett pris på 1$ = 100 cent, där betalaren vid varje betalning om 1 cent överför en av sina 100 "lotteribiljetter" till banken. En av dessa biljetter vinner banken 1$, och det är just den biljett som mottagaren kan registrera på blockchain. Det mest avgörande är att de återstående 99 biljetterna överförs mellan mottagaren och betalaren utan något externt deltagande, genom en privat kanal och med valfri hastighet. En bra beskrivning av protokollet baserat på detta schema i Emercoin-nätverket kan läsas här.

Denna schema har flera problem, till exempel kan mottagaren sluta betjäna betalaren omedelbart efter att ha fått den vinnande biljetten, men för många särskilda tillämpningar, som minutavgifter eller elektroniska prenumerationer på tjänster, kan de bortses ifrån. Det främsta kravet är självklart ärlighet i det genomförda lotteriet, och för att hålla det är PVRB helt nödvändigt.

Valet av en slumpmässig deltagare är avgörande för shardingsprotokoll som syftar till att möjliggöra horisontell skalning av blockkedjan, vilket gör det möjligt för olika BP att endast bearbeta sitt eget scope av transaktioner. Detta är en mycket komplex uppgift, särskilt när det gäller säkerhet vid sammanslagning av shards. Den ärliga valet av en slumpmässig BP för att tillsätta ansvariga för en viss shard, precis som i konsensusalgoritmer, är också en uppgift för PVRB. I centraliserade system tillsätts shards av en belastningsbalanserare, som helt enkelt beräknar en hash av förfrågan och skickar den till den nödvändiga utföraren. I blockkedjor kan möjligheten att påverka denna tillsättning leda till angrepp på konsensus. Till exempel kan en angripare kontrollera innehållet i transaktioner, han kan styra vilka transaktioner som hamnar i den shard han kontrollerar och manipulera blockkedjan inom den. Diskussionen om problemet med att använda slumpmässiga tal för shardingsuppgifter i Ethereum kan läsas. här
Sharding är en av de mest ambitiösa och seriösa uppgifterna inom blockkedjan, och dess lösning kommer att möjliggöra byggandet av decentraliserade nätverk med fantastisk prestanda och kapacitet. PVRB är bara en av de viktiga komponenterna för att lösa detta.

Spel, ekonomiska protokoll, arbitrage

Roller av slumpmässiga tal i spelindustrin är svåra att överskatta. Den uppenbara användningen i onlinecasinon, och den underliggande vid beräkningen av effekterna av en spelares handlingar – allt detta utgör extremt komplexa problem för decentraliserade nätverk, där det inte finns någon möjlighet att förlita sig på en central källa för slumpmässighet. Men, slumpmässigt val kan också lösa många ekonomiska problem och hjälpa till att bygga enklare och mer effektiva protokoll. Anta att det i vårt protokoll finns tvister angående betalning för vissa billiga tjänster, och dessa tvister uppstår ganska sällan. I sådana fall, om det finns en oåterkallelig PVRB, kan kunder och säljare enas om att slumpmässigt lösa tvister, men med en viss sannolikhet. Till exempel, med en sannolikhet på 60 % vinner kunden, och med en sannolikhet på 40 % vinner säljaren. Denna till en början absurda metod tillåter automatiskt att lösa tvister med en exakt förutsägbar andel vinster/förluster, vilket är acceptabelt för båda parter utan något deltagande av en tredje part och onödig tidsåtgång. Dessutom kan sannolikhetsförhållandet vara dynamiskt och bero på vissa globala variabler. Om till exempel företaget går bra, med ett lågt antal tvister och hög lönsamhet, kan företaget automatiskt justera sannolikheten för att lösa en tvist mot kundfokus, till exempel 70/30 eller 80/20, och omvänt, om tvister kostar mycket pengar och är bedrägliga eller oönskade, kan sannolikheten justeras åt andra hållet.

Ett stort antal intressanta decentraliserade protokoll, såsom token curaterade register, predictionsmarknader, bonding curves och många andra, utgör ekonomiska spel där gott beteende belönas och dåligt bestraffas. Dessa protokoll har ofta säkerhetsproblem som står i konflikt med varandra. Det som är skyddat mot attacker från "valarna" med miljarder tokens ("big stake") är sårbart för attacker från tusentals konton med små saldon ("sybil stake"), och åtgärder som vidtas mot en attack, till exempel icke-linjära avgifter, som skapats för att göra det olönsamt för stora insatser, diskrediteras vanligtvis av en annan attack. Eftersom det handlar om ett ekonomiskt spel kan de relevanta statistiska vikterna beräknas i förväg, och avgifter kan helt enkelt ersättas med randomiserade med motsvarande fördelning. Sådana probabilistiska avgifter implementeras extremt enkelt om det finns en pålitlig källa till slumpmessighet i blockkedjan och kräver inga komplicerade beräkningar, vilket gör livet svårare både för valarna och sybil-erna.
Samtidigt är det viktigt att komma ihåg att kontroll över en enda bit i denna slumpmessighet möjliggör fusk genom att dubbla eller halvera sannolikheterna, så en ärlig PVRB - en viktig komponent i sådana protokoll.

Var hittar man rätt slumpmessighet?

Teoretiskt sett möjliggör en ärlig slumpmässig urvalsprocess i decentraliserade nätverk bevisbar säkerhet för nästan vilket protokoll som helst mot samverkan. Motiveringen är ganska enkel - om nätverket enas om en bit, 0 eller 1, och mindre än hälften av deltagarna är oärliga, så kommer nätverket, vid tillräckligt många iterationer, garanterat att nå konsensus om denna bit med en fast sannolikhet. Bara för att den ärliga slumpen kommer att välja 51 av 100 deltagare i 51 % av fallen. Men detta gäller i teorin, eftersom det i verkliga nätverk, för att uppnå en sådan säkerhetsnivå som i artiklarna, krävs många meddelanden mellan värdar, komplex flermetodskryptografi, och varje komplicering av protokollet lägger omedelbart till nya attackvektorer.
Det är därför vi ännu inte ser en bevisat robust PVRB i blockkedjor, som har använts tillräckligt länge för att klara tester mot verkliga applikationer, flera revisioner, belastningar, och självklart, verkliga attacker, utan vilka det är svårt att kalla en produkt verkligen säker.

Det finns emellertid flera lovande tillvägagångssätt, de skiljer sig åt i många detaljer, och något av dem kommer definitivt att lösa problemet. Med dagens beräkningsresurser kan kryptografisk teori ganska smidigt omvandlas till praktiska tillämpningar. Framöver kommer vi gärna att berätta om implementationer av PVRB: det finns för närvarande flera, var och en med sitt eget viktiga egenskaper och specifikationer för genomförande, och bakom varje finns en bra idé. Det är inte så många team som sysslar med slumpmässighet, och erfarenheten från varje av dem är oerhört viktig för alla andra. Vi hoppas att vår information kommer att hjälpa andra team att gå snabbare, med tanke på erfarenheterna från föregångarna.

Källa: habr.com