Ledervalg fra Randomness Beacons og andre strategier

Ledervalg i en blockchain-indstilling har til formål at vælge den deltager, der bestemmer den næste blok, der skal føjes til blockchainen. Typisk vælges én validator pr. slot fra sættet af validatorer og får ret til at forlænge kæden med en ny blok i denne plads. (Vi antager, at validatorer holder nøjagtig tid og er enige om det aktuelle slotnummer.) I denne artikel undersøger vi strategier for randomiseret ledervalg i konsensusprotokoller. (For mere om tilfældighed generelt, se vores tidligere artikel, Offentlige tilfældigheds- og tilfældighedsbeaconsHvor vi undersøgte selvstændige protokoller til at generere offentligt verificerbare og uforudsigelige tilfældigheder.) 

Hvorfor ledervalg betyder noget

At vælge ærlige og aktive ledere er afgørende for en sund vækst i kæden. Ondsindede validatorer bør ikke være i stand til at påvirke ledervalgsprocessen for at gøre sig selv til ledere oftere. Ellers kan produktionen af ​​blokke falde i hænderne på parter, der kan censurere transaktioner eller helt stoppe blockchainen. I konsensusprotokoller i den længste kæde kan en leder, der producerer en ugyldig blok (eller slet ingen blok), få ​​kæden til midlertidigt at forgrene sig. I BFT-lignende konsensusprotokoller udløser en dårlig leder en underprotokol for visningsændring, der vil medføre en kommunikationsoverhead. 

Udvalgsvalget alternativ

Udvalgsvalg er et relateret problem, hvor målet er at vælge en ensartet tilfældig delmængde af validatorerne af en eller anden fast størrelse k. Denne funktionalitet er nyttig i sig selv, fordi der ofte er behov for underudvalg i blockchain-indstillinger for at reducere størrelsen på validatorsættet for at få konsensus til at køre hurtigere (blandt mange eksempler er Algorands sortering , Ethereums udvalgsudvalg). Men udvalgsvalg er også nyttigt til ledervalg, hvilket giver validatorerne mulighed for at undgå at genkøre en ledervalgsprotokol, hvis den valgte leder ikke dukker op. Hvis der i stedet for en leder vælges et udvalg med en fast rækkefølge, kan det andet udvalgsmedlem blive leder, hvis det første ikke er ledigt. 

Egenskaberne ved en god valgprotokol

I en ledervalgsprotokol bør lederne være uforudsigelige. Hvis en angriber finder ud af, hvem den kommende leder er, kan den starte et Denial of Service (DoS)-angreb på dem for at forhindre dem i at udgive en blokering. Angriberen kunne derefter tage den næste leder ned og så videre, hvilket fik blockchain til at stoppe. Uforudsigeligheden kan også blive styrket for at sikre, at validatoren ikke selv lærer, hvornår den skal lede, hvilket kan være vigtigt for forebyggelse af bestikkelse.

Ledervalgsprocessen bør have følgende tre egenskaber:

• Fairness: hver ærlig validator har en sandsynlighed på 1/N at blive valgt fra et sæt af N validatorer (en afslappet forestilling om spilteoretisk retfærdighed tillader det bygningsledervalg, selv i nærværelse af et ondsindet flertal, dog med en ikke-konstant nedre grænse for antallet af runder).
• uforudsigelighed: modstanderen lærer ikke den næste leder før et stykke tid T før lederen annoncerer næste blok.
• Entydighed: Der vælges nøjagtig én leder i hver plads.

Hemmeligt ledervalg

Hemmeligt ledervalg er et uforudsigeligt valg med T = 0. I denne proces er lederen ikke kendt af nogen, før den udgiver blokken. Dette eliminerer vinduet for et DoS-angreb fuldstændigt: før lederen afslører sig selv, ved angriberen ikke, hvem han skal angribe, hvilket gør sin bedste strategi til et tilfældigt gæt. Og efter at lederen har offentliggjort sin blok, er det for sent at angribe, fordi lederen allerede har opfyldt sit ansvar over for protokollen. 

Begrebet "efter at lederen har offentliggjort sin blok" er faktisk en forenkling, fordi vi ikke har øjeblikkelige udsendelser i den virkelige verden. En angriber med en stærk netværksposition vil muligvis bemærke, at en leder udsender en blokering først og hurtigt kan korrumpere lederen, oprette en anden blok og køre den originale udsendelse i front. 

