Ledarval från Randomness Beacons och andra strategier

Ledarval i en blockchain-inställning syftar till att välja den deltagare som ska bestämma nästa block som ska läggas till blockkedjan. Vanligtvis väljs en validator per lucka från uppsättningen av validatorer och får rätten att förlänga kedjan med ett nytt block i den luckan. (Vi antar att validerare håller korrekt tid och kommer överens om det aktuella slotnumret.) I den här artikeln utforskar vi strategier för randomiserat ledareval i konsensusprotokoll. (För mer om slumpmässighet i allmänhet, se vår tidigare artikel, Offentlig slumpmässighet och slumpmässighetDär vi tittade på fristående protokoll för att generera offentligt verifierbar och oförutsägbar slumpmässighet.) 

Varför ledareval är viktigt

Att välja ärliga och aktiva ledare är avgörande för en sund tillväxt av kedjan. Skadliga validerare bör inte kunna påverka ledarevalsprocessen för att göra sig själva till ledare oftare. Annars kan produktionen av block hamna i händerna på parter som kan censurera transaktioner eller stoppa blockkedjan helt. I konsensusprotokoll av längsta kedja kan en ledare som producerar ett ogiltigt block (eller inget block alls) få kedjan att tillfälligt splittras. I BFT-liknande konsensusprotokoll utlöser en dålig ledare ett underprotokoll för visningsändring som kommer att medföra en kommunikationsoverhead. 

Utskottsvalsalternativet

Val av kommitté är ett relaterat problem, där målet är att välja en enhetligt slumpmässig delmängd av validerare av någon fast storlek k. Denna funktionalitet är användbar i sin egen rätt eftersom underkommittéer ofta behövs i blockchain-inställningar för att minska storleken på valideringsuppsättningen för att få konsensus att gå snabbare (bland många exempel är Algorands sortering och Ethereums kommittéval). Men kommittéval är också användbart för ledareval, vilket gör att validerarna kan undvika att köra ett ledarevalsprotokoll igen om den valda ledaren inte dyker upp. Om det i stället för en ledare väljs ett utskott med fast ordning, kan den andra ledamoten bli ledare om den första inte är tillgänglig. 

Egenskaperna hos ett bra valprotokoll

I ett ledarvalsprotokoll bör ledarna vara oförutsägbara. Om en angripare får reda på vem den kommande ledaren är kan den starta en DoS-attack (Denial of Service) mot dem för att hindra dem från att publicera ett block. Angriparen kunde sedan ta ner nästa ledare och så vidare, vilket får blockkedjan att stanna. Oförutsägbarheten kan också stärkas för att säkerställa att valideraren själv inte lär sig när den ska leda, vilket kan vara viktigt för att förebygga mutor.

Ledarvalsprocessen bör ha följande tre egenskaper:

• Rättvisa: varje ärlig validator har en sannolikhet på 1/N att väljas från en uppsättning av N validatorer (en avslappnad uppfattning om spelteoretisk rättvisa tillåter val av byggnadsledare även i närvaro av en illvillig majoritet om än med en icke-konstant nedre gräns för antalet omgångar).
• oförutsägbarhet: motståndaren lär sig inte nästa ledare förrän en tid T innan ledaren tillkännager nästa blockering.
• unika: exakt en ledare väljs i varje plats.

Hemligt ledareval

Hemligt ledareval är ett oförutsägbart val med T = 0. I denna process är ledaren inte känd för någon förrän den publicerar blocket. Detta eliminerar fönstret för en DoS-attack helt: innan ledaren avslöjar sig själv vet angriparen inte vem han ska attackera, vilket gör sin bästa strategi till en slumpmässig gissning. Och efter att ledaren publicerat sin blockering är det för sent att attackera eftersom ledaren redan har uppfyllt sitt ansvar för protokollet. 

Begreppet "efter att ledaren publicerar sitt block" är faktiskt en förenkling, eftersom vi inte har omedelbara sändningar i den verkliga världen. En angripare med en stark nätverksposition kanske märker att en ledare sänder ett block först och snabbt kan korrumpera ledaren, skapa ett annat block och köra den ursprungliga sändningen i förväg. 

