Алгоритм консенсуса является сердцем любого блокчейна. Он обеспечивает фундаментальные гарантии безопасности, жизнеспособности и децентрализации, которые позволяют создавать приложения поверх него. В январе 2023 года Flow перешел на алгоритм консенсуса Jolteon. Это обновление приводит к более быстрому завершению блоков примерно на 33%, ускорению завершения транзакций на 20% и более быстрому обновлению сети. Это приводит к тому, что взаимодействие с пользователем подтверждается быстрее, а общая стабильность и доступность системы повышается.

Фон

С момента запуска Flow в 2020 году он использовал алгоритм консенсуса из семейства византийских отказоустойчивых (BFT) алгоритмов HotStuff[1]. HotStuff предоставляет множество полезных свойств в дополнение к основным требованиям алгоритма консенсуса:

Детерминированная завершенность. Блоки, помеченные алгоритмом как завершенные, гарантированно никогда не изменятся.
Оптимистичная отзывчивость. В счастливом пути алгоритм будет работать настолько быстро, насколько позволяет сеть, вместо того, чтобы ждать фиксированный период времени для каждого блока.
Конвейерное производство блоков — каждое новое предложение одновременно расширяет цепочку и помогает завершить предыдущий блок.

Протокол HotStuff состоит из серии раундов (часто называемых представлениями), в которых один узел является лидером и может предложить новый блок, расширив ранее предложенный блок. Для каждого последующего раунда выбирается новый лидер. (На следующих диаграммах узлы, отличные от лидера, называются репликами.) В счастливом пути квалифицированное большинство [2] комитета примет блок, проголосовав за него. Мы называем это успешным раундом.

Если блок не предлагается или набрано недостаточно голосов для достижения квалифицированного большинства, то мы считаем раунд несостоявшимся. Протокол повторит попытку с новым предложением в следующем раунде.

Особый интерес к последнему обновлению представляет компонент HotStuff под названием Pacemaker. Каждый узел поддерживает локальную переменную current_view, которая увеличивается при наблюдении успешных предложений для их текущего (или более высокого) представления или при указании Pacemaker. Pacemaker отвечает за то, чтобы отдельные узлы согласовывали текущее представление, чтобы они могли вместе продвигаться вперед.

Это особенно важно на неудачном пути протокола, чтобы восстановиться после автономного лидера или временных сетевых сбоев. Если бы в каждом раунде было успешное предложение, Пейсмейкера никогда бы не вызвали. Работа Pacemaker заключается в том, чтобы определить, когда переходить к следующему раунду, в случае отсутствия успешного предложения для текущего раунда.

Проблемы

До сих пор Flow использовал пассивный кардиостимулятор, который работает без обмена сообщениями с другими узлами. Он решает, следует ли пропустить текущее представление, основываясь на знании того, были ли успешными предыдущие представления, и функции тайм-аута с экспоненциальным увеличением. Это делает его относительно простым в реализации, но также ограничивает его эффективность, особенно в крайних случаях. Как мы увидим позже, это также имеет косвенные последствия для производительности, которые не сразу очевидны.

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

В этом случае их обычный процесс заключается в том, что следующий человек в очереди (Алиса) выберет ресторан. Интуитивно Боб позвонит Элис и Чарли, подтвердит, что они тоже ничего не слышали от Евы, затем согласится пропустить очередь Евы и позволить Алисе выбрать ресторан. Однако в более строгой схеме связи пассивного кардиостимулятора этот резервный вызов не допускается. Все, что может сделать Боб, это подождать достаточно долго, пока он не будет уверен, что Ева не позвонит.

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

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

В пределе эти сложные сетевые условия равносильны отказу системы.[3] К счастью, такие сценарии отказа случаются редко. Однако в течение более длительных периодов незапланированные отключения неизбежны, и их необходимо планировать. Подобные условия также могут возникать во время запланированных обновлений сети (называемых «sporks» для Flow[4]), поскольку разные операторы узлов подключают свои узлы к сети в разное время.

Когда возникают эти условия, сеть разбивается на группы, каждая из которых имеет менее чем квалифицированное большинство узлов, где разные группы имеют разные значения просмотра и времени ожидания. Поскольку мы требуем, чтобы подавляющее большинство узлов находились в одном и том же представлении, прогресс невозможен до тех пор, пока достаточное количество этих групп не сойдется в одном и том же представлении. Конвергенция занимает гораздо больше времени из-за отсутствия активного общения. Пассивный кардиостимулятор настроен так, что время ожидания узлов в более высоких представлениях будет медленнее, поэтому конвергенция в конечном итоге произойдет, но «в конечном итоге» может занять много времени. Когда группы различаются всего на 10 просмотров (у одной группы current_view=n, а у другой — current_view=n+10), время восстановления может возрасти до минут или даже часов.

