Stellar konsensusprotokoll on esmakordselt kirjeldatud teadusartiklis David Mazieri poolt 2015. aastal. See on 'föderatiivne bütsantsi kokkulepe', mis võimaldab juhtideta detsentraliseeritud arvutivõrkudel efektiivselt saavutada konsensust mis tahes otsuse osas. Stellar maksevõrk kasutab Stellar Consensus Protocol (SCP) süsteemi, et hoida kooskõlastatud tehingute ajalugu, mida näevad kõik osalejad.

Peetakse, et konsensusprotokollid on keerulised arusaada. SCP on lihtsam kui enamik neist, kuid jagab siiski seda mainet — osaliselt vale arusaama tõttu, et 'föderatiivne hääletamine', millele pühendatakse teadusartikli esimene pool, on SCP. Kuid see pole tõsi! See on lihtsalt oluline ehitusplokk, mida artikli teises pooles kasutatakse tõelise Stellar konsensusprotokolli loomiseks.

Selles artiklis käsitleme lühidalt, mis on „kokkuleppete süsteem”, mis võib muuta selle „bürokraatlikuks”, ja miks muuta bürokraatlik süsteem „föderaalseks”. Seejärel selgitame föderaalse hääletamisprotseduuri, millest räägitakse SCP artiklis, ja lõpuks tutvustame SCP protokolli.

Kokkuleppete süsteemid

Kokkuleppete süsteem võimaldab osalejate grupil saavutada konsensuse mingi teema üle, näiteks selle üle, mida lõunaks tellida.

Meie ettevõttes Interstellar oleme rakendanud oma söögikokkuleppe süsteemi: me 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 leiab iga päev midagi huvitavat ja toitevat.

Aga mis siis, kui John kuritarvitab meie usaldust? Ta võib üksi otsustada, et me kõik peame veganiteks saama. Nädala või kahe pärast kukutame tõenäoliselt ta ja anname võimu Elizabethile. Aga äkki talle meeldivad avokaadod anšoovistega ja ta arvab, et kõik peavad olema nagu tema. Võim rikub. Seetõttu on parem leida mõni demokraatlikum meetod: mingi viis, et tagada, et erinevad eelistused on arvesse võetud, samal ajal tagades õigeaegse ja üheselt mõistetava tulemuse, et vältida olukorda, kus 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! Aga see on petlik mulje. Kes kogub hääletussed ja teatab tulemustest? Ja miks peaksid teised uskuma seda, mida tema ütleb? Võib-olla saame eesmärkide kohaselt hääletada juhtimise usaldusväärse juhi poolt — aga kes juhib seda esimest hääletust? Mis siis, kui me ei suuda kokku leppida juhis? Või kui saame kokku lepitud, aga see juht jääb koosolekule või läheb haiglasse?

Sarnased probleemid esinevad jaotatud arvutivõrkudes. Kõik osalised või sõlmed peavad kokku leppima mingisuguses lahenduses, näiteks kelle kord on ajakohastada ühist faili või võtta ülesanne töötlemise järjekorrast. Krüptovaluuta võrgus on sõlmedel korduvalt vaja valida, milline täielik ajalugu välja näeb, mitmest võimalikust versioonist, mis mõnikord konfliktivad. See võrguleping tagab saajale, et münt on (a) kehtiv (mitte vale) ja (b) veel mitte kulutatud teises kohas. See tagab ka, et ta saab tulevikus mündi kulutada, sest uuel saajal on samad garantiid samadel põhjustel.

Igas jaotatud arvutusvõrgus peab konsensus süsteem olema tõrkekindel: see peab andma järjepidevaid tulemusi, hoolimata vigadest, nagu aeglased sidekanalid, mitte reageerivad sõlmed ja vale sõnumite järjekord. Byzantine kokkulepete süsteem on lisaks vastupidav «bütsantsi» vigadele: sõlmedele, mis annavad valeinfot, olgu need siis eksimuse tõttu või teadlikust katsest süsteemi õõnestada või mingit eelist saada. «Bütsantslik» talitlushäiretaluvus — usaldus grupi otsusele, isegi kui mõned grupiliikmed võivad vale anda või muul viisil otsuste tegemise reegleid rikkuda — sai oma nime Bütsantsi impeeriumi kindralite allegooriast, kes püüdsid korraldada rünnakut. Hea kirjeldus Anthony Stevensilt.

