Protokol konsensu Stellar byl poprvé popsán v Davidem Mazierem v roce 2015. Je to „federativní systém byzantského konsensu“, který umožňuje decentralizovaným výpočetním sítím bez vůdců efektivně dosahovat konsensu o jakémkoli rozhodnutí. Platební síť Stellar využívá Stellar Consensus Protocol (SCP) pro vedení konzistentní historie transakcí, kterou vidí všichni účastníci.
Předpokládá se, že protokoly konsensu jsou obtížné k pochopení. SCP je jednodušší než většina z nich, ale stále sdílí tuto pověst – částečně kvůli mylné představě, že „federativní hlasování“, které je věnováno první polovině vědeckého článku, je SCP. Ale to není pravda! Je to pouze důležitý stavební blok, který je ve druhé polovině článku použit k vytvoření skutečného protokolu konsensu Stellar.
V tomto článku stručně vysvětlíme, co je to „systém dohod“, co může udělat, aby byl „byzantský“, a proč udělat byzantský systém „federativním“. Poté vysvětlíme federativní hlasovací proceduru popsanou v článku o SCP a nakonec vysvětlíme samotný protokol SCP.
Systémy dohod
Systém dohod umožňuje skupině účastníků dosáhnout konsensu o nějakém tématu, například co objednat k obědu.
My v Interstellar jsme zavedli vlastní systém obědových dohod: objednáváme to, co říká náš operační manažer John. Je to jednoduchý a efektivní systém dohod. Všichni důvěřujeme Johnovi a věříme, že každý den najde něco zajímavého a výživného.
Ale co když John zneužije naši důvěru? Může jednostranně rozhodnout, že bychom se měli všichni stát vegany. Za týden nebo dva nás pravděpodobně svrhneme a předáme pravomoci Elizabeth. Ale co když má ráda avokádo s ančovičkami a myslí si, že bychom se měli všichni stát takovými? Moc kazí. Proto je lepší najít nějakou demokratickější metodu: nějaký způsob, jak zajistit, aby byly zohledněny různé preference, a zároveň zajistit včasný a jednoznačný výsledek, aby se nestalo, že nikdo neobjedná oběd nebo pět lidí zadá různé objednávky, nebo že diskuze potrvá až do večera.
Na první pohled se zdá, že řešení je jednoduché: uspořádat hlasování! Ale to je klamný dojem. Kdo bude shromažďovat hlasy a oznamovat výsledky? A proč by ostatní měli věřit tomu, co řekne? Možná nejdříve můžeme v první řadě hlasovat pro lídra, kterému důvěřujeme, aby vedl hlasování – ale kdo povede toto je první hlasování? Co když se nedokážeme shodnout na lídrovi? Nebo se shodneme, ale tento lídr zůstane zadržen na schůzce nebo onemocní?
Podobné problémy se vyskytují v distribuovaných počítačových sítích. Všichni účastníci nebo uzly musí schválit určité rozhodnutí, například kdo má aktualizovat sdílený soubor nebo vyzvednout úkol z fronty zpracování. V síti kryptoměn musejí uzly opakovaně vybírat, jaká je kompletní historie, z několika možných verzí, které někdy konfliktují. Toto síťové schválení zaručuje příjemci, že mince je (a) platná (ne falešná) a (b) ještě nebyla utracena jinde. Také zaručuje, že je bude možné v budoucnu utratit, protože nový příjemce bude mít stejné záruky ze stejných důvodů.
Jakýkoliv konsenzuální systém v distribuované výpočetní síti musí být odolný proti chybám: musí dávat konzistentní výsledky navzdory chybám, jako jsou pomalé komunikační linky, nereagující uzly a nesprávné pořadí zpráv. Byzantský konsenzuální systém je navíc odolný vůči „byzantským“ chybám: uzlům, které poskytují falešné informace, ať už vinou chyby nebo s úmyslem podkopat systém nebo získat nějakou výhodu. „Byzantská“ odolnost vůči chybám – schopnost důvěřovat skupinovému rozhodnutí, i když někteří členové skupiny mohou lhát nebo jinak nesplnit pravidla rozhodování – dostala svůj název podle , kteří se snažili koordinovat útok. u Anthonyho Stevense.
Zvažujme vlastníka kryptoměny Alisu, která si musí vybrat mezi koupí chutné zmrzliny od Boba a splácením dluhu Carol. Možná chce Alisa zaplatit oběma najednou, podvodně utratit stejnou minci. K tomu musí přesvědčit počítač Boba, že mince nikdy nebyla vyplacena Carol, a přesvědčit počítač Carol, že mince nikdy nebyla vyplacena Bobovi. Byzantský systém dohod to činí ve skutečnosti nemožným pomocí formy pravidla většiny, známého jako kvórum. Uzlu v takové síti se odmítá přejít k určité verzi historie, dokud nevidí, že dostatečný počet rovnocenných uzlů — kvórum — souhlasí s tímto přechodem. Jakmile k tomu dojde, vytvoří dostatečně velký volební blok, aby donutil zbývající uzly sítě souhlasit s jejich rozhodnutím. Alisa může donutit některé uzly lhát jejím jménem, ale pokud je síť dostatečně velká, její pokus bude potlačen hlasy čestných uzlů.
Kolik uzlů je potřeba pro kvórum? Minimálně většinu, přesněji kvalifikovanou většinu pro boj s chybami a podvody. Ale k tomu, abychom spočítali většinu, je třeba znát celkový počet účastníků. V kanceláři Interstellar nebo na obvodních volbách jsou tato čísla snadno zjistitelná. Ale pokud je vaše skupina slabě definovaná síť, do níž uzly mohou vstupovat a vystupovat podle svého uvážení bez souhlasu centrály, pak je potřeba federativní systém byzantského dohodování, schopný určovat kvóra nejen z předem daného seznamu uzlů, ale dynamicky, z neustále se měnícího a nevyhnutelně neúplného snímku uzlů v určitém okamžiku.
Může se zdát nemožné vytvořit kvórum z pohledu jednoho uzlu v rozsáhlé síti, ale je to možné. Takové kvórum může dokonce zaručit výsledky decentralizovaného hlasování. Technická dokumentace SCP ukazuje, jak to provést pomocí procedury nazvané federativní hlasování.
Pro netrpělivé
Zbytek článku podrobně popisuje federativní hlasování a protokol konsensu Stellar. Pokud vás nezajímají podrobnosti, zde je obecný přehled procesu.
- Uzly provádějí kola federálního hlasování o „nominantech“. Kolo federálního hlasování znamená:
- Uzly hlasují pro nějaké tvrzení, například „Navrhuji hodnotu V“;
- Uzly naslouchají hlasům pirátů, dokud nenajdou někoho, kdo může „přijmout“;
- Uzly hledají „kvórum“ pro toto tvrzení. Kvórum „potvrzuje“ nominanta.
- Jakmile může uzel potvrdit jednoho nebo více nominantů, snaží se „připravit“ „hlasovací lístek“ během několika kol federálního hlasování.
- Jakmile je uzel schopen zkontrolovat připravenost hlasovacího lístku, snaží se ho commitnout pomocí ještě více kol federálního hlasování.
- Jakmile může uzel potvrdit commit hlasovacího lístku, může „externealizovat“ hodnotu tohoto hlasovacího lístku použitím jej jako výsledek konsensu.
Tyto kroky zahrnují několik kol federálního hlasování, která dohromady tvoří jedno kolo SCP. Pojďme se podívat blíže na to, co se děje v každém kroku.
Federální hlasování
Federální hlasování je proces určování, zda může síť souhlasit s návrhem. V kole hlasování musí každý uzel vybrat jednu z potenciálně mnoha možných hodnot. To nemůže udělat, dokud není si jistý, že ostatní uzly v síti nevyberou jiný výsledek. Aby si tím byly jisté, uzly si vyměňují záplavu zpráv tam a zpět, aby každý potvrdil, že kvórum uzel přijímá to samé rozhodnutí. Zbytek této části vysvětluje termíny v tomto tvrzení a jak probíhá celý proces.
Kvórum a kvórum slice
Začněme definicí kvóra. Jak jsme již uvedli výše, v decentralizované síti s dynamickým členstvím není možné předem znát počet uzlů a tedy kolik je potřeba pro většinu. Federální hlasování řeší tento problém zavedením nové myšlenky kvórum slice (quorum slice): malá sada rovnocenných uzlů, kterým uzel důvěřuje, aby přenášely informace o stavu hlasování v ostatních částech sítě. Každý uzel si definuje svůj vlastní kvórum slice (člena kterého se stává de facto).
Tvorba kvóra začíná se slice kvóra. Pro každý uzel se přidávají uzly jeho kvórum slice. Poté se přidávají členové slice těchto uzlů a tak dále. Jak se proces pokračuje, objevuje se stále více uzlů, které nemůžete přidat, protože jsou již zahrnuty v podmnožině. Když už nejsou žádné nové uzly k přidání, proces se zastaví: vytvořili jsme kvórum prostřednictvím „transitivního uzávěru“ (transitive closure) podmnožiny počátečního uzlu.
Abychom našli kvórum z daného uzlu…
… přidáváme členy jeho podmnožiny…
… pak přidáváme členy podmnožin těchto uzlů.
Pokračujeme, dokud nezůstane žádný uzel k přidání.
Uzlů k přidání už není. To je kvórum.
Ve skutečnosti může každý uzel patřit více než do jedné podmnožiny. Abychom vytvořili kvórum, vyberte pouze jednu z podmnožin a přidejte členy; poté vyberte jakoukoli podmnožinu pro každého z členů a přidejte členy tohoto podmnožiny a tak dále. To znamená, že každý uzel je členem mnoha možných kvórum.
Vyberte pouze jednu podmnožinu kvórum v každém kroku.
Jedno možné kvórum. Nebo alternativní možnost…
… vybíráme jiné podmnožiny…
…(když je to možné)…
… vytváří jiné kvórum.
Jak se uzel dozví, v jakých podmnožinách jsou ostatní uzly? Stejně jako další informace o ostatních uzlech: z přenosů, které každý uzel vysílá do sítě, když se mění jeho hlasovací stav. Každé vysílání obsahuje informace o podmnožinách odesílajícího uzlu. V technické dokumentaci SCP není uveden mechanismus komunikace. Implementace obvykle používají pro zaručené vysílání zpráv po celé síti.
Připomeňme, že v nefederativním byzantském systému dohod se kvórum určuje jako většina všech uzlů. Byzantský systém dohod byl navržen z hlediska otázky: kolik nečestných uzlů je systém schopen snést? V systému s N uzly, navrženém na přežití při f selháních (podvodech), musí uzel být schopen dosáhnout pokroku tím, že obdrží odpověď od N−f peeringů, protože f z nich nemusí fungovat. Ale když dostane odpověď od N−f peeringů, lze předpokládat, že všechna f peerů (od kterých uzel neobdržel odpověď) jsou ve skutečnosti čestná. Takže škodlivých je f z N−f peeringů (od kterých byla obdržena odpověď). Aby uzly dospěly k jednomu konsensu, musí být většina zbylých uzlů čestná, tedy potřebujeme, aby N−f bylo větší než 2f, nebo N > 3f. Takže obvykle systém, navržený na přežití při f selháních, bude mít celkem N=3f+1 uzlů a velikost kvóra 2f+1. Jakmile návrh překročí práh kvóra, ostatní členové sítě jsou přesvědčeni, že jakékoli konkurenční návrhy selžou. Tak se síť sbližuje k výsledku.
Ale v federativním byzantském systému dohod nemusí být pouze většina (protože nikdo nezná celkovou velikost sítě), ale koncept většiny je zcela neužitečný! Pokud je členství v systému otevřené, může někdo získat většinu prostě provedením takzvaného útoku Sybila: opakovaným připojením k síti prostřednictvím několika uzlů. Tak proč lze tranzitivní uzavření řezu nazvat kvórum, a jak má schopnost potlačit konkurenční návrhy?
Technicky, nijak! Představte si síť šesti uzlů, kde jsou dvě trojice izolovány v řezech kvóra jeden od druhého. První podskupina může přijmout rozhodnutí, o kterém se druhá nikdy nedozví, a naopak. Pro tuto síť neexistuje způsob, jak dosáhnout konsensu (kromě náhody).
Proto SCP vyžaduje, aby pro federativní hlasování (a pro uplatnění důležitých vět v článku) síť měla vlastnost zvanou průnik kvór.. V síti s touto vlastností se jakékoli dva kvóra, která lze vytvořit, vždy překrývají alespoň v jednom uzlu. Pro určení převládajících nálad v síti je to stejně dobré, jako mít většinu. Intuitivně to znamená, že pokud jakékoli kvórum souhlasí s tvrzením X, žádné jiné kvórum nikdy nemůže souhlasit s něčím jiným, protože nutně zahrnuje nějaký uzel z prvního kvóra, který již hlasoval pro X.
Pokud v síti existuje překrytí kvór.
… pak jakékoli dvě kvóra, která můžete vytvořit…
… se vždy překrývají.
(Samozřejmě, překrývající se uzly mohou být byzantsky podvodné nebo v jiných ohledech špatné. V takovém případě překrytí kvór nepomáhá síti dosáhnout shody vůbec. Proto jsou mnohé výsledky v technickém dokumentu SCP založeny na výslovně vyjádřených předpokladech, jako je to, že v síti zůstává překrytí kvór. i po odstranění špatných uzlů.Pro zjednodušení necháme tyto předpoklady nevyjádřené ve zbytku článku).
Může se zdát nerozumné očekávat, že v síti nezávislých uzlů je možné spolehlivé překrytí kvór. Ale jsou zde dva důvody, proč je tomu tak.
První důvod spočívá v existenci samotného internetu. Internet je ideální příkladem sítě nezávislých uzlů s překrytím kvór. Většina uzlů na internetu se propojuje pouze s několika dalšími místními uzly, ale tyto malé množiny se překrývají dostatečně, aby každý uzel byl dostupný z každého jiného uzlu nějakou cestou.
Druhý důvod je specifický pro platební síť Stellar (nejběžnější použití SCP). Každý aktivum v síti Stellar má emitenta, a doporučení Stellar požaduje, aby každý emitent jmenoval jeden nebo více uzlů v síti ke zpracování žádostí o splácení. Je ve vašem zájmu zahrnout tyto uzly přímo nebo nepřímo do kvórum pro každé aktivum, o které máte zájem. Poté se kvóra pro všechny uzly, které mají zájem o dané aktivum, budou překrývat alespoň v těchto uzlech splácení. Uzly, které mají zájem o více aktiv, zahrnou do svých kvórum všechny uzly splácení příslušných emitentů a budou se snažit spojit všechna aktiva dohromady. Kromě toho jakákoli aktiva, která nejsou takto spojena s jinými v síti, a neměla by být spojena — je navrženo tak, aby v této síti nebylo překrývání kvórum (například banky v dolarové zóně někdy chtějí obchodovat s bankami v eurozóně a bankami v peso, takže jsou v jedné síti, ale nikdo z nich se nezajímá o jinou síť dětí, které obchodují s baseballovými kartičkami).
Samozřejmě, očekávání překrývání kvórum není zárukou. Jiné byzantské systémy dohod svými složitostmi mnohokrát vděčí zárukám kvórum. Důležitým novým prvkem SCP je to, že přenáší zodpovědnost za vytváření kvórum z algoritmu konsensu na úroveň aplikace. Takže, i když federativní hlasování je dostatečně obecné pro hlasování o jakýchkoli otázkách, jeho spolehlivost kriticky závisí na širším smyslu těchto hodnot. Některé hypotetické případy použití se mohou ukázat jako méně příznivé pro vytváření dobře propojených sítí než jiné.
Hlasování, přijetí a potvrzení
V kole federativního hlasování uzel volitelně začíná hlasovat pro nějakou hodnotu V. To znamená, že vysílá do sítě zprávu: „Já jsem uzel N, mé kvórum Q, a hlasuji pro V“. Když uzel hlasuje tímto způsobem, slibuje, že nikdy nehlasoval proti V a nikdy nebude.
V přenosu od rovnocenných uzlů každý uzel vidí, jak hlasují ostatní. Jakmile uzel shromáždí dostatečný počet těchto zpráv, může sledovat průřezy kvór a pokusit se najít kvóra. Pokud vidí kvór peerů, kteří také hlasují pro V, může přejít k přijetí V a vysílat tuto novou zprávu do sítě: „Jsem uzel N, mé průřezy kvór Q a přijímám V“. Přijetí zajišťuje silnější záruku než pouhé hlasování. Když uzel hlasuje pro V, nikdy nemůže hlasovat pro jiné možnosti. Ale pokud uzel přijme V, žádný uzel v síti nikdy nepřijme jinou možnost (věta 8 v technickém dokumentu SCP to dokazuje).
Samozřejmě je vysoká pravděpodobnost, že okamžitě nenajde kvór uzlů, které souhlasí s V. Ostatní uzly mohou hlasovat pro jiné hodnoty. Ale pro uzel existuje ještě jeden způsob, jak přejít od jednoduchého hlasování k přijetí. N může přijmout jinou hodnotu W, i když pro ni nehlasoval, a dokonce ani pokud pro ni nevidí kvórum. Pro rozhodnutí změnit svůj hlas stačí vidět blokující množinu uzlů, které přijaly W. Blokující množina je po jednom uzlu z každého z průřezů kvór N. Jak název napovídá, je schopná blokovat jakoukoliv jinou hodnotu. Pokud všechny uzly v takové množině přijmou W, pak (podle věty 8) nikdy nebude možné vytvořit kvórum přijímající jinou hodnotu, a proto je pro N také bezpečné přijmout W.
Uzel N se třemi průřezy kvór.
B-D-F je blokující množina pro N: zahrnuje po jednom uzlu z každého z průřezů N.
B-E je také blokující množina pro N, protože E se objevuje ve dvou průřezech N.
Ale blokující množina není kvórum. Bylo by příliš snadné podvést uzel N, aby přijal požadovanou hodnotu, pokud by stačilo hacknout pouze jeden uzel v každém průřezu N. Proto přijetí hodnoty není ještě konec hlasování. Místo toho musí N potvrdit hodnotu, to znamená vidět kvórum uzlů, které ji přijímají. Pokud se dostane tak daleko, pak, jak dokazuje technický dokument SCP (ve větě 11), zbytek sítě také nakonec potvrdí stejnou hodnotu, takže N dokončí federativní hlasování s určitou hodnotou jako výsledkem.
Federativní hlasování.
Hlasovací proces, přijímání a potvrzování tvoří jeden úplný kolo federativního hlasování. Konsensuální protokol Stellar kombinuje mnoho takových kol k vytvoření plně konsensuálního systému.
Konsensuální protokol Stellar
Dvě nejdůležitější vlastnosti konsensuálního systému – bezpečnost a odolnost. Konsensuální algoritmus je "bezpečný", pokud nikdy nemůže poskytnout různé výsledky různým účastníkům (kopie historie Boba nikdy nebude v rozporu s Kájou). "Odolnost" znamená, že algoritmus vždy vyprodukuje výsledek, tedy nezasekne se.
Popisovaný postup federativního hlasování je bezpečný v tom smyslu, že pokud uzel potvrdí hodnotu V, žádný jiný uzel nepotvrdí jinou hodnotu. Ale "nepotvrdí jinou hodnotu" neznamená, že nutně něco potvrdí. Účastníci mohou hlasovat pro tak velké množství různých hodnot, že nic nedosáhne prahu přijetí. To znamená, že v federativním hlasování chybí odolnost.
Konsensuální protokol Stellar používá federativní hlasování tak, aby zaručil jak bezpečnost, tak odolnost. (Záruky bezpečnosti a odolnosti SCP mají teoretický limit. Konstrukce vybírá velmi silnou záruku bezpečnosti, obětováním mírným oslabením odolnosti, ale s ohledem na dostatečný čas, konsensus s vysokou pravděpodobností bude dosažen). Jinými slovy, myšlenka spočívá v tom, že se provede několik federativních hlasování o několika hodnotách, dokud jedna z nich neprojde úplně všemi fázemi hlasování SCP, popsanými níže.
Hodnoty, o které SCP usiluje o konsensus, mohou být historií transakcí nebo objednávkou oběda, či čímkoli jiným, ale je důležité poznamenat, že to nejsou hodnoty, které jsou přijímány nebo potvrzovány. Místo toho federativní hlasování probíhá o prohlášeních o těchto hodnotách.
První kola federativního hlasování probíhají na fázi nominace (nominacní fáze), na skupině prohlášení typu „Navrhuji V“, možné pro mnoho různých hodnot V. Cílem nominace je najít jedno nebo více prohlášení, která projdou schválením a potvrzením.
Po nalezení ověřitelných kandidátů přechází SCP k rozhodovací fázi, jejímž cílem je nalézt určitý hlasovací lístek (tj. kontejner pro navrhovanou hodnotu) a kvórum, které může vyhlásit commit pro něj (commit). Pokud kvórum provede commit hlasovacího lístku, jeho hodnota se přijímá jako konsensus. Ale než může uzel hlasovat pro commit hlasovacího lístku, musí nejprve potvrdit zrušení všech hlasovacích lístků s nižší hodnotou čítače. Tyto kroky — zrušení hlasovacích lístků za účelem nalezení toho, pro který lze potvrdit commit — zahrnují několik kol federálního hlasování o různých tvrzeních o hlasovacích lístcích.
V následujících sekcích jsou podrobněji popsány nominace a hlasování.
Nominace
Na začátku fáze nominace může každý uzel spontánně zvolit hodnotu V a hlasovat pro prohlášení „Nominují V“. Cílem v této fázi je potvrdit nominaci určité hodnoty prostřednictvím federálního hlasování.
Je možné, že dostatečný počet uzlů hlasuje pro dostatečně různá tvrzení a žádná nominace nemůže dosáhnout přijetí. Proto kromě přenosu vlastních nominací uzly „odrážejí“ nominace svých sousedů. Odrážení (echo) znamená, že pokud uzel hlasuje pro nominaci V, ale vidí zprávu od souseda, který hlasuje pro nominaci W, nyní bude hlasovat pro nominaci jak V, tak W. (Ne všechny hlasy sousedů jsou během nominace odráženy, protože to může vést k výbuchu různých nominantů. SCP zahrnuje mechanismus regulace těchto hlasů. Krátce řečeno, existuje vzorec pro určení „priorit“ souseda z pohledu uzlu a odráženy jsou pouze hlasy vysoce prioritních uzlů. Čím déle nominace trvá, tím nižší je prah, takže uzel rozšiřuje sadu sousedů, jejichž hlasy bude odrážet. Vzorec priority jako jeden z vstupních údajů zahrnuje číslo slotu, takže vysoce prioritní peer může být pro jeden slot nízkoprioritní pro jiný, a naopak).
Konceptuálně je vyhlášení V i W oddělenými federativními hlasy, přičemž každý z nich má schopnost dosáhnout přijetí nebo potvrzení. V praxi protokoly SCP balí tyto jednotlivé hlasy dohromady.
I když hlasování pro vyhlášení V znamená slib, že nikdy nebudete hlasovat proti vyhlášení V, na aplikační úrovni – v tomto případě SCP – se určuje, co znamená "proti". SCP nevidí prohlášení, které konfliktuje s hlasováním "Vyhlašuji X", tedy neexistuje žádná zpráva "Jsem proti vyhlášení X", takže uzel může hlasovat pro vyhlášení jakýchkoli hodnot. Mnohé z těchto nominací nikam nevedou, ale nakonec bude uzel schopen přijmout nebo potvrdit jednu nebo více hodnot. Jakmile je nominant potvrzen, stává se kandidátem.
Vyhlášení SCP pomocí federativního hlasování. Může být mnoho hodnot "B" navrhovaných rovnocennými uzly a "odrážených" uzlem.
Návrh kandidátů může vést k výskytu několika potvrzovaných kandidátů. Proto SCP vyžaduje, aby aplikační úroveň poskytla nějakou metodu sloučení kandidátů do jednoho kompozitu (composite). Metoda sloučení může být jakákoli. Hlavní je, že pokud je tato metoda deterministická, každý uzel sloučí stejné kandidáty. V systému hlasování na oběd "sloučení" může znamenat jednoduše odmítnutí jednoho z dvou kandidátů. (Ale deterministicky: každý uzel musí vybrat stejnou hodnotu k zrušení. Například dřívější výběr v abecedním pořadí). V platební síti Stellar, kde probíhá hlasování o historii transakcí, sloučení dvou navrhovaných nominantů předpokládá sloučení transakcí, které obsahují, a posledních z jejich dvou časových značek.
Technický popis SCP dokazuje (věta 12), že na konci fáze vyhlášení se síť nakonec sbíhá k jednomu kompozitu. Ale je tu problém: federativní hlasování je asynchronní protokol (stejně jako SCP). Jinými slovy, uzly nejsou koordinovány podle času, ale pouze podle zpráv, které posílají. Z pohledu uzlu není jasné, kdy skončila fáze nominace. I když všechny uzly nakonec dorazí ke stejnému kompozitu, mohou si na této cestě vybrat různé trasy a vytvářet po cestě různé kandidáty, aniž by bylo možné říct, který z nich je konečný.
Ale to nevadí. Nominace je jen příprava. Hlavní je omezit počet kandidátů k dosažení konsensu, který probíhá v procesu hlasování (balloting).
Hlasování
Hlasovací lístek je pár , kde counter je celé číslo začínající na 1 a value je kandidát z fáze nominace. Může to být vlastní kandidát uzlu nebo kandidát sousedního uzlu, který byl tímto uzlem přijat. Jinými slovy, při hlasování se opakovaně pokoušíme donutit síť dosáhnout konsensu o nějakém kandidátovi v nějakém hlasovacím lístku prostřednictvím potenciálně mnoha federativních hlasování o prohlášeních o hlasovacích lístcích. Počítadla v hlasovacích lístcích sledují učiněné pokusy a hlasovací lístky s vyššími počítadly mají prioritu před hlasovacími lístky s nižšími počítadly. Pokud hlasovací lístek uvízne, začne nové hlasování, nyní o hlasovacím lístku .
Je důležité rozlišovat hodnoty (například jak by měla vypadat objednávka na oběd: pizza nebo saláty), hlasovací lístky (pár counter-value) a prohlášení o hlasovacích lístcích. Kolo SCP zahrnuje několik kol federativního hlasování, zejména na taková prohlášení:
- „Jsem připraven potvrdit hlasovací lístek B“ a
- „Vyhlašuji potvrzení hlasovacího lístku B“
Z pohledu tohoto uzlu je konsensus dosažen, když najde hlasovací lístek B, pro který může potvrdit (to znamená najít kvórum přijímající) prohlášení „Vyhlašuji potvrzení hlasovacího lístku B“. Od této chvíle je možné bezpečně jednat podle hodnoty uvedené v B – například provést tuto objednávku na oběd. To se nazývá externalizace hodnoty. Jakmile je potvrzeno přijetí hlasovacího lístku, může si uzel být jistý, že kterýkoli jiný uzel provedl externalizaci téže hodnoty nebo ji nutně provede v budoucnu.
Ačkoliv jsou konceptuálně mnohá federativní hlasování prováděna na základě žádostí o různé volební lístky, nevyměňují se tolik zpráv, protože každá zpráva obsahuje řadu volebních lístků. Jedna zpráva tak propaguje stav mnoha federativních hlasování najednou, například: „Přijímám komit volebních lístků v rozmezí od do .”
Co znamenají termíny „připraven” (prepared) a „komit” (commit)?
Uzly hlasují pro komit volebního lístku, když jsou přesvědčeny, že jiné uzly neprovedou komit volebních lístků s jinými hodnotami. Přesvědčení o tom je cílem přípravy prohlášení. Hlasování, ve kterém se říká: „Jsem připraven k comitu volebního lístku B“, je slibem, že nikdy neprovedou komit volebního lístku menšího než B, tj. s menšími čítači (SCP vyžaduje, aby hodnoty ve volebních lístcích měly určitý pořádek. Takže volební lístek je menší než , pokud N1<N2, a také pokud N1=N2 a V1<V2). Tyto menší volební lístky jsou během přípravného hlasování „zrušeny” (aborted), zatímco B je považováno za „připravené”.
Proč „Jsem připraven k comitu volebního lístku V” znamená „Slibuji, že nikdy neprovedu komit volebních lístků menších než V”? Protože SCP definuje abort jako protiklad commit. Hlasování o přípravě volebního lístku naznačuje také hlasování o zrušení některých dalších volebních lístků, a jak jsme se již zmínili, hlasování pro něco znamená slib, že proti tomu nikdy nebudou hlasovat.
Než uzel vysílá komit, musí nejprve najít volební lístek, který může potvrdit jako připravený. Jinými slovy, provádí federativní hlasování na téma „Jsem připraven k comitu volebního lístku B“, možná pro mnoho různých volebních lístků, dokud nenajde ten, který akceptuje kvórum.
Odkud pocházejí hlasovací lístky pro přípravu hlasování? Nejprve uzel vysílá přípravu na hlasování pro , kde C je kandidát-kompozit, vytvořený v rámci nominace. Nicméně i po zahájení přípravy na hlasování může nominace vést k vzniku dalších kandidátů, kteří se stanou novými hlasovacími lístky. Mezitím mohou mít piri různé kandidáty a mohou formulovat blokující množinu, která přijetí "Jsem připraven k potvrzení hlasovacího lístku B2" přesvědčí uzel také k přijetí. Nakonec zde existuje časový mechanismus, který generuje nové kolo federativního hlasování na nových hlasovacích lístcích s vyššími čítači, pokud se aktuální hlasovací lístky zaseknou.
Jakmile uzel najde hlasovací lístek B, který může potvrdit jako připravený, vysílá novou zprávu "Potvrzení hlasovacího lístku B". Toto hlasování říká pirům, že uzel se nikdy nevzdá B. Ve skutečnosti, pokud B představuje hlasovací lístek , pak "Potvrzení hlasovacího lístku " znamená bezpodmínečný souhlas hlasovat pro připravenost každého hlasovacího lístku od do . Tato dodatečná hodnota pomáhá ostatním uzlům dohnat pira s potvrzením, pokud jsou stále v dřívějších fázích protokolu.
V této fázi je třeba ještě jednou zdůraznit, že se jedná o asynchronní protokoly. Jen proto, že jeden uzel posílá hlasy pro potvrzení, neznamená, že jeho vrstevníci to dělají také. Někteří z nich stále mohou hlasovat o prohlášeních pro přípravu na hlasování, jiní již možná externilizovali hodnotu. SCP vysvětluje, jak by uzel měl zpracovávat každý typ peer-to-peer zprávy bez ohledu na jeho fázi.
Pokud zpráva „Prohlašuji commit “ nemůže být přijata nebo potvrzena, existuje šance na přijetí nebo potvrzení zprávy nebo — nebo v každém případě jakékoli zprávy se hodnotou C a ne jinou, protože uzel už slíbil nikdy neodvolat . V době, kdy uzel přenáší hlasy pro commit, to bude C nebo nic, v závislosti na tom, jak daleko se dostane konsensus. Nicméně to zatím není pro uzel dostačující k exter-nalizaci C. Některé byzantské úniky (sestávající z méně než kvora, na základě našich předpokladů o bezpečnosti) mohou uzlu lhát. Přijetí a následné potvrzení určité zprávy (nebo rozsahu zpráv) je to, co poskytuje uzlu jistotu, že konečně může exter-nalizovat C.
Hlasování SCP pomocí federativního hlasování. Nezobrazeno: v kterémkoli okamžiku se může spustit časovač, který zvýší počet v hlasování (a možná vytvoří novou kompozici z dodatečně navržených kandidátů).
A to je vše! Jakmile síť dosáhne konsensu, je připravena dělat to znovu a znovu. V platební síti Stellar se to děje přibližně každých 5 sekund: úkol, který vyžaduje jak bezpečnost, tak odolnost, zaručenou SCP.
SCP může toho dosáhnout opřením se o několik kol federativního hlasování. Federativní hlasování bylo umožněno konceptem kvórumových řezů: sadou rovnocenných uzlů, kterým se každý uzel rozhodl důvěřovat jako součást svého (subjektivního) kvóra. Tato konfigurace znamená, že lze dosáhnout konsensu i v síti s otevřeným členstvím a byzantskými podvody.
Další čtení
- Originální technický dokument SCP lze nalézt , a projektovaná specifikace pro jeho implementaci.
- Originální autor protokolu SCP David Mazieres zjednodušeně (ale stále technicky) vysvětluje jeho .
- Možná vás překvapilo, že v tomto článku nenajdete výrazy „těžba“ nebo „důkaz práce“. SCP tyto metody nepoužívá, ale některé jiné algoritmy konsensu je používají. Zain Wizerspoon napsal přístupný .
- jednoduché sítě, která dosahuje konsensu během jednoho úplného kola SCP.
- Pro čtenáře, kteří mají zájem o implementace SCP: viz. , používaný platební sítí Stellar, nebo , který jsem napsal pro lepší porozumění SCP.
Zdroj: habr.com
