Stellar konsensusprotokoll ble først beskrevet i en vitenskapelig artikkel av David Mazieres i 2015. Dette er et «federativt bysantinsk avtalesystem» som lar desentraliserte datanettverk uten ledere effektivt oppnå konsensus om en bestemt avgjørelse. Stellar betalingsnettverk bruker Stellar Consensus Protocol (SCP) for å opprettholde en enhetlig transaksjonshistorie som alle deltakere kan se.

Det antas at konsensusprotokoller er vanskelige å forstå. SCP er enklere enn de fleste, men har fortsatt et slikt rykte – delvis på grunn av misforståelsen om at «federativ avstemming», som er temaet for den første delen av den vitenskapelige artikkelen, er SCP. Men det er ikke tilfelle! Det er bare en viktig byggestein som i den andre delen av artikkelen brukes til å lage den faktiske Stellar konsensusprotokollen.

I denne artikkelen gir vi en kort oversikt over hva et «avtalesystem» er, hva som kan gjøre det «bysantinsk», og hvorfor man skal gjøre et bysantinsk system «federativt». Deretter forklarer vi den federative avstemningsprosessen som er beskrevet i artikkelen om SCP, og til slutt forklarer vi selve SCP-protokollen.

Avtalesystemer

Et avtalesystem lar en gruppe deltakere komme til enighet om et emne, for eksempel hva de skal bestille til lunsj.

Vi i Interstellar har implementert vårt eget system for lunsjavtale: vi bestiller det som vår driftsleder John sier. Dette er et enkelt og effektivt avtalesystem. Vi har alle tillit til John og tror at han hver dag vil finne noe interessant og næringsrikt.

Men hva om John misbruker vår tillit? Han kan ensidig beslutte at vi alle må bli veganere. Om en uke eller to vil vi sannsynligvis avsette ham og gi makten til Elizabeth. Men hva om hun elsker avocado med ansjos og mener at alle må bli slik. Makten korrumperer. Derfor er det bedre å finne en mer demokratisk metode: en måte å forsikre seg om at ulike preferanser blir hensyntatt, samtidig som man sikrer et tidsbestemt og entydig resultat, slik at det ikke skjer at ingen bestiller lunsj eller at fem personer legger inn forskjellige bestillinger, eller at diskusjonen drar ut til kvelden.

Det virker som en enkel løsning: å holde en avstemning! Men dette er et villedende inntrykk. Hvem skal samle inn stemmesedlene og rapportere resultatene? Og hvorfor skal de andre tro på det han sier? Kanskje kan vi først stemme på en leder vi stoler på til å lede avstemningen — men hvem skal lede denne første avstemningen? Hva om vi ikke klarer å bli enige om en leder? Eller hvis vi blir enige, men denne lederen sitter fast i et møte eller blir sykemeldt?

Lignende problemer oppstår i distribuerte datasystemer. Alle deltakere eller noder må bli enige om en løsning, for eksempel hvem som har ansvaret for å oppdatere den felles filen eller plukke opp en oppgave fra behandlingskøen. I en kryptovalutanettverk må nodene gjentatte ganger velge hvordan den fullstendige historien ser ut, blant flere mulige versjoner, som noen ganger kan være i konflikt. Denne nettverksenigheten gir mottakeren garanti for at mynten er (a) gyldig (ikke falsk) og (b) ennå ikke brukt et annet sted. Det garanterer også at han kan bruke myntene i fremtiden, fordi den nye mottakeren vil ha de samme garantiene av de samme grunnene.

Ethvert konsensus-system i et distribuert datanettverk må være robust mot feil: det må gi konsekvente resultater til tross for feil som langsomme forbindelser, ikke-responderende noder og feil rekkefølge på meldinger. Den bysantinske konsensus-systemet er i tillegg motstandsdyktig mot «bysantinske» feil: noder som gir falsk informasjon, enten det er på grunn av feil eller i et bevisst forsøk på å undergrave systemet eller oppnå en fordel. «Bysantinsk» feiltoleranse — evnen til å stole på gruppens avgjørelse, selv når enkelte medlemmer av gruppen kan lyve eller på annen måte ikke følge beslutningsprosessen — fikk sitt navn fra liknelsen om de bysantinske generalene, som prøvde å koordinere et angrep. En god beskrivelse finnes hos Anthony Stevens.

