Iprotocol yesivumelwano seStellar yachazwa kuqala kwi UDavid Mazier ngo-2015. Le "yinkqubo yesivumelwano se-Byzantine ye-federal" evumela uthungelwano lwekhompuyutha olunamagunya, olungenankokeli ukuba lufikelele kwimvumelwano ngesigqibo. Inethiwekhi yentlawulo ye-Stellar isebenzisa i-Stellar Consensus Protocol (SCP) ukugcina imbali yokuthengiselana ehambelanayo ebonakalayo kubo bonke abathathi-nxaxheba.
Iiprothokholi zemvumelwano zithathwa ngokuba nzima ukuziqonda. I-SCP ilula kuninzi lwazo, kodwa isabelana ngolu dumo - ngokuyinxenye ngenxa yengcamango ephosakeleyo yokuba "ukuvota okudibeneyo", okuyisihloko sesiqingatha sokuqala senqaku lenzululwazi, yi-SCP. Kodwa asiyonyaniso leyo! Oku nje ibhloko ebalulekileyo yokwakha ukuba isiqingatha sesibini senqaku sisebenzisa ukudala eyona Iprotocol yesivumelwano seStellar.
Kule nqaku siza kuchaza ngokufutshane ukuba yintoni "inkqubo yezivumelwano", yintoni enokuyenza "i-Byzantine" kwaye kutheni ukwenza inkqubo yaseByzantine "federal". Emva koko siya kuchaza inkqubo yokuvota edibeneyo echazwe kwinqaku le-SCP, kwaye ekugqibeleni siya kuchaza i-SCP protocol ngokwayo.
Iinkqubo zesivumelwano
Inkqubo yezivumelwano ivumela iqela labathathi-nxaxheba ukuba bafikelele kwisivumelwano ngesihloko, esifana nokuba yintoni onokuyiodola ngesidlo sasemini.
Kwa-Interstellar, siphumeze eyethu inkqubo yesivumelwano sokutyela: siyalela oko umphathi wethu wokusebenza, uJohn, akutshoyo. Le yinkqubo yesivumelwano elula nesebenzayo. Sonke siyamthemba uJohn kwaye sikholelwa ukuba uya kufumana into enomdla kunye nesondlo yonke imihla.
Kodwa kuthekani ukuba uYohane usebenzisa kakubi ithemba lethu? Unokwenza isigqibo eyedwa ukuba sonke kufuneka sibe ngabatya inyama. Kwiveki okanye ezimbini, mhlawumbi siya kumbhukuqa size sinikezele amandla kuElizabeth. Kodwa ngequbuliso uthanda iiavokhado ezine-anchovies kwaye ucinga ukuba wonke umntu kufuneka abe njalo. Amandla onakalisa. Ngoko kungcono ukufumana enye indlela yedemokhrasi: indlela ethile yokuqinisekisa ukuba ukhetho olwahlukileyo luthathelwa ingqalelo, ngelixa uqinisekisa umphumo wexesha kunye nocacileyo, ukuze kungabikho mntu ugqiba uku-odola isidlo sasemini, okanye abantu abahlanu babeke ii-odolo ezahlukeneyo, okanye ingxoxo. itsala kude kube sebusuku.
Kubonakala ngathi isisombululo silula: bamba ivoti! Kodwa lo ngumbono olahlekisayo. Ngubani oza kuqokelela amavoti aze anike ingxelo ngeziphumo? Yaye kutheni abanye befanele bakukholelwe oko akuthethayo? Mhlawumbi singakwazi ekuqaleni sivotele inkokeli esiyithembileyo ukuba ikhokele uvoto – kodwa iza kuyikhokela первым ngokuvota? Kuthekani ukuba asivumelani ngenkokeli? Okanye kuthekani ukuba sifikelela kwisivumelwano, kodwa le nkokeli ibambeke entlanganisweni okanye iye kwikhefu lokugula?
Iingxaki ezifanayo ziyenzeka kwiinethiwekhi zekhompyuter ezisasazwayo. Bonke abathathi-nxaxheba okanye ii-nodes kufuneka bavumelane ngesigqibo esithile, njengokuba ngubani ithuba lokuhlaziya ifayile ekwabelwana ngayo okanye ukususa umsebenzi kumgca wokucubungula. Kwinethiwekhi ye-cryptocurrency, ii-nodes kufuneka zikhethe ngokuphindaphindiweyo ukuba ibali elipheleleyo libukeka njani kwiinguqulelo ezininzi ezinokwenzeka, ngamanye amaxesha ziphikisana. Esi sivumelwano sothungelwano sinika isiqinisekiso kumamkeli ukuba ingqekembe yemali (a) iyasebenza (ayiyomgunyathi) kwaye (b) ayikasetyenziswa kwenye indawo. Oku kuqinisekisa ukuba uya kukwazi ukuchitha iingqekembe kwixesha elizayo kuba ummkeli omtsha uya kuba neziqinisekiso ezifanayo ngenxa yezizathu ezifanayo.
Nayiphi na inkqubo yokuvumelana kwinethiwekhi yecomputing esasazwayo kufuneka ibe yi-fault-tolerant: kufuneka ivelise iziphumo ezihambelanayo ngaphandle kweempazamo ezinjengeekhonkco ezicothayo, ii-nodes ezingaphenduliyo, kunye nomyalelo ongalunganga womyalezo. eByzantine Inkqubo yesivumelwano iphinda ixhathise kwiimpazamo ze "Byzantine": iindawo zokuhlala ezinika ulwazi olungeyonyani, nokuba kungenxa yempazamo okanye ngeenzame zangabom zokujongela phantsi inkqubo okanye ukufumana inzuzo ethile. "Byzantine" ukunyamezela impazamo - ukukwazi ukuthembela kwisigqibo seqela nangona amanye amalungu eqela exoka okanye engalandeli imigaqo yokwenza izigqibo - kubizwa ngokuba. owazama ukuququzelela uhlaselo. eAnthony Stevens.
Cinga ngomnini wemali ye-crypto u-Alice, ekufuneka akhethe phakathi kokuthenga i-ice cream emnandi kuBob kunye nokuhlawula ityala likaCarol. Mhlawumbi uAlice ufuna ukubahlawula bobabini ngaxeshanye ngokusebenzisa ingqekembe enye ngobuqhetseba. Ukwenza oku, kufuneka aqinisekise ikhomputha kaBob ukuba ingqekembe ayizange ihlawulwe kuCarol, kwaye uqinisekise ikhompyutha kaCarol ukuba le ngqekembe ayizange ihlawulwe kuBob. Inkqubo yezivumelwano zeByzantine yenza oku kungenzeki, kusetyenziswa uhlobo lomthetho wesininzi obizwa ngokuba ikhoram. I-node kuthungelwano olunjalo luyala ukufudukela kwinguqulelo ethile yembali de ibone ukuba inani elaneleyo loontanga - ikhoram - iyavumelana nolo tshintsho. Xa oku kusenzeka, baya kwenza ibhloko yokuvota enkulu ngokwaneleyo ukuze banyanzelise iindawo zenethiwekhi eziseleyo ukuba zivumelane nesigqibo sabo. U-Alice unokunyanzela ezinye iindawo ukuba zixoke egameni lakhe, kodwa ukuba inethiwekhi inkulu ngokwaneleyo, umzamo wakhe uya koyiswa ngamavoti eendawo ezithembekileyo.
Mangaphi amaqhuqhuva afunekayo kwikhoram? Ubuncinci, uninzi, okanye kunoko, uninzi olufanelekileyo ukulwa neempazamo kunye nobuqhetseba. Kodwa ukubala uninzi, kufuneka wazi inani elipheleleyo labathathi-nxaxheba. Kwiofisi ye-Interstellar okanye kunyulo lwesithili, la manani kulula ukuwafumana. Kodwa ukuba iqela lakho linethiwekhi echazwe ngokukhululekileyo apho iinodi zinokungena kwaye zihambe ngokuthanda ngaphandle kwemvume evela kwiziko, uyafuna. federal inkqubo yesivumelwano saseByzantium ekwaziyo ukumisela ikhoram hayi kuluhlu olumiselweyo lweendawo, kodwa ngokuguquguqukayo, ukusuka kumfanekiso osoloko utshintsha nongapheleliyo weendawo ezithile ngexesha elinikiweyo.
Kusenokubonakala kungenakwenzeka ukwenza ikhoram ngokwembono yendawo enye kuthungelwano olukhulu, kodwa kuyenzeka. Ikhoram elolo hlobo inokuqinisekisa neziphumo zokuvota okunatyisiweyo. Iphepha elimhlophe le-SCP libonisa indlela yokwenza oku usebenzisa inkqubo ebizwa ngevoti yomanyano.
Kwabangenamonde
Elinye inqaku lichaza ukuvota okudibeneyo kunye ne-Stellar consensus protocol ngokubanzi. Ukuba awunamdla kwiinkcukacha, nantsi isishwankathelo senkqubo.
- Iindibano ziqhuba imijikelo yokuvota komdibaniso “kwabatyunjiweyo.” Umjikelo wokuvota womanyano uthetha:
- I-node ivotela enye ingxelo, umzekelo, "Ndiphakamisa ixabiso le-V";
- I-node iphulaphula amazwi oontanga ide ifumane enye "enokwamkela";
- Indawo ijonge "ikhoram" yesi simangalo. Ikhoram “iqinisekisa” umtyunjwa.
- Nje ukuba i-node iqinisekise umtyunjwa omnye okanye ngaphezulu, izama "ukulungiselela" "ibhalothi" ngemijikelo emininzi yokuvota okudibeneyo.
- Nje ukuba indawo yokuvota ikwazile ukuqinisekisa ukuba ivoti sele ilungile, izama ukulenza ngemijikelo engakumbi yokuvota.
- Nje ukuba i-node iqinisekise ukuzibophelela kwebhalothi, inokuthi "ikhuphe ngaphandle" ixabiso lelo bhalothi ngokuyisebenzisa njengesiphumo semvumelwano.
La manyathelo abandakanya imijikelo emininzi yovoto oludibeneyo, oludibanisa umjikelo omnye we-SCP. Makhe sihlolisise okwenzekayo kwinyathelo ngalinye.
Uvoto olumanyeneyo
Ukuvota okudibeneyo yinkqubo yokumisela ukuba inethiwekhi ingavumelana nesiphakamiso. Kumjikelo wokuvota, indawo nganye kufuneka ikhethe enye kumaxabiso amaninzi anokubakho. Ayinakukwenza oku ngaphandle kokuba iqinisekile ukuba ezinye ii-nodes kwinethiwekhi aziyi kukhetha umphumo ohlukileyo. Ukuqinisekisa oku, ii-nodes zitshintshiselana ngothotho lwemiyalezo emva naphambili ukuze wonke umntu kuqinisekiswa, oko ikhoram amaqhina ithatha kwinto enye isigqibo. Inxalenye yeli candelo ichaza amagama akwesi sivakalisi kunye nendlela yonke inkqubo eyenzekayo.
Iikhoram kunye nezilayi zekhoram
Masiqale ngokuchaza ikhoram. Njengoko sixoxile ngasentla, kuthungelwano lwe-decentralized network kunye nobulungu obuguqukayo, akunakwenzeka ukwazi kwangaphambili inani leendawo kwaye ngoko ke zingaphi ezifunekayo kwisininzi. Ukuvota okuManyeneyo kusombulula le ngxaki ngokuzisa umbono omtsha ukusika ikhoram (i-quorum slice): Iseti encinci yoontanga ethi i-node ithembe ukunxibelelana ngolwazi lobume bokuvota kuyo yonke inethiwekhi. Indawo nganye ichaza iquorum slice yayo (ethi ibe lilungu le-de facto).
Ukwenziwa kwekhoram kuqala ngokunqunyulwa kwekhoram. Kwi-node nganye, ii-nodes zayo ezisikiweyo zongezwa. Emva koko imimiselo yesilayi yongezwa ezi nodi kwaye nangokunjalo. Njengoko uqhubeka, kukho iindawo ezininzi ongenakuzongeza ngenxa yokuba sele zibandakanyiwe kwisilayi. Xa kungekho nodi ezintsha zokongeza, inkqubo iyayeka: senze ikhoram ngokuthi "ukuvalwa okuguquguqukayo" kwekhoram yesilayi yenode yokuqala.
Ukufumana ikhoram kwindawo enikiweyo...
... yongeza amalungu kwisilayi sayo...
...kwaye songeza amalungu esilayi kwezi nodi.
Siqhubeka de kungabikho iindawo eziseleyo zokongeza.
Akukho ndawo zishiyekileyo zokongeza. Le yikhoram.
Enyanisweni, i-node nganye inokuvela ngaphezu kwesilayi esinye. Ukwenza ikhoram, khetha enye kuphela yezilayi kwaye wongeze amalungu; uze ukhethe nasiphi na isilayi kwilungu ngalinye kwaye wongeze amalungu oku usike njalo njalo. Oku kuthetha ukuba indawo nganye yeendawo zokuhlala ililungu leekhoram ezininzi ezinokubakho.
Khetha kuphela isilayi sekhoram kwinyathelo ngalinye.
Ikhoram enye enokwenzeka. Okanye enye into...
...khetha ezinye izilayi...
…(xa kusenzeka)…
... yenza enye ikhoram.
I-node yazi njani ukuba zeziphi izilayi zezinye iindawo ezikuzo? Ngendlela efanayo nolunye ulwazi malunga namanye ama-nodes: ukusuka kwii-transmissions ukuba i-node nganye isasaza kwinethiwekhi xa imeko yokuvota itshintsha. Usasazo ngalunye lubandakanya ulwazi malunga nokuthumela izilayi zenodi. Iphepha elimhlophe le-SCP alichazi indlela yonxibelelwano. Ukwenziwa ngokuqhelekileyo kusetyenziswa yosasazo oluqinisekisiweyo lwemiyalezo kuthungelwano lonke.
Khumbula ukuba kwi-non-federal ye-Byzantine inkqubo yezivumelwano, ikhoram ichazwa njengoninzi lwazo zonke iindawo. Inkqubo yesivumelwano saseByzantine yenzelwe ukusuka kwindawo yokujonga umbuzo: zingaphi iinode ezinganyanisekanga ezinokunyamezela inkqubo? Kwinkqubo yeenodi ze-N eziyilelwe ukuba ziphile kwiintsilelo, indawo ekuyo kufuneka ikwazi ukwenza inkqubela ngokufumana ingxelo evela koontanga be-N-f kuba u-f wabo unokuba phantsi. Kodwa emva kokuba sifumene impendulo evela koontanga be-N-f, sinokucinga ukuba zonke iintanga (apho indawo engazange ifumane mpendulo) inyanisekile. Ngoko ke, oontanga baka-N-f (ekwafunyanwa kuyo impendulo) bakhohlakele. Ukuze iindawo zokuhlala zifikelele kwimvumelwano enye, uninzi lweendawo eziseleyo kufuneka zinyaniseke, oko kukuthi, sifuna i-N−f ibe nkulu kuno-2f okanye N > 3f. Ngoko ke ngokwesiqhelo inkqubo eyilelwe ukusinda f ukusilela iya kuba netotali ye-N=3f+1 nodi kunye nobungakanani bekhoram ye-2f+1. Nje ukuba isindululo siphumelele iquorum threshold, yonke inethiwekhi iqinisekile ukuba naziphi na izindululo ezikhuphisanayo ziya kusilela. Le yindlela inethiwekhi edibana ngayo kwisiphumo.
Kodwa kwinkqubo yesivumelwano saseByzantine federal, kungekhona nje kuphela ukuba akunakubakho buninzi (kuba akukho mntu uyazi ubungakanani obupheleleyo bothungelwano), kodwa ingcamango yobuninzi ayinamsebenzi ngokupheleleyo! Ukuba ubulungu kwinkqubo buvuliwe, ngoko umntu unokufumana isininzi ngokwenza into ebizwa ngokuba yi-Sybil attack: ukujoyina ngokuphindaphindiweyo inethiwekhi kwiindawo ezininzi. Ke kutheni kunokuthiwa ukuvalwa kwesilayi esiguqukayo ikhoram, kwaye ikwazi njani ukucinezela iziphakamiso ezikhuphisanayo?
Ngokobuchwephesha, akukho ndlela! Yiba nomfanekiso-ngqondweni wothungelwano lwamaqhina amathandathu, apho ii-triplets ezimbini zibekwe zodwa kwizilayi zekhorum zomnye. Iqela elincinane lokuqala linokwenza isigqibo esingenakuze sive ngaso elesibini, kwaye ngokuphambanayo. Akukho ndlela yokuba le nethiwekhi ifikelele kwimvumelwano (ngaphandle kwamathuba).
Ke ngoko, i-SCP ifuna ukuba kuvoto oludibeneyo (kwaye ukuze iithiyori ezibalulekileyo zephepha zisebenze), inethiwekhi kufuneka ibe nepropathi ebizwa ngokuba ukunqumlana kweekhoram. Kuthungelwano olunale propati, naziphi na iikhoram ezimbini ezinokwakhiwa zihlala ziwelana kwindawo enye ubuncinane. Ukumisela uluvo olukhoyo lwenethiwekhi, oku kufana nokuba nesininzi. Ngokuzenzekelayo, oku kuthetha ukuba ukuba nayiphina ikhoram iyavumelana nenkcazo X, akukho khoram eyenye inokuze ivumelane nayo nantoni na eyenye, kuba iyakubandakanya ngokuyimfuneko indawo ethile kwikhoram yokuqala esele ivotele u-X.
Ukuba kukho ukudibana kweekhoram kuthungelwano...
... ke naziphi na iikhoram ezimbini onokuthi uzakha...
...iyakuhlala inqumlana.
(Ngokuqinisekileyo, ii-nodes ezidibeneyo zingajika zibe yi-Byzantine-exokayo okanye ngenye indlela embi. Kule meko, i-quorum intersection ayincedi inethiwekhi ukuba ivumelane nonke. Ngenxa yesi sizathu, ezininzi iziphumo kwiphepha elimhlophe le-SCP zisekelwe Ingqikelelo ecacileyo, njengokushiyeka kuthungelwano lwekhoram yokunqumla nasemva kokususa iindawo ezimbi. Ukwenza lula, masizishiye ezi ngqikelelo ngokungafihli kwelinye inqaku).
Kungabonakala kungenangqiqo ukulindela ukuba ukuwela ikhoram ethembekileyo kunokwenzeka kuthungelwano lweenodi ezizimeleyo. Kodwa kukho izizathu ezibini zokuba kube njalo.
Isizathu sokuqala bubukho be-Intanethi ngokwayo. I-Intanethi ngumzekelo ogqibeleleyo wothungelwano lweenodi ezizimeleyo ezineekhoramu ezingenelayo. Uninzi lweendawo ezikwi-Intanethi ziqhagamshela kwezinye iindawo ezimbalwa zasekhaya, kodwa ezi seti zincinci zigqithana ngokwaneleyo kangangokuba indawo nganye inokufikelelwa kuyo yonke enye indawo ecaleni kwendlela ethile.
Isizathu sesibini sithe ngqo kwinethiwekhi yentlawulo ye-Stellar (ukusetyenziswa okuqhelekileyo kwe-SCP). Yonke i-asethi kwinethiwekhi ye-Stellar inomkhuphi, kwaye izikhokelo ze-Stellar zifuna ukuba umkhuphi ngamnye atyumbe i-nodes enye okanye ngaphezulu kwinethiwekhi ukuze kuqhutywe izicelo zokuhlengwa. Kungoyena mdla wakho ukubandakanya ngokuthe ngqo okanye ngokungathanga ngqo ezi nodi kwizilayi zekhoram nge-asethi nganye onomdla kuyo. Iikhoram zazo zonke iindawo ezinomdla kwi-asethi enikiweyo ziya kuthi zidlulelane ubuncinane kwezo ndawo zihlawulelweyo. Ii-Nodes ezinomdla kwii-asethi ezininzi ziya kubandakanya zonke iindawo zokuhlawulela zabakhuphi abahlukeneyo kwizilayi zabo zekhoram, kwaye baya kufuna ukuhlanganisa zonke ii-asethi kunye. Ukongeza, naziphi na ii-asethi ezingadityaniswanga ngale ndlela kwabanye kwinethiwekhi, kwaye akufuneki idityaniswe - oku kuyilwe ukuze kungabikho ukugqithelana kwekhoram kule nethiwekhi (umzekelo, iibhanki ezisuka kwi-dollar zone ngamanye amaxesha zifuna ukurhweba kunye neebhanki ezivela kwi-euro zone kunye neebhanki ezivela kwindawo ye-peso, ngoko ke zikwinethiwekhi efanayo, kodwa akukho nanye. kubo bakhathalele uthungelwano olwahlukileyo lwabantwana abathengisa amakhadi e-baseball).
Kakade, ulindelo ukunqumla ikhoram akunjalo isiqinisekiso. Ezinye iinkqubo zesivumelwano saseByzantine zityala kakhulu ubunzima bazo kwisiqinisekiso sekhoram. I-innovation ebalulekileyo ye-SCP kukuba isusa uxanduva lokudala ii-quorums kwi-algorithm yokuvumelana ngokwayo kwaye izisa kwinqanaba lesicelo. Ngoko ke, nangona ukuvota okumanyeneyo kubanzi ngokwaneleyo ukuba kuvotelwe kuwo nawuphi na umba, ukuthembeka kwawo eneneni kuxhomekeke ngokunzulu kwintsingiselo ebanzi yezi ntsingiselo. Olunye usetyenziso oluqikelelwayo lusenokungabi luncedo ekudaleni uthungelwano oluqhagamshelwe kakuhle njengabanye.
Ukuvota, ukwamkelwa kunye nokuqinisekiswa
Kumjikelo wokuvota odibeneyo, indawo ekhethwayo iqalisa ukuvotela ixabiso elithile. Xa i-node ivota ngale ndlela, ithembisa ukuba ayizange ivote ngokuchasene no-V kwaye ayisoze.
Kusasazo lwabalingane, indawo nganye ibona indlela abanye abavota ngayo. Nje ukuba indawo ethile iqokelele ngokwaneleyo le miyalezo, inokulandela izilayi zekhoram kwaye izame ukufumana ikhoram. Ukuba ubona ikhoram yoontanga nabo bavotela u-V, angaqhubeka ukwamkelwa V kwaye ndisasaze lo myalezo mtsha kuthungelwano: "Ndingu-N, izilayi zam zekhoram ngu-Q, kwaye ndiyamamkela u-V." Ukwamkelwa kunika isiqinisekiso esinamandla kunokuvota okulula. Xa i-node ivotela i-V, ayinakuze ivotele ezinye iinketho. Kodwa ukuba i node yamkela i-V, akukho nodi kuThungelwano eyakuze yamkele enye inketho (iTheorem 8 kwi SCP iphepha elimhlophe liyangqina oku).
Ngokuqinisekileyo, kukho amathuba aphezulu okuba akusayi kubakho ngokukhawuleza ikhoram yeenodi ezivumelana no-V. Ezinye iindawo zinokuvotela amanye amaxabiso. Kodwa kukho enye indlela yokuba i-node ihambe ukusuka ekuvoteni okulula ukuya ekwamkelweni. U-N unokwamkela ixabiso elahlukileyo ku-W, nokuba akazange ayivotele, kwaye nokuba akayiboni ikhoram yayo. Ukwenza isigqibo sokutshintsha ivoti yakho, jonga nje isethi yokubhloka iindawo zokuhlala ezithe zamkelwa W. Iseti yothintelo yindawo enye ukusuka kwisilayi ngasinye sekhoram N. Njengoko igama libonisa, ingakwazi ibhloko nayiphi na enye intsingiselo. Ukuba zonke iindawo ezikuluhlu olunjalo zamkela u-W, ngoko (nge-Theorem 8) akusoze kwenzeke ukuba kwenziwe ikhoram ethatha ixabiso elahlukileyo, kwaye ke ngoko kukhuselekile ku-N ukwamkela i-W.
INode N enezilayi zekhoram ezithathu.
I-BDF yiseti yokuthintela ye-N: ibandakanya indawo enye ukusuka kwisiqwenga ngasinye se-N.
I-BE ikwayi-blocking set ye-N kuba u-E uvela kwizilayi ezibini zika-N.
Kodwa iseti yokuthintela ayiyokhoram. Kuya kuba lula kakhulu ukukhohlisa i-node ye-N ekwamkeleni ixabiso elifunekayo ukuba kwakwanele ukukrazula i-node enye kwisiqwenga ngasinye se-N. Ngoko ke, ukwamkela ixabiso akukuphela kokuvota. Endaweni yoko, u-N kufuneka aqinisekise ixabiso, oko kukuthi, abone ikhoram yeenodi ezamkelayo. Ukuba ifikelela kude, ngoko ke, njengoko i-whitepaper ye-SCP iqinisekisa (kwi-Theorem 11), yonke inethiwekhi iya kuthi ekugqibeleni iqinisekise ixabiso elifanayo, ngoko i-N iya kuphelisa ivoti edibeneyo ngexabiso elithile njengesiphumo.
Uvoto olumanyeneyo.
Inkqubo yokuvota, ukwamkelwa, kunye nokuqinisekiswa kwenza umjikelo omnye opheleleyo wokuvota okumanyeneyo. Iprotocol ye-Stellar consensus idibanisa ezininzi zale mijikelezo ukudala inkqubo yokuvumelana ngokupheleleyo.
Iprotokholi yeMvumelwano yeStellar
Ezona mpawu zimbini zibalulekileyo zenkqubo yemvumelwano zezi − ukhuseleko и ukusinda. I-algorithm yokuvumelana "ikhuselekile" ukuba ayinakuze inike iziphumo ezahlukeneyo kubathathi-nxaxheba abahlukeneyo (ikopi yembali kaBob ayisoze iphikisana noCarol). "Ukuphila" kuthetha ukuba i-algorithm iya kuhlala ivelisa umphumo, oko kukuthi, ayiyi kubamba.
Kuchazwe inkqubo yokuvota yomanyano ikhuselekile ngengqiqo yokuba ukuba i-node iqinisekisa ixabiso lika-V, akukho nodi enye iya kuqinisekisa elinye ixabiso. Kodwa “ukungayi kuqinisekisa enye intsingiselo” akuthethi ukuba kuya kuqinisekisa into ethile. Abathathi-nxaxheba banokuvota kumaxabiso amaninzi ahlukeneyo kangangokuba akukho nto iya kufikelela kumda wokwamkelwa. Oku kuthetha ukuba kwivoti yomanyano akukho ukusinda.
I-Stellar consensus protocol isebenzisa ukuvota okudibeneyo ngendlela eqinisekisa ukhuseleko kunye nokuphila. (Ukhuseleko lwe-SCP kunye neziqinisekiso zokuphila zinomda wethiyori. Uyilo lukhetha isiqinisekiso sokhuseleko esomeleleyo, sincama ukuncitshiswa okuncinci kokusinda, kodwa kunikwe ixesha elaneleyo, ukuvumelana kunokwenzeka kakhulu ukuba kufikelelwe.) Ngamafutshane, umbono kukufumana iivoti ezininzi ezidibeneyo kumaxabiso amaninzi de enye yazo iyenze kuzo zonke izigaba zokuvota ze-SCP ezichazwe ngezantsi.
Amaxabiso apho i-SCP ifuna imvumelwano inokuba yimbali yentengiselwano okanye iodolo yesidlo sasemini okanye enye into, kodwa kubalulekile ukuqaphela ukuba ayingawo amaxabiso amkelweyo okanye aqinisekisiweyo. Endaweni yoko, ukuvota komanyano kwenzeka ngokutsho iinkcazo malunga nala maxabiso.
Imijikelo yokuqala yovoto lomdibaniso lwenzeka inqanaba lokutyunjwa (isigaba sokutyumba), kwiseti yeengxelo ezinje ngo "Ndityumba u-V," mhlawumbi kumaxabiso amaninzi ahlukeneyo ka-V. Injongo yokutyumba kukufumana ingxelo enye okanye ngaphezulu ehamba ngokwamkelwa kunye nokuqinisekiswa.
Emva kokufumana abaviwa abanokuqinisekiswa, i-SCP iqhubela phambili kwisigaba sokuvota, apho injongo kukufumana into ethile. ingxelo (oko kukuthi, isingxobo sexabiso elicetywayo) kunye nekhoram enokuthi ichaze zibophelele ngayo (zibophelele). Ukuba ikhoram yenza uvoto, ixabiso layo lamkelwa njengemvumelwano. Kodwa ngaphambi kokuba i-node ivote kwisibophelelo sokuvota, kufuneka kuqala iqinisekise ukurhoxiswa zonke iivoti ezinexabiso eliphantsi lokubala. La manyathelo-ukurhoxisa iivoti ukufumana enye enokuzinikela-ibandakanya imijikelo emininzi yokuvota okudibeneyo kumabango amaninzi okuvota.
La macandelo alandelayo achaza ukutyunjwa nokuvota ngokubanzi.
Ukutyunjwa
Ekuqaleni kwesigaba sokutyumba, indawo nganye inodi inokukhetha ngokuzenzekelayo ixabiso lika-V kwaye ivotele ingxelo ethi “Ndityumba u-V.” Injongo kweli nqanaba kukuqinisekisa ukutyunjwa kwexabiso elithile ngevoti edibeneyo.
Mhlawumbi iindawo ezaneleyo zivotela izindululo ezahlukeneyo ngokwaneleyo ukuba akukho tyumbo linokufikelela kumda wokwamkelwa. Ke ngoko, ukongeza ekusasazeni iivoti zabo zokutyumba, iindawo “zibonisa” ukutyunjwa koontanga babo. I-Echo ithetha ukuba i-node ivotela ukutyunjwa kwe-V, kodwa ibona umyalezo ovela kummelwane uvotela ukutyunjwa kwe-W, ngoku iya kuvotela bobabini u-V kunye no-W. I-SCP ibandakanya indlela yokulawula ezi voti.Ngamafutshane, kukho indlela yokumisela "into ephambili" yoontanga ngokwembono yenode, kwaye kuphela ziivoti zeendawo eziphambili ngokubaluleka ezibonakaliswayo.Okukhona kutyunjwa ixesha elide. ithatha, isezantsi i-threshold, ngoko i-node yandisa iseti yeentanga zabo eza kubonisa iivoti zabo. enye, kwaye ngokuphambeneyo).
Ngokwengqiqo, utyumbo luyahambelana, zombini u-V kunye no-W ziivoti zomdibaniso ezahlukeneyo, ngamnye ekwazi ukufumana ukwamkelwa okanye ukuqinisekiswa. Ngokwesiqhelo, imiyalezo yeprotocol ye-SCP ipakisha ezi voti zomntu ngamnye kunye.
Nangona ukuvotela ukutyunjwa kuka-V kuyisithembiso sokungaze uvote ngokuchasene nokutyunjwa kuka-V, kukwinqanaba lesicelo - kule meko i-SCP - ukuba kunqunywe ukuba "ngokuchaseneyo" kuthetha ntoni. I-SCP ayiboni inkcazo ephikisana nevoti ethi "Ndityumba i-X", oko kukuthi, akukho "ndichasene nokutyumba u-X" umyalezo, ngoko i-node inokuvota ukutyumba nawaphi na amaxabiso. Uninzi lwaba batyunjiweyo aluyi kuya ndawo, kodwa ekugqibeleni i-node iya kuba nako ukwamkela okanye ukuqinisekisa ixabiso elinye okanye ngaphezulu. Xa umtyunjwa eqinisekisiwe, uba nguye umviwa.
Ukutyunjwa kwe-SCP kusetyenziswa ukuvota okumanyeneyo. Kunokubakho amanani amaninzi "B" abekwe phambili ngoontanga kwaye "ibonakaliswe" yi-node.
Ulonyulo lunokubangela ukuba kubekho abagqatswa abaninzi abaqinisekisiweyo. Ke ngoko, i-SCP ifuna umaleko wesicelo ukubonelela ngeendlela ezithile zokudibanisa abaviwa babe nye indibaniselwano (intlanganisela). Indlela yokudibanisa ingaba nantoni na. Into ephambili kukuba ukuba le ndlela i-deterministic, ngoko i-node nganye iya kudibanisa abaviwa abafanayo. Kwinkqubo yokuvota yesidlo sasemini, "ukumanyana" kusenokuthetha ukwala omnye wabagqatswa ababini. (Kodwa ngendlela yokuqinisekisa: indawo nganye kufuneka ikhethe ixabiso elifanayo ukusetwa kwakhona. Umzekelo, ukhetho lwangaphambili ngokolandelelwano lwealfabhethi). Kwinethiwekhi yentlawulo ye-Stellar, apho imbali yokuthengiselana ivotelwe khona, ukudibanisa abatyunjwa ababini abacetywayo kubandakanya ukudibanisa ukuthengiselana abakuquletheyo kunye nokugqibela kwezitampu zabo ezimbini.
Iphepha elimhlophe le-SCP libonisa (i-Theorem 12) ukuba ekupheleni kwesigaba sokwandiswa, inethiwekhi ekugqibeleni idibanisa kwi-composite enye. Kodwa kukho ingxaki: ukuvota okudibeneyo yiprothokholi engavumelaniyo (njenge-SCP). Ngamanye amazwi, ii-nodes azilungelelaniswa ngexesha, kodwa kuphela ngemiyalezo abayithumelayo. Ngokombono we-node, akucaci ukuba nini iphelile isigaba sokwandiswa. Kwaye nangona zonke iindawo ezidibeneyo ziya kuthi ekugqibeleni zifike kwindawo enye, zinokuthatha iindlela ezahlukeneyo endleleni, zidala abaviwa abadityanisiweyo abahlukeneyo endleleni, kwaye abanakuze batsho ukuba yeyiphi eyona yokugqibela.
Kodwa yinto eqhelekileyo. Ulonyulo lulungiselelo nje. Into ephambili kukukhawulela inani labaviwa ukuba bafezekise ukuvumelana, okwenzeka kwinkqubo ukubaleka isikhundla (ukuvota).
Ukubaleka
Bulletin sisibini , apho ikhawuntala iyinani elipheleleyo eliqala ku-1 kwaye ixabiso lingumgqatswa osuka kwinqanaba lonyulo. Oku kunokuba ngumgqatswa we-node ngokwakhe okanye umgqatswa we-node engummelwane owamkelwe yile nodi. Ukuthetha nje, ukuvota kubandakanya iinzame eziphindaphindiweyo zokunyanzela inethiwekhi ukuba ifikelele kwimvumelwano yomgqatswa othile kwivoti ethile ngokubamba iivoti ezininzi ezidibeneyo kwiingxelo zokuvota. Izixhobo zokubala kwiivoti zigcina umkhondo wemizamo eyenziweyo, kwaye iivoti ezinamanani aphezulu zithatha indawo yokuvota ngamanani aphantsi. Ukuba incwadana uyaxinga, ivoti entsha iyaqala, ngoku kwivoti .
Kubalulekile ukwahlula iinqobo ezisemgangathweni (umzekelo, kufuneka ibe yintoni iodolo yesidlo sasemini: ipizza okanye iisaladi), iincwadi zeendaba (i-counter-value pair) kunye iingxelo malunga namavoti. Umjikelo we-SCP ubandakanya imijikelo eliqela yokuvota komanyano, ngakumbi kwezi nkcazo zilandelayo:
- "Ndikulungele ukwenza uvoto B" kunye
- "Ndibhengeza ukuzibophelela kwebhalothi B"
Ngokwembono yendawo enikiweyo, imvumelwano iyafikelelwa xa ifumana ivoti B enokuqinisekisa ngayo (oko kukuthi, ukufumana ikhoram eyamkelekileyo) intetho ethi "Ndivota B." Ukususela kweli nqanaba, kukhuselekile ukwenza kwixabiso elichazwe kwi-B - umzekelo, ukubeka lo myalelo wesidlo sasemini. Ibizwa ngokuba ngaphandle iintsingiselo. Emva kokuba ukwamkelwa kwevoti kuqinisekisiwe, i-node inokuqiniseka ukuba nayiphi na enye i-node iye yangaphandle kwixabiso elifanayo okanye iya kwenza njalo kwixesha elizayo.
Nangona iivoti ezininzi ezimanyeneyo ziqhutywa ngokwengqiqo kumabango eevoti ezininzi ezahlukeneyo, azitshintshiselani ngemiyalezo emininzi kuba umyalezo ngamnye uquka inani leevoti. Ngaloo ndlela omnye umyalezo ukhuthaza imeko yeevoti ezininzi ezimanyeneyo ngaxeshanye, umzekelo: “Ndivuma ukuvota ukususela ngaphambili "
Lithetha ukuthini igama elithi “ukulungiselela” nelithi “ukuzibophelela”?
I-node ivoti ukwenza ivoti xa iqinisekile ukuba ezinye iindawo aziyi kuvota ngeendidi ezahlukeneyo. Ukukholisa oku kuyinjongo yokulungiselela isicelo. Ivoti ethi "Ndikulungele ukwenza ivoti B" sisithembiso sokuba ungaze wenze ivoti encinci kune-B, oko kukuthi ngenani elincinci (i-SCP ifuna ukuba amaxabiso kwiivoti abe ngolandelelwano oluthile. Ngaloo ndlela, incwadana yeendaba Ngaphantsi , ukuba u-N1
Kutheni le nto “Ndikulungele ukwenza ukuvota B” kuthetha ukuba “Ndiyathembisa ukuba asoze ndivote kancinci kuno-B”? Kuba i-SCP ichaza ukukhupha isisu njengesichasi sokuzibophelela. Ivoti yokulungiselela uvoto ikwabandakanya ivoti yokungafanelanga ezinye iivoti, kwaye, njengoko besixoxile ngaphambili, ukuvotela into enye sisithembiso sokungaze uvote ngokuchasene nayo.
Ngaphambi kokusasaza isibophelelo, indawo yokusebenzela kufuneka iqale ifumane ibhulethini enokuqinisekisa njengoko ilungisiwe. Ngamanye amazwi, lenza ivoti emanyeneyo kumxholo othi “Ndikulungele ukwenza ivoti B,” mhlawumbi kwiivoti ezininzi ezahlukeneyo, de ifumane owamkela ikhoram.
Zivela phi iivoti ukulungiselela ukuvota? Okokuqala, i-node isasaza amalungiselelo okuvotela i-<1,C>, apho i-C ingumgqatswa odibeneyo oveliswe kwinqanaba lokutyunjwa. Nangona kunjalo, nasemva kokuba amalungiselelo okuvota eqalisiwe, unyulo lunokubangela ukuba abanye abagqatswa abongezelelekileyo babonakale bengabavoti abatsha. Okwangoku, oontanga banokuba nabaviwa abahlukeneyo kwaye banokwenza isethi yokuthintela eyamkela "Ndikulungele ukwenza ivoti ye-B2" eya kuqinisekisa i-node ukuba iyamkele nayo. Okokugqibela, kukho indlela yokuvala ixesha eyenza imijikelo emitsha yokuvota okumanyeneyo kwiivoti ezintsha ezinamanani aphezulu ukuba iivoti zangoku zibambekile.
Nje ukuba indawo yokuvota ifumane ibhalothi engu-B enokuqinisekisa njengoko ilungisiwe, isasaza umyalezo omtsha “Zinikele ngebhalothi B.” Le voti ixelela oontanga ukuba i-node ayisoze yanikezela i-B. Enyanisweni, ukuba i-B yivoti , emva koko “Zibophelele ngevoti "ithetha imvume engenamiqathango yokuvotela ukulungela ukuvota ngakunye ukuya <∞, s>. Eli xabiso elongezelelweyo linceda abanye oontanga ukuba babambene nentanga yokuzibophelela ukuba basekwizigaba zangaphambili zeprotocol.
Kweli nqanaba, kufanelekile ukuba kugxininiswe kwakhona ukuba ezi ziprothokholi ezingavumelaniyo. Kungenxa yokuba enye i-node ithumela iivoti zokuzibophelela ayithethi ukuba oontanga bayo benza njalo. Abanye babo basenokuvota kwiingxelo zokulungiselela ukuvota, abanye basenokuba sele beyikhuphele ngaphandle intsingiselo. I-SCP ichaza indlela i-node kufuneka iqhube ngayo uhlobo ngalunye lomyalezo wontanga kungakhathaliseki ukuba sisiphi isigaba.
Ukuba umyalezo "Ndibhengeze ukuzibophelela » ayinakufunyanwa okanye ingqinisiswe, oko kukuthi, amathuba okuba umyalezo wamkelwe okanye uqinisekiswe okanye - okanye, kuyo nayiphi na imeko, nayiphi na ibhalothi enexabiso C, kwaye hayi nayiphi na enye, ekubeni indawo esele ithembisile ukuba ayisoze irhoxise. . Ngexesha i-node isasaza iivoti zokuzibophelela, iya kuba yi-C okanye akukho nto, kuxhomekeke ekubeni isivumelwano siya kude kangakanani. Nangona kunjalo, oku akukabikho ngokwaneleyo ukuba i-node ikhuphe ngaphandle C. Abanye oontanga baseByzantine (ababandakanya ngaphantsi kwe-quorum, ngokusekelwe kwiingcamango zethu zokhuseleko) banokuxoka kwi-node. Ukwamkela kunye nokuqinisekisa ibhalothi ethile (okanye uluhlu lweevoti) yinto enika indawo ukuzithemba ekugqibeleni uC.
Ukuvota kwe-SCP ngokuvota okumanyeneyo. Ayiboniswanga: Isibali-xesha sinokuhamba nangaliphi na ixesha, sisonyusa isibalo kwivoti (kwaye mhlawumbi sivelise indibaniselwano entsha yabagqatswa abongezelelweyo abakhethiweyo).
Kwaye konke! Nje ukuba inethiwekhi ifikelele kwimvumelwano, ikulungele ukuyenza kwakhona kwaye kwakhona. Kuthungelwano lwentlawulo ye-Stellar, oku kwenzeka kanye rhoqo ngemizuzwana emi-5: into efuna zombini ukhuseleko kunye nokuphila okuqinisekiswe yi-SCP.
I-SCP inokuphumeza oku ngokuthembela kwimijikelo emininzi yokuvota okumanyeneyo. Ukuvota okuManyeneyo kwenziwa ukuba kwenzeke ngumbono wekhoram izilayi: iiseti zoontanga apho indawo nganye egqibe ukuba iyithembe njengenxalenye yekhoram (yesifundo). Olu lungelelwaniso luthetha ukuba imvumelwano inokufikelelwa nakwinethiwekhi enobulungu obuvulekileyo kunye neenkohliso zaseByzantine.
Ukuqhubeka kokufunda
- Iphepha elimhlophe le-SCP loqobo lingafunyanwa , kwaye idrafti yeenkcukacha zokuphunyezwa kwayo.
- Umbhali wokuqala weprotocol ye-SCP, uDavid Mazier, uyichaza ngendlela elula (kodwa isenobugcisa). .
- Usenokumangaliswa ukuba ungafumani amagama athi "imigodi" okanye "ubungqina bomsebenzi" kweli nqaku. I-SCP ayisebenzisi ezi ndlela, kodwa ezinye ii-algorithms zemvumelwano zenza. Zane Witherspoon wabhala ukufikelela .
- inethiwekhi elula efikelela kwimvumelwano kumjikelo omnye opheleleyo we-SCP.
- Kubafundi abanomdla kuphunyezo lwe-SCP: bona , esetyenziswa yinethiwekhi yentlawulo yeStellar, okanye , endiyibhalele ukuqonda okungcono kwe-SCP.
umthombo: www.habr.com