Offentlig slumpmässighet och slumpmässighet

Offentlig slumpmässighet är en viktig komponent i många verkliga säkerhetsprotokoll. I vissa applikationer, som hasardspel och spel för flera spelare, ger slumpmässighet roligt. I andra applikationer ger slumpmässighet ett rättvist sätt att allokera icke-delbara resurser, allt från gröna kort, till tilldelning av domare i kretsrätten till mål, till seedning i sportturneringar. Det används också för att fördela negativ resurser, som skatterevisioner eller sekundär säkerhetskontroll på flygplatsen.

Traditionellt har vi förlitat oss på betrodda myndigheter för att skapa slumpmässighet för dessa protokoll, men i web3-världen måste vi göra bättre ifrån oss. I det här inlägget kommer vi att utforska metoder för att bygga offentligt verifierbar slumpmässighet via distribuerade slumpmässighetsfyrar och diskutera sedan några on-chain-applikationer. (Del II, som är kommande, kommer specifikt att fokusera på ledareval, samtidigt som det ger en bedömning av alternativa ledarevalsmetoder.) 

Önskade egenskaper

Att generera slumpmässiga tal är en notoriskt subtil uppgift. Till exempel har många kryptografiska nycklar läckt ut eftersom de förlitat sig på en felaktig slumptalsgenerator (för vilken Cloudflares vägg av lavalampor skulle ha fungerat som en kreativ dämpning). Det är bara privat slumpmässighet, dock där endast en part behöver generera och använda den.

Offentlig slumpmässighet är däremot en flerpartsprocess, vilket avsevärt ökar svårigheten. Ett bra protokoll för att skapa offentlig slumpmässighet kommer att ha följande säkerhetsegenskaper:

• Opartisk: Ingen angripare, eller koalition av angripare, ska kunna påverka utdata. 
• Tillförlitlig: Ingen angripare ska kunna förhindra att protokollet producerar utdata.
• kontrollerbara: Vem som helst kan enkelt verifiera protokollets utdata och bör se samma utdata som alla andra.
• Oförutsägbar: Om protokollet producerar utdata vid tidpunkten T₁, ingen borde kunna förutsäga någonting om resultatet innan en tid T₀<T₁, helst med T₀ väldigt nära T₁.

Opartiskhet är en svagare egenskap än oförutsägbarhet eftersom alla protokoll som är oförutsägbara måste vara opartiska. Datavetare skulle säga opartiskhet minskar till oförutsägbarhet, för om du kan partiska kan du förutsäga. Men ibland kommer vi att vilja resonera om dem separat eftersom de kan förlita sig på olika antaganden – till exempel kan en oärlig majoritet förutsäga resultatet, men inte påverka det.

Utöver dessa egenskaper bör protokollet vara effektivt att köra och producera ett stort antal slumpmässiga bitar. (I praktiken räcker det ofta för applikationer att producera 128 slumpmässiga bitar, använda dem för att seed en pseudoslumptalsgenerator [PNRG] för att mata ut fler bitar efter behov. Men oförutsägbarheten bör gälla för varje enskild bit av utdata för att vara användbar för sådana applikationer som lotterier eller resurstilldelningar.) Protokollet bör också helst vara effektivt när det gäller kommunikations- och beräkningskostnader.

Olika protokoll kan uppnå dessa egenskaper under olika förhållanden. Till exempel kan vissa protokoll vara opartiska av någon koalition av f₁ skadliga noder och oförutsägbara av någon koalition av f₂<f₁ skadliga noder. Det finns också olika grader av partiskhet. Till exempel, i vissa protokoll kan en deltagare vara i stånd att påverka utmatningen med "en bit" - vilket innebär att de kan välja mellan en av två möjliga utgångar. Andra attacker kan göra det möjligt för dem att fixa utdata helt. Vanligtvis vill vi dock inte tolerera någon partiskhet (eller förutsägbarhet) alls.

Det kryptografiska idealet: Randomness beacons

Kryptografer börjar ofta med att fundera på en idealisk lösning på sina problem. Vid offentlig slumpmässighet, a slumpmässighetsfyr är en idealiserad tjänst som regelbundet producerar slumpmässiga utdata som uppfyller alla nödvändiga säkerhetskrav.

