Византийская отказоустойчивость

Цели урока

• Понимать разницу между Byzantine и crash faults и почему Raft/Paxos не защищают от первых
• Знать теорему 3f+1 и уметь вычислить нужное число узлов
• Понимать три фазы PBFT и зачем каждая из них нужна
• Знать где применяется BFT на практике и когда он избыточен

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

• Принципы работы Raft/Paxos (crash fault tolerance)
• Понятие кворума и majority voting
• Базовое понимание криптографических подписей

Ethereum DAO hack 2016: 60 млн долларов украдено не через взлом сети, а через Byzantine поведение контракта - узлы делали именно то, что написано в коде, но результат был катастрофическим. Paxos/Raft бессильны когда узлы врут.

• **Bitcoin (PoW)** - вероятностный BFT для публичной сети без доверия: 51% честных узлов гарантируют консенсус
• **Hyperledger Fabric** - PBFT для межбанковских расчётов где участники - конкуренты
• **Boeing 777** - triple-modular redundancy для защиты от radiation-induced bit flips (hardware Byzantine)
• **SpaceX Falcon 9** - 3 Flight Management Computers с Byzantine-tolerant voting
• **Facebook Diem/Libra** - HotStuff BFT как основа LibraBFT с O(N) view change

Лэмпорт и задача предателей

В 1982 году Лэмпорт, Шостак и Пиз опубликовали статью «Byzantine Generals Problem» - название придумал Лэмпорт как аналогию для труднообъяснимой проблемы. До этого проблему называли «Interactive Consistency Problem», что звучало менее запоминающе. Статья оказалась настолько влиятельной, что термин «Byzantine fault» вошёл в стандартный словарь distributed systems и используется в официальных авиационных стандартах DO-178C.

Задача византийских генералов

**Июнь 2016. Ethereum DAO смарт-контракт держит 150 млн долларов. Атакующий находит уязвимость и рекурсивно вызывает withdraw 1800 раз подряд - каждый раз получая 50 ETH до того как баланс обнуляется. Украдено 60 млн долларов.** Это не баг сети - узлы Ethereum корректно выполнили код. Это Byzantine fault на уровне логики: узел делал именно то, что написано, но намеренно деструктивно.

Лэмпорт, Шостак и Пиз в 1982 году формализовали эту проблему через военную метафору. N генералов осаждают город и должны договориться: АТАКОВАТЬ или ОТСТУПИТЬ. Общение - только через гонцов. Часть генералов - предатели, которые активно мешают консенсусу.

**Byzantine fault** - узел ведёт себя произвольно: врёт о полученных сообщениях, отправляет разные данные разным получателям, сговаривается с другими предателями. Принципиальное отличие от crash fault: молчащий узел - предсказуем, лгущий - нет.

**Paxos/Raft не защищают от Byzantine faults.** Оба алгоритма предполагают модель crash-stop: узел либо работает корректно, либо молчит. Один злонамеренный узел может сломать Raft-кластер: он может отвечать разным репликам разными данными и нарушить инвариант.

Проблема генералов иллюстрирует суть: при трёх генералах и одном предателе честные не могут достичь консенсуса. Если командующий-предатель посылает генералу A приказ АТАКА, а генералу B - ОТСТУПЛЕНИЕ, то A и B видят конфликт, но не знают кто из них получил ложный приказ.

Теорема 3f+1: минимум узлов для Byzantine consensus

**Фундаментальный результат Лэмпорта, Шостака и Пиза (1982):** для достижения Byzantine consensus при наличии f злонамеренных узлов необходимо минимум 3f+1 узлов суммарно. Это математически доказанная нижняя граница - обойти её невозможно без дополнительных допущений.

**Интуиция за 3f+1:** при f Byzantine-узлах и f молчащих узлах (имитируют crash) остаётся f+1 честных голосов. Кворум составляет 2f+1. Из них как минимум f+1 - честные. Этого достаточно чтобы перевесить f предателей. Итого: f (Byzantine) + f (молчащие) + f+1 (честные) = 3f+1.

Почему 3 узла недостаточно для f=1: предположим командующий - предатель. Он посылает генералу G1 приказ АТАКА, генералу G2 - ОТСТУПЛЕНИЕ. G1 и G2 обмениваются сообщениями. G1 говорит G2: «я получил АТАКА». G2 говорит G1: «я получил ОТСТУПЛЕНИЕ». Оба видят конфликт, но оба утверждения одинаково достоверны - нет способа определить кто из трёх (Commander, G1, G2) является предателем.

При 4 узлах (3f+1 при f=1) аналогичный сценарий разрешается: кворум из 3 узлов будет содержать не менее 2 честных. Два честных узла согласуются между собой, перевешивая одного предателя.

PBFT: первый практичный BFT-алгоритм

**Castro и Liskov, MIT, 1999. PBFT (Practical Byzantine Fault Tolerance) - первый алгоритм, который сделал BFT практически применимым.** До PBFT теоретические BFT-протоколы были слишком медленными для реального использования. PBFT показал overhead всего 3% по сравнению с non-BFT системами при малых кластерах.

Три фазы PBFT

**Pre-prepare:** Primary получает запрос клиента, назначает ему sequence number n и рассылает всем репликам. **Prepare:** каждая реплика, получив Pre-prepare, рассылает Prepare всем остальным. Состояние prepared достигается когда собрано 2f Prepare-сообщений. **Commit:** после prepared каждый шлёт Commit всем. После 2f+1 Commit - операция выполняется и клиент получает Reply.

**View Change:** если реплика не получает Pre-prepare вовремя - подозревает Primary. Отправляет VIEW-CHANGE с доказательствами. Новый Primary (view+1 mod N) собирает 2f VIEW-CHANGE и рассылает NEW-VIEW. Дорого: O(N^2) сообщений. Злонамеренный Primary может намеренно триггерить view changes, замедляя систему.

BFT на практике: когда нужен и сколько стоит

**HotStuff (Facebook/Meta, 2018) решил главную проблему PBFT: O(N^2) сообщения при view change.** Ключевая идея - threshold signatures (пороговые подписи): вместо того чтобы лидер рассылал всем N^2 сообщений, каждая реплика шлёт подпись лидеру, лидер агрегирует в одну подпись и делает один broadcast. View change: O(N) вместо O(N^2). HotStuff используется в Diem/Libra и является основой LibraBFT.

**Большинству систем BFT не нужен.** Если все узлы под контролем одной организации - Raft достаточен и на порядок быстрее. BFT нужен когда участники не доверяют друг другу (разные организации, public network) или когда hardware failure может привести к Byzantine поведению (space, nuclear).

Практический выбор: внутренние системы (микросервисы, базы данных компании) - Raft или Paxos. Multi-org системы где участники конкурируют или не доверяют друг другу - BFT. Public blockchains используют вероятностный BFT (Bitcoin PoW, Ethereum PoS) который жертвует finality ради масштабируемости.

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

• Большинство production-систем используют Raft/Paxos без BFT. Какие конкретные условия в архитектуре компании сигнализировали бы о необходимости перехода на BFT-протокол?

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

• dist-09-raft — Raft is the crash-fault baseline; BFT extends it
• dist-08-paxos — Classic Paxos assumes crash faults only
• ds-03-consensus — BFT consensus is a harder variant of the consensus problem
• dist-12-consistency — BFT changes the impossibility boundaries for consistency
• crypto-28-digital-signatures