Stellars konsensusprotokoll beskrevs först i David Mazier 2015. Detta är ett "federalt bysantinskt avtalssystem" som tillåter decentraliserade, ledarlösa datornätverk att effektivt nå konsensus om ett beslut. Stellars betalningsnätverk använder Stellar Consensus Protocol (SCP) för att upprätthålla en konsekvent transaktionshistorik som är synlig för alla deltagare.
Konsensusprotokoll anses vara 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 "federated voting", som är ämnet för den första hälften av den vetenskapliga artikeln, är SCP. Men det är inte sant! Detta är bara en viktig byggsten som den andra halvan av artikeln använder för att skapa faktisk Stellar konsensusprotokoll.
I den här artikeln kommer vi kort att förklara vad ett "avtalssystem" är, vad som kan göra det "bysantinskt" och varför det bysantinska systemet blir "federalt". Vi kommer sedan att förklara det federerade röstningsförfarandet som beskrivs i SCP-artikeln, och slutligen kommer vi att förklara själva SCP-protokollet.
Avtalssystem
Ett system med överenskommelser gör att en grupp deltagare kan komma överens om ett ämne, till exempel vad de ska beställa till lunch.
På Interstellar har vi implementerat vårt eget matavtalssystem: vi beställer vad vår verksamhetschef John säger. Detta är ett enkelt och effektivt avtalssystem. Vi litar alla på John och tror att han kommer att hitta något intressant och näringsrikt varje dag.
Men vad händer om John missbrukar vårt förtroende? Han kan på egen hand bestämma att vi alla ska bli veganer. Om en vecka eller två kommer vi förmodligen störta honom och lämna över makten till Elizabeth. Men plötsligt älskar hon avokado med ansjovis och tycker att alla borde vara så. Makt korrumperar. Så det är bättre att hitta någon mer demokratisk metod: något sätt att se till att olika preferenser beaktas, samtidigt som man säkerställer ett aktuellt och entydigt resultat, så att ingen slutar med att beställa lunch, eller att fem personer gör olika beställningar, eller diskussionen drar ut på kvällen.
Det verkar som att lösningen är enkel: håll en röst! Men detta är ett missvisande intryck. Vem ska samla in röstsedlarna och rapportera resultatet? Och varför ska andra tro på vad han säger? Det kanske vi kan först rösta på en ledare som vi litar på att leda omröstningen – men som kommer att leda den först genom att rösta? Tänk om vi inte kan komma överens om en ledare? Eller tänk om vi når en överenskommelse, men den här ledaren fastnar i ett möte eller blir sjukskriven?
Liknande problem uppstår i distribuerade datornätverk. Alla deltagare eller noder måste komma överens om något beslut, till exempel vems tur det är att uppdatera en delad fil eller ta bort en uppgift från bearbetningskön. I ett kryptovalutanätverk måste noder upprepade gånger välja hur hela historien ser ut från flera möjliga versioner, som ibland är i konflikt. Detta nätverksavtal ger en garanti till mottagaren att myntet är (a) giltigt (inte förfalskat) och (b) ännu inte har spenderats någon annanstans. Detta säkerställer också att han kommer att kunna spendera mynten i framtiden eftersom den nya mottagaren kommer att ha samma garantier av samma skäl.
Alla konsensussystem i ett distribuerat datornätverk måste vara feltoleranta: det måste ge konsekventa resultat trots fel som långsamma länkar, noder som inte svarar och felaktig meddelandeordning. bysantinsk Avtalssystemet är dessutom motståndskraftigt mot "bysantinska" fel: noder som ger falsk information, oavsett om det beror på ett fel eller i ett avsiktligt försök att undergräva systemet eller få någon fördel. "Bysantinsk" feltolerans - förmågan att lita på ett gruppbeslut även när vissa gruppmedlemmar kan ljuga eller på annat sätt inte följer reglerna för beslutsfattande - kallas som försökte samordna attacken. på Anthony Stevens.
Tänk på kryptomyntsägaren Alice, som måste välja mellan att köpa läcker glass från Bob och betala av Carols skuld. Kanske vill Alice betala båda på en gång genom att bedrägligt spendera samma mynt. För att göra detta måste hon övertyga Bobs dator om att myntet aldrig betalades till Carol, och övertyga Carols dator om att myntet aldrig betalades till Bob. Det bysantinska avtalssystemet gör detta praktiskt taget omöjligt, med hjälp av en form av majoritetsstyre som kallas kvorum. En nod i ett sådant nätverk vägrar att flytta till en viss version av historien tills den ser att ett tillräckligt antal kamrater - ett kvorum - går med på en sådan övergång. När detta händer kommer de att bilda ett röstningsblock som är tillräckligt stort för att tvinga de återstående nätverksnoderna att gå med på sitt beslut. Alice kan tvinga några noder att ljuga för hennes räkning, men om nätverket är tillräckligt stort kommer hennes försök att överväldigas av rösterna från ärliga noder.
Hur många noder krävs för kvorum? Åtminstone en majoritet, eller snarare, en kvalificerad majoritet för att bekämpa fel och bedrägerier. Men för att räkna majoriteten måste du veta det totala antalet deltagare. På Interstellar-kontoret eller vid distriktsvalen är dessa siffror lätta att ta reda på. Men om din grupp är ett löst definierat nätverk där noder kan komma in och lämna efter behag utan godkännande från centret, då behöver du statlig ett bysantinskt avtalssystem som kan bestämma kvorum inte från en förutbestämd lista av noder, utan dynamiskt, från en ständigt föränderlig och oundvikligen ofullständig ögonblicksbild av noder vid en given tidpunkt.
Det kan tyckas omöjligt att skapa ett kvorum från en enda nods perspektiv i ett stort nätverk, men det är möjligt. Ett sådant beslutförhet kan till och med garantera resultatet av decentraliserad omröstning. SCP-vitboken visar hur man gör detta med en procedur som kallas genom federal omröstning.
För otålig
Resten av artikeln beskriver federerad omröstning och Stellars konsensusprotokoll mer i detalj. Om du inte är intresserad av detaljerna, här är en allmän översikt över processen.
- Noderna genomför federala omröstningar om "nominerade". En federal omröstningsomgång betyder:
- Noden röstar för något påstående, till exempel "Jag föreslår värdet på V";
- Noden lyssnar på kamraternas röster tills den hittar en som kan "ta emot";
- Noden letar efter ett "quorum" för detta påstående. Ett kvorum "bekräftar" den nominerade.
- När en nod kan bekräfta en eller flera nominerade, försöker den "förbereda" "omröstningen" genom flera omgångar av federerad omröstning.
- När en nod väl kan verifiera att omröstningen är klar försöker den genomföra den genom ännu fler federerade omröstningar.
- När en nod väl kan bekräfta att en valsedel genomförts, kan den "externalisera" värdet av den valsedeln genom att använda den som ett konsensusresultat.
Dessa steg involverar flera omgångar av federerad omröstning, som tillsammans bildar en SCP-omgång. Låt oss titta närmare på vad som händer vid varje steg.
Förbundsröstning
Federerad omröstning är ett förfarande för att avgöra om nätverket kan komma överens om ett förslag. I omröstningsrundan måste varje nod välja ett av potentiellt många möjliga värden. Den kan inte göra detta om den inte är säker på att andra noder i nätverket inte kommer att välja ett annat resultat. För att säkerställa detta utbyter noder en störtflod av meddelanden fram och tillbaka så att alla bekräftatsAtt kvorum knutpunkter tar samma Beslutet. Resten av det här avsnittet förklarar termerna i den här meningen och hur hela proceduren går till.
Kvorum och kvorumskivor
Låt oss börja med att definiera ett kvorum. Som vi diskuterade ovan är det i ett decentraliserat nätverk med dynamiskt medlemskap omöjligt att i förväg veta antalet noder och därmed hur många som behövs för majoriteten. Federated votering löser detta problem genom att introducera en ny idé quorum cut (kvorumsdel): En liten uppsättning kamrater som en nod litar på för att kommunicera röststatusinformation till resten av nätverket. Varje nod definierar sin egen kvorumdel (som den blir en de facto medlem av).
Kvorumbildningen börjar med ett kvorumsnitt. För varje nod läggs dess snittnoder till. Sedan läggs skivtermerna till dessa noder och så vidare. När du fortsätter finns det fler och fler noder som du inte kan lägga till eftersom de redan finns med i segmentet. När det inte finns fler nya noder att lägga till stannar processen: vi har bildat ett kvorum genom att "transitiv stängning" av kvorumdelen av den initiala noden.
För att hitta ett kvorum från en given nod...
... lägg till medlemmar i dess segment...
...då lägger vi till segmentmedlemmar av dessa noder.
Vi fortsätter tills det inte finns några noder kvar att lägga till.
Det finns inga noder kvar att lägga till. Detta är ett kvorum.
Faktum är att varje nod kan förekomma i mer än en skiva. För att bilda ett kvorum, välj bara en av skivorna och lägg till medlemmar; välj sedan valfritt segment för var och en av medlemmarna och lägg till medlemmar av detta skära och så vidare. Detta innebär att varje nod är medlem i många möjliga kvorum.
Välj endast en kvorumskiva vid varje steg.
Ett möjligt kvorum. Eller ett alternativ...
...välj andra skivor...
…(när det är möjligt)…
... skapar ytterligare ett kvorum.
Hur vet en nod vilka skivor andra noder finns i? På samma sätt som annan information om andra noder: från de sändningar som varje nod sänder till nätet när dess röstläge ändras. Varje sändning innehåller information om sändningsnodens skivor. SCP-vitboken anger ingen kommunikationsmekanism. Implementeringar använder vanligtvis för garanterad sändning av meddelanden i hela nätverket.
Kom ihåg att i det icke-federala bysantinska systemet av avtal definieras ett beslutfört som en majoritet av alla noder. Det bysantinska avtalssystemet är utformat utifrån frågan: hur många oärliga noder kan systemet tolerera? I ett system med N noder utformade för att överleva f misslyckanden, bör en nod kunna göra framsteg genom att ta emot feedback från N−f peers eftersom f av dem kan vara nere. Men efter att ha fått ett svar från N−f-peers, kan vi anta att alla f-peers (från vilken noden inte fick något svar) faktiskt är ärliga. Således är f av N−f-kamrater (från vilka svaret mottogs) skadliga. För att noder ska komma till samma konsensus måste majoriteten av de återstående noderna vara ärliga, det vill säga vi behöver N−f vara större än 2f eller N > 3f. Så typiskt sett kommer ett system som är designat för att överleva f misslyckanden att ha totalt N=3f+1 noder och en kvorumstorlek på 2f+1. När ett förslag passerar tröskeln för beslutförhet är resten av nätverket övertygade om att alla konkurrerande förslag kommer att misslyckas. Det är så nätverket konvergerar till resultatet.
Men i ett federalt bysantinskt avtalssystem kan det inte bara finnas en majoritet (eftersom ingen känner till nätverkets totala storlek), utan konceptet med en majoritet är helt värdelöst! Om medlemskapet i systemet är öppet kan någon få majoritet helt enkelt genom att utföra en så kallad Sybil-attack: upprepade gånger gå med i nätverket över flera noder. Så varför kan transitiv skivstängning kallas kvorum, och hur kan den undertrycka konkurrerande förslag?
Tekniskt sett, inget sätt! Föreställ dig ett nätverk av sex noder, där två trillingar är isolerade i varandras kvorumskivor. Den första undergruppen kan fatta ett beslut som den andra aldrig kommer att höra talas om, och vice versa. Det finns inget sätt för detta nätverk att nå konsensus (förutom av en slump).
Därför kräver SCP att nätverket måste ha en egenskap som kallas för federerad röstning (och för att de viktiga satserna i tidningen ska gälla) skärningspunkten mellan kvorum. I ett nätverk med den här egenskapen överlappar alla två kvorum som kan konstrueras alltid i minst en nod. För att bestämma den rådande känslan av nätverket är detta lika bra som att ha en majoritet. Intuitivt betyder detta att om något kvorum går med på uttalande X, kan inget annat kvorum någonsin gå med på något annat, eftersom det nödvändigtvis kommer att inkludera någon nod från det första kvorumet som redan har röstat för X.
Om det finns en korsning av kvorum i nätverket...
...då kan du bygga vilka två kvorum som helst...
...kommer alltid att korsa varandra.
(Självklart kan överlappande noder visa sig vara bysantinskt liggande eller på annat sätt dåliga. I det här fallet hjälper kvorumkorsningen inte alls att nätverket kommer överens. Av denna anledning är många av resultaten i SCP-vitboken baserade på explicita antaganden, såsom vad som finns kvar i nätverkets kvorumövergång även efter att ha tagit bort dåliga noder. För enkelhetens skull lämnar vi dessa antaganden implicit i resten av artikeln).
Det kan tyckas orimligt att förvänta sig att en tillförlitlig korsning av kvorum är möjlig i ett nätverk av oberoende noder. Men det finns två anledningar till att 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 korsande kvorum. De flesta noder på Internet ansluter till endast ett fåtal andra lokala noder, men dessa små uppsättningar överlappar varandra tillräckligt för att varje nod kan nås från varannan nod längs någon rutt.
Det andra skälet är specifikt för Stellars betalningsnätverk (den vanligaste användningen av SCP). Varje tillgång i Stellar-nätverket har en emittent, och Stellars riktlinjer kräver att varje emittent utser en eller flera noder på nätet för att behandla inlösenförfrågningar. Det ligger i ditt intresse att direkt eller indirekt inkludera dessa noder i kvorumsnitt för varje tillgång du är intresserad av. Kvorum för alla noder som är intresserade av en given tillgång kommer då att överlappa åtminstone vid dessa inlösennoder. Noder som är intresserade av flera tillgångar kommer att inkludera alla inlösennoder för respektive emittent i sina kvorumdelar, och de kommer att försöka slå samman alla tillgångar. Dessutom eventuella tillgångar som inte är kopplade på detta sätt till andra i nätverket, och ska inte anslutas - detta är utformat så att det inte finns någon kvorumöverlappning för detta nätverk (till exempel vill banker från dollarområdet ibland handla med banker från euroområdet och banker från pesosområdet, så de är på samma nätverk, men ingen av dem bryr sig om det separata nätverket av barn som säljer basebollkort).
Naturligtvis, ожидание quorum crossing är det inte garanti. Andra bysantinska avtalssystem har mycket av sin komplexitet att tacka garantin för kvorum. En viktig innovation med SCP är att den tar bort ansvaret för att skapa kvorum från själva konsensusalgoritmen och tar den till applikationsnivån. Således, även om federerad omröstning är tillräckligt generell för att rösta om vilken fråga som helst, beror dess tillförlitlighet faktiskt kritiskt på den bredare innebörden av dessa betydelser. Vissa hypotetiska användningar kanske inte är lika gynnsamma för att skapa välanslutna nätverk som andra.
Röstning, antagande och bekräftelse
I en federerad omröstningsomgång börjar en nod valfritt att rösta för ett värde V. Detta innebär att sända ett meddelande till nätverket: "Jag är nod N, mina kvorumdelar är Q, och jag röstar på 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 peer-to-peer-sändningar ser varje nod hur de andra röstar. När en nod har samlat tillräckligt med dessa meddelanden kan den spåra kvorumskivor och försöka hitta kvorum. Om han ser ett kvorum av jämnåriga som också röstar på V kan han gå vidare till adoption V och sänd detta nya meddelande till nätverket: "Jag är nod N, mina kvorumskivor är Q, och jag accepterar V." Acceptans ger en starkare garanti än enkel röstning. När en nod röstar på V kan den aldrig rösta på andra alternativ. Men om en nod accepterar V, kommer ingen nod i nätverket någonsin att acceptera det andra alternativet (sats 8 i SCP-vitboken bevisar detta).
Naturligtvis är det stor sannolikhet att det inte omedelbart kommer att finnas ett kvorum av noder som överensstämmer med V. Andra noder kan rösta på andra värden. Men det finns ett annat sätt för en nod att gå från enkel röstning till acceptans. N får acceptera ett annat värde för W, även om han inte röstade för det, och även om han inte ser beslutförhet för det. För att bestämma dig för att ändra din röst, se bara blockeringsset noder som har accepterat W. En blockerande uppsättning är en nod från var och en av kvorumskivorna N. Som namnet antyder kan den blockera någon annan betydelse. Om alla noder i en sådan mängd accepterar W, kommer det (genom sats 8) aldrig att vara möjligt att bilda ett kvorum som tar ett annat värde, och därför är det också säkert för N att acceptera W.
Nod N med tre kvorumskivor.
BDF är en blockeringsuppsättning för N: den innehåller en nod från var och en av skivorna av N.
BE är också en blockeringsuppsättning för N eftersom E visas i två skivor av N.
Men blockeringsuppsättningen är inte beslutför. Det skulle vara för lätt att lura nod N att acceptera det önskade värdet om det räckte att hacka bara en nod i var och en av skivorna av N. Att acceptera värdet är därför inte slutet på omröstningen. Istället måste N bekräfta värdet, det vill säga se ett kvorum av noder som accepterar det. Om det kommer så långt, kommer, som SCP-vitboken bevisar (i sats 11), även resten av nätverket så småningom att bekräfta samma värde, så N kommer att avsluta den federerade omröstningen med ett visst värde som resultat.
Förbundsröstning.
Processen för omröstning, godkännande och bekräftelse utgör en hel omgång av federerad omröstning. Stellar konsensusprotokollet kombinerar många av dessa rundor för att skapa ett komplett konsensussystem.
Stellar Consensus Protocol
De två viktigaste egenskaperna hos ett konsensussystem är − säkerhet и överlevnadsförmåga. En konsensusalgoritm är "säker" om den aldrig kan ge olika resultat till olika deltagare (Bobs kopia av historien kommer aldrig att motsäga Carol). "Livability" betyder att algoritmen alltid kommer att producera ett resultat, det vill säga att den inte kommer att fastna.
Beskrivet federalt omröstningsförfarande ofarlig i den meningen att om en nod bekräftar värdet på V, kommer ingen annan nod att bekräfta det andra värdet. Men "kommer inte att bekräfta en annan betydelse" betyder inte att det nödvändigtvis kommer att bekräfta något. Deltagarna kan rösta på så många olika värden att inget kommer att nå acceptansgränsen. Det betyder att i federal omröstning finns det nej överlevnadsförmåga.
Stellars konsensusprotokoll använder federerad röstning på ett sätt som säkerställer både säkerhet och överlevnadsförmåga. (SCP:s säkerhets- och överlevnadsgarantier har en teoretisk gräns. Designen väljer en mycket stark säkerhetsgaranti, som offras en liten begränsning av överlevnadsförmågan, men givet tillräckligt med tid är det högst troligt att konsensus uppnås.) I ett nötskal är tanken att ha flera federerade röster på flera värden tills en av dem klarar alla SCP-röstningsfaser som beskrivs nedan.
Värdena som SCP söker konsensus om kan vara transaktionshistorik eller en lunchorder eller något annat, men det är viktigt att notera att dessa inte är de värden som accepteras eller bekräftas. I stället sker federal omröstning enl uttalanden om dessa värderingar.
De första omgångarna av federala omröstningar äger rum den nomineringsstadiet (nomineringsfasen), på en uppsättning uttalanden som "Jag nominerar V," kanske för många olika värden av V. Syftet med nomineringen är att hitta ett eller flera uttalanden som går igenom acceptans och bekräftelse.
Efter att ha hittat verifierbara kandidater går SCP vidare till omröstningsfasen, där målet är att hitta en viss bulletin (det vill säga en behållare för det föreslagna värdet) och ett beslutfört som kan förklara begå för det (begå). Om ett beslutfört begår en omröstning, accepteras dess värde som konsensus. Men innan en nod kan rösta om en valsedel måste den först bekräfta annullering alla röstsedlar med lägre motvärde. Dessa steg – att avbryta omröstningar för att hitta en som kan begås – involverar flera omgångar av federerad omröstning om flera valsedlar.
Följande avsnitt beskriver nominering och omröstning mer i detalj.
Utnämning
I början av nomineringsfasen kan varje nod spontant välja ett värde för V och rösta på uttalandet "Jag nominerar V." Målet i detta skede är att bekräfta nomineringen av något värde genom en federerad omröstning.
Kanske tillräckligt många noder röstar på tillräckligt olika förslag så att ingen nominering kan nå acceptansgränsen. Därför, förutom att sända sina egna nomineringsröster, "reflekterar" noder nomineringarna av sina kamrater. Eko betyder att om en nod röstar på nominering V, men ser ett meddelande från en granne som röstar på nominering W, kommer den nu att rösta på både V och W. (Alla kamratröster ekas inte under nomineringen eftersom detta kan leda till en explosion av olika nominerade. SCP inkluderar en mekanism för att reglera dessa röster. Kort sagt finns det en formel för att bestämma "prioriteten" för en kamrat ur en nods synvinkel, och endast rösterna från högprioriterade noder återspeglas. Ju längre nomineringen är. tar, ju lägre tröskeln är, så noden expanderar uppsättningen av kamrater vars röster den kommer att återspegla. Prioritetsformeln inkluderar slotnumret som en av dess ingångar, så en högprioriterad peer för en plats kan vara en lågprioriterad peer för en annan och vice versa).
Begreppsmässigt är nomineringen parallell, både V och W är separata federala röster, var och en individuellt kapabel att uppnå acceptans eller bekräftelse. I praktiken paketerar SCP-protokollmeddelanden dessa individuella röster.
Även om att rösta på V:s nominering är ett löfte om att aldrig rösta emot V:s nominering, är det på ansökningsnivå - i det här fallet SCP - som det avgörs vad "emot" betyder. SCP ser inte ett uttalande som motsäger rösten "Jag nominerar X", det vill säga det finns inget "Jag är emot att nominera X", så noden kan rösta för att nominera vilka värden som helst. Många av dessa nomineringar kommer att gå ingenstans, men så småningom kommer noden att kunna acceptera eller bekräfta ett eller flera värden. När en nominerad är bekräftad blir han det kandidat.
SCP-nominering med hjälp av federerad omröstning. Det kan finnas många "B"-värden som läggs fram av kamrater och "reflekteras" av noden.
Nomineringar kan resultera i flera bekräftade kandidater. Därför kräver SCP att applikationslagret tillhandahåller någon metod för att kombinera kandidaterna till en sammansatt (sammansatt). Sammanfogningsmetoden kan vara vad som helst. Huvudsaken är att om denna metod är deterministisk, kommer varje nod att kombinera samma kandidater. I ett lunchröstningssystem kan "enande" helt enkelt betyda att man avvisar en av två kandidater. (Men på ett deterministiskt sätt: varje nod måste välja samma värde för att återställas. Till exempel det tidigare valet i alfabetisk ordning). I Stellars betalningsnätverk, där det röstas om transaktionshistorik, innebär en sammanslagning av två föreslagna nominerade att slå samman transaktionerna de innehåller och den senaste av deras två tidsstämplar.
SCP-vitboken bevisar (sats 12) att i slutet av förlängningsfasen konvergerar nätverket så småningom till en enda sammansättning. Men det finns ett problem: federerad röstning är ett asynkront protokoll (som SCP). Med andra ord, noder koordineras inte efter tid, utan endast av de meddelanden de skickar. Ur nodens synvinkel är det oklart när slutade förlängningsfas. Och även om alla noder så småningom kommer fram till samma sammansättning, kan de ta olika vägar längs vägen, skapa olika sammansatta kandidater längs vägen, och kan aldrig säga vilken som är den sista.
Men det är normalt. Nominering är bara förberedelse. Det viktigaste är att begränsa antalet kandidater för att uppnå konsensus, vilket sker under processen omröstning (omröstning).
Löpning
Bulletin är ett par , där räknare är ett heltal som börjar på 1 och värde är en kandidat från nomineringsstadiet. Detta kan vara en nods egen kandidat eller en angränsande nods kandidat som accepteras av den noden. Grovt sett innebär en omröstning upprepade försök att tvinga nätverket att nå konsensus om en kandidat vid en omröstning genom att hålla potentiellt många federerade omröstningar om röstsedlar. Räknare på valsedlarna håller reda på gjorda försök och valsedlar med högre antal har företräde framför valsedlar med lägre antal. Om nyhetsbrevet fastnar, en ny omröstning börjar, nu på valsedeln .
Det är viktigt att skilja betyder (till exempel vad ska lunchbeställningen vara: pizza eller sallader), nyhetsbrev (motvärdespar) och uttalanden om valsedlar. SCP-omgången inkluderar flera federala omröstningar, särskilt om följande uttalanden:
- "Jag är redo att begå omröstning B" och
- "Jag tillkännager beslutet om omröstning B"
Ur en given nods perspektiv uppnås konsensus när den hittar en omröstning B för vilken den kan bekräfta (det vill säga hitta ett kvorum som accepterar) uttalandet "Jag begår omröstning B." Från och med denna tidpunkt är det säkert att agera på värdet som anges i B - till exempel att lägga denna beställning till lunch. Det kallas externisering betydelser. När godkännandet av röstsedeln har bekräftats kan en nod vara säker på att vilken annan nod som helst har externiserat samma värde eller kommer att göra det i framtiden.
Även om många federerade omröstningar begreppsmässigt genomförs på anspråk för många olika omröstningar, utbyter de inte lika många meddelanden eftersom varje meddelande kapslar in ett antal röstsedlar. Ett meddelande främjar alltså staten för många federerade röster på en gång, till exempel: "Jag accepterar röstsedlar som sträcker sig från innan "
Vad betyder termerna "förberedd" och "förbinder sig"?
En nod röstar för att genomföra en omröstning när den är säker på att andra noder inte kommer att genomföra valsedlar med olika värden. Övertygande om detta är syftet med att förbereda ansökan. En röst som säger "Jag är redo att begå omröstning B" är ett löfte om att aldrig begå en omröstning som är mindre än B, d.v.s. med ett mindre antal (SCP kräver att värdena i valsedlar ska vara i en viss ordning. Således nyhetsbrev mindre , om N1
Varför betyder "Jag är redo att genomföra omröstning B" "Jag lovar att aldrig genomföra omröstningar som är mindre än B"? Eftersom SCP definierar abort som motsatsen till commit. En omröstning för att förbereda en omröstning innebär också en omröstning för att diskvalificera vissa andra valsedlar, och som vi diskuterade tidigare är att rösta för en sak ett löfte att aldrig rösta emot det.
Innan en commit sänds måste en nod först hitta en bulletin som den kan bekräfta som förberedd. Med andra ord genomför den en federerad omröstning om ämnet "Jag är redo att begå omröstning B", möjligen på många olika valsedlar, tills den hittar en som accepterar ett beslutfört.
Var kommer röstsedlarna ifrån för att förbereda omröstningen? Först sänder noden förberedelser för att rösta på <1,C>, där C är den sammansatta kandidaten som tagits fram vid nomineringsstadiet. Men även efter att förberedelserna för omröstningen har börjat kan nomineringarna leda till att ytterligare kandidater ser ut att bli nya valsedlar. Samtidigt kan kamrater ha olika kandidater, och de kan bilda en blockerande uppsättning som accepterar "Jag är redo att begå B2-omröstningen", vilket kommer att övertyga noden att acceptera den också. Slutligen finns det en timeout-mekanism som genererar nya omgångar av federerad omröstning om nya valsedlar med högre antal om de nuvarande valsedlarna har fastnat.
Så snart noden hittar en omröstning B som den kan bekräfta som förberedd, sänder den ett nytt meddelande "Beslut omröstning B." Denna omröstning talar om för kamrater att noden aldrig kommer att ge upp B. Faktum är att om B är en valsedel , sedan "Beslut omröstning " betyder det ovillkorliga samtycket att rösta för beredskapen för varje omröstning från till <∞, s>. Detta extra värde hjälper andra kamrater att komma ikapp den commit-peer om de fortfarande är i tidigare stadier av protokollet.
I detta skede är det värt att än en gång betona att dessa är asynkrona protokoll. Bara för att en nod skickar uppröster för en commit betyder det inte att dess kamrater också gör det. Vissa av dem kanske fortfarande röstar på uttalanden som förberedelse för omröstning, andra kan redan ha externiserat innebörden. SCP förklarar hur en nod ska behandla varje typ av peer-meddelande oavsett dess fas.
Om meddelandet "Jag har meddelat ett åtagande » kan inte tas emot eller bekräftas, det vill säga sannolikheten för att meddelandet accepteras eller bekräftas eller - eller i vilket fall som helst valsedel med värdet C, och inte någon annan, eftersom noden redan har lovat att aldrig avbryta . När en nod sänder röster för en commit kommer det att vara C eller ingenting, beroende på hur långt konsensusen går. Detta är dock ännu inte tillräckligt för att noden ska kunna externisera C. Vissa bysantinska kamrater (som utgör mindre än ett kvorum, baserat på våra säkerhetsantaganden) kan ljuga för noden. Att acceptera och sedan bekräfta någon omröstning (eller ett antal valsedlar) är det som ger noden förtroendet att slutligen externisera C.
SCP-röstning genom federerad omröstning. Visas inte: Timern kan gå av när som helst, vilket ökar antalet på röstsedeln (och eventuellt producera en ny sammansättning av ytterligare nominerade kandidater).
Och det är allt! När nätverket har nått en konsensus är det redo att göra det om och om igen. På Stellars betalningsnätverk händer detta ungefär en gång var 5:e sekund: en bedrift som kräver både säkerhet och överlevnadsförmåga som garanteras av SCP.
SCP kan uppnå detta genom att förlita sig på flera omgångar av federerad omröstning. Federerad röstning möjliggörs av konceptet med kvorumskivor: uppsättningar av kamrater som varje nod har beslutat att lita på som en del av sitt (subjektiva) kvorum. Denna konfiguration innebär att konsensus kan nås även i ett nätverk med öppet medlemskap och bysantinska bedrägerier.
Vidare läsning
- Den ursprungliga SCP-vitboken kan hittas Och utkast till specifikationer för dess genomförande.
- Den ursprungliga författaren till SCP-protokollet, David Mazier, förklarar det på ett förenklat (men fortfarande tekniskt) sätt. .
- Du kanske har blivit förvånad över att inte hitta termerna "gruvdrift" eller "bevis på arbete" i den här artikeln. SCP använder inte dessa metoder, men vissa andra konsensusalgoritmer gör det. Zane Witherspoon skrev tillgängligt .
- ett enkelt nätverk som når konsensus i en hel omgång av SCP.
- För läsare som är intresserade av SCP-implementeringar: se , som används av Stellars betalningsnätverk, eller , som jag skrev för en bättre förståelse av SCP.
Källa: will.com