Протокол консенсуса Stellar впервые описан в научной статье Дэвида Мазьера в 2015 году. Это «федеративная система византийского соглашения», которая позволяет децентрализованным вычислительным сетям без лидеров эффективно достигать консенсуса по какому-либо решению. Платёжная сеть Stellar использует Stellar Consensus Protocol (SCP) для ведения согласованной истории транзакций, которую видят все участники.

Считается, что протоколы консенсуса трудны для понимания. SCP проще большинства из них, но всё же разделяет эту репутацию — отчасти из-за ошибочной идеи о том, что «федеративное голосование», которому посвящена первая половина научной статьи, является SCP. Но это не так! Это лишь важный строительный блок, который во второй половине статье используется для создания фактического протокола консенсуса Stellar.

В этой статье вкратце расскажем, что такое «система соглашений», что может сделать её «византийской» и зачем делать византийскую систему «федеративной». Затем объясним федеративную процедуру голосования, описанную в статье по SCP, и, наконец, объясним сам протокол SCP.

Системы соглашений

Система соглашений позволяет группе участников прийти к консенсусу на какую-то тему, например, что заказать на обед.

Мы в компании Interstellar внедрили собственную систему обеденного соглашения: заказываем то, что говорит наш операционный менеджер Джон. Это простая и эффективная система соглашений. Мы все доверяем Джону и верим, что он каждый день найдёт что-то интересное и питательное.

Но что, если Джон злоупотребит нашим доверием? Он может единолично решить, что мы все должны стать веганами. Через неделю или две, вероятно, мы свергнем его и передадим полномочия Элизабет. Но вдруг она любит авокадо с анчоусами и думает, что все должны стать такими. Власть развращает. Поэтому лучше найти некий более демократичный метод: какой-то способ убедиться, что учтены разные предпочтения, при этом обеспечен своевременный и однозначный результат, чтобы не получилось так, что никто не закажет обед или пятеро человек разместят разные заказы, или обсуждение затянется до вечера.

Казалось бы, решение простое: провести голосование! Но это обманчивое впечатление. Кто будет собирать бюллетени и сообщать о результатах? И почему остальные должны верить тому, что он скажет? Возможно, мы можем сначала проголосовать за лидера, которому доверяем руководить голосованием — но кто будет руководить этим первым голосованием? Что если мы не сможем договориться о лидере? Или если договоримся, а этот лидер застрянет на встрече или уйдёт на больничный?

Похожие проблемы встречаются в распределённых компьютерных сетях. Все участники или узлы должны согласовать какое-то решение, например, чья очередь обновлять общий файл или забирать задачу из очереди обработки. В криптовалютной сети узлам неоднократно приходится выбирать, как выглядит полная история, из нескольких возможных версий, которые иногда конфликтуют. Это сетевое соглашение даёт гарантию получателю, что монета является (а) действительной (не поддельной) и (б) ещё не потраченной в другом месте. Это также гарантирует, что он сможет потратить монеты в будущем, потому что у нового получателя будут те же гарантии по тем же причинам.

Любая система согласования в распределённой вычислительной сети должна быть отказоустойчивой: она должна давать последовательные результаты, несмотря на ошибки, такие как медленные линии связи, не реагирующие узлы и неправильный порядок сообщений. Византийская система соглашений дополнительно устойчива к «византийским» ошибкам: узлам, которые дают ложную информацию, будь то из-за ошибки или в преднамеренной попытке подорвать систему или получить некое преимущество. «Византийская» отказоустойчивость — способность доверять групповому решению, даже когда некоторые члены группы могут лгать или иным образом не следовать правилам принятия решений — получила название по притче о генералах Византийской империи, которые пытались скоординировать атаку. Хорошее описание у Энтони Стивенса.

Рассмотрим владельца криптомонеты Алису, которая должна выбрать между покупкой вкусного мороженого у Боба и оплатой долга Кэрол. Возможно, Алиса хочет заплатить обоим сразу, мошеннически потратив одну и ту же монету. Для этого она должна убедить компьютер Боба, что монета никогда не была выплачена Кэрол, и убедить компьютер Кэрол, что монета никогда не была выплачена Бобу. Византийская система соглашений делает это фактически невозможным, используя форму правила большинства, называемую кворумом. Узел в такой сети отказывается от перехода к определённой версии истории, пока не увидит, что достаточное количество одноранговых узлов — кворум — согласны на такой переход. Как только это произойдёт, они сформируют достаточно большой избирательный блок, чтобы заставить оставшиеся узлы сети согласиться с их решением. Алиса может заставить некоторые узлы лгать от её имени, но если сеть достаточно велика, то её попытка будет подавлена голосами честных узлов.

