BFT-консенсус: PBFT и варианты

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

• **Hyperledger Fabric** - enterprise-блокчейн IBM, который в ранних версиях использовал PBFT для консенсуса между организациями-участниками (банки, логистика, здравоохранение)
• **Tendermint (Cosmos)** - BFT-движок, на котором построены 50+ блокчейнов (Cosmos Hub, Binance Chain, Terra). Каждый блок финален мгновенно - нет ожидания подтверждений
• **HotStuff (Diem/Libra)** - протокол Facebook/Meta для платёжной системы. Линейная complexity позволила масштабировать до сотен валидаторов. Сейчас используется в Aptos
• **Авиация и космос** - Boeing 787 и SpaceX Dragon используют BFT-подобные протоколы для согласования показаний между резервированными бортовыми компьютерами

Castro & Liskov: BFT выходит из лаборатории

В 1999 году аспирант Мигель Кастро и его научный руководитель Барбара Лисков из MIT опубликовали статью «Practical Byzantine Fault Tolerance». До этого BFT-протоколы существовали только в теории - они требовали экспоненциального числа сообщений. Кастро и Лисков показали, что BFT можно реализовать с полиномиальной сложностью O(n^2), что достаточно для десятков узлов. Лисков впоследствии получила премию Тьюринга (2008), и хотя основной вклад - это принцип подстановки Лисков (LSP), PBFT стал одной из самых цитируемых работ в distributed systems.

Предварительные знания

• The Consensus Problem: Why and How

Practical BFT: задача и решение

В 1982 году Лэмпорт, Шостак и Пиз формализовали **задачу византийских генералов**: как нескольким участникам прийти к единому решению, если некоторые из них могут лгать, молчать или отправлять противоречивые сообщения?

**Byzantine Fault** - самый сильный тип отказа: узел может вести себя произвольно злонамеренно. Это сложнее, чем crash fault (узел просто выключился).

Долгое время BFT-протоколы считались непрактичными из-за экспоненциальной сложности. В 1999 году **Мигель Кастро и Барбара Лисков** (MIT) опубликовали **PBFT** - первый BFT-протокол, пригодный для реальных систем.

Главное отличие PBFT от Nakamoto consensus (PoW/PoS): **детерминированная финальность**. Как только транзакция подтверждена - она подтверждена навсегда. Никаких «6 подтверждений для уверенности».

**Hyperledger Fabric** использовал PBFT-подобный консенсус в ранних версиях. Современные permissioned блокчейны (Hyperledger Sawtooth, Zilliqa) по-прежнему опираются на BFT-семейство.

Три фазы PBFT: Pre-Prepare, Prepare, Commit

PBFT работает в **трёх фазах**. Это минимум для достижения согласия при наличии византийских узлов. Меньше трёх фаз - и протокол уязвим.

Разберём каждую фазу:

1. **Pre-Prepare**: лидер (primary) получает запрос от клиента, назначает порядковый номер и рассылает `<PRE-PREPARE, v, n, d>` всем репликам. Реплики проверяют: корректен ли номер view, не был ли использован sequence number, совпадает ли digest.
2. **Prepare**: каждая реплика, принявшая pre-prepare, отправляет `<PREPARE, v, n, d, i>` всем остальным. Узел ждёт **2f** matching prepare-сообщений (плюс свой собственный). Это гарантия: большинство честных узлов согласны с порядком.
3. **Commit**: после получения 2f prepare-сообщений узел отправляет `<COMMIT, v, n, d, i>` всем. Ждёт **2f+1** commit-сообщений. После этого - выполняет операцию и отправляет результат клиенту.

**Почему нельзя обойтись двумя фазами?** Две фазы достаточно для crash fault (Paxos), но не для Byzantine fault. Без commit-фазы злонамеренный лидер может отправить разные pre-prepare разным репликам, и они не смогут это обнаружить до того, как примут решение.

**Кворум 2f+1** гарантирует пересечение кворумов. Любые два кворума размера 2f+1 из n=3f+1 узлов пересекаются как минимум в f+1 узлах. Из них хотя бы один - честный. Это и обеспечивает safety.

View Change: смена лидера

Что если лидер (primary) - злонамеренный? Он может задерживать запросы, отправлять противоречивые сообщения или просто упасть. PBFT решает это через механизм **view change** - смену лидера.

**View** - это номер текущей эпохи. В каждом view ровно один лидер: `primary = v mod n`, где v - номер view, n - количество узлов. При смене view лидер меняется детерминированно.

Как работает view change:

1. **Timeout**: реплика не получает ответ от лидера в течение заданного времени. Она подозревает лидера в отказе и отправляет `<VIEW-CHANGE, v+1, ...>` всем узлам.
2. **Сбор доказательств**: view-change сообщение содержит последний стабильный checkpoint и все prepared-сертификаты (proof, что сообщения прошли prepare-фазу). Это гарантирует, что новый лидер не потеряет уже согласованные запросы.
3. **Новый лидер**: узел, который является primary для view v+1, собирает 2f+1 корректных view-change сообщений и формирует `<NEW-VIEW, v+1, V, O>`, где V - set view-change сообщений, O - pre-prepare сообщения для незавершённых запросов.
4. **Возобновление**: все реплики проверяют корректность new-view сообщения, переключаются на view v+1 и продолжают обработку.