Vaatleme krüptoraha omanikku Alice'i, kes peab valima maitsva jäätise ostmise Bobile ja Carolile oma võla tasumise vahel. Võib-olla tahab Alice mõlemale korraga maksta, petlikult kulutades sama mündi. Selleks peab ta veenma Bobi arvutit, et münt polnud kunagi Carolile makstud, ja veenma Carol'i arvutit, et münt polnud kunagi Bobile makstud. Bütsantsi kokkulepete süsteem muudab selle tegelikult võimatuks, kasutades enamusreeglist tuntud kvoorumi. Sellises võrgus keeldub sõlmimast teatud ajalooversiooni, kuni piisav hulk võrdsete sõlmede — kvoorum — on nõus selle üleminekuga. Kui see juhtub, moodustavad nad piisavalt suure valimibloki, et sundida ülejäänud võrgu sõlmi nende otsusega nõustuma. Alissa võib sundida mõningaid sõlmi valetama tema nimel, kuid kui võrk on piisavalt suur, siis tema katse summutatakse ausate sõlmede häältega.

Kui palju sõlmi on kvoorumi saavutamiseks vajalik? Vähemalt enamus, täpsemalt kvalifitseeritud enamus veaparandamiseks ja pettuse vastu. Kuid enamat arvestamiseks on vajalik teada üldine osalejate arv. Interstellar'i kontoris või ringkonnavalimistel saab need numbrid kergesti teada. Kuid kui teie grupp on halvasti määratletud võrk, kuhu sõlmed saavad vabalt siseneda ja väljuda ilma keskuseta kokkuleppimata, siis on vajalik föderatiivne Byzantine lepingusüsteem, mis suudab määrata kvoorumeid mitte ette määratud sõlmede loendist, vaid dünaamiliselt pidevalt muutuva ja paratamatult mittetäieliku sõlmede väljavõtte põhjal kindlal hetkel.

Ühe sõlme vaatenurgast võib tunduda võimatu luua kvoorumit ulatuslikus võrgustikus, kuid see on siiski võimalik. Selline kvoorum võib isegi tagada detsentraliseeritud hääletamise tulemused. Tehniline dokument SCP näitab, kuidas seda teha protseduuri kaudu, mida nimetatakse föderatiivne hääletamine.

Kauakestev käitumine

Artikli ülejäänud osa kirjeldab põhjalikumalt föderatiivset hääletamist ja Stellar'i konsensuse protokolli. Kui Teil ei ole huvi üksikasjade vastu, siis siin on üldine ülevaade protsessist.

1. Sõlmed viivad läbi föderatiivse hääletamise voorud «nomineeritud» üle. Föderatiivse hääletamise voor tähendab:
   • Sõlm hääletab mingi kinnituse üle, näiteks: «Ma soovitan väärtust V»;
   • Sõlm kuulab osaliste hääli, kuni leiab sellise, kes suudab «aktsepteerida»;
   • Sõlm otsib «kvoorumi» selle kinnituse jaoks. Kvoorum «kinnitab» nomineeritud.
2. Kui sõlm suudab kinnitada üht või mitut kandidaati, proovib ta "valimis" ette valmistada mitmete föderatiivsete häälte ringide kaudu.
3. Kui sõlm on võimeline kontrollima valimis valmistumist, püüab ta seda kinnitada veelgi suuremate föderatiivsete häälte ringide kaudu.
4. Kui sõlm suudab kinnitada valimise, võib ta selle valimise väärtust "väljastada", kasutades seda konsensuse tulemuseks.

Need sammud sisaldavad mitmeid föderatiivsete häälte ringe, mis kokku moodustavad ühe SCP ringi. Uurime lähemalt, mis igas sammus toimub.

Föderatiivne hääletamine

Föderatiivne hääletamine on protseduur, et määrata, kas võrk suudab kokku leppida ettepanekus. Häälte ringis peab iga sõlm valima ühe paljusid võimalikke väärtusi, kuid ta ei saa seda teha, enne kui ei ole kindel, et teised sõlmed ei vali erinevat tulemust. Selleks, et selles veenduda, vahetavad sõlmed massiliselt sõnumeid edasi-tagasi. kinnitas, et kvorum sõlmed vastu võtma üks ja sama lahendus. Järgmised osad selgitavad selles lauses kasutatud termineid ja kogu protseduuri.

Kvoorumeid ja kvoorumi jagunemisi

Alustame kvoorumi määratlemisest. Nagu eespool arutasime, on hajutatud võrkus, kus liikmed muudavad pidevalt oma koosseisu, võimatu ette teada sõlmede arvu ning seega, kui palju on vaja enamuse saavutamiseks. Föderaalsed hääletused lahendavad selle probleemi, esitades uue idee kvoorumi jagunemisest (quorum slice): väike hulk võrdselt omavahel ühendatud sõlmi, kellele sõlm usaldab teabe edastamise hääletamise oleku kohta ülejäänud võrgus. Iga sõlm määrab oma kvoorumi jagunemise (millega ta tegelikult liitub).