Selvom dette er en meget stærk angribermodel, er der blevet foreslået forsvar mod den. Algorand foreslog sletninger model, hvor lederen faktisk er i stand til at slette nøglen, der er nødvendig for at signere blokken i dens slot før udsende det, så det er virkelig for sent at angribe, når lederen tager nogen offentlig handling. Thaddeus Dryja, Quanquan C. Liu og Neha Narula, tre forskere fra MIT Media Lab, foreslog at lederen beregner en VDF på sin blok før udsendelse, og sikrer, at en adaptiv angriber ikke kan konstruere en alternativ gyldig blok i tide til at få den accepteret for den ønskede slot.

Andre valgmetoder 

Den enkleste ledervalgsproces er runde Robin, hvor ledere vælges i deterministisk rækkefølge. På trods af at denne tilgang er forudsigelig og dermed udsat for DoS-angreb, er den velegnet til godkendte systemer, hvor validatorerne har god DoS-beskyttelse.

En leder kan også vælges ved hjælp af et output fra en ekstern tilfældigheds fyrtårn, hvis en er tilgængelig og har tillid til at være sikker. Desværre er det vanskeligt for konsensusdeltagerne selv at køre en distribueret tilfældighedsbeacon (DRB) protokol, da disse typisk antager en forestilling om pålidelig udsendelse eller konsensus, hvilket igen kræver ledervalg igen, hvilket indfører en cirkulær afhængighed.

Nuværende ledervalg i Ethereum er et godt casestudie. Hver ny leder beregner et Verifiable Randomness Function (VRF) output (en BLS-signatur på epokenummeret) og XORs værdien ind i blandingen. Værdien af ​​blandingen i slutningen af ​​epoken i definerer lederne og underudvalgene for epokens varighed i+2. Ledere og deres tidsplan er forudsigelige en epoke i forvejen (i øjeblikket ~6.4 min.). Protokollen er tilbøjelig til retfærdighedsangreb, da den sidste leder kan vælge at offentliggøre eller tilbageholde deres bidrag til blandingen og dermed påvirke resultatet af det næste valg med en smule. Hvis den sidste  k ledere samarbejder, kan de introducere k  stykker bias og gøre valg af ondsindede brugere mere sandsynligt. Ethereum Foundation arbejder aktivt på mere avancerede teknikker til ledervalg, som vi diskuterer nedenfor.

VRF-baseret ledervalg

En anden tilgang, pioneret af Algorand, Er en VRF-baseret ledervalg, hvilket indebærer, at hver validator privat beregner et VRF-output og kontrollerer, om outputtet falder under en tærskel. Denne procedure filtrerer allerede de fleste validatorer fra, da tærsklen er valgt sådan, at det er usandsynligt, at det falder under den. De få tilbageværende validatorer afslører deres VRF-output, og den med den laveste VRF-værdi vælges. Denne tilgang opnår perfekt uforudsigelighed (eller hemmeligholdelse), men den garanterer ikke unikhed. Nogle af validatorerne modtager muligvis ikke beskeder fra alle de potentielle ledere og kan antage, at den forkerte leder vandt valget, hvilket får disse validatorer til at forlade hovedkæden. 

VRF-evalueringen seedes med jævne mellemrum med output fra et tilfældighedsbeacon for at gøre det mindre forudsigeligt for validatorerne selv at se, hvilke slots de vil lede. Denne egenskab forhindrer en angriber, der stille kompromitterer validatoren, i at lære åbningen, når validatoren ville blive en leder, og lancere et angreb, når validatoren er ved at annoncere en blokering. Denne tilgang hjælper også med at forhindre bestikkelsesangreb, hvor en validator beviser over for eksterne parter, at den vil være leder i et bestemt slot og høster bestikkelse til gengæld for at udføre en opgave som leder (f.eks. blokering af en transaktion).

Sådanne tilgange, hvor antallet af valgte ledere er en tilfældig variabel, kaldes Probabilistisk ledervalg (PLE). PLE kan resultere i, at ingen ledere bliver valgt for en given plads. Dette svarer til at vælge en leder, der er ondsindet eller offline, idet pladsen i sidste ende vil ende med at blive sprunget over, hvilket reducerer effektiviteten af ​​konsensusprotokollen.

