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

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

Формулировка задачи

Первое упоминание проблемы византийских генералов появилось в 1982 году в статье Лесли Лэмпорта. Речь в ней идет о классическом примере из истории феодальных отношений, а именно — о Византии. Есть несколько генералов, которые не подчиняются друг другу. Они берут в осаду город. Генералам необходимо прийти к единому решению: вместе атаковать этот город, чтобы победить, или вместе отступить, чтобы сохранить войска. Если же некоторые из них начнут атаковать, а другие решат отступать, то противник разгромит всю армию по частям, и все генералы потерпят поражение. Им необходимо договориться, но при этом у них отсутствует надежный канал коммуникации между собой. Они могут отправлять друг другу гонцов, но враг может перехватывать гонцов, чтобы подменить сообщение. Следовательно, генералы не могут быть уверены в доставке информации и ее подлинности. В таких условиях им и необходимо прийти к общему решению: вместе атаковать или отступать.

Это наглядный пример для описания технических систем, в которых есть несколько компонентов, выполняющих общее резервирование. Какие-то компоненты могут быть сбойными. Если речь идет о сбоях, когда компонент просто отключается, то это называется Crash fault tolerance (CFT). Если же компонент продолжает работать, но при этом генерирует произвольные сообщения, которые считываются как нормальные и могут приниматься для работы в общей системе, то в этом случае мы получаем BFT-протоколы (Byzantine fault tolerance) — протоколы, стойкие к такому классу сбоев.

Протокол консенсуса Сатоши Накамото

При разработке биткоина Сатоши Накамото удачно объединил решения, которые были известны до него. Он объединил PoW (Proof-of-work) с решениями из децентрализованных систем и пришел к достаточно простому интуитивному протоколу, который до него не существовал. Это и является существенным новшеством биткоина.

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

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

Формулировки требований

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

Начнем со строгой. Задача византийских генералов должна быть решена в условиях, когда участники протокола обмениваются сообщениями, но при этом нет никакого лимита на время доставки этих сообщений, то есть сообщения могут быть потеряны с некоторой вероятностью или доставка может затянуться на очень длительный срок. Такая сеть называется асинхронной. В этих условиях работают BFT-протоколы. Среди них, например, pBFT, Honey Badger, Algorand, Hashgraph. Все эти протоколы соответствуют строгим требованиям BFT. Они работают в асинхронных сетях (за исключением Algorand — там требуется некоторое ограничение асинхронности). Их главное свойство выражается в том, что если эти протоколы уже пришли к некоторым решениям (построили цепочку блоков), то это решение невозможно отменить: система пришла и история становится неизменяемой.

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

Практическое решение

Решение задачи византийских генералов позволяет построить децентрализованную систему без какой-либо доверенной стороны, которая будет работать с высокой надежностью. Здесь мы получаем набор компонентов, которые взаимодействуют между собой по некоторому формализованному протоколу, и эти компоненты приходят к единому решению независимо от того, каким образом ведут себя сбойные компоненты. То есть в технической системе не важно, каким образом и какие сообщения посылают сбойные узлы, главное, чтобы их было меньше ⅔, если речь идет о строгих BFT-требованиях. Если мы говорим о криптовалютах, то мы можем построить полностью децентрализованную систему. Часть узлов могут быть сбойными, часть сети может отключаться какими-либо административными средствами, но сеть будет функционировать постоянно. Нет какой-либо одной или нескольких точек, отключив которые можно полностью блокировать сеть.

Влияние на современные платежные системы

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

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

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

Значение для экономики и общества

Это действительно революционный продукт, и некоторые специалисты связывают его с появлением стека протоколов TCP/IP, позволившего в 1980-е годы построить децентрализованную сеть, которую мы сейчас называем интернетом. Проводя аналогии с тем, что предложил в свое время Сатоши, такое же решение на более высоком уровне позволит построить децентрализованные организации.

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

Оцените статью
Добавить комментарий