Консенсусният протокол Stellar е описан за първи път през Дейвид Мейзиър през 2015 г. Това е „система на федерално византийско споразумение“, която позволява на децентрализирани изчислителни мрежи без лидери ефективно да постигнат консенсус по решение. Платежната мрежа Stellar използва Stellar Consensus Protocol (SCP), за да поддържа последователна история на транзакциите, която е видима за всички участници.
Консенсусните протоколи се считат за трудни за разбиране. SCP е по-прост от повечето от тях, но все още споделя тази репутация - отчасти поради погрешната идея, че "федеративното гласуване", което е предмет на първата половина на научната статия, е SCP. Но това не е вярно! Това е просто важен градивен елемент, който втората половина на статията използва за създаване действителен Консенсусен протокол Stellar.
В тази статия ще обясним накратко какво е „система от споразумения“, какво може да я направи „византийска“ и защо прави византийската система „федерална“. След това ще обясним процедурата за федеративно гласуване, описана в статията за SCP, и накрая ще обясним самия SCP протокол.
Споразуметелни системи
Система от споразумения позволява на група участници да постигнат консенсус по дадена тема, като например какво да поръчат за обяд.
В Interstellar въведохме собствена система за споразумения за хранене: ние поръчваме това, което нашият оперативен мениджър Джон казва. Това е проста и ефективна система за споразумение. Всички се доверяваме на Джон и вярваме, че всеки ден ще намира нещо интересно и питателно.
Но какво ще стане, ако Джон злоупотреби с нашето доверие? Той може еднолично да реши всички да станем вегани. След седмица-две сигурно ще го свалим и ще предадем властта на Елизабет. Но изведнъж тя обича авокадо с аншоа и смята, че всички трябва да бъдат такива. Властта развращава. Така че е по-добре да се намери някакъв по-демократичен метод: някакъв начин да се гарантира, че различните предпочитания са взети под внимание, като същевременно се гарантира навременен и недвусмислен резултат, така че никой да не поръчва обяд, или петима души да правят различни поръчки, или дискусия се проточва до вечерта.
Изглежда, че решението е просто: гласувайте! Но това е подвеждащо впечатление. Кой ще събира бюлетините и ще докладва резултатите? И защо другите трябва да вярват на това, което казва? Може би можем в началото гласувайте за лидер, на когото вярваме да води гласуването - но кой ще го води първи чрез гласуване? Ами ако не можем да се споразумеем за лидер? Или какво ще стане, ако постигнем споразумение, но този лидер заседне на среща или излезе в отпуск по болест?
Подобни проблеми възникват в разпределени компютърни мрежи. Всички участници или възли трябва да се споразумеят за някакво решение, като например чий ред е да актуализира споделен файл или да премахне задача от опашката за обработка. В мрежа за криптовалута възлите многократно трябва да избират как да изглежда пълната история от няколко възможни версии, които понякога са в конфликт. Това мрежово споразумение предоставя увереност на получателя, че монетата е (а) валидна (не е фалшива) и (б) все още не е изразходвана другаде. Това също гарантира, че той ще може да харчи монетите в бъдеще, защото новият получател ще има същите гаранции по същите причини.
Всяка консенсусна система в разпределена изчислителна мрежа трябва да е устойчива на грешки: тя трябва да произвежда последователни резултати въпреки грешки като бавни връзки, неотзивчиви възли и неправилно подреждане на съобщенията. византийски Системата за споразумение е допълнително устойчива на "византийски" грешки: възли, които дават невярна информация, независимо дали поради грешка или в умишлен опит да подкопаят системата или да получат някакво предимство. "Византийска" толерантност към грешки - способността да се доверяваш на групово решение, дори когато някои членове на групата може да лъжат или по друг начин да не следват правилата за вземане на решения - се нарича които се опитаха да координират атаката. при Антъни Стивънс.
Помислете за собственичката на крипто монети Алис, която трябва да избира между купуването на вкусен сладолед от Боб и изплащането на дълга на Карол. Може би Алис иска да плати и на двамата наведнъж, като изразходва измамно една и съща монета. За да направи това, тя трябва да убеди компютъра на Боб, че монетата никога не е била платена на Карол, и да убеди компютъра на Карол, че монетата никога не е била плащана на Боб. Византийската система от споразумения прави това практически невъзможно, използвайки форма на управление на мнозинството, наречена кворум. Възел в такава мрежа отказва да премине към определена версия на хронологията, докато не види, че достатъчен брой партньори - кворум - са съгласни с такъв преход. След като това се случи, те ще формират достатъчно голям блок за гласуване, за да принудят останалите мрежови възли да се съгласят с тяхното решение. Алис може да принуди някои възли да лъжат от нейно име, но ако мрежата е достатъчно голяма, нейният опит ще бъде победен от гласовете на честни възли.
Колко възли са необходими за кворум? Като минимум мнозинство или по-скоро квалифицирано мнозинство за борба с грешките и измамите. Но за да преброите мнозинството, трябва да знаете общия брой на участниците. В офиса на Interstellar или на районните избори тези числа са лесни за намиране. Но ако вашата група е слабо дефинирана мрежа, в която възлите могат да влизат и излизат по желание без одобрение от центъра, тогава имате нужда федерален византийска система за споразумение, способна да определя кворуми не от предварително определен списък от възли, а динамично, от постоянно променяща се и неизбежно непълна моментна снимка на възли в даден момент от време.
Може да изглежда невъзможно да се създаде кворум от гледна точка на единичен възел в обширна мрежа, но е възможно. Такъв кворум може дори да гарантира резултатите от децентрализираното гласуване. Бялата книга на SCP показва как да направите това с помощта на процедура, наречена чрез федерален вот.
За нетърпеливи
Останалата част от статията описва по-подробно федеративното гласуване и консенсусния протокол Stellar. Ако не се интересувате от подробности, ето общ преглед на процеса.
- Възлите провеждат кръгове на федерално гласуване за „номинирани“. Федерален кръг на гласуване означава:
- Възелът гласува за някакво изявление, например „Предлагам стойността на 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 съчетава много от тези кръгове, за да създаде пълна консенсусна система.
Stellar Consensus Protocol
Двете най-важни свойства на консенсусната система са − безопасност и оцеляване. Алгоритъмът за консенсус е „безопасен“, ако никога не може да даде различни резултати на различните участници (копието на историята на Боб никога няма да противоречи на Карол). „Живост“ означава, че алгоритъмът винаги ще дава резултат, тоест няма да блокира.
Описана федерална процедура за гласуване безвреден в смисъл, че ако възел потвърди стойността на V, никой друг възел няма да потвърди другата стойност. Но „няма да потвърди друго значение“ не означава, че непременно ще потвърди нещо. Участниците могат да гласуват за толкова много различни стойности, че нищо няма да достигне прага за приемане. Това означава, че при федерално гласуване няма оцеляване.
Консенсусният протокол Stellar използва федеративно гласуване по начин, който гарантира както сигурност, така и оцеляване. (Гаранциите за сигурност и оцеляване на SCP имат теоретично ограничение. Дизайнът избира много силна гаранция за сигурност, жертвайки малко смекчаване на оцеляването, но като се има предвид достатъчно време, е много вероятно да се постигне консенсус.) Накратко, идеята е да има множество обединени гласувания за множество стойности, докато една от тях премине през всички фази на гласуване на SCP, описани по-долу.
Стойностите, по които SCP търси консенсус, могат да бъдат история на транзакциите или поръчка за обяд или нещо друго, но е важно да се отбележи, че това не са стойностите, които са приети или потвърдени. Вместо това се провежда федерално гласуване според твърдения за тези ценности.
Първите кръгове на федералните избори се провеждат на етап на номиниране (фаза на номиниране), върху набор от твърдения като „Аз номинирам V“, може би за много различни стойности на V. Целта на номинацията е да се намерят едно или повече твърдения, които преминават през приемане и потвърждение.
След намиране на проверими кандидати, SCP преминава към фазата на гласуване, където целта е да се намери определен бюлетин (т.е. контейнер за предложената стойност) и кворум, който може да декларира ангажират за това (ангажирам се). Ако има кворум за гласуване, неговата стойност се приема като консенсус. Но преди даден възел да може да гласува за ангажимент за гласуване, той първо трябва да потвърди анулиране всички бюлетини с по-ниска насрещна стойност. Тези стъпки - анулиране на бюлетини, за да се намери такава, която може да бъде ангажирана - включват множество рундове на обединено гласуване на множество претенции за гласуване.
Следващите раздели описват по-подробно номинирането и гласуването.
Номинация
В началото на фазата на номиниране всеки възел може спонтанно да избере стойност за V и да гласува за изявлението „Аз номинирам V“. Целта на този етап е да се потвърди номинацията на някаква стойност чрез федерален вот.
Може би достатъчно възли гласуват за достатъчно различни предложения, така че нито една номинация да не може да достигне прага за приемане. Следователно, в допълнение към излъчването на собствените си номинационни гласове, възлите „отразяват“ номинациите на своите колеги. Ехо означава, че ако даден възел гласува за номинация V, но види съобщение от съсед, гласуващ за номинация W, той сега ще гласува и за V, и за W. (Не всички гласове на партньори се повтарят по време на номинация, защото това може да доведе до експлозия на различни номинирани. SCP включва механизъм за регулиране на тези гласувания. Накратко, има формула за определяне на "приоритета" на партньор от гледна точка на възел и се отразяват само гласовете на възли с висок приоритет. Колкото по-дълго е номинацията взема, толкова по-нисък е прагът, така че възелът разширява набор от партньори, чиито гласове ще отразява.Формулата за приоритет включва номера на слота като един от своите входове, така че партньор с висок приоритет за един слот може да бъде партньор с нисък приоритет за друг и обратно).
Концептуално, номинацията е паралелна, V и W са отделни федерални гласове, всеки поотделно способен да постигне приемане или потвърждение. На практика съобщенията на SCP протокол пакетират тези отделни гласове заедно.
Въпреки че гласуването за номинацията на V е обещание никога да не се гласува против номинацията на V, на ниво приложение - в този случай SCP - се определя какво означава "против". SCP не вижда изявление, което противоречи на гласуването „Аз номинирам X“, тоест няма съобщение „Аз съм против номинирането на X“, така че възелът може да гласува за номиниране на всякакви стойности. Много от тези номинации няма да стигнат до никъде, но в крайна сметка възелът ще може да приеме или потвърди една или повече стойности. След като кандидатът бъде потвърден, той става кандидат.
Номиниране на SCP чрез федерално гласуване. Може да има много стойности „B“, предложени от партньори и „отразени“ от възела.
Номинациите може да доведат до множество потвърдени кандидати. Следователно SCP изисква приложният слой да предостави някакъв метод за комбиниране на кандидатите в едно композитен (композитен). Методът на свързване може да бъде всякакъв. Основното е, че ако този метод е детерминиран, тогава всеки възел ще комбинира едни и същи кандидати. При система за гласуване на обяд „обединяването“ може просто да означава отхвърляне на един от двама кандидати. (Но по детерминистичен начин: всеки възел трябва да избере една и съща стойност за нулиране. Например по-ранната селекция по азбучен ред). В платежната мрежа Stellar, където се гласува историята на транзакциите, обединяването на два предложени кандидата включва обединяване на транзакциите, които те съдържат, и най-новия от техните два времеви клейма.
Бялата книга на SCP доказва (теорема 12), че до края на фазата на разширение мрежата в крайна сметка се сближава до единичен композит. Но има проблем: федеративното гласуване е асинхронен протокол (като SCP). С други думи, възлите не се координират по време, а само по съобщенията, които изпращат. От гледна точка на възела не е ясно кога приключи фаза на удължаване. И въпреки че всички възли в крайна сметка ще стигнат до един и същ композит, те могат да поемат по различни маршрути по пътя, създавайки различни композитни кандидати по пътя, и никога не могат да кажат кой е последният.
Но е нормално. Номинацията е само подготовка. Основното нещо е да се ограничи броят на кандидатите, за да се постигне консенсус, който се получава в процеса кандидатстване за длъжност (гласуване).
бягане
Бюлетин е двойка , където броячът е цяло число, което започва от 1, а стойността е кандидат от етапа на номиниране. Това може да бъде собствен кандидат на възел или кандидат на съседен възел, приет от този възел. Грубо казано, бюлетината включва повтарящи се опити да се принуди мрежата да постигне консенсус за някой кандидат в дадена бюлетина чрез провеждане на потенциално много обединени гласувания по изявления за гласуване. Броячите на бюлетините следят направените опити и бюлетините с по-висок брой имат предимство пред бюлетините с по-нисък брой. Ако бюлетинът засяда, започва ново гласуване, сега на гласуване .
Важно е да се прави разлика значение (например каква трябва да бъде поръчката за обяд: пица или салати), бюлетини (двойка насрещна стойност) и изявление относно бюлетините. Кръгът на SCP включва няколко кръга на федерално гласуване, по-специално относно следните твърдения:
- „Готов съм да дам бюлетина Б“ и
- „Обявявам включване на бюлетина Б“
От гледна точка на даден възел, консенсус се постига, когато той намери бюлетина B, за която може да потвърди (т.е. намери кворум, който приема) изявлението „Аз давам бюлетина B“. От този момент нататък е безопасно да действате спрямо стойността, посочена в B - например да направите тази поръчка за обяд. Нарича се екстернализация значения. След като приемането на бюлетината бъде потвърдено, даден възел може да бъде сигурен, че всеки друг възел е екстернализирал същата стойност или ще го направи в бъдеще.
Въпреки че концептуално много обединени гласувания се провеждат на основата на твърдения за много различни бюлетини, те не обменят толкова много съобщения, тъй като всяко съобщение капсулира определен брой бюлетини. По този начин едно съобщение популяризира състоянието на много федерални гласувания наведнъж, например: „Приемам бюлетини за ангажиране, вариращи от преди "
Какво означават термините „подготвен“ и „ангажиран“?
Възел гласува за извършване на бюлетина, когато е сигурен, че други възли няма да ангажират бюлетини с различни стойности. Убеждаването в това е целта на подготовката на приложението. Гласуване, което гласи „Готов съм да гласувам бюлетина B“, е обещание никога да не гласувам бюлетина, по-малка от B, т.е. с по-малък брой (SCP изисква стойностите в бюлетините да са в определен ред. По този начин, бюлетин по-малко , ако N1
Защо „Готов съм да дам бюлетина B“ означава „обещавам никога да не давам бюлетини, по-малки от B“? Тъй като SCP дефинира прекъсването като обратното на ангажирането. Гласуването за подготовка на бюлетина също включва гласуване за дисквалифициране на някои други бюлетини и, както обсъдихме по-рано, гласуването за едно нещо е обещание никога да не гласувате против него.
Преди да излъчи ангажимент, възелът трябва първо да намери бюлетин, който може да потвърди като подготвен. С други думи, той извършва обединено гласуване по темата „Готов съм да дам бюлетина Б“, вероятно на много различни бюлетини, докато намери такава, която приема кворум.
Откъде идват бюлетините за подготовка на вота? Първо, възелът излъчва подготовка за гласуване за <1,C>, където C е съставният кандидат, произведен на етапа на номиниране. Въпреки това, дори след началото на подготовката за гласуване, номинациите може да доведат до появата на нови кандидати като нови бюлетини. Междувременно партньорите могат да имат различни кандидати и могат да формират блокиращ набор, който приема „Готов съм да ангажирам бюлетина за B2“, което ще убеди възела също да го приеме. И накрая, има механизъм за изчакване, който генерира нови кръгове на обединено гласуване на нови бюлетини с по-висок брой, ако текущите бюлетини са блокирани.
Веднага след като възелът намери бюлетина B, която може да потвърди като подготвена, той излъчва ново съобщение „Извършете гласуване B.“ Това гласуване казва на партньорите, че възелът никога няма да се откаже от B. Всъщност, ако B е бюлетина , а след това „Извършете гласуване “ означава безусловно съгласие за гласуване за готовност на всяка бюлетина от до <∞, s>. Тази допълнителна стойност помага на други партньори да наваксат партньора на комит, ако все още са в по-ранни етапи на протокола.
На този етап си струва още веднъж да подчертаем, че това са асинхронни протоколи. Само защото един възел изпраща положителни гласове за ангажимент, не означава, че и неговите връстници го правят. Някои от тях може все още да гласуват изявления в подготовка за гласуване, други може вече да са екстернализирали смисъла. SCP обяснява как един възел трябва да обработва всеки тип партньорско съобщение, независимо от неговата фаза.
Ако съобщението „Обявих ангажимент » не може да бъде получено или потвърдено, т.е. вероятността съобщението да бъде прието или потвърдено или - или във всеки случай всяка бюлетина със стойност C, а не която и да е друга, тъй като възелът вече е обещал никога да не анулира . Докато даден възел излъчва гласове за ангажимент, той ще бъде C или нищо, в зависимост от това докъде стига консенсусът. Това обаче все още не е достатъчно, за да може възелът да екстернализира C. Някои византийски партньори (които съставляват по-малко от кворум, въз основа на нашите предположения за сигурност) може да излъжат възела. Приемането и след това потвърждаването на някои бюлетини (или набор от бюлетини) е това, което дава на възела увереността най-накрая да екстернализира C.
SCP гласуване чрез федерално гласуване. Не се показва: Таймерът може да изгасне по всяко време, увеличавайки броя на бюлетините (и евентуално създавайки нова комбинация от допълнителни номинирани кандидати).
И това е всичко! След като мрежата достигне консенсус, тя е готова да го прави отново и отново. В платежната мрежа Stellar това се случва приблизително веднъж на всеки 5 секунди: постижение, което изисква както сигурността, така и оцеляването, гарантирани от SCP.
SCP може да постигне това, като разчита на множество кръгове на федерално гласуване. Обединеното гласуване става възможно благодарение на концепцията за кворумни сегменти: набори от партньори, на които всеки възел е решил да се довери като част от своя (субективен) кворум. Тази конфигурация означава, че може да се постигне консенсус дори в мрежа с отворено членство и византийски измами.
Допълнителна информация
- Оригиналната бяла книга на SCP може да бъде намерена И проект на спецификации за изпълнението му.
- Първоначалният автор на SCP протокола, Дейвид Мазиер, го обяснява по опростен (но все пак технически) начин. .
- Може да сте се изненадали да не намерите термините „копаене“ или „доказателство за работа“ в тази статия. SCP не използва тези методи, но някои други консенсусни алгоритми го правят. Зейн Уидърспуун написа достъпно .
- проста мрежа, която достига консенсус в един пълен кръг на SCP.
- За читатели, които се интересуват от реализации на SCP: вижте , използвани от платежната мрежа Stellar, или , което написах за по-добро разбиране на SCP.
Източник: www.habr.com