Men den største advarsel med PLE er, at flere ledere kan blive valgt, hvilket nødvendiggør en form for uafgjort procedure. Forbindelser udgør en risiko for konsensus, da en validator med et vindende input kan rapportere det til kun halvdelen af ​​netværket, hvilket potentielt kan forårsage uenighed hos den valgte leder. Desuden kan processer til at løse bånd tage ekstra tid og kommunikation, hvilket skader effektiviteten. Dfinity, diskuteret mere detaljeret i det første indlæg af denne serie, bruger et VRF-baseret tilfældighedsbeacon til at vælge en enkelt leder; det ofrer dog uforudsigeligheden at gøre det. Ideelt set bør enhver proces til at vælge en leder undgå bånd helt og stadig være uforudsigelig, hvilket fører os til den hellige gral af dette forskningsområde - Single Secret Leader Election.

Enkelt hemmeligt ledervalg 

Målet Enkelt hemmeligt ledervalg (SSLE) er at vælge en unik leder fra et sæt validatorer og samtidig bevare retfærdighed og uforudsigelighed. Protocol Labs præsenterede begrebet som en forskningsproblem, og Dan Boneh, Stanford-computerforskeren og a16z kryptoforskningsrådgiver, sammen med Saba Eskandarian, Lucjan Hanzlik og Nicola Greco, tilbød senere en formel definition af SSLE. Denne unikke egenskab undgår konsensusrisici og effektivitetsomkostninger som følge af uafgjorte procedurer. Helt konkret, Sarah Azouvi fra Protocol Labs og Danielle Cappelletti fra Politecnico di Torino, Vis at når SSLE bruges sammenlignet med PLE i en længste kæde protokol, kan blokke afsluttes væsentligt hurtigere (25 procent hurtigere med en modstander, der kontrollerer en tredjedel af indsatsen). Derfor er udvikling af en praktisk SSLE-protokol et vigtigt problem.

I den mest almindelige tilgang, som vi vil kalde shuffle-baseret (bruges i både det originale SSLE papir og et Ethereum SSLE-forslag), hver validator registrerer en nuntius det ser tilfældigt ud, men som de kan bevise, tilhører dem. Noncerne er derefter samlet i en liste. Listen blandes, således at nonces bliver fjernet fra de validatorer, der har indsendt dem; det vil sige, givet den blandede liste, kan ingen modstander fortælle, hvilken validator der har indsendt hvilken nonce. Et listeindeks vælges derefter i henhold til en offentlighed tilfældigheds fyrtårn, og lederen afslører sig selv ved at bevise, at nonce på det indeks på den blandede liste tilhører dem. 

Da der kun er valgt ét indeks, udsender den shuffle-baserede protokol altid en enestående leder. Fordi det tilfældige beacon er bygget til at udsende ensartede tilfældige værdier, er protokollen også retfærdig: hver validator har lige chance for at blive valgt. Ydermere, hvis blandingen udføres korrekt (dvs. ensartet tilfældigt), og nonces bliver ulinkbare til validatorernes identiteter, opnår denne protokol også uforudsigelighed.

Blanding er nødvendig, fordi blot at vælge et indeks fra den ikke blandede liste baseret på et tilfældigt beacon allerede ville give unikhed og retfærdighed, er uforudsigelighed sværere at opnå: Hvis en modstander ved, hvilken validator, der har indsendt hvilken nonce, ved den, hvem der har indsendt nonce ved den valgte indeks og kan identificere lederen. 

Disse følgende to tilgange blander listen på forskellige måder. Jo enklere er Ethereum SSLE forslag, hvori n validatorer indsender deres nonces via Tor for at fjerne linket til validatorernes identiteter fra deres nonces. Når alle validatorer har registreret sig, blandes listen ved hjælp af et offentligt tilfældighedsbeacon, og validatorerne bliver ledere i rækkefølgen af ​​den blandede liste. Selvom denne ordning er praktisk – skal valget kun afvikles én gang pr n slots – denne afhængighed af Tor kan være uønsket (som det er tilfældet med at stole på sikkerheden af ​​enhver ekstern protokol). Desuden er den ikke helt uforudsigelig: efter den første n-1 ledere afslører sig selv, finalen nth leder er kendt.

I stedet for at bruge Tor har det originale SSLE-papir hver validator registreret til valg i rækkefølge ved at tilføje dens nonce til listen, blande listen og genrandomisering noncerne. Denne re-randomisering betyder, at hver nonce er knyttet til en ny, ikke-linkbar streng, således at validatoren, som den tilhører, stadig kan bevise ejerskab af den re-randomiserede nonce. Gen-randomisering gør det således, at en modstander ikke kan se, hvilken position en bestemt nonce endte i efter shuffle, forudsat at mindst én shuffler er ærlig.

