Tempo – Geleerde consensuslessenRadix DLT, 31 augustus 2020Radix community-leden (waarvan sommigen al bij ons zijn sinds vóór het ‘Radix’ werd genoemd!) weten dat vele jaren van hard werk ons hebben gebracht tot waar we nu zijn. We hebben onze meest recente mijlpalen onthuld met de uitgifte van het Cerberus-whitepaper dat ons baanbrekende multi-shard consensusprotocol beschrijft dat het ongekende niveau van DLT-schaling mogelijk maakt dat altijd ons doel is geweest.
Voor Cerberus zullen velen van jullie de uitgifte van het Tempo-whitepaper herinneren (of erover hebben gelezen, ons vorige DLT consensusprotocolontwerp. De ideeën bevat in dat whitepaper trokken velen van ons naar Radix als fans, bijdragers en werknemers. Terwijl Radix doorgaat met het voorwaarts drijven van de open source uitgifte van het Radix publiekle netwerk krijgen we een hoop nieuwe volgers (en terugkerende vrienden) die willen weten wat Tempo was en waarom we bewogen naar onze nieuwe Cerberus-consensus.
Betekenisvolle technologische ontwikkeling is bijna altijd een lange, kronkelige weg. Dus in deze blog willen we onze reis delen van de zoektocht van onze oprichter Dan om de tekortkomingen van bockchain op te lossen tot de ontwikkeling van Tempo, via de problemen die we ontdekten bij het testen, en hoe we ze met Cerberus oplosten. De collectieve uitdagingen, doodlopende wegen en nieuw ontdekte paden op onze weg hebben allemaal geleid dot een oplossing waarvan we geloven dat deze klaar is om Dans visie te bereiken: het leveren van de belofte van blockchain met een waarlijk wereldwijd-schalige gedecentraliseerde ledger.
Het originele verhaal De visie voor Tempo werd geboren uit een worsteling om Bitcoin te schalen. Dan realiseerde dat terwijl gedecentraliseerde financiën de toekomst was de huidige blockchaintechnologie deze niet naar de massa’s kon brengen. Het verleidelijk eenvoudige blockchainmodel waarop netwerken als Bitcoin waren gebouwd kon gewoon niet uitgebreid worden om te schalen zonder in te geven op decentralisatie. Ethereum, gebaseerd zijnde op fundamenteel dezelfde technologie, voer niet veel beter. Gerichte acyclische grafica – of DAG’s – leken een veel’belovende start, maar kwamen ook tekort in zowel schaalbaarheid als centralisatie: er was iets anders nodig.
Laten we terug gaan in de tijd voor blockchain – gedistribueerde systemen zijn decennia lang bestudeerd en gebruikt in de productie, dus waarom het verlangen naar een drastisch andere aanpak? Terwijl gedistribueerde systemen een lange geschiedenis hebben richt de benadering van gedistribueerde systemen zich op hun toepassing in gesloten omgevingen (waar netwerken kleiner zijn en niet het potentieel hebben voor veel aanvallers). Wanneer gebruikt in open omgevingen met veel nodes worden de traditionele benaderingen ofwel kruiperig traag ofwel stoppen ze volledig met functioneren. Deze benaderingen waren daarom ook niet goed geschikt voor onze visie.
Om de belofte te vervullen van een schaalbare, gedecentraliseerde ledger moesten we terug gaan naar de ontwerptafel. Een ideale ledger voor gebruik van de hele wereld moest het volgende zijn:
-
Massaal schaalbaar om miljoenen aanvragen per seconde te accommoderen.
-
Gedecentraliseerd om te verzekeren dat ’s werelds infrastructuur in controle. blijft van de mensen
-
Programmeerbaar om de creatie mogelijk te maken van gedecentraliseerde autonome applicaties.
Alle bestaande oplossingen schoten tekort op minstens één sleutelgebied. Om te komen met een alles-in-één-oplossing begonnen we met het herzien van de fundamenten. Door deze ideale proporties te vertalen naar technische vereisten konden we definiëren hoe zo’n platform eruit kon zien:
-
Massale schaal zou zowel een schaalbare data-architectuur als een schaalbaar consensusproces vereisten. Noch de bestaande blockchainbenaderingen, noch klassieke consensusmechanismen (zoals gebruikt voor bedrijfsdatabestanden) waren schaalbaar terwijl ze voldoende tolerant waren voor de soorten van verwachte fouten in een publieke omgeving.
-
Decentralisatie zou vereisten dat ieder aantal nodes op ieder moment in een netwerk zouden kunnen meedoen (of eruit vertrekken). Terwijl blockchains en DAG’s daarmee zouden kunnen omgaan waren ze niet schaalbaar. Traditionele consensusmechanismen konden geen van beide doelen ondersteunen.
-
Programmeerbaarheid zou een nieuw paradigma vereisten voor het ontwikkelen van veilige en schaalbare gedistribueerde applicaties die ondersteund zouden worden door zowel de schaalbare data-architectuur als het consensusmechanisme.
De vonkOmdat alle bestaande oplossingen onvoldoende leken voor zelfs de eerste twee van onze ambities – schaling en decentralisatie – startten we met de eerste principes: Gedistribueerde systemen repliceren de staat over een set van nodes. De waarde van een gedistribueerd systeem ligt in zijn capaciteit om zich te gedragen als een enkele eenheid voor de buitenstaande aanschouwer. Dat wil zeggen dat het er niet toe doet met welke nodes een cliënt communiceert en aan welke hij vragen stelt over een staat; ze zouden allemaal hetzelfde antwoord moeten geven. Om dit te bereiken moeten de gedistribueerde nodes
gesynchroniseerd blijven door met elkaar te communiceren.
Het grootste knelpunt in de meeste gedistribueerde systemen is daarom inter-node-communicatie. Om naar een grote vraag te schalen (meer bediening en meer verzoeken), het krachtiger maken van individuele nodes, wordt al snel inefficiënt (en gecentraliseerd). In plaats daarvan worden
meer nodes toegevoegd die parallel draaien. Deze nieuwe nodes moeten communiceren met alle andere nodes om gesynchroniseerd te blijven en te blijven optreden als een hecht geheel. Dat beperkt fundamenteel schaalbaarheid.
De natuurlijke manier om zulke systemen te schalen is door het vinden van een manier om minder inter-node-communicatie te vereisten. Maar hoe? Een traditionele benadering is om de nodes alleen te laten communiceren met
enkele andere nodes voor ieder verzoek, verschillende delen van de ledger toekennend aan verschillende nodes. Nu hoeven nodes zich alleen bezig te houden met verzoeken voor het deel van de ledger waarvoor ze verantwoordelijk zijn. Minder nodes om mee te communiceren voor ieder verzoek staat gelijk aan meer schaalbaarheid. Dit “splitsen” is een vorm van
sharding, of het opbreken van de ledger in individuele
shards voor verschillende sets van nodes om mee om te gaan. Sharding in diverse vormen werd al decennia gebruikt, dus dit was een goed startpunt.
Maar we wilden meer. Om de wereld te bedienen had ons platform alle schaalbaarheid nodig die het kon krijgen.
Een andere reden waarom nodes zo graag met elkaar communiceren is dat pBFT-stijl consensusprotocollen alle nodes nodig hebben om overeen te stemmen over
ieder verzoek voordat ze doorgaan naar het volgende. Daarmee wordt veel substantiële overbodige last geïncasseerd. Zelfs met sharding moeten nodes met alle andere nodes die relevant zijn voor ieder verzoek communiceren.
Een potentiële maar exotische oplossing voor dit probleem ligt in een simpele realisatie: wat als nodes slechts ieder verzoek accepteerden en alleen tot expliciete overeenstemming zouden komen met elkaar wanneer een verzoek betwitst wordt? Zo’n lui communicatieparadigma (ook aan gerefereerd als ‘luie consensus) zou de communicatie die nodig is tijdens normale operatie van de ledger substantieel reduceren. Het combineren van een luie consensus met sharding had het potentieel van ongeëvenaarde schaalbaarheid.
Bouwen van TempoHet idee van een gesharde ledger met luie consensus werd gerealiseerd met
Tempo. Tempo is zowel een gedistribueerde ledger als het onderliggende consensusprotocol. Het consensusdeel van Tempo is gebasseerd op de notie van
logische klokken. Iedere node heef een
teller (zijn logische klok) die toeneemt bij ieder nieuw verzoek waarvan hij getuige is, nooit afnemend. Wanneer een verzoek wordt opgeslagen voegt de node zijn huidige logische klakwaarde bij die gebeurtenis alvorens deze verder door te voeren. De set van logische klokwaarden toegeschreven door iedere node vormt een
tijdelijk bewijs.
Tijdelijke bewijzen worden nuttig in een
conflict, wanneer een node een verzoek ontvangt dat conflicteert met een verzoek dat eerder werd ontvangen. Om te bepalen welk verzoek moet worden weggedaan kan de node dan tijdelijke bewijzen verzamelen van andere nodes die gerelateerd zijn aan beide conflicterende verzoeken. Wanneer een intersectie is gevonden in een derde tijdelijk bewijs kan dit bewijs worden gebruikt om een gedeeltelijke ordening te bepalen tussen de twee verzoeken – welke eerder kwam wint. Omdat andere nodes dezelfde tijdelijke bewijzen zullen vinden voor hetzelfde verzoek zullen alle nodes tot dezelfde conclusie komen over welk verzoek het eerste kwam. Consensus wordt bereikt, allemaal zonder de overbodige last van continue voorkomend te communiceren met alle andere nodes.
Nodes moeten cryptografisch hun bijdragen aan een tijdelijk bewijs ondertekenen. Echter dat alleen weerhoudt een foute node er niet van om dezelfde logische klokwaarde te ondertekenen voor verschillende verzoeken. Daarvoor moet Tempo op de een of andere manier verifiëren dat nodes eerlijk zijn met hun tijdelijke bewijzen. Daarom sluiten nodes een
toewijding in bij hun recent getuigde verzoeken bij iedere bijdrage die ze maken aan een tijdelijk bewijs. Een toewijding is een cryptografische hash die het gemakkelijker maakt voor eerlijke nodes om enige fout te detecteren. Iedere bijdrage omvat een verschillend (maar voorspelbaar) klein stukje van die hash, de overbodige last van communicatie verder verminderend.
Bij consensus die is afgestemd op maximale schaalbaarheid zouden we ons kunnen wenden naar het andere sleutelingrediënt voor schaalbaarheid op grote schaal: sharding. Op het moment dat Tempo werd ontworpen gebruikten de meeste gedistribueerde ledgers helemaal geen sharding. En de enkele die dat dezen volgden de benadering van het dynamisch aanpassen van het aantal shards aan de doorvoervereisten. Dynamische sharding veroorzaakt echter significante consensus- en synchronisatieproblemen wanneer nodes uiteindelijk opnieuw toegekend worden wanneer de shardingconfiguratie verandert, om nog maar niet te spreken over de bruikbaarheids- en programmeerbaarheidsproblemen.
Om de problemen te vermijden van het continue te moeten herconfigureren van de gehele shardingconfiguratie kozen we om de ledger te “pre-sharden” in een massaal aantal shards die nooit veranderen. Iedere node werd toegekend aan een subset van deze shards, soepele aanpassingen mogelijk makend, passend bij de individuele capaciteit en vereisten van iedere node. Het ontwerpen van Tempo rond deze massale pre-sharding in plaats van het proberen om oplopende sharding toe te voegen zoals in de meeste benaderingen bood een uitstekend fundament om een bijna onbeperkte parallellisatie van transactieverwerking te bereiken.
Testen van TempoOp 12 juni 2019 besloten we om te kijken hoe ver we in snelheid konden gaan met een netwerk met gebruik van Tempo. Die dat draaiden we opnieuw de gehele 10 jaar van Bitcoins transactiegeschiedenis af op de Radix-ledger (alsof die transacties zo snel mogelijk naar Radix werden verzonden), met volledige transactie- en signatuurvalidatie, op een netwerk van meer dan 1000 nodes, gelijkelijk gedistribueerd over de hele wereld. Dit testnetwerk bereikte meer dan 1mlj transacties per seconde, demonstrerend wat parallellisatie over een massaal gepre-sharde ledger kan doen.
Voor de eerste keer sinds de creatie van publieke, onbeheerde netwerken demonstreerden we een technologie die zelfs ’s werelds meest eisende transactionele applicatiegebruik echt kon ondersteunen. Het was een geweldig stuk engineering dat niet mogelijk was geweest zonder zowel de enorme toewijding van ons eigen team als direct werkend met Google Cloud-engineers.
De volledig gedocumenteerde reis en het testen wordt gedetailleerde besproken in deze vier blog-posts, welke we aanraden voor je om te lezen als je de tijd hebt!
-
10 years of Bitcoin history, replayed in under 30 minutes-
Part 1: A Primer on The Scalability Test and Radix-
Part 2: How We Actually Built The Scalability Test-
Scaling DLT to over 1M TPS on Google CloudHet breken van TempoVoor alle innovaties die Tempo op tafel legde bleven er enkele fundamentele vragen. Tempo’s luie consensusmechanisme betekende dat een verzoek op ieder moment uitgedaagd kon worden en overstemd door een ander verzoek. Dat wil zeggen dat het initiële Tempo-model nooit de
finaliteit van een verzoek garandeerde. De enige manier om er zeker van te zijn dat een verzoek kon blijven was kennis te hebben van alle relevante tijdelijke bewijzen. Echter netwerkfouten en kwaadwillendheid kunnen ertoe leiden dat sommige delen van tijdelijke bewijzen ontoegankelijk zijn, wat het onmogelijk maakt om nauwkeurig finaliteit in te schatten.
Cliënten willen enige vorm van finaliteit in hun verzoeken. Het Bitcoin-stijl-consensus biedt in toenemende mate (hoewel nooit absolute) zekerheid in finaliteit, maar deze benadering was niet compatibel met Tempo. Een mogelijke oplossing om finaliteit te introduceren was om een pauzemechanisme te introduceren die verzoeken in een node zouden finaliseren nadat deze onbetwist zou worden gelaten voor een onbepaalde tijd. Helaas is zo’n oplossing kwetsbaar voor dezelfde zwakten, ofschoon uitgedrukt op een andere manier. In bepaalde netwerkconfiguraties was het mogelijk voor sommige nodes om relevante conflicterende verzoeken te missen voor finalisering van hun favoriet. Dit zou leiden tot nodes die met elkaar twisten maar niet in staat zijn om het conflict te rectificeren wanneer eenmaal ontdekt omdat verzoeken al aan beide zijden gefinaliseerd werden.
Verschillende nodes die conflicterende verzoeken finaliseren breken het model van een “hecht geheel”, zoals nodig is voor een betrouwbaar gedistribueerd systeem. Dit was een essentiële zwakte. Een onbetrouwbaar netwerk, in plaats van een kwaadwillend iemand, was genoeg om Tempos garantie van coherentie te breken. Zoals nodes bijvoorbeeld kunnen twisten over waar je je geld heen stuurde in goedwillende (ofschoon onbetrouwbare) netwerken was het Tempo-consensus niet geschikt voor gebruik in de echte wereld.
Opnieuw terug naar de fundamenten. Finaliteit, de sleutelcomponent die mist in de luie benadering van consensus van Tempo, vereist dat nodes proactief tot consensus komen bij ieder verzoek. Hoe kunnen we anders de communicatiecomplexiteit die inherent is aan deze “actieve” vorm van consensus reduceren? De communicatiecomplexiteit is zo hoog omdat alle nodes er absoluut zeker van moeten zijn dat ze in overeenstemming zijn met
alle andere nodes. Wat als we, in plaats van het najagen van een 0% waarschijnlijkheid dat nodes twisten over de kosten van hoge communicatie, een 0,0…1% van waarschijnlijkheid van onenigheid konden bereiken met veel lagere kosten?
De voordelen van het accepteren van een extreem lage waarschijnlijkheid van falen worden gerealiseerd door een
gerandomiseerde consensus (een techniek die heden populair wordt gemaakt door consensusalgoritme’s als Avalanche). Het idee is dat in plaats van het communiceren met alle nodes voor consensus op ieder verzoek een node een paar “interview”-rondes uitvoert met kleine willekeurige subsets van nodes. Als deze subset van nodes het oneens is met een node-keuze van verzoek zal de node de keuze van de meerderheid accepteren. Nadat een aantal opeenvolgende rondes zonder keuzeverandering van verzoek zal een node aannemen dat alle nodes in overeenstemming zijn en het verzoek finaliseren. Met de juiste configuratie kan een gerandomiseerde consensus een erg lage waarschijnlijkheid van twist garanderen.
De notie van gerandomiseerde consensus heeft een recente piek in populariteit genoten omdat andere gedistribueerde ledgers ernaar keken om te helpen in hun eigen schaalbaarheidsproblemen. Echter zoals met de originele visie voor Tempo gaat de aan de schaalbaarheid van gerandomiseerde consensus onderliggende premisse gepaard met een essentiële inruil: het laten stemmen van nodes op een onvoorspelbare manier maakt foutdetectie moeilijk, want het is veel moeilijker om fout gedrag algoritmisch te bewijzen. Zonder voldoende foutdetectie kunnen foute nodes andere nodes in twist met elkaar brengen. En vanwege zijn “ga mee met de meerderheid-“interview-benadering kunnen foute nodes leiden tot nodes die nooit tot overeenstemming komen, of – erger- nodes die onenigheden finaliseren (zoals in Tempo).
Wanneer shading wordt beschouwd is een gerandomiseerde consensus niet meer zo aantrekkelijk. De besparingen in communicatieve overbodige lasten die een gerandomiseerde consensus opleveren schalen exponentieel met het aantal van nodes die betrokken zijn in consensus; maar in een gesharde ledger is alleen een subset van alle nodes betrokken bij een enkele consensusbeslissing. Dit vermindert de schaalbaarheidsvoordelen zoals beloofd door een gerandomiseerde consensus zodat het “economischer” zou zijn (vanuit schaalbaarheidsstandpunt) om eenvoudigweg een pBFT-stijl consensusmechanisme te gebruiken en dan zijn prestaties te boosten met sharding.
Wat als we alle lessen die we leerden over het schalen van consensus, ledgers en sharding konden meenemen en ze toepassen op de laatste vooruitgang in consensusonderzoek? Het resultaat zou een verfrissende benadering kunnen zijn van hoog schaalbare ledgers, geworteld in een onwrikbaar en goed-onderzocht fundament.
En dat is precies wat we deden. Introductie: Cerberus.
Voorwaarts met CerberusCerberus is het product van gecombineerde decennia van onderzoek en experimenten in zowel exoterische als pBFT-stijl benaderingen van consensus, ledger-architectuur en gedistribueerde applicaties – gecombineerd met de inzichten die we verkregen bij het ontwerpen van Tempo voor grootschalige onbeheerde netwerken. De essentie van Cerberus is eenvoudig: neem een uitbreidbaar pBFT-stijl consensusalgoritme en breid het uit om onbeperkte parallellisering mogelijk te maken met gebruik van ons unieke sharding-concept.
Het fundament voor deze volgende generatie van consensusprotocol moest theoretisch degelijk zijn en, natuurlijk, presterend. Voor een voldoende primair niveau van prestaties moest het protocol communicatiecomplexiteit op de een of andere manier naar beneden brengen. De klassieke manier om communicatie te reduceren is door een
leider te nomineren voor elk verzoek die zal verzekeren dat alle nodes overeenstemmen over dat verzoek voor ze verder gaan. De meeste leider-gebaseerde consensusprotocollen kiezen enkel een nieuwe leider wanneer de huidige niet antwoordt of op een andere manier faalt om verzoeken te voltooien. Deze behandeling van leiderwisseling leidt tot extra complexiteit en minder voorspelbare prestaties.
HotStuff is een recent gepubliceerd consensusprotocol dat voortbouwt op significant eerder werk (zijn geschiedenis terug tracerend naar pBFT) maar wisselt leiders bij elk verzoek om substantiële voordelen te bereiken. Dit gestroomlijnde consensusproces maakt het verzoeken mogelijk om aan elkaar geketend te worden, een significante prestatie-optimalisatie mogelijk makend.
Belangrijk genoeg maakt HotStuffs gestroomlijnde benadering ook een essentiële innovatie mogelijk van Cerberus: het draaien van meerdere “gevallen” van consensus in parallel voor schaalbaarheid terwijl de mogelijkheid behouden blijft om transparant op ze te opereren. Zoals met de originele Tempo is de onderliggende ledger massal gepre-shard. Elke shard wordt toegewezen aan zijn eigen onafhankelijke consensusinstantie, wat een bijna onbeperkte parallellisme mogelijk maakt. Om consensus mogelijk te maken over meerder shards/instanties implementeert Cerberus een vernuftig “vlecht”-mechanisme dat in opdracht meerdere HotStuff-stijl consensus-instanties samen bindt om shardoverschrijdende verzoeken voort te drijven. Zulke vlechten worden gebonden en ontbonden zoals nodig, atomische transacties over shards mogelijk makend, wat essentieel is voor applicaties zoals gedecentraliseerde financiën (bv. Wanneer geld tussen shards wordt gestuurd). Cerberus vermijdt dus de problemen van veel sharding-benaderingen waarin shards de consensus volledig onafhankelijk uitvoeren en enkel over shards met berichten in meerdere stappen kunnen coördineren.
Cerberus’ unieke benadering tot massale sharding van zowel ledger als het consensusprotocol maakt ongeëvenaarde schaalbaarheid mogelijk terwijl flexibel wordt gebleven voor ontwikkelaars en ook zonder decentralisatie op te offeren. Bovenstaande is slechts een kleine samenvatting; om meer te leren over hoe het werkt kun je het
Cerberus whitepaper lezen en op GitHub volgen hoe we ons Cerberus
consensus-stappenplan ontwikkelen.
Website (https://www.radixdlt.com/)
Medium (https://medium.com/@radixdlt)
Telegram (https://t.me/radix_dlt)
Twitter (https://twitter.com/RadixDLT)