В поисках консенсуса: что такое и как решается «задача византийских генералов»
Одной из главных целей любой децентрализованной системы является достижение консенсуса в алгоритме действий между участниками. Описать проблему позволяет так называемая «задача византийских генералов».
Задача Лесли Лэмпорта
Первоначально задача была сформулирована еще в 1982 году американским криптографом Лесли Лэмпортом (Leslie Lamport). Этот исследователь также известен разработкой криптосистемы «подпись Лэмпорта» с открытым ключом, «часов Лэмпорта» — механизма определения порядка событий в распределенной среде, — а также системой LaTeX.
«Задача византийских генералов», представленная Лэмпортом, звучит примерно следующим образом:
Представьте армию Византийской империи, которая состоит, скажем, из четырех легионов. Каждым легионом командует один генерал. Генералы не подчиняются друг другу, но планируют штурм огромной крепости с разных сторон, удаленных друг от друга. Каждый генерал и его легион должен оценить обстановку и на рассвете либо начать штурм крепости, либо отступить. При этом все генералы должны действовать одинаково: либо совместно штурмовать, либо совместно отступать. Если хотя бы один генерал будет отступать в то время, как остальные решат штурмовать, армия потерпит поражение.
Чтобы генералы действовали синхронно, им нужно каким-то образом договориться. Для этого они могут отправлять друг другу гонцов. Но нет никакой гарантии, что посланника генерала не перехватит вражеская армия и не подменит сообщение на ложное. Также среди самих генералов могут оказаться предатели.
Иными словами, генералы не уверены в подлинности получаемой информации. В таких условиях им нужно разработать единую стратегию действий, которая обеспечит достоверность получаемой информации и в целом благоприятный исход дела.
Схематически, в упрощенном виде ситуацию можно представить картинкой, где синяя фигура — крепость\замок, красные фигуры — генералы и их легионы, а белые фигуры — каналы обмена информацией:
В чем суть задачи Задача византийских генералов — это дилемма и умозрительная постановка проблемы, характерной для технически сложных систем, в которых разные элементы должны действовать параллельно, достигая необходимого результата.
Когда разработанная нами система способна противостоять классу отказов, характерных для проблем «византийских генералов», мы говорим о так называемой «византийской отказоустойчивости» или Byzantine fault tolerance (BFT). Проще говоря, это важное свойство, при котором система продолжает работать корректно —несмотря на то, что отдельные компоненты могут выйти из строя или даже злонамеренно пытаться нарушить порядок работы.
Византийские генералы и Биткоин Поскольку Биткоин является децентрализованной одноранговой сетью, ее создатель Сатоши Накамото также столкнулся с необходимостью решения «проблемы византийских генералов». В случае с сетью Биткоина генералами выступают сетевые узлы, которые должны обрабатывать и передавать информацию, достигнув единого консенсуса.
Поскольку Биткоин использует алгоритм консенсуса Proof-of-Work, а сама сеть полностью децентрализована и не зависит от единого узла, это позволяет заменить необходимость доверия между участниками на криптографические доказательства. Даже если часть узлов сети работает некорректно или злонамеренно, механизм Proof-of-Work позволяет большинству честных участников согласовать верную цепочку блоков.
Однако Биткоин не является абсолютно устойчивым к «византийским ошибкам». Например, так называемая атака 51% теоретически может позволить злоумышленнику изменить данные в цепочке блоков. Правда, для этого ему потребуется контролировать более половины всей вычислительной мощности сети. По мере добавления новых блоков в цепь сложность реализации такой атаки экспоненциально растет, что делает ее практически невозможной в условиях современного Биткоина.
Ethereum и Proof-of-Stake Другой крупной криптовалютой, решающей дилемму византийских генералов, является Эфириум. В версии 2.0 используется алгоритм Proof-of-Stake (PoS), который, в отличие от Proof-of-Work, основывается на стейкинге. Этот подход снижает энергозатраты, делает атаки менее вероятными и увеличивает устойчивость сети к византийским отказам, — хотя накладывает свои ограничения и в целом также является спорным решением по сравнению с PoW (например, в вопросах экономической плоскости, а именно «себестоимости криптовалюты» в отсутствии трат на майнинг, оборудование и так далее).
Hedera и Hashgraph Еще одним примером решения задачи византийских генералов является криптовалюта Hedera, которая использует технологию Hashgraph вместо традиционного блокчейна. В основе Hashgraph лежит протокол gossip, что несколько отличается от подходов, применяемых в Биткоине (Proof-of-Work) и Ethereum (Proof-of-Stake). В случае с gossip, протокол, по заявлениям разработчиков, достигает асинхронной византийской отказоустойчивости (aBFT).
Проблема византийских генералов за пределами блокчейна Концепция византийской отказоустойчивости применима не только в блокчейне, но и в других распределенных системах. Например, она используется в облачных вычислениях, распределенных базах данных и системах интернета вещей (IoT). В таких системах необходимо гарантировать корректное функционирование, даже если часть элементов системы ведет себя некорректно или злонамеренно.
Заключение Задача византийских генералов остается крайне важной дилеммой и концепцией, которая легла в основу современных децентрализованных систем. Существуют разные подходы к достижению консенсусов и устойчивости систем к подобным вызовам. Такие решения как Proof-of-Work и Proof-of-Stake позволяют минимизировать риски византийских ошибок, обеспечивая стабильность и безопасность сетей.
Источник:
Bits.media
