Stellar'i konsensusprotokoll kirjeldati esmakordselt teadusartiklis David Mazier'i poolt 2015. aastal. See on "föderatiivne bütsantsi konsensus", mis võimaldab detsentraliseeritud arvutusvõrkudel ilma liidriteta tõhusalt jõuda konsensuseni mis tahes otsuse osas. Stellar'i maksevõrk kasutab Stellar Consensus Protocol (SCP) koosseisuliste tehingute ajaloos, mida kõik osalised näevad.

Peetakse, et konsensusprotokollid on keerulised arusaamiseks. SCP on lihtsam kui enamik neist, kuid jagab siiski seda mainet – osaliselt vale arusaama tõttu, et "föderatiivne hääletamine", millele teadusartikli esimene pool keskendub, on SCP. Kuid see pole tõsi! See on vaid oluline ehituskivi, mida teises osas artiklit kasutatakse Stellar'i konsensusprotokolli loomisel. reaalne Stellar'i konsensusprotokoll.

Selles artiklis anname lühikese ülevaate sellest, mis on "kokkuleppete süsteem", mis võib muuta selle "bütsantsi" ja miks muuta bütsantsi süsteem "föderatiivseks". Seejärel selgitame föderatiivset hääletusprotsessi, mis on kirjeldatud SCP artiklis, ja lõpuks selgitame SCP protokolli ennast.

Kokkuleppete süsteemid

Kokkuleppete süsteem võimaldab grupil osaleda konsensusel mingis küsimuses, näiteks selle üle, mida lõunaks tellida.

Meie ettevõttes Interstellar oleme rakendanud oma lõunasöögi kokkuleppete süsteemi: tellime seda, mida ütleb meie operatsioonijuht John. See on lihtne ja tõhus kokkuleppete süsteem. Me kõik usaldame Johni ja usume, et ta igal päeval leiab midagi huvitavat ja toitvat.

Aga mis siis, kui John väärkasutab meie usaldust? Ta võib üksi otsustada, et meil kõigil peaks olema vegan dieedile. Nädala või kahe pärast tõenäoliselt kukutame ta ja anname volitused Elizabethile. Kuid äkki talle meeldivad avokaadod anšoovistega ja ta arvab, et kõik peaksid olema sellised. Võim rikub. Seetõttu on parem leida mõni demokraatlikum meetod: mingi viis, et tagada erinevate eelistuste arvestamine, samas tagades õigeaegne ja ühemõtteline tulemus, et ei juhtuks, et keegi ei telli lõunat või viis inimest esitavad erinevaid tellimusi või arutelu venib õhtuni.

Tundub, et lahendus on lihtne: korraldada hääletus! Kuid see on petlik mulje. Kes hakkab hääli koguma ja tulemusi teatama? Ja miks peaksid teised uskuma seda, mida ta ütleb? Võib-olla saame esiteks hääletada liidri poolt, kellele usaldame hääletamise juhtimise - aga kes juhib seda esimest hääletust? Mis juhtub, kui me ei leia liidrit? Või kui leppime kokku, aga see liider jääb koosolekule või jääb haigeks?

Sarnased probleemid esinevad jaotatud arvutivõrkudes. Kõik osalised või sõlmed peavad kokku leppima mingisuguses lahenduses, näiteks kelle kord on ühist faili uuendada või võtta ülesanne töötlemise järjekorrast. Krüptovaluuta võrgus peavad sõlmed korduvalt valima, milline tundub täiuslik ajalugu, erinevate võimalike versioonide hulgast, mis mõnikord konfliktivad. See võrguleping tagab vastuvõtjale, et münt on (a) kehtiv (mitte vale) ja (b) pole veel kuskil mujal kasutatud. See tagab ka, et ta saab mõnes tulevikus münti kasutada, kuna uuel vastuvõtjal on samad garantiid samadel põhjustel.

Igapäevane konsensusvõime jaotatud arvutivõrgus peab olema rikkevastupidine: see peab andma järjepidevaid tulemusi, hoolimata vigadest, nagu aeglased sidekanalid, mitte reageerivad sõlmed ja vale sõnumite järjekord. Bütsantsi konsensus süsteem on täiendavalt vastupidav 'bütsantsi' vigadele: sõlmed, mis annavad vale teavet, olgu see siis vea tõttu või tahtlikul katsel süsteemi kahjustada või mingit eelist saada. 'Bütsantsi' tõrkedetaolek - võime usaldada grupi otsust, isegi kui mõned grupi liikmed võivad valetada või muul viisil reegleid rikkuda - on saanud nime Bütsantsi imperaatorite kindralite jutustusest, kes üritasid rünnakut koordineerida. Hea kirjeldus on Anthony Stevenilt.

