Leiderverkiezing op basis van willekeurige bakens en andere strategieën

Leiderverkiezing in een blockchain-omgeving heeft tot doel de deelnemer te selecteren die het volgende blok zal bepalen dat aan de blockchain moet worden toegevoegd. Meestal wordt één validator per slot gekozen uit de set validators en krijgt het recht om de keten uit te breiden met een nieuw blok in dat slot. (We gaan ervan uit dat validators de tijd nauwkeurig bijhouden en het eens zijn over het huidige slotnummer.) In dit artikel verkennen we strategieën voor gerandomiseerde leiderverkiezing in consensusprotocollen. (Zie ons eerdere artikel voor meer informatie over willekeur in het algemeen, Openbare willekeur en willekeurbakens, Waar we hebben gekeken naar stand-alone protocollen voor het genereren van publiek verifieerbare en onvoorspelbare willekeur.) 

Waarom leiderverkiezing ertoe doet

Het kiezen van eerlijke en actieve leiders is cruciaal voor een gezonde groei van de keten. Kwaadwillende validators mogen het verkiezingsproces van leiders niet beïnvloeden om zichzelf vaker leiders te maken. Anders zou de productie van blokken in handen kunnen vallen van partijen die transacties kunnen censureren of de blockchain helemaal kunnen stopzetten. In consensusprotocollen in de stijl van de langste keten kan een leider die een ongeldig blok (of helemaal geen blok) produceert, ervoor zorgen dat de keten tijdelijk splitst. In consensusprotocollen in BFT-stijl activeert een slechte leider een subprotocol voor het wijzigen van de weergave dat een communicatieoverhead met zich meebrengt. 

Het alternatief voor de commissieverkiezing

