Курс «Распределённые системы». Глава 7. Византийские отказы

Данные ИИ Разработка Безопасность Инфраструктура Квантовые вычисления Курсы и книги

2026 г.

Курс «Распределённые системы». Глава 7. Византийские отказы

Цели главы. Короткая глава для полноты картины: что меняется, когда узлы не просто падают, а лгут. Мы установим цену недоверия — 3f+1 узла вместо 2f+1 и квадратичный трафик вместо линейного, — разберём идею классического протокола PBFT и посмотрим на блокчейны как на византийский консенсус с открытым членством. Главный практический вывод главы противоположен её эффектной теме: в подавляющем большинстве систем византийская защита не нужна, и знать надо прежде всего границу, за которой она становится нужна.

7.1. Модель

До сих пор (глава 1) худшим отказом узла была остановка. Византийский узел ведёт себя произвольно: шлёт противоречивые сообщения разным адресатам, подделывает данные, вступает в сговор с другими отказавшими, соблюдает протокол ровно настолько, чтобы вредить незаметно. Модель покрывает и злонамеренность (взломанный узел, недобросовестный участник), и предельно причудливые сбои (перевёрнутый бит памяти, прошивка с багом) — исторически она и родилась в аэрокосмической отрасли, где датчик может не «молчать», а «врать».

Название — от задачи византийских генералов (Лэмпорт, Шостак, Пиз, 1982): генералы согласуют атаку через гонцов, но часть генералов — предатели, рассылающие разным коллегам разное. Требуется, чтобы все лояльные пришли к одному решению, что бы ни делали предатели.

7.2. Цена недоверия: 3f+1

Классическая граница (там же, 1982): в синхронной модели устных сообщений, где отправителя можно определить, но чужое сообщение нельзя доказуемо переслать, византийское соглашение при f предателях требует не меньше 3f+1 узлов. Та же численность используется практическими частично синхронными BFT-протоколами. Сравните с 2f+1 для crash-отказов: при том же f недоверие стоит ещё f узлов — треть византийского кластера уходит на компенсацию лжи.

Нижняя граница на минимальном случае n=3, f=1 — три исполнения, как у Лэмпорта, Шостака и Пиза. Есть командующий C и два заместителя L1 и L2; лояльные заместители обязаны (а) решить одинаково и (б) выполнить приказ лояльного командующего. Исполнение 1: C лоялен и приказывает обоим «атаковать», предатель L2 пересказывает L1, будто получил «отступать», — по правилу (б) L1 обязан атаковать. Исполнение 2 — зеркальное: C лоялен и приказывает «отступать», лжёт L1 — L2 обязан отступить. Исполнение 3: предатель — сам C; L1 он посылает «атаковать», L2 — «отступать», а заместители честно пересказывают друг другу полученное. Но для L1 исполнение 3 неотличимо от исполнения 1, значит, он атакует; для L2 оно неотличимо от исполнения 2, значит, он отступает. Два лояльных заместителя разошлись — нарушено (а). Четвёртый узел ломает симметрию: лояльных трое против одного лжеца, и перекрёстный обмен «а что тебе сказал X?» вскрывает противоречия большинством. Общий принцип: кворумы берутся размером 2f+1 из 3f+1 — два таких кворума пересекаются в 2f+1+2f+1−(3f+1) = f+1 узлах, то есть хотя бы в одном честном: сама арифметика пересечения из главы 6, усиленная на толщину лжи.

Криптография меняет модель. Цифровые подписи лишают предателя возможности незаметно переврать чужие слова: утверждение «B сказал 1» можно предъявить с подписью B. В синхронном authenticated Byzantine agreement это снимает классическую границу 3f+1. В полностью асинхронной модели детерминированный консенсус всё равно запрещён FLP; рандомизированные асинхронные BFT-протоколы обычно требуют n > 3f. Конкретный порог всегда нужно читать вместе с предположениями о времени, аутентификации и противнике.

7.3. PBFT: практический византийский консенсус

PBFT (Кастро, Лисков, 1999) — первый протокол, сделавший византийский консенсус практичным; идейный каркас большинства современных наследников (Tendermint/CometBFT, HotStuff и др.). Схема узнаваема после главы 6: реплицируемый автомат, лидер (primary) упорядочивает запросы, эпохи (view) с протоколом смены лидера, — но каждое «поверил лидеру» заменено на «проверил кворумом»:

pre-prepare: лидер рассылает аутентифицированное предложение с номером последовательности;
prepare: каждая реплика, проверив предложение, рассылает всем аутентифицированное согласие; сертификат prepare содержит сообщения от достаточного числа разных реплик (в классическом описании — pre-prepare и 2f совпадающих prepare), поэтому два противоречащих сертификата не могут состоять только из честных участников;
commit: ещё один всеобщий раунд подтверждений — страховка на случай смены лидера посреди дела (чтобы решение, видимое одним, не потерялось для других); после 2f+1 подтверждений запрос исполняется.

Клиент принимает ответ, получив f+1 одинаковых аутентифицированных ответов от разных реплик (хотя бы один — от честной). Цена очевидна из структуры: два раунда «все-всем» — O(n²) сообщений на запрос (у Raft — O(n)). При этом классический PBFT ради производительности заменяет большинство цифровых подписей в нормальном режиме векторами MAC, называемыми authenticators; утверждение «все подписывают всё» было бы неверным. Современные протоколы вроде HotStuff сокращают нормальный обмен с помощью пороговых и агрегированных подписей, но модель остаётся существенно дороже crash-консенсуса.

7.4. Блокчейны: BFT с открытым членством