Kujutame ette krüptomündi omanikku Alice'it, kes peab valima Bobilt maitsva jäätise ostmise ja Carolile võla tasumise vahel. Võib-olla tahab Alice mõlemale korraga maksta, petturlikult kulutades sama münti. Selleks peab ta veenma Bobi arvutit, et münt ei ole kunagi Carolile makstud, ning veenma Caroli arvutit, et münt ei ole kunagi Bobile makstud. Bytsantsi kokkuleppe süsteem muudab selle tegelikult võimatuks, rakendades enamusreegel, mida nimetatakse kvorumiks. Selles jaringanis keeldub sõlm sellest, et liikuda kindla ajalooversiooni suunas, kuni nad ei näe, et piisavalt palju võrdsete liikmete sõlmi — kvorum — on sellise muutuse suhtes nõus. Kui see juhtub, moodustavad nad piisavalt suure valijabloki, et sundida ülejäänud võrgu sõlmi nende otsusega nõustuma. Alice võib sundida mõnda sõlme valetama tema nimel, kuid kui võrk on piisavalt suur, siis tema katse purustatakse ausate sõlmede häältega.

Kui palju sõlmi on vajalik kvorumi saavutamiseks? Vähemalt enamus, täpsemalt kvalifitseeritud enamus kahjustuste ja pettuste vastu võitlemiseks. Kuid enama arvutamiseks on vajalik teada osalejate koguarv. Interstellar kontoris või ringhääletustel on need numbrid kergesti teada. Kuid kui teie rühm on halvasti määratletud võrk, kuhu sõlmed võivad vabalt siseneda ja lahkuda ilma keskusega kooskõlastamata, siis on vajalik federatiivne bytsantsi leppimise süsteem, mis suudab kvorumeid määrata mitte eelnevalt määratletud sõlmede loendist, vaid dünaamiliselt, pidevalt muutuva ja paratamatult mittetäieliku sõlmede hetkeseisust.

Võib tunduda võimatu luua kvorum üksiku sõlme vaatepunktist ulatuslikus võrgus, kuid see on võimalik. Selline kvorum võib isegi tagada detsentraliseeritud hääletamise tulemusi. Tehniline dokument SCP näitab, kuidas seda teha protseduuri kaudu, mida nimetatakse federatiivseks hääletamiseks.

Patsientide jaoks

Artiklis on üksikasjalikumalt käsitletud federatiivset hääletamist ja Stellar konsensuse protokolli. Kui te ei ole huvitatud detailidest, siis siin on protsessi üldine ülevaade.

1. Sõlm teostab föderaalse hääletamise voorusid «nomineeritud» üle. Föderaalne hääletamine tähendab:
   • Sõlm hääletab mingi ettepaneku poolt, näiteks «Ma pakun välja V väärtuse»;
   • Sõlm kuulab hääli, kuni leiab sellise, mis suudab «vastu võtta»;
   • Sõlm otsib selle ettepaneku jaoks «kvoraumi». Kvoraum «kinnitab» kandidaati.
2. Kui sõlm suudab kinnitada üht või mitut kandidaati, proovib ta «valimisse» viia läbi mitu vooru föderaalsest hääletamisest.
3. Kui sõlm suudab kontrollida valimise valmidust, proovib ta seda kinnitada veelgi rohkemate föderaalse hääletamise voorude abil.
4. Kui sõlm suudab kinnitada valimise kommitti, saab ta «eksternaliseerida» selle hääletuse väärtuse, kasutades seda konsensuse tulemuseks.

Need sammud hõlmavad mitmeid föderaalse hääletamise voorusid, mis tervikuna moodustavad ühe SCP vooru. Uurime lähemalt, mis toimub igal sammul.

Föderaalne hääletamine

Föderaalne hääletamine on protseduur, millega määratakse, kas võrk suudab kokku leppida ettepanekus. Hääletamisvoorus peab iga sõlm valima ühe potentsiaalselt paljusid väärtusi. Ta ei saa seda teha, kuni ei ole kindel, et teised võrgu sõlmed ei vali teistsugust tulemust. Selle kinnitamiseks vahetavad sõlmed eemal ja tagasi hulk sõnumeid, et igaüks kinnitaks, et kvoraum sõlmed vastuvõtavad sama otsuse. Selle jaotise ülejäänud osa selgitab selles lauses esinevaid mõisteid ja kuidas kogu protseduur toimub.

Kvoraumid ja kvoraumi lõigud

Alustame kvoraumi määratlemisest. Nagu me eespool arutasime, ei ole detsentraliseeritud võrgus, millel on dünaamiline liikmelisus, võimalik ette teada sõlmede arvu ja seega, kui palju on vajalik enamuse jaoks. Föderaalne hääletamine lahendab selle probleemi, esitades uue idee kvoraumi lõik (quorum slice): väike rühm võrdväärseid sõlmi, kellele sõlm usaldab teabe edastamise hääletamise seisundi kohta ülejäänud võrgus. Iga sõlm määratleb oma kvoraumi lõigu (mille liikmeks ta tegelikult saab). (quorum slice): väike rühm võrdsest sõlmedest, kellele sõlm usaldab teabe edastamise häälte oleku kohta ülejäänud võrgustikule. Iga sõlm määratleb oma kvorumi lõike (mille liikmeks ta tegelikult saab).

