Practical Byzantine Fault Tolerance

Practical Byzantine Fault Tolerance (PBFT, Практическая византийская отказоустойчивость) — это алгоритм консенсуса, предназначенный для обеспечения надёжности работы распределённых систем в условиях, когда некоторые узлы могут вести себя некорректно или злонамеренно. PBFT является одним из первых эффективных решений так называемой «Византийской проблемы генералов» (Byzantine Generals Problem), позволяя достичь согласия между узлами даже при наличии до одной трети неисправных или вредоносных участников. Алгоритм был разработан Мигелем Кастро (Miguel Castro) и Барбарой Лисков (Barbara Liskov) в 1999 году и впервые представлен в работе «Practical Byzantine Fault Tolerance».

История

Предпосылки создания

До появления PBFT большинство алгоритмов консенсуса, способных противостоять византийским сбоям, были либо теоретическими, либо крайне неэффективными для практического применения. Классическая работа Лесли Лэмпорта, Роберта Шостака и Маршалла Пиза (1982) формализовала «Византийскую проблему генералов», но предложенные решения требовали экспоненциального числа сообщений. В 1990-х годах с развитием распределённых систем, особенно в финансовом секторе и системах хранения данных, возникла необходимость в алгоритме, который мог бы работать с приемлемой производительностью.

Разработка и публикация

В 1999 году Мигель Кастро и Барбара Лисков из Массачусетского технологического института (MIT) представили PBFT как практическое решение. Их алгоритм снижал сложность обмена сообщениями до полиномиальной (O(n²)), что делало его пригодным для использования в системах с десятками и сотнями узлов. Первоначальная реализация была протестирована на системе хранения данных с репликацией, что подтвердило её эффективность.

Влияние на блокчейн

В 2010-х годах PBFT стал основой для многих консенсусных механизмов в блокчейн-проектах, особенно в частных и консорциумных блокчейнах, таких как Hyperledger Fabric (до версии 2.0), Zilliqa и NEO. В отличие от Proof-of-Work (PoW), PBFT не требует энергоёмких вычислений, что делает его более экологичным и быстрым для закрытых сетей.

Принцип работы

Основные понятия

PBFT работает в модели, где все узлы делятся на три категории:

• Клиент — инициирует запрос на выполнение операции.
• Реплика (узел) — участвует в консенсусе. Одна реплика назначается первичной (primary) на текущий раунд, остальные — вторичными (backup).
• Злонамеренный узел — может вести себя произвольно: не отвечать, отправлять ложные сообщения, сговариваться с другими.

Алгоритм гарантирует безопасность (safety) и живость (liveness) при условии, что количество злонамеренных узлов \( f \) не превышает \( \lfloor (n-1)/3 \rfloor \), где \( n \) — общее число узлов. То есть для устойчивости к \( f \) сбоям требуется не менее \( 3f + 1 \) узлов.

Фазы консенсуса

PBFT состоит из трёх основных фаз, которые повторяются для каждого запроса:

1. Pre-prepare (предварительная подготовка):

• Клиент отправляет запрос первичному узлу.
• Первичный узел присваивает запросу номер последовательности и рассылает сообщение «pre-prepare» всем вторичным узлам.

1. Prepare (подготовка):

• Каждый вторичный узел, получив «pre-prepare», проверяет его корректность (например, номер последовательности не дублируется).
• Если сообщение корректно, узел рассылает всем остальным узлам сообщение «prepare».
• Узел переходит в состояние «prepared» после получения \( 2f \) подтверждений «prepare» от разных узлов (включая своё собственное).

1. Commit (подтверждение):

• После достижения состояния «prepared» каждый узел рассылает сообщение «commit».
• Узел фиксирует запрос после получения \( 2f+1 \) сообщений «commit» (включая своё). Это гарантирует, что все честные узлы согласны с порядком выполнения.

После завершения фазы commit узел выполняет запрос и отправляет ответ клиенту. Клиент принимает результат, если получает \( f+1 \) одинаковых ответов от разных узлов.

Смена первичного узла (view change)

Если первичный узел подозревается в неисправности (например, не отвечает в течение тайм-аута), инициируется процедура view change:

• Вторичные узлы рассылают сообщения «view-change» с указанием нового номера раунда.
• Новый первичный узел собирает \( 2f \) подтверждений и объявляет новый раунд.
• Процедура гарантирует, что система продолжит работу, даже если первичный узел был злонамеренным.

Характеристики

Преимущества

