Offentlige tilfeldighets- og tilfeldighetssignaler

Offentlig tilfeldighet er en viktig komponent i mange virkelige sikkerhetsprotokoller. I noen applikasjoner, for eksempel gambling og flerspillerspill, gir tilfeldighet moro. I andre applikasjoner gir tilfeldighet en rettferdig måte å allokere ikke-delbare ressurser på, alt fra grønne kort, til tildeling av dommere i kretsretten til saker, til seeding i sportsturneringer. Den brukes også til å fordele negativ ressurser, som skatterevisjon eller sekundær sikkerhetskontroll på flyplassen.

Tradisjonelt har vi stolt på pålitelige myndigheter for å generere tilfeldighet for disse protokollene, men i web3-verdenen må vi gjøre det bedre. I dette innlegget vil vi utforske tilnærminger til å bygge offentlig verifiserbar tilfeldighet via distribuerte tilfeldighetsbeacons og diskuter deretter noen applikasjoner i kjeden. (Del II, som er forestående, vil spesifikt fokusere på ledervalg, samtidig som det gir en vurdering av alternativer til ledervalg.) 

Ønskede egenskaper

Å generere tilfeldige tall er en notorisk subtil oppgave. For eksempel har mange kryptografiske nøkler blitt lekket fordi de avhengig av en defekt tilfeldig tallgenerator (som Cloudflares vegg av lavalamper ville ha fungert som en kreativ avbøtende effekt). Det er bare privat tilfeldighet, men hvor bare én part trenger å generere og bruke den.

Offentlig tilfeldighet er derimot en flerpartsprosess, noe som øker vanskeligheten betydelig. En god protokoll for å produsere offentlig tilfeldighet vil ha følgende sikkerhetsegenskaper:

• Upartisk: Ingen angriper, eller koalisjon av angripere, skal være i stand til å påvirke utdataene. 
• Pålitelig: Ingen angriper skal kunne forhindre at protokollen produserer utdata.
• verifiserbar: Hvem som helst kan enkelt verifisere protokollutgangen, og bør se den samme utgangen som alle andre.
• Uforutsigbare: Hvis protokollen produserer utdata på et tidspunkt T₁, ingen skal kunne forutsi noe om utgangen før en tid T₀<T₁, ideelt sett med T₀ veldig nær T₁.

Unbiasability er en svakere egenskap enn uforutsigbarhet fordi enhver protokoll som er uforutsigbar må være upartisk. Dataforskere vil si upartiskhet reduserer til uforutsigbarhet, for hvis du kan bias, kan du forutsi. Men noen ganger vil vi ønske å resonnere om dem hver for seg fordi de kan stole på forskjellige forutsetninger – for eksempel kan et uærlig flertall forutsi resultatet, men ikke påvirke det.

I tillegg til disse egenskapene bør protokollen være effektiv til å kjøre og produsere et stort antall tilfeldige biter. (I praksis er det ofte tilstrekkelig for applikasjoner å produsere 128 tilfeldige biter, ved å bruke dem til å seede en pseudotilfeldig tallgenerator [PNRG] for å sende ut flere biter etter behov. Imidlertid bør uforutsigbarhet gjelde for hver enkelt bit av utgangen for å være brukbar for slike applikasjoner som lotterier eller ressursallokeringer.) Protokollen bør også ideelt sett være effektiv med tanke på kommunikasjons- og beregningskostnader.

Ulike protokoller kan oppnå disse egenskapene under forskjellige forhold. For eksempel kan noen protokoller være upartiske av enhver koalisjon av f₁ ondsinnede noder og uforutsigbare av enhver koalisjon av f₂<f₁ ondsinnede noder. Det er også ulike grader av skjevhet. For eksempel, i noen protokoller kan en deltaker være i stand til å bias utdataene med "en bit" - noe som betyr at de kan velge mellom en av to mulige utganger. Andre angrep kan tillate dem å fikse utdataene fullstendig. Vanligvis ønsker vi imidlertid ikke å tolerere noen skjevhet (eller forutsigbarhet) i det hele tatt.

Det kryptografiske idealet: Rogomness beacons

Kryptografer starter ofte med å tenke på en ideell løsning på problemene deres. I tilfelle av offentlig tilfeldighet, a tilfeldighetsfyrtårn er en idealisert tjeneste som regelmessig produserer tilfeldig utdata som tilfredsstiller alle nødvendige sikkerhetskrav.

