Protokol Hviezdneho konsenzu bol prvýkrát opísaný v r David Mazier v roku 2015. Ide o „federálny byzantský systém dohôd“, ktorý umožňuje decentralizovaným počítačovým sieťam bez vodcu efektívne dosiahnuť konsenzus o rozhodnutí. Platobná sieť Stellar používa protokol Stellar Consensus Protocol (SCP) na udržiavanie konzistentnej histórie transakcií, ktorá je viditeľná pre všetkých účastníkov.
Konsenzuálne protokoly sa považujú za ťažko zrozumiteľné. SCP je jednoduchší ako väčšina z nich, ale stále zdieľa túto povesť – čiastočne kvôli mylnej predstave, že „federované hlasovanie“, ktoré je predmetom prvej polovice vedeckého článku, je SCP. Ale to nie je pravda! Toto je len dôležitý stavebný kameň, ktorý druhá polovica článku používa na vytvorenie skutočné Protokol hviezdneho konsenzu.
V tomto článku stručne vysvetlíme, čo je to „systém dohôd“, čo ho robí „byzantským“ a prečo urobiť byzantský systém „federálnym“. Následne si vysvetlíme postup federatívneho hlasovania popísaný v článku SCP a nakoniec vysvetlíme samotný protokol SCP.
Dohodové systémy
Systém dohôd umožňuje skupine účastníkov dosiahnuť konsenzus na tému, napríklad čo si objednať na obed.
V spoločnosti Interstellar sme zaviedli vlastný systém dohôd o stravovaní: objednávame to, čo hovorí náš prevádzkový manažér John. Ide o jednoduchý a efektívny systém dohôd. Všetci Johnovi veríme a veríme, že každý deň nájde niečo zaujímavé a výživné.
Ale čo ak Ján zneužije našu dôveru? Môže sám rozhodnúť, že by sme sa všetci mali stať vegánmi. O týždeň alebo dva ho pravdepodobne zvrhneme a moc odovzdáme Elizabeth. Zrazu však miluje avokádo s ančovičkami a myslí si, že taký by mal byť každý. Moc korumpuje. Je teda lepšie nájsť nejaký demokratickejší spôsob: nejaký spôsob, ako zabezpečiť, aby sa zohľadnili rôzne preferencie, a zároveň zabezpečiť včasný a jednoznačný výsledok, aby si nikto neobjednal obed, alebo päť ľudí inak, alebo diskusia ťahá sa do večera.
Zdá sa, že riešenie je jednoduché: hlasujte! Ale to je klamlivý dojem. Kto bude zbierať hlasovacie lístky a oznamovať výsledky? A prečo by ostatní mali veriť tomu, čo hovorí? Možno môžeme na začiatku hlasujte za lídra, ktorému veríme, že bude viesť hlasovanie – ale kto ho bude viesť prvý hlasovaním? Čo ak sa nevieme dohodnúť na lídrovi? Alebo čo ak sa dohodneme, ale tento vodca sa zasekne na porade alebo pôjde na nemocenskú?
Podobné problémy sa vyskytujú v distribuovaných počítačových sieťach. Všetci účastníci alebo uzly sa musia dohodnúť na určitom rozhodnutí, napríklad kto je na rade, či má aktualizovať zdieľaný súbor alebo odstrániť úlohu z frontu spracovania. V kryptomenovej sieti si uzly musia opakovane vybrať, ako bude celý príbeh vyzerať, z niekoľkých možných verzií, ktoré si niekedy kolidujú. Táto sieťová dohoda poskytuje príjemcovi záruku, že minca je (a) platná (nie je sfalšovaná) a (b) ešte nebola použitá inde. To tiež zaisťuje, že bude môcť minúť mince v budúcnosti, pretože nový príjemca bude mať rovnaké záruky z rovnakých dôvodov.
Každý konsenzuálny systém v distribuovanej počítačovej sieti musí byť odolný voči chybám: musí produkovať konzistentné výsledky napriek chybám, ako sú pomalé linky, nereagujúce uzly a nesprávne usporiadanie správ. byzantský Systém dohôd je navyše odolný voči „byzantským“ chybám: uzlom, ktoré poskytujú nepravdivé informácie, či už v dôsledku chyby alebo zámerného pokusu podkopať systém alebo získať nejakú výhodu. „Byzantská“ tolerancia chýb – schopnosť dôverovať rozhodnutiu skupiny, aj keď niektorí členovia skupiny môžu klamať alebo inak nedodržiavať pravidlá rozhodovania – sa nazýva ktorí sa snažili koordinovať útok. v Anthony Stevens.
Zvážte majiteľku krypto mincí Alicu, ktorá si musí vybrať medzi kúpou lahodnej zmrzliny od Boba a splatením dlhu Carol. Možno chce Alice zaplatiť obom naraz podvodným míňaním rovnakej mince. Aby to urobila, musí presvedčiť Bobov počítač, že minca nebola nikdy zaplatená Carol, a presvedčiť Carolin počítač, že minca nebola nikdy zaplatená Bobovi. Byzantský systém dohôd to prakticky znemožňuje, využíva formu vlády väčšiny tzv kvórum. Uzol v takejto sieti odmietne prejsť na konkrétnu verziu histórie, kým neuvidí, že dostatočný počet rovesníkov – kvórum – súhlasí s takýmto prechodom. Akonáhle sa tak stane, vytvoria dostatočne veľký hlasovací blok, aby prinútil zostávajúce uzly siete súhlasiť s ich rozhodnutím. Alice môže prinútiť niektoré uzly, aby klamali v jej mene, ale ak je sieť dostatočne veľká, jej pokus bude prevalcovaný hlasmi čestných uzlov.
Koľko uzlov je potrebných pre kvórum? Minimálne väčšina, alebo skôr kvalifikovaná väčšina na boj proti chybám a podvodom. Aby ste však spočítali väčšinu, musíte poznať celkový počet účastníkov. Na úrade Interstellar alebo na okresných voľbách sa tieto čísla dajú ľahko zistiť. Ak je však vaša skupina voľne definovanou sieťou, do ktorej môžu uzly ľubovoľne vstupovať a opúšťať bez súhlasu centra, potom potrebujete federálny byzantský dohodový systém schopný určovať kvóra nie z vopred určeného zoznamu uzlov, ale dynamicky, z neustále sa meniaceho a nevyhnutne neúplného prehľadu uzlov v danom časovom bode.
Môže sa zdať nemožné vytvoriť kvórum z pohľadu jedného uzla v obrovskej sieti, ale je to možné. Takéto kvórum môže dokonca zaručiť výsledky decentralizovaného hlasovania. Biela kniha SCP ukazuje, ako to urobiť pomocou postupu s názvom federálnym hlasovaním.
Pre netrpezlivých
Zvyšok článku podrobnejšie popisuje federatívne hlasovanie a protokol Stellar konsenzu. Ak vás nezaujímajú podrobnosti, tu je všeobecný prehľad procesu.
- Uzly vedú kolá federálneho hlasovania o „nominantoch“. Federálne hlasovacie kolo znamená:
- Uzol hlasuje za nejaký výrok, napríklad „navrhujem hodnotu V“;
- Uzol počúva hlasy rovesníkov, kým nenájde ten, ktorý dokáže „prijímať“;
- Uzol hľadá "kvórum" pre toto tvrdenie. Nominanta „potvrdzuje“ kvórum.
- Keď uzol môže potvrdiť jedného alebo viacerých kandidátov, pokúsi sa „pripraviť“ „hlasovací lístok“ prostredníctvom niekoľkých kôl federálneho hlasovania.
- Akonáhle je uzol schopný overiť, že je hlasovací lístok pripravený, pokúsi sa ho odovzdať prostredníctvom ešte viacerých kôl federálneho hlasovania.
- Keď uzol dokáže potvrdiť potvrdenie hlasovania, môže „externalizovať“ hodnotu tohto hlasovacieho lístka tým, že ho použije ako výsledok konsenzu.
Tieto kroky zahŕňajú viacero kôl federálneho hlasovania, ktoré spoločne tvoria jedno kolo SCP. Pozrime sa bližšie na to, čo sa deje pri každom kroku.
Federované hlasovanie
Federované hlasovanie je postup na určenie, či sa sieť môže dohodnúť na návrhu. V hlasovacom kole si každý uzol musí vybrať jednu z potenciálne mnohých možných hodnôt. Nemôže to urobiť, pokiaľ si nie je istý, že ostatné uzly v sieti nezvolia iný výsledok. Aby sa to uistilo, uzly si vymieňajú množstvo správ tam a späť, takže každý potvrdenéŽe kvórum uzlov berie to isté rozhodnutie. Zvyšok tejto časti vysvetľuje výrazy v tejto vete a ako prebieha celý postup.
Kvóra a časti kvóra
Začnime definovaním kvóra. Ako sme diskutovali vyššie, v decentralizovanej sieti s dynamickým členstvom nie je možné vopred vedieť počet uzlov, a teda koľko je potrebných pre väčšinu. Federované hlasovanie rieši tento problém zavedením novej myšlienky uznášaniaschopná (rez kvórum): Malá množina partnerov, ktorým uzol dôveruje, že komunikujú informácie o stave hlasovania zvyšku siete. Každý uzol definuje svoj vlastný segment kvóra (ktorého sa stáva de facto členom).
Vytváranie kvóra sa začína prerušením uznášaniaschopnosti. Pre každý uzol sa pridajú jeho rezané uzly. Potom sa pridajú výrazy rezu tieto uzly a tak ďalej. Ako budete pokračovať, je tu viac a viac uzlov, ktoré nemôžete pridať, pretože sú už zahrnuté v reze. Keď už nie sú žiadne nové uzly na pridanie, proces sa zastaví: vytvorili sme kvórum „prechodným uzavretím“ časti kvóra počiatočného uzla.
Ak chcete nájsť kvórum z daného uzla...
... pridať členov jeho časti...
...potom pridáme slice členov týchto uzlov.
Pokračujeme, kým nezostanú žiadne uzly na pridanie.
Nezostali žiadne uzly na pridanie. Toto je kvórum.
V skutočnosti sa každý uzol môže objaviť vo viac ako jednom reze. Ak chcete vytvoriť kvórum, vyberte iba jednu z častí a pridajte členov; potom vyberte ľubovoľný rez pre každého člena a pridajte členov to rezať a pod. To znamená, že každý uzol je členom mnohých možných kvór.
V každom kroku vyberte iba jednu časť kvóra.
Jedno možné kvórum. Alebo alternatíva...
...vybrať iné plátky...
…(keď je to možné)…
... vytvára ďalšie kvórum.
Ako uzol vie, v ktorých rezoch sú ostatné uzly? Rovnakým spôsobom ako ostatné informácie o iných uzloch: z prenosov, ktoré každý uzol vysiela do siete, keď sa zmení jeho stav hlasovania. Každé vysielanie obsahuje informácie o segmentoch odosielajúceho uzla. Biela kniha SCP nešpecifikuje komunikačný mechanizmus. Implementácie zvyčajne používajú pre garantované vysielanie správ v celej sieti.
Pripomeňme, že v nefederálnom byzantskom systéme dohôd je kvórum definované ako väčšina všetkých uzlov. Byzantský dohodový systém je navrhnutý z hľadiska otázky: koľko nečestných uzlov môže systém tolerovať? V systéme N uzlov navrhnutých tak, aby prežili f zlyhania, by mal byť uzol schopný dosiahnuť pokrok prijímaním spätnej väzby od N-f kolegov, pretože f z nich môže byť mimo prevádzky. Ale keď sme dostali odpoveď od N-f rovesníkov, môžeme predpokladať, že všetci f rovesníci (od ktorých uzol nedostal odpoveď) sú v skutočnosti čestní. Teda f z N-f rovesníkov (od ktorých bola prijatá odpoveď) sú škodlivé. Aby uzly dosiahli rovnaký konsenzus, väčšina zostávajúcich uzlov musí byť čestná, to znamená, že potrebujeme, aby N−f bolo väčšie ako 2f alebo N > 3f. Takže typicky systém navrhnutý tak, aby prežil zlyhania f, bude mať celkovo N=3f+1 uzlov a veľkosť kvóra 2f+1. Keď návrh prekročí hranicu uznášaniaschopnosti, zvyšok siete je presvedčený, že všetky konkurenčné návrhy neuspejú. Takto sa sieť približuje k výsledku.
Ale vo federálnom byzantskom dohodovom systéme nielenže nemôže existovať väčšina (pretože nikto nepozná celkovú veľkosť siete), ale koncept väčšiny je úplne zbytočný! Ak je členstvo v systéme otvorené, potom môže niekto získať väčšinu jednoducho vykonaním takzvaného útoku Sybil: opakovaným pripájaním sa k sieti cez viacero uzlov. Prečo sa teda dá nazvať uzatváranie tranzitívnych rezov kvórum, a ako dokáže potlačiť konkurenčné návrhy?
Technicky v žiadnom prípade! Predstavte si sieť šiestich uzlov, kde sú dve trojice navzájom izolované v rezoch kvóra. Prvá podskupina môže urobiť rozhodnutie, o ktorom druhá nikdy nepočuje, a naopak. Neexistuje spôsob, ako by táto sieť dosiahla konsenzus (okrem náhody).
Preto SCP vyžaduje, aby na federatívne hlasovanie (a aby sa uplatnili dôležité teorémy článku) sieť musí mať vlastnosť tzv. priesečník kvór. V sieti s touto vlastnosťou sa akékoľvek dve kvóra, ktoré je možné zostaviť, vždy prekrývajú aspoň v jednom uzle. Na určenie prevládajúceho sentimentu siete je to rovnako dobré ako mať väčšinu. Intuitívne to znamená, že ak akékoľvek kvórum súhlasí s vyhlásením X, žiadne iné kvórum nemôže súhlasiť s ničím iným, pretože nevyhnutne bude zahŕňať nejaký uzol z prvého kvóra, ktoré už hlasovalo za X.
Ak je v sieti priesečník kvór...
...potom môžete vytvoriť akékoľvek dve kvóra...
...bude sa vždy pretínať.
(Samozrejme, prekrývajúce sa uzly sa môžu ukázať ako byzantsky ležiace alebo inak zlé. V tomto prípade prienik kvóra sieti vôbec nepomáha dohodnúť sa. Z tohto dôvodu sú mnohé výsledky v bielej knihe SCP založené na explicitné predpoklady, ako napríklad to, čo zostáva pri krížení kvóra siete aj po odstránení zlých uzlov. Pre jednoduchosť nechajme tieto predpoklady implicitné vo zvyšku článku).
Môže sa zdať nerozumné očakávať, že v sieti nezávislých uzlov je možné spoľahlivé kríženie kvóra. Ale sú dva dôvody, prečo je to tak.
Prvým dôvodom je existencia samotného internetu. Internet je dokonalým príkladom siete nezávislých uzlov s pretínajúcimi sa kvórami. Väčšina uzlov na internete sa pripája len k niekoľkým ďalším miestnym uzlom, ale tieto malé súbory sa dostatočne prekrývajú, takže každý uzol môže byť dosiahnutý z každého iného uzla na nejakej trase.
Druhý dôvod je špecifický pre platobnú sieť Stellar (najbežnejšie využitie SCP). Každé aktívum v sieti Stellar má emitenta a smernice Stellar vyžadujú, aby každý emitent určil jeden alebo viac uzlov v sieti na spracovanie žiadostí o spätné odkúpenie. Je vo vašom najlepšom záujme priamo alebo nepriamo zahrnúť tieto uzly do častí kvóra pre každé aktívum, o ktoré máte záujem. Kvóra pre všetky uzly, ktoré majú záujem o dané aktívum, sa potom budú prekrývať aspoň v týchto uzloch na uplatnenie. Uzly, ktoré majú záujem o viaceré aktíva, zahrnú do svojich častí kvóra všetky uzly spätného odkúpenia príslušných emitentov a budú sa snažiť spojiť všetky aktíva. Okrem toho všetky aktíva, ktoré nie sú týmto spôsobom prepojené s ostatnými v sieti, a by nemal byť pripojený - toto je navrhnuté tak, aby nedochádzalo k prekrývaniu kvóra pre túto sieť (napríklad banky z dolárovej zóny chcú niekedy obchodovať s bankami z eurozóny a bankami z peso zóny, takže sú v rovnakej sieti, ale žiadna z nich sa stará o samostatnú sieť detí predávajúcich bejzbalové karty).
Samozrejme, očakávania kríženie kvóra nie je záruka. Iné byzantské dohody vďačia za svoju zložitosť garancii kvór. Dôležitou inováciou SCP je, že odstraňuje zodpovednosť za vytváranie kvór zo samotného konsenzuálneho algoritmu a prináša ho na aplikačnú úroveň. Hoci je teda federálne hlasovanie dostatočne všeobecné na to, aby sa hlasovalo o akejkoľvek otázke, jeho spoľahlivosť v skutočnosti kriticky závisí od širšieho významu týchto významov. Niektoré hypotetické použitia nemusia byť také vhodné na vytvorenie dobre prepojených sietí ako iné.
Hlasovanie, prijatie a potvrdenie
Vo federatívnom hlasovacom kole začne uzol voliteľne hlasovať pre určitú hodnotu V. To znamená, že odošle správu do siete: „Som uzol N, moje časti kvóra sú Q a hlasujem za V.“ Keď uzol hlasuje týmto spôsobom, sľubuje, že nikdy nehlasoval proti V a nikdy nebude.
Vo vysielaniach typu peer-to-peer každý uzol vidí, ako hlasujú ostatní. Keď uzol zhromaždí dostatok týchto správ, môže sledovať segmenty kvóra a pokúsiť sa nájsť kvóra. Ak uvidí kvórum kolegov, ktorí tiež hlasujú za V, môže pristúpiť k adopcia V a odvysielajte túto novú správu do siete: „Som uzol N, moje segmenty kvóra sú Q a akceptujem V.“ Prijatie poskytuje silnejšiu záruku ako jednoduché hlasovanie. Keď uzol hlasuje za V, nikdy nemôže hlasovať za iné možnosti. Ale ak uzol akceptuje V, žiadny uzol v sieti nikdy neprijme druhú možnosť (veta 8 v bielej knihe SCP to dokazuje).
Samozrejme, je vysoká pravdepodobnosť, že okamžite nebude uznášaniaschopné uznášanie uzlov, ktoré súhlasia s V. Ostatné uzly môžu hlasovať za iné hodnoty. Existuje však aj iný spôsob, ako môže uzol prejsť od jednoduchého hlasovania k prijatiu. N môže prijať inú hodnotu pre W, aj keď za ňu nehlasoval, a aj keď pre ňu nevidí kvórum. Ak sa chcete rozhodnúť zmeniť svoj hlas, pozrite sa blokovacia sada uzly, ktoré akceptovali W. Blokovacia množina je jeden uzol z každého segmentu kvóra N. Ako už názov napovedá, môže blok akýkoľvek iný význam. Ak všetky uzly v takejto množine akceptujú W, potom (podľa vety 8) nebude nikdy možné vytvoriť kvórum, ktoré bude mať inú hodnotu, a preto je bezpečné aj pre N prijať W.
Uzol N s tromi rezmi kvóra.
BDF je blokovacia sada pre N: obsahuje jeden uzol z každého z rezov N.
BE je tiež blokovacia sada pre N, pretože E sa objavuje v dvoch rezoch N.
Blokovanie však nie je uznášaniaschopné. Bolo by príliš jednoduché oklamať uzol N, aby akceptoval požadovanú hodnotu, ak by stačilo hacknúť len jeden uzol v každom z rezov N. Preto akceptovanie hodnoty neznamená koniec hlasovania. Namiesto toho musí N potvrdiť hodnotu, to znamená vidieť kvórum uzlov, ktoré ju akceptujú. Ak to dôjde tak ďaleko, potom, ako dokazuje whitepaper SCP (vo vete 11), zvyšok siete nakoniec tiež potvrdí rovnakú hodnotu, takže N ukončí federatívne hlasovanie s určitou hodnotou ako výsledkom.
Federované hlasovanie.
Proces hlasovania, prijatia a potvrdenia predstavuje jedno celé kolo federálneho hlasovania. Protokol Hviezdneho konsenzu kombinuje mnohé z týchto kôl, aby sa vytvoril úplný konsenzus.
Protokol hviezdneho konsenzu
Dve najdôležitejšie vlastnosti konsenzuálneho systému sú − bezpečnosť и vitalita. Algoritmus konsenzu je „bezpečný“, ak nikdy nemôže poskytnúť rôzne výsledky rôznym účastníkom (Bobova kópia histórie nebude nikdy v rozpore s Carol). „Livability“ znamená, že algoritmus vždy vytvorí výsledok, to znamená, že sa nezasekne.
Opísaný postup federálneho hlasovania bezpečné v tom zmysle, že ak uzol potvrdí hodnotu V, žiadny iný uzol nepotvrdí inú hodnotu. Ale „nepotvrdí iný význam“ neznamená, že to nevyhnutne niečo potvrdí. Účastníci môžu hlasovať za toľko rôznych hodnôt, že nič nedosiahne prah prijatia. To znamená, že pri federálnom hlasovaní neexistuje vitalita.
Protokol Stellar consensus využíva federatívne hlasovanie spôsobom, ktorý zaisťuje bezpečnosť aj prežitie. (Záruky bezpečnosti a prežitia SCP majú teoretický limit. Návrh si vyberá veľmi silnú bezpečnostnú záruku, obetuje malé zníženie prežitia, ale ak bude dostatok času, je vysoko pravdepodobné, že sa dosiahne konsenzus.) Stručne povedané, myšlienkou je mať viacero združených hlasov na viacerých hodnotách, kým jeden z nich neprejde všetkými fázami hlasovania SCP opísanými nižšie.
Hodnoty, na ktorých SCP hľadá konsenzus, môžu byť história transakcií alebo obedová objednávka alebo niečo iné, ale je dôležité poznamenať, že to nie sú hodnoty, ktoré sú akceptované alebo potvrdené. Namiesto toho prebieha federálne hlasovanie podľa vyhlásenia o týchto hodnotách.
Prvé kolá federálneho hlasovania sa konajú dňa etapa nominácie (nominačná fáza), na súbore výrokov ako „Nominujem V“, možno pre mnoho rôznych hodnôt V. Účelom nominácie je nájsť jeden alebo viac výrokov, ktoré prejdú prijatím a potvrdením.
Po nájdení overiteľných kandidátov SCP prechádza do fázy hlasovania, kde je cieľom nájsť bulletin (čiže kontajner pre navrhovanú hodnotu) a kvórum, ktoré môže vyhlásiť zaviazať sa za to (zaviazať sa). Ak kvórum uskutoční hlasovanie, jeho hodnota sa akceptuje ako konsenzus. Ale predtým, ako môže uzol hlasovať o odovzdaní hlasovania, musí ho najprv potvrdiť zrušenie všetky hlasovacie lístky s nižšou protihodnotou. Tieto kroky – zrušenie hlasovacích lístkov s cieľom nájsť ten, ktorý sa dá zaviazať – zahŕňajú viacero kôl federálneho hlasovania o viacerých nárokoch na hlasovanie.
Nasledujúce časti podrobnejšie popisujú nomináciu a hlasovanie.
Nominácia
Na začiatku nominačnej fázy si každý uzol môže spontánne vybrať hodnotu pre V a hlasovať za vyhlásenie „Nominujem V“. Cieľom v tejto fáze je potvrdiť nomináciu určitej hodnoty prostredníctvom federálneho hlasovania.
Možno dosť uzlov hlasuje o dostatočne odlišných návrhoch, že žiadna nominácia nemôže dosiahnuť prah prijatia. Preto uzly okrem vysielania vlastných nominačných hlasov „odrážajú“ nominácie svojich kolegov. Echo znamená, že ak uzol hlasuje za nomináciu V, ale uvidí správu od suseda, ktorý hlasuje za nomináciu W, bude teraz hlasovať za V aj W. (Nie všetky hlasy kolegov sa počas nominácie odzrkadlia, pretože to môže viesť k explózii rôznych nominantov. SCP obsahuje mechanizmus na reguláciu týchto hlasov. Stručne povedané, existuje vzorec na určenie „priority“ partnera z pohľadu uzla a zohľadňujú sa iba hlasy uzlov s vysokou prioritou. Čím dlhšia je nominácia čím nižší je prah, takže uzol rozšíri množinu partnerov, ktorých hlasy bude odrážať. Vzorec priority obsahuje číslo slotu ako jeden zo svojich vstupov, takže partner s vysokou prioritou pre jeden priestor môže byť partner s nízkou prioritou pre iný a naopak).
Koncepčne je nominácia paralelná, V aj W sú samostatné federálne hlasy, z ktorých každý je samostatne schopný dosiahnuť prijatie alebo potvrdenie. V praxi správy protokolu SCP spájajú tieto jednotlivé hlasy.
Hoci hlasovanie za nomináciu V je prísľubom, že nikdy nebudete hlasovať proti nominácii V, je to na aplikačnej úrovni – v tomto prípade SCP –, čo znamená „proti“. SCP nevidí vyhlásenie, ktoré je v rozpore s hlasovaním „Nominujem X“, to znamená, že neexistuje správa „Som proti nominovaniu X“, takže uzol môže hlasovať za nomináciu akýchkoľvek hodnôt. Mnohé z týchto nominácií nikam nevedú, ale nakoniec bude uzol schopný prijať alebo potvrdiť jednu alebo viac hodnôt. Akonáhle je kandidát potvrdený, stáva sa ním kandidáta.
Nominácia SCP pomocou federálneho hlasovania. Môže existovať veľa hodnôt „B“ predložených rovesníkmi a „reflektovaných“ uzlom.
Výsledkom nominácií môže byť viacero potvrdených kandidátov. Preto SCP vyžaduje, aby aplikačná vrstva poskytovala nejaký spôsob kombinovania kandidátov do jedného zložený (kompozitný). Spôsob spájania môže byť akýkoľvek. Hlavná vec je, že ak je táto metóda deterministická, potom každý uzol bude kombinovať rovnakých kandidátov. V systéme hlasovania na obed môže „zjednotenie“ jednoducho znamenať odmietnutie jedného z dvoch kandidátov. (Ale deterministickým spôsobom: každý uzol musí vybrať rovnakú hodnotu na resetovanie. Napríklad skorší výber v abecednom poradí). V platobnej sieti Stellar, kde sa hlasuje o histórii transakcií, zlúčenie dvoch navrhovaných kandidátov zahŕňa zlúčenie transakcií, ktoré obsahujú, a poslednej z ich dvoch časových pečiatok.
SCP whitepaper dokazuje (Veta 12), že na konci fázy rozšírenia sieť nakoniec konverguje do jedného kompozitu. Ale je tu problém: federatívne hlasovanie je asynchrónny protokol (ako SCP). Inými slovami, uzly nie sú koordinované časom, ale iba správami, ktoré posielajú. Z pohľadu uzla nie je jasné kedy ukončený predlžovacej fáze. A hoci všetky uzly nakoniec dospejú k rovnakému kompozitu, môžu sa vydať rôznymi cestami, pričom môžu vytvárať rôznych kompozitných kandidátov a nikdy nemôžu povedať, ktorý z nich je konečný.
Ale je to normálne. Nominácia je len príprava. Hlavnou vecou je obmedziť počet kandidátov na dosiahnutie konsenzu, ku ktorému dochádza v procese kandidovať na úrad (hlasovanie).
Beh
Bulletin je pár , kde counter je celé číslo, ktoré začína na 1 a hodnota je kandidátom z fázy nominácie. Môže to byť vlastný kandidát uzla alebo kandidát susedného uzla akceptovaný týmto uzlom. Zhruba povedané, hlasovanie zahŕňa opakované pokusy prinútiť sieť dosiahnuť konsenzus na niektorom kandidátovi na niektorom hlasovacom lístku držaním potenciálne mnohých federálnych hlasov na hlasovacích vyhláseniach. Počítadlá na hlasovacích lístkoch zaznamenávajú uskutočnené pokusy a hlasovacie lístky s vyšším počtom majú prednosť pred hlasovacími lístkami s nižším počtom. Ak newsletter zasekne, začne sa nové hlasovanie, teraz na hlasovacom lístku .
Je dôležité rozlišovať význam (napríklad aká by mala byť objednávka na obed: pizza alebo šaláty), bulletiny (protihodnotový pár) a výkaz o hlasovacích lístkoch. Kolo SCP zahŕňa niekoľko kôl federálneho hlasovania, najmä o nasledujúcich výrokoch:
- "Som pripravený odovzdať hlasovací lístok B" a
- "Oznamujem odovzdanie hlasovacieho lístka B"
Z pohľadu daného uzla je konsenzus dosiahnutý vtedy, keď nájde hlasovací lístok B, pre ktorý môže potvrdiť (t. j. nájsť kvórum, ktoré akceptuje) vyhlásenie „Potvrdzujem hlasovanie B“. Od tohto momentu je bezpečné konať podľa hodnoty uvedenej v B – napríklad zadať túto objednávku na obed. To sa nazýva externalizácia významy. Po potvrdení prijatia hlasovacieho lístka si uzol môže byť istý, že ktorýkoľvek iný uzol externalizoval rovnakú hodnotu alebo tak urobí v budúcnosti.
Hoci mnohé združené hlasovania sú koncepčne vykonávané na základe nárokov na mnoho rôznych hlasovacích lístkov, nevymieňajú si toľko správ, pretože každá správa obsahuje určitý počet hlasovacích lístkov. Jedna správa tak propaguje stav mnohých združených hlasov naraz, napríklad: „Prijímam záväzné hlasovacie lístky od predtým "
Čo znamenajú pojmy „pripravený“ a „zaviazaný“?
Uzol hlasuje o odovzdaní hlasovacieho lístka, keď je presvedčený, že iné uzly neodovzdajú hlasovania s rôznymi hodnotami. Presvedčiť o tom je účel prípravy žiadosti. Hlasovanie, ktoré hovorí „Som pripravený odovzdať hlasovací lístok B“ je prísľub, že nikdy neodovzdáte hlasovanie menšie ako B, t. j. s menším počtom (SCP vyžaduje, aby boli hodnoty v hlasovacích lístkoch v určitom poradí. Newsletter menej , ak N1
Prečo „Som pripravený odovzdať hlasovací lístok B“ znamená „Sľubujem, že nikdy neodovzdám hlasovacie lístky menšie ako B“? Pretože SCP definuje prerušenie ako opak potvrdenia. Hlasovanie za prípravu hlasovacieho lístka zahŕňa aj hlasovanie o diskvalifikácii niektorých ďalších hlasovacích lístkov, a ako sme už diskutovali, hlasovanie za jednu vec je prísľub, že nikdy nebudem hlasovať proti.
Pred vysielaním odovzdania musí uzol najskôr nájsť bulletin, ktorý môže potvrdiť ako pripravený. Inými slovami, vykonáva federálne hlasovanie na tému „Som pripravený odovzdať hlasovanie B“, prípadne na mnohých rôznych hlasovaniach, kým nenájde ten, ktorý akceptuje kvórum.
Odkiaľ pochádzajú hlasovacie lístky na prípravu hlasovania? Po prvé, uzol vysiela prípravy na hlasovanie za <1,C>, kde C je zložený kandidát vytvorený vo fáze nominácie. Avšak aj po začatí príprav na hlasovanie môžu nominácie viesť k tomu, že sa o nových kandidátoch zdajú byť noví kandidáti. Medzitým môžu mať kolegovia rôznych kandidátov a môžu vytvoriť blokovací súbor, ktorý akceptuje „Som pripravený odovzdať hlasovanie B2“, čo presvedčí uzol, aby ho tiež prijal. Nakoniec je tu mechanizmus časového limitu, ktorý generuje nové kolá federálneho hlasovania o nových hlasovacích lístkoch s vyšším počtom, ak sa súčasné hlasovacie lístky zaseknú.
Hneď ako uzol nájde hlasovací lístok B, ktorý môže potvrdiť ako pripravený, vyšle novú správu „Potvrdiť hlasovanie B“. Toto hlasovanie hovorí kolegom, že uzol sa nikdy nevzdá B. V skutočnosti, ak B je hlasovací lístok , potom „Potvrdiť hlasovanie “ znamená bezvýhradný súhlas hlasovať za pripravenosť každého hlasovacieho lístka z na <∞, s>. Táto dodatočná hodnota pomáha ostatným partnerom dobehnúť partnera odovzdania, ak sú stále v skorších štádiách protokolu.
V tejto fáze je vhodné ešte raz zdôrazniť, že ide o asynchrónne protokoly. Len preto, že jeden uzol posiela súhlasné hlasy za odovzdanie, neznamená to, že to robia aj jeho kolegovia. Niektorí z nich možno ešte stále hlasujú o vyhláseniach v rámci prípravy na hlasovanie, iní už možno tento význam externalizovali. SCP vysvetľuje, ako by mal uzol spracovať každý typ partnerskej správy bez ohľadu na jej fázu.
Ak sa zobrazí správa „Oznámil som odovzdanie » nemožno prijať alebo potvrdiť, to znamená pravdepodobnosť prijatia alebo potvrdenia správy alebo - alebo v každom prípade akýkoľvek hlasovací lístok s hodnotou C a nie žiadny iný, pretože uzol už sľúbil, že nikdy nezruší . V čase, keď uzol odvysiela hlasy za odovzdanie, bude to C alebo nič, v závislosti od toho, ako ďaleko konsenzus zájde. To však ešte nestačí na to, aby uzol externalizoval C. Niektorí byzantskí kolegovia (ktorí tvoria menej ako kvórum na základe našich bezpečnostných predpokladov) môžu uzlu klamať. Prijatie a následné potvrdenie nejakého hlasovacieho lístka (alebo rozsahu hlasovacích lístkov) je to, čo dáva uzlu istotu, že konečne externalizuje C.
SCP hlasovanie prostredníctvom federálneho hlasovania. Nezobrazené: Časomiera sa môže kedykoľvek spustiť, čím sa zvýši počet pri hlasovaní (a prípadne sa vytvorí nová zostava ďalších nominovaných kandidátov).
A to je všetko! Keď sieť dosiahne konsenzus, je pripravená robiť to znova a znova. V platobnej sieti Stellar sa to deje približne raz za 5 sekúnd: výkon, ktorý si vyžaduje bezpečnosť aj prežitie, ktoré zaručuje SCP.
SCP to môže dosiahnuť spoliehaním sa na viacero kôl federálneho hlasovania. Federované hlasovanie umožňuje koncept segmentov kvóra: množiny kolegov, ktorým sa každý uzol rozhodol dôverovať ako súčasť svojho (subjektívneho) kvóra. Táto konfigurácia znamená, že konsenzus možno dosiahnuť aj v sieti s otvoreným členstvom a byzantskými podvodmi.
Ďalšie čítanie
- Originálny biely papier SCP nájdete A návrh špecifikácií na jeho implementáciu.
- Pôvodný autor protokolu SCP David Mazier to vysvetľuje zjednodušeným (ale stále technickým) spôsobom. .
- Možno vás prekvapilo, že ste v tomto článku nenašli výrazy „ťažba“ alebo „doklad o práci“. SCP nepoužíva tieto metódy, ale niektoré iné konsenzuálne algoritmy áno. Zane Witherspoon napísal prístupné .
- jednoduchá sieť, ktorá dosiahne konsenzus v jednom úplnom kole SCP.
- Pre čitateľov, ktorí sa zaujímajú o implementácie SCP: pozri , využívaná platobnou sieťou Stellar, príp , ktorý som napísal pre lepšie pochopenie SCP.
Zdroj: hab.com