Offentlige tilfældigheds- og tilfældighedsbeacons

Offentlig tilfældighed er en væsentlig komponent i mange virkelige sikkerhedsprotokoller. I nogle applikationer, såsom gambling og multiplayer-spil, tilføjer tilfældighed sjov. I andre applikationer giver tilfældighed en retfærdig måde at allokere ikke-delelige ressourcer på, lige fra grønne kort, til tildeling af dommere i kredsretten til sager, til seeding i sportsturneringer. Det bruges også til at allokere negativ ressourcer, såsom skatterevision eller sekundær sikkerhedsscreening i lufthavnen.

Traditionelt har vi været afhængige af betroede myndigheder til at generere tilfældigheder for disse protokoller, men i web3-verdenen bliver vi nødt til at gøre det bedre. I dette indlæg vil vi udforske tilgange til at opbygge offentligt verificerbar tilfældighed via distribuerede tilfældighedsbeacons og diskuter derefter nogle on-chain applikationer. (Del II, som er forestående, vil specifikt fokusere på ledervalg, samtidig med at der gives en vurdering af alternativer til ledervalg). 

Ønskede egenskaber

At generere tilfældige tal er en notorisk subtil opgave. For eksempel er mange kryptografiske nøgler blevet lækket, fordi de påberåbt sig en defekt tilfældig talgenerator (hvorfor Cloudflares væg af lavalamper ville have tjent som en kreativ afhjælpning). Det er bare privat tilfældighed, dog hvor kun én part behøver at generere og bruge det.

Offentlig tilfældighed er derimod en flerpartsproces, hvilket øger vanskeligheden betydeligt. En god protokol til at producere offentlig tilfældighed vil have følgende sikkerhedsegenskaber:

• Uvildigt: Ingen angribere eller koalition af angribere bør være i stand til at påvirke outputtet. 
• Pålidelig: Ingen angribere bør være i stand til at forhindre protokollen i at producere output.
• verificerbar: Enhver kan nemt verificere protokoloutputtet og bør se det samme output som alle andre.
• Uforudsigelige: Hvis protokollen producerer output på et tidspunkt T₁, ingen burde være i stand til at forudsige noget om output inden nogen tid T₀<T₁, ideelt set med T₀ meget tæt på T₁.

Unbiasability er en svagere egenskab end uforudsigelighed, fordi enhver protokol, der er uforudsigelig, skal være upartisk. Dataloger vil sige upartiskhed reducerer til uforudsigelighed, for hvis du kan bias, kan du forudsige. Men nogle gange vil vi gerne ræsonnere om dem hver for sig, fordi de kan stole på forskellige antagelser - for eksempel kan et uærligt flertal forudsige resultatet, men ikke være skævt.

Ud over disse egenskaber bør protokollen være effektiv til at køre og producere et stort antal tilfældige bits. (I praksis er det ofte tilstrækkeligt for applikationer at producere 128 tilfældige bits ved at bruge dem til at seed en pseudotilfældig talgenerator [PNRG] for at udsende flere bits efter behov. Imidlertid bør uforudsigelighed holde for hver enkelt bit af outputtet for at kunne bruges til f.eks. applikationer som lotterier eller ressourceallokeringer.) Protokollen bør også ideelt set være effektiv med hensyn til kommunikations- og beregningsomkostninger.

Forskellige protokoller kan opnå disse egenskaber under forskellige forhold. For eksempel kan nogle protokoller være upartiske af enhver koalition af f₁ ondsindede noder og uforudsigelige af enhver koalition af f₂<f₁ ondsindede noder. Der er også forskellige grader af bias. For eksempel kan en deltager i nogle protokoller være i stand til at bias outputtet med "én bit" - hvilket betyder, at de kan vælge mellem et af to mulige output. Andre angreb kan give dem mulighed for at reparere outputtet fuldstændigt. Typisk ønsker vi dog slet ikke at tolerere nogen bias (eller forudsigelighed).

Det kryptografiske ideal: Randomness fyrtårne

Kryptografer starter ofte med at tænke på en ideel løsning på deres problemer. I tilfælde af offentlig tilfældighed, a tilfældigheds fyrtårn er en idealiseret tjeneste, der regelmæssigt producerer tilfældige output, der opfylder alle de nødvendige sikkerhedskrav.

