Stellar-konsensusprotokollen ble først beskrevet i David Mazier i 2015. Dette er et "føderalt bysantinsk avtalesystem" som lar desentraliserte, lederløse datanettverk effektivt oppnå konsensus om en beslutning. Stellars betalingsnettverk bruker Stellar Consensus Protocol (SCP) for å opprettholde en konsistent transaksjonshistorikk som er synlig for alle deltakere.
Konsensusprotokoller anses som vanskelige å forstå. SCP er enklere enn de fleste av dem, men deler likevel dette ryktet – delvis på grunn av den feilaktige ideen om at «federated voting», som er tema for første halvdel av den vitenskapelige artikkelen, er SCP. Men det er ikke sant! Dette er bare en viktig byggestein som andre halvdel av artikkelen bruker for å lage faktiske Stellar konsensusprotokoll.
I denne artikkelen vil vi kort forklare hva et "avtalesystem" er, hva som kan gjøre det "bysantinsk" og hvorfor gjøre det bysantinske systemet "føderalt". Vi vil deretter forklare den fødererte stemmeprosedyren beskrevet i SCP-artikkelen, og til slutt vil vi forklare selve SCP-protokollen.
Avtalesystemer
Et system med avtaler lar en gruppe deltakere komme til enighet om et emne, for eksempel hva de skal bestille til lunsj.
Hos Interstellar har vi implementert vårt eget serveringsavtalesystem: vi bestiller det vår driftssjef, John, sier. Dette er et enkelt og effektivt avtalesystem. Vi stoler alle på John og tror at han vil finne noe interessant og næringsrikt hver dag.
Men hva om John misbruker tilliten vår? Han kan på egenhånd bestemme at vi alle skal bli veganere. Om en uke eller to vil vi sannsynligvis styrte ham og overlate makten til Elizabeth. Men plutselig elsker hun avokado med ansjos og synes alle burde være sånn. Makt korrumperer. Så det er bedre å finne en mer demokratisk metode: en måte å sørge for at ulike preferanser blir tatt i betraktning, samtidig som man sikrer et rettidig og entydig resultat, slik at ingen ender opp med å bestille lunsj, eller fem personer legger inn forskjellige bestillinger, eller diskusjonen drar utover kvelden.
Det ser ut til at løsningen er enkel: hold en stemme! Men dette er et misvisende inntrykk. Hvem skal samle stemmesedlene og rapportere resultatene? Og hvorfor skal andre tro på det han sier? Kanskje vi kan i begynnelsen stemme på en leder som vi stoler på skal lede avstemningen – men som skal lede den første ved å stemme? Hva om vi ikke kan bli enige om en leder? Eller hva om vi kommer til enighet, men denne lederen blir sittende fast i et møte eller blir sykemeldt?
Lignende problemer oppstår i distribuerte datanettverk. Alle deltakere eller noder må være enige om en avgjørelse, for eksempel hvis tur det er til å oppdatere en delt fil eller fjerne en oppgave fra behandlingskøen. I et kryptovalutanettverk må noder gjentatte ganger velge hvordan hele historien ser ut fra flere mulige versjoner, som noen ganger er i konflikt. Denne nettverksavtalen gir forsikring til mottakeren om at mynten er (a) gyldig (ikke forfalsket) og (b) ennå ikke er brukt andre steder. Dette sikrer også at han vil kunne bruke myntene i fremtiden fordi den nye mottakeren vil ha de samme garantiene av samme grunner.
Ethvert konsensussystem i et distribuert datanettverk må være feiltolerant: det må gi konsistente resultater til tross for feil som trege koblinger, noder som ikke reagerer og feil meldingsrekkefølge. bysantinsk Avtalesystemet er i tillegg motstandsdyktig mot "bysantinske" feil: noder som gir falsk informasjon, enten det er på grunn av en feil eller i et bevisst forsøk på å undergrave systemet eller få noen fordeler. "Bysantinsk" feiltoleranse - evnen til å stole på en gruppebeslutning selv når noen gruppemedlemmer kan lyve eller på annen måte ikke følger reglene for beslutningstaking - kalles som forsøkte å koordinere angrepet. hos Anthony Stevens.
Tenk på kryptomynteeier Alice, som må velge mellom å kjøpe deilig is fra Bob og betale ned Carols gjeld. Kanskje ønsker Alice å betale dem begge samtidig ved å bruke den samme mynten på en uredelig måte. For å gjøre dette må hun overbevise Bobs datamaskin om at mynten aldri ble betalt til Carol, og overbevise Carols datamaskin om at mynten aldri ble betalt til Bob. Det bysantinske avtalesystemet gjør dette praktisk talt umulig, ved å bruke en form for flertallsstyre kalt quorum. En node i et slikt nettverk nekter å flytte til en bestemt versjon av historien før den ser at et tilstrekkelig antall jevnaldrende – et quorum – godtar en slik overgang. Når dette skjer, vil de danne en stemmeblokk som er stor nok til å tvinge de gjenværende nettverksnodene til å bli enige i avgjørelsen deres. Alice kan tvinge noen noder til å lyve på hennes vegne, men hvis nettverket er stort nok, vil hennes forsøk bli overveldet av stemmene til ærlige noder.
Hvor mange noder kreves for quorum? Som et minimum, et flertall, eller rettere sagt, et kvalifisert flertall for å bekjempe feil og svindel. Men for å telle flertallet, må du vite det totale antallet deltakere. På Interstellar-kontoret eller ved distriktsvalget er disse tallene enkle å finne ut. Men hvis gruppen din er et løst definert nettverk der noder kan gå inn og ut etter eget ønske uten godkjenning fra senteret, trenger du føderal et bysantinsk avtalesystem som er i stand til å bestemme quorumer ikke fra en forhåndsbestemt liste over noder, men dynamisk, fra et stadig skiftende og uunngåelig ufullstendig øyeblikksbilde av noder på et gitt tidspunkt.
Det kan virke umulig å opprette et quorum fra perspektivet til en enkelt node i et stort nettverk, men det er mulig. Et slikt beslutningsdyktighet kan til og med garantere resultatene av desentralisert avstemning. SCP-hvitboken viser hvordan du gjør dette ved å bruke en prosedyre kalt ved føderal avstemning.
For utålmodig
Resten av artikkelen beskriver føderert stemmegivning og Stellar-konsensusprotokollen mer detaljert. Hvis du ikke er interessert i detaljene, her er en generell oversikt over prosessen.
- Nodene gjennomfører runder med føderal avstemning om "nominerte". En føderal avstemningsrunde betyr:
- Noden stemmer for et utsagn, for eksempel "Jeg foreslår verdien av V";
- Noden lytter til jevnaldrendes stemmer til den finner en som kan "motta";
- Noden ser etter et "quorum" for denne påstanden. Et quorum "bekrefter" den nominerte.
- Når en node kan bekrefte en eller flere nominerte, forsøker den å "forberede" "stemmeseddelen" gjennom flere runder med føderert avstemning.
- Når en node er i stand til å bekrefte at stemmeseddelen er klar, prøver den å foreta den gjennom enda flere runder med føderert avstemning.
- Når en node kan bekrefte en forpliktelse av en stemmeseddel, kan den "eksternalisere" verdien av den stemmeseddelen ved å bruke den som et konsensusresultat.
Disse trinnene involverer flere runder med føderert stemmegivning, som til sammen utgjør en SCP-runde. La oss se nærmere på hva som skjer ved hvert trinn.
Federert stemmegivning
Federert stemmegivning er en prosedyre for å avgjøre om nettverket kan bli enige om et forslag. I avstemningsrunden må hver node velge en av potensielt mange mulige verdier. Den kan ikke gjøre dette med mindre den er sikker på at andre noder i nettverket ikke vil velge et annet utfall. For å være sikker på dette, utveksler noder en bølge av meldinger frem og tilbake slik at alle bekreftetAt quorum knop tar samme ting avgjørelse. Resten av denne delen forklarer begrepene i denne setningen og hvordan hele prosedyren foregår.
Quorum og quorum skiver
La oss starte med å definere et quorum. Som vi diskuterte ovenfor, i et desentralisert nettverk med dynamisk medlemskap, er det umulig å vite på forhånd antall noder og dermed hvor mange som trengs for flertallet. Federert stemmegivning løser dette problemet ved å introdusere en ny idé quorum kuttet (quorum skive): Et lite sett med likemenn som en node stoler på for å kommunisere stemmestatusinformasjon til resten av nettverket. Hver node definerer sin egen quorumsdel (som den blir et de facto medlem av).
Quorumdannelse begynner med et quorumskutt. For hver node blir dens kuttede noder lagt til. Deretter legges skivebegrepene til disse nodene og så videre. Etter hvert som du fortsetter, er det flere og flere noder du ikke kan legge til fordi de allerede er inkludert i stykket. Når det ikke er flere nye noder å legge til, stopper prosessen: vi har dannet et quorum ved "transitiv lukking" av quorumsdelen av den innledende noden.
For å finne quorum fra en gitt node...
... legg til medlemmer av stykket...
...så legger vi til skivemedlemmer av disse nodene.
Vi fortsetter til det ikke er noen noder igjen å legge til.
Det er ingen noder igjen å legge til. Dette er et quorum.
Faktisk kan hver node vises i mer enn én skive. For å danne et quorum, velg bare én av skivene og legg til medlemmer; velg deretter et stykke for hvert av medlemmene og legg til medlemmer det kutte og så videre. Dette betyr at hver node er medlem av mange mulige quorumer.
Velg bare én quorumsskive ved hvert trinn.
Ett mulig beslutningsdyktighet. Eller et alternativ...
...velg andre skiver...
…(når det er mulig)…
... skaper nok et quorum.
Hvordan vet en node hvilke skiver andre noder er i? På samme måte som annen informasjon om andre noder: fra overføringene som hver node sender til nettverket når stemmetilstanden endres. Hver kringkasting inneholder informasjon om avsendernodens skiver. SCP-hvitboken spesifiserer ikke en kommunikasjonsmekanisme. Implementeringer bruker vanligvis for garantert kringkasting av meldinger i hele nettverket.
Husk at i det ikke-føderale bysantinske avtalesystemet er et quorum definert som et flertall av alle noder. Det bysantinske avtalesystemet er utformet fra synspunktet om spørsmålet: hvor mange uærlige noder kan systemet tolerere? I et system med N noder designet for å overleve f feil, bør en node kunne gjøre fremskritt ved å motta tilbakemelding fra N−f likemenn siden f av dem kan være nede. Men etter å ha mottatt et svar fra N−f-peers, kan vi anta at alle f-peers (som noden ikke mottok et svar fra) faktisk er ærlige. Således er f av N−f jevnaldrende (som svaret ble mottatt fra) ondsinnede. For at noder skal komme til samme konsensus, må flertallet av de gjenværende nodene være ærlige, det vil si at vi trenger at N−f er større enn 2f eller N > 3f. Så typisk vil et system designet for å overleve f feil ha totalt N=3f+1 noder og en quorumstørrelse på 2f+1. Når et forslag passerer quorum-terskelen, er resten av nettverket overbevist om at eventuelle konkurrerende forslag vil mislykkes. Slik konvergerer nettverket til resultatet.
Men i et føderalt bysantinsk avtalesystem kan det ikke bare være flertall (fordi ingen vet den totale størrelsen på nettverket), men konseptet med flertall er fullstendig ubrukelig! Hvis medlemskap i systemet er åpent, kan noen få flertall ganske enkelt ved å utføre et såkalt Sybil-angrep: gjentatte ganger bli med i nettverket på tvers av flere noder. Så hvorfor kan transitiv skivelukking kalles quorum, og hvordan er den i stand til å undertrykke konkurrerende forslag?
Teknisk sett, ingen måte! Se for deg et nettverk av seks noder, der to trillinger er isolert i hverandres quorumsskiver. Den første undergruppen kan ta en beslutning som den andre aldri vil høre om, og omvendt. Det er ingen måte for dette nettverket å nå konsensus (unntatt ved en tilfeldighet).
Derfor krever SCP at for føderert stemmegivning (og for at de viktige teoremene i papiret skal gjelde), må nettverket ha en egenskap kalt skjæringspunktet mellom quorumer. I et nettverk med denne egenskapen overlapper alle to quorumer som kan konstrueres alltid i minst én node. For å bestemme den rådende følelsen av nettverket er dette like godt som å ha flertall. Intuitivt betyr dette at hvis et quorum godtar setning X, kan ingen andre quorumer noen gang gå med på noe annet, fordi det nødvendigvis vil inkludere en node fra det første quorumet som allerede har stemt for X.
Hvis det er et skjæringspunkt mellom quorumer i nettverket...
...så kan du bygge to hvilket som helst quorum...
...vil alltid krysse hverandre.
(Selvfølgelig kan overlappende noder vise seg å være bysantinsk liggende eller på annen måte dårlige. I dette tilfellet hjelper ikke quorum-krysset at nettverket blir enig i det hele tatt. Av denne grunn er mange av resultatene i SCP-hvitboken basert på eksplisitte forutsetninger, for eksempel hva som er igjen i nettverkets quorum-kryssing selv etter å ha fjernet dårlige noder. For enkelhets skyld, la oss forlate disse antakelsene implisitt i resten av artikkelen).
Det kan virke urimelig å forvente at en pålitelig quorum-kryssing er mulig i et nettverk av uavhengige noder. Men det er to grunner til at det er slik.
Den første grunnen er eksistensen av Internett i seg selv. Internett er et perfekt eksempel på et nettverk av uavhengige noder med kryssende quorumer. De fleste noder på Internett kobles til bare noen få andre lokale noder, men disse små settene overlapper nok til at hver node kan nås fra annenhver node langs en eller annen rute.
Den andre grunnen er spesifikk for Stellar-betalingsnettverket (den vanligste bruken av SCP). Hvert aktiva på Stellar-nettverket har en utsteder, og Stellars retningslinjer krever at hver utsteder utpeker en eller flere noder på nettverket for å behandle innløsningsforespørsler. Det er i din interesse å direkte eller indirekte inkludere disse nodene i quorumsstykker for hver eiendel du er interessert i. Quorum for alle noder som er interessert i en gitt eiendel vil da overlappe minst ved disse innløsningsnodene. Noder som er interessert i flere eiendeler vil inkludere alle innløsningsnoder til de respektive utstedere i deres quorumsslicer, og de vil søke å slå alle eiendeler sammen. I tillegg kommer eventuelle eiendeler som ikke er knyttet på denne måten til andre på nettverket, og skal ikke kobles til - dette er utformet slik at det ikke er quorum-overlapping for dette nettverket (for eksempel vil banker fra dollarsonen noen ganger handle med banker fra eurosonen og banker fra pesosonen, så de er på samme nettverk, men ingen av dem bryr seg om det separate nettverket av barn som selger baseballkort).
Selvfølgelig ожидание quorum crossing er det ikke garanti. Andre bysantinske avtalesystemer skylder mye av sin kompleksitet garantien om quorum. En viktig nyvinning av SCP er at den fjerner ansvaret for å opprette beslutningsdyktighet fra selve konsensusalgoritmen og bringer den til søknadsnivået. Selv om føderert stemmegivning er generell nok til å stemme om ethvert spørsmål, avhenger dens pålitelighet faktisk kritisk av den bredere betydningen av disse betydningene. Noen hypotetiske bruksområder er kanskje ikke like gunstige for å skape godt sammenkoblede nettverk som andre.
Stemmegivning, aksept og bekreftelse
I en føderert avstemningsrunde begynner en node valgfritt å stemme for en verdi V. Dette betyr å kringkaste en melding til nettverket: «Jeg er node N, mine quorumsstykker er Q, og jeg stemmer på V.» Når en node stemmer på denne måten, lover den at den aldri har stemt mot V og aldri vil.
I peer-to-peer-sendinger ser hver node hvordan de andre stemmer. Når en node har samlet nok av disse meldingene, kan den spore quorumsstykker og prøve å finne quorumer. Hvis han ser et quorum av jevnaldrende som også stemmer på V, kan han gå videre til adopsjon V og kringkast denne nye meldingen til nettverket: "Jeg er node N, mine quorumsstykker er Q, og jeg aksepterer V." Aksept gir en sterkere garanti enn enkel stemmegivning. Når en node stemmer på V, kan den aldri stemme på andre alternativer. Men hvis en node aksepterer V, vil ingen node på nettverket noen gang godta det andre alternativet (setning 8 i SCP whitepaper beviser dette).
Selvfølgelig er det stor sannsynlighet for at det ikke umiddelbart vil være et quorum av noder som stemmer overens med V. Andre noder kan stemme for andre verdier. Men det er en annen måte for en node å gå fra enkel stemmegivning til aksept. N kan godta en annen verdi for W, selv om han ikke stemte for det, og selv om han ikke er beslutningsdyktig for det. For å bestemme deg for å endre stemmen din, bare se blokkeringssett noder som har akseptert W. Et blokkeringssett er én node fra hver av quorumssnittene N. Som navnet antyder, kan det blokkere noen annen betydning. Hvis alle noder i et slikt sett aksepterer W, vil det (ved teorem 8) aldri være mulig å danne et quorum som har en annen verdi, og derfor er det også trygt for N å akseptere W.
Node N med tre quorumsskiver.
BDF er et blokkeringssett for N: det inkluderer en node fra hver av skivene til N.
BE er også et blokkeringssett for N fordi E vises i to skiver av N.
Men blokkeringssettet er ikke beslutningsdyktig. Det ville være for enkelt å lure node N til å akseptere ønsket verdi hvis det var nok å hacke bare én node i hver av skivene av N. Derfor er det ikke slutten på avstemningen å akseptere verdien. I stedet må N bekrefte verdien, det vil si se et quorum av noder som godtar den. Hvis det kommer så langt, vil, som SCP-whitepaperen beviser (i teorem 11), også resten av nettverket til slutt bekrefte den samme verdien, så N vil avslutte den fødererte avstemningen med en viss verdi som resultat.
Federert stemmegivning.
Prosessen med stemmegivning, aksept og bekreftelse utgjør en hel runde med føderert avstemning. Stellar-konsensusprotokollen kombinerer mange av disse rundene for å skape et komplett konsensussystem.
Stellar Consensus Protocol
De to viktigste egenskapene til et konsensussystem er − sikkerhet и overlevelsesevne. En konsensusalgoritme er "trygg" hvis den aldri kan gi forskjellige resultater til forskjellige deltakere (Bobs kopi av historien vil aldri motsi Carol). "Livability" betyr at algoritmen alltid vil produsere et resultat, det vil si at den ikke vil sette seg fast.
Beskrevet føderal stemmeprosedyre sikker i den forstand at hvis en node bekrefter verdien til V, vil ingen annen node bekrefte den andre verdien. Men "vil ikke bekrefte en annen mening" betyr ikke at det nødvendigvis vil bekrefte noe. Deltakerne kan stemme på så mange forskjellige verdier at ingenting når akseptterskelen. Dette betyr at i føderal stemmegivning er det nei overlevelsesevne.
Stellar-konsensusprotokollen bruker føderert stemmegivning på en måte som sikrer både sikkerhet og overlevelse. (SCPs sikkerhets- og overlevelsesgarantier har en teoretisk grense. Designet velger en veldig sterk sikkerhetsgaranti, som ofrer en liten overlevelsesreduksjon, men gitt nok tid er det høyst sannsynlig at konsensus oppnås.) I et nøtteskall er ideen å ha flere fødererte stemmer på flere verdier til en av dem kommer seg gjennom alle SCP-stemmefasene beskrevet nedenfor.
Verdiene som SCP søker konsensus om kan være transaksjonshistorikk eller en lunsjbestilling eller noe annet, men det er viktig å merke seg at dette ikke er verdiene som er akseptert eller bekreftet. I stedet skjer føderal stemmegivning iht uttalelser om disse verdiene.
De første rundene med føderal avstemning finner sted kl nominasjonsstadiet (nominasjonsfasen), på et sett med utsagn som "Jeg nominerer V," kanskje for mange forskjellige verdier av V. Hensikten med nominasjonen er å finne en eller flere utsagn som går gjennom aksept og bekreftelse.
Etter å ha funnet kontrollerbare kandidater, går SCP videre til avstemningsfasen, hvor målet er å finne en viss bulletin (det vil si en beholder for den foreslåtte verdien) og et quorum som kan erklære begå for det (forplikte seg). Hvis et quorum forplikter seg til en stemmeseddel, aksepteres verdien som konsensus. Men før en node kan stemme på en stemmeseddel, må den først bekreftes kansellering alle stemmesedler med lavere tellerverdi. Disse trinnene – kansellering av stemmesedler for å finne en som kan begås – involverer flere runder med føderert avstemning om flere stemmesedler.
De følgende avsnittene beskriver nominasjon og stemmegivning mer detaljert.
Nominasjon
I begynnelsen av nominasjonsfasen kan hver node spontant velge en verdi for V og stemme på utsagnet "Jeg nominerer V." Målet på dette stadiet er å bekrefte nominasjonen av en eller annen verdi gjennom en føderert avstemning.
Kanskje nok noder stemmer på tilstrekkelig forskjellige forslag til at ingen nominasjon kan nå akseptterskelen. Derfor, i tillegg til å kringkaste sine egne nominasjonsstemmer, "reflekterer" noder nominasjonene til jevnaldrende. Ekko betyr at hvis en node stemmer for nominasjon V, men ser en melding fra en nabo som stemmer for nominasjon W, vil den nå stemme for både V og W. (Ikke alle likemannsstemmer gjentas under nominasjonen fordi dette kan føre til en eksplosjon på forskjellige nominerte. SCP inkluderer en mekanisme for å regulere disse stemmene. Kort sagt er det en formel for å bestemme "prioriteten" til en jevnaldrende fra en nodes synspunkt, og bare stemmene til høyprioriterte noder reflekteres. Jo lengre nominasjonen er tar, jo lavere terskelen er, slik at noden utvider settet med jevnaldrende hvis stemmer den vil reflektere. Prioritetsformelen inkluderer spornummeret som en av inngangene, så en høyprioritet peer for ett slot kan være en lavprioritet peer for en annen, og omvendt).
Konseptuelt er nominasjonen parallell, både V og W er separate føderale stemmer, hver enkelt i stand til å oppnå aksept eller bekreftelse. I praksis pakker SCP-protokollmeldinger disse individuelle stemmene sammen.
Selv om det å stemme for Vs nominasjon er et løfte om aldri å stemme mot Vs nominasjon, er det på søknadsnivå – i dette tilfellet SCP – det avgjøres hva «mot» betyr. SCP ser ikke et utsagn som motsier «Jeg nominerer X»-stemmen, det vil si at det ikke er noen «Jeg er imot å nominere X»-melding, så noden kan stemme for å nominere alle verdier. Mange av disse nominasjonene vil ikke gå noe sted, men til slutt vil noden kunne akseptere eller bekrefte en eller flere verdier. Når en nominert er bekreftet, blir han det kandidat.
SCP-nominasjon ved hjelp av føderert stemmegivning. Det kan være mange "B"-verdier fremsatt av jevnaldrende og "reflektert" av noden.
Nominasjoner kan resultere i flere bekreftede kandidater. Derfor krever SCP at applikasjonslaget gir en metode for å kombinere kandidatene til en sammensatte (sammensatte). Sammenføyningsmetoden kan være hva som helst. Hovedsaken er at hvis denne metoden er deterministisk, vil hver node kombinere de samme kandidatene. I et lunsjstemmesystem kan «forening» ganske enkelt bety å avvise en av to kandidater. (Men på en deterministisk måte: hver node må velge samme verdi for å tilbakestille. For eksempel det tidligere valget i alfabetisk rekkefølge). I betalingsnettverket Stellar, hvor det stemmes over transaksjonshistorikk, innebærer sammenslåing av to foreslåtte nominerte å slå sammen transaksjonene de inneholder og det siste av deres to tidsstempler.
SCP-hvitboken beviser (setning 12) at ved slutten av utvidelsesfasen konvergerer nettverket til slutt til en enkelt kompositt. Men det er et problem: forent stemmegivning er en asynkron protokoll (som SCP). Noder er med andre ord ikke koordinert etter tid, men bare av meldingene de sender. Fra nodens synspunkt er det uklart når endte utvidelsesfasen. Og selv om alle noder til slutt kommer til den samme kompositten, kan de ta forskjellige ruter underveis, skape forskjellige sammensatte kandidater underveis, og kan aldri fortelle hvilken som er den endelige.
Men det er normalt. Nominering er bare forberedelse. Det viktigste er å begrense antall kandidater for å oppnå konsensus, som oppstår i prosessen stiller til valg (avstemning).
Løping
Bulletin er et par , hvor telleren er et heltall som starter på 1 og verdien er en kandidat fra nominasjonsstadiet. Dette kan være en nodes egen kandidat eller en nabonodes kandidat akseptert av den noden. Grovt sett involverer en stemmeseddel gjentatte forsøk på å tvinge nettverket til å oppnå konsensus om en kandidat på en eller annen stemmeseddel ved å holde potensielt mange fødererte stemmer på stemmeseddelerklæringer. Tellere på stemmesedlene holder oversikt over forsøk som gjøres, og stemmesedler med høyere antall har forrang fremfor stemmesedler med lavere antall. Hvis nyhetsbrevet blir sittende fast, begynner en ny avstemning, nå på stemmeseddelen .
Det er viktig å skille mellom som betyr (for eksempel, hva bør lunsjbestillingen være: pizza eller salater), nyhetsbrev (motverdipar) og uttalelser om stemmesedler. SCP-runden inkluderer flere runder med føderal avstemning, spesielt på følgende uttalelser:
- "Jeg er klar til å begå stemmeseddel B" og
- "Jeg kunngjør forpliktelsen til stemmeseddel B"
Fra en gitt nodes perspektiv oppnås konsensus når den finner en stemmeseddel B som den kan bekrefte (det vil si finne et quorum som godtar) utsagnet "Jeg forplikter stemmeseddel B." Fra dette tidspunktet er det trygt å handle på verdien spesifisert i B - for eksempel å legge inn denne bestillingen til lunsj. Det kalles eksternalisering betydninger. Når aksept av stemmeseddelen er bekreftet, kan en node være sikker på at enhver annen node har eksternalisert samme verdi eller vil gjøre det i fremtiden.
Selv om mange forbundsstemmer konseptuelt gjennomføres på krav for mange forskjellige stemmesedler, utveksler de ikke så mange meldinger fordi hver melding innkapsler et antall stemmesedler. En melding fremmer dermed staten med mange fødererte stemmer på en gang, for eksempel: «Jeg aksepterer forpliktende stemmesedler som strekker seg fra før "
Hva betyr begrepene "forberedt" og "forplikte"?
En node stemmer for å foreta en stemmeseddel når den er sikker på at andre noder ikke vil foreta stemmesedler med andre verdier. Overbevisende dette er hensikten med å utarbeide søknaden. En stemme som sier "Jeg er klar til å forplikte stemmeseddel B" er et løfte om å aldri foreta en stemmeseddel som er mindre enn B, dvs. med et mindre antall (SCP krever at verdiene i stemmesedlene er i en bestemt rekkefølge. Derfor nyhetsbrev mindre , hvis N1
Hvorfor betyr "Jeg er klar til å foreta stemmeseddel B" "Jeg lover å aldri foreta stemmesedler som er mindre enn B"? Fordi SCP definerer abort som det motsatte av commit. En avstemning for å forberede en stemmeseddel innebærer også en avstemning for å diskvalifisere noen andre stemmesedler, og som vi diskuterte tidligere, er det å stemme for én ting et løfte om å aldri stemme mot det.
Før en commit kringkastes, må en node først finne en bulletin som den kan bekrefte som forberedt. Med andre ord utfører den en føderert avstemning om emnet "Jeg er klar til å forplikte stemmeseddel B," muligens på mange forskjellige stemmesedler, inntil den finner en som godtar et beslutningsdyktig.
Hvor kommer stemmesedlene fra for å forberede avstemningen? Først sender noden forberedelser til å stemme på <1,C>, der C er den sammensatte kandidaten som ble produsert på nominasjonsstadiet. Men selv etter at forberedelsene til avstemningen begynner, kan nominasjoner føre til at flere kandidater ser ut til å bli nye stemmesedler. I mellomtiden kan jevnaldrende ha forskjellige kandidater, og de kan danne et blokkeringssett som godtar "Jeg er klar til å foreta B2-stemmeseddelen" som vil overbevise noden om å godta den også. Til slutt er det en timeout-mekanisme som genererer nye runder med forbundsstemmegivning på nye stemmesedler med høyere antall dersom gjeldende stemmesedler sitter fast.
Så snart noden finner en stemmeseddel B som den kan bekrefte at den er forberedt, sender den en ny melding "Bekreft stemmeseddel B." Denne avstemningen forteller jevnaldrende at noden aldri vil gi opp B. Faktisk, hvis B er en stemmeseddel , deretter "Begi stemmeseddel " betyr det ubetingede samtykke til å stemme for beredskapen til hver stemmeseddel fra til <∞, s>. Denne ekstra verdien hjelper andre jevnaldrende å ta igjen den forpliktende peeren hvis de fortsatt er i tidligere stadier av protokollen.
På dette stadiet er det verdt å understreke nok en gang at dette er asynkrone protokoller. Bare fordi en node sender oppstemmer for en forpliktelse, betyr det ikke at jevnaldrende også gjør det. Noen av dem kan fortsatt stemme over uttalelser som forberedelse til avstemning, andre kan allerede ha eksternalisert meningen. SCP forklarer hvordan en node skal behandle hver type peer-melding uavhengig av fase.
Hvis meldingen "Jeg har annonsert en forpliktelse » kan ikke mottas eller bekreftes, det vil si sannsynligheten for at meldingen blir akseptert eller bekreftet eller - eller i alle fall enhver stemmeseddel med verdien C, og ikke noen annen, siden noden allerede har lovet å aldri kansellere . Innen en node sender stemmer for en forpliktelse, vil den være C eller ingenting, avhengig av hvor langt konsensus går. Dette er imidlertid ennå ikke nok for at noden skal eksternalisere C. Noen bysantinske jevnaldrende (som utgjør mindre enn et quorum, basert på våre sikkerhetsforutsetninger) kan lyve til noden. Å akseptere og deretter bekrefte en eller annen stemmeseddel (eller utvalg av stemmesedler) er det som gir noden selvtilliten til å endelig eksternalisere C.
SCP-stemmegivning gjennom føderert stemmegivning. Ikke vist: Tidtakeren kan gå av når som helst, og øke tellingen på stemmeseddelen (og muligens produsere en ny sammensetning av ytterligere nominerte kandidater).
Og det er alt! Når nettverket har nådd enighet, er det klart til å gjøre det igjen og igjen. På Stellars betalingsnettverk skjer dette omtrent en gang hvert 5. sekund: en prestasjon som krever både sikkerheten og overlevelsesevnen garantert av SCP.
SCP kan oppnå dette ved å stole på flere runder med føderert stemmegivning. Federert stemmegivning er muliggjort av konseptet med quorumssnitt: sett med jevnaldrende som hver node har bestemt seg for å stole på som en del av sitt (subjektive) quorum. Denne konfigurasjonen betyr at konsensus kan oppnås selv i et nettverk med åpent medlemskap og bysantinsk bedrag.
Videre lesning
- Den originale SCP-hvitboken kan bli funnet Og utkast til spesifikasjoner for implementeringen.
- Den opprinnelige forfatteren av SCP-protokollen, David Mazier, forklarer det på en forenklet (men fortsatt teknisk) måte. .
- Du har kanskje blitt overrasket over å ikke finne begrepene "gruvedrift" eller "bevis på arbeid" i denne artikkelen. SCP bruker ikke disse metodene, men noen andre konsensusalgoritmer gjør det. Zane Witherspoon skrev tilgjengelig .
- et enkelt nettverk som når konsensus i en hel runde med SCP.
- For lesere som er interessert i SCP-implementeringer: se , brukt av Stellars betalingsnettverk, eller , som jeg skrev for en bedre forståelse av SCP.
Kilde: www.habr.com