En sådan idealiserad slumpmässighetsfyr, liknande andra kryptografiska abstraktioner – som slumpmässiga orakel eller den generiska gruppmodellen – existerar inte i den verkliga världen. Men det är ett användbart mål att sträva efter och en användbar modell för att resonera kring protokoll som förlitar sig på offentlig slumpmässighet. 

Vi kan överväga några approximationer av en idealisk slumpmässighetsfyr.

• Centraliserade beacons: Det enklaste sättet att skapa bra slumpmässighet är genom en centraliserad tredje part med tjänster som NIST randomness beacon or random.org, som genererar slumpmässighet från atmosfäriskt buller och är ackrediterat för användning i spel. Detta beroende av en tredje part undergräver helt decentraliseringsfilosofin. I exemplet ovan måste vi faktiskt lita på att de relevanta organisationerna genererar slumpmässighet korrekt, utan några kryptografiska bevis.
• Fysisk slumpmässighet visas: Många traditionella lotterier är beroende av en offentlig visning, vilket till exempel kan inkludera att någon sträcker sig in i en behållare med pingisbollar med olika nummer på. Tyvärr är dessa ofta lätt manipulerbara. Till exempel, vissa bollar kan läggas i frysen och väljaren kan uppmanas att välja de kalla.
• Naturliga beacons: En vanlig idé är att använda slumpmässiga naturfenomen som väder eller kosmisk bakgrundsstrålning som en fyr. Tyvärr ger inte alla föreslagna källor stark konsensus. Olika observatörer kommer att se något olika värden, vilket kräver att en betrodd part återinförs för att göra en officiell mätning, med alla nackdelarna med en centraliserad beacon.
• Halvcentraliserade beacons: Ett bättre tillvägagångssätt vore att få slumpen från Bitcoin block headers direkt eller från aktiernas stängningskurser, vilket är lättare att verifiera offentligt och svårare för någon part att kontrollera helt. Ändå finns det fortfarande subtila attacker mot båda bevis-på-arbete blockchain slumpmässighet och slumpmässighet i aktiekursen. Med blockchain-headers, till exempel, kan gruvarbetare välja att undanhålla block vars rubriker producerar ett beaconvärde de inte gillar. Eller de kan välja att bryta banden när två kolliderande block hittas baserat på deras föredragna beacon-utgång.

Decentraliserade randomness beacons (DRB)

En naturlig inställning till problemen med centraliserade beacons är att designa ett decentraliserat kryptografiskt protokoll för att skapa offentlig slumpmässighet. Det här problemet är ungefär som att designa decentraliserade konsensusprotokoll, bara svårare. Alla deltagare behöver inte bara komma överens om en utdata (slumpmässigheten), utan det borde vara omöjligt för en illvillig deltagare i protokollet att fördomsfullt eller förutsäga resultatet.

Protokoll utformade för att simulera en slumpmässig beacon kallas distribuerade slumpmässiga beacons (DRBs). (Andra namn inkluderar "distribuerad myntvändning.") Problemet har studerats i decennier, med berömda omöjlighetsresultat visade sig på 1980-talet, men intresset har väckts på nytt under blockchain-eran. DRB kan användas för att tillhandahålla slumpmässighet i kedjan, vilket skulle vara en nyckelingrediens för rättvisa, säkra och transparenta applikationer i kedjan.

Det klassiska tillvägagångssättet: Protokoll för avslöjande av åtaganden

Ett mycket enkelt tvårunda protokoll räcker för en DRB i det optimistiska fallet. I omgång 1, varje deltagare i genererar ett slumpmässigt värde r_i och publicerar ett kryptografiskt åtagande c_i=Begå(r_i). I den här applikationen kan åtagandet helt enkelt vara en hashfunktion som SHA-256. Efter att varje deltagares åtagande publicerats är de låsta vid sitt val av r_i, men åtagandena avslöjar ingen information om andra deltagares bidrag. I omgång 2 ”öppnar varje deltagare sitt engagemang” genom att publicera r_i. Alla slumpmässiga värden kombineras sedan, till exempel genom att XORing dem eller (helst) hasha deras sammanlänkning.