Et sådant idealiseret tilfældighedsbeacon, der ligner andre kryptografiske abstraktioner – såsom tilfældige orakler eller den generiske gruppemodel – eksisterer ikke i den virkelige verden. Men det er et nyttigt mål at stræbe efter og en nyttig model til at ræsonnere om protokoller, der er afhængige af offentlig tilfældighed. 

Vi kan overveje et par tilnærmelser af et ideelt tilfældighedsbeacon.

• Centraliserede beacons: Den nemmeste tilgang til at skabe god tilfældighed er gennem en centraliseret tredjepart med tjenester som f.eks NIST tilfældighedsbeacon or random.org, som genererer tilfældighed fra atmosfærisk støj og er akkrediteret til brug i gambling. Denne afhængighed af en tredjepart underminerer fuldstændig decentraliseringsfilosofien. Faktisk må vi i eksemplet ovenfor stole på, at de relevante organisationer genererer tilfældighed korrekt uden kryptografisk bevis.
• Fysisk tilfældighed vises: Mange traditionelle lotterier er afhængige af en offentlig fremvisning, som for eksempel kan omfatte, at nogen rækker ind i en beholder med bordtennisbolde med forskellige numre på. Desværre er disse ofte let manipulerbare. For eksempel, visse kugler kan lægges i en fryser , vælgeren kan få besked på at vælge de kolde.
• Naturlige beacons: En almindelig idé er at bruge tilfældige naturfænomener som vejr eller kosmisk baggrundsstråling som et fyrtårn. Desværre giver alle foreslåede kilder ikke stærk konsensus. Forskellige observatører vil se lidt forskellige værdier, hvilket kræver genindførelse af en betroet part for at tage en officiel måling, med alle ulemperne ved en centraliseret beacon.
• Semi-centraliserede beacons: En bedre tilgang ville være at få tilfældigheden fra Bitcoin-blokoverskrifter direkte eller fra aktiers lukkekurser, som er nemmere at verificere offentligt og sværere for enhver part at kontrollere fuldstændigt. Alligevel eksisterer der stadig subtile angreb på begge proof-of-work blockchain tilfældighed , aktiekurstilfældighed. Med blockchain-headere, for eksempel, kan minearbejdere vælge at tilbageholde blokke, hvis headere producerer en beacon-værdi, de ikke kan lide. Eller de kan vælge at bryde båndene, når to kolliderende blokke er fundet baseret på deres foretrukne beacon-output.