Även om detta är en mycket stark angriparmodell, har försvar föreslagits mot den. Algorand föreslog raderingsmodell, där ledaren faktiskt kan radera nyckeln som krävs för att signera blocket i dess lucka innan sänder det, så det är verkligen för sent att attackera när ledaren vidtar någon offentlig handling. Thaddeus Dryja, Quanquan C. Liu och Neha Narula, tre forskare från MIT Media Lab, föreslagen att ledaren beräknar en VDF på dess block innan sändning, vilket säkerställer att en adaptiv angripare inte kan konstruera ett alternativt giltigt block i tid för att få det accepterat för den önskade luckan.

Andra valmetoder 

Den enklaste ledarevalsprocessen är round robin, där ledare väljs i deterministisk ordning. Trots att detta tillvägagångssätt är förutsägbart och därmed är benäget för DoS-attacker, är det lämpligt för behöriga system där validerarna har bra DoS-skydd.

En ledare kan också väljas med hjälp av en extern utgång slumpmässighetsfyr, om en är tillgänglig och pålitlig för att vara säker. Tyvärr är det knepigt för konsensusdeltagarna att själva köra ett DRB-protokoll (distributed randomness beacon), eftersom dessa vanligtvis utgår från en föreställning om tillförlitlig sändning eller konsensus, vilket i sin tur kräver ledareval igen, vilket inför ett cirkulärt beroende.

Aktuella ledareval i Ethereum är en bra fallstudie. Varje ny ledare beräknar en Verifiable Randomness Function (VRF)-utgång (en BLS-signatur på epoknumret) och XORs värdet i mixen. Värdet av blandningen i slutet av epok i definierar ledarna och underkommittéerna för epokens varaktighet i+2. Ledare och deras schema är förutsägbara en epok i förväg (för närvarande ~6.4 min). Protokollet är benäget för rättvisa attacker, eftersom den sista ledaren kan välja att publicera eller hålla inne med sitt bidrag till mixen och därmed påverka resultatet av nästa val med en bit. Om den sista  k ledare samarbetar, kan de införa k  bitar av partiskhet och göra valet av skadliga användare mer sannolikt. Ethereum Foundation arbetar aktivt med mer avancerade tekniker för ledareval som vi diskuterar nedan.

VRF-baserat ledarval

Ett annat tillvägagångssätt, banbrytande av Algorand, Är ett VRF-baserat ledarval, vilket innebär att varje validator privat beräknar en VRF-utgång och kontrollerar om utgången faller under ett tröskelvärde. Denna procedur filtrerar redan bort de flesta validerare, eftersom tröskeln är vald så att det är osannolikt att falla under det. De få återstående validerarna avslöjar sina VRF-utgångar, och den som har det lägsta VRF-värdet väljs. Detta tillvägagångssätt uppnår perfekt oförutsägbarhet (eller sekretess), men det garanterar inte unikhet. Vissa av validerarna kanske inte får meddelanden från alla potentiella ledare och kan anta att fel ledare vann valet, vilket gör att dessa validerare lämnar huvudkedjan. 

VRF-utvärderingen seedas periodiskt med utdata från en slumpmässig beacon för att göra det mindre förutsägbart för validerarna själva att se vilka slots de kommer att leda. Den här egenskapen förhindrar en angripare som tyst kompromissar valideraren från att lära sig luckan när valideraren skulle bli ledare och starta en attack när valideraren är på väg att meddela ett blockering. Det här tillvägagångssättet hjälper också till att förhindra mutattacker, där en validator bevisar för externa parter att den kommer att vara ledare i en viss plats och skördar mutor i utbyte mot att utföra en uppgift som ledare (t.ex. blockera en transaktion).

Sådana tillvägagångssätt, där antalet valda ledare är en slumpmässig variabel, kallas Probabilistiskt ledareval (PLE). PLE kan resultera i att inga ledare väljs för en given plats. Detta motsvarar att välja en ledare som är illvillig eller offline eftersom luckan i slutändan kommer att hoppa över, vilket minskar effektiviteten i konsensusprotokollet.

