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

Задача

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

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

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

Ситуация простая – все элементы друг другу доверяют по умолчанию, но что делать, если некоторые из них ошибаются, а другие – заведомо предоставляют ложную информацию? Как в такой ситуации принять общее «коллегиальное» решение? Данная задача носит название «Проблемы Византийских Генералов», а её решение лежит в основе устойчивостей P2P сетей.

Суть задачи

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

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

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

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

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

Византийская отказоустойчивость

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

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

Алгоритмы консенсуса

На данный момент, используются два основных алгоритма консенсуса - Proof of Work (PoW) и Proof of Stake (PoS). В первой ситуации гарантом достоверности является проделанная вычислительная работа, которую может перепроверить любой другой участник сети. Во второй – определённый денежный вклад и дальнейшая возможность гаранта вообще участвовать в процессе. В наиболее популярной на данный момент криптовалюте – Bitcoin – применяется алгоритм консенсуса Proof of Work).

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

Вывод

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

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

Лучший способ вывести криптовалюты гривну!

Подробнее