Openbare willekeur en willekeurbakens

Openbare willekeur is een essentieel onderdeel van veel real-world beveiligingsprotocollen. In sommige toepassingen, zoals gok- en multiplayer-spellen, voegt willekeurigheid toe aan plezier. In andere toepassingen biedt willekeur een eerlijke manier om niet-deelbare middelen toe te wijzen, variërend van groene kaarten tot de toewijzing van rechters van circuits aan zaken, tot deelname aan sporttoernooien. Het wordt ook gebruikt om toe te wijzen negatief middelen, zoals belastingcontroles of secundair veiligheidsonderzoek op de luchthaven.

Traditioneel vertrouwden we op vertrouwde autoriteiten om willekeur voor deze protocollen te genereren, maar in de web3-wereld moeten we het beter doen. In dit bericht onderzoeken we benaderingen voor het bouwen van openbaar verifieerbare willekeur via gedistribueerde willekeurigheidsbakens en bespreek vervolgens enkele on-chain-toepassingen. (Deel II, die binnenkort verschijnt, zal specifiek gericht zijn op de verkiezing van leiders, terwijl het een beoordeling geeft van alternatieve benaderingen voor de verkiezing van leiders.) 

Gewenste eigenschappen

Het genereren van willekeurige getallen is een notoir subtiele taak. Er zijn bijvoorbeeld veel cryptografische sleutels gelekt omdat ze vertrouwde op een defecte generator voor willekeurige getallen (waarvoor Cloudflare's wall of lavalampen zou hebben gediend als een creatieve beperking). Dat is gewoon privé willekeur, echter, waar slechts één partij het hoeft te genereren en te gebruiken.

Publieke willekeur is daarentegen een proces met meerdere partijen, wat de moeilijkheid aanzienlijk vergroot. Een goed protocol voor het produceren van openbare willekeur heeft de volgende beveiligingseigenschappen:

• Onpartijdig: Geen enkele aanvaller, of coalitie van aanvallers, mag de output beïnvloeden. 
• Betrouwbaar: Geen enkele aanvaller mag voorkomen dat het protocol uitvoer produceert.
• te verifiëren: Iedereen kan de protocoluitvoer gemakkelijk verifiëren en zou dezelfde uitvoer moeten zien als alle anderen.
• Onvoorspelbare: Als het protocol uitvoer op tijd produceert T₁, niemand zou voor enige tijd iets over de output moeten kunnen voorspellen T₀<T₁, idealiter met T₀ erg dicht bij T₁.

Onvoorspelbaarheid is een zwakkere eigenschap dan onvoorspelbaarheid, omdat elk protocol dat onvoorspelbaar is, onpartijdig moet zijn. Computerwetenschappers zouden onpartijdigheid zeggen vermindert tot onvoorspelbaarheid, want als je kunt vooroordelen, kun je voorspellen. Maar soms zullen we er afzonderlijk over willen redeneren omdat ze op verschillende veronderstellingen kunnen vertrouwen - een oneerlijke meerderheid kan bijvoorbeeld de uitkomst voorspellen, maar deze niet vertekenen.

Naast deze eigenschappen moet het protocol efficiënt kunnen worden uitgevoerd en een groot aantal willekeurige bits produceren. (In de praktijk is het vaak voldoende voor toepassingen om 128 willekeurige bits te produceren, die ze gebruiken om een ​​pseudo-willekeurige nummergenerator [PNRG] te seeden om meer bits uit te voeren als dat nodig is. Er moet echter onvoorspelbaarheid gelden voor elk afzonderlijk bit van de uitvoer om bruikbaar te zijn voor dergelijke toepassingen zoals loterijen of toewijzing van middelen.) Het protocol zou idealiter ook efficiënt moeten zijn in termen van communicatie- en rekenkosten.

Verschillende protocollen kunnen deze eigenschappen onder verschillende omstandigheden bereiken. Sommige protocollen kunnen bijvoorbeeld onbevooroordeeld zijn door een coalitie van f₁ kwaadaardige knooppunten en onvoorspelbaar door een coalitie van f₂<f₁ kwaadaardige knooppunten. Er zijn ook verschillende gradaties van vooringenomenheid. In sommige protocollen kan een deelnemer bijvoorbeeld de uitvoer met "één bit" vertekenen, wat betekent dat hij kan kiezen tussen een van de twee mogelijke uitvoer. Met andere aanvallen kunnen ze de uitvoer mogelijk volledig herstellen. Meestal willen we echter helemaal geen vooringenomenheid (of voorspelbaarheid) tolereren.

Het cryptografische ideaal: Randomness bakens

Cryptografen beginnen vaak met het bedenken van een ideale oplossing voor hun problemen. In het geval van openbare willekeur, a willekeurig baken is een geïdealiseerde service die regelmatig willekeurige uitvoer produceert die aan alle noodzakelijke beveiligingsvereisten voldoet.

Zo'n geïdealiseerd willekeurig baken, vergelijkbaar met andere cryptografische abstracties - zoals willekeurige orakels of het generieke groepsmodel - bestaat niet in de echte wereld. Maar het is een nuttig doel om naar te streven en een nuttig model om te redeneren over protocollen die berusten op openbare willekeur. 

We kunnen enkele benaderingen van een ideaal willekeurig baken beschouwen.

• Gecentraliseerde bakens: De eenvoudigste manier om goede willekeur te genereren is via een gecentraliseerde derde partij met services zoals: NIST willekeurig baken or random.org, die willekeur genereert uit atmosferische ruis en is geaccrediteerd voor gebruik bij gokken. Deze afhankelijkheid van een derde partij ondermijnt de filosofie van decentralisatie volledig. In het bovenstaande voorbeeld moeten we er inderdaad op vertrouwen dat de relevante organisaties willekeur correct genereren, zonder enig cryptografisch bewijs.
• Fysieke willekeur wordt weergegeven: Veel traditionele loterijen vertrouwen op een openbare vertoning, waaronder bijvoorbeeld iemand die in een container met pingpongballen reikt met verschillende nummers erop. Helaas zijn deze vaak gemakkelijk te manipuleren. Bijvoorbeeld, bepaalde ballen kunnen in een vriezer worden geplaatst en de selector kan worden verteld om de koude te kiezen.
• Natuurlijke bakens: Een algemeen idee is om willekeurige natuurlijke fenomenen zoals het weer of kosmische achtergrondstraling als baken te gebruiken. Helaas bieden alle voorgestelde bronnen geen sterke consensus. Verschillende waarnemers zullen iets andere waarden zien, wat een herintroductie van een vertrouwde partij vereist om een ​​officiële meting uit te voeren, met alle nadelen van een gecentraliseerd baken.
• Semi-gecentraliseerde bakens: Een betere benadering zou zijn om de willekeur te krijgen van: Bitcoin-blokheaders rechtstreeks of van slotkoersen van de aandelen, die gemakkelijker publiekelijk te verifiëren is en moeilijker voor één partij om volledig te controleren. Toch bestaan ​​er nog steeds subtiele aanvallen op beide proof-of-work blockchain-willekeurigheid en willekeur van aandelenkoersen. Met blockchain-headers kunnen miners er bijvoorbeeld voor kiezen om blokken achter te houden waarvan de headers een bakenwaarde produceren die ze niet leuk vinden. Of ze kunnen ervoor kiezen om de banden te verbreken wanneer twee botsende blokken worden gevonden op basis van hun favoriete bakenoutput.

Gedecentraliseerde randomness beacons (DRB's)

Een natuurlijke benadering van de problemen van gecentraliseerde bakens is het ontwerpen van een gedecentraliseerd cryptografisch protocol voor het produceren van openbare willekeur. Dit probleem lijkt een beetje op het ontwerpen van gedecentraliseerde consensusprotocollen, alleen moeilijker. Niet alleen moeten alle deelnemers het eens zijn over een uitvoer (de willekeur), maar het zou voor een kwaadwillende deelnemer aan het protocol onmogelijk moeten zijn om de uitvoer te beïnvloeden of te voorspellen.

Protocollen die zijn ontworpen om een ​​willekeurig baken te simuleren, worden gedistribueerde willekeurigheidsbakens (DRB's) genoemd. (Andere namen zijn onder meer "gedistribueerde munt-flipping.") Het probleem is al tientallen jaren bestudeerd, met: beroemde onmogelijkheid resultaten bewezen in de jaren 1980, maar de interesse is opnieuw aangewakkerd in het blockchain-tijdperk. DRB's kunnen worden gebruikt om willekeur in de keten te bieden, wat een belangrijk ingrediënt zou zijn voor eerlijke, veilige en transparante toepassingen in de keten.

De klassieke aanpak: protocollen vastleggen en vastleggen

Voor een DRB is in het optimistische geval een heel eenvoudig protocol van twee ronden voldoende. In ronde 1 heeft elke deelnemer i genereert een willekeurige waarde r_i en publiceert een cryptografische verbintenis c_i=Verbinden(r_i). In deze toepassing kan de verbintenis eenvoudig een hash-functie zijn, zoals SHA-256. Nadat de toezegging van elke deelnemer is gepubliceerd, zitten ze vast aan hun keuze van: r_i, maar de toezeggingen onthullen geen informatie over de bijdragen van andere deelnemers. In ronde 2 "opent elke deelnemer zijn engagement" door te publiceren r_i. Alle willekeurige waarden worden vervolgens gecombineerd, bijvoorbeeld door ze te XORen of (bij voorkeur) hun aaneenschakeling te hashen.

Dit protocol is eenvoudig en produceert een willekeurig bakenuitvoer zolang zelfs maar een van de deelnemers hun . kiest r_i willekeurig. Helaas lijdt het aan een klassieke fout: wanneer op één na alle deelnemers hun willekeurige waarde hebben onthuld, kan de laatste deelnemer de vermeende bakenuitvoer berekenen. Als ze het niet leuk vinden, kunnen ze weigeren hun waarde te publiceren en het protocol afbreken. Het negeren van de bijdrage van een defecte deelnemer lost het probleem niet op, want dat geeft een aanvaller nog steeds de keuze tussen twee bakenuitgangen (één berekend met hun bijdrage en één zonder).

Blockchains bieden een natuurlijke remedie voor dit probleem: van elke deelnemer kan worden verlangd dat hij geld in escrow zet dat in beslag wordt genomen als hij zijn willekeurige bijdrage niet bekendmaakt. Dit was precies de benadering van de klassieker RANDAO baken op Ethereum. Het nadeel van deze aanpak is dat de output nog steeds vertekend kan zijn, wat financieel de moeite waard kan zijn voor de aanvaller als het geld in escrow minder is dan het geldbedrag dat op het resultaat van het baken staat. Betere beveiliging tegen vooringenomen aanvallen vereist het plaatsen van meer munten in escrow.

Commit-reveal-recover-protocollen

In plaats van te proberen alle partijen te dwingen hun willekeurige bijdrage bekend te maken, bevatten sommige protocollen een herstelmechanisme zodat zelfs als een minderheid van de deelnemers uitvalt, de rest het protocol kan voltooien. Het is belangrijk dat het protocol in beide gevallen hetzelfde resultaat oplevert, zodat partijen het resultaat niet kunnen vertekenen door te kiezen of ze wel of niet willen afhaken.

Een benadering om dit te bereiken is om elke deelnemer de anderen te laten delen van zijn geheim, zodat een meerderheid van hen het kan reconstrueren, bijvoorbeeld met behulp van Shamir's geheim delen. Een belangrijke eigenschap is echter dat de anderen kunnen verifiëren dat het gecommitteerde geheim correct is gedeeld, wat het gebruik van een sterkere primitieve genaamd publicly verifiable secret sharing (PVSS) vereist.

Er zijn verschillende andere herstelmechanismen mogelijk, maar ze hebben allemaal dezelfde beperking. Als er zijn N deelnemers, en we willen veerkracht als een groep van maximaal f knooppunten wegvalt, dan moet het zo zijn dat elke groep van Nf deelnemers kunnen het eindresultaat berekenen. Maar dat betekent ook een kwaadaardige coalitie van Nf deelnemers kunnen het resultaat vooraf voorspellen door het herstelmechanisme privé te simuleren. Dit kan ook gebeuren tijdens de eerste ronde van het protocol, gedurende welke tijd zo'n coalitie zijn eigen willekeurigheidskeuzes kan wijzigen en het resultaat kan vertekenen. 

Anders gezegd, dit betekent dat elke coalitie van Nf knooppunten moeten ten minste één eerlijk knooppunt bevatten. Door eenvoudige algebra, Nf > f, dus f < N/2, en deze protocollen vereisen inherent een eerlijke meerderheid. Dit is een significant verschil met het oorspronkelijke beveiligingsmodel van commit-reveal, waarvoor alleen: f<N (minimaal één eerlijke deelnemer).

Deze protocollen vereisen vaak ook aanzienlijke communicatiekosten om de extra PVSS-informatie tussen alle knooppunten in elke uitvoering van het protocol te delen. De onderzoeksgemeenschap heeft de afgelopen jaren veel werk aan dit probleem gedaan, met onder meer onderzoeksvoorstellen: RandDeel, Schrapen, SecRand, HERBof Albatros, maar niemand lijkt een implementatie in de echte wereld te hebben gezien.

Verifieerbare willekeurige functiegebaseerde protocollen

Beseffen dat een groep van Nf deelnemers de willekeurige bakenwaarde in het bovenstaande protocol kunnen berekenen, leidt tot een iets eenvoudigere aanpak: deel een geheime sleutel voor de lange termijn tussen N partijen en laat ze het gebruiken om een verifieerbare willekeurige functie (VRF). De geheime sleutel wordt gedeeld via a t-uit-van-N drempelregeling, zodat eventuele t deelnemers kunnen de VRF berekenen (maar een kleinere coalitie niet). Voor t=Nf, dit biedt dezelfde veerkracht om f kwaadaardige nodes als de commit-reveal-recover-protocollen die hierboven zijn besproken.

DFINITY pionierde met deze aanpak als onderdeel van hun consensusprotocol met behulp van BLS-handtekeningen met drempelwaarde (die functioneren als een VRF). de op zichzelf staande verdronken willekeurig baken gebruikt in wezen dezelfde aanpak, waarbij een set deelnemers een drempelwaarde-BLS-ondertekent in elke ronde. De Liga van Entropie is een open source-instantie van drand die elke 30 seconden willekeur produceert met 16 deelnemende knooppunten (vanaf september 2022), gerund door een mix van bedrijven en universitaire onderzoeksgroepen. 

Een nadeel van deze benaderingen is dat het initialiseren van de drempelsleutel relatief complex is, net als het opnieuw configureren van de sleutel wanneer knooppunten toetreden of vertrekken. In het algemeen zijn de protocollen echter zeer efficiënt. 

Zoals hierboven beschreven, voegt het simpelweg ondertekenen van een tellerwaarde geen nieuwe willekeur per ronde toe, dus als een voldoende aantal deelnemerssleutels wordt gecompromitteerd, zal het protocol in elke toekomstige ronde voorspelbaar zijn.

Kettingschakel VRF combines deze benadering (met behulp van de NSEC5 VRF) met een externe bron van willekeur gespecificeerd door partijen die om willekeur verzoeken, in de praktijk meestal een recente blockchain-header. Deze gegevens worden vervolgens ingevoerd via een VRF die wordt beheerd door één partij of wordt gedrempeld naar een groep.

Ethereum's Baken ketting gebruikt momenteel op BLS gebaseerde VRF's: de indiener van elke ronde voegt zijn VRF-waarde toe aan de mix. Dit bespaart een communicatieronde in vergelijking met het commit-reveal-paradigma (ervan uitgaande dat een openbare BLS-sleutel op lange termijn eenmaal is geregistreerd), hoewel dit ontwerp enkele kanttekeningen bij de commit-reveal-aanpak erft, inclusief de mogelijkheid om de output van het baken te beïnvloeden door de output achter te houden .

Verifieerbare op vertragingsfunctie gebaseerde protocollen

Ten slotte is een veelbelovende nieuwe richting het gebruik van op tijd gebaseerde cryptografie, met name verifieerbare vertragingsfuncties (VDF's). Deze aanpak belooft een goede communicatie-efficiëntie en robuustheid te bieden met veerkracht tegen N-1 kwaadaardige knooppunten. 

Teruggaand naar het oorspronkelijke commit-onthullingsprotocol, kunnen traditionele verplichtingen worden vervangen door: getimede verplichtingen om het probleem op te lossen dat deelnemers weigeren hun willekeurige bijdrage te onthullen. Getimede verplichtingen kunnen efficiënt worden geopend door de oorspronkelijke committer, of door iedereen die bereid is een langzame functie te berekenen (in wezen een VDF). Dus als een deelnemer uit een commit-onthullingsprotocol valt, kan zijn commitment nog steeds door anderen worden geopend. Het is essentieel dat de minimale tijd om de toezegging te openen lang genoeg is om te voorkomen dat dit tijdens de eerste ronde (de vastleggingsfase) van het protocol kan worden gedaan, anders zouden kwaadwillende deelnemers de toezeggingen van anderen snel genoeg kunnen openen om hun eigen bijdrage te wijzigen en het resultaat te vertekenen .

Een nog eleganter eenrond protocol is mogelijk met moderne VDF's: laat de verplichting volledig vallen. Elke deelnemer kan eenvoudig zijn willekeurige bijdrage publiceren r_i, en het uiteindelijke resultaat is een combinatie van de bijdrage van elke deelnemer, uitgevoerd door een VDF. De vertraging bij het berekenen van de VDF zorgt ervoor dat niemand zijn inzet kan kiezen op een manier die de uiteindelijke output vertekent. Deze aanpak werd voorgesteld als UNICORN door Arjen Lenstra en Benjamin Wesolowski in 2015, en was inderdaad een belangrijke motiverende toepassing in de ontwikkeling van VDF's.

Deze aanpak heeft enige praktische toepassing gezien. Chia implementeert een versie hiervan als onderdeel van zijn consensusprotocol, met behulp van herhaalde kwadratuur VDF's in klasgroepen. Starkwar naar geïmplementeerd proof-of-concept VDF-gebaseerd baken met behulp van op SNARK gebaseerde VDF's. Ethereum ook plannen gebruiken deze aanpak, het bouwen van een speciale ASIC voor het berekenen van VDF's om willekeur te genereren op de consensuslaag.

***

Openbare willekeur is een essentieel onderdeel van veel protocollen, maar we missen nog steeds een standaard DRB die hoge beveiliging biedt. De ontwerpruimte is groot en er zijn veel hybriden en combinaties van bovenstaande benaderingen mogelijk. Het is bijvoorbeeld mogelijk om een ​​op VRF gebaseerd protocol te combineren met een op VDF gebaseerd protocol, dat bijvoorbeeld verse entropie toevoegt, zoals voorgesteld door RandRunner. De Beacon Chain van Ethereum gebruikt momenteel VRF's, hoewel het in de toekomst VDF's kan toevoegen om de mogelijkheid van vooringenomenheid door blokkeringsaanvallen te elimineren.

Het is ook een open vraag wanneer protocollen met een eerlijke meerderheid acceptabel zijn. Voor een relatief kleine, doorgelichte groep deelnemers - zoals de League of Entropy - is een eerlijke meerderheidsaanname redelijk. Aan de andere kant hebben protocollen waarvoor slechts één eerlijke deelnemer nodig is, een inherent voordeel: meer deelnemers kunnen de beveiliging alleen maar verbeteren. Dit betekent dat deze protocollen mogelijk kunnen worden ingezet met open, toestemmingsloze deelname.

In deel II bespreken we de specifieke toepassing van gerandomiseerde leidersverkiezingen in consensusprotocollen, die enigszins andere ontwerpdoelen hebben en als gevolg daarvan nog meer protocollen en benaderingen hebben voorgesteld.

***

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.