La oss vurdere kryptovaluta-eieren Alice, som må velge mellom å kjøpe deilig iskrem fra Bob og betale gjelden sin til Carol. Kanskje ønsker Alice å betale begge med samme mynt samtidig, ved å bruke den svindelaktig. For å gjøre dette må hun overbevise Bobs datamaskin om at mynten aldri har blitt betalt til Carol, og overbevise Carols datamaskin om at mynten aldri har blitt betalt til Bob. Et bysantinsk avtalesystem gjør dette praktisk talt umulig ved å bruke en flertallsregel kalt kvotum. En node i et slikt nettverk nekter å gå over til en bestemt versjon av historien, før den ser at et tilstrekkelig antall likestilte noder – kvotum – er enige om å gjøre det. Når dette skjer, vil de danne en stor nok valgblokk til å få de resterende nodene i nettverket til å godta avgjørelsen deres. Alice kan få noen noder til å lyve på hennes vegne, men hvis nettverket er stort nok, vil forsøket hennes bli overvunnet av stemmen til ærlige noder.

Hvor mange noder kreves for kvotum? Som minimum, flertallet, mer spesifikt, et kvalifisert flertall for å motstå feil og svindel. Men for å telle flertallet, må man vite det totale antallet deltakere. På Interstellar-kontoret eller ved lokale valg er disse tallene enkle å finne. Men hvis gruppen din er et svakt definert nettverk, hvor noder kan komme og gå etter eget ønske uten samtykke fra et senter, da er det nødvendig med en føderativ bysantinsk avtalesystem som kan identifisere kvotum ikke fra en forhåndsbestemt liste over noder, men dynamisk, fra et stadig skiftende og uunngåelig ufullstendig snapshot av noder på et bestemt tidspunkt.

Det kan virke umulig å skape et kvotum sett fra én nodes perspektiv i et stort nettverk, men det er mulig. Et slikt kvotum kan til og med garantere resultater fra desentralisert stemming. Det tekniske dokumentet SCP viser hvordan dette kan gjøres ved hjelp av en prosedyre kalt føderativ stemming.

For de utålmodige

Resten av artikkelen beskriver mer detaljert den føderative stemmingen og Stellar-konsensusprotokollen. Hvis du ikke er interessert i detaljene, her er en generell oversikt over prosessen.

1. Noderne holder runder med føderal afstemning om "nominaterne". En runde af føderal afstemning betyder:
   • Noden stemmer for et forslag, for eksempel "Jeg foreslår værdien V";
   • Noden lytter til stemmerne fra noderne, indtil den finder én, der kan "acceptere";
   • Noden søger efter et "kvorum" for dette forslag. Kvorummet "bekræfter" nominaten.
2. Når noden kan bekræfte én eller flere nominater, forsøger den at "forberede" "stemmesedlen" gennem flere runder med føderal afstemning.
3. Når noden er i stand til at kontrollere beredskabet af stemmesedlen, forsøger den at kommittere den med hjælp af endnu flere runder med føderal afstemning.
4. Når noden kan bekræfte kommitment af stemmesedlen, kan den "eksternalisere" værdien af denne stemmeseddel ved at bruge den som resultatet af konsensus.

Disse trin inkluderer flere runder med føderal afstemning, som tilsammen danner én runde SCP. Lad os kigge nærmere på, hvad der sker på hvert trin.

Føderal afstemning

Føderal afstemning er en procedure til at bestemme, om netværket kan enes om et forslag. I afstemningsrunden skal hver node vælge en af mange mulige værdier. Den kan ikke gøre dette, før den er sikker på, at de andre noder i netværket ikke vælger et andet resultat. For at være sikre på dette, udveksler noderne en strøm af beskeder frem og tilbage, så alle bekræfter, at kvorummet af noder godtager det samme beslutningen. Resten af denne sektion forklarer termerne i denne sætning og hvordan hele proceduren forløber.

Kvorumer og kvorumskiver

Lad os starte med at definere kvorum. Som vi diskuterede ovenfor, er det i et decentraliseret netværk med dynamisk medlemskab 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é kvorumskive (quorum slice): et lille sæt af ligestillede noder, som noden har tillid til at overføre information om afstemningsstatus til resten af netværket. Hver node bestemmer selv sin egen kvorumskive (som den bliver medlem af i praksis).

