A Stellar konszenzus protokollt először ben írták le David Mazier 2015-ben. Ez egy „szövetségi bizánci megállapodási rendszer”, amely lehetővé teszi a decentralizált, vezető nélküli számítástechnikai hálózatok számára, hogy hatékonyan konszenzusra jussanak egy döntésről. A Stellar fizetési hálózat a Stellar Consensus Protocol (SCP) segítségével konzisztens tranzakciós előzményeket tart fenn, amely minden résztvevő számára látható.
A konszenzusos protokollokat nehéz megérteni. Az SCP egyszerűbb, mint a legtöbb, de továbbra is osztja ezt a hírnevet - részben annak a téves elképzelésnek köszönhetően, hogy a tudományos cikk első felének tárgyát képező "szövetségi szavazás" az SCP. De ez nem igaz! Ez csak egy fontos építőelem, amelyet a cikk második fele használ fel tényleges Csillagkonszenzus protokoll.
Ebben a cikkben röviden elmagyarázzuk, mi az a „megállapodások rendszere”, mitől lehet „bizánci” és miért „szövetségivé” a bizánci rendszer. Ezután elmagyarázzuk az SCP cikkben leírt egyesített szavazási eljárást, végül magát az SCP protokollt.
Megállapodási rendszerek
A megállapodások rendszere lehetővé teszi, hogy a résztvevők egy csoportja konszenzusra jusson egy témában, például, hogy mit rendeljen ebédre.
Az Interstellarnál saját étkezési megállapodási rendszert vezettünk be: azt rendeljük meg, amit az üzemeltetési vezetőnk, John mond. Ez egy egyszerű és hatékony megállapodási rendszer. Mindannyian megbízunk Johnban, és hisszük, hogy minden nap talál valami érdekeset és táplálóat.
De mi van akkor, ha John visszaél a bizalmunkkal? Egyedül el tudja dönteni, hogy mindannyian vegánok legyünk. Egy-két hét múlva valószínűleg megdöntjük, és átadjuk a hatalmat Erzsébetnek. De hirtelen megszereti az avokádót a szardellával, és úgy gondolja, hogy mindenkinek ilyennek kell lennie. A hatalom korrumpál. Érdemes tehát valami demokratikusabb módszert találni: valami módot arra, hogy a különböző preferenciákat figyelembe vegyék, miközben biztosítva az időszerű és egyértelmű eredményt, hogy végül senki ne rendeljen ebédet, vagy öt ember különböző rendeléseket adjon le, vagy a megbeszélést. elhúzódik az estébe.
Úgy tűnik, a megoldás egyszerű: tartson szavazást! De ez félrevezető benyomás. Ki fogja összegyűjteni a szavazólapokat és beszámolni az eredményekről? És miért kellene másoknak elhinniük, amit mond? Talán megtehetjük eleinte olyan vezetőre szavazzunk, akire bízunk a szavazás levezénylésében – de aki vezeti azt első szavazással? Mi van, ha nem tudunk megegyezni a vezetőben? Vagy mi van, ha megegyezünk, de ez a vezető elakad egy értekezleten, vagy betegszabadságra megy?
Hasonló problémák fordulnak elő az elosztott számítógépes hálózatokban. Minden résztvevőnek vagy csomópontnak meg kell egyeznie valamilyen döntésben, például kinek a sora frissít egy megosztott fájlt vagy távolít el egy feladatot a feldolgozási sorból. Egy kriptovaluta hálózatban a csomópontoknak többször is ki kell választaniuk, hogyan néz ki a teljes történet több lehetséges verzió közül, amelyek néha ütköznek. Ez a hálózati megállapodás biztosítékot nyújt a címzett számára, hogy az érme (a) érvényes (nem hamisított), és (b) még nincs máshol elköltött. Ez azt is biztosítja, hogy a jövőben el tudja költeni az érméket, mert az új címzett ugyanazon okokból ugyanazokat a garanciákat kapja.
Egy elosztott számítástechnikai hálózatban minden konszenzusos rendszernek hibatűrőnek kell lennie: konzisztens eredményeket kell produkálnia az olyan hibák ellenére, mint a lassú hivatkozások, a nem válaszoló csomópontok és a helytelen üzenetrendezés. bizánci A megállapodási rendszer emellett ellenáll a "bizánci" hibáknak is: olyan csomópontok, amelyek hamis információkat adnak meg, akár hiba miatt, akár a rendszer aláásására vagy valamilyen előny megszerzésére irányuló szándékos kísérlet miatt. A „bizánci” hibatűrés – az a képesség, hogy megbízunk egy csoportdöntésben még akkor is, ha egyes csoporttagok hazudnak, vagy egyébként nem követik a döntéshozatal szabályait – az ún. aki megpróbálta koordinálni a támadást. Anthony Stevensnél.
Vegyük fontolóra Alice kriptoérme tulajdonosát, akinek választania kell aközött, hogy finom fagylaltot vásárol Bobtól, vagy kifizeti Carol adósságát. Lehet, hogy Alice mindkettőjüket egyszerre akarja fizetni azzal, hogy csalárd módon elkölti ugyanazt az érmét. Ehhez meg kell győznie Bob számítógépét arról, hogy az érmét soha nem fizették ki Carolnak, és meg kell győznie Carol számítógépét arról, hogy az érmét soha nem fizették ki Bobnak. A bizánci megállapodási rendszer ezt gyakorlatilag lehetetlenné teszi, a többségi szabály ún határozatképesség. Egy ilyen hálózatban egy csomópont nem hajlandó áttérni a történelem egy adott változatára, amíg nem látja, hogy elegendő számú társ - egy kvórum - beleegyezik az ilyen átmenetbe. Ha ez megtörténik, akkor elég nagy szavazótömböt alkotnak ahhoz, hogy a fennmaradó hálózati csomópontokat rákényszerítsék, hogy egyetértsenek a döntésükkel. Alice rákényszeríthet néhány csomópontot, hogy hazudjanak a nevében, de ha a hálózat elég nagy, próbálkozását elnyomja a becsületes csomópontok szavazata.
Hány csomópont szükséges a határozatképességhez? Legalább többség, vagy inkább minősített többség a hibák és csalások elleni küzdelem érdekében. De a többség megszámlálásához ismernie kell a résztvevők teljes számát. Az Interstellar irodában vagy a kerületi választásokon ezeket a számokat könnyű megtudni. De ha a csoport egy lazán meghatározott hálózat, amelybe a csomópontok tetszés szerint beléphetnek és távozhatnak a központ jóváhagyása nélkül, akkor szövetségi bizánci megállapodási rendszer, amely képes a kvórumok meghatározására nem egy előre meghatározott csomópontlistából, hanem dinamikusan, egy adott időpontban a csomópontok állandóan változó és elkerülhetetlenül hiányos pillanatképéből.
Egy hatalmas hálózat egyetlen csomópontjának szemszögéből nézve lehetetlennek tűnhet kvórum létrehozása, de lehetséges. Egy ilyen határozatképesség akár a decentralizált szavazás eredményét is garantálhatja. Az SCP fehér könyv bemutatja, hogyan kell ezt megtenni az úgynevezett eljárással szövetségi szavazással.
Türelmetlen
A cikk további része az egyesített szavazást és a Stellar konszenzus protokollját írja le részletesebben. Ha nem érdeklik a részletek, itt egy általános áttekintés a folyamatról.
- A csomópontok szövetségi szavazási köröket folytatnak a „jelöltekről”. A szövetségi szavazás a következőket jelenti:
- A csomópont valamilyen kijelentésre szavaz, például: „Javaslom a V értékét”;
- A csomópont addig hallgatja a társak hangját, amíg meg nem találja azt, amelyik képes "fogadni";
- A csomópont „kvórumot” keres ehhez az állításhoz. A határozatképesség „megerősíti” a jelöltet.
- Amint egy csomópont meg tud erősíteni egy vagy több jelöltet, megkísérli "előkészíteni" a "szavazást" több fordulós összevont szavazással.
- Amint egy csomópont ellenőrizni tudja, hogy a szavazólap készen áll-e, megkísérli lekötni azt még több egyesített szavazási körön keresztül.
- Ha egy csomópont meg tudja erősíteni egy szavazás elfogadását, akkor "externalizálhatja" a szavazás értékét, ha azt konszenzusos eredményként használja.
Ezek a lépések az egyesített szavazás több fordulóját foglalják magukban, amelyek együttesen egy SCP-kört alkotnak. Nézzük meg közelebbről, mi történik az egyes lépéseknél.
Összevont szavazás
Az összevont szavazás egy eljárás annak meghatározására, hogy a hálózat egyetért-e egy javaslattal. A szavazási körben minden csomópontnak választania kell egyet a potenciálisan sok lehetséges érték közül. Ezt nem teheti meg, hacsak nem biztos abban, hogy a hálózat többi csomópontja nem választ más eredményt. Ennek biztosítása érdekében a csomópontok üzenetek özönét váltják oda-vissza, hogy mindenki megerősítettHogy határozatképesség csomós vesz ugyanaz döntés. A szakasz további része elmagyarázza az ebben a mondatban szereplő kifejezéseket, és azt, hogy a teljes eljárás hogyan zajlik.
Kvórumok és kvórumszeletek
Kezdjük a határozatképesség meghatározásával. Ahogy fentebb tárgyaltuk, egy dinamikus tagsággal rendelkező decentralizált hálózatban nem lehet előre tudni a csomópontok számát, és így azt, hogy hányra van szükség a többség számára. Az összevont szavazás egy új ötlet bevezetésével oldja meg ezt a problémát határozatképesség csökkent (quorum slice): Egy kis csoport, amelyben a csomópont megbízik a szavazási állapot információinak kommunikálásában a hálózat többi részével. Minden csomópont meghatározza a saját kvórumszeletét (amelynek de facto tagjává válik).
A határozatképesség megalakítása a határozatképesség megszüntetésével kezdődik. Minden csomóponthoz hozzáadódnak a kivágott csomópontok. Ezután a szelet kifejezések hozzáadódnak ezeket a csomópontokat stb. Ahogy folytatja, egyre több csomópont van, amelyet nem tud hozzáadni, mert már benne vannak a szeletben. Ha nincs több új hozzáadható csomópont, a folyamat leáll: a kezdeti csomópont kvórumszeletének „tranzitív lezárásával” határozatképességet hoztunk létre.
Egy adott csomópontból határozatképesség keresése...
... a szelet tagjainak hozzáadása...
...akkor hozzáadjuk ezeknek a csomópontoknak a szelet tagjait.
Addig folytatjuk, amíg már nem lesz hozzáadható csomópont.
Már nincs hozzáadható csomópont. Ez határozatképes.
Valójában minden csomópont több szeletben is megjelenhet. A határozatképesség létrehozásához csak az egyik szeletet jelölje ki, és adjon hozzá tagokat; majd válasszon ki egy szeletet az egyes tagokhoz, és adjon hozzá tagokat azt vágni és így tovább. Ez azt jelenti, hogy minden csomópont számos lehetséges kvórum tagja.
Minden lépésben csak egy kvórumszeletet válasszon.
Egy lehetséges határozatképesség. Vagy alternatíva...
...válasszon más szeleteket...
…(ha lehetséges)…
... újabb határozatképességet hoz létre.
Honnan tudja egy csomópont, hogy a többi csomópont mely szeleteiben van? Ugyanúgy, mint a többi csomópontra vonatkozó egyéb információk: az egyes csomópontok által a hálózatba sugárzott átvitelekből, amikor a szavazati állapot megváltozik. Minden adatszórás tartalmaz információkat a küldő csomópont szeleteiről. Az SCP fehér könyv nem határoz meg kommunikációs mechanizmust. A megvalósítások általában használnak az üzenetek hálózaton belüli garantált sugárzásához.
Emlékezzünk vissza, hogy a nem szövetségi bizánci megállapodási rendszerben a határozatképességet az összes csomópont többségeként határozzák meg. A bizánci megállapodásrendszert abból a kérdésből tervezték, hogy hány tisztességtelen csomópontot tud elviselni a rendszer? Egy N csomópontból álló rendszerben, amelyet f meghibásodás túlélésére terveztek, egy csomópontnak képesnek kell lennie arra, hogy előrehaladást érjen el, ha visszajelzést kap N-f partnertől, mivel f közülük nem működik. De miután megkaptuk a választ N−f partnertől, feltételezhetjük, hogy minden f partner (amelytől a csomópont nem kapott választ) valójában őszinte. Így az N−f partner közül f (amelytől a válasz érkezett) rosszindulatú. Ahhoz, hogy a csomópontok ugyanarra a konszenzusra jussanak, a fennmaradó csomópontok többségének becsületesnek kell lennie, azaz N−f-nek nagyobbnak kell lennie 2f-nél vagy N > 3f-nél. Tehát általában egy f hiba túlélésére tervezett rendszer összesen N=3f+1 csomóponttal és 2f+1 kvórummérettel rendelkezik. Amint egy ajánlat átlépi a határozatképességi küszöböt, a hálózat többi tagja meg van győződve arról, hogy a versengő ajánlatok kudarcot vallanak. Így konvergál a hálózat az eredményhez.
De egy szövetségi bizánci megállapodási rendszerben nemhogy nem lehet többség (mert senki sem tudja a hálózat teljes méretét), de a többség fogalma teljesen használhatatlan! Ha a rendszerben való tagság nyitott, akkor valaki úgy tud többséget szerezni, ha végrehajt egy úgynevezett Sybil-támadást: ismételten csatlakozik a hálózathoz több csomóponton keresztül. Miért nevezhető tehát tranzitív szeletzárás határozatképesség, és hogyan képes elnyomni a versengő ajánlatokat?
Technikailag semmiképp! Képzeljünk el egy hat csomópontból álló hálózatot, ahol két hármas van elszigetelve egymás kvórumszeleteiben. Az első alcsoport olyan döntést hozhat, amelyről a második soha nem fog hallani, és fordítva. Ez a hálózat semmilyen módon nem juthat konszenzusra (kivéve véletlenül).
Ezért az SCP megköveteli, hogy az összevont szavazáshoz (és ahhoz, hogy a dolgozat fontos tételei érvényesüljenek), a hálózatnak rendelkeznie kell egy ún. a határozatképességek metszéspontja. Az ezzel a tulajdonsággal rendelkező hálózatban bármely két létrehozható kvórum legalább egy csomópontban mindig átfedi egymást. A hálózat uralkodó hangulatának meghatározásához ez annyit jelent, mint a többség. Ez intuitív módon azt jelenti, hogy ha bármelyik határozatképesség egyetért az X állítással, akkor egyetlen másik határozatképesség sem egyezhet bele semmi mással, mert szükségszerűen tartalmazni fog egy csomópontot az első határozatképességből, amely már szavazott X-re.
Ha a hálózatban a kvórumok metszéspontja van...
...akkor bármelyik két kvórumot felállíthat...
...mindig keresztezni fog.
(Természetesen előfordulhat, hogy az átfedő csomópontok bizánci hazugságúak vagy más módon rosszak. Ebben az esetben a kvórum metszéspontja egyáltalán nem segíti a hálózat egyetértését. Emiatt az SCP fehér könyvében szereplő eredmények közül sok az explicit feltevések, például, hogy mi maradt a hálózati kvórum átlépésében még a rossz csomópontok eltávolítása után is. Az egyszerűség kedvéért hagyjuk ezeket a feltételezéseket beleértett a cikk további részében).
Ésszerűtlennek tűnhet annak elvárása, hogy független csomópontok hálózatában megbízható kvórumátlépés lehetséges. De ennek két oka van.
Az első ok maga az Internet létezése. Az internet tökéletes példája a egymást metsző kvórumokkal rendelkező, független csomópontok hálózatának. Az interneten a legtöbb csomópont csak néhány másik helyi csomóponthoz csatlakozik, de ezek a kis halmazok eléggé átfedik egymást ahhoz, hogy minden csomópont elérhető legyen az összes többi csomópontból valamilyen útvonalon.
A második ok a Stellar fizetési hálózatra jellemző (az SCP leggyakoribb használata). A Stellar hálózaton minden eszköznek van kibocsátója, és a Stellar irányelvei megkövetelik, hogy minden kibocsátó jelöljön ki egy vagy több csomópontot a hálózaton a beváltási kérelmek feldolgozásához. Az Ön érdeke, hogy ezeket a csomópontokat közvetlenül vagy közvetve felvegye a kvórumszeletekre minden olyan elemhez, amely érdekli. Az adott eszköz iránt érdeklődő összes csomópont kvórumai legalább ezeknél a beváltási csomópontoknál átfedik egymást. A több eszköz iránt érdeklődő csomópontok a megfelelő kibocsátók összes visszaváltási csomópontját belefoglalják a kvórumszeleteikbe, és megpróbálják az összes eszközt összevonni. Ezen túlmenően minden olyan eszköz, amely nincs ilyen módon összekapcsolva másokkal a hálózaton, és nem szabad csatlakoztatni - ez úgy van kialakítva, hogy ne legyen határozatképességi átfedés ebben a hálózatban (például a dollárzónából származó bankok néha eurózónából és a peso zónából származó bankokkal akarnak kereskedni, így ugyanabban a hálózatban vannak, de egyik sem közülük a baseballkártyákat árusító gyermekek külön hálózatával foglalkoznak).
Természetesen, elvárás határozatképességi keresztezés nem garancia. Más bizánci megállapodási rendszerek bonyolultságuk nagy részét a kvórumok garantálásának köszönhetik. Az SCP fontos újítása, hogy magától a konszenzusalgoritmustól eltávolítja a kvórumok létrehozásának felelősségét, és az alkalmazás szintjére hozza azt. Így, bár a szövetségi szavazás elég általános ahhoz, hogy bármilyen kérdésről szavazni lehessen, megbízhatósága valójában kritikusan függ e jelentések tágabb jelentésétől. Előfordulhat, hogy egyes feltételezett felhasználások nem olyan kedvezőek a jól összekapcsolt hálózatok létrehozásához, mint mások.
Szavazás, elfogadás és megerősítés
Az összevont szavazási körben egy csomópont adott esetben elkezd szavazni valamilyen V értékre. Ez azt jelenti, hogy üzenetet küld a hálózatnak: „N csomópont vagyok, a kvórumszeletem Q, és V-re szavazok.” Amikor egy csomópont így szavaz, azt ígéri, hogy soha nem szavazott V ellen, és nem is fog.
A peer-to-peer adásoknál minden csomópont látja, hogyan szavaznak a többiek. Ha egy csomópont elegendő mennyiségű üzenetet gyűjtött össze, nyomon tudja követni a kvórumszeleteket, és megpróbálja megtalálni a kvórumokat. Ha azt látja, hogy a V-re is szavazó társak határozatképesek, továbbléphet örökbefogadás V, és sugározza ezt az új üzenetet a hálózatnak: „N node vagyok, a kvórumszeletem Q, és elfogadom a V-t.” Az elfogadás erősebb garanciát nyújt, mint az egyszerű szavazás. Amikor egy csomópont a V-re szavaz, soha nem szavazhat más opciókra. De ha egy csomópont elfogadja a V-t, akkor a hálózat egyik csomópontja sem fogja elfogadni a másik lehetőséget (az SCP fehér könyv 8. tétele ezt bizonyítja).
Természetesen nagy a valószínűsége annak, hogy nem lesz azonnal határozatképes az V-vel megegyező csomópontok száma. Más csomópontok más értékek mellett is szavazhatnak. De van egy másik módja annak, hogy egy csomópont az egyszerű szavazásról az elfogadás felé haladjon. N elfogadhat más értéket W-re, még akkor is, ha nem szavazott rá, és akkor is, ha nem látja határozatképességét. Ha úgy dönt, hogy megváltoztatja szavazatát, nézze meg blokkoló készlet csomópontok, amelyek elfogadták a W-t. A blokkolókészlet egy csomópont az N kvórumszeletekből. Ahogy a neve is sugallja, Blokk bármilyen más jelentése. Ha egy ilyen halmaz összes csomópontja elfogadja a W-t, akkor (a 8. tétel szerint) soha nem lesz lehetséges olyan határozatképességet létrehozni, amely eltérő értéket vesz fel, és ezért N számára is biztonságos W elfogadása.
N csomópont három kvórumszelettel.
A BDF egy blokkolókészlet N számára: tartalmaz egy csomópontot az N minden szeletéből.
A BE egyben az N blokkoló halmaza is, mivel E az N két szeletében jelenik meg.
De a blokkoló halmaz nem határozatképes. Túl könnyű lenne rávenni az N csomópontot, hogy elfogadja a kívánt értéket, ha elég lenne csak egy csomópontot feltörni N minden egyes szeletében. Ezért az érték elfogadása nem jelenti a szavazás végét. Ehelyett N-nek meg kell erősítenie az értéket, azaz látnia kell az azt elfogadó csomópontok kvórumát. Ha idáig eljut, akkor, amint azt az SCP fehér könyv bizonyítja (a 11. tételben), a hálózat többi része is megerősíti végül ugyanazt az értéket, így N egy bizonyos értékkel fejezi be az összevont szavazást.
Összevont szavazás.
A szavazás, az elfogadás és a megerősítés folyamata az egyesített szavazás egy teljes körét jelenti. A Stellar konszenzus protokoll számos ilyen kört kombinál, hogy egy teljes konszenzus rendszert hozzon létre.
Csillagkonszenzus Protokoll
A konszenzusrendszer két legfontosabb tulajdonsága a − biztonság и túlélhetőség. A konszenzusos algoritmus „biztonságos”, ha soha nem tud különböző eredményeket adni a különböző résztvevőknek (Bob történelemmásolata soha nem mond ellent Carolnak). Az „élhetőség” azt jelenti, hogy az algoritmus mindig eredményt hoz, vagyis nem akad el.
A szövetségi szavazási eljárás leírása biztonságos abban az értelemben, hogy ha egy csomópont megerősíti V értékét, akkor egyetlen másik csomópont sem fogja megerősíteni a másik értéket. De a „nem erősít meg egy másik jelentést” nem jelenti azt, hogy feltétlenül megerősít valamit. A résztvevők annyi különböző értékre szavazhatnak, hogy semmi sem éri el az elfogadási küszöböt. Ez azt jelenti, hogy a szövetségi szavazásban nincs túlélhetőség.
A Stellar konszenzus protokoll egyesített szavazást alkalmaz oly módon, hogy garantálja a biztonságot és a túlélést. (Az SCP biztonsági és túlélési garanciáinak van elméleti határa. A tervezés nagyon erős biztonsági garanciát választ, egy kis túlélési mérséklést feláldozva, de elegendő időt adva nagy valószínűséggel konszenzus születik.) Dióhéjban, az ötlet az, hogy több összevont szavazás legyen több értékre, amíg az egyik át nem jut az alább leírt SCP-szavazási fázisokon.
Az értékek, amelyekkel kapcsolatban az SCP konszenzust keres, lehetnek tranzakciós előzmények, ebédrendelés vagy valami más, de fontos megjegyezni, hogy ezek nem azok az értékek, amelyeket elfogadnak vagy megerősítenek. Ehelyett a szövetségi szavazás szerint történik kijelentéseket ezekről az értékekről.
A szövetségi szavazás első fordulóira a következő napon kerül sor jelölési szakasz (jelölési fázis), olyan állítások halmazán, mint az „Én jelölöm V-t”, esetleg V sok különböző értékére. A jelölés célja egy vagy több olyan állítás megtalálása, amely elfogadáson és megerősítésen megy keresztül.
Az ellenőrizhető jelöltek megtalálása után az SCP a szavazási szakaszba lép, ahol a cél egy bizonyos értesítő (vagyis egy konténer a javasolt értékhez) és egy határozatképesség, amely nyilatkozhat elkövetni érte (commit). Ha egy szavazás határozatképes, akkor annak értékét konszenzusként fogadják el. Mielőtt azonban egy csomópont szavazhatna egy szavazási kötelezettségre, először meg kell erősítenie törlés minden alacsonyabb ellenértékkel rendelkező szavazólapot. Ezek a lépések – a szavazások törlése, hogy megtaláljuk azt, amelyik elkötelezhető – több körös szövetségi szavazást foglal magában a több szavazólapon történő követelésről.
A következő szakaszok részletesebben ismertetik a jelölést és a szavazást.
Jelölés
A jelölési szakasz elején minden csomópont spontán kiválaszthat egy értéket V-hez, és szavazhat az „V-t jelölök” kijelentésre. A cél ebben a szakaszban az, hogy egyesített szavazással megerősítsék valamilyen érték jelölését.
Talán elég csomó csomópont szavaz elég különböző javaslatokra ahhoz, hogy egyetlen jelölés se érje el az elfogadási küszöböt. Ezért a csomópontok amellett, hogy saját jelölési szavazataikat sugározzák, „tükrözik” társaik jelölését. A visszhang azt jelenti, hogy ha egy csomópont az V jelölésre szavaz, de üzenetet lát a szomszédtól, aki W jelölésre szavaz, akkor most V-re és W-re is szavaz. (Nem minden társszavazat visszhangzik a jelölés során, mert ez a jelölés robbanásához vezethet. Különböző jelöltek. Az SCP tartalmaz egy mechanizmust ezeknek a szavazatoknak a szabályozására. Röviden, van egy képlet a partner „prioritása” meghatározására egy csomópont szemszögéből, és csak a magas prioritású csomópontok szavazatai jelennek meg. Minél hosszabb a jelölés minél alacsonyabb a küszöb, így a csomópont kibővíti azon társak halmazát, akiknek a szavazatait tükrözni fogja. A prioritási képlet egyik bemeneteként tartalmazza a résszámot, így az egyik rés magas prioritású partnere alacsony prioritású partner lehet másik, és fordítva).
Koncepcionálisan a jelölés párhuzamos, mind a V, mind a W külön szövetségi szavazat, mindegyik egyénileg képes elfogadást vagy megerősítést elérni. A gyakorlatban az SCP protokoll üzenetei ezeket az egyes szavazatokat egybe csomagolják.
Bár V jelölésére szavazni egy ígéret, hogy soha nem szavazunk V jelölése ellen, a pályázati szinten – jelen esetben az SCP-n – dől el, hogy mit jelent az „ellen”. Az SCP nem lát olyan állítást, amely ellentmond az "X-et jelölök" szavazatnak, vagyis nincs "X jelölése ellen vagyok" üzenet, így a csomópont bármilyen érték jelölésére szavazhat. Ezen jelölések közül sok nem megy sehova, de végül a csomópont képes lesz elfogadni vagy megerősíteni egy vagy több értéket. Amint egy jelöltet megerősítenek, azzá válik jelölt.
SCP-jelölés egyesített szavazással. Számos „B” érték szerepelhet, amelyeket a társak terjesztenek elő, és a csomópont „visszatükrözi”.
A jelölések több jelöltet eredményezhetnek. Ezért az SCP megköveteli az alkalmazási rétegtől, hogy biztosítson valamilyen módszert a jelöltek egyesítésére összetett (összetett). A csatlakozási mód bármi lehet. A lényeg az, hogy ha ez a módszer determinisztikus, akkor minden csomópont ugyanazokat a jelölteket fogja kombinálni. Egy ebédszavazási rendszerben az „egyesítés” egyszerűen azt jelenti, hogy két jelölt közül az egyiket elutasítják. (De determinisztikus módon: minden csomópontnak ugyanazt az értéket kell kiválasztania a visszaállításhoz. Például a korábbi kijelölést ábécé sorrendben). A Stellar fizetési hálózaton, ahol a tranzakciók előzményeiről szavaznak, két javasolt jelölt összevonása magában foglalja a bennük lévő tranzakciók és a két időbélyeg közül a legutóbbi egyesítését.
Az SCP tanulmány bizonyítja (12. tétel), hogy a kiterjesztési fázis végére a hálózat végül egyetlen kompozittá konvergál. De van egy probléma: az összevont szavazás egy aszinkron protokoll (mint az SCP). Más szóval, a csomópontokat nem az idő koordinálja, hanem csak az általuk küldött üzenetek. A csomópont szempontjából nem világos, hogy mikor vége lett kiterjesztési szakasz. És bár az összes csomópont végül ugyanahhoz az összetetthez érkezik, különböző útvonalakat járhatnak be, és különböző összetett jelölteket hozhatnak létre, és soha nem tudják megmondani, melyik a végső.
De normális. A jelölés csak felkészülés. A fő dolog a jelöltek számának korlátozása a konszenzus elérése érdekében, ami a folyamat során megtörténik szavazás (szavazás).
Futás
Bulletin egy pár , ahol a számláló egy 1-gyel kezdődő egész szám, az érték pedig egy jelölt a jelölési szakaszból. Ez lehet egy csomópont saját jelöltje vagy egy szomszédos csomópont által az adott csomópont által elfogadott jelölt. Nagyjából elmondható, hogy a szavazás azt jelenti, hogy ismételt kísérleteket tesznek arra, hogy a hálózatot arra kényszerítsék, hogy konszenzusra jussanak valamelyik jelöltről bizonyos szavazáson azáltal, hogy potenciálisan sok szövetségi szavazatot tartanak a szavazólapokon. A szavazólapokon lévő számlálók nyomon követik a kísérleteket, és a magasabb számlálószámú szavazatok elsőbbséget élveznek az alacsonyabb számlálószámmal rendelkezőkkel szemben. Ha a hírlevél elakad, új szavazás kezdődik, most a szavazólapon .
Fontos különbséget tenni jelentését (például mi legyen az ebédrendelés: pizza vagy saláták), hírlevelek (ellenérték pár) és nyilatkozatok a szavazólapokról. Az SCP-forduló több szövetségi szavazási fordulót is tartalmaz, különösen a következő nyilatkozatokról:
- „Készen állok a B szavazásra” és
- "Bejelentem a B szavazás végrehajtását"
Egy adott csomópont szemszögéből a konszenzus akkor érhető el, ha talál egy B szavazólapot, amelyre meg tudja erősíteni (vagyis határozatképesnek találja) a „B szavazást követek el” kijelentést. Innentől kezdve nyugodtan lehet a B-ben megadott érték szerint cselekedni - például ezt a rendelést ebédre leadni. Ez az úgynevezett külsővé tétele jelentések. A szavazás elfogadásának megerősítése után egy csomópont biztos lehet benne, hogy bármely másik csomópont külsőleg kiadta ugyanazt az értéket, vagy a jövőben ezt fogja tenni.
Bár sok szövetségi szavazást koncepcionálisan sok különböző szavazólapra vonatkozó követelésekre hajtanak végre, ezek nem váltanak ki annyi üzenetet, mivel minden üzenet több szavazólapot tartalmaz. Az egyik üzenet tehát egyszerre több összevont szavazás állapotát hirdeti, például: „Elfogadom a szavazatokat előtt "
Mit jelent a „felkészült” és „elkötelezett” kifejezés?
Egy csomópont akkor szavaz a szavazás végrehajtására, ha biztos abban, hogy más csomópontok nem fognak eltérő értékű szavazást végrehajtani. Ennek meggyőzése a pályázat elkészítésének célja. Az a szavazás, amelyen az áll, hogy „Kész vagyok a B szavazólap letételére” azt ígéri, hogy soha nem fogunk B-nél kisebb, azaz kisebb szavazatszámmal szavazni (az SCP megköveteli, hogy a szavazatok értékei bizonyos sorrendben legyenek. Így hírlevél Kevésbé , ha N1
Miért azt jelenti, hogy a „készen állok a B szavazólap letételére” azt, hogy „megígérem, hogy soha nem kötök le B-nél kisebb szavazatokat”? Mert az SCP a megszakítást a commit ellentéteként határozza meg. A szavazás előkészítésére irányuló szavazás egyben más szavazólapok kizárására is vonatkozik, és amint azt korábban tárgyaltuk, egy dolog mellett szavazni ígéret, hogy soha nem szavazunk ellene.
A véglegesítés sugárzása előtt a csomópontnak először meg kell találnia egy közleményt, amelyet meg tud erősíteni az előkészítésről. Más szóval, összevont szavazást hajt végre a „Kész vagyok a B szavazás letételére” témában, esetleg sok különböző szavazólapon, amíg meg nem találja azt, amelyik határozatképes.
Honnan származnak a szavazást előkészítő szavazólapok? Először a csomópont sugározza az előkészületeket, hogy az <1,C>-re szavazzon, ahol C a jelölési szakaszban előállított összetett jelölt. A jelölések azonban még a szavazásra való felkészülés megkezdése után is azt eredményezhetik, hogy további jelöltek új szavazólapokká válhatnak. Eközben a társaknak különböző jelöltjeik lehetnek, és létrehozhatnak egy blokkolókészletet, amely elfogadja a „Készen állok a B2-es szavazást”, ami meggyőzi a csomópontot, hogy elfogadja azt. Végül van egy időtúllépési mechanizmus, amely új, egyesített szavazási köröket generál magasabb számlálószámú új szavazólapokon, ha az aktuális szavazólapok elakadnak.
Amint a csomópont talál egy B szavazólapot, amelyről meg tudja erősíteni, hogy felkészült, új üzenetet sugároz: „Végezze el a B szavazást”. Ez a szavazás azt mondja a társaknak, hogy a csomópont soha nem adja fel B-t. Valójában, ha B szavazás , majd a „Végy szavazást " azt jelenti, hogy a szavazás feltétel nélküli beleegyezését jelenti minden egyes szavazólap készenlétére <∞, s>-re. Ez az extra érték segít a többi partnernek felzárkózni a véglegesítési partnerhez, ha még a protokoll korábbi szakaszaiban vannak.
Ebben a szakaszban érdemes még egyszer hangsúlyozni, hogy ezek aszinkron protokollok. Csak azért, mert az egyik csomópont pozitív szavazatot küld egy véglegesítésre, nem jelenti azt, hogy a többi csomópont is ezt teszi. Lehet, hogy egy részük még a szavazásra készülő nyilatkozatokról szavaz, mások pedig már külsőre vették a jelentést. Az SCP elmagyarázza, hogyan kell egy csomópontnak kezelnie az egyes típusú peer üzeneteket, függetlenül azok fázisától.
Ha a „Bejelentettem a kötelezettségvállalást » nem fogadható vagy nem erősíthető meg, vagyis az üzenet elfogadásának vagy megerősítésének valószínűsége vagy - vagy mindenesetre bármilyen C értékű szavazólapot, és nem mást, mivel a csomópont már megígérte, hogy soha nem törli . Mire egy csomópont szavazatokat sugároz egy commitra, az C lesz vagy semmi, attól függően, hogy milyen messzire megy a konszenzus. Ez azonban még nem elég ahhoz, hogy a csomópont külsővé tegye a C-t. Néhány bizánci társ (amelyek biztonsági feltevéseink alapján kevesebb, mint a kvórum) hazudhatnak a csomópontnak. Valamely szavazólap (vagy szavazólap-tartomány) elfogadása, majd megerősítése az, ami a csomópontnak önbizalmat ad ahhoz, hogy végre külsődjön C.
SCP szavazás szövetségi szavazással. Nem látható: Az időzítő bármikor kikapcsolhat, növelve a szavazatszámot (és esetleg további jelölt jelöltek új összetételét állítva elő).
És ez minden! Ha a hálózat konszenzusra jutott, újra és újra készen áll erre. A Stellar fizetési hálózaton ez körülbelül 5 másodpercenként történik: ez a bravúr megköveteli az SCP által garantált biztonságot és túlélést.
Az SCP ezt úgy érheti el, hogy több fordulós összevont szavazásra támaszkodik. Az egyesített szavazást a kvórumszeletek koncepciója teszi lehetővé: olyan társcsoportok, amelyekben minden csomópont úgy döntött, hogy megbízik a (szubjektív) kvóruma részeként. Ez a konfiguráció azt jelenti, hogy a nyílt tagsággal és bizánci megtévesztésekkel működő hálózatban is konszenzus születhet.
További irodalom
- Az eredeti SCP fehér papír megtalálható És végrehajtására vonatkozó előírások tervezetét.
- Az SCP protokoll eredeti szerzője, David Mazier leegyszerűsített (de mégis technikai) módon magyarázza el. .
- Meglepődhetett, hogy ebben a cikkben nem találja a „bányászat” vagy a „munka igazolása” kifejezéseket. Az SCP nem használja ezeket a módszereket, de néhány más konszenzusos algoritmus igen. Zane Witherspoon hozzáférhetővé írta .
- egy egyszerű hálózat, amely egy teljes SCP-körben konszenzusra jut.
- Az SCP implementációk iránt érdeklődő olvasóknak: lásd , a Stellar fizetési hálózat által használt, ill , amelyet az SCP jobb megértése érdekében írtam.
Forrás: will.com