Протоколът за консенсус Stellar е описан за първи път в на Дейвид Мазиера през 2015 година. Това е "федеративна система на византийско споразумение", която позволява на децентрализирани изчислителни мрежи без лидери да постигат ефективен консенсус по всяко решение. Платежната мрежа Stellar използва Stellar Consensus Protocol (SCP) за поддържане на синхронизирана история на транзакциите, която виждат всички участници.
Счита се, че протоколите за консенсус са трудни за разбиране. SCP е по-прост от повечето от тях, но все пак дели тази репутация — отчасти заради погрешната представа, че "федеративното гласуване", на което е посветена първата половина на научната статия, е SCP. Но не е така! Това е само важен строителен блок, който във втората част на статията се използва за създаване на фактическия протокол за консенсус Stellar.
В тази статия накратко ще разкажем какво представлява "системата на споразуменията", какво може да я направи "византийска" и защо да направим византийската система "федеративна". След това ще обясним федеративната процедура на гласуване, описана в статията за SCP, и накрая ще обясним самия протокол SCP.
Системи на споразумения
Системата на споразумения позволява на група участници да достигнат до консенсус по определена тема, например какво да поръчат за обяд.
В компанията Interstellar внедрихме собствена система за обядни споразумения: поръчваме това, което казва нашият оперативен мениджър Джон. Това е проста и ефективна система на споразумения. Всички ние се доверяваме на Джон и вярваме, че всеки ден ще намери нещо интересно и питателно.
Но какво, ако Джон злоупотреби с нашето доверие? Той може да реши сам, че всички трябва да станем вегани. След една или две седмици, вероятно, ще го свалим и ще предадем властта на Елизабет. Но какво, ако тя обича авокадо с аншоа и мисли, че всички трябва да станат такива? Властта развращава. Затова е по-добре да намерим по-демократичен метод: начин, по който да се уверим, че са взети предвид различни предпочитания, както и да осигурим навременен и яснен резултат, за да не се случи така, че никой да не поръча обяд или петима човека да направят различни поръчки, или обсъждането да се протака до вечерта.
Като че ли решението е просто: да проведем гласуване! Но това е заблуждаващо впечатление. Кой ще събира бюлетините и ще съобщава резултатите? И защо останалите трябва да вярват в това, което той ще каже? Може би можем първо да гласуваме за лидер, на когото имаме доверие да ръководи гласуването — но кой ще ръководи това първи гласуване? Какво ще стане, ако не можем да се споразумеем за лидер? Или ако се споразумеем, а този лидер закъснее за среща или се разболее?
Подобни проблеми се срещат в разпределени компютърни мрежи. Всички участници или възли трябва да се съгласят на някакво решение, например, на чия ред е да обновява общия файл или да вземе задача от опашката за обработка. В криптовалутна мрежа възлите многократно трябва да избират коя версия на пълната история да приемат от няколко възможни версии, които понякога конфликтуват помежду си. Това мрежово съглашение дава гаранция на получателя, че монетата е (а) валидна (не е фалшива) и (б) не е била похарчена на друго място. Това също така гарантира, че той ще може да похарчи монетите в бъдеще, тъй като новият получател ще има същите гаранции по същите причини.
Всяка система на съгласие в разпределена изчислителна мрежа трябва да бъде устойчива на откази: тя трябва да дава последователни резултати, независимо от грешки, като бавни комуникационни линии, неотговарящи възли и неправилен ред на съобщенията. Византийска система на съгласията е допълнително устойчива на "византийски" грешки: възли, които предоставят неверни данни, независимо дали поради грешка или при преднамерен опит да подкопаят системата или да получат някакво предимство. "Византийската" устойчивост на откази е способността да се довери на групово решение, дори когато някои членове на групата могат да лъжат или по друг начин да не спазват правилата за вземане на решения — получи името си от , които се опитвали да координират атака. от Антъни Стивънс.
Нека разгледаме собственичката на криптовалутата Алиса, която трябва да избере между покупка на вкусно сладоледче от Боб и изплащане на дълга към Керъл. Възможно е Алиса да иска да плати на двамата наведнъж, измамвайки, че е похарчила същата монета. За целта тя трябва да убеди компютъра на Боб, че монетата никога не е била изплатена на Керъл, и да убеди компютъра на Керъл, че монетата никога не е била изплатена на Боб. Византийската система на споразумение прави това практически невъзможно, използвайки форма на правило на мнозинството, наречена кворум. Възел в такава мрежа отказва да премине към определена версия на историята, докато не види, че достатъчно количество равноправни възли — кворум — са съгласни на такова преминаване. След като това стане, те ще формират достатъчно голям избирателен блок, за да накарат останалите възли в мрежата да се съгласят с тяхното решение. Алиса може да накара някои възли да лъжат от нейно име, но ако мрежата е достатъчно голяма, опитът ѝ ще бъде потиснат от гласовете на честните възли.
Колко възли са необходими за кворум? Минимум, мнозинство, а точно, квалифицирано мнозинство за борба с грешки и измами. Но за да се преброи мнозинството, трябва да се знае общото количество участници. В офиса на Interstellar или на окръжни избори тези цифри лесно се узнават. Но ако вашата група е слабо дефинирана мрежа, в която възлите могат да влизат и излизат по желание без съгласие с централата, тогава е необходима федеративна система на византийско споразумение, способна да определя кворумите не от предварително определен списък на възли, а динамично, от постоянно променяща се и неизменно непълна снимка на възлите в определен момент.
Може да изглежда невъзможно да се създаде кворум от гледна точка на един възел в обширна мрежа, но това е възможно. Такъв кворум дори може да гарантира резултатите от децентрализирано гласуване. Техническият документ SCP показва как да се направи това с помощта на процедура, наречена федеративно гласуване.
За нетърпеливите
Останалата част от статията по-подробно описва федеративното гласуване и протокола за консенсус Stellar. Ако подробностите не ви интересуват, ето общ преглед на процеса.
- Възлите провеждат кръгове на федерално гласуване по „номинираните“. Кръгът на федералното гласуване означава:
- Възелът гласува за някакво утвърждение, например, „Предлагам стойност V“;
- Възелът изслушва гласовете на пирите, докато не намери такъв, който може да „приеме“;
- Възелът търси „кворум“ за това утвърждение. Кворумът „потвърджава“ номинирания.
- Щом възелът може да потвърди един или няколко номинирани, той се опитва да „подготви“ „бюлетина“ чрез няколко кръга на федерално гласуване.
- Щом възелът е в състояние да провери готовността на бюлетината, той се опитва да я закомитне чрез още повече кръгове на федерално гласуване.
- Щом възелът може да потвърди комита на бюлетината, той може да „екстернализира“ стойността на тази бюлетина, използвайки я като резултат от консенсуса.
Тези стъпки включват няколко кръга на федерално гласуване, които в съвкупност образуват един кръг SCP. Нека се занимаваме по-подробно, какво се случва на всяка стъпка.
Федерално гласуване
Федералното гласуване е процедура за определяне на това, дали мрежата може да съгласува предложение. В гласувания кръг, всеки възел трябва да избере едно от потенциално многото възможни стойности. Не може да го направи, докато не е сигурен, че другите възли в мрежата няма да изберат друг резултат. За да бъдат уверени в това, възлите обменят поток от съобщения насам и натам, така че всеки потвърди, което кворум възли приема същото решение. Останалата част от този раздел обяснява термините в това предложение и как се провежда цялата процедура.
Кворуми и срези на кворума
Нека започнем с определението на кворума. Както обсъдихме по-горе, в децентрализирана мрежа с динамично членство, е невъзможно предварително да се знае броят на възлите и следователно колко са нужни за мнозинство. Федералното гласуване решава този проблем, представяйки нова идея срез на кворума (quorum slice): малък набор от равноправни възли, на които възелът се доверява да предава информация за състоянието на гласуването на останалата част от мрежата. Всеки възел определя свой собствен срез на кворума (член на който става по фактическо положение).
Формирането на кворум започва с изрязването на кворума. За всеки възел се добавят възли от неговото изрязване. След това се добавят членовете на изрезите на тези възли и така нататък. С напредването попадаме на все повече възли, които не можете да добавите, тъй като вече са включени в изреза. Когато няма нови възли за добавяне, процесът спира: ние формирахме кворум чрез „транзитивно затваряне“ на изреза на началния възел.
За да намерите кворум от даден възел…
… добавяме членовете на неговия изрез…
… след това добавяме членовете на изрезите на тези възли.
Продължаваме, докато не останат възли за добавяне.
Няма останали възли за добавяне. Това е кворум.
Всъщност, всеки възел може да бъде част от повече от един изрез. За да формирате кворум, изберете само един от изрезите и добавете членове; след това изберете произволен изрез за всеки от членовете и добавете членове този изрез и така нататък. Това означава, че всеки възел е член на множеството от възможни кворуми.
Изберете само един изрез на кворума на всяка стъпка.
Един възможен кворум. Или алтернативен вариант…
… избираме други изрези…
…(когато е възможно)…
… създава друг кворум.
Как възелът разбира в какви изрези се състоят другите възли? По същия начин, по който получава друга информация за другите възли: от предавания, които всеки възел излъчва в мрежата, когато състоянието на гласуване се променя. Всяко предаване включва информация за изрезите на изпращащия възел. В техническия документ SCP няма указан механизъм за комуникация. Реализациите обикновено използват за гарантирано излъчване на съобщения из цялата мрежа.
Напомняме, че в нефедеративната византийска система за съгласие кворумът се определя като мнозинство от всички възли. Византийската система за съгласие е разработена с оглед на следния въпрос: колко нечестни възли може да понесе системата? В система с N възли, проектирана да оцелее при f откази (измами), възелът трябва да може да постигне напредък, получавайки отговори от N-f възли, тъй като f от тях може да не функционират. Но получавайки отговори от N-f възли, можем да предположим, че всички f възли (от които възелът не е получил отговор) всъщност са честни. Така, злонамерените са f от N-f възлите (от които е получен отговор). За да постигнат съгласие, честното мнозинство от останалите възли, т.е. трябва да накараме N-f да бъде по-голямо от 2f или N > 3f. Така че обикновено система, проектирана да оцелее при f откази, ще има общо N=3f+1 възли и размер на кворума 2f+1. След като предложението премине прага на кворума, останалите членове на мрежата са убедени, че всякакви конкуриращи се предложения ще се провалят. Така мрежата стига до резултата.
Но в федеративната византийска система за съгласие не само че не може да има мнозинство (тъй като никой не знае общия размер на мрежата), но концепцията за мнозинство изобщо е безполезна! Ако членството в системата е открито, то някой може да получи мнозинство, просто извършвайки така наречената атака на Сивилла: многократно присъединявайки се към мрежата чрез няколко възли. Така че защо транзитивното затваряне на среза може да бъде наречено кворум, и как може да потисне конкуриращите предложения?
Технически, по никакъв начин! Представете си мрежа от шест възли, където две тройки са изолирани в срезовете на кворума една от друга. Първата подгрупа може да вземе решение, за което втората никога няма да чуе и обратно. За тази мрежа няма начин да се постигне съгласие (освен случайно).
Затова SCP изисква, че за федеративно гласуване (и за прилагане на важни теореми на статията) мрежата трябва да притежава свойството, наречено пересичане на кворумите. В мрежата с това свойство всяка две кворуми, които могат да бъдат построени, винаги пресичат поне в един възел. За определяне на преобладаващите настроения в мрежата това е толкова добро, колкото да имаш мнозинство. Интуитивно това означава, че ако някаква кворум се съгласява с твърдението X, никой друг кворум никога не може да се съгласи с нещо друго, тъй като той задължително ще включва някакъв възел от първата кворум, който вече е гласувал за X.
Ако в мрежата има пресичане на кворуми…
… тогава всяка две кворуми, които можете да построите…
… винаги ще се пресичат.
(Разбира се, пресичащите се възли могат да се окажат византийски лъжци или лоши по други начини. В този случай пресечението на кворумите не помага на мрежата изобщо да постигне съгласие. Поради тази причина много от резултатите в техническия документ SCP се основават на явно изразени предположения, като например, че в мрежата остава пресечението на кворумите дори след премахването на лоши възли. За простота ще оставим тези предположения неизявени в останалата част на статията).
Може да изглежда неразумно да се очаква, че в мрежа от независими възли може да има надеждно пресичане на кворумите. Но има две причини, поради които това е така.
Първата причина е съществуването на самия интернет. Интернетът е идеален пример за мрежа от независими възли с пресичане на кворумите. Повечето възли в интернет се свързват само с няколко други локални възли, но тези малки множества се пресичат достатъчно, за да може всеки възел да бъде достъпен от всеки друг възел по някакъв маршрут.
Втората причина е специфична за платежната мрежа Stellar (най-разпространеното приложение на SCP). Всеки актив в мрежата Stellar има емитент, а препоръките на Stellar изискват всеки емитент да назначи един или повече възли в мрежата за обработка на заявки за обратно изкупуване. Във ваш интерес е да включите директно или индиректно тези възли в квотите за гласуване за всеки интересуващ ви актив. Следователно квотите за всички възли, заинтересовани от даден актив, ще се припокриват най-малко в тези възли за обратно изкупуване. Възлите, заинтересовани от няколко актива, ще включват в своите квоти за гласуване всички възли за обратно изкупуване на съответните емитенти и ще се опитат да обединят всички активи заедно. Освен това, всякакви активи, които не са свързани по този начин с други в мрежата, не трябва да бъдат свързани — това е направено, за да няма припокриване на квоти в тази мрежа (например, банките в доларовата зона понякога искат да търгуват с банки в еврото и с банки в песото, затова те са в една мрежа, но никой от тях не се интересува от индивидуалната мрежа на децата, търгуващи с бейзболни карти).
Разбира се, очакването на припокриване на квотите не е гаранция. Други византийски системи на споразумения дължат голяма част от сложността си на гаранцията на квотите. Важна иновация на SCP е, че той прехвърля отговорността за създаването на квоти от самия алгоритъм за консенсус на ниво приложение. По този начин, въпреки че федеративното гласуване е доста общо за гласуването по всякакви въпроси, всъщност надеждността му критично зависи от по-широкия смисъл на тези стойности. Някои хипотетични случаи на използване могат да се окажат не толкова удобни за създаване на добре свързани мрежи, колкото други.
Гласуване, приемане и потвърждаване
В кръгът на федеративното гласуване, възел опционално започва да гласува за някаква стойност V. Това означава разпространение в мрежата на съобщение: "Аз съм възел N, моите квоти за гласуване Q и гласувам за V". Когато възелът гласува по този начин, той обещава, че никога не е гласувал против V и никога няма да го направи.
В транслациите от еднопоетапни възли всеки възел вижда как гласуват другите. След като възелът събере достатъчно количество такива съобщения, може да следи срезовете на кворумите и да опита да намери кворумите. Ако види кворум от пирове, които също гласуват за V, може да премине към приемането на V и да транслира това ново съобщение в мрежата: «Аз съм възел N, моите срезове на кворума Q и приемам V». Приемането осигурява по-силна гаранция, отколкото просто гласуване. Когато възелът гласува за V, той никога не може да гласува за други опции. Но ако възелът приеме V, никой възел в Мрежата никога няма да приеме друга опция (теорема 8 в техническия документ SCP доказва това).
Разбира се, вероятността веднага да не се намери кворум от възли, които съгласуват с V, е висока. Други възли могат да гласуват за други стойности. Но за възела има още един начин да премине от просто гласуване към приемане. N може да приеме друга стойност W, дори ако не е гласувал за нея и дори ако не вижда кворум за нея. За да реши да промени своя глас, е достатъчно да види блокираща множестто възли, приели W. Блокиращата множестто е по един възел от всеки от срезовете на кворумите на N. Както подсказва името, тя е способна да блокира всяка друга стойност. Ако всички възли в такова множество приемат W, то (по теорема 8) никога няма да успеят да формират кворум, приемащ друга стойност, и затова N също е безопасно да приеме W.
Възел N с три среза на кворумите.
B-D-F е блокираща множестто за N: тя включва по един възел от всеки от срезовете на N.
B-E също е блокираща множестто за N, защото E се появява в два среза на N.
Но блокиращата множестто не е кворум. Беше бързо да се заблуди възел N да приеме необходимата стойност, ако е достатъчно да се хакне само един възел от всеки от срезовете на N. Затова приемането на стойност не е край на гласуването. Вместо това N трябва да потвърди стойността, тоест да види кворум от възли, които я приемат. Ако стигне дотам, както доказва техническият документ SCP (в теорема 11), остатъкът от мрежата също в крайна сметка ще потвърди същата стойност, така че N ще завърши федеративното гласуване с определена стойност като резултат.
Федеративно гласуване.
Процесът на гласуване, приемане и потвърждение представлява един пълен кръг на федеративното гласуване. Протоколът на консенсуса Stellar обединява множество такива кръгове, за да създаде пълна консенсусна система.
Протокол на консенсуса Stellar
Двете най-важни свойства на консенсусната система са сигурност и жизнестойкость. Консенсусният алгоритъм е "сигурен", ако никога не може да даде различни резултати на различни участници (историята на Боб никога не ще противоречи на Карол). "Жизнестойкость" означава, че алгоритъмът винаги ще предостави резултат, тоест няма да се закучи.
Описаната процедура на федеративното гласуване е сигурна в смисъл, че ако възел потвърди стойността V, няма да бъде потвърдена друга стойност от друг възел. Но "не потвърди друга стойност" не означава, че той непременно ще потвърди нещо. Участниците могат да гласуват за толкова много различни стойности, че нищо да не достигне прага за приемане. Това означава, че в федеративното гласуване няма жизнестойкость.
Протоколът на консенсуса Stellar използва федеративното гласуване, за да гарантира както сигурността, така и жизнестойкостта. (Гаранциите за сигурност и жизнестойкост на SCP имат теоретичен лимит. Конструкцията избира много силна гаранция за сигурност, като жертва малко отслабване на жизнестойкостта, но с достатъчен срок, консенсус с висока вероятност ще бъде постигнат). С две думи, идеята е да се проведат няколко федеративни гласувания за няколко стойности, докато една от тях не премине напълно през всички фази на гласуването SCP, описани по-долу.
Стойностите, по които SCP се стреми към консенсус, могат да бъдат история на транзакции или поръчка за обяд, или нещо друго, но е важно да се отбележи, че това не са стойностите, които се приемат или потвърдиха. Вместо това федеративното гласуване се провежда по изявления за тези стойности.
Първите кръгове на федеративното гласуване се провеждат на етапа на номиниране (фаза на номиниране), на набор от изявления от типа "Издигам V", възможно за много различни стойности V. Целта на номинирането е да се намерят едно или повече изявления, които да преминат през приемане и потвърждение.
След намирането на потвърдени кандидати, SCP преминава към етапа на гласуване, където целта е да се намери определен бюлетин (тоест контейнер за предложена стойност) и кворум, който може да обяви комит за него (commit). Ако кворумът извърши комит на бюлетина, неговата стойност се приема като консенсус. Но преди възелът да може да гласува за комита на бюлетина, той трябва първо да потвърди отмяната на всички бюлетини с по-ниска стойност на брояча. Тези стъпки — отмяна на бюлетини, за да се намери такъв, за който може да се потвърди комит — включват няколко кръга на федеративно гласуване по множество заявки за бюлетини.
В следващите раздели ще бъде описано по-подробно издигането и гласуването.
Издигане
В началото на етапа на издигане всеки възел може спонтанно да избере стойност V и да гласува за потвърждение "Издигам V". Целта на този етап е да се потвърди издигането на определена стойност чрез федеративно гласуване.
Възможно е достатъчно количество възли да гласува за достатъчно различни предложения, и никако издигане не може да достигне прага на приемане. Затова освен предаването на собствените номинационни гласове, възлите "отразяват" номинациите на своите съседи. Отражение (echo) означава, че ако възелът гласува за издигане V, но вижда съобщение от съсед, гласувал за издигане W, то сега ще гласува за издигане както на V, така и на W. (Не всички гласове на съседите получават отражение по време на издигане, защото това може да доведе до експлозия на различни номинации. SCP включва механизъм за регулиране на тези гласове. С други думи, съществува формула за определяне на "приоритета" на съседа от гледна точка на възела, и се отразяват гласовете само на високоприоритетни възли. Колкото по-дълго продължава издигането, толкова по-нисък е прага, така че възелът разширява набора от съседи, чиито гласове ще отразява. Формулата за приоритет, като едно от входните данни, включва номера на слота, така че високоприоритетен равностоен възел за един слот може да бъде нископриоритетен за друг и обратно.
Концептуално предложението на V и W паралелно е отделен федеративен глас, всеки способен самостоятелно да постигне приемане или потвърждение. На практика, съобщенията на протокола SCP опаковат тези отделни гласове заедно.
Въпреки че гласуването за предложението V е обещание никога да не гласуваш против предложението V, на ниво приложение – в този случай SCP – се определя какво означава "против". SCP не вижда твърдение, което противоречи на гласуването "Аз предлагам X", т.е. няма съобщение "Аз съм против предложението X", така че възелът може да гласува за предложението на каквито и да е стойности. Много от тези номинации вероятно няма да доведат до нищо, но в крайна сметка възелът ще може да приеме или потвърди една или повече стойности. След като номинираният бъде потвърден, той става кандидат.
Предложение на SCP с използване на федеративно гласуване. Могат да съществуват множество стойности “B”, предложени от равноправни възли и „отразени“ от възел.
Предложението на кандидати може да доведе до появата на няколко потвърдими кандидати. Затова SCP изисква приложният слой да предостави метод за обединение на кандидатите в един композит (composite). Методът на обединение може да бъде всякакъв. Важно е, че ако този метод е детерминиран, всеки възел ще обедини едни и същи кандидати. В система за гласуване за обяд, „обединението“ може просто да означава отказ от един от двата кандидата. (Но по детерминиран начин: всеки възел трябва да избере една и съща стойност за анулиране. Например, по-ранен избор по азбучен ред). В платежната мрежа Stellar, където се провежда гласуване за история на транзакции, обединението на двама предложени кандидати предполага обединение на транзакциите, които те съдържат, и последните от техните две времеви марки.
Техническото описание на SCP доказва (теорема 12), че към края на фазата на предложението мрежата в крайна сметка сходства към един композит. Но има проблем: федералното гласуване е асинхронен протокол (както и SCP). С други думи, възлите не координират времето си, а само съобщенията, които изпращат. От гледна точка на възела не е ясно кога е приключила фаза на издигане. И макар че всички възли в крайна сметка ще достигнат до един и същ състав, те могат да избират различни маршрути по този път, създавайки различни кандидати по пътя, и никога не могат да кажат кой от тях е окончателен.
Но това е нормално. Издигането е само подготовка. Важно е да се ограничи броят на кандидатите за постигане на консенсус, който се случва в процеса на гласуване (гласуване).
Гласуването
Бюлетинът е двойка , където counter е цяло число, което започва от 1, а value е кандидатът от етапа на издигане. Това може да бъде собствен кандидат на възела или кандидат на съседен възел, приет от този възел. Грубо казано, по време на гласуването се предприемат многократни опити да се достигне консенсус в мрежата относно определен кандидат в определен бюлетин, като се провеждат потенциално много федеративни гласувания по заявления за бюлетини. Счетоводителите в бюлетините следят направените опити и бюлетините с по-високи счетоводители имат приоритет пред бюлетините с по-ниски счетоводители. Ако бюлетинът се блокира, започва ново гласуване, сега на бюлетина .
Важно е да се различават значения (например, какъв трябва да бъде поръчката за обяд: пица или салати), бюлетини (пара counter-value) и заявления за бюлетини. Кръгът SCP включва няколко кръга на федеративно гласуване, по-специално, по следните заявления:
- „Готов съм да се ангажирам с бюлетина B“ и
- „Обявявам ангажимента на бюлетина B“
От гледна точка на този възел консенсусът се постига, когато той намери бюлетин B, за който може да потвърди (т.е. да намери кворум, приемащ) заявлението „Обявявам ангажимента на бюлетина B“. От този момент нататък може безопасно да се действа по стойността, посочена в B – например, да се направи тази поръчка за обяд. Това се нарича екстернализация на стойността. След като е потвърдено приемането на бюлетина, възелът може да бъде сигурен, че всеки друг възел е направил екстернализация на същата стойност или задължително ще я направи в бъдеще.
Въпреки че концептуално много федеративни гласувания се провеждат по заявления за много различни бюлетини, те не обменят толкова много съобщения, защото всяко съобщение инкапсулира набор от бюлетини. Едно съобщение, следователно, напредва състоянието на много федеративни гласувания наведнъж, например: «Приемам комита на бюлетини в диапазона от до ».
Какво означават термините «подготвен» (prepared) и «комит» (commit)?
Възелът гласува за комит на бюлетина, когато е убеден, че другите възли няма да направят комит на бюлетини с различни стойности. Убедителността в това е целта на подготовката на заявлението. Гласуването, в което се казва: «Готов съм за комит на бюлетин B», е обещание никога да не се прави комит на бюлетин по-малък от B, т.е. с по-нисък брояч (SCP изисква стойностите в бюлетините да имат определен ред. Следователно, бюлетин е по-малък от , ако N1<N2, а също така ако N1=N2 и V1<V2). Тези по-малки бюлетини се «отхвърлят» (aborted) по време на подготовката на гласуването, докато B се счита за «подготвен».
Защо «Готов съм за комит на бюлетин В» означава «Обещавам никога да не допускам комит на бюлетини по-малки от В»? Защото SCP определя abort като противоположност на commit. Гласуването за подготовка на бюлетин предполага също гласуване за отмяна на някои други бюлетини, и, както обсъждахме по-рано, гласуването за нещо едно е обещание никога да не гласуваш против него.
Преди да излъчи комит, възелът първо трябва да намери бюлетин, който може да потвърди като подготвен. С други думи, той провежда федеративно гласуване на темата «Готов съм за комит на бюлетин B», възможно за много различни бюлетини, докато не намери този, който приема кворум.
Откъде идват бюлетините за подготовка на гласуването? Първо, възелът предава подготовката за гласуване за , където C е кандидат-композит, създаден по време на издигането. Въпреки това, дори след началото на подготовката за гласуване, издигането може да доведе до появата на допълнителни кандидати, които ще представляват нови бюлетини. Междувременно, пирите могат да имат различни кандидати, и те могат да оформят блокиращ набор, който приема „Готов съм да комитна бюлетина B2“, което ще убеди възела да я приеме и него. Накрая, съществува механизъм за таймаут, който генерира нови рундове на федеративно гласуване с нови бюлетини с по-високи броячи, ако текущите бюлетини са забили.
След като възелът намери бюлетина В, която може да потвърди като подготвена, той предава ново съобщение „Комит на бюлетина В“. Това гласуване казва на пирите, че възелът никога няма да се откаже от В. Всъщност, ако В представлява бюлетина , то „Комит на бюлетина “ означава безусловно съгласие да се гласува за готовността на всеки бюлетин от до . Това допълнително значение помага на други възли да настигнат пира с комита, ако все още са на по-ранни етапи на протокола.
На този етап е важно да подчертаем, че това са асинхронни протоколи. Само защото един възел изпраща гласове за комит, не означава, че неговите събратя също го правят. Някои от тях все още могат да гласуват по заявления за подготовка за гласуване, други вече може би са екстернализирали стойността. SCP обяснява как възелът трябва да обработва всеки тип еднорангово съобщение независимо от неговата фаза.
Ако съобщението „Обявявам ангажимент <N,C>“ не може да бъде прието или потвърдено, тогава има вероятност да бъде прието или потвърдено съобщение <N+1,C> или <N+2,C> — или, във всеки случай, всяко бюлетин със стойност C, а не с друга, тъй като възелът вече е обещал никога да не отмени <N,C>. До момента, в който възелът предава гласове за ангажимента, това ще бъде C или нищо, в зависимост от това колко напред ще стигне консенсуса. Обаче, това все още не е достатъчно за възела, за да екстернализира C. Някои византийски пиршества (съставляващи по-малко от кворума, на основание нашите предположения за сигурност) могат да лъжат възела. Приемането и след това потвърждаването на някое бюлетин (или диапазон от бюлетини) е това, което дава на възела увереност, накрая, да екстернализира C.
Гласуване на SCP чрез федеративно гласуване. Не е показано: по всяко време може да се активира таймер, увеличаващ брояча в бюлетина (и, възможно, да произведе нов композит от допълнително предложени кандидати).
И това е всичко! След като мрежата достигне консенсус, е готова да го прави отново и отново. В платежната мрежа Stellar това се случва приблизително на всеки 5 секунди: подвиг, който изисква както безопасност, така и устойчивост, гарантирани от SCP.
SCP може да постигне това, разчитайки на няколко кръга на федеративно гласуване. Федеративното гласуване стана възможно благодарение на концепцията за срезове на кворума: набори от равноправни възли, на които всеки възел е решил да вярва като част от своя (субективен) кворум. Тази конфигурация означава, че е възможно да се достигне консенсус дори в мрежа с открито членство и византийски измами.
Допълнителна литература
- Оригиналният технически документ на SCP можете да намерите , а проект на спецификациите за неговото внедряване.
- Оригиналният автор на протокола SCP Дейвид Мазиер опростено (но все пак технически) обяснява неговата .
- Може би сте били изненадани, че не сте намерили в тази статия термините „майнинг“ или „доказателство за работа“. SCP не използва тези методи, но някои други алгоритми за консенсус ги използват. Зейн Уизърспун е написал достъпен .
- на проста мрежа, достигаща консенсус в рамките на един пълен кръг на SCP.
- За читателите, интересуващи се от реализации на SCP: вижте , използвана от платежната мрежа Stellar, или , който написах за по-добро разбиране на SCP.
Източник: habr.com