Kvoorumi moodustamine algab kvoorumi jagunemisest. Iga sõlme juurde lisatakse tema jagunemise sõlmed. Seejärel lisatakse nende sõlmede jagunemise liikmed ja nii edasi. Aja jooksul satub üha rohkem sõlmi, mida te ei saa lisada, kuna nad on juba jagunemises. Kui uusi sõlmi enam pole, lõppeb protsess: oleme moodustanud kvoorumi algse sõlme kvoorumi jagunemise kaudu 'transitiivse sulgemisega'. ja nii edasi. Protsessi käigus satute järjest rohkemate sõlmedega, mida ei saa lisada, kuna need on juba kvoodis. Kui uusi sõlmi enam pole, peatutakse: oleme loonud kvoori „transitiivse sulgemise” abil (transitive closure) algse sõlme kvoorist.

Ette leida antud sõlmest kvorumit...

...lisame tema lõike liikmeid...

...siis lisame nende sõlmede lõikude liikmeid.

Jätkame, kuni lisamiseks pole enam sõlmi.

Lisamiseks pole sõlmi jäänud. See on kvorum.

Tegelikult võib iga sõlm kuuluda rohkem kui ühte lõiku. Kvorumi moodustamiseks valige ainult üks lõik ja lisage liikmed; seejärel valige iga liikme jaoks mõni muu lõik ja lisage liikmed sellest lõik ja nii edasi. See tähendab, et iga sõlm on osa mitmest võimalikust kvorumist.

Valige igal sammul vaid üks kvorumi lõik.

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

...valime teisi lõike...

...(kui see on võimalik)...

...moodustab teise kvorumi.

Kuidas sõlm teab, millistes lõikudes teised sõlmed on? Just nagu teavet teiste sõlmede kohta: edastustest, mida iga sõlm võrku edastab, kui tema hääletamise olek muutub. Iga edastus sisaldab teavet edastava sõlme lõikude kohta. Tehnilises dokumendis SCP ei ole suhtlemismehhanismi määratletud. Teostustes kasutatakse tavaliselt gossip protokolli õigustatud sõnumite edastamiseks kogu võrgus.

Tuletame meelde, et mittefederatiivses Bütsantsi konsensuse süsteemis määratakse kvoorum kui enamus kõigist sõlmpunktidest. Bütsantsi konsensuse süsteem on välja töötatud küsimuse seisukohalt: kui palju ebaausaid sõlmpunkte suudab süsteem taluda? N sõlmpunktiga süsteemis, mis on projekteeritud taluma f riket (pettuseid), peab sõlm suutma saavutada edusamme, saades vastuse N−f osalejalt, kuna f neist ei pruugi töötada. Kuid vastuse saades N−f osalejalt, võib eeldada, et kõik f osalejat (kellest sõlm vastust ei saanud) on tegelikult ausad. Seega on pahatahtlikud f N−f osalejast (kellest saadi vastus). Et sõlmed jõuaksid ühisele konsensusele, peab aus olema enamus ülejäänud sõlmpunktidest, s.t. meil on vajalik, et N−f oleks suurem kui 2f või N > 3f. Seega on tavaliselt süsteem, mis on projekteeritud taluma f riket, kokku N=3f+1 sõlmpunkti ja kvoorumi suurus on 2f+1. Kui ettepanek ületab kvoorumi piiri, on ülejäänud võrgu liikmed veendunud, et kõik konkurentsivõimelised ettepanekud ebaõnnestuvad. Nii jõuab võrk tulemusele.

Kuid föderatiivses Bütsantsi lepingute süsteemis ei saa mitte ainult olla enamus (sest keegi ei tea võrgu üldist suurust), vaid enamuse mõisted on täielikult kasutud! Kui liitumine süsteemiga on avatud, võib keegi saavutada enamuse, tehes nn Sybilli rünnaku: liitudes mitmeid kordi võrku eri sõlmede kaudu. Miks siis võib ülemineku sulgemist lõigata nimetada kvoorumi, ja kuidas see suudab maha suruda konkurentide ettepanekuid?

Tehniliselt ei suuda! Kujutage ette võrgustikku, kus on kuus sõlme, kus kaks kolmikute rühma on üksteise kvorumis lõigatud. Esimene alagrupp võib teha otsuse, millest teine kunagi kuulda ei saa ja vastupidi. Selle võrgu jaoks ei ole mingit võimalust konsensuse saavutamiseks (välja arvatud juhuslikult).