Detta protokoll är enkelt och producerar en slumpmässig beacon-utgång så länge som ens en av deltagarna väljer sin r_i slumpvis. Tyvärr lider det av ett klassiskt fel: när alla utom en av deltagarna har avslöjat sitt slumpmässiga värde, kan den sista deltagaren beräkna den förmodade beacon-utgången. Om de inte gillar det kan de vägra att publicera sitt värde och avbryta protokollet. Att ignorera en felaktig deltagares bidrag löser inte problemet, eftersom det fortfarande ger en angripare valet mellan två beacon-utgångar (en beräknad med deras bidrag och en utan).

Blockkedjor erbjuder ett naturligt botemedel mot detta problem: varje deltagare kan krävas att lägga några medel i deposition som beslagtas om de inte avslöjar sitt slumpmässiga bidrag. Detta var precis det tillvägagångssätt som klassikern tog RANDAO ledstjärna på Ethereum. Nackdelen med detta tillvägagångssätt är att resultatet fortfarande kan vara partisk, vilket kan vara värt ekonomiskt för angriparen om pengarna i deposition är mindre än summan pengar som åker på resultatet av beacon. Bättre säkerhet mot fördomsattacker kräver att man lägger in fler mynt i deposition.

Protokoll för begå-avslöja-återställa

Istället för att försöka tvinga alla parter att avslöja deras slumpmässiga bidrag, innehåller vissa protokoll en återställningsmekanism så att även om en minoritet av deltagarna hoppar av kan resten slutföra protokollet. Det är viktigt att protokollet ger samma resultat i båda fallen, så att parterna inte kan påverka resultatet genom att välja om de ska hoppa av eller inte.

Ett sätt att uppnå detta är att låta varje deltagare förse de andra med delar av sin hemlighet, så att en majoritet av dem kan rekonstruera den, med hjälp av t.ex. Shamirs hemlighetsdelning. En viktig egenskap är dock att de andra kan verifiera att den begångna hemligheten har delats korrekt, vilket kräver användning av en starkare primitiv som kallas offentligt verifierbar hemlighetsdelning (PVSS).

Flera andra återställningsmekanismer är möjliga, men de har alla samma begränsning. Om det finns N deltagare, och vi vill ha motståndskraft om någon grupp på upp till f noder faller ut, då måste det vara så att någon grupp av Nf deltagarna kan beräkna slutresultatet. Men det innebär också en illvillig koalition av Nf deltagare kan förutsäga resultatet i förväg genom att privat simulera återställningsmekanismen. Detta kan också hända under den första omgången av protokollet, under vilken tid en sådan koalition kan modifiera sina egna slumpmässiga val och påverka resultatet. 

Med andra ord betyder detta vilken koalition som helst Nf noder måste innehålla minst en ärlig nod. Med enkel algebra, Nf > f, Så f < N/2, och dessa protokoll kräver i sig en ärlig majoritet. Detta är en betydande skillnad mot den ursprungliga säkerhetsmodellen för commit-reveal, som bara kräver f<N (minst en ärlig deltagare).

Dessa protokoll kräver ofta också betydande kommunikationskostnader för att dela den extra PVSS-informationen mellan alla noder i varje körning av protokollet. Forskarvärlden har gjort ett stort arbete med detta problem under de senaste åren, med forskningsförslag bl.a RandShare, Skrapa, SecRand, ÖRT, eller Albatross, men ingen verkar ha sett en implementering i verkligheten.

Verifierbara slumpmässiga funktionsbaserade protokoll

Inser att en grupp av Nf deltagare kan beräkna det slumpmässiga beaconvärdet i ovanstående protokoll leder till ett något enklare tillvägagångssätt: dela en långsiktig hemlig nyckel mellan N parter och få dem att använda den för att utvärdera en verifierbar slumpmässig funktion (VRF). Den hemliga nyckeln delas via en t-ut ur-N tröskelordning, så att ev t deltagare kan beräkna VRF (men en mindre koalition kan inte). För t=Nf, detta ger samma motståndskraft till f skadliga noder som protokollen för commit-reveal-recover som diskuterats ovan.

DFINITY banat väg för detta tillvägagångssätt som en del av deras konsensusprotokoll med hjälp av tröskelvärde BLS-signaturer (som fungerar som en VRF). Den fristående lurendrejeri randomness beacon använder i huvudsak samma tillvägagångssätt, med en uppsättning deltagare tröskel-BLS-signerar en räknare i varje omgång. De League of Entropy är en öppen källkodsinstans av drand som producerar slumpmässighet var 30:e sekund med hjälp av 16 deltagande noder (september 2022), som drivs av en blandning av företag och universitetsforskningsgrupper. 

