Главная » Хабрахабр » [Перевод] Разбираемся в протоколе консенсуса Stellar

[Перевод] Разбираемся в протоколе консенсуса Stellar

Это «федеративная система византийского соглашения», которая позволяет децентрализованным вычислительным сетям без лидеров эффективно достигать консенсуса по какому-либо решению. Протокол консенсуса 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 пиров, можно предположить, что все f пиров (от которых узел не получил отклик) на самом деле честны. В системе из N узлов, спроектированной на выживание при f отказах (обманах), узел должен быть в состоянии добиться прогресса, получив отклик от N−f пиров, поскольку f из них, возможно, не функционируют. Чтобы узлы пришли к одному консенсусу, честным должно быть большинство из остальных узлов, то есть нам нужно, чтобы N−f было больше 2f или N > 3f. Таким образом, вредоносными являются f из N−f пиров (от которых получен ответ). Как только предложение переходит порог кворума, остальные члены сети убеждены, что любые конкурирующие предложения потерпят неудачу. Так что обычно система, рассчитанная на выживание при f сбоев, будет иметь в общей сложности N=3f+1 узлов и размер кворума 2f+1. Так сеть сходится к результату.

Если членство в системе открыто, то кто-то может получить большинство, просто проведя так называемую атаку Сивиллы: многократно присоединившись к сети через несколько узлов. Но в федеративной византийской системе соглашений не только не может быть большинства (потому что никто не знает общего размера сети), но концепция большинства вообще бесполезна! Так почему же транзитивное закрытие среза можно назвать кворумом, и как он способен подавлять конкурирующие предложения?

Представьте сеть из шести узлов, где две тройки изолированы в срезах кворума друг друга. Технически, никак! Для этой сети нет способа достичь консенсуса (кроме как случайно). Первая подгруппа может принять решение, о котором вторая никогда не услышит, и наоборот.

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


Если в сети есть пересечение кворумов…


… тогда любые два кворума, которые вы можете построить…


… всегда будут пересекаться.

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

Но есть две причины, почему это так. Может показаться неразумным ожидать, что в сети из независимых узлов возможно надёжное пересечением кворумов.

Интернет — идеальный пример сети независимых узлов с пересечением кворумов. Первая причина заключается в существовании самого интернета. Большинство узлов в интернете соединяются только с несколькими другими локальными узлами, но эти небольшие множества перекрываются достаточно, чтобы каждый узел был доступен из каждого другого узла по тому или иному маршруту.

У каждого актива в сети Stellar есть эмитент, а рекомендации Stellar требуют, чтобы каждый эмитент назначил один или несколько узлов в сети для обработки запросов на погашение. Вторая причина специфична для платёжной сети Stellar (наиболее распространённое применение SCP). Затем кворумы для всех узлов, заинтересованных в данном активе, будут перекрываться по крайней мере в этих узлах погашения. В ваших интересах прямо или косвенно включать эти узлы в срезы кворума для каждого интересующего вас актива. Кроме того, любые активы, которые не связаны таким образом с другими в сети, и не должны быть связаны — так задумано, чтобы для этой сети не было пересечения кворумов (например, банки из зоны доллара иногда хотят торговать с банками из зоны евро и банками из зоны песо, поэтому они находятся в одной сети, но никому из них нет дела до отдельной сети детей, торгующих бейсбольными картами). Узлы, заинтересованные в нескольких активах, будут включать в свои срезы кворума все узлы погашения соответствующих эмитентов, и они будут стремиться объединить все активы вместе.

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

В раунде федеративного голосования узел опционально начинает голосовать за какое-то значение V. Это означает трансляцию в сеть сообщения: «Я узел N, мои срезы кворумов Q, и я голосую за V». Когда узел голосует таким образом, он обещает, что никогда не голосовал против V и никогда не будет.

Как только узел соберёт достаточное количество таких сообщений, то может отследить срезы кворумов и попробовать найти кворумы. В трансляциях от одноранговых узлов каждый узел видит, как голосуют другие. Принятие обеспечивает более сильную гарантию, чем простое голосование. Если он видит кворум пиров, которые также голосуют за V, то может перейти к принятию V и транслировать это новое сообщение в сеть: «Я узел N, мои срезы кворума Q, и я принимаю V». Но если узел принимает V, ни один узел в Сети никогда не примет другой вариант (теорема 8 в техническом документе SCP доказывает это). Когда узел голосует за V, он никогда не может голосовать за другие варианты.

Другие узлы могут голосовать за другие значения. Конечно, высока вероятность, что сразу не найдётся кворум узлов, которые согласятся с V. N может принять другое значение W, даже если не голосовал за него, и даже если не видит для него кворума. Но для узла есть ещё один способ перейти от простого голосования к принятию. Блокирующее множество — это по одному узлу каждого из срезов кворумов N. Для решения изменить свой голос достаточно увидеть блокирующее множество узлов, принявших W. Если все узлы в таком множестве принимают W, то (по теореме 8) никогда не удастся сформировать кворум, принимающий иное значение, и поэтому для N также безопасно принять W. Как следует из названия, оно способно блокировать любое другое значение.


