Stellar-konsensusprotokollet beskrevs först av en vetenskaplig artikel David Mazieres 2015. Det är ett "federativt system för bysantinsk överenskommelse" som gör det möjligt för decentraliserade datanätverk utan ledare att effektivt nå enighet om en viss lösning. Betalningsnätverket Stellar använder Stellar Consensus Protocol (SCP) för att hålla en samstämmig transaktionshistorik som alla deltagare ser.

Det anses att konsensusprotokoll är svåra att förstå. SCP är enklare än de flesta av dem men delar ändå detta rykte – delvis på grund av den felaktiga idén att "federativ omröstning", som den första delen av den vetenskapliga artikeln ägnar sig åt, är SCP. Men så är det inte! Det är bara en viktig byggsten som i den andra delen av artikeln används för att skapa det faktiska Stellar konsensusprotokollet.

I denna artikel kommer vi kortfattat att förklara vad ett "överenkommelse-system" är, vad som kan göra det "bysantinskt" och varför man bör göra ett bysantinskt system "federativt". Vi kommer sedan att förklara den federativa omröstningsproceduren som beskrivs i artikeln om SCP och slutligen förklara själva SCP-protokollet.

Överenskommelse-system

Ett överenskommelse-system gör det möjligt för en grupp deltagare att enas om ett visst ämne, till exempel vad man ska beställa till lunch.

Vi på Interstellar har implementerat vårt eget system för lunchöverenskommelse: vi beställer det som vår operativa chef John säger. Det är ett enkelt och effektivt överenskommelse-system. Vi litar alla på John och tror att han varje dag kommer att hitta något intressant och näringsrikt.

Men vad händer om John missbrukar vårt förtroende? Han kan ensidigt besluta att vi alla ska bli veganer. Inom en vecka eller två kommer vi sannolikt att avsätta honom och överföra makten till Elizabeth. Men tänk om hon älskar avokado med ansjovis och tycker att alla borde bli sådana. Makten korrumperar. Därför är det bättre att hitta någon mer demokratisk metod: något sätt att se till att olika preferenser blir beaktade, samtidigt som en snabb och tydlig lösning säkerställs så att ingen beställer lunch eller fem personer gör olika beställningar, eller att diskussionen drar ut på tiden till kvällen.

Det verkar vara en enkel lösning: att hålla en omröstning! Men det är en bedräglig uppfattning. Vem ska samla in röstsedlar och rapportera resultaten? Och varför ska de andra tro på vad han säger? Kanske kan vi först rösta på en ledare som vi litar på för att leda omröstningen – men vem ska leda detta första omröstning? Vad händer om vi inte kan enas om en ledare? Eller om vi enas, men den ledaren sitter fast i ett möte eller blir sjuk?

Liknande problem uppstår i distribuerade datanätverk. Alla deltagare eller noder måste enas om någon form av beslut, till exempel vems tur det är att uppdatera en gemensam fil eller hämta en uppgift från en kö. I ett kryptovalutanätverk måste noderna gång på gång välja hur den fullständiga historien ser ut bland flera möjliga versioner, som ibland konfliktar. Detta nätverksbeslut garanterar för mottagaren att myntet är (a) giltigt (inte falskt) och (b) ännu inte använt någon annanstans. Det garanterar också att han kan spendera mynten i framtiden, eftersom den nya mottagaren kommer att ha samma garantier av samma skäl.

Vilken som helst beslutssystem i ett distribuerat databehandlingsnätverk måste vara felfritt: det ska ge konsekventa resultat trots fel som långsamma kommunikationslinjer, icke-reagerande noder och felaktig ordning av meddelanden. Byzantinska överenskommelser är dessutom motståndskraftiga mot "byzantinska" fel: noder som ger felaktig information, antingen på grund av misstag eller i ett avsiktligt försök att undergräva systemet eller få någon fördel. "Byzantinsk" felfrihet – förmågan att lita på en gruppbeslut, även när vissa medlemmar i gruppen kan ljuga eller avvika från beslutsreglerna – har fått sitt namn från berättelsen om generalerna i det Byzantinska imperiet, som försökte koordinera en attack. Ett bra beskriving av Anthony Stevens.

