Ledervalg fra Randomness Beacons og andre strategier

Ledervalg i en blokkjede-innstilling har som mål å velge deltakeren som skal bestemme neste blokk som skal legges til blokkjeden. Vanligvis velges én validator per spor fra settet med validatorer og får rett til å utvide kjeden med en ny blokk i det sporet. (Vi antar at validatorer holder nøyaktig tid og er enige om gjeldende spornummer.) I denne artikkelen utforsker vi strategier for randomisert ledervalg i konsensusprotokoller. (For mer om tilfeldighet generelt, se vår tidligere artikkel, Offentlige tilfeldighets- og tilfeldighetssignaler, Hvor vi så på frittstående protokoller for å generere offentlig verifiserbar og uforutsigbar tilfeldighet.) 

Hvorfor ledervalg er viktig

Å velge ærlige og aktive ledere er avgjørende for sunn vekst i kjeden. Ondsinnede validatorer bør ikke være i stand til å påvirke ledervalgsprosessen for å gjøre seg selv til ledere oftere. Ellers kan produksjonen av blokker falle i hendene på parter som kan sensurere transaksjoner eller stoppe blokkjeden helt. I konsensusprotokoller i lengste kjede-stil, kan en leder som produserer en ugyldig blokk (eller ingen blokk i det hele tatt) føre til at kjeden midlertidig deler seg. I konsensusprotokoller i BFT-stil utløser en dårlig leder en underprotokoll for visningsendring som vil medføre kommunikasjonskostnader. 

Komitevalgsalternativet

Valg av utvalg er et beslektet problem, der målet er å velge en jevnt tilfeldig undergruppe av validatorene av en viss størrelse k. Denne funksjonaliteten er nyttig i seg selv fordi det ofte er behov for underutvalg i blokkjedeinnstillinger for å redusere størrelsen på validatorsettet for å få konsensus til å løpe raskere (blant mange eksempler er Algorands sortering og Ethereums utvalg av utvalg). Men komitévalg er også nyttig for ledervalg, slik at validatorene kan unngå å kjøre en ledervalgprotokoll på nytt hvis den valgte lederen ikke møter opp. Dersom det i stedet for leder velges et utvalg med fast rekkefølge, kan det andre utvalgsmedlem bli leder dersom det første ikke er tilgjengelig. 

Egenskapene til en god valgprotokoll

I en ledervalgsprotokoll skal lederne være uforutsigbare. Hvis en angriper får vite hvem den kommende lederen er, kan den starte et Denial of Service (DoS)-angrep på dem for å hindre dem i å publisere en blokkering. Angriperen kunne deretter ta ned neste leder og så videre, og stoppe blokkjeden. Uforutsigbarheten kan også styrkes for å sikre at validatoren selv ikke lærer når den skal lede, noe som kan være viktig for å forebygge bestikkelser.

Ledervalgsprosessen bør ha følgende tre egenskaper:

• Rettferdighet: hver ærlig validator har en sannsynlighet på 1/N å velges fra et sett av N validatorer (en avslappet forestilling om spilleteoretisk rettferdighet tillater bygningsledervalg selv i nærvær av et ondsinnet flertall om enn med en ikke-konstant nedre grense for antall runder).
• uforutsigbarhet: motstanderen lærer ikke den neste lederen før en tid T før lederen annonserer neste blokk.
• unikhet: nøyaktig én leder velges i hvert spor.

Hemmelig ledervalg

Hemmelig ledervalg er et uforutsigbart valg med T = 0. I denne prosessen er ikke lederen kjent for noen før den publiserer blokken. Dette eliminerer vinduet for et DoS-angrep fullstendig: før lederen avslører seg selv, vet ikke angriperen hvem han skal angripe, og gjør sin beste strategi til en tilfeldig gjetning. Og etter at lederen publiserer blokkeringen sin, er det for sent å angripe fordi lederen allerede har oppfylt sitt ansvar overfor protokollen. 

Forestillingen om "etter at lederen publiserer blokken" er faktisk en forenkling, fordi vi ikke har øyeblikkelig kringkasting i den virkelige verden. En angriper med en sterk nettverksposisjon kan legge merke til at en leder kringkaster en blokk først og raskt kan ødelegge lederen, opprette en annen blokk og kjøre den opprinnelige kringkastingen i forkant. 

