Byzantine Generals Problem

Представьте отряды вокруг города. Они должны вместе наступать или вместе отступать: разрозненные действия могут их погубить. Командир рассылает приказы, но кто-то может предать остальных и сообщать разные версии. Как надёжным участникам в итоге действовать одинаково? Это не рассказ о настоящей битве, а мысленный пример для компьютеров, которым нужны согласованные записи. Например, несколько серверов — компьютеров, обеспечивающих общую службу, — должны одинаково решить, обработан ли уже платёж. Получить какой-нибудь ответ недостаточно: ответы должны складываться в общее решение. [1] [9]

Лесли Лэмпорт, Роберт Шостак и Маршалл Пиз представили известную формулировку в июле 1982 года после своей работы 1980 года о согласовании при отказах. Предатель обозначает компонент, поведение которого больше нельзя предсказать. Компьютер не обязательно просто остановится. Он может правильно ответить одному соседу и неправильно другому, пропустить сообщения или утверждать, что видел другое. Причиной бывает атака или ошибка программы. Византийский отказ описывает наблюдаемое поведение, а не намерения устройства. BFT (Byzantine Fault Tolerance) означает способность системы переносить такое поведение при определённых условиях. [1] [2]

В исходной задаче два условия. IC1 требует, чтобы все надёжные подчинённые приняли одинаковый приказ. IC2 добавляет: если командир тоже надёжен, они должны принять именно отправленный им приказ. Без второго условия правило «всегда отступайте» казалось бы решением, но игнорировало бы честного командира. В компьютерных системах различают безопасность — отсутствие противоречивых результатов — и живость, то есть возможность вообще получить результат. Другие правила определяют допустимые результаты. Согласованная запись сама по себе не доказывает истинности входного утверждения во внешнем мире. [1] [9]

Обозначим командира A, а подчинённых B и C. C получает от A приказ наступать, но B говорит, что командир приказал отступать. Лжёт B или командир разослал разные приказы? Без подписи, проверяемой после пересылки сообщения, C может не различить эти ситуации. B может столкнуться с той же неопределённостью. Если оба всегда слушаются командира, нечестный A их разделит; если всегда игнорируют его, нарушат условие для честного командира. Поэтому в этой задаче с тремя участниками и одним возможным предателем нет процедуры без подписей, которая всегда успешна. Не хватает различимых сведений, а не более быстрых компьютеров. [1] [9]

В классической модели без подписей для m возможных предателей нужно как минимум n ≥ 3m+1 участников: против одного — четверо. Здесь n — общее число участников, а m — наибольшее число предателей, которое система должна выдержать. Недостаточно добавить голос и один раз посчитать большинство. OM(m) предусматривает повторную пересылку услышанного и оценку сообщений по общим правилам; базовый случай OM(0) принимает значение командира или согласованное значение по умолчанию. Модель предполагает известных участников, прямые соединения, правильную доставку отправленных сообщений, знание непосредственного отправителя и возможность обнаружить отсутствие сообщения. «Без подписей» не означает «без всякой проверки происхождения». Без этих предпосылок число четыре ничего не гарантирует. [1] [9]

С помощью проверяемой цифровой подписи, Digital Signature, B может показать C, что именно подписал командир. Программа создаёт подпись с помощью закрытого ключа — секретного числового значения. Другие проверяют её соответствующим открытым ключом, не зная закрытого. Предатель не может незаметно изменить приказ надёжного участника или подделать его подпись. Алгоритм подписанных сообщений распространяет подписанные значения и применяет общее правило выбора. В этой модели исчезает указанное требование честного большинства, но остаются предположения о неподделываемых подписях, доставке и времени раундов. Работа Долева и Стронга 1983 года далее исследует необходимое число раундов. Даже правильная подпись не гарантирует правдивости содержания или своевременной доставки и не доказывает, что закрытый ключ не был украден. Она подтверждает происхождение конкретного сообщения, а не общую честность отправителя. [1] [3]

Когда сервер не отвечает, остальные не знают, остановился ли он или у него очень медленная связь. Результат FLP, опубликованный в 1985 году Майклом Фишером, Нэнси Линч и Майклом Патерсоном, точно описывает эту неопределённость. Процесс здесь — выполняющаяся программа. Детерминированная процедура при одинаковом состоянии и входных данных выполняет одинаковый следующий шаг, а не выбирает его случайно. В полностью асинхронной системе без известной верхней границы задержек детерминированная процедура не может гарантировать завершение согласования в каждом допустимом выполнении, если хотя бы один процесс может аварийно остановиться. Это верно даже при надёжной доставке с неограниченными задержками. Это не значит, что соглашение никогда не возникает. Практические системы добавляют временные предположения, подходящий детектор отказов или случайность. При разделении сети ожидание может быть безопаснее подтверждения несовместимых результатов. [4] [13] [8]

Мигель Кастро и Барбара Лисков в 1999 году описали Practical Byzantine Fault Tolerance, PBFT, для службы на нескольких известных репликах. Реплики — это копии службы, работающие на разных серверах и постоянно обрабатывающие одни и те же запросы. Речь не о сохранённых резервных файлах. Базовая конфигурация n = 3f+1 допускает f неисправных реплик. Из четырёх серверов один может быть византийским; две группы по три пересекаются минимум в двух серверах, среди которых хотя бы один надёжен. Требуемая группа подтверждений называется кворумом. Одного пересечения недостаточно: важны правила фаз и смены ведущего. Точнее, состояние prepared требует запроса, сообщения pre-prepare и 2f соответствующих prepare от разных реплик, кроме ведущей. Локальное подтверждение дополнительно требует 2f+1 сообщений commit, возможно включая собственное. Проверка происхождения, порядковые номера и контрольные точки противодействуют подделке, повторам и бесконечному росту журнала. Безопасность не зависит от временных границ, но продвижение требует дополнительных условий для задержек. [5] [10] [11] [12]

У Bitcoin нет заранее закрытого списка серверов. Если бы каждая новая учётная запись получала голос, нападающий мог бы создать большинство: это Sybil Attack. Поэтому Proof of Work связывает создание блоков с вычислительной работой. Блок — пакет транзакций, добавляемый в общую историю. Full Node — компьютер с программой, самостоятельно проверяющей правила, — сначала отвергает недопустимые блоки, затем выбирает допустимую ветвь с наибольшей накопленной работой. Bitcoin не выполняет OM или PBFT; временные развилки являются частью работы сети. При достаточном преимуществе честной мощности и подходящих условиях связи дополнительные подтверждения снижают риск переписывания истории, но не создают абсолютной необратимости. Исследования Bitcoin Backbone рассматривают эти условия: согласованность историй, рост цепи и долю блоков, которую могут создавать честные участники. [6] [7]

Услышав «сеть достигает консенсуса», спросите: кто может участвовать, что контролирует нападающий, сколько могут идти сообщения и когда решение может измениться? Даже Proof of Work не устраняет всех проблем. Eclipse Attack изолирует узел от честных соседей, цензура исключает транзакции, а Selfish Mining использует удержание добытых блоков. Остаются ошибки программ и возможность переписать часть истории при достаточном преимуществе атакующего. Но даже большинство вычислительной мощности не заставит правильно работающий Full Node принять блок, нарушающий его правила. История генералов учит выяснять условия соглашения, а не верить одному названию технологии. [6] [7] [8]