Et slikt idealisert tilfeldighetsfyrtårn, som ligner på andre kryptografiske abstraksjoner – for eksempel tilfeldige orakler eller den generiske gruppemodellen – eksisterer ikke i den virkelige verden. Men det er et nyttig mål å strebe etter og en nyttig modell for å resonnere rundt protokoller som er avhengige av offentlig tilfeldighet. 

Vi kan vurdere noen få tilnærminger til et ideelt tilfeldighetsbeacon.

• Sentraliserte beacons: Den enkleste tilnærmingen til å generere god tilfeldighet er gjennom en sentralisert tredjepart med tjenester som NIST tilfeldighetsfyrtårn or random.org, som genererer tilfeldighet fra atmosfærisk støy og er akkreditert for bruk i gambling. Denne avhengigheten av en tredjepart undergraver fullstendig desentraliseringsfilosofien. Faktisk, i eksemplet ovenfor må vi stole på at de relevante organisasjonene genererer tilfeldighet på riktig måte, uten noe kryptografisk bevis.
• Fysisk tilfeldighet vises: Mange tradisjonelle lotterier er avhengige av en offentlig visning, som for eksempel kan inkludere noen som strekker seg inn i en beholder med ping pongballer med forskjellige tall på. Dessverre er disse ofte lett manipulerbare. For eksempel, enkelte kuler kan legges i fryseren og velgeren kan få beskjed om å velge de kalde.
• Naturlige beacons: En vanlig idé er å bruke tilfeldige naturfenomener som vær eller kosmisk bakgrunnsstråling som et fyrtårn. Dessverre gir ikke alle foreslåtte kilder sterk konsensus. Forskjellige observatører vil se litt forskjellige verdier, noe som krever gjeninnføring av en betrodd part for å ta en offisiell måling, med alle ulempene ved en sentralisert beacon.
• Halvsentraliserte beacons: En bedre tilnærming ville være å få tilfeldigheten fra Bitcoin blokkoverskrifter direkte eller fra aksjenes sluttkurs, som er lettere å verifisere offentlig og vanskeligere for en part å kontrollere fullstendig. Likevel eksisterer det fortsatt subtile angrep på begge proof-of-work blockchain tilfeldighet og aksjekurs tilfeldighet. Med blokkjedehoder, for eksempel, kan gruvearbeidere velge å holde tilbake blokker hvis overskrifter produserer en beacon-verdi de ikke liker. Eller de kan velge å bryte båndene når to kolliderende blokker blir funnet basert på deres foretrukne beacon-utgang.

Desentraliserte tilfeldighetsbeacons (DRB)

En naturlig tilnærming til problemene med sentraliserte beacons er å designe en desentralisert kryptografisk protokoll for å produsere offentlig tilfeldighet. Dette problemet er litt som å designe desentraliserte konsensusprotokoller, bare vanskeligere. Ikke bare trenger alle deltakerne å bli enige om en utgang (tilfeldigheten), men det skal være umulig for en ondsinnet deltaker i protokollen å forutsi utdataene.

Protokoller designet for å simulere et tilfeldighetsbeacon kalles distribuerte tilfeldighetsbeacons (DRB). (Andre navn inkluderer "distribuert mynt-flipping.") Problemet har blitt studert i flere tiår, med kjente umulighetsresultater bevist på 1980-tallet, men interessen har blitt vekket igjen i blokkjedetiden. DRB-er kan brukes til å gi tilfeldighet i kjeden, som vil være en nøkkelingrediens for rettferdige, sikre og transparente applikasjoner i kjeden.

Den klassiske tilnærmingen: Commit-reveal-protokoller

En veldig enkel to-runde protokoll er tilstrekkelig for en DRB i det optimistiske tilfellet. I runde 1, hver deltaker i genererer en tilfeldig verdi r_i og publiserer en kryptografisk forpliktelse c_i=Begå(r_i). I denne applikasjonen kan forpliktelsen ganske enkelt være en hash-funksjon som SHA-256. Etter at hver deltakers forpliktelse er offentliggjort, er de låst til sitt valg av r_i, men forpliktelsene avslører ingen informasjon om andre deltakeres bidrag. I runde 2 "åpner hver deltaker sitt engasjement" ved å publisere r_i. Alle de tilfeldige verdiene blir deretter kombinert, for eksempel ved å XORing dem eller (fortrinnsvis) hashe sammenkoblingen av dem.