Когда происходит расхождение представлений, время восстановления можно уменьшить, настроив представления и значения тайм-аута на разных когортах узлов, чтобы вручную увеличить скорость сходимости. Эта стратегия может работать, но это деликатный процесс. Это требует координации между различными операторами узлов и понимания механики пассивного кардиостимулятора. Неправильные настройки могут так же легко усугубить проблему и продлить простои (с чем мы столкнулись на собственном опыте!). Хотя это смягчение может помочь, восстановление системы, как правило, слишком ненадежно и непрактично долго.

Чтобы свести к минимуму риск расхождения взглядов во время sporks, операторы заранее договариваются о времени запуска и настраивают свои узлы для скоординированного запуска в это время. Это сработало хорошо, но приводит к дополнительным простоям процесса spork. Время запуска должно соответствовать времени наихудшего случая, чтобы все операторы были готовы к запуску. Если по какой-либо причине время запуска необходимо отодвинуть, это требует ручной координации и повторного согласования времени наихудшего случая.

Джолтеонский консенсусный протокол

Jolteon был первоначально опубликован в июне 2021 года группой исследователей блокчейна Meta, Novi, и академическими сотрудниками. Команда Meta (теперь называемая Diem) внедрила Jolteon и назвала его DiemBFT v4 , который впоследствии был переименован в AptosBFT без дальнейших модификаций. Концептуально Jolteon (DiemBFT, AptosBFT) принадлежит к семейству протоколов консенсуса HotStuff. Jolteon следует концепции конвейерной финализации блоков HotStuff, но добавляет два существенных улучшения.

Активный кардиостимулятор

Первым обновлением алгоритма Jolteon является введение активного кардиостимулятора. Active Pacemaker расширяет протокол, добавляя активный механизм восстановления для просмотров без успешного предложения. Когда время ожидания узла истекает, вместо того, чтобы немедленно перейти к следующему представлению, они сначала передают сообщение о тайм-ауте, включая информацию об их текущем представлении и последнем замеченном успешном предложении. Отдельные узлы не оставят ошибочное представление, пока не обнаружат сообщения о тайм-ауте от подавляющего большинства узлов.

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

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

Во время sporks узлы могут запускаться, как только они в состоянии. Сначала, когда супербольшинство еще не в сети, эти узлы не будут пропускать просмотры. Как только подавляющее большинство узлов подключатся к сети, сеть начнет дорабатывать блоки без ручной координации или ожидания конвергенции представлений. Точно так же на время любого возможного сбоя все честные узлы останутся в одном и том же представлении, даже если они не смогут завершить какие-либо блоки. Как только основная причина будет устранена, доработка может быть немедленно возобновлена. Это приводит к более коротким sporks, меньшим операционным накладным расходам и более быстрому восстановлению после непредвиденных сбоев.

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

Скорость финализации

Flow использует разновидность алгоритма консенсуса HotStuff, который обеспечивает детерминированную завершенность для блока после того, как в цепочку будет включено достаточное количество подтверждений этого блока. Когда блок завершен, это означает, что транзакции в нем безвозвратно приняты сетью[6], поэтому время, необходимое для завершения блока, напрямую связано с опытом пользователя в отношении того, сколько времени требуется для завершения его операций.

Поскольку HotStuff является конвейерным алгоритмом, каждое подтверждение предыдущего блока одновременно является вновь предлагаемым блоком, содержащим новые пользовательские транзакции. Это также означает, что каждое подтверждение блока занимает столько же времени, сколько предложение и голосование за новый блок. В основной сети это чуть больше секунды.

До этого момента консенсус Flow требовал 3 успешных подтверждения для завершения блока. С обновлением Jolteon завершение может быть достигнуто только после 2 подтверждений. Эта разница достижима благодаря внедрению активного кардиостимулятора. Добавление к протоколу явного сообщения о неудачных представлениях изменяет логику безопасности, позволяя отдельным узлам быстрее убеждаться в консенсусе по блоку.

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

Предложение Цезаря (0-цепочка)

На рассвете Цезарь отправляет всем армиям предложение атаковать в 8 часов вечера. Наша армия присылает ответ, что мы готовы атаковать в 8 часов вечера. На данный момент мы знаем только, что наша армия и Цезарь договорились о времени атаки. Мы не уверены, получили ли другие армии предложение Цезаря, или даже получил ли Цезарь наш ответ, поэтому для нас небезопасно совершать атаку.

Мы называем наши местные знания 0-цепочкой, потому что у нас есть предложение, но нет подтверждений для него.

1-е подтверждение (1-цепочка)