Сколько узлов требуется для кворума? Как минимум, большинство, а точнее, квалифицированное большинство для борьбы с ошибками и мошенничеством. Но чтобы подсчитать большинство, нужно знать общее количество участников. В офисе Interstellar или на окружных выборах эти цифры легко узнать. Но если ваша группа — это слабо определённая сеть, в которую узлы могут входить и выходить по желанию без согласования с центром, тогда нужна федеративная система византийского соглашения, способная определять кворумы не из заранее определённого списка узлов, а динамически, из постоянно меняющегося и неизбежно неполного снимка узлов в определённый момент времени.

Может показаться невозможным создать кворум с точки зрения одного узла в обширной сети, но это возможно. Такой кворум может даже гарантировать результаты децентрализованного голосования. Технический документ SCP показывает, как это сделать с помощью процедуры, называемой федеративным голосованием.

Для нетерпеливых

Остальная часть статьи более детально описывает федеративное голосование и протокол консенсуса Stellar. Если вам не интересны подробности, вот общий обзор процесса.

1. Узлы проводят раунды федерального голосования по «номинантам». Раунд федеративного голосования означает:
   • Узел голосует за какое-либо утверждение, например, «Я предлагаю значение V»;
   • Узел слушает голоса пиров, пока не найдёт тот, который может «принять»;
   • Узел ищет «кворум» для этого утверждения. Кворум «подтверждает» номинанта.
2. Как только узел может подтвердить одного или нескольких номинантов, он пытается «подготовить» «бюллетень» через несколько раундов федеративного голосования.
3. Как только узел способен проверить готовность бюллетеня, он пытается закоммитить его с помощью ещё большего количества раундов федеративного голосования.
4. Как только узел может подтвердить коммит бюллетеня, он может «экстернализировать» ценность этого бюллетеня, используя его в качестве результата консенсуса.

Эти шаги включают несколько раундов федеративного голосования, которые в совокупности образуют один раунд SCP. Разберёмся подробнее, что происходит на каждом шаге.

Федеративное голосование

Федеративное голосование — это процедура определения того, может ли сеть согласовать предложение. В раунде голосования каждый узел должен выбрать одно из потенциально многих возможных значений. Он не может этого сделать, пока не будет уверен, что другие узлы в сети не выберут другой результат. Чтобы быть уверенными в этом, узлы обмениваются шквалом сообщений туда и обратно, чтобы каждый подтвердил, что кворум узлов принимает одно и то же решение. Остальная часть этого раздела объясняет термины в этом предложении и как происходит вся процедура.

Кворумы и срезы кворума

Начнём с определения кворума. Как мы обсуждали выше, в децентрализованной сети с динамическим членством невозможно заранее знать количество узлов и, следовательно, сколько нужно для большинства. Федеративное голосование решает эту проблему, представляя новую идею среза кворума (quorum slice): небольшой набор одноранговых узлов, которым узел доверяет передачу информации о состоянии голосования в остальной части сети. Каждый узел определяет собственный срез кворума (членом которого становится по факту).

Формирование кворума начинается со среза кворума. Для каждого узла добавляются узлы его среза. Затем добавляются члены срезов этих узлов и так далее. По мере продолжения попадается всё больше узлов, которые вы не можете добавить, потому что они уже включены в срез. Когда больше нет новых узлов для добавления, процесс прекращается: мы сформировали кворум путём «транзитивного закрытия» (transitive closure) среза кворума начального узла.

Чтобы найти кворум из данного узла…

… добавляем членов его среза…

… затем добавляем членов срезов этих узлов.

Продолжаем, пока не останется узлов для добавления.

Узлов для добавления не осталось. Это кворум.

На самом деле, каждый узел может входить более чем в один срез. Чтобы сформировать кворум, выберите только один из срезов и добавьте членов; затем выберите любой срез для каждого из членов и добавьте членов этого среза и так далее. Это означает, что каждый узел является членом множества возможных кворумов.

Выберите только один срез кворума на каждом шаге.

Один возможный кворум. Или альтернативный вариант…

… выбираем другие срезы…

…(когда это возможно)…

… создаёт другой кворум.

Как узел узнаёт, в каких срезах состоят другие узлы? Точно так же, как прочую информацию о других узлах: из передач, которые каждый узел транслирует в сеть, когда изменяется его состояние голосования. Каждая трансляция включает в себя сведения о срезах отправляющего узла. В техническом документе SCP не указан механизм коммуникации. Реализации обычно используют протокол gossip для гарантированной трансляции сообщений по всей сети.