Denne protokollen er enkel og produserer en tilfeldig beacon-utgang så lenge til og med en av deltakerne velger sin r_i tilfeldig. Dessverre lider det av en klassisk feil: når alle unntatt én av deltakerne har avslørt sin tilfeldige verdi, er den siste deltakeren i stand til å beregne den antatte beacon-utgangen. Hvis de ikke liker det, kan de nekte å publisere verdien, og avbryte protokollen. Å ignorere en defekt deltakers bidrag løser ikke problemet, fordi det fortsatt gir en angriper valget mellom to beacon-utganger (en beregnet med deres bidrag og en uten).

Blokkjeder tilbyr en naturlig løsning på dette problemet: hver deltaker kan bli bedt om å sette noen midler i deponering som blir beslaglagt hvis de ikke avslører sitt tilfeldige bidrag. Dette var akkurat tilnærmingen til klassikeren RANDAO fyrtårn på Ethereum. Ulempen med denne tilnærmingen er at utgangen fortsatt kan være partisk, noe som kan være verdt økonomisk for angriperen hvis pengene i sperret er mindre enn beløpet som kjører på resultatet av beaconen. Bedre sikkerhet mot skjemmende angrep krever at flere mynter er deponert.

Forplikte-avsløre-gjenopprette protokoller

I stedet for å prøve å tvinge alle parter til å avsløre deres tilfeldige bidrag, inkluderer noen protokoller en gjenopprettingsmekanisme slik at selv om et mindretall av deltakerne faller fra, kan resten fullføre protokollen. Det er viktig at protokollen gir det samme resultatet i begge tilfeller, slik at partene ikke kan påvirke resultatet ved å velge om de skal droppe ut eller ikke.

En tilnærming for å oppnå dette er å la hver deltaker gi de andre deler av sin hemmelighet, slik at et flertall av dem kan rekonstruere den ved å bruke f.eks. Shamirs hemmelighetsdeling. En viktig egenskap er imidlertid at de andre kan verifisere at den begåtte hemmeligheten har blitt delt på riktig måte, noe som krever bruk av en sterkere primitiv kalt offentlig verifiserbar hemmelig deling (PVSS).

Flere andre gjenopprettingsmekanismer er mulige, men de har alle samme begrensning. Hvis det er N deltakere, og vi ønsker robusthet dersom noen gruppe på opptil f noder faller ut, så må det være slik at enhver gruppe av Nf deltakerne kan beregne det endelige resultatet. Men det betyr også en ondsinnet koalisjon av Nf deltakere kan forutsi resultatet på forhånd ved privat å simulere gjenopprettingsmekanismen. Dette kan også skje under den første runden av protokollen, i løpet av denne tiden kan en slik koalisjon endre sine egne tilfeldighetsvalg og påvirke resultatet. 

Sagt på en annen måte betyr dette enhver koalisjon av Nf noder må inneholde minst én ærlig node. Ved enkel algebra, Nf > f, så f < N/2, og disse protokollene krever iboende et ærlig flertall. Dette er en betydelig forskjell til den opprinnelige sikkerhetsmodellen for commit-reveal, som bare krever f<N (minst en ærlig deltaker).

Disse protokollene krever ofte også betydelige kommunikasjonskostnader for å dele den ekstra PVSS-informasjonen mellom alle noder i hver kjøring av protokollen. Forskningsmiljøet har gjort betydelig arbeid med dette problemet de siste årene, med forskningsforslag bl.a RandShare, Skrape, SecRand, HERBeller Albatross, men ingen ser ut til å ha sett implementering i den virkelige verden.

Verifiserbare tilfeldige funksjonsbaserte protokoller

Innser at en gruppe av Nf deltakere kan beregne den tilfeldige beacon-verdien i protokollen ovenfor, fører til en noe enklere tilnærming: dele en langsiktig hemmelig nøkkel mellom N parter og få dem til å bruke det til å evaluere en verifiserbar tilfeldig funksjon (VRF). Den hemmelige nøkkelen deles via en t-ut av-N terskelordning, slik at evt t deltakere kan beregne VRF (men en mindre koalisjon kan ikke). Til t=Nf, gir dette den samme motstandskraften til f ondsinnede noder som commit-reveal-recover-protokollene diskutert ovenfor.

DFINITY banebrytende denne tilnærmingen som en del av deres konsensusprotokoll ved å bruke terskel BLS-signaturer (som fungerer som en VRF). Den frittstående svindel randomness beacon bruker i hovedsak den samme tilnærmingen, med et sett med deltakere terskel-BLS-signerer en teller i hver runde. De League of Entropy er en åpen kildekode-forekomst av drand som produserer tilfeldighet hvert 30. sekund ved bruk av 16 deltakende noder (per september 2022), drevet av en blanding av selskaper og universitetsforskningsgrupper. 