Låt oss betrakta kryptovalutaägaren Alice, som måste välja mellan att köpa god glass från Bob eller betala sin skuld till Carol. Kanske vill Alice betala båda samtidigt, genom att bedrägligt spendera samma mynt. För att göra detta måste hon övertyga Bobs dator om att myntet aldrig har betalats till Carol, och övertyga Carols dator om att myntet aldrig har betalats till Bob. Det byzantinska konsensusprotokollet gör detta i praktiken omöjligt, genom att använda en form av majoritetsregel som kallas kvorum. En nod i ett sådant nätverk avstår från att gå vidare till en specifik version av historien, tills den ser att ett tillräckligt antal jämställda noder – kvorum – är eniga om att göra så. När detta inträffar kommer de att bilda en tillräckligt stor valblock för att tvinga de återstående noderna i nätverket att acceptera deras beslut. Alice kan få vissa noder att ljuga å hennes vägnar, men om nätverket är tillräckligt stort kommer hennes försök att kvävas av rösterna från de ärliga noderna.

Hur många noder krävs för ett kvorum? Åtminstone en majoritet, närmare bestämt en kvalificerad majoritet för att hantera fel och bedrägeri. Men för att räkna ut majoriteten måste man veta det totala antalet deltagare. På kontoret Interstellar eller i distriktsval är dessa siffror lätta att ta reda på. Men om din grupp är ett svagt definierat nätverk där noder kan gå in och ut efter eget val utan samordning med en central myndighet, så krävs det en federativ byzantinsk konsensusprotokoll som kan fastställa kvorum inte från en förutbestämd lista av noder, utan dynamiskt, från en ständigt föränderlig och ofrånkomligt ofullständig ögonblicksbild av noder vid ett visst tillfälle.

Det kan verka omöjligt att skapa ett kvorum ur ett sikt av en enda nod i ett stort nätverk, men det är möjligt. Ett sådant kvorum kan till och med garantera resultaten av decentraliserad röstning. Ett tekniskt dokument, SCP, visar hur detta kan göras med en procedur som kallas federerad röstning.

För de otåliga

Den resterande delen av artikeln beskriver mer detaljerat den federerade röstningen och Stellar-konsensusprotokollet. Om du inte är intresserad av detaljerna, här är en allmän översikt över processen.

1. Noder genomför federala röstningsrundor för 'nomineringarna'. En federativ röstningsrunda innebär:
   • Noden röstar för ett påstående, till exempel 'Jag föreslår värdet V';
   • Noden lyssnar på röster från deltagarna tills den hittar någon som kan 'acceptera';
   • Noden letar efter ett 'kvorum' för detta påstående. Kvorum 'bekräftar' nominanten.
2. När noden kan bekräfta en eller flera kandidater försöker den att 'förbereda' en 'röstsedel' genom flera rundor av federativ röstning.
3. När noden är redo att kontrollera röstsedelns beredskap försöker den att åta sig den med hjälp av ytterligare rundor av federativ röstning.
4. När noden kan bekräfta engagemanget av röstsedeln kan den 'exteralisera' värdet av denna röstsedel, genom att använda den som resultat av konsensus.

Dessa steg inkluderar flera rundor av federativ röstning, som tillsammans utgör en runda av SCP. Låt oss titta närmare på vad som händer i varje steg.

Federativ röstning

Federativ röstning är en procedur för att fastställa om nätverket kan enas om ett förslag. I röstningsrundan måste varje nod välja ett av flera potentiellt möjliga värden. Den kan inte göra detta förrän den är säker på att andra noder i nätverket inte väljer ett annat resultat. För att vara säkra på detta, utbyter noderna en ström av meddelanden fram och tillbaka så att varje av, att kvorum noder accepterar samma beslutet. Övriga delar av detta avsnitt förklarar villkoren i detta påstående och hur hela proceduren går till.

Kvorum och kvorumskivor

