Надежная компьютерная система должна быть способна функционировать даже при отказе одного или нескольких компонентов. Отказавший компонент может демонстрировать нетипичное поведение: передавать противоречивые данные в разные части системы.
Проблема византийских генералов — это абстрактное выражение проблемы, связанной с отказом компонента системы, это проблема теории игр, которая описывает, насколько трудно разрозненным сторонам достичь консенсуса без помощи доверенного центрального управленца. В стратегической среде теория игр представляет собой обстоятельства среди конкурирующих участников и производит оптимальное принятие решений автономными и конкурирующими игроками.
Византийские генералы основаны на аналогии с теорией игр. Проблема заключается в том, что несколько генералов осаждают Византию. Они окружили город, но им нужно решить, когда штурмовать его всей группой. Они выиграют, если все генералы будут штурмовать одновременно; или проиграют, если будут атаковать вразнобой.
Поскольку любые письма, которые они передают или получают, могут быть перехвачены или обманом отправлены защитниками Византии, у генералов нет надежных каналов связи друг с другом, чтобы координировать одновременные атаки.
Исследование
"Проблема византийских генералов", научная статья Лесли Лэмпорта, Роберта Шостака и Маршалла Пиза, была опубликована в 1982 году.
Хотя проблема византийских генералов изучалась в компьютерных науках до 1982 года, это была одна из первых попыток ее решения.
Пример
Несколько дивизий византийской армии размещены недалеко от вражеского города и готовы к войне. Единственный способ связи для разных генералов — это гонец, и генералы должны договориться о порядке действий.
Однако, некоторые генералы, стремящиеся помешать выработать единый порядок действий, являются предателями. Чтобы гарантировать, что крошечная группа предателей не сможет прервать связь, необходим алгоритм. Для решения проблемы, лояльным генералам необходимо безопасное средство для согласования плана, т.е. консенсус и средство для его выполнения, т.е. координация.
Решение проблемы византийских генералов является сложной задачей и затрагивает все типы компьютерных систем. Проблема византийских генералов не должна быть проблемой, если разрозненной группе узлов (компьютеров или серверов) необходимо обеспечивать надежную связь.
Понимание византийской отказоустойчивости (BFT)
Существует несколько причин, по которым распределенная компьютерная система может выйти из строя. В приведенном выше примере византийские сбои — это, по сути, предатели, пытающиеся прервать связь между верными генералами.
В реальных компьютерных системах это может быть дефект ПО, неисправность оборудования или злонамеренная атака. Говоря иначе, византийские сбои не всегда должны быть результатом хорошо скоординированных усилий злоумышленника. В распределенных сетях могут возникать трудности, мешающие узлам достичь консенсуса.
Любой сбой системы, который проявляет нетипичное поведение для разных наблюдателей, называется византийским сбоем. Он не содержит ограничений и конкретных характеристик относительно типа поведения, которое может демонстрировать узел (например, узел может генерировать произвольные данные, выдавая себя за честного участника). В каждой распределенной компьютерной системе византийские сбои практически неизбежны.
Представим, что происходит отключение электроэнергии и все узлы одновременно выходят из строя. Возникает вопрос, останется ли сеть работоспособной и способной поддерживать надежную связь? Или система в целом перестает работать или внезапно становится открытой для атак?
В достаточно безопасной сети такая незначительная вещь, как несколько отключенных узлов, не оказывает заметного влияния на сеть. Византийская отказоустойчивость — это способность защищаться от таких ситуаций. Считается, что сети, которые могут выдержать много византийских сбоев, имеют более высокую устойчивость, что подразумевает, что они более безопасны.
Фактическая частота возникновения и характер византийских сбоев в различных системах является обширной и сложной темой. Тем не менее, она может быть определена таким образом, чтобы появилось формальное определение византийской отказоустойчивости.
Стоит отметить, что византийские неисправности являются наиболее серьезными и трудно устранимыми. Византийская отказоустойчивость требуется на атомных электростанциях, в системах авиационных двигателей и практически в любой системе, действия которой зависят от результатов большого количества датчиков.
Проблема византийских генералов в распределенной системе
Только децентрализованные системы подвержены проблеме византийских генералов, поскольку у них нет центрального источника информации и нет возможности подтвердить информацию, которую они получают от других пользователей сети. В централизованных системах авторитетному узлу (участнику) доверяют распространять точную информацию, предотвращая при этом распространение ошибочной или мошеннической информации по сети.
Например, в традиционной финансовой системе банкам доверяют предоставлять клиентам точные балансы и истории операций. Если банк пытается обмануть или ввести в заблуждение своих потребителей, центральный банк или правительство начинают иметь вопросы к такому банку.
Проблема византийских генералов, которая непоследовательно требует установления истины, не решается централизованными системами. Вместо этого они предпочитают вообще не сталкиваться с этой проблемой, делая выбор в пользу эффективности, а не надежности. Но централизованные системы склонны к проблеме коррупции.
Пример проблемы византийских генералов
Примером проблемы византийских генералов могут служить деньги. Как общество может создать денежную систему, которой все члены могут доверять и с которой могут согласиться? На протяжении большей части истории общества использовали в качестве валюты драгоценные металлы или другие редкие предметы, такие как раковины или стеклянные бусины. Золото решило проблему византийских генералов, потому что ему доверяли и признавали в децентрализованных системах, таких как международная торговля.
Но вес и чистота золота остаются ненадежными до сих пор. Неспособность золота полностью решить проблему византийских генералов привела к тому, что созданием и выпуском денег занялись центральные банки Правительства монополизировали монетные дворы, чтобы внушить доверие к эмитируемой валюте. Но это не решило проблему византийских генералов. Чтобы решить ее, валюта должна быть общепринятой, проверяемой и устойчивой к подделкам.
Как решить проблему византийских генералов
Проблема может быть решена путем внедрения протокола, использующего механизмы отказоустойчивости. Когда вы сталкиваетесь с неопределенностью, заранее принятый порядок исполнения является наилучшим способом сделать выбор.
В результате выбор становится вероятностным, а не детерминированным, поскольку ничего нельзя гарантировать. Это именно тот случай, когда между участниками мало прямого общения, и каждый из них самодостаточен — каждый генерал находится на своей позиции, между ними существует физическое разделение.
Блокчейн: Решение проблемы Византийских генералов
Проблема византийских генералов может быть решена с помощью блокчейна. Речь идет о том, чтобы дать людям возможность безопасно и надежно общаться в непредсказуемом мире. В реальном мире большинство сделок происходит между незнакомыми людьми, которые не знают друг друга и не доверяют друг другу.
Каждый человек подобен генералу, ожидающему приказа атаковать или защищать свою позицию. Здесь нет посредников, которые могли бы от вашего имени решить, атаковать или защищать; вы полностью предоставлены сами себе в принятии решения.
Блокчейн создает уровень, которому можно доверять без необходимости доверять каждому человеку. Это достигается за счет того, что сеть узлов объединяется для согласования истины перед ее записью. Если генерал не уверен в сути сообщения, другие генералы могут проверить его, используя то, что они знают как истину.
После того как один узел записал сообщение, его копия отправляется всем остальным узлам сети, делая информацию дублированной. Алгоритм консенсуса PoW разработан для достижения этой цели. Плохие игроки все равно будут пытаться обмануть систему, потому что информация не всегда точна.
Поскольку система была разработана для использования широкой общественностью, в блокчейне предусмотрены механизмы отказоустойчивости и безопасности. В данном сценарии криптография была необходима, чтобы гарантировать, что сообщения не могут быть изменены.
Система предоставляет пары ключей цифровой подписи сообщения с целью проверки подписанта для доказательства того, что оно исходит от тех, которые его отправили. После проверки подлинности сообщения записываются для обеспечения прозрачности и будущей подотчетности.
Как Биткоин решает проблему византийских генералов
Что касается криптовалют, то Биткоин стал первым реализованным решением проблемы византийских генералов. Многие проекты до Биткоина пытались создать виртуальные деньги, независимые от банков, но все они в той или иной степени потерпели неудачу.
Биткоину как платежной системе необходимы ресурсы для обработки передачи прав собственности и предотвращения двойных трат. Биткоин использует блокчейн, или публичную распределенную бухгалтерскую книгу, которая хранит историю всех транзакций для достижения этой цели без требования доверия получателя к отправителю и отправителя к получателю. Блокчейн, по аналогии с византийскими генералами, — это истина, с которой должны согласиться все стороны.
Если бы все узлы сети Биткоин смогли договориться о том, какие транзакции когда и в каком порядке происходили, они могли бы проверить право собственности на Биткоин и создать работающую, не требующую доверия платежную систему без необходимости в централизованном органе управления.
Proof-of-Work (PoW) и проблема византийских генералов
Сатоши Накамото выпустил первый документ по Биткоину в октябре 2008 года. Хотя название "проблема византийских генералов" не используется в этом документе, Накамото фактически предложил решение, которое было реализовано в январе 2009 года с внедрением сети Bitcoin.
Сатоши разработал способ использования криптографической безопасности и шифрования с открытым ключом для решения проблемы византийских генералов в цифровой электронной сети. Для предотвращения фальсификации данных криптографическая безопасность использует хэширование — процесс кодирования. Участник сети проверяется с помощью шифрования открытым ключом.
Транзакция закрепляется в блоке, который в криптографически связан с другими блоками своим хэш-значением. Все хэши могут быть отслежены до корня всех хэшей, которым является Генезис-блок — начальный блок. Блокчейн — это система, которая использует дерево Меркла для проверки хэшей, происходящих от начального блока.
Каждый блок в сети, который происходит от первого блока, является действительным. Майнеры, которые проверяют блоки, соревнуются между собой в решении криптографических головоломок для производства блоков в рамках метода консенсуса PoW.
Используя механизм консенсуса по принципу "доказательство работы", Биткоин преодолел проблему византийских генералов и создал четкий, объективный свод правил для блокчейна. Чтобы добавить в блокчейн информацию, называемую блоками, участник сети должен опубликовать доказательство того, что он приложил много усилий для создания этого блока. Эта работа обходится создателю в высокую цену, что стимулирует его делиться точной информацией.
В сети Биткоин не может быть разногласий или фальсификации информации, потому что правила объективны. Система отбора тех, кто может майнить новые Биткоины, и законы, регулирующие, какие транзакции являются валидными, а какие нет, тоже являются объективными. Кроме того, невозможно удалить блок из блокчейна после его добавления, что делает историю Биткоина неизменной.
Поэтому проблема византийских генералов решается майнерами, которые подобны генералам в версии блокчейна Сатоши. Каждый узел отвечает за проверку транзакций, которые похожи на сообщения, доставляемые гонцами. Врагом можно считать плохих игроков (например, хакеров), которые стремятся украсть сообщения или нанести вред сети.
Хакеры не могут легко атаковать блокчейн, поскольку сообщения используют криптографическую защиту. Чтобы предотвратить манипуляции, сообщения или транзакции объединяются в блоки и хэшируются для дополнительной защиты. Сатоши сделал все более вероятностным, заставив майнеров соревноваться за подтверждение блоков. Это делает систему более децентрализованной. Ни один майнер не может получить все вознаграждения, монополизировав проверку.
Майнерам приходится соревноваться в нахождении блоков, используя свою вычислительную мощность, известную как хэшрейт. Чем выше хэшрейт майнера, тем больше вероятность того, что он подтвердит блок. Когда майнер, решивший задачу, передает решение в сеть, все остальные майнеры должны подтвердить его или опровергнуть, если оно ошибочно. Цель сложности — это значение, которое должно быть равно или меньше правильного значения.
Участники сети Биткоин могут в любой момент согласовать состояние блокчейна и все транзакции в блокчейне. Каждый узел проверяет, являются ли блоки действительными в соответствии с критерием proof-of-work и действительны ли транзакции в соответствии с дополнительными критериями.
Если участник сети попытается передать недостоверную информацию, все узлы сети определят ее как объективно недостоверную и проигнорируют. Нет необходимости доверять другим участникам сети Биткойн "на слово", поскольку каждый узел может сам проверить любую информацию в сети, что делает Биткоин системой не требующей доверия, т.е. открытой и проверяемой.
Блокчейн децентрализован, что означает, что у системы нет единой точки отказа. Блоки сохраняются в распределенной базе данных, которая реплицируется по всей сети. Такая избыточность также способствует отказоустойчивости, гарантируя, что ни один неисправный компьютер не сможет вывести из строя всю систему. Это эквивалентно наличию множества "генеральских гонцов" на случай, если один из них попадет в засаду врага. Сообщение не будет потеряно, поскольку его скопируют другие гонцы.
Proof-of-stake (PoS) и Delegated proof-of-stake (DPoS)
PoS — это еще один механизм консенсуса блокчейна, направленный на решение проблемы византийских генералов. Впервые он был развернут в 2012 году. Сети на основе PoS, в отличие от сетей на основе PoW, не зависят от майнеров. Вместо этого используется техника, называемая стейкингом.
Пользователи (называемые валидаторами) накапливают стейки в такой системе. Валидаторы, владеющие большим количеством монет в блокчейне (стейком или долей), могут подтвердить большее количество блоков и получить большее вознаграждение. Пользователи, которые пытаются подтвердить неверные транзакции, рискуют потерять свои монеты.
Пользователи могут держать монеты в обычных кошельках, вместо того чтобы использовать специализированные машины для майнинга. В некоторых сетях на основе PoS были созданы способы предотвращения атак с двойным расходованием средств и других потенциальных уязвимостей безопасности, вызванных византийскими сбоями. Например, в Ethereum 2.0 (Serenity) использует алгоритм Casper PoS, который требует, чтобы две трети узлов согласились с блоком, прежде чем он будет создан.
Delegated Proof-of-Stake (DPoS) — это метод консенсуса в блокчейне, который работает аналогично Proof-of-Stake (POS) и был впервые разработан в 2014 году. Оба метода требуют, чтобы пользователи стейкали монеты, но в в сетях на основе DPoS только некоторые пользователи (называемые делегаты) могут подтверждать транзакции и генерировать блоки.
В целом, любой пользователь может стейкать монеты блокчейна, чтобы проголосовать в поддержку кандидата-делегата. Вознаграждение за блок обычно распределяется пропорционально количеству монет, использованных за делегатов, среди своих делегаторов.
Ноды могут достичь консенсуса значительно быстрее при использовании DPoS, чем при PoW или PoS. В масштабе это означает, что транзакции могут обрабатываться значительно быстрее. Поддержание высокого уровня византийской отказоустойчивости с помощью DPoS может стать проблематичным в некоторых случаях из-за компромисса.
Поскольку за безопасность сети отвечает меньшее количество узлов, нодам потенциально проще вступить в сговор против интересов большинства. Сети на основе DPoS пытаются избежать этого сценария, регулярно проводя перевыборы делегатов, чтобы гарантировать, что делегаты несут ответственность за свои решения.