Protokol konsenzu Stellar bol prvýkrát opísaný v Davida Mazièra v roku 2015. Ide o „federatívny systém byzantského súhlasu“, ktorý umožňuje decentralizovaným výpočtovým sieťam bez lídrov efektívne dosahovať konsenzus o akomkoľvek rozhodnutí. Platobná sieť Stellar používa Stellar Consensus Protocol (SCP) na vedenie zosúladeného histórie transakcií, ktorú vidia všetci účastníci.
Považuje sa, že protokoly konsenzu sú ťažko pochopiteľné. SCP je jednoduchší ako väčšina z nich, ale predsa len zdieľa túto povesť — čiastočne kvôli mylnej predstave, že „federatívne hlasovanie“, ktorému je venovaná prvá polovica vedeckého článku, je SCP. Nie je to tak! Je to len dôležitá súčiastka, ktorá sa v druhej polovici článku používa na vytvorenie skutočného protokolu konsenzu Stellar.
V tomto článku stručne vysvetlíme, čo je to „systém súhlasu“, čo môže urobiť jeho „byzantským“ a prečo robiť byzantský systém „federatívnym“. Potom vysvetlíme federatívny hlasovací postup, ktorý je opísaný v článku o SCP, a nakoniec vysvetlíme samotný protokol SCP.
Systémy súhlasu
Systém súhlasu umožňuje skupine účastníkov dosiahnuť konsenzus o určitej téme, napríklad čo si objednať na obed.
My v spoločnosti Interstellar sme implementovali vlastný systém obedového súhlasu: objednávame to, čo hovorí náš operačný manažér John. Je to jednoduchý a efektívny súhlasový systém. Všetci dôverujeme Johnovi a veríme, že každý deň nájde niečo zaujímavé a výživné.
Ale čo ak John zneužije našu dôveru? Môže jednostranne rozhodnúť, že všetci musíme byť vegáni. O týždeň alebo dva možno zvrhneme ho a odovzdáme moc Elisabeth. Ale zrazu ona miluje avokádo s ančovičkami a myslí si, že všetci by mali byť také. Moc kazí. Preto je lepšie nájsť nejakú demokratickejšiu metódu: nejaký spôsob, ako zabezpečiť, že sa zohľadnia rôzne preferencie, pričom zabezpečíme včasný a jednoznačný výsledok, aby sa nestalo, že nikto neobjedná obed alebo piati ľudia umiestnia rôzne objednávky, alebo diskusia potrvá až do večera.
Na prvý pohľad sa zdá, že riešenie je jednoduché: uskutočniť hlasovanie! Ale to je klamlivý dojem. Kto bude zbierať hlasovacie lístky a oznamovať výsledky? A prečo by mali ostatní veriť tomu, čo povie? Možno môžeme najprv hlasovať za lídra, ktorému dôverujeme, aby riadil hlasovanie — ale kto bude viesť toto prvým hlasovanie? Čo ak sa nedokážeme dohodnúť na lídrovi? Alebo ak sa dohodneme a tento líder uviazne na stretnutí alebo ochorie?
Podobné problémy sa vyskytujú v distribuovaných počítačových sieťach. Všetky účastníci alebo uzly musia dosiahnuť nejaké rozhodnutie, napríklad, kto má aktualizovať spoločný súbor alebo prevziať úlohu z fronty spracovania. V kryptomenovej sieti sa uzly opakovane musia rozhodnúť, ako vyzerá úplná história z niekoľkých možných verzií, ktoré niekedy konfliktujú. Toto sieťové dohodnutie zaručuje prijímateľovi, že minca je (a) platná (nie falošná) a (b) ešte nebola utratená na inom mieste. Taktiež zaručuje, že ju môže v budúcnosti utratiť, pretože nový prijímateľ bude mať rovnaké záruky z tých istých dôvodov.
Akýkoľvek systém dohovoru v distribuovanej výpočtovej sieti musí byť odolný voči poruchám: mal by poskytovať konzistentné výsledky napriek chybám, ako sú pomalé komunikačné linky, nereagujúce uzly a nesprávny poradie správ. Byzantský systém dohovoru je navyše odolný voči „byzantským“ chybám: uzlom, ktoré poskytujú nepravdivé informácie, či už z dôvodu chyby alebo z úmyselného pokusu podkopať systém alebo získať nejakú výhodu. „Byzantská“ odolnosť voči poruchám — schopnosť dôverovať skupinovému rozhodnutiu, aj keď niektorí členovia skupiny môžu klamať alebo inak sa riadiť pravidlami rozhodovania — získala názov podľa , ktorí sa snažili koordinovať útok. má Anthony Stevens.
Zvážme majiteľa kryptomeny Alisu, ktorá sa musí rozhodnúť medzi nákupom chutnej zmrzliny od Boba a splatením dlhu Carol. Možno chce Alisa zaplatiť obom naraz, podvodne minúc jednu a tú istú mincu. Na to musí presvedčiť Bobov počítač, že minca nikdy nebola vyplatená Carol, a presvedčiť Carolin počítač, že minca nikdy nebola vyplatená Bobovi. Byzantský systém dohôd to v podstate znemožňuje, pomocou formy pravidla väčšiny nazývanej kvórum. Uzol v takej sieti sa vzdáva prechodu na určitú verziu histórie, kým nevidí, že dostatočný počet rovnocenných uzlov – kvórum – súhlasí s takýmto prechodom. Hneď ako k tomu dôjde, vytvoria dostatočne veľký výberový blok, aby prinútili zostávajúce uzly siete súhlasiť s ich rozhodnutím. Alisa môže donútiť niektoré uzly klamať v jej mene, ale ak je sieť dosť veľká, jej pokus bude potlačený hlasmi čestných uzlov.
Koľko uzlov je potrebných na kvórum? Minimálne väčšina, presnejšie kvalifikovaná väčšina na boj proti chybám a podvodom. Ale aby ste spočítali väčšinu, musíte poznať celkový počet účastníkov. V kancelárii Interstellar alebo na okresných voľbách sú tieto čísla ľahko zistiteľné. Ale ak je vaša skupina slabodefinovaná sieť, do ktorej uzly môžu vstupovať a odchádzať podľa svojho želania bez súhlasu centra, potom je potrebný federálny systém byzantského dohody, schopný určovať kvórum nie z vopred určeného zoznamu uzlov, ale dynamicky, z neustále sa meniacich a nevyhnutne neúplných snímok uzlov v určitom okamihu.
Môže sa zdať nemožné vytvoriť kvórum z pohľadu jedného uzla v rozsiahlej sieti, ale je to možné. Také kvórum môže dokonca zaručiť výsledky decentralizovaného hlasovania. Technický dokument SCP ukazuje, ako to dosiahnuť pomocou postupu nazývaného federálne hlasovanie.
Pre netrpezlivých
Zvyšok článku podrobnejšie popisuje federálne hlasovanie a konsenzuálny protokol Stellar. Ak vás podrobnosti nezaujímajú, tu je všeobecný prehľad procesu.
- Uzly vykonávajú kolá federálneho hlasovania o „nominantoch“. Kolo federálneho hlasovania znamená:
- Uzol hlasuje za nejaké tvrdenie, napríklad „Navrhujem hodnotu V“;
- Uzol počúva hlasy párov, kým nenájde ten, ktorý môže „prijať“;
- Uzol hľadá „kvorum“ pre toto tvrdenie. Kvorum „potvrdzuje“ nominanta.
- Akonáhle uzol môže potvrdiť jedného alebo viacerých nominantov, snaží sa „pripraviť“ „hlasovací lístok“ cez niekoľko kôl federálneho hlasovania.
- Akonáhle uzol je schopný overiť pripravenosť hlasovacieho lístka, snaží sa ho zaviazať s použitím ešte väčšieho počtu kôl federálneho hlasovania.
- Akonáhle uzol dokáže potvrdiť záväzok hlasovacieho lístka, môže „externalizovať“ hodnotu tohto hlasovacieho lístka, používajúc ho ako výsledok konsenzu.
Tieto kroky zahŕňajú niekoľko kôl federálneho hlasovania, ktoré spolu vytvárajú jedno kolo SCP. Pozrime sa podrobnejšie, čo sa stane pri každom kroku.
Federálne hlasovanie
Federálne hlasovanie je procedúra, ktorá určuje, či môže sieť súhlasiť s návrhom. V kole hlasovania musí každý uzol vybrať jednu z potenciálne mnohých možných hodnôt. Nemôže to urobiť, kým nebude presvedčený, že ostatné uzly v sieti nevyberú iný výsledok. Aby si boli tým istí, uzly si vymieňajú záplavu správ tam a späť, aby každý potvrdil, čo kvórum uzol prijíma to isté riešenia.. Zvyšok tejto sekcie vysvetľuje pojmy v tomto tvrdení a akým spôsobom prebieha celá procedúra.
Kvorá a kvorové rezy
Začneme definíciou kvoru. Ako sme si spomenuli vyššie, v decentralizovanej sieti s dynamickým členstvom nie je možné vopred vedieť počet uzlov, a teda, koľko ich je potrebných na väčšinu. Federálne hlasovanie rieši tento problém predstavením novej myšlienky kvorového rezu (quorum slice): malá skupina rovnocenných uzlov, ktorým uzol dôveruje na prenášanie informácií o stave hlasovania do zvyšku siete. Každý uzol si určuje svoj vlastný kvorový rez (členom ktorého sa stáva fakticky).
Tvorba kvoru začína s kvorovým rezom. Pre každý uzol sa pridávajú uzly jeho kvorového rezu. Potom sa pridávajú členovia rezov týchto uzlov a tak ďalej. Ako pokračujeme, narazíme na čoraz viac uzlov, ktoré nemôžete pridať, pretože sú už zahrnuté v reze. Keď už nie sú nové uzly na pridanie, proces sa zastaví: vytvorili sme kvórum prostredníctvom „transitívneho uzavretia“ kvóra počiatočného uzla.
Aby ste našli kvórum z daného uzla…
… pridávame členov jeho rezu…
… potom pridávame členov rezov týchto uzlov.
Pokračujeme, kým nezostanú žiadne uzly na pridanie.
Uzly na pridanie nezostali. Toto je kvórum.
V skutočnosti môže každý uzol náležat' do viacerých rezov. Aby sme vytvorili kvórum, vyberte len jeden z rezov a pridajte členov; potom pre každého člena vyberte akýkoľvek rez a pridajte členov tohto rezu a tak ďalej. To znamená, že každý uzol je členom viacerých možných kvórum.
Na každom kroku vyberte len jeden rez kvórum.
Jedno možné kvórum. Alebo alternatívna možnosť…
… vyberáme iné rezy…
…(keď je to možné)…
… vytvára iné kvórum.
Ako sa uzol dozvie, v ktorých rezov sú ostatné uzly? Presne tak, ako ostatné informácie o iných uzloch: z oznámení, ktoré každý uzol vysiela do siete, keď sa mení jeho hlasovacieho stavu. Každé vysielanie obsahuje informácie o rezoch odosielajúceho uzla. V technickej dokumentácii SCP nie je uvedený mechanizmus komunikácie. Implementácie zvyčajne používajú na zabezpečené vysielanie správ po celej sieti.
Pripomíname, že v nefi federatívnom byzantskom systéme dohôd je kvórum definované ako väčšina všetkých uzlov. Byzantský systém dohôd bol vyvinutý z pohľadu otázky: koľko nespoľahlivých uzlov je systém schopný uniesť? V systéme z N uzlov, navrhnutom na prežitie pri f poruchách (klamstvách), by mal uzol mať schopnosť dosiahnuť pokrok získaním odpovede od N−f peerov, keďže f z nich možno nefunguje. Ale získaním odpovede od N−f peerov, je možné predpokladať, že všetkých f peerov (od ktorých uzol nedostal odpoveď) sú v skutočnosti čestní. Týmto sú zlovolní f z N−f peerov (od ktorých bola odpoveď prijatá). Aby uzly dospeli k jednoznačnému konsenzu, musí byť väčšina ostatných uzlov čestná, to znamená, že potrebujeme, aby N−f bolo väčšie ako 2f alebo N > 3f. Takže zvyčajne systém navrhnutý na prežitie pri f poruchách, bude mať celkovo N=3f+1 uzlov a veľkosť kvóra 2f+1. Akonáhle návrh prekročí prah kvóra, ostatní členovia siete sú presvedčení, že akékoľvek konkurujúce návrhy zlyhajú. Tak sa sieť zbieha k výsledku.
Ale vo federatívnom byzantskom systéme dohôd nemôže existovať väčšina (pretože nikto nevie o celkovej veľkosti siete), ale koncept väčšiny je vo všeobecnosti nepoužiteľný! Ak je členstvo v systéme otvorené, niekto môže získať väčšinu jednoducho vykonaním takzvanej Sybilovej útoku: viackrát sa pripojiť k sieti cez niekoľko uzlov. Tak prečo sa tranzitívne uzavretie rezu môže nazvať kvórum, a ako je schopné potláčať konkurujúce návrhy?
Technicky, nijako! Predstavte si sieť z šiestich uzlov, kde sú dve trojice izolované vo vzájomných rezoch kvóra. Prvá podskupina môže prijať rozhodnutie, o ktorom druhá nikdy nepočuje, a naopak. Pre túto sieť nie je spôsob, ako dosiahnuť konsenzus (okrem náhody).
Preto SCP vyžaduje, aby pre federatívne hlasovanie (a na aplikáciu dôležitých teoreém článku) sieť mala vlastnosť nazývanú prienik kvór.V sieti s touto vlastnosťou sa ľubovoľné dve kvóra, ktoré možno vytvoriť, vždy prekryjú aspoň v jednom uzle. Na určenie prevládajúcich nálad v sieti je to rovnako dobré, ako mať väčšinu. Intuitívne to znamená, že akékoľvek kvórum súhlasí s výrokom X, žiadne iné kvórum nemôže nikdy súhlasiť s niečím iným, pretože nevyhnutne bude zahŕňať nejaký uzol z prvého kvóra, ktorý už hlasoval za X.
Ak existuje prekrývanie kvór v sieti...
...potom akékoľvek dve kvóra, ktoré môžete zostaviť...
...vždy sa budú prekrývať.
(Samozrejme, prekrývajúce sa uzly môžu byť byzantsky klamné alebo zlé iným spôsobom. V takom prípade prekrývanie kvór nepomáha sieti dosiahnuť súhlas. Z tohto dôvodu sa mnohé výsledky v technickom dokumente SCP zakladajú na jasne vyjadrených predpokladoch, ako je to, že v sieti zostáva prekrývanie kvór... ...aj po odstránení zlých uzlov.Na jednoduchosti ponecháme tieto predpoklady... implicitné v zvyšku článku).
Môže sa zdať nerozumné očakávať, že v sieti nezávislých uzlov môže existovať spoľahlivé prekrývanie kvór. Ale existujú dva dôvody, prečo je to tak.
Prvý dôvod spočíva v samotnej existencii internetu. Internet je ideálny príklad siete nezávislých uzlov s prekrývaním kvór. Väčšina uzlov v internete sa spája len s niekoľkými ďalšími lokálnymi uzlami, ale tieto malé skupiny sa dostatočne prekryjú, aby každý uzol bol prístupný z každého iného uzla rôznymi trasami.
Druhý dôvod je špecifický pre platobnú sieť Stellar (najbežnejšie použitie SCP). Každý aktívum v sieti Stellar má emitenta, a odporúčania Stellar požadujú, aby každý emitent priradil jeden alebo viac uzlov v sieti na spracovanie požiadaviek na vyplatenie. Je vo vašom záujme priamo alebo nepriamo zahrnúť tieto uzly do rezov kvóra pre každé aktívum, ktoré vás zaujíma. Potom sa kvóra pre všetky uzly, ktoré majú záujem o dané aktívum, prekrývajú aspoň v týchto uzloch vyplatenia. Uzly, ktoré majú záujem o niekoľko aktív, budú zahŕňať do svojich rezov kvóra všetky uzly vyplatenia príslušných emitentov, a budú sa snažiť spojiť všetky aktíva dohromady. Okrem toho akékoľvek aktíva, ktoré nie sú takto spojené s inými v sieti, a nemali by byť spojené — je to navrhnuté tak, aby v tejto sieti neexistovalo prekrývanie kvóra (napríklad banky z dolárovej zóny niekedy chcú obchodovať s bankami z eurozóny a bankami z zóny pesa, takže sa nachádzajú v jednej sieti, ale nikomu z nich nezáleží na samostatnej sieti detí, ktoré obchodujú s baseballovými kartami).
Samozrejme, očakávanie prekrývania kvóra nie je zaručené. Iné byzantské systémy dohadovania majú svoju komplexnosť vo veľkej miere vďaka záruke kvóra. Dôležitou novinkou SCP je to, že znižuje zodpovednosť za vytváranie kvóra z algoritmu konsenzu na úroveň aplikácie. Takže hoci federatívne hlasovanie je dosť bežné pre hlasovanie o akýchkoľvek otázkach, jeho spoľahlivosť sa kriticky závisí od širšieho zmyslu týchto hodnôt. Niektoré hypotetické druhy využitia sa môžu ukázať ako menej vhodné na vytváranie dobre prepojených sietí ako iné.
Hlasovanie, prijatie a potvrdenie
V kole federatívneho hlasovania uzol voliteľne začne hlasovať za nejakú hodnotu V. To znamená vysielanie správy do siete: „Ja som uzol N, moje rezy kvóra Q a hlasujem za V“. Keď uzol hlasuje týmto spôsobom, sľubuje, že nikdy nehlasoval proti V a nikdy nebude.
V prenosoch z rovnocenných uzlov každý uzol vidí, ako hlasujú ostatní. Akonáhle uzol získa dostatočný počet takýchto správ, môže sledovať prieniky kvór a pokúsiť sa nájsť kvóry. Ak vidí kvór súm, ktoré tiež hlasujú za V, môže prejsť k prijatiu V a prenášať túto novú správu do siete: „Ja som uzol N, moje prieniky kvór Q a prijímam V“. Prijatie poskytuje silnejšiu záruku než jednoduché hlasovanie. Keď uzol hlasuje za V, nikdy nemôže hlasovať za iné varianty. Ale ak uzol prijme V, žiadny uzol v sieti nikdy neprijme iný variant (teoréma 8 v technickom dokumente SCP to dokazuje).
Samozrejme, existuje vysoká pravdepodobnosť, že okamžite sa nenájde kvór uzlov, ktoré by súhlasili s V. Iné uzly môžu hlasovať za iné hodnoty. Ale pre uzol existuje ešte jeden spôsob, ako prejsť od jednoduchého hlasovania k prijatiu. N môže prijať inú hodnotu W, aj keď za ňu nehlasoval, a dokonca aj keď nevidí pre ňu kvór. Na to, aby sa zmenil svoj hlas, stačí vidieť blokujúce množstvo uzlov, ktoré prijali W. Blokujúce množstvo je po jednom uzle z každého z prienikov kvór N. Ako názov napovedá, je schopné blokovať akúkoľvek inú hodnotu. Ak všetky uzly v takomto množstve prijímajú W, potom (podľa teorémy 8) sa nikdy nepodarí vytvoriť kvór, ktorý by prijal inú hodnotu, a preto je pre N bezpečné prijať W.
Uzol N s tromi prienikmi kvór.
B-D-F je blokujúce množstvo pre N: obsahuje po jednom uzle z každého z prienikov N.
B-E je tiež blokujúcim množstvom pre N, pretože E sa objavuje v dvoch prienikoch N.
Ale blokujúce množstvo nie je kvór. Bolo by príliš jednoduché oklamať uzol N, aby prijal požadovanú hodnotu, ak by stačilo hacknúť len jeden uzol v každom z prienikov N. Preto prijatie hodnoty ešte neznamená koniec hlasovania. N musí potvrdiť hodnotu, to znamená vidieť kvór uzlov, ktoré ju prijímajú. Ak sa dostane tak ďaleko, ako dokazuje technický dokument SCP (v teoréme 11), zvyšok siete tiež nakoniec potvrdí tú istú hodnotu, čím N dokončí federatívne hlasovanie s konkrétnou hodnotou ako výsledok.
Federatívne hlasovanie.
Proces hlasovania, prijímania a potvrdenia predstavuje jedno úplné kolo federatívneho hlasovania. Konsenzuálny protokol Stellar spája viacero takýchto kôl na vytvorenie úplného konsenzuálneho systému.
Konsenzuálny protokol Stellar
Dve najdôležitejšie vlastnosti konsenzuálneho systému sú bezpečnosť a odolnosť. Konsenzuálny algoritmus je „bezpečný“, ak nikdy nemôže dať rôzne výsledky rôznym účastníkom (kópia histórie Boba nikdy nebude protirečiť Carol). „Odolnosť“ znamená, že algoritmus vždy vyprodukuje výsledok, teda nenarazí.
Opísaná procedúra federatívneho hlasovania je bezpečná v tom zmysle, že ak uzol potvrdí hodnotu V, žiadny iný uzol nepotvrdí inú hodnotu. Ale „nepotvrdí inú hodnotu“ – to neznamená, že niečo nepotvrdí. Účastníci môžu hlasovať za tak veľké množstvo rôznych hodnôt, že nič nepríde nad prah prijatia. To znamená, že v federatívnom hlasovaní chýba odolnosť.
Konsenzuálny protokol Stellar používa federatívne hlasovanie tak, aby zabezpečil bezpečnosť aj odolnosť. (Záruky bezpečnosti a odolnosti SCP majú teoretický limit. Konštrukcia vyberá veľmi silnú záruku bezpečnosti na úkor malého oslabenia odolnosti, ale ak je čas dostatočný, s vysokou pravdepodobnosťou sa dosiahne konsenzus). Jednoducho povedané, myšlienka spočíva v tom, že sa uskutoční niekoľko federatívnych hlasovaní o rôznych hodnotách, kým jedna z nich neprejde kompletnými fázami hlasovania SCP, ktoré sú opísané nižšie.
Hodnoty, o ktoré SCP usiluje o konsenzus, môžu byť históriou transakcií alebo objednávkou na obed, alebo niečím iným, ale je dôležité poznamenať, že to nie sú tie hodnoty, ktoré sa prijímajú alebo potvrdzujú. Namiesto toho sa federatívne hlasovanie koná o oznamoch k týmto hodnotám..
Prvé kolá federatívneho hlasovania prebiehajú v etape nominácie (nominácia), na súbore oznámení typu „Navrhovujem V“, možno pre mnohé rôzne hodnoty V. Cieľom nominácie je nájsť jedno alebo niekoľko oznámení, ktoré prejdú prijatím a potvrdením.
Po nájdení potvrdených kandidátov SCP prechádza do etapy hlasovania, kde cieľom je nájsť akýsi hlasovací lístok (t.j. kontajner pre navrhovanú hodnotu) a kvórum, ktoré môže vyhlásiť změnu komit preň (commit). Ak kvórum vykoná komit hlasovacieho lístka, jeho hodnota sa prijíma ako konsenzus. Ale predtým, než sa uzol môže hlasovať za komit hlasovacieho lístka, musí najprv potvrdiť zrušenie všetkých hlasovacích lístkov s menšou hodnotou počítadla. Tieto kroky – zrušenie hlasovacích lístkov, aby sa našiel ten, za ktorý sa môže potvrdiť komit – zahŕňajú niekoľko kôl federatívneho hlasovania ohľadom niekoľkých vyhlásení o hlasovacích lístkoch.
V nasledujúcich oddieloch sa podrobnejšie opisuje navrhovanie a hlasovanie.
Navrhovanie
Na začiatku etapy navrhovania môže každý uzol spontánne vybrať hodnotu V a hlasovať za potvrdenie „Navrhujem V“. Cieľom v tejto etape je potvrdiť navrhnutie nejakej hodnoty prostredníctvom federatívneho hlasovania.
Je možné, že dostatočný počet uzlov hlasuje za dostatočne rôzne vyhlásenia a žiadne navrhovanie nemôže dosiahnuť prah prijatia. Preto okrem vysielania vlastných nominácií uzly „odrážajú“ nominácie svojich peerov. Odrážanie (echo) znamená, že ak uzol hlasuje za navrhnutie V, ale vidí správu od suseda, ktorý hlasuje za navrhnutie W, tak teraz bude hlasovať za navrhnutie aj V, aj W. (Nie všetky hlasy peerov sa odrážajú počas navrhovania, pretože to môže viesť k výbuchu rôznych nominantov. SCP obsahuje mechanizmus regulácie týchto hlasov. Skrátka, existuje vzorec na určenie „priorít“ peera z pohľadu uzla, a odrážajú sa hlasy iba vysoko priorizovaných uzlov. Čím dlhšie navrhovanie trvá, tým je nižší prah, takže uzol rozširuje súbor peerov, ktorých hlasy bude odrážať. Vzorec priority ako jeden z vstupov zahŕňa číslo slotu, takže vysoko priorizovaný peer pre jeden slot môže byť nízkoprioritný pre iný, a naopak).
Konceptuálne vyhadzovanie paralelne V a W – to sú samostatné federatívne hlasy, každý samostatne schopný dosiahnuť prijatie alebo potvrdenie. V praxi správy protokolu SCP balia tieto samostatné hlasy spolu.
Hoci hlasovanie za vyhadzovanie V je sľubom nikdy nehlasovať proti vyhadzovaniu V, na úrovni aplikácie - v tomto prípade SCP - sa určuje, čo znamená 'proti'. SCP nevidí tvrdenie, ktoré by bolo v rozpore s hlasovaním 'Ja vyhadzujem X', teda nie je žiadna správa 'Ja som proti vyhadzovaniu X', takže uzol môže hlasovať za vyhadzovanie akýchkoľvek hodnôt. Mnohé z týchto nominácií nikam nevedú, ale nakoniec uzol môže prijať alebo potvrdiť jednu alebo viac hodnôt. Akonáhle je nominant potvrdený, stáva sa kandidátom.
Vyhadzovanie SCP s využitím federatívneho hlasovania. Môže byť mnoho hodnôt 'B', vyhadzovaných rovnocennými uzlami a 'odrážaných' uzlom.
Vyhadzovanie kandidátov môže viesť k vzniku niekoľkých potvrdených kandidátov. Preto SCP vyžaduje, aby aplikačná úroveň poskytla akúsi metódu zlúčenia kandidátov do jedného kompozitu (composite). Metóda zlúčenia môže byť akákoľvek. Dôležité je, že ak je táto metóda deterministická, každý uzol zlúči rovnakých kandidátov. V systéme hlasovania za obed 'zlúčenie' môže jednoducho znamenať odmietnutie jedného z dvoch kandidátov. (Ale deterministicky: každý uzol musí zvoliť rovnakú hodnotu na zrušenie. Napríklad, skoršia voľba v abecednom poriadku). V platobnej sieti Stellar, kde prebieha hlasovanie o histórii transakcií, zlúčenie dvoch navrhnutých nominantov predpokladá zlúčenie transakcií, ktoré obsahujú, a posledných z ich dvoch časových pečiatok.
Technický popis SCP dokazuje (veta 12), že na konci fázy vyhadzovania sa sieť nakoniec zladí na jeden kompozit. Ale je tu problém: federatívne hlasovanie je asynchrónny protokol (rovnako ako SCP). Inými slovami, uzly nie sú koordinované v čase, ale iba prostredníctvom správ, ktoré odosielajú. Z pohľadu uzla nie je jasné, kedy skončila fáza navrhovania. A hoci všetky uzly nakoniec prídu k rovnakému kompozitu, môžu zvoliť rôzne trasy na tejto ceste, pričom vytvárajú rôznych zložených kandidátov na ceste, a nikdy nemôžu povedať, ktorý z nich je konečný.
Ale to je v poriadku. Navrhovanie je len príprava. Hlavné je obmedziť počet kandidátov na dosiahnutie konsenzu, ktorý sa uskutočňuje v procese. hlasovania (voice).
Hlasovanie
Hlasovací lístok je pár , kde counter je celé číslo, ktoré začína od 1, a value je kandidát z fázy navrhovania. Môže to byť vlastný kandidát uzla alebo kandidát susedného uzla, ktorého akceptoval tento uzol. Hrubo povedané, pri hlasovaní sa uskutočňujú mnohé pokusy donútiť sieť dosiahnuť konsenzus o nejakom kandidátovi v nejakom hlasovacom lístku, a to prostredníctvom potenciálne mnohých federatívnych hlasovaní o vyhláseniach týkajúcich sa hlasovacích lístkov. Počítadlá na hlasovacích lístkoch sledujú uskutočnené pokusy, a hlasovacie lístky s vyššími počítadlami majú prednosť pred hlasovacími lístkami s nižšími počítadlami. Ak sa hlasovací lístok zasekne, začne sa nové hlasovanie, teraz na hlasovacom lístku .
Dôležité je rozlišovať hodnoty (napríklad, aká by mala byť objednávka na obedom: pizza alebo šaláty), hlasovacie lístky (pár counter-value) a vyhlásenia o hlasovacích lístkoch. Kolo SCP zahŕňa niekoľko kôl federatívneho hlasovania, najmä na takýchto vyhláseniach:
- „Som pripravený na potvrdenie hlasovacieho lístka B“ a
- „Vyhlasujem potvrdenie hlasovacieho lístka B“
Z hľadiska tohto uzla sa konsenzus dosahuje, keď nájde hlasovací lístok B, ku ktorému môže potvrdiť (t.j. nájsť kvórum, ktoré akceptuje) vyhlásenie „Vyhlasujem potvrdenie hlasovacieho lístka B“. Od tejto chvíle je možné bezpečne konať podľa hodnoty uvedenej v B – napríklad uskutočniť túto objednávku na obedom. Toto sa nazýva externalizácia hodnoty. Akonáhle je potvrdené prijatie hlasovacieho lístka, uzol si môže byť istý, že akýkoľvek iný uzol vykonal externalizáciu tej istej hodnoty, alebo ju nevyhnutne vykoná v budúcnosti.
Aj keď sa koncepčne mnohé federatívne hlasovania vykonávajú na základe vyhlásení o mnohých rôznych hlasovacích lístkoch, nezdieľajú tak veľké množstvo správ, pretože každá správa zahŕňa radu hlasovacích lístkov. Jedna správa tak posúva stav mnohých federatívnych hlasovaní naraz, napríklad: „Súhlasím s komitom hlasovacích lístkov v rozsahu od do .“
Čo znamenajú termíny „pripravený“ (prepared) a „komit“ (commit)?
Uzol hlasuje za komit hlasovacieho lístka, keď je presvedčený, že ostatné uzly nespravia komit hlasovacích lístkov s inými hodnotami. Presvedčenie o tom je cieľom prípravy vyhlásenia. Hlasovanie, v ktorom sa hovorí: „Som pripravený na komit hlasovacieho lístka B“, je sľub, že nikdy nespravím komit hlasovacieho lístka menšieho ako B, t. j. s nižším číslom (SCP vyžaduje, aby hodnoty v hlasovacích lístkoch mali určitý poriadok. Takže hlasovací lístok je menší ako , ak N1<N2, a tiež ak N1=N2 a V1<V2). Tieto menšie hlasovacie lístky sú „zrušené“ (aborted) počas prípravného hlasovania, zatiaľ čo B je považovaný za „pripravený“.
Prečo „Som pripravený na komit hlasovacieho lístka B“ znamená „Sľubujem, že nikdy nebudem povoliť komit hlasovacích lístkov menších ako B“? Pretože SCP definuje abort ako protiklad k commit. Hlasovanie na prípravu hlasovacieho lístka predpokladá tiež hlasovanie o zrušení niektorých iných hlasovacích lístkov a, ako sme už predtým diskutovali, hlasovanie za niečo jedno je sľub, že nikdy nebudem hlasovať proti tomu.
Predtým, ako uzol prenesie komit, musí najprv nájsť hlasovací lístok, ktorý môže potvrdiť ako pripravený. Inými slovami, vykonáva federatívne hlasovanie na tému „Som pripravený na komit hlasovacieho lístka B“, pravdepodobne pre mnohé rôzne hlasovacie lístky, až kým nenájde ten, ktorý akceptuje kvórum.
Odkiaľ pochádzajú hlasovacie lístky na prípravu hlasovania? Najprv sa uzol zdieľa o príprave na hlasovanie za , kde C je kompozitný kandidát, vytvorený v rámci fázy nominácie. Avšak aj po začiatku prípravy na hlasovanie môže nominácia viesť k objaveniu nových kandidátov, ktorí sa stanú novými hlasovacími lístkami. Medzitým môžu mať páry rôznych kandidátov a môžu vytvoriť blokujúcu množinu, ktorá prijíma „Som pripravený zaviazať hlasovací lístok B2“, čím presvedčí uzol, aby ho tiež prijal. Nakoniec existuje mechanizmus časového limitu, ktorý generuje nové kolá federatívneho hlasovania s novými hlasovacími lístkami s vyššími číslami, ak súčasné hlasovacie lístky uviazli.
Akonáhle uzol nájde hlasovací lístok B, ktorý môže potvrdiť ako pripravený, zdieľa novú správu „Zviazanie hlasovacieho lístka B“. Toto hlasovanie hovorí párom, že uzol nikdy neodmietne B. V skutočnosti, ak B predstavuje hlasovací lístok , tak „Zviazanie hlasovacieho lístka “ znamená neodvolateľný súhlas hlasovať za pripravenosť každého hlasovacieho lístka od po . Táto dodatočná hodnota pomáha ostatným uzlom dohnať pára so zaviazovaním, ak sú ešte v skorších fázach protokolu.
V tejto fáze je ešte raz dôležité zdôrazniť, že ide o asynchrónne protokoly. Iba preto, že jeden uzol posiela hlasy na zaviazanie, neznamená to, že jeho rovesníci to tiež robia. Niektorí z nich môžu stále hlasovať o vyhláseniach na prípravu hlasovania, iní už možno externelizovali hodnotu. SCP vysvetľuje, ako by mal uzol spracovávať každý typ rovnocenného správy bez ohľadu na jeho fázu.
Ak správa „Ja vyhlasujem commit “ nemôže byť prijatá alebo potvrdená, existuje pravdepodobnosť prijatia alebo potvrdenia správy alebo — alebo v každom prípade akéhokoľvek bulletinu so hodnotou C, a nie akoukoľvek inou, pretože uzol už sľúbil, že nikdy neodvolá . Do doby, keď uzol zrealizuje hlasy pre commit, to bude C alebo nič, v závislosti od toho, ako ďaleko zájde konsenzus. Avšak zatiaľ je to pre uzol nedostatočné pre externilizáciu C. Niektoré byzantské zrády (tvoriace menej než kvórum, založené na našich predpokladoch o bezpečnosti) môžu klamať uzol. Prijatie a následné potvrdenie nejakého bulletinu (alebo rozsahu bulletinov) — to je to, čo dáva uzolu istotu, že konečne externilizuje C.
Hlasovanie SCP prostredníctvom federatívneho hlasovania. Nie je zobrazené: kedykoľvek môže spustiť časovač, čo zvýši počet v bulletine (a možno vytvorí nový kompozit z dodatočne navrhnutých kandidátov).
A to je všetko! Akonáhle sieť dosiahne konsenzus, je pripravená robiť to znova a znova. V platobnej sieti Stellar sa to deje približne každých 5 sekúnd: výkon, ktorý si vyžaduje ako bezpečnosť, tak aj odolnosť, zaručené SCP.
SCP to môže dosiahnuť za pomoci niekoľkých kôl federatívneho hlasovania. Federatívne hlasovanie sa stalo možným vďaka konceptu rezov kvóra: súborom rovnocenných uzlov, ktorým sa každý uzol rozhodol dôverovať ako súčasti svojho (subjektívneho) kvóra. Táto konfigurácia znamená, že je možné dosiahnuť konsenzus aj v sieti s otvoreným členstvom a byzantskými podvodmi.
Ďalšie čítanie
- Originálny technický dokument SCP je možné nájsť , a projekt špecifikácií pre jeho implementáciu.
- Pôvodný autor protokolu SCP David Mazieres zjednodušene (ale stále technicky) vysvetľuje jeho .
- Možno ste boli prekvapení, keď ste nenašli v tomto článku pojmy „ťažba“ alebo „dôkaz práce“. SCP nepoužíva tieto metódy, ale niektoré iné algoritmy konsenzu ich používajú. Zane Wizerspoon napísal prístupný .
- jednoduchá sieť dosahujúca konsenzus počas jedného kompletného kola SCP.
- Pre čitateľov, ktorí majú záujem o implementácie SCP: pozri. , používaná platobnou sieťou Stellar, alebo , ktorý som napísal pre lepšie pochopenie SCP.
Zdroj: habr.com