Danning av quorum begynner med skjæringspunktet for quorum. For hver node legges nodene i dens skjæring til. Deretter legges medlemmene av skjæringene til disse nodene og så videre. Etter hvert som prosessen fortsetter, dukker det opp flere og flere noder som du ikke kan legge til, fordi de allerede er inkludert i skjæringen. Når det ikke er flere nye noder å legge til, stopper prosessen: vi har dannet et quorum gjennom «transitiv lukking» av skjæringspunktet for den første noden.

For å finne et quorum fra en gitt node...

... legger vi til medlemmene av dens skjæring...

... deretter legger vi til medlemmene av skjæringene til disse nodene.

Vi fortsetter til det ikke er flere noder å legge til.

Det er ikke flere noder å legge til. Dette er et quorum.

Faktisk kan hver node være en del av mer enn én skjæring. For å danne et quorum velger du bare én av skjæringene og legger til medlemmene; deretter velger du hvilken som helst skjæring for hvert av medlemmene og legger til medlemmer dette av skjæringen og så videre. Dette betyr at hver node er medlem av et sett av mulige quorum.

Velg bare én skjæring for quorum i hvert steg.

Et mulig quorum. Eller et alternativ...

... velger andre skjæringer...

... (når det er mulig)...

... skaper et annet quorum.

Hvordan vet en node hvilke skjæringer andre noder består av? Akkurat som med annen informasjon om andre noder: fra meldinger som hver node sender ut i nettverket når dens stemmekonstitusjon endres. Hver sending inkluderer informasjon om skjæringene til den sendende noden. I den tekniske dokumentasjonen for SCP er ikke kommunikasjonsmekanismen spesifisert. Implementeringer bruker vanligvis gossip-protokollen for å garantere distribusjon av meldinger over hele nettverket.

La oss minne om at i det ikke-federative bysantinske konsensus-systemet defineres kvoten som majoriteten av alle noder. Det bysantinske konsensus-systemet er utviklet med tanke på spørsmålet: hvor mange uærlige noder kan systemet tåle? I et system med N noder, designet for å overleve ved f feil (svindel), må en node være i stand til å oppnå fremdrift ved å motta svar fra N−f peer-noder, siden f av dem kanskje ikke fungerer. Men ved å motta svar fra N−f peer-noder, kan man anta at alle f peer-noder (fra hvilke noden ikke fikk svar) faktisk er ærlige. Dermed er de skadelige f av N−f peer-noder (fra hvilke svar ble mottatt). For at nodene skal komme til en felles konsensus, må det være et flertall blant de gjenværende nodene, det vil si vi trenger at N−f er større enn 2f eller N > 3f. Så vanligvis vil et system designet for å overleve ved f feil ha totalt N=3f+1 noder og en kvote-størrelse på 2f+1. Så snart et forslag passerer kvotetærskelen, er de andre medlemmene i nettverket overbevist om at enhver konkurrerende forslag vil mislykkes. Så nettverket konvergerer mot et resultat.

Men i det federative bysantinske konsensus-systemet kan det ikke bare være noen flertall (fordi ingen vet den totale størrelsen på nettverket), men begrepet flertall er generelt ubrukelig! Hvis medlemskapet i systemet er åpent, kan noen få flertall bare ved å gjennomføre det som kalles en Sybil-angrep: ved gjentatte ganger å bli med i nettverket gjennom flere noder. Så hvorfor kan den transitive lukkingen av skjæringen bli kalt kvotum, og hvordan klarer det å undertrykke konkurrerende forslag?

Teknisk sett, ikke i det hele tatt! Tenk deg et nettverk av seks noder, der to grupper er isolert i kvoten sine skjæringer fra hverandre. Den første undergruppen kan fatte en beslutning som den andre aldri får høre om, og omvendt. For dette nettverket er det ingen måte å oppnå konsensus (bortsett fra ved en tilfeldighet).