Kvorumi kujundamine algab kvorumi lõikest. Iga sõlm lisab oma lõike sõlmed. Seejärel lisatakse lõikede liikmed. nende sõlmede ja nii edasi. Protsessi jätkudes satub järjest rohkem sõlmi, mida te ei saa lisada, kuna nad on juba lõikes. Kui uusi sõlmi lisamiseks enam ei ole, katkeb protsess: oleme kujundanud kvorumi algsest sõlmest 'transitiivne sulgemine' (transitive closure) kvorumi lõike kaudu.

Kuidas leida kvorum antud sõlmest…

… lisame tema lõike liikmed…

… seejärel lisame nende sõlmede lõikede liikmed.

Jätkame, kuni ei jää enam sõlmi lisamiseks.

Sõlmi lisamiseks ei ole. See on kvorum.

Tegelikult võib iga sõlm kuuluda rohkem kui ühte lõikesse. Kvorumi kujundamiseks valige ainult üks lõige ja lisage liikmed; seejärel valige iga liikme jaoks ükskõik milline lõige ja lisage liikmed. selle lõike jne. See tähendab, et iga sõlm on osa paljusid võimalikke kvorumeid.

Valige igal sammul ainult üks kvorumi lõike.

Üks võimalik kvorum. Või alternatiivne variant…

… valime teised lõiked…

… (kui see on võimalik)…

… loob teise kvorumi.

Kuidas sõlm saab teada, millistes lõikedes teised sõlmed on? Samamoodi nagu muud teavet teiste sõlmede kohta: edastustest, mida iga sõlm edastab võrgus, kui tema häälteenindus muutub. Iga edastus sisaldab teavet saatva sõlme lõikede kohta. Tehnilises dokumendis SCP ei ole määratud suhtlemismehhanismi. Tavalised rakendused kasutavad tavaliselt Gossip-protokolli teadete usaldusväärseks edastamiseks kogu võrgus.

Tulet meelde, et mittefederatiivses Bütsantsi konsensus-süsteemis määratakse kvoorum kõikide sõlmede enamuse järgi. Bütsantsi konsensus-süsteem on välja töötatud küsimuse osas: kui palju ebaausaid sõlmi suudab süsteem taluda? N sõlmest koosnevas süsteemis, mis on projekteeritud taluma f riket (petmist), peab sõlm olema suuteline saavutama edusamme, saades vastuse N−f peerilt, kuna f neist ei pruugi funktsioneerida. Kuid kui saadakse vastus N−f peerilt, võib eeldada, et kõik f peerid (kellest sõlm vastust ei saanud) on tegelikult ausad. Seega on pahatahtlikud f N−f peerist (kellest vastus on saadud). Selleks, et sõlmed jõuaksid ühe konsensuse, peab aus olema enamus ülejäänud sõlmedest, st meil on vaja, et N−f oleks suurem kui 2f või N > 3f. Seega on tavaliselt süsteem, mis on kavandatud taluma f riket, kokku N=3f+1 sõlme ja kvoorumi suurus 2f+1. Kui ettepanek ületab kvoorumi läve, on ülejäänud võrgu liikmed veendunud, et kõik konkurentsivõimelised ettepanekud ebaõnnestuvad. Nii et võrk jõuab tulemuseni.

Kuid federatiivses Bütsantsi konsensus-süsteemis ei saa mitte ainult olla enamus (kuna keegi ei tea võrgu üldsuuret), vaid enesestmõistetav enamus kontseptsioon on täiesti kasutu! Kui süsteemis on liikmelisus avatud, võib keegi saavutada enamus, läbides nii öelda Sivilia rünnaku: korduvalt liitudes võrku läbi mitme sõlme. Nii et miks võib transitiivne sulgemine lõiget nimetada kvorumiks, ja kuidas see suudab summutada konkurentsivõimelisi ettepanekuid?

Tehniliselt, mitte kuidagi! Kujutage ette kuue sõlmega võrku, kus kaks kolmikest on teineteise kvoorumi lõigetes isoleeritud. Esimene alagrupp võib teha otsuse, millest teine kunagi ei kuule, ja vastupidi. Selle võrgu jaoks ei ole võimalik konsensusele jõuda (kui mitte juhuslikult).