Låt oss börja med att definiera kvorum. Som vi diskuterade ovan, i ett decentraliserat nätverk med dynamiskt medlemskap, är det omöjligt att på förhand veta antalet noder och därmed hur många som behövs för majoritet. Federativ röstning löser detta problem genom att introducera en ny idé kvorumskiva (quorum slice): en liten uppsättning av likvärdiga noder som noden litar på för att förmedla information om röstningsstatus till den resterande delen av nätverket. Varje nod definierar sin egen kvorumskiva (medlem i denna blir den faktiskt).

Formandet av ett kvorum börjar med att skära kvorum. För varje nod läggs noderna i dess snitt till. Därefter läggs medlemmarna i skärningen till. dessa noder och så vidare. Efterhand dyker fler noder upp som du inte kan lägga till eftersom de redan ingår i snittet. När det inte finns några nya noder kvar att lägga till, avslutas processen: vi har bildat ett kvorum genom "transitiv stängning" av det ursprungliga nodens kvorumsskärning.

För att hitta kvorum från en given nod …

… lägger vi till medlemmarna i dess snitt …

… sedan lägger vi till medlemmarna i snitt av dessa noder.

Vi fortsätter tills det inte finns några fler noder att lägga till.

Det finns inga fler noder att lägga till. Detta är ett kvorum.

Egentligen kan varje nod ingå i mer än ett snitt. För att bilda ett kvorum, välj bara ett av snitten och lägg till medlemmarna; välj sedan vilket snitt som helst för var och en av medlemmarna och lägg till medlemmarna. detta snitt och så vidare. Det betyder att varje nod är medlem i ett antal möjliga kvorum.

Välj bara ett snitt av kvorum vid varje steg.

Ett möjligt kvorum. Eller ett alternativ …

… vi väljer andra snitt …

…(när det är möjligt)…

… skapar ett annat kvorum.

Hur får en nod veta i vilka snitt de andra noderna ingår? På samma sätt som annan information om andra noder: från de sändningar som varje nod överför i nätverket när dess röstningsstatus ändras. Varje sändning innehåller information om snitt av den sändande noden. Den tekniska dokumentationen SCP specificerar inte kommunikationsmekanismen. Implementationer använder vanligtvis gossip-protokollet för garanterad överföring av meddelanden över hela nätverket.

Vi påminner om att i det icke-federativa bysantinska konsensus-systemet definieras kvorum som en majoritet av alla noder. Det bysantinska konsensus-systemet är utformat med frågan i åtanke: hur många ohederliga noder kan systemet tolerera? I ett system med N noder, som är konstruerat för att överleva vid f misslyckanden (bedrägerier), måste en nod kunna uppnå framsteg genom att få svar från N−f peers, eftersom f av dem kanske inte fungerar. Men efter att ha fått svar från N−f peers, kan man anta att alla f peers (från vilka noden inte fick svar) faktiskt är ärliga. Således är f av N−f peers (från vilka svar har mottagits) skadliga. För att noder ska nå ett gemensamt konsensus, måste en majoritet av de återstående noderna vara ärliga, vilket innebär att vi behöver att N−f är större än 2f eller N > 3f. Således kommer ett system som är designat för att överleva vid f misslyckanden vanligtvis att ha totalt N=3f+1 noder och en kvorumstorlek på 2f+1. När ett förslag passerar kvorumtröskeln övertygas de övriga medlemmarna i nätverket om att alla konkurrerande förslag kommer att misslyckas. Så nätverket konvergerar mot resultatet.

Men i det federativa bysantinska konsensus-systemet kan det inte bara finnas någon majoritet (eftersom ingen vet den totala storleken på nätverket), utan vuxfärsen av majoritet är helt värdelös! Om medlemskap i systemet är öppet, så kan någon få en majoritet bara genom att genomföra en så kallad Sybil-attack: genom att upprepade gånger gå med i nätverket via flera noder. Så varför kan det transitiva stängandet av skärningen kallas kvorum, och hur kan det undertrycka konkurrerande förslag?

Tekniskt sett, på inget sätt! Föreställ dig ett nätverk av sex noder, där två grupper av tre är isolerade i varandras kvorumskärningar. Den första undergruppen kan fatta ett beslut som den andra aldrig kommer att höra talas om, och vice versa. För detta nätverk finns det inget sätt att uppnå konsensus (förutom av en tillfällighet).

