За счёт чего византийский консенсус сохраняет единый результат, если часть узлов рассылает разным участникам противоречивые сообщения?
Византийский консенсус сохраняет единый результат за счёт обмена подтверждениями между узлами, проверки согласованности этих подтверждений и требования кворума, пересекающегося по честным участникам. В типичной синхронной или частично синхронной BFT-модели для устойчивости к f византийским узлам требуется не менее 3f + 1 узлов. Поэтому противоречивые сообщения неисправных участников не позволяют двум разным значениям получить достаточное число совместимых подтверждений.
Обычные алгоритмы консенсуса, рассчитанные на отказ остановившегося узла, предполагают, что неисправный участник просто перестаёт отвечать или теряет сообщения. Этого недостаточно, если узел действует произвольно: лжёт, отправляет разные значения разным участникам или пытается нарушить протокол.
BFT-подход появился для систем, где необходимо сохранять согласованность даже при таких произвольных отказах. Это особенно важно для критичных кластеров, в которых компрометация или ошибочная реализация одного узла не должна привести к принятию разных состояний.
Пусть несколько узлов должны согласовать одну последовательность операций, а часть участников может вести себя произвольно. Злонамеренный узел способен сообщить одним участникам, что принято значение A, а другим — что принято значение B.
Если решение принимается по одному сообщению или по простому большинству без учёта пересечения кворумов, разные честные узлы могут зафиксировать разные результаты. Это приводит к расхождению состояния, двойному выполнению операций или невозможности безопасно продолжить работу после восстановления связи.
BFT-протокол обычно разделяет согласование на этапы. Узел-лидер предлагает значение, остальные проверяют предложение и рассылают подтверждения; после получения достаточного числа согласованных сообщений операция считается безопасной для фиксации. Конкретные названия фаз и порядок сообщений зависят от протокола, но принципом остаётся проверяемое кворумное подтверждение.
При n = 3f + 1 узлах кворум обычно имеет размер 2f + 1. Два таких кворума обязательно пересекаются как минимум в f + 1 узлах, поэтому среди их пересечения есть хотя бы один честный участник. Честный узел не должен подтверждать несовместимые значения в одной позиции, следовательно, два разных значения не могут одновременно получить корректное подтверждение.
Аутентификация защищает сообщения от подделки отправителя. В разных протоколах применяются цифровые подписи или MAC-коды; одного шифрования канала недостаточно, если нужно доказать, кто сформировал сообщение и какие подтверждения действительно были выданы.
У BFT есть существенные ограничения. Нужно выдерживать допущения о сетевых задержках или иметь механизм смены лидера после тайм-аутов; при слишком большом числе участников растёт коммуникационная нагрузка. Кроме того, BFT защищает от ограниченного числа неисправных узлов только при корректном выборе параметров, безопасном хранении ключей и соблюдении модели угроз.
Нужно различать безопасность и живучесть. Безопасность означает, что честные узлы не примут несовместимые результаты. Живучесть означает, что система сможет завершать операции; при недостижимом кворуме она обычно должна остановить фиксацию, а не выбирать результат ценой нарушения согласованности.
Кластер из семи валидаторов обрабатывает операции, а два валидатора скомпрометированы. Рассматривались три варианта: доверять лидеру, что быстро, но не защищает от ложного лидера; использовать обычный консенсус с отказами остановившихся узлов, что не покрывает противоречивое поведение; применить BFT-протокол с кворумом пяти узлов.
Выбран третий вариант: семь узлов позволяют выдержать два византийских отказа, поскольку выполняется условие n ≥ 3f + 1. Операция фиксируется только после достаточного набора проверяемых подтверждений, поэтому два скомпрометированных узла могут задерживать или искажать сообщения, но не способны самостоятельно навязать честным узлам два разных результата.
Цена решения — дополнительные сетевые обмены, необходимость управления ключами и возможная потеря доступности при недоступности пяти узлов. Для системы, где расхождение состояния недопустимо, этот компромисс предпочтительнее продолжения работы с риском двойной фиксации.
3f + 1, а не просто большинство?Потому что нужно одновременно выдержать до f лживых узлов, сохранить кворум честных участников и обеспечить пересечение любых двух кворумов честным узлом. В конфигурации 3f + 1 кворум 2f + 1 содержит не менее f + 1 честных узлов, а пересечение двух таких кворумов не может состоять только из неисправных участников.
Нет. Подписи доказывают происхождение и целостность сообщений, но сами по себе не заставляют узлы прийти к одному решению. Нужны протокол обмена, правила проверки предложений, кворумы, защита от повторного подтверждения несовместимых значений и механизм восстановления после смены лидера.
Только если одна из частей сохраняет необходимый кворум и выполняются сетевые предположения протокола. Меньшая часть обычно не должна фиксировать новые операции, поскольку не может получить достаточное подтверждение; это сохраняет безопасность, но снижает доступность. Если разделение сопровождается задержками, превышающими допустимые пределы, протокол может временно остановить фиксацию даже без фактической компрометации узлов.