Ang Stellar consensus protocol ay unang inilarawan sa David Mazier noong 2015. Ito ay isang "federal Byzantine agreement system" na nagbibigay-daan sa desentralisado, walang pinunong computing network na mahusay na maabot ang pinagkasunduan sa isang desisyon. Ginagamit ng network ng pagbabayad ng Stellar ang Stellar Consensus Protocol (SCP) upang mapanatili ang isang pare-parehong kasaysayan ng transaksyon na nakikita ng lahat ng kalahok.
Ang mga protocol ng pinagkasunduan ay itinuturing na mahirap maunawaan. Ang SCP ay mas simple kaysa sa karamihan sa kanila, ngunit ibinabahagi pa rin ang reputasyon na ito - bahagyang dahil sa maling ideya na ang "federated voting", na siyang paksa ng unang kalahati ng artikulong siyentipiko, ay SCP. Ngunit hindi iyon totoo! Isa lang itong mahalagang building block na ginagamit ng ikalawang kalahati ng artikulo para likhain aktuwal Stellar consensus protocol.
Sa artikulong ito ay maikli nating ipapaliwanag kung ano ang isang "sistema ng mga kasunduan", kung ano ang maaaring gawin itong "Byzantine" at bakit ginagawang "pederal" ang sistemang Byzantine. Pagkatapos ay ipapaliwanag namin ang pamamaraan ng federated na pagboto na inilarawan sa artikulo ng SCP, at sa wakas ay ipapaliwanag namin ang mismong protocol ng SCP.
Mga sistema ng kasunduan
Ang isang sistema ng mga kasunduan ay nagbibigay-daan sa isang pangkat ng mga kalahok na magkaroon ng isang pinagkasunduan sa isang paksa, tulad ng kung ano ang iuutos para sa tanghalian.
Sa Interstellar, ipinatupad namin ang aming sariling sistema ng kasunduan sa kainan: nag-uutos kami kung ano ang sinasabi ng aming operations manager na si John. Ito ay isang simple at epektibong sistema ng kasunduan. Lahat tayo ay nagtitiwala kay John at naniniwala na makakahanap siya ng isang bagay na kawili-wili at masustansya araw-araw.
Ngunit paano kung abusuhin ni John ang ating tiwala? Maaari siyang mag-isa na magpasya na dapat tayong lahat ay maging vegan. Sa isang linggo o dalawa, malamang na ibagsak natin siya at ibibigay ang kapangyarihan kay Elizabeth. Ngunit bigla niyang nagustuhan ang mga avocado na may bagoong at naisip niya na dapat lahat ay ganoon. Nakakasira ng kapangyarihan. Kaya't mas mahusay na maghanap ng ilang mas demokratikong pamamaraan: ilang paraan upang matiyak na ang iba't ibang mga kagustuhan ay isinasaalang-alang, habang tinitiyak ang isang napapanahong at hindi malabo na resulta, upang walang sinuman ang magtatapos sa pag-order ng tanghalian, o limang tao ang naglalagay ng iba't ibang mga order, o ang talakayan humahaba hanggang gabi.
Mukhang simple lang ang solusyon: bumoto! Ngunit ito ay isang mapanlinlang na impression. Sino ang kukuha ng mga balota at iuulat ang mga resulta? At bakit dapat paniwalaan ng iba ang sinasabi niya? Siguro kaya natin sa una bumoto para sa isang pinuno na pinagkakatiwalaan nating mamuno sa pagboto - ngunit kung sino ang mamumuno dito una sa pamamagitan ng pagboto? Paano kung hindi tayo magkasundo sa isang pinuno? O paano kung magkasundo tayo, ngunit ang pinunong ito ay natigil sa isang pulong o nag-sick leave?
Ang mga katulad na problema ay nangyayari sa mga distributed computer network. Ang lahat ng kalahok o node ay dapat sumang-ayon sa ilang desisyon, gaya ng kung kaninong turn na ang mag-update ng isang nakabahaging file o mag-alis ng isang gawain mula sa processing queue. Sa isang network ng cryptocurrency, paulit-ulit na kailangang piliin ng mga node kung ano ang hitsura ng buong kuwento mula sa ilang posibleng bersyon, na kung minsan ay nagkakasalungatan. Ang kasunduan sa network na ito ay nagbibigay ng katiyakan sa tatanggap na ang barya ay (a) wasto (hindi peke) at (b) hindi pa ginagastos sa ibang lugar. Tinitiyak din nito na maaari niyang gastusin ang mga barya sa hinaharap dahil ang bagong tatanggap ay magkakaroon ng parehong mga garantiya para sa parehong mga kadahilanan.
Ang anumang consensus system sa isang distributed computing network ay dapat na fault-tolerant: dapat itong makagawa ng pare-parehong mga resulta sa kabila ng mga error tulad ng mabagal na link, hindi tumutugon na mga node, at hindi tamang pag-order ng mensahe. Byzantine Ang sistema ng kasunduan ay karagdagang lumalaban sa mga error na "Byzantine": mga node na nagbibigay ng maling impormasyon, dahil man sa isang error o sa isang sadyang pagtatangka na pahinain ang system o makakuha ng ilang kalamangan. "Byzantine" fault tolerance - ang kakayahang magtiwala sa isang desisyon ng grupo kahit na ang ilang miyembro ng grupo ay maaaring magsinungaling o kung hindi man ay hindi sumusunod sa mga tuntunin ng paggawa ng desisyon - ay tinatawag na sinubukang i-coordinate ang pag-atake. kay Anthony Stevens.
Isaalang-alang ang may-ari ng crypto coin na si Alice, na dapat pumili sa pagitan ng pagbili ng masarap na ice cream mula kay Bob at pagbabayad ng utang ni Carol. Marahil ay gusto ni Alice na bayaran silang dalawa nang sabay-sabay sa pamamagitan ng mapanlinlang na paggastos ng parehong barya. Para magawa ito, dapat niyang kumbinsihin ang computer ni Bob na hindi kailanman binayaran ang barya kay Carol, at kumbinsihin ang computer ni Carol na hindi kailanman binayaran ang barya kay Bob. Ginagawa ito ng sistema ng mga kasunduan ng Byzantine na halos imposible, gamit ang isang paraan ng karamihang tuntunin na tinatawag korum. Ang isang node sa naturang network ay tumangging lumipat sa isang partikular na bersyon ng kasaysayan hanggang sa makita nito na ang isang sapat na bilang ng mga kapantay - isang korum - ay sumasang-ayon sa naturang paglipat. Kapag nangyari ito, bubuo sila ng isang bloke ng pagboto na sapat na malaki upang pilitin ang natitirang mga node ng network na sumang-ayon sa kanilang desisyon. Maaaring pilitin ni Alice ang ilang mga node na magsinungaling para sa kanya, ngunit kung ang network ay sapat na malaki, ang kanyang pagtatangka ay matatalo ng mga boto ng mga matapat na node.
Ilang node ang kailangan para sa quorum? Sa pinakamababa, isang mayorya, o sa halip, isang kwalipikadong mayorya upang labanan ang mga pagkakamali at pandaraya. Ngunit upang mabilang ang karamihan, kailangan mong malaman ang kabuuang bilang ng mga kalahok. Sa opisina ng Interstellar o sa mga halalan sa distrito, ang mga numerong ito ay madaling malaman. Ngunit kung ang iyong grupo ay isang maluwag na tinukoy na network kung saan ang mga node ay maaaring pumasok at umalis sa kalooban nang walang pag-apruba mula sa sentro, kailangan mo pederal isang sistema ng kasunduan ng Byzantine na may kakayahang tumukoy ng mga korum hindi mula sa isang paunang natukoy na listahan ng mga node, ngunit sa dinamikong paraan, mula sa isang pabago-bago at hindi maiiwasang hindi kumpletong snapshot ng mga node sa isang partikular na punto ng oras.
Maaaring mukhang imposibleng lumikha ng isang korum mula sa pananaw ng isang solong node sa isang malawak na network, ngunit ito ay posible. Ang ganitong korum ay maaari pang magarantiya ang mga resulta ng desentralisadong pagboto. Ipinapakita ng puting papel ng SCP kung paano ito gawin gamit ang tinatawag na pamamaraan sa pamamagitan ng pederal na boto.
Para sa walang pasensya
Ang natitirang bahagi ng artikulo ay naglalarawan ng federated voting at ang Stellar consensus protocol nang mas detalyado. Kung hindi ka interesado sa mga detalye, narito ang pangkalahatang pangkalahatang-ideya ng proseso.
- Ang mga node ay nagsasagawa ng mga round ng pederal na pagboto sa "mga nominado." Ang ibig sabihin ng federal voting round ay:
- Ang node ay bumoto para sa ilang pahayag, halimbawa, "Iminumungkahi ko ang halaga ng V";
- Ang node ay nakikinig sa mga boses ng mga kapantay hanggang sa ito ay makahanap ng isa na maaaring "makatanggap";
- Ang node ay naghahanap ng isang "quorum" para sa assertion na ito. "Kinukumpirma" ng isang korum ang nominado.
- Sa sandaling makumpirma ng isang node ang isa o higit pang mga nominado, sinusubukan nitong "ihanda" ang "balot" sa pamamagitan ng ilang round ng federated na pagboto.
- Sa sandaling ma-verify ng isang node na handa na ang balota, sinusubukan nitong isagawa ito sa pamamagitan ng higit pang mga round ng federated voting.
- Sa sandaling makumpirma ng isang node ang isang commit ng isang balota, maaari nitong "i-externalize" ang halaga ng balotang iyon sa pamamagitan ng paggamit nito bilang resulta ng pinagkasunduan.
Ang mga hakbang na ito ay nagsasangkot ng maraming round ng federated voting, na sama-samang bumubuo ng isang SCP round. Tingnan natin kung ano ang nangyayari sa bawat hakbang.
Federated voting
Ang federated voting ay isang pamamaraan para sa pagtukoy kung ang network ay maaaring sumang-ayon sa isang panukala. Sa round ng pagboto, dapat pumili ang bawat node ng isa sa posibleng maraming posibleng value. Hindi nito magagawa ito maliban kung ito ay kumpiyansa na ang ibang mga node sa network ay hindi pipili ng ibang resulta. Upang matiyak ito, ang mga node ay nagpapalitan ng isang barrage ng mga mensahe pabalik-balik upang ang lahat mapag-Na korum mga buhol tumatanggap pareho desisyon. Ang natitirang bahagi ng seksyong ito ay nagpapaliwanag ng mga termino sa pangungusap na ito at kung paano nangyayari ang buong pamamaraan.
Mga hiwa ng korum at korum
Magsimula tayo sa pagtukoy ng isang korum. Tulad ng tinalakay natin sa itaas, sa isang desentralisadong network na may dynamic na membership, imposibleng malaman nang maaga ang bilang ng mga node at samakatuwid kung ilan ang kailangan para sa karamihan. Nilulutas ng federated voting ang problemang ito sa pamamagitan ng pagpapakilala ng bagong ideya quorum cut (quorum slice): Isang maliit na hanay ng mga peer na pinagkakatiwalaan ng isang node upang ipaalam ang impormasyon ng status ng pagboto sa iba pang network. Ang bawat node ay tumutukoy sa sarili nitong hiwa ng korum (kung saan ito ay nagiging de facto na miyembro).
Ang pagbuo ng korum ay nagsisimula sa pagbawas ng korum. Para sa bawat node, idinagdag ang mga cut node nito. Pagkatapos ay idinagdag ang mga termino ng slice mga node na ito at iba pa. Habang nagpapatuloy ka, parami nang parami ang mga node na hindi mo maidaragdag dahil kasama na sila sa slice. Kapag wala nang mga bagong node na idaragdag, hihinto ang proseso: nakabuo kami ng isang korum sa pamamagitan ng "palipat na pagsasara" ng hiwa ng korum ng paunang node.
Upang mahanap ang quorum mula sa isang ibinigay na node...
... magdagdag ng mga miyembro ng slice nito...
...pagkatapos ay nagdaragdag kami ng mga miyembro ng slice ng mga node na ito.
Nagpapatuloy kami hanggang sa wala nang mga node na maidaragdag.
Walang mga node na natitira upang idagdag. Ito ay isang korum.
Sa katunayan, ang bawat node ay maaaring lumitaw sa higit sa isang slice. Upang bumuo ng isang korum, pumili lamang ng isa sa mga hiwa at magdagdag ng mga miyembro; pagkatapos ay pumili ng anumang slice para sa bawat isa sa mga miyembro at magdagdag ng mga miyembro ito hiwa at iba pa. Nangangahulugan ito na ang bawat node ay miyembro ng maraming posibleng korum.
Pumili lamang ng isang hiwa ng korum sa bawat hakbang.
Isang posibleng korum. O isang alternatibo...
...pumili ng iba pang hiwa...
β¦(kapag posible)β¦
... lumikha ng isa pang korum.
Paano malalaman ng isang node kung aling mga hiwa ang nasa ibang mga node? Sa parehong paraan tulad ng iba pang impormasyon tungkol sa iba pang mga node: mula sa mga pagpapadala na ini-broadcast ng bawat node sa network kapag nagbago ang estado ng pagboto nito. Kasama sa bawat broadcast ang impormasyon tungkol sa mga hiwa ng pagpapadala ng node. Ang puting papel ng SCP ay hindi tumutukoy ng mekanismo ng komunikasyon. Karaniwang ginagamit ang mga pagpapatupad para sa garantisadong pagsasahimpapawid ng mga mensahe sa buong network.
Alalahanin na sa hindi pederal na sistema ng mga kasunduan ng Byzantine, ang isang korum ay tinukoy bilang mayorya ng lahat ng mga node. Ang sistema ng kasunduan ng Byzantine ay idinisenyo mula sa punto ng view ng tanong: gaano karaming mga hindi tapat na node ang maaaring tiisin ng system? Sa isang sistema ng mga N node na idinisenyo upang makaligtas sa mga pagkabigo, ang isang node ay dapat na makapag-usad sa pamamagitan ng pagtanggap ng feedback mula sa mga Nβf na mga kapantay dahil ang f sa kanila ay maaaring bumaba. Ngunit sa pagtanggap ng tugon mula sa Nβf peer, maaari nating ipagpalagay na ang lahat ng f peer (kung saan ang node ay hindi nakatanggap ng tugon) ay talagang tapat. Kaya, ang f out sa Nβf mga kapantay (kung saan natanggap ang tugon) ay nakakahamak. Para magkaroon ng parehong consensus ang mga node, dapat na tapat ang karamihan sa natitirang mga node, ibig sabihin, kailangan natin ang Nβf na mas malaki sa 2f o N > 3f. Kaya kadalasan ang isang system na idinisenyo upang makaligtas sa mga pagkabigo ay magkakaroon ng kabuuang N=3f+1 na mga node at isang sukat ng korum na 2f+1. Kapag ang isang panukala ay pumasa sa quorum threshold, ang natitirang bahagi ng network ay kumbinsido na ang anumang nakikipagkumpitensya na mga panukala ay mabibigo. Ito ay kung paano ang network ay nagtatagpo sa resulta.
Ngunit sa isang pederal na sistema ng kasunduan sa Byzantine, hindi lamang maaaring magkaroon ng mayorya (dahil walang nakakaalam ng kabuuang sukat ng network), ngunit ang konsepto ng mayorya ay ganap na walang silbi! Kung bukas ang membership sa system, maaaring magkaroon ng mayorya ang isang tao sa pamamagitan lamang ng pagsasagawa ng tinatawag na Sybil attack: paulit-ulit na pagsali sa network sa maraming node. Kaya bakit matatawag na transitive slice closure korum, at paano nito nagagawang sugpuin ang mga nakikipagkumpitensyang panukala?
Sa teknikal na paraan, hindi! Isipin ang isang network ng anim na node, kung saan ang dalawang triplet ay nakahiwalay sa mga hiwa ng korum ng bawat isa. Ang unang subgroup ay maaaring gumawa ng isang desisyon na hindi kailanman maririnig ng pangalawa, at vice versa. Walang paraan para maabot ng network na ito ang consensus (maliban kung nagkataon).
Samakatuwid, hinihiling ng SCP na para sa federated voting (at para mailapat ang mahahalagang theorems ng papel), ang network ay dapat magkaroon ng property na tinatawag na intersection ng mga korum. Sa isang network na may ganitong property, anumang dalawang korum na maaaring buuin ay palaging magkakapatong sa kahit isang node. Para sa pagtukoy sa umiiral na damdamin ng network, ito ay kasing ganda ng pagkakaroon ng mayorya. Sa madaling salita, nangangahulugan ito na kung ang alinmang korum ay sumang-ayon sa pahayag X, walang ibang korum ang maaaring sumang-ayon sa anupaman, dahil tiyak na magsasama ito ng ilang node mula sa unang korum na bumoto na para sa X.
Kung mayroong intersection ng mga korum sa network...
...pagkatapos ay anumang dalawang korum na maaari mong buuin...
...ay laging magsa-intersect.
(Siyempre, ang magkakapatong na mga node ay maaaring lumabas na Byzantine-lying o kung hindi man masama. Sa kasong ito, ang intersection ng korum ay hindi nakakatulong sa network na sumang-ayon. Dahil dito, marami sa mga resulta sa SCP white paper ay batay sa tahasang pagpapalagay, gaya ng kung ano ang natitira sa pagtawid ng korum ng network kahit na matapos tanggalin ang masasamang node. Para sa pagiging simple, iwanan natin ang mga pagpapalagay na ito implicit sa natitirang bahagi ng artikulo).
Maaaring mukhang hindi makatwiran na asahan na ang isang maaasahang pagtawid ng korum ay posible sa isang network ng mga independiyenteng node. Pero may dalawang dahilan kung bakit ganito.
Ang unang dahilan ay ang pagkakaroon ng Internet mismo. Ang Internet ay isang perpektong halimbawa ng isang network ng mga independiyenteng node na may mga intersecting na korum. Karamihan sa mga node sa Internet ay kumokonekta sa ilang iba pang mga lokal na node, ngunit ang mga maliliit na set na ito ay sapat na nagsasapawan na ang bawat node ay maaaring maabot mula sa bawat iba pang node sa ilang ruta.
Ang pangalawang dahilan ay partikular sa network ng pagbabayad ng Stellar (ang pinakakaraniwang paggamit ng SCP). Ang bawat asset sa Stellar network ay may issuer, at ang mga alituntunin ng Stellar ay nangangailangan ng bawat issuer na magtalaga ng isa o higit pang mga node sa network upang iproseso ang mga kahilingan sa pagkuha. Para sa iyong pinakamahusay na interes na direkta o hindi direktang isama ang mga node na ito sa mga hiwa ng korum para sa bawat asset na interesado ka. Ang mga korum para sa lahat ng node na interesado sa isang partikular na asset ay mag-o-overlap kahit man lang sa mga redemption node na iyon. Isasama ng mga node na interesado sa maraming asset ang lahat ng node ng redemption ng kaukulang issuer sa kanilang mga hiwa ng korum, at sisikapin nilang pagsama-samahin ang lahat ng asset. Bilang karagdagan, ang anumang mga asset na hindi naka-link sa ganitong paraan sa iba sa network, at hindi dapat konektado - ito ay dinisenyo upang walang quorum overlap para sa network na ito (halimbawa, ang mga bangko mula sa dollar zone kung minsan ay gustong makipagkalakalan sa mga bangko mula sa euro zone at mga bangko mula sa peso zone, kaya sila ay nasa parehong network, ngunit wala sa kanila ay nagmamalasakit sa hiwalay na network ng mga bata na nagbebenta ng mga baseball card).
Siyempre, ΠΎΠΆΠΈΠ΄Π°Π½ΠΈΠ΅ quorum crossing ay hindi garantiya. Ang iba pang mga sistema ng kasunduan sa Byzantine ay may malaking pagkakautang sa kanilang pagiging kumplikado sa garantiya ng mga korum. Ang isang mahalagang inobasyon ng SCP ay ang pag-alis nito ng responsibilidad para sa paglikha ng mga korum mula sa consensus algorithm mismo at dinadala ito sa antas ng aplikasyon. Kaya, bagama't ang federated voting ay sapat na pangkalahatan upang bumoto sa anumang isyu, ang pagiging maaasahan nito ay talagang nakadepende nang kritikal sa mas malawak na kahulugan ng mga kahulugang ito. Ang ilang hypothetical na paggamit ay maaaring hindi kasing-kabuti sa paglikha ng mga network na mahusay na konektado gaya ng iba.
Pagboto, pagtanggap at kumpirmasyon
Sa isang federated na round ng pagboto, isang node ang opsyonal na magsisimulang bumoto para sa ilang halagang V. Nangangahulugan ito ng pagbo-broadcast ng mensahe sa network: "Ako ay node N, ang aking mga hiwa ng korum ay Q, at ako ay bumoto para sa V." Kapag ang isang node ay bumoto sa ganitong paraan, nangangako ito na hindi pa ito bumoto laban sa V at hindi kailanman bumoto.
Sa mga peer-to-peer na broadcast, makikita ng bawat node kung paano bumoto ang iba. Kapag sapat na ang nakolekta ng isang node sa mga mensaheng ito, maaari nitong subaybayan ang mga hiwa ng korum at subukang maghanap ng mga korum. Kung makakita siya ng isang korum ng mga kapantay na bumoto din kay V, maaari siyang magpatuloy sa pag-aampon V at i-broadcast ang bagong mensaheng ito sa network: βAko ay node N, ang aking quorum slice ay Q, at tinatanggap ko ang V.β Ang pagtanggap ay nagbibigay ng mas malakas na garantiya kaysa sa simpleng pagboto. Kapag ang isang node ay bumoto para sa V, hindi ito makakaboto para sa iba pang mga opsyon. Ngunit kung ang isang node ay tumatanggap ng V, walang node sa Network ang tatanggap sa ibang opsyon (Theorem 8 sa SCP white paper ay nagpapatunay nito).
Siyempre, may mataas na posibilidad na hindi kaagad magkakaroon ng korum ng mga node na sumasang-ayon sa V. Maaaring bumoto ang ibang mga node para sa iba pang mga halaga. Ngunit may isa pang paraan para lumipat ang isang node mula sa simpleng pagboto tungo sa pagtanggap. Maaaring tumanggap si N ng ibang halaga para kay W, kahit na hindi niya ito binoto, at kahit na wala siyang nakikitang korum para dito. Upang magpasya na baguhin ang iyong boto, tingnan lamang hanay ng pagharang node na tumanggap ng W. Ang blocking set ay isang node mula sa bawat hiwa ng korum N. Gaya ng ipinahihiwatig ng pangalan, maaari itong harangan anumang iba pang kahulugan. Kung ang lahat ng mga node sa naturang set ay tumatanggap ng W, kung gayon (sa pamamagitan ng Theorem 8) ay hindi kailanman magiging posible na bumuo ng isang korum na tumatagal ng ibang halaga, at samakatuwid ay ligtas din para sa N na tanggapin ang W.
Node N na may tatlong hiwa ng korum.
Ang BDF ay isang blocking set para sa N: kabilang dito ang isang node mula sa bawat isa sa mga hiwa ng N.
Ang BE ay isa ring blocking set para sa N dahil ang E ay lumalabas sa dalawang hiwa ng N.
Ngunit ang blocking set ay hindi isang korum. Napakadaling linlangin ang node N sa pagtanggap ng nais na halaga kung sapat na ang pag-hack ng isang node lamang sa bawat hiwa ng N. Samakatuwid, ang pagtanggap sa halaga ay hindi pagtatapos ng pagboto. Sa halip, dapat kumpirmahin ng N ang halaga, iyon ay, tingnan ang isang korum ng mga node na tumatanggap nito. Kung aabot ito ng ganoon kalayo, kung gayon, gaya ng pinatutunayan ng SCP whitepaper (sa Theorem 11), ang natitirang bahagi ng network ay magkukumpirma rin sa kalaunan ng parehong halaga, kaya't tatapusin ng N ang federated na boto na may tiyak na halaga bilang resulta.
Federated voting.
Ang proseso ng pagboto, pagtanggap, at pagkumpirma ay bumubuo ng isang buong round ng federated na pagboto. Pinagsasama ng Stellar consensus protocol ang marami sa mga round na ito upang lumikha ng kumpletong consensus system.
Stellar Consensus Protocol
Ang dalawang pinakamahalagang katangian ng isang consensus system ay β seguridad ΠΈ kaligtasan ng buhay. Ang isang consensus algorithm ay "ligtas" kung hindi ito makapagbibigay ng iba't ibang resulta sa iba't ibang kalahok (ang kopya ng kasaysayan ni Bob ay hindi kailanman sasalungat kay Carol). Ang ibig sabihin ng "Livability" ay palaging magbubunga ng resulta ang algorithm, ibig sabihin, hindi ito ma-stuck.
Inilarawan ang pederal na pamamaraan ng pagboto ligtas sa diwa na kung kinukumpirma ng isang node ang halaga ng V, walang ibang node ang magkukumpirma sa ibang halaga. Ngunit ang "hindi kumpirmahin ang isa pang kahulugan" ay hindi nangangahulugan na ito ay kinakailangang kumpirmahin ang isang bagay. Ang mga kalahok ay maaaring bumoto sa napakaraming iba't ibang mga halaga na walang makakarating sa threshold ng pagtanggap. Ibig sabihin, sa federal voting ay wala kaligtasan ng buhay.
Ang Stellar consensus protocol ay gumagamit ng federated voting sa isang paraan na nagsisiguro sa parehong seguridad at survivability. (Ang mga garantiya sa seguridad at survivability ng SCP ay may teoretikal na limitasyon. Pinipili ng disenyo ang isang napakalakas na garantiyang panseguridad, na nagsasakripisyo ng maliit na pagbawas sa survivability, ngunit binigyan ng sapat na oras, ang consensus ay mataas ang posibilidad na maabot.) Sa madaling sabi, ang ideya ay magkaroon ng maramihang mga pederasyong boto sa maraming halaga hanggang ang isa sa mga ito ay makapasok sa lahat ng mga yugto ng pagboto ng SCP na inilarawan sa ibaba.
Ang mga halaga kung saan hinahanap ng SCP ang pinagkasunduan ay maaaring kasaysayan ng transaksyon o isang order ng tanghalian o iba pa, ngunit mahalagang tandaan na hindi ito ang mga halaga na tinatanggap o nakumpirma. Sa halip, ang pederal na pagboto ay nangyayari ayon sa mga pahayag tungkol sa mga halagang ito.
Ang mga unang round ng pederal na pagboto ay magaganap sa yugto ng nominasyon (bahagi ng nominasyon), sa isang hanay ng mga pahayag tulad ng "Inominate ko si V," marahil para sa maraming iba't ibang halaga ng V. Ang layunin ng nominasyon ay maghanap ng isa o higit pang mga pahayag na dumaan sa pagtanggap at pagkumpirma.
Pagkatapos makahanap ng mga nabe-verify na kandidato, lumipat ang SCP sa yugto ng pagboto, kung saan ang layunin ay makahanap ng isang tiyak na newsletter (iyon ay, isang lalagyan para sa iminungkahing halaga) at isang korum na maaaring magdeklara mangako para dito (commit). Kung ang isang korum ay gumawa ng isang balota, ang halaga nito ay tinatanggap bilang pinagkasunduan. Ngunit bago makaboto ang isang node sa isang commit ng balota, dapat muna itong kumpirmahin pawalang-bisa lahat ng balota na may mas mababang counter value. Ang mga hakbang na itoβpagkansela ng mga balota upang mahanap ang isa na maaaring gawinβay kinasasangkutan ng maraming round ng federated na pagboto sa maraming paghahabol sa balota.
Ang mga sumusunod na seksyon ay naglalarawan ng nominasyon at pagboto nang mas detalyado.
Nominasyon
Sa simula ng yugto ng nominasyon, ang bawat node ay maaaring kusang pumili ng halaga para sa V at bumoto para sa pahayag na "Inominate ko si V." Ang layunin sa yugtong ito ay kumpirmahin ang nominasyon ng ilang halaga sa pamamagitan ng federated vote.
Marahil sapat na mga node ang bumoto sa sapat na magkakaibang mga proposisyon na walang nominasyon ang makakaabot sa threshold ng pagtanggap. Samakatuwid, bilang karagdagan sa pagsasahimpapawid ng kanilang sariling mga boto sa nominasyon, ang mga node ay "sinasalamin" ang mga nominasyon ng kanilang mga kapantay. Nangangahulugan ang Echo na kung ang isang node ay bumoto para sa nominasyon V, ngunit nakakita ng isang mensahe mula sa isang kapitbahay na bumoto para sa nominasyon na W, ito ay boboto na ngayon para sa parehong V at W. (Hindi lahat ng mga peer na boto ay echoed sa panahon ng nominasyon dahil ito ay maaaring humantong sa isang pagsabog ng iba't ibang mga nominado. Kasama sa SCP ang isang mekanismo para i-regulate ang mga boto na ito. Sa madaling sabi, mayroong isang pormula para sa pagtukoy ng "priyoridad" ng isang peer mula sa punto ng view ng isang node, at tanging ang mga boto ng mga node na may mataas na priyoridad ang makikita. Kung mas mahaba ang nominasyon tumatagal, mas mababa ang threshold, kaya lumalawak ang node sa hanay ng mga peer na ang mga boto ay makikita nito. Kasama sa priority formula ang numero ng slot bilang isa sa mga input nito, kaya ang isang high-priority na peer para sa isang slot ay maaaring isang mababang priority na peer para sa isa pa, at kabaliktaran).
Sa konsepto, ang nominasyon ay magkapareho, parehong V at W ay magkahiwalay na pederal na boto, bawat isa ay indibidwal na may kakayahang makamit ang pagtanggap o kumpirmasyon. Sa pagsasagawa, pinagsama-sama ng mga mensahe ng protocol ng SCP ang mga indibidwal na boto na ito.
Bagama't ang pagboto para sa nominasyon ni V ay isang pangako na hindi kailanman bumoto laban sa nominasyon ni V, nasa antas ng aplikasyon - sa kasong ito SCP - na tinutukoy kung ano ang ibig sabihin ng "laban". Walang nakikitang pahayag ang SCP na sumasalungat sa boto na "Inominate ko ang X", ibig sabihin, walang mensaheng "Tutol ako sa pagnominate ng X", kaya maaaring bumoto ang node upang magmungkahi ng anumang mga halaga. Marami sa mga nominasyong ito ay wala nang patutunguhan, ngunit sa kalaunan ay magagawa ng node na tanggapin o kumpirmahin ang isa o higit pang mga halaga. Kapag ang isang nominado ay nakumpirma, siya ay nagiging kandidato.
Nominasyon ng SCP gamit ang federated voting. Maaaring magkaroon ng maraming mga halaga ng "B" na iniharap ng mga kapantay at "sinasalamin" ng node.
Ang mga nominasyon ay maaaring magresulta sa maraming kumpirmadong kandidato. Samakatuwid, hinihiling ng SCP ang layer ng aplikasyon na magbigay ng ilang paraan ng pagsasama-sama ng mga kandidato sa isa pinagsama-sama (composite). Ang paraan ng pagsali ay maaaring anuman. Ang pangunahing bagay ay kung ang pamamaraang ito ay deterministiko, kung gayon ang bawat node ay pagsasamahin ang parehong mga kandidato. Sa isang sistema ng pagboto sa tanghalian, ang "pag-iisa" ay maaaring mangahulugan lamang ng pagtanggi sa isa sa dalawang kandidato. (Ngunit sa isang tiyak na paraan: ang bawat node ay dapat pumili ng parehong halaga upang i-reset. Halimbawa, ang naunang pagpili sa alpabetikong pagkakasunud-sunod). Sa network ng pagbabayad ng Stellar, kung saan binoto ang kasaysayan ng transaksyon, ang pagsasama ng dalawang iminungkahing nominado ay kinabibilangan ng pagsasama-sama ng mga transaksyong nilalaman ng mga ito at ang pinakabago sa kanilang dalawang timestamp.
Ang SCP whitepaper ay nagpapatunay (Theorem 12) na sa pagtatapos ng yugto ng extension, ang network sa kalaunan ay nagtatagpo sa isang solong composite. Ngunit may problema: ang federated voting ay isang asynchronous protocol (tulad ng SCP). Sa madaling salita, ang mga node ay hindi nakaayos ayon sa oras, ngunit sa pamamagitan lamang ng mga mensaheng ipinadala nila. Mula sa punto ng view ng node, ito ay hindi malinaw kung kailan natapos yugto ng extension. At bagama't ang lahat ng mga node ay darating sa parehong composite, maaari silang kumuha ng iba't ibang mga ruta sa daan, na lumilikha ng iba't ibang mga composite na kandidato sa daan, at hindi kailanman masasabi kung alin ang huling.
Ngunit ito ay normal. Paghahanda lang ang nominasyon. Ang pangunahing bagay ay upang limitahan ang bilang ng mga kandidato upang makamit ang pinagkasunduan, na nangyayari sa proseso tumatakbo para sa opisina (pagboto).
Tumatakbo
Bulletin ay isang mag-asawa , kung saan ang counter ay isang integer na nagsisimula sa 1 at ang value ay isang kandidato mula sa yugto ng nominasyon. Ito ay maaaring sariling kandidato ng node o kandidato ng kalapit na node na tinanggap ng node na iyon. Sa halos pagsasalita, ang isang balota ay nagsasangkot ng mga paulit-ulit na pagtatangka na pilitin ang network na maabot ang isang pinagkasunduan sa ilang kandidato sa ilang balota sa pamamagitan ng paghawak ng potensyal na maraming pederasyon na mga boto sa mga pahayag ng balota. Sinusubaybayan ng mga tagabilang sa mga balota ang mga pagtatangka na ginawa, at ang mga balota na may mas mataas na bilang ay nangunguna sa mga balota na may mas mababang bilang. Kung ang newsletter natigil, magsisimula ang isang bagong boto, ngayon sa balota .
Mahalagang makilala kahulugan (halimbawa, ano dapat ang order ng tanghalian: pizza o salad), mga newsletter (counter-value pair) at pahayag tungkol sa mga balota. Kasama sa SCP round ang ilang round ng federal voting, partikular sa mga sumusunod na pahayag:
- "Handa akong gumawa ng balota B" at
- "Inaanunsyo ko ang commit ng balota B"
Mula sa pananaw ng isang partikular na node, naaabot ang pinagkasunduan kapag nakahanap ito ng balota B kung saan maaari nitong kumpirmahin (iyon ay, humanap ng isang korum na tumatanggap) ng pahayag na "I commit ballot B." Mula sa puntong ito, ligtas na kumilos sa halagang tinukoy sa B - halimbawa, paglalagay ng order na ito para sa tanghalian. Ito ay tinatawag na panlabasisasyon mga kahulugan. Kapag nakumpirma na ang pagtanggap sa balota, matitiyak ng isang node na ang anumang iba pang node ay naglabas ng parehong halaga o gagawin ito sa hinaharap.
Bagama't maraming mga pederasyong boto ang may konseptong isinasagawa sa mga paghahabol para sa maraming iba't ibang mga balota, hindi sila nagpapalitan ng kasing dami ng mga mensahe dahil ang bawat mensahe ay naglalaman ng ilang mga balota. Ang isang mensahe sa gayon ay nagtataguyod ng estado ng maraming pederasyon na mga boto nang sabay-sabay, halimbawa: βTinatanggap ko ang mga commit ballots mula sa dati "
Ano ang ibig sabihin ng mga katagang "handa" at "nakatuon"?
Bumoto ang isang node na gumawa ng balota kapag kumpiyansa itong hindi gagawa ng mga balota na may iba't ibang halaga ang ibang mga node. Kumbinsihin ito ang layunin ng paghahanda ng aplikasyon. Ang boto na nagsasabing "Handa akong gumawa ng balota B" ay isang pangakong hindi kailanman gagawa ng balotang mas maliit sa B, ibig sabihin, na may mas maliit na bilang (Inaatasan ng SCP na ang mga halaga sa mga balota ay nasa isang tiyak na pagkakasunud-sunod. Kaya, newsletter mas kaunti , kung N1
Bakit ang ibig sabihin ng βHanda akong gumawa ng balota Bβ ay βNangangako ako na hindi kailanman gagawa ng mga balotang mas maliit sa Bβ? Dahil tinukoy ng SCP ang abort bilang kabaligtaran ng commit. Ang isang boto upang maghanda ng isang balota ay nagsasangkot din ng isang boto upang idiskwalipika ang ilang iba pang mga balota, at, gaya ng tinalakay natin kanina, ang pagboto para sa isang bagay ay isang pangakong hindi kailanman bumoto laban dito.
Bago mag-broadcast ng commit, dapat munang maghanap ang isang node ng bulletin na makumpirma nito bilang inihanda. Sa madaling salita, nagsasagawa ito ng federated na boto sa paksang βHanda akong ibigay ang balota B,β posibleng sa maraming iba't ibang balota, hanggang sa makahanap ito ng tumatanggap ng isang korum.
Saan nagmula ang mga balota upang ihanda ang boto? Una, ang node ay nagbo-broadcast ng mga paghahanda para bumoto para sa <1,C>, kung saan ang C ay ang pinagsama-samang kandidato na ginawa sa yugto ng nominasyon. Gayunpaman, kahit na nagsimula ang paghahanda para sa pagboto, ang mga nominasyon ay maaaring magresulta sa mga karagdagang kandidato na lumilitaw upang maging mga bagong balota. Samantala, ang mga kapantay ay maaaring magkaroon ng iba't ibang kandidato, at maaari silang bumuo ng blocking set na tumatanggap ng "Handa akong ibigay ang B2 na balota," na kumbinsihin ang node na tanggapin din ito. Sa wakas, mayroong mekanismo ng timeout na bumubuo ng mga bagong round ng federated na pagboto sa mga bagong balota na may mas mataas na bilang kung ang kasalukuyang mga balota ay natigil.
Sa sandaling mahanap ng node ang isang balota B na maaari nitong kumpirmahin bilang inihanda, i-broadcast nito ang isang bagong mensahe na "I-commit ang balota B." Ang boto na ito ay nagsasabi sa mga kapantay na ang node ay hindi kailanman susuko sa B. Sa katunayan, kung ang B ay isang balota , pagkatapos ay βMag-commit ng balota " ay nangangahulugan ng walang kundisyong pahintulot na bumoto para sa kahandaan ng bawat balota mula sa sa <β, s>. Ang sobrang halagang ito ay nakakatulong sa iba pang mga kapantay na makahabol sa commit na peer kung sila ay nasa mga naunang yugto pa rin ng protocol.
Sa yugtong ito, ito ay nagkakahalaga ng pagbibigay-diin muli na ang mga ito ay mga asynchronous na protocol. Hindi nangangahulugan na ang isang node ay nagpapadala ng mga upvote para sa isang commit ay nangangahulugang ginagawa din ito ng mga kapantay nito. Ang ilan sa kanila ay maaaring bumoboto pa rin sa mga pahayag bilang paghahanda sa pagboto, ang iba ay maaaring na-externalize na ang kahulugan. Ipinapaliwanag ng SCP kung paano dapat iproseso ng isang node ang bawat uri ng peer message anuman ang bahagi nito.
Kung ang mensaheng "I have announced a commit Β» hindi maaaring matanggap o makumpirma, iyon ay, ang posibilidad na ang mensahe ay matanggap o makumpirma o - o, sa anumang kaso, anumang balota na may halagang C, at hindi anumang iba pa, dahil ang node ay nangako nang hindi kailanman magkansela . Sa oras na ang isang node ay mag-broadcast ng mga boto para sa isang commit, ito ay magiging C o wala, depende sa kung gaano kalayo ang pinagkasunduan. Gayunpaman, hindi pa ito sapat para ma-externalize ng node ang C. Maaaring magsinungaling ang ilang mga Byzantine na kapantay (na mas mababa sa isang korum, batay sa aming mga pagpapalagay sa seguridad) sa node. Ang pagtanggap at pagkatapos ay pagkumpirma ng ilang balota (o hanay ng mga balota) ang nagbibigay ng kumpiyansa sa node na tuluyang ma-externalize ang C.
SCP voting sa pamamagitan ng federated voting. Hindi ipinapakita: Ang timer ay maaaring tumunog anumang oras, na nagpapataas ng bilang sa balota (at posibleng makagawa ng bagong composite ng mga karagdagang hinirang na kandidato).
At lahat na! Kapag naabot na ng network ang isang pinagkasunduan, handa na itong gawin muli at muli. Sa network ng pagbabayad ng Stellar, nangyayari ito nang humigit-kumulang isang beses bawat 5 segundo: isang gawaing nangangailangan ng parehong seguridad at kaligtasan na ginagarantiyahan ng SCP.
Maaabot ito ng SCP sa pamamagitan ng pag-asa sa maraming round ng federated voting. Ang federated na pagboto ay naging posible sa pamamagitan ng konsepto ng mga hiwa ng korum: mga hanay ng mga kapantay na napagpasyahan ng bawat node na pagkatiwalaan bilang bahagi ng (subjective) na korum nito. Ang pagsasaayos na ito ay nangangahulugan na ang consensus ay maaaring maabot kahit sa isang network na may bukas na membership at mga panlilinlang ng Byzantine.
Karagdagang pagbabasa
- Ang orihinal na puting papel ng SCP ay matatagpuan At draft na mga detalye para sa pagpapatupad nito.
- Ang orihinal na may-akda ng SCP protocol, si David Mazier, ay nagpapaliwanag nito sa isang pinasimple (ngunit teknikal pa rin) na paraan. .
- Maaaring nagulat ka na hindi mahanap ang mga terminong "pagmimina" o "patunay ng trabaho" sa artikulong ito. Hindi ginagamit ng SCP ang mga pamamaraang ito, ngunit ginagawa ng ilang iba pang mga algorithm ng pinagkasunduan. Sinulat ni Zane Witherspoon na naa-access .
- isang simpleng network na umabot sa consensus sa isang buong round ng SCP.
- Para sa mga mambabasa na interesado sa mga pagpapatupad ng SCP: tingnan , na ginagamit ng network ng pagbabayad ng Stellar, o , na isinulat ko para sa isang mas mahusay na pag-unawa sa SCP.
Pinagmulan: www.habr.com