Seetõttu nõuab SCP, et federatiivse hääletamise puhul (ja oluliste teoreemide rakendamiseks) peaks võrgus olema omadus, mida nimetatakse kvoorumite ühiseks olemiseks. Võrgus, millel on see omadus, kattuvad alati vähemalt ühes sõlmes igasugused kaks kvoorumi, mida saab koostada. Ülevaatlikult tähendab see, et kui mõni kvoorum nõustub väitega X, ei saa ükski teine kvoorum kunagi nõustuda millegi muuga, kuna see peab kindlasti sisaldama mõnda sõlme esimesest kvoorumist, mis on juba hääletanud X poolt.

Kui võrgus on kvoorumite ühisosa…

…siis kattuvad alati igasugused kaks kvoorumi, mida saate koostada…

…kattuvad alati.

(Loomulikult võivad kattuvad sõlmed olla viinapatsivõrgud või muul viisil halvad. Sel juhul ei aita kvoorumite ühinemine võrgu nõusoleku saamiseks üldse. Seetõttu põhinevad paljud tulemused tehnilises dokumendis SCP selgelt väljendatud oletustel, et võrgu sees on kvoorumite ühisosa, isegi pärast halbadest sõlmedest vabanemist. Lihtsuse huvides jätame need oletused viidatud artikli ülejäänud osas).

Võib tunduda ebamugav oodata, et sõltumatute sõlmede võrgus on võimalik usaldusväärne kvoorumite ühinemine. Kuid selleks on kaks põhjust.

Esimene põhjus on interneti olemasolu. Internet on ideaalne näide sõltumatute sõlmede võrgust, kus on kvoorumite ühinemine. Enamik interneti sõlmedest on ühendatud ainult mõne teiste kohaliku sõlmega, kuid need väikesed kogud kattuvad piisavalt, et iga sõlm oleks ligipääsetav igast teisest sõlmest igasuguste marsruutide kaudu.

Teine põhjus on spetsiifiline Stellar maksevõrgu jaoks (kõige levinum rakendus SCP). Igal varal Stellar võrgus on emitent ja Stellar'i soovitused nõuavad, et iga emitent määraks ühe või mitu sõlme, mis käsitlevad lunastamisettepanekute töötlemist. Teie huvides on otse või kaudselt kaasata need sõlmed iga huvipakkuva vara kvoorumitesse. Seeläbi kattuvad kõikide sõlmede kvoorumid, mis on huvitatud konkreetsest varast, vähemalt nendes lunastussõlmedes. Sõlmed, mis on huvitatud mitmest varast, kaasavad oma kvoorumisse kõik vastavate emitentide lunastussõlmed, ning nad püüdlevad kokku liita kõik varad. Lisaks ei tohi kõik varad, mis pole omavahel seotud, võrgu sees olla seotud — see on mõeldud nii, et selle võrgu kvoorumid ei kattuks (näiteks dollari piirkonna pangad soovivad mõnikord kaubelda euro piirkonna ja pesotoo pangandussektoriga, seega on nad samas võrgus, kuid keegi neist ei huvita eraldi võrku, kus kaupleb lastetooteid, nagu näiteks pesapallikaardid).

Muidugi, oodates kvoorumite kattumist ei ole garantii. Teised byzantium'i kokkuleppe süsteemid oma keerukuses on suures osas sõltuvad kvoorumite garantii olemasolust. SCP oluline uuendus on see, et see vabastab kvoorumite loomise vastutuse konsensusalgoritmist ja viib selle rakenduse tasandile. Seega, kuigi föderaalne hääletamine on piisavalt tavaline igasuguste küsimuste hääletamiseks, sõltub selle usaldusväärsus kriitiliselt nende tähenduste laiemast kontekstist. Mõned hüpoteetilised kasutusvõimalused võivad osutuda mitte nii mugavaks hästi seotud võrkude loomisel kui teised.

Hääletamine, vastuvõtmine ja kinnitamine

Föderaalse hääletamise voorus hakkab sõlm valikuliselt hääletama mingi väärtuse V poolt. See tähendab, et see edastab võrgus sõnumi: „Mina olen sõlm N, minu kvoorumid Q ja ma hääletan V poolt.” Kui sõlm hääletab sellisel viisil, lubab ta, et ei ole kunagi hääletanud V vastu ja ei hääleta kunagi.

Peer nodes see how others vote in broadcasts. Once a node gathers enough of these messages, it can track quorum slices and attempt to find quorums. If it sees a quorum of peers also voting for V, it can proceed to acceptance of V and broadcast this new message to the network: "I am node N, my quorum slice is Q, and I accept V." Acceptance provides a stronger guarantee than simple voting. When a node votes for V, it can never vote for other options. But if a node accepts V, no node in the network will ever accept another option (Theorem 8 in the SCP technical document proves this).