PBFT предполагает известный список участников. Публичные блокчейны решают более дикую задачу: консенсус между кем угодно, без списка, где противник может завести тысячу узлов (атака Сивиллы). Ответ Накамото (биткойн, 2008) — сделать влияние дорогим: вероятность предложить блок пропорциональна выполненной вычислительной работе, а цепочка с наибольшей накопленной работой побеждает. Согласие вероятностное: чем глубже блок, тем дороже и менее вероятен откат при доле мощности противника меньше половины. Proof-of-Stake связывает влияние с поставленным под риск капиталом и во многих системах комбинируется с BFT-финализацией комитетов. Для нашего курса блокчейн — это точка в пространстве компромиссов: открытое членство и максимальное недоверие куплены ценой пропускной способности и задержек, существенно худших, чем у небольшого Raft-кластера.

7.5. Когда это нужно — и когда нет

Внутри одной организации обычно выбирают crash-модель: типичные узлы падают и зависают, целостность каналов дают TLS и аутентификация, случайную порчу обнаруживают контрольные суммы. Но это не универсальный закон: если модель угроз включает одновременный компромисс части реплик, ошибочную прошивку общего происхождения или недоверенные административные домены, crash-консенсуса недостаточно. BFT оправдан там, где участники — разные стороны с несовпадающими интересами, либо критичность системы требует переживать компромисс реплик. Правило для архитектора: сначала честно назвать противника и общие причины отказа; модель протокола выводится из модели угроз, а не из моды.

Итоги главы

Византийский отказ = произвольное, в т.ч. злонамеренное поведение; модель угроз, а не только злого умысла.
Порог 3f+1 (против 2f+1 честной модели); кворумы 2f+1 пересекаются по f+1 — хотя бы одному честному. Подписи упрощают протоколы, лишая предателей пересказа чужих слов.
PBFT = реплицируемый автомат с проверкой каждого шага кворумом: O(n²) сообщений в нормальном режиме; классические развёртывания — единицы и десятки узлов, дальше нужны агрегированные подписи и другая структура обмена (HotStuff).
Блокчейны — византийский консенсус с открытым членством: голос удорожается работой или капиталом, финальность вероятностна или комитетна.
Нужен ли BFT — решает модель угроз, а не периметр: crash-консенсус не покрывает компрометацию реплики или общую ошибочную прошивку; типичный случай оправданного BFT — стороны с несовпадающими интересами (а контрольные суммы нужны всегда).

Упражнения

Воспроизведите доказательство невозможности при n=3, f=1 для командующего C и заместителей L1, L2: постройте три исполнения, в которых сначала верность приказу лояльного C определяет решения L1 и L2, а затем предатель C делает наблюдения лояльных заместителей неотличимыми от первых двух исполнений.
Проверьте арифметику кворумов: почему в системе из 3f+1 узлов кворум размера 2f+1 одновременно (а) достижим при f отказавших и (б) гарантирует пересечение двух кворумов хотя бы в одном честном узле? Что сломается при кворуме 2f?
Сравните стоимость фиксации одной записи в Raft (n=5) и PBFT при том же f=2 (какой n ему необходим?) по числу сообщений и раундов. Во сколько раз растёт трафик при удвоении кластера в каждом случае?
Взломанный узел Raft-кластера (не византийская модель!) может: голосовать дважды в терме, подтверждать несохранённые записи, отвечать клиентам выдуманными данными. Для каждого действия укажите, какая гарантия главы 6 рушится, — и сделайте вывод, от чего Raft не защищает по построению.
Консорциум из пяти банков строит общий реестр. Аргументируйте выбор между «Raft у нейтрального оператора» и «BFT между банками»: какие угрозы закрывает каждый вариант, где остаётся доверие и какова цена в узлах, трафике и эксплуатации?
Почему k подтверждений в сети Накамото дают вероятностную, а не абсолютную финальность? Оцените качественно, как вероятность отката блока зависит от k и доли мощности противника (известный результат из оригинальной статьи — экспоненциальное убывание при доле < 1/2).

Ответы и указания. 1: при лояльном C и приказе «атаковать» L1 обязан атаковать, даже если предатель L2 пересказывает «отступать». При лояльном C и приказе «отступать» симметрично обязан отступить L2, даже если L1 пересказывает «атаковать». Когда C предаёт и посылает L1 «атаковать», а L2 «отступать», наблюдение L1 совпадает с первым исполнением, а наблюдение L2 — со вторым. Оба заместителя лояльны, но принимают разные решения, что нарушает соглашение. 2: при f отказавших остаются 2f+1 участник — ровно кворум; два кворума пересекаются минимум по f+1 узлам, среди которых есть лояльный. Для размера 2f пересечение может целиком состоять из византийских узлов. 3: PBFT при f=2 требует n=7, поэтому сравнение с пятиузловым Raft относится к одинаковому числу переносимых отказов, но не к одинаковому n. У Raft нормальная фиксация требует O(n) сообщений после установления лидера; у классического PBFT обмен prepare/commit даёт O(n²). При удвоении n линейный трафик примерно удваивается, квадратичный — учетверяется. 4: двойной голос допускает два лидерских большинства, ложное подтверждение разрушает долговечность фиксации, выдуманный ответ — клиентскую корректность. Raft предполагает корректное исполнение протокола и защищает от crash-отказов, а не от захваченной реплики. 5: Raft у оператора проще, но все банки доверяют оператору не подменять историю; BFT распределяет доверие и переносит до f произвольно ведущих себя участников при 3f+1 узлах, платя более сложными членством, ключами и обменом. Даже BFT оставляет доверие к аутентификации, реализации и правилам допуска. 6: конкурент может строить альтернативную ветвь и попытаться догнать публичную; k блоков лишь увеличивают требуемую работу. При предположениях анализа Накамото и доле мощности меньше 1/2 вероятность догоняющего отката убывает с k, но не становится строго нулевой.