Stellar konsenzusni protokol je prvi put opisan u David Mazier 2015. Ovo je "federalni bizantski sporazumni sustav" koji omogućuje decentraliziranim računalnim mrežama bez vođa da učinkovito postignu konsenzus o odluci. Platna mreža Stellar koristi Stellar Consensus Protocol (SCP) za održavanje dosljedne povijesti transakcija koja je vidljiva svim sudionicima.
Smatra se da je protokole konsenzusa teško razumjeti. SCP je jednostavniji od većine njih, ali još uvijek dijeli tu reputaciju - dijelom zbog pogrešne ideje da je "federativno glasovanje", koje je predmet prve polovice znanstvenog članka, SCP. Ali to nije istina! Ovo je samo važan sastavni dio koji se koristi za stvaranje druge polovice članka stvarni Stellar konsenzusni protokol.
U ovom ćemo članku ukratko objasniti što je to „sustav sporazuma“, što ga može učiniti „bizantskim“ i zašto bizantski sustav učiniti „federalnim“. Zatim ćemo objasniti proceduru federalnog glasovanja opisanu u članku o SCP-u, i na kraju ćemo objasniti sam SCP protokol.
Sporazumni sustavi
Sustav dogovora omogućuje grupi sudionika da postignu konsenzus o temi, kao što je što naručiti za ručak.
U Interstellaru smo implementirali vlastiti sustav dogovora o objedovanju: naručujemo ono što kaže naš voditelj operacija, John. Ovo je jednostavan i učinkovit sustav dogovora. Johnu svi vjerujemo i vjerujemo da će svaki dan pronaći nešto zanimljivo i hranjivo.
Ali što ako John zlorabi naše povjerenje? On može sam odlučiti da svi postanemo vegani. Za tjedan-dva vjerojatno ćemo ga svrgnuti i vlast predati Elizabeti. Ali odjednom zavoli avokado s inćunima i misli da bi svi trebali biti takvi. Moć kvari. Stoga je bolje pronaći neku demokratičniju metodu: neki način da se osigura da su različite preferencije uzete u obzir, a da se osigura pravovremen i nedvosmislen rezultat, tako da nitko ne naruči ručak, ili da pet ljudi naruči različite narudžbe, ili rasprava oteže se u večer.
Čini se da je rješenje jednostavno: glasajte! Ali ovo je pogrešan dojam. Tko će skupljati glasačke listiće i javljati rezultate? I zašto bi drugi vjerovali u ono što on govori? Možda možemo na prvi glasajte za lidera kojemu vjerujemo da će voditi glasovanje - ali tko će ga voditi prvi glasanjem? Što ako se ne možemo dogovoriti oko vođe? Ili što ako se dogovorimo, ali ovaj voditelj zapne na sastanku ili ode na bolovanje?
Slični se problemi javljaju u distribuiranim računalnim mrežama. Svi sudionici ili čvorovi moraju se složiti oko neke odluke, kao što je tko je na redu za ažuriranje zajedničke datoteke ili uklanjanje zadatka iz reda čekanja za obradu. U mreži kriptovalute, čvorovi opetovano moraju birati kako izgleda cijela priča između nekoliko mogućih verzija, koje se ponekad sukobljavaju. Ovaj ugovor o mreži daje jamstvo primatelju da je novčić (a) valjan (nije krivotvoren) i (b) da još nije potrošen drugdje. To također osigurava da će on moći trošiti novčiće u budućnosti jer će novi primatelj imati ista jamstva iz istih razloga.
Svaki konsenzusni sustav u distribuiranoj računalnoj mreži mora biti tolerantan na pogreške: mora proizvoditi dosljedne rezultate unatoč pogreškama kao što su spore veze, čvorovi koji ne reagiraju i netočan redoslijed poruka. bizantski Sustav dogovora dodatno je otporan na "bizantske" pogreške: čvorove koji daju lažne informacije, bilo zbog greške ili u namjernom pokušaju potkopavanja sustava ili stjecanja neke prednosti. "Bizantska" tolerancija na greške - sposobnost vjerovanja grupnoj odluci čak i kada neki članovi grupe možda lažu ili na drugi način ne slijede pravila donošenja odluka - naziva se koji su pokušali koordinirati napad. kod Anthonyja Stevensa.
Zamislimo vlasnicu kripto novčića Alice, koja mora birati između kupovine ukusnog sladoleda od Boba i otplate Carolinog duga. Možda Alice želi platiti obojici odjednom lažno trošeći isti novčić. Da bi to učinila, mora uvjeriti Bobovo računalo da novčić nikada nije isplaćen Carol i uvjeriti Carolino računalo da novčić nikada nije isplaćen Bobu. Bizantski sustav sporazuma čini to praktički nemogućim, koristeći oblik vladavine većine tzv kvorum. Čvor u takvoj mreži odbija prijeći na određenu verziju povijesti sve dok ne vidi da dovoljan broj ravnopravnih članova - kvorum - pristaje na takav prijelaz. Kada se to dogodi, oni će formirati glasački blok dovoljno velik da prisili preostale mrežne čvorove da se slože s njihovom odlukom. Alice može prisiliti neke čvorove da lažu u njezino ime, ali ako je mreža dovoljno velika, njezin će pokušaj biti nadjačan glasovima poštenih čvorova.
Koliko je čvorova potrebno za kvorum? Minimalno, većina, ili bolje rečeno, kvalificirana većina za borbu protiv pogrešaka i prijevara. Ali da biste izračunali većinu, morate znati ukupan broj sudionika. U uredu Interstellara ili na okružnim izborima te je brojke lako saznati. Ali ako je vaša grupa labavo definirana mreža u koju čvorovi mogu ulaziti i izlaziti po želji bez odobrenja središta, tada trebate federalni bizantski sustav dogovora sposoban za određivanje kvoruma ne iz unaprijed određenog popisa čvorova, već dinamički, iz stalno promjenjive i neizbježno nepotpune snimke čvorova u određenom trenutku u vremenu.
Možda se čini nemogućim stvoriti kvorum iz perspektive jednog čvora u golemoj mreži, ali je moguće. Takav kvorum čak može jamčiti rezultate decentraliziranog glasovanja. Bijela knjiga SCP-a pokazuje kako to učiniti pomoću procedure tzv federalnim glasovanjem.
Za nestrpljivo
Ostatak članka detaljnije opisuje federalno glasovanje i Stellar konsenzusni protokol. Ako vas detalji ne zanimaju, evo općeg pregleda procesa.
- Čvorovi provode krugove saveznog glasovanja o "kandidatima". Savezni krug glasovanja znači:
- Čvor glasa za neku izjavu, na primjer, "predlažem vrijednost V";
- Čvor sluša glasove peera dok ne pronađe onaj koji može "primati";
- Č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 zajedničkog glasovanja.
- Jednom kada čvor može potvrditi da je listić spreman, pokušava ga izvršiti kroz još više krugova zajedničkog glasovanja.
- Jednom kada čvor može potvrditi predaju 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 zajedničkog glasovanja, koji zajedno čine jedan SCP krug. Pogledajmo pobliže što se događa na svakom koraku.
Federativno glasovanje
Ujedinjeno glasovanje je postupak kojim se utvrđuje može li se mreža složiti oko prijedloga. U krugu glasovanja, svaki čvor mora odabrati jednu od potencijalno mnogo mogućih vrijednosti. To ne može učiniti osim ako nije siguran da drugi čvorovi u mreži neće odabrati drugačiji ishod. Kako bi bili sigurni u to, čvorovi razmjenjuju niz poruka naprijed-natrag tako da svatko potvrđenDa kvorum čvorova uzima ista stvar odluka. Ostatak ovog odjeljka objašnjava pojmove u ovoj rečenici i kako se odvija cijeli postupak.
Kvorumi i odsječci kvoruma
Počnimo s definiranjem kvoruma. Kao što smo gore spomenuli, u decentraliziranoj mreži s dinamičkim članstvom nemoguće je unaprijed znati broj čvorova, a time i koliko ih je potrebno za većinu. Federativno glasovanje rješava ovaj problem uvođenjem nove ideje smanjenje kvoruma (odsječak kvoruma): mali skup peerova kojima čvor vjeruje da će prenijeti informacije o statusu glasovanja ostatku mreže. Svaki čvor definira svoj vlastiti odsječak kvoruma (čiji de facto postaje član).
Formiranje kvoruma počinje rezanjem kvoruma. Za svaki čvor se dodaju njegovi izrezani čvorovi. Zatim se dodaju uvjeti odsječka ovi čvorovi i tako dalje. Kako nastavljate, postoji sve više čvorova koje ne možete dodati jer su već uključeni u odsječak. Kada više nema novih čvorova za dodavanje, proces se zaustavlja: formirali smo kvorum "tranzitivnim zatvaranjem" odsječka kvoruma početnog čvora.
Da biste pronašli kvorum iz određenog čvora...
... dodaj članove svog dijela...
...zatim dodajemo članove odsječaka ovih čvorova.
Nastavljamo dok ne preostane nijedan čvor za dodavanje.
Nema više čvorova za dodavanje. Ovo je kvorum.
Zapravo, svaki se čvor može pojaviti u više od jednog dijela. Za formiranje kvoruma odaberite samo jedan od dijelova i dodajte članove; zatim odaberite bilo koji dio za svakog od članova i dodajte članove to izrezati i tako dalje. To znači da je svaki čvor član mnogih mogućih kvoruma.
Odaberite samo jedan odsječak kvoruma u svakom koraku.
Jedan mogući kvorum. Ili alternativa...
...odaberi druge kriške...
…(kada je to moguće)…
... stvara još jedan kvorum.
Kako čvor zna u kojim se dijelovima nalaze drugi čvorovi? Na isti način kao i ostale informacije o drugim čvorovima: iz prijenosa koje svaki čvor emitira mreži kada se promijeni njegovo stanje glasanja. Svako emitiranje uključuje informacije o odsječcima čvora koji šalje. Bijela knjiga SCP-a ne specificira komunikacijski mehanizam. Implementacije obično koriste za zajamčeno emitiranje poruka u cijeloj mreži.
Podsjetimo se da je u nefederalnom bizantskom sustavu sporazuma kvorum definiran kao većina svih čvorova. Bizantski sporazumni sustav je osmišljen sa stajališta pitanja: koliko nepoštenih čvorova sustav može tolerirati? U sustavu od N čvorova dizajniranih da prežive f kvarova, čvor bi trebao moći napredovati primajući povratne informacije od N−f ravnopravnih budući da f od njih može biti u kvaru. No nakon što smo primili odgovor od N−f ravnopravnih, možemo pretpostaviti da su svi f ravnopravnih (od kojih čvor nije primio odgovor) zapravo pošteni. Stoga je f od N−f ravnopravnih (od kojih je primljen odgovor) zlonamjerno. Da bi čvorovi došli do istog konsenzusa, većina preostalih čvorova mora biti poštena, to jest, potrebno nam je da N−f bude veći od 2f ili N > 3f. Dakle, obično će sustav dizajniran da preživi f kvarova imati ukupno N=3f+1 čvorova i veličinu kvoruma od 2f+1. Nakon što prijedlog prijeđe prag kvoruma, ostatak mreže je uvjeren da svi konkurentski prijedlozi neće uspjeti. Ovako mreža konvergira do rezultata.
Ali u saveznom bizantskom sporazumnom sustavu, ne samo da ne može postojati većina (jer nitko ne zna ukupnu veličinu mreže), nego je koncept većine potpuno beskoristan! Ako je članstvo u sustavu otvoreno, tada netko može dobiti većinu jednostavnim izvođenjem takozvanog Sybil napada: uzastopnim pridruživanjem mreži preko više čvorova. Pa zašto se može nazvati tranzitivno zatvaranje presjeka kvorum, i kako može potisnuti konkurentske prijedloge?
Tehnički, nema šanse! Zamislite mrežu od šest čvorova, gdje su dvije trojke međusobno izolirane u dijelovima kvoruma. Prva podskupina 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 glasovanje (i za primjenu važnih teorema iz rada), mreža mora imati svojstvo tzv. sjecište kvoruma. U mreži s ovim svojstvom, bilo koja dva kvoruma koja se mogu konstruirati uvijek se preklapaju u barem jednom čvoru. Za određivanje prevladavajućeg raspoloženja mreže, ovo je jednako dobro kao i imati većinu. Intuitivno, to znači da ako se bilo koji kvorum složi s izjavom X, niti jedan drugi kvorum se ne može složiti ni s čim drugim, jer će nužno uključiti neki čvor iz prvog kvoruma koji je već glasao za X.
Ako postoji presjek kvoruma u mreži...
...onda možete sastaviti bilo koja dva kvoruma...
...uvijek će se presijecati.
(Naravno, čvorovi koji se preklapaju mogu se pokazati kao bizantski lažni ili na drugi način loši. U ovom slučaju, križanje kvoruma uopće ne pomaže mreži da se složi. Iz tog razloga, mnogi rezultati u SCP bijeloj knjizi temelje se na eksplicitne pretpostavke, kao što je ono što je ostalo u križanju mrežnog 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 križanje kvoruma moguće u mreži neovisnih čvorova. Ali postoje dva razloga zašto je to tako.
Prvi razlog je postojanje samog Interneta. Internet je savršen primjer mreže neovisnih čvorova s kvorumima koji se križaju. Većina čvorova na Internetu povezana je sa samo nekoliko drugih lokalnih čvorova, ali ti se mali skupovi dovoljno preklapaju da se svakom čvoru može pristupiti iz svakog drugog čvora duž neke rute.
Drugi razlog je specifičan za Stellar mrežu plaćanja (najčešća upotreba SCP-a). Svaka imovina na Stellar mreži ima izdavatelja, a Stellarove smjernice zahtijevaju da svaki izdavatelj odredi jedan ili više čvorova na mreži za obradu zahtjeva za otkup. U vašem je interesu izravno ili neizravno uključiti te čvorove u odsječke kvoruma za svako sredstvo koje vas zanima. Kvorumi za sve čvorove zainteresirane za određenu imovinu tada će se preklapati barem na tim otkupnim čvorovima. Čvorovi zainteresirani za višestruku imovinu uključit će sve čvorove otkupa dotičnih izdavatelja u svoje odsječke kvoruma i nastojat će objediniti 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 (na primjer, banke iz dolarske zone ponekad žele trgovati s bankama iz euro zone i bankama iz pezo zone, tako da su na istoj mreži, ali nijedna od njih je stalo do zasebne mreže djece koja prodaju baseball kartice).
Naravno, očekivanje križanje kvoruma nije jamčiti. Drugi bizantski sporazumni sustavi uvelike duguju svoju složenost jamstvu kvoruma. Važna inovacija SCP-a je da uklanja odgovornost za stvaranje kvoruma iz samog algoritma konsenzusa i dovodi je na razinu aplikacije. Prema tome, iako je federalno glasovanje dovoljno općenito da se može glasovati o bilo kojem pitanju, njegova pouzdanost zapravo kritično ovisi o širem značenju ovih značenja. Neke hipotetske upotrebe možda neće biti pogodne za stvaranje dobro povezanih mreža kao druge.
Glasovanje, prihvaćanje i potvrda
U krugu federalnog glasovanja, čvor po izboru počinje glasovati za neku vrijednost V. To znači emitiranje poruke mreži: "Ja sam čvor N, moji dijelovi kvoruma su Q i 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 emitiranju, svaki čvor vidi kako drugi glasuju. Nakon što čvor prikupi dovoljno ovih poruka, može pratiti odsječke kvoruma i pokušati pronaći kvorume. Ako vidi kvorum kolega koji također glasaju za V, može nastaviti posvajanje V i odašilje ovu novu poruku mreži: "Ja sam čvor N, moji odsječci kvoruma su Q i prihvaćam V." Prihvaćanje daje jače jamstvo od jednostavnog glasovanja. Kada čvor glasa za V, nikada ne može glasati za druge opcije. Ali ako čvor prihvati V, niti jedan čvor na mreži nikada neće prihvatiti drugu opciju (Teorem 8 u SCP whitepaperu to dokazuje).
Naravno, postoji velika vjerojatnost da neće odmah postojati kvorum čvorova koji se slažu s V. Ostali čvorovi mogu glasati za druge vrijednosti. Ali postoji još jedan način da se čvor pomakne s jednostavnog glasanja na prihvaćanje. N može prihvatiti drugu vrijednost za W, čak i ako nije glasao za to, pa čak i ako ne vidi kvorum za to. Da odlučite promijeniti svoj glas, samo pogledajte skup za blokiranje čvorovi koji su prihvatili W. Skup za blokiranje je jedan čvor iz svakog odsječaka kvoruma N. Kao što ime sugerira, može blok bilo koje drugo značenje. Ako svi čvorovi u takvom skupu prihvate W, tada (prema teoremu 8) nikada neće biti moguće formirati kvorum koji ima drugu vrijednost, pa je stoga također sigurno da N prihvati W.
Čvor N s tri odsječka kvoruma.
BDF je blokirajući skup za N: uključuje jedan čvor iz svakog odsječaka N.
BE je također blokirajući skup za N jer se E pojavljuje u dva dijela N.
Ali skup za blokiranje nije kvorum. Bilo bi prelako prevariti čvor N da prihvati željenu vrijednost kada bi bilo dovoljno hakirati samo jedan čvor u svakom od isječaka N. Stoga prihvaćanje vrijednosti nije kraj glasovanja. Umjesto toga, N mora potvrditi vrijednost, odnosno vidjeti kvorum čvorova koji je prihvaća. Ako dođe tako daleko, tada će, kao što SCP whitepaper dokazuje (u teoremu 11), ostatak mreže također na kraju potvrditi istu vrijednost, pa će N završiti federalno glasovanje s određenom vrijednošću kao rezultatom.
Federativno glasovanje.
Proces glasovanja, prihvaćanja i potvrđivanja čini jedan puni krug zajedničkog glasovanja. Protokol konsenzusa Stellar kombinira mnoge od ovih krugova kako bi stvorio potpuni sustav konsenzusa.
Stellar Consensus Protocol
Dva najvažnija svojstva konsenzusnog sustava su − sigurnosni и sposobnost preživljavanja. Algoritam konsenzusa je "siguran" ako nikada ne može dati različite rezultate različitim sudionicima (Bobova kopija povijesti nikada neće proturječiti Carol). “Livability” znači da će algoritam uvijek dati rezultat, odnosno da neće zapeti.
Opisani savezni postupak glasovanja sef 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. Sudionici mogu glasati o toliko različitih vrijednosti da ništa neće dosegnuti prag prihvaćanja. To znači da na federalnom glasovanju nema sposobnost preživljavanja.
Protokol konsenzusa Stellar koristi federalno glasovanje na način koji osigurava sigurnost i mogućnost preživljavanja. (SCP-ova jamstva sigurnosti i preživljavanja imaju teoretsku granicu. Dizajn odabire vrlo jaku sigurnosnu garanciju, žrtvujući malo ublažavanje preživljavanja, ali s obzirom na dovoljno vremena, vrlo je vjerojatno da će se postići konsenzus.) Ukratko, ideja je imati više saveznih glasova o više vrijednosti dok jedna od njih ne prođe kroz sve SCP faze glasanja opisane u nastavku.
Vrijednosti oko kojih 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 su prihvaćene ili potvrđene. Umjesto toga, federalno glasovanje odvija se prema izjave o tim vrijednostima.
Prvi krug saveznog glasovanja održava se faza nominacije (faza nominacije), na skupu izjava kao što je "Ja 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 glasovanja, gdje je cilj pronaći određenu bilten (odnosno spremnik za predloženu vrijednost) i kvorum koji može proglasiti počiniti za to (počiniti). Ako kvorum izvrši glasovanje, njegova se vrijednost prihvaća kao konsenzus. Ali prije nego što čvor može glasovati o predaji glasovanja, prvo mora potvrditi otkazivanje svi glasački listići s manjom protuvrijednošću. Ovi koraci—poništavanje glasačkih listića kako bi se pronašao onaj koji se može predati—uključuju više krugova zajedničkog glasovanja o višestrukim zahtjevima glasačkih listića.
Sljedeći odjeljci detaljnije opisuju imenovanje i glasovanje.
Imenovanje
Na početku faze nominacije, svaki čvor može spontano odabrati vrijednost za V i glasati za izjavu "Ja nominiram V." Cilj u ovoj fazi je potvrditi imenovanje neke vrijednosti putem zajedničkog glasovanja.
Možda dovoljno čvorova glasuje o dovoljno različitim prijedlozima da nijedna nominacija ne može doseći prag prihvaćanja. Stoga, osim što emitiraju vlastite glasove nominacija, čvorovi "reflektiraju" nominacije svojih kolega. Odjek znači da ako čvor glasa za nominaciju V, ali vidi poruku od susjeda koji glasuje za nominaciju W, sada će glasati i za V i za W. (Ne ponavljaju se svi glasovi ravnopravnih članova tijekom nominacije jer to može dovesti do eksplozije različiti nominirani. SCP uključuje mehanizam za reguliranje ovih glasova. Ukratko, postoji formula za određivanje "prioriteta" ravnopravnog računala sa stajališta čvora, a odražavaju se samo glasovi čvorova visokog prioriteta. Što je nominacija duža uzima, niži je prag, tako da čvor proširuje skup ravnopravnih računala čije će glasove odražavati. Formula prioriteta uključuje broj utora kao jedan od svojih ulaza, tako da ravnopravni uređaj visokog prioriteta za jedan utor može biti ravnopravni uređaj niskog prioriteta za drugi, i obrnuto).
Konceptualno, nominacija je paralelna, i V i W su odvojeni savezni glasovi, svaki zasebno sposoban postići prihvaćanje ili potvrdu. U praksi, poruke protokola SCP pakiraju te pojedinačne glasove zajedno.
Iako je glasovanje za V-ovu nominaciju obećanje da se nikada neće glasovati protiv V-ove nominacije, na razini aplikacije - u ovom slučaju SCP-a - određuje se što znači "protiv". SCP ne vidi izjavu koja je u suprotnosti s glasovanjem "Ja nominiram X", to jest, ne postoji poruka "Ja sam protiv nominiranja X", tako da čvor može glasati za nominaciju bilo koje vrijednosti. Mnoge od ovih nominacija neće ići nikamo, ali na kraju će čvor moći prihvatiti ili potvrditi jednu ili više vrijednosti. Nakon što je kandidat potvrđen, on postaje kandidat.
Nominacija SCP-a korištenjem federalnog glasovanja. Može postojati mnogo vrijednosti "B" koje su postavili ravnopravni korisnici i "odrazili" ih čvor.
Nominacije mogu rezultirati s više potvrđenih kandidata. Stoga SCP zahtijeva da aplikacijski sloj osigura neku metodu kombiniranja kandidata u jedan kompozitni (složeni). 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 sustavu glasovanja 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 ponovno postavljanje. Na primjer, raniji odabir po abecednom redu). U platnoj mreži Stellar, gdje se glasa o povijesti transakcija, spajanje dva predložena kandidata uključuje spajanje transakcija koje sadrže i posljednje od njihove dvije vremenske oznake.
SCP whitepaper dokazuje (teorem 12) da se do kraja faze proširenja mreža konvergira u jednu kompozitnu mrežu. Ali postoji problem: federalno glasovanje je asinkroni protokol (kao SCP). Drugim riječima, čvorovi nisu vremenski usklađeni, već samo porukama koje šalju. Sa stajališta čvora, nejasno je kada završeno faza produženja. I premda ć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 konačni.
Ali normalno je. Nominacija je samo priprema. Glavna stvar je ograničiti broj kandidata kako bi se postigao konsenzus, koji se događa u procesu kandidiranje za ured (glasovanje).
Trčanje
Bilten je par , gdje je brojač cijeli broj koji počinje s 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 održavanjem potencijalno mnogo zajedničkih glasova na izjavama glasačkog listića. Brojači na glasačkim listićima prate izvršene pokušaje, a glasački listići s većim brojem glasova imaju prednost pred glasačkim listićima s manjim brojem glasova. Ako je bilten zapne, počinje novo glasovanje, sada na listiću .
Važno je razlikovati smisao (na primjer, kakav bi trebao biti redoslijed ručka: pizza ili salate), bilteni (par protuvrijednosti) i izjave o glasačkim listićima. SCP krug uključuje nekoliko krugova federalnog glasovanja, posebno o sljedećim izjavama:
- "Spreman sam za glasovanje B" i
- "Objavljujem glasovanje B"
Iz perspektive određenog čvora, konsenzus je postignut kada pronađe glasački listić B za koji može potvrditi (tj. pronaći kvorum koji prihvaća) izjavu "Predajem glasački listić B." Od ovog trenutka nadalje, sigurno je djelovati prema vrijednosti navedenoj u B - na primjer, staviti ovu narudžbu za ručak. To se zove eksternalizacija značenja. Nakon što se potvrdi prihvaćanje glasačkog listića, čvor može biti siguran da je bilo koji drugi čvor eksternalizirao istu vrijednost ili da će to učiniti u budućnosti.
Iako se mnoga ujedinjena glasovanja konceptualno provode na zahtjevima 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 stoga promiče stanje mnogih federalnih glasova odjednom, na primjer: "Prihvaćam commit glasačke listiće u rasponu od prije "
Što znače pojmovi "pripremljen" i "počiniti"?
Čvor glasa za predaju glasovanja kada je siguran da drugi čvorovi neće predati glasačke listiće s različitim vrijednostima. Uvjeriti se u to je svrha pripreme prijave. Glasanje koje kaže "Spreman sam dati glasački listić B" je obećanje da nikada neće dati glasački listić manji od B, tj. s manjim brojem glasova (SCP zahtijeva da vrijednosti u glasačkim listićima budu u određenom redoslijedu. Dakle, bilten manje , ako je N1
Zašto "Spreman sam dati glasački listić B" znači "Obećavam da nikada neću dati glasački listić manji od B"? Budući da SCP definira prekid kao suprotnost predaji. Glasovanje za pripremu glasačkog listića također uključuje glasanje za diskvalificiranje nekih drugih glasačkih listića, i, kao što smo ranije rekli, glasanje za jednu stvar je obećanje da se nikada neće glasati protiv nje.
Prije emitiranja predaje, čvor prvo mora pronaći bilten za koji može potvrditi da je pripremljen. Drugim riječima, provodi udruženo glasovanje o temi "Spreman sam dati glasački listić B", moguće na više različitih glasačkih listića, dok ne pronađe onaj koji prihvaća kvorum.
Odakle dolaze glasački listići za pripremu glasovanja? Prvo, čvor emitira pripreme za glasovanje za <1,C>, gdje je C složeni kandidat proizveden u fazi nominacije. Međutim, čak i nakon što počnu pripreme za glasovanje, nominacije mogu dovesti do toga da dodatni kandidati postanu novi glasački listići. U međuvremenu, vršnjaci mogu imati različite kandidate i mogu formirati skup za blokiranje koji prihvaća "Spreman sam predati B2 glasovanje", što će uvjeriti čvor da ga također prihvati. Konačno, postoji mehanizam vremenskog ograničenja koji generira nove krugove zajedničkog glasovanja na novim glasačkim listićima s većim brojem glasova ako su trenutni glasački listići zapeli.
Čim čvor pronađe glasački listić B koji može potvrditi da je pripremljen, emitira novu poruku "Potvrdi glasački listić B." Ovo glasanje govori kolegama da čvor nikada neće odustati od B. Zapravo, ako je B glasački listić , a zatim "Izvrši glasanje “ znači bezuvjetni pristanak na glasovanje za spremnost svakog glasačkog listića iz na <∞, s>. Ova dodatna vrijednost pomaže drugim peerovima da sustignu commit peer ako su još uvijek u ranijim fazama protokola.
U ovoj fazi vrijedi još jednom naglasiti da se radi o asinkronim protokolima. Samo zato što jedan čvor šalje pozitivne glasove za commit ne znači da to rade i njegovi vršnjaci. Neki od njih možda još uvijek glasaju o izjavama u pripremi za glasovanje, drugi su možda već eksternalizirali značenje. SCP objašnjava kako bi čvor trebao obraditi svaku vrstu ravnopravne poruke bez obzira na njezinu fazu.
Ako se pojavi poruka "Najavio sam obvezu » ne može biti primljena ili potvrđena, odnosno vjerojatnost da će poruka biti prihvaćena ili potvrđena ili - ili, u svakom slučaju, bilo koji listić s vrijednošću C, a ne bilo koji drugi, budući da je čvor već obećao da nikada neće poništiti . U trenutku kada čvor emitira glasove za commit, bit će C ili ništa, ovisno o tome koliko daleko ide konsenzus. Međutim, to još nije dovoljno da čvor eksternalizira C. Neki bizantski vršnjaci (koji čine manje od kvoruma, na temelju naših sigurnosnih pretpostavki) mogu lagati čvoru. Prihvaćanje i potom potvrđivanje nekog glasačkog listića (ili raspona glasačkih listića) je ono što čvoru daje povjerenje da konačno eksternalizira C.
SCP glasovanje putem federalnog glasovanja. Nije prikazano: mjerač vremena može se uključiti u bilo kojem trenutku, povećavajući broj na glasačkom listiću (i moguće stvarajući novu kombinaciju dodatnih nominiranih kandidata).
I to je sve! Jednom kada mreža postigne konsenzus, spremna je to činiti opet i opet. Na mreži plaćanja Stellar to se događa otprilike jednom svakih 5 sekundi: pothvat koji zahtijeva i sigurnost i sposobnost preživljavanja koje jamči SCP.
SCP to može postići oslanjajući se na više krugova zajedničkog glasovanja. Federativno glasovanje omogućeno je konceptom odsječaka kvoruma: skupovima ravnopravnih čvorova kojima je svaki čvor odlučio vjerovati kao dijelu svog (subjektivnog) kvoruma. Ova konfiguracija znači da se konsenzus može postići čak iu mreži s otvorenim članstvom i bizantskim prijevarama.
Daljnje čitanje
- Izvorni bijeli papir SCP-a može se pronaći I nacrt specifikacija za njegovu provedbu.
- Izvorni autor SCP protokola, David Mazier, objašnjava ga na pojednostavljen (ali još uvijek tehnički) način. .
- Možda ste se iznenadili što u ovom članku niste pronašli pojmove "rudarenje" ili "dokaz rada". 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 čitatelje zainteresirane za SCP implementacije: vidi , koju koristi mreža plaćanja Stellar, ili , koji sam napisao za bolje razumijevanje SCP-a.
Izvor: www.habr.com