Men den största varningen med PLE är att flera ledare kan väljas, vilket kräver någon form av oavgjort procedur. Kopplingar utgör en risk för konsensus, eftersom en validator med en vinnande input kan rapportera det till bara hälften av nätverket, vilket potentiellt kan orsaka oenighet hos den valda ledaren. Dessutom kan processer för att lösa band ta extra tid och kommunikation, vilket skadar effektiviteten. Dfinity, diskuteras mer i detalj i det första inlägget i denna serie, använder en VRF-baserad slumpmässighetsfyr för att välja en enda ledare; dock offrar det oförutsägbarheten att göra det. Helst bör varje process för att välja en ledare undvika band helt och fortfarande vara oförutsägbar, vilket leder oss till den heliga gralen för detta forskningsområde – Single Secret Leader Election.

Enstaka hemliga ledareval 

Målet med Enstaka hemliga ledareval (SSLE) är att välja en unik ledare från en uppsättning validerare samtidigt som rättvisa och oförutsägbarhet bibehålls. Protocol Labs presenterade idén som en forskningsproblem, och Dan Boneh, Stanfords datavetare och a16z kryptoforskningsrådgivare, tillsammans med Saba Eskandarian, Lucjan Hanzlik och Nicola Greco, erbjöd senare en formell definition av SSLE. Denna unika egenskap undviker konsensusrisker och effektivitetskostnader som uppstår från oavgjorda procedurer. Konkret, Sarah Azouvi, från Protocol Labs, och Danielle Cappelletti, från Politecnico di Torino, show att när SSLE används jämfört med PLE i ett längsta kedjeprotokoll, kan blocken slutföras betydligt snabbare (25 procent snabbare med en motståndare som kontrollerar en tredjedel av insatsen). Att utveckla ett praktiskt SSLE-protokoll är därför ett viktigt problem.

I det vanligaste tillvägagångssättet, som vi kommer att kalla shuffle-baserad (används i både original SSLE-papper och ett Ethereum SSLE-förslag), registrerar varje validator en nuncio som ser slumpmässigt ut, men som de kan bevisa tillhör dem. Nonserna sammanställs sedan till en lista. Listan blandas så att nonces kopplas bort från validerarna som skickade in dem; det vill säga, med tanke på den blandade listan kan ingen motståndare säga vilken validator som skickade vilket nonce. Ett listindex väljs sedan enligt en publik slumpmässighetsfyr, och ledaren avslöjar sig själv genom att bevisa att nonce vid det indexet på den blandade listan tillhör dem. 

Eftersom endast ett index väljs, matar det shuffle-baserade protokollet alltid ut en unika ledare. Eftersom den slumpmässiga fyren är byggd för att mata ut enhetliga slumpmässiga värden, är protokollet det också verkligt: varje validator har lika stor chans att bli vald. Dessutom, om blandningen görs på rätt sätt (dvs enhetligt slumpmässigt) och noncesna blir olänkade till validatorernas identiteter, uppnår detta protokoll också oförutsägbarhet.

Blandning är nödvändig eftersom att helt enkelt välja ett index från den icke blandade listan baserat på en slumpmässig beacon redan skulle ge unikhet och rättvisa, är oförutsägbarhet svårare att uppnå: Om en motståndare vet vilken validator som skickade vilket nonce, vet den vem som skickade nonce vid den valda index och kan identifiera ledaren. 

Dessa följande två tillvägagångssätt blandar listan på olika sätt. Det enklare är Ethereum SSLE-förslag, i vilken n validerare skickar in sina nonces via Tor för att koppla bort validatorernas identiteter från deras nonces. När alla validerare har registrerat sig blandas listan med en offentlig slumpmässig beacon, och validerarna blir ledare i den blandade listans ordning. Även om detta upplägg är praktiskt – måste valet genomföras endast en gång per n slots – detta beroende av Tor kan vara oönskat (som är fallet med att förlita sig på säkerheten för alla externa protokoll). Dessutom är det inte helt oförutsägbart: efter den första n-1 ledare avslöjar sig själva, finalen nth ledare är känd.

Istället för att använda Tor, har det ursprungliga SSLE-papperet varje valideringsregister för val i ordning genom att lägga till sin nonce på listan, blanda listan och randomisering på nytt noncesna. Denna omrandomisering innebär att varje nonce mappas till en ny, olänkningsbar sträng så att valideraren som den tillhör fortfarande kan bevisa äganderätten till den omslumpade nonce. Omrandomisering gör det så att en motståndare inte kan se vilken position en viss nonce hamnade i efter shuffle, förutsatt att minst en shuffler är ärlig.