Därför kräver SCP att för federativ röstning (och för att tillämpa viktiga teoremer i artikeln) måste nätverket ha en egenskap som kallas skärning av kvorum. I nätverk med den här egenskapen överlappar alltid två quorum som kan byggas över minst en nod. För att avgöra det dominerande sentimentet i nätverket är detta lika bra som att ha majoriteten. Intuitivt betyder det att om något quorum håller med om påstående X, så kan inget annat quorum någonsin hålla med om något annat, eftersom det nödvändigtvis kommer att inkludera en nod från det första quorum som redan har röstat för X.

Om det finns överlappningar mellan quorum i nätverket…

…då kommer varje två quorum som du kan bygga…

…alltid att överlappa.

(Naturligtvis kan överlappande noder visa sig vara byzantinskt bedrägliga eller dåliga på andra sätt. I så fall hjälper överlappningen mellan quorum inte nätverket att enas överhuvudtaget. Av denna anledning baseras många resultat i den tekniska SCP-dokumentationen på tydligt uttalade antaganden, som att det finns kvar överlappande quorum i nätverket även efter borttagning av dåliga noder. För enkelhetens skull låter vi dessa antaganden vara underförstådda under resten av artikeln).

Det kan verka orimligt att förvänta sig att det ska finnas pålitlig överlappning mellan quorum i ett nätverk av oberoende noder. Men det finns två skäl till varför det är så.

Det första skälet är existensen av själva internet. Internet är ett perfekt exempel på ett nätverk av oberoende noder med överlappande quorum. De flesta noder i internet kopplas endast till några få andra lokala noder, men dessa små mängder överlappar tillräckligt för att varje nod ska vara tillgänglig från varje annan nod via en eller annan rutt.

Den andra anledningen är specifik för betalningsnätverket Stellar (den mest utbredda användningen av SCP). Varje tillgång i Stellar-nätverket har en utfärdare, och Stellar-rekommendationerna kräver att varje utfärdare utser en eller flera noder i nätverket för att hantera inlösenförfrågningar. Det ligger i ditt intresse att direkt eller indirekt inkludera dessa noder i kvorumskurvorna för varje tillgång som intresserar dig. Då kommer kvorum för alla noder som är intresserade av den aktuella tillgången att överlappa sig åtminstone i dessa inlösennoder. Noder som är intresserade av flera tillgångar kommer att inkludera i sina kvorumskurvor alla inlösennoder för de aktuella utfärdarna, och de kommer att sträva efter att centralisera alla tillgångar. Dessutom, alla tillgångar som inte är kopplade på det sättet till andra i nätverket, ska inte vara kopplade — det är utformat så att det inte finns något överlapp mellan kvorum i detta nätverk (till exempel vill banker i dollarzonen ibland handla med banker i eurozonen och banker i pesozonen, så de är i ett och samma nätverk, men ingen av dem bryr sig om ett separat nätverk av barn som handlar med baseballkort).

Självklart, är förväntningen av överlappande kvorum inte en garanti. Andra byzantinska konsensussystem har mycket att tacka sin komplexitet för att säkerställa kvorum. En viktig innovation med SCP är att det avlägsnar ansvaret för att skapa kvorum frän konsensusalgoritmen och flyttar det till applikationsnivån. Således, även om federativ röstning är ganska allmän för röstning i vilka frågor som helst, beror dess tillförlitlighet i verkligheten kritiskt på en bredare förståelse av dessa värden. Vissa hypotetiska användningsområden kan visa sig vara mindre bekväma för att skapa väl sammanlänkade nätverk än andra.

Röstning, antagande och bekräftelse

I rundan av federativ röstning börjar en nod valfritt att rösta för ett visst värde V. Detta innebär att sända ett meddelande i nätverket: "Jag är nod N, mina kvorumskurvor Q, och jag röstar för V". När en nod röstar på detta sätt lovar den att den aldrig har röstat emot V och aldrig kommer att göra det.