Selv om dette er en veldig sterk angripermodell, har det blitt foreslått forsvar mot den. Algorand foreslo sletter modell, der lederen faktisk er i stand til å slette nøkkelen som er nødvendig for å signere blokken i sporet før du kringkaste det, så det er virkelig for sent å angripe når lederen tar noen offentlig handling. Thaddeus Dryja, Quanquan C. Liu og Neha Narula, tre forskere fra MIT Media Lab, foreslått at lederen beregner en VDF på blokken sin før kringkasting, og sikrer at en adaptiv angriper ikke kan konstruere en alternativ gyldig blokk i tide for å få den akseptert for ønsket spor.

Andre valgmetoder 

Den enkleste ledervalgsprosessen er round robin, hvor ledere velges i deterministisk rekkefølge. Til tross for at denne tilnærmingen er forutsigbar og dermed er utsatt for DoS-angrep, er den egnet for systemer med tillatelse der validatorene har god DoS-beskyttelse.

En leder kan også velges ved å bruke en utgang fra en ekstern tilfeldighetsfyrtårn, hvis en er tilgjengelig og klarert for å være sikker. Dessverre er det vanskelig for konsensusdeltakerne å kjøre en distribuert randomness beacon (DRB)-protokoll selv, siden disse typisk antar en forestilling om pålitelig kringkasting eller konsensus, som igjen krever ledervalg igjen, og introduserer en sirkulær avhengighet.

Gjeldende ledervalg i Ethereum er en god case-studie. Hver nye leder beregner en Verifiable Randomness Function (VRF)-utgang (en BLS-signatur på epokenummeret) og XORs verdien inn i blandingen. Verdien av blandingen ved slutten av epoken i definerer lederne og underkomiteene for epokens varighet i+2. Ledere og timeplanen deres er forutsigbare en epoke i forveien (for øyeblikket ~6.4 min). Protokollen er utsatt for rettferdighetsangrep, ettersom den siste lederen kan velge å publisere eller holde tilbake sitt bidrag til blandingen og dermed påvirke resultatet av neste valg med en bit. Hvis den siste  k ledere samarbeider, kan de introdusere k  biter av skjevhet og gjøre valg av ondsinnede brukere mer sannsynlig. Ethereum Foundation jobber aktivt med mer avanserte teknikker for ledervalg som vi diskuterer nedenfor.

VRF-basert ledervalg

En annen tilnærming, pioner av Algorand, Er en VRF-basert ledervalg, som innebærer at hver validator privat beregner en VRF-utgang og sjekker om utgangen faller under en terskel. Denne prosedyren filtrerer allerede ut de fleste validatorene, siden terskelen er valgt slik at det er usannsynlig å falle under den. De få gjenværende validatorene avslører sine VRF-utganger, og den med lavest VRF-verdi blir valgt. Denne tilnærmingen oppnår perfekt uforutsigbarhet (eller hemmelighold), men den garanterer ikke unikhet. Noen av validatorene mottar kanskje ikke meldinger fra alle potensielle ledere og kan anta at feil leder vant valget, noe som får disse validatorene til å dele seg fra hovedkjeden. 

VRF-evalueringen seedes med jevne mellomrom med utdata fra et tilfeldighetsbeacon for å gjøre det mindre forutsigbart for validatorene selv å se hvilke spor de skal lede. Denne egenskapen forhindrer en angriper som i det stille kompromitterer validatoren fra å lære seg sporet når validatoren vil bli en leder og starte et angrep når validatoren er i ferd med å annonsere en blokkering. Denne tilnærmingen bidrar også til å forhindre bestikkelsesangrep, der en validator beviser overfor eksterne parter at den vil være leder i et bestemt spor og høster bestikkelser i bytte mot å fullføre en oppgave som leder (f.eks. blokkere en transaksjon).

Slike tilnærminger, hvor antall valgte ledere er en tilfeldig variabel, kalles Probabilistisk ledervalg (PLE). PLE kan føre til at ingen ledere blir valgt for en gitt plass. Dette tilsvarer å velge en leder som er ondsinnet eller offline ved at sporet til slutt vil ende opp med å bli hoppet over, noe som reduserer effektiviteten til konsensusprotokollen.