Seetõttu nõuab SCP, et föderatiivse hääletamise jaoks (ja artikli oluliste teoreemide kohaldamiseks) peab võrgul olema omadus, mida nimetatakse kvorumite ristumiseks. Selle omadusega võrgus kattuvad alati vähemalt ühes sõlmes kõik kaks kvroomi, mille saate koostada. Selleks, et määratleda võrgu valitsevad meeleolud, on see sama hea kui omada enamust. Intuitiivselt tähendab see, et kui mõni kvroom nõustub väitega X, siis ei saa ükski teine kvroom kunagi nõustuda millegi muuga, sest see peab tingimata sisaldama mõnda sõlme esimesest kvroomist, mis on juba hääletanud X-i poolt.

Kui võrgus on kvroomide kattuvus...

...siis kõik kaks kvroomi, mida saate koostada...

...kattuvad alati.

(Muidugi võivad kattuvad sõlmed osutuda bijantsiete-lahkudeks või halbades aspektides nõrkadeks. Sel juhul ei aita kvroomide kattumine üldse võrku kokku leppida. Seetõttu põhinevad paljud tulemused tehnilises dokumendis SCP avalikult väljendatud eeldustel, näiteks et võrgu kvroomide kattuvus jääb alles... ...isegi pärast halbade sõlmede eemaldamist.. Lihtsuse huvides jätame need eeldused... ...varjatuks. ...artikli ülejäänud osas).

Mõnikord võib tunduda mõistlik, et sõltumatute sõlmede võrgus on usaldusväärne kvoorumi ületamine võimalik. Kuid on kaks põhjust, miks see nii on.

Esimene põhjus on interneti olemasolu. Internet on ideaalne näide sõltumatute sõlmede võrgust, millel on kvoorumi ületamine. Enamik interneti sõlmi on ühendatud ainult mõne teise kohaliku sõlmega, kuid need väikesed kogumid kattuvad piisavalt, et iga sõlm oleks kergesti kätte saadav mistahes muust sõlmest mingi marsruudi kaudu.

Teine põhjus on spetsiifiline Stellar maksevõrgustikule (SCP kõige levinum rakendus). Igal varal Stellar võrgus on emitter ning Stellar soovitused nõuavad, et igal emitteril oleks määratud üks või mitu sõlme, mis töötlevad lunamispäringud. On teie huvides kaasata otse või kaudselt need sõlmed iga teid huvitava vara kvora lõikes. Siis kattuvad kõikide sõlmede kvora, mis on huvitatud antud varast, vähemalt nende lunamisõlmedega. Sõlmed, mis on huvitatud mitmest varast, kaasavad oma kvora lõikesse kõik vastava emitentide lunamisõlmed ja püüavad ühendada kõik varad kokku. Lisaks, igasuguseid varasid, mis ei ole omavahel seotud, ja ei tohiks olla omavahel seotud — on see planeeritud, et sellel võrgul ei oleks kvora kattuvust (näiteks dollaritsooni pangad tahavad mõnikord kaubelda eurotsooni pankade ja peso tsooni pankadega, mistõttu nad on ühes võrgus, kuid neil ei ole mingit huvi eraldi laste võrgustiku, mis kaupleb pesapallikaartidega, vastu).

Muidugi, ootamine kvorumite ristumised ei ole garantii. Teised bütsantsi lepingusüsteemid on oma keerukuses suuresti tänu kvorumite garantiile. Oluline uuendus SCP-s on see, et see vabastab kvorumite loomise vastutusest konsensuse algoritmi ning toob selle rakendustasemele. Seega, kuigi föderatiivne hääletamine on piisavalt üldine igasuguste küsimuste hääletamiseks, sõltub selle usaldusväärsus tegelikult kriitiliselt nende tähenduste laiemast mõttest. Mõned hüpoteetilised kasutusmood võivad osutuda vähem mugavaks hästi seotud võrkude loomisel kui teised.

Hääletamine, vastuvõtt ja kinnitamine

Föderatiivse hääletamise voorus hakkab sõlm n-ö valima mingit väärtust V. See tähendab sõnumi: „Mina olen sõlm N, minu kvorumite lõiked Q ja ma hääletan V poolt.” Kui sõlm hääletab selliselt, lubab ta, et ta ei ole kunagi V vastu hääletanud ja ei tee seda kunagi.

Üksus näeb, kuidas teised hääletavad ühtse võrguülekande kaudu. Kui üksus kogub piisavalt selliseid sõnumeid, suudab ta jälgida kvoorumite lõike ja proovida leida kvoorume. Kui ta näeb kvoorumit, mis hääletab V poolt, võib ta edasi liikuda vastuvõtmiseni V ja edastada selle uue sõnumi võrku: «Mina olen üksus N, minu kvoorumi lõiked Q ja ma võtan vastu V». Vastuvõtt tagab tugevama garantii kui lihtsalt hääletamine. Kui üksus hääletab V poolt, ei või ta kunagi hääletada teiste valikute poolt. Kuid kui üksus võtab vastu V, siis ei võta ükski võrgu üksus kunagi vastu teisi valikuid (teoreem 8 SCP tehnilises dokumendis tõestab seda).

