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

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

7.1. Модель

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

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

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

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

Интуиция нижней границы на минимальном случае n=3, f=1. Узел A получает от B «значение 1», от C — «значение 0»; кто-то из них лжёт (или лжёт сам источник, рассылая разное). Для A ситуации «лжёт B» и «лжёт C» симметричны и неразличимы: любой протокол, заставляющий A решить, ошибётся в одном из зеркальных миров — а решать надо, согласие с лояльным обязательно. Четвёртый узел ломает симметрию: лояльных трое против одного лжеца, перекрёстный обмен «а что тебе сказал 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) с протоколом смены лидера, — но каждое «поверил лидеру» заменено на «проверил кворумом»:

1. pre-prepare: лидер рассылает аутентифицированное предложение с номером последовательности;
2. prepare: каждая реплика, проверив предложение, рассылает всем аутентифицированное согласие; сертификат prepare содержит сообщения от достаточного числа разных реплик (в классическом описании — pre-prepare и 2f совпадающих prepare), поэтому два противоречащих сертификата не могут состоять только из честных участников;
3. 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²) сообщений, десятки узлов — потолок классики.
• Блокчейны — византийский консенсус с открытым членством: голос удорожается работой или капиталом, финальность вероятностна или комитетна.
• Внутри доверенного периметра BFT не нужен (но контрольные суммы — нужны); он оправдан между сторонами с несовпадающими интересами.

Упражнения

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

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

Литература к главе

1. L. Lamport, R. Shostak, M. Pease, "The Byzantine Generals Problem," ACM TOPLAS 4(3), 1982.
2. M. Castro, B. Liskov, "Practical Byzantine Fault Tolerance," OSDI, 1999.
3. S. Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System," 2008.
4. M. Yin et al., "HotStuff: BFT Consensus with Linearity and Responsiveness," PODC, 2019.

Предыдущая глава || Содержание курса || Следующая глава