Men det største forbeholdet med PLE er at flere ledere kan bli valgt, noe som krever en slags uavgjort prosedyre. Bånd utgjør en risiko for konsensus, siden en validator med en vinnende input kan rapportere det til bare halvparten av nettverket, noe som potensielt kan forårsake uenighet i den valgte lederen. Videre kan prosesser for å løse bånd ta ekstra tid og kommunikasjon, og skade effektiviteten. Dfinity, diskutert mer detaljert i det første innlegget av denne serien, bruker et VRF-basert tilfeldighetsbeacon for å velge en enkelt leder; det ofrer imidlertid uforutsigbarhet å gjøre det. Ideelt sett bør enhver prosess for å velge en leder unngå bånd helt og fortsatt være uforutsigbar, noe som fører oss til den hellige gral av dette forskningsområdet – Single Secret Leader Election.

Enkelt hemmelig ledervalg 

Målet med Enkelt hemmelig ledervalg (SSLE) er å velge en unik leder fra et sett med validatorer samtidig som rettferdighet og uforutsigbarhet opprettholdes. Protocol Labs presenterte ideen som en forskningsproblem, og Dan Boneh, Stanford-dataforskeren og a16z kryptoforskningsrådgiver, med Saba Eskandarian, Lucjan Hanzlik og Nicola Greco, tilbød senere en formell definisjon av SSLE. Denne unike egenskapen unngår konsensusrisikoen og effektivitetskostnadene som oppstår fra uavgjorte prosedyrer. Helt konkret, Sarah Azouvi, fra Protocol Labs, og Danielle Cappelletti, fra Politecnico di Torino, Vis at når SSLE brukes sammenlignet med PLE i en lengste kjedeprotokoll, kan blokker sluttføres betydelig raskere (25 prosent raskere med en motstander som kontrollerer en tredjedel av innsatsen). Å utvikle en praktisk SSLE-protokoll er derfor et viktig problem.

I den vanligste tilnærmingen, som vi vil kalle shuffle-basert (brukt både i det originale SSLE-papiret og et Ethereum SSLE-forslag), hver validator registrerer en nuncio som ser tilfeldig ut, men som de kan bevise tilhører dem. Nonene blir deretter satt sammen til en liste. Listen blandes slik at nonsens blir koblet fra validatorene som sendte dem; det vil si at gitt den blandede listen, kan ingen motstander fortelle hvilken validator som sendte inn hvilken ikke. En listeindeks blir deretter valgt i henhold til en offentlighet tilfeldighetsfyrtårn, og lederen avslører seg selv ved å bevise at nonsen på den indeksen på den blandede listen tilhører dem. 

Siden bare én indeks er valgt, gir den shuffle-baserte protokollen alltid ut en unik leder. Fordi det tilfeldige beaconet er bygget for å sende ut jevnt tilfeldige verdier, er protokollen det også rettferdig: hver validator har lik sjanse til å bli valgt. Videre, hvis stokkingen utføres på riktig måte (dvs. jevnt tilfeldig) og nonsens blir ukoblingbare til validatorenes identiteter, oppnår denne protokollen også uforutsigbarhet.

Blanding er nødvendig fordi selv om man ganske enkelt velger en indeks fra den ustokkede listen basert på et tilfeldig beacon allerede vil gi unikhet og rettferdighet, er uforutsigbarhet vanskeligere å oppnå: Hvis en motstander vet hvilken validator som sendte inn hvilken nonce, vet den hvem som sendte inn nonsen ved den valgte. indeks og kan identifisere lederen. 

Disse følgende to tilnærmingene blander listen på forskjellige måter. Jo enklere er Ethereum SSLE-forslag, der n validatorer sender inn sine nonces via Tor for å koble validatorenes identiteter fra deres nonces. Når alle validatorer har registrert seg, blandes listen ved hjelp av et offentlig tilfeldighetsbeacon, og validatorene blir ledere i rekkefølgen til den blandede listen. Selv om denne ordningen er praktisk – må valget gjennomføres kun én gang pr n spor – denne avhengigheten av Tor kan være uønsket (som tilfellet er med å stole på sikkerheten til enhver ekstern protokoll). Dessuten er den ikke helt uforutsigbar: etter den første n-1 ledere avslører seg selv, finalen nth leder er kjent.

I stedet for å bruke Tor, har det originale SSLE-papiret hvert validatorregister for valg i rekkefølge ved å legge det til ikke-en til listen, blande listen og randomisering på nytt nonsene. Denne re-randomiseringen betyr at hver nonce tilordnes en ny, ikke-tilknyttbar streng slik at validatoren som den tilhører, fortsatt kan bevise eierskap til den re-randomiserte nonsen. Re-randomisering gjør det slik at en motstander ikke kan fortelle hvilken posisjon en bestemt nonce havnet i etter shuffle, forutsatt at minst én shuffler er ærlig.