I sändningar från peer-noder ser varje nod hur andra röstar. Så snart en nod samlar tillräckligt med sådana meddelanden kan den spåra urval av kvorum och försöka hitta kvorum. Om den ser ett kvorum av peers som också röstar för V kan den gå vidare till antagande av V och sända detta nya meddelande till nätverket: "Jag är nod N, mina kvorumskivor Q, och jag accepterar V". Antagande ger en starkare garanti än enkel röstning. När en nod röstar för V kan den aldrig rösta för andra alternativ. Men om en nod accepterar V, kommer ingen nod i nätverket någonsin att acceptera ett annat alternativ (teorem 8 i det tekniska dokumentet SCP bevisar detta).

Självklart är chansen hög att det inte omedelbart kommer att finnas ett kvorum av noder som håller med V. Andra noder kan rösta för andra värden. Men för noden finns det också ett annat sätt att gå från enkel röstning till antagande. N kan acceptera ett annat värde W, även om den inte har röstat för det, och även om den inte ser något kvorum för det. För att ändra sin röst räcker det med att se ett blockerande mängd noder som har antagit W. Det blockerande mängden är en nod från varje urval av kvorum N. Som namnet antyder är det kapabelt att blockera alla andra värden. Om alla noder i en sådan mängd accepterar W, kommer det (enligt teorem 8) aldrig att kunna bildas ett kvorum som accepterar ett annat värde, och därför är det också säkert för N att acceptera W.

Nod N med tre kvorumskivor.

B-D-F är ett blockerande mängd för N: det inkluderar en nod från varje urval av N.

B-E är också ett blockerande mängd för N, eftersom E förekommer i två urval av N.

Men det blockerande mängden är inte ett kvorum. Det skulle vara för lätt att lura nod N att acceptera rätt värde om det räckte med att hacka en nod i varje urval av N. Så att acceptera ett värde är ännu inte slutet på röstningen. Istället måste N bekräfta värdet, det vill säga se ett kvorum av noder som accepterar det. Om den når så långt, bevisar det tekniska dokumentet SCP (i teorem 11), att resten av nätverket också slutligen kommer att bekräfta samma värde, så N avslutar den federativa röstningen med ett visst värde som resultat.

Federativ röstning.

Röstningsprocessen, beslutet och bekräftelsen utgör en fullständig runda av federativ röstning. Stellar-konsensusprotokollet samlar flera sådana rundor för att skapa ett fullständigt konsensus-system.

Stellar-konsensusprotokollet

Två av de mest viktiga egenskaperna hos ett konsensus-system är säkerhet och resilience. En konsensus-algoritm är "säker" om den aldrig kan ge olika resultat till olika deltagare (Bobs historik kommer aldrig att motsäga Carols). "Resilience" innebär att algoritmen alltid ger ett resultat, det vill säga den fastnar aldrig.

Den beskrivna proceduren för federativ röstning är säker i den meningen att om en nod bekräftar värdet V, så kommer ingen annan nod att bekräfta ett annat värde. Men "inte bekräfta ett annat värde" innebär inte att den nödvändigtvis bekräftar något. Deltagarna kan rösta för så många olika värden att inget når tröskeln för godkännande. Detta innebär att det i den federativa röstningen saknas resilience.

Stellar-konsensusprotokollet använder federativ röstning på ett sätt som garanterar både säkerhet och resilience. (Säkerhets- och resilientgarantierna i SCP har en teoretisk gräns. Konstruktionen väljer en mycket stark säkerhetsgaranti, men offrar en liten del av resilienten, men med tillräcklig tid kommer konsensus med hög sannolikhet att uppnås). Sammanfattningsvis handlar idén om att genomföra flera federativa röstningar om flera värden, tills ett av dem passerar genom alla faser av SCP-röstning som beskrivs nedan.

De värden som SCP strävar efter att nå konsensus om kan vara historik av transaktioner eller en lunchbeställning, eller något annat, men det är viktigt att notera att detta inte är de värden som antas eller bekräftas. Istället sker den federativa röstningen om påståenden om dessa värden.

De första rundorna av den federativa röstningen äger rum i nomineringen (nomineringens fas), på en uppsättning påståenden som "Jag nominerar V", möjligtvis för många olika värden V. Målet med nomineringen är att hitta ett eller flera påståenden som går igenom godkännande och bekräftelse.

