Het Stellar-consensusprotocol werd voor het eerst beschreven in David Mazier in 2015. Dit is een ‘federaal Byzantijns overeenkomstsysteem’ dat gedecentraliseerde, leiderloze computernetwerken in staat stelt efficiënt consensus over een besluit te bereiken. Het Stellar-betalingsnetwerk maakt gebruik van het Stellar Consensus Protocol (SCP) om een consistente transactiegeschiedenis bij te houden die voor alle deelnemers zichtbaar is.
Consensusprotocollen worden als moeilijk te begrijpen beschouwd. SCP is eenvoudiger dan de meeste, maar deelt nog steeds deze reputatie - deels vanwege het verkeerde idee dat 'federatief stemmen', dat het onderwerp is van de eerste helft van het wetenschappelijke artikel, SCP is. Maar dat is niet waar! Dit is slechts een belangrijke bouwsteen die in de tweede helft van het artikel wordt gebruikt feitelijk Geweldig consensusprotocol.
In dit artikel zullen we kort uitleggen wat een “systeem van overeenkomsten” is, wat het “Byzantijns” kan maken en waarom het Byzantijnse systeem “federaal” wordt. Vervolgens leggen we de gefedereerde stemprocedure uit die wordt beschreven in het SCP-artikel, en ten slotte leggen we het SCP-protocol zelf uit.
Overeenkomstsystemen
Dankzij een systeem van afspraken kan een groep deelnemers consensus bereiken over een onderwerp, bijvoorbeeld wat ze voor de lunch moeten bestellen.
Bij Interstellar hebben we ons eigen systeem voor eetafspraken geïmplementeerd: we bestellen wat onze operations manager, John, zegt. Dit is een eenvoudig en effectief afsprakensysteem. We vertrouwen allemaal op John en geloven dat hij elke dag iets interessants en voedzaams zal vinden.
Maar wat als John ons vertrouwen misbruikt? Hij kan in zijn eentje beslissen dat we allemaal veganist moeten worden. Over een week of twee zullen we hem waarschijnlijk omverwerpen en de macht overdragen aan Elizabeth. Maar ineens houdt ze van avocado’s met ansjovis en vindt ze dat iedereen zo zou moeten zijn. Macht corrumpeert. Het is dus beter om een meer democratische methode te vinden: een manier om ervoor te zorgen dat er rekening wordt gehouden met verschillende voorkeuren en tegelijkertijd een tijdig en ondubbelzinnig resultaat te garanderen, zodat niemand uiteindelijk een lunch bestelt, of vijf mensen verschillende bestellingen plaatsen, of dat de discussie sleept zich voort tot in de avond.
Het lijkt erop dat de oplossing eenvoudig is: houd een stemming! Maar dit is een misleidende indruk. Wie verzamelt de stembiljetten en rapporteert de uitslag? En waarom zouden anderen geloven wat hij zegt? Misschien wel in eerste instantie stem op een leider van wie we vertrouwen dat hij de stemming zal leiden – maar die deze ook zal leiden de eerste door te stemmen? Wat als we het niet eens kunnen worden over een leider? Of wat als we tot overeenstemming komen, maar deze leider vastloopt in een vergadering of met ziekteverlof gaat?
Soortgelijke problemen doen zich voor in gedistribueerde computernetwerken. Alle deelnemers of knooppunten moeten het eens worden over een bepaalde beslissing, bijvoorbeeld wie aan de beurt is om een gedeeld bestand bij te werken of een taak uit de verwerkingswachtrij te verwijderen. In een cryptocurrency-netwerk moeten knooppunten herhaaldelijk kiezen hoe het volledige verhaal eruit ziet uit verschillende mogelijke versies, die soms conflicteren. Deze netwerkovereenkomst geeft de ontvanger de zekerheid dat de munt (a) geldig is (geen vervalsing) en (b) nog niet elders is uitgegeven. Dit zorgt er ook voor dat hij de munten in de toekomst kan uitgeven, omdat de nieuwe ontvanger om dezelfde redenen dezelfde garanties heeft.
Elk consensussysteem in een gedistribueerd computernetwerk moet fouttolerant zijn: het moet consistente resultaten produceren ondanks fouten zoals langzame verbindingen, niet-reagerende knooppunten en een onjuiste volgorde van berichten. Byzantijns Het overeenkomstsysteem is bovendien bestand tegen "Byzantijnse" fouten: knooppunten die valse informatie geven, hetzij als gevolg van een fout, hetzij in een opzettelijke poging om het systeem te ondermijnen of enig voordeel te behalen. ‘Byzantijnse’ fouttolerantie – het vermogen om een groepsbeslissing te vertrouwen, zelfs als sommige groepsleden liegen of zich op een andere manier niet aan de regels van de besluitvorming houden – wordt ‘Byzantijnse’ fouttolerantie genoemd. die de aanval probeerde te coördineren. bij Antonius Stevens.
Denk aan Alice, eigenaar van cryptomunten, die moet kiezen tussen het kopen van heerlijk ijs van Bob en het afbetalen van Carol's schuld. Misschien wil Alice ze allebei tegelijk betalen door op frauduleuze wijze dezelfde munt uit te geven. Om dit te doen, moet ze de computer van Bob ervan overtuigen dat de munt nooit aan Carol is betaald, en de computer van Carol ervan overtuigen dat de munt nooit aan Bob is betaald. Het Byzantijnse systeem van overeenkomsten maakt dit vrijwel onmogelijk, door gebruik te maken van een vorm van meerderheidsregel die ‘meerderheidsregel’ wordt genoemd quorum. Een knooppunt in zo'n netwerk weigert over te stappen naar een bepaalde versie van de geschiedenis totdat het ziet dat een voldoende aantal gelijken – een quorum – instemt met een dergelijke transitie. Zodra dit gebeurt, zullen ze een stemblok vormen dat groot genoeg is om de resterende netwerkknooppunten te dwingen in te stemmen met hun beslissing. Alice kan sommige knooppunten dwingen namens haar te liegen, maar als het netwerk groot genoeg is, zal haar poging worden overweldigd door de stemmen van eerlijke knooppunten.
Hoeveel knooppunten zijn vereist voor het quorum? Op zijn minst een meerderheid, of beter gezegd, een gekwalificeerde meerderheid om fouten en fraude tegen te gaan. Maar om de meerderheid te tellen, moet je het totale aantal deelnemers kennen. Op het Interstellar-kantoor of bij de districtsverkiezingen zijn deze cijfers gemakkelijk te achterhalen. Maar als uw groep een losjes gedefinieerd netwerk is waarin knooppunten naar believen kunnen binnenkomen en vertrekken zonder toestemming van het centrum, dan heeft u federaal een Byzantijns overeenkomstsysteem dat in staat is om quorums te bepalen, niet op basis van een vooraf bepaalde lijst van knooppunten, maar dynamisch, op basis van een steeds veranderende en onvermijdelijk onvolledige momentopname van knooppunten op een bepaald tijdstip.
Het lijkt misschien onmogelijk om een quorum te creëren vanuit het perspectief van een enkel knooppunt in een enorm netwerk, maar het is mogelijk. Een dergelijk quorum kan zelfs de resultaten van gedecentraliseerd stemmen garanderen. Het SCP-whitepaper laat zien hoe u dit kunt doen met behulp van een procedure genaamd door federale stemming.
Voor de ongeduldigen
De rest van het artikel beschrijft federatief stemmen en het Stellar-consensusprotocol in meer detail. Als u niet geïnteresseerd bent in de details, vindt u hier een algemeen overzicht van het proces.
- De knooppunten voeren federale stemrondes uit over ‘genomineerden’. Een federale stemronde betekent:
- Het knooppunt stemt voor een of andere uitspraak, bijvoorbeeld: “Ik stel de waarde van V voor”;
- Het knooppunt luistert naar de stemmen van de peers totdat het er een vindt die kan "ontvangen";
- Het knooppunt zoekt naar een "quorum" voor deze bewering. Een quorum ‘bevestigt’ de genomineerde.
- Zodra een knooppunt een of meer genomineerden kan bevestigen, probeert het de ‘stemming’ voor te bereiden via verschillende federatieve stemrondes.
- Zodra een knooppunt kan verifiëren dat het stembiljet gereed is, probeert het dit via nog meer gefedereerde stemrondes vast te leggen.
- Zodra een knooppunt een vastgelegd stembiljet kan bevestigen, kan het de waarde van dat stembiljet "externaliseren" door het als consensusresultaat te gebruiken.
Deze stappen omvatten meerdere gefedereerde stemrondes, die samen één SCP-ronde vormen. Laten we eens nader bekijken wat er bij elke stap gebeurt.
Federatieve stemming
Federated voting is een procedure om te bepalen of het netwerk het eens kan worden over een voorstel. In de stemronde moet elk knooppunt een van de potentieel vele mogelijke waarden kiezen. Het kan dit alleen doen als het er zeker van is dat andere knooppunten in het netwerk niet voor een andere uitkomst zullen kiezen. Om hier zeker van te zijn, wisselen knooppunten een spervuur van berichten heen en weer uit, zodat iedereen bevestigdDat quorum knopen neemt dezelfde beslissing. In de rest van dit gedeelte worden de termen in deze zin uitgelegd en hoe de hele procedure plaatsvindt.
Quorums en quorumsegmenten
Laten we beginnen met het definiëren van een quorum. Zoals we hierboven hebben besproken, is het in een gedecentraliseerd netwerk met dynamisch lidmaatschap onmogelijk om vooraf het aantal knooppunten te kennen en dus hoeveel er nodig zijn voor de meerderheid. Federated voting lost dit probleem op door een nieuw idee te introduceren quorum verlaagd (quorum slice): Een kleine set peers die een knooppunt vertrouwt om informatie over de stemstatus door te geven aan de rest van het netwerk. Elk knooppunt definieert zijn eigen quorumsegment (waarvan het de facto lid wordt).
Quorumvorming begint met een quorumverlaging. Voor elk knooppunt worden de afgesneden knooppunten toegevoegd. Vervolgens worden de segmenttermen toegevoegd deze knooppunten enzovoort. Naarmate u verdergaat, zijn er steeds meer knooppunten die u niet kunt toevoegen omdat ze al in het segment zijn opgenomen. Wanneer er geen nieuwe knooppunten meer zijn om toe te voegen, stopt het proces: we hebben een quorum gevormd door “transitieve afsluiting” van het quorumsegment van het oorspronkelijke knooppunt.
Om het quorum van een bepaald knooppunt te vinden...
... leden van zijn segment toevoegen...
...dan voegen we segmentleden van deze knooppunten toe.
We gaan door totdat er geen knooppunten meer zijn om toe te voegen.
Er zijn geen knooppunten meer om toe te voegen. Dit is een quorum.
In feite kan elk knooppunt in meer dan één segment voorkomen. Om een quorum te vormen, selecteert u slechts één van de segmenten en voegt u leden toe; selecteer vervolgens een segment voor elk van de leden en voeg leden toe het knippen enzovoort. Dit betekent dat elk knooppunt lid is van veel mogelijke quorums.
Selecteer bij elke stap slechts één quorumsegment.
Eén mogelijk quorum. Of een alternatief...
...selecteer andere plakjes...
…(als het mogelijk is)…
... creëert een nieuw quorum.
Hoe weet een knooppunt in welke segmenten andere knooppunten zich bevinden? Op dezelfde manier als andere informatie over andere knooppunten: van de transmissies die elk knooppunt naar het netwerk uitzendt wanneer de stemstatus verandert. Elke uitzending bevat informatie over de segmenten van het verzendende knooppunt. Het SCP-witboek specificeert geen communicatiemechanisme. Implementaties gebruiken doorgaans voor gegarandeerde uitzending van berichten over het hele netwerk.
Bedenk dat in het niet-federale Byzantijnse systeem van overeenkomsten een quorum wordt gedefinieerd als een meerderheid van alle knooppunten. Het Byzantijnse overeenkomstsysteem is ontworpen vanuit het perspectief van de vraag: hoeveel oneerlijke knooppunten kan het systeem tolereren? In een systeem van N-knooppunten dat is ontworpen om f-storingen te overleven, zou een knooppunt vooruitgang moeten kunnen boeken door feedback te ontvangen van N-f-peers, aangezien f van hen mogelijk niet beschikbaar is. Maar nadat we een antwoord hebben ontvangen van N−f peers, kunnen we aannemen dat alle f peers (waarvan het knooppunt geen antwoord heeft ontvangen) feitelijk eerlijk zijn. F van de N-f peers (waarvan het antwoord is ontvangen) zijn dus kwaadaardig. Om knooppunten tot dezelfde consensus te laten komen, moet de meerderheid van de resterende knooppunten eerlijk zijn, dat wil zeggen dat N−f groter moet zijn dan 2f of N > 3f. Een systeem dat is ontworpen om f-fouten te overleven, heeft dus doorgaans een totaal van N=3f+1 knooppunten en een quorumgrootte van 2f+1. Zodra een voorstel de quorumdrempel overschrijdt, is de rest van het netwerk ervan overtuigd dat eventuele concurrerende voorstellen zullen mislukken. Dit is hoe het netwerk convergeert naar het resultaat.
Maar in een federaal Byzantijns overeenkomstsysteem kan er niet alleen geen meerderheid zijn (omdat niemand de totale omvang van het netwerk kent), maar is het concept van een meerderheid volkomen nutteloos! Als het lidmaatschap van het systeem open is, kan iemand een meerderheid verwerven door simpelweg een zogenaamde Sybil-aanval uit te voeren: herhaaldelijk lid worden van het netwerk via meerdere knooppunten. Dus waarom kan transitieve slice-sluiting worden genoemd? quorum, en hoe kan zij concurrerende voorstellen onderdrukken?
Technisch gezien absoluut niet! Stel je een netwerk van zes knooppunten voor, waarbij twee drielingen geïsoleerd zijn in elkaars quorumsegmenten. De eerste subgroep kan een beslissing nemen waar de tweede nooit van zal horen, en omgekeerd. Dit netwerk kan op geen enkele manier consensus bereiken (behalve door toeval).
Daarom vereist het SCP dat voor federatief stemmen (en om de belangrijke stellingen van het artikel toe te passen) het netwerk een eigenschap moet hebben genaamd snijpunt van quorums. In een netwerk met deze eigenschap overlappen twee quorums die kunnen worden geconstrueerd altijd in ten minste één knooppunt. Voor het bepalen van het heersende sentiment van het netwerk is dit net zo goed als het hebben van een meerderheid. Intuïtief betekent dit dat als een quorum akkoord gaat met stelling X, geen enkel ander quorum ooit met iets anders kan instemmen, omdat het noodzakelijkerwijs een knooppunt uit het eerste quorum zal omvatten dat al op X heeft gestemd.
Als er een kruispunt van quorums in het netwerk is...
...dan kun je twee willekeurige quorums bouwen...
...zullen elkaar altijd kruisen.
(Natuurlijk kunnen overlappende knooppunten Byzantijns liegen of anderszins slecht blijken te zijn. In dit geval helpt het quorumkruispunt het netwerk helemaal niet tot overeenstemming te komen. Om deze reden zijn veel van de resultaten in het SCP-witboek gebaseerd op expliciete aannames, zoals wat er overblijft in de netwerkquorumovergang zelfs na het verwijderen van slechte knooppunten. Laten we voor de eenvoud deze aannames achterwege laten impliciet in de rest van het artikel).
Het lijkt misschien onredelijk om te verwachten dat een betrouwbare quorumoverschrijding mogelijk is in een netwerk van onafhankelijke knooppunten. Maar er zijn twee redenen waarom dit zo is.
De eerste reden is het bestaan van internet zelf. Het internet is een perfect voorbeeld van een netwerk van onafhankelijke knooppunten met elkaar kruisende quorums. De meeste knooppunten op het internet zijn slechts met een paar andere lokale knooppunten verbonden, maar deze kleine sets overlappen elkaar genoeg zodat elk knooppunt vanaf elk ander knooppunt langs een bepaalde route kan worden bereikt.
De tweede reden is specifiek voor het Stellar-betalingsnetwerk (het meest voorkomende gebruik van SCP). Elk actief op het Stellar-netwerk heeft een uitgever, en de richtlijnen van Stellar vereisen dat elke uitgever een of meer knooppunten op het netwerk aanwijst om inwisselingsverzoeken te verwerken. Het is in uw eigen belang om deze knooppunten direct of indirect op te nemen in quorumsegmenten voor elk item waarin u geïnteresseerd bent. Quorums voor alle knooppunten die geïnteresseerd zijn in een bepaald activum zullen elkaar dan op zijn minst overlappen op die inwisselingsknooppunten. Knooppunten die geïnteresseerd zijn in meerdere activa zullen alle aflossingsknooppunten van de respectievelijke emittenten opnemen in hun quorumsegmenten, en zij zullen proberen alle activa samen te voegen. Bovendien alle activa die niet op deze manier aan anderen op het netwerk zijn gekoppeld, en mag niet worden aangesloten - dit is zo ontworpen dat er geen quorumoverlap is voor dit netwerk (banken uit de dollarzone willen bijvoorbeeld soms handelen met banken uit de eurozone en banken uit de pesozone, dus ze zitten op hetzelfde netwerk, maar geen van hen geeft om het aparte netwerk van kinderen die honkbalkaarten verkopen).
Natuurlijk ожидание quorumoverschrijding is dat niet garantie. Andere Byzantijnse overeenkomstsystemen danken een groot deel van hun complexiteit aan de garantie van quorums. Een belangrijke innovatie van SCP is dat het de verantwoordelijkheid voor het creëren van quorums wegneemt van het consensusalgoritme zelf en dit naar het applicatieniveau brengt. Hoewel federatief stemmen dus algemeen genoeg is om over welke kwestie dan ook te stemmen, hangt de betrouwbaarheid ervan feitelijk in belangrijke mate af van de bredere betekenis van deze betekenissen. Sommige hypothetische toepassingen zijn wellicht niet zo bevorderlijk voor het creëren van goed verbonden netwerken als andere.
Stemmen, acceptatie en bevestiging
In een federatieve stemronde begint een knooppunt optioneel te stemmen voor een bepaalde waarde V. Dit betekent dat een bericht naar het netwerk wordt uitgezonden: "Ik ben knooppunt N, mijn quorumsegmenten zijn Q en ik stem voor V." Wanneer een knooppunt op deze manier stemt, belooft het dat het nooit tegen V heeft gestemd en dat het ook nooit zal doen.
Bij peer-to-peer-uitzendingen ziet elk knooppunt hoe de anderen stemmen. Zodra een knooppunt voldoende van deze berichten heeft verzameld, kan het quorumsegmenten volgen en proberen quorums te vinden. Als hij een quorum van collega's ziet die ook op V stemmen, kan hij doorgaan adoptie V en zend dit nieuwe bericht uit naar het netwerk: "Ik ben knooppunt N, mijn quorumsegmenten zijn Q en ik accepteer V." Acceptatie biedt een sterkere garantie dan eenvoudigweg stemmen. Wanneer een knooppunt voor V stemt, kan het nooit voor andere opties stemmen. Maar als een knooppunt V accepteert, zal geen enkel knooppunt op het netwerk ooit de andere optie accepteren (Stelling 8 in het SCP-whitepaper bewijst dit).
Natuurlijk is de kans groot dat er niet onmiddellijk een quorum van knooppunten zal zijn die het eens zijn met V. Andere knooppunten kunnen voor andere waarden stemmen. Maar er is een andere manier waarop een knooppunt van eenvoudig stemmen naar acceptatie kan gaan. N kan een andere waarde voor W accepteren, zelfs als hij er niet voor heeft gestemd, en zelfs als hij er geen quorum voor ziet. Om te beslissen uw stem te wijzigen, hoeft u alleen maar te kijken blokkeerset knooppunten die W hebben geaccepteerd. Een blokkeringsset is één knooppunt uit elk van de quorumsegmenten N. Zoals de naam al doet vermoeden, kan deze окировать enige andere betekenis. Als alle knooppunten in zo'n verzameling W accepteren, zal het (volgens Stelling 8) nooit mogelijk zijn om een quorum te vormen dat een andere waarde aanneemt, en daarom is het ook veilig voor N om W te accepteren.
Knooppunt N met drie quorumsegmenten.
BDF is een blokkeringsset voor N: het bevat één knooppunt uit elk van de plakjes van N.
BE is ook een blokkeringsset voor N omdat E in twee plakjes van N voorkomt.
Maar de blokkerende set is geen quorum. Het zou te gemakkelijk zijn om knooppunt N te misleiden om de gewenste waarde te accepteren als het voldoende zou zijn om slechts één knooppunt in elk van de segmenten van N te hacken. Daarom is het accepteren van de waarde niet het einde van de stemming. In plaats daarvan moet N de waarde bevestigen, dat wil zeggen, een quorum van knooppunten zien die deze accepteren. Als het zo ver komt, zal, zoals het SCP-whitepaper bewijst (in Stelling 11), de rest van het netwerk uiteindelijk ook dezelfde waarde bevestigen, zodat N de federatieve stemming zal beëindigen met een bepaalde waarde als resultaat.
Federatieve stemming.
Het proces van stemmen, aanvaarden en bevestigen vormt één volledige ronde van federatieve stemmingen. Het Stellar-consensusprotocol combineert veel van deze rondes om een compleet consensussysteem te creëren.
Stellair consensusprotocol
De twee belangrijkste eigenschappen van een consensussysteem zijn − veiligheid и overlevingskansen. Een consensusalgoritme is 'veilig' als het nooit verschillende resultaten kan opleveren voor verschillende deelnemers (Bob's kopie van de geschiedenis zal Carol nooit tegenspreken). ‘Leefbaarheid’ betekent dat het algoritme altijd een resultaat zal opleveren, dat wil zeggen dat het niet vastloopt.
Beschreven federale stemprocedure veilig in de zin dat als een knooppunt de waarde van V bevestigt, geen ander knooppunt de andere waarde zal bevestigen. Maar “zal geen andere betekenis bevestigen” betekent niet dat het noodzakelijkerwijs iets zal bevestigen. Deelnemers kunnen op zoveel verschillende waarden stemmen dat niets de acceptatiedrempel haalt. Dit betekent dat er bij federale stemmingen nee is overlevingskansen.
Het Stellar-consensusprotocol maakt gebruik van federatief stemmen op een manier die zowel veiligheid als overlevingskansen garandeert. (De veiligheids- en overlevingsgaranties van SCP hebben een theoretische limiet. Het ontwerp kiest voor een zeer sterke veiligheidsgarantie, waarbij een kleine beperking van de overlevingskansen wordt opgeofferd, maar als er voldoende tijd is, is het zeer waarschijnlijk dat consensus wordt bereikt.) Kort gezegd is het de bedoeling om meerdere federatieve stemmen te hebben over meerdere waarden, totdat een van hen alle hieronder beschreven SCP-stemfasen doorloopt.
De waarden waarover het SCP consensus zoekt kunnen de transactiegeschiedenis zijn of een lunchbestelling of iets anders, maar het is belangrijk op te merken dat dit niet de waarden zijn die worden geaccepteerd of bevestigd. In plaats daarvan vindt federale stemming plaats volgens uitspraken over deze waarden.
De eerste federale stemrondes vinden plaats op nominatie fase (nominatiefase), op een reeks uitspraken als ‘Ik nomineer V’, misschien voor veel verschillende waarden van V. Het doel van nominatie is om een of meer uitspraken te vinden die door acceptatie en bevestiging gaan.
Nadat het SCP verifieerbare kandidaten heeft gevonden, gaat het naar de stemfase, waar het doel is om een bepaalde kandidaat te vinden nieuwsbrief (dat wil zeggen een container voor de voorgestelde waarde) en een quorum dat kan declareren verbinden ervoor (toewijden). Als een quorum tot stemming overgaat, wordt de waarde ervan aanvaard als consensus. Maar voordat een knooppunt over een stembiljet kan stemmen, moet het eerst bevestigen annulering alle stembiljetten met een lagere tellerwaarde. Deze stappen – het annuleren van stembiljetten om er een te vinden die kan worden vastgelegd – omvatten meerdere stemrondes over meerdere stembiljetten.
In de volgende paragrafen worden de benoeming en het stemmen gedetailleerder beschreven.
Voordracht
Aan het begin van de nominatiefase kan elk knooppunt spontaan een waarde voor V kiezen en stemmen op de stelling “Ik nomineer V.” Het doel in dit stadium is om de nominatie van een bepaalde waarde te bevestigen door middel van een federatieve stemming.
Misschien stemmen voldoende knooppunten over voldoende verschillende voorstellen, zodat geen enkele nominatie de acceptatiedrempel kan bereiken. Daarom ‘weerspiegelen’ knooppunten, naast het uitzenden van hun eigen nominatiestemmen, de nominaties van hun collega’s. Echo betekent dat als een knooppunt stemt voor nominatie V, maar een bericht ziet van een buur die stemt voor nominatie W, het nu voor zowel V als W zal stemmen. (Niet alle peer-stemmen worden herhaald tijdens de nominatie, omdat dit kan leiden tot een explosie van stemmen). verschillende genomineerden. SCP omvat een mechanisme om deze stemmen te reguleren. Kortom, er is een formule voor het bepalen van de "prioriteit" van een peer vanuit het standpunt van een knooppunt, en alleen de stemmen van knooppunten met hoge prioriteit worden weerspiegeld. Hoe langer de nominatie neemt, hoe lager de drempel, zodat het knooppunt de reeks peers uitbreidt waarvan het de stemmen zal weerspiegelen. De prioriteitsformule omvat het slotnummer als een van de inputs, dus een peer met hoge prioriteit voor één slot kan een peer met lage prioriteit zijn voor een ander, en omgekeerd).
Conceptueel gezien is de nominatie parallel: zowel V als W zijn afzonderlijke federale stemmen, die elk afzonderlijk in staat zijn aanvaarding of bevestiging te bereiken. In de praktijk bundelen SCP-protocolberichten deze individuele stemmen samen.
Hoewel stemmen voor de nominatie van V een belofte inhoudt om nooit tegen de nominatie van V te stemmen, wordt op applicatieniveau – in dit geval het SCP – bepaald wat ‘tegen’ betekent. Het SCP ziet geen verklaring die in tegenspraak is met de stem "Ik nomineer X", dat wil zeggen dat er geen bericht "Ik ben tegen het nomineren van X" is, dus het knooppunt kan stemmen om waarden te nomineren. Veel van deze nominaties zullen nergens toe leiden, maar uiteindelijk zal het knooppunt een of meer waarden kunnen accepteren of bevestigen. Zodra een genomineerde is bevestigd, wordt hij kandidaat.
SCP-nominatie met behulp van federatieve stemming. Er kunnen veel ‘B’-waarden zijn die door collega’s naar voren worden gebracht en door het knooppunt worden ‘weerspiegeld’.
Nominaties kunnen resulteren in meerdere bevestigde kandidaten. Daarom vereist SCP dat de applicatielaag een methode biedt om de kandidaten tot één te combineren composiet (composiet). De verbindingsmethode kan van alles zijn. Het belangrijkste is dat als deze methode deterministisch is, elk knooppunt dezelfde kandidaten zal combineren. In een lunchstemsysteem kan ‘eenwording’ eenvoudigweg betekenen dat een van de twee kandidaten wordt afgewezen. (Maar op een deterministische manier: elk knooppunt moet dezelfde waarde selecteren om te resetten. Bijvoorbeeld de eerdere selectie in alfabetische volgorde). Op het Stellar-betalingsnetwerk, waar over de transactiegeschiedenis wordt gestemd, omvat het samenvoegen van twee voorgestelde genomineerden het samenvoegen van de transacties die ze bevatten en de laatste van hun twee tijdstempels.
Het SCP-whitepaper bewijst (Stelling 12) dat het netwerk aan het einde van de uitbreidingsfase uiteindelijk convergeert naar één enkele samenstelling. Maar er is een probleem: federatief stemmen is een asynchroon protocol (zoals SCP). Met andere woorden, knooppunten worden niet gecoördineerd door de tijd, maar alleen door de berichten die ze verzenden. Vanuit het oogpunt van het knooppunt is het onduidelijk wanneer eindigde uitbreidingsfase. En hoewel alle knooppunten uiteindelijk op hetzelfde composiet zullen uitkomen, kunnen ze onderweg verschillende routes nemen, waardoor ze onderweg verschillende samengestelde kandidaten creëren, en ze kunnen nooit zeggen welke de uiteindelijke is.
Maar het is normaal. Nomineren is slechts voorbereiding. Het belangrijkste is om het aantal kandidaten te beperken om consensus te bereiken, wat tijdens het proces gebeurt stemmen (stemming).
Rennen
Bulletin is een stel , waarbij counter een geheel getal is dat begint bij 1 en waarde een kandidaat is uit de nominatiefase. Dit kan de eigen kandidaat van een knooppunt zijn, of de kandidaat van een naburig knooppunt die door dat knooppunt wordt geaccepteerd. Grof gezegd omvat een stemming herhaalde pogingen om het netwerk te dwingen een consensus te bereiken over een bepaalde kandidaat op een bepaald stembiljet, door mogelijk veel gefedereerde stemmen op stemverklaringen te houden. Tellers op de stembiljetten houden de gedane pogingen bij, en stembiljetten met een hogere telling hebben voorrang op stembiljetten met een lagere telling. Als de nieuwsbrief vastloopt, begint een nieuwe stemming, die nu op het stembiljet staat .
Het is belangrijk om onderscheid te maken betekenis (wat moet de lunchbestelling bijvoorbeeld zijn: pizza of salades), nieuwsbrieven (tegenwaardepaar) en verklaring over stembiljetten. De SCP-ronde omvat verschillende federale stemrondes, met name over de volgende uitspraken:
- "Ik ben klaar om stembiljet B te plegen" en
- "Ik kondig de toewijzing van stembiljet B aan"
Vanuit het perspectief van een bepaald knooppunt wordt consensus bereikt wanneer het een stembiljet B vindt waarvoor het de verklaring "Ik voer stembiljet B" kan bevestigen (dat wil zeggen, een quorum kan vinden dat dit accepteert). Vanaf dit punt is het veilig om te handelen op basis van de waarde die is opgegeven in B, bijvoorbeeld door deze bestelling voor de lunch te plaatsen. Het heet externalisering betekenissen. Zodra de aanvaarding van het stembiljet is bevestigd, kan een knooppunt er zeker van zijn dat elk ander knooppunt dezelfde waarde heeft geëxternaliseerd of dit in de toekomst zal doen.
Hoewel veel federatieve stemmingen conceptueel worden uitgevoerd op basis van claims voor veel verschillende stembiljetten, wisselen ze niet zoveel berichten uit omdat elk bericht een aantal stembiljetten omvat. Eén boodschap promoot dus de stand van veel federatieve stemmen tegelijk, bijvoorbeeld: “Ik accepteer stembiljetten variërend van voor "
Wat betekenen de termen ‘voorbereid’ en ‘commit’?
Een knooppunt stemt voor een stemming als het er zeker van is dat andere knooppunten geen stembiljetten met verschillende waarden zullen uitbrengen. Het overtuigen hiervan is het doel van het opstellen van de aanvraag. Een stem die zegt: "Ik ben klaar om stembiljet B uit te voeren" is een belofte om nooit een stembiljet uit te brengen dat kleiner is dan B, dat wil zeggen met een kleinere telling (SCP vereist dat de waarden in stembiljetten in een bepaalde volgorde staan. Aldus nieuwsbrief minder , als N1
Waarom betekent “Ik ben klaar om stembiljet B uit te brengen” “Ik beloof nooit stembiljetten uit te brengen die kleiner zijn dan B”? Omdat SCP abort definieert als het tegenovergestelde van commit. Een stemming om een stembiljet voor te bereiden houdt ook een stemming in om andere stembiljetten te diskwalificeren, en zoals we eerder hebben besproken, betekent stemmen voor één ding de belofte om er nooit tegen te stemmen.
Voordat een commit wordt uitgezonden, moet een knooppunt eerst een bulletin vinden waarvan het kan bevestigen dat het is voorbereid. Met andere woorden, het voert een federatieve stemming uit over het onderwerp 'Ik ben klaar om stembiljet B uit te voeren', mogelijk op veel verschillende stembiljetten, totdat het er een vindt die een quorum accepteert.
Waar komen de stembiljetten vandaan om de stemming voor te bereiden? Eerst zendt het knooppunt voorbereidingen uit om op <1,C> te stemmen, waarbij C de samengestelde kandidaat is die in de nominatiefase is geproduceerd. Maar zelfs nadat de voorbereidingen voor het stemmen zijn begonnen, kunnen nominaties ertoe leiden dat extra kandidaten nieuwe stembiljetten lijken te worden. Ondertussen kunnen peers verschillende kandidaten hebben, en ze kunnen een blokkeringsset vormen die accepteert: "Ik ben klaar om de B2-stemming te plegen", wat het knooppunt zal overtuigen om het ook te accepteren. Ten slotte is er een time-outmechanisme dat nieuwe rondes van gefedereerde stemmingen genereert over nieuwe stembiljetten met hogere aantallen als de huidige stembiljetten vastlopen.
Zodra het knooppunt een stembiljet B vindt waarvan het kan bevestigen dat het is voorbereid, zendt het een nieuw bericht uit: Stembiljet B vastleggen. Deze stemming vertelt collega's dat het knooppunt B nooit zal opgeven. Sterker nog, als B een stembiljet is en vervolgens 'Stemming vastleggen " betekent de onvoorwaardelijke toestemming om te stemmen voor de gereedheid van elk stembiljet tot <∞, s>. Deze extra waarde helpt andere peers de commit-peer in te halen als ze zich nog in een eerdere fase van het protocol bevinden.
In dit stadium is het de moeite waard nogmaals te benadrukken dat dit asynchrone protocollen zijn. Het feit dat één node upvotes verzendt voor een commit betekent niet dat zijn collega's dat ook doen. Sommigen van hen stemmen misschien nog steeds over verklaringen ter voorbereiding op de stemming, anderen hebben de betekenis misschien al geëxternaliseerd. SCP legt uit hoe een knooppunt elk type peer-bericht moet verwerken, ongeacht de fase ervan.
Als het bericht "Ik heb een commit aangekondigd » kan niet worden ontvangen of bevestigd, dat wil zeggen de waarschijnlijkheid dat het bericht wordt geaccepteerd of bevestigd of - of in ieder geval een stembiljet met de waarde C, en geen ander, aangezien het knooppunt al heeft beloofd nooit te zullen annuleren . Tegen de tijd dat een knooppunt stemmen voor een commit uitzendt, zal het C of niets zijn, afhankelijk van hoe ver de consensus gaat. Dit is echter nog niet genoeg om het knooppunt C te laten externaliseren. Sommige Byzantijnse collega's (die minder dan een quorum vormen, gebaseerd op onze veiligheidsaannames) kunnen tegen het knooppunt liegen. Het accepteren en vervolgens bevestigen van een stembiljet (of een reeks stembiljetten) is wat het knooppunt het vertrouwen geeft om C uiteindelijk te externaliseren.
SCP-stemmen via federatieve stemming. Niet getoond: De timer kan op elk moment aflopen, waardoor het aantal stemmen op het stembiljet toeneemt (en mogelijk een nieuwe samenstelling van extra genomineerde kandidaten ontstaat).
En het is alles! Zodra het netwerk een consensus heeft bereikt, is het klaar om dit keer op keer te doen. Op het Stellar-betalingsnetwerk gebeurt dit ongeveer eens in de vijf seconden: een prestatie die zowel de veiligheid als de overlevingskansen vereist die door SCP worden gegarandeerd.
Het SCP kan dit bereiken door te vertrouwen op meerdere stemrondes. Gefedereerd stemmen wordt mogelijk gemaakt door het concept van quorumplakken: sets van peers die elk knooppunt heeft besloten te vertrouwen als onderdeel van zijn (subjectieve) quorum. Deze configuratie betekent dat zelfs in een netwerk met open lidmaatschap en Byzantijnse misleidingen consensus kan worden bereikt.
Verder lezen
- Het originele SCP-whitepaper is te vinden En ontwerpspecificaties voor de implementatie ervan.
- De oorspronkelijke auteur van het SCP-protocol, David Mazier, legt het op een vereenvoudigde (maar nog steeds technische) manier uit. .
- Het zal je misschien verbazen dat je de termen ‘mijnbouw’ of ‘bewijs van werk’ in dit artikel niet tegenkomt. SCP gebruikt deze methoden niet, maar sommige andere consensusalgoritmen wel. Zane Witherspoon schreef toegankelijk .
- een eenvoudig netwerk dat consensus bereikt in één volledige SCP-ronde.
- Voor lezers die geïnteresseerd zijn in SCP-implementaties: zie , gebruikt door het Stellar-betalingsnetwerk, of , die ik heb geschreven voor een beter begrip van SCP.
Bron: www.habr.com