A Stellar konszenzusprotokollt először David Mazière írta le 2015-ben. Ez egy „federatív bizánci egyetértési rendszer”, amely lehetővé teszi, hogy a decentralizált számítógépes hálózatok vezetők nélkül hatékonyan elérjék a konszenzust bármilyen döntésben. A Stellar kifizetési hálózat a Stellar Konszenzus Protokollt (SCP) használja a tranzakciók egységes történetének nyilvántartására, amelyet minden résztvevő lát.
Úgy tartják, hogy a konszenzusprotokollok nehezen érthetők. Az SCP egyszerűbb, mint a legtöbb, de mégis megőrzi ezt a hírnevet – részben azért, mert téves következtetés, hogy a cikk első felében bemutatott „federatív szavazás” maga az SCP. Pedig nem így van! Ez csak egy fontos építőelem, amelyet a cikk második felében használnak az aktuális Stellar konszenzusprotokoll létrehozásához.
A cikkben röviden áttekintjük, mi is az a „megállapodási rendszer”, miért lehet „bizánci”, és miért érdemes egy bizánci rendszert „federatívvá” tenni. Aztán elmagyarázzuk a federatív szavazási eljárást, amelyet az SCP cikkében írnak le, végül pedig magát az SCP protokollt is ismertetjük.
Megállapodási rendszerek
A megállapodási rendszer lehetővé teszi egy résztvevő csoport számára, hogy konszenzusra jussanak valamiben, például abban, hogy mit rendeljenek ebédre.
Mi, az Interstellar cégnél, bevezettük a saját ebédmegállapodásainkat: azt rendeljük, amit az operatív menedzserünk, John mond. Ez egy egyszerű és hatékony megállapodási rendszer. Mindannyian bízunk Johnban, és hisszük, hogy nap mint nap talál valami érdekeset és táplálót.
De mi van, ha John visszaél a bizalmunkkal? Ő egyedül döntheti el, hogy mindannyiunknak vegánná kell válnia. Egy-két héten belül valószínűleg megbuktatjuk őt, és a hatalmat Elizabethnek adjuk át. De mi van, ha ő szereti az avokádót angolnával, és azt gondolja, hogy mindenkinek ilyenné kell válnia? A hatalom megront. Ezért jobb valami demokratikusabb módszert találni: valamilyen módot biztosítani a különböző preferenciák figyelembevételére, miközben egy határozott és időben megvalósuló eredményt is biztosítunk, hogy ne fordulhasson elő, hogy senki sem rendel ebédet, vagy öten különböző rendeléseket adjanak le, vagy hogy a megbeszélés estig elhúzódjon.
A megoldásnak egyszerűnek kellene lennie: szavazni kellene! De ez megtévesztő benyomás. Ki fogja összegyűjteni a szavazólapokat és közölni az eredményeket? És miért kellene a többieknek hinni abban, amit mondani fog? Lehet, hogy először szavazzunk egy olyan vezetőre, akiben megbízunk, hogy vezesse a szavazást — de ki fogja vezetni ezt a szavazást? Mi van, ha nem tudunk megegyezni egy vezetőről? Vagy ha megegyezünk, de ez a vezető egy megbeszélésen ragad, vagy táppénzre megy? első Hasonló problémák merülnek fel elosztott számítógépes hálózatokban. Minden résztvevőnek vagy csomópontnak meg kell állapodnia valamilyen döntésről, például arról, hogy ki frissítse a közös fájlt, vagy ki vegye el a feladatot a feldolgozó sorból. A kriptovaluta hálózatban a csomópontoknak többször is el kell dönteniük, hogy hogyan nézzen ki a teljes történet a lehetséges verziók közül, amelyek néha ellentmondanak egymásnak. Ez a hálózati megállapodás biztosítja a címzett számára, hogy a pénz (a) érvényes (nem hamisított) és (b) nem költötték el máshol. Ez azt is garantálja, hogy ő képes lesz a jövőbeli költésekre, mert az új címzett ugyanazokat a garanciákat kapja ugyanazok miatt.
Bármely elosztott számítástechnikai hálózatban a konszenzus rendszereinek hibamentesnek kell lenniük: következetes eredményeket kell produkálniuk, függetlenül az olyan hibáktól, mint a lassú kommunikációs vonalak, nem reagáló csomópontok és a hibás üzenetküldési sorrend.
A bizánci konszenzusrendszer további ellenállást mutat a „bizánci” hibákkal szemben: azok a csomópontok, amelyek hamis információt adnak, akár hibák miatt, akár szándékos kísérletek révén a rendszer aláásására vagy előnyhöz juttatására. A „bizánci” hibatűrés — a képesség arra, hogy megbízzunk a csoportos döntésben, még akkor is, ha a csoport egyes tagjai hazudhatnak vagy más módon nem követik a döntéshozatali szabályokat — a bizánci császárság tábornokainak meséje után kapta a nevét, Jó leírás Anthony Stevensnél.
Nézzük meg a kriptovaluta tulajdonosát, Alisát, aki választania kell Bob finom fagyija és Carol adósságának kifizetése között. Lehetséges, hogy Alisa mindkettőnek szeretne azonnal fizetni, csalárdan ugyanazt a érmét felhasználva. Ehhez meg kell győznie Bob számítógépét, hogy az érmét soha nem fizették ki Carolnak, és meg kell győznie Carol számítógépét, hogy az érmét soha nem fizették ki Bobnak. A bizánci konszenzus rendszere ezt gyakorlatilag lehetetlenné teszi, használva egy többségi szabályformát, amelyet kvórumnakhívnak. Egy ilyen hálózat csomópontja nem hajlandó elfogadni egy meghatározott történeti verziót, amíg nem látja, hogy elegendő számú egyenrangú csomópont – kvórum – egyetértene ezzel az átlépéssel. Amint ez megtörténik, elegendő nagy választói blokkot formálnak, hogy rávegyék a hálózat fennmaradó csomópontjait a döntésük elfogadására. Alisa megpróbálhatja rávenni néhány csomópontot, hogy hazudjanak a nevében, de ha a hálózat elég nagy, az ő próbálkozása el fog dőlni a becsületes csomópontok szavazatai által.
Hány csomópont szükséges a kvórumhoz? Legalább a többség, pontosabban a kétharmados többség a hibák és csalások ellen. De a többség kiszámításához tudni kell a résztvevők teljes számát. Az Interstellar irodájában vagy a kerületi választások során ezeket a számokat könnyen meg lehet tudni. De ha a csoportod egy gyengén definiált hálózat, amelybe a csomópontok szabadon beléphetnek és távozhatnak középként, akkor szükség van egy szövetségi bizánci konszenzus rendszerre, amely képes a kvórumokat nem előre meghatározott csomópontok listájából, hanem dinamikusan, folyamatosan változó és elkerülhetetlenül hiányos pillanatnyi képből meghatározni.
Lehetetlennek tűnhet létrehozni egy kvórumot egy csomópont szemszögéből egy kiterjedt hálózatban, de ez lehetséges. Ilyen kvórum akár a decentralizált szavazás eredményeit is garantálhatja. A SCP technikai dokumentum bemutatja, hogyan lehet ezt megvalósítani egy eljárás segítségével, amelyet szövetségi szavazásnak.
hívnak. Aki türelmetlen,
a cikk további része részletesen bemutatja a szövetségi szavazást és a Stellar konszenzus protokollt. Ha nem érdeklik a részletek, itt egy általános áttekintés a folyamatról.
- A csomópontok szövetségi szavazási fordulókat tartanak a "jelöltek" részére. A szövetségi szavazási forduló azt jelenti:
- A csomópont szavaz egy javaslatra, például: "A V érték meghatározását javaslom";
- A csomópont hallgatja a pirok szavazatait, amíg meg nem talál egyet, amelyik "elfogadja";
- A csomópont "kér" a javaslathoz. A kórum "megerősíti" a jelöltet.
- Amint a csomópont képes megerősíteni egy vagy több jelöltet, megpróbálja "készíteni" a "szavazólapot" néhány fordulós szövetségi szavazáson keresztül.
- Miután a csomópont ellenőrizni tudja a szavazólap készen állását, próbálja meg elkötelezni azt további szövetségi szavazási fordulók révén.
- Mihelyt a csomópont megerősítheti a szavazólap elkötelezését, "externalizálhatja" ennek a szavazólapnak az értékét, elismerve azt konszenzus eredményeként.
Ezek a lépések több szövetségi szavazási fordulót foglalnak magukban, amelyek együttesen alkotnak egy SCP fordulót. Nézzük meg részletesebben, milyen események zajlanak le minden lépésnél.
Szövetségi szavazás
A szövetségi szavazás egy olyan eljárás, amely meghatározza, hogy a hálózat egy javaslatot egyesíthet-e. A szavazási fordulóban minden csomópontnak választania kell az esetlegesen sok lehetséges érték közül. Ezt nem teheti meg, amíg nem biztos abban, hogy a hálózat más csomópontjai nem választanak más eredményt. Ennek biztosítása érdekében a csomópontok visszafelé üzenetek özönét cserélik, hogy mindegyik megerősítette, hogy kvórum csomópont acceptálja ugyanazt döntés. A szakasz többi része magyarázza az e javaslatban szereplő kifejezéseket és azt, hogy zajlik végig a folyamat.
Kórumok és kórum szeletek
Kezdjük a kórum meghatározásával. Ahogy már említettük, a decentralizált, dinamikusan változó tagságú hálózatban lehetetlen előre tudni, hány csomópont van, és ezzel mennyire van szükség a többséghez. A szövetségi szavazás megoldja ezt a problémát azáltal, hogy új ötletet mutat be, kórum szeletet (quorum slice): egy kis számú egyenrangú csomópont, amelyben a csomópont megbízik, hogy információt továbbít a szavazás állapotáról a hálózat többi részére. Minden csomópont saját kórum szeletét határozza meg (amelynek tényleges tagja lesz).
A kórum kialakítása a kórum szelettel kezdődik. Minden csomóponthoz hozzáadják a szeletének csomópontjait. Ezután a szeletek tagjait ezek a csomópontok és így tovább. Ahogy folytatódik, egyre több csomópont található, amelyet nem tud hozzáadni, mert már bele van foglalva a részhalmazba. Amikor már nincsenek új csomópontok hozzáadására, a folyamat véget ér: a kvórumot a kezdő csomópont részhalmazának "transzktív lezárásával" hoztuk létre.
A kvórum megtalálásához egy adott csomópontból…
... hozzáadjuk a részhalmazának tagjait…
... majd hozzáadjuk ezeknek a csomópontoknak a részhalmazaik tagjait.
Folytatjuk, amíg nem maradnak csomópontok hozzáadásra.
Nincsenek már hozzáadható csomópontok. Ez a kvórum.
Valójában minden csomópont több részhalmazban is benne lehet. A kvórum létrehozásához válasszon ki csak egy részhalmazt, és adja hozzá a tagokat; ezután válasszon ki bármilyen részhalmazt minden tag számára, és adja hozzá a tagokat ez részhalmaz és így tovább. Ez azt jelenti, hogy minden csomópont számos lehetséges kvórumnak a tagja.
Minden lépésben válasszon ki csak egy kvórum részhalmazt.
Egy lehetséges kvórum. Vagy alternatív lehetőség…
... más részhalmazokat választunk…
... (amikor ez lehetséges)…
... létrehoz egy másik kvórumot.
Hogyan tudja a csomópont meg, hogy a többi csomópont milyen részhalmazokban van? Ugyanúgy, ahogy a többi csomópont adatát: az útvonalakon, amelyeket minden csomópont sugároz a hálózatban, amikor a szavazási állapota megváltozik. Minden sugárzás tartalmazza a küldő csomópont részhalmazaira vonatkozó információkat. A SCP technikai dokumentumban nincs megadva a kommunikáció mechanizmusa. A megvalósítások általában használnak az üzenetek megbízható átvitelére az egész hálózaton.
Ne feledjük, hogy a nemzeti viszályos bizánci megállapodási rendszerben a quorumnak a csomópontok többsége számít. A bizánci megállapodási rendszer azon kérdés köré épül, hogy hány tisztességtelen csomópontot képes elviselni a rendszer? Az N csomópontból álló rendszernek a f meghibásodás (csalás) során hosszú távú túlélésre tervezték, a csomópontnak képesnek kell lennie arra, hogy előrehaladjon, válaszokat kapva az N−f társaktól, mivel f belőlük esetleg nem működik. Ha választ kapunk az N−f társaktól, akkor feltételezhetjük, hogy az összes f társ (akiktől a csomópont nem kapott választ) valójában tisztességes. Így a f a N−f társak közül (akiktől választ kaptunk) kártékony. Ahhoz, hogy a csomópontok egy konszenzusra jussanak, a többi csomópont közül a tisztességesek többsége kell, hogy legyen, vagyis szükségünk van arra, hogy N−f nagyobb legyen, mint 2f, vagyis N > 3f. Tehát általában a f meghibásodásra tervezett rendszernek összesen N=3f+1 csomópontja és 2f+1 kvórum mérete lesz. Amint egy javaslat átlépi a kvórum küszöbértékét, a hálózat többi tagja meg van győződve arról, hogy bármely versengő javaslat kudarcot vall.
De a szövetségi bizánci megállapodási rendszerben nemcsak hogy nincs többség (mivel senki sem tudja, mekkora a hálózat), hanem a többség fogalma teljesen haszontalan! Ha a rendszer tagsága nyitott, akkor valaki egyszerűen a Sivil támadással megszerezheti a többséget: többször is csatlakozva a hálózathoz különböző csomópontokon keresztül. Tehát miért nevezhetjük a transzitív zárás szeletét kvórumnak, és hogyan képes elnyomni a versengő javaslatokat?
Technikailag semmilyen módon! Képzeljünk el egy hat csomópontból álló hálózatot, ahol két-három csomópont izolált kvórum szeletekben. Az első alcsoportra vonatkozó döntést a második soha nem hallja meg, és fordítva. Ennek a hálózatnak nincs módja a konszenzus elérésére (kivéve véletlenszerűen).
Ezért az SCP azt igényli, hogy szövetségi szavazásra (és a cikk fontos tételeinek alkalmazására) a hálózat rendelkezzen egy kvórumok metszetével. A hálózaton e tulajdonsággal bármely két kvórum, amit fel lehet építeni, mindig átfedésben van legalább egy csomóponttal. A hálózat uralkodó hangulatainak meghatározásához ez éppúgy elegendő, mint a többség birtoklása. Intuitívan ez azt jelenti, hogy ha bármely kvórum egyetért az X állítással, akkor egy másik kvórum sosem tud egy másikkal egyetérteni, mert biztosan tartalmazni fog egy csomópontot az első kvórumból, amely már szavazott X-re.
Ha a hálózaton kvórumok átfedése van…
… akkor bármely két kvórum, amit felépíthet…
… mindig átfedésben lesz.
(Természetesen az átfedő csomópontok lehetnek bizánci hazugok vagy más szempontból hibásak. Ilyen esetben a kvórumok átfedése egyáltalán nem segít a hálózat egyetértésében. Ezért sok eredmény a SCP technikai dokumentumban nyíltan megfogalmazott feltételezésen alapul, mint például az, hogy a hálózaton még mindig marad átfedés a kvórumok között még a hibás csomópontok eltávolítása után is. Az egyszerűség kedvéért hagyjuk ezeket a feltételezéseket nem kifejezettnek a cikk további részében).
Óvakodhatunk attól, hogy elvárjuk, hogy független csomópontokból álló hálózatban lehetséges a megbízható kvórumok átfedése. De két ok van, amiért ez így van.
Az első ok a internet létezésében rejlik. Az internet egy tökéletes példa a független csomópontok hálózatára kvórumok átfedésével. Az internet legtöbb csomópontja csupán néhány más helyi csomóponttal kapcsolódik, de ezek a kis halmazok annyira átfedik egymást, hogy minden csomópont elérhető legyen bármely más csomópontból valamilyen úton.
A második ok a Stellar fizetési hálózatra vonatkozik (a leggyakoribb alkalmazás az SCP). A Stellar hálózaton minden eszköznek van egy kibocsátója, és a Stellar ajánlásai megkövetelik, hogy minden kibocsátó rendeljen egy vagy több csomópontot a hálózaton a visszaváltási kérések feldolgozására. Érdekeid szolgálatában áll, hogy ezeket a csomópontokat közvetlenül vagy közvetve bevond az érdeklődési körödbe tartozó eszközök kvórumaiba. Ezt követően a kvórumok minden olyan csomópontra vonatkozóan, amely érdeklődik az adott eszköz iránt, legalább ezekben a visszaváltási csomópontokban átfedésben lesznek. A több eszköz iránt érdeklődő csomópontok a megfelelő kibocsátók visszaváltási csomópontjait be fogják vonni a kvórumaikba, és mindent meg fognak tenni, hogy az összes eszközt egyesítsék. Ezen kívül bármely, a hálózaton más eszközökkel ilyen módon nem összekapcsolt eszköz nem kell, hogy kapcsolódjon — ez a célja annak, hogy a hálózaton ne legyen kvórum átfedés (például a dollárzónában lévő bankok néha szeretnének kereskedni az eurózónába tartozó bankokkal és a pesózónával lévő bankokkal, tehát egy hálózaton vannak, de egyikük sem érdekli a kisgyerekek külön hálózatát, akik baseball kártyákkal kereskednek).
Természetesen, az a várakozás hogy a kvórumok átfedése nem garantált. Más bizánci megállapodású rendszerek összetettségét nagyrészt a kvórumok garantálása határozza meg. Az SCP egyik fontos újítása, hogy a kvórumok létrehozásáért tett felelősséget kiemeli a konszenzus algoritmusából, és alkalmazási szintre helyezi. Így, bár a szövetségi szavazás elég általános minden jelenség szavazására, a megbízhatósága kritikus mértékben függ ezeknek az értelmeknek a szélesebb kontextusától. Néhány hipotetikus felhasználási eset nem biztos, hogy olyan kényelmes lesz jól összekapcsolt hálózatok létrehozásában, mint mások.
Szavazás, elfogadás és megerősítés
A szövetségi szavazási fordulóban a csomópont opcionálisan elkezdi szavazni egy bizonyos V értéket. Ez annyit jelent, hogy a hálózaton az üzenet továbbítása: "Én N csomópont vagyok, a kvórumaim Q, és V-re szavazok". Amikor a csomópont így szavaz, ígéretet tesz arra, hogy soha nem szavazott V ellen, és soha nem is fog.
A peer-to-peer transmisijóban minden csomópont látja, hogy a többiek hogyan szavaznak. Miután egy csomópont elegendő ilyen üzenetet gyűjtött össze, nyomon tudja követni a kormányzati szeleteket, és próbálhatja megtalálni a kormányokat. Ha lát egy kormányt a résztvevőktől, akik szintén V-re szavaznak, akkor haladhat a döntés felé V elfogadása és ezt az új üzenetet továbbítja a hálózatnak: «Én N csomópont vagyok, a kormányzati szeleteim Q, és elfogadom V-t». Az elfogadás erősebb garanciát nyújt, mint a sima szavazás. Amikor egy csomópont V-re szavaz, soha nem szavazhat más lehetőségekre. De ha a csomópont elfogadja V-t, akkor a hálózatban soha egyetlen csomópont sem fog más lehetőséget elfogadni (a SCP technikai dokumentumban 8. tétel ezt bizonyítja).
Természetesen nagy a valószínűsége, hogy azonnal nem található egy kormányzati szelet csomópont, amely egyetértene V-vel. Más csomópontok más értékekre szavazhatnak. De a csomópont számára van még egy módja annak, hogy átlépjen a sima szavazásból az elfogadásba. N elfogadhatja egy másik W értéket, még akkor is, ha nem szavazott rá, és még akkor is, ha nem lát számára kormányt. Az, hogy megváltoztassa a szavazatát, elég, ha látja a blokkoló halmazt a W-t elfogadó csomópontokból. A blokkoló halmaz egy a N kormányzati szeleteiből származó csomópont. Amint a neve is sugallja, képes blokolni bármely más értéket. Ha a halmaz összes csomópontja elfogadja W-t, akkor (a 8. tétel alapján) soha nem sikerül kormányt létrehozni, amely más értéket fogad el, és ezért N számára is biztonságos W elfogadása.
Az N csomópont három kormányzati szelettel rendelkezik.
B-D-F – blokkoló halmaz N számára: egy-egy csomópontot tartalmaz N szeleteiből.
B-E szintén blokkoló halmaz N számára, mert E megjelenik N két szeletében.
De a blokkoló halmaz nem kormány. Túl könnyű lenne megtéveszteni az N csomópontot, hogy elfogadja a kívánt értéket, ha elegendő csak egy csomópontot feltörni mindegyik N szeletből. Ezért az érték elfogadása még nem a szavazás vége. Ehelyett N-nek meg kell erősítenie az értéket, azaz látnia kell a kormányzati csomópontokat, amelyek azt elfogadják. Ha eljutott eddig, akkor, ahogy a SCP technikai dokumentum (11. tétel) bizonyítja, a hálózat többi része végül szintén megerősíti ugyanazt az értéket, így N befejezi a szövetségi szavazást egy meghatározott értékkel, mint eredménnyel.
Szövetségi szavazás.
A szavazási, elfogadási és megerősítési folyamat egy teljes kör egy szövetségi szavazás során. A Stellar konszenzus protokoll több ilyen kört egyesít, hogy teljes konszenzusos rendszert hozzon létre.
Stellar konszenzus protokoll
A konszenzusos rendszer két legfontosabb tulajdonsága — biztonság és életképesség. A konszenzus algoritmus "biztonságos", ha sosem adhat különböző eredményeket a különböző résztvevőknek (Bob történetének másolata sosem lesz ellentmondásban Caroléval). Az "életképesség" azt jelenti, hogy az algoritmus mindig eredményt ad, tehát sosem marad megakadt.
A fenti szövetségi szavazási eljárás biztonságos abban az értelemben, hogy ha egy csomópont megerősít egy V értéket, akkor egy másik csomópont sem erősít meg más értéket. De az, hogy „nem erősít meg más értéket” — nem jelenti azt, hogy feltétlenül egyet kell értenie valamivel. A résztvevők olyan sok különböző érték mellett szavazhatnak, hogy semmi sem éri el a megszavazáshoz szükséges küszöböt. Ez azt jelenti, hogy a szövetségi szavazásban hiányzik a életképesség.
A Stellar konszenzus protokoll úgy használja a szövetségi szavazást, hogy biztosítsa a biztonságot és az életképességet. (A SCP biztonsági és életképességi garanciálja elméletileg korlátozott. A konstrukció nagyon erős biztonsági garanciát választ, feláldozva a kis mértékű életképesség gyengítését, de figyelembe véve elegendő időt, a konszenzus nagy valószínűséggel elérhető lesz). Röviden az elképzelés az, hogy több szövetségi szavazást rendezzenek több értékről, amíg az egyik teljesen végig nem halad az alábbiakban ismertetett SCP szavazási fázisokon.
Az értékek, amelyekre a SCP a konszenzusra törekszik, lehetnek tranzakciós történetek, ebédrendelések vagy bármi más, de fontos megjegyezni, hogy nem ezek az értékek kerülnek elfogadásra vagy megerősítésre. Ehelyett a szövetségi szavazás a ezen értékekkel kapcsolatos nyilatkozatokra történik.
Az első szövetségi szavazási fordulók a jelölési szakaszban (nomination phase) zajlanak, a "Javaslom V" típusú nyilatkozatok készletén, lehetőleg sok különböző V értékhez. A jelölés célja, hogy megtaláljanak egy vagy több olyan nyilatkozatot, amely keresztülmegy az elfogadáson és megerősítésen.
A megerősített jelöltek megtalálása után az SCP átmegy a szavazás fázisába, ahol a cél egy bizonyos szavazólap (azaz a javasolt érték konténere) és a kvórum, amely képes kihirdetni commit-ra. azt (commit). Ha a kvórum elkötelezi a szavazólapot, annak értéke konszenzusként elfogadásra kerül. De mielőtt a csomópont szavazhatna a szavazólap elkötelezésére, először meg kell erősítenie a törlését minden alacsonyabb számlálóértékű szavazólapról. Ezek a lépések — a szavazólapok törlése annak érdekében, hogy megtalálják azt, amelyikhez elkötelezést lehet erősíteni — több kört tartalmaznak a föderális szavazás során több szavazólap állítására.
A következő fejezetekben részletesebben bemutatják a jelölést és a szavazást.
Jelölés
A jelölési fázis elején minden egyes csomópont spontán módon választhat egy V értéket, és szavazhat a „Jelölöm V”-re. A cél ebben a fázisban egy érték jelölésének megerősítése a föderális szavazás révén.
Lehetséges, hogy elegendő számú csomópont szavazott elegendően eltérő állításokra, és egyetlen jelölés sem tudja elérni a meghatározott küszöböt. Ezért a saját jelölő szavazatainak továbbítása mellett a csomópontok „visszhangozzák” a szomszédaik jelöléseit. A visszhangzás (echo) azt jelenti, hogy ha egy csomópont szavaz a V jelölésre, de lát egy üzenetet a szomszédjától, aki a W jelölésre szavaz, akkor most már a V és a W jelölésre is szavazni fog. (Nem minden peer szavazat kap visszhangzást a jelölés során, mert az különböző jelöltek robbanásához vezethet. Az SCP tartalmaz egy mechanizmust ezen szavazatok szabályozására. Röviden, létezik egy képlet a peer „prioritásának” meghatározására a csomópont szempontjából, és csak a magas prioritású csomópontok szavazatait tükrözik. Minél tovább tart a jelölés, annál alacsonyabb a küszöb, így a csomópont bővíti azon peer-ek körét, akiknek a szavazatait visszhangozza. A prioritás képlete egyik bemeneti adatként tartalmazza a sávszámot, így egy magas prioritású peer egy sávszámhoz alacsony prioritású lehet egy másik számára, és fordítva).
A koncepció szerint az V és W párhuzamos előterjesztése külön szövetségi szavazatok, amelyek mindegyike képes külön-külön elfogadni vagy megerősíteni. A gyakorlatban az SCP protokoll üzenetei ezeket a különböző szavazatokat egyesítik.
Bár az V jelölésére tett szavazás azt ígéri, hogy soha nem szavaznak az V elleni előterjesztésre, az alkalmazásszintű meghatározásban – jelen esetben SCP – ez azt jelenti, hogy mi számít 'ellen'. Az SCP nem lát olyan állítást, amely ellentmond az 'X jelölésére szavazok' szavazásának, ami azt jelenti, hogy nincsen 'Ellenzem az X előterjesztését' üzenet, így a csomópont szavazhat bármelyik érték előterjesztésére. Számos jelölés nem vezet semmihez, de végül a csomópont egyszer vagy többször el tud fogadni vagy megerősíteni tud egy vagy több értéket. Amint a jelöltet megerősítik, az lesz a jelölt.
Az SCP előterjesztése szövetségi szavazással. Sok 'B' érték létezhet, amelyeket egyenrangú csomópontok terjesztenek elő és a csomópont 'visszatükröz' ilyen értékeket.
A jelöltek előterjesztése több megerősíthető jelölt létrejöttéhez vezethet. Ezért az SCP megköveteli, hogy az alkalmazásszint biztosítson valamilyen módszert a jelöltek egyesítésére egyetlen kompozit (composite). Az egyesítési módszer lehet bármilyen. A legfontosabb, hogy ha ez a módszer determinisztikus, akkor minden csomópont ugyanazokat a jelölteket egyesíti. Az étkezési szavazás rendszerében az 'egyesítés' egyszerűen egy kétrészes jelölt egyikének elutasítását jelentheti. (De determinisztikusan: minden csomópontnak ugyanazt az értéket kell választania a visszavonáshoz. Például korábban az ábécé sorrendje). A Stellar fizetési hálózatban, ahol a tranzakciók történetéről történik a szavazás, a két javasolt jelölt egyesítése magában foglalja azoknak a tranzakcióknak az egyesítését, amelyeket tartalmaznak, és legutolsó időbélyegük egyesítése.
Az SCP technikai leírása bizonyítja (12. tétel), hogy a jelölési fázis végén a hálózat végül egy kompozithoz konvergál. De van egy probléma: a szövetségi szavazás aszinkron protokoll (mint az SCP is). Más szavakkal, a csomópontok nem időben koordinálják egymást, csak a küldött üzenetek alapján. véget ért a jelölési fázis. Bár minden csomópont végül ugyanahhoz a kompozithoz jut el, különböző utakat választhatnak ezen az úton, különböző összesített jelölteket hozva létre, és soha nem tudhatják, melyik a végleges.
De ez rendben van. A jelölés csupán előkészület. A legfontosabb, hogy korlátozzuk a jelöltek számát a konszenzus elérése érdekében, amely a folyamat során következik be. szavazás (balloting).
A szavazás
A szavazólap egy pár <counter,value>, ahol a counter egy egész szám, amely 1-től indul, míg a value a jelölés fázisához tartozó jelölt. Ez lehet a csomópont saját jelöltje vagy egy szomszédos csomópont által elfogadott jelölt. Nagyjából a szavazás során többször is megpróbálják a hálózatot konszenzusra juttatni egy jelölt mellett egy adott szavazólapon, potenciálisan sok szövetségi szavazást végezve a szavazólapok nyilatkozatai alapján. A szavazólapokon lévő számlálók nyomon követik a kísérleteket, és a nagyobb számlálóval rendelkező szavazólapok prioritást élveznek a kisebb támogatásúak előtt. Ha a szavazólap <counter, value> beragad, új szavazás kezdődik, most a <counter+1, value> szavazólapon.
Fontos megkülönböztetni a jelentéseket (például milyen legyen az ebéd rendelése: pizza vagy saláta), a szavazólapokat (counter-value pár) és a szavazólapok nyilatkozatait. Az SCP kör több szövetségi szavazási kört tartalmaz, különösen az alábbi nyilatkozatokkal kapcsolatban:
- «Készen állok a B szavazólap elkötelezésére» és
- «Kijelentem a B szavazólap elkötelezését»
A csomópont szempontjából a konszenzus akkor érhető el, amikor talál egy B szavazólapot, amelyhez hitelesíteni tudja (azaz quorumot talál, amely elfogadja) a «Kijelentem a B szavazólap elkötelezését» nyilatkozatot. Ettől a pillanattól kezdve biztonságosan lehet cselekedni a B-ben megadott érték szerint – például leadni ezt az ebéd rendelést. Ezt nevezzük externelizációjának az értéknek. Miután a szavazólap elfogadását megerősítették, a csomópont biztos lehet benne, hogy bármely más csomópont externizálta ezt az értéket, vagy a jövőben szükségszerűen el fogja végezni.
Bár a koncepció szerint sok szövetségi szavazás különböző szavazólapok nyilatkozatai alapján zajlik, nem cserélnek ennyi üzenetet, mert minden üzenet egy sor szavazólapot tartalmaz. Egy üzenet így egyszerre több szövetségi szavazás állapotát képviseli, például: „Elfogadom a szavazólapok elkötelezését a és közötti tartományban.”
Mit jelentenek a „felkészített” (prepared) és az „elkötelezés” (commit) kifejezések?
A csomópont akkor szavaz a szavazólap elkötelezésére, amikor meg van győződve arról, hogy más csomópontok nem fognak más értékekkel szavazólapokat elkötelezni. Ennek megerősítése a nyilatkozat előkészítési célja. A szavazás, amely azt mondja: „Készen állok B szavazólap elkötelezésére”, egy ígéret arra, hogy soha nem fogok kisebb szavazólapot elkötelezni, mint B, azaz alacsonyabb számlálóval (az SCP megköveteli, hogy a szavazólapok értékeinek bizonyos sorrendben kell lenniük. Így a szavazólap kisebb, mint , ha N1 < N2, és akkor is, ha N1 = N2 és V1 < V2). Ezeket a kisebb szavazólapokat „megszakítottak” (aborted) az előkészítő szavazás során, míg B-et „felkészítettnek” tekintjük.
Miért jelenti a „Készen állok B szavazólap elkötelezésére” azt, hogy „Ígérem, hogy soha nem engedek el kisebb szavazólapokat, mint B”? Mert az SCP a megszakítást az elkötelezés ellentéteként definiálja. A szavazás a szavazólap előkészítéséről azt is jelenti, hogy más szavazólapok megszüntetésére szavazunk, és ahogy korábban tárgyaltuk, egy dologra való szavazás egy ígéret arra, hogy soha nem szavazunk ellene.
Mielőtt elkötelezné a szavazólapot, a csomópontnak először meg kell találnia egy olyan szavazólapot, amelyet felkészítettnek tud megerősíteni. Más szavakkal, szövetségi szavazást folytat a „Készen állok B szavazólap elkötelezésére” témában, lehetőleg sok különböző szavazólapra, amíg meg nem találja azt, amelyik elnyeri a kvórumot.
Honnan származnak a szavazati háttéranyagok? Először a csomópont közvetíti a szavazáshoz való felkészülést a -re, ahol C egy jelölt, ami a jelölési fázisban készült. Azonban még a szavazásra való felkészülés megkezdése után is, a jelölés további jelöltek megjelenését eredményezheti, amelyek új háttéranyagokká válnak. Közben a piramisok eltérő jelöltekkel rendelkezhetnek, és blokkoló halmazt alkothatnak, amely elfogadja a „Készen állok a B2 háttéranyag commitálására” üzenetet, ami meggyőzi a csomópontot, hogy azt is fogadja el. Végül van egy időtúllépési mechanizmus, amely új köröket generál a szövetségi szavazáson új háttéranyagokkal, magasabb számlálókkal, ha a jelenlegi háttéranyagok elakadtak.
Miután a csomópont megtalálta a B háttéranyagot, amelyet megerősíthet késznek, közvetíti az „B háttéranyag commitálása” üzenetet. Ez a szavazás azt jelzi a piramisoknak, hogy a csomópont soha nem fog visszautasítani B-t. Valójában, ha B egy háttéranyag, a „ háttéranyag commitálása” a szavazásra való készülés teljes beleegyezését jelenti minden háttéranyagra a értékig. Ez a plusz jelentés segít más csomópontoknak utolérni a piramist a commitálással, ha ők még a protokoll korábbi szakaszaiban vannak.
Ebben a szakaszban fontos hangsúlyozni, hogy ezek aszinkron protokollok. Az, hogy egy csomópont szavazatokat küld a commitálásra, nem jelenti azt, hogy a társai is ezt teszik. Néhányuk még mindig szavazhat az előkészítési nyilatkozatokra, míg mások esetleg már externalizálták az értéket. Az SCP elmagyarázza, hogyan kell a csomópontnak kezelnie az egyes típusú peer-to-peer üzeneteket, függetlenül a fázisuktól.
Ha a "Kijelentem a kötelezettséget <N,C>" üzenetet nem lehet elfogadni vagy megerősíteni, akkor valószínű, hogy az <N+1,C> vagy az <N+2,C> üzenetet elfogadják vagy megerősítik – vagy bármely olyan hirdetményt, amely C értéket képvisel, nem pedig mást, mivel a csomópont már megígérte, hogy soha nem vonja vissza <N,C>. Amikor a csomópont a szavazatokat közvetíti a kötelezettséghez, akkor ez C vagy semmi lesz, attól függően, hogy a konszenzus meddig jut el. Azonban ez még nem elegendő a csomópont számára, hogy C-t externalizáljon. Néhány bizánci buli (amelyek a biztonságról alkotott feltételezéseink alapján nem képeznek kvórumot) hazudhat a csomópontnak. A valamilyen hirdetmény (vagy hirdetmények tartománya) elfogadása, majd megerősítése adja meg a csomópontnak a magabiztosságot, hogy végre externalizálja C-t.
A SCP szavazás szövetségi szavazással. Nem látható: bármikor beindulhat a visszaszámláló, növelve a hirdetményben a számlálót (és esetleg új kompozit születhet további jelöltekből).
És ennyi! Mihelyt a hálózat konszenzusra jutott, készen áll arra, hogy ezt újra és újra megtegye. A Stellar pénzforgalmi hálózatában ez körülbelül 5 másodpercenként történik: ez egy olyan teljesítmény, amely mind a biztonságot, mind a rugalmasságot megköveteli, amelyet az SCP garantál.
Az SCP ezt néhány forduló szövetségi szavazásra támaszkodva éri el. A szövetségi szavazás lehetővé tette a kvórumvágások koncepciója: olyan azonos rangú csomópontok halmazait, amelyeknek minden csomópont úgy döntött, hogy megbízik a saját (szubjektív) kvórumának részeként. Ez a konfiguráció azt jelenti, hogy még nyílt tagságú és bizánci csalásokkal teli hálózatban is el lehet jutni a konszenzusra.
További olvasmány
- Az SCP eredeti műszaki dokumentumát itt található , és a bevezetésének specifikációs tervezetét.
- A SCP protokoll eredeti szerzője, David Mazieres egyszerűen (de mégis technikailag) elmagyarázza azt .
- Lehet, hogy meglepődött, amikor nem találta a "bányászat" vagy a "munkavégzés bizonyítéka" kifejezéseket ebben a cikkben. Az SCP nem használ ilyen módszereket, de néhány más konszenzus algoritmus igen. Zayn Wiserpoon egy elérhető .
- egy egyszerű hálózatról, amely az SCP egy teljes fordulóján keresztül éri el a konszenzust.
- Azok számára, akik érdeklődnek az SCP megvalósításai iránt: lásd. a Stellar által használt fizetési hálózat, vagy , amelyet a SCP jobb megértése érdekében írtam.
Forrás: habr.com
