Protokolli i konsensusit Stellar u përshkrua për herë të parë në të David Mazier në vitin 2015. Ky është një "sistem federativ i marrëveshjeve bizantine", i cili i lejon rrjeteve kompjuterike të decentralizuara pa liderë të arrijnë në mënyrë efikase konsensus mbi një vendim të caktuar. Rrjeti paguese Stellar përdor Protokollin e Konsensusit Stellar (SCP) për të mbajtur një histori të konsoliduar transaksionesh, të cilën e shohin të gjithë pjesëmarrësit.
Njihet se protokollet e konsensusit janë të vështira për t’u kuptuar. SCP është më i thjeshtë se shumica e tyre, por ndjek ende këtë reputacion — pjesërisht për shkak të idesë së gabuar se "votimi federativ", i cili përkushtohet në gjysmën e 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ë gjysmën e dytë të artikullit përdoret për të krijuar protokollin e vërtetë të konsensusit Stellar.
Në këtë artikull do të flasim shkurtimisht se çfarë është një "sistem marrëveshjesh", çfarë e bën atë "bizantin" dhe pse ta bëjmë sistemin bizantin "federativ". Pastaj do të shpjegojmë procedurën federative të votimit, të përshkruar në artikullin për SCP, dhe përfundimisht do të shpjegojmë protokollin SCP.
Sistemet e marrëveshjeve
Sistemi i marrëveshjeve i lejon një grup participantësh të arrijnë konsensus mbi një çështje, për shembull, çfarë të porosisin për drekë.
Ne në kompaninë Interstellar kemi zbatuar sistemin tonë të marrëveshjes për drekë: porosisim atë që thotë menaxheri ynë operativ, John. Kjo është një sistem i thjeshtë dhe efikas marrëveshjesh. Të gjithë ne besojmë tek John dhe jemi të sigurt se çdo ditë do të gjejë diçka interesante dhe ushqyese.
Por, çfarë nëse John e abuzon besimin tonë? Ai mund të vendosë vetëm se të gjithë ne duhet të bëhemi vegjetarianë. Pas një jave ose dy, ndoshta do ta rrëzojmë atë dhe do t'i japim pushtetin Elizabeth. Por ndoshta ajo pëlqen avokado me anchoa dhe mendon se të gjithë duhet të bëhen kështu. Fuqia korrupton. Prandaj, është më mirë të gjejmë një metodë më demokratike: një mënyrë për të siguruar se preferencat e ndryshme janë të marrë parasysh, ndërkohë që sigurohet një rezultat në kohë dhe të qartë, për të mos ndodhur që askush të mos porosisë drekë ose pesë njerëz të vendosin porosi të ndryshme, ose diskutimi të zgjasë deri në mbrëmje.
Duket sikur zgjidhja është e thjeshtë: të mbahet një votim! Por kjo është një përshtypje e gënjyer. Kush do të mbledhë fletët e votimit dhe do të kumtojë rezultatet? Dhe pse të tjerët duhet të besojnë atë që ai do të thotë? Ndoshta, ne mund të së pari votojmë për një lider të cilit i besojmë për të drejtuar votimin — por kush do ta udhëheqë këtë votim të parë? Çfarë nëse nuk mund të arrijmë një marrëveshje për liderin? Ose nëse arrijmë, por ky lider ngel në një takim ose shkon në spital? Problemet e ngjashme ndodhin në rrjetet kompjuterike të shpërndara. Të gjithë pjesëmarrësit ose nyjet duhet të bien dakord për një zgjidhje, për shembull, kush është radha për të përditësuar një skedë të përbashkët ose për të marrë një detyrë nga një radhë përpunimi. Në një rrjet kriptovalute, nyjet shpesh duhet të zgjedhin si duket historia e plotë, nga disa versione të mundshme që ndonjëherë janë në konflikt. Kjo marrëveshje rrjetore i garanton marrësit se monedha është (a) e vlefshme (jo e falsifikuar) dhe (b) ende nuk është shpenzuar diku tjetër. Kjo gjithashtu garanton që ai do të 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 marrëveshjeje në një rrjet kompjuterik të shpërndara duhet të jetë i qëndrueshëm ndaj dështimeve: ai duhet të japë rezultate të qëndrueshme, pavarësisht nga gabimet, siç janë linjat e ngadalta të komunikimit, nyjet që nuk përgjigjen dhe rendi i gabuar i mesazheve.
Një sistem marrëveshjeje bizantin është shtesë i qëndrueshëm ndaj gabimeve 'bizantine': nyjet që japin informacione të rreme, qofshin ato për shkak të gabimeve, ose për përpjekje të qëllimshme për të minuar sistemin ose për të marrë ndonjë përfitim. Qëndrueshmëria 'bizantine' — aftësia për të besuar në marrëveshjen e grupit, edhe kur disa anëtarë të grupit mund të gënjejnë ose në ndonjë mënyrë të mos ndjekin rregullat e vendimmarrjes — mori emrin nga mërganë e gjeneralëve të Perandorisë Bizantine Një përshkrim të mirë у Энтони Стивенса.
Le të shqyrtojmë pronarin e monedhës kriptografike, Alisa, e cila duhet të zgjedhë midis blerjes së një akulloje të shijshme nga Bobo dhe pagesës së borxhit ndaj Kerol. Ndoshta, Alisa dëshiron t'u paguajë të dyve njëherësh, duke e shpenzuar mashtrueshëm të njëjtën monedhë. Për këtë, ajo duhet të bindë kompjuterin e Bobos se monedha nuk ka qenë kurrë e paguar ndaj Kerol, dhe të bindë kompjuterin e Kerol se monedha nuk ka qenë kurrë e paguar ndaj Bobos. Sistemi bizantin i marrëveshjeve e bën këtë të pamundur, duke përdorur një formë rregulli të shumicës, të quajtur kuorum. Një nyje në një rrjet të tillë refuzon të kalojë në një version të caktuar të historisë, derisa të shohë se një numër i mjaftueshëm nyjesh të barabarta - kuorum - bien dakord për kalimin e tillë. Sa herë që ndodh kjo, ata formojnë një bllok mjaft të madh zgjedhor për të detyruar nyjet e tjera të rrjetit të bien dakord me vendimin e tyre. Alisa mund të detyrojë disa nyje të gënjejnë në emrin e 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 kërkohen për një kuorum? Të paktën, shumica, dhe saktësisht, një shumicë kualifikuese për të luftuar gabimet dhe mashtrimet. Por për të numëruar shumicën, duhet të dihet numri total i pjesëmarrësve. Në zyrën Interstellar ose në zgjedhjet rajonale, këto numra janë të lehta për t'u njohur. Por nëse grupi juaj është një rrjet i pakontrolluar, në të cilin nyjet mund të hyjnë dhe dalin në vullnet të tyre pa marrëveshje me një qendër, atëherë ne na nevojitet një sistem federal bizantin të marrëveshjes, i aftë për të përcaktuar kuorume jo nga një listë e përcaktuar paraprakisht nyjesh, por dinamikisht, nga një pamje që ndryshon vazhdimisht dhe që është domosdoshmërisht e paplotë në një moment të caktuar.
Mund të duket e pamundur të krijohet një kuorum nga këndvështrimi i një nyjeje në një rrjet të gjerë, por kjo është e mundur. Ky kuorum madje mund të garantojë rezultatet e votimit të decentralizuar. Dokumenti teknik SCP tregon se si të bëhet kjo përmes një procedure të quajtur votimi federal.
Për të pa durueshmit
Pjesa tjetër e artikullit e përshkruan më në detaje votimin federal dhe protokollin e konsensusit Stellar. Nëse nuk jeni të interesuar për detajet, ja një përmbledhje e përgjithshme e procesit.
- Nysetët mbajnë raunde të votimit federal për "nominatet". Raundi i votimit federativ do të thotë:
- Nyseti voton për ndonjë propozim, siç është "Propozoj vlerën V";
- Nyseti dëgjon votat e pjesëmarrësve derisa të gjejë atë që mund të "pranojë";
- Nyseti kërkon një "kuorum" për këtë propozim. Kuorumi "konfirmon" nominimin.
- Sapo nyseti të jetë në gjendje të konfirmojë një ose më shumë nominime, ai përpiqet të "përgatisë" "fletën e votimit" përmes disa raundeve të votimit federativ.
- Sapo nyseti të jetë në gjendje të verifikojë gatishmërinë e fletës së votimit, ai përpiqet ta angazhojë atë me më shumë raunde të votimit federativ.
- Sapo nyseti të mund të konfirmojë angazhimin e fletës së votimit, ai mund të "eksternalizojë" vlerën e kësaj fletë votimi, duke e përdorur atë si rezultat të konsensusit.
Këto hapa përfshijnë disa raunde të votimit federativ, të cilat së bashku formojnë një raund SCP. Le të shqyrtojmë më 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ë marrë një propozim. Në raundin e votimit, çdo nyse duhet të zgjedhë një nga shumë vlera potenciale. Ai nuk mund ta bëjë këtë derisa të jetë i sigurt se nyset e tjera në rrjet nuk do të zgjedhin një rezultat tjetër. Për të siguruar këtë, nyset shkëmbejnë një mori mesazhesh mes tyre, në mënyrë që çdo nga, që kuorum nyset merr të njëjtën vendim. Pjesa tjetër e këtij seksioni shpjegon terminologjinë në këtë propozim dhe si ndodhin të gjithë proceset.
Kuorume dhe pjesët e kuorumit
Të fillojmë me përkufizimin e kuorumit. Siç e diskutuam më lart, në një rrjet të decentralizuar me anëtarësim dinamik, është e pamundur të dihet paraprakisht numri i nyseve dhe, si rrjedhojë, sa nevojitet për shumicën. Votimi federativ zgjidh këtë problem duke paraqitur një ide të re pjesët e kuorumit (quorum slice): një grup i vogël nyse të barabartë, të cilëve nyseti u beson për të transmetuar informacionin mbi gjendjen e votimit në pjesën tjetër të rrjetit. Çdo nyse përcakton pjesën e saj të kuorumi (anëtar i të cilit bëhet faktikisht).
Formimi i kuorumit fillon me prerjen e kuorumit. Për çdo nyje, shtohen nyjet e prerjes së saj. Më pas, shtohen anëtarët e prerjeve këtyre nyjeve dhe kështu me radhë. Me kalimin e kohës, shpesh herë shfaqen më shumë nyje që nuk mund t’i shtoni, sepse ato janë tashmë të përfshira në prerje. Kur nuk ka më nyje të reja për t'u shtuar, procesi ndalon: ne formuam kuorumin përmes 'mbylljes transitive' të prerjes së kuorumit të nyjës fillestare.
Për të gjetur kuorum nga një nyje të caktuar…
... shtojmë anëtarët e prerjes së saj…
... pastaj shtojmë anëtarët e prerjeve të këtyre nyjeve.
Vazhdoni derisa të mos ketë më nyje për t'u shtuar.
Nuk ka mbetur asnjë nyje për t'u shtuar. Ky është kuorumi.
Në të vërtetë, secila nyje mund të jetë pjesë e më shumë se një prerjeje. Për të formuar kuorumin, zgjidhni vetëm një nga prerjet dhe shtoni anëtarët; më pas zgjidhni një prerje për secilin nga anëtarët dhe shtoni anëtarët këtë e prerjes dhe kështu me radhë. Kjo do të thotë se çdo nyje është anëtar i një grupi të mundshëm kuorumesh.
Zgjidhni vetëm një prerje kuorumi në secilin hap.
Një kuorum i mundshëm. Ose një opsion alternativ...
...zgjidhim prerje të tjera...
...(kur është e mundur)...
...krijon një kuorum tjetër.
Si e di një nyje se në cilat prerje përbëhen nyjet e tjera? Pikërisht ashtu siç merr informacion tjetër për nyjet e tjera: nga transmetimet që secila nyje dërgon në rrjet, kur ndryshon gjendja e saj të votimit. Çdo transmetim përfshin informacion mbi prerjet e nyjës që dërgon. Në dokumentin teknik SCP, mekanizmi i komunikimit nuk është specifikuar. Zbatimet zakonisht përdorin për transmetimin e garantuar të mesazheve në të gjithë rrjetin.
Të kujtojmë se në sistemin e marrëveshjeve bizantine jo-federale, kuorumi përcaktohet si shumicë e të gjitha nyjeve. Sistemi bizantin i marrëveshjeve është zhvilluar në lidhje me pyetjen: sa nyje të paligjshme është në gjendje të përballojë sistemi? Në një sistem me N nyje, i projektuar për të mbijetuar me f dështime (mashtresa), një nyje duhet të jetë në gjendje të arrijë përparim duke marrë përgjigje nga N−f peers, pasi f nga to, ndoshta, nuk funksionojnë. Por, duke marrë përgjigje nga N−f peers, mund të supozohet se të gjitha f peers (nga të cilët nyja nuk mori përgjigje) janë në të vërtetë të ndershëm. Kështu, dëmshëm janë f nga N−f peers (nga të cilët u mor përgjigje). Për t'u arritur në 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 sistemi, 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. Sapuni kalon pragun e kuorumit, anëtarët e mbetur të rrjetit janë të bindur se çdo propozim konkurrues do të dështojë. Kështu rrjeti arrin një rezultat.
Por në sistemin e marrëveshjeve bizantine federale, nuk mund të ketë shumicë (sepse askush nuk e di madhësinë e përgjithshme të rrjetit), dhe koncepti i shumicës është në tërësi i padobishëm! Nëse anëtarësimi në sistem është i hapur, ndokush mund të marrë shumicën, thjesht duke kryer një sulm të njohur si sulmi i Sivilës: duke u bashkuar me rrjetin përmes disa nyjeve shumë herë. Pra, përse quhet mbyllja tranzitive e prerjes kuorum, dhe si është në gjendje të shtypë propozimet konkurruese?
Teknikisht, asnjëherë! Imagjinoni një rrjet prej gjashtë nyjesh, ku dy grupe të izoluara janë në prerjet e kuorumit të njëra-tjetrës. Grupi i parë mund të marrë një vendim, për të cilin grupi i dytë kurrë nuk do të dëgjojë, dhe anasjelltas. Për këtë rrjet nuk ka mënyrë për të arritur një konsensus (përveç rastësisht).
Prandaj, SCP kërkon që për votimin federal (dhe për aplikimin e teoremave të rëndësishme të artikullit), rrjeti të ketë një pronë, e quajtur përgjatësia e kuorumëveNë një rrjet me këtë pronë, çdo dy kuorume që mund të ndërtohen, gjithmonë kanë një mbivendosje në të paktën një nyje. Për të përcaktuar ndjenjat mbizotëruese të rrjetit, kjo është po aq e mirë sa të kesh një shumicë. Intuitivisht, kjo do të thotë se nëse ndonjë kuorum është dakord me deklaratën X, asnjë kuorum tjetër nuk do të mund të jetë dakord me diçka tjetër, pasi do të përfshijë një nyje nga kuorumi i parë që ka votuar për X.
Nëse në rrjet ka mbivendosje kuorumesh…
… atëherë çdo dy kuorume që mund të ndërtoni…
… gjithmonë do të mbivendosen.
(Sigurisht, nyjet që mbivendosen mund të përfshijnë nyje të gabuara apo të gabuara në aspekte të tjera. Në këtë rast, mbivendosja e kuorumeve nuk ndihmon rrjetin të arrijë një marrëveshje. Për këtë arsye, shumë rezultate në dokumentin teknik SCP bazohen në supozime të shprehura qartë, si ajo që në rrjet ka mbivendosje kuorumesh, edhe pas eliminimit të nyjeve të këqija. Për thjeshtësi, do t'i lëmë këto supozime të heshtura pjesës tjetër të artikullit).
Mund të duket irracionale të pritet se në një rrjet të nyjeve të pavarura është e mundur një mbivendosje e qëndrueshme kuorumesh. Por ka dy arsye pse kjo është e vërtetë.
Arsyeja e parë ka të bëjë me ekzistencën e vetë internetit. Interneti është një shembull ideal i një rrjeti me nyje të pavarura që kanë mbivendosje kuorumesh. Shumica e nyjeve në internet lidhen vetëm me disa nyje lokale të tjera, por këto grupe të vogla mbivendosen mjaft sa çdo nyje të jetë e aksesueshme nga çdo nyje tjetër përmes një rruge ose një tjetër.
Arsye e dytë është specifike për rrjetin e pagesave Stellar (përdorimi më i zakonshëm SCP). Çdo aktiv në rrjetin Stellar ka një emetues, dhe rekomandimet e Stellar kërkojnë që çdo emetues të nominojë një ose më shumë nyje në rrjet për të trajtuar kërkesat për shlyerje. Është në interesin tuaj të përfshijeni, drejtpërdrejt ose tërthor, këto nyje në përzgjedhjet e kuorumit për çdo aktiv që ju intereson. Më pas, kuorumet për të gjitha nyjet e interesuara për këtë aktiv do të mbivendosen të paktën në këto nyje shlyerjeje. Nyjet që janë të interesuara për disa aktive do të përfshijnë në përzgjedhjet e tyre të kuorumit të gjitha nyjet shlyerjeje të emetuesve përkatës, dhe ato do të përpiqen të bashkojnë të gjithë aktet së bashku. Për më tepër, çdo aktiv që nuk është i lidhur në këtë mënyrë me të tjerët në rrjet, dhe nuk duhet të lidhen — është menduar që për këtë rrjet të mos ketë mbivendosje kuorumesh (p.sh., bankat nga zona e dollarit ndonjëherë duan të tregtojnë me bankat nga zona e euros dhe bankat nga zona e pesos, prandaj ato janë në një rrjet, por askujt nga ata nuk i intereson një rrjet i veçantë i fëmijëve që tregtojnë me karta bejsbolli).
Sigurisht, pritet mbivendosje kuorumesh nuk është garantim. Sistemet e tjera bizantine të konsensit me kompleksitetin e tyre shumë prej tij e detyrojnë garantimin e kuorumëve. Një novitet i rëndësishëm i SCP është se ai heq përgjegjësinë për krijimin e kuorumëve nga algoritmi i konsensusit dhe e kthen atë në nivelin e aplikacionit. Kështu, megjithëse votimi federativ është mjaft i zakonshëm për votimin mbi çdo çështje, në të vërtetë besueshmëria e tij vaçon kritikisht nga kuptimi më i gjerë i këtyre vlerave. Disa lloje hypotetike përdorimi mund të rezultojnë të mos jenë aq të përshtatshme për të krijuar rrjete të mirë lidhura, sa të tjerat.
Votimi, pranimi dhe konfirmimi
Në raundin e votimit federativ, nyja fillimisht fillon të votojë për një vlerë të caktuar V. Kjo do të thotë transmetimi në rrjet të një mesazhi: «Unë jam nyja N, përzgjedhjet e mia të kuorumit Q, dhe unë votoj për V». Kur nyja voton në këtë mënyrë, ajo premton se nuk ka votuar kurrë kundër V dhe kurrë nuk do të votojë.
Në transmetimet nga nyjet peer-to-peer, çdo nyje sheh se si votojnë të tjerët. Sapo një nyje të mbledhë një numër të mjaftueshëm mesazhesh të tilla, ajo mund të ndjekë përqindjet e kuorumit dhe të provojë të gjejë kuorume. Nëse ajo sheh një kuorum të peer-ëve që gjithashtu votojnë për V, atëherë mund të kalojë në pranimin V dhe ta transmetojë këtë mesazh të ri në rrjet: «Unë jam nyja N, përqindjet e mia të kuorumit Q dhe unë pranoj V». Pranimi siguron një garanci më të fortë se thjesht votimi. Kur një nyje votohet për V, ajo kurrë nuk mund të votojë për mundësi të tjera. Por nëse një nyje pranon V, asnjë nyje në Rrjet kurrë nuk do të pranojë një alternativë tjetër (teorema 8 në dokumentin teknik SCP e provon këtë).
Natyrisht, ka një probabilitet të lartë që nuk do të gjendet menjëherë një kuorum nyjesh që janë dakord me V. Nyje të tjera mund të votojnë për vlera të tjera. Por për një nyje, ka edhe një mënyrë tjetër për të kaluar nga votimi i thjeshtë në pranimin. N mund të pranojë një vlerë tjetër W, edhe nëse nuk ka votuar për të, dhe madje edhe nëse nuk sheh për të një kuorum. Për të ndryshuar votën e tij, mjafton të shohë një grup bllokues nyjesh që kanë pranuar W. Një grup bllokues është një nyje nga secila prej përqindjeve të kuorumit N. Siç merret me emrin, ai është në gjendje të bllokojë çdo vlerë tjetër. Nëse të gjitha nyjet në një të tillë grup pranojnë W, atëherë (sipër teoremës 8) kurrë nuk do të jetë e mundur të formohet një kuorum që pranon një vlerë tjetër, dhe për këtë arsye për N është gjithashtu e sigurt të pranojë W.
Nyja N me tre përqindje kuorumesh.
B-D-F është një grup bllokues për N: përfshin një nyje nga secila prej përqindjeve N.
B-E gjithashtu është një grup bllokues për N, sepse E shfaqet në dy përqindje N.
Por një grup bllokues nuk është një kuorum. Do të ishte tepër e lehtë të mashtrohej nyja N që të pranonte vlerën e dëshiruar, nëse mjafton të komprometohet një nyje në çdo përqindje N. Prandaj, pranimi i vlerës nuk është ende fundi i votimit. Në vend të kësaj, N duhet të konfirmojë vlerën, domethënë të shohë një kuorum nyjesh që e pranojnë atë. Nëse arrin kaq larg, atëherë siç e provon dokumenti teknik SCP (në teoremin 11), pjesa tjetër e rrjetit gjithashtu në fund do të konfirmojë të njëjtën vlerë, prandaj N do të përfundojë votimin federal me një vlerë të caktuar si rezultat.
Votimi federal.
Procesi i votimit, miratimit dhe konfirmimit përbën një raund të plotë të votimit federal. Protokolli i konsensusit Stellar bashkon shumë nga këto raunde për të krijuar një sistem të plotë konsensusi.
Protokolli i konsensusit Stellar
Dy cilësitë më të rëndësishme të një sistemi konsensusi janë siguria dhe qëndrueshmëria. Algoritmi i konsensusit është "i sigurt", nëse kurrë nuk mund të japë rezultate të ndryshme për pjesëmarrës të ndryshëm (kopja e historisë së Bobit nuk do të kundërshtojë kurrë atë të Carolit). "Qëndrueshmëria" do të thotë se algoritmi gjithmonë do të japë një rezultat, pra nuk do të ngecë.
Procedura e përshkruar e votimit federal është e sigurt në kuptimin që, nëse një node konfirmon vlerën V, asnjë node tjetër nuk do të konfirmojë një vlerë tjetër. Por "nuk do të konfirmojë një vlerë tjetër" nuk do të thotë se ai domosdoshmërisht do të konfirmojë diçka. Pjesëmarrësit mund të votojnë për një numër kaq të madh vlerash të ndryshme, sa që asgjë nuk do të arrijë pragun e miratimit. Kjo do të thotë se në votimin federal nuk ka qëndrueshmëria.
Protokolli i konsensusit Stellar përdor votimin federal në një mënyrë që garanton si sigurinë ashtu edhe qëndrueshmërinë. (Garancitë e sigurisë dhe qëndrueshmërisë së SCP kanë një kufi teorik. Konstrukti zgjidh një garanci shumë të fortë të sigurisë, duke sakrifikuar një dobësim të vogël të qëndrueshmërisë, por duke marrë parasysh kohën e mjaftueshme, konsensusi me një probabilitet të lartë do të arrihet). Me fjalë të tjera, ideja është të realizohen disa votime federale për disa vlera, derisa njëra prej tyre të kalojë plotësisht përmes të gjitha fazave të votimit SCP, të përshkruara më poshtë.
Vlerat për të cilat SCP synon konsensusin mund të jenë historia e transaksioneve ose porosia për drekë, apo diçka tjetër, por është e rëndësishme të theksohet se këto nuk janë ato vlera që miratohen ose konfirmohen. Përkundrazi, votimi federal ndodh për deklaratat për këto vlera.
Raundet e para të votimit federal ndodhin në fazën e nominimit (niveli i nominimit), në një grup deklaratash të tipit "Unë propozoi V", ndoshta për shumë vlera të ndryshme V. Qëllimi i nominimit është të gjejë një ose disa deklarata që kalojnë përmes miratimit dhe konfirmimit.
Pas pasjesh të kandidatëve të konfirmuar, SCP kalon në fazën e votimit, ku qëllimi është të gjejë një votë (domethënë një enë për vlerën e propozuar) dhe kuorumin, që mund të shpallë komit për të (commit). Nëse kuorumi bën commit të votës, vlera e saj pranohet si konsens. Por para se nyja të mund të votojë për commit-in e votës, ajo duhet së pari të konfirmojë anulimin e të gjitha votave me një vlerë numri më të vogël. Këto hapa - anulimi i votave, për të gjetur atë për të cilin mund të konfirmohet commit - përfshijnë disa raunde votimi federativ mbi disa shpallje votash.
Në seksionet që vijojnë, do të përshkruhen më hollësisht propozimi dhe votimi.
Propozimi
Në fillim të fazës së propozimit, çdo nyjë mund të zgjedhë spontanisht një vlerë V dhe të votojë për miratimin e "Unë propozoi V". Qëllimi në këtë fazë është të konfirmohet propozimi i një vlerë përmes votimit federal.
Mund të ndodhë që një numër i mjaftueshëm nyjash votojnë për shpallje mjaft të ndryshme dhe asnjë propozim nuk mund të arrijë pragun e miratimit. Prandaj, përveç transmetimit të votave të tyre të propozimit, nyjat "reflektojnë" propozimet e fqinjëve të tyre. Reflektimi (echo) do të thotë se nëse një nyjë votojnë për propozimin V, por sheh një mesazh nga një fqinji që votojnë 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 reflektohen gjatë propozimit, pasi kjo mund të çojë në një shpërthim të propozimeve të ndryshme. SCP përfshin një mekanizëm për rregullimin e këtyre votave. Në përmbledhje, ekziston një formulë për të përcaktuar "prioritetin" e fqinjit nga perspektiva e nyjës, dhe reflektohen vetëm votat e nyjave me prioritet të lartë. Sa më gjatë të zgjasë propozimi, aq më i ulët është pragu, prandaj nyja zgjeron grupin e fqinjëve, të cilët votat e tyre do të reflektohen. Formula e prioritetit si një nga hyrjet përfshin numrin e slot-it, prandaj një nyjë me prioritet të lartë për një slot mund të jetë me prioritet të ulët për një tjetër, dhe e anasjellta).
Konceptualisht, propozuar paralelisht V dhe W — janë vota federative të veçanta, secila mund të arrijë pranimin ose miratimin e veçantë. Në praktikë, mesazhet e protokollit SCP paketojnë këto vota të veçanta së bashku.
Ndërsa votimi për propozuar V — është një premtim se nuk do të votohet kurrë kundër propozuar V, në nivelin e aplikacionit ‒ në këtë rast SCP ‒ përcaktohet se çfarë do të thotë 'kundër'. SCP nuk sheh një konfirmim që është në kundërshtim me votimin 'Unë propozoj X', dmth nuk ka mesazh 'Unë jam kundër propozuar X', kështu që nodi mund të votojë për propozuar çdo vlerë. Shumë prej këtyre nominimeve nuk do të çojnë në asgjë, por në fund nodi do të jetë në gjendje të pranojë ose miratojë një ose më shumë vlera. Sapo nomini të jetë i konfirmuar, ai bëhet kandidat.
Propozimi SCP me përdorimin e votimit federativ. Mund të ketë shumë vlera “B”, të propozuara nga nodet e barabarta dhe ‘reflektuara’ nga nodi.
Propozimi i kandidatëve mund të çojë në shfaqjen 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, çdo nod do të bashkojë kandidatët e njëjtë. Në sistemin e votimit për drekë, 'bashkimi' mund të nënkuptojë thjesht heqjen e njërit nga dy kandidatët. (Por në një mënyrë të përcaktuar: çdo nod duhet të zgjedhë të njëjtën vlerë për të hequr. Për shembull, një zgjedhje më të hershme në rendin alfabetik). Në rrjetin e pagesave Stellar, ku ndodh votimi për historinë e transaksioneve, bashkimi i dy kandidatëve të propozuar nënkupton bashkimin e transaksioneve që ata përmbajnë, dhe të fundit nga dy timestamp-et e tyre.
Përshkrimi teknik i SCP e vërteton (teorema 12), se deri në përfundimin e fazës së propozimit, rrjeti në fund do të konvergojë në një kompozit të vetëm. Por ka një problem: votimi federativ është një protokoll asinkron (ashtu si SCP). Në fjali të tjera, nodet nuk koordinohen me kohë, por vetëm me mesazhet që dërgojnë. Nga këndvështrimi i nodit, nuk është e qartë se kur përfundoi fazat e shpërndarjes. Edhe pse të gjitha nyjat përfundimisht do të arrijnë në të njëjtin kompozit, ato mund të zgjedhin rrugë të ndryshme në këtë proces, duke krijuar në rrugë kandidatë të ndryshëm, dhe nuk mund të thonë kurrë se cili prej tyre është përfundimtar.
Por kjo është në rregull. Shpërndarja është thjesht një përgatitje. E rëndësishme është të kufizohet numri i kandidatëve për të arritur një konsensus, që ndodh në procesin votimit. (votimi).
Votimi
Një fletë votimi është një çift , ku counter është një numër i plotë që fillon nga 1, dhe value është kandidati nga faza e shpërndarjes. Ky mund të jetë kandidati i vetë nyjës ose kandidati i një nyjeje fqinj, i pranuar nga kjo nyjë. Në thelb, gjatë votimit ndërmerren përpjekje të shumta për të arritur konsensus në rrjet për një kandidat të caktuar në një fletë votimi duke kryer potencialisht shumë votime federale për deklarata mbi fletët e votimit. Numëruesit në fletët e votimit ndjekin përpjekjet e bëra, dhe fletët e votimit me numërues më të lartë kanë përparësi mbi ato me numërues më të ulët. Nëse fleta votimi ngec, fillon një votim i ri, tani mbi fletën e votimit .
Është e rëndësishme të dallosh kuptime (për shembull, çfarë duhet të jetë porosia për drekë: pizza apo sallata), fletët e votimit (çifti counter-value) dhe deklaratat për fletët e votimit. Rrethi SCP përfshin disa rrethana të votimit federal, veçanërisht për këto deklarata:
- «Jam i gatshëm për angazhimin e fletës së votimit B» dhe
- «Shpall angazhimin e fletës së votimit B»
Nga këndvështrimi i kësaj nyjeje, konsensusi arrihet kur ajo gjen fletën e votimit B, për të cilën mund të konfirmojë (pra të gjejë kuorumin që pranon) deklaratën «Shpall angazhimin e fletës së votimit B». Nga ky moment, mund të veprohet në mënyrë të sigurt në lidhje me vlerën e cila tregohet në B – për shembull, të bëhet ky porosi për drekë. Kjo quhet eksternalizimi i vlerës. Sa herë që konfirmohet prana e fletës së votimit, nyja mund të jetë e sigurt që çdo nyjë tjetër ka bërë eksternalizimin e kësaj vlerë ose do të bëjë patjetër atë në të ardhmen.
Megjithëse konceptualisht shumë votime federale kryhen mbi deklaratat për shumë fletëvotime të ndryshme, ato shkëmbejnë jo një numër kaq të madh mesazhesh, pasi secili mesazh inkapsulon një sërë fletëvotimesh. Një mesazh, kështu, promovon gjendjen menjëherë të shumë votimeve federale, për shembull: «Pranoj angazhimin për fletëvotimet në mes të deri në ».
Çfarë do të thotë terminat «e përgatitur» (prepared) dhe «angazhim» (commit)?
Një nyje voton për angazhimin e fletëvotimit kur është e bindur se nyjet e tjera nuk do të bëjnë angazhim për fletëvotime me vlera të tjera. Bindja në këtë është qëllimi i përgatitjes së deklaratës. Votimi, në të cilin thuhet: «Jam i gatshëm për angazhimin e fletëvotimit B», është një premtim për të mos bërë kurrë angazhim për një fletëvotim më të vogël se B, domethënë me një numër më të vogël (SCP kërkon që vlerat në fletëvotime të kenë një renditje të caktuar. Kështu, fletëvotimi është më i vogël se , nëse N1<N2, si dhe nëse N1=N2 dhe V1<V2). Këto fletëvotime më të vogla «anulohen» (aborted) gjatë votimit përgatitor, ndërsa B konsiderohet «e përgatitur».
Pse «Jam i gatshëm për angazhimin e fletëvotimit B» do të thotë «Premtoj kurrë të lejoj angazhim për fletëvotime më të vogla se B»? Sepse SCP e definon abortin si të kundërtën e angazhimit. Votimi për përgatitjen e fletëvotimit nënkupton gjithashtu votimin për anulimin e disa fletëvotimeve të tjera, dhe, siç e përmendëm më parë, votimi për diçka është një premtim për të mos votuar kurrë kundër saj.
Para se të transmetojë angazhimin, një nyje duhet së pari të gjejë një fletëvotim që mund ta konfirmojë si të përgatitur. me fjalë të tjera, ajo bën një votim federal mbi temën «Jam i gatshëm për angazhimin e fletëvotimit B», ndoshta për shumë fletëvotime të ndryshme, derisa të gjejë atë që pranon kuorumin.
Nga vijnë bulletinat për përgatitjen e votimit? Fillimisht, nyja transmeton përgatitjen për votim për , ku C është kandidati-kompozit, i krijuar gjatë fazës së propozimit. Megjithatë, edhe pasi të ketë filluar përgatitja për votim, propozimi mund të çojë në shfaqjen e kandidatëve të tjerë, të cilët do të bëhen bulletina të rinj. Ndërkohë, piratët mund të kenë kandidatë të ndryshëm dhe ata mund të formojnë një grup bllokues, i cili pranon "Jam gati për të angazhuar bulletina B2", që do t’i bindë nyjat ta pranojnë gjithashtu. Përfundimisht, ka një mekanizëm të skadimit, i cili gjeneron raunde të reja të votimit federativ me bulletina të reja me numra më të lartë, nëse bulletinat aktuale janë bllokuar.
Sa herë që nyja gjen bulletin B, i cili mund të përforcohet si të përgatitur, ajo transmeton një mesazh të ri "Angazho bulletin B". Kjo votë i tregon piratëve se nyja kurrë nuk do të heqë dorë nga B. Në të vërtetë, nëse B përfaqëson një bulletin , atëherë "Angazho bulletin " do të thotë një marrëveshje të pakushtuar për të votuar për gatishmërinë e çdo bulletini nga deri në . Ky kuptim shtesë ndihmon nyjat e tjera të përfitojnë nga angazhimi i piratëve, nëse ato ende janë në faza më të hershme të protokollit.
Në këtë fazë, është e rëndësishme të theksohet përsëri se këto janë protokolle asinkrone. Vetëm sepse një nyjë dërgon vota për angazhim, nuk do të thotë se bashkëmoshatarët e saj po bëjnë të njëjtën gjë. Disa prej tyre ende mund të votojnë për deklarata për përgatitjen e votimit, ndërsa të tjerët, ndoshta, tashmë e kanë jashtësuar vlerën. SCP shpjegon se si nyja duhet të përpunojë secilën lloj mesazhi peer-to-peer pavarësisht nga faza e saj.
Nëse mesazhi "Unë shpall një komit <N,C>" nuk mund të pranohet ose të konfirmohet, ka një gjasë për të pranuar ose konfirmuar mesazhin <N+1, C> ose <N+2, C> — ose, në çdo rast, çdo bulletin me vlerë C, dhe jo me ndonjë tjetër, meqenëse nodi ka premtuar tashmë të mos e anulojë kurrë <N,C>. Në momentin që nodi transmeton zërat për komitin, ky do të jetë C ose asgjë, në varësi të sa larg do të shkojë konsensusi. Megjithatë, për momentin, kjo nuk është e mjaftueshme për nodin për të eksternalizuar C. Disa pyra bizantinë (me më pak se kuorumin, bazuar në supozimet tona për sigurinë) mund të gënjejnë nodin. Pranimi dhe pastaj konfirmimi i ndonjë biri (ose një sërë birish) - është ajo që i jep nodit besimin përfundimisht të eksternalizojë C.
Votimi SCP përmes votimi federal. Nuk është e shfaqur: në çdo moment, mund të aktivizohet një timer, duke rritur numrin në bulletin (dhe ndoshta duke prodhuar një kompozit të ri nga kandidatët e propozuar shtesë).
Dhe kjo është gjithçka! Pasi rrjeti arrin konsensusin, ai është i gatshëm ta bëjë këtë përsëri dhe përsëri. Në rrjetin e pagesave Stellar, kjo ndodh rreth çdo 5 sekonda: një arritje që kërkon si siguri ashtu dhe qëndrushmëri, të garantuara nga SCP.
SCP mund ta arrijë këtë duke u mbështetur në disa raunde votimi federal. Votimi federal është bërë i mundur përmes konceptit të prerjeve të kuorumit: grupeve të nodave të barabartë, të cilave çdo nod ka vendosur t'u besojë si pjesë e kuorumit të tij (subjektiv). Kjo konfigurim do të thotë se mund të arrijë konsensusi edhe në një rrjet me anëtarësi të hapur dhe mashtrime bizantine.
Leximi i mëtejshëm
- Dokumenti teknik origjinal i SCP mund të gjendet , ndërsa projekti i specifikimeve për zbatimin e tij.
- Autori origjinal i protokollit SCP David Mazier shpjegon në mënyrë të thjeshtuar (por akoma teknikisht) atë .
- Me siguri ju keni mbetur të befasuar që nuk e gjetët termin "mining" ose "proof of work" në këtë artikull. SCP nuk përdor këto metoda, por disa algoritme të tjera konsensusi i përdorin ato. Zane Wiserpoon shkroi një përmbledhje të qasshme .
- ndë një rrjeti të thjeshtë që arrin konsensusin gjatë një raundi të plotë SCP.
- Për lexuesit e interesuar në zbatimin e SCP: shikoni. , e përdorur nga rrjeti i pagesave Stellar, ose , që e shkrova për të kuptuar më mirë SCP.
Burimi: habr.com
