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

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

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

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

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

Как могут генералы координировать свои действия для одновременной атаки, если им приходится полагаться на посланников, которых могут перехватить или подкупить защитники Византии?

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

Централизованные и децентрализованные системы

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

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

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

Историческая справка

Влияние Византийской империи

Хотя термин «проблема византийских генералов» не связан напрямую с Византийской империей, некоторые параллели и потенциальные влияния могли привести к возникновению этой концепции.

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

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

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

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

Термин «проблема византийских генералов» был впервые введен учеными-компьютерщиками Лесли Лэмпортом, Робертом Шостаком и Маршаллом Писом в статье, опубликованной в 1982 году.

Национальное управление по аэронавтике и исследованию космического пространства, Командование систем противоракетной обороны и Исследовательское управление армии частично поддержали исследовательскую работу. Такая поддержка подчеркивает важность этого вопроса и то, что, помимо всех типов компьютерных систем, эта концепция может быть применена к военной связи.

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

Аналогия с современными вычислениями

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

В системах блокчейна проблема византийских генералов затрагивается в протоколах консенсуса, таких как доказательство работы (PoW), для достижения соглашения между несколькими узлами в ненадежной среде. Византийская отказоустойчивость представляет собой важную характеристику децентрализованных блокчейн-сетей.

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

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

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

Популярные византийские алгоритмы отказоустойчивости

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

Практическая византийская отказоустойчивость (PBFT):

Практическая византийская отказоустойчивость (PBFT) – это алгоритм консенсуса в распределенных системах, который допускает до одной трети общего числа византийских узлов, что означает, что они могут демонстрировать произвольное и потенциально вредоносное поведение, не влияя на сеть.

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

Федеративное Византийское соглашение (FBA):

Федеративное византийское соглашение (FBA) – это еще один алгоритм консенсуса в распределенных системах, разработанный для децентрализованной сети узлов, которые могут достичь консенсуса, не полагаясь на централизованный орган власти.

FBA основан на объединении независимых узлов в группы (федерации). Каждая федерация состоит из набора узлов, которые взаимно доверяют друг другу. Алгоритм гарантирует, что узлы внутри федерации согласовывают порядок и обеспечивают достоверность транзакций или событий, в то же время позволяя различным федерациям иметь отдельные процессы консенсуса. Fedimint – это наиболее известная федерация и протокол с открытым исходным кодом для транзакций и хранения биткоина, который использует византийский отказоустойчивый алгоритм консенсуса (HBBFT).

Биткоин-решение – доказательство работы

Хотя механизм консенсуса «доказательство работы» (PoW) Биткоина технически не является византийским отказоустойчивым алгоритмом, он, тем не менее, используется для обеспечения византийской отказоустойчивости Биткоина. Узлы сети не могут объявить блок действительным, если он не содержит хеш доказательства работы, указывающий, что для его создания была проделана работа.

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

Сравнение алгоритмов BFT:

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

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

Проблема византийских генералов в компьютерных сетях

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

В white paper Биткоина 2008 года было предложено решение проблемы информатики византийских генералов:

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

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

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

Аналогию с проблемой византийских генералов можно распространить на деньги и финансовые операции, особенно в контексте децентрализованных цифровых валют, таких как биткоин.

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

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

Биткоин-решение

1. Блокчейн решает проблему двойных расходов

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

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

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

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

2. Proof-Of-Work решает проблему византийских генералов

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

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

Заключение

По мере того как общество приближается к использованию распределенных систем и принимает децентрализованные деньги, такие как биткоин, подход «проблемы византийских генералов» становится важным для координации действий множества независимых сторон, не полагаясь на центральные власти.

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

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