• Высокая скорость: PBFT не требует ресурсоёмких вычислений (как PoW) и завершается за несколько раундов обмена сообщениями. Время консенсуса составляет миллисекунды или секунды.
• Финализация: После подтверждения транзакция не может быть отменена (в отличие от блокчейнов с вероятностной финализацией, таких как Bitcoin).
• Энергоэффективность: Не требует майнинга или значительных вычислительных затрат.
• Устойчивость к византийским сбоям: Работает при наличии до 33% злонамеренных узлов.

Недостатки

• Масштабируемость: Сложность обмена сообщениями растёт квадратично (\( O(n^2) \)), что делает PBBT непригодным для сетей с тысячами узлов. Практический предел — около 100–200 узлов.
• Синхронность: Алгоритм предполагает, что задержки в сети ограничены (модель частичной синхронности). В полностью асинхронных сетях PBFT может не гарантировать живость.
• Централизация: В консорциумных сетях первичный узел может стать узким местом или мишенью для атак.
• Сложность реализации: Требует точной синхронизации часов и надёжной идентификации узлов.

Применение

Блокчейн и распределённые реестры

PBFT широко используется в консорциумных блокчейнах, где участники известны и доверяют друг другу частично:

• Hyperledger Fabric (до версии 2.0) использовал PBFT для консенсуса в каналах.
• Zilliqa — гибридный блокчейн, применяющий PBFT для финализации транзакций после обработки шардов.
• NEO — использует модифицированную версию PBFT (dBFT) для достижения консенсуса среди делегатов.
• Ripple — применяет алгоритм, основанный на идеях PBFT, но с открытым членством.

Системы хранения данных

PBFT применяется в распределённых базах данных и файловых системах, где требуется высокая надёжность:

• Google Chubby — система блокировок, использующая Paxos, но PBFT рассматривался как альтернатива для защиты от византийских сбоев.
• Apache Cassandra — в некоторых конфигурациях использует протоколы, вдохновлённые PBFT, для обеспечения согласованности.

Криптовалюты и DeFi

Некоторые криптовалюты, особенно ориентированные на скорость, используют PBFT в качестве механизма консенсуса:

• Stellar — использует Stellar Consensus Protocol (SCP), который является вариантом PBFT с открытым членством.
• Tendermint (основа Cosmos) — не является чистым PBFT, но заимствует его фазы и модель отказоустойчивости.

Модификации и производные

Practical Byzantine Fault Tolerance (PBFT) — классическая версия

Оригинальный алгоритм, описанный выше. Используется в небольших сетях (до 100 узлов).

Delegated Byzantine Fault Tolerance (dBFT)

Используется в NEO. Узлы выбирают делегатов (consensus nodes), которые выполняют PBFT. Это снижает число участников консенсуса, улучшая масштабируемость.

Federated Byzantine Agreement (FBA)

Используется в Stellar. Каждый узел выбирает набор доверенных узлов (quorum slice), и консенсус достигается на основе пересечения этих наборов. FBA не требует фиксированного числа узлов и может работать в открытых сетях.

HotStuff

Современный алгоритм, разработанный в 2018 году, который улучшает PBFT за счёт линейной сложности обмена сообщениями (\( O(n) \)) и упрощённой процедуры смены первичного узла. Используется в блокчейне Diem (ранее Libra) — проект Meta (организация признана экстремистской и запрещена в РФ).

Критика

Ограничения масштабируемости

Основная критика PBFT связана с его неспособностью работать в крупных сетях. При увеличении числа узлов до нескольких тысяч накладные расходы на обмен сообщениями становятся неприемлемыми. Это делает PBFT неподходящим для публичных блокчейнов с тысячами участников.

Уязвимость к сговору

В консорциумных сетях, где узлы контролируются различными организациями, существует риск сговора. Если злонамеренные узлы составляют более 33% от общего числа, алгоритм теряет гарантии безопасности.

Зависимость от синхронизации

В реальных интернет-сетях с непредсказуемыми задержками PBFT может требовать сложных механизмов синхронизации, что увеличивает сложность реализации.

Источники

1. Castro, M., & Liskov, B. (1999). «Practical Byzantine Fault Tolerance». Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI).
2. Lamport, L., Shostak, R., & Pease, M. (1982). «The Byzantine Generals Problem». ACM Transactions on Programming Languages and Systems.
3. Cachin, C., Guerraoui, R., & Rodrigues, L. (2011). «Introduction to Reliable and Secure Distributed Programming». Springer.
4. Hyperledger Fabric Documentation. «Consensus and PBFT» (архивная версия).
5. NEO White Paper. «Delegated Byzantine Fault Tolerance».