Efter att ha funnit bekräftade kandidater går SCP vidare till röstningssteget, där målet är att hitta någon röstsedel (det vill säga en behållare för det föreslagna värdet) och en kvorum som kan deklarera commit för det (commit). Om kvorum fattar beslut om röstsedeln, accepterar dess värde som konsensus. Men innan en nod kan rösta för att godkänna röstsedeln, måste den först bekräfta annullering av alla röstsedlar med ett lägre räknarvärde. Dessa steg – annullering av röstsedlar för att hitta den som kan bekräfta commit – inkluderar flera rundor av federativ röstning om flera påståenden om röstsedlar.

I de följande avsnitten beskrivs nominering och röstning i detalj.

Nominering

I början av nomineringssteget kan varje nod spontant välja värdet V och rösta för påståendet "Jag nominerar V". Målet i detta steg är att bekräfta nomineringen av något värde genom federativ röstning.

Det kan hända att tillräckligt många noder röstar för tillräckligt olika påståenden, och ingen nominering kan nå antagningsgränsen. Därför, förutom att sända sina egna nomineringar, "återspeglar" noder nomineringar från sina grannar. Återspegling (echo) betyder att om en nod röstar för nomineringen V, men ser ett meddelande från en granne som röstade för nomineringen W, så kommer den nu att rösta för både nomineringen V och W. (Inte alla röster från grannar återspeglas under nomineringen, eftersom detta kan leda till en explosion av olika kandidater. SCP inkluderar en mekanism för att reglera dessa röster. Kort sagt, det finns en formel för att bestämma "prioriteten" för en granne ur nodens perspektiv, och rösterna från endast högt prioriterade noder återspeglas. Ju längre nomineringen pågår, desto lägre blir tröskeln, så noden utvidgar uppsättningen grannar vars röster den kommer att återspegla. I prioriteringsformeln ingår slotnumret som en av indata, så en högt prioriterad grannnod för en slot kan vara lågt prioriterad för en annan, och vice versa).

Konceptuellt är det att föreslå både V och W parallellt separata federativa röster, där varje röst förmånsar att nå ett antagande eller godkännande. I praktiken packar SCP-protokollets meddelanden dessa separata röster tillsammans.

Även om röstandet för att föreslå V är ett löfte att aldrig rösta emot förslaget V, definieras vad "emot" betyder på applikationsnivå - i det här fallet SCP. SCP ser inget påstående som motsäger röstningen "Jag föreslår X", det vill säga det finns inget meddelande "Jag är emot att föreslå X", så noden kan rösta för att föreslå valfria värden. Många av dessa nomineringar leder ingenstans, men i slutändan kan noden acceptera eller bekräfta ett eller flera värden. När en nominerad har bekräftats, blir den en kandidat.

Föreslå SCP med federativ röstning. Det kan finnas många värden "B" föreslagna av jämlika noder och "återspeglade" av en nod.

Föreslagna kandidater kan leda till att flera bekräftade kandidater framträder. Därför kräver SCP att applikationsnivån tillhandahåller någon metod för att kombinera kandidater till en komposit (composite). Kombinationmetoden kan vara vilken som helst. Det viktigaste är att om denna metod är deterministisk, så kommer varje nod att kombinera samma kandidater. I en lunchröstningssystem kan "kombination" helt enkelt innebära att man avstår från en av de två kandidaterna. (Men på ett deterministiskt sätt: varje nod måste välja samma värde för att avbryta. Till exempel, en tidigare val i alfabetisk ordning). I Stellar betalningsnätverket, där röstandet om transaktionshistorik äger rum, innebär en sammanslagning av två föreslagna nomineringar en kombination av de transaktioner de innehåller och de senaste av deras två tidsstämplar.