В полдень мы получаем второе сообщение от Цезаря, в котором говорится, что все армии подтвердили, что могут атаковать в 8 вечера. Мы отправляем ответ, подтверждающий это. На данный момент мы знаем, что Цезарь получил подтверждение на 8 вечера от всех остальных армий. Но что знают другие армии?

Если бы второе сообщение Цезаря не дошло до других армий, то эти армии оказались бы в том же положении, в котором мы были после получения только предложения, и сочли бы небезопасным предпринимать нападение. На данный момент мы знаем, что все армии сообщили, что они могут быть готовы к атаке в 20:00. Однако мы не уверены, знают ли об этом другие армии. Так что для нас все еще небезопасно совершать атаку.

Теперь мы называем наши локальные знания 1-цепочкой, потому что у нас есть предложение и один раунд подтверждений для предложения.

2-е подтверждение (2-цепочка)

Наконец, когда наступают сумерки и наши солдаты начинают беспокоиться, мы получаем третье сообщение от Цезаря, в котором говорится, что все армии признали его второе сообщение. На данный момент мы знаем, что все другие армии знают о римских действиях в 8 часов вечера. Это третье сообщение свидетельствует о намерении римлян атаковать.

Кажется, теперь мы можем атаковать, но что, если другая армия не получит третье сообщение Цезаря? Тогда у них будет то же знание, что и у нас в полдень, после получения второго сообщения. Фактически, после каждого полученного нами сообщения мы можем только знать, что все армии получили предыдущие сообщения. В худшем случае самое последнее сообщение может дойти только до нас.

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

Так что же нам делать? Один из вариантов для Цезаря — отправить еще одно сообщение, как только он получит еще один раунд подтверждений от всех армий. Это сообщение будет информировать нас о том, что все армии увидели доказательства консенсуса римлян, которые им необходимы для атаки. Это создаст 3-цепочку (3 последовательных подтверждения для предложения), что достаточно для завершения предложения без активной резервной связи.

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

Имея в нашем распоряжении эту возможность отступить к групповому общению, все, что нужно нашей армии для совершения атаки, — это знать, что доказательство согласия существует (2-цепочка). Будем надеяться, что последнее сообщение Цезаря, содержащее эти доказательства, дойдет до всех армий. Если это не удастся, мы сможем передать нашу копию улик другим армиям с помощью быстрой видеоконференции.

Заключение

Это обновление представляет собой значительный шаг вперед в эволюции Flow, позволяя использовать последние достижения в области исследования консенсуса в производственной среде. Active Pacemaker повышает надежность, способствуя более быстрому восстановлению после обновлений сети и снижая вероятность и влияние незапланированных отключений. Это, в свою очередь, включает правило финализации блоков с двумя цепочками, что приводит к ускорению финализации транзакций на 20%. Оба улучшения в конечном итоге обеспечивают более надежную платформу для пользователей и разработчиков приложений.

Спасибо Алексу Хентшелю, Джерому Пиммелю, Мише Рыбалову, Тараку Бен Юссефу и Юрию Олексишину за помощь в подготовке этого материала.

Примечания

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

[2] Подавляющее большинство формируется строго более чем 2/3 членов комитета. В частности, при выбранном «византийском пороге» f комитет должен иметь не менее 3f+1 узлов, а подавляющее большинство формируется из 2f+1 узлов. Например, комитет с 4 узлами может допустить не более 1 византийского узла; комитет со 100 узлами может допустить не более 33 византийских узлов.

[3] Например, предположим, что мы начинаем с тайм-аута в 2 секунды и сталкиваемся с серией из 11 последовательных офлайн-лидеров. После 10-го неудачного просмотра время ожидания узла консенсуса увеличится на 2 с * 2 ^ 10 = 2048 с. Следовательно, узел будет ждать 34 минуты только в представлении 11, прежде чем сдаться и перейти к представлению 12.

[4] Форк возникает, когда в блокчейн вносятся критические изменения — если некоторые узлы не были обновлены, они могут не согласиться с тем, что является допустимым расширением цепочки, и создать противоречивую версию истории после обновления. Ложка возникает, когда состояние приложения блокчейна используется для инициализации нового блокчейна, а не инициализации из пустого состояния. Мы используем термин «spork», потому что обновления сети в Flow сочетают в себе оба этих свойства, обеспечивая быстрое обновление как протокола (как узлы взаимодействуют друг с другом), так и среды выполнения (как выполняются транзакции и хранятся данные приложения).

[5] Это квалифицированное большинство представляет собой набор узлов, которые внесли свой вклад либо в голосование, либо в тайм-аут, используемый для завершения предыдущего раунда. Его участники могут меняться от раунда к раунду. Это влияет на безопасность различных византийских пороговых допущений. Наивысший возможный византийский порог составляет f византийских узлов с не менее чем 2f+1 честными узлами, но данная система может допускать или не допускать время от времени эти f узлов.

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