Византия, столица древнего Восточного Римского Империи, когда-то была одним из самых могущественных и богатых городов мира. Однако из-за своей обширной территории Византия часто сталкивалась с внешними вторжениями и внутренними мятежами. Чтобы защитить свои границы, Византия отправляла несколько армий, каждая из которых командовалась разными генералами. Достижение консенсуса среди этих генералов становилось значительным вызовом.
Проблема византийских генералов имеет тесную связь с блокчейном. Сеть блокчейна - это распределенная сеть, где узлы, подобно византийским генералам, должны достичь консенсуса по транзакциям и данным в ненадежной сетевой среде.

Проблема двух генералов

Проблема двух генералов является особым случаем Проблемы византийских генералов. Проблема и ее доказательство неразрешимости были впервые предложены в 1975 году в статье «Некоторые ограничения и компромиссы в проектировании сетевых коммуникаций» Е.А. Аккойунлу, К.Эканадхамом и Р.В. Хубером. В 1978 году Джим Грей официально назвал эту проблему «Проблемой двух генералов» в своей книге «Заметки о операционных системах баз данных». Изначально она использовалась для анализа проблем достижения согласия через связь по ненадежной коммуникационной линии. Сейчас её часто используют для иллюстрации проблем согласованности и согласия в распределенных системах.

Определение проблемы:
Две армии страны A, каждая под командованием генерала, готовятся атаковать армию страны B. Армия страны B окружена в долине, а армии A расположены на холмах с обеих сторон долины. Однако единственный путь между двумя армиями A проходит через долину. Армия B сильнее, чем любая из армий A по отдельности, но если обе армии A нападут вместе, они смогут победить армию B.
Проблема: Можно ли разработать алгоритм, который позволит двум генералам армий A договориться о одновременном нападении? Алгоритм может включать в себя отправку и прием сообщений.
Решение: Классическая проблема двух генералов неразрешима. Нет протокола, который может гарантировать успешное согласование атаки двух армий А. Однако в практических системах проблемы могут быть относительно надежно решены, например, с помощью механизма "трехстороннего рукопожатия" в протоколе TCP.

Проблема византийских генералов

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

Решение: Если количество генералов (узлов) в византийской системе равно Z, а количество ненадежных (изменчивых) генералов равно X, то только когда Z ≥ 3X + 1, протокол византийской отказоустойчивости (BFT) может гарантировать согласованность системы.
В практических системах отказы, приводящие к неработоспособности узлов, классифицируются как "Сбои при падении", в то время как узлы, подделывающие или подделывающие сообщения, классифицируются как "Византийские сбои".

Классификация алгоритма консенсуса

Блокчейн-системы являются типом распределенной системы, особенно общедоступные цепи, такие как Биткоин и Эфириум, которые состоят из многочисленных высокодецентрализованных и взаимно недоверяющих сетевых узлов. Механизм консенсуса блокчейна обеспечивает постоянное достижение системой блокчейна согласованности данных без вилок.
На основе типа отказоустойчивости алгоритмы консенсуса могут быть классифицированы на алгоритмы без византийской отказоустойчивости (CFT) и алгоритмы с византийской отказоустойчивостью (BFT).

Алгоритмы Нетолерантности к Византийским Ошибкам

В распределенных системах алгоритмы небезопасной избыточности обеспечивают надежность всей распределенной системы, когда узлы испытывают сбои системы или неплановые отключения (небезопасные сбои). Однако, когда злонамеренные узлы подделывают или подделывают данные, алгоритмы небезопасной избыточности не могут гарантировать надежность системы. Эти алгоритмы в основном используются в закрытых контролируемых распределенных предприятиях. Самыми представительными алгоритмами небезопасной избыточности являются алгоритм Паксоса и алгоритм Raft.

Алгоритмы, обеспечивающие византийскую устойчивость к отказам

Алгоритмы бизантинской устойчивости позволяют распределенной системе обеспечивать надежность даже в случае возникновения любого типа сбоя, при условии, что количество неисправных узлов не превышает определенной доли. Проще говоря, при условии, что количество неисправных узлов (из-за не бизантинских или бизантинских сбоев) меньше определенной доли общего числа узлов, алгоритмы бизантинской устойчивости могут обеспечить надежность системы. Из-за наличия множества недоверенных сетевых узлов в блокчейн-системах, таких как Bitcoin и Ethereum, алгоритмы бизантинской устойчивости в основном используются в механизмах согласования блокчейна. Самые представительные алгоритмы бизантинской устойчивости включают PBFT (Практическую бизантинскую устойчивость), PoW (Доказательство работы) и PoS (Доказательство доли).