Den tekniska beskrivningen av SCP bevisar (teorem 12), att vid slutet av föreslagningsfasen konvergerar nätverket slutligen till en komposit. Men det finns ett problem: federativ röstning är ett asynkront protokoll (precis som SCP). Med andra ord koordineras inte noderna tidsmässigt, utan bara genom de meddelanden de skickar. Från nodens synvinkel är det oklart när det avslutades utdragningsfas. Och även om alla noder i slutändan kommer att nå samma sammansättning, kan de välja olika vägar på denna väg och skapa olika sammanslagna kandidater längs vägen, och de kan aldrig säga vilken av dem som är den definitiva.

Men det är okej. Utdragning är bara förberedelse. Det viktigaste är att begränsa antalet kandidater för att nå konsensus, vilket sker under processen röstning (balloting).

Röstning

En röst är ett par , där counter är ett heltal som börjar på 1 och value är en kandidat från steg för utdragning. Det kan vara nodens egen kandidat eller en kandidat från en granndnod som denna nod har accepterat. Grovt sett görs flera försök under röstningen för att få nätverket att nå konsensus om en kandidat i en viss röstning genom att genomföra potentiellt många federerade valomröstningar om röstningsutlåtanden. Räknare i röstningar spårar gjorda försök, och röstningar med högre räknare har företräde framför röstningar med lägre räknare. Om rösten fastnar, påbörjas en ny omröstning, nu på rösten .

Det är viktigt att särskilja värden (till exempel vad beställning av lunch ska vara: pizza eller sallad), röster (par counter-value) och uttalandena om röster. SCP-omgången omfattar flera omgångar av federationröstning, särskilt om sådana uttalanden:

• «Jag är redo att bekräfta röstning B» och
• «Jag deklarerar bekräftelse av röstning B»

Ur denna nodes perspektiv uppnås konsensus när den hittar rösten B, för vilken den kan bekräfta (det vill säga hitta en kvorum som accepterar) uttalandet «Jag deklarerar bekräftelse av röstning B». Från den punkten kan man säkert agera på värdet angivet i B - till exempel, göra denna lunchbeställning. Detta kallas externalisering av värdet. När bekräftelse om godkännande av rösten har bekräftats kan noden vara säker på att vilken annan nod som helst har genomfört externaliseringen av samma värde eller kommer att göra det i framtiden.

Även om konceptuellt många federativa omröstningar genomförs baserat på utsagor om olika röstberättiganden, utbyter de inte så många meddelanden, eftersom varje meddelande inkapslar ett antal röstberättiganden. Ett meddelande främjar således tillståndet för många federativa omröstningar samtidigt, till exempel: "Jag accepterar röstberättiganden i intervallet från till ."

Vad betyder termerna "förberedd" (prepared) och "kommitté" (commit)?

Noden röstar för att godkänna röstberättigandet när den är övertygad om att andra noder inte kommer att godkänna röstberättiganden med andra värden. Övertygelsen om detta är målet med att förbereda statementet. En omröstning som säger: "Jag är redo att godkänna röstberättigandet B" är ett löfte om att aldrig godkänna ett röstberättigande med ett värde mindre än B, dvs. med en lägre räknare (SCP kräver att värdena i röstberättigandena har en bestämd ordning. Därför är röstberättigandet mindre än om N1<N2, och även om N1=N2 och V1<V2). Dessa mindre röstberättiganden "avbryts" (aborted) under den förberedande omröstningen, medan B anses vara "förberedd".

Varför betyder "Jag är redo att godkänna röstberättigandet B" "Jag lovar att aldrig tillåta godkännande av röstberättiganden mindre än B"? För att SCP definierar abort som motsatsen till commit. En omröstning för att förbereda röstberättigandet innebär också en omröstning för att avbryta vissa andra röstberättiganden, och som vi diskuterade tidigare, att rösta för något innebär ett löfte att aldrig rösta emot det.

Innan noden kan sända en godkännandeaktion måste den först hitta ett röstberättigande som den kan bekräfta som förberett. Med andra ord, den genomför en federativ omröstning på temat "Jag är redo att godkänna röstberättigandet B", möjligtvis för många olika röstberättiganden, tills den hittar ett som accepterar kvorum.

