Протоколот за консензус на Ѕвездената првпат беше опишан во Дејвид Мазиер во 2015 година. Ова е „федерален византиски договорен систем“ кој им овозможува на децентрализираните компјутерски мрежи без лидери ефикасно да постигнат консензус за одлуката. Мрежата за плаќање Stellar го користи Stellar Consensus Protocol (SCP) за одржување на конзистентна историја на трансакции што е видлива за сите учесници.
Протоколите за консензус се сметаат за тешки за разбирање. SCP е поедноставен од повеќето од нив, но сепак ја дели оваа репутација - делумно поради погрешната идеја дека „федеративно гласање“, што е тема на првата половина на научната статија, е SCP. Но, тоа не е вистина! Ова е само важен градежен блок што го користи втората половина од статијата за да го создаде вистински Ѕвезден протокол за консензус.
Во оваа статија накратко ќе објасниме што е „систем на договори“, што може да го направи „византиски“ и зошто византискиот систем да го направи „федерален“. Потоа ќе ја објасниме процедурата за федеративно гласање опишана во написот на SCP и на крајот ќе го објасниме самиот протокол на SCP.
Договорни системи
Системот на договори им овозможува на група учесници да постигнат консензус за некоја тема, како на пример што да нарачате за ручек.
Во Interstellar, имплементиравме сопствен систем за договори за јадење: нарачуваме што вели нашиот оперативен менаџер Џон. Ова е едноставен и ефективен договорен систем. Сите му веруваме на Џон и веруваме дека секој ден ќе најде нешто интересно и хранливо.
Но, што ако Џон ја злоупотреби нашата доверба? Тој може сам да одлучи дека сите ние треба да станеме вегани. За една или две недели, веројатно ќе го собориме и ќе и ја предадеме власта на Елизабета. Но, одеднаш таа сака авокадо со аншоа и мисли дека сите треба да бидат такви. Моќта корумпира. Затоа, подобро е да се најде некој подемократски метод: некој начин да се увериме дека се земаат предвид различните преференци, притоа обезбедувајќи навремен и недвосмислен резултат, така што никој нема да заврши со нарачка за ручек, или пет луѓе да направат различни нарачки или дискусијата. се одолговлекува до вечерта.
Се чини дека решението е едноставно: одржи гласање! Но, ова е погрешен впечаток. Кој ќе ги собере гласачките ливчиња и ќе ги пријави резултатите? И зошто другите да веруваат во тоа што го кажува? Можеби можеме во прво време гласајте за лидер кому му веруваме дека ќе го води гласањето - но кој ќе го води прво со гласање? Што ако не можеме да се договориме за лидер? Или што ако се договориме, но овој лидер заглави на состанок или оди на боледување?
Слични проблеми се јавуваат во дистрибуирани компјутерски мрежи. Сите учесници или јазли мора да се согласат за некоја одлука, како на пример чиј е редот да ажурира споделена датотека или да отстрани задача од редот за обработка. Во мрежата на криптовалути, јазлите постојано треба да изберат како изгледа целосната приказна од неколку можни верзии, кои понекогаш се во конфликт. Овој мрежен договор му обезбедува уверување на примачот дека монетата е (а) валидна (не е фалсификувана) и (б) сè уште не е потрошена на друго место. Ова исто така осигурува дека тој ќе може да ги троши монетите во иднина бидејќи новиот примач ќе ги има истите гаранции од истите причини.
Секој консензус систем во дистрибуирана компјутерска мрежа мора да биде толерантен на грешки: мора да произведува конзистентни резултати и покрај грешките како што се бавните врски, јазлите што не реагираат и неправилно нарачување пораки. византиски Договорниот систем е дополнително отпорен на „византиски“ грешки: јазли кои даваат лажни информации, без разлика дали поради грешка или во намерен обид да се поткопа системот или да се добие некоја предност. „Византиска“ толеранција на грешки - способност да се верува на групна одлука дури и кога некои членови на групата може да лажат или на друг начин да не ги следат правилата за донесување одлуки - се нарекува кој се обидел да го координира нападот. кај Ентони Стивенс.
Размислете за сопственикот на крипто монети Алиса, која мора да избере помеѓу купување вкусен сладолед од Боб и отплата на долгот на Керол. Можеби Алиса сака да ги плати и двајцата одеднаш со измама трошејќи иста паричка. За да го направи ова, таа мора да го убеди компјутерот на Боб дека паричката никогаш не била платена на Керол и да го убеди компјутерот на Керол дека паричката никогаш не била платена на Боб. Византискиот систем на договори го прави тоа практично невозможно, користејќи форма на мнозинско владеење наречено кворум. Јазол во таква мрежа одбива да се пресели во одредена верзија на историјата додека не види дека доволен број врсници - кворум - се согласуваат со таквата транзиција. Откако ќе се случи ова, тие ќе формираат гласачки блок доволно голем за да ги принудат преостанатите мрежни јазли да се согласат со нивната одлука. Алис може да принуди некои јазли да лежат во нејзино име, но ако мрежата е доволно голема, нејзиниот обид ќе биде совладан од гласовите на искрените јазли.
Колку јазли се потребни за кворум? Во најмала рака, мнозинство, или подобро кажано, квалификувано мнозинство за борба против грешките и измамите. Но, за да го броите мнозинството, треба да го знаете вкупниот број на учесници. Во канцеларијата на Interstellar или на окружните избори, овие бројки лесно се откриваат. Но, ако вашата група е лабаво дефинирана мрежа во која јазлите можат да влегуваат и излегуваат по желба без одобрение од центарот, тогаш ви треба федерални византиски договорен систем способен да одредува кворуми не од однапред одредена листа на јазли, туку динамично, од постојано променлива и неизбежно нецелосна слика на јазли во даден момент во времето.
Можеби изгледа невозможно да се создаде кворум од перспектива на еден јазол во огромна мрежа, но тоа е можно. Таквиот кворум може дури и да ги гарантира резултатите од децентрализираното гласање. Белата книга на SCP покажува како да го направите ова со помош на процедура наречена со федерално гласање.
За нетрпеливи
Остатокот од статијата подетално го опишува федеративното гласање и протоколот за консензус на Ѕвездената. Ако не ве интересираат деталите, еве општ преглед на процесот.
- Јазлите спроведуваат рунди на федерално гласање за „номинираните“. Федералниот круг на гласање значи:
- Јазолот гласа за некоја изјава, на пример, „Јас ја предлагам вредноста на V“;
- Јазолот ги слуша гласовите на врсниците додека не најде некој што може да „прими“;
- Јазолот бара „кворум“ за ова тврдење. Кворумот го „потврдува“ номинираниот.
- Откако еден јазол може да потврди еден или повеќе номинирани, тој се обидува да го „подготви“ „гласачкото ливче“ преку неколку круга на федерално гласање.
- Откако еден јазол ќе може да потврди дека гласачкото ливче е подготвено, тој се обидува да го изврши преку уште повеќе кругови на федерално гласање.
- Откако еден јазол може да потврди заложба на гласачкото ливче, може да ја „надвореши“ вредноста на тоа гласачко ливче користејќи го како резултат на консензус.
Овие чекори вклучуваат повеќе кругови на федеративно гласање, кои колективно формираат еден круг SCP. Ајде внимателно да погледнеме што се случува на секој чекор.
Федерално гласање
Федерално гласање е постапка за утврдување дали мрежата може да се согласи на предлог. Во кругот на гласање, секој јазол мора да избере една од потенцијално многуте можни вредности. Не може да го направи ова освен ако не е уверен дека другите јазли во мрежата нема да изберат поинаков исход. За да се уверат во ова, јазлите разменуваат низа пораки напред-назад, така што сите потврдиДека кворум јазли прифаќа истото одлука. Остатокот од овој дел ги објаснува термините во оваа реченица и како се одвива целата постапка.
Кворуми и кворумски парчиња
Да почнеме со дефинирање на кворум. Како што дискутиравме погоре, во децентрализирана мрежа со динамично членство, невозможно е однапред да се знае бројот на јазли и затоа колку се потребни за мнозинството. Федералното гласање го решава овој проблем со воведување нова идеја намалување на кворумот (кворум парче): Мал сет на врсници на кои јазолот им верува за да ги пренесе информациите за статусот на гласање до остатокот од мрежата. Секој јазол дефинира свој кворумски дел (од кој станува де факто член).
Формирањето кворум започнува со намалување на кворумот. За секој јазол се додаваат неговите исечени јазли. Потоа се додаваат термините на парчиња овие јазли и така натаму. Како што продолжувате, има се повеќе и повеќе јазли што не можете да ги додадете бидејќи тие се веќе вклучени во парчето. Кога нема повеќе нови јазли за додавање, процесот запира: формиравме кворум со „преодно затворање“ на кворумскиот дел од почетниот јазол.
Да се најде кворум од даден јазол...
... додадете членови на неговото парче...
...потоа додаваме парчиња членови на овие јазли.
Продолжуваме додека не останат јазли за додавање.
Нема останати јазли за додавање. Ова е кворум.
Всушност, секој јазол може да се појави на повеќе од едно парче. За да формирате кворум, изберете само еден од парчињата и додајте членови; потоа изберете кое било парче за секој од членовите и додадете членови на овој сече и така натаму. Ова значи дека секој јазол е член на многу можни кворуми.
Изберете само едно парче кворум на секој чекор.
Еден можен кворум. Или алтернатива...
...изберете други парчиња...
…(кога е можно)…
... создава друг кворум.
Како еден јазол знае во кои парчиња се другите јазли? На ист начин како и другите информации за другите јазли: од преносите што секој јазол ги емитува на мрежата кога неговата состојба на гласање се менува. Секое емитување вклучува информации за парчињата на јазолот што испраќа. Белата книга на SCP не специфицира механизам за комуникација. Имплементациите обично користат за гарантирано емитување на пораки низ мрежата.
Потсетиме дека во нефедералниот византиски систем на договори, кворумот се дефинира како мнозинство од сите јазли. Византискиот договорен систем е дизајниран од гледна точка на прашањето: колку нечесни јазли може да толерира системот? Во систем од N јазли дизајнирани да преживеат f неуспеси, јазолот треба да може да напредува со примање повратни информации од N−f врсници бидејќи f од нив може да се исклучени. Но, откако добивме одговор од N−f врсници, можеме да претпоставиме дека сите f врсници (од кои јазолот не доби одговор) се всушност искрени. Така, f од N−f врсници (од кои е примен одговорот) се злонамерни. За јазлите да дојдат до истиот консензус, поголемиот дел од преостанатите јазли мора да бидат искрени, односно ни треба N−f да биде поголем од 2f или N > 3f. Значи, обично систем дизајниран да преживее f неуспеси ќе има вкупно N=3f+1 јазли и големина на кворум од 2f+1. Штом предлогот ќе го помине прагот на кворум, остатокот од мрежата е убеден дека сите конкурентни предлози ќе пропаднат. Така мрежата се приближува кон резултатот.
Но, во федерален византиски договорен систем, не само што не може да има мнозинство (бидејќи никој не ја знае вкупната големина на мрежата), туку концептот на мнозинство е сосема бескорисен! Ако членството во системот е отворено, тогаш некој може да добие мнозинство едноставно со извршување на таканаречениот напад Sybil: постојано приклучување на мрежата преку повеќе јазли. Значи, зошто може да се нарече преодно затворање на парчиња кворум, и како е во состојба да ги потисне конкурентните предлози?
Технички, нема шанси! Замислете мрежа од шест јазли, каде што две тројки се изолирани во едни со други кворумски парчиња. Првата подгрупа може да донесе одлука за која втората никогаш нема да слушне, и обратно. Нема начин оваа мрежа да постигне консензус (освен случајно).
Затоа, SCP бара дека за федерално гласање (и за да се применат важните теореми на трудот), мрежата мора да има својство наречено пресек на кворуми. Во мрежа со ова својство, кои било два кворума што може да се конструираат секогаш се преклопуваат во барем еден јазол. За одредување на преовладувачкото чувство на мрежата, ова е исто толку добро како да се има мнозинство. Интуитивно, ова значи дека ако некој кворум се согласи со изјавата X, ниту еден друг кворум никогаш не може да се согласи со ништо друго, затоа што нужно ќе вклучува некој јазол од првиот кворум кој веќе гласал за X.
Доколку има пресек на кворуми во мрежата...
...тогаш може да изградите кои било два кворума...
...секогаш ќе се вкрстуваат.
(Се разбира, преклопувачките јазли може да испаднат дека се византиски лажни или на друг начин лоши. Во овој случај, пресекот на кворумот воопшто не ѝ помага на мрежата да се согласи. Поради оваа причина, многу од резултатите во белата книга SCP се засноваат на експлицитни претпоставки, како што е она што останува во преминувањето на кворумот на мрежата дури и по отстранувањето на лошите јазли. За едноставност, да ги оставиме овие претпоставки имплицитна во остатокот од статијата).
Можеби изгледа неразумно да се очекува дека е можно сигурно преминување на кворум во мрежа од независни јазли. Но, постојат две причини зошто е тоа така.
Првата причина е постоењето на самиот Интернет. Интернетот е совршен пример за мрежа од независни јазли со вкрстени кворуми. Повеќето јазли на Интернет се поврзуваат само со неколку други локални јазли, но овие мали множества се преклопуваат доволно што до секој јазол може да се стигне од секој друг јазол по одредена рута.
Втората причина е специфична за мрежата за плаќање Stellar (најчестата употреба на SCP). Секое средство на Stellar мрежата има издавач, а упатствата на Stellar бараат секој издавач да назначи еден или повеќе јазли на мрежата за обработка на барањата за откуп. Во ваш најдобар интерес е директно или индиректно да ги вклучите овие јазли во кворумски делови за секое средство за кое сте заинтересирани. Кворумите за сите јазли заинтересирани за дадено средство потоа ќе се преклопуваат барем кај тие јазли за откуп. Јазлите заинтересирани за повеќе средства ќе ги вклучат сите јазли за откуп на соодветните издавачи во нивните делови од кворумот и тие ќе се обидат да ги здружат сите средства заедно. Покрај тоа, сите средства што не се поврзани на овој начин со други на мрежата, и не треба да се поврзува - ова е дизајнирано така што нема преклопување на кворумот за оваа мрежа (на пример, банките од зоната на доларот понекогаш сакаат да тргуваат со банките од еврозоната и банките од песо зоната, така што тие се на иста мрежа, но ниту една од нив се грижат за посебната мрежа на деца кои продаваат бејзбол картички).
Се разбира, чекање вкрстување на кворум не е гаранција. Другите византиски договорни системи должат голем дел од нивната сложеност на гаранцијата за кворуми. Важна иновација на SCP е тоа што ја отстранува одговорноста за создавање кворуми од самиот консензус алгоритам и ја носи на ниво на апликација. Така, иако федеративното гласање е доволно општо за да се гласа за кое било прашање, неговата веродостојност всушност критично зависи од поширокото значење на овие значења. Некои хипотетички употреби можеби не се толку погодни за создавање добро поврзани мрежи како другите.
Гласање, прифаќање и потврдување
Во федеративната рунда на гласање, еден јазол опционално започнува да гласа за некоја вредност V. Ова значи емитување порака до мрежата: „Јас сум јазол N, моите делови од кворумот се Q и гласам за V“. Кога еден јазол гласа на овој начин, тој ветува дека никогаш не гласал против V и никогаш нема да гласа.
Во peer-to-peer емитувањата, секој јазол гледа како гласаат другите. Откако еден јазол ќе собере доволно од овие пораки, може да следи делови од кворум и да се обиде да најде кворуми. Ако види кворум на врсници кои исто така гласаат за V, може да продолжи кон посвојување V и емитувајте ја оваа нова порака на мрежата: „Јас сум јазол N, моите делови од кворумот се Q и го прифаќам V“. Прифаќањето дава посилна гаранција од едноставното гласање. Кога јазол гласа за V, тој никогаш не може да гласа за други опции. Но, ако некој јазол прифати V, ниту еден јазол на мрежата нема да ја прифати другата опција (Теорема 8 во белата хартија SCP го докажува тоа).
Се разбира, постои голема веројатност дека нема веднаш да има кворум на јазли кои се согласуваат со V. Другите јазли може да гласаат за други вредности. Но, постои уште еден начин како јазолот да премине од едноставно гласање до прифаќање. N може да прифати различна вредност за W, дури и ако не гласал за неа, па дури и ако не гледа кворум за тоа. За да одлучите да го промените вашиот глас, само погледнете сет за блокирање јазли кои го прифатиле W. Блокирачкото множество е по еден јазол од секој од кворумските парчиња N. Како што сугерира името, може блок кое било друго значење. Ако сите јазли во такво множество го прифатат W, тогаш (со теорема 8) никогаш нема да биде возможно да се формира кворум кој зема различна вредност, и затоа е исто така безбедно за N да го прифати W.
Јазол N со три кворумски парчиња.
BDF е блокирачко множество за N: вклучува по еден јазол од секој дел од N.
BE е исто така блокирачко множество за N бидејќи E се појавува на два парчиња од N.
Но, блокадата не е кворум. Би било премногу лесно да се измами јазолот N да ја прифати саканата вредност ако е доволно да се хакира само еден јазол во секој од парчињата N. Затоа, прифаќањето на вредноста не е крај на гласањето. Наместо тоа, N мора да ја потврди вредноста, односно да види кворум од јазли кои ја прифаќаат. Ако стигне толку далеку, тогаш, како што докажува белата книга на SCP (во теорема 11), и остатокот од мрежата на крајот ќе ја потврди истата вредност, па N ќе го заврши федеративното гласање со одредена вредност како резултат.
Федерално гласање.
Процесот на гласање, прифаќање и потврдување претставува еден целосен круг на федеративно гласање. Протоколот за консензус на Stellar комбинира многу од овие кругови за да создаде целосен систем за консензус.
Ѕвездениот протокол за консензус
Двете најважни својства на консензусниот систем се - безбедност и опстанок. Алгоритмот за консензус е „безбеден“ ако никогаш не може да даде различни резултати на различни учесници (копијата на историјата на Боб никогаш нема да ѝ противречи на Керол). „Одживување“ значи дека алгоритмот секогаш ќе произведува резултат, односно нема да се заглави.
Опишана процедура за федерално гласање безбедно во смисла дека ако еден јазол ја потврди вредноста на V, ниту еден друг јазол нема да ја потврди другата вредност. Но, „нема да потврди друго значење“ не значи дека нужно ќе потврди нешто. Учесниците можат да гласаат за толку многу различни вредности што ништо нема да го достигне прагот на прифаќање. Тоа значи дека во федералното гласање нема опстанок.
Протоколот за консензус на Ѕвездената користи федеративно гласање на начин кој обезбедува и безбедност и опстанок. (Гаранциите за безбедност и опстанок на SCP имаат теоретска граница. Дизајнот избира многу силна безбедносна гаранција, жртвувајќи мало ублажување на опстанокот, но ако се има доволно време, голема е веројатноста да се постигне консензус.) Накратко, идејата е да има повеќе федерални гласови за повеќе вредности додека една од нив не ги помине сите фази на гласање на SCP опишани подолу.
Вредностите за кои SCP бара консензус може да бидат историја на трансакции или нарачка за ручек или нешто друго, но важно е да се напомене дека тоа не се вредностите што се прифаќаат или потврдуваат. Наместо тоа, федералното гласање се случува според изјави за овие вредности.
Првите кругови на федералното гласање се одржуваат на фаза на номинација (фаза на номинација), на збир на изјави како „Јас номинирав V“, можеби за многу различни вредности на V. Целта на номинацијата е да се најде една или повеќе изјави кои поминуваат низ прифаќање и потврда.
По изнаоѓање на проверливи кандидати, ДКП преминува во фазата на гласање, каде што целта е да се најде одреден билтен (односно контејнер за предложената вредност) и кворум што може да се изјасни посветат за тоа (обврзуваат). Ако кворумот го обврзе гласачкото ливче, неговата вредност се прифаќа како консензус. Но, пред еден јазол да може да гласа за извршување на гласачкото ливче, прво мора да потврди откажување сите гласачки ливчиња со помала противвредност. Овие чекори - поништување на гласачките ливчиња за да се најде едно што може да се изврши - вклучуваат повеќе кругови на федерално гласање за повеќе барања за гласачки ливчиња.
Следните делови подетално го опишуваат номинацијата и гласањето.
Номинација
На почетокот на фазата на номинација, секој јазол може спонтано да избере вредност за V и да гласа за изјавата „Јас номинирав V“. Целта во оваа фаза е да се потврди номинацијата на одредена вредност преку федеративно гласање.
Можеби доволно јазли гласаат за доволно различни предлози што ниту една номинација не може да го достигне прагот на прифаќање. Затоа, покрај емитувањето на сопствените гласови за номинација, јазлите ги „одразуваат“ номинациите на нивните врсници. Ехо значи дека ако некој јазол гласа за номинација V, но види порака од соседот кој гласа за номинација W, сега ќе гласа и за V и за W. (Не се повторуваат сите гласови од колегите за време на номинацијата бидејќи тоа може да доведе до експлозија на различни номинирани. SCP вклучува механизам за регулирање на овие гласови. Накратко, постои формула за одредување на „приоритет“ на врсниците од гледна точка на јазол и се рефлектираат само гласовите на јазлите со висок приоритет. Колку е подолга номинацијата е потребно, толку е помал прагот, па јазолот го проширува множеството врсници чии гласови ќе ги одразува. Формулата за приоритет го вклучува бројот на слотот како еден од неговите влезови, така што врсникот со висок приоритет за еден слот може да биде врсник со низок приоритет за друг, и обратно).
Концептуално, номинацијата е паралелна, и V и W се посебни федерални гласови, секој поединечно способен да постигне прифаќање или потврда. Во пракса, пораките од протоколот SCP ги спакуваат овие поединечни гласови заедно.
Иако гласањето за номинацијата на V е ветување дека никогаш нема да се гласа против номинацијата на V, на ниво на апликација - во овој случај SCP - се утврдува што значи „против“. SCP не гледа изјава што е во спротивност со гласот „Јас номинирам X“, односно нема порака „Јас сум против номинирање на X“, така што јазолот може да гласа за номинирање на какви било вредности. Многу од овие номинации нема да одат никаде, но на крајот јазолот ќе може да прифати или потврди една или повеќе вредности. Откако ќе се потврди номиниран, тој станува кандидат.
Номинација на SCP со користење на федеративно гласање. Може да има многу вредности „Б“ кои се поставени од врсниците и „рефлектирани“ од јазолот.
Номинациите може да резултираат со повеќе потврдени кандидати. Затоа, SCP бара од апликацискиот слој да обезбеди некој метод за комбинирање на кандидатите во еден композитни (композитен). Начинот на спојување може да биде кој било. Главната работа е дека ако овој метод е детерминистички, тогаш секој јазол ќе ги комбинира истите кандидати. Во системот на гласање за ручек, „обединување“ може едноставно да значи отфрлање на еден од двајцата кандидати. (Но на детерминистички начин: секој јазол мора да ја избере истата вредност за ресетирање. На пример, претходниот избор по азбучен ред). Во мрежата за плаќање Stellar, каде што се гласа за историјата на трансакциите, спојувањето на двајца предложени номинирани вклучува спојување на трансакциите што тие ги содржат и најновиот од нивните два временски ознаки.
Белата книга на SCP докажува (теорема 12) дека до крајот на фазата на проширување, мрежата на крајот се конвергира во еден композит. Но, има проблем: федеративното гласање е асинхрон протокол (како SCP). Со други зборови, јазлите не се координираат со времето, туку само со пораките што ги испраќаат. Од гледна точка на јазолот, не е јасно кога заврши фаза на продолжување. И иако сите јазли на крајот ќе пристигнат на истиот композит, тие може да земат различни правци на патот, создавајќи различни композитни кандидати на патот и никогаш не можат да кажат кој е конечниот.
Но нормално е. Номинацијата е само подготовка. Главната работа е да се ограничи бројот на кандидати за да се постигне консензус, што се случува во процесот се кандидира за функцијата (гласање).
Трчање
Билтен е пар , каде бројачот е цел број кој започнува на 1, а вредноста е кандидат од фазата на номинација. Ова може да биде сопствен кандидат на јазол или кандидат на соседниот јазол прифатен од тој јазол. Грубо кажано, гласачкото ливче вклучува повторени обиди да се принуди мрежата да постигне консензус за некој кандидат на одредено гласачко ливче со одржување на потенцијално многу федерални гласови за изјавите на гласачките ливчиња. Бројачите на гласачките ливчиња водат евиденција за направените обиди, а гласачките ливчиња со поголемо пребројување имаат предност пред гласачките ливчиња со помало броење. Доколку билтенот заглавува, започнува ново гласање, сега на гласачкото ливче .
Важно е да се направи разлика значења (на пример, каков треба да биде редоследот за ручек: пица или салати), билтени (пар противвредност) и искази за гласачките ливчиња. Рундата SCP вклучува неколку круга на федерално гласање, особено за следните изјави:
- „Подготвен сум да го обврзам гласачкото ливче Б“ и
- „Објавувам полагање на гласачкото ливче Б“
Од перспектива на даден јазол, консензус се постигнува кога ќе најде гласачко ливче Б за кое може да ја потврди (т.е., да најде кворум што ја прифаќа) изјавата „Го обврзувам гласачкото ливче Б“. Од овој момент, безбедно е да се постапи според вредноста наведена во Б - на пример, ставање на оваа нарачка за ручек. Тоа се нарекува екстернализација значења. Откако ќе се потврди прифаќањето на гласачкото ливче, јазолот може да биде сигурен дека кој било друг јазол ја има екстернализирано истата вредност или ќе го стори тоа во иднина.
Иако многу федерални гласања концептуално се спроведуваат за барања за многу различни гласачки ливчиња, тие не разменуваат толку многу пораки бидејќи секоја порака содржи одреден број гласачки ливчиња. Една порака на тој начин ја промовира состојбата на многу федерални гласови одеднаш, на пример: „Прифаќам обврзани гласачки ливчиња кои се движат од пред "
Што значат термините „подготвени“ и „посветени“?
Јазол гласа за да се изврши гласачко ливче кога е уверен дека другите јазли нема да извршат гласачки ливчиња со различни вредности. Убедување тоа е целта на подготовката на апликацијата. Гласот кој вели „Подготвен сум да го извршам гласачкото ливче Б“ е ветување дека никогаш нема да се изврши гласачко ливче помало од Б, т.е. со помало пребројување (SCP бара вредностите во гласачките ливчиња да бидат во одреден редослед. Така, билтен помалку , ако N1
Зошто „Јас сум подготвен да извршам гласачко ливче Б“ значи „Ветувам дека никогаш нема да полагам гласачки ливчиња помали од Б“? Бидејќи SCP го дефинира абортусот како спротивност на commit. Гласањето за подготовка на гласачко ливче вклучува и гласање за дисквалификување на некои други гласачки ливчиња и, како што разговаравме претходно, гласањето за една работа е ветување дека никогаш нема да се гласа против.
Пред да емитува заложба, јазолот мора прво да најде билтен што може да го потврди како подготвен. Со други зборови, врши федеративно гласање на тема „Подготвен сум да го положам гласачкото ливче Б“, веројатно на многу различни гласачки ливчиња, додека не најде едно кое прифаќа кворум.
Од каде доаѓаат гласачките ливчиња за да се подготви гласањето? Прво, јазолот емитува подготовки за гласање за <1,C>, каде што C е композитниот кандидат произведен во фазата на номинација. Сепак, дури и откако ќе започнат подготовките за гласање, номинациите може да резултираат со дополнителни кандидати кои изгледаат како нови гласачки ливчиња. Во меѓувреме, врсниците можат да имаат различни кандидати и тие можат да формираат блокада која прифаќа „Јас сум подготвен да го обврзам гласачкото ливче Б2“, што ќе го убеди и јазолот да го прифати. Конечно, постои механизам за тајмаут кој генерира нови кругови на федеративно гласање за нови гласачки ливчиња со поголемо пребројување доколку тековните гласачки ливчиња се заглавени.
Штом јазолот најде гласачко ливче Б што може да го потврди како подготвено, емитува нова порака „Посвети гласачко ливче Б“. Ова гласање им кажува на врсниците дека јазолот никогаш нема да се откаже од Б. Всушност, ако Б е гласачко ливче , потоа „Одложете гласачко ливче “ значи безусловна согласност да се гласа за подготвеноста на секое гласачко ливче од до <∞, s>. Оваа дополнителна вредност им помага на другите врсници да стигнат до врсниците за обврзување ако сè уште се во претходните фази на протоколот.
Во оваа фаза, вреди уште еднаш да се нагласи дека се работи за асинхрони протоколи. Само затоа што еден јазол испраќа гласови за заложба, не значи дека и неговите врсници го прават тоа. Некои од нив можеби сè уште гласаат за изјави во подготовка за гласање, други можеби веќе го имаат екстернализирано значењето. SCP објаснува како еден јазол треба да го обработува секој тип на peer порака без оглед на неговата фаза.
Доколку пораката „Најавив заложба » не може да се прими или потврди, односно веројатноста пораката да биде прифатена или потврдена или - или, во секој случај, кое било гласачко ливче со вредност C, а не кое било друго, бидејќи јазолот веќе вети дека никогаш нема да го откаже . До моментот кога јазолот ќе емитува гласови за заложба, ќе биде C или ништо, во зависност од тоа до каде оди консензусот. Сепак, ова сè уште не е доволно за јазолот да го екстернализира C. Некои византиски врсници (кои сочинуваат помалку од кворум, врз основа на нашите безбедносни претпоставки) може да го лажат јазолот. Прифаќањето и потоа потврдувањето на одредено гласачко ливче (или опсег на гласачки ливчиња) е она што му дава на јазолот доверба конечно да го екстернализира C.
Гласање на ДКС преку федеративно гласање. Не е прикажано: Тајмерот може да се исклучи во секое време, зголемувајќи го броењето на гласачкото ливче (и евентуално создавајќи нов состав од дополнителни номинирани кандидати).
И тоа е се! Откако мрежата ќе постигне консензус, таа е подготвена да го прави тоа повторно и повторно. На Stellar платежната мрежа, ова се случува приближно еднаш на секои 5 секунди: подвиг што бара и безбедност и опстанок гарантирани од SCP.
SCP може да го постигне ова со потпирање на повеќе кругови на федеративно гласање. Федерираното гласање е овозможено со концептот на парчиња кворум: множества од врсници на кои секој јазол одлучил да им верува како дел од својот (субјективен) кворум. Оваа конфигурација значи дека консензус може да се постигне дури и во мрежа со отворено членство и византиски измами.
Понатамошно читање
- Оригиналната бела хартија SCP може да се најде И нацрт-спецификации за нејзино спроведување.
- Оригиналниот автор на протоколот SCP, Дејвид Мазиер, го објаснува на поедноставен (но сепак технички) начин. .
- Можеби сте биле изненадени што не ги најдовте термините „рударство“ или „доказ за работа“ во оваа статија. SCP не ги користи овие методи, но некои други консензус алгоритми ги користат. Зејн Витерспун напиша достапно .
- едноставна мрежа која постигнува консензус во еден целосен круг на SCP.
- За читателите заинтересирани за имплементации на SCP: види , што се користи од мрежата за плаќање Stellar, или , што го напишав за подобро разбирање на SCP.
Извор: www.habr.com