Protokolli i konsensusit Stellar për herë të parë u përshkrua në nga David Mazier në vitin 2015. Ky është një "sistem federativ i marrëveshjes bizantine", i cili lejon rrjetet e kompjuterëve të decentralizuar pa liderë të arrijnë në mënyrë efektive konsensus mbi një vendim të caktuar. Rrjeti paguese Stellar përdor Protokollin Stellar të Konsensusit (SCP) për të ruajtur një histori të konsoliduar të transaksioneve, të cilën e shohin të gjithë pjesëmarrësit.
Mendohet se protokollet e konsensusit janë të vështira për t'u kuptuar. SCP është më i thjeshtë se shumica e tyre, por përsëri ndan këtë reputacion — pjesërisht për shkak të idesë së gabuar se "votimi federal", i cili është temë e pjesës së parë të artikullit shkencor, është SCP. Por kjo nuk është e vërtetë! Kjo është thjesht një bllok ndihmës i rëndësishëm, i cili në pjesën e dytë të artikullit përdoret për të ndërtuar protokollin e vërtetë të konsensusit Stellar.
Në këtë artikull, do të shpjegojmë shkurtimisht se çfarë është "sistemi i marrëveshjeve", çfarë mund ta bëjë atë "bizantin", dhe pse duhet ta bëjmë sistemin bizantin "federativ". Pastaj do të shpjegojmë procedurën federative të votimit, siç përshkruhet në artikullin për SCP, dhe, në fund, do të shpjegojmë vetë protokollin SCP.
Sistemet e marrëveshjeve
Sistemi i marrëveshjeve lejon një grup pjesëmarrësish të arrijnë konsensus mbi një temë të caktuar, për shembull, çfarë të porosisin për drekë.
Ne në kompaninë Interstellar kemi implementuar sistemin tonë të marrëveshjeve për drekë: porosisim atë që thotë menaxheri ynë operativ, John. Ky është një sistem i thjeshtë dhe efektiv i marrëveshjes. Ne të gjithë i besojmë John-it dhe besojmë se ai do të gjejë diçka interesante dhe ushqyese çdo ditë.
Por çfarë do ndodhte nëse John abuzon me besimin tonë? Ai mund të vendosë vetë se ne të gjithë duhet të bëhemi veganë. Pas një jave apo dy, ndoshta do ta heqim nga pozita dhe do t'ia japim fuqinë Elizabeth. Por ndoshta ajo e do avocado me ançoa dhe mendon se të gjithë duhet të bëhen të tillë. Fuqia korrupton. Prandaj, është më mirë të gjejmë një metodë më demokratike: një mënyrë për t'u siguruar që preferencat e ndryshme të merren parasysh, ndërkohë që sigurohet një rezultat të qartë dhe të shpejtë, për të mos ndodhur që askush të mos porosisë drekë, ose pesë persona të vendosin porosi të ndryshme, ose bisedat të zgjaten deri në mbrëmje.
Duket se zgjidhja është e thjeshtë: të organizojmë një votim! Por ky është një iluzion i rremë. Kush do t'i mbledhë fletët e votimit dhe do t'i raportojë rezultatet? Dhe pse të tjerët duhet të besojnë atë që ai thotë? Ndoshta mund të votojmë fillimisht për një lider, të cilit i besojmë të drejtojë votimin — por kush do ta udhëheqë këtë i pari votim? Çfarë ndodh nëse nuk arrijmë të biem dakord për një lider? Ose nëse kemi një marrëveshje, por ky lider ngec në një takim ose shkon në spital?
Probleme të ngjashme ndodhin në rrjetet komputerike të shpërndara. Të gjithë pjesëmarrësit ose nyjet duhet të bien dakord për një vendim të caktuar, për shembull, se kujt i takon për të azhurnuar një skedar të përbashkët ose për të marrë një detyrë nga lista e pritjes. Në një rrjet kriptovalutash, nyjet shpesh duhet të zgjedhin se si duket historia e plotë, nga disa versione të mundshme, që ndonjëherë përplasen. Ky konsensus në rrjet ofron garancinë për marrësin, se monedha është (a) e vlefshme (jo e falsifikuar) dhe (b) ende nuk është shpenzuar diku tjetër. Kjo gjithashtu garanton se ai mund të shpenzojë monedhat në të ardhmen, sepse marrësi i ri do të ketë të njëjtat garanci për të njëjtat arsye.
Çdo sistem pajtimi në një rrjet kompjuterik të shpërndarë duhet të jetë i qëndrueshëm ndaj dështimeve: ai duhet të japë rezultate të qëndrueshme, pavarësisht nga dështimet, të tilla si linjat e ngadalta të komunikimit, nyjet që nuk përgjigjen dhe rendi i gabuar i mesazheve. Sistemi bizantin i marrëveshjeve është gjithashtu i qëndrueshëm ndaj "gabimeve bizantine": nyjeve që japin informacione të rreme, qoftë për shkak të gabimit ose në përpjekje të qëllimshme për të minuar sistemin ose për të fituar ndonjë avantazh. Qëndrueshmëria "bizantine" - aftësia për të besuar vendimin e grupit, edhe kur disa anëtarë të grupit mund të gënjejnë ose ndryshe të mos ndjekin rregullat e vendimmarrjes - e mori emrin nga ngjarja e gjeneralëve të Perandorisë Bizantine , që përpiqeshin të koordinonin një sulm. është nga Anthony Stevens.
Le të shqyrtojmë pronarin e kriptomonedhës, Alisa, e cila duhet të zgjedhë mes blerjes së një akulli të shijshëm nga Bobi dhe shlyerjes së borxhit të Karolës. Ndoshta Alisa dëshiron të paguajë të dyve në të njëjtën kohë, duke shpenzuar një monedhë të njëjtë. Për këtë, ajo duhet të bindë komputerin e Bobit se monedha nuk është paguar kurrë Karolës dhe të bindë komputerin e Karolës se monedha nuk është paguar kurrë Bobit. Një sistem bizantin konsensusi e bën këtë praktikisht të pamundur, duke përdorur një formë rregulli të shumicës, të njohur si kvorum. Një nyje në një rrjet të tillë refuzon të kalojë në një version të caktuar të historisë derisa të mos shohë se një numër i mjaftueshëm nyjesh peer-to-peer — kvorumi — pajtohen me një kalim të tillë. Sa më shpejt të ndodhë kjo, ata formojnë një bllok mjaft të madh zgjedhor për të detyruar nyjet e tjera të rrjetit të pranojnë vendimin e tyre. Alisa mund të bëjë që disa nyje të gënjejnë në emër të saj, por nëse rrjeti është mjaft i madh, përpjekja e saj do të shtypet nga zërat e nyjeve të ndershme.
Sa nyje nevojiten për një kvorum? Të paktën, shumicë, dhe saktësisht, një shumicë kuorumi për të luftuar gabimet dhe mashtrimet. Por për të llogaritur shumicën, duhet të dihet numri total i pjesëmarrësve. Në zyrën Interstellar ose në zgjedhjet lokale, këto numra janë lehtësisht të njohur. Por nëse grupi juaj është një rrjet i dobët të përcaktuar, në të cilin nyjet mund të hyjnë dhe dalin sipas dëshirës, pa u pajtuar me një qendër, atëherë nevojitet një sistem të konsensusit bizantin, i cili është në gjendje të përcaktojë kvorumet jo nga një listë të përcaktuar paraprakisht të nyjeve, por dinamikisht, nga një pamje që ndryshon gjithmonë dhe është patjetër e paplotë e nyjeve në një moment të caktuar.
Mund të duket e pamundur të krijosh një kvorum nga këndvështrimi i një nyje në një rrjet të gjerë, por kjo është e mundur. Një kvorum i tillë mund të garantojë rezultate të votimit të decentralizuar. Dokumenti teknik SCP tregon se si të bëhet kjo përmes një procedure të quajtur votimi federativ..
Për ata që janë të padurueshëm
Pjesa tjetër e artikullit shqipton më në detaje votimin federativ dhe protokollin e konsensusit Stellar. Nëse nuk jeni të interesuar për detajet, ja një përmbledhje e përgjithshme e procesit.
- Nyjet zhvillojnë raunde votimi federativ mbi "nominat". Një raund votimi federativ do të thotë:
- Nyja voton për një propozim, për shembull, "Unë propozoj vlerën V";
- Nyja dëgjon zërat e peerëve derisa të gjejë atë që mund të "pranojë";
- Nyja kërkon "kvorumin" për këtë propozim. Kvorumi "konfirmon" nominatin.
- Sa më shpejt që nyja mund të konfirmojë një ose më shumë njoftime, ajo përpiqet të "përgatitë" "fletën e votimit" përmes disa raundesh votimi federativ.
- Sa më shpejt që nyja është në gjendje të verifikojë gatishmërinë e fletës së votimit, ajo përpiqet ta angazhojë atë përmes akoma më shumë raundesh votimi federativ.
- Sa më shpejt që nyja mund të konfirmojë angazhimin e fletës së votimit, ajo mund të "eksternalizojë" vlerën e kësaj fletë votimi, duke e përdorur atë si një rezultat konsensusi.
Këto hapa përfshijnë disa raunde votimi federativ, që në tërsinë e tyre përbëjnë një raund SCP. Le të shohim më shumë në detaje se çfarë ndodh në çdo hap.
Votimi Federativ
Votimi federativ është një procedurë për të përcaktuar nëse rrjeti mund të pajtohet me një propozim. Në një raund votimi, secila nyje duhet të zgjedhë një nga shumë vlera potencialisht të mundshme. Ajo nuk mund ta bëjë këtë derisa të jetë e sigurt se nyjet e tjera në rrjet nuk do të zgjedhin një rezultat tjetër. Për të qenë të sigurt për këtë, nyjet shkëmbejnë një sasi të madhe mesazhesh për t'u kthyer, që çdo konfirmoi, që kvorum nyje pranon të zgjedhë të njëjtën zgjidhje. Pjesa tjetër e këtij seksioni shpjegon termat në këtë propozim dhe si ndodh e gjithë procedura.
Kvorumet dhe pjesët e kvorumeve
Le të fillojmë me definimin e kvorumit. Siç e kemi diskutuar më sipër, në një rrjet të decentralizuar me anëtarësim dinamik, është e pamundur të dihet paraprakisht numri i nyjeve dhe, rrjedhimisht, sa nevojiten për shumicën. Votimi federativ zgjidh këtë problem duke paraqitur një ide të re pjesës së kvorumit (quorum slice): një grup i vogël nyjesh peer-to-peer, të cilave një nyje u beson për të transmetuar informacionin mbi gjendjen e votimit në pjesën tjetër të rrjetit. Çdo nyje përcakton pjesën e saj të kvorumit (anëtari i saj është nominalisht).
Formimi i kvorumit fillon me pjesën e kvorumit. Për çdo nyje, nyjet e saj të pjesës së kvorumit shtohen. Pastaj, anëtarët e pjesëve të këtyre nyjeve e kështu me radhë. Me vazhdimin e procesit, po zbulohen gjithnjë e më shumë nyje që nuk mund t'i shtoni, sepse ato janë përfshirë tashmë në prerje. Kur nuk ka më nyje të reja për t'u shtuar, procesi ndalet: ne kemi formuar një kuorum përmes "mbylljes transitive" të prerjes së kuorumit të nyjës fillestare.
Për të gjetur një kuorum nga një nyje e dhënë...
... shtojmë anëtarët e prerjes së saj...
... pastaj shtojmë anëtarët e prerjeve të këtyre nyjeve.
Vazhdoni, derisa të mos mbeten më nyje për t'u shtuar.
Nuk ka mbetur asnjë nyje për t'u shtuar. Ky është kuorumi.
Në të vërtetë, çdo nyje mund të jetë anëtar i më shumë se një prerje. Për të formuar një kuorum, zgjidhni vetëm një nga prerjet dhe shtoni anëtarët; pastaj zgjidhni çfarëdo prerje për secilin nga anëtarët dhe shtoni anëtarët e prerjeve dhe kështu me radhë. Kjo do të thotë se çdo nyje është anëtar i një gruaje të mundshme kuorumi. ky Zgjidhni vetëm një prerje kuorumi në çdo hap.
Një kuorum i mundshëm. Ose një alternativë tjetër...
... zgjedhim prerje të tjera...
... (kur është e mundur)...
... krijon një kuorum tjetër.
Si e di një nyje në cilat prerje janë nyjet e tjera? Ashtu si me informacionin tjetër për nyjet e tjera: nga transmetimet që çdo nyje transmeton në rrjet, kur ndryshon gjendja e saj të votimit. Çdo transmetim përfshin informacion rreth prerjeve të nyjës dërguese. Në dokumentin teknik SCP nuk është specifikuar mekanizmi i komunikimit. Zbatimet zakonisht përdorin
protokollin gossip Të kujtojmë se në sistemin e marrëveshjeve bizantine jo-federative, kuorumi përcaktohet si shumica e të gjitha nyjeve. Sistemi i marrëveshjeve bizantine është zhvilluar me perspektivën se: sa nyje të pabesa mund të mbajë sistemi? Në një sistem me N nyje, të dizajnuar për të mbijetuar me f dështime (mashtresa), një nyje duhet të jetë në gjendje të arrijë përparim duke marrë një përgjigje nga N−f peer, sepse f prej tyre mund të mos funksionojnë. Por duke marrë një përgjigje nga N−f peer, mund të supozohet se të gjitha f peer (nga të cilat nyja nuk ka marrë një përgjigje) në të vërtetë janë të ndershëm. Kështu, të dëmshme janë f nga N−f peer (nga të cilat është marrë përgjigja). Në mënyrë që nyjet të arrijnë një konsensus, shumica e nyjeve të tjera duhet të jenë të ndershëm, që do të thotë se na nevojitet që N−f të jetë më e madhe se 2f ose N > 3f. Prandaj, zakonisht një sistem i projektuar për të mbijetuar me f dështime do të ketë gjithsej N=3f+1 nyje dhe madhësinë e kuorumit 2f+1. Sa herë që propozimi kalon pragun e kuorumit, anëtarët e tjerë të rrjetit janë të bindur se çdo propozim konkurrues do të dështojë. Kështu, rrjeti arrin në një rezultat.
Por në sistemin e marrëveshjeve bizantine federative, jo vetëm që nuk mund të ketë shumicë (sepse askush nuk e di madhësinë e përgjithshme të rrjetit), por koncepti i shumicës është krejtësisht i padobishëm! Nëse anëtarësimi në sistem është i hapur, dikush mund të fitojë shumicën thjesht duke bërë një sulm të tjerë: duke u bashkuar përsëri në rrjet përmes disa nyjeve. Pse, pra, mbyllja transpitive e prerjes mund të quhet
, dhe si është në gjendje të shtypë propozimet konkurruese? kvorumTeknisht, ashtu si askund! Imagjinoni një rrjet me gjashtë nyje, ku dy grupe janë të izoluar në prerjet e kuorumit nga njëra-tjetra. Grupi i parë mund të marrë një vendim, për të cilin nëna kurrë nuk do ta dëgjojë, dhe anasjelltas. Për këtë rrjet, nuk ka asnjë mënyrë për të arritur konsensus (përveç rastësisht).
Prandaj, SCP kërkon që për votimin federativ (dhe për përdorimin e teoremave të rëndësishme të artikullit) rrjeti duhet të ketë një pronë të quajtur
kryqëzimi i kuorumit . Në një rrjet me këtë pronë, çdo dy kuora që mund të ndërtohen gjithmonë do të mbivendosen në të paktën një nyje. Për të përcaktuar opinionin dominant të rrjetit, kjo është sa e mirë sa të kesh shumicën. Intuitivisht, kjo do të thotë se nëse ndonjë kuorum bie dakord me deklaratën X, asnjë kuorum tjetër nuk mund të bie dakord me ndonjë gjë tjetër, sepse ai do të përfshijë patjetër një nyje nga kuorumi i parë që ka votuar për X.Nëse në rrjet ka kryqëzim kuorumi...
... atëherë çdo dy kuora që mund të ndërtohen...
... gjithmonë do të mbivendosen.
(Sigurisht, nyjet e mbivendosura mund të rezultojnë të jenë bizantin-pabesa ose të këqija në aspekte të tjera. Në këtë rast, kryqëzimi i kuorumit nuk ndihmon rrjetin të arrijë pajtueshmërinë në përgjithësi. Për këtë arsye, shumë rezultate në dokumentin teknik SCP bazohen në supozime të shprehura qartë, si ajo që mbetet një kryqëzim kuorumi
edhe pas largimit të nyjeve të këqija. edhe pas fshirjes së nyjeve të këqija. Për thjeshtësi, le ta lëmë këto supozime të nënkuptuara në pjesën tjetër të artikullit).
Mund të duket e pamundur të pritet që në një rrjet me nyje të pavarura të ketë një përputhje të kuorumit. Por ka dy arsye pse kjo është e vërtetë.
Arsyeja e parë është ekzistenca e vetë internetit. Interneti është një shembull ideal i një rrjeti me nyje të pavarura që kanë një përputhje të kuorumit. Shumica e nyjeve në internet lidhën vetëm me disa nyje lokale të tjera, por këto grupe të vogla mbulojnë mjaftueshëm që çdo nyje të jetë e aksesueshme nga çdo nyje tjetër përmes një rruge ose një tjetër.
Arsyeja e dytë është specifike për rrjetin e pagesave Stellar (përdorimi më i zakonshëm i SCP). Çdo aktivi në rrjetin Stellar ka një emisuer, dhe rekomandimet Stellar kërkojnë që çdo emisuer të emërojë një ose disa nyje në rrjet për të përpunuar kërkesat për shpërblim. Është në interesin tuaj të përfshini drejtpërdrejt ose tërthor këto nyje në grupet e kuorumit për çdo aktiv që ju intereson. Pastaj, kuorumet për të gjitha nyjet që janë të interesuara për këtë aktiv do të mbulojnë së paku në këto nyje shpërblimi. Nyjet që janë të interesuara në disa aktive do të përfshijnë në grupet e kuorumit të tyre të gjitha nyjet shpërblimi të emisuerëve përkatës dhe ato do të kërkojnë të bashkojnë të gjitha aktivet së bashku. Për më tepër, çdo aktive që nuk është e lidhur kështu me të tjerët në rrjet dhe nuk duhet të lidhen — është menduar që për këtë rrjet të mos kishte përputhje të kuorumit (për shembull, bankat e zonës dollarike ndonjëherë dëshirojnë të tregtojnë me bankat e zonës euro dhe bankat e zonës peso, prandaj ato janë në të njëjtin rrjet, por asnjëra nga ato nuk është e interesuar për një rrjet të veçantë të fëmijëve që tregtojnë karta bejsbolli).
Sigurisht, prisni përputhjen e kuorumit nuk është garanci. Sistemat e tjera bizantine të marrëveshjeve pezullimin e përgjegjësisë për krijimin e kuorumëve nga algoritmi konsensual dhe e transferon atë në nivelin e aplikacionit. Kështu, megjithëse votimi federativ është mjaft i zakonshëm për votime mbi çdo çështje, në të vërtetë besueshmëria e tij varet kritikisht nga kuptimi më i gjerë i këtyre vlerave. Disa lloje hipotetike përdorimi mund të mos jenë aq të përshtatshme për krijimin e rrjeteve të mirë të lidhura si të tjerat.
Votimi, miratimi dhe konfirmimi
Në raundin e votimit federativ, nodi opcionalisht fillon të votojë për një vlerë të caktuar V. Kjo do të thotë transmetimi në rrjet të mesazhit: «Unë jam nodi N, prerjet e mia të kuorumëve Q, dhe unë votoj për V». Kur nodi voton në këtë mënyrë, ai premton se nuk ka votuar ndonjëherë kundër V dhe nuk do ta bëjë asnjëherë.
Në transmetimet nga nodet e barabarta, çdo nod shikon si votojnë të tjerët. Sapo nodi të mbledhë mjaft mesazhe të tilla, ai mund të ndjekë prerjet e kuorumëve dhe të përpiqet të gjejë kuorumet. Nëse ai sheh një kuorum të peers që gjithashtu votojnë për V, atëherë mund të kalojë në miratim V dhe të transmetojë këtë mesazh të ri në rrjet: «Unë jam nodi N, prerjet e mia të kuorumit Q, dhe unë miratoj V». Miratimi ofron një garanci më të fortë se thjesht votimi. Kur nodi voton për V, ai kurrë nuk mund të votojë për mundësi të tjera. Por nëse nodi miraton V, asnjë nod në Rrjet nuk do të miratojë kurrë një mundësi tjetër (teorema 8 në dokumentin teknik SCP e provon këtë).
Sigurisht, ka një mundësi të lartë që menjëherë nuk do të gjendet një kuorum nodesh që do të pajtohen me V. Nodet e tjera mund të votojnë për vlera të tjera. Por për nodin ka një mënyrë tjetër për të kaluar nga votimi i thjeshtë në miratim. N mund të miratojë një vlerë tjetër W, madje edhe nëse nuk ka votuar për të, dhe madje edhe nëse nuk sheh një kuorum për të. Për të vendosur të ndryshojë votën e tij, është e mjaftueshme të shohë një grup bllokues nodesh që miratuan W. Grupi bllokues është nga një nod nga çdo prekje e kuorumëve N. Siç e sugjeron emri, ai është në gjendje të bllokojë ndonjë vlerë tjetër. Nëse të gjitha nyjat në një grup të tillë pranojnë W, atëherë (sipas teoremës 8) nuk do të jetë kurrë e mundur të formohet një kuorum që pranon një vlerë tjetër, dhe prandaj për N gjithashtu është në mënyrë të sigurt të pranohet W.
Nyja N me tre prerje kuorumesh.
B-D-F është një grup bllokues për N: ai përfshin nga një nyjë nga secila prej prerjeve të N.
B-E gjithashtu është një grup bllokues për N, sepse E shfaqet në dy prerje të N.
Por megjithatë, shumëzimi bllokues nuk është një kuorum. Do të ishte shumë e lehtë të mashtrohej nyja N që të pranonte një vlerë të caktuar, nëse mjafton të thyhen vetëm një nyje në secilin nga segmentet N. Prandaj, pranim i vlerës nuk është fundi i votimit. Përkundrazi, N duhet të konfirmojë vlerën, dmth. të shohë një kuorum nyjesh që e pranojnë atë. Nëse arrin deri këtu, siç tregon dokumenti teknik SCP (në teoremën 11), pjesa tjetër e rrjetit gjithashtu do ta konfirmojë të njëjtën vlerë në fund, prandaj N do të përfundojë votimin federativ me një vlerë të caktuar si rezultat.
Votimi federativ.
Procesi i votimit, pranimit dhe konfirmimit përbën një raund të plotë të votimit federativ. Protokolli i konsensusit Stellar bashkon shumë të tillë për të krijuar një sistem konsensusi të plotë.
Protokolli i konsensusit Stellar
Dy pronat më të rëndësishme të sistemit të konsensusit janë siguria dhe qëndrueshmëria. Algoritmi i konsensusit është "i sigurt", nëse nuk mund të japë kurrë rezultate të ndryshme për pjesëmarrës të ndryshëm (një kopje e historisë së Bobit nuk do të jetë kurrë në kontradiktë me atë të Carolit). "Qëndrueshmëria" do të thotë që algoritmi gjithmonë do të japë një rezultat, dmth. nuk do të ngecë.
Procedura e përshkruar e votimit federativ është e sigurt në kuptimin që nëse një nyje konfirmon vlerën V, asnjë nyje tjetër nuk do të konfirmojë një vlerë tjetër. Por "nuk do të konfirmojë një vlerë tjetër" nuk do të thotë që ajo do të konfirmojë gjithmonë diçka. Pjesëmarrësit mund të votojnë për një numër kaq të madh vlerash të ndryshme saqë asnjë vlerë nuk arrin pragun e pranimit. Kjo do të thotë se në votimin federativ mungon qëndrueshmëria.
Protokolli i konsensusit Stellar përdor votimin federativ në një mënyrë që garanton si sigurinë ashtu edhe qëndrueshmërinë. (Garancitë e sigurisë dhe qëndrueshmërisë SCP kanë një kufi teorik. Konstrukti zgjat një garanci shumë të fortë të sigurisë, duke sakrifikuar një dobësim të vogël të qëndrueshmërisë, por duke marrë parasysh një periudhë të mjaftueshme, konsensusi me probabilitet të lartë do të arrihet). Në dy fjalë, ideja është të zhvillohen disa votime federative për disa vlera, derisa njëra prej tyre të kalojë plotësisht të gjitha fazat e votimit SCP të përshkruara më poshtë.
Vlerat për të cilat SCP synon konsensusin mund të jenë historia e transaksioneve ose një porosi për drekë, ose diçka tjetër, por është e rëndësishme të theksohet se këto nuk janë vlerat që pranohet ose konfirmohet. Në vend të kësaj, votimi federativ ndodh për deklarata për këto vlera.
Raundet e para të votimit federativ ndodhin në fazën e nominimit (nomination phase), në një grup deklaratash të tipit "Unë nominova V", ndoshta për shumë vlera të ndryshme V. Qëllimi i nominimit është të gjejmë një ose më shumë deklarata që kalojnë nëpër pranimin dhe konfirmimin.
Pas gjetjes së kandidatëve të konfirmueshëm, SCP kalon në fazën e votimit, ku qëllimi është të gjejë një fletë votimi (dmth. një enë për vlerën e propozuar) dhe një kuorum, i cili mund të shpallë komit për të (commit). Nëse kuorumi e bën angazhimin e fletës së votimit, vlera e saj pranohet si konsensus. Por para se një nyje të mund të votojë për angazhimin e fletës së votimit, ajo duhet së pari të konfirmojë anulimin e të gjitha fletëve të votimit me një vlerë numruese më të vogël. Këto hapa - anulimi i fletëve të votimit për të gjetur atë, për të cilën mund të konfirmohet angazhimi - përfshijnë disa raunde votimi federativ për disa deklarata të fletëve të votimit.
Në seksionet në vijim, do të jepet një përshkrim më të detajuar të nominimit dhe votimit.
Nominimi
Në fillim të fazës së nominimit, çdo nyje mund të zgjedhë spontanisht vlerën V dhe të votojë për konfirmimin "Unë nominova V". Qëllimi në këtë fazë është të konfirmohet nominimi i një vlerës përmes votimit federativ.
Ndoshta, numri i mjaftueshëm i nyjave voton për propozime mjaft të ndryshme, dhe asnjë propozim nuk mund të arrijë pragun e miratimit. Prandaj, përveç transmetimit të votave të veta, nyjat "reflektojnë" propozimet e fqinjëve të tyre. Reflektimi do të thotë se nëse një nyje voton për propozimin V, por sheh një mesazh nga një fqinje që voton për propozimin W, atëherë tani do të votojë për propozimin si V ashtu edhe W. (Jo të gjitha votat e fqinjëve do të reflektohen gjatë propozimit, sepse kjo mund të çojë në shpërthimin e emrave të ndryshëm. SCP përfshin një mekanizëm rregullator për këto vota. Në të shkurtër, ka një formulë për të përcaktuar "prioritetin" e fqinjit nga këndvështrimi i nyjës, dhe reflektohen vetëm votat e nyjave me prioritet të lartë. Sa më gjatë të vazhdojë propozimi, aq më i ulët bëhet pragu, prandaj nyja zgjeron grupin e fqinjëve, votat e të cilëve do të reflektojë. Formula e prioritetit si një nga të dhënat e inputit përfshin numrin e slotit, kështu që një nyje me prioritet të lartë për një slot mund të jetë me prioritet të ulët për një tjetër, dhe anasjelltas.)
Konceptualisht, propozimi për V dhe W është vota të veçanta federale, secila e aftë të arrijë miratimin ose konfirmimin. Në praktikë, mesazhet e protokollit SCP paketojnë këto vota të veçanta së bashku.
Ndërsa votimi për propozimin V është një premtim për të mos votuar kurrë kundër propozimit V, në nivelin e aplikacionit - në këtë rast SCP - përcaktohet se çfarë do të thotë "kundër". SCP nuk sheh një deklaratë që shkel votimin "Unë propozoj X", domethënë nuk ka mesazh "Unë jam kundër propozimit X", prandaj nyja mund të votojë për çdo vlerë të propozimit. Shumë nga këto propozime nuk do të çojnë në asgjë, por në fund nyja do të jetë në gjendje të pranojë ose konfirmojë një ose disa vlera. Kur një kandidat konfirmohet, ai bëhet kandidat.
Propozimi SCP me votimin federal. Mund të ketë shumë vlera "B" të propozuara nga nyjat e barabarta dhe "reflektuara" nga nyja.
Propozimi i kandidatëve mund të çojë në paraqitjen e disa kandidatëve të konfirmueshëm. Prandaj, SCP kërkon që niveli aplikativ të ofrojë një metodë për të bashkuar kandidatët në një kompozit (composite). Metoda e bashkimit mund të jetë çfarëdo. E rëndësishme është që nëse kjo metodë është e përcaktuar, atëherë çdo nyjë do të bashkojë të njëjtët kandidatë. Në sistemin e votimit për drekë "bashkimi" mund të nënkuptojë thjesht heqjen e njërit nga dy kandidatëve. (Por në mënyrë të përcaktuar: çdo nyjë duhet të zgjedhë të njëjtën vlerë për heqje. Për shembull, një zgjedhje më të hershme në renditjen alfabete). Në rrjetin pagesor Stellar, ku ndodh votimi për historinë e transaksioneve, bashkimi i dy propozimeve të shpallura nënkupton bashkimin e transaksioneve që ata përmbajnë dhe më të fundit nga dy vulat e tyre.
Përshkrimi teknik i SCP provon (teorema 12) se deri në përfundimin e fazës së propozimit, rrjeti përfundimisht konvergon në një kompozit të vetëm. Por ka një problem: votimi federal është një protokoll asinkron (si SCP). Me fjalë të tjera, nyjat nuk koordinohen sipas kohës, por vetëm sipas mesazheve që dërgojnë. Nga perspektiva e nyjës, nuk është e qartë se kur ka përfunduar fazën e propozimit. Dhe ndonëse të gjitha nyjat përfundimisht do të arrijnë në të njëjtin kompozit, ato mund të zgjedhin rrugë të ndryshme në këtë udhëtim, duke krijuar në rrugë kandidatë të ndryshëm kompozit dhe kurrë nuk mund të thonë se cili prej tyre është përfundimtar.
Por kjo është në rregull. Propozimi është vetëm përgatitja. E rëndësishme është të kufizohet numri i kandidatëve për të arritur konsensusin, i cili ndodh gjatë votimit (balloting).
Votimi
Një fletë votimi është një çift , ku counter është një numër tërë që fillon nga 1, dhe value është kandidati nga faza e propozimit. Kjo mund të jetë kandidati i vetë nyjës ose një kandidat i nyjës fqinj që është pranuar nga kjo nyjë. Në thelb, gjatë votimit bëhen përpjekje të shumta për ta detyruar rrjetin të arrijë konsensus mbi një kandidat në një fletë votimi duke organzuar potencialisht shumë votime federale mbi deklaratat e fletës së votimit. Numrat në fletët e votimit mbajnë shënim përpjekjet e bëra, dhe fletët me numra më të lartë kanë prioritet mbi fletët me numra më të ulët. Nëse një fletë votimi ngec, fillon një votim i ri, tani mbi fletën votimi .
Është e rëndësishme të bëhet dallimi vlerat (p.sh., çfarë duhet të jetë porosia për drekë: pica apo sallata), fletët e votimit (çifti counter-value) dhe deklaratat për bulletinat. Rreth SCP përfshin disa raunde votimi federativ, veçanërisht për pretendime të tilla si:
- «Jam i gatshëm për t'u angazhuar për bulletin B» dhe
- «Njoftoj angazhimin për bulletin B»
Nga perspektiva e këtij nodi, konsensusi arrihet kur ai gjen bulletin B, për të cilin mund të konfirmojë (dmth. të gjejë një kuorum, që pranon) pretendimin «Njoftoj angazhimin për bulletin B». Që nga ky moment, mund të veprohet me siguri sipas vlerës e cila është e shkruar në B — për shembull, për të vendosur këtë porosi për drekë. Kjo quhet eksternalizim i vlerës. Pasi të jetë konfirmuar prania e bulletinit, nodi mund të jetë i sigurt se çdo nod tjetër e ka bërë eksternalizimin e kësaj vlerësimi ose do ta bëjë atë patjetër në të ardhmen.
Megjithëse konceptualisht shumë votime federative mbahen për pretendime mbi shumë bulletina të ndryshëm, ata nuk shkëmbejnë një numër kaq të madh mesazhe, sepse çdo mesazh inkapsulon një numër bulletinash. Një mesazh, kështu, avancojnë gjendjen e shumë votimeve federative në një herë, për shembull: «Pranoj angazhimin për bulletinat në gamën nga <min,V> deri në <max,V>».
Çfarë do të thotë terminologjia «përgatitur» (prepared) dhe «angazhim» (commit)?
Nodi voton për angazhimin e bulletinit kur është i bindur se nodet e tjera nuk do të angazhohen për bulletina me vlera të tjera. Bindja në këtë është qëllimi i përgatitjes së pretendimit. Votimi, në të cilin thuhet: «Jam i gatshëm për t'u angazhuar për bulletin B», është një premtim për të mos angazhuar kurrë për një bulletin më të vogël se B, dmth. me një numër më të ulët (SCP kërkon që vlerat në bulletina të kenë një rend të caktuar. Pra, bulletin <N1,V1> është më i vogël se <N2,V2>, nëse N1<N2, dhe gjithashtu nëse N1=N2 dhe V1<V2). Këto bulletina më të vogël «hedhen poshtë» (aborted) gjatë votimit përgatitor, ndërkohë që B konsiderohet «i përgatitur».
Pse «Jam i gatshëm për t'u angazhuar për bulletin B» do të thotë «Premtoj të mos lejoj kurrë angazhimin për bulletina më të vogël se B»? Sepse, SCP e definon abortin si një tërësi të kundërt të angazhimit. Votimi përgatitor për bulletin implicon gjithashtu votimin për të anuluar disa bulletina të tjera, dhe, siç diskutuam më parë, votimi për një gjë është një premtim për të mos votuar kundër saj kurrë.
Para se të transmetojë angazhimin, nodi duhet së pari të gjejë një bulletin që mund ta konfirmojë si të përgatitur. Në fjalë të tjera, ai zhvillon një votim federativ për temën «Jam i gatshëm për t'u angazhuar për bulletin B», ndoshta për shumë bulletina të ndryshëm, derisa të gjejë atë që pranon një kuorum.
Nga vinë bulletinat për votim përgatitor? Së pari, nodi transmeton përgatitjen për votimin për <1,C>, ku C është kandidati-kompozit i prodhuar në fazën e nominimit. Megjithatë, edhe pasi ka filluar përgatitja për votim, nominimi mund të sjellë kandidatë të tjerë të rinj, që do të bëhen bulletina të rinj. Ndërkohë, palët mund të kenë kandidatë të ndryshëm, dhe ata mund të formojnë një shumicë bllokuese, që pranon «Jam i gatshëm për t'u angazhuar për bulletin B2», çka e bind nodin që ta pranojë gjithashtu. Së fundmi, ka një mekanizëm skadence që gjeneron raunde të reja votimi federative për bulletina të rinj me numra më të lartë, nëse bulletinat aktuale kanë ngecur.
Sa herë që nodi gjen bulletin B, që mund ta konfirmojë si të përgatitur, atëherë transmeton një mesazh të ri «Angazho bulletin B». Ky votim tregon palëve se nodi kurrë nuk do ta refuzojë B. Në të vërtetë, nëse B është një bulletin <N,C>, atëherë «Angazho bulletin <N,C>» do të thotë pajtim të pakushtëzuar për të votuar për gatishmërinë e çdo bulletini nga <N,C> deri në <∞,s>. Kjo vlerë e shtuar ndihmon nodet e tjera të arrijnë palën me angazhimin, nëse ato janë ende në faza më të hershme të protokollit.
Në këtë fazë, është e rëndësishme të theksohet se këto janë protokolle asinkrone. Vetëm sepse një nod dërgon vota për angazhim, nuk do të thotë se shokët e tij e bëjnë gjithashtu. Disa nga ata ndoshta ende mund të votoni mbi pretendime për përgatitje votimi, ndërsa të tjerë ndoshta kanë bërë tashmë eksternalizimin e vlerës. SCP shpjegon se si ndihmon nodin të trajtojë çdo lloj mesazhi peer-to-peer, pavarësisht nga faza e tij.
Nëse mesazhi "Unë shpall komitin <N,C>" nuk mund të pranohet ose konfirmohet, ka një mundësi për pranimin ose konfirmimin e mesazhit <N+1, C> ose <N+2, C> — ose, në çdo rast, ndonjë buletin me vlerën C, e jo çfarëdo tjetër, pasi nodi tashmë ka premtuar se nuk do të anulojë kurrë <N,C>. Në momentin që nodi transmeton votat për komitin, do të jetë C ose asgjë, në varësi të sa larg shkon konsensusi. Megjithatë, kjo nuk është ende e mjaftueshme për nodin për të eksternalizuar C. Disa festa bizantine (të cilat përbëjnë një shumicë më të vogël, bazuar në supozimet tona për sigurinë) mund të gënjejnë nodin. Pranimi, dhe më pas konfirmimi i disa buletinash (ose një intriguing range të buletinave) — kjo është ajo që i jep nodit besimin përfundimtar për të eksternalizuar C.
Votimi SCP përmes votimit federativ. Nuk është e dukshme: në çdo moment, mund të aktivizohet një kujtesë, duke rritur numrin në buletin (dhe, ndoshta, duke prodhuar një kompozit të ri nga kandidatët e propozuar shtesë).
Dhe kjo është gjithçka! Pasi rrjeti arriti konsensusin, ai është gati ta bëjë këtë përsëri dhe përsëri. Në rrjetin e pagesave Stellar, kjo ndodh çdo 5 sekonda: një arritje që kërkon si siguri ashtu dhe qëndrueshmëri, të garantuara nga SCP.
SCP mund ta arrijë këtë duke u mbështetur në disa runde votimi federativ. Votimi federativ është bërë i mundur falë konceptit të prerjes së shumicës: grupeve të nodave të një niveli, të cilëve çdo nod ka vendosur t'u besohet si pjesë e shumicës së tij (subjektive). Kjo konfigurim do të thotë se mund të arrihet konsensusi edhe në një rrjet me anëtarësi të hapur dhe mashtrime bizantine.
Lexim të mëtejshëm
- Dokumenti teknik origjinal i SCP-së mund të gjendet , dhe projekti i specifikimeve për implementimin e tij.
- Autori origjinal i protokollit SCP, David Mazier, e shpjegon në mënyrë të thjeshtë (por akoma teknike) .
- Ndoshta ju ka befasuar që nuk e gjeni në këtë artikull termin "mining" ose "proof of work". SCP nuk i përdor këto metoda, por disa algoritme të tjera konsensusi i përdorin. Zane Weatherspoon shkruajti një .
- i një rrjeti të thjeshtë që arrin konsensusin gjatë një runde të plotë SCP.
- Për lexuesit e interesuar për implementimet e SCP: shihni , që përdoret nga rrjeti i pagesave Stellar, ose , të cilin e shkrova për një kuptim më të mirë të SCP-së.
Burimi: habr.com