En ulempe med disse tilnærmingene er at initialisering av terskelnøkkelen er relativt kompleks, og det samme er å rekonfigurere nøkkelen når noder blir med eller forlater. I det vanlige tilfellet er imidlertid protokollene svært effektive. 

Som beskrevet ovenfor, vil det å signere en tellerverdi ikke legge til noen ny tilfeldighet per runde, så hvis et tilstrekkelig antall deltakeres nøkler blir kompromittert, vil protokollen være forutsigbar i hver fremtidige runde.

Chainlink VRF skurtreskerne denne tilnærmingen (ved å bruke NSEC5 VRF) med en ekstern kilde til tilfeldighet spesifisert av parter som ber om tilfeldighet, vanligvis en nylig blokkjede-overskrift i praksis. Disse dataene blir deretter matet gjennom en VRF som drives av enten én part eller terskel til en gruppe.

Ethereum s Beacon kjede bruker for tiden BLS-baserte VRF-er: forslagsstilleren av hver runde legger til sin VRF-verdi til blandingen. Dette sparer en runde med kommunikasjon sammenlignet med commit-reveal-paradigmet (forutsatt at en langsiktig BLS-offentlig nøkkel er registrert én gang), selv om denne designen arver noen forbehold fra commit-reveal-tilnærmingen, inkludert muligheten til å forspenne beaconens utgang ved å holde tilbake utdata .

Verifiserbare forsinkelsesfunksjonsbaserte protokoller

Til slutt, en lovende ny retning er bruk av tidsbasert kryptografi, spesielt verifiserbare forsinkelsesfunksjoner (VDF-er). Denne tilnærmingen lover å gi god kommunikasjonseffektivitet og robusthet med motstandskraft mot N-1 ondsinnede noder. 

Går tilbake til den opprinnelige forpliktelsesavsløringsprotokollen, kan tradisjonelle forpliktelser erstattes med tidsbestemte forpliktelser for å eliminere problemet med deltakere som nekter å avsløre sitt tilfeldige bidrag. Tidsinnstilte forpliktelser kan åpnes effektivt av den opprinnelige committeren, eller av hvem som helst som er villig til å beregne en langsom funksjon (i hovedsak en VDF). Så hvis en deltaker faller ut av en forpliktelse-avsløringsprotokoll, kan deres forpliktelse fortsatt åpnes av andre. Det er viktig at minimumstiden for å åpne forpliktelsen er lang nok til at det ikke kan gjøres i løpet av den første runden (forpliktelsesfasen) av protokollen, ellers kan ondsinnede deltakere åpne andres forpliktelser raskt nok til å endre sitt eget bidrag og påvirke resultatet. .

En enda mer elegant en-runde protokoll er mulig med moderne VDF-er: dropp engasjementet helt. Hver deltaker kan ganske enkelt publisere sitt tilfeldige bidrag r_i, og det endelige resultatet er en kombinasjon av hver deltakers bidrag, kjørt gjennom en VDF. Tidsforsinkelsen i beregningen av VDF sikrer at ingen kan velge sin forpliktelse på en måte som påvirker den endelige produksjonen. Denne tilnærmingen ble foreslått som UNICORN av Arjen Lenstra og Benjamin Wesolowski i 2015, og var faktisk en sentral motiverende applikasjon i utvikling av VDF-er.

Denne tilnærmingen har sett en viss praktisk distribusjon. Chia implementerer en versjon av dette som en del av sin konsensusprotokoll, ved å bruke VDF-er for gjentatt kvadratur i klassegrupper. Starkware implementert en proof-of-concept VDF-basert beacon ved hjelp av SNARK-baserte VDF-er. Ethereum også planer å bruke denne tilnærmingen, bygge en dedikert ASIC for å beregne VDF-er for å generere tilfeldighet i konsensuslaget.

***

Offentlig tilfeldighet er en viktig komponent i mange protokoller, men vi mangler fortsatt noen standard DRB som gir høy sikkerhet. Designrommet er stort og mange hybrider og kombinasjoner av de ovennevnte tilnærmingene er mulige. For eksempel er det mulig å kombinere en VRF-basert protokoll med en VDF-basert protokoll, som legger til ny entropi, for eksempel, som foreslått av RandRunner. Ethereums Beacon Chain bruker for tiden VRF-er, selv om den kan legge til VDF-er i fremtiden for å eliminere muligheten for skjevhet fra blokkeringsangrep.