Of course, there is a high likelihood that a quorum of nodes agreeing on V won’t be found right away. Other nodes might vote for other values. But there is another way for the node to move from simple voting to acceptance. N can accept another value W, even if it did not vote for it, and even if it does not see a quorum for it. To change its vote, it is enough to see a blocking set of nodes that have accepted W. A blocking set consists of one node from each of the quorum slices of N. As the name suggests, it is capable of blocking any other value. If all nodes in such a set accept W, then (by Theorem 8) it will never be possible to form a quorum that accepts any other value, and therefore it is also safe for N to accept W.

Node N with three quorum slices.

B-D-F is a blocking set for N: it includes one node from each slice of N.

B-E is also a blocking set for N because E appears in two slices of N.

But a blocking set is not a quorum. It would be too easy to trick node N into accepting a desired value if it were sufficient to compromise just one node in each of the slices of N. Therefore, accepting a value is not the end of voting. Instead, N must confirm the value, meaning it must see a quorum of nodes accepting it. If it goes that far, then, as the SCP technical document proves (in Theorem 11), the rest of the network will also ultimately confirm the same value, thus N will conclude the federated voting with a determined value as the result.

Federated voting.

Hääletusprotsess ja kinnitamine moodustab ühe täiskäigu föderatiivse hääletuse raames. Stellar konsensuse protokoll ühendab palju selliseid käike, et luua täiuslik konsensus süsteem.

Stellar konsensuse protokoll

