I-Stellar consensus protocol yachazwa kuqala ku UDavid Mazier ngo-2015. Lolu "uhlelo lwesivumelwano se-federal Byzantine" oluvumela amanethiwekhi ekhompuyutha ahlukaniswe, angenabo abaholi ukuthi afinyelele ukuvumelana ngesinqumo. Inethiwekhi yokukhokha ye-Stellar isebenzisa i-Stellar Consensus Protocol (SCP) ukuze igcine umlando wokwenziwe ongaguquki obonakala kubo bonke abahlanganyeli.
Izivumelwano zokuvumelana zibhekwa njengezinzima ukuziqonda. I-SCP ilula kuneningi lazo, kodwa isabelana ngaleli sithunzi - ngokwengxenye ngenxa yombono oyiphutha wokuthi "ukuvota okuhlangene", okuyisihloko sengxenye yokuqala ye-athikili yesayensi, yi-SCP. Kodwa lokho akulona iqiniso! Lesi yisakhiwo esibalulekile esisetshenziswa ingxenye yesibili ye-athikili ukuze sidale okwangempela I-Stellar consensus protocol.
Kulesi sihloko sizochaza kafushane ukuthi "isimiso sezivumelwano" siyini, yini engayenza "i-Byzantine" nokuthi kungani yenza uhlelo lwaseByzantine "federal". Sizobe sesichaza inqubo yokuvota ehlanganisiwe echazwe esihlokweni se-SCP, futhi ekugcineni sizochaza umthetho olandelwayo we-SCP ngokwawo.
Izinhlelo zesivumelwano
Uhlelo lwezivumelwano luvumela iqembu labahlanganyeli ukuthi lifinyelele ukuvumelana ngesihloko, njengokuthi yini okufanele i-odwe ngesidlo sasemini.
Kwa-Interstellar, sisebenzise uhlelo lwethu lwesivumelwano sokudlela: si-oda okushiwo umphathi wethu wokusebenza, uJohn. Lolu uhlelo lwesivumelwano olulula nolusebenzayo. Sonke siyamethemba uJohn futhi sikholelwa ukuthi uzothola okuthile okuthakazelisayo nokunomsoco nsuku zonke.
Kodwa kuthiwani uma uJohn esebenzisa kabi ukwethemba kwethu? Anganquma eyedwa ukuthi sonke kufanele sibe ama-vegans. Esikhathini esingangesonto noma amabili, cishe sizomketula futhi sinikeze u-Elizabeth amandla. Kodwa ngokuzumayo uthanda ukwatapheya ngama-anchovies futhi ucabanga ukuthi wonke umuntu kufanele abe njalo. Amandla onakalisa. Ngakho-ke kungcono ukuthola enye indlela yentando yeningi: indlela ethile yokuqinisekisa ukuthi okuthandwayo okuhlukile kuyacatshangelwa, kuyilapho uqinisekisa umphumela ofika ngesikhathi futhi ongenambangi, ukuze kungabikho muntu ogcina e-oda ukudla kwasemini, noma abantu abahlanu bafake ama-oda ahlukene, noma ingxoxo. idonsa kuze kube kusihlwa.
Kungase kubonakale sengathi isisombululo silula: bamba ivoti! Kodwa lokhu kuwumbono odukisayo. Ubani ozoqoqa amavoti futhi abike imiphumela? Futhi kungani kufanele abanye bakukholelwe akushoyo? Mhlawumbe singakwazi ekuqaleni sivotele umholi esimethembayo ukuthi nguyena ozohola ukuvota - kodwa ozohola kuqala ngokuvota? Kuthiwani uma singavumelani ngomholi? Noma kuthiwani uma sifinyelela esivumelwaneni, kodwa lo mholi abambeke emhlanganweni noma ahambe ekhefini lokugula?
Izinkinga ezifanayo zenzeka kumanethiwekhi ekhompyutha asabalalisiwe. Bonke ababambiqhaza noma amanodi kufanele bavumelane ngesinqumo esithile, njengokuthi kuyithuba likabani lokubuyekeza ifayela elabelwe noma ukususa umsebenzi kulayini wokucubungula. Kunethiwekhi ye-cryptocurrency, ama-node kufanele akhethe ngokuphindaphindiwe ukuthi indaba egcwele ibukeka kanjani ezinguqulweni ezimbalwa ezingenzeka, ngezinye izikhathi eziphikisanayo. Lesi sivumelwano senethiwekhi sinikeza isiqinisekiso kumamukeli sokuthi uhlamvu lwemali (a) luvumelekile (hhayi okomgunyathi) futhi (b) alukakasetshenziswa kwenye indawo. Lokhu futhi kuqinisekisa ukuthi uzokwazi ukusebenzisa izinhlamvu zemali esikhathini esizayo ngoba umamukeli omusha uzoba neziqinisekiso ezifanayo ngezizathu ezifanayo.
Noma iyiphi isistimu yokuvumelana kunethiwekhi yekhompuyutha esabalalisiwe kufanele ibekezelele amaphutha: kufanele ikhiqize imiphumela engaguquki naphezu kwamaphutha afana nezixhumanisi ezihamba kancane, ama-node angaphenduli, noku-oda komlayezo okungalungile. I-Byzantine Uhlelo lwesivumelwano ngaphezu kwalokho luyamelana namaphutha "e-Byzantine": izindawo ezinikeza ulwazi olungamanga, noma ngabe kungenxa yephutha noma ngomzamo wamabomu wokubukela phansi uhlelo noma ukuzuza okuthile. "Byzantine" ukubekezelelana kwamaphutha - ikhono lokwethemba isinqumo seqembu ngisho nalapho amanye amalungu eqembu eqamba amanga noma angalandeli imithetho yokuthatha izinqumo - kubizwa ngokuthi. owazama ukuxhumanisa ukuhlasela. ku-Anthony Stevens.
Cabanga ngomnikazi wemali ye-crypto u-Alice, okufanele akhethe phakathi kokuthenga u-ayisikhilimu omnandi ku-Bob nokukhokha isikweletu sikaCarol. Mhlawumbe u-Alice ufuna ukubakhokhela bobabili ngesikhathi esisodwa ngokusebenzisa umkhonyovu uhlamvu lwemali olufanayo. Ukuze enze lokhu, kufanele akholise ikhompuyutha kaBob ukuthi uhlamvu lwemali aluzange lukhokhelwe uCarol, futhi akholise ikhompuyutha kaCarol ukuthi uhlamvu lwemali aluzange lukhokhelwe uBob. Uhlelo lwezivumelwano zaseByzantium lwenza lokhu kungenzeki nhlobo, kusetshenziswa uhlobo lomthetho weningi olubizwa ngokuthi ikhoramu. I-node kunethiwekhi enjalo yenqaba ukuthuthela enguqulweni ethile yomlando kuze kube yilapho ibona ukuthi inani elanele lontanga - ikhoramu - iyavumelana nenguquko enjalo. Uma lokhu sekwenzekile, bazokwakha ibhulokhi yokuvota enkulu ngokwanele ukuphoqa amanodi enethiwekhi asele ukuthi avumelane nesinqumo sabo. U-Alice angaphoqa amanye ama-node ukuthi amqambele amanga, kodwa uma inethiwekhi inkulu ngokwanele, umzamo wakhe uzokhungathekiswa amavoti ama-node athembekile.
Mangaki amanodi adingekayo kwikhoramu? Okungenani, iningi, noma kunalokho, iningi elifanelekayo lokulwa namaphutha nokukhwabanisa. Kodwa ukuze ubale iningi, udinga ukwazi inani eliphelele lababambe iqhaza. Ehhovisi le-Interstellar noma okhethweni lwesifunda, lezi zinombolo kulula ukuzithola. Kodwa uma iqembu lakho liyinethiwekhi echazwe ngokukhululekile lapho ama-node angangena futhi ahambe ngokuthanda ngaphandle kwemvume evela esikhungweni, udinga federal uhlelo lwesivumelwano saseByzantium olukwazi ukunquma amakhoramu hhayi ohlwini olunqunywe kusengaphambili lwamanodi, kodwa ngokuguquguqukayo, kusukela kusifinyezo esishintsha njalo nesingaphelele samanodi ngesikhathi esithile.
Kungase kubonakale kungenakwenzeka ukwakha ikhoramu ngokombono wenodi eyodwa kunethiwekhi enkulu, kodwa kuyenzeka. Ikhoramu enjalo ingaqinisekisa ngisho nemiphumela yokuvota okuhlukaniselwe izindawo. Iphepha elimhlophe le-SCP libonisa ukuthi kwenziwa kanjani lokhu kusetshenziswa inqubo ebizwa ngevoti lenhlangano.
Kwabanesineke
Esinye isihloko sichaza ukuvota okuhlangene kanye ne-Stellar consensus protocol ngokuningiliziwe. Uma ungenayo intshisekelo emininingwaneni, nansi ukubuka konke okujwayelekile kwenqubo.
- Ama-node enza imijikelezo yokuvota kwenhlangano “kwabaqokiwe.” Umjikelezo wokuvota wenhlangano usho:
- I-node ivotela isitatimende esithile, isibonelo, “Ngiphakamisa inani lika-V”;
- I-node ilalela amazwi ontanga kuze kube yilapho ithola eyodwa engakwazi "ukwamukela";
- I-node ibheka "ikhoramu" yalokhu kugomela. Ikhoramu “iqinisekisa” oqokiwe.
- Uma indawo ingaqinisekisa oyedwa noma abaningi abaqokiwe, izama "ukulungiselela" "ivoti" ngemijikelezo eminingana yokuvota okuyinhlangano.
- Uma i-node isikwazi ukuqinisekisa ukuthi ivoti selilungile, izama ukulenza ngemijikelezo eyengeziwe yokuvota okuyinhlangano.
- Uma i-node ingaqinisekisa ukuzinikela kwevoti, "ingakwazi ukukhipha" inani lalelo bhalothi ngokulisebenzisa njengomphumela wokuvumelana.
Lezi zinyathelo zifaka imijikelezo eminingi yokuvota okuyinhlangano, okuhlanganisa umjikelezo owodwa we-SCP. Ake sihlolisise ukuthi kwenzekani esinyathelweni ngasinye.
Ukuvota okuhlanganisiwe
Ukuvota okuhlangene kuyinqubo yokunquma ukuthi inethiwekhi ingavumelana yini ngesiphakamiso. Emzuliswaneni wokuvota, indawo ngayinye kufanele ikhethe inani elilodwa kwabaningi okungenzeka bangaba khona. Ayikwazi ukwenza lokhu ngaphandle uma iqiniseka ukuthi amanye ama-node kunethiwekhi ngeke akhethe umphumela ohlukile. Ukuqinisekisa lokhu, ama-node ashintshanisa inqwaba yemiyalezo emuva naphambili ukuze wonke umuntu ukuqinisekisile, lokho ikhoramu amafindo yemukela into efanayo isinqumo. Okunye kwalesi sigaba kuchaza imigomo kulo musho nokuthi yonke inqubo yenzeka kanjani.
Ikhoramu nezingcezu zekhoramu
Ake siqale ngokuchaza ikhoramu. Njengoba sixoxile ngenhla, kunethiwekhi ehlukanisiwe enobulungu obunamandla, akunakwenzeka ukwazi kusengaphambili inani lama-node ngakho-ke mangaki adingekayo kuningi. Ukuvota okuhlangene kuyixazulula le nkinga ngokwethula umbono omusha ukunqunywa kwekhoramu (i-quorum slice): Isethi encane yontanga i-node ethembela kuyo ukuze idlulisele ulwazi lwesimo sokuvota kuyo yonke inethiwekhi. I-node ngayinye ichaza ucezu lwayo lwekhoramu (okuyinto eba yilungu le-de facto).
Ukwakhiwa kwekhoramu kuqala ngokusikwa kwekhoramu. Ku-node ngayinye, ama-node ayo anqunyiwe ayengezwa. Khona-ke imigomo yesiqephu iyengezwa lawa ma-node njalo njalo. Njengoba uqhubeka, ayanda ama-node ongeke ukwazi ukuwangeza ngoba asefakiwe ocezwini. Uma engasekho ama-node amasha esizongezwa, inqubo iyama: senze ikhoramu “ngokuvalwa okuguquguqukayo” kocezu lwekhoramu lwenodi yokuqala.
Ukuthola ikhoramu endaweni ethile...
... engeza amalungu ocezu lwawo...
...bese sengeza amalungu ocezu kulawa ma-node.
Siqhubeka kuze kube yilapho engekho amanodi asele ukuze sengezwe.
Awekho amanodi asele ongawengeza. Lena ikhoramu.
Eqinisweni, i-node ngayinye ingavela kucezu olungaphezu kolulodwa. Ukwakha ikhoramu, khetha eyodwa kuphela yezingcezu bese wengeza amalungu; bese ukhetha noma yiluphi ucezu lwelungu ngalinye bese wengeza amalungu salokhu ukusika nokunye. Lokhu kusho ukuthi inodi ngayinye iyilungu lamakhoramu amaningi angaba khona.
Khetha ucezu lwekhoramu olulodwa kuphela esinyathelweni ngasinye.
Ikhoramu eyodwa engenzeka. Noma okunye...
...khetha ezinye izingcezu...
…(uma kungenzeka)…
... kudala enye ikhoramu.
I-node yazi kanjani ukuthi yiziphi izingcezu amanye amanodi akuzo? Ngendlela efanayo nolunye ulwazi mayelana namanye ama-node: kusukela ekudluliseni ukuthi i-node ngayinye isakaza kunethiwekhi lapho isimo sayo sokuvota sishintsha. Ukusakaza ngakunye kufaka phakathi ulwazi mayelana nezingcezu zenodi yokuthumela. Iphepha elimhlophe le-SCP aliyichazi indlela yokuxhumana. Imikhiqizo ngokuvamile isetshenziswa ukusakazwa okuqinisekisiwe kwemilayezo kuyo yonke inethiwekhi.
Khumbula ukuthi ohlelweni lwezivumelwano lwe-Byzantine okungeyona eyenhlangano, ikhoramu ichazwa njengeningi lawo wonke ama-node. Uhlelo lwesivumelwano saseByzantine luklanywe kusukela ekubukeni kombuzo: mangaki ama-node angathembekile uhlelo olungawabekezelela? Ohlelweni lwamanodi angu-N aklanyelwe ukusinda ekuhlulekeni, indawo kufanele ikwazi ukwenza inqubekelaphambili ngokuthola impendulo evela kontanga be-N-f njengoba u-f wabo engase abe phansi. Kodwa njengoba sithole impendulo kontanga yakwa-N-f, singacabanga ukuthi bonke ontanga (lapho i-node ingazange ithole impendulo) bathembekile ngempela. Ngakho-ke, kontanga yakwa-N-f (okwatholwa kubo impendulo) banonya. Ukuze ama-node afinyelele ekuvumelaneni okufanayo, iningi lama-node asele kufanele athembeke, okungukuthi, sidinga i-N−f ukuze ibe nkulu kuno-2f noma N > 3f. Ngakho-ke ngokuvamile isistimu eklanyelwe ukusinda ekuhlulekeni kuka-f izoba nengqikithi yamanodi angu-N=3f+1 kanye nosayizi wekhoramu ongu-2f+1. Uma isiphakamiso sesidlulile umkhawulo wekhoramu, yonke inethiwekhi iyaqiniseka ukuthi noma yiziphi iziphakamiso eziqhudelanayo zizohluleka. Lena yindlela inethiwekhi ihlangana ngayo ukuze ibe umphumela.
Kodwa ohlelweni lwesivumelwano se-Byzantine federal, hhayi nje kuphela ukuthi ngeke kube neningi (ngoba akekho owazi usayizi ophelele wenethiwekhi), kodwa umqondo weningi awunamsebenzi ngokuphelele! Uma ubulungu ohlelweni buvuliwe, khona-ke othile angathola iningi ngokwenza lokho okubizwa ngokuthi ukuhlasela kwe-Sybil: ukujoyina inethiwekhi ngokuphindaphindiwe ezindaweni eziningi. Ngakho kungani kungabizwa ngokuthi ukuvalwa kocezu olushintshayo ikhoramu, futhi ikwazi kanjani ukucindezela iziphakamiso eziqhudelanayo?
Ngobuchwepheshe, akukho ndlela! Cabanga ngenethiwekhi yamanodi ayisithupha, lapho ama-triplets amabili ehlukene ezinceleni zekhoramu zomunye nomunye. Iqembu lokuqala lingase lenze isinqumo elesibili elingeke lizwe ngaso, futhi okuphambene nalokho. Ayikho indlela yokuthi le nethiwekhi ifinyelele ukuvumelana (ngaphandle kwenhlanhla).
Ngakho-ke, i-SCP idinga ukuthi ukuze kuvotelwe izinhlangano (futhi ukuze kusetshenziswe ithiyori ebalulekile yephepha), inethiwekhi kufanele ibe nendawo ebizwa ngokuthi. ukuhlangana kwamakhoramu. Kunethiwekhi enalesi sakhiwo, noma yimaphi amakhoramu amabili angakhiwa ahlala edlula okungenani endaweni eyodwa. Ukuze kutholwe imizwa ekhona yenethiwekhi, lokhu kufana nokuba neningi. Ngokuqondayo, lokhu kusho ukuthi uma noma iyiphi ikhoramu evuma isitatimende X, ayikho enye ikhoramu engavumelana nanoma yini enye, ngoba izofaka phakathi i-node ethile evela kwikhoramu yokuqala eseyivotele u-X.
Uma kunokuhlangana kwekhoramu kunethiwekhi...
...khona-ke noma yimaphi amakhoramu amabili ongawakha...
... iyohlala iphambana.
(Kunjalo, ama-node agqagqene angase abonakale eqamba amanga e-Byzantine noma ngenye indlela embi. Kulokhu, ukuphambana kwekhoramu akusizi inethiwekhi nhlobo ukuba ivumelane. Ngenxa yalesi sizathu, imiphumela eminingi ephepheni elimhlophe le-SCP isuselwe ku- ukucatshangelwa okusobala, okufana nalokho okusele ekuweleni isibalo senethiwekhi ngisho nangemva kokukhipha ama-node amabi. Ukuze kube lula, masiyishiye le mibono sobala kuso sonke isiqephu sendatshana).
Kungase kubonakale kungenangqondo ukulindela ukuthi ukweqa ikhoramu okuthembekile kungenzeka kunethiwekhi yamanodi azimele. Kodwa kunezizathu ezimbili ezenza kube njalo.
Isizathu sokuqala ukuba khona kwe-inthanethi ngokwayo. I-inthanethi iyisibonelo esiphelele senethiwekhi yamanodi azimele anamakhoramu ahlanganayo. Amanodi amaningi aku-inthanethi axhuma kwamanye amanodi endawo ambalwa, kodwa lawa masethi amancane adlulela ngokwanele kangangokuthi yonke indawo ingafinyelelwa kuzo zonke ezinye izindawo eduze komzila othile.
Isizathu sesibili siqondene ngqo nenethiwekhi yokukhokha ye-Stellar (ukusetshenziswa okuvamile kwe-SCP). Yonke impahla kunethiwekhi ye-Stellar inomkhiphi, futhi imihlahlandlela ye-Stellar idinga ukuthi okhiphayo ngamunye akhethe indawo eyodwa noma ngaphezulu kunethiwekhi ukuze kucutshungulwe izicelo zokuhlenga. Kukuthakazelisa kakhulu ukufaka phakathi ngokuqondile noma ngokungaqondile lawa ma-node ezincekwini zekhoramu yempahla ngayinye oyithandayo. Ikhoramu yawo wonke ama-node anentshisekelo empahleni ethile ayobe esedlulana okungenani kulawo ma-node okusebenzisa. Ama-Node anentshisekelo ezimpahleni eziningi azofaka zonke izindawo zokuhlenga zabakhiphi abafanele ezicezwini zabo zekhoramu, futhi bazofuna ukuhlanganisa zonke izimpahla ndawonye. Ngaphezu kwalokho, noma yiziphi izimpahla ezingaxhunywanga ngale ndlela kwabanye kunethiwekhi, futhi akufanele ixhunywe - lokhu kuklanyelwe ukuze kungabikho ukunqwabelana kwekhoramu kule nethiwekhi (isibonelo, amabhange asuka endaweni yedola ngezinye izikhathi afuna ukuhwebelana namabhange asuka endaweni ye-euro namabhange asuka endaweni ye-peso, ngakho akunethiwekhi efanayo, kodwa akekho babo banendaba nenethiwekhi ehlukene yezingane ezithengisa amakhadi e-baseball).
Yiqiniso, silindile ukweqa ikhoramu akunjalo isiqinisekiso. Ezinye izinhlelo zezivumelwano zeByzantine zikweleta ubukhulu bobunzima bazo esiqinisekweni samakhoramu. Ukuqamba okusha okubalulekile kwe-SCP ukuthi isusa isibopho sokudala ikhoramu ku-algorithm yokuvumelana ngokwayo futhi ikulethe ezingeni lohlelo lokusebenza. Ngakho-ke, nakuba ukuvota komfelandawonye kuvamile ngokwanele ukuvota kunoma iyiphi inkinga, ukwethembeka kwakho empeleni kuncike kakhulu encazelweni ebanzi yalezi zincazelo. Okunye ukusetshenziswa okucatshangelwayo kungase kungabi kulungele ukudala amanethiwekhi axhumeke kahle njengamanye.
Ukuvota, ukwamukelwa kanye nokuqinisekiswa
Emzuliswaneni wokuvota ohlangene, i-node ngokuzikhethela iqala ukuvotela inani elithi V. Lokhu kusho ukusakaza umlayezo kunethiwekhi: “Ngiyi-node N, izingcezu zekhoramu yami ngu-Q, futhi ngivotela u-V.” Uma i-node ivota ngale ndlela, ithembisa ukuthi ayikaze ivote ngokumelene no-V futhi ayisoze.
Ekusakazweni kontanga kuya kontanga, inodi ngayinye ibona ukuthi abanye bavota kanjani. Uma i-node isiqoqe eyanele yale milayezo, ingakwazi ukulandelela izingcezu zekhoramu bese izama ukuthola ikhoramu. Uma ebona isibalo sontanga nabo abavotela u-V, angaqhubekela phambili ukutholwa V bese ngisakaza lo mlayezo omusha kunethiwekhi: "Ngiyi-node N, izingcezu zekhoramu yami zingu-Q, futhi ngiyamukela u-V." Ukwamukela kunikeza isiqinisekiso esinamandla kunokuvota okulula. Uma i-node ivotela i-V, ayikwazi ukuvotela ezinye izinketho. Kodwa uma inodi yamukela u-V, ayikho inodi Kunethiwekhi ezoke yamukele enye inketho (I-Theorem 8 ku-whitepaper ye-SCP ifakazela lokhu).
Yebo, kunethuba elikhulu lokuthi ngeke kube khona ngokushesha isibalo samanodi avumelana no-V. Amanye ama-node angavotela amanye amanani. Kodwa kunenye indlela yokuthi i-node isuke ekuvoteni okulula iye ekwamukelweni. U-N angase amukele inani elihlukile lika-W, ngisho noma engalivotelanga, futhi noma engayiboni ikhoramu yalo. Ukunquma ukushintsha ivoti lakho, vele ubone isethi yokuvimbela amanodi amukele i-W. Isethi yokuvimba iyinodi eyodwa kusuka kucezu ngalunye lwekhoramu N. Njengoba igama libonisa, ingakwazi vimba noma iyiphi enye incazelo. Uma wonke ama-node kusethi enjalo amukela u-W, khona-ke (nge-Theorem 8) ngeke kuze kwenzeke ikhoramu ethatha inani elihlukile, ngakho-ke kuphephile futhi ku-N ukwamukela i-W.
I-Node N enezingcezu ezintathu zekhoramu.
I-BDF iyisethi yokuvimba ka-N: ihlanganisa inodi eyodwa kusuka kucezu ngalunye luka-N.
I-BE iphinde ibe yisethi yokuvimba ka-N ngoba u-E uvela ezingcezu ezimbili zika-N.
Kodwa isethi yokuvimba akuyona ikhoramu. Kungaba lula kakhulu ukuphamba inodi N ekwamukeleni inani elifunekayo uma kwanele ukugqekeza inodi eyodwa kusiqeshana ngasinye sika-N. Ngakho-ke, ukwamukela inani akukona ukuphela kokuvota. Kunalokho, u-N kufanele aqinisekise inani, okungukuthi, abone ikhoramu yamanodi ayamukelayo. Uma kufika kude kangaka, khona-ke, njengoba i-whitepaper ye-SCP ifakazela (ku-Theorem 11), yonke enye inethiwekhi izogcina iqinisekisa inani elifanayo, ngakho-ke u-N uzoqeda ivoti elihlanganisiwe ngenani elithile njengomphumela.
Ukuvota okuhlanganisiwe.
Inqubo yokuvota, ukwamukela, kanye nokuqinisekiswa kuhlanganisa umjikelezo owodwa ogcwele wokuvota okuyinhlangano. I-Stellar consensus protocol ihlanganisa eminingi yale mijikelezo ukuze idale uhlelo oluphelele lokuvumelana.
I-Stellar Consensus Protocol
Izimpawu ezimbili ezibalulekile zesistimu yokuvumelana yilezi − ukuphepha и ukusinda. I-algorithm yokuvumelana "iphephile" uma ingakwazi ukunikeza imiphumela ehlukile kubahlanganyeli abahlukene (ikhophi yomlando ka-Bob ngeke iphikisane noCarol). "Ukuphila" kusho ukuthi i-algorithm izohlala ikhiqiza umphumela, okungukuthi, ngeke ibambeke.
Kuchazwe inqubo yokuvota yenhlangano iphephile ngomqondo wokuthi uma i-node iqinisekisa inani lika-V, ayikho enye i-node ezoqinisekisa elinye inani. Kodwa elithi “ngeke liqinisekise enye incazelo” akusho ukuthi lizoqinisekisa okuthile. Abahlanganyeli bangavotela amanani amaningi ahlukene kangangokuthi akukho okuzofinyelela umkhawulo wokwamukelwa. Lokhu kusho ukuthi ekuvoteni kombuso akukho ukusinda.
I-Stellar consensus protocol isebenzisa ukuvota okuhlangene ngendlela eqinisekisa kokubili ukuphepha nokuphila. (Iziqinisekiso zokuphepha nokusinda ze-SCP zinomkhawulo wethiyori. Idizayini ikhetha isiqinisekiso sokuphepha esiqine kakhulu, esidela ukuncishiswa okuncane kokusinda, kodwa uma kunikezwe isikhathi esanele, ukuvumelana kungenzeka kakhulu kufinyelelwe.) Ngamafuphi, umqondo uwukuba namavoti amaningi ahlangene ngamanani amaningi kuze kube yilapho eyodwa ifinyelela kuzo zonke izigaba zokuvota ze-SCP ezichazwe ngezansi.
Amanani i-SCP efuna ukuvumelana ngawo angaba umlando wokwenziwe noma i-oda lesidlo sasemini noma enye into, kodwa kubalulekile ukuqaphela ukuthi lawa akuwona amanani amukelwayo noma aqinisekiswayo. Esikhundleni salokho, ukuvota kombuso kwenzeka ngokusho izitatimende mayelana nalawa magugu.
Imizuliswano yokuqala yokuvota kwenhlangano yenzeka ngomhla ka- isigaba sokuqokwa (isigaba sokuqokwa), kusethi yezitatimende ezifana nokuthi “Ngiqoka u-V,” mhlawumbe ngamavelu amaningi ahlukene ka-V. Injongo yokuqoka iwukuthola isitatimende esisodwa noma ngaphezulu esihamba ngokwamukelwa nokuqinisekiswa.
Ngemva kokuthola amakhandidethi angaqinisekiswa, i-SCP iqhubekela esigabeni sokuvota, lapho inhloso kuwukuthola okuthile. umbiko (okungukuthi, isiqukathi senani elihlongozwayo) kanye nekhoramu engasho bophezela ngoba (zibophezele). Uma ikhoramu yenza ivoti, inani layo liyamukelwa njengokuvumelana. Kodwa ngaphambi kokuthi i-node ivote esivumelwaneni sokuvota, kufanele iqinisekise kuqala ukwesulwa wonke amavoti anenani eliphansi lokuphikisa. Lezi zinyathelo—ukukhansela amavoti ukuze kutholwe elingenziwa—zibandakanya imijikelezo eminingi yokuvota okuyinhlangano ezimangalweni zamavoti amaningi.
Izigaba ezilandelayo zichaza ukuqokwa nokuvota kabanzi.
Ukuqokwa
Ekuqaleni kwesigaba sokuqoka, inodi ngayinye ingakhetha ngokuzenzekelayo inani lika-V futhi ivotele isitatimende esithi “Ngiqoka u-V.” Umgomo kulesi sigaba uwukuqinisekisa ukuqokwa kwenani elithile ngevoti lenhlangano.
Mhlawumbe ama-node anele avota eziphakamisweni ezahlukene ngokwanele ukuthi akukho ukuqokwa okungafinyelela emngceleni wokwamukelwa. Ngakho-ke, ngaphezu kokusakaza amavoti abo okuqokwa, ama-node "abonisa" ukuqokwa kontanga yabo. I-Echo isho ukuthi uma i-node ivotela ukuphakanyiswa kuka-V, kodwa ibona umlayezo ovela kumakhelwane avotela igama elithi W, manje izobavotela bobabili u-V kanye no-W. (Akuwona wonke amavoti ontanga enanelwa ngesikhathi sokuqokwa ngoba lokhu kungaholela ekuqhumeni abaqokiwe abahlukene. I-SCP ihlanganisa indlela yokulawula la mavoti. Ngamafuphi, kunendlela yokunquma "izinto eziza kuqala" zontanga ngokombono wendawo, futhi amavoti kuphela ama-node abaluleke kakhulu avelayo. Uma kuphakanyiswa isikhathi eside ukuqokwa ithatha, yehlisa i-threshold, ngakho-ke inodi inweba isethi yontanga ezobonisa amavoti abo. Ifomula ebalulekile ihlanganisa inombolo ye-slot njengokunye okokufaka kwayo, ngakho-ke intanga ebaluleke kakhulu endaweni eyodwa ingase ibe intanga ebaluleke kakhulu enye, futhi ngokuphambene).
Ngokomqondo, ukuphakanyiswa kuyahambisana, kokubili u-V kanye no-W amavoti enhlangano ehlukene, ngalinye likwazi ukuzuza ukwamukelwa noma ukuqinisekiswa. Empeleni, imilayezo yephrothokholi ye-SCP ihlanganisa la mavoti angawodwana.
Nakuba ukuvotela ukuqokwa kuka-V kuyisithembiso sokuthi ngeke uvote ngokumelene nokuqokwa kuka-V, kusezingeni lesicelo - kulokhu i-SCP - lapho kunqunywa ukuthi "okuphikisanayo" kusho ukuthini. I-SCP ayisiboni isitatimende esiphikisana nevoti elithi "Ngiqoka u-X", okungukuthi, awukho umlayezo othi "Ngimelene nokuqoka u-X", ngakho-ke inodi ingavota ukuze iqoke noma imaphi amanani. Okuningi kwalokhu kuqokwa ngeke kuya ndawo, kodwa ekugcineni indawo izokwazi ukwamukela noma ukuqinisekisa inani elilodwa noma ngaphezulu. Uma oqokiwe eseqinisekisiwe, uba nguye ikhandidethi.
Ukuqokwa kwe-SCP kusetshenziswa ukuvota okuhlangene. Kungaba namavelu amaningi okuthi “B” abekwe phambili ontanga futhi “avezwe” yinodi.
Ukuqokwa kungase kuphumele kumakhandidethi amaningi aqinisekisiwe. Ngakho-ke, i-SCP idinga isendlalelo sohlelo lokusebenza ukuthi sinikeze indlela ethile yokuhlanganisa abazongenela ukhetho babe yinye inhlanganisela (okuhlanganisiwe). Indlela yokuhlanganisa ingaba yinoma yini. Into eyinhloko ukuthi uma le ndlela i-deterministic, khona-ke i-node ngayinye izohlanganisa abalingani abafanayo. Kusistimu yokuvota kwasemini, "ukuhlanganiswa" kungase kusho ukwenqaba umuntu oyedwa kwababili. (Kodwa ngendlela enqumayo: inodi ngayinye kufanele ikhethe inani elifanayo ukuze lisethwe kabusha. Isibonelo, ukukhetha kwangaphambilini ngokulandelana kwezinhlamvu). Kunethiwekhi yokukhokha ye-Stellar, lapho umlando wokwenziwe uvotelwa khona, ukuhlanganisa abaqokiwe ababili abahlongozwayo kuhilela ukuhlanganisa ukuthengiselana abakuqukethe kanye nezakamuva zezitembu zabo zesikhathi ezimbili.
Iphepha elimhlophe le-SCP lifakazela (i-Theorem 12) ukuthi ekupheleni kwesigaba sokunwetshwa, inethiwekhi igcina iguqulelwe kuyinhlanganisela eyodwa. Kodwa kunenkinga: ukuvota okuhlangene kuyiphrothokholi engavumelani (njenge-SCP). Ngamanye amazwi, ama-node awahlanganiswa ngesikhathi, kodwa kuphela ngemiyalezo ayithumelayo. Ngokombono we-node, akucaci ukuthi nini iphelile isigaba sokunweba. Futhi nakuba wonke ama-node ekugcineni efika endaweni eyinhlanganisela efanayo, angase athathe imizila ehlukene endleleni, enze amakhandidethi ayinhlanganisela ahlukene endleleni, futhi awasoze asho ukuthi iyiphi eyokugcina.
Kodwa kujwayelekile. Ukuqokwa kuwukulungiselela nje. Into esemqoka ukukhawulela inani labazongenela ukhetho ukuze kuzuzwe ukuvumelana, okwenzeka kule nqubo egijima esikhundleni (ukuvota).
Ukugijima
I-Bulletin izithandani , lapho ikhawunta iyinombolo ephelele eqala ku-1 futhi inani liyikhandidethi elisuka esigabeni sokuqoka. Lokhu kungaba ikhandidethi lenodi uqobo noma ikhandidethi lenodi engumakhelwane elamukelwe yileyo nodi. Uma sikhuluma nje, ivoti libandakanya imizamo ephindaphindiwe yokuphoqa inethiwekhi ukuthi ifinyelele ukuvumelana ngekhandidethi elithile ngevoti elithile ngokubamba amavoti okungenzeka abe yizinhlangano eziningi ezitatimendeni zokuvota. Izibali kumavoti zilandelela imizamo eyenziwe, futhi amavoti anezibalo eziphezulu athatha indawo yokuqala kunamavoti anezibalo eziphansi. Uma iphephandaba uyabhajwa, ivoti elisha liyaqala, manje ekuvotweni .
Kubalulekile ukuhlukanisa izincazelo (ngokwesibonelo, i-oda lesidlo sasemini kufanele libe yini: i-pizza noma amasaladi), izincwadi zezindaba (i-counter-value pair) kanye izitatimende mayelana namavoti. Umjikelezo we-SCP uhlanganisa imizuliswano eminingana yokuvota kombuso, ikakhulukazi ezitatimendeni ezilandelayo:
- "Sengilungele ukwenza ivoti B" kanye
- "Ngimemezela ukuzinikela kwevoti B"
Ngokombono wenodi ethile, kufinyelelwa ukuvumelana lapho kuthola ivoti B engaqinisekisa (okungukuthi, ukuthola ikhoramu eyamukelayo) isitatimende esithi "Ngenza ivoti B." Kusukela kuleli phuzu kuqhubeke, kuphephile ukwenza ngenani elishiwo ku-B - isibonelo, ukubeka leli oda ngesidlo sasemini. Kubizwa ukwenziwa kwangaphandle izincazelo. Uma ukwamukelwa kwevoti sekuqinisekisiwe, i-node ingaqiniseka ukuthi noma iyiphi enye i-node ikhiphe inani elifanayo noma izokwenza kanjalo esikhathini esizayo.
Nakuba amavoti amaningi ahlanganisiwe enziwa ngokucatshangwayo ezimangalweni zamavoti amaningi ahlukene, awashintshisani ngemilayezo eminingi ngoba umlayezo ngamunye uhlanganisa inani lamavoti. Ngakho-ke umlayezo owodwa ukhuthaza isimo samavoti amaningi ahlangene ngesikhathi esisodwa, isibonelo: “Ngivuma ukuvota kusukela ngaphambili "
Asho ukuthini amagama athi “zilungiselele” kanye “nokuzinikela”?
I-node ivota ukwenza ivoti lapho iqiniseka ukuthi amanye ama-node ngeke enze amavoti anamanani ahlukene. Ukukholisa lokhu kuyinhloso yokulungiselela isicelo. Ivoti elithi "Ngilungele ukwenza ivoti B" liyisithembiso sokungalokothi wenze ivoti elincane kuno-B, okungukuthi ngenani elincane (i-SCP idinga amanani kumavoti ukuthi abe ngokulandelana okuthile. Ngakho, iphephandaba Ngaphansi uma, N1
Kungani ukuthi “Ngilungele ukwenza ivoti B” kusho ukuthi “ngithembisa ukuthi ngeke ngivote ngaphansi kuka-B”? Ngoba i-SCP ichaza ukukhipha isisu njengokuphambene nokuzibophezela. Ivoti lokulungiselela ivoti liphinde lifake ivoti elivimbela amanye amavoti, futhi, njengoba sike saxoxa ngaphambili, ukuvotela into eyodwa kuyisithembiso sokungavoteli ngokumelene nayo.
Ngaphambi kokusakaza isivumelwano, i-node kufanele iqale ithole umbiko engaqinisekisa ukuthi ilungisiwe. Ngamanye amazwi, lenza ivoti elihlangene esihlokweni esithi “Ngilungele ukwenza ivoti B,” mhlawumbe emavotini amaningi ahlukene, kuze kube yilapho lithola owamukela ikhoramu.
Avelaphi amavoti ukuze kulungiswe ivoti? Okokuqala, indawo isakaza amalungiselelo okuvotela i-<1,C>, lapho u-C eyikhandidethi eliyinhlanganisela elikhiqizwa esigabeni sokuqokwa. Kodwa-ke, ngisho nangemva kokuba amalungiselelo okuvota eqalile, ukuphakanyiswa kungase kuphumele ekubonakaleni kwamakhandidethi abengeziwe njengamavoti amasha. Ngaleso sikhathi, ontanga bangaba namakhandidethi ahlukene, futhi bangakha isethi yokuvimbela eyamukela "Ngilungele ukwenza ivoti le-B2," elizokholisa nodi ukuthi liyamukele futhi. Okokugcina, kunendlela yokuvala isikhathi edala imijikelezo emisha yokuvota okuyinhlangano kumavoti amasha anezibalo eziphezulu uma amavoti amanje ebambekile.
Lapho nje indawo yokuvota ithola ivoti elingu-B elingaqinisekisa njengoba lilungisiwe, lisakaza umlayezo omusha othi “Zibophezele ivoti B.” Leli voti litshela ontanga ukuthi i-node ayisoze yayeka u-B. Eqinisweni, uma u-B eyivoti , bese kuthi “Zibophezele ivoti " kusho imvume engenamibandela yokuvotela ukulungela ivoti ngalinye ku-<∞, s>. Leli nani elengeziwe lisiza abanye ontanga ukuthi bahlangane nontanga yokuzibophezela uma besesezigabeni zangaphambili zephrothokholi.
Kulesi sigaba, kufanelekile ukugcizelela futhi ukuthi lawa amaphrothokholi asynchronous. Ngenxa yokuthi i-node eyodwa ithumela amavoti aphezulu esibopho akusho ukuthi ontanga bayo nabo bayakwenza. Abanye babo kungenzeka ukuthi basavotela izitatimende belungiselela ukuvota, abanye kungenzeka ukuthi sebeyikhiphile incazelo. I-SCP ichaza ukuthi i-node kufanele icubungule kanjani uhlobo ngalunye lomlayezo wontanga ngaphandle kwesigaba sawo.
Uma umyalezo othi "Ngimemezele ukuzibophezela » ayikwazi ukwamukelwa noma ukuqinisekiswa, okusho ukuthi, amathuba okuthi umyalezo wamukelwe noma uqinisekiswe noma - noma, kunoma yikuphi, noma yiliphi ivoti elinenani elingu-C, hhayi elinye, njengoba i-node isivele ithembise ukuthi ngeke ikhansele. . Ngesikhathi i-node isakaza amavoti esibopho, kuzoba ngu-C noma lutho, kuye ngokuthi ukuvumelana kuya kude kangakanani. Kodwa-ke, lokhu akukeneli ukuthi i-node ikhiphe ngaphandle C. Abanye ontanga baseByzantine (obakha ngaphansi kwekhoramu, ngokusekelwe ekucabangeni kwethu kokuphepha) bangase baqambe amanga ku-node. Ukwamukela bese uqinisekisa ivoti elithile (noma uhla lwamavoti) yikho okunikeza i-node ithemba lokuthi ekugcineni ikhiphe u-C.
Ukuvota kwe-SCP ngokuvota okuhlangene. Asiboniswa: Isibali sikhathi singacisha noma kunini, sikhulise isibalo kuvoti (futhi ngokunokwenzeka sikhiqize inhlanganisela entsha yamakhandidethi angeziwe aphakanyisiwe).
Futhi konke! Uma inethiwekhi isifinyelele ukuvumelana, isilungele ukuyenza kaningi. Kunethiwekhi yokukhokha ye-Stellar, lokhu kwenzeka cishe kanye njalo ngemizuzwana emi-5: umsebenzi odinga kokubili ukuphepha nokuphila okuqinisekiswe i-SCP.
I-SCP ingafinyelela lokhu ngokuthembela emizuliswaneni eminingi yokuvota okuyinhlangano. Ukuvota okuhlanganyelwe kwenziwa kwenzeke ngomqondo wezingcezu zekhoramu: amaqoqo nontanga leyo nodi ngayinye enqume ukulethemba njengengxenye yekhoramu (yesifundo). Lokhu kulungiselelwa kusho ukuthi ukuvumelana kungafinyelelwa ngisho nakunethiwekhi enobulungu obuvulekile kanye nenkohliso yaseByzantine.
Ukuqhubeka kokufunda
- Iphepha elimhlophe le-SCP langempela lingatholakala , futhi imininingwane esalungiswa yokuqaliswa kwayo.
- Umbhali wasekuqaleni wephrothokholi ye-SCP, uDavid Mazier, uyichaza ngendlela elula (kodwa esebuchwepheshe). .
- Kungenzeka ukuthi umangale ngokungawatholi amagama athi "izimayini" noma "ubufakazi bomsebenzi" kulesi sihloko. I-SCP ayizisebenzisi lezi zindlela, kodwa amanye ama-algorithms wokuvumelana ayawasebenzisa. U-Zane Witherspoon ubhale ukuthi uyafinyeleleka .
- inethiwekhi elula efinyelela ukuvumelana ngomzuliswano owodwa ogcwele we-SCP.
- Kubafundi abanentshisekelo ekusetshenzisweni kwe-SCP: bona , esetshenziswa inethiwekhi yokukhokha ye-Stellar, noma , engabhala ukuze ngiyiqonde kangcono i-SCP.
Source: www.habr.com