Det er også et åpent spørsmål når ærlige majoritetsprotokoller er akseptable. For en relativt liten, undersøkt gruppe deltakere – som League of Entropy – er en ærlig flertallsantakelse rimelig. På den annen side har protokoller som bare krever en enkelt ærlig deltaker en iboende fordel - flere deltakere kan bare forbedre sikkerheten. Dette betyr at disse protokollene potensielt kan distribueres med åpen, tillatelsesfri deltakelse.

I del II vil vi diskutere den spesifikke anvendelsen av randomisert ledervalg i konsensusprotokoller, som har litt forskjellige designmål og som et resultat har sett enda flere protokoller og tilnærminger foreslått.

***

Joseph Bonneau er forskningspartner hos a16z crypto. Forskningen hans fokuserer på anvendt kryptografi og blokkjedesikkerhet. Han har undervist i kryptovalutakurs ved University of Melbourne, NYU, Stanford og Princeton, og mottok en doktorgrad i informatikk fra University of Cambridge og BS/MS-grader fra Stanford.

Valeria Nikolaenko er forskningspartner hos a16z crypto. Forskningen hennes fokuserer på kryptografi og blokkjedesikkerhet. Hun har også jobbet med temaer som langdistanseangrep i PoS-konsensusprotokoller, signaturordninger, post-kvantesikkerhet og flerpartsberegning. Hun har en doktorgrad i kryptografi fra Stanford University under veiledning av professor Dan Boneh, og jobbet på Diem blockchain som en del av kjerneforskerteamet.

***

Redaktør: Tim Sullivan

***

Synspunktene som uttrykkes her er de fra individuelle AH Capital Management, LLC (“a16z”) personell som er sitert og er ikke synspunktene til a16z eller dets tilknyttede selskaper. Visse opplysninger her er innhentet fra tredjepartskilder, inkludert fra porteføljeselskaper av fond forvaltet av a16z. Selv om a16z er hentet fra kilder som antas å være pålitelige, har ikke a16z uavhengig verifisert slik informasjon og gir ingen representasjoner om den varige nøyaktigheten til informasjonen eller dens hensiktsmessighet for en gitt situasjon. I tillegg kan dette innholdet inkludere tredjepartsannonser; aXNUMXz har ikke vurdert slike annonser og støtter ikke noe reklameinnhold som finnes deri.

Dette innholdet er kun gitt for informasjonsformål, og bør ikke stoles på som juridisk, forretningsmessig, investerings- eller skatterådgivning. Du bør rådføre deg med dine egne rådgivere om disse sakene. Referanser til verdipapirer eller digitale eiendeler er kun for illustrasjonsformål, og utgjør ikke en investeringsanbefaling eller tilbud om å tilby investeringsrådgivningstjenester. Videre er dette innholdet ikke rettet mot eller ment for bruk av noen investorer eller potensielle investorer, og kan ikke under noen omstendigheter stoles på når du tar en beslutning om å investere i et fond som forvaltes av a16z. (Et tilbud om å investere i et a16z-fond vil kun gis av det private emisjonsmemorandumet, tegningsavtalen og annen relevant dokumentasjon for et slikt fond og bør leses i sin helhet.) Eventuelle investeringer eller porteføljeselskaper nevnt, referert til, eller beskrevet er ikke representative for alle investeringer i kjøretøy forvaltet av a16z, og det kan ikke gis noen garanti for at investeringene vil være lønnsomme eller at andre investeringer som gjøres i fremtiden vil ha lignende egenskaper eller resultater. En liste over investeringer foretatt av fond forvaltet av Andreessen Horowitz (unntatt investeringer som utstederen ikke har gitt tillatelse til at a16z kan offentliggjøre så vel som uanmeldte investeringer i børsnoterte digitale eiendeler) er tilgjengelig på https://a16z.com/investments /.

Diagrammer og grafer gitt i er kun for informasjonsformål og bør ikke stoles på når du tar investeringsbeslutninger. Tidligere resultater er ikke en indikasjon på fremtidige resultater. Innholdet taler kun fra den angitte datoen. Eventuelle anslag, estimater, prognoser, mål, prospekter og/eller meninger uttrykt i dette materialet kan endres uten varsel og kan avvike eller være i strid med meninger uttrykt av andre. Vennligst se https://a16z.com/disclosures for ytterligere viktig informasjon.