En nackdel med dessa tillvägagångssätt är att initiering av tröskelnyckeln är relativt komplicerad, liksom att omkonfigurera nyckeln när noder går med eller lämnar. I det vanliga fallet är dock protokollen mycket effektiva. 

Som beskrivits ovan, att bara signera ett räknarvärde tillför inte någon ny slumpmässighet per omgång, så om ett tillräckligt antal deltagares nycklar äventyras, kommer protokollet att vara förutsägbart i varje framtida omgång.

Kedjelänk VRF kombinerar detta tillvägagångssätt (med hjälp av NSEC5 VRF) med en extern källa till slumpmässighet specificerad av parter som begär slumpmässighet, vanligtvis en ny blockchain-header i praktiken. Dessa data matas sedan genom en VRF som drivs av antingen en part eller tröskelvärden till en grupp.

Ethereum s Varningskedja använder för närvarande BLS-baserade VRF:er: förslagsställaren för varje omgång lägger till sitt VRF-värde till mixen. Detta sparar en kommunikationsrunda jämfört med commit-reveal-paradigmet (förutsatt att en långsiktig BLS-publik nyckel registreras en gång), även om denna design ärver några förbehåll från commit-reveal-metoden, inklusive möjligheten att fördomsfulla beaconens utdata genom att undanhålla utdata .

Verifierbara fördröjningsfunktionsbaserade protokoll

Slutligen, en lovande ny riktning är att använda tidsbaserad kryptografi, specifikt verifierbara fördröjningsfunktioner (VDF: er). Detta tillvägagångssätt lovar att ge god kommunikationseffektivitet och robusthet med motståndskraft mot N-1 skadliga noder. 

Om vi ​​går tillbaka till det ursprungliga protokollet för avslöjande av åtaganden kan traditionella åtaganden ersättas med tidsbestämda åtaganden för att eliminera problemet med deltagare som vägrar att avslöja sitt slumpmässiga bidrag. Tidsinställda åtaganden kan öppnas effektivt av den ursprungliga committern, eller av vem som helst som är villig att beräkna en långsam funktion (i huvudsak en VDF). Således, om någon deltagare hoppar av ett protokoll för avslöjande av åtaganden, kan deras åtagande fortfarande öppnas av andra. Det är viktigt att minimitiden för att öppna engagemanget är tillräckligt lång för att det inte kan göras under den första omgången (commit-fasen) av protokollet, annars kan skadliga deltagare öppna andras åtaganden tillräckligt snabbt för att modifiera sitt eget bidrag och påverka resultatet. .

Ett ännu mer elegant engångsprotokoll är möjligt med moderna VDF:er: släpp åtagandet helt. Varje deltagare kan helt enkelt publicera sitt slumpmässiga bidrag r_i, och slutresultatet är en kombination av varje deltagares bidrag, som körs genom en VDF. Tidsfördröjningen vid beräkning av VDF säkerställer att ingen kan välja sitt engagemang på ett sätt som påverkar den slutliga produktionen. Detta tillvägagångssätt föreslogs som UNICORN av Arjen Lenstra och Benjamin Wesolowski 2015, och var verkligen en viktig motiverande applikation i utveckling av VDF.

Detta tillvägagångssätt har sett en viss praktisk implementering. Chia implementerar en version av detta som en del av sitt konsensusprotokoll, genom att använda VDF:er med upprepad kvadratur i klassgrupper. Starkware genomfört a proof-of-concept VDF-baserad beacon använder SNARK-baserade VDF:er. Ethereum också planer att använda detta tillvägagångssätt, bygga en dedikerad ASIC för beräkning av VDF:er för att generera slumpmässighet i konsensusskiktet.

***

Offentlig slumpmässighet är en viktig komponent i många protokoll, men vi saknar fortfarande någon standard DRB som ger hög säkerhet. Designutrymmet är stort och många hybrider och kombinationer av ovanstående tillvägagångssätt är möjliga. Det är till exempel möjligt att kombinera ett VRF-baserat protokoll med ett VDF-baserat protokoll, som lägger till ny entropi, till exempel, som föreslagits av RandRunner. Ethereums Beacon Chain använder för närvarande VRF:er, även om det kan lägga till VDF:er i framtiden för att eliminera möjligheten till partiskhet från blockerade attacker.