Узел N с тремя срезами кворумов.


B-D-F — блокирующее множество для N: оно включает по одному узлу каждого из срезов N.


B-E также является блокирующим множеством для N, потому что E появляется в двух срезах N.

Было бы слишком легко обмануть узел N, чтобы он принял нужное значение, если достаточно взломать всего один узел в каждом из срезов N. Но блокирующее множество — это не кворум. Вместо этого N должен подтвердить значение, то есть увидеть кворум узлов, принимающих его. Поэтому принятие значения — это ещё не конец голосования. Если он зайдёт так далеко, то, как доказывает технический документ SCP (в теореме 11), остальная часть сети также в конечном итоге подтвердит то же значение, поэтому N завершит федеративное голосование с определённым значением в качестве результата.


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

Протокол консенсуса Stellar объединяет много таких раундов для создания полной консенсусной системы. Процесс голосования, принятия и подтверждения составляет один полный раунд федеративного голосования.

Два самых важных свойства консенсусной системы — безопасность и живучесть. Консенсусный алгоритм «безопасен», если никогда не может дать разные результаты разным участникам (копия истории Боба никогда не будет противоречить Кэрол). «Живучесть» означает, что алгоритм всегда выдаст результат, то есть не застрянет.

Но «не подтвердит другое значение» — это не значит, что он обязательно что-то подтвердит. Описанная процедура федеративного голосования безопасна в том смысле, что если узел подтверждает значение V, ни один другой узел не подтвердит другое значение. Это означает, что в федеративном голосовании отсутствует живучесть. Участники могут голосовать за такое большое количество разных значений, что ничто не достигнет порога принятия.

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

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

Цель выдвижения — найти одно или несколько заявлений, которые пройти через принятие и подтверждение. Первые раунды федеративного голосования происходят на этапе выдвижения (nomination phase), на наборе заявлений типа «Я выдвигаю V», возможно, для многих различных значений V.

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

В следующих разделах более подробно описываются выдвижение и голосование.

В начале этапа выдвижения каждый узел может спонтанно выбрать значение V и проголосовать за утверждение «Я выдвигаю V». Цель на этом этапе — подтвердить выдвижение некоторого значения путём федеративного голосования.

Поэтому кроме трансляции собственных номинационных голосов, узлы «отражают» номинации своих пиров. Возможно, достаточное количество узлов голосует за достаточно разные утверждения, и никакое выдвижение не может достичь порога принятия. (Не все голоса пиров получают отражение во время выдвижения, потому что это может привести к взрыву разных номинантов. Отражение (echo) означает, что если узел голосует за выдвижение V, но видит сообщение от соседа, голосующего за выдвижение W, то теперь будет голосовать за выдвижение и V, и W. Короче говоря, существует формула для определения «приоритета» пира с точки зрения узла, и отражаются голоса только высокоприоритетных узлов. SCP включает механизм регулирования этих голосов. Формула приоритета в качестве одного из входных данных включает номер слота, поэтому высокоприоритетный одноранговый узел для одного слота может быть низкоприоритетным для другого, и наоборот). Чем дольше идёт выдвижение, тем ниже порог, поэтому узел расширяет набор пиров, чьи голоса он будет отражать.

На практике сообщения протокола SCP пакуют эти отдельные голоса вместе. Концептуально выдвижение параллельно и V, и W — это отдельные федеративные голоса, каждый отдельно способен достичь принятия или подтверждения.

SCP не видит утверждения, которое противоречит голосованию «Я выдвигаю X», то есть нет сообщения «Я против выдвижения X», поэтому узел может голосовать за выдвижение любых значений. Хотя голосование за выдвижение V — это обещание никогда не голосовать против выдвижения V, на уровне приложения — в данном случае SCP — определяется, что означает «против». Как только номинант подтверждён, он становится кандидатом. Многие из этих номинаций ни к чему не приведут, но в конечном итоге узел сможет принять или подтвердить одно или несколько значений.

Может быть много значений “B”, выдвинутых одноранговыми узлами и «отражённых» узлом.
Выдвижение SCP с использованием федеративного голосования.

Поэтому SCP требует, чтобы прикладной уровень предоставил какой-то метод объединения кандидатов в один композит (composite). Выдвижение кандидатов может привести к появлению нескольких подтверждаемых кандидатов. Главное, что если этот метод детерминирован, то каждый узел объединит одних и тех же кандидатов. Метод объединения может быть любым. (Но детерминированным образом: каждый узел должен выбрать одно и то же значение для сброса. В системе голосования за обед «объединение» может означать просто отказ от одного из двух кандидатов. В платёжной сети Stellar, где происходит голосование за историю транзакций, объединение двух предложенных номинантов предполагает объединение транзакций, которые они содержат, и последних из их двух временных меток. Например, более ранний выбор в алфавитном порядке).