Kaks kõige olulisemat omadust konsensus süsteemis — turvalisus ja vastupidavus. Konsensusalgoritm on 'turvaline', kui see ei saa kunagi anda erinevaid tulemusi erinevatele osalejatele (Bob'i ajalugu ei saa kunagi olla vastuolus Caroliga). 'Vastupidavus' tähendab, et algoritm annab alati tulemuse, s.t ei jää kinni.

Kirjeldatud föderatiivse hääletuse protseduur on turvaline selles mõttes, et kui sõlm kinnitab väärtuse V, siis ei kinnita ükski teine sõlm teist väärtust. Kuid 'ei kinnita teist väärtust' ei tähenda, et see peab tingimata midagi kinnitama. Osalejad võivad hääletada nii palju erinevate väärtuste üle, et miski ei saavuta nõusoleku läve. See tähendab, et föderatiivses hääletuses puudub vastupidavus.

Stellar konsensuse protokoll kasutab föderatiivset hääletust nii, et tagab nii turvalisuse kui ka vastupidavuse. (Turvalisuse ja vastupidavuse garantiidel on teoreetiline piir. Konstruktsioon valib väga tugeva turvalisuse garanteerimise, ohverdades veidi vastupidavuse, kuid arvestades piisavalt pika aja jooksul saab konsensus väga tõenäoliselt saavutatud). Lühidalt öeldes seisneb idee selles, et korraldatakse mitu föderatiivset hääletust mitmete väärtuste üle, kuni üks neist läbib täielikult kõik allpool kirjeldatud SCP hääletamise etapid.

Väärtused, mille üle SCP konsensust peab saavutama, võivad olla tehingute ajalugu või lõunatellimus või miski muu, kuid oluline on märkida, et need ei ole väärtused, mis on aktsepteeritud või kinnitatud. Selle asemel toimub föderatiivne hääletus väidete üle nende väärtuste kohta.

Esimesed föderatiivse hääletuse käigud toimuvad nimetamise etapis (nomination phase), koos komplekti väidete tüübiga 'Mina esitan V', võimalusel paljude erinevate väärtuste V jaoks. Nimetamise eesmärk on leida üks või mitu väidet, mis läbivad aktsepteerimise ja kinnitamise.

Pärast kinnitatud kandidaatide leidmist liigub SCP hääletamise etappi, kus eesmärk on leida teatud häälteprotsess (st ettepaneku väärtuse konteiner) ja kvoorum, mis võib väljendada komiteed selle jaoks (commit). Kui kvoorum teeb komitee hääletamise, aktsepteeritakse selle väärtus konsensuseks. Kuid enne, kui sõlm saab hääletada komitee üle, peab ta enne kinnitama kõigi madalama väärtuse hääletuste tühistamise. Need sammud - hääletuste tühistamine, et leida see, millele saab komiteed kinnitada - hõlmavad mitmeid ringe föderatiivset hääletamist mitmete hääletuste avalduste üle. Järgmistes osades kirjeldatakse lähemalt esitamist ja hääletamist.

Esitamine

Esitamise etapi alguses saab iga sõlm vabatahtlikult valida väärtuse V ja hääletada selle kinnitamise eest "Mina esitan V". Selles etapis on eesmärk kinnitada teatud väärtuse esitamine föderatiivse hääletamise teel.

Võib-olla hääletab piisav arv sõlmi piisavalt erinevate avalduste üle, ja ükski esitus ei saavuta vastuvõtmise künnist. Seetõttu, lisaks enda nominatsioonihäälte edastamisele, "peegeldavad" sõlmed oma naabrite nominatsioone. Peegeldamine (echo) tähendab, et kui sõlm hääletab V esitamise poolt, kuid näeb naabri hääletust W esitamise poolt, siis hääletab ta nüüd nii V kui ka W esitamise poolt. (Kõik naabrite hääled ei kajastu esitamise ajal, kuna see võib põhjustada erinevate nominantide plahvatuse. SCP sisaldab nende häälte reguleerimise mehhanismi. Lühidalt öeldes, on olemas valem "prioriteedi" määramiseks sõlme vaatenurgast, ning peegeldatakse ainult kõrge prioriteediga sõlmede hääli. Mida kauem esitamine kestab, seda madalam on künnis, seetõttu laiendab sõlm naabrite kogumit, kelle hääli ta peegeldab. Prioriteedi valem sisaldab ühe sisendina sloti numbrit, seega võib kõrge prioriteediga peer ühe sloti puhul olla madala prioriteediga teisel, ja vastupidi).

Võib juhtuda, et piisav arv sõlmi hääletab piisavalt erinevate ettepanekute eest, ja ükski ettepanek ei suuda saavutada vastuvõtmise künnist. Seetõttu peegeldavad sõlmed oma naabrite ettepanekute hääli lisaks oma nomineerimishäälte edastamisele. Peegeldamine tähendab, et kui sõlm hääletab ettepaneku V poolt, kuid näeb sõnumit naabrilt, kes hääletab ettepaneku W poolt, siis hakkab see nüüd hääletama nii V kui ka W ettepaneku poolt. (Kõik naabri hääled ei pruugi peegelduda hääletamise ajal, kuna see võib põhjustada erinevate nominentide plahvatuse. SCP hõlmab nende häälte reguleerimise mehhanismi. Lühidalt öeldes on olemas valem, mis määrab „prioriteedi” naabri suhtes sõlme vaatepunktist, ja peegeldatakse vaid kõrgprioriteediliste sõlmede hääli. Mida pikemalt hääletamine kestab, seda madalam on künnis, seega laiendab sõlm naabrite komplekti, kelle hääli ta peegeldab. Prioriteedi valem sisaldab ühe sisenemise andmena ka ajakonverentsi numbrit, seega võib kõrge prioriteediga võrgu sõlm ühe ajakonverentsi jaoks olla madala prioriteediga teise jaoks ja vastupidi).

Konceptsiooniliselt on nii V kui W esitlemine eraldi föderatiivsed hääled, mis igaühega eraldi suudavad saavutada aktsepteerimise või kinnitamise. Praktikas pakivad SCP protokolli sõnumid need eraldi hääled kokku.

Kuigi hääletamine V esitlemise poolt tähendab, et ei tohi kunagi hääletada V esitlemise vastu, määratletakse rakendustasandil – antud juhul SCP – see, mida tähendab 'vastu'. SCP ei näe kinnitust, mis oleks vastuolus hääletusega 'Ma esitan X', st ei ole sõnumit 'Ma olen X esitlemise vastu', seetõttu saab sõlm hääletada mis tahes väärtuste esitlemise poolt. Paljusid neist nominatsioonidest ei viida kuigi kaugele, kuid lõppkokkuvõttes suudab sõlm aktsepteerida või kinnitada ühte või mitut väärtust. Kui nominant on kinnitatud, siis ta saab kandidaadiks.

SCP esitlemine föderatiivse hääletuse kaudu. Võib esitada palju väärtusi “B”, mille on esitanud võrdsete õigustega sõlmed ja mis on 'peegeldatud' sõlme kaudu.

Kandidaatide esitamine võib viia mitme kinnitatava kandidaadi tekkimiseni. Seetõttu nõuab SCP, et rakendustasand pakuks mingit meetodit kandidaatide ühendamiseks ühte komposiiti (composite). Ühendamismeetod võib olla mis tahes. Peaasi on see, et kui see meetod on määratletud, siis ühendavad kõik sõlmed samu kandidaate. Toitlustussüsteemi hääletamisel võib 'ühendamine' tähendada lihtsalt ühe kahest kandidaadist loobumist. (Kuid määratletud viisil: iga sõlm peab valima sama väärtuse tühistamiseks. Näiteks varasem valik tähestikulises järjekorras). Stellar'i maksevõrgus, kus toimub tehingute ajaloo hääletamine, tähendab kahe esitatud nominandi ühendamine tehingute ühendamist, mida nad sisaldavad, ja nende kahe viimase aja tempot.

Tehniline kirjeldus SCP tõestab (teoreem 12), et esitlemise faasi lõpuks jõuab võrk lõpuks ühe komposiidi poole. Kuid probleem on: föderatiivne hääletamine on asünkroonne protokoll (nagu ka SCP). Teisisõnu, sõlmed ei koordineeru ajaliselt, vaid ainult saatmise kaudu saadud sõnumite kaudu. Sõlme seisukohalt ei ole selge, millal protsess lõppes ettepanekufaas. Ja kuigi kõik sõlmed jõuavad lõpuks sama komposiitini, võivad nad selle tee jooksul valida erinevaid marsruute, luues erinevaid koostisosade kandidaate, ning ei suuda kunagi öelda, kumb neist on lõplik.

Aga see on okei. Ettepanek on vaid ettevalmistus. Peamine on piirduda kandidaatide arvuga, et saavutada konsensus, mis toimub protsessi käigus. hääletamine (balloting).

Hääletamine

Hääletus on paar <counter,value>, kus counter on täisarv, mis algab numbrist 1, ja value on kandidaat ettepanekufaasist. See võib olla kas sõlme enda kandidaat või naaber sõlme kandidaat, mille see sõlm on aktsepteerinud. Üldiselt ettevõetakse hääletamisel mitmeid katseid, et jõuda konsensusele mingi kandidaadi üle teatud hääletuses, viies läbi potentsiaalselt paljusid föderaalseid hääletusi hääletuse avalduste üle. Hääletuse arvutid jälgivad tehtud katseid, ja suuremate arvu väärtustega hääletused eelistavad väiksema arvu väärtusi. Kui hääletus <counter,value> takerdub, algab uus hääletamine, nüüd hääletusel <counter+1,value>.

On oluline eristada mõisted (näiteks, kuidas peaks lõunaks tellima: pitsat või salateid), hääletusi (paar counter-value) ja hälbed hääletuste kohta. SCP voor sisaldab mitmeid ringe föderaalses hääletamises, sealhulgas selliste väidete osas:

• „Olen valmis hääletuse B kinnitamiseks“ ja
• „Kannan ette hääletust B“

Antud sõlme vaatenurgast saavutatakse konsensus, kui see leiab hääletuse B, mille osas ta võib kinnitada (st leida kvoorumi, mis aktsepteerib) väidet „Kannan ette hääletust B“. Sellest hetkest alates on ohutu tegutseda väärtuse põhjal, mis on määratud B-sse — näiteks esitada see lõunatellimus. Seda nimetatakse eksternaliseerimiseks väärtuseks. Kui hääletuse aktsepteerimine on kinnitatud, võib sõlm olla kindel, et iga teine sõlm on eksternaliseerinud sama väärtuse või kindlasti teeb seda tulevikus.

Kuigi kontseptuaalselt viiakse paljusid föderatiivseid hääletusi läbi mitmete erinevate valimiste avalduste alusel, vahetatakse neid mitte nii suure hulga sõnumitega, kuna iga sõnum kapseldab mitmeid valimisi. Üks sõnum edastab seega korraga paljude föderatiivsete hääletuste oleku, näiteks: „Ma aktsepteerin valimiste kommitte vahemikus <min,V> kuni <max,V>.”

Mida tähendavad terminid „valmistatud” (prepared) ja „kommit” (commit)?

Sõlm hääletab valimiste kommiti poolt, kui ta on veendunud, et teised sõlmed ei tee valimiste kommitte teiste väärtustega. Veendumine selles on avalduse ettevalmistamise eesmärk. Hääletamine, milles öeldakse: „Ma olen valmis valimiste kommitiks B,” on lubadus, et kunagi ei toimu valimiste kommitit, mille väärtus on väiksem kui B, st väiksema loenduri (SCP nõuab, et valimistel oleks kindel järjekord. Seega on valimine <N1,V1> väiksem kui <N2,V2>, kui N1<N2, samuti kui N1=N2 ja V1<V2). Need väiksemad valimised „tühistatakse” (aborted) ettevalmistava hääletuse käigus, samas kui B loetakse „valmistatud”.

Miks tähendab „Ma olen valmis valimiste kommitiks B” „Luban, et kunagi ei luba valimiste kommitte, mille väärtus on väiksem kui B”? Sest SCP määratleb tühistamise (abort) kommiti vastandina. Hääletamine valimiste ettevalmistamise üle eeldab samuti hääletamist mõnede teiste valimiste tühistamise üle ja nagu me varem arutasime, on hääletamine ühe asja üle lubadus, et kunagi ei hääletata selle vastu.

Enne kui sõlm edastab kommiti, peab ta esmalt leidma valimise, mille ta saab kinnitada kui ettevalmistatud. Teisisõnu hääletab ta föderatiivse hääletuse teemal „Ma olen valmis valimiste kommitiks B”, võib-olla paljude erinevate valimiste puhul, kuni leiab sellise, mis aktsepteerib kvoorumi.

Kust tulevad hääletamiseks ettevalmistatavad väljaanded? Esiteks edastab sõlm ettevalmistuse hääletamiseks , kus C on kandideeriv komplekt, mis on loodud kandidaate esitamise etapil. Siiski võib isegi pärast hääletamiseks ettevalmistuse algust kandidaadi esitamine tuua juurde uusi kandidaate, kes muutuvad uueks väljaanneteks. Samuti võivad osalistel olla erinevad kandidaatid ja nad võivad luua blokeeriva komplekti, mis aktsepteerib "Olen valmis hääletama väljaande B2", mis veenab sõlme ka selle aktsepteerima. Lõpuks on olemas ajavälja mehhanism, mis genereerib uusi ringe föderaalse hääletamise jaoks uute väljaannetega, millel on kõrgemad loendurid, kui praegused väljaanded on kinni jäänud.

Niipea kui sõlm leiab väljaande B, mille võib kinnitada kui ettevalmistatud, edastab ta uue sõnumi "Kinnita väljaanne B". See hääletamine ütleb osalistele, et sõlm ei loobu kunagi B-st. Tegelikult, kui B esindab väljaannet , siis "Kinnita väljaanne " tähendab tingimusteta nõusolekut hääletada kõigi väljaannete ettevalmistuse eest alates kuni . See lisaväärtus aitab teistel sõlmedel osalistega sammu pidada, kui nad on veel protokolli varasemates etappides.

Selles etapis on oluline rõhutada, et tegemist on asünkroonsete protokollidega. Ainult sellepärast, et üks sõlm saadab hääli kinnitamiseks, ei tähenda, et tema eakaaslased seda ka teevad. Mõned neist võivad endiselt hääletada ettepanekute seadmiseks, teised on võib-olla juba väärtuse eksternaaliseerinud. SCP selgitab, kuidas sõlm peab iga tüüpi omavahelise sõnumi töötlemisega tegema sõltumata selle faasist.

Kui sõnum "Ma kuulutan välja commit <N,C>" ei saa olla aktsepteeritud või kinnitatud, siis on tõenäosus aktsepteerida või kinnitada sõnumit <N+1, C> või <N+2, C> — või igal juhul mis tahes bulleti, mille väärtus on C, mitte miski muu, kuna sõlme on juba lubanud kunagi mitte tühistada <N,C>. Siis kui sõlm edastab hääli commit'i jaoks, on see C või mitte midagi, sõltuvalt sellest, kui kaugele konsensus jõuab. Siiski on sellest sõlm veel liiga vähe, et C-d väljastada. Mõned bütsantsi parteid (moodustades vähem kui kvoorumi, tuginedes meie ohutuse eeldustele) võivad sõlme petta. Miski teatud bulleti (või bulletite vahemiku) aktsepteerimine ja seejärel kinnitamine — see annab sõlmele lõpuks kindluse C väljastamiseks.

SCP hääletamine föderaalse hääletamise kaudu. Mitte kuvatud: igal ajal võib sisse lülituda taimer, suurendades hääletuse arvu (ja võimalusel luues uusi komposiite täiendavatest kandidaatidest).

Ja see on kõik! Kui võrk on jõudnud konsensusele, on see valmis seda tegema jälle ja jälle. Stellar maksevõrgus toimub see umbes iga 5 sekundi järel: saavutus, mis nõuab nii turvalisust kui ka vastupidavust, mida SCP tagab.

SCP võib seda saavutada, tuginedes mitmele föderaalsele hääletamise ringile. Föderaalne hääletamine sai võimalikuks tänu kvoorumi lõike kontseptsioonile: rühmadesse kuuluvad võrdsed sõlmed, kellele iga sõlmotsustas usaldada kui osa oma (subjektiivsest) kvoorumist. See konfiguratsioon tähendab, et isegi avatud liikmelisusega ja bütsantsi petmisega võrgus on võimalik saavutada konsensus.

Edasi lugemiseks

• Algset tehnilist dokumenti SCP kohta võib leida siin, vaid siit projekti spetsifikatsioonide jaoks selle rakendamiseks.
• Protokolli SCP originaalautor David Mazieres selgitab seda lihtsustatud (kuid siiski tehniliselt) viisil siin.
• Võib-olla üllatas teid see, et te ei leidnud seda artiklit otsinguterminite "kaevandamine" või "töö tõendamine". SCP ei kasuta neid meetodeid, kuid mõned teised konsensuse algoritmid kasutavad. Zane Wizerspoon kirjutas ligipääsetava ülevaate konsensuse algoritmidest.
• Samm-sammult kirjeldus lihtsast võrgust, mis saavutab konsensuse SCP ühes täisringis.
• SCP rakenduste vastu huvituvatele lugejatele: vt. C++ kood, mida Stellar maksevõrk kasutab, või Go kood, mille ma kirjutasin SCP parema mõistmise jaoks.

Allikas: habr.com