Muidugi, on suur tõenäosus, et kohe ei leita kvoorumit, mis nõustuks V-ga. Teised üksused võivad hääletada teiste väärtuste eest. Kuid üksusel on veel üks võimalus liikuda lihtsast hääletamisest vastuvõtmiseni. N võib võtta vastu teise väärtuse W, isegi kui ta ei ole selle jaoks hääletanud, ja isegi kui ta ei näe selle jaoks kvoorumit. Selleks, et muuta oma häält, piisab nägemisest blokeeriv komplekt sõlmed, mis on vastu võtnud W. Blokeeriv hulk — see koosneb ühest sõlmest iga kvoorumi lõigust N. Nimi viitab sellele, et see suudab blokeerida iga muud väärtust. Kui kõik selles hulgas olevad sõlmed võtavad vastu W, siis (teoreem 8) ei õnnestu kunagi moodustada kvoorumit, mis võtaks vastu muud väärtust, ja seega on N-i jaoks ka W vastuvõtmine ohutu.

Sõlm N, millel on kolm kvoorumi lõiku.

B-D-F — blokeeriv hulk N jaoks: see sisaldab ühte sõlme iga N-i lõigu kohta.

B-E on samuti blokeeriv hulk N jaoks, kuna E esindab kahes N-i lõigus.

Kuid blokeeriv hulk ei ole kvoorum. Oleks liiga lihtne petta sõlme N, et see aktsepteeriks vajalikku väärtust, kui on piisav, et häkkida üks ainus sõlm igas N lõikes. Seetõttu ei tähenda väärtuse aktsepteerimine veel hääletamise lõppu. Selle asemel peab N väärtust kinnitama, see tähendab nägema kvoorumit sõlmedest, mis selle aktsepteerivad. Kui ta jõuab selleni, tõestab tehniline dokument SCP (teoreem 11), et ülejäänud võrgu osa kinnitab samuti sama väärtust, seega lõpetab N föderatiivse hääletamise kindla väärtuse tulemusega.

Föderatiivne hääletamine.

Hääletamise, aktsepteerimise ja kinnitamise protsess moodustab ühe täispika föderatiivse hääletamise ringi. Stellar konsensusprotokoll kogub palju selliseid ringe, et luua täiskonsensuslik süsteem.

Stellar konsensusprotokoll

