Что такое задача византийских генералов и как она связана с BFT?

Что такое задача византийских генералов?

Задача византийских генералов –– это теоретическая дилемма, впервые представленная в 1982 году в работе Лэсли Лэмпорта, Роберта Шостака и Маршала Пиза под названием The Byzantine Generals Problem. Суть ее заключается в следующем. 

Представим, что мы попали во времена Византийской империи, которая планирует нападение на город. За это отвечает группа генералов. Каждый имеет под командованием небольшую армию. 

У военачальников есть два варианта: атаковать или отступить. Они обязаны прийти к консенсусу по этому вопросу, однако решение должно приниматься ими по отдельности. 

Ситуация усложняется тем, что войска расположены в разных локациях, поэтому единая централизованная связь отсутствует. Генералы могут общаться между собой через посыльного, но одновременно способны отправить сообщение лишь одному человеку.

Это создает риск получения неправдивой информации. Например, один из военачальников окажется предателем и намеренно передаст ложное сообщение. Или в ходе отправки произойдет подмена письма недоброжелателями. 

Подобный исход может привести к несогласованности действий, в результате чего войска будут разгромлены.

Поэтому в ходе решения задачи необходимо придумать механизм взаимодействия генералов таким образом, чтобы они пришли к консенсусу, даже если часть из них передаст неверные данные.

Что такое BFT?

На первый взгляд, данная задача никак не связана с работой блокчейна. Однако в действительности разрешение этой дилеммы напрямую влияет на такое его свойство, как BFT, в связи с чем и была написана вышеупомянутая статья The Byzantine Generals Problem.

Byzantine Fault Tolerance (BFT) или византийская отказоустойчивость –– это способность системы продолжать работу в случае, если один из узлов сети недобросовестно выполняет свои функции, независимо от причины. 

В результате теоретическое решение задачи византийских генералов позволяет на практике наделить блокчейн свойством BFT. Оно применимо не только к блокчейну, но и к другим техническим направлениям. При этом наличие этой характеристики особенно актуально для децентрализованных сетей, поскольку ее отсутствие ставит их безопасность под угрозу. Например, в результате атаки 51%.

Вариации BFT

На момент написания существуют две основные концепции реализации данного свойства.

Practical Byzantine Fault Tolerance (PBFT)

В работе алгоритма PBFT принимает участие две категории узлов. Основная нода отвечает за обработку транзакций пользователей. После она формирует из них блок, который должны проверить служебные ноды. 

Они обмениваются между собой информацией о статусе проверки. Если с блоком все в порядке, то основная нода включает его в блокчейн. При этом для достижения консенсуса необходимо 2/3 голосов всех служебных узлов.

Подобный механизм достаточно прост в исполнении и позволяет относительно быстро обрабатывать транзакции. Однако он эффективен лишь в случае ограниченного числа участников сети, отвечающих за ее работу. 

С увеличением их количества уменьшается пропускная способность, поскольку необходимо больше времени для согласования всеми нодами решения по добавлению блока. 

Также в некоторых случаях возможен захват контроля над блокчейном путем все той же атаки 51%, если злоумышленник подключит к сети достаточное количество узлов.

Federated Byzantine Agreement (FBA)

FBA является более гибким и масштабируемым механизмом. Путем общего голосования ноды выбирают представителей, которым они доверяют. Доверие основано преимущественно на прошлой активности участника сети, дающее понимание о его добросовестности.

Затем каждый избранный узел формирует так называемую подсеть, состоящую из обычных нод, которым он «верит». В каждом подобном кластере происходит свое достижение консенсуса. 

Доверенный узел формирует блок транзакций и предлагает его включить в блокчейн. Подсеть обязана проверить и решить вопрос касательно его добавления.

Так происходит первый этап валидирования сети в кластерах. Избранная нода «верит» исключительно собственной группе участников. После этого деятельность переходит на второй уровень. Лидеры подсетей договариваются между собой. Если они приходят к общему консенсусу, блок добавляется в блокчейн.

Благодаря данной системе снижается количество контактов, которые совершают узлы. Вместо всеобщего взаимодействия они коммуницируют в основном в ограниченной группе доверенных участников. За счет этого увеличивается скорость принятия решения, что благоприятно влияет на пропускную способность сети.

Однако в этой конфигурации велик риск централизации, когда ноды функционируют лишь в «собственных» группах, куда может стать проблематично попасть новым пользователям.

Практическое использование BFT

Хотя BFT является важным свойством, без которого блокчейн не сможет нормально функционировать, его концепции реализации являются лишь ориентиром. Ни один из блокчейнов не использует их в чистом виде. Ни PBFT, ни FBA. Вместе этого большинство проектов эксплуатируют определенные элементы, которые затем используются для создания алгоритмов достижения консенсуса.

В большей степени это касается системы Practical Byzantine Fault Tolerance, которая стала основой для Proof-of-Stake, Proof-of-Work и других алгоритмов достижения консенсуса. Они имплементировали аспекты безопасности, заложенные в решении задачи византийских генералов, благодаря чему децентрализованные сети могут справляться в большинстве случаев со сбоями или потенциальными атаками на них.

Выводы

Задача византийских генералов была предложена еще в 1982 году, когда блокчейн не существовал даже на уровне концепции. Тем не менее дилемма заложила принципы, которые по итогу позволили создать алгоритмы достижения консенсуса, обладающие свойством BFT.

Без этой способности распределенные сети не смогли бы качественно и безопасно обрабатывать транзакции, что в свою очередь могло подорвать доверие пользователей и помешать развитию криптовалютной индустрии в целом.