Protokol Stellar consensus byl poprvé popsán v David Mazier v roce 2015. Jedná se o „federální byzantský systém dohod“, který umožňuje decentralizovaným počítačovým sítím bez lídra efektivně dosáhnout konsensu o rozhodnutí. Platební síť Stellar používá protokol Stellar Consensus Protocol (SCP) k udržení konzistentní historie transakcí, která je viditelná všem účastníkům.
Protokoly konsenzu jsou považovány za obtížně pochopitelné. 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 "federované hlasování", které je předmětem první poloviny vědeckého článku, je SCP. Ale to není pravda! To je jen důležitý stavební kámen, který druhá polovina článku používá k vytvoření aktuální Protokol hvězdného konsenzu.
V tomto článku stručně vysvětlíme, co je to „systém dohod“, co z něj může udělat „byzantský“ a proč udělat byzantský systém „federální“. Následně si vysvětlíme postup federovaného hlasování popsaný v článku SCP a nakonec vysvětlíme samotný protokol SCP.
Systémy dohod
Systém dohod umožňuje skupině účastníků dosáhnout konsensu na určité téma, například co si objednat k obědu.
Ve společnosti Interstellar jsme zavedli náš vlastní systém jídelních dohod: objednáváme, co říká náš provozní manažer John. Jedná se o jednoduchý a účinný systém dohod. Všichni Johnovi věříme 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 sám rozhodnout, že bychom se všichni měli stát vegany. Za týden nebo dva ho pravděpodobně svrhneme a předáme moc Elizabeth. Ale najednou miluje avokádo s ančovičkami a myslí si, že takoví by měli být všichni. Moc korumpuje. Je tedy lepší najít nějakou demokratičtě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 si nikdo neobjednal oběd, nebo pět lidí jinak, nebo diskuse táhne se do večera.
Zdálo by se, že řešení je jednoduché: hlasujte! To je ale zavádějící dojem. Kdo bude sbírat hlasovací lístky a hlásit výsledky? A proč by ostatní měli věřit tomu, co říká? Možná můžeme nejprve hlasujte pro vůdce, kterému věříme, že povede hlasování – ale kdo je povede nejprve hlasováním? Co když se nemůžeme shodnout na lídrovi? Nebo co když se dohodneme, ale tento vedoucí uvízne na schůzce nebo půjde na nemocenskou?
Podobné problémy se vyskytují v distribuovaných počítačových sítích. Všichni účastníci nebo uzly se musí dohodnout na nějakém rozhodnutí, například kdo je na řadě aktualizovat sdílený soubor nebo odstranit úlohu z fronty zpracování. V kryptoměnové síti si uzly musí opakovaně vybrat, jak celý příběh vypadá, z několika možných verzí, které si někdy odporují. Tato síťová dohoda poskytuje příjemci ujištění, že mince je (a) platná (ne padělaná) a (b) dosud nebyla utracena jinde. To také zajišťuje, že bude moci v budoucnu utratit mince, protože nový příjemce bude mít stejné záruky ze stejných důvodů.
Jakýkoli konsensuální systém v distribuované počítačové síti musí být odolný proti chybám: musí poskytovat konzistentní výsledky navzdory chybám, jako jsou pomalá spojení, nereagující uzly a nesprávné řazení zpráv. byzantský Systém dohod je navíc odolný vůči "byzantským" chybám: uzlům, které poskytují nepravdivé informace, ať už kvůli chybě nebo v úmyslném pokusu podkopat systém nebo získat nějakou výhodu. "Byzantská" tolerance chyb - schopnost důvěřovat skupinovému rozhodnutí, i když někteří členové skupiny mohou lhát nebo jinak nedodržovat pravidla rozhodování - se nazývá kteří se snažili koordinovat útok. u Anthonyho Stevense.
Vezměme si majitelku kryptocoinů Alici, která si musí vybrat mezi nákupem lahodné zmrzliny od Boba a splacením dluhu Carol. Možná chce Alice zaplatit oběma najednou podvodným utracením stejné mince. Aby to udělala, musí přesvědčit Bobův počítač, že mince nebyla nikdy zaplacena Carol, a přesvědčit počítač Carol, že mince nebyla nikdy vyplacena Bobovi. Byzantský systém dohod to prakticky znemožňuje, používá formu většinového pravidla tzv kvorum. Uzel v takové síti odmítne přejít na konkrétní verzi historie, dokud neuvidí, že dostatečný počet vrstevníků – kvorum – souhlasí s takovým přechodem. Jakmile se tak stane, vytvoří dostatečně velký hlasovací blok, aby přinutil zbývající uzly sítě souhlasit s jejich rozhodnutím. Alice může přinutit některé uzly, aby lhaly jejím jménem, ale pokud je síť dostatečně velká, její pokus bude přemožen hlasy poctivých uzlů.
Kolik uzlů je potřeba pro kvorum? Minimálně většinu, nebo spíše kvalifikovanou většinu pro boj proti chybám a podvodům. Ale abyste mohli počítat většinu, musíte znát celkový počet účastníků. V kanceláři Interstellar nebo při okresních volbách lze tato čísla snadno zjistit. Ale pokud je vaše skupina volně definovaná síť, do které mohou uzly vstupovat a opouštět libovolně bez souhlasu centra, pak potřebujete federální byzantský dohodový systém schopný určovat kvora nikoli z předem určeného seznamu uzlů, ale dynamicky, z neustále se měnícího a nevyhnutelně neúplného snímku uzlů v daném okamžiku.
Může se zdát nemožné vytvořit kvorum z pohledu jediného 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í. Bílá kniha SCP ukazuje, jak to provést pomocí procedury nazvané federálním hlasováním.
Pro netrpělivost
Zbytek článku podrobněji popisuje federované hlasování a protokol Stellar consensus. Pokud vás nezajímají podrobnosti, zde je obecný přehled procesu.
- Uzly provádějí kola federálního hlasování o „nominovaných“. Federální kolo hlasování znamená:
- Uzel hlasuje pro nějaké prohlášení, například „navrhuji hodnotu V“;
- Uzel naslouchá hlasům vrstevníků, dokud nenajde ten, který může „přijímat“;
- Uzel hledá "kvorum" pro toto tvrzení. Kvórum „potvrzuje“ nominovaného.
- Jakmile uzel může potvrdit jednoho nebo více kandidátů, pokusí se „připravit“ „hlasovací lístek“ prostřednictvím několika kol federálního hlasování.
- Jakmile je uzel schopen ověřit, že je hlasovací lístek připraven, pokusí se jej odevzdat ještě více koly federovaného hlasování.
- Jakmile uzel může potvrdit potvrzení hlasování, může „externalizovat“ hodnotu tohoto hlasování tím, že jej použije jako výsledek konsensu.
Tyto kroky zahrnují více kol federovaného hlasování, které společně tvoří jedno kolo SCP. Podívejme se blíže na to, co se děje při každém kroku.
Federované hlasování
Federované hlasování je postup pro určení, zda se síť může dohodnout na návrhu. V kole hlasování si každý uzel musí vybrat jednu z potenciálně mnoha možných hodnot. Nemůže to udělat, pokud si není jistý, že ostatní uzly v síti nezvolí jiný výsledek. Aby se to ujistilo, uzly si vyměňují záplavu zpráv tam a zpět, takže všichni potvrzenoŽe usnášeníschopnost uzly trvá to samé rozhodnutí. Zbytek této části vysvětluje pojmy v této větě a jak celý postup probíhá.
Kvora a segmenty kvora
Začněme definováním kvora. Jak jsme diskutovali výše, v decentralizované síti s dynamickým členstvím není možné předem znát počet uzlů, a tedy kolik jich je potřeba pro většinu. Federované hlasování řeší tento problém zavedením nové myšlenky kvórum přerušeno (část kvora): Malá sada vrstevníků, kterým uzel důvěřuje, že sdělují informace o stavu hlasování zbytku sítě. Každý uzel definuje svůj vlastní segment kvora (jehož se stává de facto členem).
Vytváření kvora začíná přerušením kvora. Pro každý uzel jsou přidány jeho řezané uzly. Poté jsou přidány výrazy slice tyto uzly a tak dále. Jak budete pokračovat, existuje stále více uzlů, které nemůžete přidat, protože jsou již zahrnuty v řezu. Když nejsou k dispozici žádné další nové uzly k přidání, proces se zastaví: vytvořili jsme kvorum „tranzitivním uzavřením“ části kvora počátečního uzlu.
Chcete-li najít kvorum z daného uzlu...
... přidat členy jeho řezu...
...pak přidáme slice členy těchto uzlů.
Pokračujeme, dokud nezůstanou žádné uzly pro přidání.
Nezbývají žádné uzly k přidání. Toto je kvorum.
Ve skutečnosti se každý uzel může objevit ve více než jednom řezu. Chcete-li vytvořit kvorum, vyberte pouze jeden z řezů a přidejte členy; pak vyberte libovolný řez pro každý z členů a přidejte členy to řezat a tak dále. To znamená, že každý uzel je členem mnoha možných kvor.
V každém kroku vyberte pouze jeden řez kvora.
Jedno možné kvorum. Nebo alternativa...
...vyberte další plátky...
…(když je to možné)…
... vytvoří další kvorum.
Jak uzel ví, ve kterých řezech jsou ostatní uzly? Stejně jako ostatní informace o jiných uzlech: z přenosů, které každý uzel vysílá do sítě, když se změní jeho stav hlasování. Každé vysílání obsahuje informace o řezech odesílajícího uzlu. Bílá kniha SCP nespecifikuje komunikační mechanismus. Implementace obvykle používají pro zaručené vysílání zpráv v celé síti.
Připomeňme, že v nefederálním byzantském systému dohod je kvorum definováno jako většina všech uzlů. Byzantský dohodový systém je navržen z hlediska otázky: kolik nepoctivých uzlů může systém tolerovat? V systému N uzlů navržených tak, aby přežily f selhání, by měl být uzel schopen dosáhnout pokroku tím, že obdrží zpětnou vazbu od N-f vrstevníků, protože f z nich může být mimo provoz. Ale poté, co jsme obdrželi odpověď od N−f vrstevníků, můžeme předpokládat, že všech f vrstevníků (od kterých uzel neobdržel odpověď) jsou ve skutečnosti poctiví. Tedy f z N−f vrstevníků (od kterých byla přijata odpověď) je škodlivých. Aby uzly dospěly ke stejnému konsenzu, většina zbývajících uzlů musí být poctivá, to znamená, že potřebujeme, aby N−f bylo větší než 2f nebo N > 3f. Takže typicky systém navržený tak, aby přežil f selhání, bude mít celkem N=3f+1 uzlů a velikost kvora 2f+1. Jakmile návrh projde prahem kvóra, je zbytek sítě přesvědčen, že jakékoli konkurenční návrhy neuspějí. Takto síť konverguje k výsledku.
Ale ve federálním systému byzantských dohod nejenže nemůže existovat většina (protože nikdo nezná celkovou velikost sítě), ale koncept většiny je zcela zbytečný! Pokud je členství v systému otevřené, pak někdo může získat většinu jednoduše provedením takzvaného Sybil útoku: opakovaného připojování se k síti přes více uzlů. Proč se tedy může nazývat tranzitivní uzavření řezu kvorum, a jak dokáže potlačit konkurenční návrhy?
Technicky v žádném případě! Představte si síť šesti uzlů, kde jsou dvě trojice navzájem izolovány ve svých řezech kvora. První podskupina může učinit rozhodnutí, o kterém druhá nikdy neuslyší, a naopak. Neexistuje způsob, jak by tato síť dosáhla konsensu (kromě náhody).
Proto SCP vyžaduje, aby pro federované hlasování (a aby mohly platit důležité teorémy článku) síť musí mít vlastnost tzv. průsečík kvor. V síti s touto vlastností se libovolná dvě kvora, která lze sestavit, vždy překrývají alespoň v jednom uzlu. Pro určení převažujícího sentimentu sítě je to stejně dobré jako mít většinu. Intuitivně to znamená, že pokud jakékoli kvorum souhlasí s prohlášením X, žádné jiné kvorum nemůže souhlasit s ničím jiným, protože bude nutně zahrnovat nějaký uzel z prvního kvora, které již hlasovalo pro X.
Pokud dojde k průniku kvor v síti...
...pak můžete sestavit jakákoli dvě kvora...
...budou se vždy protínat.
(Samozřejmě, že se překrývající se uzly mohou ukázat jako byzantsky ležící nebo jinak špatné. V tomto případě průnik kvora vůbec nepomáhá síti se dohodnout. Z tohoto důvodu je mnoho výsledků v bílé knize SCP založeno na explicitní předpoklady, jako například to, co zbývá při křížení kvora sítě i po odstranění špatných uzlů. Pro zjednodušení nechme tyto předpoklady implicitní 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é křížení kvora. Ale jsou dva důvody, proč tomu tak je.
Prvním důvodem je existence samotného internetu. Internet je dokonalým příkladem sítě nezávislých uzlů s protínajícími se kvory. Většina uzlů na internetu se připojuje pouze k několika dalším místním uzlům, ale tyto malé sady se dostatečně překrývají, takže každý uzel může být dosažitelný z každého jiného uzlu po nějaké trase.
Druhý důvod je specifický pro platební síť Stellar (nejčastější použití SCP). Každé aktivum v síti Stellar má svého emitenta a směrnice Stellar vyžadují, aby každý emitent určil jeden nebo více uzlů v síti pro zpracování žádostí o odkup. Je ve vašem nejlepším zájmu přímo nebo nepřímo zahrnout tyto uzly do segmentů kvora pro každé aktivum, které vás zajímá. Kvora pro všechny uzly zajímající se o dané aktivum se pak budou překrývat alespoň v těchto výkupních uzlech. Uzly, které mají zájem o více aktiv, zahrnou všechny výkupní uzly příslušných emitentů do svých segmentů kvora a budou se snažit sloučit všechna aktiva dohromady. Kromě toho všechna aktiva, která nejsou tímto způsobem propojena s ostatními v síti, a by neměl být připojen - toto je navrženo tak, aby nedocházelo k překrývání kvora pro tuto síť (například banky z dolarové zóny chtějí někdy obchodovat s bankami z eurozóny a bankami z peso zóny, takže jsou ve stejné síti, ale žádná z nich se starají o samostatnou síť dětí prodávajících baseballové karty).
Samozřejmě, ожидание křížení kvora není záruka. Jiné byzantské systémy dohod vděčí za svou složitost z velké části garanci kvor. Důležitou inovací SCP je, že odstraňuje odpovědnost za vytváření kvor ze samotného konsensuálního algoritmu a přenáší jej na aplikační úroveň. Ačkoli je tedy federované hlasování dostatečně obecné na to, aby bylo možné hlasovat o jakékoli otázce, jeho spolehlivost ve skutečnosti kriticky závisí na širším významu těchto významů. Některá hypotetická použití nemusí být tak vhodná pro vytváření dobře propojených sítí jako jiná.
Hlasování, přijetí a potvrzení
Ve federovaném volebním kole začne uzel volitelně hlasovat pro nějakou hodnotu V. To znamená vysílat zprávu do sítě: „Jsem uzel N, mé části kvora jsou Q a hlasuji pro V.“ Když uzel hlasuje tímto způsobem, slibuje, že nikdy nehlasoval proti V a nikdy nebude.
Ve vysílání peer-to-peer každý uzel vidí, jak hlasují ostatní. Jakmile uzel shromáždí dostatek těchto zpráv, může sledovat segmenty kvora a pokusit se najít kvora. Pokud uvidí kvorum kolegů, kteří také hlasují pro V, může přistoupit k přijetí V a vysílat tuto novou zprávu do sítě: „Jsem uzel N, mé části kvora jsou Q a přijímám V.“ Přijetí poskytuje silnější záruku než prosté hlasování. Když uzel hlasuje pro V, nikdy nemůže hlasovat pro jiné možnosti. Ale pokud uzel akceptuje V, žádný uzel v síti nikdy nepřijme druhou možnost (věta 8 v bílé knize SCP to dokazuje).
Samozřejmě je vysoká pravděpodobnost, že nebude okamžitě usnášeníschopné uzly, které souhlasí s V. Jiné uzly mohou hlasovat pro jiné hodnoty. Existuje však další způsob, jak uzel přejít od jednoduchého hlasování k přijetí. N může přijmout jinou hodnotu pro W, i když pro ni nehlasoval, a i když pro ni nevidí kvórum. Chcete-li se rozhodnout změnit svůj hlas, podívejte se blokovací sada uzly, které přijaly W. Blokovací sada je jeden uzel z každého segmentu kvora N. Jak název napovídá, může blok jakýkoli jiný význam. Pokud všechny uzly v takové množině přijmou W, pak (podle věty 8) nebude nikdy možné vytvořit kvorum, které nabývá jiné hodnoty, a proto je také bezpečné, aby N přijal W.
Uzel N se třemi řezy kvora.
BDF je blokovací sada pro N: obsahuje jeden uzel z každého z řezů N.
BE je také blokovací sada pro N, protože E se objevuje ve dvou řezech N.
Blokovací sada však není usnášeníschopná. Bylo by příliš snadné oklamat uzel N, aby přijal požadovanou hodnotu, pokud by stačilo hacknout pouze jeden uzel v každém z řezů N. Proto přijetím hodnoty hlasování nekončí. Místo toho musí N hodnotu potvrdit, to znamená vidět kvorum uzlů, které ji přijme. Pokud to dojde tak daleko, pak, jak dokazuje whitepaper SCP (ve větě 11), zbytek sítě nakonec potvrdí stejnou hodnotu, takže N ukončí federované hlasování s určitou hodnotou jako výsledkem.
Federované hlasování.
Proces hlasování, přijetí a potvrzení tvoří jedno celé kolo federovaného hlasování. Protokol Stellar consensus spojuje mnoho z těchto kol, aby vytvořil kompletní systém konsenzu.
Protokol Stellar Consensus Protocol
Dvě nejdůležitější vlastnosti konsenzuálního systému jsou − zabezpečení и přežití. Algoritmus konsensu je „bezpečný“, pokud nikdy nemůže poskytnout různé výsledky různým účastníkům (Bobova kopie historie nebude nikdy v rozporu s Carol). „Livability“ znamená, že algoritmus vždy vytvoří výsledek, to znamená, že se nezasekne.
Popsaný federální postup hlasování bezpečný v tom smyslu, že pokud uzel potvrdí hodnotu V, žádný jiný uzel nepotvrdí jinou hodnotu. Ale „nepotvrdí jiný význam“ neznamená, že to nutně něco potvrdí. Účastníci mohou hlasovat pro tolik různých hodnot, že nic nedosáhne prahu přijetí. To znamená, že při federálním hlasování neexistuje přežití.
Protokol Stellar consensus využívá federované hlasování způsobem, který zajišťuje bezpečnost i přežití. (Záruky bezpečnosti a přežití SCP mají teoretický limit. Návrh volí velmi silnou záruku bezpečnosti, obětuje malé zmírnění přežití, ale pokud bude dostatek času, je vysoce pravděpodobné, že bude dosaženo konsensu.) Stručně řečeno, myšlenkou je mít více federovaných hlasů pro více hodnot, dokud jeden z nich neprojde všemi níže popsanými fázemi hlasování SCP.
Hodnoty, na kterých SCP hledá shodu, mohou být transakční historie nebo obědová objednávka nebo něco jiného, ale je důležité si uvědomit, že to nejsou hodnoty, které jsou přijímány nebo potvrzeny. Místo toho dochází k federálnímu hlasování podle prohlášení o těchto hodnotách.
První kola federálního hlasování se konají dne etapa nominace (nominační fáze), na sadě prohlášení jako „Nominuji V“, možná pro mnoho různých hodnot V. Účelem nominace je najít jedno nebo více prohlášení, která projdou přijetím a potvrzením.
Po nalezení ověřitelných kandidátů přechází SCP do fáze hlasování, kde je cílem najít určité бюллетень (tj. kontejner pro navrhovanou hodnotu) a kvorum, které může deklarovat spáchat za to (zavázat se). Pokud kvorum provede hlasování, jeho hodnota je přijata jako konsensus. Ale předtím, než může uzel hlasovat o potvrzení hlasování, musí nejprve potvrdit zrušení všechny hlasovací lístky s nižší protihodnotou. Tyto kroky – zrušení hlasovacích lístků za účelem nalezení takového, který lze potvrdit – zahrnují více kol federovaného hlasování o žádostech o více hlasování.
Následující části popisují nominaci a hlasování podrobněji.
Jmenování
Na začátku nominační fáze si každý uzel může spontánně vybrat hodnotu pro V a hlasovat pro výrok „Nominuji V“. Cílem v této fázi je potvrdit nominaci nějaké hodnoty prostřednictvím federálního hlasování.
Možná dost uzlů hlasuje o dostatečně odlišných návrzích, takže žádná nominace nemůže dosáhnout prahu přijetí. Proto uzly kromě vysílání vlastních nominačních hlasů „odrážejí“ nominace svých kolegů. Echo znamená, že pokud uzel hlasuje pro nominaci V, ale uvidí zprávu od souseda hlasujícího pro nominaci W, bude nyní hlasovat pro V i W. (Ne všechny hlasy kolegů se během nominace odrážejí, protože to může vést k explozi různí nominovaní. SCP obsahuje mechanismus pro regulaci těchto hlasů. Stručně řečeno, existuje vzorec pro určení „priority“ peer z pohledu uzlu a zohledňují se pouze hlasy uzlů s vysokou prioritou. Čím delší je nominace zabírá, tím nižší je práh, takže uzel rozšíří množinu kolegů, jejichž hlasy bude odrážet. Vzorec priority zahrnuje číslo slotu jako jeden ze svých vstupů, takže partner s vysokou prioritou pro jeden slot může být partner s nízkou prioritou pro jiný a naopak).
Koncepčně je nominace paralelní, V i W jsou samostatné federální hlasy, z nichž každý je samostatně schopen dosáhnout přijetí nebo potvrzení. V praxi zprávy protokolu SCP tyto jednotlivé hlasy balí dohromady.
Ačkoli hlasování pro nominaci V je příslibem, že nikdy nebudete hlasovat proti nominaci V, je to na aplikační úrovni – v tomto případě SCP –, co znamená „proti“. SCP nevidí prohlášení, které by bylo v rozporu s hlasováním „Nominuji X“, to znamená, že neexistuje zpráva „Jsem proti nominaci X“, takže uzel může hlasovat pro nominaci jakýchkoli hodnot. Mnoho z těchto nominací nikam nevede, ale nakonec bude uzel schopen přijmout nebo potvrdit jednu nebo více hodnot. Jakmile je nominovaný potvrzen, stává se jím kandidát.
Nominace SCP pomocí federovaného hlasování. Může existovat mnoho hodnot „B“ předložených kolegy a „odrážených“ uzlem.
Výsledkem nominací může být více potvrzených kandidátů. Proto SCP vyžaduje, aby aplikační vrstva poskytovala nějakou metodu kombinování kandidátů do jednoho kompozitní (kompozitní). Způsob spojování může být jakýkoli. Hlavní věc je, že pokud je tato metoda deterministická, pak každý uzel bude kombinovat stejné kandidáty. V poledním volebním systému může „sjednocení“ jednoduše znamenat odmítnutí jednoho ze dvou kandidátů. (Ale deterministickým způsobem: každý uzel musí vybrat stejnou hodnotu k resetování. Například dřívější výběr v abecedním pořadí). V platební síti Stellar, kde se hlasuje o historii transakcí, sloučení dvou navržených kandidátů zahrnuje sloučení transakcí, které obsahují, a poslední z jejich dvou časových razítek.
SCP whitepaper dokazuje (Věta 12), že na konci fáze rozšíření síť nakonec konverguje do jediného kompozitu. Ale je tu problém: federované hlasování je asynchronní protokol (jako SCP). Jinými slovy, uzly nejsou koordinovány časem, ale pouze zprávami, které odesílají. Z pohledu uzlu není jasné kdy skončilo fáze prodloužení. A i když všechny uzly nakonec dosáhnou stejného kompozitu, mohou se vydat různými cestami, vytvářet různé kompozitní kandidáty a nikdy nemohou říct, která z nich je ta konečná.
Ale je to normální. Nominace je jen příprava. Hlavní je omezit počet kandidátů pro dosažení konsensu, ke kterému v procesu dochází hlasování (hlasování).
Běh
Bulletin je pár , kde counter je celé číslo začínající na 1 a hodnota je kandidátem ve fázi nominace. Může to být vlastní kandidát uzlu nebo kandidát sousedního uzlu přijatý tímto uzlem. Zhruba řečeno, hlasování zahrnuje opakované pokusy přimět síť, aby dosáhla shody na nějakém kandidátovi na nějakém hlasování tím, že bude potenciálně mnoho federovaných hlasů na hlasovacích prohlášeních. Počítadla na hlasovacích lístcích zaznamenávají provedené pokusy a lístky s vyšším počtem mají přednost před lístky s nižším počtem. Pokud newsletter zasekne, začne nové hlasování, nyní na hlasovacím lístku .
Je důležité rozlišovat hodnoty (například jaká by měla být objednávka oběda: pizza nebo saláty), informační bulletiny (protihodnotový pár) a prohlášení o hlasovacích lístcích. Kolo SCP zahrnuje několik kol federálního hlasování, zejména o následujících prohlášeních:
- "Jsem připraven odevzdat hlasovací lístek B" a
- "Oznamuji potvrzení hlasování B"
Z pohledu daného uzlu je konsensu dosaženo, když najde hlasovací lístek B, pro který může potvrdit (tj. najít kvórum přijímající) prohlášení „Potvrdím hlasování B“. Od tohoto okamžiku je bezpečné jednat podle hodnoty uvedené v B – například zadáním této objednávky oběda. To se nazývá externalizace významy. Jakmile je potvrzeno přijetí hlasovacího lístku, uzel si může být jistý, že jakýkoli jiný uzel externalizoval stejnou hodnotu nebo tak učiní v budoucnu.
Ačkoli mnoho federovaných hlasování je koncepčně prováděno na základě požadavků na mnoho různých hlasovacích lístků, nevyměňují si tolik zpráv, protože každá zpráva obsahuje určitý počet hlasovacích lístků. Jedna zpráva tak propaguje stav mnoha federovaných hlasů najednou, například: „Přijímám závazné hlasovací lístky od před "
Co znamenají pojmy „připraven“ a „zavázat se“?
Uzel hlasuje pro odevzdání hlasování, když si je jistý, že ostatní uzly neprovedou hlasování s jinými hodnotami. Přesvědčit o tom je účelem přípravy žádosti. Hlasování, které říká „Jsem připraven odevzdat hlasovací lístek B“ je příslib, že nikdy neodevzdám hlasovací lístek menší než B, tj. s menším počtem (SCP vyžaduje, aby hodnoty v hlasovacích lístcích byly v určitém pořadí. Zpravodaj tedy méně , pokud N1
Proč „Jsem připraven odevzdat hlasovací lístek B“ znamená „Slibuji, že nikdy neprovedu hlasovací lístky menší než B“? Protože SCP definuje abort jako opak potvrzení. Hlasování pro přípravu hlasovacího lístku zahrnuje také hlasování o diskvalifikaci některých dalších hlasovacích lístků, a jak jsme již diskutovali dříve, hlasovat pro jednu věc je slib, že nikdy nebudu hlasovat proti.
Před vysíláním commitu musí uzel nejprve najít bulletin, který může potvrdit jako připravený. Jinými slovy, provádí sdružené hlasování na téma „Jsem připraven odevzdat hlasování B“, případně na mnoha různých hlasovacích lístcích, dokud nenajde ten, který přijímá kvórum.
Odkud pocházejí hlasovací lístky pro přípravu hlasování? Nejprve uzel vysílá přípravy k hlasování pro <1,C>, kde C je složený kandidát vytvořený ve fázi nominace. I po zahájení příprav na hlasování však mohou nominace vést k tomu, že se objeví další kandidáti, kteří se stanou novými kandidáty. Mezitím mohou mít kolegové různé kandidáty a mohou vytvořit blokovací sadu, která akceptuje „Jsem připraven odevzdat hlasování B2“, což přesvědčí uzel, aby to také přijal. Konečně existuje mechanismus časového limitu, který generuje nová kola federovaného hlasování o nových hlasovacích lístcích s vyšším počtem, pokud jsou aktuální hlasovací lístky zaseknuté.
Jakmile uzel najde hlasovací lístek B, který může potvrdit jako připravený, vyšle novou zprávu „Potvrdit hlasování B“. Toto hlasování říká kolegům, že uzel se nikdy nevzdá B. Ve skutečnosti, pokud B je hlasovací lístek a poté „Potvrdit hlasování “ znamená bezpodmínečný souhlas hlasovat pro připravenost každého hlasovacího lístku od na <∞, s>. Tato dodatečná hodnota pomáhá ostatním kolegům dohnat partnera odevzdání, pokud jsou stále v dřívějších fázích protokolu.
V této fázi je vhodné ještě jednou zdůraznit, že se jedná o asynchronní protokoly. Jen proto, že jeden uzel posílá souhlasy pro odevzdání, neznamená to, že to dělají i jeho kolegové. Někteří z nich možná ještě hlasují o prohlášeních při přípravě na hlasování, jiní už možná jejich význam externalizovali. SCP vysvětluje, jak by měl uzel zpracovat každý typ rovnocenné zprávy bez ohledu na její fázi.
Pokud se zobrazí zpráva „Ohlásil jsem potvrzení » nelze přijmout nebo potvrdit, tj. pravděpodobnost přijetí nebo potvrzení zprávy nebo - nebo v každém případě jakýkoli hlasovací lístek s hodnotou C a ne žádný jiný, protože uzel již slíbil, že nikdy nezruší . V době, kdy uzel odvysílá hlasy pro odevzdání, bude to C nebo nic, v závislosti na tom, jak daleko dojde shoda. To však ještě nestačí k tomu, aby uzel externalizoval C. Někteří byzantští kolegové (kteří tvoří méně než kvorum, na základě našich bezpečnostních předpokladů) mohou uzlu lhát. Přijetí a následné potvrzení některého hlasovacího lístku (nebo rozsahu hlasovacích lístků) dává uzlu jistotu, že konečně externalizuje C.
SCP hlasování prostřednictvím federálního hlasování. Nezobrazeno: Časomíra se může kdykoli spustit, čímž se zvýší počet při hlasování (a možná vznikne nová sestava dalších nominovaných kandidátů).
A to je všechno! Jakmile síť dosáhne konsensu, je připravena to dělat znovu a znovu. V platební síti Stellar se to děje přibližně každých 5 sekund: výkon, který vyžaduje bezpečnost a přežití garantované SCP.
SCP toho může dosáhnout tím, že se bude spoléhat na více kol federovaného hlasování. Federované hlasování umožňuje koncept segmentů kvora: sady vrstevníků, kterým se každý uzel rozhodl důvěřovat jako součást svého (subjektivního) kvora. Tato konfigurace znamená, že konsensu lze dosáhnout i v síti s otevřeným členstvím a byzantskými podvody.
Další čtení
- Originál white paper SCP lze nalézt a návrh specifikací pro jeho realizaci.
- Původní autor protokolu SCP David Mazier to vysvětluje zjednodušeně (ale stále technicky). .
- Možná vás překvapilo, že jste v tomto článku nenašli výrazy „těžba“ nebo „důkaz práce“. SCP tyto metody nepoužívá, ale některé jiné konsensuální algoritmy ano. Zane Witherspoon napsal přístupně .
- jednoduchá síť, která dosáhne konsensu v jednom úplném kole SCP.
- Pro čtenáře, kteří se zajímají o implementace SCP: viz , používané platební sítí Stellar, popř , který jsem napsal pro lepší pochopení SCP.
Zdroj: www.habr.com