Kaks kõige olulisemat omadust konsensuslikust süsteemist on turvalisus ja elujõud. Konsensusalgotitm on "turvaline", kui see ei saa kunagi anda erinevaid tulemusi erinevatele osalejatele (Bob'i ajalugu ei ole kunagi vastuolus Caroliga). "Elujõud" tähendab, et algoritm annab alati tulemuse, st ei jää kinni.

Käesolev föderaalne hääletamisprotseduur on turvaline selle tähenduses, et kui sõlm kinnitab väärtust V, ei tohi ükski teine sõlm kinnitada teist väärtust. Kuid "mitte kinnitada teist väärtust" ei tähenda, et see peab tingimata midagi kinnitama. Osalejad võivad hääletada nii paljude erinevate väärtuste üle, et ükski ei jõua vastuvõtu künniseni. See tähendab, et föderaalsetes hääletustes puudub elujõud.

Stellar konsensusprotokoll kasutab föderatiivset hääletamist, et tagada nii turvalisus kui ka elujõud. (SCP turvalisuse ja elujõudluse garantiil on teoreetiline piir. Konstruktsioon valib väga tugeva turvalisuse garanteerimise, ohverdades veidi elujõudlust, kuid arvestades piisavat aega, saavutatakse kõrge tõenäosusega konsensus.) Üldiselt seisneb idee selles, et korraldatakse mitmeid föderatiivseid hääletusi mitmete väärtuste üle, kuni üks neist läbib täielikult kõik SCP hääletamisfaasid, nagu allpool kirjeldatud.

Väärtused, mille üle SCP konsensusele püüab, võivad olla tehingute ajalugu, lõunaeine tellimus või midagi muud, kuid oluline on märkida, et need ei ole väärtused, mis on vastu võetud või kinnitatud. Selle asemel toimub föderatiivne hääletamine nende väärtuste väidete üle.

Esimesed föderatiivse hääletamise voorud toimuvad esitamisseerval (nomination phase), avalike selgituste kogumisel, mis on määratud vormingule «Ma esitan V», on võimalik paljude erinevate väärtuste V jaoks. Esitamise eesmärk on leida üks või mitu selgitust, mis lähevad edasi vastuvõtmise ja kinnitamise protsessi.

Kinnitatavate kandidaatide leidmisel liigub SCP hääletamise etappi, kus eesmärk on leida teatud hääletus (st ettepaneku väärtuse anum) ja kvoorum, mis suudab kuulutada kommitt selle jaoks (commit). Kui kvoorum teeb hääletuse kommitti, võetakse selle väärtus konsensuse põhjal vastu. Kuid enne, kui sõlm saab kommitti hääletada, peab ta kõigepealt kinnitama tühistuse kõigi madalama arvu hääletuste puhul. Need sammud — hääletuste tühistamine, et leida see, mille jaoks saab kommitti kinnitada — hõlmavad mitmeid ringe föderaalset hääletamist mitmete hääletuste deklaratsioonide üle.

Järgnevates osades käsitletakse lähemalt esitamise ja hääletamise protsesse.

Esitamine

Etapi alguses võib iga sõlm spontaanselt valida väärtuse V ja hääletada kinnituse üle, et "Ma esitan V". Selle etapi eesmärk on kinnitada mõne väärtuse esitamine föderatiivse hääletamise kaudu.

Võimalik, et piisav arv sõlmi hääletab piisavalt erinevate ettepanekute poolt ja ükski esitamine ei saavuta vastuvõtu piiri. Seetõttu, peale oma nomineerimise häälte edastamise, "peegeldavad" sõlmed oma võrgustiku nomineerimisi. Peegeldamine (echo) tähendab, et kui sõlm hääletab ettepaneku V poolt, aga näeb naabri sõnumit, kes hääletab ettepaneku W poolt, hääletab ta nüüd nii ettepaneku V kui ka W poolt. (Kõiki võrgustiku häälte peegeldusi ei saa hääletamisel kajastada, kuna see võib viia erinevate nominentide plahvatuseni. SCP sisaldab nende häälte reguleerimise mehhanismi. Lühidalt öeldes, on olemas valem, et määrata „prioriteet” võrgu vaates, ja peegeldatakse ainult kõrge prioriteediga sõlmede hääli. Mida kauem ettepanek kestab, seda madalam on piir, seega laiendab sõlm seeria sõlmi, kelle hääli ta peegeldab. Prioriteedi valem sisaldab ühe sisendidena slotinumbrit, seega võib kõrge prioriteediga võrgu sõlm ühe sloti jaoks olla madala prioriteediga teise jaoks ja vastupidi).

Kontseptuaalselt on samaaegne esitlemine nii V kui ka W eraldi föderatiivsed hääled, millest igaüks on võimeline jõudma vastu võtmiseni või heakskiitmiseni. Praktiliselt pakivad SCP protokolli sõnumid need eraldi hääled kokku.

Kuigi hääletamine V esitlemise poolt on lubadus mitte hääletada V esitlemise vastu, määratleb rakenduse tasand — antud juhul SCP —, mida tähendab „vastu”. SCP ei näe väidet, mis on vastuolus häältega „Ma esitan X”, see tähendab, et ei ole sõnumit „Ma olen vastu X esitlemisele”, seega võib sõlm hääletada ükskõik milliste väärtuste esitlemise poolt. Paljud neist kandidaatidest ei vii kuhugi, kuid lõppkokkuvõttes suudab sõlm heaks kiita või kinnitada ühe või mitu väärtust. Kui kandidaat on kinnitatud, siis ta muutub kandidaadiks.

SCP esitlemine föderatiivse hääletamisega. Ühtselt pingereas olevate sõlmede poolt võib olla palju väärtusi 'B', mis on esitatud ja 'peegelduvad' sõlme.

Kandidaatide esitlemine võib viia mitme kinnitatava kandidaadi tekkimiseni. Seetõttu nõuab SCP, et rakendustase pakuks mingisugust meetodit kandidaatide ühtsesse andmesse ühendamiseks. komposiit (composite). Ühendamise meetod võib olla ükskõik milline. Peaasi, et kui see meetod on määratletud, ühendab iga sõlm samu kandidaate. Toitlustamise hääletussüsteemis võib «ühendamine» tähendada lihtsalt ühe kandidaadi tagasilükkamist. (Aga määratletud viisil: iga sõlm peab valima sama väärtuse lähtestamiseks. Näiteks varasema valiku põhjal tähestikulises järjekorras). Stellar'i maksevõrgus, kus toimub tehingute ajaloo hääletamine, eeldab kahe esitatud kandidaadi ühendamine tehingute ühendamist, mida nad sisaldavad, ja nende kahe ajatempli viimast.

SCP-i tehniline kirjeldus tõestab (teoreem 12), et esitlemise faasi lõpuks jõuab võrk lõpuks ühte komposiiti. Kuid probleem on järgmine: föderaalne hääletamine on asünkrooniline protokoll (nagu ka SCP). Teisisõnu, sõlmed ei koordineeru ajaliselt, vaid ainult sõnumite kaudu, mida nad saadavad. Sõlme vaatenurgast pole selge, millal lõppes esitlemise faas. Ja kuigi kõik sõlmed jõuavad lõpuks samasse komposiiti, võivad nad sellel teel valida erinevaid marsruute, luues erinevaid kandidaate, ja kunagi ei saa nad öelda, milline neist on lõplik.

Aga see pole probleem. Esitlemine on vaid ettevalmistus. Peamine on piirata kandidaatide arvu konsensuse saavutamiseks, mis toimub hääletamise (hääletamine).

Hääletamine

Bületten on paar , kus counter on täisarv, mis algab numbrist 1, ja value on esitatud kandidaat. See võib olla node'i oma kandidaat või naabernode'i kandidaat, mille see node on vastu võtnud. Üldiselt, kui hääletatakse, on eesmärgiks üritada korduvalt saavutada üksmeelt võrgu poolt mingi kandidaadi üle teatud bületis kaudu, võimaldades potentsiaalselt mitmeid föderaalseid hääletusi bületise avalduste üle. Bülettenites olevad loendurid jälgivad tehtud katseid, ja suurema loenduriga bületendid on eelistatud väiksema loenduriga bületistest. Kui bületten jääb seisma, algab uus hääletus, nüüd bületisel .

Oluline on eristada väärtusi (näiteks mis peaks olema lõunasöögi tellimus: pitsat või salateid), bülette (paar counter-value) ja bülette avaldusi. SCP voor hõlmab mitmeid voorusid föderaalsest hääletamisest, sealhulgas järgmiste avalduste osas: bülletäänidest. SCP voor sisaldab mitmeid voorude föderaalse hääletamise ringe, mille käigus arutatakse järgmisi avaldusi:

• „Olen valmis bületise B komiteeks“ ja
• „Ma kuulutan välja bületise B komitee“

Selle sõlme vaatenurgast saavutatakse konsensus, kui see leiab B-bületäi, mille jaoks suudetakse kinnitada (st leida kvoot, mis aktsepteerib) avaldust „Ma kuulutan välja B-bületi komitee“. Sellest hetkest alates saab ohutult tegutseda, tuginedes B-s märgitud tähendusele — näiteks esitada selle lõunasöögi tellimuse. Seda nimetatakse eksternaliseerimiseks tähenduseks. Kui bületsläte on kinnitatud, võib sõlm olla kindel, et mis tahes muu sõlm on sama tähenduse eksternaliseerinud või kindlasti teeb seda tulevikus.

Kuigi kontseptuaalselt toimub paljusid föderaalseid hääletusi erinevate bülettide avalduste osas, vahetatakse neid siiski mitte väga suure hulga sõnumite kaudu, sest iga sõnum kapseldab hulga bülette. Üks sõnum edendab seega samaaegselt paljusid föderaalseid hääletusi, näiteks: „Ma aktsepteerin bülettide komiteed vahemikus kuni “.

Mida tähendavad terminid „valmistatud“ (prepared) ja „komitee“ (commit)?

Sõlm hääletab valimisnimekirja kinnitamise poolt, kui ta on veendunud, et teised sõlmed ei tee valimisnimekirja kinnitamisega teisi väärtusi. Selle veendumise saavutamine on avalduse ettevalmistamise eesmärk. Hääletamine, kus öeldakse: "Olen valmis kinnitama valimisnimekirja B", on lubadus mitte kunagi kinnitada valimisnimekirja väiksemas osas kui B, st väiksema loenduri kohaselt (SCP nõuab, et valimisnimekirjades oleksid väärtused kindlas järjekorras. Niisiis, valimisnimekiri on väiksem kui , kui N1<N2, ja samuti kui N1=N2 ja V1<V2). Need väiksemad valimisnimekirjad „tühistatakse” (aborted) ettevalmistava hääletamise käigus, samal ajal kui B loetakse „valmis” seremooniad.

Miks tähendab „Olen valmis kinnitama valimisnimekirja B” „Lubadus mitte kunagi lubada valimisnimekirju, mis on väiksemad kui B”? Sellepärast, et SCP määratleb tühistamise vastandina kinnitamisele. Valimisnimekirja ettevalmistamisel tähendab hääletamine ka teiste valimisnimekirjade tühistamise hääletamist ja nagu me varem arutasime, on hääletamine millegi poolt lubadus mitte kunagi hääletada selle vastu.

Enne kui sõnum väljastatakse, peab sõlm esmalt leidma hääletuse, mille ta võib kinnitada kui koostatud. Teisisõnu, ta viib läbi föderatiivse hääletuse teema "Olen valmis hääletama B hääletuse üle", mis võib kehtida paljude erinevate hääletuste kohta, kuni ta leiab selle, mis saavutab kvoorumi.

Kust tulevad hääletused hääletamiseks? Esmalt edastab sõlm ettevalmistuse hääletuseks <1,C>, kus C on kandidaat-komposiit, mis luuakse kandidaatide esitamise etapis. Kuid isegi pärast hääletamise ettevalmistamise algust võivad kandidaadid, kes on üles seatud, tuua esile uusi kandidaate, mis muutuvad valikute hääletusteks. Samal ajal võivad osalistel olla erinevad kandidaadid ning nad võivad moodustada blokimeeriva hulga, mis aktsepteerib "Olen valmis hääletama B2 hääletuse üle", veenides sõlme seda samuti aktsepteerima. Lõpuks on olemas ajamisseade, mis genereerib uusi föderatiivse hääletuse vooru kõrgemate loenduritega, kui praegused hääletused on kinni jäänud.

Kui sõlm leiab B-bülletääni, mida saab kinnitada kui ettevalmistatud, edastab ta uue sõnumi "B bülletääni kinnitamine". See häälteandmise protsess ütleb piramidele, et sõlm ei loobu kunagi B-st. Tegelikult, kui B on bülletään , siis "B bülletääni kinnitamine " tähendab tingimusteta nõusolekut hääletada iga bülletääni eest kuni . See lisamine aitab teistel sõlmedel piramidele kinnitada, kui nad on endiselt protokollis varasematel etappidel.

Sellel etapil on oluline rõhutada, et tegu on asünkroonsete protokollidega. Ainult seetõttu, et üks sõlm saadab häälte kinnitamiseks, ei tähenda see, et tema eakaaslased teevad sama. Mõned neist võivad ikka veel hääletada ettepanekute kinnitamiseks, teised võivad juba väärtuse eksternaliseerida. SCP selgitab, kuidas sõlm peaks iga tüüpi peer-to-peer sõnumit sõltumata selle faasist käsitlema.

Kui teade "Ma kuulutan välja komitee <N,C>" ei saa olla aktsepteeritud ega kinnitatud, siis on tõenäosus, et teade <N+1,C> või <N+2,C> — või igal juhul mõni teade väärtusega C, mitte miski muu, kuna sõlm on juba lubanud kunagi mitte tühistada <N,C>. kui sõlm edastab hääli komiteele, siis on see C või mitte midagi, sõltuvalt sellest, kui kaugele konsensus läheb. Kuid selleks ei ole sõlmele veel piisavalt, et väljastada C. Mõned bütsantsi peod (mis on vähem kui kvoorum, tuginedes meie turvalisuse oletustele) võivad sõlmele vale anda. Teatud teate (või teate vahemiku) vastuvõtmine ja seejärel kinnitamine on see, mis annab sõlmele lõpuks kindluse, et väljastada C.

SCP hääletamine föderatiivse hääletamise kaudu. Ei näidata: igal hetkel võib töösse minna taimer, suurendades hääletuse arvestit (ja võib-olla luua uusi komposiitkandidaate).

Ja see ongi kõik! Niipea kui võrgu konsensus saavutatakse, on see valmis seda uuesti ja uuesti tegema. Stellar'i maksevõrgus juhtub see umbes iga 5 sekundi järel: saavutus, mis nõuab nii turvalisust kui ka vastupidavust, mida garanteerib SCP.

SCP saavutab selle, tuginedes mitmele voorule föderatiivsetest hääletustest. Föderatiivne hääletus on võimalik tänu kvora lõike mõistele: rikkaid, võrdselt usaldatavaid sõlmed, millele iga sõlm otsustas toetuda oma (subjektiivse) kvora osana. See konfiguratsioon tähendab, et konsensuseni on võimalik jõuda isegi avatud liikmelisuse ja bütsantsi petetega võrgu keskkonnas.

Edasi lugemine

• SCP algne tehniline dokument on saadaval siit, ja siin rakendamise projektispetsiifikatsioonides.
• Protokolli SCP originaalautor David Mazier selgitab seda lihtsustatult (kuid siiski tehniliselt) siit.
• Võib-olla olite üllatunud, et ei leidnud artiklis termineid „kaevandamine” või „töö tõend”. SCP ei kasuta neid meetodeid, kuid mõned teised konsensuse algoritmid kasutavad. Zane Witherspoon on kirjutanud saadaval koondülevaate konsensusalgoritmidest.
• Samm-sammult kirjeldus lihtne võrgu, mis saavutab konsensuse ühe täieliku SCP-ringiga.
• Lugejatele, keda huvitavad SCP-lahendused: vt. C++ kood, mida Stellari maksevõrk kasutab, või Go kood, mille ma kirjutasin SCP parema mõistmise jaoks.

Allikas: habr.com