Но есть проблема: федеративное голосование — это асинхронный протокол (как и SCP). Техническое описание SCP доказывает (теорема 12), что к окончанию фазы выдвижения сеть в конечном итоге сходится к одному композиту. С точки зрения узла неясно, когда завершилась фаза выдвижения. Другими словами, узлы не координируются по времени, а только по сообщениям, которые отправляют. И хотя все узлы в конечном итоге придут к одному и тому же композиту, они могут выбрать разные маршруты на этом пути, создавая по дороге разных составных кандидатов, и никогда не могут сказать, какой из них окончательный.

Выдвижение — лишь подготовка. Но это нормально. Главное ограничить число кандидатов для достижения консенсуса, который происходит в процессе баллотирования (balloting).

Бюллетень — это пара , где counter — целое число, которое начинается с 1, а value — кандидат из этапа выдвижения. Это может быть собственный кандидат узла или кандидат соседнего узла, принятый этим узлом. Грубо говоря, при баллотировании предпринимаются неоднократные попытки заставить сеть достичь консенсуса по какому-то кандидату в каком-то бюллетене путём проведения потенциально многих федеративных голосований по заявлениям о бюллетенях. Счётчики в бюллетенях отслеживают сделанные попытки, и бюллетени с более высокими счётчиками имеют приоритет над бюллетенями с более низкими счётчиками. Если бюллетень застревает, начинается новое голосование, теперь на бюллетене .

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

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

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

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

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

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

Потому, что SCP определяет abort как противоположность commit. Почему «Я готов к коммиту бюллетеня В» означает «Обещаю никогда не допускать коммит бюллетеней меньше В»? Голосование по подготовке бюллетеня подразумевает также голосование по отмене некоторых других бюллетеней, и, как мы обсуждали ранее, голосование за что-то одно — это обещание никогда не голосовать против него.

Другими словами, он проводит федеративное голосование на тему «Я готов к коммиту бюллетеня B», возможно, для многих различных бюллетеней, пока не найдёт тот, который принимает кворум. Прежде чем транслировать коммит, узел должен сначала найти бюллетень, который он может подтвердить как подготовленный.

Сначала узел транслирует подготовку к голосованию за <1,C>, где C — кандидат-композит, произведённый на этапе выдвижения. Откуда берутся бюллетени для подготовки голосования? Между тем, у пиров могут быть разные кандидаты, и они могут сформировать блокирующее множество, которое принимает «Я готов к коммиту бюллетеня B2», что убедит узел тоже его принять. Однако даже после начала подготовки к голосованию выдвижение может привести к появлению дополнительных кандидатов, которые станут новыми бюллетенями. Наконец, есть механизм таймаута, который генерирует новые раунды федеративного голосования на новых бюллетенях с более высокими счётчиками, если текущие бюллетени застряли.

Это голосование говорит пирам, что узел никогда не откажется от В. Как только узел находит бюллетень В, который может подтвердить как подготовленный, то транслирует новое сообщение «Коммит бюллетеня В». Это дополнительное значение помогает другим узлам догнать пира с коммитом, если они ещё находятся на более ранних этапах протокола. На самом деле, если В представляет собой бюллетень <N,C>, то «Коммит бюллетеня <N,C>» означает безоговорочное согласие голосовать за готовность каждого бюллетеня от <N,C> до <∞, с>.

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

К тому времени, когда узел транслирует голоса для коммита, это будет C или ничего, в зависимости от того, насколько далеко зайдёт консенсус. Если сообщение «Я объявляют коммит <N,C>» не может быть принято или подтверждено, то есть вероятность принятия или подтверждения сообщения <N+1, С> или <N+2, С> — или, во всяком случае, любого бюллетеня со значением С, а не любым другим, поскольку узел уже обещал никогда не отменять <N,C>. Некоторые византийские пиры (составляющие меньше кворума, основываясь на наших предположениях о безопасности) могут лгать узлу. Однако этого пока недостаточно узлу для экстернализации C. Принятие, а затем подтверждение некоторого бюллетеня (или диапазона бюллетеней) — вот что даёт узлу уверенность, наконец, экстернализировать C.

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

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

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

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

Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Из жизни с Kubernetes: Как HTTP-сервер испанцев не жаловал

Все приложения написаны на . Представитель нашего клиента, стек приложений которого обитает в облаке от Microsoft (Azure), обратился с проблемой: с недавнего времени часть запросов некоторых клиентов из Европы стала завершаться ошибкой 400 (Bad Request). NET, развёрнуты в Kubernetes… Этот ...

[Перевод] Умные часы с Бейсиком на физическом 6502

Процессор 6502 существует более 40 лет и до сих пор используется в ряде встроенных систем. Компания WDC продолжает выпускать 65C02 и периферийные микросхемы серии 65Cxx. Автор обнаружил, что теперь они доступны и в корпусах PLCC и QFP, но эти варианты ...