Протоколът на консенсус 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). С други думи, възлите не са координирани по време, а само по съобщенията, които изпращат. От гледна точка на възела не е ясно кога приключи фаза на издигане. И макар че всички възли в крайна сметка ще достигнат до една и съща композиция, те могат да изберат различни маршрути по този път, създавайки различни съставни кандидати по пътя, и никога не могат да кажат кой от тях е окончателният.
Но това е нормално. Издигането е само подготовка. Основното е да се ограничи броят на кандидатите за постигане на консенсус, който настъпва в процеса на гласуването (balloting).
Гласуването
Бюлетината е двойка , където counter е цяло число, започващо от 1, а value е кандидат от етапа на издигане. Това може да бъде собствен кандидат на възела или кандидат на съседен възел, приет от този възел. Грубо казано, по време на гласуването се предприемат многократни опити мрежата да постигне консенсус по някакъв кандидат в някаква бюлетина, провеждайки потенциално много федерални гласувания по декларации за бюлетини. Счетоводителите в бюлетините проследяват направените опити, а бюлетини с по-високи счетоводи имат приоритет над бюлетини с по-ниски счетоводи. Ако бюлетина закъснее, започва ново гласуване, сега върху бюлетина .
Важно е да се различават стойности (например, какъв трябва да бъде поръчката за обяд: пица или салати), бюлетините (двойка counter-value) и изявленията за бюлетините. Кръгът SCP включва няколко кръга на федерално гласуване, в частност за такива декларации:
- "Готов съм да ангажирам бюлетина B" и
- "Обявявам ангажиране на бюлетина B"
От гледна точка на този възел консенсусът се постига, когато той намери бюлетина B, за която може да потвърди (тоест да намери кворум, който да я приеме) декларацията "Обявявам ангажиране на бюлетина B". От този момент нататък може безопасно да се действа според стойността, посочена в Б – например, да се направи тази поръчка за обяд. Това се нарича екстернализация на стойността. След като е потвърдено приемането на бюлетината, възелът може да е сигурен, че всеки друг възел е извършил екстернализация на тази съща стойност или задължително ще я извърши в бъдеще.
Въпреки че концептуално много федеративни гласувания се провеждат по заявления относно много различни бюлетини, те обменят не толкова много съобщения, тъй като всяко съобщение инкапсулира поредица от бюлетини. По този начин едно съобщение напредва състоянието на много федеративни гласувания едновременно, например: „Приемам комита на бюлетините в диапазона от до “.
Какво означават термините „подготвен“ (prepared) и „комит“ (commit)?
Възелът гласува за комита на бюлетина, когато е убеден, че другите възли няма да направят комит на бюлетини с други стойности. Убуждението в това е целта на подготовката на заявлението. Гласуването, в което се казва: „Готов съм за комита на бюлетин B“, е обещание никога да не извършвам комит на бюлетин с по-малка стойност от B, т.е. с по-нисък брояч (SCP изисква стойностите в бюлетините да имат определен ред. По този начин бюлетин е по-малък от , ако N1<N2, а също така, ако N1=N2 и V1<V2). Тези по-малки бюлетини „се отменят“ (aborted) по време на подготовителното гласуване, докато B се счита за „подготвен“.
Защо „Готов съм за комита на бюлетин В“ означава „Обещавам никога да не допускам комит на бюлетини по-малки от В“? Защото SCP определя abort като противоположност на commit. Гласуването за подготовката на бюлетина включва също гласуване за отмяна на някои други бюлетини, и, както обсъдихме по-рано, гласуването за нещо едно е обещание никога да не гласува против него.
Преди да излъчи комита, възелът първо трябва да намери бюлетината, която може да потвърди като подготвена. С други думи, той провежда федеративно гласуване на темата „Готов съм за комита на бюлетин B“, вероятно за много различни бюлетини, докато не намери такава, която приема кворум.
Откуда идват бюлетините за подготовка на гласуването? Първо, възелът предава подготовката за гласуване за <1,C>, където C е кандидат-композит, произведен на етапа на номинацията. Въпреки това, дори след началото на подготовката за гласуване, номинацията може да доведе до появата на допълнителни кандидати, които ще станат нови бюлетини. Междувременно, пирите могат да имат различни кандидати и те могат да образуват блокиращо множество, което приема „Готов съм за комит на бюлетин B2“, което ще убеди възела също да го приеме. Накрая, съществува механизъм за изчакване, който генерира нови кръгове на федеративно гласуване по нови бюлетини с по-високи броячи, ако текущите бюлетини са закъсали.
След като възелът намери бюлетин В, който може да потвърди като подготвен, той предава ново съобщение „Комит на бюлетин В“. Това гласуване казва на пирите, че възелът никога няма да се откаже от В. Всъщност, ако В представлява бюлетин <N,C>, то „Комит на бюлетин <N,C>“ означава безусловно съгласие да се гласува за готовността на всеки бюлетин от <N,C> до <∞, с>. Тази допълнителна стойност помага на другите възли да настигнат пира с комит, ако те все още са на по-ранни етапи на протокола.
На този етап е важно отново да се подчертае, че това са асинхронни протоколи. Само защото един възел изпраща гласове за комит, не означава, че неговите връстници също го правят. Някои от тях все още могат да гласуват по заявления за подготовка на гласуването, други вече може да са екстернализирали стойността. SCP обяснява как възелът трябва да обработва всеки тип еднопосочно съобщение независимо от неговата фаза.
Ако съобщението "Обявявам комит <N,C>" не може да бъде прието или потвърдено, тогава има вероятност да бъде прието или потвърдено съобщение <N+1, С> или <N+2, С> — или, в крайна сметка, всякакво бюлетин с стойност С, а не каквото и да било друго, тъй като възелът вече е обещал никога да не отменя <N,C>. В момента, когато възелът трансферира гласове за комита, това ще бъде C или нищо, в зависимост от това колко далеч ще стигне консенсусът. Въпреки това, това все още не е достатъчно за възела, за да екстернализира C. Някои византийски пиршества (съставляващи по-малко от кворума, основано на нашите предположения за сигурност) могат да излъжат възела. Приемането, а след това потвърдbling на някакво бюлетин (или диапазон бюлетини) — това е, което дава на възела увереност, най-накрая да екстернализира C.
Гласуване на SCP чрез федеративно гласуване. Не е показано: по всяко време таймерът може да се задейства, увеличавайки брояча в бюлетина (и, възможно, произвеждайки нов композит от допълнително издигнати кандидати).
И това е всичко! Веднъж когато мрежата е достигнала консенсус, тя е готова да го направи отново и отново. В платежната мрежа Stellar това се случва на всеки 5 секунди: постижение, което изисква и сигурност, и издръжливост, гарантирани от SCP.
SCP може да постигне това, опирайки се на няколко кръга на федеративно гласуване. Федеративното гласуване стана възможно благодарение на концепцията за квотомни срезове: набори от равноправни възли, на които всеки възел е решил да се доверява като част от своя (субективен) кворум. Тази конфигурация означава, че е възможно да се достигне до консенсус дори в мрежа с открито членство и византийски измами.
Допълнително четене
- Оригиналният технически документ на SCP може да бъде намерен , а проект за спецификации за неговото внедряване.
- Оригиналният автор на протокола SCP Дейвид Мазиер обяснява опростено (но все пак технически) неговото .
- Може би сте били изненадани, че не видяхте термини "майнинг" или "доказателство за работа" в тази статия. SCP не използва тези методи, но някои други алгоритми за консенсус ги използват. Зейн Уизърспун е написал достъпен .
- на проста мрежа, достигаща консенсус в хода на един пълен кръг на SCP.
- За читатели, заинтересовани от реализациите на SCP: вижте. , използван от платената мрежа Stellar, или , който написах за по-добро разбиране на SCP.
Източник: habr.com
