Protokol soglasja Stellar je bil prvič opisan v Davida Mazièrea leta 2015. Gre za »federalni sistem bizantinskega soglasja«, ki decentraliziranim računalniškim omrežjem brez vodij omogoča učinkovito dosego soglasja o kakšni odločitvi. Plačilna mreža Stellar uporablja Stellar Consensus Protocol (SCP) za vodenje usklajene zgodovine transakcij, ki jo vidijo vsi udeleženci.
Menijo, da so protokoli soglasja težko razumljivi. SCP je enostavnejši od večine, a kljub temu deli to sloves — deloma zaradi napačnega prepričanja, da je »federalno glasovanje«, ki mu je posvečena prva polovica znanstvenega članka, SCP. A to ni res! To je le pomemben gradnik, ki se v drugi polovici članka uporablja za ustvarjanje dejanskega protokola soglasja Stellar.
V tem članku bomo na kratko razložili, kaj je »sistem soglasij«, kaj ga lahko naredi »bizantinskega« in zakaj bi morali bizantinski sistem narediti »federalen«. Nato bomo pojasnili federalno glasovalno proceduro, opisano v članku o SCP, in na koncu razložili sam protokol SCP.
Sistemi soglasij
Sistem soglasij omogoča skupini udeležencev, da doseže soglasje o neki temi, na primer, kaj naročiti za kosilo.
V podjetju Interstellar smo uvedli svoj lastni sistem soglasja o kosilu: naročamo to, kar pove naš operativni vodja John. To je enostaven in učinkovit sistem soglasij. Vsi zaupamo Johnu in verjamemo, da bo vsak dan našel nekaj zanimivega in hranljivega.
Toda kaj, če John zlorabi naše zaupanje? Lahko enostransko odloči, da moramo postati veganisti. Čez teden ali dva ga bomo verjetno odstavili in pooblastila prenesli na Elizabeth. Ampak potem, ona ima rada avocado z ančami in misli, da bi morali vsi biti taki. Moč pokvari. Zato je bolje najti nek bolj demokratičen način: nek način, da zagotovimo, da so upoštevane različne preference, hkrati pa zagotoviti pravočasno in nedvoumen rezultat, da ne pridemo v situacijo, da nihče ne naroči kosila ali da pet ljudi odda različne naročilnice ali da se razprava zavleče do večera.
Zdi se, da je rešitev preprosta: izvesti glasovanje! Vendar je to zavajajoč vtis. Kdo bo zbiral glasovnice in sporočal rezultate? In zakaj bi morali drugi verjeti tistemu, kar bo povedal? Morda lahko najprej glasujemo za vodjo, kateremu zaupamo, da bo vodil glasovanje — vendar kdo bo vodil to prvo glasovanje? Kaj se zgodi, če se ne moremo dogovoriti o vodji? Ali pa se dogovorimo, a ta vodja obstane na srečanju ali gre na bolniško?
Podobne težave se pojavljajo v razdistributed računalniških omrežjih. Vsi sodelujoči ali vozlišča morajo uskladiti neko rešitev, na primer, kdo bo posodobil skupno datoteko ali vzel nalogo iz obdelovalne vrste. V omrežju kriptovalut morajo vozlište večkrat izbrati, kako izgleda popolna zgodovina, iz več možnih različic, ki včasih nasprotujejo ena drugi. To omrežno soglasje daje prejemniku zagotovilo, da je vrednost (a) veljavna (ne ponarejena) in (b) še ni bila porabljena na drugem mestu. Prav tako zagotavlja, da bo lahko vrednost porabil v prihodnosti, ker bo nov prejemnik imel iste garancije iz istih razlogov.
Vsak sistem usklajevanja v razdistributed računalniški mreži mora biti odporen na okvare: mora dajati dosledne rezultate, kljub napakam, kot so počasne komunikacijske črte, neodzivna vozlišča in napačen vrstni red sporočil. Bizantinska sistem soglasij je dodatno odporen na „bizantinske“ napake: vozlišča, ki dajejo napačne informacije, bodisi zaradi napake ali zaradi namernega poskusa, da bi podkrepili sistem ali pridobili kakšno prednost. „Bizantinska“ odpornost na okvare — sposobnost zaupati skupinskemu odločanju, tudi ko nekateri člani skupine lahko lažejo ali drugače ne upoštevajo pravil odločanja — je dobila ime po , ki so poskušali uskladiti napad. imajo Anthony Stevens.
Upoštevajmo lastnico kriptovalute Aliso, ki mora izbrati med nakupom okusnega sladoleda pri Bobu in plačilom dolga Carol. Morda Alisa želi plačati obema hkrati, z goljufivo porabo iste valute. Zato mora prepričati Bobov računalnik, da valuta nikoli ni bila plačana Carol, in prepričati Carolin računalnik, da valuta nikoli ni bila plačana Bobu. Bizantinski sistem soglasja to dejansko onemogoča z uporabo oblike pravila večine, imenovane kvorum. Vozlišča v takšni mreži zavrnejo prehod na določeno različico zgodovine, dokler ne vidijo, da je dovolj velika količina enakopravnih vozlišč - kvorum - soglasna za tak prehod. Ko se to zgodi, oblikujejo dovolj velik volilni blok, da prisilijo preostala vozlišča v omrežju, da se strinjajo z njihovo odločitvijo. Alisa lahko prisili nekatera vozlišča, da lažejo v njeno ime, toda če je omrežje dovolj veliko, bo njen poskus zatrten s strani poštenih vozlišč.
Koliko vozlišč je potrebnih za kvorum? Vsaj večina, natančneje kvalificirana večina, ki se bori proti napakam in goljufijam. Vendar pa za štetje večine potrebujemo vedeti skupno število udeležencev. V pisarni Interstellar ali pri okrožnih volitvah so te številke lahko enostavno ugotovljive. Toda če je vaša skupina slabo definirana mreža, kjer se lahko vozlišča priključujejo in izključujejo po želji brez usklajevanja s centrom, potem potrebujete federalni sistem bizantinskega soglasja, ki je sposoben določati kvorume ne iz vnaprej določenega seznama vozlišč, temveč dinamično, iz nenehno spreminjajočega se in neizogibno nepopolnega posnetka vozlišč v določenem trenutku.
Zdi se lahko nemogoče ustvariti kvorum z vidika posameznega vozlišča v široki mreži, vendar je to mogoče. Tak kvorum lahko celo zagotovi rezultate decentraliziranega glasovanja. Tehnični dokument SCP prikazuje, kako to doseči s postopkom, imenovanim federalno glasovanje.
Za nestrpne
Preostali del članka podrobneje opisuje federalno glasovanje in protokol soglasja Stellar. Če vas podrobnosti ne zanimajo, tukaj je splošen pregled procesa.
- Voizli izvajajo federativne glasovalne kroge za 'nominirance'. Federativno glasovanje pomeni:
- Voizel glasuje za kakršno koli izjavo, na primer, 'predlagam vrednost V';
- Voizel posluša glasove peerov, dokler ne najde tistega, ki ga lahko 'sprejme';
- Voizel išče 'kvorum' za to izjavo. Kvorum 'potrdi' nominanta.
- Ko voizel lahko potrdi enega ali več nominantov, poskuša 'pripraviti' 'glasovnico' skozi več krogov federativnega glasovanja.
- Ko je voizel sposoben preveriti pripravljenost glasovnice, poskuša njen commit izvesti s še več krogi federativnega glasovanja.
- Ko voizel lahko potrdi commit glasovnice, lahko 'eksternalizira' vrednost te glasovnice, tako da jo uporabi kot rezultat konsenza.
Ti koraki vključujejo več krogov federativnega glasovanja, ki skupaj tvorijo en krog SCP. Poglejmo podrobneje, kaj se dogaja pri vsakem koraku.
Federativno glasovanje
Federativno glasovanje je postopek, s katerim se ugotovi, ali lahko omrežje uskladi predlog. V glasovalnem krogu mora vsak voizel izbrati eno od potencialno mnogih možnih vrednosti. To ne more storiti, dokler ne bo prepričan, da drugi voizli v omrežju ne bodo izbrali drugega rezultata. Da bi bili v tem prepričani, si voizli izmenjujejo veliko sporočil sem ter tja, da bi vsak potvrdio, da kvorum voizlov sprejema isto odločitev. Preostali del tega razdelka pojasnjuje pojme v tej izjavi in kako poteka celoten postopek.
Kvorumi in delni kvorumi
Začnimo z opredelitvijo kvoruma. Kot smo ugotovili zgoraj, je v decentraliziranem omrežju z dinamičnim članstvom skoraj nemogoče vnaprej vedeti, koliko voizlov je in zato koliko jih je potrebno za večino. Federativno glasovanje rešuje to težavo s predstavitvijo nove ideje delnega kvoruma (quorum slice): majhna skupina enakopravnih voizlov, kateri voizel zaupa prenos informacije o stanju glasovanja v preostalo omrežje. Vsak voizel določi svoj lasten delni kvorum (ki postane član dejansko).
Oblikovanje kvoruma se začne z delnim kvorumom. Za vsak voizel se dodajo voizli njegovega delnega kvoruma. Nato se dodajo člani delnih kvorumov. teh vozlova itd. Kako nadaljujete, naletite na vedno več vozlov, ki jih ne morete dodati, ker so že vključeni v rez. Ko ni več novih vozlov za dodajanje, se postopek ustavi: oblikovali smo kvorum preko „transitivnega zapiranja“ rezanja kvoruma začetnega vozla.
Da bi našli kvorum iz danega vozla...
... dodamo člane njegovega reza...
... nato dodamo člane rezov teh vozlov.
Nadaljujemo, dokler ne ostane več vozlov za dodajanje.
Vozlov za dodajanje ni več. To je kvorum.
V resnici lahko vsak vozel pripada več kot enemu rezu. Da bi oblikovali kvorum, izberite le en rez in dodajte člane; nato izberite katerikoli rez za vsak član in dodajte člane tega reza itd. To pomeni, da je vsak vozel član množice možnih kvorumov.
Izberite le en rez kvoruma na vsakem koraku.
Eden možnih kvorumov. Ali alternativna možnost...
... izberemo druge reze...
... (ko je to mogoče)...
... ustvarja drugi kvorum.
Kako vozlu uspe izvedeti, v katerih rezih so drugi vozli? Enako kot druge informacije o drugih vozlih: iz sporočil, ki jih vsak vozel predvaja v omrežje, ko se spremeni njegovo glasovalno stanje. Vsaka oddaja vključuje informacije o rezih pošiljateljevega vozla. V tehničnem dokumentu SCP mehanizem komunikacije ni določen. Izvedbe običajno uporabljajo za zagotovitev predvajanja sporočil po celotnem omrežju.
Pripomnimo, da je v nefeuderalnem bizantinskem sistemu sporazumov kvorum definiran kot večina vseh vozlišč. Bizantinski sistem sporazumov je zasnovan z vidika vprašanja: koliko nepoštenih vozlišč lahko sistem prenese? V sistemu z N vozlišči, zasnovanem za preživetje pri f napakah (prevarah), mora vozlišče biti sposobno doseči napredek, če prejme odziv od N−f peers, saj f od njih morda ne deluje. Če pa prejme odziv od N−f peers, lahko domnevamo, da so vsa f peers (od katerih vozlišče ni prejelo odziva) dejansko poštena. Tako so zlonamerna f iz N−f peers (od katerih je bil prejet odgovor). Da bi vozlišča dosegla enoten konsenz, mora biti večina preostalih vozlišč poštenih, to pomeni, da potrebujemo, da je N−f več kot 2f ali N > 3f. Tako običajno sistem, zasnovan za preživetje pri f napakah, vključuje skupno N=3f+1 vozlišč in velikost kvoruma 2f+1. Ko predlog preseže prag kvoruma, so preostali člani omrežja prepričani, da bodo vsi konkurenčni predlogi neuspešni. Tako omrežje konvergira k rezultatu.
Toda v feudalnem bizantinskem sistemu sporazumov ne more biti samo večine (ker nihče ne ve skupne velikosti omrežja), ampak je koncept večine sploh brez smisla! Če je članstvo v sistemu odprto, lahko nekdo pridobi večino, preprosto z izvedbo tako imenovanega Sibyl atac: večkrat se pridružuje omrežju prek več vozlišč. Zakaj torej se lahko tranzitivno zapiranje preseka imenuje kvorum, in kako lahko zatira konkurenčne predloge?
Tehnično, nikakor! Predstavite si omrežje s šestimi vozlišči, kjer sta dve trojici izolirani v presečnih kvorumih drug drugega. Prva podskupina lahko sprejme odločitev, o kateri druga nikoli ne bo slišala, in obratno. Za to omrežje ni načina, da bi doseglo konsenz (razen naključno).
Zato SCP zahteva, da mora imeti omrežje za feudalno glasovanje (in za uporabo pomembnih teoremov članka) lastnost, imenovano presečišče kvorumovV omreži s to lastnostjo se vsak dva kvora, ki ju lahko zgradimo, vedno prekrivata vsaj v enem vozlišču. Za določitev prevladujočih razpoloženj omrežja je to prav tako dobro, kot imeti večino. Intuitivno to pomeni, da če kateri koli kvor soglaša z trditvijo X, noben drug kvor nikoli ne more soglašati z nečim drugim, ker bo nujno vseboval neko vozlišče iz prvega kvora, ki je že glasovalo za X.
Če v omrežju obstaja prekrivanje kvorov…
… potem se vsak dva kvor, ki ju lahko zgradite…
… vedno prekrivata.
(Seveda se lahko prekrivajoča vozlišča izkažejo za bizantinsko lažna ali slaba na druge načine. V tem primeru prekrivanje kvorov ne pomaga omrežju, da bi se sploh uskladilo. Iz tega razloga temelji veliko rezultatov v tehničnem dokumentu SCP na izrecno izraženih predpostavkah, kot je to, da v omrežju ostaja prekrivanje kvorov, tudi po odstranitvi slabih vozlišč.. Zaradi preprostosti bomo te predpostavke pustili neizrecne v preostalem delu članka).
Morda se zdi nerazumljivo pričakovati, da je v omrežju neodvisnih vozlišč možno zanesljivo prekrivanje kvorov. Vendar sta tukaj dva razloga, zakaj je to tako.
Prvi razlog je obstoj samega interneta. Internet je idealen primer omrežja neodvisnih vozlišč s prekrivanjem kvorov. Večina vozlišč v internetu je povezana le z nekaterimi drugimi lokalnimi vozlišči, toda ta majhna množica se dovolj prekriva, da je bilo vsako vozlišče dostopno iz katerega koli drugega vozlišča po eni ali drugi poti.
Druga razlog specifičan je za platnu mrežu Stellar (najčešće korišćena primena SCP). Svaka imovina u Stellar mreži ima izdavaoca, a preporuke Stellar-a zahtevaju da svaki izdavaoc imenuje jedan ili više čvorova u mreži za obradu zahteva za otkup. U vašem je interesu direktno ili indirektno uključiti te čvorove u kvorum za svaku imovinu koja vas zanima. Tada će kvorumi za sve čvorove koji su zainteresovani za određenu imovinu biti preklapani barem u tim čvorovima za otkup. Čvorovi zainteresovani za više imovine uključivaće u svoje kvorume sve čvorove za otkup odgovarajućih izdavaoca, i nastojaće da povežu sve imovine zajedno. Pored toga, sve imovine koje nisu na taj način povezane sa ostalima u mreži, i ne treba da budu povezane — tako je zamišljeno da u ovoj mreži ne bude preklapanja kvoruma (na primer, banke iz dolarske zone ponekad žele da trguju sa bankama iz evro zone i bankama iz zone peza, tako da su u istoj mreži, ali nije ih briga za posebnu mrežu dece koja trguju bejzbol karticama).
Naravno, očekivanje preklapanja kvoruma nije garancija. Druge vizantijske sisteme dogovora svoju složenost u velikoj meri duguju garanciji kvoruma. Važna novina SCP-a je to što prebacuje odgovornost za formiranje kvoruma sa samog algoritma konsenzusa na nivo aplikacije. Tako, iako je federativno glasanje dovoljno opšte za glasanje o bilo kojim pitanjima, zapravo njegova pouzdanost kritički zavisi od šireg značenja ovih vrednosti. Neki hipotetički načini korišćenja možda neće biti toliko povoljni za stvaranje dobro povezanih mreža kao drugi.
Glasanje, prihvatanje i potvrda
U rundi federativnog glasanja čvor opcionalno počinje da glasa za neku vrednost V. To podrazumeva emitovanje poruke u mrežu: „Ja sam čvor N, moji kvorumi Q, i glasam za V“. Kada čvor glasa na ovaj način, on se obavezuje da nikada nije glasao protiv V i nikada neće.
V prenosih od enakih vozlišč vsak vozlišče vidi, kako glasujejo drugi. Ko vozlišče zbere dovolj takšnih sporočil, lahko sledi rezom kvorumov in poskusi najti kvorume. Če vidi kvorum vozlišč, ki prav tako glasujejo za V, lahko preide k sprejemanju V in to novo sporočilo prenese v omrežje: 'Jaz sem vozlišče N, moji rezi kvorumov Q, in sprejemam V'. Sprejemanje zagotavlja močnejšo garancijo kot zgolj glasovanje. Ko vozlišče glasuje za V, nikoli ne more glasovati za druge možnosti. Če pa vozlišče sprejme V, nobeno vozlišče v omrežju nikoli ne bo sprejelo druge možnosti (teorema 8 v tehničnem dokumentu SCP to dokazuje).
Seveda je verjetnost, da takoj ne bo našel kvoruma vozlišč, ki bi se strinjala z V, velika. Druga vozlišča lahko glasujejo za druge vrednosti. Vendar ima vozlišče še en način, kako preiti od preprostega glasovanja k sprejemanju. N lahko sprejme drugo vrednost W, tudi če zanje ni glasovalo, in tudi če ne vidi kvoruma za to. Zadostuje, da vidi blokirajoče množice vozlišč, ki so sprejela W. Blokirajoče množice so po en vozlišče iz vsakega rezanja kvorumov N. Kot pove ime, je sposobno blokirati
katerekoli druge vrednosti. Če vsa vozlišča v tako množico sprejmejo W, potem (po teoremi 8) nikoli ne bo mogoče oblikovati kvoruma, ki bi sprejel drugo vrednost, zato je za N tudi varno sprejeti W.
Vozlišče N z tremi rezi kvorumov.
B-D-F je blokirajoča množica za N: vključuje po en vozlišče iz vsakega reza N.
B-E je prav tako blokirajoča množica za N, ker E nastopa v dveh rezih N.
Toda blokirajoča množica ni kvorum. Prelahko bi bilo prevarati vozlišče N, da sprejme želeno vrednost, če bi bilo dovolj, da bi heker prelomil le eno vozlišče v vsakem rezu N. Zato sprejemanje vrednosti še ne pomeni konca glasovanja. Namesto tega mora N potrditi vrednost, torej videti kvorum vozlišč, ki jo sprejemajo. Če ga doseže, kot dokazuje tehnični dokument SCP (v teoremi 11), bo tudi preostalo omrežje na koncu potrdilo isto vrednost, zato bo N zaključil federativno glasovanje z določeno vrednostjo kot rezultatom.
Postopek glasovanja, sprejetja in potrjevanja predstavlja en celotni krog federativnega glasovanja. Protokol soglasja Stellar združuje več takšnih krogov za ustvarjanje celotnega soglasnega sistema.
Protokol soglasja Stellar
Dve najpomembnejši lastnosti soglasnega sistema sta varnost in odzivnost. Soglasni algoritem je 'varen', če nikoli ne more dati različnih rezultatov različnim udeležencem (kopija zgodovine Boba nikoli ne bo v nasprotju s Carol). 'Odzivnost' pomeni, da algoritem vedno izda rezultat, kar pomeni, da ne obtiči.
Opišani postopek federativnega glasovanja je varen v tem smislu, da če vozlišče potrdi vrednost V, nobeno drugo vozlišče ne bo potrdilo druge vrednosti. Vendar 'ne bo potrdilo druge vrednosti' ne pomeni, da bo nujno nekaj potrdilo. Udeleženci lahko glasujejo za tako veliko število različnih vrednosti, da nič ne doseže praga sprejetja. To pomeni, da v federativnem glasovanju ni odzivnost.
Protokol soglasja Stellar uporablja federativno glasovanje na način, ki zagotavlja tako varnost kot odzivnost. (Zagotavljanje varnosti in odzivnosti SCP ima teoretično omejitev. Konstrukcija izbere zelo močno zagotovilo varnosti, žrtvuje pa majhno oslabitev odzivnosti, vendar glede na dovolj dolgo obdobje bo soglasje z visoko verjetnostjo doseženo). Na kratko, ideja je izvesti več federativnih glasovanj o več vrednostih, dokler ena od njih popolnoma ne preide skozi vse faze glasovanja SCP, opisane spodaj.
Vrednosti, za katere SCP stremi k soglasju, so lahko zgodovina transakcij ali naročilo za malico, ali kaj drugega, vendar je pomembno omeniti, da to niso tiste vrednosti, ki se sprejemajo ali potrjujejo. Namesto tega poteka federativno glasovanje o izjavah o teh vrednostih.
Prvi krogi federativnega glasovanja potekajo na fazni nominaciji (nominacijska faza), pri naboru izjav vrste 'Predlagam V', morda za mnoge različne vrednosti V. Cilj nominacije je najti eno ali več izjav, ki preidejo skozi sprejem in potrditev.
Po iskanju potrjenih kandidatov SCP preide na fazo glasovanja, kjer je cilj najti nek. glasilni list. (torej vsebnik za predlagano vrednost) in kvorum, ki lahko razglasi. commit za njega (commit). Če kvorum izvede commit glasila, se njegova vrednost sprejme kot konsenz. A preden lahko vozlišče glasuje za commit glasila, mora najprej potrditi. preklic. vseh glasil s manjšim števcem. Ti koraki — preklic glasil, da najdejo tistega, za katerega je mogoče potrditi commit — vključujejo več krogov federativnega glasovanja o več trditvah o glasilih.
V naslednjih razdelkih so podrobneje opisani predlog in glasovanje.
Predlog.
Na začetku faze predloga lahko vsako vozlišče spontano izbere vrednost V in glasuje za potrditev 'Jaz predlagam V'. Cilj v tej fazi je potrditi predlog določene vrednosti z federativnim glasovanjem.
Morda bo dovolj vozlišč glasovalo za dovolj različne trditve in noben predlog ne more doseči praga sprejetja. Zato poleg predvajanja lastnih nominacijskih glasov, vozlišča 'odražajo' nominacije svojih peer-ov. Odražanje (echo) pomeni, da če vozlišče glasuje za predlog V, vendar vidi sporočilo od soseda, ki glasuje za predlog W, bo zdaj glasovalo za predlog tako V kot W. (Ne vsi glasovi peer-ov se odražajo med predlogom, ker to lahko privede do eksplozije različnih nominantov. SCP vključuje mehanizem za regulacijo teh glasov. Na kratko, obstaja formula za določitev 'prioritete' peer-a z vidika vozlišča, in odražajo se glasovi le visokoprioritetnih vozlišč. Čim dlje traja predlog, tem nižji je prag, zato vozlišče razširi nabor peer-ov, katerih glasove bo odražalo. Formula prioritete kot enega od vhodnih podatkov vključuje številko slot-a, zato je visokoprioritetno enakovredno vozlišče za en slot lahko nizkoprioritizirano za drugega, in obratno).
Konceptualno, istovremeno iznošenje i V i W je odvojeni federativni glasovi, od kojih svaki može da postigne usvajanje ili potvrdu. U praksi, SCP protokol pakira ove odvojene glasove zajedno.
Iako glasanje za iznošenje V predstavlja obećanje da nikada neće glasati protiv iznošenja V, na nivou aplikacije - u ovom slučaju SCP - određuje se šta znači „protiv“. SCP ne prepoznaje tvrdnju koja protivreči glasanju „Ja iznosim X“, to jest, nema poruke „Ja sam protiv iznošenja X“, pa čvor može glasati za iznos svake vrednosti. Mnogi od ovih nominacija neće dovesti do ničega, ali u konačnici čvor će moći da prihvati ili potvrdi jednu ili više vrednosti. Kada je nominant potvrđen, postaje kandidat.
Iznošenje SCP-a koristeći federativno glasanje. Mnoge vrednosti 'B' mogu se iznositi od strane ravnopravnih čvorova i 'reflektovati' od strane čvora.
Iznošenje kandidata može dovesti do pojave više potvrđenih kandidata. Stoga SCP zahteva da aplikacioni nivo pruži neku metodu za spajanje kandidata u jedan kompozit (composite). Metoda spajanja može biti bilo koja. Glavna stvar je da, ako je ova metoda deterministička, svaki čvor će spojiti iste kandidate. U sistemu glasanja za ručak, 'spajanje' može jednostavno značiti odbacivanje jednog od dva kandidata. (Ali deterministički: svaki čvor mora izabrati istu vrednost za poništavanje. Na primer, raniji izbor u abecednom redu). U platnoj mreži Stellar, gde se glasa o istoriji transakcija, spajanje dva predložena nominanta podrazumeva spajanje transakcija koje sadrže i poslednjih od njih dve vremenske oznake.
Tehnički opis SCP-a dokazuje (teorema 12) da se do kraja faze iznošenja mreža konačno konvergira ka jednom kompozitu. Ali postoji problem: federativno glasanje je asinhroni protokol (kao i SCP). Drugim rečima, čvorovi nisu usaglašeni u vremenu, već samo u porukama koje šalju. Sa stanovišta čvora nije jasno kada se je končala faza potiskanja. In čeprav bodo vsi vozli na koncu prišli do istega združevanja, lahko izberejo različne poti na tej poti, kar ustvarja različne sestavne kandidate, in nikoli ne morejo povedati, kateri je končni.
Ampak to je v redu. Potiskanje je le priprava. Glavno je omejiti število kandidatov za dosego konsenza, ki nastane v procesu glasovanja (glasovanje).
Glasovanje
Glasovnica je par , kjer je counter celo število, ki se začne s 1, value pa je kandidat iz faze potiskanja. To je lahko lastni kandidat vozla ali kandidat sosednjega vozla, ki ga sprejema to vozlo. Na grobo, pri glasovanju se izvajajo večkratni poskusi za dosego konsenza v omrežju o nekem kandidatu v neki glasovnici z izvajanjem potencialno številnih federativnih glasovanj o izjavah o glasovnicah. Števci v glasovnicah spremljajo opravljene poskuse in glasovnice z višjimi števci imajo prednost pred glasovnicami z nižjimi števci. Če glasovnica zmrzne, se začne novo glasovanje, zdaj o glasovnici .
Pomembno je razlikovati pomeni (na primer, kakšna naj bo naročilo za kosilo: pica ali solate), glasovnice (par counter-value) in izjave o glasovnicah. Krog SCP vključuje več krogov federativnih glasovanj, zlasti o takih izjavah:
- "Pripravljen sem potrditi glasovnico B" in
- "Jaz razglašam potrditev glasovnice B"
Z vidika tega vozla se konsenz doseže, ko najde glasovnico B, za katero lahko potrdi (tj. najde kvorum, ki sprejema) izjavo "Jaz razglašam potrditev glasovnice B". Od tega trenutka je mogoče varno delovati po vrednosti, navedeni v B – na primer, oddati to naročilo za kosilo. To se imenuje eksternalizacija vrednosti. Ko je potrjeno sprejetje glasovnice, lahko vozlo verjame, da je katero koli drugo vozlo opravilo eksteralizacijo te iste vrednosti ali jo bo nujno opravilo v prihodnosti.
Čeprav konceptualno mnoge federativne volitve potekajo na podlagi izjav o več različnih glasovnicah, si izmenjajo manjšo količino sporočil, saj vsako sporočilo inkapsulira vrsto glasovnic. Tako eno sporočilo promovira stanje več federativnih volitev hkrati, na primer: „Sprejemam zavezo glasovnic v razponu od do .”
Kaj pomenita izraza „pripravljen” (prepared) in „zaveza” (commit)?
Svojo zavezo glasovnice odda vozlišče, ko je prepričano, da druga vozlišča ne bodo oddala zaveze glasovnic z drugimi vrednostmi. Prepričanje o tem je cilj pripravljanja izjave. Glasovanje, v katerem se izjasni: „Pripravljen sem na zavezo glasovnice B”, je obljuba, da nikoli ne bom oddal zavezo glasovnice, ki je manjša od B, tj. z manjšim števcem (SCP zahteva, da imajo vrednosti v glasovnicah določen red. Tako je glasovnica manjša od , če je N1<N2, prav tako, če je N1=N2 in V1<V2). Te manjše glasovnice se „prekličejo” (aborted) med pripravljalnim glasovanjem, medtem ko je B obravnavana kot „pripravljena”.
Zakaj „Pripravljen sem na zavezo glasovnice V” pomeni „Obljubljam, da nikoli ne bom dovolil zaveze glasovnic, manjših od V”? Ker SCP definira abort kot nasprotje commit. Glasovanje o pripravljenosti glasovnice prav tako implicira glasovanje o preklicu nekaterih drugih glasovnic, in, kot smo že razpravljali, glasovanje za nekaj enega je obljuba, da se nikoli ne bom glasoval proti temu.
Preden odda zavezo, mora vozlišče najprej najti glasovnico, ki jo lahko potrdi kot pripravljeno. Z drugimi besedami, opravi federativno glasovanje na temo „Pripravljen sem na zavezo glasovnice B”, morda za več različnih glasovnic, dokler ne najde tiste, ki sprejme kvorum.
Kje izhajajo glasovnice za pripravo glasovanja? Najprej vozlišče prenese pripravo za glasovanje za , kjer je C kandidat-kompozit, ki je bil pripravljen v fazi predloga. Vendar pa lahko tudi po začetku priprave na glasovanje predlog vodi do dodatnih kandidatov, ki postanejo nove glasovnice. Medtem imajo lahko pirom različne kandidate in lahko oblikujejo blokirno množico, ki sprejema "Pripravljen sem za potrjevanje glasovnice B2", kar prepriča vozlišče, da jo tudi sprejme. Nazadnje obstaja mehanizem časovne omejitve, ki generira nove načine federativnega glasovanja na novih glasovnicah z višjimi števcem, če trenutne glasovnice obtičijo.
Ko vozlišče najde glasovnico B, ki jo lahko potrdi kot pripravljeno, prenese novo sporočilo "Potrditev glasovnice B". To glasovanje pove pirom, da vozlišče nikoli ne bo opustilo B. V resnici, če je B glasovnica , to pomeni "Potrditev glasovnice " brezpogojno soglasje za glasovanje o pripravljenosti vsake glasovnice od do . Ta dodatna vrednost pomaga drugim vozliščem, da uhitijo pira s potrditvijo, če so še na prejšnjih fazah protokola.
Na tej točki je vredno ponovno poudariti, da so to asimetrični protokoli. To, da eno vozlišče odda glasove za potrditev, ne pomeni, da tudi njegovi vrstniki to počnejo. Nekateri od njih morda še vedno kažejo glasove za prijave za pripravo glasovanja, drugi so morda že eksternalizirali vrednost. SCP razlaga, kako mora vozlišče obravnavati vsak tip enakovrednega sporočila ne glede na njegovo fazo.
Če sporočilo „Jaz razglašam commit <N,C>“ ne more biti sprejeto ali potrjeno, obstaja možnost sprejema ali potrjevanja sporočila <N+1,C> ali <N+2,C> — ali, v vsakem primeru, katerega koli biltena s vrednostjo C, ne pa katerega koli drugega, saj je vozlišče že obljubilo, da nikoli ne prekliče <N,C>. Do takrat, ko vozlišče odda glasove za commit, bo to C ali nič, odvisno od tega, kako daleč bo šel konsenz. Vendar to še ni dovolj, da bi vozlišče lahko eksternaliziralo C. Nekateri bizantinski bendi (ki predstavljajo manj kot kvorum, na podlagi naših predpostavk o varnosti) lahko lažejo vozlišču. Sprejem in nato potrditev nekega biltena (ali niza biltenov) je to, kar vozlišču daje zaupanje, da končno eksternalizira C.
Glasovanje SCP prek federativnega glasovanja. Ni prikazano: kadarkoli se lahko sproži časovnik, ki poveča števec v biltenu (in morda ustvari nov kompozit iz dodatno predlaganih kandidatov).
In to je to! Ko doseže omrežje konsenz, je pripravljeno to početi znova in znova. V plačilnem omrežju Stellar se to zgodi približno na vsakih 5 sekund: podvig, ki zahteva tako varnost kot obstojnost, garantiran s SCP.
SCP to doseže z več krogi federativnega glasovanja. Federativno glasovanje je postalo mogoče zaradi koncepta rezov kvoruma: sklopov enakopravnih vozlišč, katerim je vsak vozlišče se odločilo zaupati kot del svojega (subjektivnega) kvoruma. Ta konfiguracija pomeni, da lahko pridemo do konsenza tudi v omrežju odprtega članstva in bizantinskimi prevarami.
Dodatno branje
- Izvirni tehnični dokument SCP je na voljo , a projekt specifikacij za njegovo izvajanje.
- Izvirni avtor protokola SCP David Mazier poenostavljeno (a vendar tehnično) razlaga njegov .
- Morda ste bili presenečeni, ker v tem članku niste našli izrazov „rudarjenje“ ali „dokaz delovanja“. SCP ne uporablja teh metod, vendar jih uporabljajo nekateri drugi algoritmi konsenza. Zane Wiser spoon je napisal dostopen .
- preproste mreže, ki doseže konsenz v eni celotni rundi SCP.
- Za bralce, ki jih zanima izvajanje SCP: glej. , ki ga uporablja plačilna mreža Stellar, ali , ki sem jo napisal za boljše razumevanje SCP.
Izvor: habr.com
