Задача византийских генералов: Математический консенсус при предательстве
Как синхронизировать работу сети независимых серверов, если известно, что некоторые из них могут сломаться или быть захвачены хакерами, посылающими ложную информацию? Эта проблема является главным вызовом при проектировании отказоустойчивых баз данных, сетей блокчейн и бортовых компьютеров космических кораблей. В 1982 году Лесли Лампорт математически формализовал эту проблему в виде знаменитой «Задачи византийских генералов».
Условие задачи звучит как военная метафора. Византия осаждает вражеский город. Армия разделена на несколько легионов, каждым командует свой генерал. Генералы общаются только через гонцов. Чтобы победить, они должны выработать единый консенсус: "Атаковать" или "Отступать". Но среди генералов есть предатели, которые могут отправлять разные приказы разным генералам, чтобы внести хаос и погубить армию.
Алгоритм достигает Византийского консенсуса (BFT - Byzantine Fault Tolerance), если он математически гарантирует, что все лояльные (честные) генералы в итоге примут одно и то же согласованное решение, несмотря на любые ухищрения предателей.
Лампорт доказал фундаментальную теорему о пороге безопасности: если гонцы передают устные сообщения (которые можно подделать), то консенсус невозможен, если число предателей больше или равно трети от общего числа генералов. Формула гласит: система устойчива только если общее число узлов N ≥ 3f + 1, где f — число предателей. То есть для защиты от одного взломанного сервера в кластере должно быть минимум 4 сервера. Чтобы обойти это жесткое математическое ограничение, Лампорт ввел подписанные сообщения (криптографические цифровые подписи, которые нельзя подделать). С подписями армия может прийти к консенсусу при любом количестве предателей!
В мире децентрализованных сетей (Bitcoin) классический BFT неприменим, так как там нет фиксированного, известного заранее списка серверов (генералов), и злоумышленник может создать миллион фальшивых "генералов" (Атака Сивиллы). Сатоши Накамото решил эту дискретную задачу, объединив консенсус с криптографическим доказательством работы (Proof-of-Work), сделав процесс голосования вычислительно дорогим.
В закрытых корпоративных кластерах (где все IP-адреса известны) сегодня используются практические алгоритмы достижения консенсуса — Paxos и его более понятный аналог Raft. Они опираются на выборы лидера и репликацию логов, обеспечивая целостность данных в распределенных системах вроде Apache Kafka и Kubernetes (etcd).