Derfor krever SCP at for federativ avstemning (og for anvendelse av viktige teoremer i artikkelen) må nettverket ha en egenskap som kalles kvotekrysning. I nettverket med denne egenskapen, vil alltid to quorum som kan bygges, overlappe i minst ett nod. For å bestemme de dominerende stemningene i nettverket, er dette like nyttig som å ha flertallet. Intuitivt betyr dette at hvis et quorum er enig i utsagn X, kan ikke noe annet quorum aldri være enig i noe annet, fordi det må inkludere en node fra det første quorum som allerede har stemt for X.

Hvis det er overlapping av quorum i nettverket…

… så vil enhver to quorum du kan bygge…

… alltid krysse hverandre.

(Selvfølgelig kan de overlappende nodene vise seg å være bysantinske-lurendreiere eller dårlige på andre måter. I så fall vil ikke overlappingen av quorum hjelpe nettverket med å oppnå enighet i det hele tatt. Av denne grunn er mange resultater i det tekniske dokumentet SCP basert på åpenbart uttrykte antakelser, som at det er et overlapp mellom quorum i nettverket, selv etter fjerning av dårlige noder.. For enkelhets skyld lar vi disse antakelsene vær uuttalt i resten av artikkelen).

Det kan virke urimelig å forvente pålitelig overlapping av quorum i et nettverk av uavhengige noder. Men det er to grunner til at dette er tilfelle.

Den første grunnen er eksisteringen av selve internett. Internett er et perfekt eksempel på et nettverk av uavhengige noder med overlapping av quorum. De fleste noder på internett kobles kun til noen få andre lokale noder, men disse små settene overlapper stort nok til at hver node er tilgjengelig fra hverandre node via en eller annen rute.

Den andre grunnen er spesifikk for betalingsnettet Stellar (den mest utbredte bruken av SCP). Hver aktivum i Stellar-nettverket har en utsteder, og Stellar-rekommandasjoner krever at hver utsteder utpeker en eller flere noder i nettverket for å håndtere innløsningsforespørsler. Det er i din interesse å inkludere disse nodene direkte eller indirekte i kvorumene for hvert aktivum som interesserer deg. Dermed vil kvorumene for alle noder som er interessert i et bestemt aktivum, overlappe i det minste på disse innløsningsnodene. Noder som er interessert i flere aktivum, vil inkludere alle innløsningsnoder til de aktuelle utstederne i sine kvorumskutter, og de vil tilstrebe å samle alle aktivum sammen. I tillegg vil eventuelle aktivum som ikke er knyttet på denne måten til andre i nettverket, og skal ikke være knyttet — det er designet slik at det ikke skal være overlappende kvorum i dette nettverket (for eksempel ønsker banker i dollar-sonen noen ganger å handle med banker i euro-sonen og banker i pesos-sonen, så de er i ett og samme nettverk, men ingen av dem bryr seg om det separate nettet av barn som handler baseballkort).

Selvfølgelig, vendingen av kvorumene er ikke en garanti. Andre byzantinske konsensusystemer skylder mye av sin kompleksitet til kvorumgarantiene. Et viktig nyskapende aspekt ved SCP er at det avlaster ansvaret for å danne kvorum fra selve konsensusalgoritmen og flytter det til applikasjonsnivå. Dermed, selv om føderativ stemmegivning er temmelig generelt for å stemme om hva som helst, avhenger påliteligheten i virkeligheten kritisk av en bredere forståelse av disse verdiene. Noen hypotetiske bruksformer kan vise seg å være mindre gunstige for å skape godt sammenkoblede nettverk enn andre.

Stemmegivning, vedtak og bekreftelse

I runden for føderativ stemmegivning kan en node valgfritt begynne å stemme for en verdi V. Dette betyr å sende et budskap til nettverket: «Jeg er node N, mine kvorumskutter er Q, og jeg stemmer for V». Når en node stemmer på denne måten, lover den at den aldri har stemt mot V og aldri vil gjøre det.

I overføringene fra peer-noder ser hver node hvordan andre stemmer. Så snart noden har samlet et tilstrekkelig antall slike meldinger, kan den spore skjæringspunktene til kvorumene og prøve å finne kvorumer. Hvis den ser et kvorum av noder som også stemmer for V, kan den gå videre til vedtak V og sende denne nye meldingen til nettverket: «Jeg er node N, mine skjæringspunkter til kvorum Q, og jeg vedtar V». Vedtak gir en sterkere garanti enn enkel avstemning. Når en node stemmer for V, kan den aldri stemme for andre alternativer. Men hvis en node vedtar V, vil ingen noder i nettet noen gang vedta et annet alternativ (teorem 8 i det tekniske dokumentet SCP beviser dette).