Selvom denne sekventielle blandingstilgang fra det originale SSLE-papir undgår afhængighed af Tor og opnår de formelle egenskaber ved SSLE, er det dyrt: hver gang en ny validator registrerer sig, skal de sende hele den blandede liste til blockchainen, gen-randomisere alle nonces, og give et bevis på, at de gjorde det ærligt, hvilket resulterer i lineær mængde kommunikation pr. validator. Med et uændret sæt validatorer skal dette gøres (amortiseres) én gang pr. valg, da lederen omregistrerer sig, når de har afsløret beviset for nonce. Papiret giver en afvejning mellem effektivitet og forudsigelighed: vi kan i stedet blande kun en mindre delmængde af listen, hvilket reducerer omkostningerne, hvis vi er villige til at tillade en lille mængde forudsigelighed. At opnå en god balance mellem effektivitet og sikkerhed er udfordrende, og som følge heraf mangler SSLE-protokoller endnu at blive brugt bredt i praksis. 

Denne sekventielle blandingstilgang kan bekvemt også bruges til at løse komitévalgsproblemet ved at bruge det tilfældige fyrtårn til at vælge k distinkte indekser fra listen som udvalgsmedlemmer. Dette er en flot præstation, da problemet ikke er trivielt løst af VRF-baserede tilgange, da man kører en probabilistisk VRF-baseret protokol k gange kan vælge en varierende udvalgsstørrelse afhængigt af tilfældigheden. 

Andre tilgange til SSLE

En anden shuffle-baseret tilgang er Adaptivt sikker SSLE fra Hedeselskabet. Denne konstruktion er lidt mere kompliceret, men opnår en stærkere forestilling om sikkerhed, der beskytter mod en adaptiv modstander i Algorands slettemodel. Denne modstander er adaptiv, idet den kan vælge, hvilke validatorer der skal korrumperes under protokollen, i modsætning til før protokollen starter. 

En yderligere udfordring i SSLE er at vælge hver validator med sandsynlighed proportional med deres indsats, snarere end ensartet tilfældigt. Blandingsbaserede protokoller kan naivt opnå dette ved at tillade hver validator at registrere flere nonce: en nonce for hver indsatsenhed, de har. Omkostningerne ved at blande stiger dog lineært med antallet af indsatsenheder S, bliver meget dyrt selv for realistiske indsatsfordelinger. En elegant MPC-baseret SSLE tilgang øger kompleksiteten kun med log S, og det undgår også behovet for en pålidelig opsætning eller tilfældighedsbeacon. Men sammenlignet med shuffling-baserede tilgange kræver det flere kommunikationsrunder (logaritmisk i antallet af deltagere) pr. valgt leder

***

Vi har opsummeret vores analyse i denne praktiske tabel.

	Fairness	Uforudsigelighed/ Hemmelighed*	Entydighed
Runde Robin	✓	✗	✓
Ideel tilfældigheds-fyrtårn	✓	✗	✓
Ethereums ledervalg (aktuelt)	✗	✗	✓
VRF-baseret ledervalg (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Round-robin beacon er fuldt forudsigelig, men i resten af ​​beacons ✗ betyder, at begrebet opnås i en vis begrænset grad: ideel-tilfældig-beacon er uforudsigelig, men modstanderen lærer outputtet på samme tid med den valgte leder, derfor kan den valgte leder blive angrebet, før den annoncerer en blokering; Etherums beacon er uforudsigelig op til ~6 min. og kan være en smule partisk for at skade retfærdigheden; Algorand vælger flere ledere med en lille sandsynlighed.

SSLE er en lovende retning, der opnår retfærdighed, uforudsigelighed og unikhed. To fremtrædende udfordringer, som dets vedtagelse står over for, er effektivitet og evnen til at imødekomme uensartede indsatsfordelinger. Ydermere antager de shuffle-baserede SSLE-tilgange, som vi fremhæver, eksistensen af ​​et uvildigt tilfældigt beacon, hvilket ikke er ligetil at opnå i praksis. Da SSLE først for nylig er blevet formelt defineret, vil vi sandsynligvis se forbedrede protokoller, der løser dets udfordringer i den nærmeste fremtid. 

***

Miranda Kristus er ph.d.-studerende i Computer Science ved Columbia University, hvor hun er medlem af Theory Group og Presidential Fellow. Hun er også forskningspraktikant hos a16z crypto.

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.