Протоколы BFT: PBFT и Tendermint

Проблема византийских генералов, сформулированная Лэмпортом, Шостаком и Пизом в 1982 году, ставит вопрос: может ли распределённая система достичь консенсуса, если некоторые участники отправляют противоречивые сообщения? Название связано с византийскими генералами, которые должны согласовать атаку, но среди которых могут быть предатели, отдающие противоречивые приказы. Система является отказоустойчивой к византийским сбоям (BFT), если достигает корректного консенсуса, несмотря на наличие до f вредоносных узлов среди 3f+1 узлов. BFT считается эталоном для консенсуса в блокчейнах, которым требуется безопасность в условиях действий злоумышленников.

PBFT, разработанный Кастро и Лисковым в 1999 году, стал первым практическим протоколом BFT и показал, что BFT может эффективно работать в реальных системах. PBFT работает в представлениях, или раундах, каждое из которых имеет назначенного первичного узла, то есть лидера. В обычном режиме используются три фазы: предварительная подготовка — первичный узел рассылает запрос клиента и порядковый номер; подготовка — реплики рассылают согласие с этим порядковым номером; фиксация — реплики рассылают подтверждение фиксации. Запрос выполняется после того, как реплика собирает 2f+1 совпадающих сообщений о фиксации. PBFT обеспечивает безопасность и живучесть, если менее 1/3 реплик являются византийскими.

Главное ограничение PBFT — сложность обмена сообщениями O(n^2) для каждого запроса: каждая из n реплик отправляет сообщения всем остальным на фазах подготовки и фиксации. Для n=100 реплик каждый запрос порождает примерно 10 000 сообщений. Поэтому PBFT непрактичен для больших наборов валидаторов. Сообщество исследователей BFT два десятилетия работало над улучшением этого показателя: BFT-SMART уменьшил константные множители, HotStuff достиг линейной сложности обмена сообщениями благодаря модели ретрансляции лидером, а Tendermint адаптировал идеи PBFT для использования в публичных блокчейнах.

Когда первичный узел PBFT считается неисправным из-за тайм-аута, реплики запускают смену представления. Каждая реплика рассылает сообщение о смене представления, содержащее её состояние — подготовленные значения из старого представления. Новый первичный узел собирает 2f+1 таких сообщений, формирует сообщение о новом представлении, подтверждающее согласованность перехода состояния с ранее зафиксированными значениями, и рассылает его. Смена представления требует большого числа сообщений — O(n^3) — и была практическим узким местом. Такие оптимизации, как сертификат смены представления в PBFT и конвейерная архитектура HotStuff, решают эту проблему.

Tendermint, созданный в 2014 году Квоном и запущенный в промышленной эксплуатации в Cosmos в 2019 году, адаптирует PBFT для публичных блокчейнов. В Tendermint для каждого блока предусмотрены три фазы: предложение — лидер рассылает предложенный блок; предварительное голосование — валидаторы голосуют за предложение; предварительная фиксация — валидаторы голосуют за фиксацию после получения двух третей предварительных голосов. Блок считается зафиксированным, когда валидатор собирает две трети голосов за предварительную фиксацию, то есть сертификат кворума. Валидаторы по очереди предлагают блоки в циклическом порядке с учётом доли. Если раунд завершается по тайм-ауту без фиксации, валидаторы переходят к следующему раунду с пустым голосом.

Tendermint обеспечивает строгую безопасность: зафиксированный блок является окончательным и не может быть отменён, пока менее трети доли не контролируется византийскими участниками. Это синхронная финализация — после фиксации разветвлений нет. Для живучести требуется частично синхронная сеть: протокол продолжает работу, как только задержки сообщений становятся ограниченными, но постоянная синхронность не нужна. Компромисс между живучестью и безопасностью фундаментален: Tendermint жертвует живучестью и может остановиться при разделении сети, чтобы гарантировать безопасность, тогда как такие цепочки, как Bitcoin, жертвуют безопасностью, допуская временные разветвления ради живучести.

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

Протокол межблочного взаимодействия Cosmos (IBC) опирается на мгновенную финализацию Tendermint при переводах между цепочками. Лёгкий клиент Tendermint отслеживает набор валидаторов и последнюю фиксацию — заголовок блока вместе с двумя третями подписей за предварительную фиксацию. Чтобы проверить пакет из цепочки A, модуль IBC цепочки B проверяет сертификат кворума: две трети валидаторов цепочки A должны подписать соответствующий заголовок блока. Поэтому безопасность IBC зависит от гарантии BFT Tendermint: перевод между цепочками становится окончательным сразу после фиксации исходного блока.

HotStuff, предложенный Yin и другими в 2018 году и ставший основой для LibraBFT и DiemBFT компании Facebook, а теперь используемый в Aptos и Sui, достигает сложности обмена сообщениями O(n) за раунд консенсуса благодаря звездообразной топологии: все валидаторы отправляют голоса лидеру, лидер объединяет их в пороговую подпись — QC, сертификат кворума — и рассылает QC. HotStuff использует трёхфазную цепочную архитектуру, в которой доказательства безопасности охватывают три последовательных QC, что позволяет применять конвейерную обработку. Линейная сложность делает HotStuff практичным для 100–300 валидаторов, как в сетях Aptos и Sui.

Корпоративные блокчейны, включая Hyperledger Fabric, Besu и Quorum, используют консенсус BFT в сетях с разрешённым доступом, где личности валидаторов известны. Служба упорядочивания Hyperledger Fabric на основе Raft обеспечивает отказоустойчивость к сбоям, но не к византийским действиям, в доверенных консорциумах. Запланированный этап развития Fabric предусматривает SmartBFT — реализацию в виде библиотеки. R3 Corda использует кластер нотариусов с BFT-SMART для предотвращения двойной траты. Выбор между CFT и BFT отражает предположения о доверии: BFT необходим, когда валидаторы могут действовать враждебно, а CFT достаточно, когда они лишь ненадёжны.

Чтобы понять BFT, необходимо знать, от каких атак он защищает систему, а от каких — нет. BFT обрабатывает случаи, когда валидаторы отправляют разным узлам противоречивые сообщения, а также случаи, когда валидаторы выходят из строя или замолкают. Он не защищает от атак Sybil: злоумышленник, который получает контроль над третью валидаторов, создавая поддельные личности, может нарушить безопасность. Поэтому публичные цепочки BFT используют взвешивание по доле в стейкинге: приобретение трети доли требует реальных денег и обеспечивает защиту от Sybil-атак. BFT также предполагает, что сообщения в конечном счёте будут доставлены, то есть работает в условиях частичной синхронности: разделение сети, длящееся дольше тайм-аута живучести, может остановить цепочку.

Какова максимальная доля византийских валидаторов в стандартном протоколе BFT, при которой сохраняется безопасность?

Протоколы BFT обеспечивают консенсус при наличии до трети вредоносных валидаторов. PBFT, созданный в 1999 году, доказал практичность BFT, но имеет сложность обмена сообщениями O(n^2). Tendermint адаптирует PBFT для блокчейнов, обеспечивая мгновенную финализацию и блокировку голосов. HotStuff достигает сложности O(n) с помощью сертификатов кворума QC на основе пороговых подписей и используется в Aptos и Sui. Cosmos IBC использует мгновенную финализацию Tendermint для проверенных переводов между цепочками. Корпоративные блокчейны используют BFT-SMART или Raft в зависимости от того, ожидаются ли византийские действия или только сбои.