Selvfølgelig er det stor sjanse for at det umiddelbart ikke finnes et kvorum av noder som er enige om V. Andre noder kan stemme for andre verdier. Men for noden er det en annen måte å gå fra enkel avstemning til vedtak. N kan vedta en annen verdi W, selv om den ikke har stemt for det, og selv om den ikke ser et kvorum for det. For å ændre sin stemme er det nok å se et blokkerende sett av noder som har vedtatt W. Det blokkerende settet er én node fra hver av skjæringspunktene til kvorumene N. Som navnet antyder, er det i stand til å blokkere enhver annen verdi. Hvis alle noder i et slikt sett vedtar W, så (ifølge teorem 8) vil det aldri være mulig å danne et kvorum som vedtar en annen verdi, og derfor er det også trygt for N å vedta W.

Node N med tre skjæringspunkter av kvorumer.

B-D-F er et blokkerende sett for N: det inkluderer én node fra hver av skjæringspunktene til N.

B-E er også et blokkerende sett for N, fordi E vises i to av skjæringspunktene til N.

Men et blokkerende sett er ikke et kvorum. Det ville vært for enkelt å lure node N til å vedta den ønskede verdien hvis det var tilstrekkelig å hacke bare én node i hver av skjæringspunktene til N. Derfor er vedtak av verdien ikke slutten på avstemningen. I stedet må N bekrefte verdien, det vil si se et kvorum av noder som vedtar den. Hvis den kommer så langt, beviser det tekniske dokumentet SCP (i teorem 11) at resten av nettverket også til slutt vil bekrefte den samme verdien, så N vil fullføre den føderale avstemningen med en bestemt verdi som resultat.

Føderal avstemning.

Prosessen for avstemning, vedtak og bekreftelse utgjør én hel runde med føderal avstemning. Stellar konsensusprotokollen kombinerer mange slike runder for å skape et komplett konsensusssystem.

Stellar konsensusprotokoll

De to viktigste egenskapene til et konsensussystem er sikkerhet og robusthet. Konsensusalgoritmen er «sikker» hvis den aldri kan gi forskjellige resultater til forskjellige deltakere (Bobs historie vil aldri stride med Carols). «Robusthet» betyr at algoritmen alltid vil gi et resultat, det vil si at den ikke vil henge seg opp.

Den beskrevne prosedyren for føderal avstemning er sikker i den forstand at hvis en node bekrefter verdien V, så vil ingen annen node bekrefte en annen verdi. Men «ikke bekrefte en annen verdi» betyr ikke at den nødvendigvis bekrefter noe. Deltakere kan stemme for så mange forskjellige verdier at ingenting når terskelen for vedtak. Dette betyr at det ikke er robusthet.

Stellar konsensusprotokollen bruker føderal avstemning på en måte som garanterer både sikkerhet og robusthet. (Sikkerhets- og robusthetsgarantiene til SCP har et teoretisk begrenset nivå. Konstruksjonen velger en veldig sterk sikkerhetsgaranti, og ofrer en liten svekkelse av robustheten, men med tilstrekkelig tid vil konsensus med stor sannsynlighet bli oppnådd). I korte trekk går ideen ut på å gjennomføre flere føderale avstemninger om flere verdier inntil en av dem går helt gjennom alle fasene av SCPs avstemning, som beskrevet nedenfor.

Verdiene som SCP søker konsensus om kan være en transaksjonshistorikk eller en bestilling av lunsj, eller noe annet, men det er viktig å merke seg at dette ikke er de verdiene som bli vedtatt eller bekreftet. I stedet skjer den føderale avstemningen om påstander om disse verdiene.

De første rundene med føderal avstemning skjer på nominasjonsstadiet (nominasjonsfase), med et sett av påstander som «Jeg foreslår V», muligens for mange forskjellige verdier av V. Målet med nominasjonen er å finne én eller flere påstander som kan gå gjennom vedtakelse og bekreftelse.

