Die Stellar konsensus protokol is die eerste keer beskryf in David Mazier in 2015. Dit is 'n "federale Bisantynse ooreenkomsstelsel" wat gedesentraliseerde, leierlose rekenaarnetwerke toelaat om doeltreffend konsensus oor 'n besluit te bereik. Die Stellar-betalingsnetwerk gebruik die Stellar Consensus Protocol (SCP) om 'n konsekwente transaksiegeskiedenis te handhaaf wat vir alle deelnemers sigbaar is.
Konsensusprotokolle word as moeilik beskou om te verstaan. SCP is eenvoudiger as die meeste van hulle, maar deel steeds hierdie reputasie – deels weens die verkeerde idee dat “federated voting”, wat die onderwerp van die eerste helfte van die wetenskaplike artikel is, SCP is. Maar dis nie waar nie! Dit is net 'n belangrike bousteen wat die tweede helfte van die artikel gebruik om te skep werklike Stellar konsensus protokol.
In hierdie artikel sal ons kortliks verduidelik wat 'n "stelsel van ooreenkomste" is, wat dit "Bisantyns" kan maak en hoekom die Bisantynse stelsel "federaal" maak. Ons sal dan die gefedereerde stemprosedure verduidelik wat in die SCP-artikel beskryf word, en laastens sal ons die SCP-protokol self verduidelik.
Ooreenkomsstelsels
'n Stelsel van ooreenkomste laat 'n groep deelnemers toe om 'n konsensus te bereik oor 'n onderwerp, soos wat om vir middagete te bestel.
By Interstellar het ons ons eie eetooreenkomsstelsel geïmplementeer: ons bestel wat ons bedryfsbestuurder, John, sê. Dit is 'n eenvoudige en effektiewe ooreenkomsstelsel. Ons almal vertrou John en glo dat hy elke dag iets interessants en voedsaam sal vind.
Maar wat as John ons vertroue misbruik? Hy kan eiehandig besluit dat ons almal vegane moet word. Oor 'n week of twee sal ons hom waarskynlik omverwerp en die mag aan Elizabeth oorgee. Maar skielik is sy mal oor avokado's met ansjovis en dink almal moet so wees. Mag korrupteer. Dit is dus beter om 'n meer demokratiese metode te vind: 'n manier om seker te maak dat verskillende voorkeure in ag geneem word, terwyl 'n tydige en ondubbelsinnige resultaat verseker word, sodat niemand uiteindelik middagete bestel nie, of vyf mense verskillende bestellings plaas, of die bespreking sloer aan tot in die aand.
Dit wil voorkom asof die oplossing eenvoudig is: hou 'n stem! Maar dit is 'n misleidende indruk. Wie sal die stembriewe afhaal en die uitslae rapporteer? En hoekom moet ander glo wat hy sê? Miskien kan ons op die eerste stem vir 'n leier wat ons vertrou om die stemming te lei - maar wat dit sal lei eerste deur te stem? Wat as ons nie oor 'n leier kan saamstem nie? Of wat as ons 'n ooreenkoms bereik, maar hierdie leier sit vas in 'n vergadering of gaan met siekverlof?
Soortgelyke probleme kom in verspreide rekenaarnetwerke voor. Alle deelnemers of nodusse moet saamstem oor een of ander besluit, soos wie se beurt dit is om 'n gedeelde lêer op te dateer of 'n taak uit die verwerkingstou te verwyder. In 'n cryptocurrency-netwerk moet nodusse herhaaldelik kies hoe die volle storie lyk uit verskeie moontlike weergawes, wat soms bots. Hierdie netwerkooreenkoms verskaf versekering aan die ontvanger dat die muntstuk (a) geldig (nie vervals nie) en (b) nog nie elders bestee is nie. Dit verseker ook dat hy die munte in die toekoms sal kan spandeer omdat die nuwe ontvanger dieselfde waarborge sal hê om dieselfde redes.
Enige konsensusstelsel in 'n verspreide rekenaarnetwerk moet foutverdraagsaam wees: dit moet konsekwente resultate lewer ten spyte van foute soos stadige skakels, nie-reagerende nodusse en verkeerde boodskapbestelling. Bisantyns Die ooreenkomsstelsel is addisioneel bestand teen "Bisantynse" foute: nodusse wat vals inligting gee, hetsy as gevolg van 'n fout of in 'n doelbewuste poging om die stelsel te ondermyn of voordeel te verkry. "Bisantynse" foutverdraagsaamheid - die vermoë om 'n groepbesluit te vertrou selfs wanneer sommige groeplede mag lieg of andersins nie die reëls van besluitneming volg nie - word genoem wat probeer het om die aanval te koördineer. by Anthony Stevens.
Oorweeg kripto-munteienaar Alice, wat moet kies tussen die koop van heerlike roomys by Bob en die delging van Carol se skuld. Miskien wil Alice albei gelyktydig betaal deur dieselfde muntstuk op bedrieglike wyse te spandeer. Om dit te doen, moet sy Bob se rekenaar oortuig dat die munt nooit aan Carol betaal is nie, en Carol se rekenaar oortuig dat die munt nooit aan Bob betaal is nie. Die Bisantynse stelsel van ooreenkomste maak dit feitlik onmoontlik, met behulp van 'n vorm van meerderheidsheerskappy genoem kworum. 'n Nodus in so 'n netwerk weier om na 'n bepaalde weergawe van geskiedenis te beweeg totdat dit sien dat 'n voldoende aantal eweknieë - 'n kworum - tot so 'n oorgang instem. Sodra dit gebeur, sal hulle 'n stemblok vorm wat groot genoeg is om die oorblywende netwerknodusse te dwing om met hul besluit saam te stem. Alice kan sommige nodusse dwing om namens haar te lieg, maar as die netwerk groot genoeg is, sal haar poging oorweldig word deur die stemme van eerlike nodusse.
Hoeveel nodusse word benodig vir kworum? Op 'n minimum, 'n meerderheid, of liewer, 'n gekwalifiseerde meerderheid om foute en bedrog te bekamp. Maar om die meerderheid te tel, moet jy die totale aantal deelnemers ken. By die Interstellar-kantoor of by die distriksverkiesings is hierdie getalle maklik om uit te vind. Maar as jou groep 'n losweg gedefinieerde netwerk is waarin nodusse na goeddunke kan in- en vertrek sonder goedkeuring van die sentrum, dan moet jy federale 'n Bisantynse ooreenkomsstelsel wat in staat is om kworums te bepaal nie uit 'n voorafbepaalde lys nodusse nie, maar dinamies, uit 'n voortdurend veranderende en onvermydelik onvolledige momentopname van nodusse op 'n gegewe tydstip.
Dit lyk dalk onmoontlik om 'n kworum te skep vanuit die perspektief van 'n enkele nodus in 'n groot netwerk, maar dit is moontlik. So 'n kworum kan selfs die resultate van gedesentraliseerde stemming waarborg. Die SCP-witskrif wys hoe om dit te doen deur 'n prosedure genoem deur federale stemming.
Vir die ongeduldige
Die res van die artikel beskryf gefedereerde stemming en die Stellar-konsensusprotokol in meer besonderhede. As jy nie in die besonderhede belangstel nie, hier is 'n algemene oorsig van die proses.
- Die nodusse voer rondes van federale stemming oor "genomineerdes". 'n Federale stemronde beteken:
- Die nodus stem vir een of ander stelling, byvoorbeeld, "Ek stel die waarde van V voor";
- Die nodus luister na die maats se stemme totdat dit een kry wat kan "ontvang";
- Die nodus soek 'n "kworum" vir hierdie bewering. 'n Kworum "bevestig" die genomineerde.
- Sodra 'n nodus een of meer genomineerdes kan bevestig, poog dit om die "stembrief" deur middel van verskeie rondes van federatiewe stemming te "voorberei".
- Sodra 'n nodus in staat is om te verifieer dat die stembrief gereed is, poog dit om dit te pleeg deur nog meer rondtes van gefedereerde stemming.
- Sodra 'n nodus 'n pleging van 'n stembrief kan bevestig, kan dit die waarde van daardie stembrief "eksternaliseer" deur dit as 'n konsensusresultaat te gebruik.
Hierdie stappe behels verskeie rondtes van gefedereerde stemming, wat gesamentlik een SCP-ronde vorm. Kom ons kyk van naderby na wat by elke stap gebeur.
Gefedereerde stemming
Gefedereerde stemming is 'n prosedure om te bepaal of die netwerk oor 'n voorstel kan saamstem. In die stemronde moet elke nodus een van potensieel baie moontlike waardes kies. Dit kan dit nie doen tensy dit vol vertroue is dat ander nodusse in die netwerk nie 'n ander uitkoms sal kies nie. Om seker te maak hiervan, ruil nodusse 'n stortvloed boodskappe heen en weer sodat almal bevestigWat kworum knope neem dieselfde besluit. Die res van hierdie afdeling verduidelik die terme in hierdie sin en hoe die hele prosedure plaasvind.
Kworums en kworumskywe
Kom ons begin deur 'n kworum te definieer. Soos ons hierbo bespreek het, in 'n gedesentraliseerde netwerk met dinamiese lidmaatskap, is dit onmoontlik om vooraf die aantal nodusse te weet en dus hoeveel nodig is vir die meerderheid. Gefedereerde stemming los hierdie probleem op deur 'n nuwe idee bekend te stel kworum sny (kworumskyfie): 'n Klein stel eweknieë wat 'n nodus vertrou om stemstatusinligting aan die res van die netwerk te kommunikeer. Elke nodus definieer sy eie kworumskyfie (waarvan dit 'n de facto lid word).
Kworumvorming begin met 'n kworumsnit. Vir elke nodus word sy gesnyde nodusse bygevoeg. Dan word die snyterme bygevoeg hierdie nodusse en so aan. Soos jy voortgaan, is daar meer en meer nodusse wat jy nie kan byvoeg nie omdat hulle reeds in die sny ingesluit is. Wanneer daar nie meer nuwe nodusse is om by te voeg nie, stop die proses: ons het 'n kworum gevorm deur die "oorgangssluiting" van die kworumsnit van die aanvanklike nodus.
Om kworum van 'n gegewe nodus te vind...
... voeg lede van sy sny by...
...dan voeg ons snylede van hierdie nodusse by.
Ons gaan voort totdat daar geen nodusse oor is om by te voeg nie.
Daar is geen nodusse oor om by te voeg nie. Dit is 'n kworum.
Trouens, elke nodus kan in meer as een sny voorkom. Om 'n kworum te vorm, kies slegs een van die skywe en voeg lede by; kies dan enige sny vir elk van die lede en voeg lede by van hierdie sny en so aan. Dit beteken dat elke nodus 'n lid van baie moontlike kworums is.
Kies slegs een kworumskyf by elke stap.
Een moontlike kworum. Of 'n alternatief...
...kies ander snye...
…(wanneer dit moontlik is) …
... skep nog 'n kworum.
Hoe weet 'n nodus in watter skywe ander nodusse is? Op dieselfde manier as ander inligting oor ander nodusse: van die uitsendings wat elke nodus na die netwerk uitsaai wanneer sy stemtoestand verander. Elke uitsending bevat inligting oor die stuurnodus se snye. Die SCP-witskrif spesifiseer nie 'n kommunikasiemeganisme nie. Implementerings gebruik gewoonlik vir gewaarborgde uitsaai van boodskappe regdeur die netwerk.
Onthou dat in die nie-federale Bisantynse stelsel van ooreenkomste, 'n kworum gedefinieer word as 'n meerderheid van alle nodusse. Die Bisantynse ooreenkomsstelsel is ontwerp vanuit die oogpunt van die vraag: hoeveel oneerlike nodusse kan die stelsel duld? In 'n stelsel van N nodusse wat ontwerp is om f mislukkings te oorleef, behoort 'n nodus in staat te wees om vordering te maak deur terugvoer van N-f eweknieë te ontvang aangesien f van hulle af kan wees. Maar nadat ons 'n reaksie van N-f eweknieë ontvang het, kan ons aanvaar dat alle f eweknieë (waaruit die nodus nie 'n reaksie ontvang het nie) eintlik eerlik is. Dus, f uit N−f eweknieë (waarvan die reaksie ontvang is) is kwaadwillig. Vir nodusse om tot dieselfde konsensus te kom, moet die meerderheid van die oorblywende nodusse eerlik wees, dit wil sê, ons moet N−f groter as 2f of N > 3f wees. So tipies sal 'n stelsel wat ontwerp is om f mislukkings te oorleef, 'n totaal van N=3f+1 nodusse en 'n kworumgrootte van 2f+1 hê. Sodra 'n voorstel die kworumdrempel verbysteek, is die res van die netwerk oortuig dat enige mededingende voorstelle sal misluk. Dit is hoe die netwerk na die resultaat konvergeer.
Maar in 'n federale Bisantynse ooreenkomsstelsel kan daar nie net 'n meerderheid wees nie (omdat niemand die totale grootte van die netwerk ken nie), maar die konsep van 'n meerderheid is heeltemal nutteloos! As lidmaatskap in die stelsel oop is, dan kan iemand 'n meerderheid kry bloot deur 'n sogenaamde Sybil-aanval uit te voer: herhaaldelik by die netwerk aan te sluit oor verskeie nodusse. So hoekom kan transitiewe sny sluiting genoem word kworum, en hoe is dit in staat om mededingende voorstelle te onderdruk?
Tegnies, geen manier nie! Stel jou 'n netwerk van ses nodusse voor, waar twee drielinge in mekaar se kworumskywe geïsoleer is. Die eerste subgroep kan 'n besluit neem waarvan die tweede nooit sal hoor nie, en omgekeerd. Daar is geen manier vir hierdie netwerk om konsensus te bereik nie (behalwe toevallig).
Daarom vereis SCP dat vir gefedereerde stemming (en vir die belangrike stellings van die vraestel om van toepassing te wees), die netwerk 'n eiendom moet hê genaamd kruising van kworums. In 'n netwerk met hierdie eienskap oorvleuel enige twee kworums wat gekonstrueer kan word altyd in ten minste een nodus. Om die heersende sentiment van die netwerk te bepaal, is dit so goed as om 'n meerderheid te hê. Intuïtief beteken dit dat indien enige kworum tot stelling X instem, geen ander kworum ooit tot iets anders kan instem nie, want dit sal noodwendig een of ander nodus van die eerste kworum wat reeds vir X gestem het, insluit.
As daar 'n kruising van kworums in die netwerk is...
...dan enige twee kworums wat jy kan bou...
...sal altyd kruis.
(Natuurlik kan oorvleuelende nodusse Bisantyns-lê of andersins sleg blyk te wees. In hierdie geval help die kworumkruising glad nie dat die netwerk saamstem nie. Om hierdie rede is baie van die resultate in die SCP-witskrif gebaseer op eksplisiete aannames, soos wat in die netwerkkworumkruising oorbly selfs nadat slegte nodusse verwyder is. Vir eenvoud laat ons hierdie aannames implisiete in die res van die artikel).
Dit lyk dalk onredelik om te verwag dat 'n betroubare kworumkruising moontlik is in 'n netwerk van onafhanklike nodusse. Maar daar is twee redes waarom dit so is.
Die eerste rede is die bestaan van die internet self. Die internet is 'n perfekte voorbeeld van 'n netwerk van onafhanklike nodusse met kruisende kworums. Die meeste nodusse op die internet koppel aan slegs 'n paar ander plaaslike nodusse, maar hierdie klein stelle oorvleuel genoeg dat elke nodus van elke ander nodus langs die een of ander roete bereik kan word.
Die tweede rede is spesifiek vir die Stellar-betalingsnetwerk (die mees algemene gebruik van SCP). Elke bate op die Stellar-netwerk het 'n uitreiker, en Stellar se riglyne vereis dat elke uitreiker een of meer nodusse op die netwerk aanwys om aflossingversoeke te verwerk. Dit is in jou beste belang om hierdie nodusse direk of indirek in kworumskywe in te sluit vir elke bate waarin jy belangstel. Kworums vir alle nodusse wat in 'n gegewe bate belangstel, sal dan ten minste by daardie aflossingsnodes oorvleuel. Nodusse wat in veelvuldige bates belangstel, sal alle aflossingsnodes van die onderskeie uitreikers in hul kworumskywe insluit, en hulle sal poog om alle bates saam te voeg. Daarbenewens, enige bates wat nie op hierdie manier gekoppel is aan ander op die netwerk, en moet nie gekoppel word nie - dit is so ontwerp dat daar geen kworum oorvleueling vir hierdie netwerk is nie (byvoorbeeld, banke van die dollarsone wil soms handel dryf met banke van die eurosone en banke uit die pesosone, dus is hulle op dieselfde netwerk, maar geen van hulle gee om vir die aparte netwerk van kinders, wat bofbalkaarte verkoop).
Van die kursus, verwagting kworumkruising is nie waarborg. Ander Bisantynse ooreenkomsstelsels het baie van hul kompleksiteit te danke aan die waarborg van kworums. 'n Belangrike innovasie van SCP is dat dit die verantwoordelikheid vir die skep van kworums van die konsensusalgoritme self verwyder en dit na die toepassingsvlak bring. Alhoewel gefedereerde stemming dus algemeen genoeg is om oor enige kwessie te stem, hang die betroubaarheid daarvan eintlik krities af van die breër betekenis van hierdie betekenisse. Sommige hipotetiese gebruike is dalk nie so bevorderlik vir die skep van goed gekoppelde netwerke soos ander nie.
Stem, aanvaarding en bevestiging
In 'n gefedereerde stemronde begin 'n nodus opsioneel vir een of ander waarde V stem. Dit beteken om 'n boodskap na die netwerk uit te saai: "Ek is node N, my kworumskywe is Q, en ek stem vir V." Wanneer 'n nodus op hierdie manier stem, belowe dit dat dit nog nooit teen V gestem het nie en ook nooit sal nie.
In eweknie-uitsendings sien elke nodus hoe die ander stem. Sodra 'n nodus genoeg van hierdie boodskappe versamel het, kan dit kworumskywe opspoor en probeer om kworums te vind. As hy 'n kworum van eweknieë sien wat ook vir V stem, kan hy voortgaan na aanneming V en saai hierdie nuwe boodskap aan die netwerk uit: "Ek is node N, my kworumskywe is Q, en ek aanvaar V." Aanvaarding bied 'n sterker waarborg as eenvoudige stemming. Wanneer 'n nodus vir V stem, kan dit nooit vir ander opsies stem nie. Maar as 'n nodus V aanvaar, sal geen nodus op die netwerk ooit die ander opsie aanvaar nie (Stelling 8 in die SCP-witskrif bewys dit).
Natuurlik is daar 'n groot waarskynlikheid dat daar nie onmiddellik 'n kworum van nodusse sal wees wat met V saamstem nie. Ander nodusse mag vir ander waardes stem. Maar daar is 'n ander manier vir 'n nodus om van eenvoudige stemming na aanvaarding te beweeg. N mag 'n ander waarde vir W aanvaar, al het hy nie daarvoor gestem nie, en al sien hy nie 'n kworum daarvoor nie. Om te besluit om jou stem te verander, kyk net blokkeer stel nodusse wat W aanvaar het. 'n Blokkeringstel is een nodus van elk van die kworumskywe N. Soos die naam aandui, kan dit blok enige ander betekenis. As alle nodusse in so 'n versameling W aanvaar, sal dit (deur Stelling 8) nooit moontlik wees om 'n kworum te vorm wat 'n ander waarde aanneem nie, en daarom is dit ook veilig vir N om W te aanvaar.
Nodus N met drie kworumskywe.
BDF is 'n blokkeerstel vir N: dit bevat een nodus van elk van die snye N.
BE is ook 'n blokkeerstel vir N omdat E in twee snye N voorkom.
Maar die blokkeerstel is nie 'n kworum nie. Dit sou te maklik wees om nodus N te mislei om die verlangde waarde te aanvaar as dit genoeg was om net een nodus in elk van die snye N te kap. Daarom is die aanvaarding van die waarde nie die einde van die stemming nie. In plaas daarvan moet N die waarde bevestig, dit wil sê, 'n kworum van nodusse sien wat dit aanvaar. As dit so ver kom, dan, soos die SCP-witskrif bewys (in Stelling 11), sal die res van die netwerk ook uiteindelik dieselfde waarde bevestig, dus sal N die gefedereerde stemming beëindig met 'n sekere waarde as resultaat.
Gefedereerde stemming.
Die proses van stemming, aanvaarding en bevestiging vorm een volle rondte van gefedereerde stemming. Die Stellar-konsensusprotokol kombineer baie van hierdie rondtes om 'n volledige konsensusstelsel te skep.
Stellar Consensus Protocol
Die twee belangrikste eienskappe van 'n konsensusstelsel is − veiligheid и oorlewing. ’n Konsensusalgoritme is “veilig” as dit nooit verskillende resultate aan verskillende deelnemers kan gee nie (Bob se kopie van geskiedenis sal Carol nooit weerspreek nie). "Lewenswaardigheid" beteken dat die algoritme altyd 'n resultaat sal lewer, dit wil sê, dit sal nie vashaak nie.
Beskryf federale stemprosedure veilig in die sin dat as 'n nodus die waarde van V bevestig, geen ander nodus die ander waarde sal bevestig nie. Maar "sal nie 'n ander betekenis bevestig nie" beteken nie dat dit noodwendig iets sal bevestig nie. Deelnemers kan oor soveel verskillende waardes stem dat niks die aanvaardingsdrempel sal bereik nie. Dit beteken dat daar by federale stemming geen oorlewing.
Die Stellar-konsensusprotokol gebruik gefedereerde stemming op 'n manier wat beide veiligheid en oorlewing verseker. (SCP se sekuriteit en oorlewingswaarborge het 'n teoretiese limiet. Die ontwerp kies 'n baie sterk sekuriteitswaarborg, wat 'n klein oorlewingsversagting opoffer, maar gegewe genoeg tyd, sal konsensus hoogs waarskynlik bereik word.) In 'n neutedop, die idee is om veelvuldige gefedereerde stemme oor veelvuldige waardes te hê totdat een van hulle deur al die SCP-stemfases wat hieronder beskryf word, haal.
Die waardes waaroor SCP konsensus soek, kan transaksiegeskiedenis of 'n middagetebestelling of iets anders wees, maar dit is belangrik om daarop te let dat dit nie die waardes is wat aanvaar of bevestig word nie. In plaas daarvan vind federale stemming plaas volgens stellings oor hierdie waardes.
Die eerste rondes van federale stemming vind plaas op nominasie stadium (nominasiefase), op 'n stel stellings soos "Ek nomineer V," miskien vir baie verskillende waardes van V. Die doel van nominasie is om een of meer stellings te vind wat deur aanvaarding en bevestiging gaan.
Nadat verifieerbare kandidate gevind is, gaan SCP aan na die stemfase, waar die doel is om 'n sekere nuusbrief (dit wil sê 'n houer vir die voorgestelde waarde) en 'n kworum wat kan verklaar pleeg daarvoor (pleeg). As 'n kworum 'n stembrief pleeg, word die waarde daarvan as die konsensus aanvaar. Maar voordat 'n nodus oor 'n stembrief kan stem, moet dit eers bevestig kansellasie alle stembriewe met 'n laer toonbankwaarde. Hierdie stappe - om stembriewe te kanselleer om een te vind wat gepleeg kan word - behels verskeie rondtes van gefedereerde stemming oor veelvuldige stembrief-eise.
Die volgende afdelings beskryf nominasie en stemming in meer besonderhede.
Benoeming
Aan die begin van die nominasiefase kan elke nodus spontaan 'n waarde vir V kies en stem vir die stelling "Ek nomineer V." Die doel op hierdie stadium is om die benoeming van een of ander waarde deur middel van 'n federatiewe stemming te bevestig.
Miskien stem genoeg nodusse oor voldoende verskillende stellings dat geen nominasie die aanvaardingsdrempel kan bereik nie. Benewens die uitsaai van hul eie nominasiestemme, “reflekteer” nodusse dus die nominasies van hul eweknieë. Echo beteken dat as 'n nodus vir nominasie V stem, maar 'n boodskap sien van 'n buurman wat vir nominasie W stem, sal dit nou vir beide V en W stem. (Nie alle eweknie-stemme word tydens nominasie weerklink nie, want dit kan lei tot 'n ontploffing van verskillende benoemdes. SCP sluit 'n meganisme in om hierdie stemme te reguleer. Kortliks, daar is 'n formule vir die bepaling van die "prioriteit" van 'n eweknie vanuit 'n nodus se oogpunt, en slegs die stemme van hoë prioriteit nodusse word weerspieël. Hoe langer die nominasie neem, hoe laer die drempel, dus brei die nodus stel eweknieë uit wie se stemme dit sal weerspieël. Die prioriteitsformule sluit die gleufnommer as een van sy insette in, dus 'n hoë-prioriteit eweknie vir een gleuf kan 'n lae-prioriteit eweknie vir wees 'n ander, en omgekeerd).
Konseptueel is die nominasie parallel, beide V en W is afsonderlike federale stemme, elkeen individueel in staat om aanvaarding of bevestiging te verkry. In die praktyk pak SCP-protokolboodskappe hierdie individuele stemme saam.
Alhoewel om vir V se nominasie te stem 'n belofte is om nooit teen V se nominasie te stem nie, is dit op die aansoekvlak - in hierdie geval SCP - wat bepaal word wat "teen" beteken. SCP sien nie 'n stelling wat die "Ek nomineer X"-stem weerspreek nie, dit wil sê, daar is geen "Ek is teen die benoeming van X"-boodskap nie, so die nodus kan stem om enige waardes te nomineer. Baie van hierdie nominasies sal nêrens heen gaan nie, maar uiteindelik sal die nodus een of meer waardes kan aanvaar of bevestig. Sodra 'n genomineerde bevestig is, word hy kandidaat.
SCP-benoeming deur gebruik te maak van gefedereerde stemming. Daar kan baie "B"-waardes wees wat deur eweknieë voorgehou word en deur die nodus "weerspieël" word.
Nominasies kan lei tot verskeie bevestigde kandidate. Daarom vereis SCP dat die toepassingslaag een of ander metode verskaf om die kandidate in een te kombineer saamgestelde (saamgestelde). Die aansluitingsmetode kan enigiets wees. Die belangrikste ding is dat as hierdie metode deterministies is, dan sal elke nodus dieselfde kandidate kombineer. In 'n middagete-stemstelsel kan "eenwording" bloot beteken dat een van twee kandidate verwerp word. (Maar op 'n deterministiese manier: elke nodus moet dieselfde waarde kies om terug te stel. Byvoorbeeld, die vroeëre seleksie in alfabetiese volgorde). In die Stellar-betalingsnetwerk, waar oor transaksiegeskiedenis gestem word, behels die samesmelting van twee voorgestelde genomineerdes die samevoeging van die transaksies wat hulle bevat en die jongste van hul twee tydstempels.
Die SCP-witskrif bewys (Stelling 12) dat die netwerk teen die einde van die uitbreidingsfase uiteindelik na 'n enkele samestelling konvergeer. Maar daar is 'n probleem: gefedereerde stemming is 'n asynchrone protokol (soos SCP). Met ander woorde, nodusse word nie deur tyd gekoördineer nie, maar slegs deur die boodskappe wat hulle stuur. Vanuit die nodus se oogpunt is dit onduidelik wanneer geëindig het uitbreiding fase. En alhoewel alle nodusse uiteindelik by dieselfde samestelling sal aankom, kan hulle verskillende roetes langs die pad neem, wat verskillende saamgestelde kandidate langs die pad skep, en kan nooit sê watter een die finale een is nie.
Maar dis normaal. Nominasie is net voorbereiding. Die belangrikste ding is om die aantal kandidate te beperk om konsensus te bereik, wat in die proses plaasvind hardloop vir die amp (stemming).
Hardloop
Bulletin is 'n paartjie , waar teller 'n heelgetal is wat by 1 begin en waarde 'n kandidaat vanaf die nominasiestadium is. Dit kan 'n nodus se eie kandidaat wees of 'n naburige nodus se kandidaat wat deur daardie nodus aanvaar word. Rofweg gesproke behels 'n stembrief herhaalde pogings om die netwerk te dwing om 'n konsensus oor een of ander kandidaat op een of ander stembrief te bereik deur potensieel baie gefedereerde stemme oor stembriefverklarings te hou. Tellers op die stembriewe hou rekord van pogings wat gemaak is, en stembriewe met hoër tellings geniet voorrang bo stembriewe met laer tellings. As die nuusbrief vashaak, 'n nuwe stemming begin, nou op die stembrief .
Dit is belangrik om te onderskei wat beteken (byvoorbeeld, wat moet die middagete bestelling wees: pizza of slaaie), nuusbriewe (teenwaarde-paar) en verklarings oor stembriewe. Die SCP-rondte sluit verskeie rondtes van federale stemming in, veral oor die volgende stellings:
- "Ek is gereed om stembrief B te pleeg" en
- "Ek kondig die pleeg van stembrief B aan"
Vanuit 'n gegewe nodus se perspektief word konsensus bereik wanneer dit 'n stembrief B vind waarvoor dit die stelling "Ek verbind stembrief B" kan bevestig (dit wil sê, vind 'n kworum aanvaar). Van hierdie punt af is dit veilig om op te tree op die waarde wat in B gespesifiseer word - byvoorbeeld om hierdie bestelling vir middagete te plaas. Dit word genoem eksternalisering betekenisse. Sodra aanvaarding van die stembrief bevestig is, kan 'n nodus seker wees dat enige ander nodus dieselfde waarde geëksteraliseer het of dit in die toekoms sal doen.
Alhoewel baie gefedereerde stemme konseptueel uitgevoer word oor eise vir baie verskillende stembriewe, ruil dit nie soveel boodskappe uit nie, want elke boodskap bevat 'n aantal stembriewe. Een boodskap bevorder dus die toestand van baie gefedereerde stemme op een slag, byvoorbeeld: “Ek aanvaar pleeg stembriewe wat wissel van voor "
Wat beteken die terme "voorbereid" en "verbind"?
'n Knooppunt stem om 'n stembrief te pleeg wanneer dit vol vertroue is dat ander nodusse nie stembriewe met verskillende waardes sal pleeg nie. Om dit te oortuig is die doel van die voorbereiding van die aansoek. 'n Stem wat sê "Ek is gereed om stembrief B te pleeg" is 'n belofte om nooit 'n stembrief kleiner as B te pleeg nie, dit wil sê met 'n kleiner telling (SCP vereis dat die waardes in stembriewe in 'n sekere volgorde moet wees. Dus, nuusbrief minder , as N1
Waarom beteken "Ek is gereed om stembrief B te pleeg" "Ek belowe om nooit stembriewe kleiner as B te pleeg nie"? Omdat SCP aborte definieer as die teenoorgestelde van commit. 'n Stem om 'n stembrief voor te berei, behels ook 'n stemming om sommige ander stembriewe te diskwalifiseer, en, soos ons vroeër bespreek het, is om vir een ding te stem 'n belofte om nooit daarteen te stem nie.
Voordat 'n commit uitgesaai word, moet 'n nodus eers 'n bulletin vind wat dit kan bevestig as voorbereid. Met ander woorde, dit voer 'n gefedereerde stemming uit oor die onderwerp "Ek is gereed om stembrief B te pleeg," moontlik op baie verskillende stembriewe, totdat dit een vind wat 'n kworum aanvaar.
Waar kom die stembriewe vandaan om die stemming voor te berei? Eerstens, die nodus saai voorbereidings uit om vir <1,C> te stem, waar C die saamgestelde kandidaat is wat in die nominasiestadium geproduseer word. Selfs nadat voorbereidings vir stemming begin het, kan nominasies egter daartoe lei dat bykomende kandidate nuwe stembriewe word. Intussen kan eweknieë verskillende kandidate hê, en hulle kan 'n blokkeerstel vorm wat aanvaar "Ek is gereed om die B2-stembrief te pleeg," wat die nodus sal oortuig om dit ook te aanvaar. Laastens is daar 'n uittelmeganisme wat nuwe rondtes van gefedereerde stemming op nuwe stembriewe met hoër tellings genereer as die huidige stembriewe vassteek.
Sodra die nodus 'n stembrief B vind wat dit kan bevestig as voorbereid, saai dit 'n nuwe boodskap uit: "Bewerk stembrief B." Hierdie stemming sê vir eweknieë dat die nodus B nooit sal prysgee nie. Trouens, as B 'n stembrief is , dan “Gee stembrief " beteken die onvoorwaardelike toestemming om te stem vir die gereedheid van elke stembrief vanaf na <∞, s>. Hierdie ekstra waarde help ander eweknieë om die commit-eweknie in te haal as hulle nog in vroeër stadiums van die protokol is.
Op hierdie stadium is dit die moeite werd om weereens te beklemtoon dat dit asinchrone protokolle is. Net omdat een nodus opstemme vir 'n commit stuur, beteken dit nie dat sy eweknieë dit ook doen nie. Sommige van hulle stem dalk nog oor stellings ter voorbereiding van stemming, ander het dalk reeds die betekenis geëksternaliseer. SCP verduidelik hoe 'n nodus elke tipe eweknieboodskap moet verwerk, ongeag die fase daarvan.
As die boodskap "Ek het 'n verbintenis aangekondig » kan nie ontvang of bevestig word nie, dit wil sê die waarskynlikheid dat die boodskap aanvaar of bevestig sal word of - of, in elk geval, enige stembrief met die waarde C, en nie enige ander nie, aangesien die nodus reeds belowe het om nooit te kanselleer nie . Teen die tyd dat 'n nodus stemme vir 'n commit uitsaai, sal dit C of niks wees, afhangend van hoe ver die konsensus gaan. Dit is egter nog nie genoeg vir die nodus om C te eksternaliseer nie. Sommige Bisantynse eweknieë (wat minder as 'n kworum uitmaak, gebaseer op ons sekuriteitsaannames) kan vir die nodus lieg. Om die een of ander stembrief (of reeks stembriewe) te aanvaar en dan te bevestig, is wat die nodus die vertroue gee om C uiteindelik te eksternaliseer.
SCP-stemming deur gefedereerde stemming. Nie gewys nie: Die tydhouer kan enige tyd afgaan, wat die telling op die stembrief verhoog (en moontlik 'n nuwe samestelling van bykomende genomineerde kandidate produseer).
En dit is al! Sodra die netwerk 'n konsensus bereik het, is dit gereed om dit weer en weer te doen. Op die Stellar-betalingsnetwerk gebeur dit ongeveer een keer elke 5 sekondes: 'n prestasie wat beide die sekuriteit en oorlewing vereis wat deur SCP gewaarborg word.
SCP kan dit bereik deur staat te maak op verskeie rondtes van gefedereerde stemming. Gefedereerde stemming word moontlik gemaak deur die konsep van kworumskywe: stelle eweknieë wat elke nodus besluit het om te vertrou as deel van sy (subjektiewe) kworum. Hierdie opset beteken dat konsensus bereik kan word selfs in 'n netwerk met oop lidmaatskap en Bisantynse misleidings.
Verdere leeswerk
- Die oorspronklike SCP-witskrif kan gevind word En konsepspesifikasies vir die implementering daarvan.
- Die oorspronklike skrywer van die SCP-protokol, David Mazier, verduidelik dit op 'n vereenvoudigde (maar steeds tegniese) manier. .
- Jy was dalk verbaas om nie die terme "mynbou" of "bewys van werk" in hierdie artikel te vind nie. SCP gebruik nie hierdie metodes nie, maar sommige ander konsensusalgoritmes wel. Zane Witherspoon het toeganklik geskryf .
- 'n eenvoudige netwerk wat konsensus bereik in een volle rondte van SCP.
- Vir lesers wat belangstel in SCP-implementerings: sien , wat deur die Stellar-betalingsnetwerk gebruik word, of , wat ek geskryf het vir 'n beter begrip van SCP.
Bron: will.com