Även om denna sekventiella blandningsmetod från det ursprungliga SSLE-dokumentet undviker beroende av Tor och uppnår de formella egenskaperna hos SSLE, är det dyrt: närhelst en ny validator registrerar sig måste de lägga upp hela den blandade listan till blockkedjan, slumpa alla nonces på nytt, och ge ett bevis på att de gjorde det ärligt, vilket resulterar i linjär kommunikation per validator. Med en oföränderlig uppsättning validerare måste detta göras (amorteras) en gång per val, eftersom ledaren omregistrerar sig när de har avslöjat beviset för nonce. Tidningen ger en avvägning mellan effektivitet och förutsägbarhet: vi kan istället blanda bara en mindre delmängd av listan, vilket minskar kostnaderna, om vi är villiga att tillåta en liten mängd förutsägbarhet. Att uppnå en bra balans mellan effektivitet och säkerhet är utmanande, och som ett resultat av detta har SSLE-protokoll ännu inte använts i stor utsträckning i praktiken. 

Lämpligen kan denna sekventiella blandningsmetod också användas för att lösa kommittévalsproblemet, genom att använda den slumpmässiga fyren för att välja k distinkta index från listan som kommittémedlemmar. Detta är en bra prestation, eftersom problemet inte är trivialt löst med VRF-baserade tillvägagångssätt, eftersom man kör ett probabilistiskt VRF-baserat protokoll k gånger kan välja en varierande kommittéstorlek beroende på slumpmässigheten. 

Andra metoder för SSLE

En annan blandningsbaserad metod är Adaptivt säker SSLE från DDH. Denna konstruktion är något mer komplicerad men uppnår en starkare föreställning om säkerhet, skyddar mot en adaptiv motståndare i Algorands raderingsmodell. Denna motståndare är anpassningsbar genom att den kan välja vilka validatorer som ska korrumperas under protokollet, i motsats till innan protokollet startar. 

En ytterligare utmaning i SSLE är att välja varje validator med sannolikhet proportionell mot deras insats, snarare än enhetligt slumpmässigt. Blandningsbaserade protokoll kan på ett naivt sätt uppnå detta genom att tillåta varje validator att registrera flera nonce: en nonce för varje insatsenhet de har. Kostnaden för att blanda ökar dock linjärt med antalet insatsenheter S, blir mycket dyr även för realistiska insatsfördelningar. En elegant MPC-baserad SSLE tillvägagångssättet ökar komplexiteten endast med log S, och det undviker också behovet av en pålitlig installation eller slumpmässig beacon. Jämfört med blandningsbaserade tillvägagångssätt kräver det dock fler kommunikationsomgångar (logaritmiskt i antalet deltagare) per vald ledare

***

Vi har sammanfattat vår analys i den här praktiska tabellen.

	Rättvisa	oförutsägbarhet/ Sekretess*	unika
Round-robin	✓	✗	✓
Idealisk slumpmässighetsfyr	✓	✗	✓
Ethereums ledareval (nuvarande)	✗	✗	✓
VRF-baserat ledarval (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Round-robin beacon är helt förutsägbar, men i resten av beacons ✗ innebär att föreställningen uppnås upp till en viss begränsad grad: ledstjärna för ideal-slumpmässighet är oförutsägbar men motståndaren lär sig resultatet samtidigt med den valda ledaren, därför kan den valda ledaren attackeras innan den tillkännager en blockering; Etherums beacon är oförutsägbar upp till ~6 min och kan vara något partisk för att skada rättvisan; Algorand väljer flera ledare med liten sannolikhet.

SSLE är en lovande riktning som uppnår rättvisa, oförutsägbarhet och unikhet. Två framträdande utmaningar inför antagandet är effektivitet och förmågan att hantera olikformiga insatsersfördelningar. Dessutom antar de shuffle-baserade SSLE-metoderna som vi lyfter fram att det finns en opartisk slumpmässig beacon, vilket inte är enkelt att uppnå i praktiken. Eftersom SSLE först nyligen har formellt definierats, kommer vi sannolikt att se förbättrade protokoll som tar itu med dess utmaningar inom en snar framtid. 

***

Miranda Kristus är doktorand i datavetenskap vid Columbia University, där hon är medlem i teorigruppen och presidentstipendiat. Hon är också forskarpraktikant på a16z crypto.

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.