Etter å ha funnet bekreftede kandidater, går SCP videre til avstemningsfasen, der målet er å finne en viss stemmeseddel (det vil si beholderen for det foreslåtte verdien) og quorum som kan erklære commiten for det (commit). Hvis quorumet gjør commit av stemmeseddelen, aksepteres dens verdi som konsensus. Men før en node kan stemme for commit av stemmeseddelen, må den først bekrefte annuleringen av alle stemmesedler med lavere telleverdi. Disse trinnene — annullering av stemmesedler for å finne den som kan bekrefte commit — inkluderer flere runder med føderal avstemning om flere påstander om stemmesedler.

I de følgende avsnittene beskrives nominasjon og avstemming mer detaljert.

Nominasjon

I begynnelsen av nominasjonsfasen kan hver node spontant velge en verdi V og stemme for å bekrefte "Jeg nominerer V". Målet i denne fasen er å bekrefte nominasjonen av en viss verdi gjennom føderal avstemning.

Det kan hende at et tilstrekkelig antall noder stemmer for tilstrekkelig forskjellige påstander, og ingen nominering når akseptterskelen. Derfor, i tillegg til å transmittere sine egne nominasjonsstemmer, "reflekterer" nodene nomineringene fra sine naboer. Refleksjon (echo) betyr at hvis en node stemmer for nominasjonen V, men ser en melding fra en nabo som stemmer for nominasjonen W, så vil den nå stemme for både nominasjonene V og W. (Ikke alle stemmer fra naboer får refleksjon under nominasjonsprosessen, da dette kan føre til en eksplosjon av forskjellige nominerte. SCP inkluderer en mekanisme for regulering av disse stemmene. Kort sagt, det finnes en formel for å bestemme "prioriteten" til en nabo sett fra noden, og kun stemmene fra høyprioriterte noder blir reflektert. Jo lengre nominasjonen pågår, jo lavere blir terskelen, så noden utvider settet av naboer hvis stemmer den vil reflektere. Prioritetsformelen som en av inngangsparameterne inkluderer slotnummeret, så en høyprioritert peer for én slot kan være lavprioritert for en annen, og omvendt).

Konseptuelt er det å fremme både V og W separate føderale stemmer, som hver for seg kan oppnå aksept eller bekreftelse. I praksis pakker SCP-protokollen disse separate stemmene sammen.

Selv om å stemme for å fremme V er et løfte om aldri å stemme imot, definerer applikasjonsnivået – i dette tilfellet SCP – hva «imot» betyr. SCP ser ikke noen uttalelse som motsetter seg stemmene «Jeg fremmer X», det vil si det finnes ingen melding «Jeg er imot å fremme X», så noden kan stemme for å fremme alle verdier. Mange av disse nominasjonene vil ikke føre til noe, men til slutt vil noden kunne akseptere eller bekrefte en eller flere verdier. Når en nominert er bekreftet, blir han kandidaten.

Fremme av SCP ved hjelp av føderalt stemmesystem. Det kan være mange verdier “B” som fremmes av likestilte noder og «reflektert» av noden.

Fremming av kandidater kan føre til flere bekreftbare kandidater. Derfor krever SCP at applikasjonsnivået gir en eller annen metode for å kombinere kandidater til én kompositt (kompositt). Metoden for kombinasjon kan være hvilken som helst. Det viktigste er at hvis denne metoden er deterministisk, så vil hver node kombinere de samme kandidatene. I en stemmesystem for lunsj kan «kombinering» ganske enkelt bety å avstå fra én av de to kandidatene. (Men på en deterministisk måte: hver node må velge den samme verdien som skal forkastes. For eksempel, et tidlig valg i alfabetisk rekkefølge). I betalingsnettverket Stellar, hvor avstemningen skjer for transaksjonshistorikken, innebærer kombinasjon av to foreslåtte nominerte å kombinere transaksjonene de inneholder, samt de nyeste av deres to tidsstempler.

Den tekniske beskrivelsen av SCP beviser (teorem 12) at ved slutten av nominasjonsfasen konvergerer nettverket til slutt til én kompositt. Men det er et problem: føderal stemmegivning er en asynkron protokoll (som SCP). Med andre ord, nodene er ikke koordinert etter tid, men bare etter meldingene de sender. Fra nodens synspunkt er det uklart når ble avsluttet fasa forslaging. Selv om alle noder til slutt vil komme til den samme kompositt, kan de ta forskjellige ruter på veien, noe som skaper ulike sammensatte kandidater underveis, og de kan aldri si hvilken av dem som er den endelige.

