Stellar konsensusprotokol blev først beskrevet i David Mazières i 2015. Det er et „federeret system for byzantinsk enighed“, som gør det muligt for decentraliserede beregningsnetværk uden ledere effektivt at nå enighed om en beslutning. Stellar betalingsnetværk bruger Stellar Consensus Protocol (SCP) til at opretholde en konsistent historie af transaktioner, som alle deltagere kan se.
Det anses for, at konsensusprotokoller er svære at forstå. SCP er lettere end de fleste af dem, men deler stadig dette ry - delvist på grund af den fejlagtige idé om, at „federeret stemmeafgivning“, som den første halvdel af den videnskabelige artikel er dedikeret til, er SCP. Men det er ikke tilfældet! Det er blot en vigtig byggesten, der i den anden halvdel af artiklen bruges til at konstruere den faktiske Stellar konsensusprotokol.
I denne artikel vil vi kort fortælle, hvad en „aftalesystem“ er, hvad der kan gøre det „byzantinsk“ og hvorfor man bør gøre et byzantinsk system „federeret“. Derefter vil vi forklare den federerede stemmeafgivningsprocedure, som beskrives i artiklen om SCP, og til sidst vil vi forklare selve SCP-protokollen.
Aftalesystemer
Aftalesystemet gør det muligt for en gruppe deltagere at nå til enighed om et emne, for eksempel hvad de skal bestille til frokost.
Vi hos Interstellar har implementeret vores eget frokostaftalesystem: vi bestiller det, vores operationschef John siger. Det er et simpelt og effektivt aftalesystem. Vi stoler alle på John og tror, at han hver dag vil finde noget interessant og nærende.
Men hvad nu hvis John misbruger vores tillid? Han kan ensidigt beslutte, at vi alle skal være veganere. Om en uges tid vil vi sandsynligvis vælte ham og give magten videre til Elizabeth. Men hvad nu hvis hun elsker avocado med ansjoser og tænker, at alle skal være sådan? Magt korrumperer. Derfor er det bedre at finde en mere demokratisk metode: en måde at sikre, at forskellige præferencer tages i betragtning, samtidig med at der opnås et rettidigt og entydigt resultat, så det ikke ender med, at ingen bestiller frokost, eller fem personer afgiver forskellige bestillinger, eller diskussionen strækker sig til aftenen.
Det kan tilsyneladende synes simpelt: at afholde en afstemning! Men det er en vildledende opfattelse. Hvem skal indsamle stemmesedlerne og rapportere resultaterne? Og hvorfor skulle de andre tro på, hvad vedkommende siger? Måske kan vi først stemme på en leder, som vi stoler på til at lede afstemningen — men hvem skal lede denne anges først afstemning? Hvad hvis vi ikke kan blive enige om en leder? Eller hvis vi bliver enige, og denne leder sidder fast i et møde eller bliver syg?
Lignende problemer opstår i distribuerede computersystemer. Alle deltagere eller noder skal blive enige om en løsning, for eksempel hvis det er ens tur til at opdatere en fælles fil eller tage en opgave fra en behandlingskø. I et kryptovaluta-netværk må noderne gentagne gange vælge, hvordan den fulde historie ser ud, fra flere mulige versioner, der nogle gange er i konflikt. Denne netværksaftale garanterer modtageren, at mønten er (a) gyldig (ikke falsk) og (b) endnu ikke er brugt et andet sted. Det garanterer også, at han vil kunne bruge mønterne i fremtiden, fordi den nye modtager vil have de samme garantier af de samme grunde.
Enhver konsensusmekanisme i et distribueret computersystem skal være fejltolerant: den skal give konsekvente resultater trods fejl som langsomme forbindelser, ikke-responderende noder og forkert rækkefølge af beskeder. Den byzantinske konsensusmekanisme er yderligere modstandsdygtig over for 'byzantinske' fejl: noder, der giver falske oplysninger, enten på grund af fejl eller i et bevidst forsøg på at underminere systemet eller opnå en fordel. 'Byzantinsk' fejltolerance — evnen til at stole på en gruppes beslutning, selv når nogle medlemmer af gruppen kan lyve eller på anden måde ikke følge beslutningsreglerne — har fået sit navn fra , som forsøgte at koordinere et angreb. finder man hos Anthony Stevens.
Lad os overveje kryptovaluta-ejeren Alice, som skal vælge mellem at købe lækker is fra Bob eller betale sin gæld til Carol. Måske vil Alice gerne betale begge med det samme og snyde ved at bruge den samme mønt. For at gøre dette skal hun overbevise Bobs computer om, at mønten aldrig er blevet betalt til Carol, og overbevise Carols computer om, at mønten aldrig er blevet betalt til Bob. Et byzantinsk konsensusystem gør dette praktisk umuligt ved hjælp af en form for flertalsregel, som kaldes kvorum. En node i et sådant netværk nægter at gå videre til en bestemt version af historien, indtil den ser, at tilstrækkeligt mange ligeværdige noder - kvorum - er enige om at skifte. Når det sker, danner de en tilstrækkeligt stor valgblok til at tvinge de resterende noder i netværket til at acceptere deres beslutning. Alice kan få nogle noder til at lyve på hendes vegne, men hvis netværket er stort nok, vil hendes forsøg blive nedslidt af stemmerne fra ærlige noder.
Hvor mange noder kræves der for at danne et kvorum? Som minimum et flertal, nærmere bestemt et kvalificeret flertal, for at bekæmpe fejl og svindel. Men for at tælle flertallet er det nødvendigt at kende det samlede antal deltagere. I Interstellar-kontoret eller ved lokale valg er disse tal let tilgængelige. Men hvis din gruppe er et svagt defineret netværk, hvor noder kan komme og gå efter eget valg uden godkendelse fra en central instans, er der behov for en federativ byzantinsk konsensusordning, der kan bestemme kvora ikke fra en forudbestemt liste over noder, men dynamisk fra et konstant skiftende og uundgåeligt ufuldstændigt snapshot af noder på et givet tidspunkt.
Det kan synes umuligt at skabe et kvorum fra synspunktet af en enkelt node i et stort netværk, men det er muligt. Et sådant kvorum kan endda garantere resultaterne af decentraliseret afstemning. Det tekniske dokument SCP viser, hvordan dette kan gøres ved hjælp af en procedure kaldet federativ afstemning.
For de utålmodige
Den resterende del af artiklen beskriver mere detaljeret den federative afstemning og Stellar-konsensusprotokollen. Hvis du ikke er interesseret i detaljerne, er her et overblik over processen.
- Noderne gennemfører runder af den føderale afstemning om "nominatioerne". En runde af den føderale afstemning indebærer:
- Noden stemmer for en påstand, for eksempel "Jeg foreslår værdien V";
- Noden lytter til stemmerne fra peerne, indtil den finder en, som kan "acceptere";
- Noden leder efter et "kvorum" for denne påstand. Kvoret "bekræfter" nomineringen.
- Når noden kan bekræfte en eller flere nomineringer, forsøger den at "forberede" "stemmesedlen" gennem flere runder af den føderale afstemning.
- Når noden er i stand til at kontrollere beredskaben af stemmesedlen, forsøger den at forpligte den med hjælp af endnu flere runder af den føderale afstemning.
- Når noden kan bekræfte forpligtelsen af stemmesedlen, kan den "eksternalisere" værdien af denne stemmeseddel ved at bruge den som resultat af konsensus.
Disse trin omfatter flere runder af den føderale afstemning, som samlet set udgør én runde SCP. Lad os se nærmere på, hvad der sker i hvert trin.
Føderal afstemning
Føderal afstemning er en procedure, hvormed det bestemmes, om netværket kan enes om et forslag. I afstemningsrunden skal hver node vælge et af mange potentielt mulige værdier. Den kan ikke gøre dette, før den er sikker på, at andre noder i netværket ikke vil vælge et andet resultat. For at være sikre på dette, udveksler noderne en væld af beskeder frem og tilbage, så hver har bekræftet, at kvorum node modtager den samme løsning. Resten af denne sektion forklarer de termer, som er nævnt i denne påstand, og hvordan hele proceduren finder sted.
Kvourummer og kvourskiver
Lad os begynde med at definere et kvorum. Som nævnt tidligere, i et decentralt netværk med dynamisk medlemskab er det umuligt at vide på forhånd, hvor mange noder der er, og derfor hvor mange der kræves for et flertal. Føderal afstemning løser dette problem ved at introducere en ny idé kvourskiver (quorum slice): et lille sæt af ligestillede noder, som noden har tillid til at videregive information om afstemningsstatus til resten af netværket. Hver node definerer sin egen kvourskive (som den bliver medlem af i praksis).
Dannelsen af kvorum begynder med kvourskiver. For hver node tilføjes noderne fra dens kvourskive. Derefter tilføjes medlemmer fra kvourskiverne disse noder og så videre. Efterhånden som processen fortsætter, finder man flere og flere noder, som man ikke kan tilføje, fordi de allerede er inkluderet i quorumskiverne. Når der ikke er flere nye noder at tilføje, stopper processen: vi har dannet et quorum gennem "transitiv lukning" (transitive closure) af quorumskiven fra den oprindelige node.
For at finde et quorum fra en given node…
… tilføjer vi medlemmer af dens skive…
… derefter tilføjer vi medlemmer af skiverne fra disse noder.
Vi fortsætter, indtil der ikke er flere noder at tilføje.
Der er ikke flere noder at tilføje. Dette er et quorum.
Faktisk kan hver node være en del af mere end én skive. For at danne et quorum, vælg kun én af skiverne og tilføj medlemmer; vælg derefter en hvilken som helst skive for hvert af medlemmerne og tilføj medlemmerne. denne skiven og så videre. Det betyder, at hver node er medlem af mange mulige quorum.
Vælg kun én quorumskive ad gangen.
Én mulig quorum. Eller et alternativt valg…
… vælger andre skiver…
…(når det er muligt)…
… skaber et andet quorum.
Hvordan finder en node ud af, hvilke skiver de andre noder tilhører? På samme måde som anden information om andre noder: fra de meddelelser, som hver node transmitterer i netværket, når dens stemmestatus ændres. Hver meddelelse indeholder oplysninger om skiverne fra den afsendende node. I den tekniske dokumentation SCP er der ikke angivet en kommunikationsmekanisme. Implementeringerne bruger typisk til garanteret transmission af beskeder over hele netværket.
Lad os minde om, at i det ikke-føderale byzantinske aftalesystem defineres et quorum som flertallet af alle noder. Det byzantinske aftalesystem er udviklet med hensyn til spørgsmålet: hvor mange uærlige noder kan systemet tåle? I et system med N noder, designet til at overleve ved f fejl (bedragerier), skal en node være i stand til at opnå fremskridt ved at modtage svar fra N−f peer, da f af dem muligvis ikke fungerer. Men når der modtages svar fra N−f peer, kan man antage, at alle f peer (som noden ikke har modtaget svar fra) faktisk er ærlige. Dermed er de skadelige f af N−f peer (som noden har modtaget svar fra). For at noderne skal nå til enighed, skal flertallet af de resterende noder være ærlige, hvilket betyder, at vi har brug for, at N−f er større end 2f eller N > 3f. Så typisk vil et system designet til at overleve ved f fejl have i alt N=3f+1 noder og størrelse quorum 2f+1. Så snart forslaget passerer quorum-grænsen, er resten af netværket overbevist om, at enhver konkurrenceforslag vil mislykkes. Så netværket konvergerer mod et resultat.
Men i det føderale byzantinske aftalesystem kan der ikke kun være flertal (fordi ingen kender det samlede netværks størrelse), men konceptet med flertal er helt meningsløst! Hvis medlemskabet i systemet er åbent, kan nogen få flertal ved simpelthen at udføre et såkaldt Sybil-angreb: ved gentagne gange at tilslutte sig netværket gennem flere noder. Så hvorfor kan det transitive lukning af skæringen kaldes kvorum, og hvordan kan det undertrykke konkurrenceforslag?
Teknisk set, ikke på nogen måde! Forestil dig et netværk af seks noder, hvor to grupper er isoleret i hinandens quorum-skæringer. Den første undergruppe kan træffe en beslutning, som den anden aldrig vil høre, og omvendt. For dette netværk er der ingen måde at opnå enighed på (andet end ved tilfældigheder).
Derfor kræver SCP, at for føderal afstemning (og for anvendelse af vigtige teoremer i artiklen) skal netværket have en egenskab, der kaldes skæringskvora. I netværk med denne egenskab vil enhver to quorum, der kan opbygges, altid overlappe hinanden i mindst ét knudepunkt. For at bestemme de dominerende holdninger i netværket er det lige så godt som at have flertallet. Intuitivt betyder det, at hvis et hvilket som helst quorum er enig i udsagnet X, kan intet andet quorum nogensinde være enig i noget andet, fordi det nødvendigvis vil inkludere et knudepunkt fra det første quorum, som allerede har stemt for X.
Hvis der er overlap mellem quorum i netværket...
… så vil enhver to quorum, du kan opbygge...
… altid krydse hinanden.
(Selvfølgelig kan de overlappende knudepunkter vise sig at være byzantinsk bedrageriske eller dårlige på andre måder. I så fald hjælper overlapningen af quorum ikke netværket med at opnå enighed overhovedet. Af denne grund bygger mange resultater i det tekniske dokument SCP på åbenlyse antagelser, såsom at der i netværket stadig er overlap mellem quorum, selv efter fjernelse af dårlige knudepunkter.. For enkelhedens skyld lader vi disse antagelser være underforståede i resten af artiklen).
Det kan synes urimeligt at forvente, at det er muligt med pålideligt overlap mellem quorum i et netværk af uafhængige knudepunkter. Men der er to grunde til, at dette er tilfældet.
Den første grund er tilstedeværelsen af selve internettet. Internettet er et ideelt eksempel på et netværk af uafhængige knudepunkter med overlap mellem quorum. De fleste knudepunkter i internettet forbinder kun med nogle få andre lokale knudepunkter, men disse små sæt overlapper tilstrækkeligt, så hvert knudepunkt er tilgængeligt fra hvert andet knudepunkt via en eller anden rute.
Den anden årsag er specifik for betalingsnetværket Stellar (den mest almindelige anvendelse af SCP). Hver aktiv i Stellar-netværket har en udsteder, og Stellar-anbefalingerne kræver, at hver udsteder tildeler en eller flere noder i netværket til at håndtere indløsningsanmodninger. Det er i din interesse hurtigt eller indirekte at inkludere disse noder i quorum-slices for hvert aktiv, du er interesseret i. Derefter vil quorum for alle de noder, der er interesseret i det pågældende aktiv, overlappe sig i det mindste i disse indløsningsnoder. Noder, der er interesseret i flere aktiver, vil inkludere alle indløsningsnoderne fra de relevante udstedere i deres quorum-slices, og de vil stræbe efter at kombinere alle aktiverne. Desuden vil aktiver, der ikke er forbundet på denne måde med andre i netværket, ikke være forbundet — dette er tilsigtet, så der ikke er nogen overlapning af quorum i dette netværk (for eksempel ønsker banker i dollarzonen nogle gange at handle med banker i eurozonen og banker i peso, så de er i samme netværk, men ingen af dem er interesserede i et separat netværk af børn, der handler med baseballkort).
Selvfølgelig, forventning til overlapning af quorum er ikke en garanti. Andre byzantinske konsensusystemer er i høj grad præget af garantien for quorum. En vigtig innovation ved SCP er, at det frigør skabelsen af quorum fra selve konsensusalgoritmen og flytter det til applikationsniveau. Derfor, selvom føderal stemmeafgivning er relativt almindelig for stemmeafgivning om enhver sag, afhænger dens pålidelighed kritisk af den bredere betydning af disse værdier. Nogle hypotetiske anvendelser kan vise sig at være mindre hensigtsmæssige til at skabe godt forbundne netværk end andre.
Stemmesystem, godkendelse og bekræftelse
I runden om føderal stemmeafgivning begynder noden valgfrit at stemme for en bestemt værdi V. Dette betyder, at der sendes en meddelelse til netværket: "Jeg er node N, mine quorum-slices Q, og jeg stemmer for V". Når noden stemmer på denne måde, lover den, at den aldrig har stemt imod V og aldrig vil.
I peer-to-peer-transmission ser, ser hver node, hvordan andre stemmer. Når en node har samlet tilstrækkeligt med sådanne meddelelser, kan den spore de quorum-skiv, der er blevet dannet, og forsøge at finde quorum. Hvis den ser et quorum af peers, der også stemmer for V, kan den gå videre til acceptance af V og sende den nye meddelelse til netværket: „Jeg er node N, mine quorum-skiver Q, og jeg accepterer V.” Accept giver en stærkere garanti end simpel stemmeafgivning. Når en node stemmer for V, kan den aldrig stemme for andre muligheder. Men hvis en node accepterer V, vil ingen node i netværket nogensinde acceptere en anden mulighed (teorem 8 i SCP-teknisk dokumentation beviser dette).
Selvfølgelig er der en høj sandsynlighed for, at der ikke straks vil blive fundet et quorum af noder, der er enige om V. Andre noder kan stemme for andre værdier. Men for noden er der en anden måde at gå fra simpel stemmeafgivning til acceptance. N kan acceptere en anden værdi W, selvom den ikke har stemt for den, og selvom den ikke ser et quorum for denne. blokerende mængde noder, der har accepteret W. Den blokerende mængde er én node fra hver af quorum-skiverne N. Som navnet antyder, er den i stand til at blokere en hvilken som helst anden værdi. Hvis alle noder i en sådan mængde accepterer W, så (ifølge teorem 8) vil det aldrig være muligt at danne et quorum, der accepterer en anden værdi, og derfor er det også sikkert for N at acceptere W.
Node N med tre quorum-skiver.
B-D-F er den blokerende mængde for N: den inkluderer én node fra hver af skiverne N.
B-E er også en blokerende mængde for N, fordi E vises i to af skiverne N.
Men den blokerende mængde er ikke et quorum. Det ville være for nemt at narre node N til at acceptere den ønskede værdi, hvis det var tilstrækkeligt at hacke én node i hver af skiverne N. Derfor er accept af en værdi ikke slutningen på stemmeafgivningen. I stedet skal N bekræfte værdien, hvilket betyder, at den skal se et quorum af noder, der accepterer det. Hvis den kommer så langt, som det bevises af SCP-teknisk dokumentation (i teorem 11), vil resten af netværket også til sidst bekræfte den samme værdi, så N afslutter det føderative stemme med en bestemt værdi som resultat.
Føderativ stemmeafgivning.
Stemmesystemet til vedtagelse og bekræftelse udgør en fuld runde af føderal stemmeafgivning. Stellar konsensusprotokol samler mange sådanne runder for at skabe et komplet konsensus-system.
Stellar konsensusprotokol
De to mest vigtige egenskaber ved et konsensus-system er sikkerhed og modstandsdygtighed. Konsensusalgoritmen er "sikker", hvis den aldrig kan give forskellige resultater til forskellige deltagere (Bob's historie vil aldrig modsige Carol's). "Modstandsdygtighed" betyder, at algoritmen altid vil producere et resultat, dvs. den vil ikke sidde fast.
Den beskrevne procedure for føderal stemmeafgivning er sikker i den forstand, at hvis en node bekræfter værdien V, så vil ingen anden node bekræfte en anden værdi. Men "ikke bekræfte en anden værdi" betyder ikke, at den nødvendigvis vil bekræfte noget. Deltagere kan stemme for så mange forskellige værdier, at ingen når tærsklen for vedtagelse. Dette betyder, at der i føderal stemmeafgivning ikke findes modstandsdygtighed.
Stellar konsensusprotokol bruger føderal stemmeafgivning på en måde, der garanterer både sikkerhed og modstandsdygtighed. (Sikkerheds- og modstandsdygtighedsgarantierne for SCP har en teoretisk grænse. Konstruktet vælger en meget stærk sikkerhedsgaranti, hvilket ofrer en lille smule af modstandsdygtighed, men under hensyntagen til tilstrækkelig tid vil konsensus med høj sandsynlighed blive nået). Kort sagt går idéen ud på at afholde flere føderale stemmeafgivelser for flere værdier, indtil en af dem fuldt ud går igennem alle faserne af SCP-stemmesystemet, som beskrevet nedenfor.
De værdier, som SCP stræber efter at opnå konsensus om, kan være historien om transaktioner eller en bestilling på frokost, eller noget andet, men det er vigtigt at bemærke, at det ikke er disse værdier, der vedtages eller bekræftes. I stedet finder føderal stemmeafgivning sted for udsagn om disse værdier.
De første runder af føderal stemmeafgivning finder sted i nomineringens fase (nomination phase), i et sæt udsagn som "Jeg nominerer V", muligvis for mange forskellige værdier V. Målet med nomineringen er at finde et eller flere udsagn, der kan nå vedtagelse og bekræftelse.
Efter at have fundet bekræftede kandidater går SCP videre til afstemningsfasen, hvor målet er at finde en eller anden stemme (det vil sige en beholder for den foreslåede værdi) og et quorum, der kan erklære commit for det (commit). Hvis quorummet foretager en commit af stemmen, accepteres dens værdi som konsensus. Men før en node kan stemme for commit af stemmen, skal den først bekræfte annulleringen af alle stemmer med en lavere tælleværdi. Disse trin — annullering af stemmer for at finde den, som commit kan bekræftes for — involverer flere runder af føderativ afstemning over flere erklæringer om stemmer.
I de følgende afsnit beskrives nominering og afstemning mere detaljeret.
Nominering
I begyndelsen af nomineringstrinnet kan hver node spontant vælge værdien V og stemme for at bekræfte "Jeg nominerer V". Målet på dette trin er at bekræfte nomineringen af en given værdi gennem føderativ afstemning.
Det er muligt, at et tilstrækkeligt antal noder stemmer for tilstrækkeligt forskellige erklæringer, og ingen nominering kan nå tærsklen for godkendelse. Derfor, ud over at overføre deres egne nominative stemmer, "reflekterer" noder nomineringer fra deres naboer. Refleksion betyder, at hvis en node stemmer for nomineringen V, men ser en besked fra en nabo, der stemmer for nomineringen W, så vil den nu stemme for både nomineringen V og W. (Ikke alle stemmer fra naboer reflekteres under nomineringen, da dette kan føre til en eksplosion af forskellige kandidater. SCP inkluderer en mekanisme til at regulere disse stemmer. Kort sagt, der findes en formel til at bestemme "prioriteten" af en peer set fra noden, og kun stemmer fra højprioriterede noder reflekteres. Jo længere nomineringen varer, jo lavere er tærsklen, så noden udvider sættet af naboer, hvis stemmer den vil reflektere. Prioritetsformlen inkluderer slotnumret som en af inputene, så en højprioriteret peer-node for én slot kan være lavprioriteret for en anden, og omvendt).
Konceptuelt er fremsættelsen af både V og W separate føderative stemmer, hver især i stand til at opnå vedtagelse eller bekræftelse. I praksis pakker SCP-protokolens meddelelser disse separate stemmer sammen.
Selvom stemmeafgivningen for fremsættelse af V er et løfte om aldrig at stemme imod fremsættelse af V, defineres der på anvendelsesniveauet - i dette tilfælde SCP - hvad 'imod' betyder. SCP ser ikke en erklæring, der strider imod stemmeafgivningen 'Jeg fremsætter X', dvs. der er ikke en meddelelse 'Jeg stemmer imod fremsættelse af X', så noden kan stemme for fremsættelse af enhver værdi. Mange af disse nomineringer vil ikke føre til noget, men i sidste ende kan noden godkende eller bekræfte en eller flere værdier. Når en nominant er bekræftet, bliver han nominert.
Fremsættelse af SCP ved hjælp af føderativ stemmeafgivning. Der kan være mange værdier “B”, der fremsættes af ligestillede noder og 'reflekteret' af en node.
Fremsættelse af kandidater kan føre til, at der opstår flere bekræftede kandidater. Derfor kræver SCP, at applikationsniveauet giver en metode til at sammenlægge kandidaterne til én komposit (komposit). Sammenlægningsmetoden kan være en hvilken som helst. Det vigtigste er, at hvis denne metode er deterministisk, så vil hver node sammenlægge de samme kandidater. I et måltid stemmesystem kan 'sammenlægningen' blot betyde at forkaste en af de to kandidater. (Men på en deterministisk måde: hver node skal vælge den samme værdi til nulstilling. For eksempel tidligere valg i alfabetisk rækkefølge). I Stellar betalingsnetværket, hvor stemmeafgivning om transaktionshistorik finder sted, indebærer sammenlægningen af to foreslåede kandidater en sammenlægning af de transaktioner, de indeholder, og de seneste af deres to tidsstempler.
Den tekniske beskrivelse af SCP beviser (teorem 12), at netværket i sidste ende konvergerer til en enkelt komposit ved afslutningen af fremsætningsfasen. Men der er et problem: føderativ stemmeafgivning er en asynkron protokol (ligesom SCP). Med andre ord er noderne ikke koordineret tidsmæssigt, men kun via de meddelelser, de sender. Set fra en nodes synspunkt er det uklart, hvornår afsluttet udriftsfase. Selvom alle noder til sidst vil komme til den samme sammensætning, kan de vælge forskellige ruter undervejs, hvilket skaber forskellige kandidater undervejs, og de kan aldrig vide, hvilken der er den endelige.
Men det er i orden. Udrift er blot en forberedelse. Det vigtigste er at begrænse antallet af kandidater for at opnå konsensus, hvilket sker i processen. afstemning (afstemning).
Afstemning
En stemmeseddel er et par , hvor counter er et helt tal, der starter fra 1, og value er kandidaten fra udriftsfasen. Dette kan være nodens egen kandidat eller en kandidat fra en nabo-node, som denne node har accepteret. Groft sagt gør afstemningen gentagne forsøg på at få netværket til at nå konsensus om en kandidat i en given stemmeseddel ved at gennemføre potentielt mange føderale afstemninger om stemmesedler. Tællere i stemmesedlerne holder styr på de foretagne forsøg, og stemmesedler med højere tællere har prioritet over dem med lavere tællere. Hvis stemmesedlen hænger fast, påbegyndes en ny afstemning, nu på stemmesedlen .
Det er vigtigt at skelne mellem værdier (for eksempel hvad bestillingen til frokost skal være: pizza eller salater), stemmesedler (par counter-value) og udtalelser om stemmesedler. En SCP-runde inkluderer flere runder af føderal afstemning, især om sådanne udsagn:
- "Jeg er klar til at forpligte stemmeseddel B" og
- "Jeg erklærer forpligtelsen til stemmeseddel B".
Fra dette nodes perspektiv opnås konsensus, når den finder stemmeseddel B, som den kan bekræfte (dvs. finde et quorum, der accepterer) udsagnet "Jeg erklærer forpligtelsen til stemmeseddel B". Fra dette tidspunkt kan man sikkert handle efter værdien angivet i B – for eksempel ved at placere denne frokostbestilling. Dette kaldes eksternalisering af værdien. Når det er bekræftet, at stemmesedlen er vedtaget, kan noden være sikker på, at enhver anden node har eksternaliseret denne samme værdi eller vil gøre det i fremtiden.
Selvom mange føderative afstemninger konceptuelt udføres på erklæringer om mange forskellige stemmesedler, udveksles der ikke så mange beskeder, fordi hver besked indkapsler en række stemmesedler. En besked fremmer således tilstanden for mange føderative afstemninger på én gang, for eksempel: «Jeg accepterer committet af stemmesedler i intervallet fra til .»
Hvad betyder begreberne «forberedt» (prepared) og «commit» (commit)?
Noden stemmer for commit af stemmesedlen, når den er overbevist om, at andre noder ikke vil foretage commit af stemmesedler med andre værdier. At blive overbevist om dette er målet med at forberede erklæringen. Stemmesedlen, der siger: «Jeg er klar til commit af stemmesedlen B», er et løfte om aldrig at foretage commit af en stemmeseddel mindre end B, dvs. med en lavere tæller (SCP kræver, at værdierne i stemmesedlerne har en bestemt rækkefølge. Således er stemmesedlen mindre end , hvis N1<N2, og også hvis N1=N2 og V1<V2). Disse mindre stemmesedler «annulleres» (aborted) under forberedelsesafstemningen, mens B betragtes som «forberedt».
Hvorfor betyder «Jeg er klar til commit af stemmesedlen B» «Jeg lover aldrig at tillade commit af stemmesedler mindre end B»? Fordi SCP definerer abort som modsætning til commit. Afstemning om forberedelse af stemmesedlen indebærer også afstemning om annullering af nogle andre stemmesedler, og som vi har diskuteret før, er afstemning om én ting et løfte om aldrig at stemme imod den.
Før en commit kan sendes, skal noden først finde en stemmeseddel, som den kan bekræfte som forberedt. Med andre ord, den gennemfører en føderativ afstemning om emnet «Jeg er klar til commit af stemmesedlen B», muligvis for mange forskellige stemmesedler, indtil den finder den, der accepterer kvorummet.
Hvor kommer stemmesedlerne til valgforberedelsen fra? Først transmitterer noden forberedelsen til stemmesedlen for , hvor C er kandidatkompositten, der blev produceret under nomineringen. Men selv efter begyndelsen af stemmesedlens forberedelse kan nomineringen føre til nye kandidater, som vil blive nye stemmesedler. Imellemtiden kan pirerne have forskellige kandidater, og de kan danne en blokkerende mængde, der accepterer "Jeg er klar til at kommittere stemmeseddel B2", hvilket overbeviser noden om også at tage den med. Endelig er der en timeout-mekanisme, der genererer nye runder af føderal afstemning på nye stemmesedler med højere tællere, hvis de nuværende stemmesedler sidder fast.
Når noden finder en stemmeseddel B, som kan bekræftes som forberedt, transmitterer den en ny besked "Commit stemmeseddel B". Denne afstemning fortæller pirerne, at noden aldrig vil give afkald på B. I virkeligheden, hvis B er en stemmeseddel , så betyder "Commit stemmeseddel " ubetinget samtykke til at stemme for beredskabet af hver stemmeseddel fra til . Denne ekstra betydning hjælper andre noder med at indhente piren med commit, hvis de stadig er på tidligere faser af protokollen.
På dette tidspunkt er det værd at understrege, at disse er asynkrone protokoller. Bare fordi en node sender stemmer for commit, betyder det ikke, at dens jævnaldrende også gør det. Nogle af dem kan stadig stemme om erklæringer til forberedelsen af afstemningen, mens andre muligvis allerede har eksternaliseret betydningen. SCP forklarer, hvordan en node skal håndtere hver type peer-to-peer besked uafhængigt af dens fase.
Hvis beskeden "Jeg erklærer commit <N,C>" ikke kan accepteres eller bekræftes, er der en chance for, at beskeden <N+1, C> eller <N+2, C> vil blive accepteret eller bekræftet — eller under alle omstændigheder enhver bulletins med værdien C, og ikke nogen anden, da noden allerede har lovet aldrig at tilbagekalde <N,C>. På det tidspunkt, hvor noden transmitterer stemmer for committet, vil det være C eller intet, afhængigt af hvor langt konsensus strækker sig. Men dette er stadig ikke tilstrækkeligt for noden til at eksternalisere C. Nogle byzantinske bedragere (som udgør mindre end quorum baseret på vores antagelser om sikkerhed) kan lyve for noden. Accepteringen og derefter bekræftelsen af et bestemt bulletin (eller et interval af bulletins) — det er hvad der giver noden sikkerhed for endelig at eksternalisere C.
Afstemning af SCP gennem føderativ afstemning. Ikke vist: når som helst kan en timer aktiveres, der øger tælleren i bulletinen (og muligvis skabe en ny komposit af yderligere nominerede kandidater).
Og det er det! Så snart netværket når til konsensus, er det klar til at gøre det igen og igen. I Stellar betalingsnetværket sker dette cirka hvert 5. sekund: et brag, der kræver både sikkerhed og modstandsdygtighed, garanteret af SCP.
SCP kan opnå dette ved at stole på flere runder af føderativ afstemning. Føderativ afstemning blev muliggjort ved konceptet med quorum-skiver: sæt af ligestillede noder, som hver node har besluttet at stole på som en del af sin (subjektive) quorum. Denne konfiguration betyder, at man kan nå til konsensus selv i et åbent medlemskabsnetværk med byzantinske bedrageri.
Yderligere læsning
- Det originale tekniske dokument for SCP kan findes , og specifikationsprojekt for dets implementering.
- Den originale forfatter af SCP-protokollen, David Mazieres, forklarer det forenklet (men stadig teknisk) .
- Du har måske været overrasket over ikke at finde udtrykkene "minedrift" eller "proof-of-work" i denne artikel. SCP bruger ikke disse metoder, men nogle andre konsensusalgoritmer gør. Zain Waiswpoon har skrevet en tilgængelig .
- af et simpelt netværk, der når konsensus i løbet af én fuld runde af SCP.
- For læsere, der er interesseret i implementeringer af SCP: se , der bruges af betalingsnetværket Stellar, eller , som jeg skrev for bedre at forstå SCP.
Kilde: habr.com