Det är också en öppen fråga när ärliga majoritetsprotokoll är acceptabla. För en relativt liten, granskad grupp av deltagare – som League of Entropy – är ett ärligt majoritetsantagande rimligt. Å andra sidan har protokoll som bara kräver en enda ärlig deltagare en inneboende fördel – fler deltagare kan bara förbättra säkerheten. Detta innebär att dessa protokoll potentiellt kan distribueras med öppet, tillståndslöst deltagande.

I del II kommer vi att diskutera den specifika tillämpningen av randomiserat ledareval i konsensusprotokoll, som har lite olika designmål och som ett resultat har sett ännu fler protokoll och tillvägagångssätt föreslagna.

***

Joseph Bonneau är en forskningspartner på a16z crypto. Hans forskning fokuserar på tillämpad kryptografi och blockchain-säkerhet. Han har undervisat i kryptovalutakurser vid University of Melbourne, NYU, Stanford och Princeton, och tagit doktorsexamen i datavetenskap från University of Cambridge och BS/MS-grader från Stanford.

Valeria Nikolaenko är en forskningspartner på a16z crypto. Hennes forskning fokuserar på kryptografi och blockchain-säkerhet. Hon har också arbetat med ämnen som långdistansattacker i PoS-konsensusprotokoll, signaturscheman, postkvantsäkerhet och flerpartsberäkning. Hon har en doktorsexamen i kryptografi från Stanford University under ledning av professor Dan Boneh, och arbetade på Diem blockchain som en del av kärnforskargruppen.

***

Redaktör: Tim Sullivan

***

De åsikter som uttrycks här är de från den individuella AH Capital Management, LLC (“a16z”) personal som citeras och är inte åsikterna från a16z eller dess dotterbolag. Viss information som finns här har erhållits från tredjepartskällor, inklusive från portföljbolag av fonder som förvaltas av a16z. Även om den är hämtad från källor som anses vara tillförlitliga, har a16z inte självständigt verifierat sådan information och gör inga utfästelser om informationens varaktiga riktighet eller dess lämplighet för en given situation. Dessutom kan detta innehåll innehålla tredjepartsannonser; a16z har inte granskat sådana annonser och stöder inte något reklaminnehåll i dem.

Detta innehåll tillhandahålls endast i informationssyfte och bör inte litas på som juridisk rådgivning, affärs-, investerings- eller skatterådgivning. Du bör rådfråga dina egna rådgivare i dessa frågor. Hänvisningar till värdepapper eller digitala tillgångar är endast i illustrativt syfte och utgör inte en investeringsrekommendation eller erbjudande om att tillhandahålla investeringsrådgivningstjänster. Dessutom är detta innehåll inte riktat till eller avsett att användas av några investerare eller potentiella investerare, och får inte under några omständigheter lita på när man fattar ett beslut om att investera i någon fond som förvaltas av a16z. (Ett erbjudande om att investera i en a16z-fond kommer endast att göras av det privata emissionsmemorandumet, teckningsavtalet och annan relevant dokumentation för en sådan fond och bör läsas i sin helhet.) Alla investeringar eller portföljbolag som nämns, hänvisas till, eller beskrivna är inte representativa för alla investeringar i fordon som förvaltas av a16z, och det finns ingen garanti för att investeringarna kommer att vara lönsamma eller att andra investeringar som görs i framtiden kommer att ha liknande egenskaper eller resultat. En lista över investeringar gjorda av fonder som förvaltas av Andreessen Horowitz (exklusive investeringar för vilka emittenten inte har gett tillstånd för a16z att offentliggöra såväl som oanmälda investeringar i börsnoterade digitala tillgångar) finns tillgänglig på https://a16z.com/investments /.

Diagram och grafer som tillhandahålls i är endast i informationssyfte och bör inte litas på när man fattar investeringsbeslut. Tidigare resultat är inte en indikation på framtida resultat. Innehållet talar endast från det angivna datumet. Alla prognoser, uppskattningar, prognoser, mål, framtidsutsikter och/eller åsikter som uttrycks i detta material kan ändras utan föregående meddelande och kan skilja sig åt eller strida mot åsikter som uttrycks av andra. Se https://a16z.com/disclosures för ytterligare viktig information.