Ang Stellar consensus protocol una nga gihulagway sa David Mazier niadtong 2015. Kini usa ka "federal Byzantine agreement system" nga nagtugot sa desentralisado, walay lider nga mga network sa kompyuter nga epektibong makab-ot ang konsensus sa usa ka desisyon. Ang network sa pagbayad sa Stellar naggamit sa Stellar Consensus Protocol (SCP) aron mapadayon ang makanunayon nga kasaysayan sa transaksyon nga makita sa tanan nga mga partisipante.
Ang mga protocol sa consensus giisip nga lisud sabton. Ang SCP mas simple kay sa kadaghanan kanila, apan nag-ambit gihapon niini nga reputasyon - bahin tungod sa sayop nga ideya nga ang "federated voting", nga mao ang hilisgutan sa unang katunga sa siyentipikong artikulo, mao ang SCP. Apan dili kana tinuod! Kini usa lamang ka importante nga bloke sa pagtukod nga gigamit sa ikaduhang katunga sa artikulo sa paghimo aktuwal Stellar consensus protocol.
Niini nga artikulo atong ipasabut sa daklit kung unsa ang usa ka "sistema sa mga kasabutan", unsa ang makahimo niini nga "Byzantine" ug nganong gihimo ang sistema sa Byzantine nga "federal". Atong ipasabot unya ang federated voting procedure nga gihulagway sa SCP nga artikulo, ug sa kataposan atong ipasabot ang SCP protocol mismo.
Mga sistema sa kasabutan
Ang usa ka sistema sa mga kasabutan nagtugot sa usa ka grupo sa mga partisipante sa pagkab-ot sa usa ka consensus sa usa ka hilisgutan, sama sa unsay i-order alang sa paniudto.
Sa Interstellar, gipatuman namo ang among kaugalingong sistema sa kasabotan sa pagpangaon: among gi-order ang giingon sa among operations manager, si John. Kini usa ka yano ug epektibo nga sistema sa kasabutan. Kitang tanan misalig kang John ug nagtuo nga siya makakitag butang nga makapainteres ug masustansya kada adlaw.
Apan komosta kon abusohan ni Juan ang atong pagsalig? Makahukom siya nga mag-inusara nga kitang tanan mahimong mga vegan. Sa usa o duha ka semana, lagmit atong mapukan siya ug itugyan ang gahom kang Elizabeth. Apan sa kalit siya nahigugma sa mga avocado nga adunay dilis ug naghunahuna nga ang tanan kinahanglan nga ingon niana. Ang gahum makadaot. Mao nga mas maayo nga mangita usa ka labi ka demokratikong pamaagi: usa ka paagi aron masiguro nga ang lainlaing mga gusto gikonsiderar, samtang gisiguro ang usa ka tukma sa panahon ug dili klaro nga sangputanan, aron wala’y usa nga magtapos sa pag-order sa paniudto, o lima ka tawo ang nagbutang sa lainlaing mga order, o ang panaghisgot. nagdagan hangtod sa gabii.
Morag simple ra ang solusyon: pagpahigayon og boto! Apan kini usa ka makapahisalaag nga impresyon. Kinsa ang mokolekta sa mga balota ug magreport sa mga resulta? Kag ngaa dapat patihan sang iban ang iya ginasiling? Tingali mahimo nato sa una boto alang sa usa ka lider nga among gisaligan nga manguna sa pagboto - apan kinsa ang manguna niini una pinaagi sa pagboto? Unsa kaha kon dili kita magkasinabot sa usa ka lider? O unsa kaha kung magkasinabot kita, apan kini nga lider ma-stuck sa usa ka miting o moadto sa sick leave?
Ang susamang mga problema mahitabo sa gipang-apod-apod nga mga network sa kompyuter. Ang tanang partisipante o mga node kinahanglang magkauyon sa pipila ka desisyon, sama sa kang kinsang turno ang pag-update sa usa ka shared file o pagtangtang sa usa ka buluhaton gikan sa processing queue. Sa usa ka network sa cryptocurrency, ang mga node balik-balik nga kinahanglan nga mopili kung unsa ang hitsura sa tibuuk nga istorya gikan sa daghang posible nga mga bersyon, nga usahay magkasumpaki. Kini nga kasabutan sa network naghatag kasiguruhan sa nakadawat nga ang sensilyo (a) balido (dili peke) ug (b) wala pa gigasto sa ubang lugar. Gisiguro usab niini nga makagasto siya sa mga sensilyo sa umaabot tungod kay ang bag-ong nakadawat adunay parehas nga garantiya alang sa parehas nga mga hinungdan.
Ang bisan unsang consensus system sa usa ka distributed computing network kinahanglan nga fault-tolerant: kini kinahanglan nga mopatunghag makanunayon nga mga resulta bisan pa sa mga sayop sama sa hinay nga mga link, dili motubag nga mga node, ug dili husto nga pag-order sa mensahe. Byzantine Ang sistema sa kasabotan dugang nga makasugakod sa "Byzantine" nga mga sayop: mga node nga naghatag ug sayop nga impormasyon, bisan tungod sa usa ka sayop o sa tinuyo nga pagsulay sa pagdaot sa sistema o pagbaton ug pipila ka bentaha. Ang "Byzantine" fault tolerance - ang abilidad sa pagsalig sa usa ka desisyon sa grupo bisan kung ang pipila ka mga miyembro sa grupo mahimong mamakak o kung dili mosunod sa mga lagda sa paghimo og desisyon - gitawag kinsa misulay sa pag-coordinate sa pag-atake. sa Anthony Stevens.
Hunahunaa ang tag-iya sa crypto coin nga si Alice, kinsa kinahanglang mopili tali sa pagpalit ug lamiang ice cream gikan kang Bob ug pagbayad sa utang ni Carol. Tingali gusto ni Alice nga bayran silang duha sa usa ka higayon pinaagi sa malimbongon nga paggasto sa parehas nga sensilyo. Aron mahimo kini, kinahanglan niyang kombinsihon ang kompyuter ni Bob nga ang sensilyo wala gayud ibayad ngadto kang Carol, ug kombinsihon ang kompyuter ni Carol nga ang sensilyo wala gayud ibayad kang Bob. Ang sistema sa mga kasabutan sa Byzantine naghimo niini nga halos imposible, gamit ang usa ka porma sa kadaghanan nga lagda nga gitawag korum. Ang usa ka node sa ingon nga network nagdumili sa pagbalhin sa usa ka partikular nga bersyon sa kasaysayan hangtod nga makita nga usa ka igo nga gidaghanon sa mga kauban - usa ka korum - miuyon sa ingon nga pagbalhin. Kung mahitabo na kini, maghimo sila usa ka bloke sa pagboto nga adunay igo nga kadako aron mapugos ang nahabilin nga mga node sa network nga mouyon sa ilang desisyon. Mahimong pugson ni Alice ang pipila ka mga node sa pagpamakak alang kaniya, apan kung ang network igo nga kadako, ang iyang pagsulay mabug-atan sa mga boto sa mga matinud-anon nga mga node.
Pila ka buko ang gikinahanglan para sa korum? Sa labing gamay, usa ka kadaghanan, o labi pa, usa ka kwalipikado nga kadaghanan nga makigbatok sa mga sayup ug pagpanglimbong. Apan aron maihap ang kadaghanan, kinahanglan nimo mahibal-an ang kinatibuk-ang gidaghanon sa mga partisipante. Sa opisina sa Interstellar o sa mga eleksyon sa distrito, kini nga mga numero dali nga mahibal-an. Apan kung ang imong grupo usa ka luag nga gihubit nga network diin ang mga node mahimong mosulod ug mobiya sa gusto nga wala’y pagtugot gikan sa sentro, nan kinahanglan nimo pederal usa ka sistema sa kasabotan sa Byzantine nga makahimo sa pagdeterminar sa mga korum dili gikan sa gitakda nang daan nga listahan sa mga node, apan sa dinamikong paagi, gikan sa kanunay nga nag-usab-usab ug dili kalikayan nga dili kompleto nga snapshot sa mga node sa gihatag nga punto sa panahon.
Morag imposible ang paghimo og usa ka korum gikan sa panglantaw sa usa ka node sa usa ka halapad nga network, apan kini posible. Ang maong korum makagarantiya pa gani sa resulta sa desentralisadong pagboto. Ang puti nga papel sa SCP nagpakita kon unsaon pagbuhat niini gamit ang gitawag nga pamaagi pinaagi sa pederal nga boto.
Para sa mga walay pasensya
Ang nahabilin sa artikulo naghulagway sa federated voting ug ang Stellar consensus protocol sa mas detalyado. Kung dili ka interesado sa mga detalye, ania ang usa ka kinatibuk-ang pagtan-aw sa proseso.
- Ang mga node nagpahigayon mga hugna sa federal nga pagboto sa "mga nominado." Ang pederal nga hugna sa pagboto nagpasabut:
- Ang node nagboto alang sa pipila ka pahayag, pananglitan, "Akong gisugyot ang bili sa V";
- Ang node maminaw sa mga tingog sa mga kaedad hangtod nga makit-an ang usa nga "makadawat";
- Ang node nangita alang sa usa ka "korum" alang niini nga pagpahayag. Ang usa ka korum “nagpamatuod” sa nominado.
- Sa higayon nga makumpirma sa usa ka node ang usa o daghan pa nga mga nominado, kini mosulay sa "pag-andam" sa "boto" pinaagi sa daghang mga hugna sa federated nga pagboto.
- Sa higayon nga mapamatud-an sa usa ka node nga andam na ang balota, kini mosulay sa paghimo niini pinaagi sa mas daghang hugna sa pederasyon nga pagboto.
- Sa higayon nga ang usa ka node makakumpirma sa usa ka commit sa usa ka balota, kini mahimong "externalize" ang bili sa maong balota pinaagi sa paggamit niini ingon nga usa ka consensus nga resulta.
Kini nga mga lakang naglakip sa daghang mga hugna sa pederasyon nga pagboto, nga hiniusang nagporma usa ka hugna sa SCP. Atong tan-awon pag-ayo kon unsay mahitabo sa matag lakang.
Federated nga pagboto
Ang federated voting usa ka pamaagi sa pagtino kung ang network makauyon ba sa usa ka proposal. Sa round sa pagboto, ang matag node kinahanglang mopili og usa sa posibleng daghan nga posibleng mga bili. Dili kini mahimo gawas kung kini masaligon nga ang ubang mga node sa network dili mopili ug lahi nga sangputanan. Aron masiguro kini, ang mga node magbinayloay sa usa ka barrage sa mga mensahe pabalik-balik aron ang tanan gipamatud-an, kana korum buhol gidawat sama nga butang ang desisyon. Ang nahabilin niini nga seksyon nagpatin-aw sa mga termino niini nga sentence ug kung giunsa ang tibuok nga pamaagi mahitabo.
Mga korum ug mga hiwa sa korum
Magsugod kita pinaagi sa pagtino sa usa ka korum. Sama sa atong gihisgutan sa ibabaw, sa usa ka desentralisado nga network nga adunay dinamikong membership, imposible nga mahibal-an daan ang gidaghanon sa mga node ug busa pila ang gikinahanglan alang sa kadaghanan. Gisulbad sa federated voting kini nga problema pinaagi sa pagpaila sa usa ka bag-ong ideya pagputol sa korum (hiwa sa korum): Usa ka gamay nga hugpong sa mga kaedad nga gisaligan sa usa ka node aron ipahibalo ang kasayuran sa kahimtang sa pagboto sa ubang bahin sa network. Ang matag node naghubit sa kaugalingon nga hiwa sa korum (diin kini mahimong de facto nga miyembro).
Ang pagporma sa korum magsugod sa pagputol sa korum. Alang sa matag node, ang giputol nga mga node idugang. Dayon ang mga termino sa slice gidugang kini nga mga node ug uban pa. Sa imong pagpadayon, nagkadaghan ang mga node nga dili nimo madugang tungod kay naapil na sila sa slice. Kung wala nay bag-ong mga node nga idugang, ang proseso mohunong: naghimo kami og korum pinaagi sa "transitive closure" sa hiwa sa korum sa inisyal nga node.
Aron makit-an ang korum gikan sa gihatag nga node...
... idugang ang mga miyembro sa iyang slice...
...dayon atong idugang ang mga miyembro sa slice niini nga mga node.
Nagpadayon kami hangtod nga wala nay nahabilin nga mga node nga idugang.
Wala nay mga node nga idugang. Kini usa ka korum.
Sa tinuud, ang matag node mahimong makita sa labaw sa usa ka hiwa. Aron maporma ang usa ka korum, pagpili lamang og usa sa mga hiwa ug pagdugang og mga miyembro; unya pilia ang bisan unsang hiwa alang sa matag usa sa mga miyembro ug idugang ang mga miyembro kini putlon ug uban pa. Kini nagpasabut nga ang matag node usa ka miyembro sa daghang posible nga mga korum.
Pagpili lamang og usa ka hiwa sa korum sa matag lakang.
Usa ka posible nga korum. O alternatibo...
...pagpili ug ubang mga hiwa...
…(kung mahimo)…
... nagmugna og laing korum.
Giunsa pagkahibalo sa usa ka node kung unsang mga hiwa ang naa sa ubang mga node? Sa parehas nga paagi sama sa ubang impormasyon bahin sa ubang mga node: gikan sa mga transmission nga gisibya sa matag node ngadto sa network kung ang estado sa pagboto niini mausab. Ang matag sibya naglakip sa impormasyon bahin sa mga hiwa sa pagpadala sa node. Ang puti nga papel sa SCP wala magtino sa mekanismo sa komunikasyon. Ang mga pagpatuman kasagarang gigamit alang sa garantiya nga pagsibya sa mga mensahe sa tibuok network.
Hinumdumi nga sa dili pederal nga Byzantine nga sistema sa mga kasabutan, ang usa ka korum gihubit nga kadaghanan sa tanan nga mga node. Ang sistema sa kasabotan sa Byzantine gidesinyo gikan sa punto sa panglantaw sa pangutana: pila ka dili matinud-anon nga mga buko ang maagwanta sa sistema? Sa usa ka sistema sa mga N node nga gidisenyo aron mabuhi sa mga kapakyasan, ang usa ka node kinahanglan nga makahimo sa pag-uswag pinaagi sa pagdawat og feedback gikan sa N−f mga kaedad tungod kay ang f niini mahimong ubos. Apan sa nakadawat ug tubag gikan sa N−f mga kaedad, atong mahunahuna nga ang tanan nga f kaedad (nga gikan sa node wala makadawat ug tubag) tinuod nga matinud-anon. Busa, f gikan sa N−f mga kaedad (diin nadawat ang tubag) malisyoso. Alang sa mga node nga moabut sa parehas nga consensus, ang kadaghanan sa nahabilin nga mga node kinahanglan nga matinud-anon, nga mao, kinahanglan naton ang N−f nga labi ka dako sa 2f o N> 3f. Mao nga kasagaran ang usa ka sistema nga gidisenyo aron mabuhi ang mga kapakyasan adunay kinatibuk-an nga N=3f+1 nga mga node ug usa ka gidak-on sa korum nga 2f+1. Sa higayon nga ang usa ka proposal makapasar sa quorum threshold, ang uban sa network kombinsido nga ang bisan unsa nga kompetisyon nga mga proposal mapakyas. Mao kini ang paagi nga ang network naghiusa sa resulta.
Apan sa usa ka pederal nga sistema sa kasabutan sa Byzantine, dili lamang mahimo nga wala’y kadaghanan (tungod kay wala’y nahibal-an ang kinatibuk-ang gidak-on sa network), apan ang konsepto sa kadaghanan hingpit nga wala’y kapuslanan! Kung ang pagkamiyembro sa sistema bukas, nan ang usa ka tawo makakuha og kadaghanan pinaagi lamang sa paghimo sa usa ka gitawag nga pag-atake sa Sybil: balik-balik nga pag-apil sa network sa daghang mga node. Busa nganong matawag ang transitive slice closure korum, ug sa unsang paagi kini makasumpo sa mga sugyot nga nakigkompetensya?
Sa teknikal, dili mahimo! Hunahunaa ang usa ka network sa unom ka mga buko, diin duha ka triplet ang gilain sa usag usa nga mga hiwa sa korum. Ang una nga subgroup mahimo’g maghimo usa ka desisyon nga dili gyud madungog sa ikaduha, ug vice versa. Walay paagi alang niini nga network nga makaabot sa consensus (gawas sa sulagma).
Busa, ang SCP nagkinahanglan nga alang sa federated voting (ug para sa importante nga theorems sa papel nga magamit), ang network kinahanglan adunay usa ka kabtangan nga gitawag intersection sa mga korum. Sa usa ka network nga adunay kini nga kabtangan, ang bisan unsang duha nga mga korum nga mahimong matukod kanunay nga magsapaw sa labing menos usa ka node. Alang sa pagtino sa nagpatigbabaw nga sentimento sa network, kini sama ka maayo nga adunay kadaghanan. Sa intuitive nga paagi, kini nagpasabut nga kung adunay bisan unsang korum nga mouyon sa pahayag nga X, wala’y lain nga korum nga makauyon sa bisan unsa pa, tungod kay kinahanglan nga maglakip kini pipila ka node gikan sa una nga korum nga nakaboto na alang sa X.
Kung adunay intersection sa mga korum sa network...
...dayon bisan unsang duha ka korum nga imong matukod...
...mag-intersect kanunay.
(Siyempre, ang nagsapaw-sapaw nga mga node mahimong mahimong Byzantine-bakak o dili maayo. Niini nga kaso, ang intersection sa korum dili makatabang sa network nga magkauyon. Tungod niini, daghan sa mga resulta sa puti nga papel sa SCP gibase sa tin-aw nga mga pangagpas, sama sa kung unsa ang nahabilin sa pagtabok sa korum sa network bisan human sa pagtangtang sa dili maayo nga mga node. Alang sa kayano, biyaan nato kini nga mga pangagpas implicit sa ubang bahin sa artikulo).
Morag dili makatarunganon ang pagdahum nga ang usa ka kasaligan nga pagtabok sa korum posible sa usa ka network sa mga independente nga node. Apan adunay duha ka rason nganong ingon niini.
Ang unang rason mao ang paglungtad sa Internet mismo. Ang Internet usa ka hingpit nga ehemplo sa usa ka network sa mga independente nga mga node nga adunay intersecting nga mga korum. Kadaghanan sa mga node sa Internet nagkonektar sa pipila lamang sa ubang mga lokal nga node, apan kini nga gagmay nga mga set igo nga nagsapaw nga ang matag node maabot gikan sa uban nga mga node sa pipila ka ruta.
Ang ikaduha nga rason mao ang espesipiko sa network sa pagbayad sa Stellar (ang labing komon nga paggamit sa SCP). Ang matag asset sa Stellar network adunay issuer, ug ang Stellar's guidelines nagkinahanglan sa matag issuer nga magtudlo ug usa o daghan pang node sa network aron maproseso ang mga hangyo sa pagtubos. Alang sa imong labing kaayo nga interes nga direkta o dili direkta nga ilakip kini nga mga node sa mga hiwa sa korum alang sa matag asset nga interesado ka. Ang mga korum para sa tanang node nga interesado sa usa ka gihatag nga asset magsapaw sa labing menos niadtong mga redemption node. Ang mga node nga interesado sa daghang mga asset maglakip sa tanang redemption node sa tagsa-tagsa nga mga nag-isyu sa ilang mga hiwa sa korum, ug sila maninguha sa paghiusa sa tanang mga kabtangan. Dugang pa, ang bisan unsang mga kabtangan nga wala ma-link niini nga paagi sa uban sa network, ug dili angay konektado - kini gidisenyo aron walay quorum overlap alang niini nga network (pananglitan, ang mga bangko gikan sa dollar zone usahay gusto nga makignegosyo sa mga bangko gikan sa euro zone ug mga bangko gikan sa peso zone, mao nga sila anaa sa sama nga network, apan wala kanila nagpakabana sa bulag nga network sa mga bata nga namaligya og mga baseball card).
Siyempre, pagpaabot ang pagtabok sa korum dili garantiya. Ang ubang mga sistema sa kasabotan sa Byzantine nakautang sa kadaghanan sa ilang pagkakomplikado sa garantiya sa mga korum. Usa ka importante nga kabag-ohan sa SCP mao nga kini nagtangtang sa responsibilidad sa paghimo sa mga korum gikan sa consensus algorithm mismo ug nagdala niini sa lebel sa aplikasyon. Sa ingon, bisan kung ang federated nga pagboto igo nga kinatibuk-an aron makaboto sa bisan unsang isyu, ang kasaligan niini sa tinuud nagdepende sa labi ka lapad nga kahulugan niini nga mga kahulugan. Ang ubang mga hypothetical nga paggamit mahimong dili sama ka maayo sa paghimo og maayo nga konektado nga mga network sama sa uban.
Pagboto, pagdawat ug pagkumpirma
Sa usa ka federated voting round, usa ka node ang opsyonal nga magsugod sa pagbotar alang sa pipila ka bili nga V. Kini nagpasabot sa pagsibya sa usa ka mensahe ngadto sa network: "Ako node N, ang akong mga hiwa sa korum kay Q, ug ako nagbotar sa V." Kung ang usa ka node mobotar niining paagiha, kini nagsaad nga kini wala gayud mobotar batok sa V ug dili gayud.
Sa peer-to-peer nga mga sibya, makita sa matag node kung giunsa pagboto sa uban. Sa higayon nga ang usa ka node nakakolekta na og igo niini nga mga mensahe, kini makasubay sa mga hiwa sa korum ug maningkamot sa pagpangita og mga korum. Kung makakita siya og korum sa mga kaedad nga mobotar usab kang V, makapadayon siya pagsagop V ug i-broadcast kining bag-ong mensahe ngadto sa network: “Ako si node N, ang akong mga hiwa sa korum kay Q, ug akong gidawat ang V.” Ang pagdawat naghatag og mas lig-on nga garantiya kay sa yano nga pagboto. Kung ang usa ka node mobotar alang sa V, dili kini makabotar sa ubang mga kapilian. Apan kung ang usa ka node modawat sa V, walay node sa Network ang modawat sa laing kapilian (Theorem 8 sa SCP whitepaper nagpamatuod niini).
Siyempre, adunay taas nga posibilidad nga wala dayon usa ka korum sa mga node nga mouyon sa V. Ang ubang mga node mahimong mobotar sa ubang mga mithi. Apan adunay laing paagi alang sa usa ka node nga mobalhin gikan sa yano nga pagboto ngadto sa pagdawat. Mahimong modawat si N og lain nga bili para sa W, bisan og wala siya mobotar niini, ug bisan og wala siya makakita og korum niini. Para makadesisyon nga usbon ang imong boto, tan-awa lang blocking set node nga midawat sa W. Ang blocking set usa ka node gikan sa matag usa sa mga hiwa sa korum N. Ingon sa gisugyot sa ngalan, mahimo kini babagan bisan unsa nga lain nga kahulogan. Kung ang tanan nga mga node sa ingon nga usa ka set modawat sa W, nan (sa Theorem 8) dili gyud posible nga maporma ang usa ka korum nga nagkuha usa ka lahi nga kantidad, ug busa luwas usab alang sa N nga modawat sa W.
Node N nga adunay tulo ka hiwa sa korum.
Ang BDF usa ka blocking set alang sa N: kini naglakip sa usa ka node gikan sa matag usa sa mga hiwa sa N.
Ang BE usa usab ka blocking set alang sa N tungod kay ang E makita sa duha ka hiwa sa N.
Apan ang blocking set dili usa ka korum. Sayon ra kaayo ang paglimbong sa node N sa pagdawat sa gitinguha nga kantidad kung igo na ang pag-hack sa usa lang ka node sa matag usa sa mga hiwa sa N. Busa, ang pagdawat sa kantidad dili katapusan sa pagboto. Hinuon, kinahanglan nga kumpirmahon sa N ang kantidad, nga mao, tan-awa ang usa ka korum sa mga node nga nagdawat niini. Kung ingon niana ka layo, nan, ingon sa gipamatud-an sa whitepaper sa SCP (sa Theorem 11), ang nahabilin sa network sa katapusan makumpirma usab ang parehas nga kantidad, mao nga tapuson sa N ang pederasyon nga boto nga adunay piho nga kantidad ingon sangputanan.
Federated nga pagboto.
Ang proseso sa pagboto, pagdawat, ug pagkumpirma naglangkob sa usa ka bug-os nga hugna sa federated nga pagboto. Ang Stellar consensus protocol naghiusa sa daghan niini nga mga hugna aron makahimo og usa ka kompleto nga consensus system.
Stellar Consensus Protocol
Ang duha ka labing importante nga mga kabtangan sa usa ka consensus system mao ang − luwas и pagkaluwas. Ang usa ka consensus algorithm "luwas" kung dili kini makahatag ug lain-laing mga resulta sa lain-laing mga partisipante (ang kopya sa kasaysayan ni Bob dili gayud mosupak ni Carol). Ang "Livability" nagpasabot nga ang algorithm kanunay nga magpatunghag resulta, nga mao, dili kini ma-stuck.
Gihulagway nga federal nga pamaagi sa pagboto luwas sa diwa nga kung ang usa ka node nagpamatuod sa bili sa V, walay laing node nga mokumpirma sa laing bili. Apan ang "dili magpamatuod sa laing kahulogan" wala magpasabot nga kini magpamatuod sa usa ka butang. Ang mga partisipante mahimong makabotar sa daghang lain-laing mga kantidad nga wala’y makaabut sa threshold sa pagdawat. Kini nagpasabot nga sa federal voting walay pagkaluwas.
Ang Stellar consensus protocol naggamit sa federated voting sa paagi nga nagsiguro sa seguridad ug survivability. (Ang mga garantiya sa seguridad ug survivability sa SCP adunay teoretikal nga limitasyon. Ang disenyo nagpili sa usa ka lig-on kaayo nga garantiya sa seguridad, nagsakripisyo sa usa ka gamay nga survivability mitigation, apan gihatagan og igong panahon, ang consensus lagmit nga makab-ot.) Sa laktud nga pagkasulti, ang ideya mao ang pagbaton og daghang mga pederasyon nga mga boto sa daghang mga kantidad hangtod ang usa niini makaagi sa tanan nga mga hugna sa pagboto sa SCP nga gihulagway sa ubos.
Ang mga kantidad nga gipangita sa SCP nga konsensus mahimong kasaysayan sa transaksyon o usa ka order sa paniudto o uban pa, apan hinungdanon nga timan-an nga dili kini ang mga kantidad nga gidawat o gikumpirma. Hinuon, ang pederal nga pagboto mahitabo sumala sa mga pahayag mahitungod niini nga mga mithi.
Ang unang hugna sa federal nga pagboto mahitabo sa yugto sa nominasyon (bahin sa nominasyon), sa usa ka hugpong sa mga pahayag sama sa "Gi-nominate nako si V," tingali alang sa daghang lainlaing mga kantidad sa V. Ang katuyoan sa nominasyon mao ang pagpangita sa usa o daghang mga pahayag nga moagi sa pagdawat ug pagkumpirma.
Human makit-an ang mapamatud-an nga mga kandidato, ang SCP mopadayon sa yugto sa pagboto, diin ang katuyoan mao ang pagpangita sa usa ka piho. buletin (nga mao, usa ka sudlanan alang sa gisugyot nga bili) ug usa ka korum nga makapahayag pasalig para niini (commit). Kon ang usa ka korum mohimo og balota, ang bili niini dawaton isip consensus. Apan sa dili pa makabotar ang usa ka node sa usa ka commit sa balota, kinahanglan una kini nga kumpirmahon pagkansela tanang balota nga adunay mas ubos nga counter value. Kini nga mga lakang—pagkansela sa mga balota aron makit-an ang usa nga mahimo—naglakip sa daghang hugna sa federated nga pagboto sa daghang mga pag-angkon sa balota.
Ang mosunod nga mga seksyon naghulagway sa nominasyon ug pagboto sa mas detalyado.
Nominasyon
Sa sinugdanan sa hugna sa nominasyon, ang matag node mahimong kusang makapili og usa ka bili alang sa V ug mobotar sa pahayag nga "I nominate si V." Ang tumong niini nga yugto mao ang pagkumpirma sa nominasyon sa pipila ka bili pinaagi sa federated vote.
Tingali igo nga mga node ang nagboto sa igo nga lainlaing mga proposisyon nga wala’y nominasyon nga makaabut sa threshold sa pagdawat. Busa, dugang sa pagsibya sa ilang kaugalingong mga boto sa nominasyon, ang mga node "nagpakita" sa mga nominasyon sa ilang mga kaedad. Ang echo nagpasabot nga kung ang usa ka node mobotar sa nominasyon nga V, apan makakita og mensahe gikan sa silingan nga mobotar sa nominasyon nga W, kini karon mobotar na sa V ug W. lain-laing mga nominado. Ang SCP naglakip sa usa ka mekanismo sa pag-regulate niini nga mga boto. Sa laktud, adunay usa ka pormula sa pagtino sa "priority" sa usa ka kaedad gikan sa punto sa panglantaw sa usa ka node, ug ang mga boto lamang sa mga high priority node ang makita. Mas taas ang nominasyon mokuha, mas ubos ang threshold, mao nga ang node mopalapad sa set sa mga kaedad kansang mga boto makita niini. lain, ug vice versa).
Sa konsepto, ang nominasyon managsama, ang V ug W managsama nga pederal nga mga boto, ang matag usa adunay katakus sa pagkab-ot sa pagdawat o pagkumpirma. Sa praktis, ang mga mensahe sa protocol sa SCP nag-package niining mga indibidwal nga mga boto.
Bisan pa nga ang pagbotar sa nominasyon ni V usa ka saad nga dili gyud mobotar batok sa nominasyon ni V, anaa sa lebel sa aplikasyon - sa niini nga kaso SCP - nga matino kung unsa ang gipasabut sa "batok". Ang SCP wala makakita og pahayag nga sukwahi sa "I nominate X" nga boto, sa ato pa, walay "Ako batok sa pag-nominate sa X" nga mensahe, mao nga ang node makabotar sa pag-nominate sa bisan unsang mga bili. Daghan niini nga mga nominasyon dili moadto bisan asa, apan sa katapusan ang node makahimo sa pagdawat o pagkumpirma sa usa o daghan pa nga mga kantidad. Kung makumpirma ang usa ka nominado, mahimo na siya kandidato.
Nominasyon sa SCP gamit ang federated voting. Mahimong adunay daghang "B" nga mga kantidad nga gibutang sa unahan sa mga kaedad ug "gipakita" sa node.
Ang mga nominasyon mahimong moresulta sa daghang nakumpirma nga mga kandidato. Busa, gikinahanglan sa SCP ang application layer nga maghatag ug pipila ka pamaagi sa paghiusa sa mga kandidato ngadto sa usa composite (composite). Ang paagi sa pag-apil mahimong bisan unsa. Ang nag-unang butang mao nga kung kini nga pamaagi deterministiko, nan ang matag node maghiusa sa parehas nga mga kandidato. Sa sistema sa pagboto sa paniudto, ang "paghiusa" mahimong magpasabot lamang sa pagsalikway sa usa sa duha ka kandidato. (Apan sa usa ka deterministikong paagi: ang matag node kinahanglang mopili sa samang kantidad nga i-reset. Pananglitan, ang naunang pagpili sa alpabetikong han-ay). Sa Stellar nga network sa pagbayad, diin ang kasaysayan sa transaksyon gibotohan, ang paghiusa sa duha ka gisugyot nga mga nominado naglakip sa paghiusa sa mga transaksyon nga anaa niini ug ang pinakaulahi sa ilang duha ka timestamp.
Gipamatud-an sa whitepaper sa SCP (Theorem 12) nga sa pagtapos sa yugto sa extension, ang network sa kadugayan maghiusa sa usa ka composite. Apan adunay problema: ang federated voting usa ka asynchronous protocol (sama sa SCP). Sa laing pagkasulti, ang mga node wala gi-coordinate sa oras, apan pinaagi lamang sa mga mensahe nga ilang gipadala. Gikan sa punto sa panglantaw sa node, dili klaro kung kanus-a natapos yugto sa extension. Ug bisan kung ang tanan nga mga node sa kadugayan moabut sa parehas nga composite, mahimo silang mag-agi sa lainlaing mga ruta sa agianan, maghimo lainlaing mga komposit nga kandidato sa agianan, ug dili gyud makasulti kung kinsa ang katapusan.
Pero normal ra. Pagpangandam lang ang nominasyon. Ang nag-unang butang mao ang paglimite sa gidaghanon sa mga kandidato aron makab-ot ang consensus, nga mahitabo sa proseso modagan alang sa katungdanan (pagboto).
Nagdagan
Ang Bulletin usa ka magtiayon , diin ang counter usa ka integer nga nagsugod sa 1 ug ang kantidad usa ka kandidato gikan sa yugto sa nominasyon. Mahimo kini nga kandidato sa kaugalingon nga node o kandidato sa silingan nga node nga gidawat sa kana nga node. Sa laktod nga pagkasulti, ang usa ka balota naglakip sa balik-balik nga pagsulay sa pagpugos sa network sa pagkab-ot sa usa ka consensus sa pipila ka kandidato sa pipila ka balota pinaagi sa paghupot sa posibleng daghang mga pederasyon nga mga boto sa mga pahayag sa balota. Ang mga tig-ihap sa mga balota nagsubay sa mga pagsulay nga gihimo, ug ang mga balota nga adunay mas taas nga mga ihap mag-una sa mga balota nga adunay mas ubos nga mga ihap. Kung ang newsletter natanggong, nagsugod ang bag-ong boto, karon sa balota .
Importante nga mailhan mga mithi (pananglitan, unsa ang order sa paniudto: pizza o salads), mga newsletter (counter-value pares) ug mga pahayag mahitungod sa mga balota. Ang SCP round naglakip sa pipila ka hugna sa federal nga pagboto, ilabi na sa mosunod nga mga pahayag:
- "Andam ko nga mohimo sa balota B" ug
- "Akong gipahibalo ang pasalig sa balota B"
Gikan sa usa ka gihatag nga panglantaw sa node, ang consensus makab-ot sa diha nga kini makakaplag sa usa ka balota B diin kini makakumpirma (nga mao, pagpangita sa usa ka korum nga modawat) sa pahayag nga "I commit ballot B." Gikan niini nga punto, luwas nga molihok sa kantidad nga gitakda sa B - pananglitan, pagbutang niini nga order alang sa paniudto. Gitawag kini eksternalisasyon mga kahulugan. Sa higayon nga mapamatud-an na ang pagdawat sa balota, ang usa ka node makasiguro nga ang bisan unsa nga lain nga node naka-externalize sa samang bili o buhaton kini sa umaabot.
Bisan kung daghang mga pederasyon nga mga boto ang gikonsepto nga gihimo sa mga pag-angkon alang sa daghang lainlaing mga balota, wala sila magbayloay og daghang mga mensahe tungod kay ang matag mensahe naglangkob sa daghang mga balota. Ang usa ka mensahe sa ingon nagpasiugda sa kahimtang sa daghang pederasyon nga mga boto sa usa ka higayon, pananglitan: "Gidawat nako ang mga balota nga nagsalig gikan sa kaniadto "
Unsa ang gipasabut sa mga termino nga "nag-andam" ug "nagpasalig"?
Ang usa ka node mobotar sa paghimo sa usa ka balota kung kini masaligon nga ang ubang mga node dili makahimo sa mga balota nga adunay lain-laing mga bili. Ang pagkumbinser niini mao ang katuyoan sa pag-andam sa aplikasyon. Ang usa ka boto nga nag-ingon nga "Andam na ako nga mohimo sa balota B" usa ka saad nga dili gyud mohimo usa ka balota nga mas gamay sa B, i.e. nga adunay gamay nga ihap (Gikinahanglan sa SCP nga ang mga kantidad sa mga balota naa sa usa ka piho nga han-ay. Busa, newsletter gamay ra , kung N1
Ngano nga ang "Andam ko nga mohimo sa balota B" nagpasabut nga "Ako mosaad nga dili gyud mohimo og mga balota nga mas gamay sa B"? Tungod kay gihubit sa SCP ang abort isip sukwahi sa commit. Ang usa ka boto sa pag-andam sa usa ka balota naglakip usab sa usa ka boto sa pag-disqualify sa ubang mga balota, ug, sama sa atong gihisgutan sa sayo pa, ang pagbotar sa usa ka butang usa ka saad nga dili gayud mobotar batok niini.
Sa dili pa i-broadcast ang usa ka commit, ang usa ka node kinahanglan una nga mangita usa ka bulletin nga kini makumpirma nga giandam. Sa laing pagkasulti, kini naghimo sa usa ka federated nga boto sa hilisgutan nga "Andam ko nga mohimo sa balota B," posible sa daghang lain-laing mga balota, hangtud kini makakita og usa nga modawat sa usa ka korum.
Diin gikan ang mga balota aron maandam ang boto? Una, ang node nagsibya sa mga pagpangandam sa pagboto sa <1,C>, diin ang C mao ang composite nga kandidato nga gihimo sa yugto sa nominasyon. Bisan pa, bisan human magsugod ang mga pagpangandam alang sa pagbotar, ang mga nominasyon mahimong moresulta sa dugang nga mga kandidato nga magpakita nga mahimong bag-ong mga balota. Sa kasamtangan, ang mga kaedad mahimong adunay lain-laing mga kandidato, ug sila makahimo sa usa ka blocking set nga modawat "Ako andam sa pagtugyan sa B2 balota," nga mokombinsir sa node sa pagdawat niini usab. Sa katapusan, adunay usa ka mekanismo sa timeout nga makamugna og mga bag-ong hugna sa federated nga pagboto sa bag-ong mga balota nga adunay mas taas nga mga ihap kung ang kasamtangan nga mga balota natanggong.
Sa diha nga ang node makit-an ang usa ka balota B nga kini makumpirma ingon nga giandam, kini magsibya sa usa ka bag-ong mensahe nga "I-commit ang balota B." Kini nga boto nagsulti sa mga kaedad nga ang node dili gayud mohatag sa B. Sa pagkatinuod, kung ang B usa ka balota , dayon ang “Commit ballot " nagpasabot sa walay kondisyon nga pagtugot sa pagboto alang sa kaandam sa matag balota gikan sa ngadto sa <∞, s>. Kini nga dugang nga kantidad makatabang sa ubang mga kaedad nga makaabut sa commit peer kung naa pa sila sa una nga mga yugto sa protocol.
Niini nga yugto, angay nga ipasiugda pag-usab nga kini mga asynchronous nga mga protocol. Tungod lang kay ang usa ka node nagpadala ug upvotes alang sa usa ka commit wala magpasabot nga ang mga kaedad niini mobuhat usab. Ang uban kanila tingali nagbotar pa sa mga pahayag agig pangandam sa pagbotar, ang uban tingali nakagawas na sa kahulogan. Gipatin-aw sa SCP kung giunsa pagproseso sa usa ka node ang matag klase sa mensahe sa kauban bisan unsa pa ang bahin niini.
Kung ang mensahe "Gipahibalo nako ang usa ka pasalig » dili madawat o makumpirma, nga mao, ang posibilidad nga ang mensahe madawat o makumpirma o - o, sa bisan unsang kaso, bisan unsang balota nga adunay kantidad nga C, ug dili bisan unsang uban pa, tungod kay ang node misaad na nga dili na kanselahon . Sa panahon nga ang usa ka node magsibya sa mga boto alang sa usa ka commit, kini mahimong C o wala, depende sa kung unsa ka layo ang consensus. Bisan pa, kini dili pa igo alang sa node sa pag-externalize sa C. Ang ubang mga Byzantine nga mga kaedad (nga naglangkob sa ubos sa usa ka korum, base sa among mga pangagpas sa seguridad) mahimong mamakak sa node. Ang pagdawat ug dayon pagkumpirma sa pipila ka balota (o sakup sa mga balota) mao ang naghatag sa kompiyansa sa node aron sa katapusan ma-externalize ang C.
SCP voting pinaagi sa federated voting. Wala gipakita: Ang timer mahimong mopalong bisan unsang orasa, nga magdugang sa ihap sa balota (ug posible nga maghimo usa ka bag-ong komposisyon sa dugang nga nominado nga mga kandidato).
Ug kini tanan! Kung nakab-ot na sa network ang usa ka consensus, andam na kini nga buhaton kini pag-usab. Sa network sa pagbayad sa Stellar, kini mahitabo halos kausa sa matag 5 segundos: usa ka buhat nga nanginahanglan sa seguridad ug pagkaluwas nga gigarantiyahan sa SCP.
Makab-ot kini sa SCP pinaagi sa pagsalig sa daghang hugna sa pederasyon nga pagboto. Ang federated voting nahimong posible pinaagi sa konsepto sa mga hiwa sa korum: mga set sa mga kaedad nga ang matag node nakahukom nga saligan isip kabahin sa (subjective) nga korum niini. Kini nga configuration nagpasabot nga ang consensus mahimong maabot bisan sa usa ka network nga adunay bukas nga membership ug Byzantine nga mga limbong.
Dugang nga pagbasa
- Ang orihinal nga puti nga papel sa SCP makita ug draft specifications alang sa pagpatuman niini.
- Ang orihinal nga tagsulat sa SCP protocol, si David Mazier, nagpatin-aw niini sa usa ka gipayano (apan sa gihapon teknikal) nga paagi. .
- Tingali natingala ka nga wala makit-an ang mga termino nga "pagmina" o "pamatuod sa trabaho" sa kini nga artikulo. Ang SCP wala mogamit niini nga mga pamaagi, apan ang uban nga mga consensus algorithms. Gisulat ni Zane Witherspoon nga ma-access .
- usa ka yano nga network nga nakab-ot ang consensus sa usa ka tibuuk nga hugna sa SCP.
- Para sa mga magbabasa nga interesado sa mga pagpatuman sa SCP: tan-awa , gigamit sa network sa pagbayad sa Stellar, o , nga akong gisulat para sa mas maayong pagsabot sa SCP.
Source: www.habr.com