Decentraliserede tilfældighedsbeacons (DRB'er)

En naturlig tilgang til problemerne med centraliserede beacons er at designe en decentraliseret kryptografisk protokol til at producere offentlig tilfældighed. Dette problem er lidt som at designe decentraliserede konsensusprotokoller, kun sværere. Ikke kun skal alle deltagerne blive enige om et output (tilfældigheden), men det burde være umuligt for en ondsindet deltager i protokollen at bias eller forudsige outputtet.

Protokoller designet til at simulere et tilfældighedsbeacon kaldes distribuerede tilfældighedsbeacons (DRB'er). (Andre navne inkluderer "distribueret mønt-flipping.") Problemet er blevet undersøgt i årtier, med berømte umulighedsresultater bevist i 1980'erne, men interessen er blevet genvundet i blockchain-æraen. DRB'er kunne bruges til at give on-chain tilfældighed, hvilket ville være en nøgleingrediens for retfærdige, sikre og gennemsigtige on-chain-applikationer.

Den klassiske tilgang: Commit-reveal-protokoller

En meget simpel to-rund protokol er tilstrækkelig til en DRB i det optimistiske tilfælde. I runde 1, hver deltager i genererer en tilfældig værdi r_i og udgiver et kryptografisk engagement c_i=Begå(r_i). I denne applikation kan forpligtelsen simpelthen være en hashfunktion som SHA-256. Efter at hver deltagers tilsagn er offentliggjort, er de låst fast i deres valg af r_i, men forpligtelserne afslører ingen oplysninger om andre deltageres bidrag. I runde 2 "åbner hver deltager deres engagement" ved at publicere r_i. Alle de tilfældige værdier kombineres derefter, for eksempel ved at XORinge dem eller (helst) hash deres sammenkædning.

Denne protokol er enkel og producerer et tilfældigt beacon output, så længe selv en af ​​deltagerne vælger deres r_i tilfældigt. Desværre lider den af ​​en klassisk fejl: Når alle på nær en af ​​deltagerne har afsløret deres tilfældige værdi, er den sidste deltager i stand til at beregne det formodede beacon-output. Hvis de ikke kan lide det, kan de nægte at offentliggøre deres værdi og afbryde protokollen. At ignorere en defekt deltagers bidrag løser ikke problemet, for det giver stadig en angriber valget mellem to beacon-output (et beregnet med deres bidrag og et uden).

Blockchains tilbyder en naturlig løsning på dette problem: hver deltager kan blive bedt om at lægge nogle midler i spærret, som bliver beslaglagt, hvis de ikke afslører deres tilfældige bidrag. Dette var præcis den tilgang, klassikeren tog RANDAO fyrtårn på Ethereum. Ulempen ved denne tilgang er, at outputtet stadig kan være skævt, hvilket kan være umagen værd økonomisk for angriberen, hvis pengene i deponering er mindre end mængden af ​​penge, der kører på resultatet af beaconen. Bedre sikkerhed mod skævvridende angreb kræver, at der lægges flere mønter i spærret.

Commit-reveal-recover-protokoller

I stedet for at forsøge at tvinge alle parter til at afsløre deres tilfældige bidrag, indeholder nogle protokoller en gendannelsesmekanisme, så selv hvis et mindretal af deltagere dropper ud, kan resten fuldføre protokollen. Det er vigtigt, at protokollen giver det samme resultat i begge tilfælde, så parterne ikke kan påvirke resultatet ved at vælge, om de vil droppe ud eller ej.

En tilgang til at opnå dette er at få hver deltager til at give de andre dele af sin hemmelighed, så et flertal af dem kan rekonstruere den ved at bruge f.eks. Shamirs deling af hemmeligheder. En vigtig egenskab er dog, at de andre kan verificere, at den begåede hemmelighed er blevet delt korrekt, hvilket kræver brug af en stærkere primitiv kaldet offentligt verificerbar hemmelighedsdeling (PVSS).

Flere andre gendannelsesmekanismer er mulige, men de har alle den samme begrænsning. Hvis der er N deltagere, og vi ønsker robusthed, hvis nogen gruppe på op til f noder falder ud, så må det være sådan, at enhver gruppe af Nf deltagere kan beregne det endelige resultat. Men det betyder også en ondsindet koalition af Nf deltagere kan forudsige resultatet på forhånd ved privat at simulere gendannelsesmekanismen. Dette kan også ske under den første runde af protokollen, hvor en sådan koalition kunne ændre deres egne tilfældighedsvalg og påvirke resultatet. 

Sagt på en anden måde betyder dette enhver koalition af Nf noder skal indeholde mindst én ærlig node. Ved simpel algebra, Nf > f, Så f < N/2, og disse protokoller kræver i sagens natur et ærligt flertal. Dette er en væsentlig forskel i forhold til den originale sikkerhedsmodel for commit-reveal, som kun kræver f<N (mindst én ærlig deltager).

Disse protokoller kræver ofte også betydelige kommunikationsomkostninger for at dele den ekstra PVSS-information mellem alle noder i hver kørsel af protokollen. Forskermiljøet har arbejdet betydeligt med dette problem i de seneste år, med forskningsforslag bl.a RandShare, Skrabe, SecRand, HERB eller Albatross, men ingen ser ud til at have set implementering i den virkelige verden.

Verificerbare tilfældige funktionsbaserede protokoller

At indse, at en gruppe af Nf deltagere kan beregne den tilfældige beacon-værdi i ovenstående protokol, fører til en noget enklere tilgang: del en langsigtet hemmelig nøgle mellem N parter og få dem til at bruge det til at evaluere en verificerbar tilfældig funktion (VRF). Den hemmelige nøgle deles via en t-ud af-N tærskelordning, således at evt t deltagere kan beregne VRF (men en mindre koalition kan ikke). Til t=Nf, dette giver den samme modstandskraft til f ondsindede noder som commit-reveal-recover-protokollerne diskuteret ovenfor.

DFINITY banebrydende for denne tilgang som en del af deres konsensusprotokol ved hjælp af tærskel BLS-signaturer (som fungerer som en VRF). Den selvstændige fup randomness beacon bruger i det væsentlige den samme tilgang, med et sæt deltagertærskel-BLS-underskriver en tæller i hver runde. Det Entropiens Liga er en open source-forekomst af drand, der producerer tilfældighed hvert 30. sekund ved hjælp af 16 deltagende noder (fra september 2022), drevet af en blanding af virksomheder og universitetsforskningsgrupper. 

En ulempe ved disse tilgange er, at initialisering af tærskelnøglen er relativt kompleks, ligesom rekonfigurering af nøglen, når noder slutter sig til eller forlader. I det almindelige tilfælde er protokollerne dog meget effektive. 

Som beskrevet ovenfor tilføjer blot at signere en tællerværdi ikke nogen ny tilfældighed pr. runde, så hvis et tilstrækkeligt antal deltageres nøgler kompromitteres, så vil protokollen være forudsigelig i hver fremtidige runde.

Kædelink VRF kombinerer denne tilgang (ved at bruge NSEC5 VRF) med en ekstern kilde til tilfældighed specificeret af parter, der anmoder om tilfældighed, typisk en nylig blockchain-header i praksis. Disse data føres derefter gennem en VRF, som drives af enten én part eller tærskelværdi til en gruppe.

Ethereum s Beacon Chain bruger i øjeblikket BLS-baserede VRF'er: forslagsstilleren af ​​hver runde tilføjer deres VRF-værdi til blandingen. Dette sparer en kommunikationsrunde sammenlignet med commit-reveal-paradigmet (forudsat at en langsigtet BLS offentlig nøgle er registreret én gang), selvom dette design arver nogle forbehold fra commit-reveal-tilgangen, herunder muligheden for at bias beaconens output ved at tilbageholde output .

Verificerbare forsinkelsesfunktionsbaserede protokoller

Endelig er en lovende ny retning at bruge tidsbaseret kryptografi, specifikt verificerbare forsinkelsesfunktioner (VDF'er). Denne tilgang lover at give god kommunikationseffektivitet og robusthed med modstandsdygtighed over for N-1 ondsindede noder. 

Går man tilbage til den oprindelige forpligtelsesafsløringsprotokol, kan traditionelle forpligtelser erstattes med tidsbestemte forpligtelser at eliminere problemet med deltagere, der nægter at afsløre deres tilfældige bidrag. Tidsindstillede forpligtelser kan åbnes effektivt af den oprindelige committer eller af enhver, der er villig til at beregne en langsom funktion (i det væsentlige en VDF). Således, hvis en deltager dropper ud af en forpligtelsesafsløringsprotokol, kan deres forpligtelse stadig åbnes af andre. Det er vigtigt, at minimumstiden til at åbne forpligtelsen er lang nok til, at det ikke kan lade sig gøre i den første runde (forpligtelsesfasen) af protokollen, ellers kan ondsindede deltagere åbne andres forpligtelser hurtigt nok til at ændre deres eget bidrag og påvirke resultatet .

En endnu mere elegant en-runde protokol er mulig med moderne VDF'er: slip forpligtelsen helt. Hver deltager kan blot offentliggøre deres tilfældige bidrag r_i, og det endelige resultat er en kombination af hver deltagers bidrag, kørt gennem en VDF. Tidsforsinkelsen i beregningen af ​​VDF sikrer, at ingen kan vælge deres forpligtelse på en måde, der fordrejer det endelige output. Denne tilgang blev foreslået som UNICORN af Arjen Lenstra og Benjamin Wesolowski i 2015, og var faktisk en central motiverende applikation i udvikling af VDF'er.

Denne tilgang har set en vis praktisk implementering. Del implementerer en version af dette som en del af sin konsensusprotokol, ved hjælp af gentagne kvadrering af VDF'er i klassegrupper. Starkware gennemført en proof-of-concept VDF-baseret beacon ved hjælp af SNARK-baserede VDF'er. Ethereum også planer at anvende denne tilgang, opbygning af en dedikeret ASIC til beregning af VDF'er for at generere tilfældighed i konsensuslaget.

***

Offentlig tilfældighed er en væsentlig komponent i mange protokoller, men vi mangler stadig enhver standard DRB, der giver høj sikkerhed. Designrummet er stort, og mange hybrider og kombinationer af ovenstående tilgange er mulige. For eksempel er det muligt at kombinere en VRF-baseret protokol med en VDF-baseret protokol, som f.eks. tilføjer frisk entropi, som foreslået af RandRunner. Ethereums Beacon Chain bruger i øjeblikket VRF'er, selvom det kan tilføje VDF'er i fremtiden for at eliminere muligheden for bias fra blokeringstilbageholdelsesangreb.

Det er også et åbent spørgsmål, hvornår ærlige flertalsprotokoller er acceptable. For en relativt lille, undersøgt gruppe af deltagere - som League of Entropy - er en ærlig flertalsantagelse rimelig. På den anden side har protokoller, som kun kræver en enkelt ærlig deltager, en iboende fordel – flere deltagere kan kun forbedre sikkerheden. Dette betyder, at disse protokoller potentielt kan implementeres med åben, tilladelsesfri deltagelse.

I del II vil vi diskutere den specifikke anvendelse af randomiseret ledervalg i konsensusprotokoller, som har lidt forskellige designmål og som et resultat har set endnu flere protokoller og tilgange foreslået.

***

Joseph Bonneau er forskningspartner hos a16z crypto. Hans forskning fokuserer på anvendt kryptografi og blockchain-sikkerhed. Han har undervist i kryptovalutakurser ved University of Melbourne, NYU, Stanford og Princeton og modtog en PhD i datalogi fra University of Cambridge og BS/MS-grader fra Stanford.

Valeria Nikolaenko er forskningspartner hos a16z crypto. Hendes forskning fokuserer på kryptografi og blockchain-sikkerhed. Hun har også arbejdet med emner som langdistanceangreb i PoS-konsensusprotokoller, signaturordninger, post-kvantesikkerhed og multi-party beregning. Hun har en ph.d. i kryptografi fra Stanford University under vejledning af professor Dan Boneh og arbejdede på Diem blockchain som en del af kerneforskerteamet.

***

Redaktør: Tim Sullivan

***

De synspunkter, der er udtrykt her, er dem fra det enkelte AH Capital Management, LLC ("a16z") personale, der er citeret, og er ikke synspunkter fra a16z eller dets tilknyttede selskaber. Visse oplysninger indeholdt heri er indhentet fra tredjepartskilder, herunder fra porteføljeselskaber af fonde forvaltet af a16z. Selvom det er taget fra kilder, der menes at være pålidelige, har a16z ikke uafhængigt verificeret sådanne oplysninger og fremsætter ingen erklæringer om informationernes vedvarende nøjagtighed eller deres passende for en given situation. Derudover kan dette indhold omfatte tredjepartsreklamer; a16z har ikke gennemgået sådanne annoncer og støtter ikke noget reklameindhold indeholdt deri.

Dette indhold er kun givet til informationsformål og bør ikke påberåbes som juridisk, forretningsmæssig, investerings- eller skatterådgivning. Du bør rådføre dig med dine egne rådgivere om disse spørgsmål. Henvisninger til værdipapirer eller digitale aktiver er kun til illustrationsformål og udgør ikke en investeringsanbefaling eller tilbud om at levere investeringsrådgivningstjenester. Ydermere er dette indhold ikke rettet mod eller beregnet til brug af nogen investorer eller potentielle investorer og kan under ingen omstændigheder stoles på, når der træffes en beslutning om at investere i en fond, der administreres af a16z. (Et tilbud om at investere i en a16z-fond vil kun blive givet af private placement-memorandummet, tegningsaftalen og anden relevant dokumentation for en sådan fond og bør læses i deres helhed.) Eventuelle investeringer eller porteføljeselskaber nævnt, refereret til eller beskrevne er ikke repræsentative for alle investeringer i køretøjer, der administreres af a16z, og der kan ikke gives sikkerhed for, at investeringerne vil være rentable, eller at andre investeringer foretaget i fremtiden vil have lignende karakteristika eller resultater. En liste over investeringer foretaget af fonde forvaltet af Andreessen Horowitz (undtagen investeringer, hvortil udstederen ikke har givet tilladelse til, at a16z offentliggør såvel som uanmeldte investeringer i offentligt handlede digitale aktiver) er tilgængelig på https://a16z.com/investments /.

Diagrammer og grafer, der er angivet i, er udelukkende til informationsformål og bør ikke stoles på, når der træffes nogen investeringsbeslutning. Tidligere resultater er ikke vejledende for fremtidige resultater. Indholdet taler kun fra den angivne dato. Alle fremskrivninger, estimater, prognoser, mål, udsigter og/eller meninger udtrykt i disse materialer kan ændres uden varsel og kan afvige fra eller være i modstrid med andres meninger. Se venligst https://a16z.com/disclosures for yderligere vigtige oplysninger.