Protokol Stellar konsenzusa je prvi put opisan u David Mazier 2015. Ovo je „federalni vizantijski sporazumni sistem“ koji omogućava decentralizovanim računarskim mrežama bez lidera da efikasno postignu konsenzus o odluci. Stellar platna mreža koristi Stellar Consensus Protocol (SCP) za održavanje konzistentne istorije transakcija koja je vidljiva svim učesnicima.
Smatra se da su protokoli konsenzusa teško razumljivi. SCP je jednostavniji od većine njih, ali i dalje dijeli ovu reputaciju - dijelom zbog pogrešne ideje da je "federativno glasanje", što je tema prve polovine naučnog članka, SCP. Ali to nije istina! Ovo je samo važan građevni blok koji druga polovina članka koristi za stvaranje aktuelna Protokol zvjezdanog konsenzusa.
U ovom članku ćemo ukratko objasniti šta je „sistem ugovora“, šta ga može učiniti „vizantijskim“ i zašto vizantijski sistem učiniti „federalnim“. Zatim ćemo objasniti proceduru federalnog glasanja opisanu u SCP članku, a na kraju ćemo objasniti i sam SCP protokol.
Sistemi sporazuma
Sistem dogovora omogućava grupi učesnika da postigne konsenzus o nekoj temi, kao što je šta naručiti za ručak.
U Interstellaru smo implementirali vlastiti sistem dogovora o blagovanju: naručujemo ono što kaže naš operativni menadžer John. Ovo je jednostavan i efikasan sistem dogovora. Svi vjerujemo Johnu i vjerujemo da će svaki dan pronaći nešto zanimljivo i hranljivo.
Ali šta ako Džon zloupotrebi naše poverenje? On može sam odlučiti da svi trebamo postati vegani. Za nedelju ili dve, verovatno ćemo ga svrgnuti i predati vlast Elizabeti. Ali odjednom voli avokado sa inćunima i misli da bi svi trebali biti takvi. Snaga kvari. Zato je bolje pronaći neku demokratskiju metodu: neki način da se uzmu u obzir različita preferencije, a da se pritom osigura pravovremeni i nedvosmislen rezultat, tako da niko na kraju ne naruči ručak, ili da pet osoba naruči različite narudžbe, ili diskusiju povlači se u veče.
Čini se da je rješenje jednostavno: održite glasanje! Ali ovo je pogrešan utisak. Ko će prikupiti glasačke listiće i prijaviti rezultate? I zašto bi drugi verovali u ono što on kaže? Možda možemo na početku glasajte za lidera kome vjerujemo da će voditi glasanje - ali koji će ga voditi prvo glasanjem? Šta ako se ne možemo dogovoriti oko vođe? Ili šta ako se dogovorimo, ali ovaj vođa zaglavi na sastanku ili ode na bolovanje?
Slični problemi se javljaju u distribuiranim računarskim mrežama. Svi sudionici ili čvorovi moraju se složiti oko neke odluke, na primjer čiji je red da ažurira dijeljeni fajl ili ukloni zadatak iz reda za obradu. U mreži kriptovaluta, čvorovi stalno moraju birati kako će cijela priča izgledati iz nekoliko mogućih verzija, koje se ponekad sukobljavaju. Ovaj mrežni ugovor pruža sigurnost primaocu da je novčić (a) važeći (nije krivotvoren) i (b) da još nije potrošen na drugom mjestu. To također osigurava da će moći trošiti novčiće u budućnosti jer će novi primalac imati iste garancije iz istih razloga.
Svaki sistem konsenzusa u distribuiranoj računarskoj mreži mora biti tolerantan na greške: mora proizvesti konzistentne rezultate uprkos greškama kao što su spore veze, čvorovi koji ne reaguju i netačan redosled poruka. Byzantine Sistem dogovora je dodatno otporan na "vizantijske" greške: čvorove koji daju lažne informacije, bilo zbog greške ili u namjernom pokušaju da se potkopa sistem ili stekne neka prednost. "Vizantijska" tolerancija grešaka - sposobnost vjerovanja grupnoj odluci čak i kada neki članovi grupe mogu lagati ili na drugi način ne slijediti pravila donošenja odluka - naziva se koji je pokušao da koordinira napad. kod Anthony Stevensa.
Zamislite vlasnicu kripto kovanica Alice, koja mora birati između kupovine ukusnog sladoleda od Boba i otplate Kerolinog duga. Možda Alice želi platiti oboje odjednom lažnim trošenjem istog novčića. Da bi to učinila, ona mora uvjeriti Bobov kompjuter da novčić nikada nije plaćen Kerol i uvjeriti Kerolin kompjuter da novčić nikada nije plaćen Bobu. Vizantijski sistem sporazuma to čini praktično nemogućim, koristeći oblik vladavine većine tzv kvorum. Čvor u takvoj mreži odbija da pređe na određenu verziju istorije sve dok ne vidi da dovoljan broj vršnjaka - kvorum - pristaje na takvu tranziciju. Jednom kada se to dogodi, oni će formirati glasački blok koji je dovoljno velik da prisili preostale mrežne čvorove da se slože s njihovom odlukom. Alice može natjerati neke čvorove da lažu u njeno ime, ali ako je mreža dovoljno velika, njen pokušaj će biti nadvladan glasovima poštenih čvorova.
Koliko čvorova je potrebno za kvorum? U najmanju ruku, većina, ili bolje rečeno, kvalifikovana većina za borbu protiv grešaka i prijevara. Ali da biste prebrojali većinu, morate znati ukupan broj učesnika. U Interstellar kancelariji ili na izborima u okrugu, ove brojke je lako saznati. Ali ako je vaša grupa slabo definirana mreža u koju čvorovi mogu ulaziti i izlaziti po volji bez odobrenja centra, onda vam je potrebno federalni vizantijski sporazumni sistem sposoban da odredi kvorume ne iz unapred određene liste čvorova, već dinamički, iz stalno promenljivog i neizbežno nekompletnog snimka čvorova u datom trenutku.
Možda izgleda nemoguće stvoriti kvorum iz perspektive jednog čvora u ogromnoj mreži, ali je moguće. Takav kvorum može čak garantovati rezultate decentralizovanog glasanja. SCP bijeli papir pokazuje kako se to može učiniti koristeći proceduru tzv saveznim glasanjem.
Za nestrpljivo
Ostatak članka detaljnije opisuje federalno glasanje i Stellar protokol konsenzusa. Ako vas ne zanimaju detalji, evo opšteg pregleda procesa.
- Čvorovi provode krugove federalnog glasanja o "nominiranima". Savezni krug glasanja znači:
- Čvor glasa za neku izjavu, na primjer, “Predlažem vrijednost V”;
- Čvor sluša glasove vršnjaka dok ne pronađe onaj koji može "primiti";
- Čvor traži "kvorum" za ovu tvrdnju. Kvorum "potvrđuje" kandidata.
- Jednom kada čvor može potvrditi jednog ili više kandidata, pokušava "pripremiti" "glasački listić" kroz nekoliko krugova udruženog glasanja.
- Jednom kada je čvor u mogućnosti da potvrdi da je glasački listić spreman, pokušava ga izvršiti kroz još više krugova udruženog glasanja.
- Jednom kada čvor može potvrditi urezivanje glasačkog listića, može "eksternalizirati" vrijednost tog glasačkog listića koristeći ga kao rezultat konsenzusa.
Ovi koraci uključuju više krugova federalnog glasanja, koji zajedno čine jedan krug SCP-a. Pogledajmo bliže šta se dešava na svakom koraku.
Federalno glasanje
Udruženo glasanje je postupak za određivanje da li se mreža može složiti oko prijedloga. U krugu glasanja, svaki čvor mora izabrati jednu od potencijalno mnogo mogućih vrijednosti. Ne može to učiniti osim ako je uvjeren da drugi čvorovi u mreži neće izabrati drugačiji ishod. Da bi bili sigurni u to, čvorovi razmjenjuju hrpu poruka naprijed-nazad tako da svi potvrđen, to kvorum čvorovi prihvata isti odluka. Ostatak ovog odjeljka objašnjava termine u ovoj rečenici i kako se odvija čitava procedura.
Kvorumi i dijelovi kvoruma
Počnimo s definiranjem kvoruma. Kao što smo gore raspravljali, u decentraliziranoj mreži sa dinamičkim članstvom, nemoguće je unaprijed znati broj čvorova, a samim tim i koliko ih je potrebno za većinu. Federalno glasanje rješava ovaj problem uvođenjem nove ideje kvorum cut (kvorum slice): Mali skup vršnjaka kojima čvor vjeruje da bi prenio informacije o statusu glasanja ostatku mreže. Svaki čvor definira svoj vlastiti kvorum (čiji postaje de facto član).
Formiranje kvoruma počinje sečenjem kvoruma. Za svaki čvor dodaju se njegovi izrezani čvorovi. Zatim se dodaju termini sreza ovi čvorovi i tako dalje. Kako nastavite, sve je više čvorova koje ne možete dodati jer su već uključeni u isječak. Kada više nema novih čvorova za dodavanje, proces se zaustavlja: formirali smo kvorum “tranzitivnim zatvaranjem” kvoruma isječka početnog čvora.
Da biste pronašli kvorum iz datog čvora...
... dodaj članove svog dijela...
...onda dodajemo članove preseka ovih čvorova.
Nastavljamo sve dok ne ostane nijedan čvor za dodavanje.
Nema više čvorova za dodavanje. Ovo je kvorum.
U stvari, svaki čvor se može pojaviti u više od jednog dijela. Da biste formirali kvorum, odaberite samo jedan od rezova i dodajte članove; zatim odaberite bilo koji dio za svakog od članova i dodajte članove to rezati i tako dalje. To znači da je svaki čvor član mnogih mogućih kvoruma.
Odaberite samo jednu kvorumsku dionicu u svakom koraku.
Jedan mogući kvorum. Ili alternativa...
...odaberite druge kriške...
…(kada je to moguće)…
... stvara još jedan kvorum.
Kako čvor zna u kojim se rezovima nalaze drugi čvorovi? Na isti način kao i ostale informacije o drugim čvorovima: od prijenosa koje svaki čvor emituje na mrežu kada se promijeni stanje glasanja. Svako emitiranje uključuje informacije o dijelovima čvora koji šalje. Bijela knjiga SCP-a ne navodi mehanizam komunikacije. Implementacije obično koriste za garantovano emitovanje poruka širom mreže.
Podsjetimo da je u nefederalnom vizantijskom sistemu sporazuma kvorum definiran kao većina svih čvorova. Vizantijski sporazumni sistem je dizajniran sa stanovišta pitanja: koliko nepoštenih čvorova sistem može tolerisati? U sistemu od N čvorova koji je dizajniran da preživi f kvarova, čvor bi trebao biti u stanju da napreduje primanjem povratnih informacija od N-f vršnjaka jer f može biti u kvaru. Ali nakon što smo dobili odgovor od N−f kolega, možemo pretpostaviti da su svi f ravnopravni (od kojih čvor nije dobio odgovor) zapravo iskreni. Dakle, f od N−f vršnjaka (od kojih je primljen odgovor) su zlonamjerni. Da bi čvorovi došli do istog konsenzusa, većina preostalih čvorova mora biti iskrena, to jest, potrebno nam je da N−f bude veći od 2f ili N > 3f. Dakle, tipično će sistem dizajniran da preživi f kvarova imati ukupno N=3f+1 čvorova i veličinu kvoruma 2f+1. Kada prijedlog prijeđe prag kvoruma, ostatak mreže je uvjeren da će bilo koji konkurentski prijedlozi propasti. Ovako se mreža konvergira do rezultata.
Ali u federalnom vizantijskom sporazumnom sistemu, ne samo da ne može postojati većina (jer niko ne zna ukupnu veličinu mreže), već je koncept većine potpuno beskoristan! Ako je članstvo u sistemu otvoreno, onda neko može steći većinu jednostavnim izvođenjem takozvanog napada na Sybil: više puta se pridružujući mreži preko više čvorova. Pa zašto se može nazvati tranzitivno zatvaranje preseka kvorum, i kako je u stanju suzbiti konkurentske prijedloge?
Tehnički, nema šanse! Zamislite mrežu od šest čvorova, gdje su dvije trojke izolirane u kvorumskim rezovima. Prva podgrupa može donijeti odluku za koju druga nikada neće čuti, i obrnuto. Ne postoji način da ova mreža postigne konsenzus (osim slučajno).
Stoga, SCP zahtijeva da za udruženo glasanje (i da bi se važne teoreme rada primjenjivale), mreža mora imati svojstvo tzv. presek kvoruma. U mreži sa ovim svojstvom, bilo koja dva kvoruma koja se mogu konstruisati uvijek se preklapaju u najmanje jednom čvoru. Za određivanje preovlađujućeg raspoloženja mreže, ovo je jednako dobro kao da imate većinu. Intuitivno, to znači da ako se bilo koji kvorum složi sa izjavom X, nijedan drugi kvorum se nikada ne može složiti ni sa čim drugim, jer će nužno uključiti neki čvor iz prvog kvoruma koji je već glasao za X.
Ako postoji raskrsnica kvoruma u mreži...
...onda bilo koja dva kvoruma koja možete izgraditi...
...uvek će se ukrštati.
(Naravno, čvorovi koji se preklapaju mogu se pokazati kao vizantijski ili na neki drugi način loši. U ovom slučaju, raskrsnica kvoruma uopće ne pomaže mreži da se dogovori. Iz tog razloga, mnogi rezultati u SCP bijeloj knjizi su zasnovani na eksplicitne pretpostavke, kao što je ono što je ostalo u mreži kvoruma čak i nakon uklanjanja loših čvorova. Radi jednostavnosti, ostavimo ove pretpostavke implicitno u ostatku članka).
Može se činiti nerazumnim očekivati da je pouzdano ukrštanje kvoruma moguće u mreži nezavisnih čvorova. Ali postoje dva razloga zašto je to tako.
Prvi razlog je postojanje samog interneta. Internet je savršen primjer mreže nezavisnih čvorova sa kvorumima koji se ukrštaju. Većina čvorova na Internetu se povezuje sa samo nekoliko drugih lokalnih čvorova, ali ovi mali skupovi se dovoljno preklapaju da se do svakog čvora može doći iz svakog drugog čvora duž neke rute.
Drugi razlog je specifičan za mrežu plaćanja Stellar (najčešća upotreba SCP-a). Svaka imovina na Stellar mreži ima izdavaoca, a Stellarove smjernice zahtijevaju od svakog izdavaoca da odredi jedan ili više čvorova na mreži za obradu zahtjeva za otkup. U vašem je najboljem interesu da direktno ili indirektno uključite ove čvorove u rezove kvoruma za svako sredstvo koje vas zanima. Kvorumi za sve čvorove zainteresovane za dato sredstvo će se tada preklapati barem na tim čvorovima otkupa. Čvorovi zainteresirani za više sredstava uključit će sve čvorove otkupa odgovarajućih emitenata u svoje kvorumske dijelove i nastojat će udružiti svu imovinu zajedno. Osim toga, sva sredstva koja nisu na ovaj način povezana s drugima na mreži, i ne bi trebao biti povezan - ovo je osmišljeno tako da nema preklapanja kvoruma za ovu mrežu (npr. banke iz dolarske zone ponekad žele da trguju sa bankama iz zone evra i bankama iz peso zone, pa su na istoj mreži, ali nijedna od njih brine o odvojenoj mreži djece koja prodaju bejzbol karte).
Naravno, čekaju prelaz kvoruma nije garancija. Drugi vizantijski sistemi sporazuma duguju veliki dio svoje složenosti garanciji kvoruma. Važna inovacija SCP-a je da uklanja odgovornost za stvaranje kvoruma iz samog algoritma konsenzusa i dovodi ga na nivo aplikacije. Stoga, iako je federalno glasanje dovoljno uopšteno da se glasa o bilo kom pitanju, njegova pouzdanost zapravo kritično zavisi od šireg značenja ovih značenja. Neke hipotetičke upotrebe možda neće biti tako pogodne za stvaranje dobro povezanih mreža kao druge.
Glasanje, prihvatanje i potvrda
U federalnom krugu glasanja, čvor opciono počinje glasati za neku vrijednost V. To znači emitiranje poruke mreži: “Ja sam čvor N, moji kvorumski dijelovi su Q, a ja glasam za V.” Kada čvor glasa na ovaj način, on obećava da nikada nije glasao protiv V i da nikada neće.
U peer-to-peer emitovanju, svaki čvor vidi kako drugi glasaju. Jednom kada čvor prikupi dovoljno ovih poruka, može pratiti dijelove kvoruma i pokušati pronaći kvorume. Ako vidi kvorum kolega koji takođe glasaju za V, može nastaviti usvajanje V i emitujte ovu novu poruku mreži: „Ja sam čvor N, moji kvorumski delovi su Q, i prihvatam V.” Prihvatanje pruža jaču garanciju od običnog glasanja. Kada čvor glasa za V, nikada ne može glasati za druge opcije. Ali ako čvor prihvati V, nijedan čvor na mreži nikada neće prihvatiti drugu opciju (teorema 8 u SCP bijeloj knjizi to dokazuje).
Naravno, postoji velika vjerovatnoća da odmah neće postojati kvorum čvorova koji se slažu sa V. Drugi čvorovi mogu glasati za druge vrijednosti. Ali postoji još jedan način da čvor pređe sa jednostavnog glasanja na prihvatanje. N može prihvatiti drugačiju vrijednost za W, čak i ako nije glasao za to, pa čak i ako ne vidi kvorum za to. Da biste odlučili promijeniti svoj glas, pogledajte blok za blokiranje čvorovi koji su prihvatili W. Blokirajući skup je jedan čvor iz svakog kvoruma N. Kao što ime sugerira, može blok bilo koje drugo značenje. Ako svi čvorovi u takvom skupu prihvate W, tada (prema teoremi 8) nikada neće biti moguće formirati kvorum koji ima drugačiju vrijednost, pa je stoga sigurno da N prihvati W.
Čvor N sa tri kvoruma preseka.
BDF je skup za blokiranje za N: uključuje po jedan čvor iz svake isječke N.
BE je također skup za blokiranje za N jer se E pojavljuje u dva dijela N.
Ali skup za blokiranje nije kvorum. Bilo bi previše lako prevariti čvor N da prihvati željenu vrijednost ako je bilo dovoljno hakovati samo jedan čvor u svakom od isječaka N. Stoga prihvatanje vrijednosti nije kraj glasanja. Umjesto toga, N mora potvrditi vrijednost, odnosno vidjeti kvorum čvorova koji je prihvata. Ako stigne tako daleko, onda, kao što SCP whitepaper dokazuje (u teoremi 11), ostatak mreže će također na kraju potvrditi istu vrijednost, tako da će N završiti udruženo glasanje sa određenom vrijednošću kao rezultatom.
Federalno glasanje.
Proces glasanja, prihvatanja i potvrđivanja čini jedan puni krug zajedničkog glasanja. Stellar konsenzus protokol kombinuje mnoge od ovih rundi kako bi stvorio potpuni sistem konsenzusa.
Stellar Consensus Protocol
Dva najvažnija svojstva sistema konsenzusa su − sigurnost и preživljavanje. Algoritam konsenzusa je "siguran" ako nikada ne može dati različite rezultate različitim učesnicima (Bobova kopija istorije nikada neće biti u suprotnosti sa Carol). „Životnost“ znači da će algoritam uvijek proizvesti rezultat, odnosno neće se zaglaviti.
Opisana procedura federalnog glasanja sigurno u smislu da ako čvor potvrdi vrijednost V, nijedan drugi čvor neće potvrditi drugu vrijednost. Ali “neće potvrditi drugo značenje” ne znači da će nužno nešto potvrditi. Učesnici mogu glasati za toliko različitih vrijednosti da ništa neće dostići prag prihvatanja. To znači da na federalnom glasanju nema preživljavanje.
Protokol Stellar konsenzusa koristi udruženo glasanje na način koji osigurava sigurnost i preživljavanje. (SCP-ove garancije sigurnosti i preživljavanja imaju teoretsko ograničenje. Dizajn bira vrlo jaku sigurnosnu garanciju, žrtvujući malo ublažavanje preživljavanja, ali s obzirom na dovoljno vremena, vrlo je vjerovatno da će se postići konsenzus.) Ukratko, ideja je imati više udruženih glasova za više vrijednosti sve dok jedan od njih ne prođe kroz sve faze SCP glasanja opisane u nastavku.
Vrijednosti o kojima SCP traži konsenzus mogu biti povijest transakcija ili narudžba za ručak ili nešto drugo, ali važno je napomenuti da to nisu vrijednosti koje se prihvaćaju ili potvrđuju. Umjesto toga, federalno glasanje se odvija prema izjave o ovim vrijednostima.
Održavaju se prvi krugovi saveznog glasanja faza nominacije (faza nominacije), na skupu izjava kao što je „Nominiram V“, možda za mnogo različitih vrijednosti V. Svrha nominacije je pronaći jednu ili više izjava koje prolaze kroz prihvaćanje i potvrdu.
Nakon pronalaženja provjerljivih kandidata, SCP prelazi na fazu glasanja, gdje je cilj pronaći određeni bilten (odnosno, kontejner za predloženu vrijednost) i kvorum koji se može deklarirati počiniti za to (počiniti). Ako kvorum izvrši glasanje, njegova vrijednost se prihvata kao konsenzus. Ali prije nego što čvor može glasati za urezivanje glasanja, prvo mora potvrditi otkazivanje svi glasački listići sa manjom protuvrijednošću. Ovi koraci – poništavanje glasačkih listića kako bi se pronašao onaj koji se može izvršiti – uključuju više krugova federalnog glasanja o višestrukim zahtjevima za glasanje.
Sljedeći odjeljci detaljnije opisuju nominacije i glasanje.
Nominacija
Na početku faze nominacije, svaki čvor može spontano izabrati vrijednost za V i glasati za izjavu “Imenujem V”. Cilj u ovoj fazi je potvrditi nominaciju neke vrijednosti putem saveznog glasanja.
Možda dovoljno čvorova glasa za dovoljno različite prijedloge da nijedna nominacija ne može dosegnuti prag prihvatanja. Stoga, osim što emituju vlastite glasove za nominaciju, čvorovi „reflektuju“ nominacije svojih kolega. Eho znači da ako čvor glasa za nominaciju V, ali vidi poruku od susjeda koji glasa za nominaciju W, sada će glasati i za V i za W. (Ne odjekuju svi glasovi kolega tokom nominacije jer to može dovesti do eksplozije različiti nominovani. SCP uključuje mehanizam za regulisanje ovih glasova. Ukratko, postoji formula za određivanje "prioriteta" vršnjaka sa tačke gledišta čvora, a odražavaju se samo glasovi čvorova visokog prioriteta. Što je nominacija duža uzima, što je prag niži, tako da čvor proširuje skup kolega čije će glasove odražavati. Formula prioriteta uključuje broj slota kao jedan od svojih ulaza, tako da ravnopravna jedinica visokog prioriteta za jedan slot može biti ravnopravna jedinica niskog prioriteta za drugo, i obrnuto).
Konceptualno, nominacija je paralelna, i V i W su odvojeni savezni glasovi, svaki pojedinačno može postići prihvatanje ili potvrdu. U praksi, poruke SCP protokola pakuju ove pojedinačne glasove zajedno.
Iako je glasanje za V-ovu nominaciju obećanje da se nikada neće glasati protiv V-ove nominacije, na nivou primjene - u ovom slučaju SCP - se utvrđuje šta znači "protiv". SCP ne vidi izjavu koja je u suprotnosti sa glasanjem "I nominiram X", to jest, ne postoji poruka "Ja sam protiv nominovanja X", tako da čvor može glasati za nominaciju bilo koje vrijednosti. Mnoge od ovih nominacija neće ići nigdje, ali će na kraju čvor moći prihvatiti ili potvrditi jednu ili više vrijednosti. Kada se kandidat potvrdi, on postaje kandidat.
SCP nominacija korištenjem federalnog glasanja. Može postojati mnogo "B" vrijednosti koje iznose vršnjaci i "reflektira" čvor.
Nominacije mogu rezultirati višestrukim potvrđenim kandidatima. Stoga, SCP zahtijeva da sloj aplikacije obezbijedi neki metod kombinovanja kandidata u jedan kompozitni (kompozit). Metoda spajanja može biti bilo koja. Glavna stvar je da ako je ova metoda deterministička, tada će svaki čvor kombinirati iste kandidate. U sistemu glasanja za ručak, "ujedinjenje" može jednostavno značiti odbijanje jednog od dva kandidata. (Ali na deterministički način: svaki čvor mora odabrati istu vrijednost za resetiranje. Na primjer, raniji odabir po abecednom redu). U platnoj mreži Stellar, gdje se glasa o historiji transakcija, spajanje dva predložena kandidata uključuje spajanje transakcija koje sadrže i posljednje od njihove dvije vremenske oznake.
SCP whitepaper dokazuje (teorema 12) da se na kraju faze proširenja mreža na kraju konvergira u jedan kompozit. Ali postoji problem: udruženo glasanje je asinhroni protokol (kao SCP). Drugim riječima, čvorovi nisu koordinirani vremenom, već samo porukama koje šalju. Sa tačke gledišta čvora, nejasno je kada završio faza produženja. I iako će svi čvorovi na kraju doći do istog kompozita, oni mogu ići različitim rutama na putu, stvarajući različite kompozitne kandidate na putu, i nikada ne mogu reći koji je od njih konačni.
Ali to je normalno. Nominacija je samo priprema. Glavna stvar je ograničiti broj kandidata kako bi se postigao konsenzus, koji se javlja u procesu kandidovanje za funkciju (glasanje).
Trčanje
Bilten je par , gdje je brojač cijeli broj koji počinje od 1, a vrijednost je kandidat iz faze nominacije. To može biti vlastiti kandidat čvora ili kandidat susjednog čvora kojeg taj čvor prihvaća. Grubo govoreći, glasanje uključuje ponovljene pokušaje da se mreža prisili da postigne konsenzus o nekom kandidatu na nekom glasačkom listiću tako što će održati potencijalno mnogo saveznih glasova na izjavama o glasanju. Brojači na glasačkim listićima prate učinjene pokušaje, a listići sa većim brojem glasova imaju prednost nad listićima sa manjim brojem glasova. Ako je bilten zapne, počinje novo glasanje, sada na glasačkom listiću .
Važno je razlikovati vrijednosti (na primjer, kakav bi trebao biti ručak: pica ili salate), bilteni (par protiv vrijednosti) i izjave o glasačkim listićima. SCP runda uključuje nekoliko krugova federalnog glasanja, posebno o sljedećim izjavama:
- "Spreman sam da glasam B" i
- "Objavljujem izvršenje glasanja B"
Iz perspektive datog čvora, konsenzus se postiže kada pronađe glasački listić B za koji može potvrditi (tj. pronaći kvorum koji prihvata) izjavu "Ja povjeravam glasački listić B." Od ovog trenutka, sigurno je djelovati prema vrijednosti navedenoj u B - na primjer, naručiti ovu narudžbu za ručak. To se zove eksternalizacija značenja. Kada se potvrdi prihvatanje glasačkog listića, čvor može biti siguran da je bilo koji drugi čvor eksternalizirao istu vrijednost ili će to učiniti u budućnosti.
Iako se mnoga udružena glasanja konceptualno provode na osnovu zahtjeva za mnogo različitih glasačkih listića, oni ne razmjenjuju toliko poruka jer svaka poruka sadrži određeni broj glasačkih listića. Jedna poruka tako promoviše stanje mnogih saveznih glasova odjednom, na primjer: „Prihvatam potvrdne glasačke listiće u rasponu od prije "
Šta znače izrazi “pripremljen” i “posvećeni”?
Čvor glasa za urezivanje glasačkog listića kada je siguran da drugi čvorovi neće urezati glasačke listiće s različitim vrijednostima. Uvjeravanje u to je svrha pripreme prijave. Glas koji kaže "Spreman sam da izvršim glasanje B" je obećanje da nikada neće dati glasački listić manji od B, tj. sa manjim brojem (SCP zahtijeva da vrijednosti u listićima budu u određenom redoslijedu. Dakle, bilten manje , ako je N1
Zašto “spreman sam da glasam B” znači “obećavam da nikada neću dati glasačke listiće manje od B”? Zato što SCP definiše prekid kao suprotnost urezivanja. Glasanje za pripremu glasačkog listića također uključuje glasanje za diskvalifikaciju nekih drugih listića, a, kao što smo ranije raspravljali, glasanje za jednu stvar je obećanje da nikada nećete glasati protiv.
Prije emitiranja urezivanja, čvor prvo mora pronaći bilten koji može potvrditi da je pripremljen. Drugim riječima, vrši udruženo glasanje o temi „Spreman sam da izvršim glasanje B“, moguće na mnogo različitih glasačkih listića, sve dok ne pronađe onaj koji prihvata kvorum.
Odakle dolaze glasački listići za pripremu glasanja? Prvo, čvor emituje pripreme za glasanje za <1,C>, gdje je C složeni kandidat proizveden u fazi nominacije. Međutim, čak i nakon što pripreme za glasanje počnu, nominacije mogu dovesti do toga da dodatni kandidati postanu novi glasački listići. U međuvremenu, kolege mogu imati različite kandidate i mogu formirati blok za blokiranje koji prihvata "Spreman sam da izvršim glasanje B2", što će uvjeriti čvor da ga također prihvati. Konačno, postoji mehanizam timeouta koji generiše nove krugove federalnog glasanja na novim glasačkim listićima s većim brojem ako su trenutni glasački listići zaglavljeni.
Čim čvor pronađe glasački listić B za koji može potvrditi da je pripremljen, emituje novu poruku „Učini glasački listić B“. Ovo glasanje govori kolegama da čvor nikada neće odustati od B. U stvari, ako je B glasački listić , a zatim „Počini glasanje “ znači bezuslovni pristanak da se glasa za spremnost svakog glasačkog listića iz do <∞, s>. Ova dodatna vrijednost pomaže drugim kolegama da sustignu ravnopravnog urezivanja ako su još uvijek u ranijim fazama protokola.
U ovoj fazi vrijedi još jednom naglasiti da se radi o asinhronim protokolima. Samo zato što jedan čvor šalje glasove za urezivanje ne znači da to rade i njegovi vršnjaci. Neki od njih možda još uvijek glasaju o izjavama u pripremi za glasanje, drugi su možda već eksternalizirali značenje. SCP objašnjava kako bi čvor trebao obraditi svaki tip ravnopravne poruke bez obzira na njegovu fazu.
Ako se pojavi poruka "Najavio sam urezivanje » ne može biti primljena ili potvrđena, odnosno vjerovatnoća da će poruka biti prihvaćena ili potvrđena ili - ili, u svakom slučaju, bilo koji glasački listić sa vrijednošću C, a ne bilo koji drugi, pošto je čvor već obećao da nikada neće otkazati . Do trenutka kada čvor emituje glasove za urezivanje, biće C ili ništa, u zavisnosti od toga koliko daleko ide konsenzus. Međutim, to još uvijek nije dovoljno da čvor eksternalizira C. Neki vizantijski vršnjaci (koji čine manje od kvoruma, na osnovu naših sigurnosnih pretpostavki) mogu lagati čvoru. Prihvatanje i zatim potvrđivanje nekog glasačkog listića (ili raspona glasačkih listića) je ono što čvoru daje samopouzdanje da konačno eksternalizira C.
SCP glasanje putem federalnog glasanja. Nije prikazano: Tajmer se može uključiti u bilo koje vrijeme, povećavajući broj na glasačkom listiću (i eventualno stvarajući novi sastav dodatnih nominiranih kandidata).
I to je sve! Kada mreža postigne konsenzus, spremna je da to čini iznova i iznova. Na mreži Stellar plaćanja, ovo se događa otprilike svakih 5 sekundi: podvig koji zahtijeva i sigurnost i preživljavanje koje garantuje SCP.
SCP to može postići oslanjajući se na više krugova federalnog glasanja. Federativno glasanje je omogućeno konceptom kvorumskih isječaka: skupovi kolega kojima je svaki čvor odlučio vjerovati kao dio svog (subjektivnog) kvoruma. Ova konfiguracija znači da se konsenzus može postići čak iu mreži s otvorenim članstvom i vizantijskim obmanama.
Dalje čitanje
- Originalni SCP bijeli papir se može pronaći i nacrt specifikacija za njegovu implementaciju.
- Originalni autor SCP protokola, David Mazier, objašnjava to na pojednostavljen (ali ipak tehnički) način. .
- Možda ste bili iznenađeni što u ovom članku niste pronašli izraze “rudarstvo” ili “dokaz o radu”. SCP ne koristi ove metode, ali neki drugi konsenzusni algoritmi koriste. Zane Witherspoon je napisao pristupačno .
- jednostavna mreža koja postiže konsenzus u jednom punom krugu SCP-a.
- Za čitaoce zainteresovane za SCP implementacije: vidi , koju koristi Stellar platna mreža, ili , koji sam napisao radi boljeg razumijevanja SCP-a.
izvor: www.habr.com