**Safety при смене view**: новый лидер обязан включить все запросы, которые уже были «prepared» в предыдущем view. Без этого смена лидера могла бы откатить уже согласованные транзакции.

**Защита от злонамеренного лидера**: если новый лидер тоже оказывается Byzantine, таймер сработает снова и произойдёт ещё одна смена view. Поскольку f < n/3, за не более чем f+1 смен view гарантированно будет выбран честный лидер.

**Exponential backoff**: каждый следующий таймер удваивается, чтобы избежать бесконечных view change. Но при этом вводится **catch-up** механизм: если 2f+1 узлов уже в новом view, отстающий узел подтягивается.

Communication Complexity и масштабирование BFT

PBFT решил задачу BFT для практических систем, но у него есть фундаментальный bottleneck - **количество сообщений растёт квадратично**.

Именно поэтому классический PBFT практически не используется при n > 20-30 узлов. Для блокчейнов с сотнями валидаторов (Ethereum: ~900,000 валидаторов) нужны другие подходы.

**Threshold signatures** - ключевая оптимизация. Вместо того чтобы каждый узел отправлял сообщение каждому, используется агрегация подписей:

Сравнение BFT-протоколов по поколениям:

**HotStuff** - прорыв 2018 года. Три ключевых улучшения: 1. линейная communication complexity через threshold signatures 2. pipelined фазы - каждый новый блок начинает prepare для себя и завершает commit предыдущего 3. простой view change (самая сложная часть PBFT) за O(n).

**Tradeoff**: снижение complexity до O(n) обычно требует доверия к лидеру на один раунд (optimistic) или использования криптографических примитивов (threshold signatures, BLS aggregation), которые вычислительно дороже простых подписей.

Ключевые идеи

• **PBFT** - первый практический BFT-протокол (1999). Выдерживает f < n/3 Byzantine-узлов и даёт **детерминированную финальность** - помните генералов из начала? Трёх раундов сообщений достаточно, чтобы армия действовала согласованно, даже если треть генералов - предатели
• **Три фазы** (pre-prepare → prepare → commit) с кворумом 2f+1 гарантируют и **safety** (не принимаем противоречивые решения), и **liveness** (система продвигается вперёд)
• **View change** - механизм смены злонамеренного или упавшего лидера. Prepared-сертификаты обеспечивают сохранность уже согласованных решений при смене view
• **O(n^2) сообщений** - фундаментальный bottleneck PBFT. Threshold signatures (BLS aggregation) снижают complexity до **O(n)**, что позволяет масштабировать BFT до сотен валидаторов
• **Эволюция**: PBFT (1999) → Tendermint (2014) → HotStuff (2018) → каждое поколение решало проблему предыдущего. От «работает на 4 узлах в лаборатории» до «работает на сотнях узлов в продакшене»

Связанные темы

PBFT - фундамент всего семейства BFT-консенсусов. Понимание трёх фаз и view change необходимо для изучения современных протоколов:

• Введение в консенсус — Базовые понятия: safety, liveness, fault tolerance. PBFT конкретизирует эти абстракции для Byzantine модели
• Tendermint — Прямой потомок PBFT: упрощённый view change, интеграция с PoS. Сохраняет O(n^2), но добавляет accountability (slashing)
• HotStuff — Следующее поколение: линейная complexity через threshold signatures, pipelined view change. Решил главную проблему PBFT

Вопросы для размышления

• Почему порог устойчивости BFT (f < n/3) строже, чем у Nakamoto consensus (f < n/2)? Что мы получаем взамен за эту «дороговизну»?
• Если все 3f+1 узлов - честные, PBFT всё равно требует три фазы. Можно ли оптимизировать протокол для «оптимистичного» случая, когда Byzantine-узлов нет? (подсказка: посмотрите на SBFT и fast path)
• Представьте, что вы проектируете консенсус для сети из 1000 узлов. PBFT не подходит из-за O(n^2). HotStuff снижает до O(n) через threshold signatures. Но threshold signatures - вычислительно дорогие. Какие ещё архитектурные решения могут помочь? (подсказка: committee selection, sharding валидаторов)

Связанные уроки

• bc-15-pos — PoS использует BFT как внутренний консенсус
• bc-05-consensus-intro — Введение в консенсус - обязательный контекст
• bc-17-nakamoto-vs-classical — Nakamoto vs BFT - следующий сравнительный урок
• bc-18-tendermint — Tendermint - практическая реализация BFT
• ds-03-consensus — Distributed consensus - математическая база BFT
• prob-02-combinatorics — 1/3 byzantine bound - комбинаторное доказательство
• dist-10-byzantine