Stellar-konsensusprotokollen blev først beskrevet i David Mazier i 2015. Dette er et "føderalt byzantinsk aftalesystem", der gør det muligt for decentraliserede, lederløse computernetværk effektivt at opnå konsensus om en beslutning. Stellar betalingsnetværket bruger Stellar Consensus Protocol (SCP) til at opretholde en konsistent transaktionshistorik, der er synlig for alle deltagere.
Konsensusprotokoller anses for svære at forstå. SCP er enklere end de fleste af dem, men deler stadig dette ry - blandt andet på grund af den fejlagtige idé, at "federated voting", som er emnet for første halvdel af den videnskabelige artikel, er SCP. Men det er ikke sandt! Dette er blot en vigtig byggesten, som den anden halvdel af artiklen bruger til at skabe faktiske Stellar konsensus protokol.
I denne artikel vil vi kort forklare, hvad et "system af aftaler" er, hvad der kan gøre det "byzantinsk" og hvorfor gøre det byzantinske system "føderalt". Vi vil derefter forklare den fødererede afstemningsprocedure beskrevet i SCP-artiklen, og til sidst vil vi forklare selve SCP-protokollen.
Aftalesystemer
Et system af aftaler giver en gruppe deltagere mulighed for at nå til enighed om et emne, såsom hvad de skal bestille til frokost.
Hos Interstellar har vi implementeret vores eget spiseaftalesystem: vi bestiller, hvad vores driftschef, John, siger. Dette er et enkelt og effektivt aftalesystem. Vi stoler alle på John og tror på, at han vil finde noget interessant og nærende hver dag.
Men hvad hvis John misbruger vores tillid? Han kan på egen hånd bestemme, at vi alle skal blive veganere. Om en uge eller to vil vi formentlig vælte ham og overdrage magten til Elizabeth. Men pludselig elsker hun avocadoer med ansjos og synes, at alle burde være sådan. Magt korrumperer. Så det er bedre at finde en mere demokratisk metode: en måde at sikre, at der tages hensyn til forskellige præferencer, samtidig med at man sikrer et rettidigt og entydigt resultat, så ingen ender med at bestille frokost, eller fem personer afgiver forskellige ordrer, eller diskussionen trækker ud på aftenen.
Det ser ud til, at løsningen er enkel: hold en afstemning! Men dette er et misvisende indtryk. Hvem skal indsamle stemmesedlerne og rapportere resultaterne? Og hvorfor skulle andre tro på, hvad han siger? Måske kan vi i første omgang stemme på en leder, som vi har tillid til at lede afstemningen – men som skal lede den den første ved at stemme? Hvad hvis vi ikke kan blive enige om en leder? Eller hvad hvis vi når til enighed, men denne leder bliver hængende i et møde eller bliver sygemeldt?
Lignende problemer opstår i distribuerede computernetværk. Alle deltagere eller noder skal være enige om en beslutning, såsom hvis tur det er til at opdatere en delt fil eller fjerne en opgave fra behandlingskøen. I et cryptocurrency-netværk skal noder gentagne gange vælge, hvordan hele historien ser ud fra flere mulige versioner, som nogle gange er i konflikt. Denne netværksaftale sikrer modtageren, at mønten er (a) gyldig (ikke forfalsket) og (b) endnu ikke er brugt andetsteds. Dette sikrer også, at han vil være i stand til at bruge mønterne i fremtiden, fordi den nye modtager vil have de samme garantier af samme årsager.
Ethvert konsensussystem i et distribueret computernetværk skal være fejltolerant: det skal producere konsistente resultater på trods af fejl som langsomme links, ikke-responsive noder og forkert meddelelsesrækkefølge. byzantinsk Aftalesystemet er desuden modstandsdygtigt over for "byzantinske" fejl: knudepunkter, der giver falsk information, uanset om det skyldes en fejl eller i et bevidst forsøg på at underminere systemet eller opnå en fordel. "Byzantinsk" fejltolerance - evnen til at stole på en gruppebeslutning, selv når nogle gruppemedlemmer kan lyve eller på anden måde ikke følger reglerne for beslutningstagning - kaldes som forsøgte at koordinere angrebet. hos Anthony Stevens.
Overvej kryptomønt-ejeren Alice, som skal vælge mellem at købe lækker is fra Bob og betale Carols gæld. Måske vil Alice betale dem begge på én gang ved svigagtigt at bruge den samme mønt. For at gøre dette skal hun overbevise Bobs computer om, at mønten aldrig blev betalt til Carol, og overbevise Carols computer om, at mønten aldrig blev betalt til Bob. Det byzantinske system af aftaler gør dette praktisk talt umuligt, ved at bruge en form for flertalsstyre kaldet kvorum. En node i et sådant netværk nægter at flytte til en bestemt version af historien, indtil den ser, at et tilstrækkeligt antal jævnaldrende - et kvorum - er enige i en sådan overgang. Når dette sker, vil de danne en stemmeblok, der er stor nok til at tvinge de resterende netværksknuder til at acceptere deres beslutning. Alice kan tvinge nogle noder til at lyve på hendes vegne, men hvis netværket er stort nok, vil hendes forsøg blive overvældet af stemmerne fra ærlige noder.
Hvor mange noder er nødvendige for at være kvorum? Som minimum et flertal, eller rettere sagt, et kvalificeret flertal for at bekæmpe fejl og svig. Men for at tælle flertallet skal du kende det samlede antal deltagere. På Interstellar-kontoret eller ved distriktsvalget er disse tal nemme at finde ud af. Men hvis din gruppe er et løst defineret netværk, hvor noder kan komme ind og ud efter ønske uden godkendelse fra centeret, så skal du føderale et byzantinsk aftalesystem, der er i stand til at bestemme kvorummer ikke ud fra en forudbestemt liste af noder, men dynamisk, ud fra et konstant skiftende og uundgåeligt ufuldstændigt øjebliksbillede af noder på et givet tidspunkt.
Det kan virke umuligt at skabe et kvorum fra perspektivet af en enkelt node i et stort netværk, men det er muligt. Et sådant beslutningsdygtighed kan endda garantere resultaterne af decentraliseret afstemning. SCP-hvidbogen viser, hvordan man gør dette ved hjælp af en procedure kaldet ved føderal afstemning.
For den utålmodige
Resten af artiklen beskriver fødereret afstemning og Stellar-konsensusprotokollen mere detaljeret. Hvis du ikke er interesseret i detaljerne, er her en generel oversigt over processen.
- Noderne gennemfører runder af føderal afstemning om "nominerede". En føderal afstemningsrunde betyder:
- Noden stemmer for et udsagn, for eksempel "Jeg foreslår værdien af V";
- Noden lytter til jævnaldrendes stemmer, indtil den finder en, der kan "modtage";
- Noden leder efter et "quorum" for denne påstand. Et beslutningsdygtigt "bekræfter" den nominerede.
- Når en node kan bekræfte en eller flere nominerede, forsøger den at "forberede" "afstemningen" gennem flere runder af fødereret afstemning.
- Når en node er i stand til at bekræfte, at stemmesedlen er klar, forsøger den at begå den gennem endnu flere runder af fødereret afstemning.
- Når først en node kan bekræfte en forpligtelse af en stemmeseddel, kan den "eksternalisere" værdien af den stemmeseddel ved at bruge den som et konsensusresultat.
Disse trin involverer flere runder af fødereret afstemning, som tilsammen udgør én SCP-runde. Lad os se nærmere på, hvad der sker ved hvert trin.
Federated afstemning
Fødereret afstemning er en procedure til at afgøre, om netværket kan blive enige om et forslag. I afstemningsrunden skal hver node vælge en af potentielt mange mulige værdier. Den kan ikke gøre dette, medmindre den er sikker på, at andre noder i netværket ikke vil vælge et andet resultat. For at sikre dette, udveksler noder en byge af beskeder frem og tilbage, så alle bekræftetDet kvorum noder tager samme beslutning. Resten af dette afsnit forklarer vilkårene i denne sætning, og hvordan hele proceduren foregår.
Kvorummer og kvorumsskiver
Lad os starte med at definere et kvorum. Som vi diskuterede ovenfor, er det i et decentralt netværk med dynamisk medlemskab umuligt på forhånd at vide antallet af noder og dermed hvor mange, der skal til for flertallet. Fødereret afstemning løser dette problem ved at introducere en ny idé quorum cut (kvorumsudsnit): Et lille sæt peers, som en node har tillid til at kommunikere oplysninger om stemmestatus til resten af netværket. Hver node definerer sit eget kvorumsudsnit (som det bliver et de facto medlem af).
Kvorumsdannelse begynder med et kvorumssnit. For hver node tilføjes dens afskårne noder. Derefter tilføjes udsnitsvilkårene disse noder og så videre. Efterhånden som du fortsætter, er der flere og flere noder, som du ikke kan tilføje, fordi de allerede er inkluderet i udsnittet. Når der ikke er flere nye noder at tilføje, stopper processen: vi har dannet et kvorum ved "transitiv lukning" af kvorumsdelen af den indledende node.
For at finde et kvorum fra en given node...
... tilføje medlemmer af dens udsnit...
...så tilføjer vi udsnitsmedlemmer af disse noder.
Vi fortsætter, indtil der ikke er nogen noder tilbage at tilføje.
Der er ingen noder tilbage at tilføje. Dette er et kvorum.
Faktisk kan hver node optræde i mere end én skive. For at danne et kvorum skal du kun vælge et af udsnittene og tilføje medlemmer; vælg derefter et vilkårligt udsnit for hvert af medlemmerne, og tilføj medlemmer det klippe og så videre. Det betyder, at hver node er medlem af mange mulige kvorummer.
Vælg kun et kvorumsudsnit ved hvert trin.
Et muligt beslutningsdygtighed. Eller et alternativ...
...vælg andre udsnit...
…(når det er muligt)…
... skaber endnu et kvorum.
Hvordan ved en node, hvilke skiver andre noder er i? På samme måde som anden information om andre knudepunkter: fra de transmissioner, som hver knude udsender til netværket, når dens stemmetilstand ændres. Hver udsendelse indeholder information om afsenderknudepunktets udsnit. SCP-hvidbogen specificerer ikke en kommunikationsmekanisme. Implementeringer bruger typisk for garanteret udsendelse af beskeder i hele netværket.
Husk på, at i det ikke-føderale byzantinske system af aftaler er et beslutningsdygtighed defineret som et flertal af alle noder. Det byzantinske aftalesystem er designet ud fra spørgsmålet: hvor mange uærlige noder kan systemet tolerere? I et system af N noder designet til at overleve f fejl, bør en node være i stand til at gøre fremskridt ved at modtage feedback fra N−f peers, da f af dem kan være nede. Men efter at have modtaget et svar fra N−f peers, kan vi antage, at alle f peers (hvorfra noden ikke modtog et svar) faktisk er ærlige. Således er f ud af N−f jævnaldrende (hvorfra svaret blev modtaget) ondsindede. For at noder kan opnå samme konsensus, skal størstedelen af de resterende noder være ærlige, det vil sige, at vi skal have N−f til at være større end 2f eller N > 3f. Så typisk vil et system designet til at overleve f fejl have i alt N=3f+1 noder og en kvorumstørrelse på 2f+1. Når et forslag passerer quorum-tærsklen, er resten af netværket overbevist om, at eventuelle konkurrerende forslag vil mislykkes. Sådan konvergerer netværket til resultatet.
Men i et føderalt byzantinsk aftalesystem kan der ikke kun være flertal (fordi ingen kender netværkets samlede størrelse), men begrebet flertal er fuldstændig ubrugeligt! Hvis medlemskab af systemet er åbent, så kan nogen få flertal ved blot at udføre et såkaldt Sybil-angreb: gentagne gange tilslutte sig netværket på tværs af flere noder. Så hvorfor kan transitiv skivelukning kaldes kvorum, og hvordan er det i stand til at undertrykke konkurrerende forslag?
Teknisk set, ingen måde! Forestil dig et netværk af seks noder, hvor to trillinger er isoleret i hinandens kvorumssnit. Den første undergruppe kan træffe en beslutning, som den anden aldrig vil høre om, og omvendt. Der er ingen måde for dette netværk at nå konsensus (undtagen ved et tilfælde).
Derfor kræver SCP, at netværket skal have en egenskab kaldet for fødereret afstemning (og for at de vigtige sætninger i papiret skal gælde). skæringspunktet mellem kvorummer. I et netværk med denne egenskab overlapper alle to kvorummer, der kan konstrueres, altid i mindst én node. For at bestemme netværkets fremherskende stemning er dette lige så godt som at have flertal. Intuitivt betyder dette, at hvis et kvorum accepterer udsagn X, kan intet andet kvorum nogensinde gå med til noget andet, fordi det nødvendigvis vil inkludere en node fra det første kvorum, der allerede har stemt for X.
Hvis der er en skæring af kvorummer i netværket...
...så kan du opbygge to quorums...
...vil altid krydse hinanden.
(Selvfølgelig kan overlappende noder vise sig at være byzantinsk liggende eller på anden måde dårlige. I dette tilfælde hjælper quorum-krydset slet ikke netværket med at blive enige. Af denne grund er mange af resultaterne i SCP-hvidbogen baseret på eksplicitte antagelser, såsom hvad der er tilbage i netværkets quorum crossing selv efter at have fjernet dårlige noder. For nemheds skyld, lad os forlade disse antagelser implicit i resten af artiklen).
Det kan virke urimeligt at forvente, at en pålidelig quorum-krydsning er mulig i et netværk af uafhængige knudepunkter. Men der er to grunde til, at det er sådan.
Den første grund er eksistensen af selve internettet. Internettet er et perfekt eksempel på et netværk af uafhængige noder med krydsende kvorummer. De fleste noder på internettet forbinder kun til nogle få andre lokale noder, men disse små sæt overlapper hinanden nok til, at hver node kan nås fra hver anden node ad en eller anden rute.
Den anden grund er specifik for Stellar betalingsnetværk (den mest almindelige brug af SCP). Hvert aktiv på Stellar-netværket har en udsteder, og Stellars retningslinjer kræver, at hver udsteder udpeger en eller flere noder på netværket til at behandle indløsningsanmodninger. Det er i din interesse direkte eller indirekte at inkludere disse noder i kvorumsudsnit for hvert aktiv, du er interesseret i. Kvorum for alle noder, der er interesseret i et givet aktiv, vil så overlappe i det mindste ved disse indløsningsknuder. Noder, der er interesseret i flere aktiver, vil inkludere alle indløsningsknuder fra de respektive udstedere i deres kvorumssnit, og de vil søge at samle alle aktiver. Hertil kommer eventuelle aktiver, der ikke på denne måde er knyttet til andre på netværket, og bør ikke tilsluttes - dette er designet således, at der ikke er quorum overlapning for dette netværk (for eksempel ønsker banker fra dollarzonen nogle gange at handle med banker fra eurozonen og banker fra pesozonen, så de er på samme netværk, men ingen af dem bekymrer sig om det separate netværk af børn, der sælger baseballkort).
Naturligvis ожидание quorum crossing er ikke garanti. Andre byzantinske aftalesystemer skylder meget af deres kompleksitet garantien om kvorum. En vigtig nyskabelse ved SCP er, at den fjerner ansvaret for at skabe kvorummer fra selve konsensusalgoritmen og bringer den til ansøgningsniveauet. Selvom fødereret afstemning er generel nok til at stemme om ethvert spørgsmål, afhænger dens pålidelighed faktisk kritisk af den bredere betydning af disse betydninger. Nogle hypotetiske anvendelser er måske ikke så befordrende for at skabe godt forbundne netværk som andre.
Afstemning, accept og bekræftelse
I en fødereret afstemningsrunde begynder en node eventuelt at stemme for en eller anden værdi V. Det betyder, at man sender en besked til netværket: "Jeg er node N, mine kvorumsudsnit er Q, og jeg stemmer på V." Når en node stemmer på denne måde, lover den, at den aldrig har stemt imod V og aldrig vil.
I peer-to-peer-udsendelser ser hver node, hvordan de andre stemmer. Når en node har samlet nok af disse beskeder, kan den spore kvorumsudsnit og forsøge at finde kvorummer. Hvis han ser et kvorum af jævnaldrende, der også stemmer på V, kan han gå videre til adoption V og udsend denne nye besked til netværket: "Jeg er node N, mine kvorumsudsnit er Q, og jeg accepterer V." Accept giver en stærkere garanti end simpel afstemning. Når en node stemmer på V, kan den aldrig stemme på andre muligheder. Men hvis en node accepterer V, vil ingen node på netværket nogensinde acceptere den anden mulighed (sætning 8 i SCP-hvidbogen beviser dette).
Selvfølgelig er der stor sandsynlighed for, at der ikke umiddelbart vil være et quorum af noder, der stemmer overens med V. Andre noder kan stemme for andre værdier. Men der er en anden måde for en node at gå fra simpel afstemning til accept. N kan acceptere en anden værdi for W, selvom han ikke stemte for det, og selvom han ikke er beslutningsdygtig for det. For at beslutte at ændre din stemme, se bare blokeringssæt noder, der har accepteret W. Et blokeringssæt er én node fra hver af kvorumssnittene N. Som navnet antyder, kan det blok enhver anden betydning. Hvis alle noder i et sådant sæt accepterer W, så vil det (ved sætning 8) aldrig være muligt at danne et kvorum, der tager en anden værdi, og derfor er det også sikkert for N at acceptere W.
Node N med tre quorum skiver.
BDF er et blokeringssæt for N: det inkluderer en node fra hver af skiverne af N.
BE er også et blokeringssæt for N, fordi E optræder i to skiver af N.
Men blokeringssættet er ikke et beslutningsdygtigt. Det ville være for nemt at narre node N til at acceptere den ønskede værdi, hvis det var nok at hacke kun én node i hver af skiverne af N. Derfor er accept af værdien ikke slutningen på afstemningen. I stedet skal N bekræfte værdien, det vil sige se et kvorum af noder, der accepterer den. Hvis det når så langt, så vil, som SCP-hvidbogen beviser (i sætning 11), også resten af netværket til sidst bekræfte den samme værdi, så N vil afslutte den fødererede afstemning med en vis værdi som resultat.
Federated afstemning.
Processen med afstemning, accept og bekræftelse udgør en hel runde af fødereret afstemning. Stellar-konsensusprotokollen kombinerer mange af disse runder for at skabe et komplet konsensussystem.
Stellar Consensus Protocol
De to vigtigste egenskaber ved et konsensussystem er − sikkerhed и overlevelsesevne. En konsensusalgoritme er "sikker", hvis den aldrig kan give forskellige resultater til forskellige deltagere (Bobs kopi af historien vil aldrig modsige Carol). "Livability" betyder, at algoritmen altid vil producere et resultat, det vil sige, at den ikke sætter sig fast.
Beskrevet føderal afstemningsprocedure sikker i den forstand, at hvis en node bekræfter værdien af V, vil ingen anden node bekræfte den anden værdi. Men "vil ikke bekræfte en anden betydning" betyder ikke, at det nødvendigvis vil bekræfte noget. Deltagerne kan stemme på så mange forskellige værdier, at intet når acceptgrænsen. Det betyder, at der ved føderal afstemning er nej overlevelsesevne.
Stellar-konsensusprotokollen bruger fødereret afstemning på en måde, der sikrer både sikkerhed og overlevelse. (SCP's sikkerheds- og overlevelsesgarantier har en teoretisk grænse. Designet vælger en meget stærk sikkerhedsgaranti, der ofrer en lille overlevelsesreduktion, men givet nok tid, er det højst sandsynligt, at der opnås konsensus). I en nøddeskal er ideen at have flere fødererede stemmer på flere værdier, indtil en af dem kommer igennem alle SCP-afstemningsfaserne beskrevet nedenfor.
De værdier, som SCP søger konsensus om, kan være transaktionshistorik eller en frokostordre eller noget andet, men det er vigtigt at bemærke, at det ikke er de værdier, der accepteres eller bekræftes. I stedet sker føderal afstemning iflg udsagn om disse værdier.
De første runder af føderale afstemninger finder sted d nomineringsfasen (nomineringsfase), på et sæt udsagn som "Jeg nominerer V," måske for mange forskellige værdier af V. Formålet med nominering er at finde en eller flere udsagn, der går gennem accept og bekræftelse.
Efter at have fundet verificerbare kandidater, går SCP videre til afstemningsfasen, hvor målet er at finde en bestemt opslag (det vil sige en beholder for den foreslåede værdi) og et beslutningsdygtigt, der kan erklære begå for det (forpligte). Hvis et kvorum forpligter en stemmeseddel, accepteres dens værdi som konsensus. Men før en node kan stemme om en stemmeseddel, skal den først bekræftes aflysning alle stemmesedler med lavere modværdi. Disse trin – annullering af stemmesedler for at finde en, der kan begås – involverer flere runder af fødereret afstemning om flere stemmesedler.
De følgende afsnit beskriver nominering og afstemning mere detaljeret.
Nominering
I begyndelsen af nomineringsfasen kan hver node spontant vælge en værdi for V og stemme på udsagnet "Jeg nominerer V." Målet på dette stadium er at bekræfte nomineringen af en vis værdi gennem en fødereret afstemning.
Måske stemmer nok noder om tilstrækkeligt forskellige forslag til, at ingen nominering kan nå accepttærsklen. Ud over at udsende deres egne nomineringsstemmer "afspejler" noder derfor nomineringerne af deres jævnaldrende. Ekko betyder, at hvis en node stemmer for nominering V, men ser en besked fra en nabo, der stemmer for nominering W, vil den nu stemme for både V og W. (Ikke alle peer-stemmer gentages under nominering, da dette kan føre til en eksplosion på forskellige nominerede. SCP inkluderer en mekanisme til at regulere disse stemmer. Kort sagt er der en formel til at bestemme "prioriteten" af en peer fra en nodes synspunkt, og kun stemmerne fra højprioriterede noder afspejles. Jo længere nomineringen er tager, jo lavere tærskelværdien er, så noden udvider sæt af peers, hvis stemmer den vil afspejle. Prioritetsformlen inkluderer slotnummeret som et af dets input, så en højprioritet peer for en slot kan være en lavprioritet peer for en anden og omvendt).
Konceptuelt er nomineringen parallel, både V og W er separate føderale stemmer, hver individuelt i stand til at opnå accept eller bekræftelse. I praksis pakker SCP-protokolmeddelelser disse individuelle stemmer sammen.
Selvom det at stemme for V's nominering er et løfte om aldrig at stemme imod V's nominering, er det på ansøgningsniveau - i dette tilfælde SCP - at det afgøres, hvad "imod" betyder. SCP ser ikke et udsagn, der modsiger "Jeg nominerer X"-stemmen, det vil sige, at der ikke er nogen "Jeg er imod at nominere X"-besked, så noden kan stemme for at nominere alle værdier. Mange af disse nomineringer vil gå ingen vegne, men i sidste ende vil noden være i stand til at acceptere eller bekræfte en eller flere værdier. Når en nomineret er bekræftet, bliver han det kandidat.
SCP nominering ved hjælp af fødereret afstemning. Der kan være mange "B"-værdier fremsat af peers og "reflekteret" af noden.
Nomineringer kan resultere i flere bekræftede kandidater. Derfor kræver SCP, at applikationslaget giver en eller anden metode til at kombinere kandidaterne til én sammensatte (sammensatte). Sammenføjningsmetoden kan være hvad som helst. Det vigtigste er, at hvis denne metode er deterministisk, vil hver node kombinere de samme kandidater. I et frokostafstemningssystem kan "forening" blot betyde, at man opgiver en af to kandidater. (Men på en deterministisk måde: hver node skal vælge den samme værdi for at nulstille. For eksempel det tidligere valg i alfabetisk rækkefølge). I Stellar-betalingsnetværket, hvor der stemmes om transaktionshistorik, involverer sammenlægning af to foreslåede nominerede en sammenlægning af de transaktioner, de indeholder, og det seneste af deres to tidsstempler.
SCP-hvidbogen beviser (sætning 12), at ved slutningen af udvidelsesfasen konvergerer netværket til sidst til en enkelt sammensætning. Men der er et problem: fødereret afstemning er en asynkron protokol (som SCP). Med andre ord er noder ikke koordineret efter tid, men kun af de beskeder, de sender. Fra nodens synspunkt er det uklart hvornår sluttede forlængelsesfasen. Og selvom alle noder i sidste ende vil ankomme til den samme sammensætning, kan de tage forskellige ruter undervejs og skabe forskellige sammensatte kandidater undervejs, og kan aldrig sige, hvilken der er den endelige.
Men det er normalt. Nominering er blot forberedelse. Det vigtigste er at begrænse antallet af kandidater for at opnå konsensus, hvilket sker i processen stille op til embedet (afstemning).
Løb
Bulletin er et par , hvor tæller er et heltal, der starter ved 1, og værdi er en kandidat fra nomineringsstadiet. Dette kan være en nodes egen kandidat eller en tilstødende nodes kandidat accepteret af den node. Groft sagt involverer en afstemning gentagne forsøg på at tvinge netværket til at nå til enighed om en kandidat på en eller anden afstemning ved at afholde potentielt mange forbundsstemmer på stemmesedler. Tællere på stemmesedlerne holder styr på de forsøg, der er gjort, og stemmesedler med højere antal har forrang frem for stemmesedler med lavere tal. Hvis nyhedsbrevet bliver hængende, begynder en ny afstemning, nu på stemmesedlen .
Det er vigtigt at skelne betydning (f.eks. hvad skal frokostbestillingen være: pizza eller salater), nyhedsbreve (modværdipar) og erklæring om stemmesedler. SCP-runden inkluderer flere føderale afstemningsrunder, især om følgende udtalelser:
- "Jeg er klar til at begå afstemning B" og
- "Jeg annoncerer forpligtelsen af stemmeseddel B"
Fra en given nodes perspektiv opnås konsensus, når den finder en stemmeseddel B, som den kan bekræfte (det vil sige finde et quorum, der accepterer) udsagnet "Jeg forpligter stemmeseddel B." Fra dette tidspunkt er det sikkert at handle på den værdi, der er angivet i B - for eksempel at afgive denne ordre til frokost. Det kaldes eksternalisering betydninger. Når accept af stemmesedlen er bekræftet, kan en node være sikker på, at enhver anden node har eksternaliseret den samme værdi eller vil gøre det i fremtiden.
Selvom mange fødererede afstemninger konceptuelt udføres på krav for mange forskellige stemmesedler, udveksler de ikke så mange meddelelser, fordi hver meddelelse indkapsler et antal stemmesedler. Et budskab fremmer således staten af mange fødererede stemmer på én gang, for eksempel: "Jeg accepterer stemmesedler fra Før "
Hvad betyder udtrykkene "forberedt" og "forpligte"?
En node stemmer for at foretage en stemmeseddel, når den er sikker på, at andre noder ikke vil begå stemmesedler med andre værdier. Overbevisende dette er formålet med at udarbejde ansøgningen. En stemme, der siger "Jeg er klar til at begå stemmeseddel B" er et løfte om aldrig at begå en stemmeseddel, der er mindre end B, dvs. med et mindre antal (SCP kræver, at værdierne i stemmesedlerne er i en bestemt rækkefølge. Således nyhedsbrev mindre hvis N1
Hvorfor betyder "Jeg er klar til at begå stemmeseddel B" "Jeg lover aldrig at begå stemmesedler, der er mindre end B"? Fordi SCP definerer abort som det modsatte af commit. En afstemning om at forberede en stemmeseddel indebærer også en afstemning om at diskvalificere nogle andre stemmesedler, og som vi diskuterede tidligere, er det at stemme for én ting et løfte om aldrig at stemme imod det.
Før en commit udsendes, skal en node først finde en bulletin, som den kan bekræfte som forberedt. Med andre ord udfører den en fødereret afstemning om emnet "Jeg er klar til at begå afstemning B," muligvis på mange forskellige stemmesedler, indtil den finder en, der accepterer et beslutningsdygtigt.
Hvor kommer stemmesedlerne fra for at forberede afstemningen? Først udsender noden forberedelser til at stemme på <1,C>, hvor C er den sammensatte kandidat, der er produceret på nomineringsstadiet. Men selv efter at forberedelserne til afstemningen er begyndt, kan nomineringer resultere i, at yderligere kandidater ser ud til at blive nye stemmesedler. I mellemtiden kan peers have forskellige kandidater, og de kan danne et blokeringssæt, der accepterer "Jeg er klar til at begå B2-afstemningen", hvilket vil overbevise noden om også at acceptere den. Endelig er der en timeout-mekanisme, der genererer nye runder af forbundsafstemning om nye stemmesedler med højere antal, hvis de nuværende stemmesedler sidder fast.
Så snart noden finder en stemmeseddel B, som den kan bekræfte som forberedt, udsender den en ny besked "Bekræft stemmeseddel B." Denne afstemning fortæller jævnaldrende, at noden aldrig vil opgive B. Faktisk, hvis B er en stemmeseddel , derefter "Begiv stemmeseddel " betyder det ubetingede samtykke til at stemme for klarheden af hver stemmeseddel fra til <∞, s>. Denne ekstra værdi hjælper andre peers med at indhente den forpligtende peer, hvis de stadig er i tidligere stadier af protokollen.
På dette stadium er det værd at understrege endnu en gang, at der er tale om asynkrone protokoller. Bare fordi en node sender upvotes for en commit, betyder det ikke, at dens jævnaldrende også gør det. Nogle af dem stemmer muligvis stadig om udtalelser som forberedelse til afstemning, andre kan allerede have eksternaliseret betydningen. SCP forklarer, hvordan en node skal behandle hver type peer-meddelelse uanset dens fase.
Hvis beskeden "Jeg har annonceret en forpligtelse » kan ikke modtages eller bekræftes, dvs. sandsynligheden for, at meddelelsen bliver accepteret eller bekræftet eller - eller under alle omstændigheder enhver stemmeseddel med værdien C, og ikke nogen anden, da noden allerede har lovet aldrig at annullere . På det tidspunkt, hvor en node udsender stemmer for en commit, vil den være C eller ingenting, afhængigt af hvor langt konsensus går. Dette er dog endnu ikke nok til, at noden eksternaliserer C. Nogle byzantinske peers (som udgør mindre end et kvorum, baseret på vores sikkerhedsantagelser) kan lyve til noden. At acceptere og derefter bekræfte en stemmeseddel (eller række af stemmesedler) er det, der giver noden tillid til endelig at eksternalisere C.
SCP-afstemning gennem fødereret afstemning. Ikke vist: Timeren kan gå i gang når som helst, hvilket øger antallet af stemmesedler (og producerer muligvis en ny sammensætning af yderligere nominerede kandidater).
Og det er det hele! Når netværket er nået til konsensus, er det klar til at gøre det igen og igen. På Stellars betalingsnetværk sker dette cirka en gang hvert 5. sekund: en bedrift, der kræver både sikkerheden og overlevelsesevnen garanteret af SCP.
SCP kan opnå dette ved at stole på flere runder af fødereret afstemning. Fødereret afstemning er muliggjort af konceptet med kvorumssnit: sæt af peers, som hver node har besluttet at stole på som en del af sit (subjektive) kvorum. Denne konfiguration betyder, at konsensus kan nås selv i et netværk med åbent medlemskab og byzantinske bedrag.
Yderligere læsning
- Den originale SCP hvidbog kan findes Og udkast til specifikationer for dens gennemførelse.
- Den oprindelige forfatter til SCP-protokollen, David Mazier, forklarer det på en forenklet (men stadig teknisk) måde. .
- Du er måske blevet overrasket over ikke at finde udtrykkene "minedrift" eller "bevis på arbejde" i denne artikel. SCP bruger ikke disse metoder, men nogle andre konsensusalgoritmer gør det. Zane Witherspoon skrev tilgængeligt .
- et simpelt netværk, der når konsensus i en hel runde af SCP.
- For læsere, der er interesseret i SCP-implementeringer: se , brugt af Stellar betalingsnetværk, eller , som jeg skrev for en bedre forståelse af SCP.
Kilde: www.habr.com