Men det er greit. Forslag er bare en forberedelse. Hovedsaken er å begrense antallet kandidater for å oppnå en konsensus, som skjer i prosessen. stemmegivning (stemmegivning).

Stemmegivning

En stemmeseddel er et par , der counter er et heltall som begynner på 1, og value er kandidaten fra forslagsfasen. Dette kan være nodens egen kandidat eller en kandidat fra en nabonode som er akseptert av denne noden. Grovt sett, i stemmegivningen gjøres gjentatte forsøk på å få nettverket til å oppnå konsensus om en kandidat i en bestemt stemmeseddel ved å gjennomføre potensielt mange føderative stemmegivninger på stemmesedler. Tellere i stemmesedlene sporer gjennomførte forsøk, og stemmesedler med høyere tellere har prioritet over stemmesedler med lavere tellere. Hvis stemmeseddelen sitter fast, begynner en ny stemmegivning nå på stemmeseddelen .

Det er viktig å skille mellom verdier (for eksempel hva lunsjbestillingen skal være: pizza eller salater), stemmesedler (paret counter-value) og uttalelser om stemmesedler. SCP-runden inkluderer flere runder med føderativ stemmegivning, spesielt på utsagn som:

• «Jeg er klar til å forplikte stemmeseddel B» og
• «Jeg erklærer forpliktelsen til stemmeseddel B»

Fra denne nodens perspektiv oppnås konsensus når den finner stemmeseddel B, som den kan bekrefte (det vil si finne et flertall som aksepterer) utsagnet «Jeg erklærer forpliktelsen til stemmeseddel B». Fra dette øyeblikket kan man trygt handle i henhold til verdien angitt i B – for eksempel legge inn denne lunsjbestillingen. Dette kalles eksternalisering av verdien. Når aksept av stemmeseddelen er bekreftet, kan noden være sikker på at enhver annen node har eksteralisert denne samme verdien eller nødvendigvis vil gjøre det i fremtiden.

Selv om mange føderale avstemninger skjer gjennom krav om mange forskjellige stemmesedler, utveksler de ikke så mange meldinger, fordi hver melding kapsler inn en rekke stemmesedler. Én melding fremmer dermed tilstanden til mange føderale avstemninger samtidig, for eksempel: «Jeg godtar å foreta en forpliktelse på stemmesedlene fra <min,V> til <max,V>».

Hva betyr begrepene «forberedt» (prepared) og «forpliktelse» (commit)?

Noden stemmer for forpliktelsen av stemmesedlen når den er overbevist om at andre noder ikke vil foreta forpliktelse av stemmesedler med andre verdier. Å overbevise om dette er målet med å forberede erklæringen. En avstemning der det sies: «Jeg er klar til å forplikte meg til stemmeseddel B», er et løfte om aldri å foreta forpliktelse av stemmesedler mindre enn B, det vil si med en lavere teller (SCP krever at verdiene i stemmesedler har en bestemt rekkefølge. Dermed er stemmeseddel <N1,V1> mindre enn <N2,V2>, hvis N1<N2, og også hvis N1=N2 og V1<V2). Disse mindre stemmesedlene «avvises» (aborted) under forberedelsesstemmesedelen, mens B betraktes som «forberedt».

Hvorfor betyr «Jeg er klar til å forplikte meg til stemmeseddel B» «Jeg lover aldri å tillate forpliktelse av stemmesedler mindre enn B»? Fordi SCP definerer abort som motsetningen til forpliktelse. Forberedelsesstemmesedelen innebærer også avstemning om avvikling av andre stemmesedler, og som vi har diskutert tidligere, innebærer en avstemning for noe ett – et løfte om aldri å stemme imot det.

Før en forpliktelse sendes ut, må noden først finne en stemmeseddel som den kan bekrefte som forberedt. Med andre ord gjennomfører den en føderal avstemning på temaet «Jeg er klar til å forplikte meg til stemmeseddel B», muligens for mange forskjellige stemmesedler, inntil den finner den som godtar kvoren.

