Задача византийских генералов исследует, могут ли исправные процессы согласовать одно решение, если неисправные действуют произвольно и отправляют противоречивые сообщения разным получателям. Формулировка Лэмпорта, Шостака и Пиза 1982 года доказывает нижнюю границу 3m+1 участников для допуска m предателей в модели устных сообщений без подписей и описывает рекурсивные алгоритмы для устных и подписанных сообщений. Это результаты при точных предпосылках, а не синоним любого блокчейн-консенсуса.
Лэмпорт, Шостак и Пиз опубликовали аллегорию в ACM TOPLAS в июле 1982 года для объяснения интерактивной согласованности реплицированных систем. Разделённые генералы выбирают один план, хотя предатель может сообщать разным адресатам разное. Византийский отказ сильнее остановки: компонент способен лгать, противоречить себе, пропускать сообщения или казаться исправным лишь части системы. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Статья разделяет IC1: все верные лейтенанты исполняют один приказ, и IC2: если командир верен, они исполняют его приказ. Современные аналоги — согласие или safety, валидность и завершение или liveness. Гарантии осмысленны только вместе с моделью сети, аутентификацией и пределом числа отказов. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
В модели устных сообщений известен непосредственный отправитель, отсутствие обнаруживается и каждая пара связана, но предатель шлёт разные значения. OM(m) рекурсивно пересылает значения и применяет детерминированное большинство. Для m византийских процессов нужно не менее 3m+1 участников, то есть более двух третей верных. Трое не выдерживают одного предателя из-за неразличимости его роли. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Неподделываемая подпись раскрывает противоречивую рассылку и не даёт изменить приказ, подписанный верным участником. Алгоритм пересылает новые подписанные значения и одинаково решает по собранному множеству. При идеальных предпосылках допускается любое число предателей. Но подпись доказывает источник, а не истину, своевременную доставку или честность скомпрометированного ключа; Долев и Стронг уточнили границы раундов. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Возможность гарантировать продвижение зависит от временных условий. Результат Fischer–Lynch–Paterson 1985 года показывает, что в полностью асинхронной детерминированной системе сообщений даже один процесс, которому разрешено аварийно остановиться, оставляет допустимое выполнение без завершения консенсуса. FLP не утверждает, что реальные системы никогда не согласуются. Гарантия продвижения требует дополнительных предположений, например временных границ, начинающих действовать в некоторый момент, или детектора отказов с определёнными свойствами, либо перехода к рандомизированному протоколу. Одного назначения лидера недостаточно. При долгом разделении сети безопасный протокол может перестать завершать операции. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT Мигеля Кастро и Барбары Лисков 1999 года превращает византийское согласие в реплицированный автомат состояний. Базовая конфигурация n = 3f+1 выдерживает f византийских реплик. Подготовленность включает pre-prepare от первичной реплики и 2f соответствующих сообщений prepare; локальное подтверждение требует подготовленности и 2f+1 соответствующих сообщений commit. Пересечения кворумов и правила смены представления препятствуют противоречивым подтверждениям. Аутентификация, порядковые номера, контрольные точки и смена представления противодействуют подделке, повторам, росту журнала и неисправному лидеру. Известный набор реплик и детерминированная окончательность отличаются от открытой сети Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin не исполняет OM или PBFT и не считает поимённо известные узлы. Устойчивый к атакам Sybil механизм Proof of Work взвешивает конкурирующие истории по накопленной работе; каждый Full Node независимо отвергает блоки, нарушающие правила консенсуса, и следует допустимой цепи с наибольшей совокупной работой. Временные развилки ожидаемы. При предположениях о честном превосходстве работы и связи вероятность переписывания убывает с глубиной подтверждений, но это не математическая необратимость. Модель Bitcoin Backbone формализует общий префикс, рост и качество цепи при явно заданной доле работы атакующего и сетевых условиях. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Утверждение, что Bitcoin решил задачу византийских генералов, скрывает смену модели. Классическое согласие начинается с фиксированной группы известных участников и предела f; Bitcoin допускает изменяющихся псевдонимных участников и внешний дефицитный ресурс. Его гарантии всё равно требуют конкретных предположений о доставке сообщений. Proof of Work ограничивает влияние идентичностей Sybil, но не предотвращает атаки eclipse, цензуру, эгоистичный майнинг, ошибки программ и реорганизацию при большинстве хешрейта. Модель угроз должна определять атакующего, временные условия, членство и окончательность; одного обозначения BFT недостаточно. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Для полной картины прочитайте эту статью вместе с Nakamoto consensus, Proof of Work, Правила консенсуса, Двойная трата, Bitcoin, Finality.