Varifrån kommer valsedlarna för röstningsförberedelser? Först sänder noden ut förberedelser för röstning för <1,C>, där C är en kompositkandidat som producerades på nomineringsteget. Men även efter att förberedelserna för röstningen har börjat kan nomineringen leda till nya kandidater som blir nya valsedlar. Under tiden kan deltagarna ha olika kandidater och de kan bilda en blockerande mängd som accepterar "Jag är redo att commit-a valsedel B2", vilket övertygar noden att också acceptera den. Slutligen finns det en timeoutmekanism som genererar nya omgångar av federerad röstning på nya valsedlar med högre räknare, om de aktuella valsedlarna har fastnat.

Så snart noden hittar valsedel B, som kan bekräftas som förberedd, sänder den ut ett nytt meddelande "Commit av valsedel B". Denna röstning meddelar deltagarna att noden aldrig kommer att avstå från B. Faktiskt, om B representerar valsedeln <N,C>, så betyder "Commit av valsedel <N,C>" ovillkorligt samtycke att rösta för beredskapen för varje valsedel från <N,C> till <∞, s>. Detta extra värde hjälper andra noder att hinna ikapp med deltagaren med commit, om de fortfarande är på tidigare steg i protokollet.

Vid detta steg är det värt att betona igen att detta är asynkrona protokoll. Bara för att en nod skickar röster för commit betyder det inte att dess kollegor också gör det. Vissa av dem kan fortfarande rösta på påståenden för röstningsförberedelser, medan andra kanske redan har externt värderat betydelsen. SCP förklarar hur en nod ska hantera varje typ av peer-to-peer-meddelande oavsett dess fas.

Om meddelandet "Jag meddelar kommittén <N,C>" inte kan accepteras eller bekräftas, finns det en möjlighet att meddelandet <N+1, C> eller <N+2, C> accepteras eller bekräftas — eller, i alla fall, vilket som helst meddelande med värdet C, och inte något annat, eftersom noden redan har lovat att aldrig avbryta <N,C>. Vid den tidpunkt då noden sänder röster för kommittén, kommer det att vara C eller ingenting, beroende på hur långt konsensus går. Men detta är inte tillräckligt för noden att externt bekräfta C. Vissa byzantinska pizzer (som utgör mindre än quorum, baserat på våra antaganden om säkerhet) kan ljuga för noden. Att acceptera och sedan bekräfta ett visst meddelande (eller en rad meddelanden) — det är vad som ger noden förtroende för slutligen att externalisera C.

Röstning av SCP genom federativ röstning. Ej visat: när som helst kan en timer aktiveras, vilket ökar räknaren i omröstningen (och eventuellt skapa en ny sammansättning av ytterligare föreslagna kandidater).

Och det är allt! Så snart nätverket har nått konsensus är det redo att göra det igen och igen. I Stellar betalningsnätverket sker detta ungefär var 5:e sekund: en prestation som kräver både säkerhet och livskraft, garanterad av SCP.

SCP kan uppnå detta genom att förlita sig på flera omgångar av federativ röstning. Federativ röstning blev möjlig genom konceptet av quorum-skikt: uppsättningar av likaberättigade noder som varje nod har beslutat att lita på som en del av sin (subjektiva) quorum. Denna konfiguration innebär att man kan nå konsensus även i ett öppet medlemsnätverk med byzantinska bedrägerier.

Vidare läsning

• Det ursprungliga tekniska dokumentet för SCP kan hittas här, och ). Ett typiskt exempel på användning: specifikationsprojektet för dess implementering.
• Den ursprungliga författaren av SCP-protokollet, David Mazieres, förklarar det förenklat (men ändå tekniskt) här.
• Du har kanske blivit förvånad över att inte hitta termerna "gruvdrift" eller "arbetsbevis" i denna artikel. SCP använder inte dessa metoder, men vissa andra konsensusalgoritmer gör. Zayne Witherspoon har skrivit en tillgänglig översikt över konsensusalgoritmer.
• Steg-för-steg-beskrivning en enkel nätverksmodell som når konsensus under en fullständig runda av SCP.
• För läsare som är intresserade av implementationer av SCP: se. C++-kod, som används av betalningsnätverket Stellar, eller Go-kod, som jag skrev för att bättre förstå SCP.

Källa: habr.com