Hvor kommer stemmesedlerne til forberedelse af afstemningen fra? Først transmitterer noden forberedelsen til afstemningen for , hvor C er en sammensat kandidat, der blev produceret i opstillingsfasen. Men selv efter at forberedelsen til afstemningen er begyndt, kan opstillingen føre til, at der kommer nye kandidater, som vil blive nye stemmesedler. I mellemtiden kan piraterne have forskellige kandidater, og de kan danne et blokkerende sæt, der accepterer "Jeg er klar til at kommittere stemmesedlen B2", hvilket vil overbevise noden om også at acceptere det. Endelig er der en timeout-mekanisme, der genererer nye runder af føderativ afstemning på nye stemmesedler med højere tællere, hvis de aktuelle stemmesedler sidder fast.

Når noden finder en stemmeseddel B, der kan bekræftes som forberedt, transmitterer den en ny besked "Commit stemmeseddel B". Denne afstemning fortæller piraterne, at noden aldrig vil afvise B. Faktisk, hvis B er en stemmeseddel , 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 piraten med commit, hvis de stadig befinder sig på tidligere stadier af protokollen.

På dette tidspunkt skal det endnu engang understreges, at dette er asynkrone protokoller. Bare fordi én node sender stemmer for commit, betyder det ikke, at dens jævnaldrende også gør det. Nogle af dem kan stadig stemme på erklæringer til forberedelse af afstemningen, mens andre muligvis allerede har eksternaliseret betydningen. SCP forklarer, hvordan noden skal håndtere hver type peer-to-peer besked uafhængigt af dens fase.

Hvis meldingen «Jeg erklærer forpliktelse » ikke kan godtas eller bekreftes, er det en sjanse for at meldingen eller kan godtas eller bekreftes—eller, i alle fall, enhver bulletin med verdien C, og ikke noe annet, siden noden allerede har lovet aldri å tilbakekalle . Når noden sender stemmer for forpliktelsen, blir det enten C eller ingenting, avhengig av hvor langt konsensus vil gå. Men dette er fortsatt ikke tilstrekkelig for noden til å eksternalisere C. Noen bysantinske såkalte (som utgjør mindre enn kvorum, basert på våre antagelser om sikkerhet) kan lyve for noden. Å akseptere og deretter bekrefte en eller flere bulletiner (eller et intervall av bulletiner)—det er det som gir noden tillit til endelig å eksternalisere C.

Ballotering av SCP gjennom føderativ avstemning. Ikke vist: når som helst kan en timer gå av, noe som øker telleren i bulletinen (og muligens produsere en ny kompositt fra tilleggskandidater).

Og det er det! Når nettverket har kommet til konsensus, er det klart til å gjøre det igjen og igjen. I Stellar betalingsnettverket skjer dette omtrent hvert 5. sekund: en prestasjon som krever både sikkerhet og robusthet, garantert av SCP.

SCP kan oppnå dette ved å stole på flere runder med føderativ avstemning. Føderativ avstemning ble muliggjort av konseptet med kvorumsnitt: sett av likeverdige noder som hver node har besluttet å stole på som en del av sitt (subjektive) kvorum. Denne konfigurasjonen betyr at man kan komme til konsensus selv i et nett med åpen medlemskap og bysantinske bedrageri.

Ytterligere lesing

• Den opprinnelige tekniske dokumentasjonen av SCP kan bli funnet her, men here prosjektspesifikasjoner for implementeringen.
• Den opprinnelige forfatteren av SCP-protokollen, David Mazieres, forklarer den på en forenklet (men fortsatt teknisk) måte her.
• Du har kanskje blitt overrasket over ikke å finne begrepene «gruvearbeid» eller «bevis på arbeid» i denne artikkelen. SCP bruker ikke disse metodene, men noen andre konsensusalgoritmer bruker dem. Zayn Witherspoon har skrevet en tilgjengelig oversikt over konsensusalgoritmer.
• Trinnvis beskrivelse en enkel nettverksstruktur som når konsensus i løpet av en full SCP-runde.
• For lesere som er interessert i implementeringer av SCP: se. C++-kode, brukt av betalingsnettverket Stellar, eller Go-kode, som jeg skrev for bedre forståelse av SCP.

Kilde: habr.com