Напомним, что в нефедеративной византийской системе соглашений кворум определяется как большинство всех узлов. Византийская система соглашений разработана с точки зрения вопроса: сколько нечестных узлов способна вынести система? В системе из 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 стремится к консенсусу, могут быть историей транзакций или заказом на обед, или чем-то ещё, но важно отметить, что это не те значения, которые принимаются или подтверждаются. Вместо этого федеративное голосование происходит по заявлениям об этих значениях.

Первые раунды федеративного голосования происходят на этапе выдвижения (nomination phase), на наборе заявлений типа «Я выдвигаю 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,value>, где counter — целое число, которое начинается с 1, а value — кандидат из этапа выдвижения. Это может быть собственный кандидат узла или кандидат соседнего узла, принятый этим узлом. Грубо говоря, при баллотировании предпринимаются неоднократные попытки заставить сеть достичь консенсуса по какому-то кандидату в каком-то бюллетене путём проведения потенциально многих федеративных голосований по заявлениям о бюллетенях. Счётчики в бюллетенях отслеживают сделанные попытки, и бюллетени с более высокими счётчиками имеют приоритет над бюллетенями с более низкими счётчиками. Если бюллетень <counter, value> застревает, начинается новое голосование, теперь на бюллетене <counter+1, value>.

Важно различать значения (например, каким должен быть заказ на обед: пицца или салаты), бюллетени (пара counter-value) и заявления о бюллетенях. Раунд SCP включает в себя несколько раундов федеративного голосования, в частности, по таким заявлениям:

• «Я готов к коммиту бюллетеня B» и
• «Я объявляю коммит бюллетеня B»

С точки зрения данного узла консенсус достигается, когда он находит бюллетень B, для которого может подтвердить (то есть найти кворум, принимающий) заявление «Я объявляю коммит бюллетеня B». С этого момента можно безопасно действовать по значению, указанному в В — например, разместить этот заказ на обед. Это называется экстернализацией значения. Как только подтверждено принятие бюллетеня, узел может быть уверен, что любой другой узел совершил экстернализацию этого же значения или обязательно совершит её будущем.

Хотя концептуально многие федеративные голосования проводятся по заявлениям о многих различных бюллетенях, они обмениваются не таким большим количеством сообщений, потому что каждое сообщение инкапсулирует ряд бюллетеней. Одно сообщение, таким образом, продвигает состояние сразу многих федеративных голосований, например: «Я принимаю коммит бюллетеней в диапазоне от <min,V> до <max,V>».

Что означает термины «подготовлен» (prepared) и «коммит» (commit)?

Узел голосует за коммит бюллетеня, когда он убеждён, что другие узлы не сделают коммит бюллетеней с другими значениями. Убеждение в этом является целью подготовки заявления. Голосование, в котором говорится: «Я готов к коммиту бюллетеня B», — это обещание никогда не совершать коммит бюллетеня меньше, чем B, т. е. с меньшим счётчиком (SCP требует, чтобы значения в бюллетенях имели определённый порядок. Таким образом, бюллетень <N1,V1> меньше <N2,V2>, если 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. Некоторые византийские пиры (составляющие меньше кворума, основываясь на наших предположениях о безопасности) могут лгать узлу. Принятие, а затем подтверждение некоторого бюллетеня (или диапазона бюллетеней) — вот что даёт узлу уверенность, наконец, экстернализировать C.

Баллотирование SCP через федеративное голосование. Не показано: в любой момент может сработать таймер, увеличив счётчик в бюллетене (и, возможно, произвести новый композит из дополнительных выдвинутых кандидатов).

И это всё! Как только сеть пришла к консенсусу, она готова делать это снова и снова. В платёжной сети Stellar это происходит примерно раз в 5 секунд: подвиг, который требует как безопасности, так и живучести, гарантированных SCP.

SCP может добиться этого, опираясь на несколько раундов федеративного голосования. Федеративное голосование стало возможным благодаря концепции срезов кворума: наборов одноранговых узлов, которым каждый узел решил доверять как части своего (субъективного) кворума. Эта конфигурация означает, что можно прийти к консенсусу даже в сети с открытым членством и византийскими обманами.

Дальнейшее чтение

• Оригинальный технический документ SCP можно найти здесь, а тут проект спецификаций для его внедрения.
• Оригинальный автор протокола SCP Дэвид Мазьер упрощённо (но всё же технически) объясняет его здесь.
• Возможно, вы были удивлены, не найдя в этой статье терминов «майнинг» или «доказательство работы». SCP не использует эти методы, но некоторые другие алгоритмы консенсуса используют. Зейн Уизерспун написал доступный обзор алгоритмов консенсуса.
• Пошаговое описание простой сети, достигающей консенсуса в ходе одного полного раунда SCP.
• Для читателей, заинтересованных в реализациях SCP: см. код C++, используемый платёжной сетью Stellar, или код Go, который я написал для лучшего понимания SCP.

Источник: habr.com