Commissieverkiezing is een gerelateerd probleem, waarbij het doel is om een ​​uniform willekeurige subset van de validators van een vaste grootte te selecteren k. Deze functionaliteit is op zichzelf nuttig omdat subcommissies vaak nodig zijn in blockchain-instellingen om de grootte van de validatorset te verkleinen om de consensus sneller te laten verlopen (onder vele voorbeelden zijn Algorands sortering en Ethereum's commissieselectie). Maar commissieverkiezing is ook nuttig voor de verkiezing van leiders, waardoor de validators kunnen voorkomen dat een verkiezingsprotocol voor leiders opnieuw wordt uitgevoerd als de gekozen leider niet komt opdagen. Als in plaats van een leider een commissie wordt gekozen met een vaste volgorde, kan het tweede commissielid leider worden als het eerste niet beschikbaar is. 

De eigenschappen van een goed verkiezingsprotocol

In een leidersverkiezingsprotocol moeten de leiders onvoorspelbaar zijn. Als een aanvaller erachter komt wie de toekomstige leider is, kan hij een Denial of Service-aanval (DoS) op hem uitvoeren om te voorkomen dat hij een blokkade publiceert. De aanvaller kan dan de volgende leider uitschakelen, enzovoort, waardoor de blockchain tot stilstand komt. Onvoorspelbaarheid kan ook worden versterkt om ervoor te zorgen dat de validator zelf niet leert wanneer hij gaat leiden, wat belangrijk kan zijn voor het voorkomen van omkoping.

Het verkiezingsproces van de leider moet de volgende drie eigenschappen hebben:

• Eerlijkheid: elke eerlijke validator heeft een kans van 1/N te kiezen uit een set van N validators (een ontspannen begrip van speltheoretische eerlijkheid staat toe het opbouwen van leiderverkiezing, zelfs in de aanwezigheid van een kwaadwillende meerderheid, zij het met een niet-constante ondergrens voor het aantal rondes).
• Onvoorspelbaarheid: de tegenstander leert de volgende leider pas enige tijd T voordat de leider het volgende blok aankondigt.
• Uniciteit: in elk slot wordt precies één leider gekozen.

Geheime leidersverkiezing

Geheime leiderverkiezing is een onvoorspelbare verkiezing met T = 0. In dit proces is de leider bij niemand bekend totdat hij het blok publiceert. Dit elimineert het venster voor een DoS-aanval volledig: voordat de leider zichzelf onthult, weet de aanvaller niet wie hij moet aanvallen, waardoor zijn beste strategie een willekeurige gok wordt. En nadat de leider zijn blokkade heeft gepubliceerd, is het te laat om aan te vallen, omdat de leider zijn verantwoordelijkheid voor het protocol al heeft vervuld. 

Het idee van "nadat de leider zijn blok publiceert" is eigenlijk een vereenvoudiging, omdat we geen onmiddellijke uitzending hebben in de echte wereld. Een aanvaller met een sterke netwerkpositie merkt misschien dat een leider eerst een blok uitzendt en kan de leider snel corrumperen, een ander blok maken en de oorspronkelijke uitzending naar voren halen. 

Hoewel dit een zeer sterk aanvallermodel is, zijn er verdedigingsmechanismen tegen voorgesteld. Algorand stelde de uitwissingsmodel, waarin de leider daadwerkelijk de sleutel kan wissen die nodig is om het blok in zijn slot te ondertekenen vaardigheden het uitzenden, dus het is echt te laat om aan te vallen tegen de tijd dat de leider openbare actie onderneemt. Thaddeus Dryja, Quanquan C. Liu en Neha Narula, drie onderzoekers van het MIT Media Lab, voorgestelde dat de leider een VDF op zijn blok berekent voordat het wordt uitgezonden, zodat een adaptieve aanvaller niet op tijd een alternatief geldig blok kan bouwen om het te laten accepteren voor het gewenste slot.

Andere verkiezingsmethoden 

Het eenvoudigste verkiezingsproces voor leiders is ronde robin, waar leiders in deterministische volgorde worden gekozen. Ondanks dat deze aanpak voorspelbaar is en dus gevoelig is voor DoS-aanvallen, is het geschikt voor systemen met toestemming waarbij de validators een goede DoS-bescherming hebben.

Een leider kan ook worden gekozen met behulp van een output van een externe willekeurig baken, als er een beschikbaar en vertrouwd is om veilig te zijn. Helaas is het lastig voor de consensusdeelnemers om zelf een gedistribueerd randomness beacon (DRB)-protocol uit te voeren, aangezien deze meestal uitgaan van een notie van betrouwbare uitzending of consensus, wat op zijn beurt weer leiderverkiezing vereist, wat een circulaire afhankelijkheid introduceert.

Actueel leiderverkiezing in Ethereum is een goede casus. Elke nieuwe leider berekent een Verifiable Randomness Function (VRF)-output (een BLS-handtekening op het epoch-nummer) en XORs de waarde in de mix. De waarde van de mix aan het einde van het tijdperk i definieert de leiders en de subcommissies voor de duur van het tijdperk i+2. Leiders en hun schema zijn één tijdvak van tevoren voorspelbaar (momenteel ~ 6.4 min). Het protocol is vatbaar voor aanvallen op eerlijkheid, aangezien de laatste leider ervoor kan kiezen om zijn bijdrage aan de mix te publiceren of achter te houden en zo de uitslag van de volgende verkiezingen een klein beetje te beïnvloeden. Als de laatste  k leiders samenspannen, kunnen ze introduceren k  stukjes vooringenomenheid en maken de verkiezing van kwaadwillende gebruikers waarschijnlijker. De Ethereum Foundation werkt actief aan meer geavanceerde technieken voor het kiezen van leiders die we hieronder bespreken.

Op VRF gebaseerde leiderverkiezing

Een andere benadering, gepionierd door Algorand, is een Op VRF gebaseerde leiderverkiezing, waarbij elke validator privé een VRF-output berekent en controleert of de output onder een drempel valt. Deze procedure filtert al de meeste validators eruit, aangezien de drempel zo is gekozen dat het onwaarschijnlijk is dat u eronder komt. De weinige overgebleven validators onthullen hun VRF-outputs en degene met de laagste VRF-waarde wordt gekozen. Deze aanpak bereikt perfecte onvoorspelbaarheid (of geheimhouding), maar garandeert geen uniciteit. Sommige validators ontvangen mogelijk geen berichten van alle potentiële leiders en gaan er mogelijk van uit dat de verkeerde leider de verkiezing heeft gewonnen, waardoor deze validators zich afsplitsen van de hoofdketen. 

De VRF-evaluatie wordt periodiek gezaaid met de uitvoer van een willekeursbaken om het minder voorspelbaar te maken voor de validators zelf om te zien welke slots ze gaan leiden. Deze eigenschap voorkomt dat een aanvaller die stilletjes de validator compromitteert, het slot leert wanneer de validator een leider zou worden en een aanval start wanneer de validator op het punt staat een blokkering aan te kondigen. Deze aanpak helpt ook bij het voorkomen van omkopingsaanvallen, waarbij een validator aan externe partijen bewijst dat hij een leider zal zijn in een bepaald slot en steekpenningen ontvangt in ruil voor het voltooien van een taak als leider (bijvoorbeeld het blokkeren van een transactie).

Dergelijke benaderingen, waarbij het aantal gekozen leiders een willekeurige variabele is, worden genoemd Probabilistische leiderverkiezing (PLE). PLE kan ertoe leiden dat er geen leiders worden gekozen voor een bepaald slot. Dit komt overeen met het kiezen van een leider die kwaadaardig of offline is, in die zin dat het slot uiteindelijk zal worden overgeslagen, waardoor de efficiëntie van het consensusprotocol afneemt.

Maar het grootste voorbehoud bij PLE is dat er meerdere leiders kunnen worden gekozen, waardoor een soort tie-breaking-procedure nodig is. Stropdas vormt een risico voor consensus, aangezien een validator met een winnende input dit mogelijk aan slechts de helft van het netwerk rapporteert, wat mogelijk onenigheid veroorzaakt bij de gekozen leider. Bovendien kunnen processen voor het oplossen van banden extra tijd en communicatie vergen, wat ten koste gaat van de efficiëntie. Dfinity, nader besproken in het eerste bericht van deze serie gebruikt een VRF-gebaseerd willekeursbaken om een ​​enkele leider te kiezen; het offert echter onvoorspelbaarheid op om dit te doen. Idealiter zou elk proces voor het kiezen van een leider banden volledig moeten vermijden en toch onvoorspelbaar moeten zijn, wat ons leidt naar de heilige graal van dit onderzoeksgebied: Single Secret Leader Election.

Enkele geheime leiderverkiezing 

Doel van Enkele geheime leiderverkiezing (SSLE) is het selecteren van een unieke leider uit een reeks validators met behoud van eerlijkheid en onvoorspelbaarheid. Protocol Labs presenteerde het idee als een onderzoeks probleem, en Dan Boneh, de computerwetenschapper van Stanford en a16z crypto-onderzoeksadviseur, met Saba Eskandarian, Lucjan Hanzlik en Nicola Greco, boden later een formele definitie van SSLE. Deze uniciteitseigenschap vermijdt de consensusrisico's en efficiëntiekosten die voortvloeien uit tie-breaking-procedures. Concreet, Sarah Azouvi, van Protocol Labs, en Danielle Cappelletti, van Politecnico di Torino, tonen dat wanneer SSLE wordt gebruikt in vergelijking met PLE in een protocol met de langste keten, blokken aanzienlijk sneller kunnen worden voltooid (25 procent sneller met een tegenstander die een derde van de inzet controleert). Het ontwikkelen van een praktisch SSLE-protocol is dus een belangrijk probleem.

In de meest gebruikelijke benadering, die we zullen noemen shuffle-gebaseerd (gebruikt in zowel het originele SSLE-papier als een Ethereum SSLE-voorstel), registreert elke validator a nuntius dat er willekeurig uitziet, maar waarvan ze kunnen bewijzen dat het van hen is. De nonces worden vervolgens gebundeld in een lijst. De lijst wordt zo geschud dat de nonces losgekoppeld worden van de validators die ze hebben ingediend; dat wil zeggen, gezien de geschudde lijst kan geen enkele tegenstander zeggen welke validator welke nonce heeft ingediend. Vervolgens wordt een lijstindex gekozen op basis van een publiek willekeurig baken, en de leider onthult zichzelf door te bewijzen dat de nonce bij die index van de geschudde lijst van hen is. 

Aangezien er slechts één index wordt gekozen, geeft het op shuffle gebaseerde protocol altijd een unieke leider. Omdat het willekeurige baken is gebouwd om uniform willekeurige waarden uit te voeren, is het protocol dat ook eerlijk: elke validator heeft een gelijke kans om gekozen te worden. Bovendien, als het schudden correct wordt uitgevoerd (dwz uniform en willekeurig) en de nonces niet meer kunnen worden gekoppeld aan de identiteit van de validators, bereikt dit protocol ook onvoorspelbaarheid.

Schudden is nodig omdat het simpelweg kiezen van een index uit de niet-geschudde lijst op basis van een willekeurig baken al uniekheid en eerlijkheid zou geven, maar onvoorspelbaarheid is moeilijker te bereiken: als een tegenstander weet welke validator welke nonce heeft ingediend, weet hij wie de nonce heeft ingediend op de gekozen index en kan de leider identificeren. 

Deze volgende twee benaderingen schudden de lijst op verschillende manieren door elkaar. Hoe eenvoudiger is de Ethereum SSLE-voorstel, waarin n validators dienen hun nonces in via Tor om de identiteit van de validators los te koppelen van hun nonces. Zodra alle validators zich hebben geregistreerd, wordt de lijst geschud met behulp van een openbaar willekeursbaken en worden de validators leiders in de volgorde van de geschudde lijst. Hoewel dit schema praktisch is, hoeft de verkiezing maar één keer per keer te worden gehouden n slots – deze afhankelijkheid van Tor kan ongewenst zijn (zoals het geval is bij het vertrouwen op de beveiliging van een extern protocol). Bovendien is het niet perfect onvoorspelbaar: na de eerste n-1 leiders onthullen zich, de finale nth leider is bekend.

In plaats van Tor te gebruiken, laat het originele SSLE-papier elke validator zich achtereenvolgens registreren voor verkiezing door zijn nonce aan de lijst toe te voegen, de lijst door elkaar te schudden en opnieuw willekeurig maken de nonnen. Deze herrandomisering betekent dat elke nonce wordt toegewezen aan een nieuwe, niet-koppelbare reeks, zodat de validator waartoe deze behoort nog steeds kan bewijzen dat hij eigenaar is van de opnieuw gerandomiseerde nonce. Opnieuw willekeurig maken zorgt ervoor dat een tegenstander niet kan zeggen in welke positie een bepaalde nonce terecht is gekomen na het schudden, ervan uitgaande dat ten minste één schudder eerlijk is.

Hoewel deze sequentiële shuffling-benadering van het originele SSLE-document afhankelijkheid van Tor vermijdt en de formele eigenschappen van SSLE bereikt, is het duur: telkens wanneer een nieuwe validator zich registreert, moet hij de volledige geschudde lijst naar de blockchain posten, alle nonces opnieuw willekeurig maken en een bewijs leveren dat ze dit eerlijk hebben gedaan, wat resulteert in een lineaire hoeveelheid communicatie per validator. Met een onveranderlijke set validators moet dit eenmaal per verkiezing worden gedaan (afgeschreven), aangezien de leider zich opnieuw registreert zodra ze het bewijs voor de nonce hebben onthuld. Het artikel geeft een instelbare afweging tussen efficiëntie en voorspelbaarheid: we kunnen in plaats daarvan slechts een kleinere subset van de lijst door elkaar schudden, waardoor de kosten worden verlaagd, als we bereid zijn een kleine hoeveelheid voorspelbaarheid toe te staan. Het bereiken van een goede balans tussen efficiëntie en veiligheid is een uitdaging, en als gevolg hiervan moeten SSLE-protocollen in de praktijk nog veel worden gebruikt. 

Handig is dat deze volgorde van schudden ook kan worden gebruikt om het commissieverkiezingsprobleem op te lossen, door het willekeurige baken te gebruiken om k verschillende indices uit de lijst als commissieleden te kiezen. Dit is een mooie prestatie, aangezien het probleem niet triviaal wordt opgelost door VRF-gebaseerde benaderingen, aangezien het uitvoeren van een probabilistisch VRF-gebaseerd protocol k tijden kunnen een variërende commissiegrootte kiezen, afhankelijk van de willekeur. 

Andere benaderingen van SSLE

Een andere op shuffle gebaseerde benadering is Adaptief beveiligde SSLE van DDH. Deze constructie is iets ingewikkelder, maar zorgt voor een sterker idee van veiligheid, bescherming tegen een adaptieve tegenstander in het uitwissingsmodel van Algorand. Deze tegenstander is adaptief in die zin dat hij kan kiezen welke validators hij wil corrumperen tijdens het protocol, in tegenstelling tot voordat het protocol start. 

Een andere uitdaging bij SSLE is het kiezen van elke validator met waarschijnlijkheid die evenredig is aan hun inzet, in plaats van uniform willekeurig. Op shuffling gebaseerde protocollen kunnen dit naïef bereiken door elke validator meerdere nonces te laten registreren: één nonce voor elke eenheid van inzet die ze hebben. De kosten van het schudden nemen echter lineair toe met het aantal inzeteenheden S, erg duur worden, zelfs voor realistische inzetverdelingen. Een elegante MPC-gebaseerde SSLE benadering heeft complexiteit die alleen toeneemt met log S, en het vermijdt ook de noodzaak van een vertrouwde setup of willekeursbaken. In vergelijking met op shuffle gebaseerde benaderingen zijn er echter meer communicatierondes nodig (logaritmisch in het aantal deelnemers) per gekozen leider

***

We hebben onze analyse samengevat in deze handige tabel.

	Eerlijkheid	Onvoorspelbaarheid/ Geheimhouding*	Uniciteit
Round-robin	✓	✗	✓
Ideale willekeur-baken	✓	✗	✓
Ethereum's leiderverkiezing (huidig)	✗	✗	✓
Op VRF gebaseerde leiderverkiezing (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Het round-robin-baken is volledig voorspelbaar, maar in de rest van de bakens ✗ betekent dat het begrip tot op zekere hoogte wordt bereikt: baken met ideale willekeur is onvoorspelbaar, maar de tegenstander leert de output tegelijkertijd met de gekozen leider, vandaar dat de gekozen leider kan worden aangevallen voordat hij een blokkade aankondigt; Het baken van Etherum is onvoorspelbaar tot ~6 min en kan enigszins vertekend zijn om de eerlijkheid te schaden; Algorand kiest meerdere leiders met een kleine kans.

SSLE is een veelbelovende richting, waarbij eerlijkheid, onvoorspelbaarheid en uniciteit worden bereikt. Twee prominente uitdagingen waarmee de acceptatie wordt geconfronteerd, zijn efficiëntie en het vermogen om niet-uniforme verdelingen van aandelen op te vangen. Bovendien gaan de op shuffle gebaseerde SSLE-benaderingen die we benadrukken uit van het bestaan ​​van een onbevooroordeeld willekeurig baken, wat in de praktijk niet eenvoudig te bereiken is. Aangezien SSLE pas onlangs formeel is gedefinieerd, zullen we in de nabije toekomst waarschijnlijk verbeterde protocollen zien die de uitdagingen aanpakken. 

***

Miranda Christus is een PhD-student Computer Science aan Columbia University, waar ze lid is van de Theory Group en een Presidential Fellow. Ze is ook een onderzoeksstagiair bij a16z crypto.

Jozef Boneau is een onderzoekspartner bij a16z crypto. Zijn onderzoek richt zich op toegepaste cryptografie en blockchain-beveiliging. Hij heeft cryptocurrency-cursussen gegeven aan de Universiteit van Melbourne, NYU, Stanford en Princeton, en behaalde een doctoraat in computerwetenschappen aan de Universiteit van Cambridge en BS/MS-graden van Stanford.

Valeria Nikolaenko is een onderzoekspartner bij a16z crypto. Haar onderzoek richt zich op cryptografie en blockchain-beveiliging. Ze heeft ook gewerkt aan onderwerpen als langeafstandsaanvallen in PoS-consensusprotocollen, handtekeningschema's, post-kwantumbeveiliging en multi-party computation. Ze is gepromoveerd in cryptografie aan de Stanford University onder adviseurschap van professor Dan Boneh, en werkte aan de Diem-blockchain als onderdeel van het kernonderzoeksteam.

***

Editor: Tim Sullivan

***

De standpunten die hier naar voren worden gebracht, zijn die van het individuele personeel van AH Capital Management, LLC (“a16z”) dat wordt geciteerd en zijn niet de standpunten van a16z of haar gelieerde ondernemingen. Bepaalde informatie in dit document is verkregen uit externe bronnen, waaronder van portefeuillebedrijven van fondsen die worden beheerd door a16z. Hoewel ontleend aan bronnen die betrouwbaar worden geacht, heeft a16z dergelijke informatie niet onafhankelijk geverifieerd en doet het geen uitspraken over de blijvende nauwkeurigheid van de informatie of de geschiktheid ervan voor een bepaalde situatie. Bovendien kan deze inhoud advertenties van derden bevatten; a16z heeft dergelijke advertenties niet beoordeeld en keurt de daarin opgenomen advertentie-inhoud niet goed.

Deze inhoud is uitsluitend bedoeld voor informatieve doeleinden en mag niet worden beschouwd als juridisch, zakelijk, investerings- of belastingadvies. U dient hierover uw eigen adviseurs te raadplegen. Verwijzingen naar effecten of digitale activa zijn alleen voor illustratieve doeleinden en vormen geen beleggingsaanbeveling of aanbod om beleggingsadviesdiensten te verlenen. Bovendien is deze inhoud niet gericht op of bedoeld voor gebruik door beleggers of potentiële beleggers, en mag er in geen geval op worden vertrouwd bij het nemen van een beslissing om te beleggen in een fonds dat wordt beheerd door a16z. (Een aanbod om te beleggen in een a16z-fonds wordt alleen gedaan door middel van het onderhandse plaatsingsmemorandum, de inschrijvingsovereenkomst en andere relevante documentatie van een dergelijk fonds en moet in hun geheel worden gelezen.) Alle genoemde beleggingen of portefeuillebedrijven waarnaar wordt verwezen, of beschreven zijn niet representatief voor alle investeringen in voertuigen die door a16z worden beheerd, en er kan geen garantie worden gegeven dat de investeringen winstgevend zullen zijn of dat andere investeringen die in de toekomst worden gedaan vergelijkbare kenmerken of resultaten zullen hebben. Een lijst van investeringen die zijn gedaan door fondsen die worden beheerd door Andreessen Horowitz (met uitzondering van investeringen waarvoor de uitgevende instelling geen toestemming heeft gegeven aan a16z om openbaar te maken, evenals onaangekondigde investeringen in openbaar verhandelde digitale activa) is beschikbaar op https://a16z.com/investments /.

De grafieken en grafieken die hierin worden verstrekt, zijn uitsluitend bedoeld voor informatieve doeleinden en er mag niet op worden vertrouwd bij het nemen van een investeringsbeslissing. In het verleden behaalde resultaten zijn geen indicatie voor toekomstige resultaten. De inhoud spreekt alleen vanaf de aangegeven datum. Alle projecties, schattingen, voorspellingen, doelstellingen, vooruitzichten en/of meningen die in deze materialen worden uitgedrukt, kunnen zonder voorafgaande kennisgeving worden gewijzigd en kunnen verschillen of in strijd zijn met meningen van anderen. Zie https://a16z.com/disclosures voor aanvullende belangrijke informatie.