Selv om denne sekvensielle tilnærmingen til stokking fra det originale SSLE-dokumentet unngår avhengighet av Tor og oppnår de formelle egenskapene til SSLE, er det dyrt: hver gang en ny validator registrerer seg, må de legge ut hele den blandede listen til blokkjeden, randomisere alle nonces på nytt, og gi et bevis på at de gjorde det ærlig, noe som resulterer i lineær mengde kommunikasjon per validator. Med et uendret sett med validatorer, må dette gjøres (amortiseres) én gang per valg, ettersom lederen registrerer seg på nytt når de har avslørt beviset for nonce. Oppgaven gir en avveining mellom effektivitet og forutsigbarhet: vi kan i stedet blande bare en mindre delmengde av listen, og redusere kostnadene, hvis vi er villige til å tillate en liten mengde forutsigbarhet. Å oppnå en god balanse mellom effektivitet og sikkerhet er utfordrende, og som et resultat er SSLE-protokoller ennå ikke brukt mye i praksis. 

Denne sekvensielle tilnærmingen kan også brukes til å løse komitévalgproblemet ved å bruke det tilfeldige fyrtårnet for å velge k distinkte indekser fra listen som komitémedlemmer. Dette er en fin prestasjon, siden problemet ikke er trivielt løst av VRF-baserte tilnærminger, siden man kjører en sannsynlig VRF-basert protokoll k ganger kan velge en varierende komitéstørrelse avhengig av tilfeldigheten. 

Andre tilnærminger til SSLE

En annen shuffle-basert tilnærming er Adaptivt sikre SSLE fra DDH. Denne konstruksjonen er litt mer komplisert, men oppnår en sterkere forestilling om sikkerhet, og beskytter mot en adaptiv motstander i Algorands slettemodell. Denne motstanderen er adaptiv ved at den kan velge hvilke validatorer som skal ødelegges under protokollen, i motsetning til før protokollen starter. 

En ytterligere utfordring i SSLE er å velge hver validator med sannsynlighet proporsjonal med deres innsats, i stedet for jevnt tilfeldig. Blandingsbaserte protokoller kan naivt oppnå dette ved å la hver validator registrere flere nonce: én nonce for hver innsatsenhet de har. Imidlertid øker kostnadene ved stokking lineært med antall innsatsenheter S, og blir veldig dyrt selv for realistiske innsatsfordelinger. En elegant MPC-basert SSLE tilnærmingen øker kompleksiteten bare med logg S, og det unngår også behovet for et pålitelig oppsett eller tilfeldighetsbeacon. Sammenlignet med stokkingbaserte tilnærminger krever det imidlertid flere kommunikasjonsrunder (logaritmisk i antall deltakere) per valgt leder

***

Vi har oppsummert analysen vår i denne praktiske tabellen.

	Rettferdighet	Uforutsigbarhet/ Hemmelighold*	unikhet
Round-robin	✓	✗	✓
Ideell tilfeldighet-fyrtårn	✓	✗	✓
Ethereums ledervalg (nåværende)	✗	✗	✓
VRF-basert ledervalg (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Round-robin beacon er fullt forutsigbart, men i resten av beacons ✗ betyr at forestillingen oppnås i en viss begrenset grad: ideal-tilfeldighet-fyrtårn er uforutsigbart, men motstanderen lærer resultatet samtidig med den valgte lederen, derfor kan den valgte lederen bli angrepet før den kunngjør en blokkering; Etherums beacon er uforutsigbar opptil ~6 min og kan være litt partisk for å skade rettferdigheten; Algorand velger flere ledere med liten sannsynlighet.

SSLE er en lovende retning som oppnår rettferdighet, uforutsigbarhet og unikhet. To fremtredende utfordringer ved bruken er effektivitet og evnen til å imøtekomme uensartede innsatsfordelinger. Videre antar de shuffle-baserte SSLE-tilnærmingene som vi fremhever eksistensen av et objektivt tilfeldig beacon, som ikke er enkelt å oppnå i praksis. Siden SSLE først nylig har blitt formelt definert, vil vi sannsynligvis se forbedrede protokoller som tar opp utfordringene i nær fremtid. 

***

Miranda Kristus er doktorgradsstudent i informatikk ved Columbia University, hvor hun er medlem av teorigruppen og presidentstipendiat. Hun er også forskerpraktikant ved a16z crypto.

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.